Determining Changes in Data Across Machines Efficiently with a Merkle Tree
When you have data distributed on multiple machines, you often want to be able to ensure that the data on one computer is the same as data on another. There are several scenarios where knowing the set of data across machines is in sync. In this article we will build a straight forward implementation of a Merkle tree that can be used to efficiently compute the differences in a set of data between multiple computers.
A What Tree?
A Merkle Tree is a data structure that allows the efficient comparison of a series of elements to find differences. They are used in distributed systems when you need to be able to efficiently find differences between machines without having to transmit the entire data set. They can also be used to efficiently check that a set of files or one very large file has not been modified in transit. For example in a peer to peer scenario, you can query a trusted host to ensure that the data you are receiving from a peer has not been modified.
How Do They Work
Let’s start with a simple example. Suppose you have two computers each running the same program. You want modifications made to the data on one computer to be reflected on the other. You are happily transmitting changes from one machine to the other when one of the machines crashes, or goes offline due to networking issues. When the second machine is reachable again, you want to only transmit the data that is missing or different. A Merkle Tree will help you do just that.
Before we dive into the actual Merkle tree implementation, let’s do the simple naive implementation. You could compute a hash function for every element in the set and transmit those hashes between machines. This will result in transmitting the hash for every element in the set and for a large number of elements we would like to transmit the minimum amount of data.
To do that, we will build a Merkle Tree. A Merkle tree is a special binary tree where only the leaf nodes hold values, the other nodes in the tree are for searching, but we’ll get to that later.
To construct the tree we will start with the root and then build a tree based on the number of leaf nodes we will have. For now, let’s assume that eight leaves are sufficient, then we need a tree of height 3 (remember 2^3 = 8). We construct our balanced binary tree recursively at each level until we reach a leaf nodes. This results in a tree that looks like the one in the diagram below:
For each node in the tree we can compute a hash value for it’s children. Using a hash function (crc if low security, or SHA1 or another cryptographically secure hash when required) we can compute the hash value for each node by recursively computing the hash for the left node and concatenating that hash with the hash of the right node. In the case of a leaf node (no children) then the hash is computed based on the stored value.
Using the example tree in diagram1 we can compute the hash value of the root node according to the following rules.
Let h be the hash function you have decided for your implementation. In our example we will use SHA1. The hash for any node in the tree is h(N) = h(h(N.left) + h(N.right)) where N.left and N.right are left and right sub trees of that node. Therefore the hash for the root h(A) = h(h(B) + h(C))
h(B) = h(h(D) + h(E)) h(C) = h(h(F) + h(G)) h(D) = h(h(1) + h(2)) h(E) = h(h(3) + h(4)) h(F) = h(h(5) + h(6)) h(G) = h(h(7) + h(8))
In our scala implementation the hashes are computed lazily when requested, but they could be computed once and cached, that optimization is left as an exercise for the reader.
With our tree constructed we can determine if two trees are identical by comparing the hash of the root: h(A) If the root matches congratulations your trees are identical. The identical case is not that interesting, what happens if the third and fifth leaf nodes are different. How do you determine that using the Merkle tree.
In that scenario h(A) != h(A’) where A’ is the root of a tree on another machine. We would then look at the hash for the children of A and see that D and D’ matched, but E and E’ did not, we then compare h(3) and h3’) see they do not match but h(4 and h(4’) do. We would use a similar set of comparisons on the sub tree rooted at C to discover that h(5) and h(5’) do not match.
In our implementation we don’t name nodes with letters and numbers, instead we address sub trees based on the range of leaf nodes they encompass. For example the hash for h(A) would represent the entire range one through eight (1,8), while B represents one through four (1,4) and so on down the tree. A leaf node’s range is it’s position from the left so one would be (1,1).
CODE, or it didn’t happen
I have published an implementation an implementation of a sha1 hashing merkle tree in scala on Github. I chose scala for fun to learn the language. The implementation consists of two classes. Node.scala and Tree.scala
The node is not very interesting, it uses the SHA1 message digest algorithm, and recursively determines the hash for any of it’s child nodes. Empty leaf nodes have a hash value equal to empty string, and that value will bubble up the tree if the neighboring children are also empty.
I will call attention to the SHA1 method is, because converting the digest from bytes to a string was somewhat annoying, it’s worth copying it from here should you need to do something similar.
The tree class is where the magic happens :-)
Tree exposes three methods
- insert(value : String) - Insert a String into the tree.
- hash_for_range(search_start : Int, search_end : Int) - Determine the hash for a range of child nodes.
- leaf_node_(number : Int) - Get the actual Node object representing a leaf node.
The tree class does a couple “clever” things. On the first insert it creates a balanced tree based on an initial size. The tree will resize itself like a hash table when it is full and another node is inserted. The resize doubles the size of the tree and copies the leaves from the smaller tree to the larger one. Originally I created a new tree on resize but when refactoring the tree, I know only add one more level of the tree, and move the values from the old leaves to the new ones.
Only leaf nodes hold values. The other nodes contain a hash representing their child nodes. Insert automatically assigns the value to the next available leaf node in the tree.
The hash for range method is interesting you specify a range of leaf nodes you would like the hash for. A tree with 8 elements
would return the hash of the root,
would return the hash for the node left of the root, and
would return just the hash for the 8th leaf node. Hash for range is used to compare the hashes between two trees. This way you can navigate to just the child nodes that are different. Again as we discussed above If the root hash of the two trees is the same, then every node is identical, otherwise you get more and more specific until you find the leaf nodes that are not identical. Finally you use the
method to retrieve the specific node that is different between the two trees.
The other methods are for utility purposes. This code is still very new and not yet ripe. Please don’t use it in a production system. I will include a license file once the code has some tests.
Until next time. Happy Coding!