Plonk By Hand

Reference

plonk by hand (part1)

plonk by hand (part2)

plonk by hand (part3)

Codes

All the codes below are python with SageMath.

K = GF(101)
# y^2=x^3+3
E = EllipticCurve(K,[0,0,0,0,3])

G = E(1,2) # <G> is subgroup of order 17, 17*G=inf
for i in range(1,18):
    print(i*G)

​​​​(1 : 2 : 1)
​​​​(68 : 74 : 1)
​​​​(26 : 45 : 1)
​​​​(65 : 98 : 1)
​​​​(12 : 32 : 1)
​​​​(32 : 42 : 1)
​​​​(91 : 35 : 1)
​​​​(18 : 49 : 1)
​​​​(18 : 52 : 1)
​​​​(91 : 66 : 1)
​​​​(32 : 59 : 1)
​​​​(12 : 69 : 1)
​​​​(65 : 3 : 1)
​​​​(26 : 56 : 1)
​​​​(68 : 27 : 1)
​​​​(1 : 99 : 1)
​​​​(0 : 1 : 0)

embedding degree

The degree of the extension field of characteristic

$p$ that contains every point of order

$r$ on the elliptic curve is the embedding degree. It has a simple formula: the embedding degree is the smallest number

$k$ such that

$r|p^k-1$. Since

$600\ast 17=({101}^2-1)/17$, the embedding degree for

$\mathbb{E}({\mathbb{F}}_{101})$ is

$2$.

If r is relatively prime to the charactersitc p of the field, then there will be exactly

$r^2$ points of order r in

${\mathbb{F}}_{p^k}$. Thus, there are total of

${17}^2$ points on the elliptic curve

$\mathbb{E}({\mathbb{F}}_{{101}^2})$

extension field

Find an irreducible polynomial of degree

$2$ on

${\mathbb{F}}_{101}$, e.g.

$x^2+2$. Let

$u$ be a solution, then all the points in

${\mathbb{F}}_{{101}^2}$ can be written as

$a+b\cdot u,\mathrm{\forall }a,b\in {\mathbb{F}}_{101}$

# use the twisted curve technique from pairing for beginner
# to get another generator of order 17 (G2)
# (36, 31*u) 
mod(36^3,101)+3  == mod(31^2,101)*(-2)  # x^3+3 = y^2 mod 101

​​​​True

# define field extention F_{101^2} over F_101 with irreducible poly x^2+2
del(x)
x=var("x")
K2.<u> = GF(101^2, modulus=x^2 + 2,name='x')
# elliptic curve over F_{101^2}
E2=EllipticCurve(K2,[0,0,0,0,3])
P=E2(36,31*u)
2*P

​​​​(90 : 82*u : 1)

trusted setup

a circuit with

$n$ gates requires an SRS with at least

$n+5$ elements as below

$$G_1,s\cdot G_1,\cdots ,s^{n+2}\cdot G_1,G_2,s\cdot G_2$$

suppose secret random number

$s=2$, and

$n=4$ we have srs:

$$(1,2),(68,74),(65,98),(18,49),(1,99),(68,27),(65,3),(31,36u),(90,82u)$$

Statement

(Pythagorean Triangle) Find

$(x_1,x_2,x_3)$ such that

$x_1^2+x_2^2=x_3^2$.

General form of plonk circuit is

$$q_{L}a+q_{R}b+q_{O}c+q_{M}ab+q_C=0$$
The Pythagorean circuit becomes

$$\begin{gathered} 0\cdot a_1+0\cdot b_1+(-1)\cdot c_1+1\cdot a_1{b}_1+0=0 \\ 0\cdot a_2+0\cdot b_2+(-1)\cdot c_2+1\cdot a_2{b}_2+0=0 \\ 0\cdot a_3+0\cdot b_3+(-1)\cdot c_3+1\cdot a_3{b}_3+0=0 \\ 1\cdot a_4+1\cdot b_4+(-1)\cdot c_4+0\cdot a_4{b}_4+0=0 \end{gathered}$$

In matrix form we have:

a	b	c	q_L	q_R	q_O	q_M	q_C
3	3	9	0	0	-1	1	0
4	4	16	0	0	-1	1	0
5	5	25	0	0	-1	1	0
9	16	25	1	1	-1	0	0

where

$a,b,c$ are advice columns in halo2, and the rest five columns are selectors (fixed column)

polynomial interpolation

We need subgroup of order

$4$ to interpolate each column, and luckily, the scalar field

${\mathbb{F}}_{17}$ has root of unity

$\omega =4$. Thus the subgroup is

$H$, and we can split the non-zero elements into cosets.

$$\begin{gathered} H=({\omega }^0,{\omega }^1,{\omega }^2,{\omega }^4)=(1,4,16,13) \\ {k}_{1}H=2H=(2,8,15,9) \\ {k}_{2}H=3H=(3,12,14,5) \end{gathered}$$

For polynomial

$f(x)=a+bx+c{x}^2+d{x}^3$,

$f({\omega }^i)=(1,{\omega }^i,{\omega }^{2i},{\omega }^{3i})\cdot (a,b,c,d{)}^T$. Define matrix

$\mathrm{\Omega }=({\omega }^{ij}{)}_{i,j}$. By inverse FFT, we have

$$\begin{gathered} (a,b,c,d)={\mathrm{\Omega }}^{-1}\cdot (f({\omega }^0),f({\omega }^1),f({\omega }^2),f({\omega }^3){)}^T \\ =\frac{1}{4}({\omega }^{-ij}{)}_{i,j}\cdot (f({\omega }^0),f({\omega }^1),f({\omega }^2),f({\omega }^3){)}^T \end{gathered}$$

$${\mathrm{\Omega }}^{-1}=\begin{array}{c}\frac{1}{4}\end{array}\cdot \left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 13& 16& 4\\ 1& 16& 1& 16\\ 1& 4& 16& 13\end{array}\right]=\left[\begin{array}{cccc}13& 13& 13& 13\\ 13& 16& 4& 1\\ 13& 4& 13& 4\\ 13& 1& 4& 16\end{array}\right]$$
Notice

$({\omega }^{-ij}{)}_{i,j}$ is "conjugate transpose" of

$\mathrm{\Omega }$, not transpose.

omega=matrix(GF(17),[[1,1,1,1],[1,4,16,13],[1,16,1,16],[1,13,16,4]])
omega.inverse()

​​​​[13 13 13 13]
​​​​[13 16  4  1]
​​​​[13  4 13  4]
​​​​[13  1  4 16]

Thus all the polynomials for each row are:

$$\begin{gathered} f_a=1+13x+3x^2+3x^3 \\ {f}_b=7+3x+14x^2+13x^3 \\ {f}_c=6+5x+11x^2+4x^3 \\ {q}_L=13+x+4x^2+16x^3 \\ {q}_R=13+x+4x^2+16x^3 \\ {q}_O=16 \\ {q}_M=5+16x+13x^2+x^3 \\ {q}_C=0 \end{gathered}$$

copy constraint

From

$x_1^2+x_2^2=x_3^3$, we have

$6$ constraints:

$$\begin{gathered} a_1=b_1=x_1 \\ {a}_2=b_2=x_2 \\ {a}_3=b_3=x_3 \\ {a}_4=c_1 \\ {b}_4=c_2 \\ {c}_4=c_3 \\ (a_1,b_1),(a_2,b_2),(a_3,b_3),(a_4,c_1),(b_4,c_2),(c_4,c_3) \end{gathered}$$

encode permutation from copy constraint as polynomial

If we use

$H=[1,4,16,13]$ to define the values on cell

$\mathbf{a}$,

$k_{1}H=[2,8,15,9]$ to define values on cell

$\mathbf{b}$,

$k_{2}H=[3,12,14,5]$ to label values on cell

$\mathbf{c}$. The only requirement here is that these values are unique. Then, the

$6$ copy constraints defined permutaion on these values:

$(1,2)(4,8)(16,15)(13,3)(9,12)(14,5)$. And we can encode them as polynomials:

$$\begin{gathered} S_{{\sigma }_1}(x)=7+13x+10x^2+6x^3 \\ {S}_{{\sigma }_2}(x)=4+13\ast x^2+x^3 \\ {S}_{{\sigma }_3}(x)=6+7x+3x^2+14x^3 \end{gathered}$$

# fine the polynomial by apply inverse FFT
H=[1,4,16,13] # values of S_{sigma1}(x) before permutation
H1=[2,8,15,9] # values of S_{sigma2}(x) before permutation
H2=[3,12,14,5] 
perm = Permutation('(1,2)(16,15)(4,8)(13,3)(9,12)(14,5)') # permutation on the evaluation domain of polynomials
val = [[perm(i)] for i in H] # values of S_{sigma1}(x) after permutation
val1 = [[perm(i)] for i in H1] # values of S_{sigma2}(x) after permutation
val2 = [[perm(i)] for i in H2]
p=omega.inverse()*matrix(GF(17),val)
p1=omega.inverse()*matrix(GF(17),val1)
p2=omega.inverse()*matrix(GF(17),val2)
print(p.transpose())
print(p1.transpose())
print(p2.transpose())

​​​​[ 7 13 10  6]
​​​​[ 4  0 13  1]
​​​​[ 6  7  3 14]

# check the polynomial evaluation on [1,omega,omega^2,omega^3]
perm = Permutation('(1,2)(16,15)(4,8)(13,3)(9,12)(14,5)')
H=[1,4,16,13]
H1=[2,8,15,9]
H2=[3,12,14,5] 
R.<t>=PolynomialRing(GF(17))

p1=7+13*t+10*t^2+6*t^3
l1=[int(p1(x)) for x in H]
print(l1,[perm(i) for i in H]) # should equal

p2=4+13*t^2+t^3
l2=[int(p2(x)) for x in H]
print(l2,[perm(i) for i in H1]) # should equal

p3=6+7*t+3*t^2+14*t^3
l3=[int(p3(x)) for x in H]
print(l3,[perm(i) for i in H2])

​​​​[2, 8, 15, 3] [2, 8, 15, 3]
​​​​[1, 4, 16, 12] [1, 4, 16, 12]
​​​​[13, 9, 5, 14] [13, 9, 5, 14]

Round 1

commit a,b,c
With

$Z_H(x)=x^4-1$, we have:

$$\begin{gathered} a(x)=(b_{1}x+b_2)\cdot Z_H(x)+f_a(x) \\ b(x)=(b_{3}x+b_4)\cdot Z_H(x)+f_b(x) \\ c(x)=(b_{5}x+b_6)\cdot Z_H(x)+f_c(x) \end{gathered}$$

Generating random numbers in

${\mathbb{F}}_{17}$, suppose we got

$(b_1,b_2,b_3,b_4,b_5,b_6)=(7,4,11,12,16,2)$. Then

$$\begin{gathered} a(x)=14+6x+3x^2+3x^3+4x^4+7x^5 \\ b(x)=12+9x+14x^2+13x^3+12x^4+11x^5 \\ c(x)=4+6x+11x^2+4x^3+2x^4+16x^5 \end{gathered}$$
Finally, we commit them with SRS

$$\begin{gathered} [a(x)]=[a(x)]\cdot (1,2)=(91,66) \\ [b(x)]=(26,45) \\ [c(x)]=(91,35) \end{gathered}$$

def commit_to_curve(coeff, base):
    commitment = 0*base;
    s = 2 # secret value
    for i in range(len(coeff)):
        commitment += coeff[i]*(s^i*base)
    return commitment
a=[14,6,3,3,4,7]
b=[12,9,14,13,12,11]
c=[4,6,11,4,2,16]        
comm_a = commit_to_curve(a,G)
comm_b = commit_to_curve(b,G)
comm_c = commit_to_curve(c,G)
print(comm_a,comm_b,comm_c)

​​​​(91 : 66 : 1) (26 : 45 : 1) (91 : 35 : 1)

Round 2

Generate

$(b_7,b_8,b_9)=(14,11,7)\in {\mathbb{F}}_{17}$, get challenge

$(\beta ,\gamma )=(12,13)\in {\mathbb{F}}_{17}$, compute

$z(x)$:

$$\begin{gathered} z(x)=(b_7{x}^2+b_{8}x+b_9)\cdot Z_H(x)+acc(x) \\ ac{c}_0=1 \\ ac{c}_i=ac{c}_{i-1}\frac{(a_i+\beta {\omega }^{i-1}+\gamma )(b_i+\beta k_1{\omega }^{i-1}+\gamma )(c_i+\beta k_2{\omega }^{i-1}+\gamma )}{(a_i+\beta S_{{\sigma }_1}({\omega }^{i-1})+\gamma )(b_i+\beta S_{{\sigma }_2}({\omega }^{i-1})+\gamma )(c_i+\beta S_{{\sigma }_3}({\omega }^{i-1})+\gamma )} \\ ac{c}_1=1\cdot \frac{(3+12\ast 1+13)(3+12\ast 2\ast 1+13)(9+12\ast 3\ast 1+13)}{(3+12\ast 2+13)(3+12\ast 1+13)(9+12\ast 13+13)}=\frac{11\cdot 6\cdot 7}{6\cdot 11\cdot 8}=3 \\ ac{c}_2=3\cdot \frac{(4+12\ast 4+13)(4+12\ast 2\ast 4+13)(16+12\ast 3\ast 4+13)}{(4+12\ast 8+13)(4+12\ast 4+13)(16+12\ast 9+13)}=3\cdot \frac{14\cdot 11\cdot 3}{11\cdot 14\cdot 1}=9 \\ ac{c}_2=9\frac{(5+12\ast 16+13)(5+12\ast 2\ast 16+13)(25+12\ast 3\ast 16+13)}{(5+12\ast 15+13)(5+12\ast 16+13)(25+12\ast 5+13)}=9\cdot \frac{6\cdot 11\cdot 2}{11\cdot 6\cdot 13}=4 \\ acc(x)=16x+5x^2+14x^3 \\ z(x)=(14x^2+11x+7)(x^4-1)+16x+5x^2+14x^3=10+5x+8x^2+14x^3+7x^4+11x^5+14x^6 \\ [z(x){]}_1=[z(x)]\ast (1,2)=(32,59) \end{gathered}$$

# commitment of z(x)
omega=matrix(GF(17),[[1,1,1,1],[1,4,16,13],[1,16,1,16],[1,13,16,4]])
acc=omega.inverse()*matrix(GF(17),[[1],[3],[9],[4]])
coeff_z = [10,5,8,14,7,11,14]
commit_to_curve(coeff_z,G)

​​​​(32 : 59 : 1)

Round 3

Compute quotient challenge

$\alpha =15\in {\mathbb{F}}_{17}$, compute quotient polynomial

$$\begin{gathered} t(x)=(a(x)b(x)q_M(x)+a(x)q_L(x)+b(x)q_R(x)+c(x)q_O(x)+PI(x)+q_C(x))\frac{1}{Z_H(x)} \\ +(a(x)+\beta x+\gamma )(b(x)+\beta k_{1}x+\gamma )(c(x)+\beta k_{2}x+\gamma )z(x)\frac{\alpha }{Z_H(x)} \\ -(a(x)+\beta S_{{\sigma }_1}(x)+\gamma )(b(x)+\beta S_{{\sigma }_2}(x)+\gamma )(c(x)+\beta S_{{\sigma }_2}(x)+\gamma )z(\omega x)\frac{\alpha }{Z_H(x)} \\ +(z(x)-1)L_1(x)\frac{{\alpha }^2}{Z_H(x)} \end{gathered}$$
Then split into degree

$<n+2$ polynomials

$t_{lo}(x),t_{mid}(x),t_{hi}(x)$ where

$$t(x)=t_{lo}(x)+t_{mid}(x)+t_{hi}(x)$$
Output

$[t_{lo}(x)],[t_{mid}(x)],[t_{hi}(x)]$.

We have

$$\begin{gathered} t(x)=11x^{17}+7x^{16}+2x^{15}+16x^{14}+6\ast x^{13}+15x^{12}+x^{11}+10x^{10}+2x^9+x^8+8x^7+13x^6+13x^5+9x^3+13x^2+16x+11 \\ {t}_{lo}=11+16x+13x^2+9x^3+13x^5 \\ {t}_{mid}=13+8x+x^2+2x^3+10x^4+x^5 \\ {t}_{hi}=15+6x+16x^2+2x^3+7x^4+11x^5 \end{gathered}$$

And the commitment

$$\begin{gathered} [t_{lo}{]}_1=(12,32) \\ [t_{mid}{]}_1=(26,45) \\ [t_{hi}{]}_1=(91,66) \end{gathered}$$

omega=matrix(GF(17),[[1,1,1,1],[1,4,16,13],[1,16,1,16],[1,13,16,4]])
R.<x>=PolynomialRing(GF(17))
# Lagrange polynomial L_1(x)
L_1=omega.inverse()*matrix(GF(17),[[1],[0],[0],[0]])
l1=13+13*x+13*x^2+13*x^3
a = 14+6*x+3*x^2+3*x^3+4*x^4+7*x^5
b =12+9*x+14*x^2+13*x^3+12*x^4+11*x^5
c=4+6*x+11*x^2+4*x^3+2*x^4+16*x^5
q_L=13+x+4*x^2+16*x^3
q_R =13+x+4*x^2+16*x^3 
q_O = 16 
q_M=5+16*x+13*x^2+x^3
z = 10+5*x+8*x^2+14*x^3+7*x^4+11*x^5+14*x^6
zomega = 10+3*x+9*x^2+12*x^3+7*x^4+10*x^5+3*x^6
sig1=7+13*x+10*x^2+6*x^3
sig2=4+13*x^2+x^3
sig3=6+7*x+3*x^2+14*x^3
t1=(a*b*q_M + a*q_L +b*q_R+c*q_O)
t2=(a+12*x+13)*(b+12*2*x+13)*(c+12*3*x+13)*z*15
t3=(a+12*sig1+13)*(b+12*sig2+13)*(c+12*sig3+13)*zomega*15
t4=(z-1)*l1*15*15
final=t1+t2-t3+t4
t=final/(x^4-1)
t

​​​​11*x^17 + 7*x^16 + 2*x^15 + 16*x^14 + 6*x^13 + 15*x^12 + x^11 + 10*x^10 + 2*x^9 + x^8 + 8*x^7 + 13*x^6 + 13*x^5 + 9*x^3 + 13*x^2 + 16*x + 11

tlow=[11,16,13,9,0,13]
tmid=[13,8,1,2,10,1]
thi=[15,6,16,2,7,11]
tlow=commit_to_curve(tlow,G)
tmid=commit_to_curve(tmid,G)
thi=commit_to_curve(thi,G)
print(tlow,tmid,thi)

​​​​(12 : 32 : 1) (26 : 45 : 1) (91 : 66 : 1)

Round 4

Linearization. Compute evaluation challenge

$\zeta =5\in {\mathbb{F}}_{19}$.

Compute opening evaluations

$$\begin{gathered} \overline{a}=a(\zeta ),\overline{b}=b(\zeta ),\overline{c}=c(\zeta ) \\ \overline{S_{{\sigma }_1}}=S_{{\sigma }_1}(\zeta ),\overline{S_{{\sigma }_2}}=S_{{\sigma }_2}(\zeta ) \\ \overline{t}=t(\zeta ) \\ \overline{z_{\omega }}=z(\omega \zeta ) \end{gathered}$$
Compute linearization polynomial (linear w.r.p commitment values):

$$\begin{gathered} r(x)=\overline{a}\overline{b}{q}_M(x)+\overline{a}{q}_L(x)+\overline{b}{q}_R(x)+\overline{c}{q}_O(x)+q_C(x) \\ +\alpha (\overline{a}+\beta \zeta +\gamma )(\overline{b}+\beta k_1\zeta +\gamma )(\overline{c}+\beta k_2\zeta +\gamma )z(x) \\ -\alpha (\overline{a}+\beta \overline{S_{{\sigma }_1}}+\gamma )(\overline{b}+\beta \overline{S_{{\sigma }_2}}+\gamma )\beta \overline{z_{\omega }}{S}_{{\sigma }_3}(x) \\ +{\alpha }^{2}z(x)L_1(\zeta ) \end{gathered}$$
The definition of

$r(x)$ is not same as in plonk paper, where we removed all the constant terms when we do linearization. This can save one verifier scalar multiplication.

Compute linearization evaluation

$\overline{r}=r(\zeta )$. And output

$$\overline{a},\overline{b},\overline{c},\overline{S_{{\sigma }_1}},\overline{S_{{\sigma }_2}},\overline{z_{\omega }},\overline{t},\overline{r}$$

Supose

$\zeta =5$, we have (I skip the calculation here, just copy from the blog):

$$\begin{gathered} \overline{a}=a(5)=15,\overline{b}=13,\overline{c}=5,\overline{S_{{\sigma }_1}}=1,\overline{S_{{\sigma }_2}}=12,\overline{t}=1,\overline{z_{\omega }}=15 \\ r(x)=16x+9x^2+13x^3+8x^4+15x^5+16x^6 \\ \overline{r}=15 \end{gathered}$$
Output

$$\begin{gathered} \overline{a}=15,\overline{b}=13,\overline{c}=5 \\ \overline{S_{{\sigma }_1}}=1,\overline{S_{{\sigma }_2}}=12 \\ \overline{t}=1 \\ \overline{z_{\omega }}=15 \\ \overline{r}=15 \end{gathered}$$

Round 5

Compute opening challenge

$v\in {\mathbb{F}}_{19}$

Compute opening proof polynomial

$W_{\zeta }(x)$:

$$W_{\zeta }(x)=\begin{array}{c}\frac{1}{x-\zeta }\end{array}\cdot \left[\begin{array}{c}{t}_{lo}(x)+{\zeta }^{n+2}{t}_{mid}(x)+{\zeta }^{2n+4}{t}_{hi}(x)-\overline{t}\\ +v(r(x)-\overline{r})\\ +v^2(a(x)-\overline{a})\\ +v^3(b(x)-\overline{b})\\ +v^4(c(x)-\overline{c})\\ +v^5(S_{{\sigma }_1}(x)-\overline{S_{{\sigma }_1}})\\ +v^6(S_{{\sigma }_2}(x)-\overline{S_{{\sigma }_2}})\end{array}\right]$$
Compute opening proof polynomial

$W_{\zeta \omega }(x)$:

$$W_{\zeta \omega }(x)=\frac{z(x)-\overline{z_{\omega }}}{x-\zeta \omega }$$
Output

$$[W_{\zeta }(x){]}_1,[W_{\zeta \omega }(x){]}_1$$

Given

$\zeta =5$, we have

$[W_{\zeta }(x){]}_1=(91,35),[W_{\zeta \omega }(x){]}_1=(65,98)$

FF=GF(17)
omega=FF(4);zeta=FF(5)
v=FF(12);tbar=FF(1);abar=FF(15);bbar=FF(13);cbar=FF(5);
sig1bar=FF(1);sig2bar=FF(12);zomega=FF(15);rbar=FF(15)
R.<x>=PolynomialRing(GF(17))
tlow=11+16*x+13*x^2+9*x^3+13*x^5
tmid=13+8*x+x^2+2*x^3+10*x^4+x^5
thi=15+6*x+16*x^2+2*x^3+7*x^4+11*x^5
r=16*x+9*x^2+13*x^3+8*x^4+15*x^5+16*x^6
sig1=7+13*x+10*x^2+6*x^3
sig2=4+13*x^2+x^3
z = 10+5*x+8*x^2+14*x^3+7*x^4+11*x^5+14*x^6
term1=tlow+zeta^6*tmid+zeta^12*thi-tbar
term2=v*(r-rbar)
term3=v^2*(a-abar)+v^3*(b-bbar)+v^4*(c-cbar)
term4=v^5*(sig1-sig1bar)+v^6*(sig2-sig2bar)
Wz=(term1+term2+term3+term4)/(x-zeta)
Wzw=(z-zomega)/(x-zeta*omega)

wz=[16,13,2,9,3,5]
wzw=[13,14,2,13,2,14]
c1=commit_to_curve(wz,G)
c2=commit_to_curve(wzw,G)
print(c1,c2)

​​​​(91 : 35 : 1) (65 : 98 : 1)

Proof

$$\begin{gathered} \pi =([a],[b],[c],[z],[t_{lo}],[t_{mid}],[t_{hi}],[W_{\zeta }],[W_{\zeta \omega }] \\ \overline{a},\overline{b},\overline{c},\overline{S_{{\sigma }_1}},\overline{S_{{\sigma }_2}},\overline{z_{\omega }},\overline{r}) \end{gathered}$$
In our case,

$$\begin{gathered} \pi =((91,66),(26,45),(91,35),(32,59),(12,32),(26,45),(91,66),(91,35),(65,98) \\ 15,13,5,1,12,15,15) \end{gathered}$$

Verify Preprocessing

$$\begin{gathered} [q_M]=(12,69) \\ [q_L]=(32,42) \\ [q_R]=(32,42) \\ [q_O]=(1,99) \\ [q_C]=\mathrm{\infty } \\ [s_{{\sigma }_1}]=(68,74) \\ [s_{{\sigma }_2}]=(65,3) \\ [s_{{\sigma }_3}]=(18,49) \end{gathered}$$

R.<x>=PolynomialRing(GF(17))
omega=matrix(GF(17),[[1,1,1,1],[1,4,16,13],[1,16,1,16],[1,13,16,4]])
qm=omega.inverse()*matrix(GF(17),[[1],[1],[1],[0]]) #[ 5 16 13  1]
commit_to_curve([ 5, 16, 13,  1],G) # [q_M]=(12,69)

​​​​(12 : 69 : 1)

Verifier Algorithm

1. Validate
   $[a],[b],[c],[z],[t_{lo}],[t_{mid}],[t_{hi}],[W_{\zeta }],[W_{\zeta \omega }]\in G_1$
2. Validate
   $\overline{a},\overline{b},\overline{c},\overline{S_{{\sigma }_1}},\overline{S_{{\sigma }_2}},\overline{z_{\omega }},\overline{r}\in {\mathbb{F}}_{17}$.
3. Validate
   $w_{i\in [l]}\in {\mathbb{F}}_{17}$ (public inputs)
4. Compute zero polynomial evaluation:
   $Z_H(\zeta )={\zeta }^n-1$.
5. Compute
   $L_1(\zeta )=\frac{{\zeta }^n-1}{n(\zeta -1)}$
6. Compute public input polynomial evaluation:
   $PI(\zeta )=\sum _{i\in [l]}{w}_i{L}_i(\zeta )$
7. Compute quotient polynomial evaluation:
   
   $$\overline{t}=\frac{\overline{r}+PI(\zeta )-(\overline{a}+\beta \overline{S_{{\sigma }_1}}+\gamma )(\overline{b}+\beta \overline{S_{{\sigma }_2}}+\gamma )(\overline{c}+\gamma )\alpha -L_1(\zeta ){\alpha }^2}{Z_H(\zeta )}$$
8. Compute first part of batched polynomial commitment. Define
   $[D]=v[r(x)]+u[z]$:
   
   $$\begin{gathered} [D]=\overline{a}\overline{b}v[q_M]+\overline{a}v[q_L]+\overline{b}v[q_R]+\overline{c}v[q_O]+v[q_C] \\ +((\overline{a}+\beta \zeta +\gamma )(\overline{b}+\beta k_1\zeta +\gamma )(\overline{c}+\beta k_2\zeta +\gamma )\alpha v+L_1(\zeta ){\alpha }^{2}v+u)[z] \\ -(\overline{a}+\beta \overline{S_{{\sigma }_1}}+\gamma )(\overline{b}+\beta S_{{\sigma }_2}+\gamma )\alpha v\beta \overline{z_{\omega }}[S_{{\sigma }_3}] \end{gathered}$$
9. Compute full batched polynomial commitment
   
   $$[F]=[t_{lo}]+{\zeta }^{n+2}[t_{mid}]+{\zeta }^{2n+4}[t_{hi}]+[D]+v^2[a]+v^3[b]+v^4[c]+v^5[S_{{\sigma }_1}]+v^6[S_{{\sigma }_2}]$$
10. Compute group encoded batch evaluation
    $[E]$:
    
    $$[E]=(\overline{t}+v\overline{r}+v^2\overline{a}+v^3\overline{b}+v^4\overline{c}+v^5\overline{S_{{\sigma }_1}}+v^6\overline{S_{{\sigma }_2}}+u\overline{z_{\omega }})\cdot [1]$$
11. Batch validate all evaluations:
    
    $$e([W_{\zeta }]+u[W_{\zeta \omega }],[s{]}_2)=e(\zeta [W_{\zeta }]+u\zeta \omega [W_{\zeta \omega }]+[F]-[E],[1{]}_2)$$

Calculation

Let's check steps

$9-11$ for each of the polynomials. For example the terms with

$u$

$$\begin{gathered} e(u\cdot s\cdot [W_{\zeta \omega }],1)\stackrel{?}{=}e(u\zeta \omega [W_{\zeta \omega }]+u[z]-uz(\omega \zeta ),1) \\ e(u\cdot (s-\zeta \omega )[W_{\zeta \omega }],1)\stackrel{?}{=}e(u(z(s)-z(\omega \zeta ),1) \\ (s-\zeta \omega )\frac{z(s)-z(\zeta \omega )}{s-\zeta \omega }\stackrel{?}{=}z(s)-z(\omega \zeta ) \end{gathered}$$
Let's check

$r(x)$, here we define

$[W_{\zeta }]=\frac{v(r(s)-r(\zeta ))}{s-\zeta }$ for simplicity:

$$\begin{gathered} e(s\cdot [W_{\zeta }],1)\stackrel{?}{=}e(\zeta [W_{\zeta }]+v\cdot r(s)-v\overline{r},1) \\ e((s-\zeta )\cdot \frac{v(r(s)-r(\zeta ))}{s-\zeta },1)\stackrel{?}{=}e(v(r(s)-r(\zeta )),1) \end{gathered}$$
Let's check

$t(x)$, here we define

$[W_{\zeta }]=\frac{t_{lo}(s)+{\zeta }^{n+2}{t}_{mid}(s)+{\zeta }^{2n+4}{t}_{hi}(s)-t(\zeta )}{s-\zeta }$ for simplicity

$$\begin{gathered} e((s-\zeta )[W_{\zeta }],1)\stackrel{?}{=}e([t_{lo}]+{\zeta }^{n+2}[t_{mid}]+{\zeta }^{2n+4}[t_{hi}]-\overline{t},1) \\ e(t_{lo}(s)+{\zeta }^{n+2}{t}_{mid}(s)+{\zeta }^{2n+4}{t}_{hi}(s)-t(\zeta ),1)\stackrel{?}{=}e(t_{lo}(s)+{\zeta }^{n+2}{t}_{mid}(s)+{\zeta }^{2n+4}{t}_{hi}(s)-t(\zeta ),1) \end{gathered}$$
The other terms are easy to check as well.

Verify with concret example

1. the blog only checks the points are on the curve, not check if in the subgroup
   $G_1$. However, in our case, we have the table of all elements of
   $G_1$, which is easy to compare the commitments with table.
2. just check the values are less than
   $17$.
3. skip, no public inputs.
4. $Z_H(\zeta )=12$
5. $L_1(\zeta )=\frac{{\zeta }^n-1}{n(\zeta -1)}=5$
6. skip, no public inputs.
7. $\overline{t}=1$
8. $[D]=inf$
9. $[F]=(68,27)$
10. $[E]=(1,2)$
11. $e((32,42),(36,31u))\stackrel{?}{=}e((12,69),(90,82u))$

FF=GF(17)
zeta=FF(5)
#4.
zh=zeta^4-1
#5.
l1=(zeta^4-1)/(4*(zeta-1)) #l1=5
#7.
alpha=FF(15);beta=FF(12);gamma=FF(13)
[a,b,c,sig1,sig2,zw,r]=[FF(x) for x in [15,13,5,1,12,15,15]]
t=(r-(a+beta*sig1+gamma)*(b+beta*sig2+gamma)*(c+gamma)*alpha-l1*alpha^2)/zh

#8
zeta=5;alpha=15;beta=12;gamma=13;l1=5
[a,b,c,sig1,sig2,zw,r] = [15,13,5,1,12,15,15]
k1=2;k2=3;v=12;u=4;qm=E(12,69);ql=E(32,42);qr=E(32,42);qo=E(1,99)
ssig1=E(68,74);ssig2=E(65,3);ssig3=E(18,49)
z=E(32,59)
dn1=a*b*v*qm+a*v*ql+b*v*qr+c*v*qo
dn2a=(a+beta*zeta+gamma)*(b+beta*k1*zeta+gamma)*(c+beta*k2*zeta+gamma)*alpha*v+l1*alpha^2*v+u
dn2=dn2a*z
dn3a=(a+beta*sig1+gamma)*(b+beta*sig2+gamma)*a*v*beta*zw
dn3=dn3a*ssig3
D=dn1+dn2+dn3 # (0:1:0)=inf

#9.
n=4
[ca,cb,cc,cz,ctlo,ctmid,cthi,cwz,cwzw]=[E(91,66),E(26,45),E(91,35),E(32,59),E(12,32),E(26,45),E(91,66),E(91,35),E(65,98)]
F=ctlo+zeta^(n+2)*ctmid+zeta^(2*n+4)*cthi+D+v^2*ca+v^3*cb+v^4*cc+v^5*ssig1+v^6*ssig2
#10.
t=1
Es=t+v*r+v^2*a+v^3*b+v^4*c+v^5*sig1+v^6*sig2+u*zw
E0=Es*G
#11.
left1=cwz+u*cwzw
left2=2*G
w=4
right1=zeta*cwz+u*zeta*w*cwzw+F-E0
right2=G

# 11.
K = GF(101)
# y^2=x^3+3
E = EllipticCurve(K,[0,0,0,0,3])
# define field extention F_{101^2} over F_101 with irreducible poly x^2+2
# x is poluted so we need to reset them before define K2
del(x)
x=var("x")
K2.<u> = GF(101^2, modulus=x^2 + 2,name='x')
# elliptic curve over F_{101^2}
E2=EllipticCurve(K2,[0,0,0,0,3])
P=E2(36,31*u)
2*P

tags: public plonk zkp