> For the complete documentation index, see [llms.txt](https://fidesinnova.gitbook.io/docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://fidesinnova.gitbook.io/docs/fides-zero-knowledge-proof-zkp-algorithm/3-proof-generation-phase/3-1-proof-generation-algorithm.md).

# 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
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://fidesinnova.gitbook.io/docs/fides-zero-knowledge-proof-zkp-algorithm/3-proof-generation-phase/3-1-proof-generation-algorithm.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.