ZK-SNARKs: The Low Level Working

Published on: Feb 28, 2022

Feb 28, 2022

Currently at Xord we are researching ZK-SNARKs in depth.  Although Maksym Petkus does an excellent job of explaining why and how ZK-SNARKs works. I am still left with many questions at the time of reading the paper. In doing so, my purpose of writing is to make this research more accessible and take a deep dive into the low level concepts. This article will discuss each step of ZK-SNARKs at low level from polynomials to general purpose zero knowledge proofs.

Legacy blockchains such as Bitcoin and Ethereum are facing the huge problem of long queues of verification blocks due to their over-growing state size. With zero-knowledge we don’t need to replay each block for verification.  We have tons of resources available in bits and pieces but the concrete picture is still indispensable. 

Zero-knowledge succinct non-interactive arguments of knowledge or simply ZK-SNARK is a shrewd method of proving something is true or false without revealing any sacred information.

It was proposed in 1980’s by three MIT researchers Shafi Goldwasser, Silvio Micali and Charles Rackoff. Back then, they were working on an Interactive proof system where the prover interacts with the verifier to convince him about something without declaring any specific knowledge.

  1. Succinct--> The proof is a few hundred bytes which can be verified in milliseconds regardless of the size of the problem.
  2. Non-interactive--> The proof is a single message from prover to verifier. No back and forth communication is required.
  3. ARgument of knowledge--> A zero-knowledge argument is a zero-knowledge proof which has computational soundness (a polynomial-time prover can not convince the verifier about the false statement.

Examples

  1. To prove that you know the solution of a sudoku puzzle without providing the solution.
  2. Paying taxes without revealing earnings.
  3. Matching DNA without revealing full DNA.
  4. Trustless computing which outsources the computation while validating the authenticity of the computation.
  5. One party computes and everyone can verify.

Here is the hierarchical research of zero-knowledge proofs since its inception in 1985.

 A zk protocol must satisfy these three properties:

  1. Completeness: If the statement is true, the verifier will get convinced.
  2. Soundness: A cheating prover with false proof can not convince the verifier.
  3. Zero-Knowledgeness: The interaction only reveals if the statement is true or false, nothing else.

The ZK-SNARK Journey

Let us assume that a verifier wants to verify certain transactions in a block. For simplicity, take 20 transactions in a block. The verifier can only check one transaction at a time. In order to verify the whole block the verifier can proceed with arbitrary positions of a block with 1/20 confidence. A verifier must proceed until he reaches certain confidence. The downside of such a proving method is that one must go through a number of checkpoints proportional to the number of transactions which is impractical if we include thousands of transactions in a block. Instead we use the moon math of zero-knowledge to get the assurity of the prover’s claim.

The first step in the journey of ZK-SNARKs is to create a function to write proofs. This should work in any language but realistically this won’t provide much good to ZK-SNARKs construction. ZK-SNARKs work with specific construction which is also known as Quadratic Arithmetic Programs.

I have written a basic guide to QAPs as well. You can read it from here.

To begin with, suppose we have a polynomial x3-5x2+5x-3 which represents some graph points. The degree of the polynomial is the greatest exponent of x, which in this case is 3. Note here, that for blockchain this degree is directly proportional to the amount of data need to represent.

Polynomials provide an advantageous property, which is if we have two different polynomials with degree d. They can not have the same intersection points more than the d points. Means if the prover slightly tries to change the original data he can not convince the verifier. To elaborate, let's slightly alter the above equation.

 x3-5x2+8x-3 

We can see that even the smallest change in the coefficients can produce a dramatically different result. 

To mathematically evaluate the shared points we can equate both the equations.

x3-5x2+5x-2 = x3-5x2+8x-3 

3x-1=0

x=1/3 is the only point where the two polynomials intersect. Thus we can assure that the evaluation of any polynomial at any arbitrary position is compelled to represent a unique value. No two different polynomials could commit to the same data points. This property provides another great advantage which is:

If a prover is claiming to know some polynomial at some large degree d, the verifier can easily verify by evaluating that polynomial in different checkpoints. The verifier will simply:

  1. Give the position x to the prover for the evaluation of polynomials.
  2. The prover will provide the polynomial result at x to the verifier.
  3. The verifier will match the result with the locally computed result. If this matches the verifier will get satisfied that the prover P knows the polynomial. The verifier here is not storing anything except the statement which he is trying to validate.

This is the main reason why polynomials have high significance in ZK-snarks. We will see the working of above points in a short while but first we need to understand the basic concepts of polynomial and its representation.

A polynomial can be expressed as:

c0x0+c1x1+. . . .+cnxn

So if a person claimed that he or she knows the polynomial, what exactly they mean is that they have the knowledge of c0,c1,. . .cn. So basically these coefficients can store the account address and the corresponding values in two different polynomials which will then be represent as a tuple with their corresponding indexes. We can also represent this polynomial as a product of its factors.

(x-α0)(x-α1). . . (x-αn)=0

Take a polynomial x3-4x2+3x= (x-0)(x-1)(x-3)----------------------------------- Equation1

Now if a prover claims that he knows a polynomial with degree 3 and have roots 1 and 3 without disclosing the polynomial itself, he needs to prove that indeed his polynomial p(X)have the roots t(x)=(x-1)(x-3) also known as target polynomial and some arbitrary polynomial h(x). The target polynomial for now made public by the prover and can be use by both prover and verifier.

Meaning the prover is not revealing all the roots however, whatever the target roots he is revealing is going to form a polynomial after the multiplication of remaining roots.

such as in the above equation1 he is making the public roots and target polynomial-> (x-1)(x-3)

p(x)=t(x).h(x)

The h(x) here is the hidden root (x-0).

In simple words there must exist a polynomial h(x) which makes p(x)=t(x).h(x). so the most easiest way of finding h(x) is to take the ratio of p(X) and t(X).

h(x)=p(x)/t(x)

If the prover is unable to find such h(x), this indicates that the cofactors t(x) are not the correct.

In our example if we divide the p(x) x3-4x2+3x to t(X)=(x-1)(x-3)=x2-4x+3 

h(x)=x3-4x2+3x/ x2-4x+3

h(x)=x(x2-4x+3) /x2-4x+3

We have got the result h(X)=x with remainder 0 which is the other root of the equation.

How the Protocol Works?

  • Verifier samples random value r and evaluates t(r). He then sends this r to the prover.
  • The prover calculate h(x)=p(x)/t(x) and evaluate it at r.
  • The prover sends the evaluation of p(x) and h(x) at r which is (p(r) and h(r) )to the verifier.
  • The verifier first evaluates t(x) at r and then checks the relation p(r)=t(r).h(r) which ensures that  p(x) has cofactors as t(x) and h(x).

Now, using this construction we can check the validity of a polynomial without learning the polynomial itself which kinda lies in the zone of zero-knowledge and succinctness. Nonetheless there are multiple issues with this scheme.

Problem 

What if the prover does not know the polynomial p(x) or don't acquire the full blockchain data? so how can he convince the verifier about some false polynomial?

He can do this, because the prover knows x=r in advance  he can calculate the t=t(r) by selecting some random h(r) which proves to be p(r)=t(r).h(r), which will be accepted by the verifier as the equation holds.

This means with public t(x) he can compute the t(r) and guess the polynomial h(r)such that it fullfills this condition.

p(r)=t(r).h(r)

The Possible Solution

The issue lies with r and t(r) which the prover knows in advance. We can solve this issue If the verifier, instead of providing the original r, gives something which can not be tempered and served as a blackbox such as the hash of r. However, we must not forget that we need to perform arithmetic calculations over r which in normal encryption is not possible with hashes.

So to combat this, researchers have introduced a new strong encryption method known as “Strong Homomorphic Encryption”, which allows arithmetic operations on hashes. We will discuss about these arithmetic operations in details.

Backed with such technology, we can evaluate a polynomial with an encrypted value of x or random r provides by the verifier. We now take a step by step approach of designing the SNARK protocol. From completeness to zero-knowledge to non-interactivity.

Completeness

Step 1: Encryption of a Polynomial

Before proceeding we must know that the homomorphic encryption doesn’t allow exponentiation of an encrypted value. hence we cant perform this action: E(x), E(x)2and E(x)3 instead the prover must be given the values of power of x from 1 to 3: E(x), E(x2 )and E(x3)so the evaluation for the equation x3-3x2+2x will be E(x3)1.E(x2)-3.E(x)2

(gx3)1.(gx2)-3.(gx)2

gx3-3x2+2x

So the protocol for polynomial with degree 3 will look like this:

  • Verifier will sample the random value r=5 and calculates all  the ith encryption of r  at g=2

E(ri)=gri such as ( gr0, gr1, . . grd) and provide these encrypted powers to the prover.


Now with taking the equation mentioned above we redesign our protocol.

  • Verifier evaluates unencrypted target polynomial t(r) at r=5. t(r)=(5-1)(5-3)=8
    E(5)3=(2^5),(2^52),(2^53). Note here that the verifier has no knowledge of coefficients.
  • Prover calculates h(x)=p(x)/t(x) which is (x-0).
  • Using encrypted powers (gr0, gr1, . . grd =(2^5),(2^52),(2^53)) and coefficients (c0,c1,. . .,cn =2,-3,1) prover evaluates gp(r)=(gr0)c0,(gr1)c1, . . .(grd)cd OR (2^5)2,(2^52)-3,(2^53)1and E(h(r))=gh(r) =2rand send the evaluated gp(r) and gh(r) to the verifier.
  • In the last step, the verifier checks the relation gp=(g(t(s).h)

Although this protocol has restricted the prover’s celerity, there are still few conditions exists where the prover can forge the proof without actually using the given encrypted power of random r. 

Soundness

Restriction on the Polynomial

The knowledge of a polynomial hides in its coefficients c0, c1, . . .cn , or in (exponential form) in its exponents P(xi)ci=gci. xi A prover needs to compute gp, gh. However, he is not forced to do that. He, the prover can compute any arbitrary values such as zp, zh to satisfy the equation zp= (zh)t(x). For example for any random value r, the prover can compute zh=gr and zp=(gt(x))r where, gt(s) can be computed from the public encryption power of x.  We get these public powers by initial setup ceremony or the preprocessing of SNARK.

To understand this let's consider our previous example of third degree polynomial f(x)=x3-3x2+2x .  What we desire here is that only encryption of x is homomorphically multiplied by some arbitrary coefficient c and nothing else. Let's see how we could do this? We could do this by using alpha shift or knowledge of exponent assumption.

Suppose Eve has a value “α”, that she wants Jacob’s to exponentiate to any power. The only requirement here is that only this specific α should get exponentiated, nothing else. This is how we design a protocol to do that.

  • Eve chooses some random value r.
  • Calculates α'=αr(mod n).
  • Eve now provides this tuple (α,α') to Jacob, assuming that he will perform exponentiation on each value and return the resulting tuple (x, x') such that the alpha shift remains constant.

Now,  Jacob can not retrieve the alpha shift from the provided tuple. The only way to produce a right response is to exponentiate the given tuple.

  • Jacob chooses some value b.
  • Calculates x=(α)b modn and x'.=(α')b modn .
  • Reply with (x, x'))

Having the response (x, x') and r Eve checks the equality.

(x)r=x'

b)r=(α')b

Hence, this protocol provides a proof to Eve that Jacob has exponentiated α by some value only known to him, and indeed he has not performed any other operation such as addition or multiplication since doing this will disturb the alpha shift. This provides full confidence to the system.

To continue with our example of   x3-3x2+2x . We can again re-design the protocol with a similar approach.

  1. Verifier choses the random s, and provides evaluations for x=s for power 3 as ( gs1,gs2,gs3).
  2. Prover applies the coefficient c and evaluates g(p)=((gs3)1,(gs2)-1(gs)2)=gs3-3s2+2s and g(p')=((gα.s3)1,(gα.s2)-1(gα.s)2)=gα.(s3-3s2+2s).
  3. Verifier checks (gp)α=gp'.

We now have a robust protocol which has restricted the prover to only use the provided encryption as without this the α-shift will not be preserved. We now have reached the completeness and few basic scenarios of soundness of the protocol but the drawback in zero-knowledgness is still there.

Maksym in his paper has provided a very strong argument which states that “while theoretically polynomial coefficients ci can have a vast range of values, in reality, it might be quite limited , which means that the verifier could brute-force limited range of coefficients combinations until the result is equal to the prover’s answer. For instance if we consider the range of 100 values for each coefficient, the degree 2 polynomial would total to 1 million of distinct combinations, which considering brute-force would require less than 1 million iterations. Moreover, the secure protocol should be secure even in cases where there is only one coefficient, and its value is 1”. Because the verifier can extract the polynomial knowledge using the data provided by the prover, we need to make certain implications in the protocol. 

Zero-Knowledgeness

Suppose the proof provided is gp,gp',gh and they have to pass the following checks:

gp=(gh)t(s)

(gp)α=gp'

We can use the similar approach of shift property to alter the proof in a way that the validity still holds but no knowledge has been revealed. We can shift these values with some random . 

  • The prover calculates (gp(s)) δ,(gh(s)δ,(gp'(s)))δ and provides this to the verifier. 
  • The verifier checks that (gp) δ=((gh) δ)t(s).

((gp)δ)α=(gp')δ

After improvements the checks still hold.

g δ.p=g δ.t(s)h

g δ.αp=g δ.p'

In the above step we have made a protocol which can securely transmit the proof without revealing any knowledge. 

The last step towards our writing is non-interactivity. 

Non-Interactivity 

The question arises here is why we really need non-interactivity? There might be the following reasons for doing so.

  1. Blockchain is a one way road.
  2. The verifier can collaborate with the prover and reveal the secret s and alpha-shift to create a fake proof.
  3. The proof is only valid for the original verifier, as nobody could trust the same proof or prover.
  4. This is also inefficient if one wants to prove multiple verifiers simultaneously.
  5. Prover needs to be online all the time for every verifier.

So we need the secret parameters (t(s),α) to be reusable, public, trustworthy and infeasible to forge. We can do this by using the same encryption method the verifier has used for his secret s but to note here that we or the verifier needs to perform multiplication with these secret parameters and we can’t do that with homomorphic encryption. That's where pairings come in.

Parings leverage the elliptic curves to achieve the non-interactivity and soundness of the protocol. In Zero-knowledge we want to destroy most of the information or somehow design functions in way that they should produce an output which are completely irrelevant to the input. However, in order to prevent the prover from cheating and generating fake proofs the verifier must know what statement is being proven which is linked to the soundness of scheme. Pairing in itself is a deep topic which we are leaving for another post but below i have tried to give a gist of this blackbox.

Cryptographic Pairings 

Pairings or bilinear mappings is a cryptographic function which can be denoted as e(g*,g*) which have two encrypted inputs (g α,gb) from one set of numbers which map them to another set of numbers as their multiplication representation such as e(g α,g b)=e(g,g)αb.

Since the multiplication has a different set of numbers than the inputs therefore, we can not derive the input from it. We have a property in cryptography which swaps the base to the exponent while producing the same answer as before the swap.

e(gα,gb)=αg.bg=(αb)g

Since the multiplication of ab will give a different g so the encrypted multiplication can not be guessed. We can even perform addition with pairings too.

e(gα,gb).e(gc,gd)=gαb.gcd=gαb+cd=e(g,g)αb+cd

Here are some of the properties of pairings.

e(gα,gb)=e(gbgα)=e(gαb,g1)=e(g1,gαb)=e(g1,gα)b=e(g1,g1)αb

How pairings helps us in constructing SNARK, we will see that in the next post.

Resources

  1. Bryan Parno, Craig Gentry, Jon Howell, and Mariana Raykova. Pinocchio: Nearly Practical Verifiable Computation. Cryptology ePrint Archive, Report 2013/279
  1. Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again. Cryptology ePrint Archive, Report 2011/443
  2. Vitalik Buterin. zk-SNARKs: Under the Hood. 2017

Written by

Modularism maxi, exploring scalability problems in blockchain tech.

Related articles

© 2022 | All Rights Reserved
arrow-leftarrow-right linkedin facebook pinterest youtube rss twitter instagram facebook-blank rss-blank linkedin-blank pinterest youtube twitter instagram