Zero knowledge proofs for a Merkle Tree

Say I have a publicly available Merkle tree, and I want to prove the existence of a leaf (containing a number, maybe) in the tree. I could give the path along with the siblings, for a normal Merkle proof, but this reveals the leaf itself.

How can I do this in zero knowledge, i.e., proving that the leaf exists, but not revealing which leaf?

• Is it possible, that you mean proving the leaf exists without revealing the content of the leaf? – AleksanderRas Jan 18 at 10:09
• Yes, maybe I should clarify a bit. A leaf is just a number, so it existing in the tree does not make it special to me, as compared to another number not in the tree. – user2505282 Jan 18 at 10:15
• I don't think the problem is well specified. In ZK proofs you typically have like a public instance of something, and a prover wants to prove something about it. What is the public instance here? Is the tree public? – Daniel Jan 18 at 11:54
• @Daniel, Yes, the tree is public. – user2505282 Jan 18 at 17:46

The "path" is only a witness for your proof; you don't actually want to give the path to the verifier. Turns out that going from a NP-problem with witness to an actual zero-knowledge proof is not that trivial.

What you could do: one of your leaves $$L_1, \dots, L_{n}$$ has the value of your commitment $$x$$. You might write something like

$$\bigvee^{n}_{i=1}\left(L_i=x\right).$$

This is a satisfaction problem, so it's suited to be fed in a bunch of ZK libraries.

Lately, I've been playing with rank-1 constraint systems (r1cs), such as provided by libsnark or in a little time by dalek's bulletproof'' library. These provide non-interactive, fast, compact zero-knowledge proves.

You said your leaves could contain numbers. This translates very nicely in a r1cs system!

$$\prod^n_{i=1}(L_i-x)=0$$

You simply prove that one of the roots of the above polynomial equals zero, which is true when $$x$$ represents a leaf.