Goals
- Quick Recap on Hash-Based One-Time Signature Schemes
- Explain how Hash-Based Multi-Signature Schemes work
- Show how Hash-Based Multi-Signatures will* be used in the Beam Chain
- Talk about tradeoffs / parameter selection
1st Presentation
Why?
BLS Signatures which are used in Ethereum's PoS consensus are based on Elliptic Curve Cryptography which isn't Post-Quantum Secure.
Current State
- Producer creates Block
- Validators sign Block via BLS
- Aggregators aggregate signatures via BLS Signature Aggregation
Desired State
- Producer creates Block
- Validators sign Block with Post-Quantum Signature Scheme
- Aggregators aggregate signatures with Post-Quantum SNARK
Winternitz-OTS Recap
Cryptographic Hash Function Recap
- Any output of \(H\) looks random
- \(H\) maps an arbitrary-length input \(m\) to a fixed-length output \(h\)
- An \(m\) always maps to the same \(h\)
- Given \(m\), it's easy to compute \(h\)
- Given \(h\), it's hard* to find \(m\)
\[ H(m) \rightarrow h \]
\[ m \not\leftarrow h \]
Hash Chains
\[ H^i(m) = H(H(...H(m))) \]
\[ H^{i+1} = H(H^i(m)) = H(H(H(...H(m)))) \]
\[ pk = H(...H(H(sk))) \]
Big Idea
If one gets an interim value at position \(i\) and knows the overall length \(n\) of the Hash Chain, then they can continue to hash the interim value \(n - i\) times to see if they end up with \(pk\).
Simple Winternitz-OTS
Key Generation
- Generate Private Key \(sk\) by randomly sampling bits
- Pick Hash function that produces outputs of lenthg \(n \text{ bits}\)
- Hash Private Key \(2^n -1\) times to generate public key \(pk\)
Signing
- Hash message \(m\) to compute \(h = H(m)\)
- Interpret \(h\) as a number \(x\)
- Hash Private Key \(sk\) \(x\)-times to generate signature \(\sigma\)
Verification
- Compute number of missing iterations to reach \(pk\) as \(j = (2^n - 1) - x\)
- Hash signature \(\sigma\) \(j\)-times and check if the result is equal to \(pk\)
Problems
- Computationally Expensive
- Sequential Operation
- High Number of Hash Computations
- Signature Forgeries
- \(H(m)\) –> \(H(H(m))\)
1. Computationally Expensive
- Split message into \(l\) chunks of \(w \text{ bits}\) each
- Have one hash-chain for each chunk \(l_i\) that has max-length \(2^w\)
- Each hash-chain starts from a dedicated Private Key \(sk_i\)
- Each hash-chain ends with a dedicated Public Key \(pk_i\)
- Signing and verifying is done per hash-chain
We have to distribute \(l\) Public Keys for signature verification.
Hash all \(l\) Public Keys "into" one Public Key \(pk\).
- Split message into \(l\) chunks of \(w \text{ bits}\) each
- Have one hash-chain for each chunk \(l_i\) that has max-length \(2^w\)
- Each hash-chain starts from a dedicated Private Key \(sk_i\)
- Each hash-chain ends with a dedicated Public Key \(pk_i\)
- Hash all Public Keys \(pk_i\) to derive Public Key \(pk\)
- Signing and verifying is done per hash-chain
- Results of verifications are combined to see if \(pk\) can be recomputed
2. Signature Forgeries
Compute a checksum and append it to the data that will be signed.
Checksum changes whenever any \(\sigma_i\) is changed.
\[ c = \sum_{i=0}^{l-1} ((2^w - 1) - x_i) \]
Sum of all the missing hash iterations necessary to reach \(pk_i\) for each individual chunk \(l_i\).
\(c\) will be reduced by \(1\), whenever a signature \(\sigma' = H(\sigma)\) for chunk \(l\) is forged.
\(c\) is also signed as \(\sigma_c = H^c(sk_c)\).
We'd need to undo one hash iteration to adapt the checksum \(c\) which isn't possible due to the one-wayness of Hash Functions.
Classical Winternitz-OTS
Checksum adds additional overhead…
Allow only messages that result in a pre-defined sum of interim values.
\[ T \approx \frac{l \times (2^w - 1)}{2} \]
Target Sum Winternitz-OTS
OTS –> MTS
How do we go from a One-Time Signature to Many-Time Signatures?
Why is Winternitz a One-Time Signature Scheme?
So how do we go from OTS to MTS?
Merkle Tree
Great, because it only uses Hash Functions!
- Instantiate Winternitz-OTS \(n\) times
- Treat Public Key \(pk\) of each instantiation as a leaf of the Merkle Tree
Signing & Verifying
eXtended Merkle Signature Scheme (XMSS)
How do we know which Merkle Tree Leaf to choose?
Enumerate leafs from left to right.
Each leaf will be assigned to a slot = Synchronization
What about signature aggregation?
TBD
Post-Quantum SNARK
Which Hash Function should we use?
SHA-3 (Conservative choice)
Poseidon 2 (Faster aggregations)
Signature Size vs. Computation Cost
Signature Size = Bandwidth Requirement
Computation = Verification & Aggregation Costs
Parameter Selection
SHA-3-256
Poseidon 2
If this piqued your interested, then you can use the resources I used to make this presentation to dive deeper into the specifics.
Additional Resources
- Hash-Based Multi-Signatures for Post-Quantum Ethereum
- Understanding Cryptography (2nd Edition) - Chapter 12.4
- XMSS: Hash-based Stateful Digital Signature
- RFC 8391 - XMSS: eXtended Merkle Signature Scheme
- Explore Expander Bootcamp: Post-quantum Aggregatable Signature
- Post-quantum cryptography: Hash-based signatures
- SPHINCS+ - Step by Step