Merkle Trees as a Signature Scheme: One Key, Many One-Time Keys

A hash-based signature rests on a single assumption: that a hash function is preimage-resistant. No factoring, no discrete logarithm, no elliptic curve structure. The price of that weak assumption is that the signing key is a large collection of secret values rather than one scalar, and the job of the construction is to publish a compact commitment to all of them and to prove, per signature, which one was used.

The one-time primitive comes first. Lamport’s scheme is the simplest: the secret key is $2n$ random strings for a message hash of $n$ bits, and the public key is their hashes. To sign, reveal one string per bit position, choosing the first or second depending on the bit. Verification hashes the revealed strings and compares. Revealing two strings for the same position, which happens if two different messages are signed, exposes enough to forge. Hence one-time: the scheme is secure for exactly one signature and collapses after two.

Building the tree

Take $2^h$ one-time key pairs. Hash each one-time public key to a leaf value, and build a binary hash tree over the leaves: a parent is the hash of its two children’s concatenation, and the root is the public key of the whole scheme. A signature consists of the one-time signature for the message plus the $h$ sibling hashes on the path from the chosen leaf to the root.

Verification recomputes the leaf from the one-time public key, then combines it with each authentication path element in turn, hashing upward. After $h$ steps the recomputed value must equal the published root. The path is $h$ hashes of output length each, so for $h = 20$ with SHA-256 the path is 640 bytes and the scheme supports $2^{20}$, about a million, signatures.

/* Fold an authentication path up to the root, given the leaf index. */
void root_from_path(const uint8_t leaf[32], uint8_t node[32],
                    const uint8_t *auth, unsigned index, unsigned height)
{
    memcpy(node, leaf, 32);
    for (unsigned level = 0; level < height; level++) {
        uint8_t buf[64];
        if (index & 1) {                   /* node is a right child */
            memcpy(buf, auth + 32 * level, 32);
            memcpy(buf + 32, node, 32);
        } else {                           /* node is a left child */
            memcpy(buf, node, 32);
            memcpy(buf + 32, auth + 32 * level, 32);
        }
        SHA256(buf, 64, node);   /* OpenSSL: <openssl/sha.h> */
        index >>= 1;
    }
}

The index is not transmitted as a separate field in most formats; it is implied by the one-time public key, since each leaf is at a known position. Getting the ordering within the hash wrong, or hashing the wrong operands at the wrong level, produces a root that never matches, which is at least a loud failure.

The state problem

The signer must never use the same leaf twice. Once a leaf’s one-time key has signed one message, that leaf is spent, and reusing it allows forgery. The obvious implementation keeps a counter of the next unused index, persists it, and increments it after each signature.

That counter is the scheme’s entire security-critical state, and it is a liability in several ways. A process that signs, crashes before persisting the incremented counter, and restarts will reuse a leaf. A backup restored from before a batch of signatures will reuse every leaf in the batch. A horizontally scaled service with two instances sharing a key and each holding its own copy of the counter will interleave and collide. Log shipping lag between two data centres produces the same result with a delay.

The consequence is asymmetric in a way that differs from ECDSA nonce reuse. Reusing an OTS leaf does not immediately reveal the long-term key. It reveals the second message’s signature for that leaf, and from two OTS signatures the attacker can forge additional OTS signatures under that leaf. The long-term key survives, and the root is unchanged, but every message that leaf could sign is now forgeable. If the leaf has signed messages under different contexts, the damage is confined to those contexts; if the signing policy is “one signature per message”, the attacker can sign arbitrary new messages with that leaf and they verify against the same root. The remaining leaves are unaffected, so the compromise is bounded but permanent for that index.

The state can be removed at a cost. A stateless scheme fixes the leaf index by deriving it from the message and a randomizer, so any leaf can be used for any signature and collisions are handled by the one-time scheme tolerating a small number of signatures per key, or by the construction having enough leaves that the birthday bound is safe. SPHINCS+ is the standardised example: it uses a few-time signature at the bottom and a hypertree of Merkle trees above, with the top tree’s height chosen so that the total number of signatures remains far below the collision threshold. The signature size grows accordingly, to several kilobytes, because every layer contributes an authentication path.

Trade-offs against number-theoretic schemes

The signature is large. A Merkle tree of height 20 with SHA-256 gives a 640-byte authentication path, since the path has 20 nodes of 32 bytes each. On top of that sits the one-time signature. Lamport’s scheme for a 256-bit hash reveals 256 values of 32 bytes, about 8 kilobytes, because one secret string per bit position is disclosed. Winternitz chains compress that: with a digit width of 4 bits, a 256-bit hash becomes 64 digits plus a 3-digit checksum, so 67 revealed values of 32 bytes, about 2.1 kilobytes, and each revealed value costs up to 15 hash computations to walk its chain to the right position. A width of 8 bits halves the count to 34 values, about 1.1 kilobytes, but raises the per-chain work to as much as 255 hashes. Total signature sizes therefore run from roughly 1.7 to 9 kilobytes depending on the parameter.

Verification is cheap and, crucially, uniformly cheap: a fixed number of hash evaluations, no secret-dependent branches, no modular arithmetic with variable timing. Signing is expensive because generating a leaf’s one-time key means hashing $2n$ random strings, and generating a tree means hashing every leaf. The full tree for $h = 20$ is a million leaves and can be precomputed once per key, then kept in storage; the signer only needs the authentication path for the current leaf, which is $h$ hashes, but maintaining the path incrementally as the index advances requires either storing the whole tree or recomputing subtrees on the fly.

There is a middle path that keeps signing fast at the cost of storage: store every node of the tree, which for $h = 20$ and 32-byte hashes is about 64 megabytes. That is a large key file but manageable on a server. The alternative, recomputing the path from the leaves each time, costs a full tree traversal per signature, which is $2^{20}$ hashes and no longer competitive with an RSA signature.

Key generation and the root

Generating the key means generating $2^h$ fresh secret values. A common shortcut derives them pseudorandomly from a single seed and the index, using a PRF or a hash of the seed and index. This makes the secret key a 32-byte seed, and the tree is regenerated from it on demand. The security argument then rests on the PRF’s output being unpredictable, which is the same assumption a symmetric cipher makes.

The root must be published and bound to an identity, which for a hash-based scheme means the same infrastructure as any other public key: a certificate, a key transparency log, or an out-of-band distribution. There is no structure in the root that reveals the scheme, so an implementation that expects a particular key encoding will reject a valid root from a different one. The encoding of the root, the seed, and the signature must match between signer and verifier exactly, which is what the various interoperability test vectors exist to pin down.

The tree’s height fixes a hard limit on the number of signatures. Running out is not a graceful degradation; the signer simply cannot sign. A deployment must either choose a height large enough for the key’s lifetime, or arrange to roll to a new key before exhaustion and publish the new root. A tree of height 20 with one signature per second exhausts in about twelve days, so the height is chosen against the expected signature rate and the key rotation policy, not against the key’s lifetime alone.

Where the construction fits

Hash-based signatures are chosen when the assumption matters more than the size: firmware signing keys that must remain verifiable for decades, code signing in environments where the verifier has no elliptic curve library, and any setting where a future quantum computer invalidates the number-theoretic assumptions but a hash function remains a hash function. The BLS aggregation construction in the number-theoretic world buys compactness and aggregation at the cost of pairings; the hash-based construction buys assumption minimalism at the cost of state and bytes. The gap between them is large and it is not going to close.

The one-time primitive underneath is the same idea as Poly1305’s one-time key: a secret that is safe exactly once, with a catastrophic failure on the second use. The difference is that Poly1305’s failure reveals a key through algebra, while an OTS leaf’s failure reveals only that leaf’s forgery capability. The tree is what makes the one-time primitive usable at scale, by giving the signer a way to choose a fresh leaf and a way for the verifier to connect that leaf to a single published value.