A Gentle Introduction to Zero-Knowledge Proofs with Hands-On Examples

Exploring Zcash Sapling Transactions

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. On this website we illustratively 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, we let the reader experience 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.

This article is divided into two parts. In the first part -- 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.

Part 1

What are notes and note commitment trees? How does a zk proof statement look like?

Practical example: Create a note and generate a zk proof for its existence.

Part 2

What are SNARKs? What are spend descriptions and how they are verified?

Practical example: Choose a Sapling tx ID and get a glimpse of what happens behind the scene.

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 $\mathrm{v}$ of the note $n$ .
The shielded payment address $\mathrm{pk}$ to which the note was generated in a previous output description.
The commitment trapdoor $\mathrm{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 $\mathrm{cm}$ , its position $\mathrm{pos}$ and path $\mathrm{path}$ in the commitment tree such that $\mathrm{cm} = \mathrm{cm}$ $(n)$ and $\mathrm{(cm}$ , $\mathrm{pos}$ , $\mathrm{path)}$ form a valid Merkle path, i.e. roots in $\mathrm{rt}$ . Here $\mathrm{cm}$ is the note commitment, i.e. the result when applying the commitment function $\mathrm{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 $\mathrm{rt}$ of a note commitment tree together with a proof.

Before we dig deeper into this matter in the second part of this article, let us create a note and calculate the anchor of the commitment tree containing its note commitment. For this we have set up an empty test commitment tree using the code from the librustzcash library:


      // create note & commitment using given value
      let note = to
          .create_note(value, Fs::random(&mut rng), &JUBJUB)
          .unwrap();
      
      let cm = Node::new(note.cm(&JUBJUB).into_repr());

      // create empty commitment tree and add commitment
      let mut tree = CommitmentTree::new();
      tree.append(cm).unwrap();
      
      let witness = IncrementalWitness::from_tree(&tree);
      let merkle_path = witness.path().unwrap();

      let anchor = Fr::from(witness.root());

      // ... proof generation skipped here

We use a payment address to to which the new note belongs. Fs is the scalar field of the JUBJUB curve and Fr the field of the arithmetic circuit engine. JUBJUB contains pre-computed parameters for the Jubjub curve. You find links to the repositories at the bottom of this page and some math background is explained in part two.

Choose the note value, and let's execute this code. Enjoy this moment, you are printing money ;-)