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

State Proofs (a.k.a. Compact Certificates) allow external parties to efficiently validate Algorand blocks.

The technical report provides the overall approach of State Proofs; this section describes the specific details of how State Proofs are realized in Algorand.

As a brief summary of the technical report, State Proofs operate in three steps:

1. The first step is to commit to a set of participants eligible to produce signatures, along with a weight for each participant. In Algorand’s case, these end up being the online accounts, and the weights are the account μALGO balances.

2. The second step is for each participant to sign the same message, and broadcast this signature to others. In Algorand’s case, the message would contain a commitment on blocks in a specific period.

3. The third step is for Relay Nodes to collect these signatures from a significant fraction of participants (by weight) and generate a State Proof. Given enough signatures, a Relay Node can form a State Proof, which effectively consists of a small number of signatures, pseudo-randomly chosen out of all the signatures.

The resulting State Proof proves that at least some ProvenWeightProvenWeight of participants have signed the message. The actual weight of all participants who have signed the message must be greater than ProvenWeightProvenWeight.

The State Proof scheme requires a commitment to a dense array of participants, in some well-defined order. Algorand uses Vector Commitment to guarantee this property.

Leaf hashing is done in the following manner:

Leaf=Hash(spp||Weight||KeyLifeTime||StateProofpk),Leaf=Hash(spp||Weight||KeyLifeTime||StateProofpk),

for each online participant.

Where:

• WeightWeight is a 64-bit, little-endian integer representing the participant’s balance in μALGO,

• KeyLifeTimeKeyLifeTime is a 64-bit, little-endian constant integer with value of 256256,

• StateProofpkStateProofpk is a 512-bit string representing the participant’s Merkle signature scheme commitment.

Similarly to the participant commitment, the State Proof scheme requires a commitment to a signature array.

Leaf hashing is done in the following manner:

Leaf=Hash(sps||L||SerializedMerkleSignature),Leaf=Hash(sps||L||SerializedMerkleSignature),

for each online participant.

Where:

• LL is a 64-bit, little-endian integer representing the participant’s LL value as described in the technical report.

• SerializedMerkleSignatureSerializedMerkleSignature representing a Merkle Signature of the participant merkle signature binary representation

When a signature is missing in the signature array, i.e., the prover didn’t receive a signature for this slot, the slot would be decoded as an empty string. As a result, the vector commitment leaf of this slot would be the hash value of the constant domain separatorMB (the bottom leaf).

As described in the technical report section IV.A, a State Proof contains a pseudorandomly chosen set of signatures. The choice is made using a coin.

In Algorand’s implementation, the coin derivation is made in the following manner:

Hin=(spc||Version||ParticipantCommitment||ln(ProvenWeight)||SignatureCommitment||SignedWeight||StateProofMessageHash)Hin=(spc||Version||ParticipantCommitment||ln⁡(ProvenWeight)||SignatureCommitment||SignedWeight||StateProofMessageHash)

Where:

• VersionVersion is an 8-bit constant with value of 00,

• ParticipantCommitmentParticipantCommitment is a 512-bit string representing the vector commitment root on the participant array’

• ln(ProvenWeight)ln⁡(ProvenWeight) an 8-bit string representing the natural logarithm value of ProvenWeightProvenWeight with 16 bits of precision, as described in [SNARK-Friendly
  Weight Threshold Verification](https://specs.algorand.co/_archive/dev/cryptographic-specs/weight-thresh.pdf),

• SignatureCommitmentSignatureCommitment is a 512-bit string representing the vector commitment root on the signature array,

• SignedWeightSignedWeight is a 64-bit, little-endian integer representing the State Proof signed weight,

• StateProofMessageHashStateProofMessageHash is a 256-bit string representing the message that the State Proof would verify (it would be the hash result of the State Proof message).

For short, we refer below to the revealed signatures simply as “reveals”.

We compute:

R=SHAKE256(Hin)R=SHAKE256(Hin)

Then, for every reveal, we:

• Extract a 64-bit string from RR,

• Use rejection sampling and extract an additional 64-bit string from RR if needed.

This would guarantee a uniform random coin in [0,SignedWeight)[0,SignedWeight).

A State Proof consists of seven fields:

• The Vector Commitment root to the array of signatures, under the msgpack key c.

• The total weight of all signers whose signatures appear in the array of signatures, under the msgpack key w.

• The Vector commitment proof for the signatures revealed above, under the msgpack key S.

• The Vector commitment proof for the participants revealed above, under the msgpack key P.

• The FALCON signature salt version, under the msgpack key v, is the expected salt version of every signature in the state proof.

• The set of revealed signatures, chosen as described in section IV.A of the [technical
  report](https://eprint.iacr.org/archive/2020/1568/20210330:194331), under the msgpack key r. This set is stored as a msgpack map. The key of the map is the position in the array of the participant whose signature is being revealed. The value in the map is a msgpack struct with the following fields:

  • The participant information, encoded as described above, under the msgpack key p.

  • The signature information, encoded as described above, under the msgpack key s.

• A sequence of positions, under the msgpack key pr. The sequence defines the order of the participant whose signature is being revealed. Example:

PositionsToReveal=[IntToInd(coin0),…,IntToInd(coinNumReveals−1)]PositionsToReveal=[IntToInd(coin0),…,IntToInd(coinNumReveals−1)]

Where IntToIndIntToInd and NumRevealsNumReveals are defined in the technical report, section IV.

Note that, although the State Proof contains a commitment to the signatures, it does not contain a commitment to the participants.

The set of participants must already be known to verify a State Proof. In practice, a commitment to the participants is stored in the Block Header of an earlier block, and in the State Proof message proven by the previous State Proof.

A State Proof is valid for the message hash, with respect to a commitment to the array of participants, if:

• The depth of the vector commitment for the signature and the participant information should be less than or equal to 2020,

• All FALCON signatures should have the same salt version, and it should be equal to the salt version specified in the State Proof,

• The number of reveals in the State Proof should be less than or equal to 640640,

• Using the trusted ProvenWeightProvenWeight (supplied by the verifier), the State Proof should pass the SNARK-Friendly Weight Threshold Verification check.

• All of the participant and signature information that appears in the reveals is validated by the Vector Commitment proofs for the participants (against the commitment to participants, supplied by the verifier) and signatures (against the commitment in the state proof itself), respectively.

• All the signatures are valid signatures for the message hash.

• For every i∈{0,…,NumReveals−1}i∈{0,…,NumReveals−1} there is a reveal in map denoted by riri, where ri←T[PositionsToReveal[i]]ri←T[PositionsToReveal[i]] and ri.Sig.L≤coini<ri.Sig.L+ri.Part.Weightri.Sig.L≤coini<ri.Sig.L+ri.Part.Weight.

TT is defined in the technical report, section IV.

• targetCtargetC: “classical” security strength. This is set to k+qk+q (where k+qk+q are defined in section IV.A of the technical report). The goal is to have <=1/2k<=1/2k probability of breaking the State Proof by an attacker that makes up to 2q2q hash evaluations/queries. We use targetC=192targetC=192, which corresponds to, for example, (k=128,q=64)(k=128,q=64), or (k=96,q=96)(k=96,q=96).

• targetPQtargetPQ: “post-quantum” security strength. This is set to k+2qk+2q, because at a cost of about 2q2q, a quantum attacker can search among up to 22q22q hash evaluations (this is a highly attacker-favorable estimate). We use targetPQ=256targetPQ=256, which corresponds to, for example, (k=128,q=64)(k=128,q=64), or (k=96,q=80)(k=96,q=80).

In order for the SNARK prover for State Proofs to be efficient enough, we must impose an upper-bound MaxRevealsCMaxRevealsC on the number of “reveals” the State Proof can contain, while still reaching its target security strength targetC=192targetC=192. Concretely, we currently wish to set MaxRevealsC=480MaxRevealsC=480.

Similarly, the quantum-secure verifier aims for a larger security strength of targetPQ=256targetPQ=256, and we can also impose an upper-bound MaxRevealsPQMaxRevealsPQ on the number of reveals it can handle. (Recall that a smaller number of reveals means that SignedWeightProvenWeightSignedWeightProvenWeight must be larger to reach particular security strength, so we cannot set MaxRevealsCMaxRevealsC or MaxRevealsPQMaxRevealsPQ too low.)

To generate a SNARK proof, we need to be able to “downgrade” a valid State Proof with targetPQtargetPQ strength into one with merely targetCtargetC strength, by truncating some of the reveals to stay within the bounds.

First, let us prove that a valid State Proof with (( NRev_{PQ} ) number of reveals that satisfies Equation (5) in SNARK-Friendly Weight Threshold Verification for a given targetCtargetC can be “downgrade” to have:

NumRevealsC=ceil(NumRevealsPQ×targetCtargetPQ)NumRevealsC=ceil(NumRevealsPQ×targetCtargetPQ)

We remark that values d,b,T,Y,Dd,b,T,Y,D (in SNARK-Friendly Weight Threshold Verification) only depend on SignedWeightSignedWeight, but not the number of reveals nor the target.

Hence, we just need to prove that:

NumRevealsC>=targetC×T×YDNumRevealsC>=targetC×T×YD

Which implies it is sufficient to prove:

NumRevealsPQ×targetCtargetPQ>=targetC×T×YDNumRevealsPQ×targetCtargetPQ>=targetC×T×YD

Since targetC>0targetC>0 and targetPQ>0targetPQ>0, we just need to prove that:

NumRevealsPQ>=targetPQ×T×YD.NumRevealsPQ>=targetPQ×T×YD.

This last inequality holds since the State Proof satisfies Equation (5).

For a given MaxRevealsCMaxRevealsC and the desired security strengths, we need to calculate a suitable targetPQtargetPQ bound so that the following property holds:

Since the “downgraded“ State Proof has:

NumRevealsC=ceil(NumRevealsPQ×targetCtargetPQ),NumRevealsC=ceil(NumRevealsPQ×targetCtargetPQ),

And NumRevealsPQ<=MaxRevealsPQNumRevealsPQ<=MaxRevealsPQ, and NumRevealsC<=MaxRevealsCNumRevealsC<=MaxRevealsC we get:

MaxRevealsC<=ceil(MaxRevealsPQ×targetCtargetPQ)MaxRevealsC<=ceil(MaxRevealsPQ×targetCtargetPQ)

And we can set

MaxRevealsC<=ceil(MaxRevealsPQ×targetCtargetPQ)MaxRevealsC<=ceil(MaxRevealsPQ×targetCtargetPQ)

Since reveals do not bottleneck the quantum-secure verifier, we can take:

MaxRevealsPQ<=floor(MaxRevealsC×targetPQtargetC)MaxRevealsPQ<=floor(MaxRevealsC×targetPQtargetC)

To be an equality, i.e., MaxRevealsPQ=floor(…)MaxRevealsPQ=floor(…).

Therefore, we must set MaxRevealsPQ=640MaxRevealsPQ=640.