zk-SNARK Concepts Explained In Different Levels of Complexity

For the last few months I’ve been studying zk-SNARK material and I recall what it felt like to hear many of the terms used by the zk-SNARK researchers before I learned what they meant.

Well, you see, first you need to FRI the PLONK system such that it is an R1CS…

I’ve decided to write an ELI15 for zk-SNARK jargon since I’ve yet to come across something similar during my studies. Note the 1 (ELI15). I’m going to assume some basic understanding of cryptography (hashing, Merkle trees, etc), polynomials, and computer science in my explanations.

This post is written for my own benefit. After all,

If you can’t explain it to a six year old, you don’t understand it yourself. — Albert Einstein

I hope to stake a claim in the ground such that others will correct any misunderstanding that I may have about the subject. However, my hope is that this post is also beneficial to others. For these reasons, the post will be made publicly available.

Note that the intended audience for this post is someone who has no familiarity with zk-SNARKs, so many of the definitions will be mathematically imprecise (see the Finite Field definition below for example).

Interactive Proofs

Interactive proofs are protocols where a prover and verifier communicate with one another such that the prover can prove to the verifier that they performed some computation correctly. These are usually taught as a precursor to SNARKs since the same mental model can be carried over between the two and an interactive proof can be turned into a SNARK using Fiat-Shamir Transformation.

Fiat-Shamir Transformation

So what is Fiat-Shamir transformation?

This is a way to make an interactive proving system non-interactive (the N in SNARK). Dan Boneh offers a good explanation here. In general, you replace the round-trip network calls between prover and verifier with a hash function, which the verifier can check that the prover executed properly to produce its randomness.

Random Oracle Model

This is related to the Fiat-Shamir transformation. When someone talks about the random oracle model, they’re saying “we assume that some idealized random hash function exists”. You could think of the random oracle model as a mental model that was leveraged to develop the Fiat-Shamir transformation technique to remove interactivity from interactive proofs.

Interactive Oracle Proof

Now that we’ve defined most of these terms, defining this one will be easier since we can use those terms in this definition.

An interactive oracle proof (called an IOP) is an interactive proof that uses an oracle to make the proving and verification more efficient.

Schwartz-Zippel Lemma

This observation is literally what makes SNARKs possible. — Dan Boneh

The Schwartz-Zippel lemma states that if you randomly evaluate a non-zero polynomial, the probability that the evaluation equals 0 is at most the degree of the polynomial (call it d) divided by the number of possible inputs to the polynomial (call it p).

This sounds complex, but intuitively it means that the probability that you pick a root of the polynomial (d) out of all of the possible values to pick (p) is d/p.

What is interesting about this lemma is that it also applies to multivariate polynomials.

Sum Check Protocol

This interactive protocol uses the Schwartz-Zippel lemma to probabilistically check whether two polynomials are equal to one another without evaluating both polynomials directly.

David Wong has a video explainer here.

The Boolean Hypercube

Speaking of that video. David mentions the boolean hypercube. What’s that?

You’ll often see this written as {0,1}^n. The mathematical notation kind of gives it away as the set of bit strings of length n. For example: {0,1}² would be {00, 01, 10, 11}.

GKR Protocol

GKR stands for the authors of the protocol: Goldwasser, Kalai, and Rothblum. The GKR protocol was one of the first protocols (published in 2015) to verify the evaluation of a general-purpose arithmetic circuit probabilistically using the Sum Check Protocol.

Arithmetic Circuit

If you’re familiar with traditional circuits, which operate over boolean values and operators, this is the same concept but applied to (you guessed it) arithmetic. One interesting thing to note about the gates of these circuits is that, in the context of zk-SNARKs, at the time of this writing, they only operate over addition and multiplication operators.

R1CS

R1CS stands for “Rank 1 Constraint System”. Rank 1 comes from linear algebra and implies that the constraint system uses matrices. It’s a common intermediate representation for arithmetic circuits along the pipeline from computation to zk-SNARK.

Vitalik has a blog post explaining how to go from computation to zk-SNARK that contains an image that I’ve found useful when thinking of this pipeline.

The post also has a basic step-by-step explanation of how to build a R1CS representation of a circuit that’s been constructed from a very basic computation so it’s easy to follow.

Polynomial Commitment Scheme

A polynomial commitment scheme (you may hear this as PCS from the researchers) is a way for a prover to commit to a given polynomial without revealing the coefficients of the polynomial to the verifier.

Two common polynomial commitment schemes at the time of this writing are KZG and FRI, but there are other versions folks are experimenting with like Dory, Ligero, and Brakedown.

Again, Dan Boneh gives an excellent high-level explanation in .

Polynomial commitment schemes are usually combined with polynomial interactive oracle proofs and Fiat-Shamir transformation to produce SNARKs. Surprised that you understood all of that? 😛

KZG

KZG stands for Kate, Zaverucha, and Goldberg, which are the authors of this polynomial commitment scheme.

It uses “powers of Tau” to generate global parameters that are then used to commit to polynomials. It’s a trusted setup, so it requires that the powers of Tau be deleted after they’re used to generate the global parameters. Since they need to be deleted, you’ll often hear the powers of Tau called “toxic waste”.

You’ll also hear about “KZG ceremonies” which are ways for everyone participating in the ceremony to contribute randomness to the powers of Tau such that only 1 participant in the ceremony needs to delete their contribution to the randomness for the toxic waste to be discarded.

Powers of Tau

So, what are these powers of Tau? Tau is a random field element that’s repeatedly multiplied by itself and your group elements during the KZG polynomial commitment scheme.

Finite Field

Speaking of “field elements”, you may hear “finite field” mentioned often by researchers, what is that?

At the time of this writing, SNARKs cannot operate over all integers, so the finite field is the subset of integers that your SNARK is defined to operate in. The field elements I mentioned in the Powers of Tau definition are elements of this defined finite field.

Finite fields use modular arithmetic to constrain the field to the requisite size.

Fast Reed-Solomon Interactive Oracle Proofs of Proximity (FRI)

FRI is a popular alternative polynomial commitment scheme to KZG that doesn’t involve a trusted setup (called “transparent”, which consequently is the T in STARK). It uses Reed-Solomon encoding and Merkle trees to probabilistically check the validity of a degree D polynomial using less than D queries (hence the “Fast”).

Vitalik has a nice explainer here.

Lagrange Interpolation

Lagrange Interpolation is a way to construct a polynomial that passes through a given set of points. It’s used as a polynomial analog of Reed-Solomon encoding whereby if two polynomials differ by even a small amount their Lagrange interpolation evaluations will differ dramatically.

There is a great explanation on the /r/3Blue1Brown subreddit of how to construct a Lagrange interpolation here. But, the important part in the context of SNARKs is the distance amplification property mentioned above.

Multi-Linear Extensions

Multi-Linear Extensions (often shortened to MLEs) are multilinear polynomials (e.g. x_1*x_2 +4*x_1 +3*x_2) constructed from multivariate polynomials (e.g. 3x² + 2xy + y³ + 5) via Lagrange interpolation. These multilinear polynomials are useful in the zk-SNARK context because they’re usually faster to verify.

Witness

A witness is an input to some computation that is used to prove the correctness of a statement without providing the statement directly.

In the context of arithmetic circuits, a witness is a way for the prover to construct a computational “trace” of its execution of the arithmetic circuit that allows the verifier to probabilistically check the validity of the prover’s execution in sub-linear time without giving away the circuit itself.

Note that a prover’s witness is secret, meaning that it’s not given to the verifier directly, but instead, a succinct proof is given in its place (hence the S in SNARK).

Permutations Over Lagrange-Bases for Oecumenical Noninteractive Arguments of Knowledge (PLONK)

PLONK is a popular type of SNARK that involves proving 4 things about an arithmetic circuit

1. the gates of the circuit are correct
2. the inputs to the circuit are correct
3. the wiring between the gates is correct
4. the output of the circuit is correct

The term “permutation” comes from the way that the wiring is proved since PLONK uses a permutation of the polynomial to prove the wiring's correctness.

If you’re a ZK project looking for an engineer, developer advocate, or security professional DM me on Twitter.

If you’re interested in doing a ZK development or security boot camp join this mailing list.

You can also follow me on Twitter if you’re interested in keeping up to date on smart contract auditing and zero-knowledge cryptography.