How Can I Have a 1,000 Private Keys But Just One Public Key? … Well, That’s Merkle Magic

How Can I Have a 1,000 Private Keys But Just One Public Key? … Well, That’s Merkle Magic

It’s strange that once you learn something fundamental, it often sticks. With IPv4 we learn about subnets and IP address classifications, and then we configure our firewall rules to integrate these. And so IPv6 has come along, and we are a bit stuck, as we can fail to scale our existing knowledge and methods into a new area. And the same could be said for our public key methods, and where we create a difficult puzzle to solve, and hope to generate a trap door in the puzzle for those who have a secret.

This leads to a public key and a private key. In most cases we either use RSA or ECC for our public key methods, and where we use our private key to sign a message, and then our public key to prove our identity. But, quantum computers have RSA and ECC in their sights, and we must move away from these, and investigate new methods. One such method is hash-based signing. With this we can have a one time private key, and which is proven by our public key. It is a bit like having a whole lot of cards with random numbers printed on them, and where we reveal each card with our signature on them. No-one can predict which number will appear on the card, as they will always be random.

With a Merkle Trees, we create a tree of hashes and then create a root hash. We start from the bottom of the tree with the original data, and then concatencate two values together, and make a hash of these. We then move up the tree talking two hashes at a time and hashing them together. Now, we can use this method for our public key encryption. For this we can create 1,024 private keys that we will use to sign our messages, and then the root of the Merkle Tree will become our public key. There’s no large number multiplication or ellipic curve point adding, just good old — and fast — hashing. So let’s say we have eight secrets (P1, … P8), and then hash P1 and P2 to give P12, and then hash this with P34 to get P1234, and then hash this with P5678 to get a public key hash value:

In this case I can keep P1, P2 … P8 secret, so that no-one will know these values until I use them. To prove I do know them, I will publish my public key (P12345678), and then will prove that I know P1 by showing the chain that goes from my public key to P1 (P1234, P5678, P12, P34, P1 and P2). I then do not releave any information about P3, P4, … P8, and can use these in future signings. When I run out of secrets, I then just create another public key, and a whole lots of secrets (my private keys).

Merkle Trees

So let’s say we have the names of a few countries: ‘France’, ‘Germany’, ‘Denmark’, ‘Sweden’, ‘UK’, ‘Spain’, and ‘Italy’. We can then hash as [here]:

Input:		 [ 'France', 'Germany', 'Denmark', 'Sweden', 'UK', 'Spain', 'Italy' ]
Root hash:	 65C7C87E2731AE97D0BE89EA3299A544FD28DE6A
Tree depth	 3
Tree levels:	 4
Tree nodes:	 7

Level  0
[ '65C7C87E2731AE97D0BE89EA3299A544FD28DE6A' ]

Level  1
[ '8D832398ACABF7B669C023174169C8876F9764DC',
  '2BBB8E1E1D16671B763D0C026C9A2BA43FD73381' ]

Level  2
[ '0F705D70B6CF6FFE1FE570FC24947767438541FA',
  'A5D0D57347C4BE03B6E91E0176D5E53614AA861E',
  'F8A5C1FC111019BDCD2E6F7877299878F9699640',
  'AD79EF0F076D3A686AB9738925F4DD2C7E69D7D1' ]

Level  3
[ 'E3772AC4B4DB87B4A8DBFA59EF43CD1A8AD29515',
  '17D53E0E6A68ACDF80B78D4F9D868C8736DB2CEC',
  '89DA124E04DFE1AD9946CD37D91A119E1D028898',
  '72DDD2B619AF6D6A73FEBF80F7FCAD22495498CD',
  '7770D04C7BFB791E7C95959F12D6797BEE87A8D8',
  '20A8DF9B760336178FCA425339EC1C7E542A2463',
  'AD79EF0F076D3A686AB9738925F4DD2C7E69D7D1' ]

The root of the tree is then 65C7C87E2731…299A544FD28DE6A, and we have seven nodes and four levels. We can now draw the Merkle Tree:

The SHA-1 hash of ‘France’ is E3772AC4B4D…43CD1A8AD29515. Notice that because we have an odd number of nodes, the hash for ‘Italy’ is used for the next level. If we create with no hashing method, we can clearly see the structure of the true. In this case we use ‘1’,’2',’3',’4' and ‘5’ for our data [here]:

var merkle = require('merkle');
Input: [ ‘1’, ‘2’, ‘3’, ‘4’, ‘5’ ]
Type: none
Root hash: 12345
Tree depth 3
Tree levels: 4
Tree nodes: 6
Level 0[ ‘12345’ ]
Level 1[ ‘1234’, ‘5’ ]
Level 2[ ‘12’, ‘34’, ‘5’ ]
Level 3[ ‘1’, ‘2’, ‘3’, ‘4’, ‘5’ ]

The great advantage of using a Merkle Tree is that we can easily check that a value is included in the root hash. In the diagram below, to test that ‘Germany’ (Node 2) is in the tree, we would need only need Node 1, Node 34 and Node 567 in order to generate the root (Node 1234567):

The reason we only need nodes 1, 34 and 567, is that we can regenerate Node 12 and Node 1234 from these values. Bitcoin, for example, uses this method in order to check the validity of a transaction within the block. We can then add our transactions into a Merkle Tree, and produce a root hash. Within the block we can then add the root hash of the previous block and the root hash of the next block, and thus interlock the blocks into a chain:

Merkle signatures scheme (MSS)

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 presented for W-OTS and Lamport only provide for a one-use — or 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 “2cf24dba5fb0a30e26e83b2ac5b9e29e1 — e73043362938b9824”.

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

Thank you Ralph Merkle!