ConvergeLedger.Integrity.MerkleTree (Converge Ledger v0.1.2)

View Source

Merkle tree implementation for cryptographic integrity verification.

A Merkle tree is a binary tree of hashes where:

  • Leaf nodes contain hashes of data items
  • Internal nodes contain hashes of their children
  • The root hash represents the integrity of all data

Use Cases

  • Snapshot verification: Detect corruption before loading
  • Efficient sync: Identify which entries differ between replicas
  • Audit proofs: Prove an entry exists without revealing all entries
  • Tamper detection: Any change to data changes the root hash

Usage

iex> entries = [entry1, entry2, entry3]
iex> hashes = Enum.map(entries, &MerkleTree.hash_entry/1)
iex> root = MerkleTree.compute_root(hashes)
iex> MerkleTree.to_hex(root)
"a1b2c3d4..."

Properties

  • Deterministic: Same inputs → same root hash
  • Collision-resistant: Different inputs → different root hash (with high probability)
  • Single-element trees: Hash is combined with itself (Bitcoin-style)

Summary

Types

hash()
proof()

Functions

combine(left, right)

Combines two hashes into a parent hash (for internal tree nodes).

compute_root(hashes)

Computes the Merkle root from a list of leaf hashes.

compute_root_from_entries(entries)

Computes the Merkle root from a list of entries.

from_hex(hex)

Converts a hexadecimal string to a hash.

generate_proof(hashes, index)

Generates a Merkle proof for a leaf at the given index.

hash(content)

Computes the SHA-256 hash of binary content.

hash_entry(entry)

Computes the hash of an Entry.

to_hex(hash)

Converts a hash to a hexadecimal string.

to_short_hex(hash)

Returns a short form of the hash for display (first 16 hex chars).

verify_entries(entries, expected_root)

Verifies entries against an expected Merkle root.

verify_proof(leaf_hash, proof, expected_root)

Verifies a Merkle proof for a leaf hash.

verify_root(hashes, expected_root)

Verifies that a computed root matches an expected root.

Types

hash()

@type hash() :: binary()

proof()

@type proof() :: [{:left | :right, hash()}]

Functions

combine(left, right)

@spec combine(hash(), hash()) :: hash()

Combines two hashes into a parent hash (for internal tree nodes).

compute_root(hashes)

@spec compute_root([hash()]) :: hash()

Computes the Merkle root from a list of leaf hashes.

Uses standard binary Merkle tree construction:

  • Empty list: returns hash of empty binary
  • Single element: combined with itself (Bitcoin-style)
  • Multiple elements: build tree bottom-up

Examples

iex> MerkleTree.compute_root([])
<<227, 176, 196, ...>>  # hash of ""

iex> h = MerkleTree.hash("data")
iex> MerkleTree.compute_root([h])
MerkleTree.combine(h, h)  # single element duplicated

compute_root_from_entries(entries)

@spec compute_root_from_entries([ConvergeLedger.Entry.t()]) :: hash()

Computes the Merkle root from a list of entries.

Entries are hashed and then combined into a tree.

from_hex(hex)

@spec from_hex(String.t()) :: {:ok, hash()} | {:error, :invalid_hex}

Converts a hexadecimal string to a hash.

generate_proof(hashes, index)

@spec generate_proof([hash()], non_neg_integer()) ::
  {:ok, proof()} | {:error, :invalid_index}

Generates a Merkle proof for a leaf at the given index.

The proof contains the sibling hashes needed to recompute the root. Returns {:ok, proof} or {:error, :invalid_index}.

hash(content)

@spec hash(binary()) :: hash()

Computes the SHA-256 hash of binary content.

hash_entry(entry)

@spec hash_entry(ConvergeLedger.Entry.t()) :: hash()

Computes the hash of an Entry.

Combines context_id, key, payload, sequence, and appended_at_ns into a deterministic hash.

to_hex(hash)

@spec to_hex(hash()) :: String.t()

Converts a hash to a hexadecimal string.

to_short_hex(hash)

@spec to_short_hex(hash()) :: String.t()

Returns a short form of the hash for display (first 16 hex chars).

verify_entries(entries, expected_root)

@spec verify_entries([ConvergeLedger.Entry.t()], hash()) :: boolean()

Verifies entries against an expected Merkle root.

verify_proof(leaf_hash, proof, expected_root)

@spec verify_proof(hash(), proof(), hash()) :: boolean()

Verifies a Merkle proof for a leaf hash.

Given a leaf hash, its proof (sibling hashes), and the expected root, verifies that the leaf is indeed part of the tree.

verify_root(hashes, expected_root)

@spec verify_root([hash()], hash()) :: boolean()

Verifies that a computed root matches an expected root.