The commitment phase contains two parts; AHP commitment and PFR commitment. After reviewing the algorithm, 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 .
The Prover obtains t−SLT matrices A, B and t−Diag matrix C for the arithmetic circuit that is a directed acyclic graph of gates and wire inputs where wires carry values from F and each gate adds or multiplies. This work is done 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 or multiplication. 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=01otherwiseb) If si is multiplication
- A1+ni+i,li={left inputli=01otherwise
- B1+ni+i,ri={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−ne,y1,..,yne), where ne is the number of registers that change in all program, "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.
2-1- PFR Commitment
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=2ng 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
ComT=∑i=0degTaigτi=∑i=0degTaick(i) where ai is coefficient of xi in polynomial T(x).
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) where ck′(i)=ck(i)ri with random r. 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=0degTaick′(i) where ai is coefficient of xi in polynomial T(x).