In this section, we will review the commitment phase of the protocol. This phase contains two parts; AHP commitment and PFR commitment. We also provide an example to clarify the method.
Let If be a functional set that contains triple matrices if=(A,B,C)∈(Fn×n)3 so that for all input vector X, there exists a unique vector Y and a witness (intermediate) W such that AzoBz=Cz where z=(1,X,W,Y).
Note that a triple of matrices (A,B,C)∈(Fn×n)3 is a functional triple if and only if A and B are t−strictly lower triangular matrices (t−SLT) and C is t-diagonal matrix (t−Diag). Here, t=∣X∣+1 .
Note that the Prover obtains t−SLT matrices A, B and t−Diag matrix C for the arithmetic circuit based on the following construction:
1- Initialize three zero square matrices A,B,C over F of order ng+ni+1 where ng is the number of gates and ni is the number of inputs. Here, rows and columns of matrices are indexed on {0,1,...,ng+ni}.
Here, the gate i is corresponding to tuple (li,ri,si) where li and ri are left and right input indices in z, respectively where z is indexed on {0,1,..,ng+ni} and si is gate selector, addition, minus, multiplication or division. Note that if left input is a value v, then li=0 or right input is a value v, then ri=0.
2- For i=0..,ng−1:a) Set C1+ni+i,1+ni+i=1b) If si is addition
- A1+ni+i,0=1
- B1+ni+i,li={left inputli=01otherwise
- B1+ni+i,ri={right inputri=01otherwise
c) If si is minus
- A1+ni+i,0=1
- B1+ni+i,li={addition inverse of left inputli=01otherwise
- B1+ni+i,ri={addition inverse of right inputri=01otherwised) If si is multiplication
- A1+ni+i,li={left inputli=01otherwise
- B1+ni+i,ri={right inputri=01otherwise
e) If si is division
- A1+ni+i,li={multiplicative inverse of left inputli=01otherwise
- B1+ni+i,ri={multiplicative inverse of right inputri=01otherwise
3- Outputs matrices A,B and C.
Note 1: Here, input vector contains 32 registers. Therefore, ni=32 and X=(x1,x2,...,x32) where xi corresponds to ith register, Ri.
Note 2: For example, if k+1th gate is "add R1 , R1, 5", that means R1(k+1)=5+R1(k) then since z=(1,x1,x2,..x32,w1,..,wng−32,y1,..,y32), "For" loop in i=k, obtains C1+32+k,1+32+k=1 , A1+32+k,0=1, B1+32+k,lk=0=5 and B1+32+k,rk=1=1.
Commit(ck,if=(A,B,C)∈If,r∈R): This function outputs
as following:
1 - The Prover selects randomness r=(r1,...,rsAHP(0)) of randomness space R .
2- The Prover calculates OPFR=Enc(if=(A,B,C)) as encoded index as following:
The Prover encodes each matrix A,B and C by three polynomials. The matrix M, M∈{A,B,C}, is encoded by polynomials rowM(x), colM(x) and valM(x) so that rowM(γi)=ωri, colM(γi)=ωci and valM(γi)=vi for i∈{0,1,2,..,m−1} where m=2n2−n−2t2−t is maximum of the number of nonzero entries in the matrix M, The value of n=ng+ni+1 is the order of the matrix. Also, γ is a generator of multiplicative subgroup K of F of order m (K=<γ> and ∣K∣=m) and ω is a generator of multiplicative subgroup H of F of order n (H=<ω> and ∣H∣=n). Also ri,ci∈{0,1,...,n−1} and vi∈F are row number, column number and value of ith nonzero entry, respectively. Then, lets OPFR=(rowA0,....,rowAm−1,colA0,...,colAm−1,valA0,...,valAm−1,rowB0,....,rowBm−1,colB0,...,colBm−1,valB0,...,valBm−1,rowC0,....,rowCm−1,colC0,...,colCm−1,valC0,...,valCm−1)
where rowMi, colMiand valMi are coefficient of xi of polynomials rowM(x), colM(x)and valM(x) , respectively. The vector OPFR is called as encoded index.
3- The Prover calculates ComT=PC.Commit(ck,T,dAHP(N,0,i)=m,rT) for each polynomial T(x). Note that T∈{RowM,ColM,valM∣M∈{A,B,C}}.
For example, if the polynomial commitment scheme KZG is used, then ck=pk.
ComT=∏i∈{0,1,...,degT}(gτi)ai=∏i∈{0,1,..,degT}ck(i)ai where ai is coefficient of xi in polynomial T(x).
Size of Commitment: ∣ComPFR∣=9.
4- The Prover sends ComPFR to the Verifier.
Commit(ck,if=(A,B,C)∈If,r∈R): This function outputs ComAHP=(ComAHP0,ComAHP1,ComAHP2,ComAHP3,ComAHP4,ComAHP5,ComAHP6,ComAHP7,ComAHP8)
as following:
1 - The Prover selects randomness r=(r1,...,rsAHP(0)) of random space R.
2- The Prover calculates OAHP=Enc(if=(A,B,C)) as encoded index as following:
For M∈{A,B,C}, the polynomial rowM′:K→H with rowM′(k=γi)=ωri for 1≤i≤∣∣M∣∣=m , ∣∣M∣∣ is the number of nonzero entries in M, and ri∈{0,1,...,n−1} is row number of ith nonzero entry, γ is a generator of multiplicative subgroup K of F of order m (K=<γ> and ∣K∣=m) and ω is a generator of multiplicative subgroup H of F of order n (H=<ω> and ∣H∣=n). The value of n is the order of the matrix and otherwise rowM′(k) returns an arbitrary element in H.
The polynomial colM′:K→H with colM′(k=γi)=ωci for 1≤i≤∣∣M∣∣ and ci∈{0,1,...,n−1} is column number of ith nonzero entry and otherwise colM′(k) returns an arbitrary element in H.
And , the polynomial valM′:K→H with valM′(k=γi)=uH(rowM′(k),rowM′(k))uH(colM′(k),colM′(k))vi for 1≤i≤∣∣M∣∣ where vi is value of ith nonzero entry and otherwise valM′(k) returns zero where for each x∈H, uH(x,x)=∣H∣x∣H∣−1.
Now, rowM′^, colM′^ and valM′^ are extensions of rowM′, colM′ and valM′ so that are agree on K.OAHP=(row′^A0,....,row′^Am−1,col′^A0,...,col′^Am−1,val′^A0,...,val′^Am−1,row′^B0,....,row′^Bm−1,col′^B0,...,col′^Bm−1,val′^B0,...,val′^Bm−1,row′^C0,....,row′^Cm−1,col′^C0,...,col′^Cm−1,val′^C0,...,val′^Cm−1)
where row′^Mi, col′^Miand val′^Mi are coefficient of xi of polynomials row′^M(x), col′^M(x)and val′^M(x) , respectively. The vector OAHP is called as encoded index.
3- The Prover calculates commitment for ith polynomial T(x) of encoded index asComT=PC.Commit(ck,T,dAHP(N,0,i)=m,rT). Note that T∈{Row′^M,Col′^M,val′^M∣M∈{A,B,C}}.
For example, if the polynomial commitment scheme KZG is used, then
ComT=∏i∈{0,1,...,degT}(gτi)ai=∏i∈{0,1,..,degT}ck(i)ai where ai is coefficient of xi in polynomial T(x).
Note that the inverse of number a in this field is ap−2(modp) , so 7−1≡26(mod181).
At we see, the matrices A and B are 2−SLT and matrix C is 2−Diag. Also AzoBz=Cz.
We consider z=(1,x,w1,w2,y) where w1=5x, w2=w1+11 and y=26w2. For example, with input x=4, z=(1,4,20,31,82).
We consider multiplicative subgroup H of order n=ng+ni+1=5 with generator
ω=236≡59(mod181). Note that if g is a generator of field F of order p, then, gnp−1is a generator of a multiplicative subgroup of it of order n. Therefore, H={1,ω,ω2,ω3,ω4}={1,59,42,125,135}.
Also, consider multiplicative subgroup K of order m=2n2−n−2t2−t=9 where t=ni+1=2 with generator γ=gmp−1=220≡43(mod181). Therefore,K={1,γ,γ2,...,γ8}={1,43,39,48,73,62,132,65,80}.
1- The Prover Selects r=(r1,...,rsAHP(0)) of random space R.
2- The Prover calculates O=Enc(if=(A,B,C)) as encoded index as following:.
First, calculates the polynomial rowA(x). Since matrix A has three non-zero entries that the first of them is in the second row, so c0=2 and rowA(γ0)=ω2 , note that rows numbered of zero, the second is in the third row, so c1=3 and rowA(γ1)=ω3 and the third is in the fourth row, so c2=4 and rowA(γ2)=ω4. Note that to construct all three polynomials, we read the entries in the matrix in row or column order. Here they are read in row order.
According to the values defined for γ and ω, we have rowA(1)=42, rowA(43)=125 and rowA(39)=135. Therefore based on Lagrange polynomials, have rowA(x)=∑i=13yiLi(x), sorowA(x)=42L1(x)+125L2(x)+135L3(x), where L1(x)=(1−43)(1−39)(x−43)(x−39)=(−42)(−38)(x−43)(x−39). Now, since −42≡139(mod181), −38≡143(mod181), −43≡138(mod181)and −39≡142(mod181), therefore L1(x)=(139)(143)(x+138)(x+142)and since (139)(143)≡148(mod181)and 148−1≡170(mod181), have L1(x)=170(x+138)(x+142)=170x2+178x+15. We get in a similar way that L2(x)=167x2+17x+178 and L3(x)=25x2+167x+170. Therefore rowA(x)=77x2+109x+37.
Now, calculates colA(x). Since matrix A has three non-zero entries that the first of them is in the first column, so r0=1 and colA(γ0)=ω1 , note that columns numbered of zero, the second is in the zero column, so r1=0 and colA(γ1)=ω0 and the third is in the third column, so r2=3 and colA(γ2)=ω3. Therefore colA(1)=59, colA(43)=1 and colA(39)=125. So colA(x)=59L1(x)+L2(x)+125L3(x)=109x2+81x+50.
Now, calculates valA(x). Since matrix A has three non-zero entries such that the value of all of them is one, therefore v0=v1=v2=1. So, valA(x)=L1(x)+L2(x)+L3(x)=1.
Therefore, the matrix A is encoded by rowA(x)=77x2+109x+37, colA(x)=109x2+81x+50 and valA(x)=1.
Now, encodes the matrix B. First, calculates the polynomial rowB(x). Since matrix B has four non-zero entries such that the first of them is in the second row, so c0=2 and rowB(γ0)=ω2 . The second and the third are in the third row, so c1=c2=3 and rowB(γ1)=rowB(γ2)=ω3 and the fourth is in the fourth row, so c3=4 and rowB(γ3)=ω4. Therefore, rowB(1)=42, rowB(43)=125, rowB(39)=125 and rowB(48)=135. So rowB(x)=42L1(x)+125L2(x)+125L3(x)+135L4(x) where L1(x)=(1−43)(1−39)(1−48)(x−43)(x−39)(x−48)=(139)(143)(134)(x+138)(x+142)(x+133)=103(x+138)(x+142)(x+133). Since 103−1≡58(mod181), so L1(x)=58(x+138)(x+142)(x+133)=58x3+62x2+116x+127. We get in a similar way that L2(x)=39x3+7x2+19x+116, L3(x)=138x3+155x2+7x+62 and L4(x)=127x3+138x2+39x+58. Therefore rowB(x)=76x3+35x2+174x+119.
Now, calculates colB(x). Since matrix B has four non-zero entries that the first, second and fourth of them are in zero column, so r0=r1<