merklecpp

A header-only C++ library for creation and manipulation of Merkle trees. It supports the usual operations, like hash insertion, root computation, and path extraction, as well as some more unusual features like flushing, retracting, and tree segment serialisation.

Usage

merklecpp requires C++20.

#include <merklecpp.h>

merkle::Tree::Hash hash("fa8f44eabb728d4020e7f33d1aa973faaef19de6c06679bccdc5100a3c01f54a");

merkle::Tree tree;
tree.insert(hash);
...
auto root = tree.root();
auto path = tree.path(0);
assert(path->verify(root));

Tiled storage (tlog-tiles)

The companion header merklecpp_tiles.h adds optional, header-only support for persisting a tree as tlog-tiles tile files progressively (optionally dropping already-tiled leaves from memory) and for retrieving inclusion and consistency proofs from those tiles, from the in-memory tree, or from a combination of the two. The hashing is unchanged: tiles and tile-derived proofs are templated on the tree's existing hash function, so a tile-derived inclusion proof is byte-identical to one from merkle::Tree::path() and verifies with the same merkle::Path::verify().

#include <merklecpp_tiles.h>

merkle::tiles::TiledTree::Config cfg;
cfg.prefix = "/var/log/mylog";       // tile files live here
cfg.retention_margin = 1024;         // retain at least 1024 tiled leaves too
cfg.compact_on_flush = true;         // opt in to dropping already-tiled leaves

merkle::tiles::TiledTree log(cfg);
for (const auto& leaf_hash : batch)
  log.append(leaf_hash);

// Write newly-complete tiles. With compaction enabled
// this also drops from memory the leaves already covered by a full tile;
// otherwise the tree keeps every leaf and you can call log.compact() later.
// Use flush_up_to(committed_leaf_count) instead to preserve a speculative
// suffix.
log.flush();

// Proofs are served from tiles + the resident tree, even for flushed leaves.
assert(log.size() > 0);
auto inclusion = log.inclusion_proof(/*index=*/0, log.size());
assert(inclusion->verify(log.root()));

if (log.size() > 1)
{
  auto consistency =
    log.consistency_proof(/*m=*/log.size() / 2, /*n=*/log.size());
}

TiledTree constructors create a new tiled tree. The configured prefix may exist, but the default alias requires <prefix>/sha256-256w/tile not to exist, even as an empty directory. Construction atomically claims that tile namespace.

Applications that persist the matching tree state and full-tile boundary can resume an existing namespace directly:

auto log = merkle::tiles::TiledTree::resume(
  cfg,
  "sha256",
  serialised_tree,
  full_tile_boundary);

The boundary must cover a complete, durable tile prefix at every required level and overlap the resident portion of the serialized tree. Recovery reads every required tile, validates each stored roll-up, and compares the prefix root with the serialized frontier. Tile files beyond the boundary are treated as untrusted and replaced when a later flush reaches them. The application remains responsible for establishing namespace ownership.

After an interrupted flush, restore the last successful prefix and the possibly larger rollback seal separately:

auto log = merkle::tiles::TiledTree::resume(
  cfg,
  "sha256",
  serialised_tree,
  flushed_tile_boundary,
  immutable_boundary);

If tiles are not ready yet, restore the logical tree first and populate the namespace independently. This does not claim or inspect the namespace; the caller must establish exclusive ownership:

auto log = merkle::tiles::TiledTree::from_frontier(
  cfg,
  "sha256",
  serialised_tree);

merkle::tiles::TileStore repair_store(cfg.prefix, "sha256");
auto repair = merkle::tiles::TileWriter::repair(
  repair_store,
  trusted_full_tile_boundary);
repair.write_up_to(target_size, leaf_at);

// After the repair writer is quiesced:
log.adopt_tile_prefix(target_full_tile_boundary);

The independent writer can run in the background. The caller must serialize writers for the namespace and quiesce them before adoption. Until the repaired prefix overlaps the resident frontier, root computation and appends remain available but tile-dependent proofs and flushes of non-resident history fail.

See the tiled storage guide for a how-to covering flushing, compaction, rollback, proofs, and the lower-level building blocks, and the illustrated walkthrough for the tile layout and proof algorithms.

Building and testing

Tests are built by default. Configure, build, and run them with:

cmake -S . -B build
cmake --build build
cmake -E chdir build ctest

Some tile coverage is intentionally long-running. LONG_TESTS is off by default for local builds; turn it on when you want the full tile stress suite, including level-2 tile coverage and tile proof timing:

cmake -S . -B build -DLONG_TESTS=ON

CI enables LONG_TESTS in Release configurations so pull requests exercise the full tiled-storage matrix; Debug configurations run the short suite. Every Release job publishes its time_tiles measurements as a table in the GitHub Actions job summary.

CMake option	Default	Purpose
BUILD_TESTING	ON	Build tests; set OFF for a library-only build
LONG_TESTS	OFF	Include level-2 tile and time_tiles coverage
OPENSSL	OFF	Enable OpenSSL hashes, SHA-384/512 tiled aliases, and tests
CLANG_TIDY	OFF	Run clang-tidy while compiling tests
TRACE	OFF	Enable internal Merkle-tree trace output
PROFILE	OFF	Add profiling flags to test targets

Contributing

This project welcomes contributions and suggestions. Most contributions require you to agree to a Contributor License Agreement (CLA) declaring that you have the right to, and actually do, grant us the rights to use your contribution. For details, visit https://cla.opensource.microsoft.com.

When you submit a pull request, a CLA bot will automatically determine whether you need to provide a CLA and decorate the PR appropriately (e.g., status check, comment). Simply follow the instructions provided by the bot. You will only need to do this once across all repos using our CLA.

This project has adopted the Microsoft Open Source Code of Conduct. For more information see the Code of Conduct FAQ or contact opencode@microsoft.com with any additional questions or comments.

Trademarks

This project may contain trademarks or logos for projects, products, or services. Authorized use of Microsoft trademarks or logos is subject to and must follow Microsoft's Trademark & Brand Guidelines. Use of Microsoft trademarks or logos in modified versions of this project must not cause confusion or imply Microsoft sponsorship. Any use of third-party trademarks or logos are subject to those third-party's policies.