# Hash-Based Multi-Signatures for Post-Quantum Ethereum

\----

Philipp Muens - [muens.io](https://muens.io)

X - [@pm**m**uens](https://x.com/pmmuens)
TG - [@pmuens](https://t.me/pmuens)
GH - [@pmuens](https://github.com/pmuens)

---

## Goals

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

---

## 1st Presentation

[Hash-Based Signatures - From First Principles](https://hackmd.io/@pmuens/HkcCMejEJl)

---

## The Paper

[Hash-Based Multi-Signatures for Post-Quantum Ethereum](https://eprint.iacr.org/2025/055.pdf)

---

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

---

<img alt="HBMSFPQE - Winternitz-OTS - Message Splitting" src="https://hackmd.io/_uploads/ByI5wSIKyg.png" width="550" />

---

We have to distribute $l$ Public Keys for signature verification.

---

Hash all $l$ Public Keys "into" one Public Key $pk$.

---

<img alt="HBMSFPQE - Winternitz-OTS - Single Public Key" src="https://hackmd.io/_uploads/ByGSdSItkx.png" width="400" />

---

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

---

<img alt="HBMSFPQE - Winternitz-OTS - Checksum I" src="https://hackmd.io/_uploads/SykYOHLFye.png" width="500" />

---

<img alt="HBMSFPQE - Winternitz-OTS - Checksum II" src="https://hackmd.io/_uploads/SJxz7rvYkg.png" width="500" />

---

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

---

<img alt="HBMSFPQE - Target Sum Winternitz-OTS I" src="https://hackmd.io/_uploads/r1bxFS8Kkl.png" width="500" />

---

<img alt="HBMSFPQE - Target Sum Winternitz-OTS II" src="https://hackmd.io/_uploads/BJqMtrLYkx.png" width="500" />

---

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

---

<img alt="HBMSFPQE - Winternitz-OTS OTS I" src="https://hackmd.io/_uploads/ryarFHLY1l.png" width="400" />

---

<img alt="HBMSFPQE - Winternitz-OTS OTS II" src="https://hackmd.io/_uploads/SkLIGrPK1l.png" width="400" />

---

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

<img alt="Screenshot 2025-02-09 at 4.33.23 PM" src="https://hackmd.io/_uploads/ByJfiH8YJe.png" width="650" />

---

### Poseidon 2

<img alt="Screenshot 2025-02-09 at 4.33.38 PM" src="https://hackmd.io/_uploads/rkbYsB8Fke.png" width="650" />

---

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](https://eprint.iacr.org/2025/055.pdf)
- [Understanding Cryptography (2nd Edition) - Chapter 12.4](https://www.cryptography-textbook.com)
- [XMSS: Hash-based Stateful Digital Signature](https://www.telsy.com/en/xmss-hash-based-stateful-digital-signature)
- [RFC 8391 - XMSS: eXtended Merkle Signature Scheme](https://www.rfc-editor.org/rfc/rfc8391.html)
- [Explore Expander Bootcamp: Post-quantum Aggregatable Signature](https://www.youtube.com/watch?v=N7O4qpt6FW0)
- [Post-quantum cryptography: Hash-based signatures](https://www.redhat.com/en/blog/post-quantum-cryptography-hash-based-signatures)
- [SPHINCS+ - Step by Step](https://er4hn.info/blog/2023.12.16-sphincs_plus-step-by-step/)

---

## Thank You!

\----

Philipp Muens - [muens.io](https://muens.io)

X - [@pm**m**uens](https://x.com/pmmuens)
TG - [@pmuens](https://t.me/pmuens)
GH - [@pmuens](https://github.com/pmuens)