Hash-Based Multi-Signatures for Post-Quantum Ethereum

-–-

Philipp Muens - muens.io

X - @pmmuens
TG - @pmuens
GH - @pmuens

Goals

1. Quick Recap on Hash-Based One-Time Signature Schemes
2. Explain how Hash-Based Multi-Signature Schemes work
3. Show how Hash-Based Multi-Signatures will* be used in the Beam Chain
4. Talk about tradeoffs / parameter selection

1st Presentation

Hash-Based Signatures - From First Principles

The Paper

Hash-Based Multi-Signatures for Post-Quantum Ethereum

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

1. Producer creates Block
2. Validators sign Block via BLS
3. Aggregators aggregate signatures via BLS Signature Aggregation

Desired State

1. Producer creates Block
2. Validators sign Block with Post-Quantum Signature Scheme
3. 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

1. Generate Private Key \(sk\) by randomly sampling bits
2. Pick Hash function that produces outputs of lenthg \(n \text{ bits}\)
3. Hash Private Key \(2^n -1\) times to generate public key \(pk\)

Signing

1. Hash message \(m\) to compute \(h = H(m)\)
2. Interpret \(h\) as a number \(x\)
3. Hash Private Key \(sk\) \(x\)-times to generate signature \(\sigma\)

Verification

1. Compute number of missing iterations to reach \(pk\) as \(j = (2^n - 1) - x\)
2. 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!

1. Instantiate Winternitz-OTS \(n\) times
2. 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

Thank You!

-–-

Philipp Muens - muens.io

X - @pmmuens
TG - @pmuens
GH - @pmuens