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?

  • $\begingroup$ Is it possible, that you mean proving the leaf exists without revealing the content of the leaf? $\endgroup$ Commented Jan 18, 2019 at 10:09
  • $\begingroup$ 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. $\endgroup$ Commented Jan 18, 2019 at 10:15
  • $\begingroup$ 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? $\endgroup$
    – Daniel
    Commented Jan 18, 2019 at 11:54
  • $\begingroup$ @Daniel, Yes, the tree is public. $\endgroup$ Commented Jan 18, 2019 at 17:46

1 Answer 1


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


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!


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

  • $\begingroup$ Thanks. I'll need to read a little more about this, though. $\endgroup$ Commented Jan 19, 2019 at 15:55
  • $\begingroup$ 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! $\endgroup$ Commented Jan 21, 2019 at 7:44
  • $\begingroup$ Interstellar's spacesuit's spec document contains quite some documentation on how they use r1cs; IMO that gives quite some insight. $\endgroup$ Commented Jan 21, 2019 at 7:46
  • $\begingroup$ can this be done without r1cs? $\endgroup$ Commented Jul 15, 2019 at 22:10
  • $\begingroup$ 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. $\endgroup$ Commented Jul 16, 2019 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.