2018-07-16

Creating fake zkSNARK proofs

As you may know, zkSNARKs are a way to create Zero-Knowledge Proofs. Specifically, succinct and non-interactive ones.

Explaining what they are exactly is a bit too much for this post, so I refer you to the following:

  1. How zkSNARKs are constructed in — by the Zcash team.
  2. Trustless Computing on Private Data — blog post by QED‐it’s lead cryptographer Daniel Benarroch and Prof. Aviv Zohar.
  3. Prove-it, Blockchain-it: ZKP in Action — a video of a meetup explaining ZKPs and how to create one for Sudoku.
  4. The Incredible Machine — blog post by QED‐it’s Chief Scientist Prof. Aviv Zohar, explaining trusted setup.
  5. The Hunting of the SNARK — a series of riddles to experiment with ZKPs.

In QED-it we use zkSNARKs, among other tools, to create Zero-Knowledge Blockchains for the enterprise.

The production deployment of zkSNARKs that is most known is probably Zcash — a cryptocurrency with unlinkable transactions and hidden amounts. Zcash, and some others utilizing zkSNARKs, are based on a construction called Pinnochio although more specifically BCTV14a.

This is a marvelous technology, and as you might suspect, nothing is for free! There’s a notable downside to this construction — the “trusted setup”.

Trusted Setup

The setup is a process where the CRS (Common Reference String) is generated, or more publicly known as the pair of proving and verification keys. These “keys” are used by the prover and verifer to generate and verify proofs for a specific problem (or constraint system), respectively.

In this process, there are random elements which are sampled and must be kept secret — if the prover knows them, they will be able to create proofs which are verified successfully, without using an actual solution to the problem during the proving process. In other words, to forge proofs and break soundness. This randomness is also known as “toxic waste”.

There are ways to avoid this worry and not put trust in a single entity. For public circuits, these usually involve a Multi-Party Computation — a process in which multiple players donate their own randomness, which they destroy afterwards. The interesting fact is that it’s enough that one player is honest and destroys their randomness for the whole process to be secure.

Some notable examples of using MPCs to do trusted setup are again, by Zcash:

  1. “The Ceremony” podcast
  2. Powers of Tau