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 and by three polynomials. The matrix , , is encoded by polynomials , and so that , and for where is maximum of the number of nonzero entries in the matrix , The value of is the order of the matrix. Also, is a generator of multiplicative subgroup of of order ( and ) and is a generator of multiplicative subgroup of of order ( and ). Also and are row number, column number and value of nonzero entry, respectively. Then, lets
where , and are coefficient of of polynomials , and , respectively. The vector is called as encoded index.
3- The Prover calculates for each polynomial . Note that { { } }.
For example, if the polynomial commitment scheme is used, then where is coefficient of in polynomial .
Size of Commitment: .
4- The Prover sends 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 , to prove that for public and . Now, we create a commitment for Algebraic Holographic Proof (AHP), , in this section.
: This function outputs
, here with random .
1 - The Prover selects random from random space . Note that as explained in the setup phase. 2- The Prover calculates as encoded index as following:
Considering as a generator of multiplicative subgroup of of order (i.e., and ), as a generator of multiplicative subgroup of of order (i.e., and ), for each matrix , we generate 3 polynomials , , and as described in the following steps:
The polynomial is constructed by for where is the number of nonzero entries in , and is the row number of nonzero entry and otherwise, is an arbitrary element in . Note that starts from zero. This step generate 3 polynomials; , , .
The polynomial is constructed by for and is column number of nonzero entry and otherwise returns an arbitrary element in . This step generate 3 polynomials; , , .
The polynomial is constructed by for where is value of nonzero entry and otherwise returns zero where for each , .
Now, we define , and as domain-extend of polynomials , and where their domains are extended from subgroup to filed . Therefore, , , , and . =
where , and are coefficient of of polynomials , and , respectively. The vector is called the encoded index.
3- The Prover calculates commitment for polynomial { } as .
For example, if the polynomial commitment scheme is used, then where is coefficient of in polynomial are calculated by the Prover as follows: , , , , , , , , .
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.
Last updated