The signature scheme
A Winternitz one-time signature under a Merkle tree, over keccak256, with tweakable hashes. Verified on-chain in about 110k gas.
The scheme follows the layout of XMSS (RFC 8391) with the tweakable hashes of SPHINCS+ "simple", instantiated with keccak256: the one hash the EVM computes with a native opcode. Its security rests on keccak256 as a hash function and on nothing else.
Parameters
| Parameter | Value |
|---|---|
| Hash | keccak256, 32-byte output |
Winternitz parameter w | 16 (4 bits per digit) |
| Chains per one-time key | 67: 64 message digits + 3 checksum digits |
| Chain length | 15 steps (positions 0 to 15) |
| Tree height | Variable, read from the signature; at most 20 |
| Key | 32 bytes |
| Signature | 64 + 67·32 + 32·height bytes: 2,464 at height 8 |
| Post-quantum security | 128 bits against preimage search (Grover) |
Tweakable hashes
Every hash in the structure is
H(seed, address, data) = keccak256(seed ‖ address ‖ data)where seed is the key's 32-byte public seed and address is a word that says where in the structure the hash sits:
address = kind << 96 | a << 64 | b << 32 | ckind | Used for | a | b | c |
|---|---|---|---|---|
| 0 | Chain step | leaf | chain | step |
| 1 | Leaf | leaf | ||
| 2 | Tree node | height of its children | index at its level | |
| 3 | Key | tree height | ||
| 4 | Message | leaf |
No two hashes in any key share an input prefix. A value computed at one place is useless at every other place and in every other key: multi-target attacks get no discount.
The one-time signature
A leaf has 67 secret chain starts. Chain i is walked by hashing with address (0, leaf, i, step); its public end is
position 15.
To sign a 32-byte digest d with leaf ℓ:
m = H(seed, (4, ℓ), d): the message is bound to this seed and this leaf.- Split
minto 64 base-16 digitsd₀ … d₆₃. - Checksum
c = Σ (15 − dᵢ), written as 3 base-16 digits. - For each of the 67 digits, reveal the chain value at that digit's position.
The verifier walks each revealed value the remaining 15 − digit steps to reach the chain ends. To forge another
message from a signature, some digit has to go down, which means walking a chain backwards: a preimage. Raising a
message digit is possible, but it lowers the checksum, whose chains would then have to be walked backwards.
The tree
leaf node = H(seed, (1, ℓ), end₀ ‖ … ‖ end₆₆)
inner node = H(seed, (2, childHeight, index), left ‖ right)
key = H(seed, (3, height), root)The key commits to the seed, the height and the root. A signature carries the authentication path: one sibling per level, from the leaf to the root.
Signature layout
seed (32) | leaf index (32) | 67 chain values (32 each) | authentication path (32 per level)The height is the length of the path, so one verifier handles every tree size. The vault never stores a height: it is part of what the key commits to.
Verification on-chain
Xmss.recover(digest, signature) returns (key, leaf):
- Recompute
mand the 67 digits. - Walk the 67 chains to their ends: on average about 500 keccak256 calls.
- Hash the ends into the leaf node, then climb the path to the root.
- Return
H(seed, (3, height), root)and the leaf index.
The caller compares the key with the one it holds. A malformed signature returns the zero key, which belongs to no account. The whole function is assembly over a single scratch buffer: recovering a signature of a 1,024-leaf key costs about 110,000 gas.
Why recovery, not verification
The function returns the key instead of checking it against an input. This mirrors ecrecover: the vault looks up the
account's key and compares. A signature is valid for exactly one key, so nothing more needs to be passed in.
Test vectors
The TypeScript implementation in the SDK and the Solidity library are checked against each other with shared vectors
(contracts/test/XmssVectors.t.sol, generated by packages/sdk/scripts/gen-vectors.ts).