Speedrun to Groth16 Zero Knowledge Proofs

Introduction

Zero knowledge proofs are perhaps the one of the most noble cryptographic inventions made and popularized with the introduction of blockchains. It also is known for its notoriously complex mathematics behind it.

This article intends to cover the mathematical machinery behind it in as concisely as possible without losing the context. All the arithmetic operations in this article is implicitly assumed to be done inside a finite field with some chosen prime number, .

Note:This is not a from scratch explanation of why zero-knowledge proofs work. I assume the reader knows about finite fields, set theory, group theory and basic properties of elliptic curves.

Arithmetic Circuits

An arithmetic circuit is simply a system of equations. Needless to say, system of equations with mathematical operations like addition and multiplication.

An example of arithmetic circuit would be:

In arithmetic circuit the equality (symbol ) should be read as assertion rather than assignment. We say an arithmetic circuit to be satisfied when we have valid values for the input variables - , and in this case.

A valid assignment in our example would be: , and .

R1CS (Rank-1 Constraint System)

A rank-1 constraint system or r1cs is also a system of equations. But the difference is that each equation in the system can only have one multiplication. Although any number of additions are allowed.

Taking up from previous example, the equation remains same since it only has additions(and multiplication by constants). But we have to break the second equation since it has more than one multiplication. A valid r1cs would be:

We simply broke to introduce another variable so as to comply with r1cs.

We call witness a vector that has values that satisfies our r1cs. Lets define our witness as:

In r1cs, we generally re-arrange the variables to create it in this form:

So to take an example equation:

²

We break this into:

Our witness looks like:

Notice that instead of one simple equation of form we have multiple. All of these can be folded into matrices- , and .

Let's work out the equations in to get the matrices , and .

Equation 1

As obvious in this case we have , and .

To satisfy we have:

It satisfies:

Working out will yield the same as .

Equation 2

The equation 2 is:

If worked out in similar way as first equation we will get:

The same can be verified.

Equation 3

This is a bit different:

We can rewrite it as:

So now, is , is and is 1.

Now following the same rules considering our witness vector () we get:

This can also be verified by matrix multiplication.

Final R1CS

Now if we combine all of the representations i.e. combine , and as rows of , and similarly for and , we get:

These matrices along with the chosen witness in satisfy the equation:

where represents Hadamard product.

Bare Proof

Circuit Constraints

R1CS matrices , and .

Proof

Witness vector .

Verification

Check if holds.

But this is far from being zero knowledge proof. Because the proof is witness itself and it is revealed to verifier. Also, it is not succinct because the proof grows as the witness vector grows.

Pairings

Let us assume that , and be the generator elements of the groups , and respectively, such that pairing elements from and gives us an element in . That is:

We will use operator to represent the pairing operation. For example:

where , and . The prover is going to use property of pairing to improve the our proof.

Get into more details about pairings here.

Encrypted Witness Proof

This time the prover encrypts the witness vector to hide it. Consider the equation , we want to hide our witness . Here's how we approach it. We do an element-wise multiplication of our witness vector with both and :

Now instead of plain witness vector , prover sends and vectors as proof. The verifier cannot extract any witness value from these due to discrete logarithm problem.

Circuit Constraints

R1CS matrices , and .

Proof

Encrypted witness vectors and .

Verification

Check if equation holds:

The proof is now zero knowledge since the witness is encrypted - nobody apart from prover sees it. But the proof is still not succinct since the proof grows as the witness vector grows.

QAP (Quadratic Arithmetic Program)

QAPs are also arithmetic circuits but instead of matrices as we did before, we represent the constraints as a set of polynomials.

As we saw before, to verify we check if the following assertion must hold. But this takes time and is expensive, we want to verify it in constant time. To achieve this, we convert the matrices into polynomials and apply some useful theorems.

Lagrange Interpolation

The lagrange interpolation is the theorem that given points - there exists a unique polynomial of degree that passes through all of them. Read more here.

Lagrange interpolation is the key to make proof succinct by converting the matrices , and into polynomials. Let's take the matrix for example. The product gives us a vector of elements. The function can convert this vector into a polynomial . Same goes for and :

Interpolation is a linear operation, so it is homomorphic. That is, for any two vectors and , . If we take each column of as vector and convert these into polynomials , using and then weigh them with the witness vector items , we get the same polynomial as in . Similar argument goes for and .

Given this we can now write:

Now we have successfully converted the original r1cs at into polynomials. But we cannot just apply the same equality check to polynomials. That is,

will not hold, since degrees of the polynomials will not match, and nor will the equality.

To balance the equation we can introduce another polynomial :

such that for the correct chosen witness and hence equality holds.

A naive approach would be to just let prover choose . But it has critical flaw. The prover can choose get any random witness and calculate , r(x) and . Then prover can choose any arbitrary polynomial that balances the equation .

We restrict to have roots , so that the term vanishes to at any degree. To put this restriction is composed as:

and fix the to always be:

which forces to have roots and so do for .

Then can simply be calculated as:

Schwartz-Zippel Lemma

Schwartz-Zippel lemma says that given two polynomials and with degrees and where , the maximum number of points they can intersect is . This holds true even for polynomials in finite field.

This lemma can be exploited to check if two polynomials and are equal, succinctly. The naive way would be to check equality of all coefficients of polynomials - which would take linear time . But if polynomials are evaluated at some random variable and then comparing the evaluations and is constant time .

The check only fails for number of points where evaluations will be equal even though the polynomials are not same. But for a finite field of a very large size such that , it is very highly unlikely that a random point would be one of such points.

Succinct Proof

Now the verifier can use above property of Schwartz-Zippel lemma by choosing a random element and sends it to the prover to evaluate polynomials without revealing them. And prover calculates following:

Circuit Constraints

The polynomials , , and .

Proof

The elements , and .

Verification

Verifier checks:

This convinces verifier that prover indeed has the knowledge of a valid witness because the chances of prover randomly receiving a where polynomials intersect is close to none.

But this is still not secure since we have no way to verify that prover indeed performed the polynomial evaluations correctly.

This is where trusted setup comes in.

Trusted Setup

The trusted setup is basically a mechanism to evaluate a polynomial on a secret value such that it doesn't reveal information about the polynomial to the verifier and the prover does not get to know what value they are evaluating on.

Let be the polynomial in question. To initiate a party picks a secret scalar and calculates all the powers for :

Then to commit to it by multiplying the same by a generator point :

Theses powers of committed as elliptic curve points i.e. is called structure reference string (SRS). Using SRS anyone can compute any polynomial (of degree at most ) at without actually know the value of .

But right not there's a flaw. The person creating the SRS chose and is supposed to destroy it. It may not chose to do so and compromise or misuse it.

To tackle the problem of trusting single party for generating the SRS we make this setup multiparty. We do this by forwarding the SRS successively through multiple parties who also choose a secret scalar, say, and operate on previous SRS:

Now this process can go on and on through many number of parties. Even if one of the participating parties of this setup destroys their secret, it remains safe. The resulting artifact we get at the end of this ceremony is also called powers of tau.

QAP With Trusted Setup

Note that while we had laid out the QAP in , we didn't encrypt the witness. Now that prover has the trusted setup's SRS it can use it for encrypting the polynomials , , and .

Suppose trusted setup was performed to generate the SRS corresponding to both and groups as:

We encrypt the polynomial with , with and with . Writing for the coefficients of (highest degree first), and similarly for and , we take the dot product of the coefficient list with the matching half of the SRS from :

where operator represents dot product of two vectors.

But we can't really calculate the yet. Because we don't know the SRS for . The prover cannot use the SRS it used for and . Why? Because the degrees of polynomial differ from those. We need to figure out this SRS first. That means trusted setup needs to account for it.

Luckily, remember from that is a fixed known polynomial beforehand at the time of trusted setup, unlike . So for SRS for the polynomial , the ceremony can simply plug in the value to to get constant .

Now coming to , it has a degree of , inferred from . The ceremony can create trusted setup now as:

The whole trusted setup now gives us the SRS:

Proof With Trusted Setup

And now we can complete our previous evaluation as:

Circuit Constraints

The polynomials , , and .

Proof

The group elements , and .

Trusted Setup SRS

The elements:

Verification

The verifier checks:

The parameters , and is our proof. It is zero knowledge and succinct.

Groth16 Algorithm

The equation gives a legitimate algorithm to perform a valid zk proof verification. But right now, there is nothing stopping a prover from coming up random values to calculate , and to hand over to verifier.

and

To solve for the problem above Groth16 introduces two additional parameters and . These parameters are output of the trusted setup:

If we somehow update the verification formula to:

Now the point is unknown to everyone. The prover knows discrete logs of and . If it tries to select any such two points, to make the proof valid it will have to calculate also. But it cannot do so since is unknown and so it its discrete log. Similar argument goes if prover starts from a random .

But we cannot just randomly introduce it in our original equation. Instead let's try to come up with it by introducing the and to LHS of it.

Note that we used and to replace with .

The updated , and becomes:

The trusted setup now has to also random sample and to produce and as part of SRS.

Given our trusted setup the encrypted points become:

We've run into a problem now. To calculate , we cannot simply do point multiplication of and . Our trusted setup provides the and points, not plain values - those are discarded.

The problematic term for is part. And note that prover has to calculate without revealing the actual polynomials. Lets rewrite in summation form:

Prover cannot reveal to anyone. Trusted setup has to be independent of any witness value.

Therefore for each corresponding to each , the trusted setup must generate points as:

Notice we cannot calculate just one point. Because we have to separate witness vector item out and each term is being multiplied by a different term.

Groth16 Proof Without Public Inputs

Given new trusted setup SRS, now we can complete as:

Circuit Constraints

The polynomials , , and .

Trusted Setup SRS

The elements:

Proof

The group elements , and .

Verification

The verifier checks :

Public Inputs

Right now all of the values in witness vector remains private. But in practice, a verifier would want some of those values to be public so as to bind the prover to values of its requirements.

A naive approach would be to just let some subset of values in be exposed to verifier. Suppose, prover let subset ( size) of witness values to be public. Now instead of prover computing the commitments for this public part, verifier computes it:

So now represents public and rest represent private parts. The verification equation becomes:

But this would allow the prover to forge proofs with incorrect witness. In current form, the elements are meant to be used with the public elements of witness and rest i.e. for private. But nothing guarantees it.

For example, prover can pick a from one and calculate:

zeroing out the kth term.

And keep equation still balanced but moving over kth into the private part as:

Out original assertion with modified and in still holds. But the witness is incorrect.

Separating Public and Private Inputs: and

To segregate the public and private inputs, Groth16 introduces two more parameters and to the trusted setup. The trusted setup now generates the point differently for public and private inputs.

For public inputs:

and for private inputs:

Also since the part is also need to be private, the trusted setup also modifies the previous SRS for it from as:

Groth16 Proof With Public Inputs

As shown, the trusted setup simply divides the public and private parts by and respectively. The verifier now has to calculate as:

And the private part of is calculated as:

Circuit Constraints

The polynomials , , and .

Trusted Setup SRS

The elements:

Proof

The group elements , , and .

Verification

The verifier checks:

Note that we paired the terms with and , where the SRS was divided by and respectively - causing the terms to effectively cancel out and balance the equation.

Adding Randomness

Everything works fine so far. But there's still one flaw. An adversary can observing the proofs can run a brute force attack to find the witness, especially if the witness vector is small size. The same witness always produces exact same proof, so adversary can just keep guessing the witness until the generated proof matches the observed proof. In short, the proving algorithm is deterministic - it has no randomness.

To cope with this Groth16 introduces two random finite field elements and that prover pricks, every time it generates a proof.

Groth16 modifies the and polynomials by adding and to them:

(Note: the prover does not actually know the values of and since they are part of the trusted setup. But it can still use them to calculate and .)

Since and are modified, and also has to be modified to keep the equation balanced.

Using we can rewrite the above as:

Note that we have previously established that in and . Using that:

Now we know what and are supposed to be (the LHS parts). We need to determine the the public part and private part of the RHS. For that we need to convert RHS of in summation form, since the public and private subsets fo witness are processed differently:

As said earlier, witness public and private subsets are and respectively. So we can split the summation into two parts:

We have broken the RHS into two parts - the first part is the public part and the second part is the private part.

But remember in implementation, the public and private parts need to be divided by and and respectively. So we can rewrite the above as:

Observer now and determine our updated proof's elements in plain form:

(Note: We have extra terms and also now).

But the is in plain form. We need to convert those into group elements , , and to achieve the zero knowledge property. Lets see how.

First, trusted setup already provides and , so prover just needs to pair them as:

For the trusted setup provides and . It also provides SRS for polynomial term - . So prover can calculate as:

The element can be calculated similarly as:

For the trusted setup provides SRS for public witness part - (see ). It also yields the point. So prover calculates :

For the trusted setup provides SRS for rest () private witness part - (see ). But before calculating which must be a group element of (generator ) prover also needs to perform the point multiplication of with the term which is also part of .

Note that and are just random scalars chosen by the prover. and are already provided by trusted setup. is already calculated. But is a new term prover needs to calculate (previously we calculated ) as:

Now prover can calculate as:

Final Groth16 Proof

Now let us recall what each party has so far for the final proof generation:

Circuit Constraints

The polynomials , , and .

Trusted Setup SRS

The elements:

Proof

The group elements , , and .

Verification

The verifier checks:

This is the Groth16 proof system. It is succinct, zero knowledge and non-interactive. The proof size is constant, independent of the size of the circuit. The verification time is also constant, making it efficient for practical applications.