# 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