2- Commitment Phase

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\textit{I}_f be a functional set that contains triple matrices if=(A,B,C)(Fn×n)3i_f=(A,B,C)\in (\mathbb{F}^{n\times n})^3 so that for all input vector X X, there exists a unique vector Y Y and a witness (intermediate) WW such that AzoBz=CzAz\hspace{1mm} o\hspace{1mm} Bz=Cz where z=(1,X,W,Y)z=(1,X,W,Y). Note that a triple of matrices (A,B,C)(Fn×n)3(A,B,C)\in (\mathbb{F}^{n\times n})^3 is a functional triple if and only if AA and BB are tt-strictly lower triangular matrices (tSLT)(t-SLT) and CC is tt-diagonal matrix (tDiag)(t-Diag). Here, t=X+1t=|X|+1 . The Prover obtains tSLTt-SLT matrices AA, BB and tDiagt-Diag matrix CC for the arithmetic circuit that is a directed acyclic graph of gates and wire inputs where wires carry values from F\mathbb{F} and each gate adds or multiplies. This work is done based on the following construction:

1- Initialize three zero square matrices A,B,CA, B, C over F\mathbb{F} of order ng+ni+1n_g +n_i + 1 where ngn_g is the number of gates and nin_i is the number of inputs. Here, rows and columns of matrices are indexed on {0,1,...,ng+ni}\{0,1,...,n_g+n_i\}. Here, the gate ii is corresponding to tuple (li,ri,si)(l_i, r_i, s_i) where lil_i and rir_i are left and right input indices in zz, respectively where zz is indexed on {0,1,..,ng+ni}\{0,1,..,n_g+n_i\} and sis_i is gate selector, addition or multiplication. Note that if left input is a value vv, then li=0l_i=0 or right input is a value vv, then ri=0r_i=0.

2- For i=0..,ng1: i=0.., n_g-1: a)a) Set C1+ni+i,1+ni+i=1C_{1+n_i+i, 1+n_i+i}=1 b)b) If si s_i is addition - A1+ni+i,0=1A_{1+n_i+i,0}=1 - B1+ni+i,li={left inputli=01otherwiseB_{1+n_i+i,l_i}=\begin{cases}\text{left input}\hspace{1cm}l_i=0\\1\hspace{2.2cm}\text{otherwise}\end{cases} - B1+ni+i,ri={right inputri=01otherwiseB_{1+n_i+i,r_i}=\begin{cases}\text{right input}\hspace{1cm}r_i=0\\1\hspace{2.2cm}\text{otherwise}\end{cases} b)b) If sis_i is multiplication - A1+ni+i,li={left inputli=01otherwiseA_{1+n_i+i,l_i}=\begin{cases}\text{left input}\hspace{1cm}l_i=0\\1\hspace{2.2cm}\text{otherwise}\end{cases} - B1+ni+i,ri={right inputri=01otherwiseB_{1+n_i+i,r_i}=\begin{cases}\text{right input}\hspace{1cm}r_i=0\\1\hspace{2.2cm}\text{otherwise}\end{cases}

3- Outputs matrices A,BA, B and CC.

Note 1: Here, input vector contains 32 registers. Therefore, ni=32n_i=32 and X=(x1,x2,...,x32)X=(x_1,x_2,...,x_{32}) where xix_i corresponds to ithi^{th} register, RiR_i.

Note 2: For example, if k+1thk+1^{th} gate is "add R1R_1 , R1R_1, 5", that means R1(k+1)=5+R1(k)R_1^{(k+1)}=5+R_1^{(k)} then since z=(1,x1,x2,..x32,w1,..,wngne,y1,..,yne)z=(1,x_1,x_2,..x_{32},w_1,..,w_{n_g-n_e},y_1,..,y_{n_e}), where nen_e is the number of registers that change in all program, "For" loop in i=ki=k, obtains C1+32+k,1+32+k=1C_{1+32+k,1+32+k}=1 , A1+32+k,0=1A_{1+32+k,0}=1, B1+32+k,lk=0=5B_{1+32+k,l_{k}=0}=5 and B1+32+k,rk=1=1B_{1+32+k,r_k=1}=1.

2-1- PFR Commitment

Commit(ck,if=(A,B,C)If,rR)Commit(ck,i_f=(A,B,C)\in \textit{I}_f,r\in R): This function outputs

ComPFR=(ComrowA,ComcolA,ComvalA,ComrowB,ComcolB,ComvalB,ComrowC,ComcolC,ComvalC)Com_{PFR}=(Com_{row_A},Com_{col_A},Com_{val_A},Com_{row_B},Com_{col_B},Com_{val_B},Com_{row_C},Com_{col_C},Com_{val_C})

as following: 1 - The Prover selects randomness r=(r1,...,rsAHP(0))r=(r_1,...,r_{s_{AHP}(0)}) of randomness space RR . 2- The Prover calculates OPFR=Enc(if=(A,B,C))\overrightarrow{O}_{PFR}=Enc(i_f=(A,B,C)) as encoded index as following:

The Prover encodes each matrix A,BA, B and CC by three polynomials. The matrix MM, M{A,B,C}M\in\{A, B, C\}, is encoded by polynomials rowM(x)row_{M}(x), colM(x)col_M(x) and valM(x)val_M(x) so that rowM(γi)=ωrirow_M(\gamma^i)=\omega^{r_i}, colM(γi)=ωcicol_M(\gamma^i)=\omega^{c_i} and valM(γi)=vival_M(\gamma^i)=v_i for i{0,1,2,..,m1}i\in\{0,1,2,..,m-1\} where m=2ngm=2n_g is maximum of the number of nonzero entries in the matrix MM, The value of n=ng+ni+1n=n_g+n_i+1 is the order of the matrix. Also, γ\gamma is a generator of multiplicative subgroup K\mathbb{K} of F\mathbb{F} of order mm (K=<γ>\mathbb{K}=<\gamma> and K=m|\mathbb{K}|=m) and ω\omega is a generator of multiplicative subgroup H\mathbb{H} of F\mathbb{F} of order nn (H=<ω>\mathbb{H}=<\omega> and H=n|\mathbb{H}|=n). Also ri,ci{0,1,...,n1}r_i,c_i\in \{0,1,...,n-1\} and viFv_i\in \mathbb{F} are row number, column number and value of ithi^{th} nonzero entry, respectively. Then, lets OPFR=(rowA0,....,rowAm1,colA0,...,colAm1,valA0,...,valAm1,rowB0,....,rowBm1,colB0,...,colBm1,O_{PFR}=(row_{A_0},....,row_{A_{m-1}},col_{A_0},...,col_{A_{m-1}},val_{A_0},...,val_{A_{m-1}},row_{B_0},....,row_{B_{m-1}},col_{B_0},...,col_{B_{m-1}}, valB0,...,valBm1,rowC0,....,rowCm1,colC0,...,colCm1,valC0,...,valCm1)val_{B_0},...,val_{B_{m-1}},row_{C_0},....,row_{C_{m-1}},col_{C_0},...,col_{C_{m-1}},val_{C_0},...,val_{C_{m-1}})

where rowMirow_{M_i}, colMicol_{M_i}and valMival_{M_i} are coefficient of xix^i of polynomials rowM(x)row_{M}(x), colM(x)col_{M}(x)and valM(x)val_{M}(x) , respectively. The vector OPFRO_{PFR} is called as encoded index.

3- The Prover calculates ComT=PC.Commit(ck,T,dAHP(N,0,i)=m,rT)Com_{T}=PC.Commit(ck,T,d_{AHP}(N,0,i)=m,r_{T}) for each polynomial T(x)T(x). Note that T{RowM,ColM,valMM{A,B,C}}T\in\{Row_M,Col_M,val_M\hspace{2mm}|\hspace{2mm}M\in\{A,B,C\}\}.

For example, if the polynomial commitment scheme KZGKZG is used, then ComT=i=0degTaigτi=i=0degTaick(i)Com_{T}=\sum_{i=0}^{deg_T}a_ig\tau^i=\sum_{i=0}^{deg_T}a_ick(i) where aia_i is coefficient of xix^i in polynomial T(x)T(x).

Size of Commitment: ComPFR=9|Com_{PFR}|=9.

4- The Prover sends ComPFRCom_{PFR} to the Verifier.

CommitmentID= Lower4Bytes(SHA256(Manufacturer_Name, Device_Type, Device_Hardware_Version, Firmware_Version, Lines Vec<u64>))

2-2- AHP Commitment

Commit(ck,if=(A,B,C)If,rR)Commit(ck',i_f=(A,B,C)\in \textit{I}_f,r\in R): This function outputs ComAHP=(ComAHP0,ComAHP1,ComAHP2,ComAHP3,ComAHP4,ComAHP5,ComAHP6,ComAHP7,ComAHP8)Com_{AHP}=(Com_{AHP}^{0},Com_{AHP}^1,Com_{AHP}^2,Com_{AHP}^3,Com_{AHP}^4,Com_{AHP}^5,Com_{AHP}^6,Com_{AHP}^7,Com_{AHP}^8)

as following: 1 - The Prover selects randomness r=(r1,...,rsAHP(0))r=(r_1,...,r_{s_{AHP}(0)}) of random space RR. 2- The Prover calculates OAHP=Enc(if=(A,B,C))\overrightarrow{O}_{AHP}=Enc(i_f=(A,B,C)) as encoded index as following:

For M{A,B,C}M\in \{A,B,C\}, the polynomial rowM:KHrow'_M:\mathbb{K}\to\mathbb{H} with rowM(k=γi)=ωrirow'_M(k=\gamma^i)=\omega^{r_i} for 1iM=m1\leq i\leq ||M||=m , M||M|| is the number of nonzero entries in MM, and ri{0,1,...,n1}r_i\in \{0,1,...,n-1\} is row number of ithi^{th} nonzero entry, γ\gamma is a generator of multiplicative subgroup K\mathbb{K} of F\mathbb{F} of order mm (K=<γ>\mathbb{K}=<\gamma> and K=m|\mathbb{K}|=m) and ω\omega is a generator of multiplicative subgroup H\mathbb{H} of F\mathbb{F} of order nn (H=<ω>\mathbb{H}=<\omega> and H=n|\mathbb{H}|=n). The value of nn is the order of the matrix and otherwise rowM(k)row'_M(k) returns an arbitrary element in H\mathbb{H}.

The polynomial colM:KHcol'_M:\mathbb{K}\to\mathbb{H} with colM(k=γi)=ωcicol'_M(k=\gamma^i)=\omega^{c_i} for 1iM1\leq i\leq ||M|| and ci{0,1,...,n1}c_i\in \{0,1,...,n-1\} is column number of ithi^{th} nonzero entry and otherwise colM(k)col'_M(k) returns an arbitrary element in H\mathbb{H}. And , the polynomial valM:KHval'_M:\mathbb{K}\to\mathbb{H} with valM(k=γi)=viuH(rowM(k),rowM(k))uH(colM(k),colM(k))val'_M(k=\gamma^i)=\frac{v_i}{u_{\mathbb{H}}(row'_M(k),row'_M(k))u_{\mathbb{H}}(col'_M(k),col'_M(k))} for 1iM1\leq i\leq ||M|| where viv_i is value of ithi^{th} nonzero entry and otherwise valM(k)val'_M(k) returns zero where for each xHx \in \mathbb{H}, uH(x,x)=HxH1u_{\mathbb{H}}(x,x)=|\mathbb{H}|x^{|\mathbb{H}|-1}. Now, rowM^\hat{row'_M}, colM^\hat{col'_M} and valM^\hat{val'_M} are extensions of rowMrow'_M, colMcol'_M and valMval'_M so that are agree on K\mathbb{K}.OAHP=(row^A0,....,row^Am1,col^A0,...,col^Am1,val^A0,...,val^Am1,row^B0,....,row^Bm1,col^B0,...,col^Bm1,\overrightarrow{O}_{AHP}=(\hat{row'}_{A_0},....,\hat{row'}_{A_{m-1}},\hat{col'}_{A_0},...,\hat{col'}_{A_{m-1}},\hat{val'}_{A_0},...,\hat{val'}_{A_{m-1}},\hat{row'}_{B_0},....,\hat{row'}_{B_{m-1}},\hat{col'}_{B_0},...,\hat{col'}_{B_{m-1}},val^B0,...,val^Bm1,row^C0,....,row^Cm1,col^C0,...,col^Cm1,val^C0,...,val^Cm1)\hat{val'}_{B_0},...,\hat{val'}_{B_{m-1}},\hat{row'}_{C_0},....,\hat{row'}_{C_{m-1}},\hat{col'}_{C_0},...,\hat{col'}_{C_{m-1}},\hat{val'}_{C_0},...,\hat{val'}_{C_{m-1}})

where row^Mi\hat{row'}_{M_i}, col^Mi\hat{col'}_{M_i}and val^Mi\hat{val'}_{M_i} are coefficient of xix^i of polynomials row^M(x)\hat{row'}_{M}(x), col^M(x)\hat{col'}_{M}(x)and val^M(x)\hat{val'}_{M}(x) , respectively. The vector OAHP\overrightarrow{O}_{AHP} is called as encoded index.

3- The Prover calculates commitment for ithi^{th} polynomial T(x)T(x) of encoded index asComT=PC.Commit(ck,T,dAHP(N,0,i)=m,rT)Com_{T}=PC.Commit(ck',T,d_{AHP}(N,0,i)=m,r_{T}) where ck(i)=ck(i)rick'(i)=ck(i )\hspace{1mm}r^i with random rr. Note that T{Row^M,Col^M,val^MM{A,B,C}}T\in\{\hat{Row'}_M,\hat{Col'}_M,\hat{val'}_M\hspace{2mm}|\hspace{2mm}M\in\{A,B,C\}\}.

For example, if the polynomial commitment scheme KZGKZG is used, then ComT=i=0degTaick(i)Com_{T}=\sum_{i=0}^{deg_T}a_ick'(i) where aia_i is coefficient of xix^i in polynomial T(x)T(x).

4- The Prover sends ComAHP0=i=0degrow^A(x)row^Aick(i)Com_{AHP}^0=\sum_{i=0}^{deg_{\hat{row'}_A(x)}}\hat{row'}_{A_i}\hspace{1.1mm}ck'(i), ComAHP1=i=0degcol^A(x)col^Aick(i)Com_{AHP}^1=\sum_{i=0}^{deg_{\hat{col'}_A(x)}}\hat{col'}_{A_i}\hspace{1.1mm}ck'(i), ComAHP2=i=0degval^A(x)val^Aick(i)Com_{AHP}^2=\sum_{i=0}^{deg_{\hat{val'}_A(x)}}\hat{val'}_{A_i}\hspace{1.1mm}ck'(i), ComAHP3=i=0degrow^B(x)row^Bick(i)Com_{AHP}^3=\sum_{i=0}^{deg_{\hat{row'}_B(x)}}\hat{row'}_{B_i}\hspace{1.1mm}ck'(i), ComAHP4=i=0degcol^B(x)col^Bick(i)Com_{AHP}^4=\sum_{i=0}^{deg_{\hat{col'}_B(x)}}\hat{col'}_{B_i}\hspace{1.1mm}ck'(i), ComAHP5=i=0degval^B(x)val^Bick(i)Com_{AHP}^5=\sum_{i=0}^{deg_{\hat{val'}_B(x)}}\hat{val'}_{B_i}\hspace{1.1mm}ck'(i), ComAHP6=i=0degrow^C(x)row^Cick(i)Com_{AHP}^6=\sum_{i=0}^{deg_{\hat{row'}_C(x)}}\hat{row'}_{C_i}\hspace{1.1mm}ck'(i), ComAHP7=i=0degcol^C(x)col^Cick(i)Com_{AHP}^7=\sum_{i=0}^{deg_{\hat{col'}_C(x)}}\hat{col'}_{C_i}\hspace{1.1mm}ck'(i), ComAHP8=i=0degval^C(x)val^Cick(i)Com_{AHP}^8=\sum_{i=0}^{deg_{\hat{val'}_C(x)}}\hat{val'}_{C_i}\hspace{1.1mm}ck'(i).

2-3- PFR and AHP Commitment.json File Format

{
    "CommitmentID":  64-bit,
    "Class": 32-bit Integer,
    "IoT_Manufacturer_Name": String,
    "IoT_Device_Name": String,
    "Device_Hardware_Version": float,
    "Firmware_Version": float,
    "Lines": = 64-bit Array,
    "vk'":=
    
    // PFR Commitment   
    "ComRowA": 64-bit Integer,
    "ComColA": 64-bit Integer,
    "ComValA": 64-bit Integer,
    "ComRowB": 64-bit Integer,
    "ComColB": 64-bit Integer,
    "ComValB": 64-bit Integer,
    "ComRowC": 64-bit Integer,
    "ComColC": 64-bit Integer,
    "ComValC": 64-bit Integer,
    "RowA": 64-bit Integer,
    "ColA": 64-bit Integer,
    "ValA": 64-bit Integer,
    "RowB": 64-bit Integer,
    "ColB": 64-bit Integer,
    "ValB": 64-bit Integer,
    "RowC": 64-bit Integer,
    "ColC": 64-bit Integer,
    "ValC": 64-bit Integer,

    // AHP Commitment
    "ComRow'A": 64-bit Integer,
    "ComCol'A": 64-bit Integer,
    "ComVal'A": 64-bit Integer,
    "ComRow'B": 64-bit Integer,
    "ComCol'B": 64-bit Integer,
    "ComVal'B": 64-bit Integer,
    "ComRow'C": 64-bit Integer,
    "ComCol'C": 64-bit Integer,
    "ComVal'C": 64-bit Integer,
    "Row'A": 64-bit Integer,
    "Col'A": 64-bit Integer,
    "Val'A": 64-bit Integer,
    "Row'B": 64-bit Integer,
    "Col'B": 64-bit Integer,
    "Val'B": 64-bit Integer,
    "Row'C": 64-bit Integer,
    "Col'C": 64-bit Integer,
    "Val'C": 64-bit Integer,
    
    "Curve": String,
    "PolynomialCommitment": String
}

Param.json File Format

Last updated