Post-quantum aggregatable signatures for the beam chain

Dmitry Khovratovich (Ethereum Foundation)

(joint work with J. Drake, B. Wagner, and M. Kudinov)

Ethereum consensus

1. Producers create blocks
2. Blocks get signed by validators
3. Signatures are aggregated

Current solution

1. BLS signatures are sent to aggregator in groups of 512.
2. Aggregators publish aggregated signatures (a linear combination)
3. 1024 agg-signatures are published.

​

Thanks to Orbit, we will organize 8K-16K validators per slot.

Quantum breaks

1. BLS signatures are elliptic-curve based and succumb to quantum attacks
2. All EC-based SNARK constructions also fail as aggregations

Beam chain view

1. Validators sign with a post-quantum signatures.
2. They are all sent to aggregators (with redundancy).
3. Aggregators employ a post-quantum SNARK to create aggregated signatures

​

Post-quantum possibilities

PQ signatures:

1. Lattice-based signatures
2. Hash-based signatures
3. MQ signatures

PQ aggregation.

1. Plain collection
2. Lattice custom aggregators
3. PQ proofs (Stark, GKR) and PQ commitments (FRI, Binius)

Hash-based signatures

1. Simple construction
2. Small size
3. Simple assumptions
4. Standard model proofs

Contra:

1. For efficient aggregation we need rather new hashes.
2. The quantum and classical security less studied

One-time signature: Winternitz

1. Create v hash chains of length 2^w.
2. Public key is a hash of chain ends

​

This can sign 5⁵ messages

One-time signature: (Target Sum)-Winternitz

• Create v hash chains of length W.
• Public key is a hash of chain ends
• To sign a message, interpret it as an integer base-W and publish chain entries.
• Allow only messages with sum of positions equal to T~vW/2.
• Verification cost: vW/2 chain hashes and a public key hash.
• In real schemes W is a power of 2.

This is a signature of message (3,2,3,0,3)

Stateful hash-based signature: XMSS

1. Merkle tree over Winternitz public keys.
2. All leafs are enumerated: slots. One pk per slot.
3. Convenient when all signatures are enumerated.

Stateless hash-based signatures: SPHINCS

If stateless signatures are needed, the constructions are much more complicated:

1. Several trees
2. Many-time signatures in between.

Selecting parameters

1. We need to supply additional inputs into each hashing call
1. P - user-unique
2. T - position-unique
2. Sizes of P, T, and hash outputs are taken to closely match provable bounds.
3. Hash function - SHA-3 or Poseidon

​

Candidate construction

1. Poseidon for hashing
2. Lifetime of 2²⁰ slots
3. Chain length 2^w for some w in {2,4,8}.
4. Total v chains, with v~155/w, plus checksum chains

​

Key generation

1. For each slot generate v chains of length 2^w and hash the outputs into a tree.
2. Publish the root.

Generate with PRNG

Signature generation

1. Find R such H(P,T,M,R) has checksum T.
2. Produce the chain positions.
3. Add chain entries to the signature.
4. Produce a Merkle proof for the given slot.

Parameters for Poseidon

Most interesting instances:

Parameters for Poseidon

One example:

• Chains of length 4
• Total 78 chains
• Target sum of indices : 129
• Chain hash is Babybear-Poseidon2-16 with 7-word output
• Merkle and public key hash are wider Poseidons
• Lifetime 11 days => tree with 2¹⁸ entries
• Total signature size: (78+18)*7 words

Reference implementations

https://github.com/b-wagn/hash-sig

Concrete parameter values:

https://github.com/b-wagn/hash-sig/blob/main/src/signature/generalized_xmss/instantiations_poseidon.rs

​

Aggregation circuit