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: \[ \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 \(n\) and \(m\) are both a power of \(2\).

Party and Dealer's algorithm

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 \(\mathbf{a}_{L, (j)}, \mathbf{a}_{R, (j)}\), and to the per-bit blinding factors \(\mathbf{s}_{L, (j)}, \mathbf{s}_{R, (j)}\).

\[ \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 \(\widetilde{v}_{(j)}, \widetilde{a}_{(j)}, \widetilde{s}_{(j)}\) are sampled randomly from \({\mathbb Z_p}\) and \(\mathbf{s}_{L, (j)}, \mathbf{s}_{R, (j)}\) are sampled randomly from \({\mathbb Z_p}^{n}\).

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:

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

The dealer adds \(A\) and \(S\) to the protocol transcript and obtains challenge scalars \(y,z \in {\mathbb Z_p}\) 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: \[ \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) = {\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: \[ \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 \(t_{1, (j)}, t_{2, (j)}\): \[ \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 \(\tilde{t}_{1, (j)}, \tilde{t}_{2, (j)}\) are sampled randomly from \({\mathbb Z_p}\).

The parties all send their \(T_{1, (j)}\) and \(T_{2, (j)}\) values to the dealer as PolyCommitment. The dealer then computes \(T_1\) and \(T_2\) as follows: \[ \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 \(T_1\) and \(T_2\) to the protocol transcript and obtains a challenge scalar \(x \in {\mathbb Z_p}\) from the transcript. The dealer sends \(x\) as PolyChallenge to all of the parties.

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

\[ \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: \[ \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), {\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), \tilde{t}(x), \tilde{e}\) as follows: \[ \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), {\tilde{t}}(x), {\tilde{e}}\) to the protocol transcript, obtains a challenge scalar \(w \in {\mathbb Z_p}\), and uses it to create a point \(Q\):

\[ Q \gets w \cdot B \]

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

\[ \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: \[ \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 \({\mathbf{H}}' = {\mathbf{y}}^{-n \cdot m} \circ {\mathbf{H}}\).

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

The complete range proof consists of \(9+2k\) 32-byte elements: \[ \{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 \(n\), the \(m\) value commitments \(V_{(j)}\), and \(32 \cdot (9 + 2 k)\) bytes of the proof data where \(k = \log_2(n \cdot m)\):

\[ \{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)}, \dots, V_{(m)}, A, S\) are added to obtain challenge scalars \(y,z \in {\mathbb Z_p}\),
2. \(T_1, T_2\) are added to obtain a challenge \(x \in {\mathbb Z_p}\),
3. \(t(x), {\tilde{t}}(x), \tilde{e}\) are added to obtain a challenge \(w \in {\mathbb Z_p}\).

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

\[ \{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)\) (see notes):

\[ \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 \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}}. \]

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

\[ 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 = wB\) and \(P' = P + t(x) wB\) as needed for transition to the inner-product protocol:

\[ 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 \(P\) is:

\[ \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 \; {\xleftarrow{\$}} \; {\mathbb Z_p}\), 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:

\[ \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/{\mathbf{s}}\) are inverses of \(\mathbf{s}\), computed as a reversed list of \(\mathbf{s}\).

Individual share validation

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:

1. Verify that \(\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 \(\mathbf{l}_{(j)}(x)\) and \( \mathbf{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.

2. Verify the constant term of the polynomial \(t_{(j)}(x)\)

The dealer wants to check if this statement is correct: \[ \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)} = z^j\) and \({\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:

\[ \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} \]

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

The dealer wants to check if this statement is correct: \[ \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)} = z^j\) and \({\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:

\[ \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 \; {\xleftarrow{\$}} \; {\mathbb Z_p}\), 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:

\[ \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 \[ \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 \]