The Merkle signature scheme is a digital signature scheme based on hash trees (also called Merkle trees) and one-time signatures such as the Lamport signature scheme. It was developed by Ralph Merkle in the late 1970s and is an alternative to traditional digital signatures such as the Digital Signature Algorithm or RSA.
The advantage of the Merkle signature scheme is that it is believed to be resistant against quantum computer algorithms. The traditional public key algorithms, such as RSA and ElGamal would become insecure in case an effective quantum computer can be built (due to Shor's algorithm). The Merkle signature scheme however only depends on the existence of secure hash functions. This makes the Merkle signature scheme very adjustable and resistant to quantum computing. Note that Merkle signature is a one time signature with finite signing potential; the work of Moni Naor and Moti Yung on signature based on one-way permutations and functions (and the invention of universal one-way hash function) give a way to extend a Merkle like signature to a complete signature scheme.
The Merkle signature scheme can be used to sign a limited number of messages with one public key
pub
. The number of possible messages must be a power of two, so we denote the possible number of messages as
N
=
2
n
.
The first step of generating the public key
pub
is to generate
N
private/public key pairs
(
X
i
,
Y
i
)
of some one-time signature scheme (such as the Lamport signature scheme). For each
1
≤
i
≤
2
n
, a hash value of the public key
h
i
=
H
(
Y
i
)
is computed.
With these hash values
h
i
a hash tree is built, by placing these
2
n
hash values as leaves and recursively hashing to form a binary tree. Let
a
i
,
j
denote the node in the tree with height
i
and left-right position
j
. Then, the hash values
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,
a
1
,
0
=
H
(
a
0
,
0
|
|
a
0
,
1
)
and
a
2
,
0
=
H
(
a
1
,
0
|
|
a
1
,
1
)
. In this way, a tree with
2
n
leaves and
2
n
+
1
−
1
nodes is built.
The private key of the Merkle signature scheme is the entire set of
(
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
pub
is the root of the tree,
a
n
,
0
. The individual public keys
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
M
with the Merkle signature scheme, the signer picks a key pair
(
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).
First, the signer chooses a
(
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
sig
′
and corresponding public key
Y
i
. To prove to the message verifier that
(
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
h
i
=
a
0
,
i
was used to compute the public key
a
n
,
0
at the root of the tree. The path in the hash tree from
a
0
,
i
to the root be
n
+
1
nodes, call them
A
0
,
…
,
A
n
, with
A
0
=
a
0
,
i
=
H
(
Y
i
)
being a leaf and
A
n
=
a
n
,
0
=
pub
being the root.
We know that
A
i
is a child of
A
i
+
1
. To let the verifier calculate the next node
A
i
+
1
given the previous, they need to know the other child of
A
i
+
1
, the sibling node of
A
i
. We call this node
auth
i
, so that
A
i
+
1
=
H
(
A
i
|
|
auth
i
)
. Hence,
n
nodes
auth
0
,
…
,
auth
n
−
1
are needed, to reconstruct
A
n
=
a
n
,
0
=
pub
from
A
0
=
a
0
,
i
. An example of an authentication path is illustrated in the figure on the right.
These nodes
auth
0
,
…
,
auth
n
−
1
, the
Y
i
, and the one-time signature
sig
′
, together constitute a signature of
M
using the Merkle signature scheme:
sig
=
(
sig
′
|
|
Y
i
|
|
auth
0
|
|
auth
1
|
|
…
|
|
auth
n
−
1
)
.
Note that when using Lamport signature scheme for signing, the
sig
′
contains a part of the private key
X
i
.
The receiver knows the public key
pub
, the message
M
, and the signature
sig
=
(
sig
′
|
|
Y
i
|
|
auth
0
|
|
auth
1
|
|
…
|
|
auth
n
−
1
)
. First, the receiver verifies the one-time signature
sig
′
of the message
M
using the one-time signature public key
Y
i
. If
sig
′
is a valid signature of
M
, the receiver computes
A
0
=
H
(
Y
i
)
by hashing the public key of the one-time signature. For
j
=
1
,
…
,
n
−
1
, the nodes of
A
j
of the path are computed with
A
j
=
H
(
A
j
−
1
|
|
auth
j
−
1
)
. If
A
n
equals the public key
pub
of the Merkle signature scheme, the signature is valid.
