# 2- Commitment Phase

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

$$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 )\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 $$row\_{AHP\_N}(x)$$, $$col\_{AHP\_N}(x)$$, and $$val\_{AHP\_N}(x)$$ as described in the following steps:
* The polynomial $$row\_{AHP\_N}:\mathbb{K}\to\mathbb{H}$$ is constructed by $$row\_{AHP\_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, $$row\_{AHP\_N}(k)$$ is an arbitrary element in $$\mathbb{H}$$. Note that $$i$$ starts from zero. This step generate 3 polynomials; $$row\_{AHP\_A}(x)$$, $$row\_{AHP\_B}(x)$$, $$row\_{AHP\_C}(x)$$.
* The polynomial $$col\_{AHP\_N}:\mathbb{K}\to\mathbb{H}$$ is constructed by $$col\_{AHP\_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 $$col\_{AHP\_N}(k)$$ returns an arbitrary element in $$\mathbb{H}$$. This step generate 3 polynomials; $$col\_{AHP\_A}(x)$$, $$col\_{AHP\_B}(x)$$, $$col\_{AHP\_C}(x)$$.
* The polynomial $$val\_{AHP\_N}:\mathbb{K}\to\mathbb{H}$$ is constructed by $$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\leq i\leq ||N||-1$$ where $$v\_i$$ is value of $$i^{th}$$ nonzero entry and otherwise $$val\_{AHP\_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{row\_{AHP\_N}}$$, $$\hat{col\_{AHP\_N}}$$ and $$\hat{val\_{AHP\_N}}$$ as domain-extend of polynomials $$row\_{AHP\_N}$$, $$col\_{AHP\_N}$$ and $$val\_{AHP\_N}$$ where their domains are extended from subgroup $$\mathbb{K}$$ to filed $$\mathbb{F}$$. Therefore, $$\forall k \in \mathbb{K}$$, $$row\_{AHP\_N}(k) = \hat{row\_{AHP\_N}}(k)$$, $$col\_{AHP\_N}(k) = \hat{col\_{AHP\_N}}(k)$$, and $$val\_{AHP\_N}(k) = \hat{val\_{AHP\_N}}(k)$$.\
\
$$\overrightarrow{O}\_{AHP}$$=

$$(\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}}},....$$

$$,\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 $$\hat{row\_{AHP\_{N\_i}}}$$, $$\hat{col\_{AHP\_{N\_i}}}$$ and $$\hat{val\_{AHP\_{N\_i}}}$$ are coefficient of $$x^i$$ of polynomials $$\hat{row\_{AHP\_N}}(x)$$, $$\hat{col\_{AHP\_N}}(x)$$ and $$\hat{val\_{AHP\_N}}(x)$$, respectively. The vector $$\overrightarrow{O}\_{AHP}$$ is called the **encoded index**.

3- The Prover calculates commitment for polynomial $$T\in$$ { $$\hat{row\_{AHP\_N}},\hat{col\_{AHP\_N}},\hat{val\_{AHP\_N}}\hspace{2mm}|\hspace{2mm}N\in{A,B,C}$$ } as $$Com\_{AHP\_T}=PC.Commit(ck',T,d\_{AHP}(N,0,i)=m,s\_i)$$.

For example, if the polynomial commitment scheme $$KZG$$ is used, then\
$$Com\_{AHP\_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:\
$$Com\_{AHP}^0=\sum\_{i=0}^{deg\_{\hat{row\_{AHP\_A}}(x)}}\hat{row\_{AHP\_{A\_i}}}\hspace{1.1mm}ck'(i)$$,\
$$Com\_{AHP}^1=\sum\_{i=0}^{deg\_{\hat{col\_{AHP\_A}}(x)}}\hat{col\_{AHP\_{A\_i}}}\hspace{1.1mm}ck'(i)$$,\
$$Com\_{AHP}^2=\sum\_{i=0}^{deg\_{\hat{val\_{AHP\_A}}(x)}}\hat{val\_{AHP\_{A\_i}}}\hspace{1.1mm}ck'(i)$$,\
$$Com\_{AHP}^3=\sum\_{i=0}^{deg\_{\hat{row\_{AHP\_B}}(x)}}\hat{row\_{AHP\_{B\_i}}}\hspace{1.1mm}ck'(i)$$,\
$$Com\_{AHP}^4=\sum\_{i=0}^{deg\_{\hat{col\_{AHP\_B}}(x)}}\hat{col\_{AHP\_{B\_i}}}\hspace{1.1mm}ck'(i)$$,\
$$Com\_{AHP}^5=\sum\_{i=0}^{deg\_{\hat{val\_{AHP\_B}}(x)}}\hat{val\_{AHP\_{B\_i}}}\hspace{1.1mm}ck'(i)$$,\
$$Com\_{AHP}^6=\sum\_{i=0}^{deg\_{\hat{row\_{AHP\_C}}(x)}}\hat{row\_{AHP\_{C\_i}}}\hspace{1.1mm}ck'(i)$$,\
$$Com\_{AHP}^7=\sum\_{i=0}^{deg\_{\hat{col\_{AHP\_C}}(x)}}\hat{col\_{AHP\_{C\_i}}}\hspace{1.1mm}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.