This is intended to be an introduction to zk-SNARKS that requires no previous knowledge of them. I have tried my best to simplify where I can and make sure that this remains an introduction, not an all-encompassing guide. Despite my best efforts, there is still some challenging math and arduous terms that may be difficult to understand at first. Don’t be discouraged by these obstacles; these are concepts that take time to understand and will become clearer as you study them more. I have also included links to additional resources at the bottom of the article.
A zk-SNARK is a Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. That may seem like a lot to unpack, but all it really means is that a zk-SNARK is a way to prove possession of some asset while not actually revealing what the asset is. Furthermore, this is accomplished without the need to redo the computation to ensure the proof is correct, and without any interaction between a prover (the party who seeks to prove they possess some asset) and a verifier (the party who should verify that this is true). This may sound impossible, but through some tricky math and having the ability to check the resulting proof at any time, it can be done.
zk-SNARKs are an incredibly interesting concept and very useful, particularly in the context of blockchains. In a publicly viewable blockchain where privacy is key, zk-SNARKs bring improved scalability (well over 10x) and privacy. Scalability is improved because, with a zk-SNARK proof, one party can perform the proof off-chain, using their own computing power, and then publish that proof on-chain. This removes the need for the multiple parties to spend resources doing the original proof, and anyone viewing the blockchain can then quickly check the proof. Additionally, privacy is improved because publicly viewable blocks do not reveal the asset or parties involved (unless the implementor wants to allow them to be revealed). Some interesting real-world uses for zk-SNARKs are:
It is worth mentioning here that zk-SNARKs have a “cousin” called zk-STARKs and other alternatives, which I will discuss more at end of this article. There are also other zero knowledge proofs that exist or are in development.
At a high level, zk-SNARKs work by transforming computations into a system of polynomials and then using these polynomials to prove that the computation is correct. Several encryption techniques and a trusted setup phase are used to keep this process tamper-proof. The resulting proof can then be quickly verified inside of a smart contract by anyone at any point later in time.
The goal here is transform a computation into polynomials that the prover can use to develop a proof that the computation was done correctly. If you do not know what a polynomial is, it is simply an equation represented in the form f(x) = cnxn+…+c1x1+c0x0 where all c’s are constants and x is the input. The highest power of x determines the degree of the polynomial. For instance, 2x4-1x3+0x2+0x1+12x0 is a polynomial of degree four, and it can be rewritten as 2x4-x3+12. The reason why polynomials are needed will be explained later - just know that this is an essential step.
In order to make this transformation, the program must be broken down into smaller possible operations consisting of basic arithmetic operations (also called “flattening” the program), and then these operations are transformed into a rank 1 constraint system (R1CS) which contains constraints that, when combined, define the computation that occurred. Then, this set of constraints is turned into polynomials (specifically, a quadratic arithmetic program). In an effort to simplify this, I am skipping over some mathematical steps that are involved in these transformations, such as Lagrange interpolation, but, again, the important thing to note here is that the computation that needs to be proved can be transformed into these polynomials.
A broad summary of this transformation: Computation/Program -> Basic Operations -> R1CS -> Quadratic Arithmetic Program -> Ready For zk-SNARK Algorithm
Up to this point, it probably does not make much sense why the program needs to be transformed into a polynomial. Here is why: polynomials have the important property that 2 different polynomials of degree n can intersect at, at most, n points. To simplify through example, the polynomial f(x) = x3-4x2+2x+1 is of degree three. For any different polynomial of degree greater than or equal to three, any given input x could have the same output as f(x) a maximum of three times since the highest degree is three. Compared to the number of possible points that you could check the two equations on for equality, three is a negligible number.
This is key, as it allows us to check the polynomial representation of a program quickly by picking an arbitrary point and seeing if the prover can indeed evaluate the polynomial correctly at that point. There is no need to check the polynomial at every point in order to ensure equality. Unless the prover knows the point in advance, which we will disallow through trusted setup as discussed later, the prover will not be able to craft fake polynomials that can create undetectably fake proofs.
Any solvable polynomial can also be factored. For instance, our earlier example of x3-4x2+2x+1 has one input x at which the output is 0 (that point is x=1). We will call this a root, and we can then rewrite the equation as (x-1)(x2-3x-1). Here, we only have one solution (x=1), but we can imagine other equations that have up to n solutions where n is the highest degree in the polynomial.
So, if the prover wants to prove that he knows a polynomial of degree three with solution x=1 without actually telling us the polynomial, then he can prove that he knows a polynomial that is a multiplication of (x-1) and something else, which we will refer to as h(x). In the above example, h(x) was x2-3x-1. To reiterate, a polynomial f(x) can be rewritten as t(x)*h(x) where t(x) is the factored out parts (like (x-1)) and h(x) is what we can multiply these factors by (like x2-3x-1) in order to obtain f(x).
This is where things get a little bit tricky to follow, even without mentioning some of the deeper level math, but bear with me.
Let’s call our polynomial for a given program f(x). This is an abstraction; f(x) is actually made up of separate polynomials, which are typically denoted as A(x), B(x), and C(x), and these combine to make up a quadratic arithmetic program where A(x)*B(x) = C(x) over a range of x values. Further, each of these polynomials are made up of a linear combination of a set of polynomials: one for each constraint that we have on our program. I will be simplifying this by referring to these as f(x) where f(x) = A(x)*B(x)-C(x), but the links provided at the end of the article go more in-depth if you want to learn more.
We know that f(x) must have specific constraints on it since we formed it from a R1CS made up of various constraints that defined our program. Namely, f(x) will be 0 for all integer values from x=1 to x=c, where c is our number of constraints. Therefore, f(x) has roots from x=1 to x=c. Just as before, we can write f(x) as t(x)*h(x) where t(x) is our factored-out roots and looks like:
t(x) = (x-1)*(x-2)*…*(x-c)
Dividing f(x) by t(x) should give us our polynomial h(x) with no remainder. If there is a remainder, then f(x) did not really have the roots specified in t(x).
Additionally, the coefficients of our constraint polynomials that make up the quadratic arithmetic program that we briefly mentioned earlier are publicly known (however, the actual execution trace that the prover wishes to prove is not). This is essential, as they represent the computation that we wish to prove. These will be used during verification. t(x) is also publicly known and can be easily calculated once the number of constraints set earlier in the process.
As stated before, f(x) = t(x)*h(x). The prover can now, knowing f(x) and t(x), calculate h(x) by dividing f(x) by t(x). The prover does not actually relay this knowledge of h(x). Instead, the prover evaluates h(x) at a randomly chosen point that I will call “r”. If he can provide an h(r) that is equal to f(r) / t(r), then he has passed the proof and this divisibility can be verified. Other things that are checked here include the coefficients of the constraints provided by the prover (ensuring they are the same) and the validity of commitments for the polynomials that make up f(x) (the quadratic arithmetic program). What do I mean by commitments? Commitments of polynomials like h(r) involve encryption, allowing them to remain secret by hiding them, and will be explained later.
We figured out that the prover must calculate h(r) at a random point r. However, if the prover knows this point, then he can use that knowledge to create fake polynomials that evaluate correctly at that point and thus create fake proofs. This is where the need for something called “trusted setup” comes in.
Trusted setup is a way of creating this point r as well as keys that can be used to create and verify proofs. The actual value of this point r must be destroyed at the end of the trusted setup process so that no one can know the actual value.
Trusted setup is often done through a ceremony utilizing various parties. Each party does a portion of the computation to calculate the secret point, and each must destroy their part of the computation. This is often referred to as “toxic waste”. An interesting aspect of multi-party trusted setup is that there is only the need for one of the parties to be honest and truly discard his toxic waste (though we would obviously prefer every party to do so). Zcash, a cryptocurrency that implements zk-SNARKs, has an interesting video of their trusted setup ceremony that can be found online in which they went through great lengths to ensure the confidentiality of the setup. The r value is kept around for later use by saving it in a very specific way, but that is out of the scope of this article.
Several points made so far, such as the ability to keep point r a secret or the ability to hide f(x), may seem to be standing on shaky ground. However, various encryption schemes are used in zk-SNARKs in order to accomplish these feats, including partially homomorphic encryption (also referred to in zk-SNARKs as polynomial commitments or hidings), bilinear pairings, Fast Fourier transforms, and elliptical curve pairings. These are more advanced concepts that I will not cover here, but I will provide a few important notes about these encryption techniques and other mathematical tricks used:
Up to this point, we have not really discussed what makes these proofs zero-knowledge. I’ll make this brief and broad: the zero-knowledge aspect of zk-SNARKS comes from both homomorphic encryption and from adding some randomness into our polynomials while still maintaining the ability to perform certain operations correctly and check for equality. This way, no one can know exactly what was being proved, even from the small glimpses of data that could be seen in verification.
I plan to write similar articles on zk-STARKS and the Pickles SNARK soon, so keep an eye out for those.
ZK rollups
https://docs.ethhub.io/ethereum-roadmap/layer-2-scaling/zk-rollups/
Pickles zk-SNARK (used in Mina Protocol)
https://medium.com/minaprotocol/meet-pickles-snark-enabling-smart-contract-on-coda-protocol-7ede3b54c250#:~:text=Pickles%20is%20the%20only%20setupless,stands%20up%20against%20other%20systems
Spartan zk-SNARK
https://github.com/microsoft/Spartan
Recommended further reading on zk-SNARKS
http://www.zeroknowledgeblog.com/index.php/zk-snarks
https://vitalik.ca/general/2017/02/01/zk_snarks.html
https://vitalik.ca/general/2021/01/26/snarks.html
libsnark: a C++ library for zk-SNARK proofs
https://github.com/scipr-lab/libsnark