# Example 2

### AHP Proof

$$Proof (\mathbb{F}\_{1678321}, \mathbb{H}, \mathbb{K}, A, B, C, X=(7 , 11 ,0 ,1 ,0 ,1 ,0 ,0 ,0 ,2 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,7 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0, 0),W=(12,22),Y=(32,84))$$

1- The Prover puts $$X=(7,11,0,1,0,1,0,0,0,2,0,0,0,0,0,0,0,0,7,0,0,...,0)$$ in $$Com\_{AHP\_X}^1$$ . We consider $$z=(1,x\_1,x\_2,...,x\_{32},w\_1,w\_2,y\_1,y\_2)$$ where $$w\_1=x\_1+5$$, $$w\_2=x\_2\times x\_{10}$$ , $$y\_1=w\_2+10$$ and $$y\_2=w\_1\times x\_{19}$$. Therefore\
$$z=(1,X,W,Y)=(1,7,11,0,1,0,1,0,0,0,2,0,0,0,0,0,0,0,0,7,0,0,...,0,12,22,32,84)$$ The Prover calculates:

$$z\_A=Az=\begin{bmatrix}0\0\0\0\0\\:\1\11\1\12\end{bmatrix}$$, $$z\_B=Bz=\begin{bmatrix}0\0\0\0\0\\:\12\2\32\7\end{bmatrix}$$, $$z\_C=Cz=\begin{bmatrix}0\0\0\0\0\\:\12\22\32\84\end{bmatrix}$$

2- The Prover calculates the polynomial $$z\_A(x)$$using indexing $$z\_A$$ by elements of $$\mathbb{H}$$ that mean $$z\_A(x)$$ is the polynomial where $$z\_A(1)=...=z\_A(\omega^{32})=0$$, $$z\_A(\omega^{33})=1$$, $$z\_A(\omega^{34})=11$$, $$z\_A(\omega^{35})=1$$ and $$z\_A(\omega^{36})=12$$.

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}$$.\
Here, for simplicity, let $$b=2$$. The Prover calculates $$\hat{z}\_A(x)$$ such that agree with $$z\_A(x)$$ on $$\mathbb{H}$$ and also $$\hat{z}\_A(3)=3$$, $$\hat{z}\_A(4)=4$$.

Therefore, we have

$$\hat{z}*A(x)=L*{34}(x)+11L\_{35}(x)+L\_{36}(x)+12L\_{37}(x)+3L\_{38}(x)+4L\_{39}(x)=$$\
$$287049x^{38} + 1530559x^{37} + 904146x^{36} + 766942x^{35} + 900649x^{34} + 705790x^{33} + 88593x^{32} + 1406132x^{31} + 222647x^{30} + 897917x^{29} + 981227x^{28} + 1080203x^{27} + 166128x^{26} + 1374718x^{25} + 150588x^{24} + 561332x^{23} + 607746x^{22} + 144534x^{21} + 876189x^{20} + 1124687x^{19} + 1070791x^{18} + 933185x^{17} + 446434x^{16} + 216721x^{15} + 654101x^{14} + 1319736x^{13} + 44719x^{12} + 1448628x^{11} + 482390x^{10} + 604857x^9 + 1459683x^8 + 1498609x^7 + 1506753x^6 + 1322746x^5 + 321181x^4 + 1167473x^3 + 1216744x^2 + 703489x + 692083$$

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}$$ that mean $$\hat{z}\_B(1)=...=\hat{z}\_B(\omega^{32})=0$$, $$\hat{z}\_B(\omega^{33})=12$$, $$\hat{z}*B(\omega^{34})=2$$, $$\hat{z}*B(\omega^{35})=32$$ and $$\hat{z}*B(\omega^{36})=7$$ and also $$b=2$$ random locations $$\hat{z}*B(3)=3$$ and $$\hat{z}*B(4)=4$$. So, $$\hat{z}*B(x)=12L*{34}(x)+2L*{35}(x)+32L*{36}(x)+7L*{37}(x)+3L*{38}(x)+4L*{39}(x)=$$\
$$161089x^{38} + 1433536x^{37} + 238219x^{36} + 346226x^{35} + 1104416x^{34} + 613699x^{33} + 1378515x^{32} + 108992x^{31} + 95427x^{30} + 329078x^{29} + 86471x^{28} + 228443x^{27} + 395171x^{26} + 62079x^{25} + 1633970x^{24} + 379821x^{23} + 1501801x^{22} + 1249926x^{21} + 616403x^{20} + 1137937x^{19} + 1001808x^{18} + 883357x^{17} + 807358x^{16} + 1538605x^{15} + 1046489x^{14} + 969902x^{13} + 1160416x^{12} + 1109343x^{11} + 1454517x^{10} + 483212x^9 + 1314862x^8 + 565414x^7 + 875354x^6 + 128579x^5 + 915543x^4 + 1574629x^3 + 1309763x^2 + 450382x + 1197347$$

Similarly, calculates polynomial $$\hat{z}\_C(x)$$ such that $$\hat{z}\_C(x)\in \mathbb{F}^{<|\mathbb{H}|+b}\[x]$$ that agree with $$z\_C(x)$$ on $$\mathbb{H}$$ that mean $$\hat{z}\_C(1)=...=\hat{z}\_C(\omega^{32})=0$$, $$\hat{z}\_C(\omega^{33})=12$$ , $$\hat{z}*C(\omega^{34})=22$$, $$\hat{z}*C(\omega^{35})=32$$ and $$\hat{z}*C(\omega^{36})=84$$ and also $$b=2$$ random locations $$\hat{z}*C(3)=3$$ and $$\hat{z}*C(4)=4$$. So, $$\hat{z}*C(x)=12L*{34}(x)+22L*{35}(x)+32L*{36}(x)+84L*{37}(x)+3L*{38}(x)+4L*{39}(x)=$$\
$$411621x^{38 }+ 1135315x^{37} + 1041565x^{36} + 1267429x^{35} + 702672x^{34} + 1544342x^{33} + 1289612x^{32 }+ 70607x^{31} + 1084584x^{30} + 418963x^{29} + 406701x^{28} + 1248319x^{27} + 849425x^{26} + 1422362x^{25} + 1308156x^{24} + 475901x^{23} + 287621x^{22} + 1484809x^{21} + 835172x^{20} + 192385x^{19} + 1001678x^{18} + 1374779x^{17} + 456462x^{16} + 64473x^{15} + 948391x^{14} + 258251x^{13} + 1536835x^{12} + 1216001x^{11} + 27794x^{10} + 1666393x^9 + 1197528x^8 + 118632x^7 + 1415153x^6 + 1478306x^5 + 227473x^4 + 521470x^3 + 1270694x^2 + 856256x + 452290$$

The Prover 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]={\omega^{33},\omega^{34},\omega^{35},\omega^{36}}\to \mathbb{F}$$

$$\bar{W}(h)=\frac{W(h)-\hat{X}(h)}{v\_{\mathbb{H}\[\leq |X|+1]}(h)},\hspace{1mm}h\in{w^{33},w^{34}}$$

$$\bar{W}(h)=\frac{Y(h)-\hat{X}(h)}{v\_{\mathbb{H}\[\leq |X|+1]}(h)},\hspace{1mm}h\in{w^{35},w^{36}}$$

and $$v\_{\mathbb{H}\[\leq |X|+1]}(h)$$ is vanishing polynomial on $$\mathbb{H}\[\leq |X|+1]={1,\omega,...,\omega^{32}}$$, therefore $$v\_{\mathbb{H}\[\leq |X|+1]}(h)=(h-1)(h-\omega)...(h-\omega^{32})$$. Also $$\hat{X}(h)$$ is the polynomial such that $$\hat{X}(1)=1$$ and $$\hat{X}(\omega)=7$$, $$\hat{X}(\omega^2)=11$$, $$\hat{X}(\omega^4)=1$$, $$\hat{X}(\omega^6)=1$$, $$\hat{X}(\omega^{10})=2$$, $$\hat{X}(\omega^{19})=7$$, $$\hat{X}(\omega^i)=0$$ for $$i\in{1,...,32}-{1,2,4,6,10,19}$$, therefore $$\hat{X}(x)=1609426x^{32} + 145361x^{31} + 1059045x^{30} + 558036x^{29} + 838324x^{28} + 732837x^{27} + 976113x^{26} + 1264050x^{25} + 1273306x^{24} + 173112x^{23} + 551049x^{22} + 69676x^{21} + 904932x^{20} + 1127571x^{19} + 546454x^{18} + 227060x^{17} + 368192x^{16} + 552618x^{15} + 1053934x^{14} + 1614372x^{13} + 339618x^{12} + 826651x^{11} + 852561x^{10} + 649028x^9 + 350872x^8 + 760561x^7 + 761015x^6 + 1256843x^5 + 750361x^4 + 868552x^3 + 1432254x^2 + 741241x + 1618112$$Therefore,

$$\hat{w}(x)=379888x^5 + 1037474x^4 + 1130442x^3 + 55492x^2 + 1492556x + 1299562$$

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)$$. Since $$\hat{z}\_A(x)\hat{z}*B(x)-\hat{z}*C(x)=1014490x^{76} + 91446x^{75} + 1040499x^{74} + 247239x^{73} + 340507x^{72} + 198429x^{71} + 1248016x^{70} + 1122641x^{69} + 1067491x^{68} + 1268939x^{67} + 926637x^{66} + 270789x^{65} + 35309x^{64 }+ 1572201x^{63} + 1392158x^{62} + 1197501x^{61} + 1269609x^{60} + 225080x^{59} + 236470x^{58} + 1171130x^{57} + 988x^{56} + 1073543x^{55} + 1461879x^{54} + 1490686x^{53} + 314250x^{52} + 974543x^{51} + 772228x^{50} + 1301945x^{49} + 1393100x^{48} + 842325x^{47} + 148723x^{46} + 632720x^{45} + 1426141x^{44} + 178796x^{43} + 1520995x^{42} + 913282x^{41} + 716999x^{40 }+ 1535044x^{39} + 506626x^{38} + 188456x^{37} + 1431082x^{36} + 1337814x^{35} + 1479892x^{34 }+ 430305x^{33} + 555680x^{32} + 610830x^{31} + 409382x^{30} + 751684x^{29} + 1407532x^{28 }+ 1643012x^{27} + 106120x^{26} + 286163x^{25} + 480820x^{24} + 408712x^{23} + 1453241x^{22} + 1441851x^{21} + 507191x^{20} + 1677333x^{19} + 604778x^{18} + 216442x^{17} + 187635x^{16} + 1364071x^{15} + 703778x^{14 }+ 906093x^{13} + 376376x^{12} + 285221x^{11} + 835996x^{10} + 1529598x^9 + 1045601x^8 + 252180x^7 + 1499525x^6 + 157326x^5 + 765039x^4 + 961322x^3 + 807108x^2 + 1080249x + 449366$$\
and $$v*{\mathbb{H}}(x)=\prod*{h\in\mathbb{H}}(x-h)=x^{37}+1$$, The Prover finds\
$$h\_0(x)=1014490x^{39} + 91446x^{38} + 1040499x^{37} + 247239x^{36} + 340507x^{35} + 198429x^{34} + 1248016x^{33 }+ 1122641x^{32} + 1067491x^{31} + 1268939x^{30} + 926637x^{29} + 270789x^{28} + 35309x^{27} + 1572201x^{26} + 1392158x^{25} + 1197501x^{24} + 1269609x^{23} + 225080x^{22} + 236470x^{21} + 1171130x^{20 }+ 988x^{19} + 1073543x^{18} + 1461879x^{17} + 1490686x^{16 }+ 314250x^{15} + 974543x^{14} + 772228x^{13} + 1301945x^{12} + 1393100x^{11} + 842325x^{10} + 148723x^9 + 632720x^8 + 1426141x^7 + 178796x^6 + 1520995x^5 + 913282x^4 + 716999x^3 + 871213x^2 + 598072x + 1228955$$

4- The Prover samples a fully random $$s(x)\in\mathbb{F}^{<2|\mathbb{H}|+b-1=71}\[x]$$. Consider $$s(x)=7x^{10}+100x^8+2x^3+1$$. Then, the Prover computes sum $$\sigma\_1=\sum\_{k\in \mathbb{H}}s(k)=4255$$\\

5- The Prover sends $$Com\_{AHP\_X}^2=\sum\_{i=0}^{deg\_{\hat{W}(x)}}\hat{w}*i\hspace{1mm}ck(i)=1058742$$,\
$$Com*{AHP\_X}^{3}=\sum\_{i=0}^{deg\_{\hat{z}*A(x)}}\hat{z}*{A\_i}ck(i)=1287898$$, $$Com\_{AHP\_X}^{4}=\sum\_{i=0}^{deg\_{\hat{z}*B(x)}}\hat{z}*{B\_i}ck(i)= 937880$$,\
$$Com\_{AHP\_X}^{5}=\sum\_{i=0}^{deg\_{\hat{z}*C(x)}}\hat{z}*{C\_i}ck(i)=1199255$$, $$Com\_{AHP\_X}^{6}=\sum\_{i=0}^{deg\_{h\_0(x)}}h\_{0\_i}ck(i)= 255923$$ and\
$$Com\_{AHP\_X}^{7}=\sum\_{i=0}^{deg\_{s(x)}}s\_i\hspace{1mm}ck(i)=490704$$.

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))$$, $$\eta\_A=hash(s(1))$$, $$\eta\_B=hash(s(2))$$, $$\eta\_C=hash(s(3))$$. Let $$\alpha=10$$, $$\eta\_A=2$$, $$\eta\_B=30$$ and $$\eta\_C=100$$.

7- The Prover finds polynomials $$g\_1(x)$$ and $$h\_1(x)$$ such 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 $$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^{37}-y^{37}}{x-y}$$ . Also $$r\_M(x,y)=\sum\_{k\in \mathbb{H}}r(x,k)\hat{M}(k,y)$$ for $$M\in {A,B,C}$$.

Now, since $$\sum\_M\eta\_M\hat{z}\_M(x)=\eta\_A\hat{z}\_A(x)+\eta\_B\hat{z}\_B(x)+\eta\_C\hat{z} \_C(x)$$and $$r(\alpha,x)=r(10,x)=\frac{10^{37}-x^{37}}{10-x}$$, so the second term of the left of equation $$(1)$$ is $$r(\alpha,x)\sum\_M\eta\_M\hat{z}\_M(x)=1254201x^{74} + 951966x^{73} + 113589x^{72} + 498811x^{71} + 1098223x^{70} + 623670x^{69} + 506831x^{68} + 1427824x^{67 }+ 170669x^{66} + 1564892x^{65} + 456048x^{64} + 783754x^{63} + 911524x^{62} + 1557714x^{61} + 1027780x^{60} + 1574033x^{59} + 142618x^{58} + 1400297x^{57} + 282168x^{56} + 1384750x^{55} + 197195x^{54} + 1663151x^{53 }+ 118626x^{52} + 518880x^{51} + 143413x^{50 }+ 254527x^{49} + 1480415x^{48} + 1393054x^{47} + 890674x^{46} + 1601841x^{45} + 234410x^{44} + 600518x^{43 }+ 570901x^{42} + 601977x^{41} + 1491129x^{40} + 827957x^{39} + 851643x^{38} + 345650x^{37} + 347482x^{36} + 330919x^{35} + 857128x^{34} + 883439x^{33} + 1523863x^{32} + 1228455x^{31} + 1360072x^{30} + 1477512x^{29} + 1221548x^{28} + 1641696x^{27} + 92216x^{26} + 1513130x^{25} + 606487x^{24} + 1664443x^{23} + 814464x^{22} + 1431125x^{21} + 1550828x^{20} + 646554x^{19} + 1535880x^{18} + 1048877x^{17} + 1232429x^{16} + 1017318x^{15} + 1153784x^{14} + 1454648x^{13} + 885815x^{12} + 852481x^{11} + 26667x^{10} + 127017x^9 + 957446x^8 + 137943x^7 + 729959x^6 + 1418974x^5 + 1383097x^4 + 1529852x^3 + 637155x^2 + 1142934x + 830201$$

Also, $$\hat{z}(x)=\hat{W}(x)v\_{\mathbb{H}\[\leq |X|+1]}(x)+\hat{X}(x)=379888x^{38} + 554258x^{37} + 249703x^{36} + 693580x^{35} + 237592x^{34} + 1271221x^{33} + 247551x^{32} + 1512810x^{31} + 759758x^{30} + 1072537x^{29} + 253693x^{28} + 25719x^{27} + 1222503x^{26} + 1627866x^{25 }+ 1384100x^{24} + 548181x^{23} + 649897x^{22} + 258321x^{21} + 1617844x^{20} + 354870x^{19} + 637040x^{18 }+ 767176x^{17} + 1615730x^{16} + 1214248x^{15} + 326060x^{14} + 1213865x^{13} + 1172680x^{12} + 65141x^{11} + 118953x^{10} + 478016x^9 + 1051458x^8 + 1675614x^7 + 949880x^6 + 108738x^5 + 1497503x^4 + 486095x^3 + 958242x^2 + 1278901x + 1350868$$ that agree with $$z$$ on $$\mathbb{H}$$. Also, $$r\_A(10,x)=\sum\_{k\in \mathbb{H}}r(10,k)\hat{A}(k,x)$$ where $$\hat{A}(x,y)$$ is a polynomial such that $$\hat{A}(\omega^{33},1)=1$$, $$\hat{A}(\omega^{34},\omega^2)=1$$, $$\hat{A}(\omega^{35},1)=1$$, $$\hat{A}(\omega^{36},\omega^{33})=1$$, and $$\hat{A}(x,y)=0$$ for the rest of points in $$\mathbb{H}\times\mathbb{H}$$. So, $$\hat{A}(x,y)$$ is a bivariate polynomial that passes from these 1369 points. 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\_A}(k)=\sum*{k\in \mathbb{K}}\frac{x^{37}-\hat{row}*{AHP\_A}(k)^{37}}{x-\hat{row}*{AHP\_A}(k)}\frac{y^{37}-\hat{col}*{AHP\_B}(k)^{37}}{y-\hat{col}*{AHP\_A}(k)}\hat{val}*{AHP\_A}(k)$$\
So $$r\_A(10,x)=\sum*{k\in\mathbb{H}}r(10,k)\hat{A}(k,x)=535865x^{36 }+ 426856x^{35} + 475596x^{34} + 458091x^{33} + 1506591x^{32} + 1335527x^{31} + 552969x^{30} + 1601654x^{29} + 745399x^{28} + 1280385x^{27} + 671303x^{26} + 934855x^{25} + 898910x^{24} + 1158968x^{23} + 641386x^{22} + 323675x^{21} + 1562721x^{20} + 775117x^{19} + 327316x^{18} + 1420073x^{17} + 1643380x^{16} + 1205782x^{15} + 1516893x^{14} + 985877x^{13} + 986845x^{12} + 1246093x^{11} + 815873x^{10} + 1148146x^9 + 734510x^8 + 147988x^7 + 284318x^6 + 1525335x^5 + 891280x^4 + 360740x^3 + 448902x^2 + 980633x + 1111155$$ where

Now, calculates $$\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)=\sum\_{k\in \mathbb{K}}\frac{x^{37}-\hat{row}*{AHP\_B}(k)^{37}}{x-\hat{row}*{AHP\_B}(k)}\frac{y^{37}-\hat{col}*{AHP\_B}(k)^{37}}{y-\hat{col}*{AHP\_B}(k)}\hat{val}*{AHP\_B}(k)$$\
So, $$r\_B(10,x)=\sum*{k\in\mathbb{H}}r(10,k)\hat{B}(k,x)=$$\
$$1620326x^{36} + 1066668x^{35} + 96125x^{34} + 603567x^{33} + 558242x^{32} + 351383x^{31} + 1220164x^{30} + 1113220x^{29} + 511617x^{28} + 218379x^{27} + 543077x^{26} + 178907x^{25} + 1329682x^{24} + 58568x^{23} + 1146533x^{22} + 948877x^{21} + 45785x^{20} + 1231010x^{19} + 398692x^{18} + 1334094x^{17} + 506342x^{16} + 28965x^{15} + 158706x^{14} + 657240x^{13} + 506136x^{12} + 484833x^{11} + 713105x^{10} + 498148x^9 + 1237146x^8 + 95520x^7 + 1145960x^6 + 1517154x^5 + 414812x^4 + 1548405x^3 + 614052x^2 + 1634786x + 1454002$$

Now, calculates $$\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)=\sum\_{k\in \mathbb{K}}\frac{x^{37}-\hat{row}^{37}*{AHP\_C}(k)}{x-\hat{row}*{AHP\_C}(k)}\frac{y^{37}-\hat{col}^{37}*{AHP\_C}(k)}{y-\hat{col}*{AHP\_C}(k)}\hat{val}*{AHP\_C}(k)$$\
So, $$r\_C(10,x)=\sum*{k\in\mathbb{H}}r(10,k)\hat{C}(k,x)=$$\
$$564874x^{36 }+ 158712x^{35} + 1068273x^{34} + 705225x^{33} + 585350x^{32} + 1605845x^{31} + 41353x^{30} + 177119x^{29} + 934488x^{28} + 418387x^{27} + 217275x^{26} + 277881x^{25} + 544871x^{24} + 906984x^{23 }+ 1088639x^{22} + 730223x^{21} + 114465x^{20} + 205097x^{19} + 1381442x^{18} + 366209x^{17} + 1014467x^{16} + 30473x^{15} + 1671297x^{14 }+ 539462x^{13} + 45399x^{12} + 1575452x^{11} + 676582x^{10} + 1015618x^9 + 1425352x^8 + 26812x^7 + 661279x^6 + 93349x^5 + 1038786x^4 + 203161x^3 + 277282x^2 + 1676177x + 1111155$$

Therefore, the third term of the left of equation $$(1)$$ is

$$(\sum\_M \eta\_M r\_M(\alpha,x))\hat{z}(x)=(2r\_A(10,x)+30r\_B(10,x)+100r\_C(10,x))\hat{z}(x)$$

Therefore, the left of equation $$(1)$$ is $$s(x)+r(\alpha,x)\sum\_M \eta\_M \hat{z}M(x)-(\sum\_M \eta\_M r\_M(\alpha,x))\hat{z}(x)=$$

Now, the Prover finds polynomials $$g\_1(x)$$ and $$h\_1(x)$$ such that $$h\_1(x)v\_{\mathbb{H}}(x)+xg\_1(x)+\frac{\sigma\_1}{|\mathbb{H}|}=$$

Therefore, the Prover finds polynomials $$g\_1(x)$$ and $$h\_1(x)$$

$$g\_1(x)=1399127x^{35} + 234054x^{34} + 551311x^{33} + 1464283x^{32} + 1033988x^{31} + 1393070x^{30} + 1584021x^{29} + 262549x^{28} + 468851x^{27} + 524434x^{26 }+ 730124x^{25} + 1548291x^{24} + 347787x^{23} + 1420568x^{22} + 686369x^{21} + 1104796x^{20 }+ 1652093x^{19} + 186165x^{18} + 1119820x^{17} + 336318x^{16} + 1203175x^{15} + 360741x^{14} + 187190x^{13} + 521109x^{12} + 284740x^{11} + 1422180x^{10} + 475884x^9 + 1047600x^8 + 1225116x^7 + 1150001x^6 + 290466x^5 + 829975x^4 + 1519190x^3 + 1077679x^2 + 852032x + 1610672$$

$$h\_1(x)=560656x^{37 }+ 60831x^{36} + 218428x^{35} + 666069x^{34} + 1029772x^{33} + 758630x^{32} + 1446724x^{31} + 1077267x^{30} + 1190239x^{29} + 1586425x^{28} + 37621x^{27} + 1029983x^{26} + 1501234x^{25} + 721528x^{24} + 980207x^{23} + 1104424x^{22} + 980405x^{21} + 722662x^{20} + 459859x^{19} + 908256x^{18} + 1595013x^{17} + 1492468x^{16} + 546404x^{15} + 734174x^{14} + 405471x^{13} + 1348410x^{12} + 339556x^{11} + 1274900x^{10} + 676949x^9 + 1524717x^8 + 735990x^7 + 1659120x^6 + 1225339x^5 + 236096x^4 + 925377x^3 + 849078x^2 + 589799x + 404586$$

The Prover sends,\
$$Com\_{AHP\_X}^{8}=\sum\_{i=0}^{deg\_{g\_1(x)}}g\_{1\_i}ck(i)=704382$$ and $$Com\_{AHP\_X}^{9}=\sum\_{i=0}^{deg\_{h\_1(x)}}h\_{1\_i}ck(i)=1412858$$ 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))$$). Let $$\beta\_1=22$$.

9- The Prover calculates $$\sigma\_2=\sum\_{k\in\mathbb{H}}r(\alpha,k)\sum\_{M}\eta\_M\hat{M}(k,\beta\_1)=378950$$ .

Then, the Prover finds $$g\_2(x)$$ and $$h\_2(x)$$ such 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}|}$$

where $$r(\alpha,x)\sum\_M\eta\_M \hat{M}(x,\beta\_1)=r(10,x)(2\hat{A}(x,22)+30\hat{B}(x,22)+100\hat{C}(x,22))$$

$$=139x^{72} + 1209936x^{71} + 190587x^{70} + 504890x^{69} + 1288979x^{68} + 1468677x^{67} + 1440246x^{66} + 522806x^{65} + 1359862x^{64} + 80868x^{63 }+ 1206390x^{62} + 1046755x^{61} + 385478x^{60} + 565523x^{59} + 1148470x^{58} + 1201845x^{57} + 1116465x^{56} + 815461x^{55} + 1518339x^{54} + 1552482x^{53} + 226534x^{52} + 1483660x^{51} + 1193665x^{50} + 861411x^{49} + 598582x^{48} + 1195837x^{47} + 528169x^{46} + 785026x^{45 }+ 1054528x^{44 }+ 542637x^{43} + 1028077x^{42} + 1467957x^{41} + 539089x^{40 }+ 1014793x^{39} + 1213976x^{38} + 1577305x^{37} + 1642895x^{36} + 90614x^{35} + 1441442x^{34 }+ 12666x^{33} + 501190x^{32} + 200147x^{31 }+ 597144x^{30} + 1424505x^{29} + 783489x^{28} + 1343873x^{27} + 202672x^{26} + 1040663x^{25} + 540033x^{24} + 1541994x^{23} + 964649x^{22} + 1064430x^{21} + 1392111x^{20} + 366564x^{19} + 315215x^{18} + 1400207x^{17} + 1618951x^{16} + 95617x^{15} + 1118036x^{14} + 1344820x^{13} + 526493x^{12} + 1160359x^{11} + 97560x^{10} + 465203x^9 + 865325x^8 + 1087974x^7 + 1483111x^6 + 808894x^5 + 844762x^4 + 1305256x^3 + 751081x^2 + 786432x + 292698$$

Hence, the Prover finds $$g\_2(x)=1642895x^{35} + 90753x^{34} + 973057x^{33} + 203253x^{32} + 1006080x^{31} + 1489126x^{30} + 387500x^{29} + 1186430x^{28} + 1306295x^{27} + 1025414x^{26} + 283540x^{25} + 568732x^{24} + 1586788x^{23} + 249151x^{22} + 1530172x^{21} + 534579x^{20} + 915635x^{19} + 1483029x^{18} + 1130676x^{17} + 1240225x^{16} + 1493112x^{15} + 322151x^{14} + 923375x^{13} + 860164x^{12} + 1387904x^{11} + 80620x^{10} + 1293397x^9 + 993372x^8 + 1650351x^7 + 464181x^6 + 347427x^5 + 158650x^4 + 634398x^3 + 166024x^2 + 87553x + 322087$$\
\
and

$$h\_2(x)=139x^{35} + 1209936x^{34} + 190587x^{33} + 504890x^{32} + 1288979x^{31} + 1468677x^{30} + 1440246x^{29 }+ 522806x^{28} + 1359862x^{27} + 80868x^{26} + 1206390x^{25} + 1046755x^{24} + 385478x^{23} + 565523x^{22} + 1148470x^{21} + 1201845x^{20} + 1116465x^{19} + 815461x^{18} + 1518339x^{17} + 1552482x^{16} + 226534x^{15} + 1483660x^{14} + 1193665x^{13} + 861411x^{12} + 598582x^{11} + 1195837x^{10} + 528169x^9 + 785026x^8 + 1054528x^7 + 542637x^6 + 1028077x^5 + 1467957x^4 + 539089x^3 + 1014793x^2 + 1213976x + 1577305$$

\
The Prover sends , $$Com\_{AHP\_X}^{10}=\sum\_{i=0}^{deg\_{g\_2(x)}}g\_{2\_i}ck(i)=1380487$$ and\
$$Com\_{AHP\_X}^{11}=\sum\_{i=0}^{deg\_{h\_2(x)}}h\_{2\_i}ck(i)=259428$$ 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. For example $$\beta\_2=80$$.

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))})=1162153$$ . Then, the Prover finds polynomials $$g\_3(x)$$ and $$h\_3(x)$$ such 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))$$\
$$=1296906x^{35} + 1631745x^{34} + 612500x^{33} + 526824x^{32} + 42462x^{31} + 818776x^{30} + 1402893x^{29} + 949566x^{28} + 616603x^{27} + 986171x^{26} + 460008x^{25} + 1582261x^{24} + 1077886x^{23} + 595820x^{22} + 1014838x^{21} + 1426636x^{20} + 118993x^{19} + 1092349x^{18} + 2468x^{17} + 425912x^{16} + 662080x^{15} + 665736x^{14} + 1149617x^{13} + 1658716x^{12} + 817522x^{11} + 616119x^{10} + 1252653x^9 + 1566732x^8 + 839662x^7 + 1069376x^6 + 1211198x^5 + 1604604x^4 + 1470873x^3 + 289754x^2 + 317183x + 1271979$$\
and $$b(x)=\prod\_{M\in{A,B,C}}(\beta\_2-\hat{row}*{AHP\_M}(x))(\beta\_1-\hat{col}*{AHP\_M}(x))=$$$$916454x^{42} + 1260873x^{41} + 570130x^{40} + 932807x^{39} + 205150x^{38} + 1351730x^{37} + 1505570x^{36} + 119616x^{35} + 661575x^{34} + 1229440x^{33} + 1192933x^{32} + 11364x^{31} + 164433x^{30} + 929209x^{29} + 661767x^{28} + 82832x^{27} + 968909x^{26} + 553623x^{25} + 282790x^{24} + 780101x^{23} + 444918x^{22} + 1247671x^{21} + 553487x^{20} + 1667118x^{19} + 498300x^{18} + 338714x^{17} + 1340147x^{16} + 917454x^{15} + 1066984x^{14} + 1408571x^{13} + 566713x^{12} + 741597x^{11} + 828088x^{10} + 727848x^9 + 1313411x^8 + 1457306x^7 + 827199x^6 + 569669x^5 + 24811x^4 + 1103826x^3 + 579226x^2 + 1603084x + 624045$$

Therefore

$$g\_3(x)=423903x^6 + 1432943x^5 + 936488x^4 + 482019x^3 + 31948x^2 + 604913x + 651087$$\
and

$$h\_3(x)=75192x^{41} + 1425410x^{40} + 366361x^{39} + 15942x^{38} + 443512x^{37} + 1636377x^{36} + 1557044x^{35} + 746441x^{34} + 826820x^{33} + 1513071x^{32} + 1120754x^{31} + 901651x^{30} + 374419x^{29} + 278754x^{28} + 371149x^{27} + 659171x^{26} + 370586x^{25} + 494858x^{24} + 79718x^{23} + 229682x^{22} + 504490x^{21} + 1552618x^{20} + 1525264x^{19} + 146174x^{18} + 296224x^{17} + 968029x^{16} + 291466x^{15} + 934467x^{14} + 59156x^{13} + 1627926x^{12} + 1581132x^{11} + 243139x^{10} + 808890x^9 + 555919x^8 + 1106775x^7 + 417461x^6 + 990811x^5 + 591777x^4 + 284092x^3 + 1261059x^2 + 1522666x + 998008$$

The Prover sends , $$Com\_{AHP\_X}^{12}=\sum\_{i=0}^{deg\_{g\_3(x)}}g\_{3\_i}ck(i)=1418032$$ and $$Com\_{AHP\_X}^{13}=\sum\_{i=0}^{deg\_{h\_3(x)}}h\_{3\_i}ck(i)=1079279$$\
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)$$.

12- The Prover sends $$\pi\_{AHP}^1=4255$$, $$\pi\_{AHP}^2=(1299562, 1492556, 55492, 1130442,1037474, 379888)$$, $$\pi\_{AHP}^3=( 692083, 703489,1216744, 1167473, 321181, 1322746, 1506753, 1498609, 1459683,604857, 482390, ...)$$$$\pi\_{AHP}^4=(1197347,450382,1309763,1574629,915543,128579,875354,565414,1314862,483212, 1454517,$$\
$$1501801,379821,1633970,62079,395171,228443,86471,329078,95427, 108992,1378515,613699,$$\
$$1104416,346226,238219,1433536,161089)$$

$$\pi^5\_{AHP}=$$\
$$(452290,856256,1270694,521470,227473,1478306,1415153,118632,1197528,1666393, 27794,$$ $$1484809,287621,475901,1308156,1422362,849425,1248319,406701,418963, 1084584,70607,$$\
$$,1289612,1544342,702672,1267429,1041565,1135315,411621)$$.

$$\pi\_{AHP}^6=$$\
$$(1228955,598072,871213,716999,913282,1520995,178796,1426141,632720,148723,842325,$$\
$$1393100,1301945,772228, 974543,1490686,1461879,1073543,988,1171130,236470, 225080,$$\
$$1269609,1197501,1392158,1572201,35309,270789,926637,1268939,926637,1268939,$$\
$$1067491,1122641,1248016,198429,340507,247239,1040499,91446,1014490)$$\
and

$$\pi\_{AHP}^7=$$<br>

to the Verifier that are value of $$\sigma\_1$$, coefficients of polynomials $$\hat{W}(x)$$, $$\hat{z}\_A(x)$$, $$\hat{z}\_B(x)$$, $$\hat{z}\_C(x)$$,$$h\_0(x)$$ and $$s(x)$$, respectively.

13-The Prover sends\
$$\pi\_{AHP}^8=$$

and\
$$\pi\_{AHP}^{9}=$$\
to the Verifier that are coefficients of polynomials $$g\_1(x)$$ and $$h\_1(x)$$, respectively.

14-The Prover sends $$\pi\_{AHP}^{10}=378950$$, $$\pi\_{AHP}^{11}=()$$ and $$\pi\_{AHP}^{12}=()$$ that are value of $$\sigma\_2$$ and coefficients of polynomials $$g\_2(x)$$ and $$h\_2(x)$$, respectively.

15- The Prover sends $$\pi\_{AHP}^{13}=1162153$$, $$\pi\_{AHP}^{14}=()$$ and $$\pi\_{AHP}^{15}=()$$ that are value of $$\sigma\_3$$ and coefficients of polynomials $$g\_3(x)$$ and $$h\_3(x)$$, respectively.

16- The Prover chooses random values $$\eta\_{\hat{w}}$$, $$\eta\_{\hat{z}*A}$$, $$\eta*{\hat{z}*B}$$, $$\eta*{\hat{z}*C}$$, $$\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}$$. For example, $$\eta\_{\hat{w}}=1$$, $$\eta\_{\hat{z}*A}=4$$, $$\eta*{\hat{z}*B}=10$$, $$\eta*{\hat{z}*C}=8$$, $$\eta*{h\_0}=32$$, $$\eta\_s=45$$, $$\eta\_{g\_1}=92$$, $$\eta\_{h\_1}=11$$, $$\eta\_{g\_2}=1$$, $$\eta\_{h\_2}=5$$, $$\eta\_{g\_3}=25$$ and $$\eta\_{h\_3}=63$$.

17- The Prover calculates the linear combination$$p(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)$$.

The Prover obtains\
$$p(x)=1380454x^{41} + 849817x^{40} + 159830x^{39} + 1591067x^{38} + 1280259x^{37} + 129759x^{36} + 1642325x^{35 }+ 1231259x^{34} + 1091449x^{33} + 1071613x^{32} + 608376x^{31} + 1671687x^{30} + 1634568x^{29} + 794532x^{28} + 450142x^{27} + 1460185x^{26} + 849620x^{25} + 1337323x^{24} + 1094067x^{23} + 1046543x^{22} + 1173097x^{21} + 922535x^{20} + 166446x^{19} + 1212718x^{18} + 116006x^{17} + 657804x^{16} + 39944x^{15} + 289261x^{14} + 209333x^{13} + 1276111x^{12} + 363314x^{11} + 103604x^{10} + 554869x^9 + 513127x^8 + 586495x^7 + 1263408x^6 + 1598951x^5 + 20405x^4 + 276795x^3 + 1644690x^2 + 238507x + 242842$$

18- The Prover calculates $$p(x)$$ in $$x=x'$$ (value of $$x'$$ is received from the Verifier), then puts it in $$\pi\_{AHP}^{16}$$ . Therefore $$\pi\_{AHP}^{16}=p(x')=y'$$. For example, if $$x'=2$$, then $$\pi\_{AHP}^{16}=p(2)=627433$$.

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 builds polynomial\
$$q(x)=\frac{p(x)-y'}{x-x'}=$$\
$$1380454x^{40} + 254083x^{39} + 667996x^{38} + 1248738x^{37} + 421093x^{36} + 971945x^{35} + 229573x^{34} + 12084x^{33} + 1115617x^{32} + 1624526x^{31} + 500786x^{30} + 994938x^{29} + 267802x^{28 }+ 1330136x^{27} + 1432093x^{26} + 967729x^{25} + 1106757x^{24} + 194195x^{23} + 1482457x^{22} + 654815x^{21} + 804406x^{20} + 853026x^{19} + 194177x^{18} + 1601072x^{17} + 1639829x^{16} + 580820x^{15} + 1201584x^{14} + 1014108x^{13} + 559228x^{12 }+ 716246x^{11} + 117485x^{10} + 338574x^9 + 1232017x^8 + 1298840x^7 + 1505854x^6 + 918474x^5 + 79257x^4 + 178919x^3 + 634633x^2 + 1235635x + 1031456$$\
and calculates $$\pi\_{AHP}^{17}=gq(\tau)$$ by using $$ck$$ as following:\
$$\pi\_{AHP}^{17}=\sum\_{i=0}^{deg\_{q(x)}}q\_i\hspace{1mm}ck(i)=588602$$ where $$q\_i$$ is the coefficient of $$x^i$$ of $$q(x)$$.

```
{
    "commitmentId": 64-bit,
    "class": 32-bit Integer,
    "input": 4
    "output": 82    
       
    "P_AHP1": 4255
    "P_AHP2": [1299562,1492556,55492,1130442,1037474,379888],
    "P_AHP3": [692083,703489,1216744,1167473,321181,1322746,1506753,1498609,1459683,604857,
            482390,1448628,44719,1319736,654101,216721,446434,933185,1070791,1124687,
            876189,144534,607746,561332,150588,1374718,166128,1080203,981227,897917,
            222647,1406132,88593,705790,900649,766942,904146,1530559,287049],
    "P_AHP4": [1197347,450382,1309763,1574629,915543,128579,875354,565414,1314862,483212,
               1454517,1109343,1160416,969902,1046489,1538605,807358,883357,1001808,1137937,
               616403,1249926,1501801,379821,1633970,62079,395171,228443,86471,329078,95427,
               108992,1378515,613699,1104416,346226,238219,1433536,161089],  
    "P_AHP5": [452290,856256,1270694,521470,227473,1478306,1415153,118632,1197528,1666393,
               27794,1216001,1536835,258251,948391,64473,456462,1374779,1001678,192385,
               835172,1484809,287621,475901,1308156,1422362,849425,1248319,406701,418963,
               1084584,70607,1289612,1544342,702672,1267429,1041565,1135315,411621],

    "P_AHP6": [1228955,598072,871213,716999,913282,
               1520995,178796,1426141,632720,148723,842325,1393100,1301945,772228,
               974543,1490686,1461879,1073543,988,1171130,236470,225080,1269609,
               1197501,1392158,1572201,35309,270789,926637,1268939,926637,1268939
               1067491,1122641,1248016,198429,340507,247239,1040499,91446,1014490],
    "P_AHP7": [],
    "P_AHP8": [],
    "P_AHP9": [],
    "P_AHP10": 
    "P_AHP11": [],
    "P_AHP12": [],
    "P_AHP13": 
    "P_AHP14": [],
    "P_AHP15": [],
    "P_AHP16": 
    "P_AHP17": 
    
    "Com_AHP1_x": [7,11,0,1,0,1,0,0,0,2,0,0,0,0,0,0,0,0,7,0,0,0,0,0,0,0,0,0,0,0,0,0]
    "Com_AHP2_x": 1058742,
    "Com_AHP3_x": 1287898,
    "Com_AHP4_x": 937880,
    "Com_AHP5_x": 1199255,
    "Com_AHP6_x": 255923,  
    "Com_AHP7_x": 490704,
    "Com_AHP8_x": 704382,
    "Com_AHP9_x": 1412858,
    "Com_AHP10_x": 1380487,
    "Com_AHP11_x": 259428,
    "Com_AHP12_x": 1418032,
    "Com_AHP13_x": 1079279
}
```

##


---

# Agent Instructions: 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:

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

The question should be specific, self-contained, and written in natural language.
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.