Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

• Auto
• Light
• Dark

Algorand Specifications

A State Proof message for rounds (X⋅δSP,…,(X+1)⋅δSP](X⋅δSP,…,(X+1)⋅δSP]
for some number XX, contains the following components:

• Light block headers commitment for rounds (X⋅δSP,…,(X+1)⋅δSP](X⋅δSP,…,(X+1)⋅δSP], under msgpack key b.

• First attested round which would be equal to X⋅δSP+1X⋅δSP+1, under msgpack key f.

• Last attested round which would be equal to (X+1)⋅δSP(X+1)⋅δSP, under msgpack key l.

• Participant commitment used to verify state proof for rounds ((X+1)⋅δSP,…,(X+2)⋅δSP]((X+1)⋅δSP,…,(X+2)⋅δSP], under msgpack key v.

• The value ln(ProvenWeight)ln⁡(ProvenWeight) with 1616 bits of precision that would be used to verify State Proof for rounds ((X+1)⋅δSP,…,(X+2)⋅δSP]((X+1)⋅δSP,…,(X+2)⋅δSP], under msgpack key P. This field is calculated based on the total weight of the participants see state-proof-transaction

Each block header keeps track of the state needed to construct, validate, and record State Proofs.

This tracking data is stored in a map under the msgpack key spt in the block header. The type of the State Proof indexes the map; at the moment, only type 00 is supported. In the future, other types of state proofs might be added.

For type 00:

• KQSP=256KQSP=256,
• fSP=232×30100fSP=232×30100 (as the fraction numerator out of 232232),
• NSP=1024NSP=1024,
• δSP=256δSP=256,
• δSP,b=16δSP,b=16.

The value of the tracking data is a msgpack map with three elements:

• Under key n, the next expected round of a State Proof should be formed. When upgrading from an earlier consensus protocol to a protocol that supports State Proofs, the n field is set to the lowest value such that n is a multiple of δSPδSP and so that the n is at least the first round of the new protocol (supporting State Proofs) plus δSP,b+δSPδSP,b+δSP. This field is set in every block.

• Under key v, the root of the vector commitment to an array of participants that are eligible to vote in the State Proof at round δSPδSP from the current block. Only blocks whose round number is a multiple of δSPδSP have a non-zero v field.

• Under key t, the total online stake at round δSPδSP (with pending rewards).

The participants committed to by the vector commitment are chosen in a specific fashion:

• First off, because it takes some time to collect all of the online participants (more than the target assembly time for a block), the set of participants and total online non-expired stake appearing in a commitment in block at round rr are actually based on the account state from round r−δSP,br−δSP,b.

• The participants are sorted by the number of μALGO they currently hold (including any pending rewards). This enables more compact proofs of pseudorandomly chosen participants weighted by their μALGO holdings. Only accounts in the online state are included in this list of participants.

• To limit the worst-case size of this vector commitment, the array of participants contains just the top NSPNSP participants. Efficiently computing the top NSPNSP accounts by their μALGO balance is difficult in the presence of pending rewards. Thus, to make this top-NSPNSP calculation more efficient, we choose the top accounts based on a normalized balance, denoted below by nInI.

The normalized balance is a hypothetical balance: consider an account II with current balance aIaI. If an account had a balance nInI in the genesis block, and did not perform any transactions since then, then its balance by the current round (when rewards are included) will be aIaI, except perhaps due to rounding effects.

In more detail, let r∗IrI∗ be the last round in which a transaction touched account II (and therefore all pending rewards were added to it). Consider the following quantities, as defined in the Account State:

• The raw balance aIaI of the account II at round r∗IrI∗ is its total balance on that round.

• The rewards base a′IaI′ is meant to capture the total rewards allocated to all accounts up to round r∗IrI∗, expressed as a fraction of the total stake (with limited precision as described below).

Given these two quantities, the normalized balance of an online account II is aI(1+a′I)aI(1+aI′).

Important

EXAMPLE:

For example, if the total amount of rewards distributed up to round r∗IrI∗ is 20%20% of the total stake, then the normalized balance is aI1.2aI1.2.

To limit the required precision in this calculation, the system uses a parameter UrUr that specifies the rewards-earning unit, namely, accounts only earn rewards for a whole number of UrUr μALGO. (Currently Ur=1,000,000Ur=1,000,000, so the rewards-earning unit is 11 ALGO.)

The parameter a′IaI′ above is an integer such that a′IUraI′Ur is the desired fraction, rounded down to the precision of 1Ur1Ur.

The normalized balance is computed as:

nI=⌊aI⋅Ur(a′I+Ur)⌋.nI=⌊aI⋅Ur(aI′+Ur)⌋.

• To limit the resources allocated for creating State Proofs, State Proof parameters are set to NSP=1024NSP=1024, δSP=256δSP=256, and δSP,b=16δSP,b=16.

• Setting KQSP=targetPQKQSP=targetPQ to achieve post-quantum security for State Proofs. For further details, refer to the State Proofs [normative\

• specification](../crypto/crypto-state-proofs.md).

• Algorand assumes that at least 70%70% of the participating stake is honest. Under this assumption, there can’t be a malicious State Proof that the verifier would accept and have a signed weight of more than 30%30% of the total online stake. Hence, we set fSP=232×30100fSP=232×30100 (as the numerator of a fraction out of 232232).