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

The Merkle scheme uses FALCON scheme as the underlying digital signature algorithm.

For further details on FALCON scheme, refer to the Cryptography primitives specification.

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.

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.

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).