# Plonk By Hand
## Reference
[plonk by hand (part1)](https://research.metastate.dev/plonk-by-hand-part-1/)
[plonk by hand (part2)](https://research.metastate.dev/plonk-by-hand-part-2-the-proof/)
[plonk by hand (part3)](https://research.metastate.dev/plonk-by-hand-part-3-verification/)
## Codes
All the codes below are python with SageMath.
```python
K = GF(101)
# y^2=x^3+3
E = EllipticCurve(K,[0,0,0,0,3])
```
```python
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 * 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, \forall a, b\in \mathbb{F}_{101}$
```python
# 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
```python
# 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_La+q_Rb+q_Oc+q_Mab+q_C=0$$
The Pythagorean circuit becomes
$$0\cdot a_1+0\cdot b_1+(-1)\cdot c_1 + 1\cdot a_1b_1+0=0\\
0\cdot a_2+0\cdot b_2+(-1)\cdot c_2 + 1\cdot a_2b_2+0=0\\
0\cdot a_3+0\cdot b_3+(-1)\cdot c_3 + 1\cdot a_3b_3+0=0\\
1\cdot a_4 + 1\cdot b_4 + (-1)\cdot c_4 + 0\cdot a_4b_4+0=0
$$
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.
$$H=(\omega^0,\omega^1,\omega^2,\omega^4)=(1,4,16,13)\\
k_1H=2H=(2,8,15,9)\\
k_2H=3H=(3,12,14,5)
$$
For polynomial $f(x)=a+bx+cx^2+dx^3$, $f(\omega^i)=(1,\omega^i,\omega^{2i},\omega^{3i})\cdot (a,b,c,d)^T$. Define matrix $\Omega=(\omega^{ij})_{i,j}$. By inverse FFT, we have
$$(a,b,c,d)=\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 $$
$$\Omega^{-1}=
\begin{matrix}
\frac{1}{4}
\end{matrix}
\cdot
\begin{bmatrix}
1 & 1 & 1 & 1\\
1 & 13 & 16 & 4\\
1 & 16 & 1 & 16\\
1 & 4 & 16 & 13
\end{bmatrix}
=
\begin{bmatrix}
13 & 13 & 13 & 13\\
13 & 16 & 4 & 1\\
13 & 4 & 13 & 4\\
13 & 1 & 4& 16
\end{bmatrix}
$$
Notice $(\omega^{-ij})_{i,j}$ is "conjugate transpose" of $\Omega$, not transpose.
```python
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:
$$
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\\
$$
**copy constraint**
From $x_1^2+x_2^2=x_3^3$, we have $6$ constraints:
$$
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)
$$
**encode permutation from copy constraint as polynomial**
If we use $H=[1,4,16,13]$ to define the values on cell $\mathbf{a}$, $k_1H=[2,8,15,9]$ to define values on cell $\mathbf{b}$, $k_2H=[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:
$$
S_{\sigma_1}(x)=7+13x+10x^2+6x^3\\
S_{\sigma_2}(x)=4+13*x^2+x^3\\
S_{\sigma_3}(x)=6+7x+3x^2+14x^3\\
$$
```python
# 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]
```python
# 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:
$$
a(x) = (b_1x+b_2)\cdot Z_H(x) + f_a(x)\\
b(x) = (b_3x+b_4)\cdot Z_H(x) + f_b(x) \\
c(x) = (b_5x+b_6)\cdot Z_H(x) + f_c(x) \\
$$
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
$$
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\\
$$
Finally, we commit them with SRS
$$
[a(x)] = [a(x)]\cdot (1,2) =(91,66)\\
[b(x)] = (26,45)\\
[c(x)] = (91,35)\\
$$
```python
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)$:
$$
z(x)=(b_7x^2+b_8x+b_9)\cdot Z_H(x) + acc(x)\\
acc_0 = 1\\
acc_i = acc_{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)}\\
acc_1 = 1\cdot\frac{(3+12*1+13)(3+12*2*1+13)(9+12*3*1+13)}{(3+12*2+13)(3+12*1+13)(9+12*13+13)}=\frac{11\cdot 6\cdot 7}{6\cdot 11\cdot 8}=3\\
acc_2=3\cdot\frac{(4+12*4+13)(4+12*2*4+13)(16+12*3*4+13)}{(4+12*8+13)(4+12*4+13)(16+12*9+13)}=3\cdot\frac{14\cdot 11\cdot 3}{11\cdot 14\cdot 1}=9\\
acc_2=9\frac{(5+12*16+13)(5+12*2*16+13)(25+12*3*16+13)}{(5+12*15+13)(5+12*16+13)(25+12*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)]*(1,2)= (32,59)
$$
```python
# 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
$$
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)}
$$
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
$$
t(x)=11x^{17} + 7x^{16} + 2x^{15} + 16x^{14} + 6*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\\
$$
And the commitment
$$[t_{lo}]_1=(12,32)\\
[t_{mid}]_1=(26,45)\\
[t_{hi}]_1=(91,66)$$
```python
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
```python
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
$$\bar{a}=a(\zeta),\bar{b}=b(\zeta),\bar{c}=c(\zeta)\\
\bar{S_{\sigma_1}}=S_{\sigma_1}(\zeta), \bar{S_{\sigma_2}}=S_{\sigma_2}(\zeta)\\
\bar{t}=t(\zeta)\\
\bar{z_{\omega}}=z(\omega\zeta)
$$
Compute linearization polynomial (linear w.r.p commitment values):
$$r(x)=\bar{a}\bar{b}q_M(x)+\bar{a}q_L(x)+\bar{b}q_R(x)+\bar{c}q_O(x)+q_C(x)\\
+\alpha(\bar{a}+\beta\zeta+\gamma)(\bar{b}+\beta k_1\zeta+\gamma)(\bar{c}+\beta k_2\zeta+\gamma)z(x)\\
-\alpha(\bar{a}+\beta\bar{S_{\sigma_1}}+\gamma)(\bar{b}+\beta\bar{S_{\sigma_2}}+\gamma)\beta\bar{z_{\omega}} S_{\sigma_3}(x)\\
+\alpha^2z(x)L_1(\zeta)\\
$$
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 $\bar{r}=r(\zeta)$. And output
$$\bar{a},\bar{b},\bar{c},\bar{S_{\sigma_1}},\bar{S_{\sigma_2}},\bar{z_{\omega}},\bar{t},\bar{r}$$
Supose $\zeta=5$, we have (I skip the calculation here, just copy from the blog):
$$
\bar{a}=a(5)=15,\bar{b}=13,\bar{c}=5,\bar{S_{\sigma_1}}=1,\bar{S_{\sigma_2}}=12,\bar{t}=1,\bar{z_{\omega}}=15\\
r(x)= 16x+9x^2+13x^3+8x^4+15x^5+16x^6\\
\bar{r}=15
$$
Output $$
\bar{a}=15,\bar{b}=13,\bar{c}=5 \\
\bar{S_{\sigma_1}}=1,\bar{S_{\sigma_2}}=12\\
\bar{t}=1\\
\bar{z_{\omega}}=15\\
\bar{r}=15
$$
### Round 5
Compute opening challenge $v\in\mathbb{F}_{19}$
Compute opening proof polynomial $W_{\zeta}(x)$:
$$
W_{\zeta}(x) =
\begin{matrix}
\frac{1}{x-\zeta}
\end{matrix}\cdot
\begin{bmatrix}
t_{lo}(x)+\zeta^{n+2}t_{mid}(x)+\zeta^{2n+4}t_{hi}(x)-\bar{t}\\
+v(r(x) - \bar{r})\\
+v^2(a(x) - \bar{a})\\
+v^3(b(x) - \bar{b})\\
+v^4(c(x) - \bar{c})\\
+v^5(S_{\sigma_1}(x) - \bar{S_{\sigma_1}})\\
+v^6(S_{\sigma_2}(x) - \bar{S_{\sigma_2}})\\
\end{bmatrix}
$$
Compute opening proof polynomial $W_{\zeta\omega}(x)$:
$$W_{\zeta\omega}(x)=\frac{z(x)-\bar{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)$
```python
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)
```
```python
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
$$\pi=([a],[b],[c],[z],[t_{lo}],[t_{mid}],[t_{hi}],[W_{\zeta}],[W_{\zeta\omega}]\\
\bar{a},\bar{b},\bar{c},\bar{S_{\sigma_1}},\bar{S_{\sigma_2}},\bar{z_{\omega}},\bar{r})$$
In our case,
$$\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)$$
### Verify Preprocessing
$$[q_M]=(12,69)\\
[q_L]=(32,42) \\
[q_R]= (32,42)\\
[q_O]=(1,99)\\
[q_C]= \infty\\
[s_{\sigma_1}]=(68,74)\\
[s_{\sigma_2}]= (65,3)\\
[s_{\sigma_3}]= (18,49)$$
```python
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$
1. Validate $\bar{a},\bar{b},\bar{c},\bar{S_{\sigma_1}},\bar{S_{\sigma_2}},\bar{z_{\omega}},\bar{r}\in\mathbb{F}_{17}$.
1. Validate $w_{i\in[l]}\in \mathbb{F}_{17}$ (public inputs)
1. Compute zero polynomial evaluation: $Z_H(\zeta)=\zeta^n-1$.
1. Compute $L_1(\zeta)=\frac{\zeta^n-1}{n(\zeta-1)}$
1. Compute public input polynomial evaluation: $PI(\zeta)=\sum_{i\in[l]}w_iL_i(\zeta)$
1. Compute quotient polynomial evaluation:
$$\bar{t}=\frac{\bar{r}+PI(\zeta)-(\bar{a}+\beta\bar{S_{\sigma_1}}+\gamma)(\bar{b}+\beta\bar{S_{\sigma_2}}+\gamma)(\bar{c}+\gamma)\alpha-L_1(\zeta)\alpha^2}{Z_H(\zeta)}$$
1. Compute first part of batched polynomial commitment. Define $[D]=v[r(x)]+u[z]$:
$$[D]=\bar{a}\bar{b}v[q_M]+\bar{a}v[q_L]+\bar{b}v[q_R]+\bar{c}v[q_O]+v[q_C]\\
+((\bar{a}+\beta\zeta+\gamma)(\bar{b}+\beta k_1\zeta+\gamma)(\bar{c}+\beta k_2\zeta+\gamma)\alpha v+L_1(\zeta)\alpha^2 v+u)[z]\\
-(\bar{a}+\beta\bar{S_{\sigma_1}}+\gamma)(\bar{b}+\beta{S_{\sigma_2}}+\gamma)\alpha v\beta\bar{z_{\omega}}[S_{\sigma_3}]$$
1. 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}]$$
1. Compute group encoded batch evaluation $[E]$:
$$[E]=(\bar{t}+v\bar{r}+v^2\bar{a}+v^3\bar{b}+v^4\bar{c}+v^5\bar{S_{\sigma_1}}+v^6\bar{S_{\sigma_2}}+u\bar{z_{\omega}})\cdot[1]$$
1. 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$
$$
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)\\
$$
Let's check $r(x)$, here we define $[W_{\zeta}]=\frac{v(r(s)-r(\zeta))}{s-\zeta}$ for simplicity:
$$
e(s\cdot[W_{\zeta}],1)\stackrel{?}{=}e(\zeta[W_{\zeta}]+v\cdot r(s)-v\bar{r},1)\\
e((s-\zeta)\cdot\frac{v(r(s)-r(\zeta))}{s-\zeta},1)\stackrel{?}{=}e(v(r(s)-r(\zeta)),1)\\
$$
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
$$
e((s-\zeta)[W_{\zeta}],1)\stackrel{?}{=}e([t_{lo}]+\zeta^{n+2}[t_{mid}]+\zeta^{2n+4}[t_{hi}]-\bar{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)\\
$$
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. $\bar{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))$
```python
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
```
```python
#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
```
```python
#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
```
```python
# 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`
Sign in with Wallet
Connect another wallet