3
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ Thanks. I'll need to read a little more about this, though. $\endgroup$ – user2505282 Jan 19 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$ – Ruben De Smet Jan 21 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$ – Ruben De Smet Jan 21 at 7:46
  • $\begingroup$ can this be done without r1cs? $\endgroup$ – WeCanBeFriends Jul 15 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$ – Ruben De Smet Jul 16 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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