## 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](https://eprint.iacr.org/archive/2020/1568/20210330:194331)
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](https://specs.algorand.co/crypto/crypto-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](https://eprint.iacr.org/archive/2020/1568/20210330:194331).

- SerializedMerkleSignatureSerializedMerkleSignature representing a Merkle Signature of the participant
[merkle signature binary representation](https://specs.algorand.co/keys/keys-state-proof#signatures)

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 separator](https://specs.algorand.co/crypto/crypto-domain-separators)`MB` (the bottom leaf).

As described in the [technical report](https://eprint.iacr.org/archive/2020/1568/20210330:194331)
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](https://specs.algorand.co/crypto/crypto-state-proofs#participant-commitment),
    under the msgpack key `p`.
  
  - The signature information, encoded as described [above](https://specs.algorand.co/crypto/crypto-state-proofs#signature-format),
    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](https://eprint.iacr.org/archive/2020/1568/20210330:194331),
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](https://specs.algorand.co/_archive/dev/cryptographic-specs/weight-thresh.pdf)
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](https://eprint.iacr.org/archive/2020/1568/20210330:194331),
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](https://eprint.iacr.org/archive/2020/1568/20210330:194331)).
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](https://specs.algorand.co/_archive/dev/cryptographic-specs/weight-thresh.pdf)
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](https://specs.algorand.co/_archive/dev/cryptographic-specs/weight-thresh.pdf))
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.