From One Seed to a Thousand Leaves - Merkle’s Authentication Tree

The Great Seal of Realm - the sign of a royal approval. For centuries, Kings and Queens, Emperors and Empresses, Ladies and Lords used seals to leave their family names on the important documents. But what was left for us, ordinary commoners? Simple autographs were our low budget seals. Their uniqueness comes from a combination of pen pressure, speed and rhythm, letter slant, and spacing. But the world is evolving. We can hardly imagine navigating modern life without computer, mobile phone, or internet. And the problem with ordinary autographs in this setting is that they can be easily copy-pasted from one document to another just like a fancy sticker. It is very helpful when you don’t want to print the document, only to sign it and then scan it again, since we all know the struggle of drawing with a touchpad or a computer mouse (at least I always get some weird doodles instead of a signature). But unfortunately, if you can copy-paste it, then anyone else can do the same. And I bet it won’t feel very nice if one morning you wake up and all your stocks and investments are gone because someone forged your autograph on a gift deed, will it? But no worries. Already in 1979 Ralph Charles Merkle came up with an idea of a digital signature, which he described in his PhD thesis “Secrecy, Authentication, and Public Key Systems”. Though to be accurate, the idea of a digital signature was not his. He improved an already existing Lamport-Diffie one-time signature, which, in turn, was an improved version of Rabin’s signature, as Leslie Lamport mentions himself in the description to his report paper on the Microsoft research forum. So what is that Lamport-Diffie one-time signature? Merkle explains it with a very nice and clear example. Imagine two people: Alice, who has a stock, and Bob - a broker. Alice wants to sell her stock, but Bob can accept neither a phone call nor a message as a confirmation (since it’s so easy to deepfake someone’s voice nowadays). So they remember that when Alice bought this stock she computed $F(x)=y$ using a one-way function (some examples of such functions can be found in the previous post) and sent it to Bob. They even signed a contract that contained $F$ and $y$, but not $x$, and agreed that if Alice wants to sell her share, she’ll reveal her $x$ to Bob. Note that $F$ is a one-way function, therefore irreversible, which means there is no other way for Bob to get $x$ unless Alice reveals it to him. This is why we can claim that the 1-bit message that Alice sends is authenticated. And what if Alice wants to send a longer message? Rarely does someone want to sell the entire stock at once. Much more often, people sell a certain number of shares. For example, Alice wants to sell 11 shares. For her to do that, the buying contract has to look a bit different. Alice would have had to choose $j$ private keys $x$: \[\begin{matrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_j \end{matrix}\] and compute $y_j = F(x_j)$ for each $j$. These $j$ public key values she then shares with Bob as a public key vector $Y_i$. The value $j$ is a fixed number representing the bit length of the message that Alice can sign. For our example, we will use $j=100$. So some time later, Alice wants to send a message $m$: “Sell 11 shares”. First, she needs a binary representation of her message: 01010011 01100101 01101100 01101100 00100000 00110001 00110001 00100000 01110011 01101000 01100001 01110010 01100101 01110011 The length of this message is 112 bits, but since $j=100$, she has only 100 precomputed keys and therefore can sign only 100 bits. Does it mean she has to make her message shorter? Of course not. Instead we just use another one-way function to map all 112 bits to 100 bits. And if the message was too short, we would extend it with zeroes until it had exactly 100 bits. So for each bit out of 100, she has a private key $x_j$ and a public key $y_j$. To sign her message $m$, she sends Bob all the $x_j$ for all the bits that equal 1 in her message. So in our example for the letter s she sends: \[\begin{array}{l} \texttt{01010011} \\[1ex] x_2 \\ x_4 \\ x_7 \\ x_8 \end{array}\] For the next letter e, she reveals: \[\begin{array}{l} \texttt{01100101} \\[1ex] x_2 \\ x_3 \\ x_6 \\ x_8 \end{array}\] …and so on. This way, Alice signs every bit of her message. So the message is secured? Actually, not completely. There is a way for Bob to alter the message. He can just pretend he never got one of the private keys $x_j$ from Alice, therefore changing 1 in the message to 0. This way he can say that instead of 11 shares: 00110001 00110001 Alice asked him to sell only 10 shares: 00110001 00110000 To avoid this, Lamport and Diffie suggest appending $m’$ - a complement of $m$ - to the end of the message. This way, if Bob wants to change 11 shares to 10 shares, he would have to reveal $x_j$ that corresponds to 1 in the complement $m’$ (the very last bit of the forged message in the following example), which he can’t do as Alice never sent him that private key. Example: Original mm' = 00110001 00110001 11001110 11001110 Forged mm' = 00110001 00110000 11001110 11001111 Everything seems to be working well now. But the problem is, such one-time signature requires too much storage space. So Ralph Merkle decided to improve the algorithm and suggested another way to sign messages. How does Merkle improve the Lamport-Diffie one-time signature? Merkle’s first solution was to reduce the actual length of the protected message. So Lamport suggested using the complement $m’$ of $m$ to protect Bob from altering the signature, right? That was a good idea, but it also made the message twice as long as it was. To save some storage space, Merkle adds the count of 0s to the end of the message $m$. For that he would need only $\lceil \log_2 j \rceil$ (or in our example $\lceil \log_2 100 \rceil = 7$) additional bits, which is significantly less than in Lamport’s idea. Why $\log_2$? The count of zeroes is stored as a binary number. For a 100-bit message, the count can be at most 100, and 100 sits between $2^6=64$ and $2^7=128$, so we need 7 bits to store it. Can we store the number of 1s instead of 0s? No, since that won’t protect the signature from being altered. You see, Bob can only change 1s to 0s, not the other way around. For changing 0 to 1, he would need a private key that he never got. Let’s look at an example. We will have an 8-bit instead of a 100-bit message with five 0s: 10001100 101 ^ ^ m count of 0s Now Bob wants to forge the message by changing one bit from 1 to 0. The message now has six 0s: 10001000 110 ^ ^ m count of 0s As you can see, changing 1 to 0 in one part means also changing 0 to 1 in the count field, which Bob can’t do. Now if instead of 0s, we were appending the number of 1s: 10001100 11 ^ ^ m count of 1s Bob would be able to forge it without any problem by just changing 1s to 0s in both parts: 10001000 10 But do we have to store all those public keys that take up so much space? Of course (if we use the Lamport-Diffie one-time signature). Otherwise, how would Bob know it’s Alice who is sending him the keys? What if it was an enemy of Alice, Eva, who created all the public and private keys right before signing her evil message “Gift all my stocks to Eva. Alice” and sending it to Bob? It can only be fixed with some sort of prior arrangement. But as we can imagine, storing all those public keys takes a lot of Bob’s storage. So Merkle came up with another solution called “tree authentication”. How does tree authentication work? The whole construction looks like a binary tree. The leaves are the $Y_i$ values (the public keys calculated using the Lamport-Diffie method). The inner nodes and the root are computed inductively using another one-way function $H$. We start from the leaves with: \[H(i, i, Y) = F(Y_i)\] and go up to the root using: \[H(i, j, Y) = F\!\left( H\!\left(i,\, \frac{i+j}{2},\, Y\right),\; H\!\left(\frac{i+j}{2} + 1,\, j,\, Y\right) \right)\] This might seem complicated at first, but let’s look at an example and try to understand how exactly the signing process works. Example: Let’s assume Alice wants to be able to send eight signed messages to Bob. First she computes 8 vectors $Y_1, Y_2, \ldots, Y_8$ using Lamport-Diffie signature. Then Alice calculates the leaf nodes: \[\begin{aligned} H(1, 1, Y_1) &= F(Y_1) \\ H(2, 2, Y_2) &= F(Y_2) \\ &\;\;\vdots \\ H(8, 8, Y_8) &= F(Y_8) \end{aligned}\] Then she takes pairs of leaf nodes and creates inner nodes: \[\begin{aligned} H(1, 2, Y_{1,2}) &= F\!\big( H(1, 1, Y_1),\; H(2, 2, Y_2) \big) \\ H(3, 4, Y_{3,4}) &= F\!\big( H(3, 3, Y_3),\; H(4, 4, Y_4) \big) \\ H(5, 6, Y_{5,6}) &= F\!\big( H(5, 5, Y_5),\; H(6, 6, Y_6) \big) \\ H(7, 8, Y_{7,8}) &= F\!\big( H(7, 7, Y_7),\; H(8, 8, Y_8) \big) \end{aligned}\] Then pairs the new nodes again: \[\begin{aligned} H(1, 4, Y_{1,4}) &= F\!\big( H(1, 2, Y_{1,2}),\; H(3, 4, Y_{3,4}) \big) \\ H(5, 8, Y_{5,8}) &= F\!\big( H(5, 6, Y_{5,6}),\; H(7, 8, Y_{7,8}) \big) \end{aligned}\] And one more time: \[H(1, 8, Y_{1,8}) = F\!\big( H(1, 4, Y_{1,4}),\; H(5, 8, Y_{5,8}) \big)\] The value $H(1, 8, Y_{1,8})$ that Alice gets is a root value $R$. This is the only value that Bob and Alice have to agree upon before signing any messages and therefore the only public key that Bob needs to store. Here is what the resulting tree looks like: graph TD R["H(1,8) = Root R"] --> H14["H(1,4)"] R --> H58["H(5,8)"] H14 --> H12["H(1,2)"] H14 --> H34["H(3,4)"] H58 --> H56["H(5,6)"] H58 --> H78["H(7,8)"] H12 --> H11["H(1,1) = F(Y₁)"] H12 --> H22["H(2,2) = F(Y₂)"] H34 --> H33["H(3,3) = F(Y₃)"] H34 --> H44["H(4,4) = F(Y₄)"] H56 --> H55["H(5,5) = F(Y₅)"] H56 --> H66["H(6,6) = F(Y₆)"] H78 --> H77["H(7,7) = F(Y₇)"] H78 --> H88["H(8,8) = F(Y₈)"] How does Alice actually sign the message? Let’s imagine in the form of a dialogue between Alice and Bob how exactly the first message $m_1$ out of eight available messages is signed. Alice: