docs
  • README
  • Browsing the Fides Innova ZKP Network
  • Connecting Your MetaMask to the Network
  • Full Node
  • Introduction
  • Mobile App
  • Publishing Service Contracts on the Fides Innova Blockchain
  • Web App (User Panel, Admin Panel)
  • Fides Zero-Knowledge Proof (ZKP) Algorithm
    • 1- Setup Phase
      • 1- Setup Phase
      • Example 1
      • Example 2
    • 2-commitment-phase
      • 2- Commitment Phase
      • Example 1
      • Example 2
    • 3- Proof Generation Phase
      • 3- Proof Generation Phase
      • Example 1
      • Example 2
    • 4- Proof Verification Phase
      • 4- Proof Verification Phase
      • Example 1
      • Example 2
    • 5-target-architecture
      • Target architecture - RISC-V RV32IM
      • Target architecture - ARMv6-M Cortex-M0 32-bit ARM - RaspberryPi Pico
      • Target architecture - Cortex-A53 - for Siemens SIMATIC IOT2050
  • Tech Stack
    • Message Queuing Telemetry Transport (MQTT) protocol
    • Service Contract
    • Service Market
    • ZKP-enabled JavaScript Execution
  • ZKP and IoT Device Firmware Integration (zk-Device Design)
    • E-Card; a sample zk-Device
      • Installation
      • Instruction Set Architecture (ISA)
      • Mesh IoT Network
      • Reset
Powered by GitBook
On this page
  • 3-1- PFR Proof
  • 3-2- AHP Proof
  • 3-3- Proof Structure
  • 3-4- Proof JSON file format
  1. Fides Zero-Knowledge Proof (ZKP) Algorithm
  2. 3- Proof Generation Phase

3- Proof Generation Phase

In this section, we will review the proof generation phase of the protocol. This phase contains two parts; AHP proof and PFR proof. We also provide an example to clarify the method.

Previous3- Proof Generation PhaseNextExample 1

Last updated 2 months ago

3-1- PFR Proof

Proof(F,H,K,A,B,C)Proof (\mathbb{F}, \mathbb{H}, \mathbb{K}, A, B, C)Proof(F,H,K,A,B,C): This function outputs πPFR=(πPFR1,πPFR2,πPFR3,πPFR4,πPFR5,πPFR6,πPFR7,πPFR8,πPFR9,πPFR10)\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})πPFR​=(πPFR1​,πPFR2​,πPFR3​,πPFR4​,πPFR5​,πPFR6​,πPFR7​,πPFR8​,πPFR9​,πPFR10​).

Note that in this polynomial oracle proof, the Prover wants to prove three following claims: 1.1.1. rowPFRA(x)row_{PFR_A}(x)rowPFRA​​(x) , colPFRA(x)col_{PFR_A}(x)colPFRA​​(x) and valPFRA(x)val_{PFR_A}(x)valPFRA​​(x) is encoding of a t−SLTt-SLTt−SLT matrix. 2.2.2. rowPFRB(x)row_{PFR_B}(x)rowPFRB​​(x) , colPFRB(x)col_{PFR_B}(x)colPFRB​​(x) and valPFRB(x)val_{PFR_B}(x)valPFRB​​(x) is encoding of a t−SLTt-SLTt−SLT matrix. 3.3.3. rowPFRC(x)row_{PFR_C}(x)rowPFRC​​(x) , colPFRC(x)col_{PFR_C}(x)colPFRC​​(x) and valPFRC(x)val_{PFR_C}(x)valPFRC​​(x) is encoding of a t−Diagt-Diagt−Diag matrix.

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

1- To prove strictly lower triangularity of the matrices AAA and BBB, the Prover must prove that log⁡ωrowPFRM(γi)>log⁡ωcolPFRM(γi)\log^{row_{PFR_M}(\gamma^i)}_{\omega}> \log^{col_{PFR_M}(\gamma^i)}_{\omega}logωrowPFRM​​(γi)​>logωcolPFRM​​(γi)​ for i∈i \in i∈{ 0,1,..,m−10,1,..,m-10,1,..,m−1 } and M∈M\inM∈ { A,BA,BA,B } . This does by Discrete−log−comparison−protocolDiscrete-log-comparison-protocolDiscrete−log−comparison−protocol.

2- To prove the first ttt rows of AAA and BBB are all zeros, the Prover must prove that rowPFRM(K)⊆{ωt,ωt+1,...,ωn−1}row_{PFR_M}(\mathbb{K})\subseteq\{\omega^t,\omega^{t+1},...,\omega^{n-1}\}rowPFRM​​(K)⊆{ωt,ωt+1,...,ωn−1}. This does by subsetoverKprotocolsubset\hspace{1mm}over\hspace{1mm} \mathbb{K}\hspace{1mm}protocolsubsetoverKprotocol .

3- To prove the diagonality of the matrix CCC, the Prover must prove that seqK(rowPFRC)=seqK(colPFRC)seq_{\mathbb{K}}(row_{PFR_C})=seq_{\mathbb{K}}(col_{PFR_C})seqK​(rowPFRC​​)=seqK​(colPFRC​​) where seqK(h)=(h(k):k∈K)seq_{\mathbb{K}}(h)=(h(k):k\in\mathbb{K})seqK​(h)=(h(k):k∈K). This does by GeometricsequenceGeometric\hspace{1mm} sequenceGeometricsequence and zerooverKprotocolszero\hspace{1mm}over\hspace{1mm}\mathbb{K}\hspace{1mm}protocolszerooverKprotocols.

4- To prove the first ttt rows of CCC are all zeros, the Prover must prove that there is a vector v∈(F∗)n−tv\in(\mathbb{F^*})^{n-t}v∈(F∗)n−t so that seqK(valPFRC)=v⃗∣∣0⃗seq_{\mathbb{K}}(val_{PFR_C)}=\vec{v}||\vec{0}seqK​(valPFRC​)​=v∣∣0 . This does by GeometricsequenceGeometric\hspace{1mm} sequenceGeometricsequence and zerooverKprotocolszero\hspace{1mm}over\hspace{1mm}\mathbb{K}\hspace{1mm}protocolszerooverKprotocols.

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

3-2- AHP Proof

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

ΠAHP=(ComAHPX,πAHP)\Pi_{AHP}=(Com_{AHP_X},\pi_{AHP})ΠAHP​=(ComAHPX​​,πAHP​)

where ComAHPX=(ComAHPX1,ComAHPX2,ComAHPX3,ComAHPX4,ComAHPX5,ComAHPX6,ComAHPX7,ComAHPX8,ComAHPX9,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,ComAHPX​​=(ComAHPX​1​,ComAHPX​2​,ComAHPX​3​,ComAHPX​4​,ComAHPX​5​,ComAHPX​6​,ComAHPX​7​,ComAHPX​8​,ComAHPX​9​, ComAHPX10,ComAHPX11,ComAHPX12,ComAHPX13)Com_{AHP_X}^{10},Com_{AHP_X}^{11},Com_{AHP_X}^{12},Com_{AHP_X}^{13})ComAHPX​10​,ComAHPX​11​,ComAHPX​12​,ComAHPX​13​)

and πAHP=(πAHP1,πAHP2,πAHP3,πAHP4,πAHP5,πAHP6,πAHP7,πAHP8,πAHP9,πAHP10,πAHP11,πAHP12,πAHP13,πAHP14,πAHP15,πAHP16,πAHP17)\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})πAHP​=(πAHP1​,πAHP2​,πAHP3​,πAHP4​,πAHP5​,πAHP6​,πAHP7​,πAHP8​,πAHP9​,πAHP10​,πAHP11​,πAHP12​,πAHP13​,πAHP14​,πAHP15​,πAHP16​,πAHP17​)

as following:

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)$.

and

17- The Prover builds the linear combination

3-3- Proof Structure

Proof set is

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})

  • 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
}

1- The Prover calculates zA=Azz_A=AzzA​=Az, zB=Bzz_B=BzzB​=Bz, zC=Czz_C=CzzC​=Cz where z=(1,X,W,Y)z=(1,X,W,Y)z=(1,X,W,Y), for input XXX that puts in ComAHPX1Com_{AHP_X}^1ComAHPX​1​.

2- The Prover calculates polynomial zA(x)z_A(x)zA​(x)using indexing zAz_AzA​ by elements of H\mathbb{H}H. Then, calculates polynomial z^A(x)\hat{z}_A(x)z^A​(x) using the polynomial zA(x)z_A(x)zA​(x)such that z^A(x)∈F<∣H∣+b[x]\hat{z}_A(x)\in \mathbb{F}^{<|\mathbb{H}|+b}[x]z^A​(x)∈F<∣H∣+b[x] that agree with zA(x)z_A(x)zA​(x) on H\mathbb{H}H. Note that values of up to bbb locations in this polynomial reveals no information about the witness www provided the locations are in F−H\mathbb{F}-\mathbb{H}F−H. Similarly, calculates polynomial z^B(x)\hat{z}_B(x)z^B​(x) so that z^B(x)∈F<∣H∣+b[x]\hat{z}_B(x)\in \mathbb{F}^{<|\mathbb{H}|+b}[x]z^B​(x)∈F<∣H∣+b[x] that agree with zB(x)z_B(x)zB​(x) on H\mathbb{H}H. Also, calculates polynomial z^C(x)\hat{z}_C(x)z^C​(x) so that z^C(x)∈F<∣H∣+b[x]\hat{z}_C(x)\in \mathbb{F}^{<|\mathbb{H}|+b}[x]z^C​(x)∈F<∣H∣+b[x] that agree with zC(x)z_C(x)zC​(x) on H\mathbb{H}H.

Then, calculates polynomial W^(x)∈F<ng+b[x]\hat{W}(x)\in \mathbb{F}^{<n_g+b}[x]W^(x)∈F<ng​+b[x] that agree with Wˉ(x)\bar{W}(x)Wˉ(x) on H[>∣X∣+1]\mathbb{H}[>|X|+1]H[>∣X∣+1] where

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

Wˉ(h)=W(h)−X^(h)vH[≤∣X∣+1](h)\bar{W}(h)=\frac{W(h)-\hat{X}(h)}{v_{\mathbb{H}[\leq |X|+1]}(h)}Wˉ(h)=vH[≤∣X∣+1]​(h)W(h)−X^(h)​

Note that H[>∣X∣+1]\mathbb{H}[>|X|+1]H[>∣X∣+1] includes the members of H\mathbb{H}H except for the first ∣X∣+1|X|+1∣X∣+1 members. Also, vH[≤∣X∣+1](h)v_{\mathbb{H}[\leq |X|+1]}(h)vH[≤∣X∣+1]​(h) is vanishing polynomial on H[≤∣X∣+1]\mathbb{H}[\leq |X|+1]H[≤∣X∣+1] and X^(h)\hat{X}(h)X^(h) is the polynomial obtained using indexing xxx by elements of H[≤∣X∣+1]\mathbb{H}[\leq |X|+1]H[≤∣X∣+1].

3- The Prover finds polynomial h0(x)h_0(x)h0​(x) so that z^A(x)z^B(x)−z^C(x)=h0(x)vH(x)\hat{z}_A(x)\hat{z}_B(x)-\hat{z}_C(x)=h_0(x)v_{\mathbb{H}}(x)z^A​(x)z^B​(x)−z^C​(x)=h0​(x)vH​(x).

4- The Prover samples a fully random s(x)∈F<2∣H∣+b−1[x]s(x)\in\mathbb{F}^{<2|\mathbb{H}|+b-1}[x]s(x)∈F<2∣H∣+b−1[x] and computes sum σ1=∑k∈Hs(k)\sigma_1=\sum_{k\in \mathbb{H}}s(k)σ1​=∑k∈H​s(k)

6- The Verifier chooses random numbers α\alphaα, ηA\eta_AηA​, ηB\eta_BηB​, ηC\eta_CηC​ and sends them to the Prover. ( Note that the Prover can choose α=hash(s(0)+s(1)+1)\alpha=hash(s(0)+s(1)+1)α=hash(s(0)+s(1)+1), ηA=hash(s(2)+s(3)+2)\eta_A=hash(s(2)+s(3)+2)ηA​=hash(s(2)+s(3)+2), ηB=hash(s(4)+s(5)+3)\eta_B=hash(s(4)+s(5)+3)ηB​=hash(s(4)+s(5)+3), ηC=hash(s(6)+s(7)+4)\eta_C=hash(s(6)+s(7)+4)ηC​=hash(s(6)+s(7)+4).

7- The Prover finds polynomials g1(x)g_1(x)g1​(x) and h1(x)h_1(x)h1​(x) so that

s(x)+r(α,x)∑MηMz^M(x)−(∑MηMrM(α,x))z^(x)=h1(x)vH(x)+xg1(x)+σ1∣H∣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}|}s(x)+r(α,x)∑M​ηM​z^M​(x)−(∑M​ηM​rM​(α,x))z^(x)=h1​(x)vH​(x)+xg1​(x)+∣H∣σ1​​ (1)(1)(1)

where z^(x)=W^(x)vH[≤∣X∣+1](x)+X^(x)\hat{z}(x)=\hat{W}(x)v_{\mathbb{H}[\leq |X|+1]}(x)+\hat{X}(x)z^(x)=W^(x)vH[≤∣X∣+1]​(x)+X^(x) that agree with zzz on H\mathbb{H}H and r(x,y)=uH(x,y)=vH(x)−vH(y)x−yr(x,y)=u_{\mathbb{H}}(x,y)=\frac{v_{\mathbb{H}}(x)-v_{\mathbb{H}}(y)}{x-y}r(x,y)=uH​(x,y)=x−yvH​(x)−vH​(y)​ , vH(x)=∏h∈H(x−h)=x∣H∣−1v_{\mathbb{H}}(x)=\prod_{h\in \mathbb{H}}(x-h)=x^{|\mathbb{H}|}-1vH​(x)=∏h∈H​(x−h)=x∣H∣−1. Therefore r(x,y)=x∣H∣−y∣H∣x−yr(x,y)=\frac{x^{|\mathbb{H}|}-y^{|\mathbb{H}|}}{x-y}r(x,y)=x−yx∣H∣−y∣H∣​. (Note that r(x,y)r(x,y)r(x,y)satisfies two useful algebraic properties. First, the univariate polynomials (r(x,a))a∈H(r(x,a))_{a\in \mathbb{H}}(r(x,a))a∈H​ are linearly independent and r(x,y)r(x,y)r(x,y) is their (unique) low-degree extension. Second, r(x,y)r(x,y)r(x,y) vanishes on the square H×H\mathbb{H}\times \mathbb{H}H×H except for on the diagonal, where it takes on the (non-zero) values (r(a,a))a∈H(r(a,a))_{a\in \mathbb{H}}(r(a,a))a∈H​.) . Also rM(x,y)=∑k∈Hr(x,k)M^(k,y)r_M(x,y)=\sum_{k\in \mathbb{H}}r(x,k)\hat{M}(k,y)rM​(x,y)=∑k∈H​r(x,k)M^(k,y) for M∈{A,B,C}M\in \{A,B,C\}M∈{A,B,C} where A^(x,y)\hat{A}(x,y)A^(x,y) is a bivariate polynomial that passes from 25 points where theses points are obtained using indexing rows and columns of AAA by elements of H\mathbb{H}H. This polynomial can obtain as following: A^(x,y)=∑k∈KuH(x,row^AHPA(k))uH(y,col^AHPA(k))val^AHPA(k)\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)A^(x,y)=∑k∈K​uH​(x,row^AHPA​​(k))uH​(y,col^AHPA​​(k))val^AHPA​​(k)

, B^(x,y)\hat{B}(x,y)B^(x,y) similarly as following: B^(x,y)=∑k∈KuH(x,row^AHPB(k))uH(y,col^AHPB(k))val^AHPB(k)\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)B^(x,y)=∑k∈K​uH​(x,row^AHPB​​(k))uH​(y,col^AHPB​​(k))val^AHPB​​(k)

and C^(x,y)\hat{C}(x,y)C^(x,y) similarly as following: C^(x,y)=∑k∈KuH(x,row^AHPC(k))uH(y,col^AHPC(k))val^AHPC(k)\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)C^(x,y)=∑k∈K​uH​(x,row^AHPC​​(k))uH​(y,col^AHPC​​(k))val^AHPC​​(k)

The Prover sends ComAHPX8=∑i=0degg1(x)g1ick(i)Com_{AHP_X}^{8}=\sum_{i=0}^{deg_{g_1(x)}}g_{1_i}ck(i)ComAHPX​8​=∑i=0degg1​(x)​​g1i​​ck(i) and ComAHPX9=∑i=0degh1(x)h1ick(i)Com_{AHP_X}^{9}=\sum_{i=0}^{deg_{h_1(x)}}h_{1_i}ck(i)ComAHPX​9​=∑i=0degh1​(x)​​h1i​​ck(i) to the Verifier where g1ig_{1_i}g1i​​ is coefficient of xix^ixi of polynomial g1(x)g_1(x)g1​(x) and h1ih_{1_i}h1i​​ is coefficient of xix^ixi of polynomial h1(x)h_1(x)h1​(x).

8- The Verifier selects β1∈F−H\beta_1\in \mathbb{F}-\mathbb{H}β1​∈F−H and sends it to the Prover. (The Prover can selects β1=hash(s(8))∈F−H\beta_1=hash(s(8))\in \mathbb{F}-\mathbb{H}β1​=hash(s(8))∈F−H ).

9- The Prover calculates σ2=∑k∈Hr(α,k)∑MηMM^(k,β1)\sigma_2=\sum_{k\in\mathbb{H}}r(\alpha,k)\sum_{M}\eta_M\hat{M}(k,\beta_1)σ2​=∑k∈H​r(α,k)∑M​ηM​M^(k,β1​). Then, the Prover finds g2(x)g_2(x)g2​(x) and h2(x)h_2(x)h2​(x) so that r(α,x)∑MηMM^(x,β1)=h2(x)vH(x)+xg2(x)+σ2∣H∣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}|}r(α,x)∑M​ηM​M^(x,β1​)=h2​(x)vH​(x)+xg2​(x)+∣H∣σ2​​

The Prover sends ComAHPX10=∑i=0degg2(x)g2ick(i)Com_{AHP_X}^{10}=\sum_{i=0}^{deg_{g_2(x)}}g_{2_i}ck(i)ComAHPX​10​=∑i=0degg2​(x)​​g2i​​ck(i) and ComAHPX11=∑i=0degh2(x)h2ick(i)Com_{AHP_X}^{11}=\sum_{i=0}^{deg_{h_2(x)}}h_{2_i}ck(i)ComAHPX​11​=∑i=0degh2​(x)​​h2i​​ck(i) where g2ig_{2_i}g2i​​ is coefficient of xix^ixi of polynomial g2(x)g_2(x)g2​(x) and h2ih_{2_i}h2i​​ is coefficient of xix^ixi of polynomial h2(x)h_2(x)h2​(x).

10- The Verifier selects β2∈F−H\beta_2\in \mathbb{F}-\mathbb{H}β2​∈F−H and sends it to the Prover. ( The Prover can select β2=hash(s(9))∈F−H\beta_2=hash(s(9))\in \mathbb{F}-\mathbb{H}β2​=hash(s(9))∈F−H ).

11- The Prover calculates σ3=∑k∈K(∑MηMvH(β2)vH(β1)valAHPM^(k)(β2−rowAHPM^(k))(β1−colAHPM^(k)))\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))})σ3​=∑k∈K​(∑M​ηM​(β2​−rowAHPM​​^​(k))(β1​−colAHPM​​^​(k))vH​(β2​)vH​(β1​)valAHPM​​^​(k)​). Then, the Prover finds polynomials g3(x)g_3(x)g3​(x) and h3(x)h_3(x)h3​(x) so that h3(x)vK(x)=a(x)−b(x)(xg3(x)+σ3∣K∣)h_3(x)v_{\mathbb{K}}(x)=a(x)-b(x)(xg_3(x)+\frac{\sigma_3}{|\mathbb{K}|})h3​(x)vK​(x)=a(x)−b(x)(xg3​(x)+∣K∣σ3​​) where a(x)=∑M∈{A,B,C}ηMvH(β2)vH(β1)val^AHPM(x)∏N∈{A,B,C}−{M}(β2−row^AHPN(x))(β1−col^AHPN(x))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))a(x)=∑M∈{A,B,C}​ηM​vH​(β2​)vH​(β1​)val^AHPM​​(x)∏N∈{A,B,C}−{M}​(β2​−row^AHPN​​(x))(β1​−col^AHPN​​(x))and b(x)=∏M∈{A,B,C}(β2−row^AHPM(x))(β1−col^AHPM(x))b(x)=\prod_{M\in\{A,B,C\}}(\beta_2-\hat{row}_{AHP_M}(x))(\beta_1-\hat{col}_{AHP_M}(x))b(x)=∏M∈{A,B,C}​(β2​−row^AHPM​​(x))(β1​−col^AHPM​​(x)).

The Prover sends ComAHPX12=∑i=0degg3(x)g3ick(i)Com_{AHP_X}^{12}=\sum_{i=0}^{deg_{g_3(x)}}g_{3_i}ck(i)ComAHPX​12​=∑i=0degg3​(x)​​g3i​​ck(i) and ComAHPX13=∑i=0degh3(x)h3ick(i)Com_{AHP_X}^{13}=\sum_{i=0}^{deg_{h_3(x)}}h_{3_i}ck(i)ComAHPX​13​=∑i=0degh3​(x)​​h3i​​ck(i) where g3ig_{3_i}g3i​​ is coefficient of xix^ixi of polynomial g3(x)g_3(x)g3​(x) and h3ih_{3_i}h3i​​ is coefficient of xix^ixi of polynomial h3(x)h_3(x)h3​(x).

12- The Prover sends πAHP1=σ1\pi_{AHP}^1=\sigma_1πAHP1​=σ1​,

πAHP2=(w0^,w1^,w3^,...,w∣W∣+b−1^)\pi_{AHP}^2=(\hat{w_0},\hat{w_1},\hat{w_3},...,\hat{w_{|W|+b-1}})πAHP2​=(w0​^​,w1​^​,w3​^​,...,w∣W∣+b−1​^​),

πAHP3=(z^A0,z^A1,...,z^A∣H∣+b−1)\pi_{AHP}^3=(\hat{z}_{A_0},\hat{z}_{A_1},...,\hat{z}_{A_{|H|+b-1}})πAHP3​=(z^A0​​,z^A1​​,...,z^A∣H∣+b−1​​), πAHP4=(z^B0,z^B1,...,z^B∣H∣+b−1)\pi_{AHP}^4=(\hat{z}_{B_0},\hat{z}_{B_1},...,\hat{z}_{B_{|H|+b-1}})πAHP4​=(z^B0​​,z^B1​​,...,z^B∣H∣+b−1​​), πAHP5=(z^C0,z^C1,...,z^C∣H∣+b−1)\pi_{AHP}^5=(\hat{z}_{C_0},\hat{z}_{C_1},...,\hat{z}_{C_{|H|+b-1}})πAHP5​=(z^C0​​,z^C1​​,...,z^C∣H∣+b−1​​), πAHP6=(h00,h01,...,h0∣H∣+2b−2)\pi_{AHP}^6=(h_{0_0},h_{0_1},...,h_{0_{|H|+2b-2}})πAHP6​=(h00​​,h01​​,...,h0∣H∣+2b−2​​) and πAHP7=(s0,s1,...,s2∣H∣+b−2)\pi_{AHP}^7=(s_0,s_1,...,s_{2|H|+b-2})πAHP7​=(s0​,s1​,...,s2∣H∣+b−2​) 13- The Prover sends πAHP8=(g10,...,g1∣H∣−2)\pi_{AHP}^8=(g_{1_0},...,g_{1_{|H|-2}})πAHP8​=(g10​​,...,g1∣H∣−2​​) and πAHP9=(h10,...,h1∣H∣+b−2)\pi_{AHP}^{9}=(h_{1_0},...,h_{1_{|H|+b-2}})πAHP9​=(h10​​,...,h1∣H∣+b−2​​) .

14-The Prover sends πAHP10=σ2\pi_{AHP}^{10}=\sigma_2πAHP10​=σ2​, πAHP11=(g20,...,g2∣H∣−2)\pi_{AHP}^{11}=(g_{2_0},...,g_{2_{|H|-2}})πAHP11​=(g20​​,...,g2∣H∣−2​​) and πAHP12=(h20,...,h2∣H∣−2)\pi_{AHP}^{12}=(h_{2_0},...,h_{2_{|H|-2}})πAHP12​=(h20​​,...,h2∣H∣−2​​).

15- The Prover sends πAHP13=σ3\pi_{AHP}^{13}=\sigma_3πAHP13​=σ3​, πAHP14=(g30,...,g3∣K∣−2)\pi_{AHP}^{14}=(g_{3_0},...,g_{3_{|K|-2}})πAHP14​=(g30​​,...,g3∣K∣−2​​) and πAHP15=(h30,...,h36∣K∣−6)\pi_{AHP}^{15}=(h_{3_0},...,h_{3_{6|K|-6}})πAHP15​=(h30​​,...,h36∣K∣−6​​) .

16- The Prover chooses random values ηrowAHPA\eta_{row_{AHP_A}}ηrowAHPA​​​ , ηcolAHPA\eta_{col_{AHP_A}}ηcolAHPA​​​ , ηvalAHPA\eta_{val_{AHP_A}}ηvalAHPA​​​ , ηrowAHPB\eta_{row_{AHP_B}}ηrowAHPB​​​ , ηcolAHPB\eta_{col_{AHP_B}}ηcolAHPB​​​ , ηvalAHPB\eta_{val_{AHP_B}}ηvalAHPB​​​ , ηrowAHPC\eta_{row_{AHP_C}}ηrowAHPC​​​ , ηcolAHPC\eta_{col_{AHP_C}}ηcolAHPC​​​ , ηvalAHPC\eta_{val_{AHP_C}}ηvalAHPC​​​ , ηw^\eta_{\hat{w}}ηw^​, ηz^A\eta_{\hat{z}_A}ηz^A​​, ηz^B\eta_{\hat{z}_B}ηz^B​​, ηz^C\eta_{\hat{z}_C}ηz^C​​, ηz^\eta_{\hat{z}}ηz^​, ηh0\eta_{h_0}ηh0​​, ηs\eta_sηs​, ηg1\eta_{g_1}ηg1​​, ηh1\eta_{h_1}ηh1​​, ηg2\eta_{g_2}ηg2​​, ηh2\eta_{h_2}ηh2​​, ηg3\eta_{g_3}ηg3​​ and ηh3\eta_{h_3}ηh3​​ of F\mathbb{F}F The Verifier can choose as following: ηrowAHPA=hash(s(10))\eta_{row_{AHP_A}}=hash(s(10))ηrowAHPA​​​=hash(s(10)) , ηcolAHPA=hash(s(11))\eta_{col_{AHP_A}}=hash(s(11))ηcolAHPA​​​=hash(s(11)) , ηvalAHPA=hash(s(12))\eta_{val_{AHP_A}}=hash(s(12))ηvalAHPA​​​=hash(s(12)) , ηrowAHPB=hash(s(13))\eta_{row_{AHP_B}}=hash(s(13))ηrowAHPB​​​=hash(s(13)) , ηcolAHPB=hash(s(14))\eta_{col_{AHP_B}}=hash(s(14))ηcolAHPB​​​=hash(s(14)) , ηvalAHPB=hash(s(15))\eta_{val_{AHP_B}}=hash(s(15))ηvalAHPB​​​=hash(s(15)) ,ηrowAHPC=hash(s(16))\eta_{row_{AHP_C}}=hash(s(16))ηrowAHPC​​​=hash(s(16)) , ηcolAHPC=hash(s(17))\eta_{col_{AHP_C}}=hash(s(17))ηcolAHPC​​​=hash(s(17)) , ηvalAHPC=hash(s(18))\eta_{val_{AHP_C}}=hash(s(18))ηvalAHPC​​​=hash(s(18)) , ηw^=hash(s(19))\eta_{\hat{w}}=hash(s(19))ηw^​=hash(s(19)), ηz^A=hash(s(20))\eta_{\hat{z}_A}=hash(s(20))ηz^A​​=hash(s(20)), ηz^B=hash(s(20))\eta_{\hat{z}_B}=hash(s(20))ηz^B​​=hash(s(20)), ηz^C=hash(s(21))\eta_{\hat{z}_C}=hash(s(21))ηz^C​​=hash(s(21)), ηh0=hash(s(22))\eta_{h_0}=hash(s(22))ηh0​​=hash(s(22)), ηs=hash(s(23))\eta_{s}=hash(s(23))ηs​=hash(s(23)), ηg1=hash(s(24))\eta_{g_1}=hash(s(24))ηg1​​=hash(s(24)), ηh1=hash(s(25))\eta_{h_1}=hash(s(25))ηh1​​=hash(s(25)), ηg2=hash(s(26))\eta_{g_2}=hash(s(26))ηg2​​=hash(s(26)), ηh2=hash(s(27))\eta_{h_2}=hash(s(27))ηh2​​=hash(s(27)), ηg3=hash(s(28))\eta_{g_3}=hash(s(28))ηg3​​=hash(s(28)), ηh3=hash(s(29))\eta_{h_3}=hash(s(29))ηh3​​=hash(s(29)).

p(x)=ηrowAHPArow^AHPA(x)+ηcolAHPAcol^AHPA(x)+ηvalAHPAval^AHPA(x)+ηrowAHPBrow^AHPB(x)+ηcolAHPBcol^AHPB(x)+ηvalAHPBval^AHPB(x)+ηrowAHPCrow^AHPC(x)+ηcolAHPBcol^AHPB(x)+ηvalAHPCval^AHPC(x)+ηw^w^(x)+ηz^Az^A(x)+ηz^Bz^B(x)+ηz^Cz^C(x)+ηh0h0(x)+ηss(x)+ηg1g1(x)+ηh1h1(x)+ηg2g2(x)+ηh2h2(x)+ηg3g3(x)+ηh3h3(xp(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(xp(x)=ηrowAHPA​​​row^AHPA​​(x)+ηcolAHPA​​​col^AHPA​​(x)+ηvalAHPA​​​val^AHPA​​(x)+ηrowAHPB​​​row^AHPB​​(x)+ηcolAHPB​​​col^AHPB​​(x)+ηvalAHPB​​​val^AHPB​​(x)+ηrowAHPC​​​row^AHPC​​(x)+ηcolAHPB​​​col^AHPB​​(x)+ηvalAHPC​​​val^AHPC​​(x)+ηw^​w^(x)+ηz^A​​z^A​(x)+ηz^B​​z^B​(x)+ηz^C​​z^C​(x)+ηh0​​h0​(x)+ηs​s(x)+ηg1​​g1​(x)+ηh1​​h1​(x)+ηg2​​g2​(x)+ηh2​​h2​(x)+ηg3​​g3​(x)+ηh3​​h3​(x \

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

19- The Prover computes πAHP17=PC.Eval(ck,p(x),dp,rp,x′)\pi_{AHP}^{17}=PC.Eval(ck,p(x),d_p,r_p,x')πAHP17​=PC.Eval(ck,p(x),dp​,rp​,x′) where dpd_pdp​ is degree bound of p(x)p(x)p(x) and rpr_prp​ is a random value. For example, if the polynomial commitment scheme KZGKZGKZG is used, then the Prover calculates polynomial q(x)=p(x)−y′x−x′q(x)=\frac{p(x)-y'}{x-x'}q(x)=x−x′p(x)−y′​ and πAHP17=gq(τ)\pi_{AHP}^{17}=g\hspace{1mm}q(\tau)πAHP17​=gq(τ) by using ckckck as following: πAHP17=∑i=0degq(x)qick(i)\pi_{AHP}^{17}=\sum_{i=0}^{deg_{q(x)}}q_i\hspace{1mm}ck(i)πAHP17​=∑i=0degq(x)​​qi​ck(i), where qiq_iqi​ is the coefficient of xix^ixi of q(x)q(x)q(x).

ΠAHP=(ComAHPX,πAHP)\Pi_{AHP}=(Com_{AHP_X},\pi_{AHP})ΠAHP​=(ComAHPX​​,πAHP​)

where ComAHPX=(ComAHPX1,ComAHPX2,ComAHPX3,ComAHPX4,ComAHPX5,ComAHPX6,ComAHPX7,ComAHPX8,ComAHPX9,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,ComAHPX​​=(ComAHPX​1​,ComAHPX​2​,ComAHPX​3​,ComAHPX​4​,ComAHPX​5​,ComAHPX​6​,ComAHPX​7​,ComAHPX​8​,ComAHPX​9​, ComAHPX10,ComAHPX11,ComAHPX12,ComAHPX13)Com_{AHP_X}^{10},Com_{AHP_X}^{11},Com_{AHP_X}^{12},Com_{AHP_X}^{13})ComAHPX​10​,ComAHPX​11​,ComAHPX​12​,ComAHPX​13​)

ComAHPX1=XCom_{AHP_X}^1=XComAHPX​1​=X, ComAHPX2=∑i=0degW^(x)w^ick(i)Com_{AHP_X}^2=\sum_{i=0}^{deg_{\hat{W}(x)}}\hat{w}_i\hspace{1mm}ck(i)ComAHPX​2​=∑i=0degW^(x)​​w^i​ck(i), ComAHPX3=∑i=0degz^A(x)z^Aick(i)Com_{AHP_X}^{3}=\sum_{i=0}^{deg_{\hat{z}_A(x)}}\hat{z}_{A_i}ck(i)ComAHPX​3​=∑i=0degz^A​(x)​​z^Ai​​ck(i), ComAHPX4=∑i=0degz^B(x)z^Bick(i)Com_{AHP_X}^{4}=\sum_{i=0}^{deg_{\hat{z}_B(x)}}\hat{z}_{B_i}ck(i)ComAHPX​4​=∑i=0degz^B​(x)​​z^Bi​​ck(i), ComAHPX5=∑i=0degz^C(x)z^Cick(i)Com_{AHP_X}^{5}=\sum_{i=0}^{deg_{\hat{z}_C(x)}}\hat{z}_{C_i}ck(i)ComAHPX​5​=∑i=0degz^C​(x)​​z^Ci​​ck(i), ComAHPX6=∑i=0degh0(x)h0ick(i)Com_{AHP_X}^{6}=\sum_{i=0}^{deg_{h_0(x)}}h_{0_i}ck(i)ComAHPX​6​=∑i=0degh0​(x)​​h0i​​ck(i), ComAHPX7=∑i=0degs(x)sick(i)Com_{AHP_X}^{7}=\sum_{i=0}^{deg_{s(x)}}s_i\hspace{1mm}ck(i)ComAHPX​7​=∑i=0degs(x)​​si​ck(i), ComAHPX8=∑i=0degg1(x)g1ick(i)Com_{AHP_X}^{8}=\sum_{i=0}^{deg_{g_1(x)}}g_{1_i}ck(i)ComAHPX​8​=∑i=0degg1​(x)​​g1i​​ck(i), ComAHPX9=∑i=0degh1(x)h1ick(i)Com_{AHP_X}^{9}=\sum_{i=0}^{deg_{h_1(x)}}h_{1_i}ck(i)ComAHPX​9​=∑i=0degh1​(x)​​h1i​​ck(i), ComAHPX10=∑i=0degg2(x)g2ick(i)Com_{AHP_X}^{10}=\sum_{i=0}^{deg_{g_2(x)}}g_{2_i}ck(i)ComAHPX​10​=∑i=0degg2​(x)​​g2i​​ck(i), ComAHPX11=∑i=0degh2(x)h2ick(i)Com_{AHP_X}^{11}=\sum_{i=0}^{deg_{h_2(x)}}h_{2_i}ck(i)ComAHPX​11​=∑i=0degh2​(x)​​h2i​​ck(i), ComAHPX12=∑i=0degg3(x)g3ick(i)Com_{AHP_X}^{12}=\sum_{i=0}^{deg_{g_3(x)}}g_{3_i}ck(i)ComAHPX​12​=∑i=0degg3​(x)​​g3i​​ck(i), ComAHPX13=∑i=0degh3(x)h3ick(i)Com_{AHP_X}^{13}=\sum_{i=0}^{deg_{h_3(x)}}h_{3_i}ck(i)ComAHPX​13​=∑i=0degh3​(x)​​h3i​​ck(i)

πAHP1=σ1\pi_{AHP}^1=\sigma_1πAHP1​=σ1​, πAHP2=(w^0,w^1,w^3,...,w^ng+b−1)\pi_{AHP}^2=(\hat{w}_0,\hat{w}_1,\hat{w}_3,...,\hat{w}_{n_g+b-1})πAHP2​=(w^0​,w^1​,w^3​,...,w^ng​+b−1​), πAHP3=(z^A0,z^A1,...,z^A∣H∣+b−1)\pi_{AHP}^3=(\hat{z}_{A_0},\hat{z}_{A_1},...,\hat{z}_{A_{|H|+b-1}})πAHP3​=(z^A0​​,z^A1​​,...,z^A∣H∣+b−1​​), πAHP4=(z^B0,z^B1,...,z^B∣H∣+b−1)\pi_{AHP}^4=(\hat{z}_{B_0},\hat{z}_{B_1},...,\hat{z}_{B_{|H|+b-1}})πAHP4​=(z^B0​​,z^B1​​,...,z^B∣H∣+b−1​​), πAHP5=(z^C0,z^C1,...,z^C∣H∣+b−1)\pi_{AHP}^5=(\hat{z}_{C_0},\hat{z}_{C_1},...,\hat{z}_{C_{|H|+b-1}})πAHP5​=(z^C0​​,z^C1​​,...,z^C∣H∣+b−1​​), πAHP6=(h00,h01,...,h0∣H∣+2b−2)\pi_{AHP}^6=(h_{0_0},h_{0_1},...,h_{0_{|H|+2b-2}})πAHP6​=(h00​​,h01​​,...,h0∣H∣+2b−2​​), πAHP7=(s0,s1,...,s2∣H∣+b−2)\pi_{AHP}^7=(s_0,s_1,...,s_{2|H|+b-2})πAHP7​=(s0​,s1​,...,s2∣H∣+b−2​), πAHP8=(g10,...,g1∣H∣−2)\pi_{AHP}^8=(g_{1_0},...,g_{1_{|H|-2}})πAHP8​=(g10​​,...,g1∣H∣−2​​), πAHP9=(h10,...,h1∣H∣+b−2)\pi_{AHP}^{9}=(h_{1_0},...,h_{1_{|H|+b-2}})πAHP9​=(h10​​,...,h1∣H∣+b−2​​), πAHP10=σ2\pi_{AHP}^{10}=\sigma_2πAHP10​=σ2​, πAHP11=(g20,...,g2∣H∣−2)\pi_{AHP}^{11}=(g_{2_0},...,g_{2_{|H|-2}})πAHP11​=(g20​​,...,g2∣H∣−2​​), πAHP12=(h20,...,h2∣H∣−2)\pi_{AHP}^{12}=(h_{2_0},...,h_{2_{|H|-2}})πAHP12​=(h20​​,...,h2∣H∣−2​​), πAHP13=σ3\pi_{AHP}^{13}=\sigma_3πAHP13​=σ3​, πAHP14=(g30,...,g3∣K∣−2)\pi_{AHP}^{14}=(g_{3_0},...,g_{3_{|K|-2}})πAHP14​=(g30​​,...,g3∣K∣−2​​), πAHP15=(h30,...,h36∣K∣−6)\pi_{AHP}^{15}=(h_{3_0},...,h_{3_{6|K|-6}})πAHP15​=(h30​​,...,h36∣K∣−6​​), πAHP16=y′\pi_{AHP}^{16}=y'πAHP16​=y′, πAHP17=∑i=0degq(x)qick(i)\pi_{AHP}^{17}=\sum_{i=0}^{deg_{q(x)}}q_i\hspace{1mm}ck(i)πAHP17​=∑i=0degq(x)​​qi​ck(i).

where w^i\hat{w}_iw^i​ is coefficient of xix^ixi in polynomial W^(x)\hat{W}(x)W^(x), z^Ai\hat{z}_{A_i}z^Ai​​ is coefficient of xix^ixi in polynomial z^A(x)\hat{z}_A(x)z^A​(x), z^Bi\hat{z}_{B_i}z^Bi​​ is coefficient of xix^ixi in polynomial z^B(x)\hat{z}_B(x)z^B​(x), z^Ci\hat{z}_{C_i}z^Ci​​ is coefficient of xix^ixi in polynomial z^C(x)\hat{z}_C(x)z^C​(x), h0ih_{0_i}h0i​​ is coefficient of xix^ixi in polynomial h0(x)h_0(x)h0​(x), sis_{i}si​ is coefficient of xix^ixi in polynomial s(x)s(x)s(x), g1ig_{1_i}g1i​​ is coefficient of xix^ixi of polynomial g1(x)g_1(x)g1​(x) and h1ih_{1_i}h1i​​ is coefficient of xix^ixi of polynomial h1(x)h_1(x)h1​(x), g2ig_{2_i}g2i​​ is coefficient of xix^ixi of polynomial g2(x)g_2(x)g2​(x) and h2ih_{2_i}h2i​​ is coefficient of xix^ixi of polynomial h2(x)h_2(x)h2​(x), g3ig_{3_i}g3i​​ is coefficient of xix^ixi of polynomial g3(x)g_3(x)g3​(x) and h3ih_{3_i}h3i​​ is coefficient of xix^ixi of polynomial h3(x)h_3(x)h3​(x).

Size of AHP proof: ∣ΠAHP∣=10∣H∣+7∣K∣+∣W∣+8b+6|\Pi_{AHP}|=10|\mathbb{H}|+7|\mathbb{K}|+|W|+8b+6∣ΠAHP​∣=10∣H∣+7∣K∣+∣W∣+8b+6.