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, B$ and $C$ by three polynomials. The matrix $N$, $N\in\{A, B, C\}$, is encoded by polynomials $row_{PFR_N}(x)$, $col_{PFR_N}(x)$ and $val_{PFR_N}(x)$ so that $row_{PFR_N}(\gamma^i)=\omega^{r_i}$, $col_{PFR_N}(\gamma^i)=\omega^{c_i}$ and $val_{PFR_N}(\gamma^i)=v_i$ for $i\in\{0,1,2,..,m-1\}$ where $m=2n_g$ is maximum of the number of nonzero entries in the matrix $N$, The value of $n=n_g+n_i+1$ is the order of the matrix. Also, $\gamma$ is a generator of multiplicative subgroup $\mathbb{K}$ of $\mathbb{F}$ of order $m$ ($\mathbb{K}=<\gamma>$ and $|\mathbb{K}|=m$) and $\omega$ is a generator of multiplicative subgroup $\mathbb{H}$ of $\mathbb{F}$ of order $n$ ($\mathbb{H}=<\omega>$ and $|\mathbb{H}|=n$). Also $r_i,c_i\in \{0,1,...,n-1\}$ and $v_i\in \mathbb{F}$ are row number, column number and value of $i^{th}$ nonzero entry, respectively. Then, lets $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}}},$ $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}}},$ $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 $row_{PFR_{N_i}}$, $col_{PFR_{N_i}}$and $val_{PFR_{N_i}}$ are coefficient of $x^i$ of polynomials $row_{PFR_N}(x)$, $col_{PFR_N}(x)$and $val_{PFR_N}(x)$ , respectively. The vector $O_{PFR}$ is called as encoded index.

3- The Prover calculates $Com_{PFR_T}=PC.Commit(ck,T,d_{AHP}(N,0,i)=m,r_{T})$ for each polynomial $T(x)$. Note that $T\in\{row_{PFR_N},col_{PFR_N},val_{PFR_N}\hspace{2mm}|\hspace{2mm}N\in\{A,B,C\}\}$.

For example, if the polynomial commitment scheme $KZG$ is used, then $Com_{T}=\sum_{i=0}^{deg_T}a_ig\tau^i=\sum_{i=0}^{deg_T}a_ick(i)$ where $a_i$ is coefficient of $x^i$ in polynomial $T(x)$.

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

4- The Prover sends $Com_{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 $f$, to prove that $y=f(x)$ for public $x$ and $y$. Now, we create a commitment for Algebraic Holographic Proof (AHP), $AHP\hspace{1mm}Com$ , in this section.

$Commit(ck',m_f=(A,B,C)\in \textit{M}_f,s\in R)$: This function outputs $AHP\hspace{1mm}Com=(AHP\hspace{1mm}Com_0,AHP\hspace{1mm}Com_1,AHP\hspace{1mm}Com_2,AHP\hspace{1mm}Com_3,AHP\hspace{1mm}Com_4,AHP\hspace{1mm}Com_5,AHP\hspace{1mm}Com_6,$$AHP\hspace{1mm}Com_7,AHP\hspace{1mm}Com_8)$

where $ck'(i)=ck(i )\hspace{1mm}r'^i$ with random $r'$. 1 - The Prover selects random $s=(s_1,...s_{s_{AHP}(0)})$ from random space $R$. Note that $s_{AHP}(0)=9$ as explained in the setup phase. 2- The Prover calculates $\overrightarrow{O}_{AHP}=Enc(m_f=(A,B,C))$ as encoded index as following:

• Considering $\gamma$ as a generator of multiplicative subgroup $\mathbb{K}$ of $\mathbb{F}$ of order $m$ (i.e., $\mathbb{K}=<\gamma>$ and $|\mathbb{K}|=m$), $\omega$ as a generator of multiplicative subgroup $\mathbb{H}$ of $\mathbb{F}$ of order $n$ (i.e., $\mathbb{H}=<\omega>$ and $|\mathbb{H}|=n$), for each matrix $N\in \{A,B,C\}$, we generate 3 polynomials $AHProw_N(x)$, $AHPcol_N(x)$, and $AHPval_N(x)$ as described in the following steps:

• The polynomial $AHProw_N:\mathbb{K}\to\mathbb{H}$ is constructed by $AHProw_N(k=\gamma^i)=\omega^{r_i}$ for $0\leq i\leq ||N||-1$ where $||N||$ is the number of nonzero entries in $N$, and $r_i\in \{0,1,...,n-1\}$ is the row number of $i^{th}$ nonzero entry and otherwise, $AHProw_N(k)$ is an arbitrary element in $\mathbb{H}$. Note that $i$ starts from zero. This step generate 3 polynomials; $AHProw_A(x)$, $AHProw_B(x)$, $AHProw_C(x)$.

• The polynomial $AHPcol_N:\mathbb{K}\to\mathbb{H}$ is constructed by $AHPcol_N(k=\gamma^i)=\omega^{c_i}$ for $0\leq i\leq ||N||-1$ and $c_i\in \{0,1,...,n-1\}$ is column number of $i^{th}$ nonzero entry and otherwise $AHPcol_N(k)$ returns an arbitrary element in $\mathbb{H}$. This step generate 3 polynomials; $AHPcol_A(x)$, $AHPcol_B(x)$, $AHPcol_C(x)$.

• The polynomial $AHPval_N:\mathbb{K}\to\mathbb{H}$ is constructed by $AHPval_N(k=\gamma^i)=\frac{v_i}{u_{\mathbb{H}}(AHProw_N(k),AHProw_N(k))u_{\mathbb{H}}(AHPcol_N(k),AHPcol_N(k))}$ for $0\leq i\leq ||N||-1$ where $v_i$ is value of $i^{th}$ nonzero entry and otherwise $AHPval_N(k)$ returns zero where for each $x \in \mathbb{H}$, $u_{\mathbb{H}}(x,x)=|\mathbb{H}|x^{|\mathbb{H}|-1}$.

Now, we define $\hat{AHProw_N}$, $\hat{AHPcol_N}$ and $\hat{AHPval_N}$ as domain-extend of polynomials $AHProw_N$, $AHPcol_N$ and $AHPval_N$ where their domains are extended from subgroup $\mathbb{K}$ to filed $\mathbb{F}$. Therefore, $\forall k \in \mathbb{K}$, $AHProw_N(k) = \hat{AHProw_N}(k)$, $AHPcol_N(k) = \hat{AHPcol_N}(k)$, and $AHPval_N(k) = \hat{AHPval_N}(k)$. $\overrightarrow{O}_{AHP}=(\hat{AHProw}_{A_0},....,\hat{AHProw}_{A_{m-1}},\hat{AHPcol}_{A_0},...,\hat{AHPcol}_{A_{m-1}},\hat{AHPval}_{A_0},...,\hat{AHPval}_{A_{m-1}},$$\hat{AHProw}_{B_0},...,\hat{AHProw}_{B_{m-1}},\hat{AHPcol}_{B_0},....,\hat{AHPcol}_{B_{m-1}},\hat{AHPval}_{B_0},...,\hat{AHPval}_{B_{m-1}},$ $\hat{AHProw}_{C_0},...,\hat{AHProw}_{C_{m-1}},\hat{AHPcol}_{C_0},...,\hat{AHPcol}_{C_{m-1}},\hat{AHPval}_{C_0},....,\hat{AHPval}_{C_{m-1}})$

where $\hat{AHProw}_{N_i}$, $\hat{AHPcol}_{N_i}$and $\hat{AHPval}_{N_i}$ are coefficient of $x^i$ of polynomials $\hat{AHProw}_{N}(x)$, $\hat{AHPcol}_{N}(x)$ and $\hat{AHPval}_{N}(x)$, respectively. The vector $\overrightarrow{O}_{AHP}$ is called the encoded index.

3- The Prover calculates commitment for polynomial $T\in\{\hat{AHProw}_N,\hat{AHPcol}_N,\hat{AHPval}_N\hspace{2mm}|\hspace{2mm}N\in\{A,B,C\}\}$ as $AHP\hspace{1mm}Com_{T}=PC.Commit(ck',T,d_{AHP}(N,0,i)=m,s_i)$.

For example, if the polynomial commitment scheme $KZG$ is used, then $AHP\hspace{1mm}com_{T}=\sum_{i=0}^{deg_T}a_ick'(i)$ where $a_i$ is coefficient of $x^i$ in polynomial $T(x)$ are calculated by the Prover as follows: $AHP\hspace{1mm}Com_0=\sum_{i=0}^{deg_{\hat{AHProw}_A(x)}}\hat{AHProw}_{A_i}\hspace{1.1mm}ck'(i)$, $AHP\hspace{1mm}Com_1=\sum_{i=0}^{deg_{\hat{AHPcol}_A(x)}}\hat{AHPcol}_{A_i}\hspace{1.1mm}ck'(i)$, $AHP\hspace{1mm}Com_2=\sum_{i=0}^{deg_{\hat{AHPval}_A(x)}}\hat{AHPval}_{A_i}\hspace{1.1mm}ck'(i)$, $AHP\hspace{1mm}Com_3=\sum_{i=0}^{deg_{\hat{AHProw}_B(x)}}\hat{AHProw}_{B_i}\hspace{1.1mm}ck'(i)$, $AHP\hspace{1mm}Com_4=\sum_{i=0}^{deg_{\hat{AHPcol}_B(x)}}\hat{AHPcol}_{B_i}\hspace{1.1mm}ck'(i)$, $AHP\hspace{1mm}Com_5=\sum_{i=0}^{deg_{\hat{AHPval}_B(x)}}\hat{AHPval}_{B_i}\hspace{1.1mm}ck'(i)$, $AHP\hspace{1mm}Com_6=\sum_{i=0}^{deg_{\hat{AHProw}_C(x)}}\hat{AHProw}_{C_i}\hspace{1.1mm}ck'(i)$, $AHP\hspace{1mm}Com_7=\sum_{i=0}^{deg_{\hat{AHPcol}_C(x)}}\hat{AHPcol}_{C_i}\hspace{1.1mm}ck'(i)$, $AHP\hspace{1mm}Com_8=\sum_{i=0}^{deg_{\hat{AHPval}_C(x)}}\hat{AHPval}_{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

{
    "commitment_id": String,
    "iot_developer_name": String,
    "iot_device_name": String,
    "device_hardware_version": String,
    "firmware_version": String,
    "class": 32-bit Integer,
    "m": 64-bit Integer,
    "n": 64-bit Integer,
    "p": 64-bit Integer,
    "g": 64-bit Integer,   
        
    // PFR Commitment   
    "PFRrow_A": 64-bit Array,
    "PFRcol_A": 64-bit Array,
    "PFRval_A": 64-bit Array,
    "PFRrow_B": 64-bit Array,
    "PFRcol_B": 64-bit Array,
    "PFRval_B": 64-bit Array,
    "PFRrow_C": 64-bit Array,
    "PFRcol_C": 64-bit Array,
    "PFRval_C": 64-bit Array,
    
    "PFR Com0": 64-bit Integer,
    "PFR Com1": 64-bit Integer,
    "PFR Com2": 64-bit Integer,
    "PFR Com3": 64-bit Integer,
    "PFR Com4": 64-bit Integer,
    "PFR Com5": 64-bit Integer,
    "PFR Com6": 64-bit Integer,
    "PFR Com7": 64-bit Integer,
    "PFRCom8": 64-bit Integer,   

    // AHP Commitment
    "AHProw_A": 64-bit Array,
    "AHPcol_A": 64-bit Array,
    "AHPval_A": 64-bit Array,
    "AHProw_B": 64-bit Array,
    "AHPcol_B": 64-bit Array,
    "AHPval_B": 64-bit Array,
    "AHProwC_": 64-bit Array,
    "AHPcol_C": 64-bit Array,
    "AHPval_C": 64-bit Array,
    
    "AHP Com0": 64-bit Integer,
    "AHP Com1": 64-bit Integer,
    "AHP Com2": 64-bit Integer,
    "AHP Com3": 64-bit Integer,
    "AHP Com4": 64-bit Integer,
    "AHP Com5": 64-bit Integer,
    "AHP Com6": 64-bit Integer,
    "AHP Com7": 64-bit Integer,
    "AHP Com8": 64-bit Integer,    
    
    "curve": String,
    "polynomial_commitment": String
}

Param.json File Format