Tiled storage and proofs — a guide to `merklecpp_tiles.h`#

merklecpp_tiles.h is an optional, header-only companion to merklecpp.h. It lets you persist a Merkle tree as a set of immutable tile files on disk and serve inclusion and consistency proofs from those tiles, from the in-memory tree, or from a combination of the two — so proofs stay available even after old entries are dropped from memory.

It builds on the tlog-tiles file/directory layout but is not trying to be wire-compatible with external tlog-tiles clients. merklecpp adds an algorithm-qualified directory above the standard tile/ layout so different hash functions can safely share one configured prefix. This page is a practical how-to; see the illustrated walkthrough for a visual model of the tile layout and proof algorithms.

Requirements and a note on hashing #

C++20. Both headers use std::format; tile storage additionally uses <filesystem> and small platform-specific file-sync calls.
Include the companion header; it pulls in merklecpp.h for you:
```
#include <merklecpp_tiles.h>
```
Everything lives in namespace merkle::tiles and is templated on the same <HASH_SIZE, HASH_FUNCTION> as your tree. The default aliases (merkle::tiles::TiledTree, TileStore, TileWriter, ProofEngine, …) use the same SHA-256 as merkle::Tree, so a tile-derived inclusion proof is byte-identical to one from merkle::Tree::path() and verifies with the usual merkle::Path::verify().
With OPENSSL=ON, corresponding TiledTree384/TiledTree512, TileStore384/TileStore512, writer, source, proof-engine, and entry-bundle aliases use the OpenSSL-backed SHA-384 and SHA-512 functions.
A custom hash function must use the constructor overload that supplies a lowercase storage name, for example MyTiledTree(cfg, "custom-sha256"). Otherwise construction throws because merklecpp cannot infer the namespace. Names may contain lowercase letters, digits, and internal hyphens. The reserved sha256, sha384, and sha512 names must match the configured hash size.
You insert leaf hashes, not raw entries — exactly like merkle::Tree. Deriving a leaf hash from an entry (e.g. leaf = H(entry)) is your application’s job. The tile hash values are whatever your HASH_FUNCTION produces; they are not RFC 6962 unless you instantiate your tree with an RFC 6962 hash function (not required, and not the goal here).

Thread safety #

The tiled-storage API provides no internal synchronization. Treat each TileStore, TileWriter, TileHashSource, ProofEngine, TiledTree, and EntryBundleWriter instance as single-threaded.

Serialize access to any one object, including methods declared const: tile-backed proof generation updates the TileHashSource LRU cache. Writers sharing a prefix must also be serialized. Independent TileStore objects may read that prefix concurrently with the single serialized writer because tiles are published atomically and only appear at their final path when complete.

Quick start: `TiledTree`#

TiledTree is the high-level wrapper: append leaf hashes, flush them to disk (which writes tiles), and ask for proofs. This example is included directly from the tiles_docs test so the documented code is compiled and run.

TiledTree::Config cfg;
cfg.prefix = storage_directory;

TiledTree log(cfg);
for (const Hash& leaf : batch)
{
  log.append(leaf);
}

// Persist newly-complete tiles to disk.
log.flush();

const auto n = log.size();
if (n == 0)
{
  throw std::runtime_error("expected at least one leaf");
}
const Hash root = log.root();

// Inclusion proof for leaf 0 in the tree of n leaves.
const auto inclusion = log.inclusion_proof(0, n);
if (!inclusion->verify(root))
{
  throw std::runtime_error("inclusion proof did not verify");
}

This example assumes batch is non-empty. root() throws on an empty tree; size(), flush(), flush_up_to(), and compact() are safe at size 0.

TiledTree can be move-constructed, but it cannot be copied or assigned. Move construction keeps its writer bound to the destination tree’s tile store.

Config::prefix is resolved to an absolute path when the store is constructed. A relative prefix therefore binds to the working directory at that moment; later working-directory changes do not move the tile store.

TiledTree constructors always create a new tiled tree. The configured prefix may already exist, but the algorithm-qualified tile namespace must not: the default alias atomically creates <prefix>/sha256-256w/tile and rejects it whenever it already exists, even if it is empty.

Resuming an externally checkpointed tree #

Tile files do not identify the tree that produced them or contain enough state to restore its size and root. An application that separately persists the tree state and boundaries can reopen an existing namespace with resume():

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

serialised_tree is the existing merkle::Tree serialization. full_tile_boundary is a leaf count, must be a multiple of TILE_WIDTH, and must identify a complete, durable tile prefix at every required level. The factory deserializes the tree, rejects trailing bytes, and requires its resident range to satisfy Config::retention_margin. It reads every required tile, checks every stored higher-level entry against the roll-up of its child tile, and compares the resulting prefix root with the past root derived from the serialized frontier. Missing, malformed, divergent, or incorrectly rolled-up tiles reject recovery before the tree is exposed. This verification is linear in the stored prefix and may perform substantial I/O for a large tree.

The application remains responsible for establishing namespace ownership. The boundary cannot be inferred from the tree’s min_index() or from the files on disk. Existing files beyond it are excluded from proof reads and replaced from the restored tree when a later flush() reaches them.

An interrupted flush may publish files and advance immutable_size() without advancing flushed_size(). Persist both values with the serialized frontier and restore them with the five-argument overload:

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

The complete prefix through flushed_tile_boundary is verified and available to proofs. immutable_boundary separately restores the rollback seal. Tiles between the two boundaries remain untrusted and are replaced from the resident frontier when flush() is retried. Both boundaries are tile-aligned, flushed_tile_boundary <= immutable_boundary, and neither may exceed the serialized tree’s last complete tile boundary. When they are equal, the four-argument overload above is equivalent.

An ordinary lower-level TileWriter intentionally resumes existing full tiles and trusts the caller to supply the same tree and hash function. A fresh writer scans the requested range in order, stopping at the first missing or malformed file, so an interior hole is rewritten rather than hidden by later files.

Restoring while tiles are populated or repaired #

An application need not block logical tree recovery on tile reconstruction. from_frontier() restores only the serialized tree and binds the configured namespace without inspecting, creating, or trusting it:

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

root(), size(), and append() are immediately available. flushed_size() and immutable_size() start at zero. If the serialized tree has already discarded old leaves, proofs requiring that history and flush() fail clearly until a complete tile prefix overlaps the resident frontier. The application must establish exclusive ownership of the namespace; unlike fresh construction, this factory does not claim it.

Populate or repair the namespace with an independent store and a repair writer:

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,
  [&](uint64_t i) -> const merkle::Hash& { return authoritative_leaf(i); });

The trusted boundary must be tile-aligned. Tiles below it are preserved; every tile at or beyond it is replaced from the supplied authoritative leaves as the writer reaches that tile. This makes the same API suitable for an absent namespace, a stale suffix, or a namespace whose untrusted portion needs repair. The application remains responsible for validating the trusted prefix.

The independent writer may run on a background thread because it owns a separate TileStore and does not access the TiledTree. Do not run it concurrently with log.flush() or another writer for the namespace. Quiesce the repair writer before making its output visible to the tree:

log.adopt_tile_prefix(target_full_tile_boundary);

Adoption is monotonic. It performs the same exhaustive tile, roll-up, and prefix root verification as resume(), then updates both the flushed and immutable boundaries and resets the live writer at that prefix. Files beyond it remain untrusted and are replaced by later live flushes. Adoption does not compact; call compact() separately when desired.

Persist the serialized frontier, flushed boundary, and immutable boundary atomically as one application checkpoint. On restart, pass them to resume(); during a rebuild, pass the frontier alone to from_frontier() and adopt only after repair completes.

flush() is incremental: each call writes only the full tiles that became complete since the previous call. Tiles in the trusted prefix are immutable. Files in an untrusted repair suffix may be replaced before that suffix is adopted. The remaining frontier stays in memory until it crosses the next full-tile boundary.

For a tree that contains a speculative or otherwise rollbackable suffix, flush only a committed prefix:

log.flush_up_to(committed_leaf_count);

The argument is a leaf count, not the index of the final leaf. Only complete tiles wholly contained in that prefix are written and sealed; later leaves stay resident and rollbackable. flush() is equivalent to flush_up_to(log.size()). A count beyond size() throws, while a count whose full-tile boundary precedes flushed_size() is a monotonic no-op. With compact_on_flush, compaction is likewise limited to the resulting flushed boundary.

Tile files are written through unique temporary files, synced, then published with an atomic replace. On POSIX, file contents are synced, each newly created directory is made durable by syncing its parent, and the destination directory is synced after the rename. Before reusing a visible file, a writer also re-confirms its directory chain and destination directory. On Windows, file contents are flushed and the rename is write-through, but directory syncs are no-ops and directory-entry durability is left to the filesystem. A wrong-size file at a tile path is treated as unpublished and is rewritten when the source leaves are still resident.

Flushing and compaction #

By default flush() only writes tiles; it keeps every leaf resident in memory. Dropping already-tiled leaves from memory (“compaction”) is opt-in, because once you drop them you can only prove them from the tiles.

merkle::tiles::TiledTree::Config cfg;
cfg.prefix           = "/var/log/mylog";
cfg.compact_on_flush = true;   // drop tiled leaves after each flush
cfg.retention_margin = 4096;   // keep at least 4096 tiled leaves resident too

merkle::tiles::TiledTree log(cfg);

compact_on_flush (default false): when set, flush() calls compact() for you.
compact() can also be called explicitly at any time. It drops from memory only leaves already covered by a successfully published full tile. retention_margin is counted back from flushed_size(), then rounded down to a tile boundary; the un-tiled frontier is always resident in addition to the margin, and alignment may retain up to TILE_WIDTH - 1 extra tiled leaves. The final tiled leaf is also retained so rollback to exactly immutable_size() remains representable. Treat the margin as a minimum, not an exact resident count. compact() returns the new minimum (smallest still-resident) leaf index.
Proofs for dropped leaves are still produced — they are served from the tiles and transparently combined with the resident frontier.

flushed_size() is the boundary completed successfully at every required tile level, and it is the only boundary used for proof reads and compaction. immutable_size() is the rollback boundary. A flush seals that boundary before it starts writing, because an error can occur after a full tile becomes visible. If a flush throws, immutable_size() may advance while flushed_size() does not. Keep the same tree contents, correct the I/O failure, and retry flush(); finalized tiles are reused rather than rewritten.

Protect compacted tile files from external deletion or truncation. Once a tile’s leaves are no longer resident, flush() cannot regenerate a missing or malformed copy and throws an error naming the first non-resident leaf. Restore the tile from backup; retrying alone cannot recover it.

log.compact();                      // free memory now
auto resident_from = log.tree_ref().min_index();

Rollback #

Tiles are immutable, so you may only roll back entries beyond the boundary returned by immutable_size(). retract_to enforces this:

log.retract_to(index);   // keep leaves [0, index], drop the rest

Allowed when the resulting size is >= immutable_size().
Throws otherwise, because a flush may already have published an immutable full tile for that range.
The exact immutable_size() boundary remains available after compaction; compaction retains the final tiled leaf needed by the in-memory tree.
After a successful flush, immutable_size() == flushed_size(). After an interrupted flush, immutable_size() may be larger until the same tree state is flushed successfully.
retract_to mirrors merkle::Tree::retract_to: index is the new last leaf, so the resulting size is index + 1.
An index at or beyond the current last leaf is a no-op.

Warning

Treat tree_ref() as an inspection escape hatch unless you also maintain every tiled-tree invariant yourself. Direct retraction bypasses the guard, can make flushed_size() and immutable_size() exceed size(), and can make flushed_size() regress. Use TiledTree::retract_to instead.

store_ref() is similarly unsafe for direct Merkle-tile mutation. A later flush trusts any correctly sized tile written through it without checking that the hashes match the in-memory tree. A mismatched tile can silently invalidate proofs after compaction. Constructing an EntryBundleWriter over store_ref() is safe because entry bundles are separate application data and are never used to resolve Merkle proofs.

Proofs #

Both proof types come from TiledTree (or, at a lower level, from ProofEngine). They are produced with your tree’s hash function, so they match what merkle::Tree would produce. Requests outside the current tree (e.g. a size greater than size(), or an out-of-range index) throw std::runtime_error rather than returning an incorrect proof.

Inclusion proofs #

// Prove leaf `index` in a tree of `size` leaves.
std::shared_ptr<merkle::Path> p = log.inclusion_proof(index, size);
bool ok = p->verify(root_at_size);

size is the tree size you are proving against:

size == log.size() ⇒ equivalent to merkle::Tree::path(index); verify against log.root().
a past size ⇒ equivalent to merkle::Tree::past_path(index, size - 1); verify against the root at that size (e.g. a past root you are auditing).

size may even exceed flushed_size(): the recent, not-yet-tiled frontier is taken from the resident tree while the older part comes from tiles.

Consistency proofs #

std::vector<merkle::Hash> proof = log.consistency_proof(m, n);   // m <= n
bool ok = merkle::tiles::ProofEngine::verify_consistency(
  m, n, old_root /* root at size m */, new_root /* root at size n */, proof);

verify_consistency is a static helper, so you can verify on a client that only has the two roots and the proof.

The arguments are tree sizes (leaf counts). If you have leaf indices instead, use the variant that maps index i to the tree of size i + 1 (the “last leaf” convention, matching past_path/retract_to):

// Equivalent to consistency_proof(i + 1, j + 1).
auto proof = log.consistency_proof_from_indices(i, j);   // i <= j

Both TiledTree and the lower-level ProofEngine provide consistency_proof_from_indices.

Lower-level building blocks #

If you manage your own tree/storage you can use the pieces directly instead of TiledTree.

Index types and object lifetimes #

TiledTree mirrors merkle::Tree and uses size_t for indices and counts. The lower storage and proof layer (TileStore, TileWriter, hash sources, ProofEngine, and EntryBundleWriter) uses uint64_t, matching tlog-tiles; that is why leaf and entry callbacks below take uint64_t. Conversions back to the in-memory tree’s index type are range-checked rather than truncated.

Low-level objects own none of the objects passed to them. A store must outlive its writers and tile sources; a tree must outlive its memory source; sources must outlive a CombinedHashSource and ProofEngine. Returned proofs hold hash copies and may safely outlive the engine that produced them.

Writing tiles from your own tree #

merkle::Tree tree;
for (auto& leaf : batch) tree.insert(leaf);

merkle::tiles::TileStore  store("/var/log/mylog");
merkle::tiles::TileWriter writer(store);

// Write all newly-complete full tiles; keep the remaining frontier in memory.
auto stats = writer.write_up_to(
  tree.num_leaves(),
  [&](uint64_t i) -> const merkle::Hash& { return tree.leaf(i); });
// stats.full_written

TileWriter keeps an in-memory next-file cursor. A new writer reconstructs it by checking the contiguous prefix only up to the number of full files relevant to the requested tree size. Existing files are re-confirmed as durably published before reuse; malformed files and holes are rewritten.

Reading tiles and computing proofs #

A HashSource resolves the root of a complete subtree; pick where it reads from:

TileHashSource(store, available_size) — from full tile files; resolves the full-tile-covered prefix only (the frontier needs a memory source).
MemoryHashSource(tree) — from a resident merkle::Tree.
CombinedHashSource(primary, secondary) — try primary first, then secondary (e.g. memory then tiles).

const uint64_t available = tree.num_leaves();
const uint64_t tiled =
  available - (available % merkle::tiles::TILE_WIDTH);

merkle::tiles::TileHashSource src(store, available);
merkle::tiles::ProofEngine    engine(src);

if (tiled > 0)
{
  merkle::Hash root = engine.root(tiled);
  auto inclusion    = engine.inclusion_proof(/*index=*/0, tiled);
}

if (tiled > 1)
{
  auto consistency = engine.consistency_proof(/*m=*/tiled / 2, tiled);
}

A tile-only source can resolve proofs whose subtrees all lie within the full-tile-covered prefix (available_size is rounded down to a whole number of tiles); requests beyond tiled throw. For the live frontier, combine it with a MemoryHashSource — which is exactly what TiledTree does for you.

TiledTree simply wires a CombinedHashSource(MemoryHashSource, TileHashSource) into a ProofEngine for you. It creates these sources for each proof call, so its tile cache is per-call and repeated tile-served proofs may re-read the same files. A long-lived lower-level TileHashSource retains its 64-tile LRU cache across calls; reuse it with a ProofEngine when that matters, and serialize access.

Entry bundles (optional)#

If you also want to store the raw log entries (tlog-tiles “entry bundles”), use EntryBundleWriter. Bundles are level-0 only and application-owned — merklecpp stores leaf hashes; you supply the raw bytes and decide how an entry maps to its leaf hash. Only full bundles (256 entries) are written; the incomplete tail stays with your application until it completes a bundle.

merkle::tiles::EntryBundleWriter bundles(store);
bundles.write_up_to(num_entries,
  [&](uint64_t i) -> std::vector<uint8_t> { return raw_entry_bytes(i); });

// Read a full bundle back (256 entries).
std::vector<std::vector<uint8_t>> e = store.read_entry_bundle(/*index=*/0);

Entries are encoded as big-endian uint16 length-prefixed byte strings. Each entry is therefore limited to 65,535 bytes; a larger entry throws. Bundles live in the same algorithm-qualified store at tile/entries/<index>, although their bytes are application-owned rather than hash-dependent. Missing or malformed bundles break the contiguous prefix and are rewritten by a new writer when it resumes.

With TiledTree, construct the writer from the exposed store:

merkle::tiles::EntryBundleWriter bundles(log.store_ref());

On-disk layout #

Under the configured prefix, merklecpp adds an algorithm-qualified format directory above the standard tlog-tiles layout:

<prefix>/
  sha256-256w/                # algorithm-qualified format directory
    tile/0/000, tile/0/001 … # level-0 tiles (leaf hashes), 256 hashes each
    tile/1/…                 # higher levels (roll-ups of full tiles below)
    tile/entries/…           # optional raw entry bundles

Tile indices use the tlog-tiles path encoding: zero-padded 3-digit groups with all but the last prefixed by x (e.g. index 1234067 -> x001/x234/067). Every tile is full (256-wide), final, and immutable. Entries beyond the last full-tile boundary remain in memory. The built-in SHA-384 and SHA-512 aliases use sha384-256w and sha512-256w; a custom hash uses the explicit algorithm name passed to its constructor. TileStore::root() returns this format directory, not the configured prefix. Levels range from 0 through 63; every successful flush writes all full roll-ups required by the current tree size. See the tlog-tiles specification for the standard geometry and the illustrated walkthrough for how merklecpp stores and resolves those tiles.

Tiled storage and proofs — a guide to merklecpp_tiles.h#

Tiled storage and proofs — a guide to `merklecpp_tiles.h`#