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.
3-1- PFR Proof
The proof of these claims is done in the following steps:
3-2- AHP Proof
as following:
and
3-3- Proof Structure
Proof set is
CommitmentID is explained on the Commitment Phase page.
DeviceEncodedID = Base64<MAC>
Input and Output are the device input and output, respectively.
{"CommitmentID":,"DeviceEncodedID":"","TimeStamp": <The Unix time of the program execution>,"Input":4,"Output":82,"P1AHP":62,"P2AHP":[166,121,161,97,149],"P3AHP":[168,141,45,26,63,165],"P4AHP":[124,81,137,101,71,178],"P5AHP":[49,157,169,96,80,50],"P6AHP":[32,16,153,20,1,164,45,92],"P7AHP":[115,3,0,0,20,1,0,17,101,0],"P8AHP":[100,90,92],"P9AHP":[31,127,66,180,143],"P10AHP":70,"P11AHP":[105,173,30],"P12AHP":[162,82,96],"P13AHP":84,"P14AHP":[113,43,74,109,158,82,26], "P15AHP":[172,79,126,76,150,133,56,118,136,54,23,115,139,172,57,68,46,77,83,113,38,81,128,180,22,151,14,100,52,59,17,123,122,83,77,6,122,72,130,59,84,85,106,86,18,162,58,5],
"P16AHP":[xxxxxx],"Protocol":"fidesinnova_v1"}
Proof(F,H,K,A,B,C): This function outputs π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.rowA(x) , colA(x) and valA(x) is encoding of a t−SLT matrix.
2.rowB(x) , colB(x) and valB(x) is encoding of a t−SLT matrix.
3.rowC(x) , colC(x) and valC(x) is encoding of a t−Diag matrix.
1- To prove strictly lower triangularity of the matrices A and B, the Prover must prove that
logωrowM(γi)>logωcolM(γi) for i∈{0,1,..,m−1} and M∈{A,B}. This does by
Discrete−logcomparisonprotocol.
2- To prove the first t rows of A and B are all zeros, the Prover must prove that
rowM(K)⊆{ωt,ωt+1,...,ωn−1}. This does by subsetoverKprotocol .
3- To prove the diagonality of the matrix C, the Prover must prove that seqK(rowC)=seqK(colC)where seqK(h)=(h(k):k∈K). This does by Geometricsequence and zerooverKprotocols.
4- To prove the first t rows of C are all zeros, the Prover must prove that there is a vector v∈(F∗)n−t so that seqK(valC)=v∣∣0 . This does by Geometricsequence and zerooverKprotocols.
The steps 3 and 4 result that all the non-zero entries of the matrix C are in the positions (ωt,ωt),(ωt+1,ωt+1),...,(ωn,ωn).
Proof(F,H,K,A,B,C,X,W,Y): This function outputs
ΠAHP=(ComAHPX,πAHP)
where
ComAHPX=(ComAHPX1,ComAHPX2,ComAHPX3,ComAHPX4,ComAHPX5,ComAHPX6,ComAHPX7,ComAHPX8,ComAHPX9,ComAHPX10,ComAHPX11,ComAHPX12)
and πAHP=(πAHP1,πAHP2,πAHP3,πAHP4,πAHP5,πAHP6,πAHP7,πAHP8,πAHP9,πAHP10,πAHP11,πAHP12,πAHP13,πAHP14,πAHP15,πAHP16,πAHP17)
1- The Prover calculates zA=Az, zB=Bz, zC=Cz where z=(1,X,W).
2- The Prover calculates polynomial zA(x)using indexing zA by elements of H. Then, calculates polynomial z^A(x) using the polynomial zA(x)such that z^A(x)∈F<∣H∣+b[x] that agree with zA(x) on H. Note that values of up to b locations in this polynomial reveals no information about the witness w provided the locations are in F−H. Similarly, calculates polynomial z^B(x) so that z^B(x)∈F<∣H∣+b[x] that agree with zB(x) on H. Also, calculates polynomial z^C(x) so that z^C(x)∈F<∣H∣+b[x] that agree with zC(x) on H.
Then, calculates polynomial w^(x)∈F<∣w∣+b[x] that agree with wˉ(x) on H[>∣x∣+1] where
wˉ:H[>∣x∣+1]→F
wˉ(h)=vH[≤∣x∣+1](h)w(h)−x^(h)
Note that H[>∣x∣+1] includes the members of H except for the first ∣x∣+1 members. Also, vH[≤∣x∣+1](h) is vanishing polynomial on H[≤∣x∣+1] and x^(h) is the polynomial obtained using indexing x by elements of H[≤∣x∣+1].
3- The Prover finds polynomial h0(x) so that 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] and computes sum σ1=∑k∈Hs(k)
5- The Prover sends ComAHPX1=∏i∈{0,1,..,degw^(x)}ck(i)w^i, ComAHPX2=∏i∈{0,1..,degz^A(x)}ck(i)z^Ai, ComAHPX3=∏i∈{0,1,..,degz^B(x)}ck(i)z^Bi, ComAHPX4=∏i∈{0,1,..,degz^C(x)}ck(i)z^Ci, ComAHPX5=∏i∈{0,1,..,degh0(x)}ck(i)h0i and ComAHPX6=∏i∈{0,1,..,degs(x)}ck(i)si where w^i is coefficient of xi in polynomial w^(x), z^Ai is coefficient of xi in polynomial z^A(x), z^Bi is coefficient of xi in polynomial z^B(x), z^Ci is coefficient of xi in polynomial z^C(x), h0i is coefficient of xi in polynomial h0(x), si is coefficient of xi in polynomial s(x).
6- The Verifier chooses random numbers α, ηA, ηB, ηC and sends them to the Prover. ( Note that the Prover can choose α=hash(s(0)+s(1)+1), ηA=hash(s(2)+s(3)+2), ηB=hash(s(4)+s(5)+3), ηC=hash(s(6)+s(7)+4).
7- The Prover finds polynomials g1(x) and h1(x) so that
where z^(x)=w^(x)vH[≤∣x∣+1](x)+x^(x) that agree with z on H and r(x,y)=uH(x,y)=x−yvH(x)−vH(y) , vH(x)=∏h∈H(x−h)=x∣H∣−1. Therefore
r(x,y)=x−yx∣H∣−y∣H∣. (Note that r(x,y)satisfies two useful algebraic properties. First, the univariate polynomials (r(x,a))a∈H are linearly independent and r(x,y) is their (unique) low-degree extension. Second, r(x,y) vanishes on the square H×H except for on the diagonal, where it takes on the (non-zero) values (r(a,a))a∈H.) . Also rM(x,y)=∑k∈Hr(x,k)M^(k,y) for M∈{A,B,C} where 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 H. This polynomial can obtain as following:
A^(x,y)=∑k∈KuH(x,rowA′^(k))uH(y,colA′^(k))valA′^(k)
, B^(x,y) similarly as following:
B^(x,y)=∑k∈KuH(x,rowB′^(k))uH(y,colB′^(k))valB′^(k)
and C^(x,y) similarly as following:
C^(x,y)=∑k∈KuH(x,rowC′^(k))uH(y,colC′^(k))valC′^(k)
The Prover sends ComAHPX7=∏i∈{0,1,..,degg1(x)}ck(i)g1i and ComAHPX8=∏i∈{0,1,..,degh1(x)}ck(i)h1i to the Verifier where g1i is coefficient of xi of polynomial g1(x) and h1i is coefficient of xi of polynomial h1(x).
8- The Verifier selects β1∈F−H and sends it to the Prover. (The Prover can selects β1=hash(s(8))).
9- The Prover calculates σ2=∑k∈Hr(α,k)∑MηMM^(k,β1). Then, the Prover finds g2(x) and h2(x) so that r(α,x)∑MηMM^(x,β1)=h2(x)vH(x)+xg2(x)+∣H∣σ2
The Prover sends ComAHPX9=∏i∈{0,1,..,degg2(x)}ck(i)g2i and ComAHPX10=∏i∈{0,1,..,degh2(x)}ck(i)h2i where g2i is coefficient of xi of polynomial g2(x) and h2i is coefficient of xi of polynomial h2(x).
10- The Verifier selects β2∈F−H and sends it to the Prover. (The Prover can select β2=hash(s(9))).
11- The Prover calculates σ3=∑k∈K(∑MηM(β2−rowM′^(k))(β1−colM′^(k))vH(β2)vH(β1)valM′^(k)). Then, the Prover finds polynomials g3(x) and h3(x) so that h3(x)vK(x)=a(x)−b(x)(xg3(x)+∣K∣σ3) where a(x)=∑M∈{A,B,C}ηMvH(β2)vH(β1)valM′^(x)∏N∈{A,B,C}−{M}(β2−rowN′^(x))(β1−colN′^(x))and b(x)=∏M∈{A,B,C}(β2−rowM′^(x))(β1−colM′^(x)).
The Prover sends ComAHPX11=∏i∈{0,1,..,degg3(x)}ck(i)g3i and ComAHPX12=∏i∈{0,1,..,degh3(x)}ck(i)h3i where g3i is coefficient of xi of polynomial g3(x) and h3i is coefficient of xi of polynomial h3(x).
12- The Prover sends πAHP1=σ1, πAHP2=(w^0,w^1,w^3,...,w^∣w∣+b−1), πAHP3=(z^A0,z^A1,...,z^A∣H∣+b−1), πAHP4=(z^B0,z^B1,...,z^B∣H∣+b−1), πAHP5=(z^C0,z^C1,...,z^C∣H∣+b−1), πAHP6=(h00,h01,...,h0∣H∣+2b−2) and πAHP7=(s0,s1,...,s2∣H∣+b−2)
13- The Prover sends πAHP8=(g10,...,g1∣H∣−2) and πAHP9=(h10,...,h1∣H∣+b−2) .
14-The Prover sends πAHP10=σ2, πAHP11=(g20,...,g2∣H∣−2) and πAHP12=(h20,...,h2∣H∣−2).
15- The Prover sends πAHP13=σ3, πAHP14=(g30,...,g3∣K∣−2) and πAHP15=(h30,...,h36∣K∣−6) .
16- The Prover chooses random values ηw^, ηz^A, ηz^B, ηz^C, ηh0, ηs, ηg1, ηh1, ηg2, ηh2, ηg3 and ηh3 of F as following:
ηw^=hash(s(10)), ηz^A=hash(s(11)), ηz^B=hash(s(12)), ηz^C=hash(s(13)), ηh0=hash(s(14)), ηs=hash(s(15)), ηg1=hash(s(16)), ηh1=hash(s(17)), ηg2=hash(s(18)), ηh2=hash(s(19)), ηg3=hash(s(20)), ηh3=hash(s(21)).
17- The Prover builds the linear combinationp(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(x).
18- The Prover calculates p(x) in x=z (value of z is received from the Verifier. Also, can select as z=hash(s(22))), then puts it in πAHP16 . Therefore πAHP16=p(z)=y′.
19- The Prover computes πAHP17=PC.Eval(ck,p(x),dp,rp,z) where dp is degree bound of p(x) and rp is a random value.
For example, if the polynomial commitment scheme KZG is used, then the Prover calculates polynomial q(x)=x−zp(x)−y′ and πAHP17=gq(τ) by using ck as following:
πAHP17=∏i∈{0,1,..,degq(x)}ck(i)qi where qi is the coefficient of xi of q(x).
ΠAHP=(ComAHPX,πAHP)
where
ComAHPX=(ComAHPX1,ComAHPX2,ComAHPX3,ComAHPX4,ComAHPX5,ComAHPX6,ComAHPX7,ComAHPX8,ComAHPX9,ComAHPX10,ComAHPX11,ComAHPX12)