Zero-knowledge Merkle Membership Proofs

Say we want to prove that a particular value exists as a leaf in a Merkle tree, without revealing which value we’re talking about.

This is a common ingredient in zero-knowledge blockchain applications (‘zApps’), where we want to refer to private states; without revealing the value or storage location of such states.

Here’s a pretty GIF to illustrate:

Notes

• The values 0…30 in the tree are node indices, not node values. The actual values at each node are not shown, because they’d just be random-looking hashes which would make the illustration cluttered and confusing.
• A leaf’s path comprises its parent nodes up the tree.
• A leaf’s sibling path comprises the siblings of its path (where ‘siblings’ are two nodes which share a parent node).
• The binary decomposition of a leaf’s index (indexed from 0) gives us the “leftness” or “rightness” of its sibling path (relative to its path) up the tree.

Example

Say, for example, we want to prove that we know the value at node index 19 (equiv. leaf index 4), without revealing the value nor its location.

• Get the membership witness for the leaf: i.e. the value itself; its leaf index; and its sibling path.
• Re-calculate the root of the Merkle tree (from the membership witness), as part of a zk-SNARK proof generation process.
• Submit the zk-SNARK’s proof and public input (the root), to the verifier (smart contract).

The verifier will:

• verify the zk-SNARK,
• check that the submitted root equals the stored root.

If both checks pass, the verifier will be convinced that we’ve correctly referred to a private state. Crucially, notice that we’ve not revealed to the verifier which state we were referring to, as the only intelligible information we submitted was the root.

That’s it for this article. Enjoy watching my GIF.

:)