Modern C++: Implementing a Merkle Tree

Merkle Trees store a hash of the sub-tree in each of the Nodes, so that the whole tree’s contents can be validated against tampering.
They are used, for example, in Bitcoin’s blockchain, and in Cassandra to validate replicas.
In this article, we will show how to implement a generic Merkle Tree using features of Modern C++.

Previous implementation

A few years ago, we had shown a simplified implementation of Merkle Trees: that one worked, but had a few shortcomings; most notably, using “raw” const char* pointers, it shifted a lot of burden on the client code to keep track of where the data was, when and how to allocate it and, most importantly, how to deallocate it once done.

It also restricted the user’s options in defining a hashing function (by requiring it to return a const char *) and specifying the length of the hash result at compile time:

template <typename T, char* (hash_func)(const T&), 
    size_t hash_len> 
class MerkleNode;

This code has now been completely revised and updated to take full advantage of C++11’s smart pointers, and making the hashing function fully customizable by the user: the code is available as part of my “Distributed System Library”.

Author’s Note: Medium editor is particularly sucky, and even more so when…