A Gentle Introduction to Zero-Knowledge Proofs
By:doch_doch
After having spent quite some time understanding the use of zero-knowledge proofs in the Zcash protocol, we thought that our insights might be of interest to others, too. In this article we explain the major steps in verifying a shielded transaction in Zcash to anyone familiar with Bitcoin’s basic mechanics. With the help of interactive examples (on our website!), we try to make the reader experiencing what zero-knowledge proofs are.
Why zero-knowledge proofs? Well, that’s probably known by now, but this question serves as a good warm up… Bitcoin transactions are transparent allowing anybody to trace the movement of coins and their trajectories. To introduce anonymity, Zcash’s spend and output descriptions use zero-knowledge (zk) proofs to hide information about the sender, recipients, and transaction amounts. We will shed some light on how you may verify in the current version of Zcash — called Sapling — that a transaction is valid without seeing neither any data about the wallet it originated from nor to whom and how much money was sent.
SNARKs: Zk-SNARKs are special zk proofs (more precisely, arguments, but that’s a technical subtlety). The S of the acronym stands for succinct, i.e. the proofs are small in size, and the runtime for proof generation and verification is short. The N stands for non-interactive which means that in this proof system the prover can convince the verifier to know a secret with just one message. Both properties, S and N, are very useful, particularly for blockchains. J. Groth developed one of the most efficient zk-SNARK proposals to date, and is therefore used in Zcash Sapling transactions.
In the first part of this article — written in a simpler language — we set the focus on only one statement of the Sapling spend description: existence of a note. For this particular spend statement we will exemplarily generate a proof for a secret value of your choice. We then run the verification algorithm with the option to manipulate the input data to showcase that only with valid data the output is “true”.
The second part describes all data of the spend description without elaborate commentary, going quite fast through many difficult cryptographic tools. To provide further readings regarding these processes, we give helpful links to already existing introductions or literature covering these topics in more detail. In the latter section, you are also invited to load the spend description data of a real Sapling transaction and to get an idea of why the verification was indeed successful.
Proving Existence of a Note in Zero-Knowledge
Notes and Note Commitments
For better understanding, we may imagine notes simply as currencies transferred during transactions even though this characterization is inaccurate in some ways. During a transaction, the original note of a sender becomes “invalidated” (by inserting it into the list of spent notes) and transformed into several new notes that are then issued to the encrypted recipients’ addresses. Of course, the value of the newly generated notes may not exceed the value of the spent note (minus the transaction fees charged by the miners).Since Sapling does not make plain notes publicly readable for reasons of anonymity, they are “hidden”. To avoid clandestine manipulations of notes, e.g. increasing the note value to favor the sender, however, the plain notes may not be altered. This is achieved by cryptographic functions, so-called commitments, which can hide the note data and bind the content to the commitment not allowing any alterations afterwards. Although never revealed, the sender must prove knowledge of the plain note data by providing evidence that (s)he has a commitment trapdoor — something like a key to open the commitment.Here comes a slightly incomplete definition of the note data structure (for more details see Zcash Protocol Specification, 3.2): a note n in Sapling consists of
The value v of the note n.
The shielded payment address pk to which the note was generated in a previous output description.
The commitment trapdoor rcm of the note n.
Note Commitment Tree and Valid Merkle Path
As already mentioned, transactions “consume” existing notes and generate new ones. To control this process efficiently, note commitments are organized in Merkle trees. But unlike their use in Bitcoin, Zcash’s Merkle trees are incremental, i.e. of a fixed depth, but which can be incremented horizontally with new notes created in transaction outputs. These trees are called note commitment trees, and their Merkle roots (“anchors”) change whenever new notes are added in the “still-to-be-filled“ leafs.
Note Commitment Tree (inspiring source: Zcash Protocol Spec).
A valid Merkle path in this tree, i.e. a path of hashes from the leaf containing the note commitment you want to spend up to the anchor, proves that this leaf belongs to the tree. It is therefore a note that has previously been added to the commitment tree in an output description, and hence can be spent.
Zero-knowledge Version of a Valid Merkle Path
To prove knowledge of a spendable note in “zero-knowledge” requires to prove knowledge of a note whose commitment is a leaf of a commitment tree without pointing to the specific leaf nor revealing any data of this note. Actually, there are two things to prove: knowing a note commitment and that this note commitment has a valid Merkle path. This is a composable zk proof, i.e. zk proofs with hiding intermediary value. Namely, the proof statement says that the spender knows a note n, a commitment cm, its position pos and path in the commitment tree such that cm=cm(n) and (cm, pos, path) form a valid Merkle path, i.e. roots in rt. Here cm is the note commitment, i.e. the result when applying the commitment function cm() to the note n, which is an intermediary between the note n, and the Merkle path, and is not shown to the public! The spend description only provides the anchor rt of a note commitment tree together with a proof.
To create a note and generate a zero-knowledge proof of its existence jump to their interactive website!
Authors
Hartwig Mayer, Martin Scheerer
Ange Potier (artist)