Properties that any zero knowledge based proving system needs to entertain:

  1. Completeness: Any honest prover can convince verifier of the statement and witness.
  2. Soundness: Any malicious prover can never convince a verifier of the statement that it’s trying to prove. In other words, if a prover doesn’t know witness, it can never convince the verifier.

Any proving system defines an n-variate polynomial with an evaluation recipe. Two parties involved in the process are Prover and Verifier.

SNARK

snark

Argument system that generate succinct and fast proofs for public statement in and secret witness in . The statement and witness need to be encoded in an arithmetic circuit .

Arithmetic circuits:

Requirements:

  1. Completeness:
  2. Knowledge Sound: P doesn’t know negligible

More formal definition:

Soundness

For dummies like me: for every polynomial time adversary, there exists an extractor that uses adversary to find out about , even though adversary doesn't know about , because if it would, then adversary can generate arbitrary proofs.

(S,P,V) is knowledge sound for a circuit if for every poly. time adversary A = (A_0, A_1) such that:

there is an efficient extractor , that uses s.t.

Zero Knowledge

For any normal proof, there exists a simulator which can generate proofs without knowledge of .

(S,P,V) is zero knowledge for circuit C if there is an efficient Sim s.t. , the distribution:

is indistinguishable from the distribution:

Proofs

Two ways to prove statement:

  • Interactive: prover and verifier goes back and forth to agree on some random values and parameters which verifier can then verify.
  • Non-interactive: Pre-processing done to generate a proof that allows verifier to verify circuit.

Preprocess argument system: prover preprocesses to generate public parameters .

Consists of :

  • : generate
  • : generate proof
  • : verify proof

How does gets generated? Is it done for every circuit or some other method? Wouldn't it be very bad UX if we have to run every time?: Each circuit needs some summary that can be used to verify the proof as no verifier will run the whole computation again, otherwise there's no benefits of these systems.

There has to be some randomisation involved that prover can’t forge by itself to generate these parameters.

  • First method is to generate random for every circuit outside prover.
  • Second is to generate a random value once , create some public parameters based on that, use those parameters to generate
  • Totally transparent: no random secrets needed to generate circuit parameters.

Pipeline followed by any ZKP system:

flowchart LR
A["computation"]
B["circuit"]
C["prover"]
D["IOP"]
E["verifier"]
A-- arithmetisation --> B
B-->C
C-->D
D-->E

Any circuit need to be proven to verifier, so we need to encode and evaluate our polynomial. Thus, most SNARK system consist of two components:

  1. Functional commitment scheme (FCS)
  2. Interactive oracle proofs (IOP)

PLONK: poly-IOP for General Circuit

Plonk IOP can be used with different PCS to generate different proving systems. For example:

  1. Aztec’s proving system: KZG+Plonk
  2. Halo2: Bulletproofs + Plonk, used by zcash
  3. Plonky2: FRI + Plonk, used by polygon zkevm
  4. Scroll: (halo2) plonk + kzg
Step 1: Compile Circuit for a Computation Trace

Suppose you have a circuit with inputs , and gates C where is the statement inputs and is the witness input. Our goal is to prove to verifier that .

circuit

We put inputs , and compute the computation trace through the circuit. The computation trace comes out to be:

inputs:561
Gate 0:5611
Gate 1:617
Gate 2:11777 Output
Step 2: Encode Trace in Polynomial
  • Calculate of = where |C|: no. of gates and |I|: no. of inputs
  • Aim: encode in a polynomial of form:
  • Encode inputs:
  • Encode gate wirings:
    • left input to gate l
    • right input to gate l
    • output of gate l
  • Prover has evaluations of , can use FFT to interpolate coefficients in
Step 3: Prove Validity of P

What does prover needs to prove to verifier in order to convince it?

  • correct output: to prove that output of computation was according to the statements and witness committed.
  • correct inputs: proves
  • correct intermediate gate evaluations:
  • wiring between gates is according to the statement specified by prover

Proof Gadgets for IOP

  • equality test to test if polynomial and are equal and note that verifier only has the commitment, verifier queries the polynomial at point or opens the commitment and test if values providied by prover are equal. But this generates soundness error.
  • soundness error two polynomials in can be zero at at most d roots, if
    • this assumption has error d/p such that if suppose g is not same as f, then g can have at most d different roots. thus, error
    • this is derived from Schwartz-Zippel Lemma kzg-proof-system

let be some subset of of size . Let be the polynomial that prover wants to prove. Verifier has commitment to this polynomial .

We can construct efficient poly-IOPs for the following tasks:

  1. Zero Test: Prove that is identically zero on
  2. Sumcheck: Prove that
  3. Product check: Prove that
  4. Permutation check: Prove that where is a permutation polynomial.

Question

  • Why do we do these checks only? What is the significance of these checks? What other checks can be done? Can we remove some checks or combine some checks?
  • How does the permutation polynomial is calculated?
  • Find the reasons behind these checks? Could you have come up with these yourselves?

Vanishing Polynomial of is . If becomes the multiplicative subgroup formed using primitive root of unity, then VP becomes . Thus, VP can be calculated in logarithmic time.

Zero Check

Let . Calculate .

Send to verifier, and verifier opens commitment at point , and check . This proves that f(x) is divisible by X^k-1, hence, f has roots in .

Sum Check

Read Sumcheck

Product Check on

We want to prove . Naively, we can send all evaluations of in but that will be quadratic in degree d. Instead, we can create a polynomial that evaluates to 1 at .

Let’s try a toy example in sage taken from here:

// verifying that f(x)=c in GF(17) for w = 4
F17 = GF(17)
R17.<x> = PolynomialRing(F17)
w = F17(4)
c0 = F17(2)
c1 = F17(3)
c2 = F17(4)
c3 = F17(5)
c = c0*c1*c2*c3
points = [(w^0, c0), (w, c1), (w^2, c2), (w^3, c3)]
R17.lagrange_polynomial(points)

So, we can define polynomial s.t. for s=1,…,k-1. Now in order to prove product check, we’ll prove:

  1. for all . This will be used to a zero test on t(X) so that verifier can get convinced that prover actually computed . This is proven using: .

The same product check holds for rational function as well, i.e. . Prove this using:

Permutation Check

It is used to check that two polynomials are permutation of each other. Mainly, prover wants to prove that: is a permutation of .

permutation

Can be done by creating two polynomials and and doing product check on these two polynomials. How will the product check work? It’s simply testing that .

Why can't we do zero test to check that these polynomials are equal? ::

Prescribed Permutation Check

Instead of just proving the permutation, prover wants to prove that , where is a permutation if is a bijection.

Why can't you use zero check here to check the two polynomials are equal? :: because g(W(y)) where y in will become O(d^2) in prover time. We don't want quadratic time prover.

Observation: If is a permutation of then . We prove this by defining bivariate polynomial:

We do product check on these two polynomials such that , where is the input queried by verifier.

Proving Validity of T(x).

T(x) is the polynomial that encodes the computation trace of the circuit.

Prove Inputs Were Correct.

Create polynomial v(y) on and do zero test on:

Prove Gate Evaluations Are Correct

Define a selector polynomial S(X) which is:

  1. if gate #l is an addition gate.
  2. if gate #l is a multiplication gate.

Then, you define the polynomial:

then it’s just the zero check.

Combining Gate Constraints into One Equation

You can very easily combine gate constraints into one equation:

where,

  1. : selector polynomial created for evaluation for left, right of a gate respectively.
  2. : selector polynomial for addition gate.
  3. : selector polynomial for multiplication gate.
  4. : polynomial for constant in a gate, ex: public inputs of the circuit.
  5. : polynomial for left, input and output values of the gates.

We can rewrite in terms of linear factors in ,

Term is Vanishing Polynomial:. Since, is a primitive nth root of unity, forms a cyclic group, and . Plonk says that, constraint system is satisfied, when the constraint equation is completely divided by Vanishing polynomial.

Prove Gate Wirings Are Correct.

encode the wires as permutation polynomial and prove through permutation check that wiring along the circuit is correct.

But we have three different n-degree poly, namely , thus we join these three polys into one polynomial of degree-3n:

and create a permutation on which gives . is chosen such that subset of array forms cycles.

Recap

plonk-iop

Formal Protocol

Prover’s Algorithm

Round 1:

Compute and send commitments to verifier.

Round 2:
  • Compute permutation challenge .
  • Compute permutation polynomial and send commitment to verifier.
Round 3:
  • Compute quotient polynomial and send commitment to verifier.
  • It uses quotient challenge: to distinguish the three conditions.

It contains all three conditions that is to be proven to the verifier, i.e.

  • equality constraint involving
  • permutation constraint:
Round 4:

Evaluation of at and evaluation challenge: at . Namely, .

Round 5:

Linearisation polynomial can be interpreted as . Thus, prover proves , evaluated at .

Proof polynomial: , and . It contains separate terms for each polynomial, separated using opening challenge: . Send and .

Overall Proof:

Proof consists of:

  1. 9 points:
  2. 6 evaluations:
  3. multipoint evaluation challenge:
  4. operations

Verifier Algorithm

Explained intuition behind the steps really well here. Just reiterating those here:

can be written as , and . Combining these two identities with multipoint evaluation challenge , we get:

Plonk Extensions

  • Turboplonk: Custom gates
  • Ultraplonk: Turboplonk+ Plookup
  • Hyperplonk
  • UniPlonk
  • Fflonk
  • Goblinplonk

TurboPlonk

Plonk’s arithmetization allows to efficiently add gates other than addition/multiplication. These gates are necessary to reduce constraints in a repetitive computation like hash function computation which involves bitwise arithmetic like XOR.

This article from Kobi explains really well, the design considerations for a custom gate model of MiMc hash.

Plonkup

Explanation of prover and verifier’s algorithm with reasoning of each step can be found in a beautiful explanation in a blog post by Joshua and by Hector.

References