This is a documentation for the internal implementation of the aggregated range proof. You may find the introduction to all the pieces of the range proof protocol in the notes module.
The aggregated range proof is a zero-knowledge proof of the following relation:
ZK-PK{v(0),v(1),…,v(m−1)∈Zp:v(0),v(1),…,v(m−1)∈[0,2n)}
To create the aggregated range proof, m individual parties which each have a secret value v(j)exchange messages with one dealer, without revealing their secrets. You may find more information on how the parties and dealers are implemented in aggregated protocol notes.
The protocol begins with each party j computing three commitments: to the value v(j), to the bits of that value aL,(j),aR,(j), and to the per-bit blinding factors sL,(j),sR,(j).
V(j)A(j)S(j)←Com(v(j),v(j))←Com(aL,(j),aR,(j))←Com(sL,(j),sR,(j))=v(j)⋅B+v(j)⋅B=⟨aL,(j),G(j)⟩+⟨aR,(j),H(j)⟩+a(j)B=⟨sL,(j),G(j)⟩+⟨sR,(j),H(j)⟩+s(j)B where v(j),a(j),s(j) are sampled randomly
from Zp and sL,(j),sR,(j) are sampled randomly from Zpn.
The parties all send their V(j), A(j), and S(j) values to the dealer as BitCommitment. The dealer adds each V(j) value to the protocol transcript, in order. The dealer then computes A and S as follows:
AS=j=0∑m−1A(j)=j=0∑m−1S(j)
The dealer adds A and S to the protocol transcript and obtains challenge scalars y,z∈Zp from the transcript. The dealer sends y,z as BitChallenge to all of the parties.
Using their secret vectors and the challenges y,z from BitChallenge, each party constructs vector polynomials:
l(j)(x)r(j)(x)l0,(j)l1,(j)r0,(j)r1,(j)=l0,(j)+l1,(j)x=r0,(j)+r1,(j)x←aL,(j)−z1←sL,(j)←y(j)n∘(aR,(j)+z1)+z2z(j)2n←y(j)n∘sR,(j)
The inner product of the above vector polynomials is:
t(j)(x)=⟨l(j)(x),r(j)(x)⟩=t0,(j)+t1,(j)x+t2,(j)x2,
Each party uses Karatsuba’s method to compute the coefficients of that polynomial as follows:
t0,(j)t2,(j)t1,(j)←⟨l0,(j),r0,(j)⟩,←⟨l1,(j),r1,(j)⟩,←⟨l0,(j)+l1,(j),r0,(j)+r1,(j)⟩−t0,(j)−t2,(j)
The party commits to the terms t1,(j),t2,(j):
T1,(j)T2,(j)←Com(t1,(j),t~(j1)←Com(t2,(j),t~2,(j))=t1,(j)⋅B+t~1,(j)⋅B=t2,(j)⋅B+t~2,(j)⋅B where t~1,(j),t~2,(j) are sampled randomly from Zp.
The parties all send their T1,(j) and T2,(j) values to the dealer as PolyCommitment. The dealer then computes T1 and T2 as follows:
T1T2=j=0∑m−1T1,(j)=j=0∑m−1T2,(j)
The dealer adds T1 and T2 to the protocol transcript and obtains a challenge scalar x∈Zp from the transcript. The dealer sends x as PolyChallenge to all of the parties.
Each party uses x to evaluate their polynomials l(j)(x),r(j)(x),t(j)(x):
Next, each party computes their synthetic blinding factors:
t~(j)(x)e~(j)←z2v~(j)+xt~1,(j)+x2t~2,(j)←a(j)+xs(j)
The parties all send their values t(j)(x),t~(j)(x),e~(j),l(j)(x),r(j)(x) to the dealer as ProofShare. The dealer then computes t(x),t~(x),e~ as follows:
t(x)t~(x)e~=j=0∑m−1t(j)(x)=j=0∑m−1t~(j)(x)=j=0∑m−1e~(j)
The dealer adds t(x),t~(x),e~ to the protocol transcript, obtains a challenge scalar w∈Zp, and uses it to create a point Q:
Q←w⋅B
The dealer creates the aggregated vector polynomials l(x),r(x) by concatenating all of the individual party l(j)(x) and r(j)(x) values:
The input to the verifier is the aggregated proof, which contains the range size n, the m value commitments V(j), and 32⋅(9+2k) bytes of the proof data where k=log2(n⋅m):
{A,S,T1,T2,t(x),t~(x),e~,Lk,Rk,…,L1,R1,a,b}
The verifier uses the Fiat-Shamir transform to obtain challenges by adding the appropriate data sequentially to the protocol transcript:
V(0),V(1),…,V(m),A,S are added to obtain challenge scalars y,z∈Zp,
T1,T2 are added to obtain a challenge x∈Zp,
t(x),t~(x),e~ are added to obtain a challenge w∈Zp.
The verifier combines two equations in one by sampling a random factor c$Zp,
multiplying the first equation by c, and adding it with the second equation.
Finally, verifier groups all scalars by each point and performs a single multiscalar multiplication:
0=?++++++++++1⋅Ax⋅Scz2⋅V(0)+cz3⋅V(1)+⋯+czm+1⋅V(m−1)cx⋅T1cx2⋅T2(w(t(x)−ab)+c(δ(y,z)−t(x)))⋅B(−e−ct~(x))⋅B⟨−z1−as,G⟩⟨z1+y−n⋅m∘(z2(z02n∣∣z12n∣∣…∣∣zm−12n)−b/s),H⟩⟨[u12,…,uk2],[L1,…,Lk]⟩⟨[u1−2,…,uk−2],[R1,…,Rk]⟩ where 1/s are inverses of s, computed as a reversed list of s.
If the dealer is aggregating a proof across m parties, and if one of those parties is faulty (or malicious) and creates an invalid ProofShare, then the AggregatedProof that the dealer creates will also be invalid. Therefore, it is helpful to be able to check the validity of an individual ProofShare, in order to determine if a party is at fault and if so, to block it.
The math for checking ProofShare validity is very similar to checking AggregatedProof validity, but does not require combining values from multiple parties. The goal of checking ProofShare validity is to verify three equations:
Verify that ⟨l(j)(x),r(j)(x)⟩=t(j)(x)
The dealer can perform this check by simply taking the inner product of l(j)(x) and r(j)(x) and verifying that it is equal to t(j)(x). Note that the dealer is not creating a proof, and thus the proof compactness of the inner product protocol is not a benefit in this situation, so it is sufficient to just perform an inner product multiplication.
Verify the constant term of the polynomial t(j)(x)
The dealer wants to check if this statement is correct:
t(j)(x)B+t~(j)(x)B=?z2z(j)V(j)+δ(y,z)(j)B+xT1,(j)+x2T2,(j),δ(j)(y,z)=(z−z2)⋅⟨1,y(j)n⟩−z3z(j)⋅⟨1,2n⟩
If we rewrite the check as a comparison with the identity point, and plug in the definitions z(j)=zj and y(j)n=y[j⋅n:(j+1)⋅n]n⋅m=ynyj⋅n, we get:
The dealer wants to check if this statement is correct:
A(j)+xS(j)−z⟨1,G(j)⟩+z⟨1,H(j)⟩+⟨z2z(j)(y(j)n)−1∘2n,H(j)⟩=?e(j)B+⟨l(j)(x),G(j)⟩+⟨r(j)(x)∘(y(j)n)−1,H(j)⟩
If we rewrite the check as a comparison with the identity point, and plug in the definitions z(j)=zj and y(j)n=y[j⋅n:(j+1)⋅n]n⋅m=ynyj⋅n, we get:
The dealer can combine equations 2 and 3 into one by sampling a random factor c$Zp,
multiplying equation 2 by c, and adding it with equation 3. Finally, the dealer groups all scalars by each point and performs a single multiscalar multiplication: