Merkle signature scheme

The Merkle signature scheme can be used to sign a limited number of messages with one public key ${\displaystyle {\text{pub}}}$. The number of possible messages must be a power of two, so we denote the possible number of messages as ${\displaystyle N=2^{n}}$.

The first step of generating the public key ${\displaystyle {\text{pub}}}$ is to generate ${\displaystyle N}$ private/public key pairs ${\displaystyle (X_{i},Y_{i})}$ of some one-time signature scheme (such as the Lamport signature scheme). For each ${\displaystyle 1\leq i\leq 2^{n}}$, a hash value of the public key ${\displaystyle h_{i}=H(Y_{i})}$ is computed.

Merkle Tree with 8 leaves

With these hash values ${\displaystyle h_{i}}$ a hash tree is built, by placing these ${\displaystyle 2^{n}}$ hash values as leaves and recursively hashing to form a binary tree. Let ${\displaystyle a_{i,j}}$ denote the node in the tree with height ${\displaystyle i}$ and left-right position ${\displaystyle j}$. Then, the hash values ${\displaystyle h_{i}=a_{0,i}}$ are the leaves. The value for each inner node of the tree is the hash of the concatenation of its two children. For example, ${\displaystyle a_{1,0}=H(a_{0,0}||a_{0,1})}$ and ${\displaystyle a_{2,0}=H(a_{1,0}||a_{1,1})}$. In this way, a tree with ${\displaystyle 2^{n}}$ leaves and ${\displaystyle 2^{n+1}-1}$ nodes is built.

The private key of the Merkle signature scheme is the entire set of ${\displaystyle (X_{i},Y_{i})}$ pairs. One of the major problems with the scheme is that the size of the private key scales linearly with the number of messages to be sent.

The public key ${\displaystyle {\text{pub}}}$ is the root of the tree, ${\displaystyle a_{n,0}}$. The individual public keys ${\displaystyle Y_{i}}$ can be made public without breaking security. However, as they are not needed in the public key, it is more practical to keep them secret to minimize its size.

To sign a message ${\displaystyle M}$ with the Merkle signature scheme, the signer picks a key pair ${\displaystyle (X_{i},Y_{i})}$, signs using the one-time signature scheme, and then adds additional information to prove that it was indeed one of the original key pairs (rather than one newly generated by a forger).

Merkle tree with path A and authentication path for i = 2, n = 3

First, the signer chooses a ${\displaystyle (X_{i},Y_{i})}$ pair which had not previously been used to sign any other message, and uses the one-time signature scheme to sign the message, resulting in a signature ${\displaystyle {\text{sig}}'}$ and corresponding public key ${\displaystyle Y_{i}}$. To prove to the message verifier that ${\displaystyle (X_{i},Y_{i})}$ was in fact one of the original key pairs, the signer simply includes intermediate nodes of the Merkle tree so that the verifier can verify ${\displaystyle h_{i}=a_{0,i}}$ was used to compute the public key ${\displaystyle a_{n,0}}$ at the root of the tree. The path in the hash tree from ${\displaystyle a_{0,i}}$ to the root be ${\displaystyle n+1}$ nodes, call them ${\displaystyle A_{0},\ldots ,A_{n}}$, with ${\displaystyle A_{0}=a_{0,i}=H(Y_{i})}$ being a leaf and ${\displaystyle A_{n}=a_{n,0}={\text{pub}}}$ being the root.

We know that ${\displaystyle A_{i}}$ is a child of ${\displaystyle A_{i+1}}$. To let the verifier calculate the next node ${\displaystyle A_{i+1}}$ given the previous, they need to know the other child of ${\displaystyle A_{i+1}}$, the sibling node of ${\displaystyle A_{i}}$. We call this node ${\displaystyle {\text{auth}}_{i}}$, so that ${\displaystyle A_{i+1}=H(A_{i}||{\text{auth}}_{i})}$. Hence, ${\displaystyle n}$ nodes ${\displaystyle {\text{auth}}_{0},\ldots ,{\text{auth}}_{n-1}}$ are needed, to reconstruct ${\displaystyle A_{n}=a_{n,0}={\text{pub}}}$ from ${\displaystyle A_{0}=a_{0,i}}$. An example of an authentication path is illustrated in the figure on the right.

These nodes ${\displaystyle {\text{auth}}_{0},\ldots ,{\text{auth}}_{n-1}}$, the ${\displaystyle Y_{i}}$, and the one-time signature ${\displaystyle {\text{sig}}'}$, together constitute a signature of ${\displaystyle M}$ using the Merkle signature scheme: ${\displaystyle {\text{sig}}=({\text{sig}}'||Y_{i}||{\text{auth}}_{0}||{\text{auth}}_{1}||\ldots ||{\text{auth}}_{n-1})}$.

Note that when using Lamport signature scheme for signing, the ${\displaystyle {\text{sig}}'}$ contains a part of the private key ${\displaystyle X_{i}}$.

The receiver knows the public key ${\displaystyle {\text{pub}}}$, the message ${\displaystyle M}$, and the signature ${\displaystyle {\text{sig}}=({\text{sig}}'||Y_{i}||{\text{auth}}_{0}||{\text{auth}}_{1}||\ldots ||{\text{auth}}_{n-1})}$. First, the receiver verifies the one-time signature ${\displaystyle {\text{sig}}'}$ of the message ${\displaystyle M}$ using the one-time signature public key ${\displaystyle Y_{i}}$. If ${\displaystyle {\text{sig}}'}$ is a valid signature of ${\displaystyle M}$, the receiver computes ${\displaystyle A_{0}=H(Y_{i})}$ by hashing the public key of the one-time signature. For ${\displaystyle j=1,\ldots ,n-1}$, the nodes of ${\displaystyle A_{j}}$ of the path are computed with ${\displaystyle A_{j}=H(A_{j-1}||{\text{auth}}_{j-1})}$. If ${\displaystyle A_{n}}$ equals the public key ${\displaystyle {\text{pub}}}$ of the Merkle signature scheme, the signature is valid.

• E. Dahmen, M. Dring, E. Klintsevich, J. Buchmann, L.C. Coronado Garca. "CMSS - an improved merkle signature scheme". Progress in Cryptology - Indocrypt 2006, 2006.
• E. Klintsevich, K. Okeya, C.Vuillaume, J. Buchmann, E.Dahmen. "Merkle signatures with virtually unlimited signature capacity". 5th International Conference on Applied Cryptography and Network Security - ACNS07, 2007.
• Ralph Merkle. "Secrecy, authentication and public key systems / A certified digital signature". Ph.D. dissertation, Dept. of Electrical Engineering, Stanford University, 1979.
• Moni Naor, Moti Yung: Universal One-Way Hash Functions and their Cryptographic Applications .STOC 1989: 33-43
• S. Micali, M. Jakobsson, T. Leighton, M. Szydlo. "Fractal merkle tree representation and traversal". RSA-CT 03, 2003

• Efficient Use of Merkle Trees - RSA labs explanation of the original purpose of Merkle trees + Lamport signatures, as an efficient one-time signature scheme.
• An introduction to hash-based signatures and Merkle signatures by Adam Langley.
• A 4 parts series on hash-based signatures by David Wong.