# 3- Proof Generation Phase

## 3-1- PFR Proof

$$Proof (\mathbb{F}, \mathbb{H}, \mathbb{K}, A, B, C)$$: This function outputs $$\pi\_{PFR}=(\pi\_{PFR}^1,\pi\_{PFR}^2,\pi\_{PFR}^3,\pi\_{PFR}^4,\pi\_{PFR}^5,\pi\_{PFR}^6,\pi\_{PFR}^7,\pi\_{PFR}^8,\pi\_{PFR}^9,\pi\_{PFR}^{10})$$.

Note that in this polynomial oracle proof, the Prover wants to prove three following claims:\
$$1.$$ $$row\_{PFR\_A}(x)$$ , $$col\_{PFR\_A}(x)$$ and $$val\_{PFR\_A}(x)$$ is encoding of a $$t-SLT$$ matrix.\
$$2.$$ $$row\_{PFR\_B}(x)$$ , $$col\_{PFR\_B}(x)$$ and $$val\_{PFR\_B}(x)$$ is encoding of a $$t-SLT$$ matrix.\
$$3.$$ $$row\_{PFR\_C}(x)$$ , $$col\_{PFR\_C}(x)$$ and $$val\_{PFR\_C}(x)$$ is encoding of a $$t-Diag$$ matrix.

The proof of these claims is done in the following steps:

1- To prove strictly lower triangularity of the matrices $$A$$ and $$B$$, the Prover must prove that $$\log^{row\_{PFR\_M}(\gamma^i)}*{\omega}> \log^{col*{PFR\_M}(\gamma^i)}\_{\omega}$$ for $$i \in$${ $$0,1,..,m-1$$ } and $$M\in$$ { $$A,B$$ } . This does by $$Discrete-log-comparison-protocol$$.

2- To prove the first $$t$$ rows of $$A$$ and $$B$$ are all zeros, the Prover must prove that $$row\_{PFR\_M}(\mathbb{K})\subseteq{\omega^t,\omega^{t+1},...,\omega^{n-1}}$$. This does by $$subset\hspace{1mm}over\hspace{1mm} \mathbb{K}\hspace{1mm}protocol$$ .

3- To prove the diagonality of the matrix $$C$$, the Prover must prove that $$seq\_{\mathbb{K}}(row\_{PFR\_C})=seq\_{\mathbb{K}}(col\_{PFR\_C})$$ where $$seq\_{\mathbb{K}}(h)=(h(k):k\in\mathbb{K})$$. This does by $$Geometric\hspace{1mm} sequence$$ and $$zero\hspace{1mm}over\hspace{1mm}\mathbb{K}\hspace{1mm}protocols$$.

4- To prove the first $$t$$ rows of $$C$$ are all zeros, the Prover must prove that there is a vector $$v\in(\mathbb{F^\*})^{n-t}$$ so that $$seq\_{\mathbb{K}}(val\_{PFR\_C)}=\vec{v}||\vec{0}$$ . This does by $$Geometric\hspace{1mm} sequence$$ and $$zero\hspace{1mm}over\hspace{1mm}\mathbb{K}\hspace{1mm}protocols$$.

The steps 3 and 4 result that all the non-zero entries of the matrix $$C$$ are in the positions $$(\omega^t,\omega^t),(\omega^{t+1},\omega^{t+1}),...,(\omega^n,\omega^n)$$.

## 3-2- AHP Proof

$$Proof (\mathbb{F}, \mathbb{H}, \mathbb{K}, A, B, C, X,W,Y)$$: This function outputs

$$\Pi\_{AHP}=(Com\_{AHP\_X},\pi\_{AHP})$$

where\
\
$$Com\_{AHP\_X}=(Com\_{AHP\_X}^{1},Com\_{AHP\_X}^2,Com\_{AHP\_X}^3,Com\_{AHP\_X}^4,Com\_{AHP\_X}^5,Com\_{AHP\_X}^6,Com\_{AHP\_X}^7,Com\_{AHP\_X}^8,Com\_{AHP\_X}^9,$$ $$Com\_{AHP\_X}^{10},Com\_{AHP\_X}^{11},Com\_{AHP\_X}^{12},Com\_{AHP\_X}^{13})$$

and $$\pi\_{AHP}=(\pi\_{AHP}^{1},\pi\_{AHP}^2,\pi\_{AHP}^3,\pi\_{AHP}^4,\pi\_{AHP}^5,\pi\_{AHP}^6,\pi\_{AHP}^7,\pi\_{AHP}^8,\pi\_{AHP}^9,\pi\_{AHP}^{10},\pi\_{AHP}^{11},\pi\_{AHP}^{12},\pi\_{AHP}^{13},\pi\_{AHP}^{14},\pi\_{AHP}^{15},\pi\_{AHP}^{16},\pi\_{AHP}^{17})$$

as following:

1- The Prover calculates $$z\_A=Az$$, $$z\_B=Bz$$, $$z\_C=Cz$$ where $$z=(1,X,W,Y)$$, for input $$X$$ that puts in $$Com\_{AHP\_X}^1$$.

2- The Prover calculates polynomial $$z\_A(x)$$using indexing $$z\_A$$ by elements of $$\mathbb{H}$$. Then, calculates polynomial $$\hat{z}\_A(x)$$ using the polynomial $$z\_A(x)$$such that $$\hat{z}\_A(x)\in \mathbb{F}^{<|\mathbb{H}|+b}\[x]$$ that agree with $$z\_A(x)$$ on $$\mathbb{H}$$. Note that values of up to $$b$$ locations in this polynomial reveals no information about the witness $$w$$ provided the locations are in $$\mathbb{F}-\mathbb{H}$$. Similarly, calculates polynomial $$\hat{z}\_B(x)$$ so that $$\hat{z}\_B(x)\in \mathbb{F}^{<|\mathbb{H}|+b}\[x]$$ that agree with $$z\_B(x)$$ on $$\mathbb{H}$$. Also, calculates polynomial $$\hat{z}\_C(x)$$ so that $$\hat{z}\_C(x)\in \mathbb{F}^{<|\mathbb{H}|+b}\[x]$$ that agree with $$z\_C(x)$$ on $$\mathbb{H}$$.

Then, calculates polynomial $$\hat{W}(x)\in \mathbb{F}^{\<n\_g+b}\[x]$$ that agree with $$\bar{W}(x)$$ on $$\mathbb{H}\[>|X|+1]$$ where

$$\bar{W}:\mathbb{H}\[>|X|+1]\to \mathbb{F}$$

$$\bar{W}(h)=\frac{W(h)-\hat{X}(h)}{v\_{\mathbb{H}\[\leq |X|+1]}(h)}$$

Note that $$\mathbb{H}\[>|X|+1]$$ includes the members of $$\mathbb{H}$$ except for the first $$|X|+1$$ members. Also, $$v\_{\mathbb{H}\[\leq |X|+1]}(h)$$ is vanishing polynomial on $$\mathbb{H}\[\leq |X|+1]$$ and $$\hat{X}(h)$$ is the polynomial obtained using indexing $$x$$ by elements of $$\mathbb{H}\[\leq |X|+1]$$.

3- The Prover finds polynomial $$h\_0(x)$$ so that $$\hat{z}\_A(x)\hat{z}\_B(x)-\hat{z}*C(x)=h\_0(x)v*{\mathbb{H}}(x)$$.

4- The Prover samples a fully random $$s(x)\in\mathbb{F}^{<2|\mathbb{H}|+b-1}\[x]$$ and computes sum $$\sigma\_1=\sum\_{k\in \mathbb{H}}s(k)$$

5- The Prover sends $`Com_{AHP_X}^2=\sum_{i=0}^{deg_{\hat{W}(x)}}\hat{w}_i\hspace{1mm}ck(i)`$ , $`Com_{AHP_X}^{3}=\sum_{i=0}^{deg_{\hat{z}_A(x)}}\hat{z}_{A_i}ck(i)`$, $`Com_{AHP_X}^{4}=\sum_{i=0}^{deg_{\hat{z}_B(x)}}\hat{z}_{B_i}ck(i)`$, $`Com_{AHP_X}^{5}=\sum_{i=0}^{deg_{\hat{z}_C(x)}}\hat{z}_{C_i}ck(i)`$, $`Com_{AHP_X}^{6}=\sum_{i=0}^{deg_{h_0(x)}}h_{0_i}ck(i)`$, and $`Com_{AHP_X}^{7}=\sum_{i=0}^{deg_{s(x)}}s_i\hspace{1mm}ck(i)`$, where $`\hat{w}_i`$ is coefficient of $`x^i`$ in polynomial $`\hat{W}(x)`$, $`\hat{z}_{A_i}`$ is coefficient of $`x^i`$ in polynomial $`\hat{z}_A(x)`$, $`\hat{z}_{B_i}`$ is coefficient of $`x^i`$ in polynomial $`\hat{z}_B(x)`$, $`\hat{z}_{C_i}`$ is coefficient of $`x^i`$ in polynomial $`\hat{z}_C(x)`$, $`h_{0_i}`$ is coefficient of $`x^i`$ in polynomial $`h_0(x)`$, $`s_{i}`$ is coefficient of $`x^i`$ in polynomial $`s(x)`$.

6- The Verifier chooses random numbers $$\alpha$$, $$\eta\_A$$, $$\eta\_B$$, $$\eta\_C$$ and sends them to the Prover. ( Note that the Prover can choose $$\alpha=hash(s(0)+s(1)+1)$$, $$\eta\_A=hash(s(2)+s(3)+2)$$, $$\eta\_B=hash(s(4)+s(5)+3)$$, $$\eta\_C=hash(s(6)+s(7)+4)$$.

7- The Prover finds polynomials $$g\_1(x)$$ and $$h\_1(x)$$ so that

$$s(x)+r(\alpha,x)\sum\_{M}\eta\_M\hat{z}*M(x)-(\sum*{M}\eta\_Mr\_M(\alpha,x))\hat{z}(x)=h\_1(x)v\_{\mathbb{H}}(x)+xg\_1(x)+\frac{\sigma\_1}{|\mathbb{H}|}$$ $$(1)$$

where $$\hat{z}(x)=\hat{W}(x)v\_{\mathbb{H}\[\leq |X|+1]}(x)+\hat{X}(x)$$ that agree with $$z$$ on $$\mathbb{H}$$ and $$r(x,y)=u\_{\mathbb{H}}(x,y)=\frac{v\_{\mathbb{H}}(x)-v\_{\mathbb{H}}(y)}{x-y}$$ , $$v\_{\mathbb{H}}(x)=\prod\_{h\in \mathbb{H}}(x-h)=x^{|\mathbb{H}|}-1$$. Therefore\
$$r(x,y)=\frac{x^{|\mathbb{H}|}-y^{|\mathbb{H}|}}{x-y}$$. (Note that $$r(x,y)$$satisfies two useful algebraic properties. First, the univariate polynomials $$(r(x,a))*{a\in \mathbb{H}}$$ are linearly independent and $$r(x,y)$$ is their (unique) low-degree extension. Second, $$r(x,y)$$ vanishes on the square $$\mathbb{H}\times \mathbb{H}$$ except for on the diagonal, where it takes on the (non-zero) values $$(r(a,a))*{a\in \mathbb{H}}$$.) . Also $$r\_M(x,y)=\sum\_{k\in \mathbb{H}}r(x,k)\hat{M}(k,y)$$ for $$M\in {A,B,C}$$ where $$\hat{A}(x,y)$$ is a bivariate polynomial that passes from 25 points where theses points are obtained using indexing rows and columns of $$A$$ by elements of $$\mathbb{H}$$. This polynomial can obtain as following:\
$$\hat{A}(x,y)=\sum\_{k\in \mathbb{K}}u\_{\mathbb{H}}(x,\hat{row}*{AHP\_A}(k))u*{\mathbb{H}}(y,\hat{col}*{AHP\_A}(k))\hat{val}*{AHP\_A}(k)$$

, $$\hat{B}(x,y)$$ similarly as following:\
\
$$\hat{B}(x,y)=\sum\_{k\in \mathbb{K}}u\_{\mathbb{H}}(x,\hat{row}*{AHP\_B}(k))u*{\mathbb{H}}(y,\hat{col}*{AHP\_B}(k))\hat{val}*{AHP\_B}(k)$$

and $$\hat{C}(x,y)$$ similarly as following:\
\
$$\hat{C}(x,y)=\sum\_{k\in \mathbb{K}}u\_{\mathbb{H}}(x,\hat{row}*{AHP\_C}(k))u*{\mathbb{H}}(y,\hat{col}*{AHP\_C}(k))\hat{val}*{AHP\_C}(k)$$

\
The Prover sends $$Com\_{AHP\_X}^{8}=\sum\_{i=0}^{deg\_{g\_1(x)}}g\_{1\_i}ck(i)$$ and $$Com\_{AHP\_X}^{9}=\sum\_{i=0}^{deg\_{h\_1(x)}}h\_{1\_i}ck(i)$$ to the Verifier where $$g\_{1\_i}$$ is coefficient of $$x^i$$ of polynomial $$g\_1(x)$$ and $$h\_{1\_i}$$ is coefficient of $$x^i$$ of polynomial $$h\_1(x)$$.

8- The Verifier selects $$\beta\_1\in \mathbb{F}-\mathbb{H}$$ and sends it to the Prover. (The Prover can selects $$\beta\_1=hash(s(8))\in \mathbb{F}-\mathbb{H}$$ ).

9- The Prover calculates $$\sigma\_2=\sum\_{k\in\mathbb{H}}r(\alpha,k)\sum\_{M}\eta\_M\hat{M}(k,\beta\_1)$$. Then, the Prover finds $$g\_2(x)$$ and $$h\_2(x)$$ so that $$r(\alpha,x)\sum\_M \eta\_M\hat{M}(x,\beta\_1)=h\_2(x)v\_{\mathbb{H}}(x)+xg\_2(x)+\frac{\sigma\_2}{|\mathbb{H}|}$$

The Prover sends $$Com\_{AHP\_X}^{10}=\sum\_{i=0}^{deg\_{g\_2(x)}}g\_{2\_i}ck(i)$$ and $$Com\_{AHP\_X}^{11}=\sum\_{i=0}^{deg\_{h\_2(x)}}h\_{2\_i}ck(i)$$ where $$g\_{2\_i}$$ is coefficient of $$x^i$$ of polynomial $$g\_2(x)$$ and $$h\_{2\_i}$$ is coefficient of $$x^i$$ of polynomial $$h\_2(x)$$.

10- The Verifier selects $$\beta\_2\in \mathbb{F}-\mathbb{H}$$ and sends it to the Prover. ( The Prover can select $$\beta\_2=hash(s(9))\in \mathbb{F}-\mathbb{H}$$ ).

11- The Prover calculates $$\sigma\_3=\sum\_{k\in\mathbb{K}}(\sum\_M \eta\_M\frac{v\_{\mathbb{H}}(\beta\_2)v\_{\mathbb{H}}(\beta\_1)\hat{val\_{AHP\_M}}(k)}{(\beta\_2-\hat{row\_{AHP\_M}}(k))(\beta\_1-\hat{col\_{AHP\_M}}(k))})$$. Then, the Prover finds polynomials $$g\_3(x)$$ and $$h\_3(x)$$ so that $$h\_3(x)v\_{\mathbb{K}}(x)=a(x)-b(x)(xg\_3(x)+\frac{\sigma\_3}{|\mathbb{K}|})$$ where $$a(x)=\sum\_{M\in {A,B,C}} \eta\_M v\_{\mathbb{H}}(\beta\_2)v\_{\mathbb{H}}(\beta\_1)\hat{val}*{AHP\_M}(x)\prod*{N\in{A,B,C}-{M}}(\beta\_2-\hat{row}*{AHP\_N}(x))(\beta\_1-\hat{col}*{AHP\_N}(x))$$and $$b(x)=\prod\_{M\in{A,B,C}}(\beta\_2-\hat{row}*{AHP\_M}(x))(\beta\_1-\hat{col}*{AHP\_M}(x))$$.

The Prover sends $$Com\_{AHP\_X}^{12}=\sum\_{i=0}^{deg\_{g\_3(x)}}g\_{3\_i}ck(i)$$ and $$Com\_{AHP\_X}^{13}=\sum\_{i=0}^{deg\_{h\_3(x)}}h\_{3\_i}ck(i)$$ where $$g\_{3\_i}$$ is coefficient of $$x^i$$ of polynomial $$g\_3(x)$$ and $$h\_{3\_i}$$ is coefficient of $$x^i$$ of polynomial $$h\_3(x)$$.

and

12- The Prover sends $$\pi\_{AHP}^1=\sigma\_1$$,

$$\pi\_{AHP}^2=(\hat{w\_0},\hat{w\_1},\hat{w\_3},...,\hat{w\_{|W|+b-1}})$$,

$$\pi\_{AHP}^3=(\hat{z}*{A\_0},\hat{z}*{A\_1},...,\hat{z}*{A*{|H|+b-1}})$$, $$\pi\_{AHP}^4=(\hat{z}*{B\_0},\hat{z}*{B\_1},...,\hat{z}*{B*{|H|+b-1}})$$, $$\pi\_{AHP}^5=(\hat{z}*{C\_0},\hat{z}*{C\_1},...,\hat{z}*{C*{|H|+b-1}})$$, $$\pi\_{AHP}^6=(h\_{0\_0},h\_{0\_1},...,h\_{0\_{|H|+2b-2}})$$ and $$\pi\_{AHP}^7=(s\_0,s\_1,...,s\_{2|H|+b-2})$$\
\
13- The Prover sends $$\pi\_{AHP}^8=(g\_{1\_0},...,g\_{1\_{|H|-2}})$$ and $$\pi\_{AHP}^{9}=(h\_{1\_0},...,h\_{1\_{|H|+b-2}})$$ .

14-The Prover sends $$\pi\_{AHP}^{10}=\sigma\_2$$, $$\pi\_{AHP}^{11}=(g\_{2\_0},...,g\_{2\_{|H|-2}})$$ and $$\pi\_{AHP}^{12}=(h\_{2\_0},...,h\_{2\_{|H|-2}})$$.

15- The Prover sends $$\pi\_{AHP}^{13}=\sigma\_3$$, $$\pi\_{AHP}^{14}=(g\_{3\_0},...,g\_{3\_{|K|-2}})$$ and $$\pi\_{AHP}^{15}=(h\_{3\_0},...,h\_{3\_{6|K|-6}})$$ .

16- The Prover chooses random values $$\eta\_{row\_{AHP\_A}}$$ , $$\eta\_{col\_{AHP\_A}}$$ , $$\eta\_{val\_{AHP\_A}}$$ , $$\eta\_{row\_{AHP\_B}}$$ , $$\eta\_{col\_{AHP\_B}}$$ , $$\eta\_{val\_{AHP\_B}}$$ ,\
$$\eta\_{row\_{AHP\_C}}$$ , $$\eta\_{col\_{AHP\_C}}$$ , $$\eta\_{val\_{AHP\_C}}$$ , $$\eta\_{\hat{w}}$$, $$\eta\_{\hat{z}*A}$$, $$\eta*{\hat{z}*B}$$, $$\eta*{\hat{z}*C}$$, $$\eta*{\hat{z}}$$, $$\eta\_{h\_0}$$, $$\eta\_s$$, $$\eta\_{g\_1}$$, $$\eta\_{h\_1}$$, $$\eta\_{g\_2}$$, $$\eta\_{h\_2}$$, $$\eta\_{g\_3}$$ and $$\eta\_{h\_3}$$ of $$\mathbb{F}$$ The Verifier can choose as following:\
$$\eta\_{row\_{AHP\_A}}=hash(s(10))$$ , $$\eta\_{col\_{AHP\_A}}=hash(s(11))$$ , $$\eta\_{val\_{AHP\_A}}=hash(s(12))$$ , $$\eta\_{row\_{AHP\_B}}=hash(s(13))$$ , $$\eta\_{col\_{AHP\_B}}=hash(s(14))$$ , $$\eta\_{val\_{AHP\_B}}=hash(s(15))$$ ,$$\eta\_{row\_{AHP\_C}}=hash(s(16))$$ , $$\eta\_{col\_{AHP\_C}}=hash(s(17))$$ , $$\eta\_{val\_{AHP\_C}}=hash(s(18))$$ ,\
$$\eta\_{\hat{w}}=hash(s(19))$$, $$\eta\_{\hat{z}*A}=hash(s(20))$$, $$\eta*{\hat{z}*B}=hash(s(20))$$, $$\eta*{\hat{z}*C}=hash(s(21))$$, $$\eta*{h\_0}=hash(s(22))$$, $$\eta\_{s}=hash(s(23))$$, $$\eta\_{g\_1}=hash(s(24))$$, $$\eta\_{h\_1}=hash(s(25))$$, $$\eta\_{g\_2}=hash(s(26))$$, $$\eta\_{h\_2}=hash(s(27))$$, $$\eta\_{g\_3}=hash(s(28))$$, $$\eta\_{h\_3}=hash(s(29))$$.

17- The Prover builds the linear combination

$$p(x)=\eta\_{row\_{AHP\_A}}\hat{row}*{AHP\_A}(x)+\eta*{col\_{AHP\_A}}\hat{col}*{AHP\_A}(x)+\eta*{val\_{AHP\_A}}\hat{val}*{AHP\_A}(x)+\eta*{row\_{AHP\_B}}\hat{row}*{AHP\_B}(x)+\eta*{col\_{AHP\_B}}\hat{col}*{AHP\_B}(x)+\eta*{val\_{AHP\_B}}\hat{val}*{AHP\_B}(x)+\eta*{row\_{AHP\_C}}\hat{row}*{AHP\_C}(x)+\eta*{col\_{AHP\_B}}\hat{col}*{AHP\_B}(x)+\eta*{val\_{AHP\_C}}\hat{val}*{AHP\_C}(x)+\eta*{\hat{w}}\hat{w}(x)+\eta\_{\hat{z}*A}\hat{z}*A(x)+\eta*{\hat{z}*B}\hat{z}*B(x)+\eta*{\hat{z}*C}\hat{z}*C(x)+\eta*{h\_0}h\_0(x)+\eta\_ss(x)+\eta*{g\_1}g\_1(x)+\eta*{h\_1}h\_1(x)+\eta*{g\_2}g\_2(x)+\eta\_{h\_2}h\_2(x)+\eta\_{g\_3}g\_3(x)+\eta\_{h\_3}h\_3(x$$ \\

18- The Prover calculates $$p(x)$$ in $$x=x'$$ (value of $$x'$$ is received from the Verifier. Also, can select as $$x'=hash(s(22)))$$, then puts it in $$\pi\_{AHP}^{16}$$ . Therefore $$\pi\_{AHP}^{16}=p(x')=y'$$.

19- The Prover computes $$\pi\_{AHP}^{17}=PC.Eval(ck,p(x),d\_p,r\_p,x')$$ where $$d\_p$$ is degree bound of $$p(x)$$ and $$r\_p$$ is a random value.\
For example, if the polynomial commitment scheme $$KZG$$ is used, then the Prover calculates polynomial $$q(x)=\frac{p(x)-y'}{x-x'}$$ and $$\pi\_{AHP}^{17}=g\hspace{1mm}q(\tau)$$ by using $$ck$$ as following:\
$$\pi\_{AHP}^{17}=\sum\_{i=0}^{deg\_{q(x)}}q\_i\hspace{1mm}ck(i)$$, where $$q\_i$$ is the coefficient of $$x^i$$ of $$q(x)$$.

## 3-3- Proof Structure

Proof set is

$$\Pi\_{AHP}=(Com\_{AHP\_X},\pi\_{AHP})$$

where\
\
$$Com\_{AHP\_X}=(Com\_{AHP\_X}^{1},Com\_{AHP\_X}^2,Com\_{AHP\_X}^3,Com\_{AHP\_X}^4,Com\_{AHP\_X}^5,Com\_{AHP\_X}^6,Com\_{AHP\_X}^7,Com\_{AHP\_X}^8,Com\_{AHP\_X}^9,$$ $$Com\_{AHP\_X}^{10},Com\_{AHP\_X}^{11},Com\_{AHP\_X}^{12},Com\_{AHP\_X}^{13})$$

$$Com\_{AHP\_X}^1=X$$,\
$$Com\_{AHP\_X}^2=\sum\_{i=0}^{deg\_{\hat{W}(x)}}\hat{w}*i\hspace{1mm}ck(i)$$,\
$$Com*{AHP\_X}^{3}=\sum\_{i=0}^{deg\_{\hat{z}*A(x)}}\hat{z}*{A\_i}ck(i)$$,\
$$Com\_{AHP\_X}^{4}=\sum\_{i=0}^{deg\_{\hat{z}*B(x)}}\hat{z}*{B\_i}ck(i)$$,\
$$Com\_{AHP\_X}^{5}=\sum\_{i=0}^{deg\_{\hat{z}*C(x)}}\hat{z}*{C\_i}ck(i)$$,\
$$Com\_{AHP\_X}^{6}=\sum\_{i=0}^{deg\_{h\_0(x)}}h\_{0\_i}ck(i)$$,\
$$Com\_{AHP\_X}^{7}=\sum\_{i=0}^{deg\_{s(x)}}s\_i\hspace{1mm}ck(i)$$,\
$$Com\_{AHP\_X}^{8}=\sum\_{i=0}^{deg\_{g\_1(x)}}g\_{1\_i}ck(i)$$,\
$$Com\_{AHP\_X}^{9}=\sum\_{i=0}^{deg\_{h\_1(x)}}h\_{1\_i}ck(i)$$,\
$$Com\_{AHP\_X}^{10}=\sum\_{i=0}^{deg\_{g\_2(x)}}g\_{2\_i}ck(i)$$,\
$$Com\_{AHP\_X}^{11}=\sum\_{i=0}^{deg\_{h\_2(x)}}h\_{2\_i}ck(i)$$,\
$$Com\_{AHP\_X}^{12}=\sum\_{i=0}^{deg\_{g\_3(x)}}g\_{3\_i}ck(i)$$,\
$$Com\_{AHP\_X}^{13}=\sum\_{i=0}^{deg\_{h\_3(x)}}h\_{3\_i}ck(i)$$

and $$\pi\_{AHP}=(\pi\_{AHP}^{1},\pi\_{AHP}^2,\pi\_{AHP}^3,\pi\_{AHP}^4,\pi\_{AHP}^5,\pi\_{AHP}^6,\pi\_{AHP}^7,\pi\_{AHP}^8,\pi\_{AHP}^9,\pi\_{AHP}^{10},\pi\_{AHP}^{11},\pi\_{AHP}^{12},\pi\_{AHP}^{13},\pi\_{AHP}^{14},\pi\_{AHP}^{15},$$$$\pi\_{AHP}^{16},\pi\_{AHP}^{17})$$

\
$$\pi\_{AHP}^1=\sigma\_1$$,\
$$\pi\_{AHP}^2=(\hat{w}*0,\hat{w}*1,\hat{w}*3,...,\hat{w}*{n\_g+b-1})$$,\
$$\pi*{AHP}^3=(\hat{z}*{A\_0},\hat{z}*{A\_1},...,\hat{z}*{A\_{|H|+b-1}})$$,\
$$\pi\_{AHP}^4=(\hat{z}*{B\_0},\hat{z}*{B\_1},...,\hat{z}*{B*{|H|+b-1}})$$,\
$$\pi\_{AHP}^5=(\hat{z}*{C\_0},\hat{z}*{C\_1},...,\hat{z}*{C*{|H|+b-1}})$$,\
$$\pi\_{AHP}^6=(h\_{0\_0},h\_{0\_1},...,h\_{0\_{|H|+2b-2}})$$,\
$$\pi\_{AHP}^7=(s\_0,s\_1,...,s\_{2|H|+b-2})$$,\
$$\pi\_{AHP}^8=(g\_{1\_0},...,g\_{1\_{|H|-2}})$$,\
$$\pi\_{AHP}^{9}=(h\_{1\_0},...,h\_{1\_{|H|+b-2}})$$,\
$$\pi\_{AHP}^{10}=\sigma\_2$$,\
$$\pi\_{AHP}^{11}=(g\_{2\_0},...,g\_{2\_{|H|-2}})$$,\
$$\pi\_{AHP}^{12}=(h\_{2\_0},...,h\_{2\_{|H|-2}})$$,\
$$\pi\_{AHP}^{13}=\sigma\_3$$,\
$$\pi\_{AHP}^{14}=(g\_{3\_0},...,g\_{3\_{|K|-2}})$$,\
$$\pi\_{AHP}^{15}=(h\_{3\_0},...,h\_{3\_{6|K|-6}})$$,\
$$\pi\_{AHP}^{16}=y'$$,\
$$\pi\_{AHP}^{17}=\sum\_{i=0}^{deg\_{q(x)}}q\_i\hspace{1mm}ck(i)$$.

where $$\hat{w}*i$$ is coefficient of $$x^i$$ in polynomial $$\hat{W}(x)$$, $$\hat{z}*{A\_i}$$ is coefficient of $$x^i$$ in polynomial $$\hat{z}*A(x)$$, $$\hat{z}*{B\_i}$$ is coefficient of $$x^i$$ in polynomial $$\hat{z}*B(x)$$, $$\hat{z}*{C\_i}$$ is coefficient of $$x^i$$ in polynomial $$\hat{z}*C(x)$$, $$h*{0\_i}$$ is coefficient of $$x^i$$ in polynomial $$h\_0(x)$$, $$s\_{i}$$ is coefficient of $$x^i$$ in polynomial $$s(x)$$, $$g\_{1\_i}$$ is coefficient of $$x^i$$ of polynomial $$g\_1(x)$$ and $$h\_{1\_i}$$ is coefficient of $$x^i$$ of polynomial $$h\_1(x)$$, $$g\_{2\_i}$$ is coefficient of $$x^i$$ of polynomial $$g\_2(x)$$ and $$h\_{2\_i}$$ is coefficient of $$x^i$$ of polynomial $$h\_2(x)$$, $$g\_{3\_i}$$ is coefficient of $$x^i$$ of polynomial $$g\_3(x)$$ and $$h\_{3\_i}$$ is coefficient of $$x^i$$ of polynomial $$h\_3(x)$$.

* Size of AHP proof: $$|\Pi\_{AHP}|=10|\mathbb{H}|+7|\mathbb{K}|+|W|+8b+6$$.
* CommitmentID is explained on the Commitment Phase page.
* DeviceEncodedID = Base64\<MAC>
* Input and Output are the device input and output, respectively.

## 3-4- Proof JSON file format

```
{
    "commitmentId": 64-bit,
    "class": 32-bit Integer,
    "input": 64-bit Integer,
    "output": 64-bit Integer,    
       
    "P_AHP1": 64-bit Integer,
    "P_AHP2": 64-bit Array,
    "P_AHP3": 64-bit Array,
    "P_AHP4": 64-bit Array,
    "P_AHP5": 64-bit Array,
    "P_AHP6": 64-bit Array,
    "P_AHP7": 64-bit Array,
    "P_AHP8": 64-bit Array,
    "P_AHP9": 64-bit Array,
    "P_AHP10": 64-bit Integer,
    "P_AHP11": 64-bit Array,
    "P_AHP12": 64-bit Array,
    "P_AHP13": 64-bit Integer,
    "P_AHP14": 64-bit Array,
    "P_AHP15": 64-bit Array,
    "P_AHP16": 64-bit Integer, 
    "P_AHP17": 64-bit Array,
      
    "Com_AHP1_x": 64-bit Integer,
    "Com_AHP2_x": 64-bit Integer,
    "Com_AHP3_x": 64-bit Integer,
    "Com_AHP4_x": 64-bit Integer,
    "Com_AHP5_x": 64-bit Integer,
    "Com_AHP6_x": 64-bit Integer,   
    "Com_AHP7_x": 64-bit Integer,
    "Com_AHP8_x": 64-bit Integer,
    "Com_AHP9_x": 64-bit Integer,
    "Com_AHP10_x": 64-bit Integer,
    "Com_AHP11_x": 64-bit Integer,
    "Com_AHP12_x": 64-bit Integer,
    "Com_AHP13_x": 64-bit Integer
}
```