From One Seed to a Thousand Leaves - Merkle’s Authentication Tree | Math behind Security

An implementation of a small Merkle Tree can be found in my GitHub Repository.

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}<br>x_1 \\<br>x_2 \\<br>x_3 \\<br>\vdots \\<br>x_j<br>\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}<br>\texttt{01010011} \\[1ex]<br>x_2 \\<br>x_4 \\<br>x_7 \\<br>x_8<br>\end{array}\]

For the next letter e, she reveals:

\[\begin{array}{l}<br>\texttt{01100101} \\[1ex]<br>x_2 \\<br>x_3 \\<br>x_6 \\<br>x_8<br>\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...