Inner-product and Bulletproofs

The Bulletproofs protocol when appeared made some kind of revolution in ZK world, especially in anonymous transactions where range proofs are the most complicated and important part to validate correct transfer. Today, may protocols rely on Bulletproofs of Bulletproofs+ (more advanced version) to enable range-proofs. Additionally, Bulletproofs protocol introduced the proof of correct scalar multiplication of committed vectors (called inner-product argument), that becomes also useful in many other protocols. That is why, understanding how original Bulletproofs protocol works is so important nowadays.

Inner-product argument

As mentioned, we start from defining the protocol that enables proof of correct scalar vector multiplication. Let’s put generators $g,h\in {\mathbb{G}}^n,u\in \mathbb{G}$ and vectors $a,b\in {\mathbb{F}}^n$ and $c=⟨a,b⟩=\sum a_i{b}_i\in \mathbb{F}$. For the commitment $C=⟨a,g⟩+⟨b,h⟩\in \mathbb{G}$ we are going to proof a validness of $c$. This protocol works with $O(n)$ prover complexity and $O(\log n)$ proof size, and has name inner-product argument, but many sources refer to it just as Bulletproofs.

Let’s put $n^{\prime }=n/2$ (we assume that $n$ is a power of two) and also notate $v_L$ and $v_R$ first and last halves of vector $v$. WLOG, we also modify the commitment a little, assuming that $P=C+u\cdot c$ and now starting to work only with $P$ instead of $C$.

We define the following additively homomorphic function $H:{\mathbb{F}}^{2n+1}\to \mathbb{G}$ as:

$$H(a,a^{\prime },b,b^{\prime },c)=⟨g_L,a⟩+⟨g_R,a^{\prime }⟩+⟨h_L,b⟩+⟨h_R,b^{\prime }⟩+u\cdot c$$

Then, the prover and the verifier run the following protocol for the input $P,a,b,c,g,h,u$:

1. The prover evaluates and shares the following values:

   $$L=H(0^{n^{\prime }},a_L,b_R,0^{n^{\prime }},⟨a_L,b_R⟩)=⟨g_R,a_L⟩+⟨h_L,b_R⟩+u\cdot ⟨a_L,b_R⟩$$ $$R=H(a_R,0^{n^{\prime }},0^{n^{\prime }},b_L,⟨a_R,b_L⟩)=⟨g_L,a_R⟩+⟨h_R,b_L⟩+u\cdot ⟨a_R,b_L⟩$$

   We also note that

   $$P=H(a_L,a_R,b_L,b_R,c)$$

2. The verifier samples challenge $x\in \mathbb{F}$ and shares with the prover

3. The prover puts

   $$\hat{a}=x{a}_L+x^{-1}{a}_R\in {\mathbb{F}}^{n^{\prime }}$$ $$\hat{b}=x^{-1}{b}_L+x{b}_R\in {\mathbb{F}}^{n^{\prime }}$$

4. The prover shares $\hat{a}$ and $\hat{b}$

5. 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},⟨\hat{a},\hat{b}⟩)$$

Note, that if we go through the obvious proof of scalar multiplication, the prover has to share $a,b$ with the verifier directly that consumes $2n$ elements of proof size, but the presented protocol reduces the proof size to elements $\hat{a},\hat{b},L,R$ that is only $n+2$ elements.

Next, we can put new generators

$$\hat{g}=x^{-1}{g}_L+x{g}_R\in {\mathbb{G}}^{n^{\prime }}$$ $$\hat{h}=x{h}_L+x^{-1}{h}_R\in {\mathbb{G}}^{n^{\prime }}$$

and then, the final check at Phase 4/5 is equal to the check that for the commitment $\hat{P}=⟨\hat{a},\hat{g}⟩+⟨\hat{b},\hat{h}⟩$ to the vectors $\hat{a},\hat{b}$, the $\hat{c}=⟨\hat{a},\hat{b}⟩$ 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$ where the prover opens $a,b$ directly.

You can check the implementation of inner-product argument in my crypto library.

Completeness

$$\hat{P}=x^2\cdot L+P+x^{-2}\cdot R=$$ $$=x^2(⟨g_R,a_L⟩+⟨h_L,b_R⟩+u\cdot ⟨a_L,b_R⟩)+x^{-2}(⟨g_L,a_R⟩+⟨h_R,b_L⟩+u\cdot ⟨a_R,b_L⟩)+$$ $$+⟨g_L,a_L⟩+⟨g_R,a_R⟩+⟨h_L,b_L⟩+⟨h_R,b_R⟩+u\cdot c=$$ $$=⟨a_L+x^{-2}{a}_R,g_L⟩+⟨x^2{a}_L+a_R,g_R⟩+⟨b_L+x^2{b}_R,h_L⟩+⟨x^{-2}{b}_L+b_R,h_R⟩+$$ $$+(x^2⟨a_L,b_R⟩+x^{-2}⟨a_R,b_L⟩+c)\cdot u=$$ $$=x^{-1}⟨x{a}_L+x^{-1}{a}_R,g_L⟩+x⟨x{a}_L+x^{-1}{a}_R,g_R⟩+x⟨x^{-1}{b}_L+x{b}_R,h_L⟩+x^{-1}⟨x^{-1}{b}_L+x{b}_R,h_R⟩+$$ $$+⟨x{a}_L+x^{-1}{a}_R,x^{-1}{b}_L+x{b}_R⟩u=$$ $$=H(x^{-1}(x{a}_L+x^{-1}{a}_R),x(x{a}_L+x^{-1}{a}_R),x(x^{-1}{b}_L+x{b}_R),x^{-1}(x^{-1}{b}_L+x{b}_R),⟨x{a}_L+x^{-1}{a}_R,x^{-1}{b}_L+x{b}_R⟩)=$$ $$=H(x^{-1}\hat{a},x\hat{a},x\hat{b},x^{-1}\hat{b},⟨\hat{a},\hat{b}⟩)$$

or it equals to $H({\hat{a}}_L,{\hat{a}}_R,{\hat{b}}_L,{\hat{b}}_R,⟨\hat{a},\hat{b}⟩)$ over the new generators $\hat{g},\hat{h}$.