So How Do Two Banks Check Their Transfers Without An Auditor? Ask Ralph!

So How Do Two Banks Check Their Transfers Without An Auditor? Ask Ralph!

I want to present the usage of Merkle trees in the creation of a quantum computing robust cryptography method, so I’m going to provide some of the basics of their usage.

Bob The Bank

Let’s say we have two banks who do billions of transactions every day, and they want to check that all the transactions, or a batch of transactions, have been received correctly? One way is to use a Merkle tree (or a hash tree), and which is a method that was patented by Ralph Merkle [here] in 1979, where each non-leaf node is the hash of its children. Then, to check all the transactions, we would compute the hashes and calculate a root hash, and exchange that.

So let’s say we have Bob The Bank, and Alice Online, and they exchange transactions. If they want to check their transactions at the end of the day, they can each compute the hash tree, by hashing non-leaf nodes with the hash of the children:

Bob The Bank will then send the root hash to Alice Online, and she can then check that she computes the same value. If they agree, they have the same set of transactions. But let’s say that Alice Online just wants to search for one of the branches of the tree. We can do this in Merkle trees by only increasing computing power by log(N) — where N is the number of nodes in the tree (where a hash list would vary with the number of nodes). In this way we could check to see if transactions 3 and 4 are in the tree.

Here is a simple demo of the Merkle tree method:

So what?

Merkle trees are used in so many applications, including with P2P networks, but also with Bitcoin transactions, Git distributions, and in the BitTorrent protocol. You will also find it in NoSQL systems including with Apache Cassandra. And you’ll also find it as a quantum robust hashing method [here].