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