GoKawiilAn 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.
... continue reading