Skip to Content
⚠️ This documentation is AI-generated, for personal use only, and is not supported or endorsed by Google.
ReferenceProof SystemMerkle Commitments

Merkle Commitments

The merkle/ module provides Ligero with a compact column commitment scheme: SHA-256-hashed leaves organized in a binary tree, with compressed proofs for multi-index openings. The MerkleCommitment wrapper salts each leaf with a per-leaf nonce, making the commitment zero-knowledge. You will almost certainly not call this module directly, but this is the reference to understand what the root inside a ZkProof actually represents and how to debug opening failures.

When to reach for it

  • You’re debugging a verification failure and want to isolate a Merkle-path check.
  • You’re reading the proof blob format and need to know how MerkleProof deserializes.

Design overview

The module provides two primary classes: MerkleTree on the prover side builds a binary tree by hashing upward from n leaves stored at indices [0, n); MerkleTreeVerifier on the verifier side checks a compressed proof of inclusion for a queried set of positions.

Hashing uses SHA-256 via util/crypto.h. Internal nodes combine their children via Digest::hash2(left, right), which sequentially updates a SHA-256 context with both digests and produces the parent hash.

Compressed multi-opening. When a verifier queries a set of positions that share ancestor nodes in the tree, those ancestors are omitted from the proof blob—they’re recomputable from the queried leaves themselves. For k independent positions in a tree of n leaves, worst case is O(k · log n), but in practice much less when queries cluster (which they do in Ligero, where queried column indices are uniformly random distinct indices drawn via ts.choose()).

Zero-knowledge via leaf salting. MerkleCommitment—the wrapper Ligero uses—sets each leaf to SHA-256(nonce ‖ leaf-data) with a fresh 32-byte nonce per leaf. Nonces are revealed as part of an opening; everything else about the tableau remains hidden, preserving witness privacy.

API surface

Prover side (MerkleTree):

  • MerkleTree(size_t n) — allocate space for n leaves
  • void set_leaf(size_t pos, const Digest& leaf) — store a leaf at position pos in the range [0, n)
  • Digest build_tree() — compute all internal nodes bottom-up and return the root
  • size_t generate_compressed_proof(std::vector<Digest>& proof, const size_t pos[], size_t np) — generate a compressed inclusion proof for np leaf positions

Verifier side (MerkleTreeVerifier):

  • MerkleTreeVerifier(size_t n, const Digest& root) — initialize with tree size and the commitment root
  • bool verify_compressed_proof(const Digest* proof, size_t proof_len, const Digest leaves[], const size_t pos[], size_t np) const — check the compressed proof against the provided leaf values and their positions

Commitment wrapper (MerkleCommitment):

  • MerkleCommitment(size_t n) — allocate for n leaves with nonce vectors
  • Digest commit(const std::function<void(size_t, SHA256 &)> &updhash, RandomEngine &rng) — generate fresh nonces, combine each with leaf data via the provided updhash callback, set leaves, and return the root
  • void open(MerkleProof &proof, const size_t pos[], size_t np) — generate an opening containing the nonces and compressed path for the queried positions

Example

MerkleTree mt(4);
Digest leaves[4] = {Digest{100}, Digest{101}, Digest{102}, Digest{103}};
for (size_t i = 0; i < 4; i++) {
  mt.set_leaf(i, leaves[i]);
}
Digest root = mt.build_tree();
 
size_t pos[2] = {1, 3};
std::vector<Digest> proof;
mt.generate_compressed_proof(proof, pos, 2);
 
MerkleTreeVerifier v(4, root);
Digest open_leaves[2] = {leaves[1], leaves[3]};
bool ok = v.verify_compressed_proof(proof.data(), proof.size(),
                                    open_leaves, pos, 2);

See it used

Last updated on
LigeroTranscript & Randomness