I read the zcash paper recently. But I have been puzzled by a question. How did the authors prove that the coin commitment appears as a leaf of a Merkle tree with root rt? Apparently, the authors provided authentication paths for a commitment. But how to provide them in a private way?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Unfortunately, an in depth answer for me would be too long and is actually the scope of the Zerocash paper itself, which I recommend you re-read thoroughly.
A high-level answer: Instead of providing the authentication path, which would leak the position of the coin commitment in the tree and break anonymity, Zerocash gives a zero-knowledge proof of knowledge (ZKPoK) of such a valid authentication path. (In fact, the ZKPoK argues much more than just the validity of the path.)
The ZKPoK is instantiated so that it is succinct and efficient-to-verify via the techniques and implementation of [BCTV13], which is in turn based on the Pinocchio zk-SNARK from [PGHR13e].
References
[BCTV13] Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture; by Eli Ben-Sasson and Alessandro Chiesa and Eran Tromer and Madars Virza; in Cryptology ePrint Archive, Report 2013/879; 2013; https://eprint.iacr.org/2013/879
[PGHR13e] Pinocchio: Nearly Practical Verifiable Computation; by Bryan Parno and Craig Gentry and Jon Howell and Mariana Raykova; in Cryptology ePrint Archive, Paper 2013/279; 2013; https://eprint.iacr.org/2013/279
