# 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`
Last changed by  
 
Chao
742

Read more

Barrett Reduction

Barrett reduction allows us to quickly calculate the quotient $q$ and reminder $r$ of $a \pmod n$, i.e. $a = q\cdot n + r, 0\leq r<n$. GLV One of the use case is in GLV decomposition. For simplicity, we consider all the integers below are less than $2^{256}$. We want to decompose $k=k_1+k_2\cdot\lambda$ with both $k_1, k_2$ are small. Here is the correspondence $$k\rightarrow a,k_1\rightarrow r, k_2\rightarrow q, \lambda\rightarrow n$$ When $\lambda$ is $128$ bit, we can use Barrett reduction to derive $k_1, k_2$ with $k_1<2^{128}, k_2<2^{128}$. In the glv paper, it considers more general case where $\lambda$ might not be $128$ bit and hence use lattice based algorithm to derive small $k_1, k_2$ (which might not less than $2^{128}$)

3/24/2023
Lookup argument for folding

Example Assume in lookup arguments, we have two columns $(A,S)$, and try to lookup $A_i\in S$. Firstly, we cannot directly fold two such instances, e.g. with random factor $r=1$: $$A_1=[1,1,2,3], S_1=[1,2,3,4,5]\ A_2=[1,1,1,2], S_2=[1,2,3,4,5]\ A_1+A_2=[2,2,3,5], S_1+S_2=[2,4,6,8,10]$$ Obviously $(A_1+A_2, S_1+S_2)$ will not work. And since the lookup is arbitrary, we probably will not have any explicit formula to make the folding of $(A,S)$ work. Attempt 1 Assume we want to calcualte a function $F: X\rightarrow Y$. Instead of writing circuit for $F$, we do lookup argument that $(x,F(x))\in S$. Here $S={(x,F(x))|x\in X}$.

3/20/2023
Montgomery modular multiplication

Original version Suppose $a,b\in \mathbb{Z}_N$, modular multiplication $[ab]$ requires first multiply them in the range $[0,N^2-2N+1]$, and then use Euclidean division theorem to get $ab=qN+r,q=\lfloor ab/N\rfloor$, such that $[ab]=r$. The division is quite expensive. Montgomery form is to choose a different divisor $R>N$ with $\gcd{(R, N)}=1$. For example, by choose $R=2^n$, the division is just shift by $n$ bits. Thus, we just want to make sure the numerator is divisible by $R$. Montgomery form of $a$ is defined as $\bar{a}=[aR]$, i.e. residual class of $aR$. We have: $$\gcd{(R,N)}=1\implies \exists R^{-1}:RR^{-1}\equiv 1\implies\exists N'<R:RR^{-1}=N'N+1$$ i.e. $N'$ is negative mod inverse of $N$ w.r.t $R$. And we have multiplication by $R$ is ring isomorphism. And: $$T=[aR][bR]\equiv abR\cdot R\equiv [abR]\cdot R$$ Notice $T<N\cdot N< R*N$. For any $0\leq T < RN$, define reduction form of $T$ as: $$t=redc(T):=TR^{-1}\pmod N$$ i.e. $\overline{ab}=redc(\bar{a}\bar{b})$. We use the following algorithm to do the reduction:

2/10/2023
MACI v1.0: top-up voice credits

Introduction In previous design, when an user signup, she will get an initial voice credit balance. This info is stored in corresponding stateLeaf. For multiple polls, an user can spend credits upto this initial balance. e.g. If an user has initial 100 credits. Then she can spend a total of 100 credits for each poll. If she wants to spend more than initial balance, she has to signup again. The purpose of top-up feature is to allow users to add more credits without signup again. Design One approach is to modify the voiceCreditBalance on the stateLeaf each time when user deposit new credits. This is the current approach we are going to take. Proposal Notice that an user cannot just arbitrarily send a topup command to add credits. Instead, we add an ERC20 contract to store voting credits. Then the user can use the topup function in poll.sol to deposit tokens into the contract address. In the current design, we don't allow users to withdraw their tokens. The reason is that withdraw feature can allow malicious one to bribe others offline to transfer their keys. Without withdraw function, the malicious cannot distinguish whether key transferred is valid or not. Since now the poll.sol contract address will hold all the funds deposit from users for the current pollID. At the end of poll, the coordinator (or anyone) can transfer funds in poll.sol into hardcoded address which is used for public goods.

1/19/2023
Read more from Chao
Published on HackMD