Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I was browsing the Wikipedia article on Merkle signature schemes and noted that it says:
The number of possible messages must be a power of two[…]
Why is that? If the nodes of tree are formed by hashing two public keys together by concatenation, why can't three or four be concatenated to form nodes? Also, since the structure does not take the form of certificates that contain a set of public keys signed by another public (root or otherwise), how can new keys be added?
You could, indeed, form a Merkle tree where each internal node is formed from the hash of 3 (or more) lower level nodes. However, because it hurts signature size (which is the main expense of Merkle trees), we never do it.
In a Merkle signature, we reveal the preimage to the leaf node (which may involve a Winternitz signature), and also the authentication path; that is, the internal values of the nodes that are hashed along the path between the leaf and the root.
For example, in this three level Merkle tree:
We reveal $H(Y[2])$, from which the verifier can compute the value $A[0]$. And to prove that it is the correct value, we reveal the values $auth[0]$ (so that the verifier can compute $A[1]$), the value $auth[1]$ (so that the verifier can compute $A[2]$), and the value $auth[2]$ (so that the verifier can compute $A[3]$, which is the root value). The verifier would then compute the computed root value from the expected value in the Merkle public key; if it compares, then either this was signed by the correct private key, or someone managed to find a preimage for either $A[0], A[1], A[2], A[3]$.
So, this Merkle tree can sign up to 8 signatures using a signature size of 3 hashes (plus whatever hashes the lower level Winternitz uses). In general, a Merkle tree of height $h$ can sign $2^h$ messages by revealing $h$ internal nodes.
Now, let us consider a Merkle tree where each internal node is 3 lower level nodes hashed together. In this case, every part of the authentication path must consider of 2 revealed nodes (as the verifier needs to be able to recompute that hash value of the internal node). So, we get a Merkle tree of height $h$ that can size $3^h$ messages, however each such message reveals $2h$ internal nodes.
It turns out that, for any desired total number of messages, the Merkle tree of degree 3 has a total authentication path that is at least as most (and usually more) than a Merkle tree of degree 2.
In addition, you asked:
how can new keys be added?
In a single level Merkle tree, we can't. Because the public key at the root is a complex function of all the leaf nodes, we need to compute all the leaf nodes (and the value of all the internal nodes) at key generation time.
However, we can get around this by using a two (or more) level Merkle tree. That is, we generate two Merkle trees, a top level one, and a bottom level one. And, we sign the root of the bottom level tree with the top level. We then use the bottom level one to sign actual messages (and the signature of this joint system would be the Merkle signature of the bottom level tree, along with the signature of the bottom level tree with the top level tree). We keep on signing the bottom level tree as new messages until that runs out.
Then, once that runs out, we generate a fresh bottom level Merkle tree, and sign that with the top level Merkle tree (which has signed only one value so far, and so can sign a second message). We can keep on signing; if both the top level and the bottom level trees are of height $h$, then we can sign a total of $2^{2h}$ messages, and only have to generate a total of $2^{h+1}$ leaf nodes (and internal nodes) when we generate the initial public key.
This does increase the signature size (because of the internal Winternitz signatures); however it does allow us to create a signature scheme that can sign a large number of messages, but doesn't require a huge amount of time to generate the public key.
Why is that? If the nodes of tree are formed by hashing two public keys together
by concatenation, why can't three or four be concatenated to form nodes?
Concatenating four "to form nodes" would still restrict N to
powers of two (since it would in fact restrict N to powers of 4).
Otherwise, my guess is that the result would not quite be the "Merkle signature scheme".
Also, since the structure does not take the form of certificates that contain a set of
public keys signed by another public (root or otherwise), how can new keys be added?
If the messages which get one-time signed include a bit that indicates whether the signature is internal (not the bottom row) or external (bottom row), then new keys can be added by using more internal signatures to extend the tree, rather than directly signing external messages.
