Merkle Tree Primer
A Merkle tree is a binary hash tree that lets you commit to a large dataset with a single root hash, then prove that any individual item belongs to that set with a logarithmic proof. Meridian uses Merkle trees to anchor recipe attestations on-chain without uploading every recipe.
1. Hashing the leaves
Each recipe in the batch is serialized canonically and hashed with SHA-256. The output is a fixed 32-byte digest. Identical inputs always yield identical digests, and any single-bit change cascades through the entire output.
leaf_0 = sha256(canon(recipe_0)) leaf_1 = sha256(canon(recipe_1)) leaf_2 = sha256(canon(recipe_2)) leaf_3 = sha256(canon(recipe_3))
2. Building the tree
Pair adjacent leaves and hash each pair to produce the next layer. Repeat until only one hash remains — that is the root. If the layer has an odd count, duplicate the last node. For a batch of N recipes, the tree has ceil(log2(N)) layers and exactly one root.
3. Proving inclusion
A proof of inclusion for recipe i is the list of sibling hashes along the path from leaf_i to the root. The verifier rehashes upward and compares to the published root. Proof size is logarithmic in N, so a batch of one million recipes needs only twenty hashes to prove membership.