Merkle Helps Rebuild Our World of Trust — Again!

Merkle Helps Rebuild Our World of Trust — Again!

You can call it what you want … blockchain or DLT … I only see the Merkle Tree and public key signing. But we now face a major problem in that the methods which are used to sign for transactions on the blockchain are at risk from the rise of quantum computers. We thus need signing methods which will not be cracked in a post-quantum computing world. And, so, again, we turn to the genius of Ralph Merkle, and his Merkle Tree.

Merkle signatures

The roots of hash-based methods is Merkle trees, and which are a way of hashing used in many applications, including with Bitcoin, Ethereum, Git distribution systems, No SQL, and P2P file transfer. With a Merkle tree we take our data elements, and then hash them, and take pairs of these hashes to create a new hash, and so we build a hierarchical tree. At the top of the tree is the root element (in this case Hash1234):

In this way, we can use the tree to see if we have matching data on systems. On a P2P network, we can transfer a file by splitting it into data segments and then distributing these segments across the network. A trusted source will have the complete Merkle tree for rebuilding the file, and a client can thus rebuild from the Merkle tree and determine the parts of the file which are still missing (or are in error). Once transferred, the root hash (and all the other hashes) will then match. In its core method, the Merkle Signature Scheme (MSS) has serious performance and memory issues, but enhanced methods such as XMSS create the hash table with much less of a performance hit.

The methods present for W-OTS and Lamport only provide for a one-time signature. In order to sign many messages, we can use the Merkel signature scheme (MSS). With we take a hash of the keys and build these as the leaves of the tree. The root of the tree is then the public key — the verification key. We then just use the private key of the OTS method to create the signature. The sender also sends the authentication path, which is the neighbouring nodes within the path which leads to the root of the tree. At the receiver end, they can then rebuild the tree using the verification key (which can be received a digital certificate) and the authentication path. For we move onto another key pair and where the index of the key part is revealed.

In the following example we have our root as the public key, and then want to sign with Key3. We then show the authentication path which takes us to the root (as defined in the bold arrows):

In the following we have a message of “hello” and which has a SHA-256 hash of “2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824”.

We first produce four sets of key pairs (and which can only be used once each). For each set of key-pairs we have 32 256-bit random numbers, and the public key is 32 256-bit versions of the private key, and that have been hashed 256 times.

We then take the message and hash it with SHA-256. Next we take each 8-bit value in the hash (N), and then hash 256-N times using SHA-256. These values become the signature.

To verify the receiver takes the hash of the message, and takes the SHA-256 hash. Next they will take each 8-bit value of the received signature, and then hash it by the value of the byte in the hash of the message. The results should be the corresponding value in the public key.

The Merkle root defines the top level hash, and where the authentication of the hash for the corresponding key pair is also given.

Message:		hello
Hash(message):		2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

=== Calculate four signatures with 32 key pairs each ===
Private key [0][0]:	4db81f526b64d69b58a6a1cf9578dc9e04eac297414e9fe63a85df2ccef11a6a
Private key [0][1]:	673d627b7badf7461257d3e65bd557bda0da24e6485d97e86cf92d784bbbcdc6
....
Private key [0][31]:	5d4b71021c9d90ec95822037004d994e15bee4587fc08cf33d1877cc8c5fe153
....
Public key [0][0]:	336196ed0c22d4cff3218c9000e24c70a0bfec5e0ca318afe4899a16ccc755c6
Public key [0][1]:	fa0a9ce753520bb142dc97c10fc313e09b6f5f83639d9bfb2beabd78785276e0
....
Public key [0][31]:	a5912d99be04e9af0fdc6e2b2903788d7023c6ddae69a7b409e07e57465e246b

=== Determine Merkle Root ====
Merkle root:		3fa78ced3b5dc205b3dbfc29a89a2352d11f16c2a751c15666f25e73c6a54fbf

=== Create signature ====
Signature [0]:		9e82faf05429db2854001abf42ea38eec1cd6cbf1b76292cc1bc8ef82ca61216
....
Signature [31]:		aaaf98ff8576a19ac758b765a5eb75d42286bf548188e5778a294f09f78aa42a

=== Verify signature ====
Verified MSS:		True
Merkle path:	[('161b01f3c986543bda6a9a49bde5820f7ba5324cdfd5ea4535d897fed750309c', '47dfb8b70b1a7e8227dca2b226410d818104f4af45352f5334f4230436903c4c'), ('b344637c77e539df5d5396b354bbc2c3d202d6b2fd4ce8175338ae42035ec1a6', '61eddc1359167727065c94a0427b8d18811a791fae7db2b5103dc3b20b1a3cf5'), ['3fa78ced3b5dc205b3dbfc29a89a2352d11f16c2a751c15666f25e73c6a54fbf']]
Verify root		True

A demonstration of this method is given here.

Conclusions

Our current digital work is almost full trustless. We must move increasing into a world where we sign every transaction. But there are risks, and the major risks is that the existing public key methods used for signing can be broken by quantum computers. We must thus plan to deprecate these methods — soon — and move towards more robust ways — and Merkle signatures are a good way forward, especially when integrated with other OTS methods.