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

*Images in this note are extracted from Benedikt Wagner and Philipp Muens's slides but errors are mine.*

## Beam Chain context

In the Beam Chain, validators play a crucial role in attesting the validity of Ethereum blocks using their cryptographic signatures. Each validator possesses a key pair (private and public key), and their signatures collectively ensure the integrity of the blockchain. However, storing every validator’s signature on-chain for each block is prohibitively expensive in terms of both cost and data storage. To address this, we need an efficient method to aggregate these signatures before committing them on-chain.


Currently, Ethereum’s Beacon Chain relies on BLS signatures using the BLS12-381 elliptic curve. These signatures are compact and, thanks to the pairing properties of BLS, can be efficiently aggregated—making them well-suited for consensus.

However, a critical drawback of BLS signatures is their vulnerability to quantum attacks. Since they rely on elliptic curve cryptography and the discrete logarithm problem, a sufficiently powerful quantum computer could break their security. This presents a long-term risk to Ethereum’s consensus model in a post-quantum world.

Our goal is to develop a post-quantum multi-signature scheme—one that enables both individual signatures and efficient aggregation—ensuring Ethereum remains secure against quantum threats while maintaining scalability and efficiency.

## Exploring post-quantum multi-signature designs

A variety of cryptographic approaches have been explored to develop secure digital signatures resistant to quantum attacks. These efforts can be broadly categorized into four main families:

- **Lattice- and code-based signatures:** These are among the most actively researched post-quantum cryptographic primitives. However, selecting secure parameters for lattice-based schemes is a complex and error-prone task, making them more challenging to deploy compared to purely hash-based approaches.
- **Isogeny-based signatures:** These rely on the hardness of problems in elliptic curve isogeny graphs, though recent cryptanalytic breakthroughs have raised concerns about their long-term security.
- **Multivariate polynomial equation signatures:** These leverage the difficulty of solving large systems of multivariate equations but often suffer from impractically large key sizes or verification inefficiencies.
- **Hash-based signatures:** These stand out due to their minimal assumptions, conceptual simplicity, and ease of implementation. Unlike the other approaches, they do not rely on complex algebraic structures, making them particularly attractive for blockchain applications. However, a significant limitation in the Ethereum context is that hash-based signatures do not natively support aggregation—a critical challenge given that Ethereum validators sign blocks, and these individual signatures must be efficiently aggregated into a single compact signature.

Despite this limitation, hash-based signatures remain one of the most promising candidates for Ethereum’s long-term post-quantum security. While this work primarily focuses on their potential for Ethereum’s proof-of-stake mechanism, other alternatives merit further exploration.

For instance, an emerging approach involves aggregating Falcon signatures using the lattice-based proof system LaBRADOR, which enables both compact individual and aggregate signatures. However, its security proofs rely on rewinding techniques, whose implications in the post-quantum setting remain uncertain. More broadly, we anticipate that recent lattice-based folding schemes could serve as a strong foundation for further research into non-interactive, post-quantum signature aggregation methods.

## Public aggregation process

A complete multi-signature scheme requires two key components: an **individual signature scheme** (as discussed earlier, with a preference for hash-based systems) and a **public aggregation process** to efficiently combine multiple signatures. While a detailed analysis of aggregation techniques is beyond the scope of this document, it is essential to provide a high-level overview of this critical aspect.

One promising approach for aggregating multiple signatures is leveraging **succinct arguments of knowledge**—a cryptographic proof system where the proof (or argument) is significantly smaller than the underlying witness. In this context, the aggregation process works by constructing a succinct argument that proves knowledge of all valid individual signatures, with the complete set of signatures acting as the witness.

If the succinct argument system itself is based on hash functions, the resulting multi-signature scheme can be made **plausibly post-quantum secure**. A particularly elegant and modular approach is to use **post-quantum SNARKs (pqSNARKs)** to aggregate hash-based signatures. This method not only aligns with post-quantum security requirements but also benefits from ongoing advancements in hash-based succinct argument systems.

While an in-depth examination of this technique is left for future work, current research indicates that this is the most promising candidate for **secure and scalable** multi-signature aggregation in a post-quantum Ethereum ecosystem.


## Signature Requirements

For a signature scheme to be a viable candidate for post-quantum Ethereum, it must meet several key criteria. In particular, hash-based signatures should be aggregation-friendly to ensure scalability and efficiency in the Ethereum ecosystem. The most important requirements are:

- **Compact Signatures**
The size of individual signatures must be small to minimize bandwidth consumption for aggregators. Large signatures can quickly become a bottleneck. For example, if each signature were 32 KiB, and Ethereum operated with a four-second slot, with one second allocated for aggregators to collect signatures, a committee of 4,096 signers (i.e., $2^{12}$) would generate a total of 128 GiB of signature data per second. This would require a network bandwidth of at least 1 GiB/s, which is completely impractical. By contrast, if signatures were under 4 KiB, bandwidth requirements would drop significantly, making it feasible to support larger validator committees.

- **Standard Model Security**
The security of the signature scheme should rely on well-defined cryptographic assumptions in the standard model, rather than relying heavily on the random oracle model. The **standard model** means that security is proven using real-world, well-understood mathematical properties, such as preimage resistance or collision resistance of hash functions. In contrast, the **random oracle model** assumes that a hash function behaves like a perfectly random function, which provides stronger theoretical security guarantees but does not always translate directly into real-world implementations. While the random oracle model can be useful for reasoning about security, we aim for security proofs that are as tight and concrete as possible. Tighter proofs reduce the need for excessive security margins, allowing for more efficient parameter choices without sacrificing security.

- **Efficient Hashing**
Since hash-based signature verification relies heavily on hash function computations, the efficiency of aggregation is directly influenced by the amount of hashing required. Reducing unnecessary hashing steps improves overall performance, especially when aggregating large numbers of signatures. An ideal scheme should minimize redundant hashing while maintaining security, ensuring that verification and aggregation remain computationally feasible at scale.

By focusing on these criteria—small signatures, strong security foundations, and efficient hashing—we can move toward a practical, post-quantum-ready multi-signature scheme that aligns with Ethereum's long-term vision.


## Existing Hash-Based Signature Schemes

Since one of our primary goals is to design a scheme that minimizes the number of hash evaluations required for verification, we initially considered SPHINCS signatures. While SPHINCS offers strong security guarantees and does not require state management, its complexity makes it unsuitable for our needs.

Instead, we focus on a more classical approach that builds many-time signatures from one-time signatures, such as Winternitz signatures. This idea, originating from Merkle’s PhD thesis, is the foundation of the **XMSS (eXtended Merkle Signature Scheme)**.

### How XMSS Works
XMSS leverages **Merkle trees** to extend one-time signatures into many-time signatures. The signer generates a long sequence of one-time key pairs and commits to them using a Merkle tree. The **Merkle root** then serves as the public key for the entire scheme.

To sign the *i-th* message, the signer:
1. Uses the *i-th* one-time private key to sign the message.
2. Includes the corresponding *i-th* one-time public key in the signature.
3. Provides a Merkle proof (a path in the Merkle tree) to verify that this public key is part of the committed structure.

A key characteristic of XMSS is that it is **synchronized** (or **stateful**), meaning that each signature is tied to a specific position in the sequence. This requires careful tracking to ensure that each key is used only once, making it slightly more cumbersome to manage but significantly more efficient than stateless alternatives.

By refining XMSS and tightening its security proofs, our work aims to create a **practical, efficient, and secure** hash-based multi-signature scheme suitable for post-quantum Ethereum.


## The XMSS Approach

A crucial insight in the proof-of-stake (PoS) setting is that validators only need to sign once per slot. This means that a synchronized signature scheme is sufficient, removing the need for the added complexity of fully stateless schemes like SPHINCS+ and SPHINCS-C.

Instead, we can adopt a simpler XMSS-based approach, which leverages the structured nature of PoS to create a many-time signature scheme with built-in synchronization. This allows validators to sign blocks efficiently without the risk of key reuse, while still maintaining strong post-quantum security guarantees.

Additionally, XMSS enables more efficient aggregation by making use of succinct argument techniques, significantly reducing the overhead associated with handling multiple signatures.

### Why is a synchronized many-time signature sufficient?

In traditional signing schemes, a stateless signature approach like SPHINCS+ is often favored because it allows signatures to be generated independently, without requiring the signer to keep track of past uses of their key. However, this flexibility comes at a cost: stateless schemes require more complex mechanisms to avoid security pitfalls, such as using large one-time key pools or generating new key pairs frequently.

In proof-of-stake Ethereum, validators are required to sign exactly once per slot. This structured signing process allows for a synchronized many-time signature scheme like XMSS, where each signature is associated with a specific position in a sequence (or epoch). Since each validator signs only once per slot, there is no risk of accidentally reusing a key inappropriately, which is a major concern in one-time signature schemes. This makes XMSS a natural fit for PoS, as it simplifies the signature process while maintaining post-quantum security.


### From One-Time Signing to Many-Time Signing

XMSS transforms a collection of one-time signatures into a many-time signature scheme using a Merkle tree. This allows a signer to securely generate multiple signatures while keeping a compact and efficient verification process.

#### 1. Key Generation
The signer begins by generating multiple one-time key pairs (OTS), each consisting of:
- A private key:
$$ sk_1^{OTS}, sk_2^{OTS}, \dots, sk_L^{OTS} $$
- A corresponding public key:
$$ pk_1^{OTS}, pk_2^{OTS}, \dots, pk_L^{OTS} $$

These public keys are structured into a Merkle tree, where the Merkle root serves as the main public key for the scheme:
$$ pk = \text{root of the Merkle tree} $$

#### 2. Signing a Message in Slot $i$
To sign a message $m$ for a specific slot $i$, the signer:
1. Uses the corresponding one-time private key:
$$ sk_i^{OTS} $$
2. Produces a signature consisting of:
- The one-time public key:
$$ pk_i^{OTS} $$
- A Merkle proof, which verifies that $pk_i^{OTS}$ is part of the Merkle tree.
- The actual one-time signature on the message:
$$ \text{Sig}(sk_i^{OTS}, m) $$

#### 3. Verification Process
For a verifier to check the validity of the signature:
1. They verify the Merkle proof, ensuring that $pk_i^{OTS}$ is correctly linked to the Merkle root.
2. They check the one-time signature to confirm that it was produced using $pk_i^{OTS}$.

This approach allows many-time signing while maintaining strong cryptographic security. By leveraging the Merkle tree structure, XMSS ensures that each signature remains compact and efficiently verifiable, making it a practical choice for post-quantum Ethereum validation.


## One-Time Signatures via Hash Chains

### Some Interesting Hash Properties

Before diving into how hash chains are used to generate one-time signatures, it's essential to recall some fundamental properties of hash functions.

A hash function $H$ behaves like a random function, mapping an arbitrary-length input $m$ to a fixed-length output $h$. Importantly, the mapping is deterministic, meaning that the same input always produces the same output. However, while computing $h$ from $m$ is easy, the process is effectively a **one-way process**.

This property, known as **preimage resistance**, makes it computationally infeasible to find *any* input $m'$ that produces a given hash $h$. Moreover, it is theoretically **impossible** to be certain that a found preimage ($m'$) is the *original* input ($m$), since multiple different inputs can result in the same hash value.

\begin{aligned}
    H(m) &\to h \\
    m &\not\leftarrow h \quad \text{(preimage resistant & one-way)}
\end{aligned}

A hash chain is constructed by applying $H$ iteratively on an initial value $m$, producing a sequence of hashes:

\begin{aligned}
    H^i(m) &= \underbrace{H(H(\dots H(m) \dots))}_{i \text{ times}} \\
    H^{i+1}(m) &= H(H^i(m)) = \underbrace{H(H(H(\dots H(m) \dots)))}_{i+1 \text{ times}}
\end{aligned}

This property is particularly useful for cryptographic applications, as it allows us to derive a public key from a secret key by repeatedly applying the hash function:

\begin{equation}
pk = \underbrace{H(H(\dots H(sk) \dots))}_{n \text{ times}}
\end{equation}

A key advantage of this approach is that if an intermediate hash value at position $i$ is known, and the total chain length $n$ is predetermined, then one can simply hash the intermediate value $n - i$ more times to verify whether it reaches the expected public key $pk$.

This principle forms the foundation of the Winternitz One-Time Signature (OTS) scheme, which we will now explore in more detail.

### Simple Winternitz-OTS

The Winternitz One-Time Signature (OTS) scheme provides a simple and efficient way to generate and verify signatures using a hash-based approach. The process consists of three main steps: **key generation**, **signing**, and **verification**.

#### Key Generation
1. Generate the private key $sk$ by randomly sampling a sequence of bits.
2. Choose a cryptographic hash function $H$ that produces outputs of length $n$ bits.
3. Compute the public key $pk$ by applying the hash function $2^n - 1$ times to the private key:
$$
pk = H^{(2^n - 1)}(sk)
$$

#### Signing Process
1. Hash the message $m$ to obtain a digest:
$$
h = H(m)
$$
2. Interpret $h$ as a numerical value $x$ in base 10.
3. Compute the signature $\sigma$ by hashing the private key **$x$ times**:
$$
\sigma = H^x(sk)
$$

#### Verification
1. Determine how many more iterations are needed to reach the public key:
$$
j = (2^n - 1) - x
$$
2. Compute $H^j(\sigma)$ and check whether it matches the public key:
$$
H^j(\sigma) \stackrel{?}{=} pk
$$

If the computed value matches the public key, the signature is valid. This method ensures that once a signature is used, the private key information is partially leaked, making it secure only for one-time use.


However, this approach has some drawbacks.

First, the entire process is highly sequential and difficult to parallelize, making it computationally inefficient. Since each operation depends on the previous one, a large number of hash computations are required, which significantly increases processing time.

However, this simple approach has a critical vulnerability. Because the signature $\sigma = H^x(sk)$ reveals an intermediate value in the hash chain, an attacker can easily forge signatures for new messages. If an attacker observes a valid signature for a message $m$ that hashes to $x$, they can forge a signature for any other message $m'$ that hashes to a value $x' > x$. They simply take the original signature $\sigma$ and compute $H^{x' - x}(\sigma)$ to produce a new, valid signature. This one-way property makes the scheme insecure for more than a single use.

To address these issues, the solution is to first compute a hash of the message and then split this **message digest** into $l$ chunks of $w$ bits each. Instead of relying on a single hash chain, we create one independent hash chain for each chunk. Each chain has a maximum length of $2^w$ and follows a structured approach:
- Each hash chain starts from a dedicated private key $sk_i$.
- It progresses through a sequence of hashes.
- It terminates at a dedicated public key $pk_i$.

With this approach, signing and verification are performed separately for each hash chain, improving efficiency while reducing the risk of forgery. This method introduces a more structured and parallelizable design, making it more practical for real-world cryptographic applications.


To enable signature verification, we need to distribute $l$ public keys, each corresponding to a separate hash chain. Instead of handling them individually, we aggregate these $l$ public keys into a single public key $pk$ by applying a hash function.

During verification, the results from each individual hash chain are checked, and if all are valid, they are combined to reconstruct $pk$. The signature is considered valid if the recomputed $pk$ matches the expected public key.


### Signature Forgery Prevention


To prevent signature forgery, a checksum is computed and appended to the data before signing. This ensures that any modification to an individual signature component affects the overall integrity of the signature. The checksum is defined as:

$$
c = \sum_{i=0}^{l-1} ((2^w - 1) - x_i)
$$

This represents the total number of remaining hash iterations required to reach $pk_i$ for each individual chunk $l_i$.

If an attacker attempts to forge a signature by generating $\sigma' = H(\sigma)$ for a given chunk $l_i$, the checksum $c$ decreases by 1. However, since the checksum itself is signed as:

$$
\sigma_c = H^c (sk_c)
$$

any modification to an individual signature would require reversing a hash operation to correctly adjust $c$. Due to the one-way nature of hash functions, this is computationally infeasible, effectively preventing signature forgery.


## Classical Winternitz-OTS

However, using checksums introduces additional overhead in both computation and storage. An alternative approach is to restrict valid messages to those whose corresponding hash-derived values sum to a predefined target value:

$$
T \approx \dfrac{l \times (2^w - 1)}{2}
$$

This ensures that any valid message produces a structured signature, making unauthorized modifications detectable without requiring an explicit checksum. By enforcing this constraint, we can maintain security while reducing the computational cost associated with verifying an additional checksum.


## Target Sum Winternitz-OTS

A key challenge in transitioning from a one-time signature (OTS) scheme to a many-time signature scheme is understanding why Winternitz-OTS is inherently limited to signing a single message. This is crucial for its application in the Beam Chain context.

### Why is Winternitz a One-Time Signature Scheme?

To see the issue, let's consider a scenario where a signer uses the first two **components of their private key**, $sk_0$ and $sk_1$, to sign a message $m_1$. Since the signature scheme is based on iterative hashing, each part of the signature reveals a certain number of hash iterations starting from its corresponding secret value.

An attacker who observes this signature can exploit the one-way nature of the hash function. Specifically, they cannot reverse the hash function to retrieve the original secret values $sk_0$ or $sk_1$, but they can generate new valid signatures for other messages by hashing the observed signature values further up their respective chains.

### Illustration of the Attack

The first set of figures shows the correct signing process for $m_1$, where the signer uses $sk_0$ and $sk_1$ to generate intermediate values leading to a valid signature.

The second set of figures illustrates how an attacker can craft a fraudulent signature for a different message $m'$ or $m''$. By selecting positions that are greater than or equal to the originally signed positions, the attacker can generate a valid-looking signature without needing access to the private keys.

This attack is possible because each hash chain is unidirectional—meaning that once a position is used for signing, all subsequent positions become insecure for future signatures.


### Merkle Tree

Merkle trees are a powerful cryptographic tool that leverage hash functions extensively, making them an ideal structure for improving the security and scalability of hash-based signature schemes like Winternitz-OTS.

By using a Merkle tree, we can:
1. Instantiate Winternitz-OTS multiple times to allow for many-time signatures.
2. Treat each individual public key $pk_i$ from a Winternitz-OTS instance as a leaf in the Merkle tree.

The following illustration shows how multiple Winternitz-OTS public keys are arranged as leaves in a Merkle tree. Each level of the tree applies hash functions to combine child nodes, ultimately leading to a single root public key $pk$. This root key serves as the global public key for the entire scheme, significantly reducing the storage and transmission overhead compared to managing each $pk_i$ individually.


In the following illustration, we see how signing and verification work within this Merkle tree structure. When signing a message, the signature includes not only the Winternitz-OTS signature for that specific leaf but also a Merkle proof (also called an authentication path). This proof consists of the necessary hash values from sibling nodes along the path to the root, allowing the verifier to reconstruct and validate the correct Merkle root without needing access to the full tree.


This approach makes it possible to efficiently verify multiple signatures while maintaining strong security guarantees, as forging a signature would require breaking the hash function or finding a collision within the Merkle structure—both of which are computationally infeasible.

## eXtended Merkle Signature Scheme (XMSS)

A key aspect of applying XMSS in this context is determining which **Merkle tree leaf** to use for signing at any given time. To achieve this, the leaves are **sequentially enumerated from left to right**, ensuring an organized and structured assignment.


### Leaf Assignment to Slots

Each leaf corresponds to a specific slot, meaning that signing operations are synchronized with the progression of time. This provides a predictable and structured approach to key usage, preventing key reuse vulnerabilities while maintaining efficiency. The second illustration shows how each slot is mapped to a different leaf in the Merkle tree, ensuring that no leaf is used more than once.


However, an important question arises: what happens when all the leaves in a Merkle tree have been used?

Once all the leaves are exhausted, a completely new Merkle tree must be generated, including new Winternitz-OTS instantiations for the tree leaves. This ensures continued security by providing fresh one-time keys while maintaining the structured signing approach. Since each Merkle tree root acts as a stable public key, it must be shared with all validators whenever a new tree is created. This update ensures that the system remains synchronized and that signatures can still be verified correctly.

Every Merkle tree has a pre-determined lifetime, which directly affects both security and efficiency. A longer lifetime means that the tree has more leaves available, reducing the frequency of tree regeneration and public key updates. However, this also results in a larger tree, which increases computational and storage requirements. The trade-off between tree size and refresh frequency is an essential consideration in practical implementations.

### Security Properties for Hash Functions in XMSS

The security of XMSS and its variants is fundamentally tied to the properties of the underlying hash functions. To ensure resilience against attacks, several key security properties must be satisfied.

Multi-target preimage resistance ensures that given multiple target outputs, it remains computationally infeasible to find an input that maps to any of them. Similarly, multi-target undetectability guarantees that an adversary cannot efficiently distinguish between different target values when given a set of potential inputs.

Multi-target collision resistance extends the classical collision resistance property by considering scenarios where an attacker attempts to find two different inputs mapping to any one of multiple predefined outputs. An even stronger variant, multi-target collision resistance with random sampling, introduces additional randomness, making such attacks significantly harder.

These properties serve as concrete cryptanalytic targets for evaluating the robustness of hash functions used in XMSS. Ensuring that the chosen hash functions exhibit these properties is crucial for the long-term security of XMSS, particularly in the post-quantum setting where conventional assumptions about cryptographic strength may no longer hold. By establishing these rigorous security guarantees, XMSS can maintain its integrity as a viable alternative to traditional digital signature schemes.


## Hash tweaks

One important concept in the original paper is the concept of tweak.

### What is a Tweak in Simple Words?
A tweak is an extra unique input added to a hash function to make each hash computation distinct, even if the main input (the message) is the same.

Think of it as a label or an identifier that tells the hash function:
- *"This hash is for a Merkle tree node."*
- *"This hash is for a chain in my digital signature."*
- *"This hash is for a leaf in the tree."*

The purpose of a tweak is to avoid collisions between different types of hash computations. Even if two different processes (e.g., chain hashing and tree hashing) hash the same value, the tweak ensures that the outputs will be different.

### An Analogy to Understand Tweaks

Imagine you are naming files on your computer. If you save two documents with the same name, the computer might overwrite the first one. To avoid this, you add extra details to the filename, like:
- `"report.docx"` → `"report_v1.docx"` (Version tweak)
- `"report.docx"` → `"report_final.docx"` (Final version tweak)

Similarly, a tweak ensures that different types of hashes (like Merkle tree nodes, chain hashes, etc.) do not mix up, even if they have the same input data.