Selectors and Interpolation

A trivial way for the verifier to check if the constraints on the circuit hold would be to get copies of $LI,RI$ and $O$ and check them. But this would defeat the purpose of delegating the computation, because the amount of work that the prover has to do is equivalent to recomputing $F_4^2$ on his own. To make this more efficient, consider the following encoding of the vectors $LI,RI$ and $O$: suppose there was an easy way to transform those vectors into polynomials $a(x),b(x),c(x)$ such that, for every index $i\in I$, $a(i)=LI(i)$, $b(i)=RI(i)$ and $c(i)=O(i)$.

If this was possible, then the processor $P$ could hand in $a(x),b(x)$ and $c(x)$ to the validator, who can compute:

$$t(x)=a(x)+b(x)-c(x)$$

This polynomial has the property that for all indexes $i\in I\setminus 4$, $t(i)=0$.

Additionally, the validator needs to check that:

$$t^{\prime }(x)=a(x)\ast b(x)-c(x)$$

is zero for $x=4$.

Selectors

In order to simplify those checks, PLONK introduces the so-called selector columns (and their respective polynomials as follows). Consider three boolean vectors $SL,SR,SM$ such that $SL$ and $SR$ are set if a given index contains an addition gate, and zero otherwise. Likewise, $SM$ will be set whenever there is a multiplication gate. Their polynomial version satisfy $qL(i)=SL(i),qR(i)=SR(i),qM(i)=SM(i)$. Then we could compress checks for both addition and multiplication gates into one:

$$t(x)=qL(x)\cdot a(x)+qR(x)\cdot b(x)+qM(x)\cdot (a(x)\cdot b(x))-c(x)$$

This polynomial should now be 0 for all $i\in I$.

Wiring constraints

Moreover, we could also encode the missing constraints as follows:

$$f_1(x)=a(x+1)-b(x)$$$$f_2(x)=b(x+1)-c(x)$$

These two should also be zero at all but the last two indexes, $i\in I\setminus \{3,4\}$. Last we need to check:

$$f_3(x)=b(x)-c(x-1)$$$$f_4(x)=a(x)-b(x)$$

which should hold for $x=4$.

So by encoding the vectors $L,R,O$ into polynomials $a(x),b(x),c(x)$, a validator $V$ could in principle check all that is needed to convince themselves that $F_4^2=c(4)$ was computed correctly.

Although mathematically the Fibonacci function is defined over the naturals $\mathbb{N}$, when implementing zero-knowledge proofs we crucially do all arithmetic in a finite field ${\mathbb{F}}_p$, meaning values are taken modulo a prime $p$. There are various reasons why this is done. First, many cryptographic constructions rely on the difficulty of certain discrete problems over finite fields. Also, working on a field ensures every nonzero element has a multiplicative inverse, which will be useful in the following to reason about operations over polynomials. Last, arithmetic modulo $p$ is straightforward to implement and typically efficient.

Exercise 3

Represent the vectors $LI,RI,O,SL,SR,SM$ as polynomials $a,b,c,qL,qR,qM$ over the finite field ${\mathbb{F}}_p$ defined by

$$p=21888242871839275222246405745257275088548364400416034343698204186575808495617.$$

This prime number is the order of the bn254 elliptic curve, which will be useful in the following. To interpolate the polynomials use Lagrange interpolation as follows. Given a set of points $X=\{x_1,x_2,\dots ,x_n\}$ and data $(x_i,y_i)$ for each $i\in I$, the interpolating polynomial $f(x)$:

$$f(x)=\sum _{j\in I}(y_j\prod _{\begin{array}{c}i\in I\\ i\ne j\end{array}}\frac{x-x_i}{x_j-x_i})\in {\mathbb{F}}_p[x].$$

def interpolate(I, Y):
    """
    Given two lists I and Y of the same length n:
      I = [x1, x2, ..., x_n]
      Y = [y1, y2, ..., y_n]
    where all x_i are distinct, return the Lagrange interpolation polynomial f(x)
    such that f(x_i) = y_i for each i.
    """    
    #Solve here!
    return f

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617
F = GF(p)
R.<x> = PolynomialRing(F, 'x')   


SL= {1:1,2:1,3:1,4:0} #Similar as before, we use dictionaries to map 1..4 to selectors for each gate
SR=
SM=


qL = interpolate(I,list(SL.values())) #We interpolate over indexes i in I and the images SL[i] 
qR = 
qM = 


a =
b = 
c =

If computed correctly you should be able to check the following properties on the polynomials:

• They are all polynomials of degree 3 over ${\mathbb{F}}_p$
• When evaluated over the indexes $I$ you get the expected values as defined by $LI,RI,O$.
• When defining $t=a(x)+b(x)-c(x)$ you get 0 over the indexes $I$.

For example, the first polynomial is:

$$\begin{array}{rl}a(x)=& 10944121435919637611123202872628637544274182200208017171849102093287904247809x^3\\ +& 10944121435919637611123202872628637544274182200208017171849102093287904247805x^2\\ +& 8x\\ +& 21888242871839275222246405745257275088548364400416034343698204186575808495612\end{array}$$

#Is a(x) correctly interpolated?
for i in I:
    assert (a(i) == LI[i])

#Is b(x) correctly interpolated?
for i in I:
    assert b(i) == RI[i]

#Is c(x) correctly interpolated?
for i in I:
    assert (c(i) == O[i])


t = qM*a*b + qL*a+qR*b-c

#Do gate constraints hold?
for i in I:
    assert (t(i) == 0)

At this point we can also check the recursive constraints.

#Constraint f1
f1 = a(x+1)-b(x)

for i in I:
    if (i !=3) and (i != 4):
     assert f1(i) == 0

#Constraint f1
f2 = b(x+1)-c(x)

for i in I:
    if (i !=3) and (i != 4):
     assert f2(i) == 0