Ethereum Signature Schemes Explained: ECDSA, BLS, XMSS, and Post-Quantum leanSig with Rust Code Examples

TL;DR: A guide to the mathematics, code, attacks, and future of cryptographic signatures in Ethereum—from ECDSA transactions to BLS consensus aggregation and the post-quantum lean signature. Includes working Rust code examples using lambdaworks.

In 2010, Sony's PlayStation 3 security was considered unbreakable. Then a hacker noticed something odd: Sony had used the same random number twice when signing their firmware. That single repeated value let attackers derive Sony's master private key. Every PS3 ever made became hackable. What can we learn from this? Digital signatures are only as strong as their weakest implementation detail.

Every time you send a transaction on Ethereum, you are making a mathematical claim that only you could have made, a proof based on the hardness of well-established problems. But here is the rub: we are building critical infrastructure on assumptions that quantum computers will eventually break. So what is the way forward? We prepare, and that means understanding what we are actually relying on and what the future looks like.

This post examines the signature schemes most relevant to Ethereum's present and future: ECDSA for transaction signing, BLS for consensus aggregation, and XMSS as a post-quantum candidate. Each section pairs mathematical definitions with working Rust code using lambdaworks. The XMSS version used is not the candidate for Ethereum, but serves to illustrate the point.

Signature Scheme Tradeoffs at a Glance

Before we dive in, let us acknowledge an uncomfortable truth (which is almost universal in Engineering): there is no perfect signature scheme. There are trade-offs in speed, aggregation capabilities, signature size, post-quantum security, and SNARK-friendliness.

BLS gives us native aggregation but fails post-quantum. XMSS is quantum-safe but does not aggregate natively. leanSig combines the best of both: quantum resistance and STARK-based aggregation, though signatures sizes are way larger than BLS.

Part I: ECDSA — The Foundation of Ethereum Transactions

How Elliptic Curve Cryptography Works

ECDSA operates on elliptic curves over finite fields. The curve used by Ethereum (secp256k1) is defined by:

$$y^2 = x^3 + 7 \pmod{p}$$

where $p = 2^{256} - 2^{32} - 977$, a carefully chosen prime.

Why this specific curve?:

1. $a = 0$ simplifies point doubling (fewer multiplications).
2. $p$ is a pseudo-Mersenne prime, making modular reduction fast.

Points on this curve form a group under the chord-and-tangent addition law. The critical operation is scalar multiplication: given a point $G$ (the generator) and a scalar $k$, compute $kG = G + G + \cdots + G$ ($k$ times).

The Elliptic Curve Discrete Logarithm Problem (ECDLP) states:

Given points $G$ and $Q = kG$, finding $k$ is computationally infeasible.

For a 256-bit curve, the best classical attack (Pollard's rho) requires $O(\sqrt{n}) \approx 2^{128}$ operations—well beyond current computational power.

Finite Field Arithmetic with lambdaworks

Before working with elliptic curves, we need finite field arithmetic. Here is how lambdaworks handles this, using the secp256k1 field definitions already built into the library:

use lambdaworks_math::elliptic_curve::short_weierstrass::curves::secp256k1::curve::Secp256k1FieldElement;
use lambdaworks_math::field::element::FieldElement;

// Field elements in F_p where p = 2^256 - 2^32 - 977
let a = Secp256k1FieldElement::from(7u64);
let b = Secp256k1FieldElement::from(11u64);

// All arithmetic is automatically mod p
let sum = &a + &b;          // (7 + 11) mod p = 18
let product = &a * &b;      // (7 × 11) mod p = 77
let inverse = a.inv().unwrap(); // 7^(-1) mod p
assert_eq!(&a * &inverse, Secp256k1FieldElement::one());

This is the foundation for everything that follows. Every point addition, every scalar multiplication, every signature computation happens in this field.

lambdaworks example reference: The Pohlig-Hellman example demonstrates a discrete logarithm attack on weak groups, showcasing field arithmetic in practice.

ECDSA Key Generation

The key generation algorithm is remarkably simple:

ECDSA-KeyGen():
    1. Select random d ∈ [1, n-1]        // Private key (256-bit integer)
    2. Compute Q = d × G                  // Public key (curve point)
    3. Return (d, Q)

In Rust, using elliptic curve types from lambdaworks:

use lambdaworks_math::elliptic_curve::short_weierstrass::curves::secp256k1::curve::Secp256k1;
use lambdaworks_math::elliptic_curve::traits::IsEllipticCurve;
use lambdaworks_math::unsigned_integer::element::UnsignedInteger;

// The generator point G for secp256k1 is built into lambdaworks
let generator = Secp256k1::generator();

// Private key: a random 256-bit scalar
// In production, use a cryptographically secure RNG
let private_key = UnsignedInteger::<4>::from_hex_unchecked(
    "c6b506142fb077e8f06e8e1b2b12a8c63ed60abe2bdb4fea50e39e12ef9e5298"
);

// Public key: Q = d × G (scalar multiplication)
let public_key = generator.operate_with_self(private_key);
// This point (x, y) is your Ethereum address (after hashing)

ECDSA Signing Algorithm

The signing algorithm reveals the treacherous algebra of ECDSA:

ECDSA-Sign(d, message):
    1. e = H(message)                     // Hash the message (256 bits)
    2. Select random k ∈ [1, n-1]         // THE NONCE - this is critical!
    3. Compute R = k × G                  // Ephemeral point
    4. r = R.x mod n                      // x-coordinate becomes r
    5. s = k⁻¹(e + r·d) mod n            // THE SIGNATURE EQUATION
    6. Return (r, s)

The signature equation is where we combine all the relevant data:

$$s = k^{-1}(e + r \cdot d) \mod n$$

This equation binds together:

• $e$: the message hash (public after signing)
• $r$: derived from $kG$ (public in signature)
• $d$: your private key (secret!)
• $k$: the nonce (must be kept secret AND unique)

Here is the full signing algorithm implemented step by step with lambdaworks. We use the secp256k1 curve types and scalar field arithmetic directly, mirroring each line of the pseudocode:

use lambdaworks_math::elliptic_curve::short_weierstrass::curves::secp256k1::curve::Secp256k1;
use lambdaworks_math::elliptic_curve::short_weierstrass::curves::secp256k1::field_extension::Secp256k1PrimeField;
use lambdaworks_math::elliptic_curve::traits::IsEllipticCurve;
use lambdaworks_math::field::element::FieldElement;
use lambdaworks_math::cyclic_group::IsGroup;

type ScalarField = FieldElement<Secp256k1PrimeField>;

/// ECDSA signing using lambdaworks primitives.
/// Returns (r, s) as scalar field elements.
fn ecdsa_sign(
    private_key: &ScalarField,  // d
    msg_hash: &ScalarField,     // e = H(message)
    nonce: &ScalarField,        // k — in production, derive via RFC 6979!
) -> (ScalarField, ScalarField) {
    let generator = Secp256k1::generator();

    // Step 1: R = k × G (ephemeral point on the curve)
    let r_point = generator.operate_with_self(nonce.canonical());

    // Step 2: r = R.x mod n (extract x-coordinate as a scalar)
    let [x, _y] = r_point.to_affine().coordinates();
    let r = ScalarField::new(x.canonical());

    // Step 3: s = k⁻¹ · (e + r·d) mod n  — THE SIGNATURE EQUATION
    let k_inv = nonce.inv().unwrap();
    let s = &k_inv * &(msg_hash + &(&r * private_key));

    (r, s)
}

ECDSA Verification: Why It Works

ECDSA-Verify(Q, message, (r, s)):
    1. e = H(message)
    2. u₁ = e · s⁻¹ mod n
    3. u₂ = r · s⁻¹ mod n
    4. R' = u₁ × G + u₂ × Q
    5. Return (R'.x mod n == r)

And the verification, again step by step:

/// ECDSA verification using lambdaworks primitives.
/// Q is the public key (a curve point), (r, s) is the signature.
fn ecdsa_verify(
    public_key: &ShortWeierstrassProjectivePoint<Secp256k1>,
    msg_hash: &ScalarField,     // e = H(message)
    r: &ScalarField,
    s: &ScalarField,
) -> bool {
    let generator = Secp256k1::generator();

    // Step 1: s_inv = s⁻¹ mod n
    let s_inv = s.inv().unwrap();

    // Step 2: u₁ = e · s⁻¹,  u₂ = r · s⁻¹
    let u1 = msg_hash * &s_inv;
    let u2 = r * &s_inv;

    // Step 3: R' = u₁·G + u₂·Q  (two scalar multiplications + point addition)
    let r_prime = generator
        .operate_with_self(u1.canonical())
        .operate_with(&public_key.operate_with_self(u2.canonical()));

    // Step 4: Check R'.x mod n == r
    let [x_prime, _] = r_prime.to_affine().coordinates();
    ScalarField::new(x_prime.canonical()) == *r
}

Notice how each line of code maps directly to a line of the pseudocode. The underlying field arithmetic—modular inversion, multiplication, and the elliptic curve scalar multiplication—is handled by lambdaworks.

The correctness proof: Starting from the verification computation:

$$R^\prime = u_1 G + u_2 Q$$

Substitute $Q = dG$:

$$R^\prime = u_1 G + u_2 (dG) = (u_1 + u_2 d)G$$

Now substitute $u_1 = es^{- 1}$ and $u_2 = rs^{-1}$:

$$R^\prime = s^{- 1}(e + rd)G$$

Recall from signing that $s = k^{- 1}(e + rd)$, which means $(e + rd) = sk$:

$$R^\prime = s^{- 1}(sk)G = kG = R$$

The verification reconstructs the original point $R$! Since $r = R.x \mod n$, the signature verifies. The key insight is that verification essentially "undoes" the masking performed during signing. The value $s$ encodes $k$ in a way that requires knowing $d$ to compute, but verification reconstructs $kG$ using only public information.

lambdaworks example reference: The Naive Schnorr signatures example demonstrates a closely related signature scheme with a similar structure. Schnorr signatures use a simpler equation ($s = k - e \cdot d$).

The Nonce Catastrophe: Why k Must Never Be Reused

Now we arrive at the most dangerous part of ECDSA. The nonce $k$ is like a one-time pad, except the consequences of reuse are catastrophic in a different way. Reuse a one-time pad, and your message becomes readable. Reuse an ECDSA nonce, and your private key becomes computable (and therefore anyone can forge signatures).

The complete attack derivation:

Suppose an attacker observes two signatures on different messages $m_1$ and $m_2$, both signed with the same nonce $k$:

$$\begin{aligned}
s_1 &= k^{- 1}(e_1 + r \cdot d) \mod n \newline
s_2 &= k^{- 1}(e_2 + r \cdot d) \mod n
\end{aligned}$$

Note: same $k$ means same $r$ (since $r = (kG).x$). The attacker notices $r_1 = r_2$.

Step 1: Subtract the equations

$$s_1 - s_2 = k^{- 1}(e_1 - e_2) \mod n$$

Step 2: Solve for $k$

$$k = \frac{e_1 - e_2}{s_1 - s_2} \mod n$$

Everything on the right side is public! The attacker now knows $k$.

Step 3: Extract the private key

$$d = \frac{s \cdot k - e}{r} \mod n$$

Game over: The private key is recovered from publicly observable data.

Worked Example: Nonce Reuse Attack with Small Numbers

Let's work through a concrete example:

Setup:

• $n = 23$ (group order)
• Private key: $d = 7$
• Nonce (reused!): $k = 5$
• Assume $r = (kG).x \mod 23 = 15$

First signature on message where $e_1 = H(m_1) = 11$:

$$s_1 = k^{-1}(e_1 + rd) = 5^{-1}(11 + 15 \times 7) \mod 23$$

We need $5^{-1} \mod 23$. Since $5 \times 14 = 70 = 3 \times 23 + 1$, we have $5^{-1} = 14$.

$$s_1 = 14 \times (11 + 105) = 14 \times 116 = 14 \times (116 \mod 23) = 14 \times 1 = 14$$

Second signature on message where $e_2 = H(m_2) = 3$:

$$s_2 = 14 \times (3 + 105) = 14 \times 108 = 14 \times (108 \mod 23) = 14 \times 16 = 224 \mod 23 = 17$$

The attack:

$$k = \frac{e_1 - e_2}{s_1 - s_2} = \frac{11 - 3}{14 - 17} = \frac{8}{-3} \mod 23$$

Since $-3 \equiv 20 \pmod{23}$ and $20^{-1} = 15$ (since $20 \times 15 = 300 = 13 \times 23 + 1$):

$$k = 8 \times 15 = 120 \mod 23 = 5 \quad \checkmark$$

Now extract $d$:

$$d = \frac{s_1 \cdot k - e_1}{r} = \frac{14 \times 5 - 11}{15} = \frac{59}{15} \mod 23$$

$59 \mod 23 = 13$, and $15^{-1} = 20$:

$$d = 13 \times 20 = 260 \mod 23 = 7 \quad \checkmark$$

The private key $d = 7$ is recovered. Here is a Rust simulation of this attack using lambdaworks field arithmetic:

use lambdaworks_math::field::element::FieldElement;
use lambdaworks_math::field::fields::u64_prime_field::U64PrimeField;

// Working in Z_23 (small field for demonstration)
type F = U64PrimeField<23>;
type FE = FieldElement<F>;

fn nonce_reuse_attack() {
    let d = FE::from(7u64);  // Secret key (attacker doesn't know this)
    let k = FE::from(5u64);  // Nonce (reused!)
    let r = FE::from(15u64); // From kG.x

    // Two signatures with the SAME nonce
    let e1 = FE::from(11u64);
    let s1 = k.inv().unwrap() * (&e1 + &r * &d); // s1 = 14

    let e2 = FE::from(3u64);
    let s2 = k.inv().unwrap() * (&e2 + &r * &d); // s2 = 17

    // === THE ATTACK (uses only public data) ===
    // Step 1: Recover k
    let k_recovered = (&e1 - &e2) * (&s1 - &s2).inv().unwrap();
    assert_eq!(k_recovered, FE::from(5u64)); // k = 5 ✓

    // Step 2: Recover private key
    let d_recovered = (&s1 * &k_recovered - &e1) * r.inv().unwrap();
    assert_eq!(d_recovered, FE::from(7u64)); // d = 7 ✓

    println!("Private key recovered: d = 7");
}

Real-World ECDSA Nonce Disasters

This is not just academic knowledge. Here is what happened when people got it wrong:

The solution: RFC 6979

Modern implementations derive $k$ deterministically:

$$k = \text{HMAC-DRBG}(\text{private_key}, \text{message_hash})$$

This is deterministic (same inputs → same $k$), unique (different messages → different $k$), and secret (depends on private key).

Part II: BLS Signatures — How Ethereum Scales to 1 Million Validators

At this point, a reasonable question is: "Why not just use ECDSA everywhere?" The answer becomes clear when you try to scale.

Ethereum has over 900,000 validators. Each slot requires attestations from thousands of validators. With ECDSA, that is thousands of separate signature verifications every 12 seconds. BLS signature aggregation changes the math entirely.

Bilinear Pairings: The Mathematics Behind Aggregation

BLS relies on bilinear pairings, a mathematical operation that seems like it should break everything (it was first used to try to break the discrete log problem), but instead enables efficient aggregation.

Definition: A bilinear pairing is a map:

$$e: G_1 \times G_2 \rightarrow G_T$$

satisfying the bilinearity property:

$$e(aP, bQ) = e(P, Q)^{ab}$$

This lets us "multiply in the exponent", moving between additive groups ($G_1$, $G_2$) and a multiplicative group ($G_T$).

The BLS Signature Scheme

The algorithms for BLS signatures are (you can swap which group holds public keys vs signatures):

Key Generation:

sk ← random scalar in Z_p
pk = sk × G₂ ∈ G₂

Signing:

H = hash_to_curve(message) ∈ G₁
σ = sk × H ∈ G₁

Verification:

Check: e(σ, G₂) = e(H(m), pk)

Why BLS Verification Works

Starting with the left side:

$$e(\sigma, G_2) = e(sk \cdot H(m), G_2) = e(H(m), G_2)^{sk}$$

Now the right side:

$$e(H(m), pk) = e(H(m), sk \cdot G_2) = e(H(m), G_2)^{sk}$$

Both sides equal $e(H(m), G_2)^{sk}$. The pairing's bilinearity property lets us move scalar factors between the two arguments—this is the mathematical magic that makes BLS work.

BLS Sign and Verify with lambdaworks

We can implement BLS signing and verification directly with lambdaworks's BLS12-381 curve and pairing support. The signing is just a scalar multiplication in $G_1$; the verification is a pairing check:

use lambdaworks_math::elliptic_curve::short_weierstrass::curves::bls12_381::{
    curve::BLS12381Curve,
    twist::BLS12381TwistCurve,
    pairing::BLS12381AtePairing,
    field_extension::BLS12381PrimeField,
};
use lambdaworks_math::elliptic_curve::traits::{IsEllipticCurve, IsPairing};
use lambdaworks_math::cyclic_group::IsGroup;
use lambdaworks_math::field::element::FieldElement;

type ScalarField = FieldElement<BLS12381PrimeField>;

/// BLS key generation: sk is a random scalar, pk = sk × G₂
fn bls_keygen(sk: u64) -> (u64, /* pk */ impl IsGroup) {
    let g2 = BLS12381TwistCurve::generator();
    let pk = g2.operate_with_self(sk);
    (sk, pk)
}

/// BLS signing: σ = sk × H(m)
/// Here we simplify hash-to-curve as scalar × G₁ for illustration.
/// A production implementation MUST use a proper hash_to_curve (RFC 9380).
fn bls_sign(sk: u64, msg_point: &impl IsGroup) -> impl IsGroup {
    msg_point.operate_with_self(sk)
}

/// BLS verification: check e(σ, G₂) == e(H(m), pk)
fn bls_verify(
    signature: &ShortWeierstrassProjectivePoint<BLS12381Curve>,
    msg_point: &ShortWeierstrassProjectivePoint<BLS12381Curve>,
    public_key: &ShortWeierstrassProjectivePoint<BLS12381TwistCurve>,
) -> bool {
    let g2 = BLS12381TwistCurve::generator();

    // Left side:  e(σ, G₂)
    let lhs = BLS12381AtePairing::compute(signature, &g2);
    // Right side: e(H(m), pk)
    let rhs = BLS12381AtePairing::compute(msg_point, public_key);

    lhs == rhs  // Bilinearity guarantees equality for valid signatures
}

Note on hash-to-curve: The snippet above simplifies H(m) as a scalar multiple of $G_1$. A real BLS implementation must use a standards-compliant hash-to-curve function (RFC 9380) to map arbitrary messages to points on $G_1$ without introducing any exploitable structure. lambdaworks provides the BLS12-381 curve infrastructure on top of which such a function can be built.

BLS Signature Aggregation: The Key to Scaling Ethereum

Without aggregation, we would need to keep all the signatures by all the validators and verify each of them separately. This scales linearly with the number of validators and becomes a serious problem for scaling. For example, if 16384 validators have to sign, we need $16384 \times 64\ \text{bytes} = 2^{20}\ \text{bytes} = 1\ \text{MB}$. With aggreation, even though the verification time of the aggregated signature is slower than an indivial EDCSA, it is way more efficient (both in terms of storage and verification) than doing linear work with $N$ sufficiently large. In particular, with BLS aggregation, the aggregated signature is 48 bytes, exactly the same size as a single signature.

Given $n$ signatures $\sigma_1, \ldots, \sigma_n$ on the same message:

$$\sigma_{agg} = \sigma_1 + \sigma_2 + \cdots + \sigma_n$$

The aggregate is still 48 bytes in compressed form. Verification:

$$e(\sigma_{agg}, G_2) \stackrel{?}{=} e(H(m), pk_1 + pk_2 + \cdots + pk_n)$$

Proof that this works:

$$e(\sigma_{agg}, G_2) = e\left(\sum_{i=1}^n sk_i \cdot H(m), G_2\right) = \prod_{i=1}^n e(H(m), G_2)^{sk_i} = e(H(m), G_2)^{\sum sk_i} = e(H(m), \sum pk_i)$$

Bandwidth savings:

Without BLS, Ethereum's current validator set would be impossible. Of course, we still need to keep track who signed the message, but that is a bitstring as long as the number of validators in the set.

Aggregation in code is straightforward—it's just point addition in $G_1$:

/// Aggregate n BLS signatures into one.
/// sig_agg = σ₁ + σ₂ + ... + σₙ  (point addition in G₁)
fn bls_aggregate(
    signatures: &[ShortWeierstrassProjectivePoint<BLS12381Curve>],
) -> ShortWeierstrassProjectivePoint<BLS12381Curve> {
    signatures
        .iter()
        .skip(1)
        .fold(signatures[0].clone(), |acc, sig| acc.operate_with(sig))
}

/// Aggregate n public keys for same-message verification.
/// pk_agg = pk₁ + pk₂ + ... + pkₙ  (point addition in G₂)
fn bls_aggregate_public_keys(
    public_keys: &[ShortWeierstrassProjectivePoint<BLS12381TwistCurve>],
) -> ShortWeierstrassProjectivePoint<BLS12381TwistCurve> {
    public_keys
        .iter()
        .skip(1)
        .fold(public_keys[0].clone(), |acc, pk| acc.operate_with(pk))
}

// Usage: verify the aggregate with a SINGLE pairing check
// e(sig_agg, G₂) == e(H(m), pk_agg)
let is_valid = bls_verify(&sig_agg, &msg_point, &pk_agg);

The verification cost is a single pairing check regardless of whether 100 or 1,000,000 validators signed.

Pairing-Based Verification in Code

Working with BLS12-381 pairings in lambdaworks:

use lambdaworks_math::elliptic_curve::short_weierstrass::curves::bls12_381::curve::BLS12381Curve;
use lambdaworks_math::elliptic_curve::short_weierstrass::curves::bls12_381::twist::BLS12381TwistCurve;
use lambdaworks_math::elliptic_curve::short_weierstrass::curves::bls12_381::pairing::BLS12381AtePairing;
use lambdaworks_math::elliptic_curve::traits::IsEllipticCurve;
use lambdaworks_math::cyclic_group::IsGroup;
use lambdaworks_math::elliptic_curve::traits::IsPairing;

// G1 and G2 generators
let g1 = BLS12381Curve::generator();
let g2 = BLS12381TwistCurve::generator();

// Simulating: e(sk * H, G2) == e(H, sk * G2)
// This is the core bilinearity check behind BLS verification
let sk = 42u64;
let sig = g1.operate_with_self(sk);   // σ = sk × G₁ (simplified)
let pk = g2.operate_with_self(sk);    // pk = sk × G₂

// Verify: e(σ, G₂) == e(G₁, pk)
let lhs = BLS12381AtePairing::compute(&sig, &g2);
let rhs = BLS12381AtePairing::compute(&g1, &pk);
assert_eq!(lhs, rhs); // Bilinearity holds!

Note: lambdaworks provides full BLS12-381 pairing implementations, including optimal ate pairings and Miller loops—the same operations used by Ethereum's consensus layer.

The Rogue Key Attack on BLS

There's something almost suspicious about BLS. This "controlled leakage" enables aggregation, but it also enables attacks if we're not careful.

The attack scenario:

1. Alice has public key $pk_A = sk_A \cdot G_2$
2. Mallory observes $pk_A$ and creates a rogue public key:
   $$pk_M^{rogue} = sk_M \cdot G_2 - pk_A = (sk_M - sk_A) \cdot G_2$$
3. Mallory registers $pk_M^{rogue}$ as her public key
4. Now look at the aggregated public key:
   $$pk_A + pk_M^{rogue} = pk_A + sk_M \cdot G_2 - pk_A = sk_M \cdot G_2$$
   Alice's key vanishes!
5. Mallory signs a message alone: $\sigma = sk_M \cdot H(m)$
6. This verifies as a joint signature from Alice and Mallory!

The defense: Proof of Possession (PoP)

Every participant must prove they know their secret key by signing their own public key:

$$\pi = sk \cdot H_{pop}(pk)$$

Mallory can't create a valid PoP for her rogue key because she doesn't know the discrete log of $pk_M^{rogue} = (sk_M - sk_A) \cdot G_2$. She knows $sk_M$, but not $sk_A$. Ethereum requires PoP during validator registration.

Part III: XMSS — Hash-Based Signatures for Quantum Safety

BLS gives us aggregation, but it shares ECDSA's weakness: both fall to quantum attacks. Shor's algorithm solves discrete logarithms in polynomial time, $O(n^3)$ instead of $O(2^{n/2})$.

If you believe large-scale quantum computers are coming, then we need schemes based on different hardness assumptions. Hash-based signatures are the answer. Their security reduces to a remarkably clean statement: if the hash function is secure, so is the signature.

The Quantum Threat to Ethereum

Why XMSS survives: there is no algebraic structure for Shor's algorithm to exploit. Security depends only on hash function properties. Grover provides only a quadratic speedup: $2^n \rightarrow 2^{n/2}$.

WOTS+: The One-Time Building Block

XMSS is built from Winternitz One-Time Signatures (WOTS+), a scheme where each key can sign exactly one message.

The hash chain construction:

Position:   0      1      2      3     ...    w-1
            |      |      |      |            |
           sk → H(sk) → H²(sk) → H³(sk) → ... → pk
            ↑                                   ↑
         secret                              public

For Winternitz parameter $w = 16$: each chain has 16 positions (0 to 15), message digits are base-16 (4 bits each), and a 256-bit hash produces 64 message chains + 3 checksum chains = 67 total.

To sign a message digit $d$, reveal position $d$ in the corresponding chain. The verifier can always hash forward to check the signature:

Message hash digits: [7, 10, 3, 15, 2, ...]

Chain 0: reveal position 7  → verifier hashes 8 times to reach pk
Chain 1: reveal position 10 → verifier hashes 5 times to reach pk
Chain 2: reveal position 3  → verifier hashes 12 times to reach pk

Building Hash Chains with lambdaworks

Hash chains are the core primitive of XMSS. Here is how to build one using lambdaworks:

use lambdaworks_crypto::hash::sha3::Sha3Hasher;
use lambdaworks_crypto::hash::traits::IsCryptoHash;

/// Build a WOTS+ hash chain of length `steps` from a secret key
fn hash_chain(secret: &[u8; 32], steps: usize) -> Vec<[u8; 32]> {
    let hasher = Sha3Hasher::new();
    let mut chain = Vec::with_capacity(steps + 1);
    chain.push(*secret);

    for i in 0..steps {
        let prev = &chain[i];
        // Hash forward: H(H(...H(sk)...))
        let hash_output = hasher.hash(prev);
        let mut next = [0u8; 32];
        next.copy_from_slice(&hash_output[..32]);
        chain.push(next);
    }
    chain
}

// The public key is the END of the chain
// The secret key is the START
let secret = [0x42u8; 32];
let chain = hash_chain(&secret, 15); // w=16, positions 0..15
let public_key = chain[15]; // Published
let signing_key = chain[0]; // Secret!

// To sign digit d=7: reveal chain[7]
// Verifier hashes 8 times: H^8(chain[7]) should equal public_key
let mut verification = chain[7];
let hasher = Sha3Hasher::new();
for _ in 0..8 {
    let h = hasher.hash(&verification);
    verification.copy_from_slice(&h[..32]);
}
assert_eq!(verification, public_key); // Signature valid!

lambdaworks example reference: The Merkle Tree CLI example demonstrates building Merkle trees with lambdaworks's crypto primitives. XMSS uses a Merkle tree of WOTS+ public keys—the same construction, applied to signature key management.

The XMSS Key Reuse Attack

Here's where XMSS differs fundamentally from ECDSA and BLS: signing twice with the same one-time key is catastrophic.

Setup: Same WOTS+ key signs two messages:

• Message 1: digits $M_1 = [7, 10, 3, 15, 2, 8, \ldots]$
• Message 2: digits $M_2 = [4, 12, 9, 6, 11, 8, \ldots]$

The critical insight is that, for each chain, the attacker can compute any position ≥ min($M_1[i]$, $M_2[i]$). The attacker can forge a signature on any message $M_3$ where $\forall i: M_3[i] \geq \min(M_1[i], M_2[i])$. This is a huge space of forgeable messages.

Worked example with $w = 4$:

Message 1: M₁ = [2, 1, 3, 0]
Message 2: M₂ = [1, 3, 0, 2]

Attacker's capability per chain:
  Chain 0: min(2,1) = 1 → can forge digits 1, 2, 3
  Chain 1: min(1,3) = 1 → can forge digits 1, 2, 3
  Chain 2: min(3,0) = 0 → can forge digits 0, 1, 2, 3 (HAS SECRET KEY!)
  Chain 3: min(0,2) = 0 → can forge digits 0, 1, 2, 3 (HAS SECRET KEY!)

Target: M₃ = [2, 2, 1, 1] — is this forgeable?
  Chain 0: need 2, have 1 → compute H(sig₂[0]) ✓
  Chain 1: need 2, have 1 → compute H(sig₁[1]) ✓
  Chain 2: need 1, have 0 → compute H(sig₂[2]) ✓
  Chain 3: need 1, have 0 → compute H(sig₁[3]) ✓

FORGED! Without knowing any secret key element directly.

The Checksum Defense

You might wonder: why can't an attacker forge from a single signature by just hashing forward? The checksum prevents this.

$$\text{checksum} = \sum_{i} (w - 1 - M[i])$$

For $M = [7, 10, 3, 15]$ with $w = 16$:

$$C = (15-7) + (15-10) + (15-3) + (15-15) = 8 + 5 + 12 + 0 = 25$$

If an attacker increases a message digit (say 8 instead of 7), the checksum decreases. To forge the decreased checksum digit, the attacker needs to hash backward—which is computationally infeasible. The two-signature attack bypasses this because with two different checksums, the attacker has enough chain elements to forge checksums too.

Real-World State Management Disasters

The XMSS key reuse vulnerability isn't just theoretical. State management failures happen:

System Crash:
    T₁: Sign message, state = index 5
    T₂: Write signature to network
    T₃: ─── CRASH ───
    T₄: Reboot, reload from disk (state still shows index 4!)
    T₅: Sign new message with index 5 (REUSE!)

VM Cloning:
    VM-Original: state = 50
    Clone VM → VM-Copy: state = 50
    Both VMs sign → index 50, 51, 52... used by BOTH

Best practices: atomic state updates (increment and persist before returning signature), hardware security modules with monotonic counters, conservative index advancement, and using SPHINCS+ when state management is hard (stateless, but larger signatures).

Part IV: Lean Ethereum and the Future of Signature Aggregation

What is Lean Ethereum?

Announced in 2025 by the Ethereum Foundation, Lean Ethereum is a complete redesign of Ethereum's consensus layer with four pillars:

1. Lean Consensus: Redesign for security, decentralization, and seconds-level finality
2. Lean Cryptography: Hash-based signatures that work for both SNARKs and quantum computers
3. Lean Governance: Strategic bundling of protocol upgrades
4. Lean Craft: Minimalism, modularity, and formal verification

Zero-knowledge proofs play a core-part in this new design: Lean Consensus/Fort mode provides post-quantum security and scalability for the consensus, while Lean Execution/Beast mode provides unprecedented scale for execution in a highly decentralized blockchain.

The Signature Problem in Lean Consensus

Lean Ethereum aims for 3-slot finality (finality in ~12 seconds instead of ~15 minutes), reduced staking requirement (from 32 ETH to 1 ETH, enabling more validators), and post-quantum security. This creates a signature aggregation challenge at unprecedented scale.

leanSig: Post-Quantum Signatures for Ethereum

leanSig is a hash-based signature scheme designed for Ethereum's consensus layer. It is based on XMSS/Winternitz signatures (hash-based, quantum-safe), optimized for SNARK verification, and supports a key lifetime of 8 years.

Performance targets (from lean roadmap):

leanMultisig: Aggregating Hash-Based Signatures with SNARKs

leanMultisig tackles the hard problem: how do you aggregate hash-based signatures?

Unlike BLS where aggregation is simple point addition, hash-based signatures require a fundamentally different approach:

1. Use a SNARK (STARK) to prove that N individual XMSS signatures are valid
2. The "aggregate signature" is the SNARK proof
3. Verification is SNARK verification, not signature verification

At a high level, the leanMultisig flow looks like this:

┌─────────────────────────────────────────────────────────────┐
│  Validator 1: leanSig.sign(sk₁, msg) → σ₁ (~2.5 KB)       │
│  Validator 2: leanSig.sign(sk₂, msg) → σ₂ (~2.5 KB)       │
│  ...                                                        │
│  Validator N: leanSig.sign(skₙ, msg) → σₙ (~2.5 KB)       │
└───────────────────────┬─────────────────────────────────────┘
                        │
                        ▼
┌─────────────────────────────────────────────────────────────┐
│  Aggregator (SNARK prover):                                 │
│    π = PROVE("all N signatures are valid")                  │
│    Aggregate proof π ≈ ~100 KB (constant size!)             │
└───────────────────────┬─────────────────────────────────────┘
                        │
                        ▼
┌─────────────────────────────────────────────────────────────┐
│  Consensus:                                                 │
│    VERIFY(π) → true/false                                   │
│    One verification, milliseconds, post-quantum safe        │
└─────────────────────────────────────────────────────────────┘

The leanMultisig repository contains the working implementation of this SNARK-based aggregation scheme. It benchmarks aggregating hundreds of XMSS signatures per second on consumer hardware (M4 Max). This is the code that will eventually replace BLS aggregation in Ethereum's consensus layer. We will cover this in an upcoming post.

Why hash-based signatures are SNARK-friendly:

Hash functions are "SNARK-native" because they're built from XOR, AND, and shifts, operations that map directly to arithmetic circuits. Poseidon was specifically designed for SNARKs. There is no expensive modular exponentiation or elliptic curve arithmetic.

The Roadmap: From BLS to leanMultisig

2020–2025: BLS signatures (current)
    ↓
2025–2027: Hybrid phase (BLS + leanSig research)
    ↓
2027–2030: leanSig deployment with SNARK aggregation
    ↓
2030+: Full post-quantum consensus

Conclusion: The Storm on the Horizon

The honest assessment is that quantum computers cannot break ECDSA today, though it does not mean they won't in the near future. We are building infrastructure meant to last decades, and cryptographic transitions take years to complete.

Digital signatures are the load-bearing walls of crypto. Every transaction, every block, every attestation rests on the assumption that forging one is computationally infeasible. We've examined four approaches: ECDSA for compatibility and speed, BLS for scalability through native aggregation, XMSS for quantum resistance, and leanSig/leanMultisig for quantum resistance with SNARK-based aggregation.

The Lean Ethereum initiative represents the most ambitious attempt to solve these challenges, combining hash-based cryptography with SNARK-based aggregation to create a consensus layer that's both scalable and quantum-resistant.

Each signature scheme reflects different tradeoffs. The next decade will likely see Ethereum transition through all of them.

Further Reading

Standards and Specifications

• FIPS 186-5: Digital Signature Standard
• RFC 6979: Deterministic ECDSA
• RFC 8391: XMSS Specification
• BLS12-381 For The Rest Of Us

Ethereum-Specific

• Upgrading Ethereum — BLS Signatures
• EIP-2537: BLS Precompiles
• EIP-7702: Account Abstraction
• Vitalik's Splurge Post — Post-Quantum

Lean Ethereum

• Lean Consensus Roadmap
• leanSig GitHub
• leanMultisig GitHub

Academic Papers

• Boneh-Lynn-Shacham 2001: Original BLS paper
• Biased Nonce Sense (ePrint 2019/023): Lattice attacks on ECDSA nonces
• BLS Attack Analysis (ePrint 2021/377): Comprehensive BLS security

Implementation

• lambdaworks: Rust library for field arithmetic, elliptic curves, pairings, hash functions, SNARKs, and STARKs