2- Commitment Phase

The commitment phase contains two parts; AHP commitment and PFR commitment. After reviewing the algorithm, we will provide an example to clarify each parts.

Let $\textit{M}_f$ be a functional set which contains triple matrices $m_f=(A,B,C)\in (\mathbb{F}^{n\times n})^3$ such that for each input vector $X$, there is a unique output vector $Y$ as well as a witness (intermediate) $W$ where $Az\hspace{1mm} o\hspace{1mm} Bz=Cz$ considering $z=(1,X,W,Y)$.

The triplet $(A,B,C)\in (\mathbb{F}^{n\times n})^3$ is a functional set if and only if $A$ and $B$ are $t-$ strictly lower triangular matrices $(t-SLT)$ and $C$ is $t-$ diagonal matrix $(t-Diag)$ [1]. 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. Wires carry values from $\mathbb{F}$ and gates are add or multiplication. This work is done based on the two steps of the following construction:

  • Initialize three zero square matrices $A, B, C$ over $\mathbb{F}$ of order $n=n_g +n_i + 1$ where $n_g$ is the number of gates and $n_i$ is the number of inputs. Rows and columns of matrices are indexed on { $0,1,...,n_g+n_i$ }. Also, Gate $i$ with two left L and right R inputs and a selector S. We show the Gate $i$ with a tuple $(l_i, r_i, s_i)$ where $l_i$ and $r_i$ are the left and right inputs' indexes in $z$, respectively. Note that $z$ is indexed on { $0,1,..,n_g+n_i$ }. Hence, $l_i$ and $r_i$ are between $0$ and $n_g+n_i$. Also, $s_i$ is either "Addition" or "Multiplication". Note, if the left input is a value $v$, then $l_i=0$ or if the right input is a value $v$, then $r_i=0$.

  • For $i=0.., n_g-1:$ $a)$ Set $C_{1+n_i+i, 1+n_i+i}=1$ $b)$ If $s_i$ is "Addition" - $A_{1+n_i+i,\hspace{1mm}0}=1$ - $B_{1+n_i+i,\hspace{1mm}l_i}=\begin{cases}\text{left input}\hspace{1cm}l_i=0\\1\hspace{2.2cm}\text{otherwise}\end{cases}$ - $B_{1+n_i+i,\hspace{1mm}r_i}=\begin{cases}\text{right input}\hspace{1cm}r_i=0\\1\hspace{2.2cm}\text{otherwise}\end{cases}$ $b)$ If $s_i$ is multiplication - $A_{1+n_i+i,\hspace{1mm}l_i}=\begin{cases}\text{left input}\hspace{1cm}l_i=0\\1\hspace{2.2cm}\text{otherwise}\end{cases}$ - $B_{1+n_i+i,\hspace{1mm}r_i}=\begin{cases}\text{right input}\hspace{1cm}r_i=0\\1\hspace{2.2cm}\text{otherwise}\end{cases}$

If our processing machine has 32 registers, then the size of the input vector $X$ will be 32. Therefore, $n_i=32$ and $X=(x_1,x_2,...,x_{32})$ where $x_i$ corresponds to $i^{th}$ register, $R_i$. Also, $z=(1,x_1,x_2,..x_{32},w_1,..,w_{n_g-n_r},y_1,..,y_{n_r})$ where $n_r$ is the number of registers that change during a program execution. For example, assume the first gate in a computation is the instruction "add $R_1$ , $R_1$, 5", which means $R_1^{(2)}=R_1^{(1)}+5$ . In the above "for" loop in step $i=0$, $s_0$="Addition", $l_0=1$, and $r_0=0$, hence $C_{1+32,\hspace{1mm}1+32}=1$ , $A_{1+32,\hspace{1mm}0}=1$, , and $B_{{1+32},\hspace{1mm}0}=5$.

2-1- PFR Commitment

PFR aims to prove the target program is a function with mentioned characteristics in $A, B, C$. PFR function will be edited later. $Commit(ck,m_f=(A,B,C)\in \textit{M}_f,s\in R)$: This function outputs $Com_{PFR}=(Com_{PFR}^0,Com_{PFR}^1,Com_{PFR}^2,Com_{PFR}^3,Com_{PFR}^4,Com_{PFR}^5,Com_{PFR}^6,Com_{PFR}^7,Com_{PFR}^8)$

as following:

1 - The Prover selects randomness $s=(s_1,...,s_{s_{AHP}(0)})$ of randomness space $R$.

2- The Prover calculates $\overrightarrow{O}_{PFR}=Enc(m_f=(A,B,C))$ as encoded index as following:

The Prover encodes each matrix A,BA, B and CC by three polynomials. The matrix NN, N∈{A,B,C}N\in\{A, B, C\}, is encoded by polynomials rowPFRN(x)row_{PFR_N}(x), colPFRN(x)col_{PFR_N}(x) and valPFRN(x)val_{PFR_N}(x) so that rowPFRN(γi)=ωrirow_{PFR_N}(\gamma^i)=\omega^{r_i}, colPFRN(γi)=ωcicol_{PFR_N}(\gamma^i)=\omega^{c_i} and valPFRN(γi)=vival_{PFR_N}(\gamma^i)=v_i for i∈{0,1,2,..,m−1}i\in\{0,1,2,..,m-1\} where m=2ngm=2n_g is maximum of the number of nonzero entries in the matrix NN, 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,...,n−1}r_i,c_i\in \{0,1,...,n-1\} and vi∈Fv_i\in \mathbb{F} are row number, column number and value of ithi^{th} nonzero entry, respectively. Then, lets OPFR=(rowPFRA0,....,rowPFRAm−1,colPFRA0,...,colPFRAm−1,valPFRA0,...,valPFRAm−1,O_{PFR}=(row_{PFR_{A_0}},....,row_{PFR_{A_{m-1}}},col_{PFR_{A_0}},...,col_{PFR_{A_{m-1}}},val_{PFR_{A_0}},...,val_{PFR_{A_{m-1}}}, rowPFRB0,...,rowPFRBm−1,colPFRB0,...,colPFRBm−1,valPFRB0,....,valPFRCm−1,row_{PFR_{B_0}},...,row_{PFR_{B_{m-1}}},col_{PFR_{B_0}},...,col_{PFR_{B_{m-1}}},val_{PFR_{B_0}},....,val_{PFR_{C_{m-1}}}, rowPFRC0,...,rowPFRCm−1,colPFRC0,...colPFRCm−1,valPFRC0,...,valPFRCm−1)row_{PFR_{C_0}},...,row_{PFR_{C_{m-1}}},col_{PFR_{C_0}},...col_{PFR_{C_{m-1}}},val_{PFR_{C_0}},...,val_{PFR_{C_{m-1}}})

where rowPFRNirow_{PFR_{N_i}}, colPFRNicol_{PFR_{N_i}} and valPFRNival_{PFR_{N_i}} are coefficient of xix^i of polynomials rowPFRN(x)row_{PFR_N}(x), colPFRN(x)col_{PFR_N}(x) and valPFRN(x)val_{PFR_N}(x) , respectively. The vector OPFRO_{PFR} is called as encoded index.

3- The Prover calculates ComPFRT=PC.Commit(ck,T,dAHP(N,0,i)=m,rT)Com_{PFR_T}=PC.Commit(ck,T,d_{AHP}(N,0,i)=m,r_{T}) for each polynomial T(x)T(x). Note that T∈T\in { rowPFRN,colPFRN,valPFRN∣N∈row_{PFR_N},col_{PFR_N},val_{PFR_N}\hspace{2mm}|\hspace{2mm}N\in { A,B,CA,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

As mentioned before AHP phase aims, without revealing any information about function ff, to prove that y=f(x)y=f(x) for public xx and yy. Now, we create a commitment for Algebraic Holographic Proof (AHP), AHPComAHP\hspace{1mm}Com , in this section.

Commit(ck′,mf=(A,B,C)∈Mf,s∈R)Commit(ck',m_f=(A,B,C)\in \textit{M}_f,s\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) , here ck′(i)=ck(i)r′ick'(i)=ck(i )\hspace{1mm}r'^i with random r′r'.

1 - The Prover selects random s=(s1,...ssAHP(0))s=(s_1,...s_{s_{AHP}(0)}) from random space RR. Note that sAHP(0)=9s_{AHP}(0)=9 as explained in the setup phase. 2- The Prover calculates O→AHP=Enc(mf=(A,B,C))\overrightarrow{O}_{AHP}=Enc(m_f=(A,B,C)) as encoded index as following:

  • Considering γ\gamma as a generator of multiplicative subgroup K\mathbb{K} of F\mathbb{F} of order mm (i.e., K=<γ>\mathbb{K}=<\gamma> and ∣K∣=m|\mathbb{K}|=m), ω\omega as a generator of multiplicative subgroup H\mathbb{H} of F\mathbb{F} of order nn (i.e., H=<ω>\mathbb{H}=<\omega> and ∣H∣=n|\mathbb{H}|=n), for each matrix N∈{A,B,C}N\in \{A,B,C\}, we generate 3 polynomials rowAHPN(x)row_{AHP_N}(x), colAHPN(x)col_{AHP_N}(x), and valAHPN(x)val_{AHP_N}(x) as described in the following steps:

  • The polynomial rowAHPN:K→Hrow_{AHP_N}:\mathbb{K}\to\mathbb{H} is constructed by rowAHPN(k=γi)=ωrirow_{AHP_N}(k=\gamma^i)=\omega^{r_i} for 0≤i≤∣∣N∣∣−10\leq i\leq ||N||-1 where ∣∣N∣∣||N|| is the number of nonzero entries in NN, and ri∈{0,1,...,n−1}r_i\in \{0,1,...,n-1\} is the row number of ithi^{th} nonzero entry and otherwise, rowAHPN(k)row_{AHP_N}(k) is an arbitrary element in H\mathbb{H}. Note that ii starts from zero. This step generate 3 polynomials; rowAHPA(x)row_{AHP_A}(x), rowAHPB(x)row_{AHP_B}(x), rowAHPC(x)row_{AHP_C}(x).

  • The polynomial colAHPN:K→Hcol_{AHP_N}:\mathbb{K}\to\mathbb{H} is constructed by colAHPN(k=γi)=ωcicol_{AHP_N}(k=\gamma^i)=\omega^{c_i} for 0≤i≤∣∣N∣∣−10\leq i\leq ||N||-1 and ci∈{0,1,...,n−1}c_i\in \{0,1,...,n-1\} is column number of ithi^{th} nonzero entry and otherwise colAHPN(k)col_{AHP_N}(k) returns an arbitrary element in H\mathbb{H}. This step generate 3 polynomials; colAHPA(x)col_{AHP_A}(x), colAHPB(x)col_{AHP_B}(x), colAHPC(x)col_{AHP_C}(x).

  • The polynomial valAHPN:K→Hval_{AHP_N}:\mathbb{K}\to\mathbb{H} is constructed by valAHPN(k=γi)=viuH(rowAHPN(k),rowAHPN(k))uH(colAHPN(k),colAHPN(k))val_{AHP_N}(k=\gamma^i)=\frac{v_i}{u_{\mathbb{H}}(row_{AHP_N}(k),row_{AHP_N}(k))u_{\mathbb{H}}(col_{AHP_N}(k),col_{AHP_N}(k))} for 0≤i≤∣∣N∣∣−10\leq i\leq ||N||-1 where viv_i is value of ithi^{th} nonzero entry and otherwise valAHPN(k)val_{AHP_N}(k) returns zero where for each x∈Hx \in \mathbb{H}, uH(x,x)=∣H∣x∣H∣−1u_{\mathbb{H}}(x,x)=|\mathbb{H}|x^{|\mathbb{H}|-1}.

Now, we define rowAHPN^\hat{row_{AHP_N}}, colAHPN^\hat{col_{AHP_N}} and valAHPN^\hat{val_{AHP_N}} as domain-extend of polynomials rowAHPNrow_{AHP_N}, colAHPNcol_{AHP_N} and valAHPNval_{AHP_N} where their domains are extended from subgroup K\mathbb{K} to filed F\mathbb{F}. Therefore, ∀k∈K\forall k \in \mathbb{K}, rowAHPN(k)=rowAHPN^(k)row_{AHP_N}(k) = \hat{row_{AHP_N}}(k), colAHPN(k)=colAHPN^(k)col_{AHP_N}(k) = \hat{col_{AHP_N}}(k), and valAHPN(k)=valAHPN^(k)val_{AHP_N}(k) = \hat{val_{AHP_N}}(k). O→AHP\overrightarrow{O}_{AHP}=

(rowAHPA0^,...,rowAHPAm−1^,colAHPA0^,...,,colAHPA0^,...,colAHPAm−1^,valAHPA0^,...,valAHPAm−1^rowAHPB0^,...,rowAHPBm−1^,colAHPB0^,....(\hat{row_{AHP_{A_0}}},...,\hat{row_{AHP_{A_{m-1}}}},\hat{col_{AHP_{A_0}}},...,,\hat{col_{AHP_{A_0}}},...,\hat{col_{AHP_{A_{m-1}}}},\hat{val_{AHP_{A_0}}},...,\hat{val_{AHP_{A_{m-1}}}}\hat{row_{AHP_{B_0}}},...,\hat{row_{AHP_{B_{m-1}}}},\hat{col_{AHP_{B_0}}},....

,colAHPBm−1^,valAHPB0^,...,valAHPBm−1^,rowAHPC0^,...,rowAHPCm−1^,colAHPC0^,...,colAHPCm−1^,valAHPC0^,....,valAHPCm−1^),\hat{col_{AHP_{B_{m-1}}}},\hat{val_{AHP_{B_0}}},...,\hat{val_{AHP_{B_{m-1}}}},\hat{row_{AHP_{C_0}}},...,\hat{row_{AHP_{C_{m-1}}}},\hat{col_{AHP_{C_0}}},...,\hat{col_{AHP_{C_{m-1}}}},\hat{val_{AHP_{C_0}}},....,\hat{val_{AHP_{C_{m-1}}}})

where rowAHPNi^\hat{row_{AHP_{N_i}}}, colAHPNi^\hat{col_{AHP_{N_i}}} and valAHPNi^\hat{val_{AHP_{N_i}}} are coefficient of xix^i of polynomials rowAHPN^(x)\hat{row_{AHP_N}}(x), colAHPN^(x)\hat{col_{AHP_N}}(x) and valAHPN^(x)\hat{val_{AHP_N}}(x), respectively. The vector O→AHP\overrightarrow{O}_{AHP} is called the encoded index.

3- The Prover calculates commitment for polynomial T∈T\in { rowAHPN^,colAHPN^,valAHPN^∣N∈{A,B,C}\hat{row_{AHP_N}},\hat{col_{AHP_N}},\hat{val_{AHP_N}}\hspace{2mm}|\hspace{2mm}N\in\{A,B,C\} } as ComAHPT=PC.Commit(ck′,T,dAHP(N,0,i)=m,si)Com_{AHP_T}=PC.Commit(ck',T,d_{AHP}(N,0,i)=m,s_i).

For example, if the polynomial commitment scheme KZGKZG is used, then ComAHPT=∑i=0degTaick′(i)Com_{AHP_T}=\sum_{i=0}^{deg_T}a_ick'(i) where aia_i is coefficient of xix^i in polynomial T(x)T(x) are calculated by the Prover as follows: ComAHP0=∑i=0degrowAHPA^(x)rowAHPAi^ck′(i)Com_{AHP}^0=\sum_{i=0}^{deg_{\hat{row_{AHP_A}}(x)}}\hat{row_{AHP_{A_i}}}\hspace{1.1mm}ck'(i), ComAHP1=∑i=0degcolAHPA^(x)colAHPAi^ck′(i)Com_{AHP}^1=\sum_{i=0}^{deg_{\hat{col_{AHP_A}}(x)}}\hat{col_{AHP_{A_i}}}\hspace{1.1mm}ck'(i), ComAHP2=∑i=0degvalAHPA^(x)valAHPAi^ck′(i)Com_{AHP}^2=\sum_{i=0}^{deg_{\hat{val_{AHP_A}}(x)}}\hat{val_{AHP_{A_i}}}\hspace{1.1mm}ck'(i), ComAHP3=∑i=0degrowAHPB^(x)rowAHPBi^ck′(i)Com_{AHP}^3=\sum_{i=0}^{deg_{\hat{row_{AHP_B}}(x)}}\hat{row_{AHP_{B_i}}}\hspace{1.1mm}ck'(i), ComAHP4=∑i=0degcolAHPB^(x)colAHPBi^ck′(i)Com_{AHP}^4=\sum_{i=0}^{deg_{\hat{col_{AHP_B}}(x)}}\hat{col_{AHP_{B_i}}}\hspace{1.1mm}ck'(i), ComAHP5=∑i=0degvalAHPB^(x)valAHPBi^ck′(i)Com_{AHP}^5=\sum_{i=0}^{deg_{\hat{val_{AHP_B}}(x)}}\hat{val_{AHP_{B_i}}}\hspace{1.1mm}ck'(i), ComAHP6=∑i=0degrowAHPC^(x)rowAHPCi^ck′(i)Com_{AHP}^6=\sum_{i=0}^{deg_{\hat{row_{AHP_C}}(x)}}\hat{row_{AHP_{C_i}}}\hspace{1.1mm}ck'(i), ComAHP7=∑i=0degcolAHPC^(x)colAHPCi^ck′(i)Com_{AHP}^7=\sum_{i=0}^{deg_{\hat{col_{AHP_C}}(x)}}\hat{col_{AHP_{C_i}}}\hspace{1.1mm}ck'(i), ComAHP8=∑i=0degvalAHPC^(x)valAHPCi^ck′(i)Com_{AHP}^8=\sum_{i=0}^{deg_{\hat{val_{AHP_C}}(x)}}\hat{val_{AHP_{C_i}}}\hspace{1.1mm}ck'(i).

4- The prover send the calculated commitment values to the Verifier.

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

A publicly accessible file to be published on a public repository, such as a blockchain.

{
    "commitmentId": String,
    "deviceType": String,
    "deviceIdType": String,
    "deviceModel": String,
    "manufacturer": String,
    "softwareVersion": String,
    "class": 32-bit Integer,
    "m": 64-bit Integer,
    "n": 64-bit Integer,
    "p": 64-bit Integer,
    "g": 64-bit Integer,   
        
    // PFR Commitment   
    "row_PFR_A": 64-bit Array,
    "col_PFR_A": 64-bit Array,
    "val_PFR_A": 64-bit Array,
    "row_PFR_B": 64-bit Array,
    "col_PFR_B": 64-bit Array,
    "val_PFR_B": 64-bit Array,
    "row_PFR_C": 64-bit Array,
    "col_PFR_C": 64-bit Array,
    "val_PFR_C": 64-bit Array,
    
    "Com_PFR0": 64-bit Integer,
    "Com_PFR1": 64-bit Integer,
    "Com_PFR2": 64-bit Integer,
    "Com_PFR3": 64-bit Integer,
    "Com_PFR4": 64-bit Integer,
    "Com_PFR5": 64-bit Integer,
    "Com_PFR6": 64-bit Integer,
    "Com_PFR7": 64-bit Integer,
    "Com_PFR8": 64-bit Integer,   

    // AHP Commitment
    "row_AHP_A": 64-bit Array,
    "col_AHP_A": 64-bit Array,
    "val_AHP_A": 64-bit Array,
    "row_AHP_B": 64-bit Array,
    "col_AHP_B": 64-bit Array,
    "val_AHP_B": 64-bit Array,
    "row_AHP_C": 64-bit Array,
    "col_AHP_C": 64-bit Array,
    "val_AHP_C": 64-bit Array,
    
    "Com_AHP0": 64-bit Integer,
    "Com_AHP1": 64-bit Integer,
    "Com_AHP2": 64-bit Integer,
    "Com_AHP3": 64-bit Integer,
    "Com_AHP4": 64-bit Integer,
    "Com_AHP5": 64-bit Integer,
    "Com_AHP6": 64-bit Integer,
    "Com_AHP7": 64-bit Integer,
    "Com_AHP8": 64-bit Integer,    
    
    "curve": String,
    "polynomial_commitment": String
}

  • commitmentId: Unique identifier for the commitment.

  • deviceType: Type of the IoT device (e.g., 'Sensor', 'Actuator', Car).

  • deviceIdType: Type of the device identifier (e.g., 'MAC', 'VIN').

  • deviceModel: Model of the IoT device.

  • manufacturer: Manufacturer of the IoT device (e.g., 'Siemens', 'Tesla').

  • softwareVersion: Software or firmware version of the device.

Param.json File Format

A privately accessible file created for the manufacturer, placed alongside the code to accelerate the proof-generation process. It includes information about the A, B, and C matrices.

Previous2-commitment-phaseNextExample 1

Last updated