## 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

Algorand achieves [forward security](https://en.wikipedia.org/wiki/Forward_secrecy) using a _Merkle Signature Scheme_. This scheme consists of using a different _ephemeral_ _key_ for each round in which it will be used. The scheme uses _vector commitment_ to generate commitment to those keys.

The private key **MUST** be deleted after the round passes to achieve complete forward secrecy.

> This is analogous to the scheme discussed in the [voting keys section](https://specs.algorand.co/keys/keys-participation).

The Merkle scheme uses [FALCON](https://falcon-sign.info/) scheme as the underlying digital signature algorithm.

> For further details on FALCON scheme, refer to the Cryptography primitives [specification](https://specs.algorand.co/crypto/crypto#falcon).

The tree’s depth is bound to 1616 to bound verification paths on the tree. Hence, the maximum number of keys which can be created is at most 216216.

> Important
>
> **IMPLEMENTATION:**
>
> Merkle signature scheme [reference implementation](https://github.com/algorand/go-algorand/blob/b6e5bcadf0ad3861d4805c51cbf3f695c38a93b7/crypto/merklesignature/merkleSignatureScheme.go).

The scheme generates multiple keys for the entire participation period. Given FirstValidRound, LastValidRound and a KeyLifeTime, a key is generated for each round r that holds:

FirstValidRound≤r≤LastValidRound∧rmodKeyLifeTime=0

Currently, KeyLifeTime=256 rounds.

After generating the public keys, the scheme creates a vector commitment using the keys as leaves.

Leaf hashing is done in the following manner:

leafi=Hash(“KP”\|\|SchemeID\|\|r\|\|Pki), for each corresponding round.

Where:

- SchemeID is a 16-bit, little-endian constant integer with value of 00.

- r is a 64-bit, little-endian integer representing the start round for which the key Pki is valid. The key would be valid for all rounds in \[r,…,r+KeyLifeTime−1\].

- Pki is a 14,344-bit string representing the FALCON ephemeral public key.

- Hash is the SUBSET-SUM hash function as defined in the [Cryptographic Primitives Specification](https://specs.algorand.co/crypto/crypto).

A _signature_ in the scheme consists of the following elements:

- Signature is a signature generated with the FALCON scheme.

- VerifyingKey is a FALCON ephemeral public key.

- VectorIndex is an index of the ephemeral public key leaf in the vector commitment.

- Proof is an array of size n (n≤16 since the number of keys is bounded) which contains hash results (Digest0,…,Digestn). Proof is used as a Merkle verification path on the ephemeral public key.

When the _committer_ gives a n-depth authentication path for index VectorIndex, the _verifier_ must write VectorIndex as n-bit number and read it from MSB to LSB to determine the leaf-to-root path.

When signature is to be hashed, it must be serialized into a binary string according to the following format:

SignatureBitString=(SchemeID\|\|Signature\|\|VerifyingKey\|\|VectorIndex\|\|Proof)

Where:

- SchemeID is a 16-bit, little-endian constant integer with value of 00.

- Signature is a 12,304-bit string representing a FALCON signature in a CT format.

- VerifyingKey is a 14,344-bit string.

- VectorIndex is a 64-bit, little-endian integer.

- Proof is constructed in the following way:
  - if n=16:
    Proof=(n\|\|Digest0\|\|…\|\|Digest15)
  - else:
    Proof=(n\|\|ZeroDigest0\|\|…\|\|ZeroDigestd−1\|\|Digest0\|\|…\|\|Digestn−1)

Where:

- n is a 8-bit string.

- Digest is a 512-bit string representing sumhash result.

- ZeroDigest is a constant 512-bit string with value 00.

- d=16−n

A signature s for a message m at round r is valid under the public commitment pk and KeyLifeTime if:

- The FALCON signature s.Signature is valid for the message m under the public key s.VerifyingKey

- The proof s.Proof is a valid vector commitment proof for the entry Leaf at index s.VectorIndex with respect to the vector commitment root pk where:
  - Leaf:=“KP”\|\|SchemeID\|\|Round\|\|s.VerifyingKey,
  - Round:=r−(r mod KeyLifeTime).