The Merkle Tree Library is a C library implementing a binary [Merkle (hash) tree] (https://en.wikipedia.org/wiki/Merkle_tree). The library was initially developed for use with the [Secure Block Device] (http://www.iaik.tugraz.at/content/research/opensource/secure_block_device/). As such it has the following properties:
- Binary hash tree using SHA-256 as hash algorithm
- Supports variable size data stores
- max number of elements and max hash tree levels are compile-time parameters
- hash tree grows automatically when new integrity tags (mt_add() function) are appended
- hash tree shrinks, when number of integrity tags is truncated (mt_truncate() function)
The library build system is based on make. We currently do not support a configure script, if you want to adapt the library to your needs, adapt the 'src/mt_config.h' header file by yourself.
CppUnit - We provide a small set of unit test cases using CppUnit. For building and running the tests CppUnit is a dependency.
Valgrind - By default the test suite is run with Valgrind's memcheck tool to help detect memory leaks. Unless use of Valgrind is deactivated, it needs to be installed.
Doxygen - The library is (sparsely) documented. Doxygen is required to create the documentation.
Untar the source, change into the library's root directory, and 'make' it. Supported targets are:
- debug - build with debug information enabled
- coverage - build with debugging and coverage support
- release - build optimzed (-O3, no debug) release version
- doc - build the documentation (as it is) using Doxygen
- test - run the CppUnit based test suite. Call with 'make VGRUN= test' to deactivate Valgrind.
- clean - clean up build artifacts
All successful builds create a static library 'libMerkleTree.a' in the 'src' directory, for linking to other applications.
This library has so far been tested on ARM (32-bit) and AMD64.
The library's user interface is specified in 'src/merkletree.h'. The 'tests/MerkleTreeTest.cpp' outlines how to use the library. Also the Secure Block Device uses this library to ensure overall data integrity. Typically, a new Merkle Tree instance is created by calling mt_create(). The instance has to be destroyed by a subsequent call to mt_delete(). In between new integrity tags can be appended to the tree as leafs by using mt_add(). An existing leaf can be updated using the mt_update() function. Each addition or update of a leaf will update the root hash of the hash tree, which can be obtained by calling the mg_get_root() function. Finally, to reduce the size of the hash tree, the mt_truncate() function can be used to specify a new last leaf in the tree. All leaves with a higher index will be invalidated and the memory used to store them freed. This is useful for example to support a data store that can shrink and grow in size.
For details on the licensing see LICENSE. The Merkle Tree Library uses the 'sha.h' and 'sha224-256.c' files from RFC4634 as implementation of the SHA-256 hash.