### Question 35. What is Merkle's Tree Signature
Scheme?

Merkle proposed a digital signature scheme that was based on both one-time
signatures (see Question 43) and a hash function
(see Question 94) and that provides an infinite tree
of one-time signatures [Mer90b].

One-time signatures normally require the publishing of large amounts
of data to authenticate many messages, since each signature can only be
used once. Merkle's scheme solves the problem by implementing the signatures
via a tree-like scheme. Each message to be signed corresponds a node in
a tree, with each node consisting of the verification parameters that are
used to sign a message and to authenticate the verification parameters
of subsequent nodes. Although the number of messages that can be signed
is limited by the size of the tree, the tree can be made arbitrarily large.
Merkle's signature scheme is fairly efficient, since it requires only the
application of hash functions.