Build with MerkleForge.
MerkleForge separates generic contracts, hash implementations, and tree variants into focused crates. The design lets applications choose only the layers they need while keeping tree behavior generic over cryptographic algorithms.
Installation
Add the complete binary-tree stack to your application:
[dependencies]
merkle-core = "0.2.1"
merkleforge-hash = "0.2.1"
merkle-variants = "0.2.1"Applications implementing their own HashFunction can omit merkleforge-hash.
Architecture
| Crate | Responsibility | Main API |
|---|---|---|
merkle-core | Contracts and shared types | HashFunction, MerkleTree, MerkleProof |
merkleforge-hash | Cryptographic adapters | Sha256, Keccak256, Blake3 |
merkle-variants | Concrete tree implementations | BinaryMerkleTree<H> |
Core traits
HashFunction defines leaf hashing, internal-node hashing, the empty digest, and algorithm metadata. MerkleTree<H> defines mutation, root access, proof generation, and tree metadata. ProofVerifier<H> supports verification without retaining tree state.
Hash functions
| Adapter | Algorithm | Typical use |
|---|---|---|
Sha256 | SHA-256 | Widely interoperable authenticated data |
Keccak256 | Keccak-256 | Ethereum-compatible hashing |
Blake3 | BLAKE3 | High-throughput software hashing |
Domain separation
Leaf and internal-node inputs are hashed in separate domains. SHA-256 and Keccak-256 use distinct prefix bytes; BLAKE3 uses separate derive-key contexts. This prevents an encoded internal node from being interpreted as a leaf pre-image.
BinaryMerkleTree
The binary implementation stores leaves and internal nodes in a contiguous vector. The leaf layer is padded to a power of two with the selected hash adapter's empty digest.
- Insertion returns a stable
LeafIndex. - Interior removal replaces the leaf with the empty digest.
- Trailing removals can shrink the padded tree.
- Proof depth is logarithmic in padded leaf capacity.
- The root is recomputed only along the changed path after insertion.
Proof generation and verification
A MerkleProof<D> records the leaf index, logical leaf count, and one sibling digest per non-leaf level. Each proof node also records whether its sibling belongs on the left or right.
Verification starts by hashing the raw leaf data, folds the sibling path toward the root, validates path structure, and compares the reconstructed digest with the trusted root.
construction: O(n)
single insertion: O(log n)
proof generation: O(log n)
proof verification: O(log n)
proof size: O(log n)Tree metadata
metadata() returns a diagnostic snapshot containing logical leaf count, tree height, allocated node count, hash algorithm name, and variant name. This is useful for logging, benchmark labeling, and generic tooling.
Safety and project status
The workspace forbids unsafe Rust and includes unit, integration, property-based, documentation, and benchmark coverage. MerkleForge remains research software and has not received an independent cryptographic audit. Do not treat the current release as audited production infrastructure.