From BLS to leanXMSS signatures
By Manu.
leanXMSS and the consensus changes around it are still being designed, and they change quickly. This page follows the leanXMSS specification draft for the signature scheme, and the PQ Gasper draft spec for what validators sign, both as of November 2026. Later versions may differ.
This page is for anyone curious about how Ethereum validators could sign in a post-quantum world: stakers, node operators, client developers, and anyone else following the topic. You don't need any background in cryptography. Read it like a short book, from top to bottom: each section builds on the ones before it. It starts with what every signature scheme does, then builds up leanXMSS, the post-quantum scheme proposed to replace BLS for validators.
XMSS stands for eXtended Merkle Signature Scheme, and leanXMSS is the version designed by the Lean Ethereum research effort.
Here is what a leanXMSS signature looks like:
signature = leaf index (4 bytes)
‖ ρ⁰ (16 bytes) ‖ 58 revealed values (928 bytes) ‖ path in bottom tree b (256 bytes)
‖ ρ¹ (16 bytes) ‖ 58 revealed values (928 bytes) ‖ path in the top tree (256 bytes)
= 2,404 bytes
If neither the name nor this signature means anything to you yet, that's expected. By the end of this page, you'll have built the scheme piece by piece: you'll know what each word of its name means, what each part of the signature is, why it has to be there, and what would go wrong without it.
Why Ethereum needs signatures
A digital signature lets you prove that a message comes from you and hasn't been changed, in a way anyone can check and nobody can fake. Every block and every vote your validator sends carries one.
Your validator's messages don't go straight to the rest of the network. They're passed along from peer to peer, through computers run by strangers. Any of them could change a message on the way, or write a new one and claim it came from you.
That matters because a validator's vote carries weight: it's backed by its stake, and the chain decides which blocks are final by counting those votes. If anyone could vote in your name, they could steer the chain with your ETH.
So every message needs a proof attached that:
- Only you could have made it. Nobody else can produce a valid proof for your validator.
- It covers exactly this message. Change one bit and the proof no longer checks out.
- Anyone can check it, on their own, without asking you or trusting whoever passed the message along.
A digital signature is that proof.
There's a flip side: once you've signed something, you can't deny it. That's what makes slashing possible. Two signed votes that contradict each other are proof, which anyone can check, that your validator broke the rules.
The four pieces
| Piece | What it is | Who has it |
|---|---|---|
| Private key | A large random number. Whoever holds it can sign in your name. | You only. Also called the secret key. |
| Public key | A value computed from the private key. It identifies you. | Everyone. A validator's public key is stored on chain. |
| Message | What you sign: a block, a vote, an exit request... | Everyone. Signing doesn't hide it. |
| Signature | A value computed from the private key and the message. | Everyone. It travels with the message. |
Computing the public key from the private key is easy. Going the other way must be practically impossible: that's what makes it safe to publish the public key.
The three operations
- Key generation. Pick a private key at random and compute the public key from it. You do this once, then publish the public key.
- Signing. Combine your private key with the message to produce the signature. Only the holder of the private key can do this.
- Verifying. Take the public key, the message and the signature, and check that they match. The answer is valid or invalid. Anyone can do this, and it needs nothing secret.
A valid answer tells the verifier two things. The signature was made with the private key behind this public key, and the message is exactly the one that was signed. If either the message or the signature is altered, the answer is invalid.
A signature doesn't hide anything. The message stays readable by everyone. The signature only proves who approved it.
How many signatures a validator makes
A validator keeps the same public key for its whole life, which can last decades.
| Message | When | How often |
|---|---|---|
| Preregistration | Optionally, before the first deposit, to bind the key to its withdrawal credentials | Once at most |
| Attestation | Every epoch, a vote for the head of the chain | 225 per day, about 82,000 per year |
| Block | When chosen to propose | Rarely. With about a million validators, once every four to five months on average |
| Proposer preferences | Before each block it proposes | Same as blocks |
| Aggregate | When chosen to combine its committee's attestations | Occasionally |
| Payload timeliness vote | When chosen for the payload timeliness committee | Occasionally |
| Voluntary exit | When leaving | Once |
Builders, which are a separate kind of participant, also sign payload bids and payloads.
Attestations dominate: a validator signs about 82,000 messages a year, nearly all of them votes. Over a few decades, that's a few million.
Mandatory properties
A signature scheme for Ethereum validators must have these properties.
| Property | Why |
|---|---|
| #1 - Keys that are practical to create and store | Creating a key shouldn't take days, and the private key has to fit on an ordinary machine. |
| #2 - Small public keys | Every public key is stored in the beacon state, which every node keeps. |
| #3 - Small signatures | Every vote travels through the network on its own. Any extra byte is multiplied by about a million validators voting every epoch. |
| #4 - One public key for a whole life | The public key is registered on chain once, so it has to cover every message the validator will ever sign: a few million over a few decades. |
| #5 - Fast, predictable verification | Each check has to be quick, and take the same time whatever the message, so nobody can craft messages that are slow to check. |
| #6 - Aggregation | Many signatures on the same vote have to be combined into one proof that's checked in one go. |
| #7 - Secure against quantum computers | Nobody can forge a signature, even with a large quantum computer, and even after seeing as many of your signatures as they like. |
Building leanXMSS step by step
The rest of this page builds leanXMSS one step at a time. Each step starts from a given signature scheme, and alters it to add more of the mandatory properties. The first step is the BLS scheme.
BLS signatures
BLS is the scheme Ethereum validators use today. It's built on an elliptic curve: a set of points with a special way of "adding" two points to get a third one. Adding a point to itself many times is called multiplying it by a number.
- Key generation. The private key is a random number. The public key is a fixed starting point on the curve, multiplied by the private key. Multiplying is fast, but given the result, finding the number it was multiplied by is considered to take a classical computer billions of years.
- Signing. Turn the message into a point on the curve with a hash function, then multiply that point by the private key. The result is the signature.
- Verifying. A special function on the curve, called a pairing, lets anyone check that the signature and the public key were made with the same private key, without knowing that key.
Here is how BLS does on each mandatory property:
- #1 - Keys that are practical to create and store. Creating a key means picking a random number and doing one multiplication, which is instant. The private key is 32 bytes.
- #2 - Small public keys. A public key is a single point on the curve: 48 bytes.
- #3 - Small signatures. A signature is also a single point: 96 bytes, whatever the message.
- #4 - One public key for a whole life. A BLS key can sign any number of messages. One key pair serves a validator for as long as it runs.
- #5 - Fast, predictable verification. Checking a signature always takes the same work: turn the message into a point, then compute two pairings. That's about a millisecond on an ordinary machine, and no message is slower to check than another.
- #6 - Aggregation. Signatures add up. Add many signatures on the same message together, and add their public keys together, and the sum of the signatures checks out against the sum of the public keys. A single check covers thousands of validators. That's why Ethereum chose BLS.
- #7 - Secure against quantum computers. This is where BLS fails. Going back from the public key to the private key is hard for a classical computer, but a large enough quantum computer could do it quickly, with Shor's algorithm. Every validator's public key is on chain, so an attacker with such a machine could compute every validator's private key and sign in the name of all of them.
BLS has almost every mandatory property. It misses only one, but not a small one: it isn't secure against quantum computers. The rest of this page builds a scheme that ticks every box.
| Property | BLS signatures |
|---|---|
| #1 - Keys that are practical to create and store | ✅ |
| #2 - Small public keys | ✅ |
| #3 - Small signatures | ✅ |
| #4 - One public key for a whole life | ✅ |
| #5 - Fast, predictable verification | ✅ |
| #6 - Aggregation | ✅ |
| #7 - Secure against quantum computers | ❌ |
Lamport signatures
BLS can be broken by a quantum computer, as explained above. We need a signature scheme that Shor's algorithm can't break. A scheme built only from a hash function is one: Shor's algorithm doesn't apply to hash functions.
A hash function turns any input into a short, fixed-size output that looks random. Ethereum's hash function, Keccak-256, outputs 32 bytes. Computing a hash is fast, but going back from a hash to an input that produces it is considered to take billions of years: the only known method is guessing, about 2²⁵⁶ tries. A quantum computer guesses faster, with Grover's algorithm, but that only brings it down to about 2¹²⁸ tries, which still takes billions of years. So you can publish the hash of a secret without revealing the secret, and later, when you reveal it, anyone can hash it and see that it matches.
That proves you know a secret, but a signature also has to say which message you approve. The Lamport signature, invented in 1979, does this with nothing but hashes. Here it is on a tiny message of 4 bits.
The message. Four bits, for example 1011. Number them from left to right: bit 0 is 1, bit 1 is 0, bit 2 is 1 and bit 3 is 1.
The private key. For each of the four bits, pick two random secrets. The first one stands for "this bit is 0", the second one for "this bit is 1". That's 8 secrets: 2 per message bit, one for the 0 value of the bit and one for the 1 value. Name them by bit and value: a0 and a1 for bit 0, b0 and b1 for bit 1, and so on. When signing, you'll reveal only the one that matches the bit's actual value.
bit 0 bit 1 bit 2 bit 3
if bit is 0: a0 b0 c0 d0
if bit is 1: a1 b1 c1 d1
Each secret is a random 32-byte number, the same size as a hash. For example:
a0 = 0xd50ae76437a2caf062c8ca597b7edff500e7229ce2a75d6b1acb908fe3769e43
The private key is all the secrets put end to end.
private key = a0 ‖ a1 ‖ b0 ‖ b1 ‖ c0 ‖ c1 ‖ d0 ‖ d1
The public key. Hash each of the 8 secrets, and publish the 8 hashes in the same layout. H(a0) stands for the hash of a0. Anyone can see them, but nobody can work back to the secrets.
bit 0 bit 1 bit 2 bit 3
if bit is 0: H(a0) H(b0) H(c0) H(d0)
if bit is 1: H(a1) H(b1) H(c1) H(d1)
Each hash is 32 bytes. For example, with Keccak-256:
H(a0) = 0x7a10b2e126327a3e175505e4b43f39fe19c539381c2ec5a47167ce17d7739dce
The public key is all the hashes put end to end.
public key = H(a0) ‖ H(a1) ‖ H(b0) ‖ H(b1) ‖ H(c0) ‖ H(c1) ‖ H(d0) ‖ H(d1)
The signature. For each bit of the message, reveal the secret from the matching row. The other four secrets stay hidden.
message: 1 0 1 1
signature: a1 b0 c1 d1
Each revealed secret is 32 bytes. For example, the first one:
a1 = 0x1eb32b7430e9a35f797989fd6eb5c1f15b52124c03014bb9a4efc86bc7ca3c1a
The signature is all the revealed secrets put end to end.
signature = a1 ‖ b0 ‖ c1 ‖ d1
Verifying. For each bit, hash the revealed secret and compare it with the public key entry in the same place. H(a1) must match the "bit is 1" entry of bit 0, H(b0) the "bit is 0" entry of bit 1, and so on. If all four match, the signature is valid.
Why nobody can forge it. To sign 0011 instead, a forger needs a0. The signer never revealed it, and the public key only holds its hash, which can't be reversed. Changing any bit of the message needs a secret that was never shown.
Here is how Lamport does on each mandatory property. A real message can be any length, so in practice you sign its 32-byte hash: 256 bits, so 512 secrets.
-
#1 - Keys that are practical to create and store. One private key is 512 secrets: 16 KB. That's easy to create and to store. Lamport meets this one.
-
#2 - Small public keys. The public key is 512 hashes: 16 KB, against 48 bytes for BLS.
-
#3 - Small signatures. A signature reveals 256 secrets: 8 KB, against 96 bytes for BLS. Each revealed secret carries a single bit of the message, which is why it's so big.
-
#4 - One public key for a whole life. A key can sign only once. Using the previous example, if the same key that signed
1011also signs0010, it revealsa0andd0too. A forger then holds both secrets for bits 0 and 3, and can sign two messages that were never signed:0011and1010. Each new signature gives away more secrets. So a validator would need a new key for every message it ever signs: millions of them, tens of gigabytes.Try it: with the key below, sign
1011, then sign0010with the same key. Then check whether a forger can now sign0011.A 4-bit Lamport keyreal Keccak-256 · values shortenedMessage to signbit 0bit 1bit 2bit 3if bit is 0a0 = hiddenH(a0) = …b0 = hiddenH(b0) = …c0 = hiddenH(c0) = …d0 = hiddenH(d0) = …if bit is 1a1 = hiddenH(a1) = …b1 = hiddenH(b1) = …c1 = hiddenH(c1) = …d1 = hiddenH(d1) = …secret, still hiddenrevealed by a signatureboth secrets of this bit revealedNo signatures yet. The public key is published, and every secret is hidden.
Message a forger wantsForgery blockedTo sign 0011, the forger needs a0, b0, c1, d1, which were never revealed. Only their hashes are public, and a hash can't be reversed. -
#5 - Fast, predictable verification. Checking a signature means hashing 256 secrets, which takes a fraction of a millisecond, and the work is the same for every message. Lamport meets this one.
-
#6 - Aggregation. There's no way to add Lamport signatures together the way BLS does. Each one has to be sent and checked on its own.
-
#7 - Secure against quantum computers. Lamport is built from a hash function and nothing else. A quantum computer only speeds up guessing, which isn't enough to reverse a hash.
| Property | BLS signatures | Lamport signatures |
|---|---|---|
| #1 - Keys that are practical to create and store | ✅ | ✅ |
| #2 - Small public keys | ✅ | ❌ |
| #3 - Small signatures | ✅ | ❌ |
| #4 - One public key for a whole life | ✅ | ❌ |
| #5 - Fast, predictable verification | ✅ | ✅ |
| #6 - Aggregation | ✅ | ❌ |
| #7 - Secure against quantum computers | ❌ | ✅ |
To get #7, we gave up four properties BLS already had: #2, #3, #4 and #6. The next steps win them back, one at a time, without losing #7.
Hash chains
Each secret revealed in a Lamport signature stands for only one bit of the message. So a signature needs 256 of them: 8 KB.
In Lamport, each revealed secret answers a question with two possible answers: is this bit 0 or 1? A hash chain lets a single revealed value answer a question with four possible answers: 0, 1, 2 or 3. Four answers carry 2 bits at once, so a signature needs half as many values.
Building a chain. Pick a random 32-byte secret and call it x0. Hash it to get x1. Hash x1 to get x2, and x2 to get x3. Each step forward is easy. Going back, from x3 to x2 for example, would mean reversing a hash, which nobody can do.
- The private key is the start of the chain,
x0. With one chain, that's the whole private key. To sign a real message you need many chains, as shown below, and the private key is then all their starts put end to end. - The public key is the end of the chain,
x3. With many chains, it's all their ends put end to end. - To sign a number from 0 to 3, reveal the position with that number. To sign 1, reveal
x1. - To verify, hash the revealed value until you reach position 3, and check that the result is the public key. A signature on 1 is hashed twice:
x1tox2, thenx2tox3.
Pick a number to sign, and watch what the signature reveals and what the verifier does with it:
Signing a whole message. Take the message's 32-byte hash, and split its 256 bits into pairs. Each pair is a number from 0 to 3: 00 is 0, 01 is 1, 10 is 2 and 11 is 3. That gives 128 numbers, and each one gets its own chain. The private key is the 128 chain starts, the public key the 128 chain ends, and a signature reveals one position on each chain: 128 values, 4 KB, half of Lamport's 8 KB.
Why 4 positions? Longer chains carry more bits per value, so you need fewer chains, and signatures get smaller. But each extra position is one more hash for the signer to compute and for the verifier to walk. For a 32-byte message hash:
| Positions per chain | Bits per value | Chains | Signature size | Hashes to build all chains | Hashes to verify (average) |
|---|---|---|---|---|---|
| 2 | 1 | 256 | 8 KB | 256 | 128 |
| 4 | 2 | 128 | 4 KB | 384 | 192 |
| 16 | 4 | 64 | 2 KB | 960 | 480 |
| 256 | 8 | 32 | 1 KB | 8,160 | 4,080 |
Going from 2 to 4 positions halves the signature for 50% more verifier work. Going on to 16 would halve it again, but the verifier would do 2.5 times as much.
The catch. Hashing only goes forward, and anyone can hash. If a signature reveals x1 on some chain, anyone can hash it to get x2 and x3. So a forger can take a real signature and raise any of its numbers, which gives a valid signature on a message the signer never approved. Raising is free; only lowering is impossible.
Try it with 4 chains, so 8 bits of message. Sign a message, then pick one a forger wants. Whenever every number the forger wants is at least the signed one, the forgery works:
No signature yet. The public key is the 4 chain ends.
The checksum
A forger can only move numbers up, never down. So the classic fix is to also sign a number that goes down whenever any message number goes up. Then every forgery needs at least one chain to go down, which nobody can do. That number is called the checksum.
Computing the checksum. For each number of the message, count how far it is from the top position, 3. Then add up these distances. For the message 1 0 2 1:
checksum = (3 - 1) + (3 - 0) + (3 - 2) + (3 - 1)
= 2 + 3 + 1 + 2 = 8
Raising any number of the message shrinks its distance to the top, so the checksum goes down.
Signing the checksum. Write the checksum in base 4 too, and sign its digits with extra chains, exactly like the message's numbers. 8 in base 4 is 2 0, because 8 = 2 × 4 + 0. With a 4-number message, the checksum is at most 4 × 3 = 12, so 2 extra chains are always enough. A signature now reveals one position on each of the 4 message chains and the 2 checksum chains.
Why the forgery fails now. Say the forger wants 2 1 3 1 instead. Its checksum is (3 - 2) + (3 - 1) + (3 - 3) + (3 - 1) = 5, which is 1 1 in base 4. The first checksum chain would have to go from 2 down to 1, which means reversing a hash. This always happens: whatever the forger raises, the checksum gets smaller, and a smaller number written with the same number of digits always has at least one lower digit.
Try the same forgery as before, now with the checksum:
checksum = (3 − 1) + (3 − 0) + (3 − 2) + (3 − 1) = 8 → in base 4: 2 0
No signature yet. The public key is the 6 chain ends.
checksum = (3 − 2) + (3 − 1) + (3 − 3) + (3 − 1) = 5 → in base 4: 1 1
For a real message. The message's hash gives 128 numbers, so the checksum is at most 128 × 3 = 384. Written in base 4, 384 is 1 2 0 0 0, which has 5 digits. So the checksum needs 5 extra chains, for 133 chains in all, and a signature is 133 × 32 bytes, about 4 KB.
Here is how hash chains with a checksum do on each mandatory property, for a real message with 133 chains:
-
#1 - Keys that are practical to create and store. The private key is 133 chain starts: about 4 KB. That's easy to create and to store.
-
#2 - Small public keys. The public key is 133 chain ends: about 4 KB, against 48 bytes for BLS.
-
#3 - Small signatures. A signature reveals 133 values: about 4 KB. That's half of Lamport's 8 KB, but still far from 96 bytes for BLS.
-
#4 - One public key for a whole life. A key still signs only once. With two signatures, a forger can start from the lower of the two revealed positions on every chain, checksum chains included, and hash forward from there. The checksum no longer stops them.
-
#5 - Fast, predictable verification. On each chain, the verifier hashes the revealed value up to the end:
3 - dhashes for a numberd. So the work depends on the message. Here is how much:- On the 128 message chains, the verifier does
3 - dhashes per chain. Added up, that's exactly the checksum,C. - On the 5 checksum chains, it does
3 - chashes for each base-4 digitcof the checksum. Added up, that's 15 minus the sum of the checksum's digits.
total = C + 15 - (sum of C's base-4 digits)The fastest message has all its numbers at 3:
Cis 0, and the total is 0 + 15 - 0 = 15 hashes. The slowest has all its numbers at 0:Cis 384, which is1 2 0 0 0in base 4, and the total is 384 + 15 - 3 = 396 hashes. Every other message lands in between, and someone could search for messages that are slow to check. Lamport had this property, and hash chains lose it. - On the 128 message chains, the verifier does
-
#6 - Aggregation. As with Lamport, signatures can't be combined. Each one has to be sent and checked on its own.
-
#7 - Secure against quantum computers. Still built from a hash function and nothing else.
| Property | BLS signatures | Lamport signatures | Hash chains |
|---|---|---|---|
| #1 - Keys that are practical to create and store | ✅ | ✅ | ✅ |
| #2 - Small public keys | ✅ | ❌ | ❌ |
| #3 - Small signatures | ✅ | ❌ | ❌ |
| #4 - One public key for a whole life | ✅ | ❌ | ❌ |
| #5 - Fast, predictable verification | ✅ | ✅ | ❌ |
| #6 - Aggregation | ✅ | ❌ | ❌ |
| #7 - Secure against quantum computers | ❌ | ✅ | ✅ |
So hash chains leave us worse off than Lamport: on top of everything Lamport was missing, we lost #5. The next step gets it back.
A fixed sum
With a checksum, the verifier's work depends on the message, anywhere from 15 to 396 hashes. #5 asks for the same work whatever the message.
The checksum works because it balances the message: when a message number goes up, a checksum number has to go down. A fixed sum gets the same balance without any extra chain.
The rule. The signer only signs messages whose numbers add up to one fixed total, called the target.
In the small examples so far, the message was just 8 bits, signed as they were. A real message is any text, so the signer first hashes it, then reads the first 8 bits of the hash as 4 numbers. The signer chooses the message, but not the numbers: they come out of the hash.
Signing with only the rule. Take 4 chains and a target of 6. The signer hashes the message and reads 4 numbers from the hash. If they add up to 6, it signs them. If they don't, it can't: the rule forbids it, and the signer can't change the message.
Why a target of 6? Each number goes from 0 to 3, so it's 1.5 on average, and 4 numbers add up to 6 on average. 6 is also the most common total: of the 256 sets of 4 numbers a hash can give, 44 add up to 6, more than for any other target. The further the target is from 6, the fewer sets reach it, down to a single one for 0 (0000) and for 12 (3333).
Type a message to see whether it can be signed. The grid shows all 256 sets of 4 numbers, and highlights those that add up to the target. Then change the target, and watch how many sets are left: even at 6, only about 1 message in 6 can be signed.
- 1. Its Keccak-256 hash, 32 bytes
0x47a0ca3e91930c161cd91c63ce966df588e59df4f5e5534564d48c0ce03ac686 - 2. Its first byte, 8 bits, split into pairs
0x47 = 01 00 01 11 - 3. Each pair is a number from 0 to 3
01 → 1, 00 → 0, 01 → 1, 11 → 3, which add up to 1 + 0 + 1 + 3 = 5
Only 44 of the 256 possible hashes add up to 6: about 1 message in 6 can be signed.
With only 8 bits, many messages share the same numbers, so a forger could simply look for another message that gives the same 8 bits, and reuse the signature. A real signature uses all 256 bits of the hash, where finding such a message is hopeless.
A scheme that can sign only a few messages is useless: a validator has to sign its vote, whatever it is.
Meeting the rule. The signer can't change the message, but it can change what gets hashed. It adds a counter, called the randomizer ρ (rho), and tries ρ = 0, 1, 2 and so on, until the numbers of hash(message ‖ ρ) add up to the target. This is called grinding. The winning ρ goes into the signature, so the verifier can compute the same hash.
numbers = hash(message ‖ ρ), split into base-4 digits
try ρ = 0, 1, 2, … until the numbers add up to the target
signature = ρ ‖ one revealed position per chain
Verifying. The verifier recomputes the numbers from the message and ρ, and checks that they add up to the target. Then, on each chain, it hashes the revealed value 3 - d times and compares the result with the public end of the chain.
Why a forger is stuck. A forgery must pass the same check, so its numbers must add up to the target too. From a real signature, a forger can raise a number by hashing forward. But raising one number pushes the sum above the target, so another number would have to go down. Lowering means walking a chain backward, which nobody can do.
Why verification is predictable. On each chain, the verifier hashes 3 - d times. Over all chains, that's 3 × the number of chains, minus the sum of the numbers. The sum is always the target, so the work is the same for every signature. With 128 chains and a target of 192, every signature takes 384 - 192 = 192 hashes.
Try it with 4 chains and a target of 6. Type a message and sign it: the panel lists every ρ the signer tries. Then play the forger. You can even pick any 4 numbers you like, which a real forger can't do, since they come out of a hash:
- 1. Keccak-256 hash of the message and ρ = 0, 32 bytes
0xe2b7792c08af020308eda4ef74aa06b9a20c1d9bc7337982cad71fe9c41576f0 - 2. Its first byte, 8 bits, split into pairs
0xe2 = 11 10 00 10 - 3. Each pair is a number from 0 to 3
11 → 3, 10 → 2, 00 → 0, 10 → 2, which add up to 3 + 2 + 0 + 2 = 7
- 4. Grinding: try ρ = 0, 1, 2… until the numbers add up to 6
Press “Sign it” to start.
No signature yet.
Start the search somewhere secret. The panel starts at ρ = 0 to keep things simple. A real signer shouldn't. If the search always starts at 0, anyone can work out in advance which ρ the signer will use for any message. An attacker can use that before anything is signed: they look for two messages, a harmless one and a harmful one, whose hashes give the same numbers with the ρ the signer will pick. Then they get the signer to sign the harmless one, and the signature also works for the harmful one.
Finding two inputs with the same hash, both of your choosing, is called a collision. It's much easier than finding an input that matches a given hash: about 2¹²⁸ tries instead of 2²⁵⁶ for a 32-byte hash. That's still far out of reach. But leanXMSS uses shorter, 16-byte hashes to keep signatures small, and there a collision takes only about 2⁶⁴ to 2⁷⁴ tries, within reach of a well-funded attacker.
The fix is to start the search at a value only the signer can compute, derived from its private key and the message. Nobody can predict ρ before the signature exists. Once it exists, the numbers are fixed, and a forger has to find another message that gives exactly those numbers: matching a given hash, not just any two. And because the start comes from the message, signing the same message twice gives the same ρ, and the same signature.
start = hash(private key ‖ message)
try ρ = start, start + 1, start + 2, … until the numbers add up to the target
The exact formula leanXMSS uses for the start is shown further down.
Picking the target. A higher target leaves less work for the verifier, but fewer hashes add up to it, so the signer grinds longer. For 128 chains:
| Target | Verifier hashes, for every signature | Signer tries, on average |
|---|---|---|
| 192, the average sum | 192 | about 32 |
| 220 | 164 | about 370 |
| 240 | 144 | about 45,000 |
| 250 | 134 | about 1,350,000 |
Moving work from the verifiers to the signer is a good trade: each signature is made once, but checked by thousands of nodes.
Here is how a fixed sum does on each mandatory property, with 128 chains:
- #1 - Keys that are practical to create and store. The private key is 128 chain starts: 4 KB.
- #2 - Small public keys. The public key is 128 chain ends: 4 KB, against 48 bytes for BLS.
- #3 - Small signatures. A signature is ρ and 128 revealed values: about 4 KB, slightly smaller than with the checksum, but still far from 96 bytes for BLS.
- #4 - One public key for a whole life. A key still signs only once. With two signatures, a forger can start from the lower of the two revealed positions on every chain. These add up to less than the target, so the forger can raise them back to the target in many ways, and grinds their own message until it lands on one.
- #5 - Fast, predictable verification. Every signature takes the same number of hashes, set by the target. We have it back.
- #6 - Aggregation. Signatures still can't be combined.
- #7 - Secure against quantum computers. Still built from a hash function and nothing else.
| Property | BLS signatures | Lamport signatures | Hash chains | A fixed sum |
|---|---|---|---|---|
| #1 - Keys that are practical to create and store | ✅ | ✅ | ✅ | ✅ |
| #2 - Small public keys | ✅ | ❌ | ❌ | ❌ |
| #3 - Small signatures | ✅ | ❌ | ❌ | ❌ |
| #4 - One public key for a whole life | ✅ | ❌ | ❌ | ❌ |
| #5 - Fast, predictable verification | ✅ | ✅ | ❌ | ✅ |
| #6 - Aggregation | ✅ | ❌ | ❌ | ❌ |
| #7 - Secure against quantum computers | ❌ | ✅ | ✅ | ✅ |
We're back to the same properties as Lamport: #1, #5 and #7. Nothing new is ticked, but everything got smaller:
| Lamport | Hash chains with a fixed sum | |
|---|---|---|
| Private key | 512 secrets, 16 KB | 128 chain starts, 4 KB |
| Public key | 512 hashes, 16 KB | 128 chain ends, 4 KB |
| Signature | 256 secrets, 8 KB | 128 values and ρ, about 4 KB |
Both keys are 4 times smaller, and signatures twice as small. That's progress, but still far from BLS's 48-byte public keys and 96-byte signatures.
One hash for the public key
The public key is 128 chain ends: 4 KB, against 48 bytes for BLS. Every node has to store one per validator.
The verifier doesn't actually need the chain ends in advance. It rebuilds them from the signature anyway: on each chain, it hashes the revealed value up to the end. So instead of publishing all 128 ends, the signer can publish a single hash of them. The verifier hashes the ends it rebuilt, and compares the result with that one hash.
- The private key doesn't change: the 128 chain starts.
- The public key is now one hash of all the chain ends: 32 bytes.
- The signature doesn't change: ρ, then one revealed value per chain.
- To verify, recompute the numbers from the message and ρ, and check that they add up to the target. Hash each revealed value up to the end of its chain. Then hash all the ends together, and compare the result with the public key.
Why it's still safe. If a forger changes any revealed value, the end of that chain changes, and so does the hash of all the ends. To get the right public key anyway, they would need different ends that hash to the same value: matching a given hash, which nobody can do.
Sign a message, and follow the verifier as it rebuilds the ends and compares. Then let a forger change a single bit of the signature:
- 1. Keccak-256 hash of the message and ρ = 0, 32 bytes
0x06227a95e356742901afc4c02fbcfd7f80dc5178b55fbdaf0c4f7bf2e6abb7f1 - 2. Its first byte, 8 bits, split into pairs
0x06 = 00 00 01 10 - 3. Each pair is a number from 0 to 3
00 → 0, 00 → 0, 01 → 1, 10 → 2, which add up to 0 + 0 + 1 + 2 = 3
- 4. Grinding: try ρ = 0, 1, 2… until the numbers add up to 6
Press “Sign it” to start.
Only the public key is published. Sign the message to see the verifier at work.
hash(end0 ‖ end1 ‖ end2 ‖ end3)…published once…The 128 chains, together with this one hash, form a one-time key: a key that signs a single message.
Here is how a one-time key does on each mandatory property:
- #1 - Keys that are practical to create and store. The private key is still 128 chain starts: 4 KB.
- #2 - Small public keys. The public key is a single hash: 32 bytes, even smaller than BLS's 48 bytes.
- #3 - Small signatures. A signature is still ρ and 128 revealed values: about 4 KB, against 96 bytes for BLS.
- #4 - One public key for a whole life. A one-time key still signs only once, as its name says.
- #5 - Fast, predictable verification. The verifier does one more hash, over all the ends, for every signature. The work is still the same whatever the message.
- #6 - Aggregation. Signatures still can't be combined.
- #7 - Secure against quantum computers. Still built from a hash function and nothing else.
| Property | BLS signatures | Lamport signatures | Hash chains | A fixed sum | One hash for the public key |
|---|---|---|---|---|---|
| #1 - Keys that are practical to create and store | ✅ | ✅ | ✅ | ✅ | ✅ |
| #2 - Small public keys | ✅ | ❌ | ❌ | ❌ | ✅ |
| #3 - Small signatures | ✅ | ❌ | ❌ | ❌ | ❌ |
| #4 - One public key for a whole life | ✅ | ❌ | ❌ | ❌ | ❌ |
| #5 - Fast, predictable verification | ✅ | ✅ | ❌ | ✅ | ✅ |
| #6 - Aggregation | ✅ | ❌ | ❌ | ❌ | ❌ |
| #7 - Secure against quantum computers | ❌ | ✅ | ✅ | ✅ | ✅ |
A tree of one-time keys
A one-time key signs a single message. A validator signs a few million messages in its life, so it would need a few million one-time keys, and would have to publish a new public key for every message.
The signer creates many one-time keys up front, and builds a single public key that stands for all of them. To do that, it uses a Merkle tree:
- The leaves are the public keys of the one-time keys. Each one is the hash of the last positions of the key's chains, as in the previous step:
hash(end0 ‖ end1 ‖ … ‖ end127), 32 bytes. - Each node above is the hash of its two children:
parent = hash(left ‖ right). Each level has half as many nodes as the one below. - The root is the single node at the top. It's the validator's public key: 32 bytes, however many leaves there are.
Signing. The signer picks a leaf it has never used, and signs with that one-time key, as in the previous step. The signature also carries:
- The leaf index: the position of the leaf in the row, counting from 0.
- The path, also called the Merkle proof: the sibling of each node on the way from the leaf up to the root, one per level.
signature = leaf index ‖ ρ ‖ one revealed value per chain ‖ path
For example, in a tree of 8 leaves, the signature of leaf 5 carries 3 siblings, one per level:
path = leaf4 ‖ hash(leaf6 ‖ leaf7) ‖ hash(hash(leaf0 ‖ leaf1) ‖ hash(leaf2 ‖ leaf3))
Verifying. The verifier rebuilds the leaf from the one-time signature, as in the previous step. Then it climbs: it hashes the leaf with the first sibling of the path, hashes the result with the next sibling, and so on, up to the top. The signature is valid if the climb ends at the root.
At each level, the verifier has to know whether its node is the left or the right child, since hash(a ‖ b) and hash(b ‖ a) are different. The bits of the leaf index tell it: read from the right, one bit per level, 0 means left and 1 means right.
Why it's still safe. A forger who signs with a one-time key of their own gets a different leaf. To climb from it to the real root, at some level their two children would have to hash to the same parent as the real ones: matching a given hash, which nobody can do.
Pick a leaf and follow the climb. Then let a forger swap in a one-time key of their own:
- Leaf index 5 = 101 in binary
Read from the right, one bit per level: 0 means the node is on the left, 1 on the right.
from leaf 5 and its path…the root, published once…How many leaves. A tree with h levels has 2h leaves. A leanXMSS key covers 2³² leaves, about 4.3 billion one-time keys, so a single tree would have 32 levels, and a path of 32 hashes: 1 KB. In PQ Gasper, each leaf is tied to a slot and a type of message, as shown further down. With that layout, a key lasts about 178 years.
Never use a leaf twice. Nothing in the math stops the signer from signing two different messages with the same leaf, and doing so helps forgers, as with Lamport signatures. So the signer keeps a record of the leaves it has already used, and updates it before any signature leaves the machine. A scheme that needs such a record is called stateful.
In PQ Gasper, the signer doesn't pick the leaf: each message has a fixed leaf, computed from its type and its slot, or its target epoch for an attestation (PQ Gasper spec). Reusing a leaf would then mean signing two different messages of the same type for the same slot, which an honest validator never does: for blocks and attestations, it's even slashable.
Here is how a tree of one-time keys does on each mandatory property:
- #1 - Keys that are practical to create and store. To publish the root, the signer first has to compute every leaf: 2³² one-time keys of 128 chains, each chain hashed 3 times. That's about 1.7 trillion hashes, which takes days. And all the chain starts take 2³² × 4 KB: 16 TB.
- #2 - Small public keys. The public key is the root: 32 bytes.
- #3 - Small signatures. A signature is the leaf index, ρ, 128 revealed values and 32 path hashes: about 5 KB, against 96 bytes for BLS.
- #4 - One public key for a whole life. One root covers 2³² one-time keys, enough for any validator.
- #5 - Fast, predictable verification. The verifier does the same work as before, plus 32 hashes to climb the tree. That's the same for every signature.
- #6 - Aggregation. Signatures still can't be combined.
- #7 - Secure against quantum computers. Still built from a hash function and nothing else.
| Property | BLS signatures | Lamport signatures | Hash chains | A fixed sum | One hash for the public key | A tree of one-time keys |
|---|---|---|---|---|---|---|
| #1 - Keys that are practical to create and store | ✅ | ✅ | ✅ | ✅ | ✅ | ❌ |
| #2 - Small public keys | ✅ | ❌ | ❌ | ❌ | ✅ | ✅ |
| #3 - Small signatures | ✅ | ❌ | ❌ | ❌ | ❌ | ❌ |
| #4 - One public key for a whole life | ✅ | ❌ | ❌ | ❌ | ❌ | ✅ |
| #5 - Fast, predictable verification | ✅ | ✅ | ❌ | ✅ | ✅ | ✅ |
| #6 - Aggregation | ✅ | ❌ | ❌ | ❌ | ❌ | ❌ |
| #7 - Secure against quantum computers | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ |
We finally have #4, but we lost #1: creating the key takes days, and storing it takes 16 TB.
A top tree and bottom trees
To publish the root, the signer first has to compute all 2³² leaves: about 1.7 trillion hashes, which takes days. And it has to store the chain starts of all 2³² one-time keys: 16 TB.
A one-time key can sign any 32-byte value, not only the hash of a message. In particular, it can sign the root of another tree. That lets the signer split the work into two layers:
- The top tree holds 2¹⁶ = 65,536 one-time keys, the top keys. Its root is the public key. It's built when the key is created.
- The bottom trees: there are 65,536 different bottom trees, one per leaf of the top tree. Each holds 65,536 one-time keys, the bottom keys. Only bottom keys sign messages. Each bottom tree is built only when it's needed.
- Top key b signs the root of bottom tree b, written Rb.
That's 2¹⁶ × 2¹⁶ = 2³² bottom keys, as many as the leaves of the single tree in the previous step.
It's tempting to picture the bottom roots as the leaves of the top tree. They aren't.
Every leaf, top or bottom, is built the same way: the hash of the last positions of one one-time key's chains.
# from the chain ends of top key b
top leaf b = hash(end0 ‖ end1 ‖ … ‖ end127)
# from the leaves of bottom tree b
R_b = root of bottom tree b
Top leaf b and Rb are unrelated values, and neither is computed from the other.
What ties them together is a one-time signature: top key b signs Rb, the same way a bottom key signs a message.
That's why the top tree can be built before any bottom tree exists.
The leaf index picks two keys. As before, the 32-bit leaf index tells which bottom key signs the message. Its first 16 bits give the bottom tree b, and its last 16 bits give the key k inside that tree. Top key b is the one that signs Rb.
b = leaf index ÷ 65,536
k = leaf index mod 65,536
Which leaf for which message. In PQ Gasper, the signer doesn't pick any unused leaf: every message has a fixed leaf, computed from its type and its slot.
- The first 32,768 leaves are for messages a key signs at most once. A preregistration uses leaf 0, and a voluntary exit leaf 1.
- The next 2²⁹ leaves hold one attestation per target epoch. A validator never attests twice for the same target epoch, since that's a slashable double vote.
- All the leaves after that are split into 8 leaves per slot, one per type of message: block, aggregate, payload timeliness vote and so on.
preregistration: leaf index = 0
voluntary exit: leaf index = 1
attestation: leaf index = 32,768 + target epoch
other messages: leaf index = 32,768 + 2^29 + 8 × slot + offset of the message type
Pick a message and a slot, and see where its leaf lands:
- The target epoch
15,000,000 ÷ 32 = epoch 468,750 - The leaf index
leaf index = 32,768 + target epoch = 32,768 + 468,750 = 501,518 - The leaf index in binary, 32 bits
00000000000001111010011100001110 - First 16 bits: the bottom tree, and the top key that signs its root
b = 501,518 ÷ 65,536 = 7 - Last 16 bits: the key inside the bottom tree
k = 501,518 mod 65,536 = 42,766
When each tree is built.
- When the key is created, only the top tree is built. Each of its 65,536 leaves takes 385 hashes: 128 chains hashed 3 times, plus the leaf hash. With the tree on top, that's about 25 million hashes: a few seconds.
- The first time a key of bottom tree b has to sign, the signer builds tree b: another 25 million hashes. Top key b signs its root Rb, and the signer stores that signature. The signer can also build the next bottom tree in advance, so no signature has to wait.
- For each message signed in tree b, a bottom key signs the message, and the stored signature of Rb is copied into the signature as is.
Doesn't top key b sign 65,536 times? No. It signs one value, Rb, once. That single signature is then copied into all the signatures of tree b. A one-time key must never sign two different values, but showing the same signature again reveals nothing new.
The signature now has two halves. The bottom half is new for every message. The top half is the same for every message signed in tree b. Rb itself isn't included: the verifier rebuilds it from the bottom half.
signature = leaf index
‖ ρ⁰ ‖ 128 revealed values ‖ path in bottom tree b (16 hashes) # bottom key k signs the message
‖ ρ¹ ‖ 128 revealed values ‖ path in the top tree (16 hashes) # top key b signs R_b
ρ⁰ and ρ¹ are two different values: each half grinds its own. ρ⁰ makes the numbers of hash(message ‖ ρ⁰) add up to the target, and ρ¹ those of hash(R_b ‖ ρ¹).
Verifying.
- From the bottom half, rebuild the leaf of bottom key k from the message, as in the previous steps. Then climb its path: the top of the climb is Rb.
- From the top half, rebuild the leaf of top key b, with Rb as the message. Then climb its path, and compare the top of the climb with the public key.
Here is how two layers of trees do on each mandatory property:
- #1 - Keys that are practical to create and store. Creating a key takes about 25 million hashes: a few seconds. The secrets of a bottom tree only have to exist while that tree is in use: they can be drawn when the tree is built, and erased once all its keys are used. So the signer stores the top keys and one or two bottom trees at a time, 4 KB per one-time key: about half a gigabyte.
- #2 - Small public keys. The public key is the root of the top tree: 32 bytes.
- #3 - Small signatures. A signature now holds two one-time signatures and two paths: about 9 KB, against 96 bytes for BLS.
- #4 - One public key for a whole life. One root still covers 2³² bottom keys.
- #5 - Fast, predictable verification. The verifier does twice the work of the previous step: two one-time signatures and two climbs of 16 levels. That's the same for every signature.
- #6 - Aggregation. Signatures still can't be combined.
- #7 - Secure against quantum computers. Still built from a hash function and nothing else.
| Property | BLS signatures | Lamport signatures | Hash chains | A fixed sum | One hash for the public key | A tree of one-time keys | A top tree and bottom trees |
|---|---|---|---|---|---|---|---|
| #1 - Keys that are practical to create and store | ✅ | ✅ | ✅ | ✅ | ✅ | ❌ | ✅ |
| #2 - Small public keys | ✅ | ❌ | ❌ | ❌ | ✅ | ✅ | ✅ |
| #3 - Small signatures | ✅ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ |
| #4 - One public key for a whole life | ✅ | ❌ | ❌ | ❌ | ❌ | ✅ | ✅ |
| #5 - Fast, predictable verification | ✅ | ✅ | ❌ | ✅ | ✅ | ✅ | ✅ |
| #6 - Aggregation | ✅ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ |
| #7 - Secure against quantum computers | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
Shorter hashes and fewer chains
A signature holds two one-time signatures and two paths: about 9 KB. Every vote travels through the network on its own, so this is far too big.
Almost everything in a signature is a hash: the revealed values and the path nodes. Two changes make them smaller and fewer.
Keep only 16 bytes of each hash. Every hash in the scheme keeps only the first 16 bytes of Keccak-256, instead of all 32. That halves every revealed value and every path node.
It's still safe. Going back from a 16-byte hash to an input takes about 2¹²⁸ tries. A quantum computer running Grover's algorithm brings that down to about 2⁶⁴ steps, which have to run one after another. That's the level of security of the smallest post-quantum signatures standardized so far. A collision only takes about 2⁶⁴ tries, but the scheme never relies on collisions being hard: that's why the search for ρ starts somewhere secret.
Sign a 16-byte hash of the message. The hash of the message is now 16 bytes too: 128 bits, so 64 base-4 numbers, and 64 chains.
Force a few numbers to 0. A number that must be 0 carries no information, so it doesn't need a chain. leanXMSS changes the rule to:
- The first 58 numbers add up to 106.
- The last 6 numbers are all 0.
Only 58 chains are left.
Why force numbers instead of using a shorter hash? 58 base-4 numbers hold 116 bits. So the signer could also sign a 116-bit hash, with no forced numbers. But then a forger would only have to match 116 bits of the signed hash: about 2¹¹⁶ tries. With forced numbers, the hash is still 128 bits long, and a forger has to match all of it, the 6 forced numbers included: about 2¹²⁸ tries. The forced numbers cost the signer some grinding, and buy 12 bits of security for free.
Why 0? Any fixed value would work as well: each forced number has a 1 in 4 chance of matching it, whatever the value, and none of them needs a chain. 0 is the natural choice. The 64 numbers are the hash read as a number in base 4, smallest digit first, so the last 6 are its 6 highest digits. Requiring them to be 0 means the hash, read as a number, is smaller than 4⁵⁸ = 2¹¹⁶, just like a number written 000123 is really 123. The signature then signs a 58-digit number, whose digits are exactly the 58 chains.
Each forced zero makes the rule harder to meet, so the signer grinds longer: about 1 million values of ρ on average. That's a fraction of a second, and only the signer pays for it. The verifier always walks 58 × 3 - 106 = 68 steps along the chains.
Type a message and sign it, with the real leanXMSS rule. The panel runs in your browser, so it takes a few seconds to try a million values of ρ:
- 1. Keccak-256 hash of the message and ρ = 0, 32 bytes
0x082f378bb91f7446b4f03ddf9988842cc72baaf4534a4ce14f8bd0040a81d502 - 2. Keep the first 16 bytes: the digest
0x082f378bb91f7446b4f03ddf9988842c - 3. Each byte gives 4 numbers, 2 bits each, read from the rightbyte 0 · 0x08
00x3000x2010x1200x00byte 1 · 0x2f00x7010x6211x5311x43byte 2 · 0x3700x11011x10301x9111x83byte 3 · 0x8b10x15200x14010x13211x123byte 4 · 0xb910x19211x18310x17201x161byte 5 · 0x1f00x23001x22111x21311x203byte 6 · 0x7401x27111x26301x25100x240byte 7 · 0x4601x31100x30001x29110x282byte 8 · 0xb410x35211x34301x33100x320byte 9 · 0xf011x39311x38300x37000x360byte 10 · 0x3d00x43011x42311x41301x401byte 11 · 0xdf11x47301x46111x45311x443byte 12 · 0x9910x51201x50110x49201x481byte 13 · 0x8810x55200x54010x53200x520byte 14 · 0x8410x59200x58001x57100x560byte 15 · 0x2c00x63010x62211x61300x600 - 4. The rule✗ x58 to x63 are all 0✗ x0 to x57 add up to 88, not 106
- 5. Grinding: try ρ = 0, 1, 2… until the digest meets the rule
Press “Sign it” to start. - 6. Each of the 58 chains reveals the position given by its number
Other choices keep about the same grinding work:
| Chains | Forced zeros | Target | Verifier steps | Revealed values | Signer tries (average) |
|---|---|---|---|---|---|
| 64 | 0 | 136 | 56 | 1,024 bytes | about 650,000 |
| 60 | 4 | 117 | 63 | 960 bytes | about 750,000 |
| 58 | 6 | 106 | 68 | 928 bytes | about 1,050,000 |
Each row is as secure as the others, since a forger still has to match the signed 16-byte hash. leanXMSS picks 58 chains: the smallest signature, for a few more verifier steps.
The final size. Each half of the signature is now ρ (16 bytes), 58 revealed values (928 bytes) and a path of 16 nodes (256 bytes): 1,200 bytes.
signature = leaf index (4 bytes)
‖ ρ⁰ (16 bytes) ‖ 58 revealed values (928 bytes) ‖ path in bottom tree b (256 bytes)
‖ ρ¹ (16 bytes) ‖ 58 revealed values (928 bytes) ‖ path in the top tree (256 bytes)
= 2,404 bytes
This is the layout given in the leanXMSS spec.
| Previous step | Now | |
|---|---|---|
| Hash size | 32 bytes | 16 bytes |
| Chains per one-time key | 128 | 58 |
| One-time signature | about 4 KB | 944 bytes |
| Path | 16 × 32 = 512 bytes | 16 × 16 = 256 bytes |
| Signature | about 9 KB | 2,404 bytes |
Here is how shorter hashes and fewer chains do on each mandatory property:
- #1 - Keys that are practical to create and store. Even better than before. A leaf now takes 175 hashes: 58 chains hashed 3 times, plus the leaf hash. Building the top tree takes about 11.5 million hashes. Each one-time key holds 58 chain starts of 16 bytes: 928 bytes. In leanXMSS, the signer doesn't even store them: the private key is a single 32-byte seed, and every chain start is computed from it when needed (leanXMSS spec).
- #2 - Small public keys. The root of the top tree is now 16 bytes. The leanXMSS public key also includes a 16-byte random value, the public parameter: 32 bytes in all (leanXMSS spec).
- #3 - Small signatures. 2,404 bytes, about 4 times smaller than the previous step. That's still 25 times a BLS signature, but small enough to send every vote on its own.
- #4 - One public key for a whole life. One root still covers 2³² bottom keys.
- #5 - Fast, predictable verification. The verifier walks 68 chain steps per half, and climbs 16 levels per half, for every signature.
- #6 - Aggregation. Signatures still can't be combined.
- #7 - Secure against quantum computers. Matching a given 16-byte hash still takes about 2⁶⁴ steps with a quantum computer.
| Property | BLS signatures | Lamport signatures | Hash chains | A fixed sum | One hash for the public key | A tree of one-time keys | A top tree and bottom trees | Shorter hashes and fewer chains |
|---|---|---|---|---|---|---|---|---|
| #1 - Keys that are practical to create and store | ✅ | ✅ | ✅ | ✅ | ✅ | ❌ | ✅ | ✅ |
| #2 - Small public keys | ✅ | ❌ | ❌ | ❌ | ✅ | ✅ | ✅ | ✅ |
| #3 - Small signatures | ✅ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ✅ |
| #4 - One public key for a whole life | ✅ | ❌ | ❌ | ❌ | ❌ | ✅ | ✅ | ✅ |
| #5 - Fast, predictable verification | ✅ | ✅ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ |
| #6 - Aggregation | ✅ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ |
| #7 - Secure against quantum computers | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
Labels on every hash
A key computes a huge number of hashes, about 2⁴⁰ across all its chains and trees. To forge, an attacker has to find an input whose hash matches a value the verifier will check against, such as a chain value that hasn't been revealed yet. If any of those 2⁴⁰ values would do, each guess would get 2⁴⁰ chances to hit one, and 2¹²⁸ tries would drop to about 2⁸⁸. Across a million validators, about 2²⁰ keys, it would drop to about 2⁶⁸.
The fix is to make every hash call different from every other one, by putting two 16-byte labels in front of its input. A hash with labels like this is called a tweakable hash, written Th:
Th(P, A, M) = first 16 bytes of Keccak-256(P ‖ A ‖ M)
- A, the address, says which hash call this is inside the key: what it computes (a chain step, a leaf, a tree node, a digest), on which layer, for which one-time key, and at which position. No two hash calls of a key share an address, so a guess aimed at one address can only hit the hash with that address. Attacking all the hashes of a key at once is then no easier than attacking one.
- P, the public parameter, is 16 random bytes picked for each key. It does the same job across keys: attacking a million validators at once is no easier than attacking one.
The verifier needs P to redo every hash, so P is published next to the root. The public key becomes root ‖ P: 32 bytes.
Every hash on this page is really a Th call, with its own address:
| Hash call | In leanXMSS |
|---|---|
| Chain step from position μ, on chain i | Th(P, A_chain(layer, key, μ), x ‖ i) |
| Leaf | Th(P, A_leaf(layer, key), end0 ‖ … ‖ end57) |
| Digest | Th(P, A_msg(layer, key), message ‖ ρ) |
| Tree node | Th(P, A_node(layer, level, j), left ‖ right) |
The chain step also hashes in the chain number i, written on 16 bytes, since its address doesn't contain it. And the digest's address contains the key, which on the bottom layer is the leaf index itself. So a signature only works at the leaf index it was made for: moved to another leaf, its digest changes.
The widgets earlier on this page leave these labels out, to stay readable. The widgets from here on use them exactly as the spec does.
How an address is written. An address is 16 bytes (leanXMSS spec):
- 4 bytes for the key, or for the node's position in its level;
- 3 bytes for the tree level, or the pair of chains, plus 2²³ on the top layer, so that the two layers never share an address;
- 1 byte for the type of hash call, plus 32 × μ for a chain step from position μ;
- 8 bytes that are always 0.
Numbers are written smallest byte first. Pick a hash call and see its address:
701100004 byteskey 4,4640000003 bytes0211 bytetype 1 + 32 × 100000000000000008 bytesalways 00x70110000000000210000000000000000: the address of one step along a chain. Numbers are written smallest byte first, so 4,464 (0x1170) is stored as 70 11 00 00.
Here is how labels on every hash do on each mandatory property:
- #1 - Keys that are practical to create and store. Unchanged.
- #2 - Small public keys. The public key is now the root and P: 32 bytes.
- #3 - Small signatures. Unchanged: 2,404 bytes. The labels go into the hashes, not into the signature.
- #4 - One public key for a whole life. Unchanged: 2³² leaves.
- #5 - Fast, predictable verification. The verifier hashes the same values as before, with labels in front: still the same work for every signature.
- #6 - Aggregation. Signatures still can't be combined.
- #7 - Secure against quantum computers. Stronger: an attacker can no longer aim at all the hashes of a key, or of all keys, at once.
| Property | BLS signatures | Lamport signatures | Hash chains | A fixed sum | One hash for the public key | A tree of one-time keys | A top tree and bottom trees | Shorter hashes and fewer chains | Labels on every hash |
|---|---|---|---|---|---|---|---|---|---|
| #1 - Keys that are practical to create and store | ✅ | ✅ | ✅ | ✅ | ✅ | ❌ | ✅ | ✅ | ✅ |
| #2 - Small public keys | ✅ | ❌ | ❌ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ |
| #3 - Small signatures | ✅ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ✅ | ✅ |
| #4 - One public key for a whole life | ✅ | ❌ | ❌ | ❌ | ❌ | ✅ | ✅ | ✅ | ✅ |
| #5 - Fast, predictable verification | ✅ | ✅ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
| #6 - Aggregation | ✅ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ |
| #7 - Secure against quantum computers | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
One seed for every secret
The signer has to know the chain starts of every one-time key: 2³² bottom keys and 2¹⁶ top keys, with 58 starts of 16 bytes each. That's about 4 TB. Even keeping only the top keys and the current bottom tree, it's about 120 MB, which changes with every new bottom tree and is hard to back up.
The chain starts don't have to be truly random. They only have to look random to anyone who doesn't hold the key. So the signer keeps a single random 32-byte seed, S₀, and computes each secret when it needs it, by hashing the seed with the address of that secret. A function that turns one secret into as many random-looking values as needed is called a pseudorandom function. The same seed and address always give the same output, and without the seed, the outputs can't be predicted.
- Tag the seed:
S = Keccak-256("leanXMSS" ‖ S₀). If the same 32 bytes were ever used by another system, that system would hash them differently, so a leak on that side would reveal nothing here. Adding a fixed label like this is called domain separation. - The public parameter:
P = Th(16 zero bytes, A_param, S). P comes from the seed too, so there's nothing extra to store. - The chain starts:
Keccak-256(P ‖ A_prf(layer, key, j) ‖ S)gives 32 bytes, which start two chains: the first 16 bytes start chain 2j, and the last 16 bytes chain 2j + 1. A one-time key needs 29 such calls for its 58 chains. - The start of the ρ search:
R₀ = Th(P, A_rnd(layer, key), S ‖ message), and the signer tries ρ = R₀, R₀ + 1, R₀ + 2 and so on. This is the secret start from earlier, made precise: it depends on the seed, the one-time key and the message. Signing the same message again at the same leaf gives the same signature.
Creating a key comes down to picking a random S₀, then building the top tree. The private key is S₀: 32 bytes. The public key is the root of the top tree and P: 32 bytes (leanXMSS spec).
Pick a one-time key and a chain, and follow the derivation. The test seed is the one of the spec's known-answer test, and its P matches the test's public key:
- 1. Tag the seed with the scheme's name
S = Keccak-256("leanXMSS" ‖ S₀)
= 0xc306f2f0b92ee43045d5250f965d59d3cb991c3ecf3441d3df46381cff75c5d1 - 2. The public parameter
P = Th(16 zero bytes, A_param, S)
= 0x8787ad501aafe4b64e2488107b5e3ec3, the last 16 bytes of the test public key 0x…8787ad501aafe4b64e2488107b5e3ec3 - 3. One Keccak call for chains 0 and 1
Keccak-256(P ‖ A_prf ‖ S), with A_prf = 0x00000000000000000000000000000000
= 0x853271e165902fb4ce38911c7437f3cafac3e2af2c2acf84e1d1f2609fdf5cb4 - 4. Its first 16 bytes start chain 0
x0 = 0x853271e165902fb4ce38911c7437f3ca - 5. Three steps along chain 0
x1 = Th(P, A_chain(0), x0 ‖ 0) = 0xc1da83f960c1d7704129b0f2db71f302
x2 = Th(P, A_chain(1), x1 ‖ 0) = 0x168200d1b54e95514e45f1b4bb1b0787
x3 = Th(P, A_chain(2), x2 ‖ 0) = 0x794ce0db1cba8b2d613ae9beda7645ec, the end
The seed doesn't record which leaves were already used. leanXMSS on its own leaves that to the signer, and PQ Gasper doesn't need it, since each message has a fixed leaf.
Here is how one seed for every secret does on each mandatory property:
- #1 - Keys that are practical to create and store. The private key is 32 bytes, as small as a BLS private key, and easy to back up. Creating a key takes about 14 million Keccak permutations: a few seconds.
- #2 - Small public keys. Unchanged: 32 bytes.
- #3 - Small signatures. Unchanged: 2,404 bytes.
- #4 - One public key for a whole life. Unchanged: 2³² leaves.
- #5 - Fast, predictable verification. Unchanged: the verifier never sees the seed.
- #6 - Aggregation. Signatures still can't be combined.
- #7 - Secure against quantum computers. The seed is only ever hashed.
| Property | BLS signatures | Lamport signatures | Hash chains | A fixed sum | One hash for the public key | A tree of one-time keys | A top tree and bottom trees | Shorter hashes and fewer chains | Labels on every hash | One seed for every secret |
|---|---|---|---|---|---|---|---|---|---|---|
| #1 - Keys that are practical to create and store | ✅ | ✅ | ✅ | ✅ | ✅ | ❌ | ✅ | ✅ | ✅ | ✅ |
| #2 - Small public keys | ✅ | ❌ | ❌ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
| #3 - Small signatures | ✅ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ✅ | ✅ | ✅ |
| #4 - One public key for a whole life | ✅ | ❌ | ❌ | ❌ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ |
| #5 - Fast, predictable verification | ✅ | ✅ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
| #6 - Aggregation | ✅ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ |
| #7 - Secure against quantum computers | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
One proof for many signatures
leanXMSS signatures can't be added together like BLS signatures. With about a million validators, about 31,000 of them attest in every slot. Putting all their signatures in a block would take 31,000 × 2,404 bytes, about 75 MB, and checking them would take 31,000 × 186 Keccak permutations, about 5.8 million.
Aggregation doesn't need the signatures themselves to combine. It only needs a way to convince every node, quickly, that all the signatures exist and are valid. That's what a proof does: whoever holds the signatures computes a short proof that they all pass verification, and anyone can check that proof without seeing them.
PQ Gasper uses a STARK, a kind of proof built only from hash functions, so it's also secure against quantum computers. The proof covers a list of statements. Each statement is a list of public keys, a leaf index and a message, and the proof shows that every one of those public keys signed that message at that leaf index:
statement = (public keys, leaf index, message)
That's one more reason attestations use the leaf of their target epoch: all the validators of a committee sign the same message at the same leaf index, so their signatures fit in a single statement.
From signatures to one proof per block.
- Each validator signs its attestation and sends it on the network, with its own 2,404-byte signature.
- The aggregator of each committee collects the signatures of its committee, and proves them with one proof.
- The proposer merges the aggregators' proofs into one proof for the block.
- The attestations in the block carry no signature at all, only the proof. Every node checks that single proof.
Why #5 matters here. Inside the proof, every hash of every verification is computed again, and that's expensive for whoever builds the proof. Because a leanXMSS verification always takes exactly 186 Keccak permutations, the work to prove a signature is known in advance and the same for every signature. That's the reason behind the fixed sum, and behind keeping chains short.
The PQ Gasper draft spec defines what the proof functions do, not the actual STARK. Its reference version just puts the signatures end to end and checks them one by one, and it caps a proof at 1 MiB. The size and the cost of the real proof are still being worked out.
Here is how leanXMSS with proofs does on each mandatory property:
- #1 - Keys that are practical to create and store. Unchanged: a few seconds to create a key.
- #2 - Small public keys. Unchanged: 32 bytes, the root and the public parameter.
- #3 - Small signatures. Unchanged: 2,404 bytes for each signature on the network. Blocks don't carry them anymore, only the proof.
- #4 - One public key for a whole life. Unchanged: 2³² leaves.
- #5 - Fast, predictable verification. A node checks one proof per block instead of one signature per attestation.
- #6 - Aggregation. The signatures of a committee, then of a whole block, are covered by a single proof.
- #7 - Secure against quantum computers. A STARK, like leanXMSS, is built only from hash functions.
| Property | BLS signatures | Lamport signatures | Hash chains | A fixed sum | One hash for the public key | A tree of one-time keys | A top tree and bottom trees | Shorter hashes and fewer chains | Labels on every hash | One seed for every secret | One proof for many signatures |
|---|---|---|---|---|---|---|---|---|---|---|---|
| #1 - Keys that are practical to create and store | ✅ | ✅ | ✅ | ✅ | ✅ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ |
| #2 - Small public keys | ✅ | ❌ | ❌ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
| #3 - Small signatures | ✅ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ✅ | ✅ | ✅ | ✅ |
| #4 - One public key for a whole life | ✅ | ❌ | ❌ | ❌ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
| #5 - Fast, predictable verification | ✅ | ✅ | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
| #6 - Aggregation | ✅ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ✅ |
| #7 - Secure against quantum computers | ❌ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
Summary
Every part of the signature from the top of this page now has a reason to be there:
signature = leaf index (4 bytes)
‖ ρ⁰ (16 bytes) ‖ 58 revealed values (928 bytes) ‖ path in bottom tree b (256 bytes)
‖ ρ¹ (16 bytes) ‖ 58 revealed values (928 bytes) ‖ path in the top tree (256 bytes)
= 2,404 bytes
- The leaf index says which one-time key signed: a leaf of a tree, split between a top tree and a bottom tree.
- ρ⁰ and ρ¹ are the values ground until the numbers add up to the target, one per layer.
- The revealed values are one position on each of the 58 chains.
- The paths let the verifier climb from each leaf to the root of its tree.
Back to the name. XMSS stands for eXtended Merkle Signature Scheme:
- Merkle signature scheme: one-time keys gathered under a Merkle tree, whose root is the public key. Ralph Merkle proposed it in 1979, and it's what a tree of one-time keys built.
- eXtended: XMSS, published in 2011 and standardized in RFC 8391, extends it, mainly by putting labels in front of every hash, as in labels on every hash. That keeps the scheme safe under weaker assumptions about the hash function.
- lean: leanXMSS is the version designed by the Lean Ethereum research effort. It stacks two layers of trees, uses one-time keys with the fixed sum in place of a checksum (the spec calls them WOTS⁺C), and picks every size for Ethereum validators.
leanXMSS next to BLS.
| BLS | leanXMSS | |
|---|---|---|
| Security rests on | A hard problem on elliptic curves | A hash function, Keccak-256 |
| Quantum computer | Broken | Not known to be broken |
| Private key | 32 bytes | 32 bytes, the seed |
| Public key | 48 bytes | 32 bytes, the root and P |
| Signature | 96 bytes | 2,404 bytes |
| Signatures per key | Unlimited | 2³², one message per leaf |
| Verification | Two pairings | 186 Keccak permutations, always |
| Aggregation | Built in | Through a STARK proof |
What it costs. Keccak-256 works by running one fixed scrambling step, called a permutation, on every 136-byte block of its input, so work is counted in permutations (leanXMSS spec):
| Task | Permutations |
|---|---|
| Verifying a signature | 186: per layer, 1 for the digest, 68 for the chains, 8 for the leaf and 16 for the path |
| Creating a key | 212 × 2¹⁶ - 1, about 14 million: per top key, 29 for the chain starts, 174 for the chains and 8 for the leaf, then the tree |
| Building a bottom tree | The same, about 14 million, once per bottom tree |
| Signing | About 2²⁰, one per value of ρ tried. The top half is ground once per bottom tree. |
The signer gives up after 2³² values of ρ, but the chance of getting that far is below e-2048: it never happens.
How secure it is (leanXMSS spec):
- Proved: if Keccak-256 behaves like an ideal random function, an attacker who computes q hashes forges a signature with probability at most q / 2¹²⁷. The proof is checked by a computer, in the Lean proof assistant, for the scheme exactly as specified, down to the bytes. A known attack shows the bound can't be much better: about 2¹²⁷ hashes.
- Not proved: attacks that use Keccak's internal structure, and quantum attackers. Against a quantum computer, the authors expect about 2⁶⁴ steps that have to run one after another, the same level as the smallest standardized post-quantum signatures.
- Out of scope: reusing a leaf. The proof assumes each leaf signs at most once, which is up to the signer, and which PQ Gasper handles by giving every message a fixed leaf.
Check it yourself. The panel below checks the signature of the spec's known-answer test, with the code that runs every widget from Labels on every hash on. It runs the full 186-permutation check in your browser. Let a forger change one bit, and see at which step the check fails:
- Public key, 32 bytes: the root, then P
0x4066673001949b6ff8b9299fd4ea17d28787ad501aafe4b64e2488107b5e3ec3 - Message, 32 bytes
0x030a11181f262d343b424950575e656c737a81888f969da4abb2b9c0c7ced5dc - Signature, 2,404 bytes
0x197ec3a54ab37fda07f17443a094323d907adaa5ab5ac29e75e5c84e1ae8fa946252a948a23ecd7478faec84792b4225813e106a0b17c90699f98c5654578559e9d511cfdfd25f17e1158a83dece055b7cbbca62ef0e7350a3a1482b476daaf2f4eaa39f9b747e05dcc889fd373e0f78c2d2803df1b33c71321ead659608d2bcf3a800f6bcc6dc61885d3423eb32d94741210ab62e48c4a372f146c7b1d1f3699dfc3956948e4133e7618e98368bc521706f9187dd42381c926e6078475722f81b4303819c6f25853cfad3999ed6f22347531448fe665f44a6be25252a6c8463ca37ab916721d8fd8be6a5bf98c41f0c08b55ee31c5c4d5b2730749ffeae75be72f88d33e6c9bee3b0ce32ecd5ab7d8d99bd2220eb0147e7d9e201b5072b8d05cf3c1d5a67df5e17e598a1b1643876bf2cdc4266671fe52e0172c99436173b233c14055b3d727427b0fcce99db56f62dc879f000ee30fdc15574bb0ed3b0e0482138ba0cb1746ddf3f60eb0d4e1b9530d8868e86eeaa4f61ad75c4e990a0cb6f53478461cfbb6ac3e6985a02f5a0ad92b9a977cb83c0b16de2acf7b34db9c68cd43d7a7e9c198193e079e8f269d7817a2327ae36829570da33d5abfe0e6c05bc1bf00c2544372091091c7567a7528efe2a8bf0bde46b41319a3b38cc614f835e2277db8fab2355dd4bcf1ba1cb3cfbbf479a4d937b732c43f3bd837ca9954f9cf0644935eec1f15406c7a295e14d17ca70ca12a6de8ed2f47c555b47c9d1e944cfb0cc1584f4e743d337666657abd592aed46d9abd29428fa1318700f01c4181fd4bec4c3f0dccc2b89871001dca52ac953cba0a179ad5fac76dc393a2bc29d851bb1eed8f0b1db11442a061f9e5891cb4e29a7c1dc10e965c284d88e019fa4dcb08017bbcb40d4565734b7d93c71ddadd7ea9baa11ccf36f5e24a53fa753b9cfb511ccfb24511b4bf196dae8bd79dca1e373ee7804ae75b782cc1ebd7fb5419477b91d9ebf770c8b8343950cd8188e6c214432dec181354e26bc63b400d8417c39c1d76dc026b3ab4846381bf1ee4a5fe0669e13516bcddd092972b32d04f85077c61e8612275c4ebedc44dcc14447bc9046ba255e76b9b8f8c1ef79ceba544825f8247982fb5d9db2bf5a35a2acf1b16fbaf13f7d0ff35159aa1784a9f29770c22eb8aff5f2cdd2fa237d3733589990c7599b9121288fb4238c76a6598049b0423d2783b958ed8e286fcdcc9c7afa44bdadbd2b35a1b3b514db5c2c629219f4149f826d7d4257763027b53a5e80fa0cc65ba4ba69f703ff9613dd9c1f6bdb5f7d7cf9ec5e2af83e5e450dfe1c2c70abc94799af8818783ecffb9eef78400d31568590d4c0be74625d5693016c5d1fb58a0c836dbaf119b3e3e4eb72bdb672b3aa5f4ad2eff3ffc781d1709f6c64fea5dec637a5d550d7f6705948678180238f3689a7d1d76bdb546d488114f00c20994547b704e8da939e2af6b25b00b00d950fef2b48e71dbfe36901773d8399110bed512835e099e0fd37a5ca0b25e36a2d8d686f3eeeb885d518ec0a638c5701de12b4f2b4dbe9bb1c9cccf8467343e6f6ed138d288788aa62a9d3ceb9983deb169c362bd6b2371e249da790caa01d4951ae802af942496b961d2d945dac632d0de257130f64d51e15a5fbb27f1ebd86a02973bfe579ebf2bc7b96d717d7e1ad1702a558ceb2931104cb12e0181f8cca79a1b4641250dd079d764315da3e353344731a6887cb8c4f40db18d48d4f6ace8d2e61d59400ef5989cbdaa9fb872a297399c7582eaf9c326fe710477a94a9acfffef86e551d9828cb74f904d8ef7f7371da1cac3350244ddbcce25a9343cbfa9ff26d99604e22002231acc274d9c653d27a145a1693d34fd7e2b655657494ae20ec973ef2171b841fe649a68d50fbeed24a4f431537fed5c83aba505623c0932a5312456784621fcf48d68f5f5c8baca777fa3e8fded83151af52f8a61ac16e081a995388c65cd1c4048dd23058730f99f30a1318d90645bc97e2a6e1f057aa77264e8fd64d90a9a666a089da47ed5221709188b035cbc33ff4475771d3e7f97c59198436cd01697c80f026eae8b62f6ab7ed85020c0435c2f6dc7c68cdb935d3cf7af3375148d8d930d9271558286eefdfae2b230515c77917a5cd0e53c0365b29c2a7fdc7c2a45f37b5404268d086e3dc03408809997e18db52a96b139ff9bbd1ac10ba2ca7bdc2816c8a8fb8617e7b2e4da6d9c25800654115d942225544ede646898a8f2e1b2e58fc23b04b27de90b979e92f7e476a37078a7fe7524d14e989d55801bafa76f2c95bab2be4d4e1aa7af0901230bbbe165eda4ced79f93451db1ae2ed96f61a5361eef7d273c72371ca9d3817444b57cb583faf664c136db0545d0c19b27dcea8e06915b0477a47e6eda88e4e21a08f58ef05fc2edfe56611b5c2eafdac533fbd128df912fe70dd80e7b2ff461653a1a20cb43dc26cbc63cba1f147ee535e9a6598eab4057eeae7a42880073e852b07e4577d253d81c2913dec65d791c633929ae20324d781c863b55f3f1e7f2b8109113cad9f69809ead710550fd0911d3eca56024fe59e803207385be64f30cdab3ad725625027480f249589bcfadaa6a405ad64af254205e8aa94f072debc845c24a7777dbe02ed63d7f6f52100e920f7f70eaa24da500f49647b30f3600c3957cf377e2e2a2e595ecd7afad88a4e023fac9309028f7df9b7466dc5813fe87ebfad134552dae21b798f47e4905402f49e8a73d34a869d4ea263c4155179bbae386f2c0143be22e4a06692413c055850d18184d154aafabced577ab971b8d60d04cbb7ca9659922c0e32495ad38ae45ddf1d17609d670cfd96ff6a83528c6b0a1675e41ec19659ce8ea00bdf0e7cf2b107be44b77fde15ab2109a0c101259ddf1b44cd65f63ad00debbc5f8bf0e20f143e0bba3ad02e9caae1af6f300cd3ca829cbbf608c3e04ed741d5accce221c756077ce07a80909344c2ccdfe30973ab9893053660959af119daba015c681fd76aae0cdb8e7343d642c3b99ebbd6f02618fce119b93ef375566204759ee9f3563822d6ab3933dce2b85c9d8db63c25007f30977950a050ed2ebfd640461ac486643152063d05fe12b659aa8e96d549b7cb4bc03138f53a8a4909d58190fd52d764d5ec35448e22a27ade99d7757248e16e4b88705dd2ed03c59a9f1afa7c0c518bef46d9358809fdac1edb2da8f88a1bec8c01585b24a16d234de5cb938315f701bec2298c91c08ff74e6e47c3b957202438611fdc0a87d2f2ae7141712cc8c51d7708c14ad3966d5af85e0aa41dec0925e54539f3ac2fce96901e960269ac44ec59a5e0d0becf655b47db2b06eb6c72a3fe61a3181eb3a9941bd2de28a063
- 1. Read the leaf index
leaf index = 2,781,052,441, so the bottom tree is b = 42,435 - 2. Bottom half: the message's digest
✓ last 6 numbers are 0 · ✓ first 58 add up to 106 - 3. Rebuild the leaf of bottom key 2,781,052,441, then climb to the root of its tree
0xf599467f08d5b980901799b080989f69 - 4. Top half: the digest of that root
✓ last 6 numbers are 0 · ✓ first 58 add up to 106 - 5. Rebuild the leaf of top key 42,435, then climb to the top
0x4066673001949b6ff8b9299fd4ea17d2
Two last details.
- Keccak-256 isn't SHA3-256. leanXMSS uses Ethereum's Keccak-256, which differs from the standard SHA3-256 in a single padding byte: 0x01 instead of 0x06. The two give different hashes for the same input.
- RANDAO uses something else. Today, a proposer adds randomness to the chain with its BLS signature of the epoch, which has exactly one valid value. A leanXMSS signer could pick among many valid values of ρ, and nudge the randomness. So PQ Gasper gives each validator a separate committed list of random values, a VRF tree, for this (PQ Gasper spec).