Ariel Gabizon: The KZG PCS scheme and PlonK SNARK
1 The KZG polynomial commitment scheme - an informal intro
The idea of polynomial commitment schemes is that a prover can send a short commitment to a large polynomial ; and later open it at a point chosen by the verifier. can also construct a proof that the value he sends is really for the he had in mind during commitment time.
2 The KZG commitment scheme:
Prequisites: Given integer security parameter . We assume access to
Groups of prime order written additively with randomly chosen generator and generator . Denote by the field of size . A bi-linear pairing function such that
For , we use the notation .
Remark 2.1. How do we actually construct pairings?? They were first constructed by André Weil, where is taken to be the degree zero divisor class group of an algebraic curve - which is the same as the so-called Jacobian of the curve. In crypto we always use elliptic curves which are a special case, and where this group is isomorphic to the curve itself! These pairings were part of Weil's proof of what's called the Riemann hypothesis for curves over finite fields/Algebraic function fields. Much later, Victor Miller showed a practical algorithm to compute them (the "Miller loop").
2.1 The scheme:
setup: Generate srs , for random . Commitment to :
The open protocol - proving
computes sends V outputs acc if and only if
3 The Algebraic Group Model
We wish to capture the notion of an Algebraic Adversary that can generate new group elements by doing "natural" operations on the set of group elements he already received.
The intuition is that when the discrete log is hard, the group elements look random to (an efficient) adversary, and thus there's no other way for him to produce "useful" group elements.
More formally,
Definition 3.1. By an SRS-based protocol we mean a protocol between a prover and verifier such that at before the protocol begins a randomized procedure setup is run, returning a string srs .
In our protocols, by an algebraic adversary in an SRS-based protocol we mean a poly -time algorithm which satisfies the following.
Whenever outputs an element , it also outputs a vector over such that .
4 Knowledge Soundness of the KZG scheme
We say a PCS has Knowledge soundness in the Algebraic Group Model if, there exists an efficient algorithm such that any algebraic adversary has probability at most to win the following game:
outputs a commitment . outputs a polynomial outputs . takes part of in open . wins iff
(a) outputs acc in the end of open.
(b) .
We use the following extension of the discrete-log assumption:
Definition 4.1. The assumption for says that: For any efficient algorithm A, the probability that given for random outputs is negl
Lemma 4.2. Assuming the for has knowledge soundness in the algebraic group model
Proof. We must define the extractor : When outputs , since it's algebraic, it also outputs such that . will simply output . Let be some efficient algebraic adversary.
We will describe an algorithm following the game between and such that whenever wins the game, finds !.
During open when sends , it also sends such that . Assume we're in the case that won the game. This means that sent and such that acc. This means that In our case this is the same as This implies
Define the polynomial
We claim that can't be the zero polynomial: If it was, in particular , and then , which means - but won the game so !
So isn't the zero polynomial in the case that won. We claim that in this case we can find :
Note that we can compute the coefficients of , since sent the coefficients of and .
Since accepting means that . Thus, we can factor , and will be one of its roots. We can check for each root of if by checking .
5 Lecture 2: Proving circuit satisfiability Plonk style
We'll look at arithmetic circuits over
with addition and multiplication gates of fan-in 2 and unbounded fan-out. We'll assume there's a unique output wire we'll denote by the number of gates and the number of wires. We'll assume input wires go only into one gate (as someone astutely observed during the lecture, otherwise we need extra copy constraints in the BP program described later).
Draw example of circuit
Given such a circuit we can look at the relation containing all pairs ) such that is a valid assignment to the wires of with output value .
Though in SNARK context, we almost always want to look at relations and separate the instance and witness, for simplicity we'll focus on simply proving knowledge of some assignment to .
5.1 Baby-Plonk programs
We wish to reduce checking an assignment to a circuit to checking an assignment to a Plonk program. In the literature you will find references to Turbo-plonk and ultra-plonk programs. Here for simplicity, we look at a much more restricted notion of "baby plonk" programs, that are still sufficient to capture our circuits.
Definition 5.1. A Baby-PlonK program BP is defined by
vectors . A set of "copy constraints" of the form " " for some and
A set of vectors satisfies BP if
For each
Setting all copy constraints are satisfied.
Draw example as rectangle - emphasizing local vs global
5.2 Some algebra
Let's assume is a power of two, and divides . That means there's an element of order . That is is a multiplicative subgroup of order . We denote by the vanishing polynomial of . We have .
We have for any polynomial that for all iff is divisible by , i.e. iff there exists such that .
Given vector we'll say a polynomial interpolates over if it has degree for all . There is always such unique where are the Lagrange base of .
Given we abuse notation and denote by the same names the polynomials interpolating them.
Define
Assume that satisfy the copy constraints of BP. (Verifying that is in fact the more interesting part of PlonK and we'll deal with that later!) Then we have that satisfy BP iff is divisible by .
5.3 A protocol for checking satisfiability (missing the copy constraint checks for now)
Now we can use the KZG scheme to get a protocol checking an assignment for BP. The cool thing is that the proof size will be a constant number of and elements independent of ! (For construction to work we need that so in fact in terms of bit-length the proof is
In the description below we write com(()f) for the KZG commitment of .
Below we assume has a satisfying assignment to BP.
Preprocessing: We precompute the KZG commitments com(A),com(M) of and send them to .
The protocol:
computes and sends com(a),com(b),com(c) to V. With defined as above, computes the quotient polynomial . computes and sends com( to . V chooses random and sends it to . sends to . sends the KZG opening proofs for the above values. V verifies the KZG openings proofs for all values. computes . V accepts iff .
6 Lecture 3: the PlonK permutation argument (based on Bayer-Groth)
6.1 Copy checks via permutations
Let , and redefine as . In BP we have a bunch of constraints for . We can reduce all checks to one permutation check. This mean checking for some fixed permutation on , that . Here we define by . example: Say we have the constraints . Define . Then satisfies the copy constraints iff .
6.2 Mutliset checks via grand products
Let's look at a related problem that we will use soon for the permutation check. Now has two vectors of size and wishes to show to they are equal as multisets, i.e. that there is some permutation such that .
Here is a protocol for this.
V sends random shows to that
Claim 6.1. Let . The check in equation 2 holds with probability one if are mutliset equal, and probability at most if they are not.
Proof. Define the polynomials We are checking . If are mutliset equal so this holds for all . If they are not so they can be equal for at most .
One main question is how efficiently shows to that equation 2 holds when only has commitments to ? We will see a solution soon!
6.3 Permuations via mulitset checks
For our SNARK, we wish to check that for a fixed permutation . We show we can reduce this check to a multiset check.
Claim 6.2. Given a permutation on and vectors , we have if and only if the sets of pairs and are equal as (multi)sets.
The mulitset protocol dealt with scalars, not tuples. Here we can use a little randomness to reduce the scalars to tuples.
Claim 6.3. Given sets of pairs as in the claim above and . Define the mutlisets . Then if are different as sets, then are different as multisets except with probability over
Proof. If , there is some pair . For any fixed the probability that is at most . Now do a union bound over elements of .
6.4 grand products via polynomial equations
Now we deal with the following question. Suppose has a KZG-commitment to a polynomial of degree (as before think of as interpolating the vector over . Suppose that . How can prove this to ?
Protocol:
interpolates on the vector with values for . I.e . computes and send to . sends random to . computes poly:
sends random to . sends sends the KZG opening proofs for the above values. verifies the openings proofs for all values. V computes accepts iff .
Claim 6.4. If then rejects e.w.p .
Proof. Define the polynomial
similar to the protocol of the previous lecture, the protocol is checking if vanishes on via a divisibility check. Assume it does vanish on . Then e.w.p over this implies both terms and vanish on .
vanishing on implies . vanishing on implies that for each . And so
as required.
6.5 Putting it all together
We sketch how the above components can be used to show assuming has :
chooses random .
uses the above grand product argument to show . For the vector defined as
To enable this we compute in a preprocessing phase the polynomials that interpolate on the identity and permutation. I.e. . For full details see Section 5 of the PlonK paper.
7 Lecture 4 - lookup arguments
Say we want to prove in a plonk program that . We could do it as follows: sends the binary decomposition and proves that
Send are binary, via equation .
This takes gates - in fact more like since the addition has to be split up. Lookup arguments offer an alternative approach. For polynomials let's write if as sets . A lookup protocol allows proving this to having . Say . Say we want to check all of 's vals are . In the above example, we could precompute com( for with values on and apply lookup protocol.
7.1 plookup - Lookup protocols via multiset checks
Fix . Define the multi-set
Claim 7.1. Assume (for simplicity mainly) contains distinct values and is sorted: if and only if there exists such that defining , we have as multisets.
Proof. only if: Define to be the sorted version of the (mutli-set) union . Then .
7.2 Lookups based on log-derivative
The main claim is :
Claim 7.2. Assume is prime and larger than if and only if there exists such that as rational functions
Proof. only if: Define to be the number of times appears in . if(sketch): The functions for different are linearly independent, therefore the functions in the equation being equal implies every coefficient is equal. So there can't be any on the RHS for .
protocol idea:check identity on random
computes and send chooses random . sends for polynomial with checks that is well-formed and sums to zero on .
Checking that is well-formed - has the correct values, can be done by a quotient polynomial similar to others we've seen.
7.3 Proving a polynomial sums to zero:
We rely on the following claim from the Aurora paper:
Claim 7.3. Given .
Proof.
We have for all .