Bulletproof+
In Layman's terms
Our goal stays the same: prove that the amount that we are sending lies between $0$ and $2^{64}-1$ atomic units (piconeros) (and consequently it is not negative as well).
Bulletproof+ introduces a more optimized way for storing and calculating the inner-product (described in bulletproofs). These changes improve the performance by increasing the speed for generation and verification of the proofs and by saving space. A comparison between BP and BP+ is shown on the table below.
m | Proof size (B) | Generation time (ms) | Verification time (ms) | |||
---|---|---|---|---|---|---|
BP | BP+ | BP | BP+ | BP | BP+ | |
1 | 672 | 576 | 140.5 | 109.8 | 56.5 | 46.8 |
4 | 800 | 704 | 550.3 | 431.6 | 214.3 | 179.4 |
8 | 864 | 768 | 1095.8 | 864.8 | 423.5 | 359.0 |
16 | 928 | 832 | 2190.3 | 1772.0 | 839.8 | 730.0 |
32 | 992 | 896 | 4392.0 | 3687.4 | 1702.4 | 1528.3 |
Math behind
The biggest difference between the bulletproof and bulletproof+ protocol is the way to prepare and perform the inner-product, while on BP we use the Improved Inner Product (IIP) on BP+ we use the Weighted Inner Product (WIP) protocol. The weighted inner product can be defined as: \[ \sum_{i=1}^{n} y^{i} \cdot (a_ib_i) = \textbf{a} \odot_{y} \textbf{b} = \langle \textbf{c}, \overrightarrow{y} \rangle \] and it obeys the bilinear property: \[ \textbf{a} \odot_{y} \textbf{b} = \textbf{a}_L \odot_{y} \textbf{b}_L + (y^{\frac{n}{2}} \cdot \textbf{a}_R) \odot_{y} \textbf{b}_R. \] In the same way of bulletproofs, we want to find a scalar product that describe our problem so we can benefit from the $\textit{log n}$ scalar product scheme to store the variables involved. The idea is a little bit different here though. Instead of blinding the unblinded factors and making commitments to them, as is done in bulletproof, we will make use of the fact that weigthed product already blinds the unblinded factors. So, similarly to bulletproofs, from the three equations below:
- $v ={\langle {\mathbf{a}_{L}}, {\mathbf{2}^{n}} \rangle}$ , where $\textbf{a}_L$ is the binary vector representing $v$ and $\textbf{2}^n$ is the power of two vector where $n=64$
- $\textbf{a}_{R} = \textbf{a}_{L} - \textbf{1}^{n}$
- $\textbf{a}_{L} \circ \textbf{a}_{R} = \textbf{0}^{n}$
Finally, we store in the blockchain for the bulletproof+ range-proofs:
- $V$: a vector of points with commitments to $v[i]$ and hiding values $\gamma[i]$.
- $A$: a point which represents the commitment to $\textbf{a}_L$ and $\textbf{a}_R$ and hiding value $\alpha$.
- $A1$: a point part of the WIP.
- $B$: a point part of the WIP.
- $r1$: scalar part of the WIP.
- $s1$: scalar part of the WIP.
- $d1$: scalar part of the WIP.
- $\textbf{L}$: a vector of points of size $log_2(64 * \text{outputs})$ containing the proving steps for the weighted inner product.
- $\textbf{R}$: a vector of points of size $log_2(64 * \text{outputs})$ containing the proving steps for the weighted inner product.