When the Bulletproofs protocol appeared, it made some kind of revolution in the ZK world, especially in anonymous transactions, where range proofs are the most complicated and important part of validating a correct transfer. Today, many protocols rely on Bulletproofs or Bulletproofs+ (a more advanced version) to enable range proofs. Additionally, the Bulletproofs protocol introduced the proof of correct scalar multiplication of committed vectors (called the inner-product argument), which became also useful in many other protocols. That is why understanding how the original Bulletproofs protocol works is so important nowadays.
Inner-product argument
As mentioned, we start by defining the protocol that enables proof of correct scalar vector multiplication. Let’s take generators $g, h \in \mathbb{G}^n, u \in \mathbb{G}$ and vectors $a, b \in \mathbb{F}^n$ and $c = \langle a, b \rangle = \sum a_ib_i \in \mathbb{F}$. For the commitment $C = \langle a, g \rangle + \langle b, h \rangle \in \mathbb{G}$, we are going to prove the validity of $c$. This protocol works with $O(n)$ prover complexity and $O(\log{n})$ proof size, and is called the inner-product argument, but many sources refer to it just as Bulletproofs.
Let’s set $n’ = n/2$ (we assume that $n$ is a power of two) and also denote by $v_L$ and $v_R$ the first and last halves of vector $v$. WLOG, we also modify the commitment a little, assuming that $P = C + u\cdot c$, and now start to work only with $P$ instead of $C$.
We define the following additively homomorphic function $H: \mathbb{F}^{2n + 1} \rightarrow \mathbb{G}$ as:
\[H(a, a', b, b', c) = \langle g_L, a \rangle + \langle g_R, a' \rangle + \langle h_L, b \rangle + \langle h_R, b' \rangle + u\cdot c\]Then, the prover and the verifier run the following protocol for the input $P, a, b, c, g, h, u$:
-
The prover evaluates and shares the following values:
\[L = H(0^{n'}, a_L, b_R, 0^{n'}, \langle a_L, b_R \rangle) = \langle g_R, a_L \rangle + \langle h_L, b_R \rangle + u\cdot \langle a_L, b_R \rangle\]\(R = H(a_R, 0^{n'}, 0^{n'}, b_L, \langle a_R, b_L \rangle) = \langle g_L, a_R \rangle + \langle h_R, b_L \rangle + u\cdot \langle a_R, b_L \rangle\) We also note that \(P = H(a_L, a_R, b_L, b_R, c)\)
-
The verifier samples a challenge $x \in \mathbb{F}$ and shares it with the prover.
-
The prover puts
\[\hat{a} = xa_L + x^{-1}a_R \in \mathbb{F}^{n'}\] \[\hat{b} = x^{-1}b_L + xb_R \in \mathbb{F}^{n'}\] -
The prover shares $\hat{a}$ and $\hat{b}$
-
The verifier puts $\hat{P} = x^2\cdot L + P + x^{-2}\cdot R$ and checks that
\[\hat{P} = H(x^{-1}\hat{a}, x\hat{a}, x\hat{b}, x^{-1}\hat{b}, \langle \hat{a}, \hat{b} \rangle)\]
Note that if we go through the obvious proof of scalar multiplication, the prover has to share $a,b$ with the verifier directly, which consumes $2n$ elements of proof size, but the presented protocol reduces the proof to the elements $\hat{a}, \hat{b}, L, R$, which is only $n+2$ elements.
Next, we can put new generators \(\hat{g} = x^{-1}g_L + xg_R \in \mathbb{G}^{n'}\)
\(\hat{h} = xh_L + x^{-1}h_R \in \mathbb{G}^{n'}\) and then the final check at Phase 4/5 is equivalent to checking that, for the commitment $\hat{P} = \langle \hat{a}, \hat{g} \rangle + \langle \hat{b}, \hat{h} \rangle$ to the vectors $\hat{a}, \hat{b}$, the $\hat{c} = \langle \hat{a}, \hat{b} \rangle$ is a valid scalar multiplication. So, instead of Phase 4/5, the prover and the verifier can run the protocol again over the input $\hat{P}, \hat{a}, \hat{b}, \hat{c}, \hat{g}, \hat{h}, u$, where each next step divides the size of the proof data by two until the size reaches $1$, at which point the prover opens $a,b$ directly.
You can check the implementation of the inner-product argument in my crypto library.
Completeness
\[\begin{gathered} \hat{P} = x^2\cdot L + P + x^{-2}\cdot R =\\ = x^2 (\langle g_R, a_L \rangle + \langle h_L, b_R \rangle + u\cdot \langle a_L, b_R \rangle) + x^{-2}(\langle g_L, a_R \rangle + \langle h_R, b_L \rangle + u\cdot \langle a_R, b_L \rangle) +\\ + \langle g_L, a_L \rangle + \langle g_R, a_R \rangle + \langle h_L, b_L \rangle + \langle h_R, b_R \rangle + u\cdot c =\\ = \langle a_L + x^{-2}a_R, g_L\rangle + \langle x^2a_L + a_R, g_R\rangle + \langle b_L + x^2b_R, h_L\rangle + \langle x^{-2}b_L + b_R, h_R\rangle +\\ + (x^2\langle a_L, b_R \rangle + x^{-2}\langle a_R, b_L \rangle + c)\cdot u =\\ = x^{-1}\langle xa_L + x^{-1}a_R, g_L\rangle + x\langle xa_L + x^{-1}a_R, g_R\rangle + x\langle x^{-1}b_L + xb_R, h_L\rangle +\\ + x^{-1}\langle x^{-1}b_L + xb_R, h_R\rangle + \langle xa_L + x^{-1}a_R, x^{-1}b_L + xb_R\rangle u =\\ = H(x^{-1}\hat{a}, x\hat{a}, x\hat{b}, x^{-1}\hat{b}, \langle \hat{a}, \hat{b} \rangle),\\ \end{gathered}\]for $\hat{a} = xa_L + x^{-1}a_R$ and $\hat{b} = x^{-1}b_L + xb_R$.
Finally, it is equal to $H(\hat{a}_L, \hat{a}_R, \hat{b}_L, \hat{b}_R, \langle \hat{a}, \hat{b} \rangle)$ with the new generators $\hat{g}, \hat{h}$.