[][src]Module bulletproofs::range_proof

[]

The range_proof module contains an API for producing a proof that multiple integer values are within a certain range.

Aggregated range proof protocol

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(m1)Zp:v(0),v(1),,v(m1)[0,2n)} \operatorname{ZK-PK}\left\{ v_{(0)}, v_{(1)}, \dots, v_{(m-1)} \in {\mathbb Z_p} : v_{(0)}, v_{(1)}, \dots, v_{(m-1)} \in [0, 2^n) \right\}

where nn and mm are both a power of 22.

Party and Dealer's algorithm

To create the aggregated range proof, mm individual parties which each have a secret value v(j)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 jj computing three commitments: to the value v(j)v_{(j)}, to the bits of that value aL,(j),aR,(j)\mathbf{a}_{L, (j)}, \mathbf{a}_{R, (j)}, and to the per-bit blinding factors sL,(j),sR,(j)\mathbf{s}_{L, (j)}, \mathbf{s}_{R, (j)}.

V(j)Com(v(j),v~(j))=v(j)B+v~(j)B~A(j)Com(aL,(j),aR,(j))=aL,(j),G(j)+aR,(j),H(j)+a~(j)B~S(j)Com(sL,(j),sR,(j))=sL,(j),G(j)+sR,(j),H(j)+s~(j)B~ \begin{aligned} V_{(j)} &\gets \operatorname{Com}(v_{(j)}, {\widetilde{v}_{(j)}}) && = v_{(j)} \cdot B + {\widetilde{v}_{(j)}} \cdot {\widetilde{B}} \\ A_{(j)} &\gets \operatorname{Com}({\mathbf{a}}_{L, (j)}, {\mathbf{a}}_{R, (j)}) && = {\langle {\mathbf{a}}_{L, (j)}, {\mathbf{G}_{(j)}} \rangle} + {\langle {\mathbf{a}}_{R, (j)}, {\mathbf{H}_{(j)}} \rangle} + {\widetilde{a}_{(j)}} {\widetilde{B}} \\ S_{(j)} &\gets \operatorname{Com}({\mathbf{s}}_{L, (j)}, {\mathbf{s}}_{R, (j)}) && = {\langle {\mathbf{s}}_{L, (j)}, {\mathbf{G}_{(j)}} \rangle} + {\langle {\mathbf{s}}_{R, (j)}, {\mathbf{H}_{(j)}} \rangle} + {\widetilde{s}_{(j)}} {\widetilde{B}} \\ \end{aligned} where v~(j),a~(j),s~(j)\widetilde{v}_{(j)}, \widetilde{a}_{(j)}, \widetilde{s}_{(j)} are sampled randomly from Zp{\mathbb Z_p} and sL,(j),sR,(j)\mathbf{s}_{L, (j)}, \mathbf{s}_{R, (j)} are sampled randomly from Zpn{\mathbb Z_p}^{n}.

The parties all send their V(j)V_{(j)}, A(j)A_{(j)}, and S(j)S_{(j)} values to the dealer as BitCommitment. The dealer adds each V(j)V_{(j)} value to the protocol transcript, in order. The dealer then computes AA and SS as follows:

A=j=0m1A(j)S=j=0m1S(j) \begin{aligned} A &= \sum_{j=0}^{m-1} A_{(j)} \\ S &= \sum_{j=0}^{m-1} S_{(j)} \end{aligned}

The dealer adds AA and SS to the protocol transcript and obtains challenge scalars y,zZpy,z \in {\mathbb Z_p} from the transcript. The dealer sends y,zy, z as BitChallenge to all of the parties.

Using their secret vectors and the challenges y,zy, z from BitChallenge, each party constructs vector polynomials: l(j)(x)=l0,(j)+l1,(j)xr(j)(x)=r0,(j)+r1,(j)xl0,(j)aL,(j)z1l1,(j)sL,(j)r0,(j)y(j)n(aR,(j)+z1)+z2z(j)2nr1,(j)y(j)nsR,(j) \begin{aligned} {\mathbf{l}}_{(j)}(x) &= {\mathbf{l}}_{0, (j)} + {\mathbf{l}}_{1, (j)} x \\ {\mathbf{r}}_{(j)}(x) &= {\mathbf{r}}_{0, (j)} + {\mathbf{r}}_{1, (j)} x \\ {\mathbf{l}}_{0, (j)} &\gets {\mathbf{a}}_{L, (j)} - z {\mathbf{1}} \\ {\mathbf{l}}_{1, (j)} &\gets {\mathbf{s}}_{L, (j)} \\ {\mathbf{r}}_{0, (j)} &\gets {\mathbf{y}}^{n}_{(j)} \circ ({\mathbf{a}}_{R, (j)} + z {\mathbf{1}}) + z^{2} z_{(j)}{\mathbf{2}}^{n} \\ {\mathbf{r}}_{1, (j)} &\gets {\mathbf{y}}^{n}_{(j)} \circ {\mathbf{s}}_{R, (j)} \end{aligned}

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, t_{(j)}(x) = {\langle {\mathbf{l}}_{(j)}(x), {\mathbf{r}}_{(j)}(x) \rangle} = t_{0, (j)} + t_{1, (j)} x + t_{2, (j)} x^{2},

Each party uses Karatsuba’s method to compute the coefficients of that polynomial as follows: t0,(j)l0,(j),r0,(j),t2,(j)l1,(j),r1,(j),t1,(j)l0,(j)+l1,(j),r0,(j)+r1,(j)t0,(j)t2,(j) \begin{aligned} t_{0, (j)} &\gets {\langle {\mathbf{l}}_{0, (j)}, {\mathbf{r}}_{0, (j)} \rangle}, \\ t_{2, (j)} &\gets {\langle {\mathbf{l}}_{1, (j)}, {\mathbf{r}}_{1, (j)} \rangle}, \\ t_{1, (j)} &\gets {\langle {\mathbf{l}}_{0, (j)}+ {\mathbf{l}}_{1, (j)}, {\mathbf{r}}_{0, (j)} + {\mathbf{r}}_{1, (j)} \rangle} - t_{0, (j)} - t_{2, (j)} \end{aligned}

The party commits to the terms t1,(j),t2,(j)t_{1, (j)}, t_{2, (j)}: T1,(j)Com(t1,(j),t~(j1)=t1,(j)B+t~1,(j)B~T2,(j)Com(t2,(j),t~2,(j))=t2,(j)B+t~2,(j)B~ \begin{aligned} T_{1, (j)} &\gets \operatorname{Com}(t_{1, (j)}, {\tilde{t}_{(j1}}) && = t_{1, (j)} \cdot B + {\tilde{t}_{1, (j)}} \cdot {\widetilde{B}} \\ T_{2, (j)} &\gets \operatorname{Com}(t_{2, (j)}, {\tilde{t}_{2, (j)}}) && = t_{2, (j)} \cdot B + {\tilde{t}_{2, (j)}} \cdot {\widetilde{B}} \end{aligned} where t~1,(j),t~2,(j)\tilde{t}_{1, (j)}, \tilde{t}_{2, (j)} are sampled randomly from Zp{\mathbb Z_p}.

The parties all send their T1,(j)T_{1, (j)} and T2,(j)T_{2, (j)} values to the dealer as PolyCommitment. The dealer then computes T1T_1 and T2T_2 as follows: T1=j=0m1T1,(j)T2=j=0m1T2,(j) \begin{aligned} T_1 &= \sum_{j=0}^{m-1} T_{1, (j)} \\ T_2 &= \sum_{j=0}^{m-1} T_{2, (j)} \\ \end{aligned}

The dealer adds T1T_1 and T2T_2 to the protocol transcript and obtains a challenge scalar xZpx \in {\mathbb Z_p} from the transcript. The dealer sends xx as PolyChallenge to all of the parties.

Each party uses xx to evaluate their polynomials l(j)(x),r(j)(x),t(j)(x)\mathbf{l}_{(j)}(x), \mathbf{r}_{(j)}(x), t_{(j)}(x):

l(j)l0,(j)+l1,(j)xr(j)r0,(j)+r1,(j)xt(j)(x)t0,(j)+t1,(j)x+t2,(j)x2 \begin{aligned} \mathbf{l}_{(j)} &\gets {\mathbf{l}}_{0, (j)} + {\mathbf{l}}_{1, (j)} x\\ \mathbf{r}_{(j)} &\gets {\mathbf{r}}_{0, (j)} + {\mathbf{r}}_{1, (j)} x\\ t_{(j)}(x) &\gets t_{0, (j)} + t_{1, (j)} x + t_{2, (j)} x^{2} \end{aligned}

Next, each party computes their synthetic blinding factors: t~(j)(x)z2v~(j)+xt~1,(j)+x2t~2,(j)e~(j)a~(j)+xs~(j) \begin{aligned} {\tilde{t}}_{(j)}(x) &\gets z^{2} {\tilde{v}}_{(j)} + x {\tilde{t}}_{1, (j)} + x^{2} {\tilde{t}}_{2, (j)} \\ \tilde{e}_{(j)} &\gets {\widetilde{a}}_{(j)} + x {\widetilde{s}}_{(j)} \end{aligned}

The parties all send their values t(j)(x),t~(j)(x),e~(j),l(j)(x),r(j)(x)t_{(j)}(x), {\tilde{t}}_{(j)}(x), \tilde{e}_{(j)}, \mathbf{l}_{(j)}(x), \mathbf{r}_{(j)}(x) to the dealer as ProofShare. The dealer then computes t(x),t~(x),e~t(x), \tilde{t}(x), \tilde{e} as follows: t(x)=j=0m1t(j)(x)t~(x)=j=0m1t~(j)(x)e~=j=0m1e~(j) \begin{aligned} t(x) &= \sum_{j=0}^{m-1} t_{(j)}(x) \\ {\tilde{t}}(x) &= \sum_{j=0}^{m-1} {\tilde{t}}_{(j)}(x) \\ {\tilde{e}} &= \sum_{j=0}^{m-1} \tilde{e}_{(j)} \end{aligned}

The dealer adds t(x),t~(x),e~t(x), {\tilde{t}}(x), {\tilde{e}} to the protocol transcript, obtains a challenge scalar wZpw \in {\mathbb Z_p}, and uses it to create a point QQ:

QwB Q \gets w \cdot B

The dealer creates the aggregated vector polynomials l(x),r(x)\mathbf{l}(x), \mathbf{r}(x) by concatenating all of the individual party l(j)(x)\mathbf{l}_{(j)}(x) and r(j)(x)\mathbf{r}_{(j)}(x) values:

l(x)=l(0)(x)l(1)(x)l(m1)(x)r(x)=r(0)(x)r(1)(x)r(m1)(x) \begin{aligned} {\mathbf{l}}(x) &= {\mathbf{l}}_{(0)}(x) || {\mathbf{l}}_{(1)}(x) || \dots || {\mathbf{l}}_{(m-1)}(x) \\ {\mathbf{r}}(x) &= {\mathbf{r}}_{(0)}(x) || {\mathbf{r}}_{(1)}(x) || \dots || {\mathbf{r}}_{(m-1)}(x) \\ \end{aligned}

The dealer then performs the inner product argument to prove the relation: PK{(G,HGnm,P,QG;l,rZpnm):P=l,G+r,H+l,rQ} \operatorname{PK}\left\{ ({\mathbf{G}}, {\mathbf{H}}' \in {\mathbb G}^{n \cdot m}, P', Q \in {\mathbb G}; {\mathbf{l}}, {\mathbf{r}} \in {\mathbb Z_p}^{n\cdot m}) : P' = {\langle {\mathbf{l}}, {\mathbf{G}} \rangle} + {\langle {\mathbf{r}}, {\mathbf{H}}' \rangle} + {\langle {\mathbf{l}}, {\mathbf{r}} \rangle} Q \right\} where H=ynmH{\mathbf{H}}' = {\mathbf{y}}^{-n \cdot m} \circ {\mathbf{H}}.

The result of the inner product proof is a list of 2k2k points and 22 scalars, where k=log2(nm)k = \log_2(n \cdot m): {Lk,Rk,,L1,R1,a,b}\{L_k, R_k, \dots, L_1, R_1, a, b\}.

The complete range proof consists of 9+2k9+2k 32-byte elements: {A,S,T1,T2,t(x),t~(x),e~,Lk,Rk,,L1,R1,a,b} \{A, S, T_1, T_2, t(x), {\tilde{t}}(x), \tilde{e}, L_k, R_k, \dots, L_1, R_1, a, b\}

Verifier's algorithm

The input to the verifier is the aggregated proof, which contains the range size nn, the mm value commitments V(j)V_{(j)}, and 32(9+2k)32 \cdot (9 + 2 k) bytes of the proof data where k=log2(nm)k = \log_2(n \cdot m):

{A,S,T1,T2,t(x),t~(x),e~,Lk,Rk,,L1,R1,a,b} \{A, S, T_1, T_2, t(x), {\tilde{t}}(x), \tilde{e}, L_{k}, R_{k}, \dots, L_1, R_1, a, b\}

The verifier uses the Fiat-Shamir transform to obtain challenges by adding the appropriate data sequentially to the protocol transcript:

  1. V(0),V(1),,V(m),A,SV_{(0)}, V_{(1)}, \dots, V_{(m)}, A, S are added to obtain challenge scalars y,zZpy,z \in {\mathbb Z_p},
  2. T1,T2T_1, T_2 are added to obtain a challenge xZpx \in {\mathbb Z_p},
  3. t(x),t~(x),e~t(x), {\tilde{t}}(x), \tilde{e} are added to obtain a challenge wZpw \in {\mathbb Z_p}.

The verifier computes the following scalars for the inner product argument:

{u12,,uk2,u12,,uk2,s0,,sn1} \{u_{1}^{2}, \dots, u_{k}^{2}, u_{1}^{-2}, \dots, u_{k}^{-2}, s_0, \dots, s_{n-1}\}

The goal of the verifier is to check two equations:

  1. First, verify the constant term of the polynomial t(x)t(x) (see notes):

t(x)B+t~(x)B~=?j=0m1zj+2V(j)+δ(y,z)B+xT1+x2T2,δ(y,z)=(zz2)1,ynmj=0m1zj+31,2nm \begin{aligned} t(x) B + {\tilde{t}}(x) {\widetilde{B}} \stackrel{?}{=} \sum_{j=0}^{m-1} z^{j+2} V_{(j)} + \delta(y,z) B + x T_{1} + x^{2} T_{2},\\ \delta(y,z) = (z - z^{2}) \cdot {\langle {\mathbf{1}}, {\mathbf{y}}^{n \cdot m} \rangle} - \sum_{j=0}^{m-1} z^{j+3} \cdot {\langle {\mathbf{1}}, {\mathbf{2}}^{n \cdot m} \rangle}\\ \end{aligned}

If we rewrite the check as a comparison with the identity point, we get: 0=?j=0m1zj+2V(j)+δ(y,z)B+xT1+x2T2t(x)Bt~(x)B~. 0 \stackrel{?}{=} \sum_{j=0}^{m-1} z^{j+2} V_{(j)} + \delta(y,z) B + x T_{1} + x^{2} T_{2} - t(x) B - {\tilde{t}}(x) {\widetilde{B}}.

  1. Second, verify the inner product argument for the vectors l(x),r(x)\mathbf{l}(x), \mathbf{r}(x) that form the t(x)t(x) (see inner-product protocol)

P=?as,G+ynm(b/s),H+abQj=1k(Ljuj2+uj2Rj). P' \overset ? = {\langle a \cdot {\mathbf{s}}, {\mathbf{G}} \rangle} + {\langle {\mathbf{y}^{-n \cdot m}} \circ (b /{\mathbf{s}}), {\mathbf{H}} \rangle} + abQ - \sum_{j=1}^{k} \left( L_{j} u_{j}^{2} + u_{j}^{-2} R_{j} \right).

Rewriting as a comparison with the identity point and expanding Q=wBQ = wB and P=P+t(x)wBP' = P + t(x) wB as needed for transition to the inner-product protocol:

0=?P+t(x)wBas,Gynm(b/s),HabwB+j=1k(Ljuj2+uj2Rj), 0 \overset ? = P + t(x) wB - {\langle a \cdot {\mathbf{s}}, {\mathbf{G}} \rangle} - {\langle {\mathbf{y}^{-n \cdot m}} \circ (b /{\mathbf{s}}), {\mathbf{H}} \rangle} - abwB + \sum_{j=1}^{k} \left( L_{j} u_{j}^{2} + u_{j}^{-2} R_{j} \right), where the definition of PP is:

P=e~B~+A+xSz1,G+zynm,H+j=0m1zj+22n,H[jn:(j+1)n]=e~B~+A+xSz1,G+z1,H+j=0m1zj+22ny[jn:(j+1)n]nm,H[jn:(j+1)n]=e~B~+A+xSz1,G+z1,H+ynmz2(z02nz12nzm12n),H \begin{aligned} P &= -{\widetilde{e}} {\widetilde{B}} + A + x S - z{\langle {\mathbf{1}}, {\mathbf{G}} \rangle} + z{\langle {\mathbf{y}}^{n \cdot m}, {\mathbf{H}'} \rangle} + \sum_{j=0}^{m-1} {\langle z^{j+2} \cdot {\mathbf{2}}^n, {\mathbf{H}'}_{[j \cdot n : (j+1) \cdot n]} \rangle} \\ &= -{\widetilde{e}} {\widetilde{B}} + A + x S - z{\langle {\mathbf{1}}, {\mathbf{G}} \rangle} + z{\langle {\mathbf{1}}, {\mathbf{H}} \rangle} + \sum_{j=0}^{m-1} {\langle z^{j+2} \cdot {\mathbf{2}}^n \circ {\mathbf{y}}^{n \cdot m}_{[j \cdot n : (j+1) \cdot n]}, {\mathbf{H}}_{[j \cdot n : (j+1) \cdot n]} \rangle}\\ &= -{\widetilde{e}} {\widetilde{B}} + A + x S - z{\langle {\mathbf{1}}, {\mathbf{G}} \rangle} + z{\langle {\mathbf{1}}, {\mathbf{H}} \rangle} + {\langle {{\mathbf{y}}^{-n \cdot m} \circ z^2 (z^0 \mathbf{2}^n || z^1 \mathbf{2}^n || \dots || z^{m-1} \mathbf{2}^n)}, {\mathbf{H}} \rangle} \end{aligned}

The verifier combines two equations in one by sampling a random factor c$Zpc \; {\xleftarrow{\$}} \; {\mathbb Z_p}, multiplying the first equation by cc, and adding it with the second equation.

Finally, verifier groups all scalars by each point and performs a single multiscalar multiplication:

0=?1A+xS+cz2V(0)+cz3V(1)++czm+1V(m1)+cxT1+cx2T2+(w(t(x)ab)+c(δ(y,z)t(x)))B+(e~ct~(x))B~+z1as,G+z1+ynm(z2(z02nz12nzm12n)b/s),H+[u12,,uk2],[L1,,Lk]+[u12,,uk2],[R1,,Rk] \begin{aligned} 0 \quad \stackrel{?}{=} & \quad 1 \cdot A \\ + & \quad x \cdot S \\ + & \quad cz^2 \cdot V_{(0)} + cz^3 \cdot V_{(1)} + \dots + cz^{m+1} \cdot V_{(m-1)} \\ + & \quad cx \cdot T_1 \\ + & \quad cx^2 \cdot T_2 \\ + & \quad \Big(w \big(t(x) - ab\big) + c \big(\delta(y,z) - t(x)\big) \Big) \cdot B\\ + & \quad (-{\widetilde{e}} - c{\tilde{t}}(x)) \cdot \widetilde{B} \\ + & \quad {\langle {-z\mathbf{1} - a\mathbf{s}}, {\mathbf{G}} \rangle}\\ + & \quad {\langle {z\mathbf{1} + {\mathbf{y}}^{-n \cdot m} \circ (z^2 (z^0 \mathbf{2}^n || z^1 \mathbf{2}^n || \dots || z^{m-1} \mathbf{2}^n) - b/{\mathbf{s}})}, {\mathbf{H}} \rangle}\\ + & \quad {\langle [u_{1}^2, \dots, u_{k}^2 ], [L_1, \dots, L_{k}] \rangle}\\ + & \quad {\langle [u_{1}^{-2}, \dots, u_{k}^{-2} ], [R_1, \dots, R_{k}] \rangle} \end{aligned} where 1/s1/{\mathbf{s}} are inverses of s\mathbf{s}, computed as a reversed list of s\mathbf{s}.

Individual share validation

If the dealer is aggregating a proof across mm 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:

  1. Verify that l(j)(x),r(j)(x)=t(j)(x)\langle \mathbf{l}_{(j)}(x), \mathbf{r}_{(j)}(x) \rangle = t_{(j)}(x)

The dealer can perform this check by simply taking the inner product of l(j)(x)\mathbf{l}_{(j)}(x) and r(j)(x) \mathbf{r}_{(j)}(x) and verifying that it is equal to t(j)(x)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.

  1. Verify the constant term of the polynomial t(j)(x)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)=(zz2)1,y(j)nz3z(j)1,2n \begin{aligned} t_{(j)}(x) B + {\tilde{t}}_{(j)}(x) {\widetilde{B}} \stackrel{?}{=} z^{2} z_{(j)} V_{(j)} + \delta(y,z)_{(j)} B + x T_{1, (j)} + x^{2} T_{2, (j)},\\ \delta_{(j)}(y,z) = (z - z^{2}) \cdot {\langle {\mathbf{1}}, {\mathbf{y}}^{n}_{(j)} \rangle} - z^{3} z_{(j)} \cdot {\langle {\mathbf{1}}, {\mathbf{2}}^{n} \rangle}\\ \end{aligned}

If we rewrite the check as a comparison with the identity point, and plug in the definitions z(j)=zjz_{(j)} = z^j and y(j)n=y[jn:(j+1)n]nm=ynyjn{\mathbf{y}}^{n}_{(j)} = {\mathbf{y}}^{n \cdot m}_{[j\cdot n : (j+1) \cdot n]} = {\mathbf{y}}^n y^{j \cdot n}, we get:

0=?zj+2V(j)+δ(y,z)(j)B+xT1,(j)+x2T2,(j)t(j)(x)Bt~(j)(x)B~,δ(j)(y,z)=(zz2)1,ynyjnzj+31,2n \begin{aligned} 0 \stackrel{?}{=} z^{j+2} V_{(j)} + \delta(y,z)_{(j)} B + x T_{1, (j)} + x^{2} T_{2, (j)} - t_{(j)}(x) B - {\tilde{t}}_{(j)}(x) {\widetilde{B}},\\ \delta_{(j)}(y,z) = (z - z^{2}) \cdot {\langle {\mathbf{1}}, {\mathbf{y}}^n \cdot y^{j \cdot n} \rangle} - z^{j+3} \cdot {\langle {\mathbf{1}}, {\mathbf{2}}^{n} \rangle}\\ \end{aligned}

  1. Prove that l(j)(x),r(j)(x) \mathbf{l}_{(j)}(x), \mathbf{r}_{(j)}(x) are correct

The dealer wants to check if this statement is correct: A(j)+xS(j)z1,G(j)+z1,H(j)+z2z(j)(y(j)n)12n,H(j)=?e~(j)B~+l(j)(x),G(j)+r(j)(x)(y(j)n)1,H(j) \begin{aligned} A_{(j)} + xS_{(j)} - z{\langle {\mathbf{1}}, {\mathbf{G}}_{(j)} \rangle} + z{\langle {\mathbf{1}}, {\mathbf{H}}_{(j)} \rangle} + {\langle z^{2} z_{(j)} (\mathbf{y}^{n}_{(j)})^{-1} \circ {\mathbf{2}}^n, {\mathbf{H}}_{(j)} \rangle} \stackrel{?}{=} {\widetilde{e}}_{(j)} {\widetilde{B}} + {\langle \mathbf{l}_{(j)}(x), {\mathbf{G}}_{(j)} \rangle} + {\langle \mathbf{r}_{(j)}(x) \circ (\mathbf{y}^{n}_{(j)})^{-1}, {\mathbf{H}}_{(j)} \rangle} \end{aligned}

If we rewrite the check as a comparison with the identity point, and plug in the definitions z(j)=zjz_{(j)} = z^j and y(j)n=y[jn:(j+1)n]nm=ynyjn{\mathbf{y}}^{n}_{(j)} = {\mathbf{y}}^{n \cdot m}_{[j\cdot n : (j+1) \cdot n]} = {\mathbf{y}}^n y^{j \cdot n}, we get:

0=?A(j)+xS(j)z1,G(j)+z1,H(j)+zj+2ynyjn2n,H(j)e~(j)B~l(j)(x),G(j)r(j)(x)ynyjn,H(j) \begin{aligned} 0 \stackrel{?}{=}A_{(j)} + xS_{(j)} - z{\langle {\mathbf{1}}, {\mathbf{G}}_{(j)} \rangle} + z{\langle {\mathbf{1}}, {\mathbf{H}}_{(j)} \rangle} + {\langle z^{j+2} \cdot \mathbf{y}^{-n} y^{-j \cdot n} \circ {\mathbf{2}}^n, {\mathbf{H}}_{(j)} \rangle} - {\widetilde{e}}_{(j)} {\widetilde{B}} - {\langle \mathbf{l}_{(j)}(x), {\mathbf{G}}_{(j)} \rangle} - {\langle \mathbf{r}_{(j)}(x) \circ \mathbf{y}^{-n} y^{-j \cdot n} , {\mathbf{H}}_{(j)} \rangle} \end{aligned}

The dealer can combine equations 2 and 3 into one by sampling a random factor c$Zpc \; {\xleftarrow{\$}} \; {\mathbb Z_p}, multiplying equation 2 by cc, and adding it with equation 3. Finally, the dealer groups all scalars by each point and performs a single multiscalar multiplication:

0=?1A(j)+xS(j)+(e~(j)ct~(j)(x))B~+c(δ(j)(y,z)t(j)(x))B+czj+2V(j)+cxT1,(j)+cx2T2,(j)+l(j)(x)z1,G(j)+r(j)(x)ynyjn+z1+zj+2ynyjn2n,H(j) \begin{aligned} 0 \quad \stackrel{?}{=} & \quad 1 \cdot A_{(j)} \\ + & \quad x \cdot S_{(j)} \\ + & \quad (-{\widetilde{e}_{(j)}} - c{\tilde{t}}_{(j)}(x)) \cdot \widetilde{B} \\ + & \quad c \big(\delta_{(j)}(y,z) - t_{(j)}(x)\big) \cdot B\\ + & \quad cz^{j+2} \cdot V_{(j)} \\ + & \quad cx \cdot T_{1, (j)} \\ + & \quad cx^2 \cdot T_{2, (j)} \\ + & \quad {\langle {- \mathbf{l}_{(j)}(x)} -z\mathbf{1}, {\mathbf{G}_{(j)}} \rangle}\\ + & \quad {\langle {- \mathbf{r}_{(j)}(x)} \circ \mathbf{y}^{-n} y^{-j \cdot n} + z\mathbf{1} + z^{j+2} \cdot \mathbf{y}^{-n} y^{-j \cdot n} \circ {\mathbf{2}}^n, {\mathbf{H}}_{(j)} \rangle}\\ \end{aligned}

Modules

dealer

The dealer module contains the API for the dealer state while the dealer is engaging in an aggregated multiparty computation protocol.

messages

The messages module contains the API for the messages passed between the parties and the dealer in an aggregated multiparty computation protocol.

party

The party module contains the API for the party state while the party is engaging in an aggregated multiparty computation protocol.

Structs

RangeProof

The RangeProof struct represents a proof that one or more values are in a range.

Functions

delta

Compute δ(y,z)=(zz2)1,ynmj=0m1zj+31,2nm \delta(y,z) = (z - z^{2}) \langle \mathbf{1}, {\mathbf{y}}^{n \cdot m} \rangle - \sum_{j=0}^{m-1} z^{j+3} \cdot \langle \mathbf{1}, {\mathbf{2}}^{n \cdot m} \rangle