Before we start, let's recall our goal with rangeproofs: 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).

Explaining Bulletproofs (BP) in layman's terms is not an easy task so let's do justice to the saying "a picture is worth a thousand words" to get the motivations to do it. Below you will find an illustration of a standard one input and two outputs transaction using confidential transactions versus bulletproofs.

As you remember from Borromean signatures, we had to store one commitment $C_i$ for each bit $i$ of the amount, but what if we could prove that we know all the $C_i$ values without actually storing all of them? This is the main idea of Bulletproofs. We will do some math tricks to prove that we know a very long vector without actually storing it.

Before I start, I would like to emphasize that it is only my understanding of how Bulletproofs work and it does not cover all its aspects and it may not have the depth that you are looking for. There are actually much better materials available, from which I built my understanding of BP. Please look at the Resources page to explore them. With that said, let's start just another text from someone trying to introduce BP.

If we look at the "ecdhInfo" of a transaction, we will see that the amount information is public stored at the blockchain (not explicitly but as a commitment). Let's start from there. Suppose we have a transaction with commitment $C=xG+vH$ where $x$ is the blinding factor and $v$ is the amount. Our objective with Bulletproofs (a form of rangeproofs) is to prove, in a very compact way, without revealing $v$, that it lies between $0$ and $2^n-1$ where $n=64$ in Monero.

Let's start structuring the problem in math terms. We want to prove that $0<v<2^n-1$ and in order to do so, it suffices to prove that the following three statements are true:

1. $v=⟨{𝐚}_L,{\mathbf{2}}^n⟩$ , where ${𝐚}_L$ is the binary vector representing $v$ and ${\mathbf{2}}^n$ is the power of two vector where $n=64$
2. ${𝐚}_R={𝐚}_L-{\mathbf{1}}^n$
3. ${𝐚}_L\circ {𝐚}_R={\mathbf{0}}^n$

For example, if $v=5$ and $n=3$, we have the range of possible values going from 0 to $2^3-1=7$ and the above equations can be easily checked for this case:

• $v=5$
• ${\mathbf{2}}^n=[2^0,2^1,2^2]=[1,2,4]$
• ${𝐚}_L=[1,0,1]$
• ${𝐚}_R=[0,-1,0]$

We observe that if the vector ${𝐚}_L$ is not made of 0s and 1s, then the product ${𝐚}_L\circ {𝐚}_R$ won't be 0. Now we just need to find a way to combine these three statements into one so we can simply verify whether that new equation created holds. Let's start by slightly modifying 2) and 3) with the goal of letting it as a dot product that is equal to 0.

We will make use of the Schwartz-Zippel lemma which roughly states that the probability of finding a root for a polynome of order $n$ between all the possible numbers $N$ is roughly $n/N$. As we are playing with modular arithmetics, $N$ is pretty big and finding a root is very unlikely unless all the coefficients are zero. (For a random $y$ different from 0 and given the polynome $P(y)=a_0+a_1{y}^1+a_2{y}^2+...+a_n{y}^n$, $P(y)=0$ if $a_0=a_1=a_2=...=a_n=0$ with a negligible probability otherwise.)

1. $v=⟨{𝐚}_L,{\mathbf{2}}^n⟩$ , where ${𝐚}_L$ is the binary vector representing $v$ and ${\mathbf{2}}^n$ is the power of two vector where $n=64$
2. ${𝐚}_R={𝐚}_L-{\mathbf{1}}^n⟶⟨{𝐚}_L-{\mathbf{1}}^n-{𝐚}_R,{𝐲}^n⟩=0$
3. ${𝐚}_L\circ {𝐚}_R={\mathbf{0}}^n⟶⟨{𝐚}_L\circ {𝐚}_R,{𝐲}^n⟩=0$

We did this manipulation to have all the terms equal to zero and as dot products. Now we can manipulate a bit this terms to find an equation that would only be valid if all these equations are true. Let's use again the polynome trick to represent this single equation as it is a valid assumption to make as we want to have linearly indepent (LI) terms. We can multiply each term by another random scalar, called $z$, and group them into one equation. As we want to have LI terms again and we have only three terms, we need a polynome of order 2. Let's do it:

1. $v{z}^2=⟨{𝐚}_L,{\mathbf{2}}^n⟩z^2$
2. $⟨{𝐚}_L-{\mathbf{1}}^n-{𝐚}_R,{𝐲}^n⟩z=0z=0$
3. $⟨{𝐚}_L\circ {𝐚}_R,{𝐲}^n⟩=0$

Now let's rewrite the terms as a polynomial equation: $v{z}^2+0+0=⟨{𝐚}_L,{\mathbf{2}}^n⟩z^2+⟨{𝐚}_L-{\mathbf{1}}^n-{𝐚}_R,{𝐲}^n⟩z+⟨{𝐚}_L\circ {𝐚}_R,{𝐲}^n⟩$

How to expand the equation and find delta

Applying some math manipulations, it is possible to achieve the independent term as we want (see Dalek's equations):

Finally, we want to combine these terms into a single inner product. Our goal is to rearrange the inner product above so that terms involving ${𝐚}_L$ appear only on the left-hand side, terms involving ${𝐚}_R$ appear only on the right-hand side, and non-secret terms (which the verifier can compute on its own) are factored out into a new term $\delta (y,z)$.

First, break the statement into simpler terms, then rearrange: $$\begin{array}{ccc}\hfill z^{2}v& =z^2⟨{𝐚}_L,{\mathbf{2}}^n⟩+z⟨{𝐚}_L,{𝐲}^n⟩-z⟨{𝐚}_R,{𝐲}^n⟩-z⟨\mathbf{1},{𝐲}^n⟩+⟨{𝐚}_L,{𝐚}_R\circ {𝐲}^n⟩\hfill & \text{(1)}\\ \hfill z^{2}v+z⟨\mathbf{1},{𝐲}^n⟩& =z^2⟨{𝐚}_L,{\mathbf{2}}^n⟩+z⟨{𝐚}_L,{𝐲}^n⟩-z⟨\mathbf{1},{𝐚}_R\circ {𝐲}^n⟩+⟨{𝐚}_L,{𝐚}_R\circ {𝐲}^n⟩\hfill & \text{(2)}\\ \hfill z^{2}v+z⟨\mathbf{1},{𝐲}^n⟩& =⟨{𝐚}_L,z^2{\mathbf{2}}^n⟩+⟨{𝐚}_L,z{𝐲}^n⟩+⟨-z\mathbf{1},{𝐚}_R\circ {𝐲}^n⟩+⟨{𝐚}_L,{𝐚}_R\circ {𝐲}^n⟩\hfill & \text{(3)}\\ \hfill z^{2}v+z⟨\mathbf{1},{𝐲}^n⟩& =⟨{𝐚}_L,z^2{\mathbf{2}}^n+z{𝐲}^n+{𝐚}_R\circ {𝐲}^n⟩+⟨-z\mathbf{1},{𝐚}_R\circ {𝐲}^n⟩\hfill & \text{(4)}\end{array}$$ To combine the terms on the right-hand side, add $⟨-z\mathbf{1},z^2{\mathbf{2}}^n+z{𝐲}^n⟩$ to each side, then simplify: $$\begin{array}{ccc}\hfill z^{2}v+z⟨\mathbf{1},{𝐲}^n⟩-⟨z\mathbf{1},z^2{\mathbf{2}}^n+z{𝐲}^n⟩& =⟨{𝐚}_L,z^2{\mathbf{2}}^n+z{𝐲}^n+{𝐚}_R\circ {𝐲}^n⟩\hfill & \text{(1)}\\ \hfill & +⟨-z\mathbf{1},z^2{\mathbf{2}}^n+z{𝐲}^n+{𝐚}_R\circ {𝐲}^n⟩\hfill & \text{(2)}\\ \hfill z^{2}v+(z-z^2)⟨\mathbf{1},{𝐲}^n⟩-z^3⟨\mathbf{1},{\mathbf{2}}^n⟩& =⟨{𝐚}_L-z\mathbf{1},z^2{\mathbf{2}}^n+z{𝐲}^n+{𝐚}_R\circ {𝐲}^n⟩\hfill & \text{(3)}\end{array}$$ Combining all non-secret terms outside the inner product $$\delta (y,z)=(z-z^2)⟨\mathbf{1},{𝐲}^n⟩-z^3⟨\mathbf{1},{\mathbf{2}}^n⟩,$$ we finally obtain $$z^{2}v+\delta (y,z)=⟨{𝐚}_L-z\mathbf{1},{𝐲}^n\circ ({𝐚}_R+z\mathbf{1})+z^2{\mathbf{2}}^n⟩.$$ This is equivalent to the original inner-product equation, but has a single inner product with ${𝐚}_L$ on the left, ${𝐚}_R$ on the right, and non-secret terms factored out. Let's call the left-hand side of the single inner product equation "unblinded" $𝐥(x)$ and the right-hand side "unblinded" $𝐫(x)$, such that $$\begin{array}{ccc}\hfill \text{unblinded }𝐥(x)& ={𝐚}_L-z\mathbf{1}\hfill & \text{(1)}\\ \hfill \text{unblinded }𝐫(x)& ={𝐲}^n\circ ({𝐚}_R+z\mathbf{1})+z^2{\mathbf{2}}^n\hfill & \text{(2)}\\ \hfill z^{2}v+\delta (y,z)& =⟨\text{unblinded }𝐥(x),\text{unblinded }𝐫(x)⟩\hfill & \text{(3)}\end{array}$$

After some math and rearranging the terms in order to have a dot product between terms only dependent on ${𝐚}_L$ and ${𝐚}_R$, we achieve the following equation: $z^{2}v+\delta (y,z)=⟨{𝐚}_L-z\mathbf{1},{𝐲}^n\circ ({𝐚}_R+z\mathbf{1})+z^2{\mathbf{2}}^n⟩$

Let's now name the left side of the equation $\text{unblinded }𝐥({𝐚}_L,z)$ and observe that it is only a function of ${𝐚}_L$ while the right side is now named $\text{unblinded }𝐫({𝐚}_R,y,z)$ and is a function of ${𝐚}_R$ (the result of the inner product is a scalar).

$z^{2}v+\delta (y,z)=⟨\text{unblinded }𝐥,\text{unblinded }𝐫⟩$

We name these terms unblinded because we cannot send them to the verifier without exposing ${𝐚}_L$ and ${𝐚}_R$. If we did so, we would reveal the value $v$ that we are trying to hide. So, in order to make it zero-knowledge, we need to blind these terms and make commitments to them. Let's start by rewritting the left and right side of our dot product with a blinding vector defined as $𝐥(x)$ and $𝐫(x)$ as:

$$𝐥(x)={𝐥}_0+{𝐥}_{1}x=({𝐚}_L+{𝐬}_{L}x)-z\mathbf{1}$$ $$𝐫(x)={𝐫}_0+{𝐫}_{1}x={𝐲}^n\circ (({𝐚}_R+{𝐬}_{R}x)+z\mathbf{1})+z^2{\mathbf{2}}^n$$

Now we have our inner product as one equation and if we can prove that it is true than we would achieve our goal of proving that $v$ lies between $0$ and $2^{64}-1$. Now the tricky and ingenious part comes to play. Our inner product is a function of $a_L$ and $a_R$ which are pretty big vectors (128 scalars each) and we don't want to store them in the blockchain, otherwise we would not get any advantage in relation to the previous Sigma protocol or Confidential Transactions that we had before. The idea here is to find a way to store the proofs in a manner that it scales under $O(n)$ in space (which is the case of Confidential Transactions). It turns out that it is possible to do it in $O(2lo{g}_{2}n)$, which is a great improvement! For instance, for a vector of n=128 scalars, we could store only 14 scalars.

Let's see how Monero specifically does it by first considering the general ideas and equations and then a small example to understand it.

We will use the method 'Divide and Conquer' so at each step we will reduce our problem into a similar problem but with a smaller size until we reach a trivial solution and we can propagate back the final result to solve the big problem.

So, in the beginning, we have our vectors $𝐥$ and $𝐫$ and its inner product $t=⟨𝐥,𝐫⟩$.

Let's define $P$ as a function of $𝐥$ , $𝐫$ and $t=⟨𝐥,𝐫⟩$. Where $U$ is a point known by the verifier and prover.

$$P=𝐚𝐆+𝐛𝐇+⟨𝐚,𝐛⟩U$$

Notice that this is the main equation that we want to prove its validity. If this equation holds, then we know that the creator knows $𝐚$ and $𝐛$ and its inner product. (Moreover, we also know that ${𝐚}_L$ is made of bits and $v$ lies on the desired range). Our goal will be to store less data than $𝐚$ and $𝐛$ themselves while letting the verifier know that this equation is true. Only the value P will be stored in the blockchain.

Now let's define the variables that will be in the recursion, where $x$ is a scalar that depends on $𝐋$ and $𝐑$ and the sub-indices $l$ and $h$ represent the lower and higher part of the vector when split into two parts, respectively:

$$c_L=⟨{𝐚}_l,{𝐛}_h⟩$$ $$c_R=⟨{𝐚}_h,{𝐛}_l⟩$$ $$L={𝐚}_l{𝐆}_h+{𝐛}_h{𝐇}_l+c_{L}U$$ $$R={𝐚}_h{𝐆}_l+{𝐛}_l{𝐇}_h+c_{R}U$$ $${𝐆}^{\prime }={𝐆}_l{x}^{-1}+{𝐆}_{h}x$$ $${𝐇}^{\prime }={𝐇}_{l}x+{𝐇}_h{x}^{-1}$$ $${𝐚}^{\prime }={𝐚}_{l}x+{𝐚}_h{x}^{-1}$$ $${𝐛}^{\prime }={𝐛}_l{x}^{-1}+{𝐛}_{h}x$$ Notice again that we are trying to find a way to store as less information as possible in the blockchain while maintaining a solid mathematical proof of the inner product $c=⟨𝐚,𝐛⟩$, where $𝐚=𝐥$, $𝐛=𝐫$ and $c=t$ initially. According to the above definitions, let's see how we can express $c^{\prime }$ and $P^{\prime }$: $$c^{\prime }=⟨{𝐚}^{\prime },{𝐛}^{\prime }⟩=⟨{𝐚}_{l}x+{𝐚}_h{x}^{-1},{𝐛}_l{x}^{-1}+{𝐛}_{h}x⟩=\underset{⟨𝐚,𝐛⟩}{\underbrace{⟨{𝐚}_l,{𝐛}_l⟩+⟨{𝐚}_h,{𝐛}_h⟩}}+\underset{c_L}{\underbrace{⟨{𝐚}_l,{𝐛}_h⟩}}{x}^2+\underset{c_R}{\underbrace{⟨{𝐚}_h,{𝐛}_l⟩}}{x}^{-2}=c+c_L{x}^2+c_R{x}^{-2}$$ $$P^{\prime }={𝐚}^{\prime }{𝐆}^{\prime }+{𝐛}^{\prime }{𝐇}^{\prime }+⟨{𝐚}^{\prime },{𝐛}^{\prime }⟩U$$ Let's start by expressing ${𝐚}^{\prime }{𝐆}^{\prime }$ , ${𝐛}^{\prime }{𝐇}^{\prime }$ and $⟨{𝐚}^{\prime },{𝐛}^{\prime }⟩$ separately. $${𝐚}^{\prime }{𝐆}^{\prime }=({𝐚}_{l}x+{𝐚}_h{x}^{-1})({𝐆}_l{x}^{-1}+{𝐆}_{h}x)={𝐚}_l{𝐆}_l+{𝐚}_h{𝐆}_h+{𝐚}_l{𝐆}_h{x}^2+{𝐚}_h{𝐆}_l{x}^{-2}$$ $${𝐛}^{\prime }{𝐇}^{\prime }=({𝐛}_l{x}^{-1}+{𝐛}_{h}x)({𝐇}_{l}x+{𝐇}_h{x}^{-1})={𝐛}_l{𝐇}_l+{𝐛}_h{𝐇}_h+{𝐛}_l{𝐇}_h{x}^{-2}+{𝐛}_h{𝐇}_l{x}^2$$ $$⟨{𝐚}^{\prime },{𝐛}^{\prime }⟩U=(c+c_L{x}^2+c_R{x}^{-2})U$$ Now let's try to express everything together to see how $P^{\prime }$ looks. $$P^{\prime }=\underset{𝐚𝐆}{\underbrace{{𝐚}_l{𝐆}_l+{𝐚}_h{𝐆}_h}}+\underset{𝐛𝐇}{\underbrace{{𝐛}_l{𝐇}_l+{𝐛}_h{𝐇}_h}}+\underset{L{x}^2}{\underbrace{{𝐚}_l{𝐆}_h{x}^2+{𝐛}_h{𝐇}_l{x}^2+c_L{x}^{2}U}}+\underset{R{x}^{-2}}{\underbrace{{𝐚}_h{𝐆}_l{x}^{-2}+{𝐛}_l{𝐇}_h{x}^{-2}+c_R{x}^{-2}U}}+\underset{⟨𝐚,𝐛⟩}{\underbrace{cU}}$$ $$P^{\prime }=\underset{P}{\underbrace{𝐚𝐆+𝐛𝐇+⟨𝐚,𝐛⟩U}}+L{x}^2+R{x}^{-2}$$ $$P^{\prime }=P+L{x}^2+R{x}^{-2}$$

Let's take a step back and look what we have accomplished.

1. We started storing P in the blockchain (which is the commitment to $𝐚$,$𝐛$ and our inner product).
2. At each round we stored the points $L$ and $R$ (typically for a vector containing 128 scalars, we will make 7 rounds and store 7 values for $L$ and $R$ each) and we cut by half the dimension of $𝐚$,$𝐛$,$𝐆$,$𝐇$ (without storing them in the blockchain).
3. By the end of each round, we can compute $P^{\prime }$ which depends on the previous $P$, $L$ and $R$ and known values of $x$.
4. In the last round, $P^{\prime }$ is trivially calculated as the last dot product $c^{\prime }=⟨{𝐚}^{\prime },{𝐛}^{\prime }⟩$ will be a number and we will therefore know its value.
5. We store the last $a$ and $b$ scalars so the verifier can reconstruct the tests (as he knows how to construct $𝐆$ and $𝐇$) without knowing the whole scalar vectors $𝐚$ and $𝐛$.
6. By knowing the last $P^{\prime }$, we can reconstruct all previous $P$ and verify that our initial equation holds.

Finally, we can rewrite the above procedure into one equation in order to test if P is true as informed.

$$L_1{x}_1^2+\cdots +L_k{x}_k^2+P^{\prime }+R_k{x}_k^{-2}+\cdots +R_1{x}_1^{-2}\stackrel{?}{=}aG+bH+abU$$

Where the scalars $a$ and $b$ and the point vectors $L$ and $R$ are stored in the blockchain. The values of $x_1\cdots x_k$ can be retrieved as a function of $L$ and $R$ for each step as part of the non-interactive Fiat-Shamir protocol.

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 ${𝐚}_L$ and ${𝐚}_R$ and hiding value $\alpha$.
• $S$: a point which represents the commitment to ${𝐬}_L$ and ${𝐬}_R$ and hiding value $\rho$.
• $T1$: a point which represents the commitment to $t1$ and hiding value ${\tau }_1$.
• $T2$: a point which represents the commitment to $t2$ and hiding value ${\tau }_2$.
• $taux$: a scalar, which represents the hiding value related to $T1$, $T2$, $V$ and $t$.
• $mu$: a scalar, which represents the hiding value related to $A$ and $S$.
• $𝐋$: a vector of points of size $lo{g}_2(64*\text{outputs})$ containing the proving steps for the inner product.
• $𝐑$: a vector of points of size $lo{g}_2(64*\text{outputs})$ containing the proving steps for the inner product.
• $a$: a scalar which represents the value of $\text{a}$ in the last step of the inner product.
• $b$: a scalar which represents the value of $\text{b}$ in the last step of the inner product.
• $t$: a scalar, which represents the inner product value to be tested.