Discussion on zk-SNARKs

1

This is based on February’s IFT ZK Call. Visit the IFT ZK Meeting Notes for additional resources, and the video of this meeting (pending).

For the last several years, zero-knowledge has been a popular term in Web3 for a variety of reasons. This can be attributed to three reasons:

  1. Extensive research that has produced several zero-knowledge arguments in a short time. A Cambrian Explosion of zero-knowledge arguments occurred during the mid 2010s to now giving us Pinocchio, Groth16, Bulletproofs, Sonic, Plonk, Aurora, Halo2, Plonky2, and so many more. Development has been fueled by practical design interests into web3.
  2. Privacy conscious applications that require secure and efficient arguments: privacy coins (zcash, Monero), zkVMs (RISC0, Nexus), privacy voting (zkVote, zkVoting).
  3. Marketing hype. There are some projects that advertise themselves to have zk, but they do not possess any privacy protection. Instead, the term ‘zk’ is used as a buzzword to refer to succinct. This is a common issue that on at least two occasions has been discussed in the zkpodcast telegram.

So, what is a zk-SNARK? The term zk-SNARK is self-descriptive for the kind of arguments that it refers to. Specifically, zk-SNARK is short for a Zero-Knowledge, Succinct, Non-interactive ARgument of Knowledge. More precisely,

  • Zero-knowledge. No private information is leaked.
  • Succinct. Short proof size and fast verification
  • Non-interactive. No communication is required during proof generation and verification.
  • Argument of knowledge. special kind of proof that the Prover possesses claimed knowledge.

A zk-SNARK can be used to prove that a (public) statement and (private) witness satisfies an arithmetic circuit. The arithmetic circuit is determined by the specific application.
A zk-SNARK guarantees:

  • An honest Prover’s claim will always be accepted.
  • A malicious Prover cannot produce a valid proof.
  • A Prover that can construct a valid proof must possess a valid witness for the statement.
  • No information concerning the witness should be leaked.

For a keen reader that is interested in zero-knowledge arguments in general, these guarantees are actually probabilistic. For example, “a malicious Prover can only produce a valid proof with negligible probability.”

Where can zk-SNARKs be found?

  1. zkVMs. Generates proofs of execution.
    • RISC0: STARK and Groth16.
    • Nexus: Nova, Halo2(KZG), and Groth16
  2. Privacy currencies.
    • zCash: originally used an optimized version of Pinocchio, Groth16 in sapling, and Halo2 in orchard.
    • Monero: uses Bulletproofs+
  3. Gaming. Generate proof of player’s activity in a multiplayer game to enforce honest activity amongst players.
    • DarkForest: uses Groth16

There are additional properties that we may wish for a zk-SNARK to possess:

  • Universal. The same public parameters can be used for many different circuits.
  • Transparent. No trusted ceremony to construct public parameters.
  • Updatable. The public parameters can be updated.
  • Scalable. Proof generation occurs in quasilinear time.

We note that there is a closely related class of arguments called zk-STARKs; in STARK, the s stands for scalable and t stands for transparent. The majority of zk-STARKs are zk-SNARKs, and many newer zk-SNARKs are zk-STARKs. However, for the most part, zk-STARK is not commonly used to refer to transparent zk-SNARKs.

A transparent zk-SNARK is desirable as this means that no trapdoors exist in the generation of the public parameters. If these values are leaked, then proofs can be forged. An updatable zk-SNARK can remedy the lack of a transparent setup by allowing parties to provide their randomness in the creation/update of a set of public parameters. A single honest user in such a ceremony ensures the setup maintains the claimed integrity.

Universal setups offer added flexibility by providing us with a single set of parameters that can be used for a multitude of circuits. But is there a time in which we might be content with a zk-SNARK that is not universal?

  • In applications that have circuits that are used repeatedly.
  • A compression layer to compress a large proof produced by a universal zk-SNARK to a shorter proof of a non-universal zk-SNARK.

Groth16 is a popular zk-SNARK due to its short proof size. Groth16 emits a proof consisting of 3 group elements. Recent proof systems such as Polymath and Pari has worked to ‘refine’ Groth16 to bring the concrete proof size down.
Concretely, for the elliptic curve BLS12-381, a Groth16 proof uses1536 bits, a Polymath proof uses 1408 bits, and a Pari proof uses 1280 bits. However, from a theoretical standpoint, Groth16 is still the ‘limit’ for proofs with only group elements for a pairing base zk-SNARK; that such a proof must have at least two group elements.

Other properties of Groth16:

  • Requires a per circuit trusted setup.
  • Groth16 proof size consists of 3 group elements.
  • Groth16 is not transparent, not universal, not updatable.

In the talk, we dived into some of the math behind Groth16. However, for brevity and clarity. I will omit this for now, but we can expand upon this in the comments if requested. :slight_smile:

1 Like