# 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? Jan 18, 2019 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. Jan 18, 2019 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? Jan 18, 2019 at 11:54
• @Daniel, Yes, the tree is public. Jan 18, 2019 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.

• Thanks. I'll need to read a little more about this, though. Jan 19, 2019 at 15:55
• Sadly, there are not many decent resources on this that I can find, so make sure to ask these kind of questions here on crypto.SE. It's quite a nice question! Jan 21, 2019 at 7:44
• Interstellar's spacesuit's spec document contains quite some documentation on how they use r1cs; IMO that gives quite some insight. Jan 21, 2019 at 7:46
• can this be done without r1cs? Jul 15, 2019 at 22:10
• While the answer is probably "yes", the answer to "how" becomes equally probably a lot more complex. You could have a look at this question, where other users propose several systems that encode pre-image knowledge. Jul 16, 2019 at 7:59