> 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-3-example-2.md). # 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}^{\|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=$$
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 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-3-example-2.md?ask=&goal= ``` `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.