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)
BPBP+ BPBP+ BPBP+
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:

  1. $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$
  2. $\textbf{a}_{R} = \textbf{a}_{L} - \textbf{1}^{n}$
  3. $\textbf{a}_{L} \circ \textbf{a}_{R} = \textbf{0}^{n}$
we can organize the terms into one equation, with some arrangements, using the WIP: \[ (\textbf{a}_L -z \cdot \textbf{1}^n) \odot_y (\textbf{a}_R + z \cdot \textbf{1}^n + \textbf{2}^n \circ \overleftarrow{y}^n) = y^{n+1} \cdot a - \zeta(y,z). \] where $\zeta(y,z)= zy^{n+1} \cdot \langle \textbf{2}^n,\textbf{1}^n \rangle + (z^2-z) \cdot \langle \textbf{1}^n,\overrightarrow{y}^n \rangle$ Finally, the inner product can also use the method 'divide to conquer' and the prover has to prove that $c = \textbf{a} \odot_y \textbf{b}$ holds. First, he can commit to vectors $(\textbf{a}_L, \textbf{b}_R)$ and $(\textbf{a}_R, \textbf{b}_L)$ and the scalars $c_L = \textbf{a}_L \odot_{y} \textbf{b}_R$ and $c_R = (y^{\frac{n}{2}} \cdot \textbf{a}_R) \odot_{y} \textbf{b}_L$. Now, similarly to the bulletproof, the iteractions can be written as: \[ \hat{\textbf{a}} = x\textbf{a}_L + x^{-1}(y^{\frac{n}{2}} \cdot \textbf{a}_R), \quad \hat{\textbf{b}} = x^{-1}\textbf{b}_L + x\textbf{b}_R. \\[4pt] \implies \hat{\textbf{a}} \odot_y \hat{\textbf{b}} = x^2c_L + c + x^{-2}c_R. \]

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.