Fact.MerkleMountainRange (Fact v0.3.1)
View SourceA Merkle Mountain Range (MMR) for cryptographic verification of event history integrity.
An MMR is an append-only authenticated data structure that commits to the full sequence of events in a database. Each event becomes a leaf in the tree, and internal nodes are computed by hashing pairs of children. The structure enables:
- Tamper detection — any modification, deletion, reordering, or insertion of events changes the root hash
- Inclusion proofs — compact O(log n) proofs that a specific event is part of the committed history
- External verification — root hashes can be exported and shared with auditors for independent verification
The MMR operates out of the write path by subscribing to event notifications via
PubSub and processing them asynchronously. This adds zero latency to event writes.
Batching is configurable via :batch_size and :flush_interval.
Each leaf commits to the event's content hash, its ledger position, and the previous leaf's hash, forming a hash chain within the MMR that detects reordering and insertion.
The MMR is stored as a flat binary file where node at position i is at byte offset
i * hash_size, enabling O(1) random access for proof generation.
This module requires CAS mode (record_file_name configured with hash@1). The leaf
hash is the record ID, which is already the content hash of the event.
Configuration
The MMR is opt-in, configured via Fact.open/2:
{:ok, db} = Fact.open("data/my_db", merkle: [
batch_size: 10,
flush_interval: 1_000
])See merkle_option/0 for available options.
Summary
Types
A compact proof that an event at a given position is included in the MMR.
MMR configuration options.
Options accepted by start_link/1.
The result of a full MMR verification.
Functions
Returns a specification to start this module under a supervisor.
Creates an inclusion proof for the event at the given ledger position.
Returns the number of leaves (events) committed to the MMR.
Returns the current peak hashes of the MMR.
Starts a Fact.MerkleMountainRange process linked to the calling process.
Verifies the integrity of the MMR against the stored events.
Verifies an inclusion proof independently, without access to the database.
Types
@type inclusion_proof() :: %{ leaf_index: non_neg_integer(), leaf_hash: binary(), sibling_hashes: [binary()], peaks: [binary()] }
A compact proof that an event at a given position is included in the MMR.
:leaf_index- The zero-based leaf index in the MMR.:leaf_hash- The hash of the leaf node.:sibling_hashes- The sibling hashes needed to recompute the path from leaf to peak.:peaks- The current peak hashes of the MMR.
@type merkle_option() :: {:batch_size, pos_integer()} | {:flush_interval, pos_integer()}
MMR configuration options.
:batch_size- Maximum number of events to buffer before flushing to the MMR file. Defaults to1(per-event).:flush_interval- Maximum time in milliseconds before flushing a partial batch. Defaults to1_000(1 second).
@type option() :: {:database_id, Fact.database_id()} | {:name, GenServer.name()} | merkle_option()
Options accepted by start_link/1.
:database_id- (required) The database identifier.:name- (required) The registered process name, typically constructed viaFact.Registry.via/2.:batch_size- Seemerkle_option/0.:flush_interval- Seemerkle_option/0.
@type verification_result() :: :ok | {:error, :tampered, [non_neg_integer()]} | {:error, term()}
The result of a full MMR verification.
:ok- The MMR matches the stored events.{:error, :tampered, positions}- Discrepancies found at the given store positions.{:error, term()}- An error occurred during verification.
Functions
Returns a specification to start this module under a supervisor.
See Supervisor.
@spec create_proof(Fact.database_id(), non_neg_integer()) :: {:ok, inclusion_proof()} | {:error, term()}
Creates an inclusion proof for the event at the given ledger position.
The proof contains the sibling hashes needed to recompute the path from the leaf to its peak. An auditor can verify the proof without access to the full database.
@spec leaf_count(Fact.database_id()) :: {:ok, non_neg_integer()} | {:error, :not_enabled}
Returns the number of leaves (events) committed to the MMR.
@spec peaks(Fact.database_id()) :: {:ok, [binary()]} | {:error, :not_enabled}
Returns the current peak hashes of the MMR.
The peaks represent the roots of the complete binary subtrees that make up the MMR. Together they form the "root hash" — a commitment to the entire event history. An external party can compare peaks against their own computation to verify integrity.
@spec start_link([option()]) :: GenServer.on_start()
Starts a Fact.MerkleMountainRange process linked to the calling process.
Requires :database_id and :name in opts. Additional merkle_option/0 keys are optional.
@spec verify(Fact.database_id()) :: verification_result()
Verifies the integrity of the MMR against the stored events.
Rebuilds the MMR from scratch by reading all events and comparing against the
stored MMR file. Returns :ok if the MMR matches, or {:error, :tampered, positions}
with a list of leaf positions where discrepancies were found.
@spec verify_proof(inclusion_proof(), atom()) :: :ok | {:error, term()}
Verifies an inclusion proof independently, without access to the database.
Given a proof (as returned by create_proof/2) and the hash algorithm used by the database,
recomputes the path from the leaf hash through the sibling hashes and checks that
the result matches one of the peaks in the proof. This allows an external auditor to
confirm that a specific event is part of the committed history.
Returns :ok if the proof is valid, or {:error, reason} if verification fails.
Example
{:ok, proof} = Fact.MerkleMountainRange.create_proof(db, 1)
:ok = Fact.MerkleMountainRange.verify_proof(proof, :sha256)