# [−][src]Module bulletproofs::inner_product_proof

The inner_product_proof module contains API for producing a compact proof of an inner product of two vectors.

# Inner product argument protocol

These notes explain how the protocol is implemented in the InnerProductProof type.

We want to prove the relation $\operatorname{PK}\left\{ ({\mathbf{G}}, {\mathbf{H}} \in {\mathbb G}^n, P', Q \in {\mathbb G}; {\mathbf{a}}, {\mathbf{b}} \in {\mathbb Z_p}^n) : P' = {\langle {\mathbf{a}}, {\mathbf{G}} \rangle} + {\langle {\mathbf{b}}, {\mathbf{H}} \rangle} + {\langle {\mathbf{a}}, {\mathbf{b}} \rangle} Q \right\}$ where $$n = 2^{k}$$ is a power of $$2$$.

## Prover’s algorithm

To start, we sketch the interactive version of this protocol, and then describe the optimizations discussed in the Bulletproofs paper for the non-interactive version.

The protocol consists of $$k = \lg n$$ rounds, indexed by $$j = k,\ldots,1$$. In the $$j$$-th round, the prover computes \begin{aligned} L_{j} &\gets {\langle {\mathbf{a}}_{\operatorname{lo}}, {\mathbf{G}}_{\operatorname{hi}} \rangle} + {\langle {\mathbf{b}}_{\operatorname{hi}}, {\mathbf{H}}_{\operatorname{lo}} \rangle} + {\langle {\mathbf{a}}_{\operatorname{lo}}, {\mathbf{b}}_{\operatorname{hi}} \rangle} Q, \\ R_{j} &\gets {\langle {\mathbf{a}}_{\operatorname{hi}}, {\mathbf{G}}_{\operatorname{lo}} \rangle} + {\langle {\mathbf{b}}_{\operatorname{lo}}, {\mathbf{H}}_{\operatorname{hi}} \rangle} + {\langle {\mathbf{a}}_{\operatorname{hi}}, {\mathbf{b}}_{\operatorname{lo}} \rangle} Q, \end{aligned} and sends $$L_{j}, R_{j}$$ to the verifier. The verifier responds with a challenge value $$u_{j} {\xleftarrow{\}}{\mathbb{Z}_p}$$. The prover uses $$u_{j}$$ to compute \begin{aligned} {\mathbf{a}} &\gets {\mathbf{a}}_{\operatorname{lo}} \cdot u_{j} + u_{j}^{-1} \cdot {\mathbf{a}}_{\operatorname{hi}}, \\ {\mathbf{b}} &\gets {\mathbf{b}}_{\operatorname{lo}} \cdot u_{j}^{-1} + u_{j} \cdot {\mathbf{a}}_{\operatorname{hi}}, \end{aligned} the prover and verifier both compute \begin{aligned} {\mathbf{G}} &\gets {\mathbf{G}}_{\operatorname{lo}} \cdot u_{j}^{-1} + u_{j} \cdot {\mathbf{G}}_{\operatorname{hi}}, \\ {\mathbf{H}} &\gets {\mathbf{H}}_{\operatorname{lo}} \cdot u_{j} + u_{j}^{-1} \cdot {\mathbf{H}}_{\operatorname{hi}}, \end{aligned} and use these vectors (all of length $$2^{j-1}$$) for the next round. After the last ($$j = 1$$) round, the prover sends $$a, b = {\mathbf{a}}_{0}, {\mathbf{b}}_{0}$$ to the verifier, who accepts if and only if \begin{aligned} L_{1} u_{1}^{2} + \cdots + L_{k} u_{k}^{2} + P' + R_{k} u_{k}^{-2} + \cdots + R_{1} u_{1}^{-2}&\overset ? = aG + bH + abQ, \end{aligned} where $$G, H = {\mathbf{G}}_{0}, {\mathbf{H}}_{0}$$.

To make the protocol noninteractive, we replace the transmission of the $$L_{j}$$ and $$R_{j}$$ and the response $$u_{j}$$ with a Fiat-Shamir challenge, so that each $$u_{j}$$ is generated as a hash of the transcript $$L_{k},R_{k},\ldots,L_{j},R_{j}$$. At the end of the prover’s computation, they send $$a,b,L_{k},R_{k},\ldots,L_{1},R_{1}$$ to the verifier.

## Verifier’s algorithm

Since the final $$G$$ and $$H$$ values are functions of the challenges $$u_{k},\ldots,u_{1}$$, the verifier has to compute them as part of the verification process. However, while the prover needs to compute the intermediate vectors $${\mathbf{G}}$$, $${\mathbf{H}}$$ in order to compute the $$L_{j}$$ and $$R_{j}$$, the verifier doesn’t, and can compute the final $$G$$, $$H$$ directly from the vectors $${\mathbf{G}}$$, $${\mathbf{H}}$$ and the challenges $$u_{k}, \ldots, u_{1}$$.

Let $${\mathbf{G}}^{(j)}$$ be the value of $${\mathbf{G}}$$ in the $$j$$-th round, and let $$G_{i}$$ be the $$i$$-th entry of the initial vector $${\mathbf{G}}^{(k)} = (G_{0}, \ldots, G_{n-1})$$. We have \begin{aligned} {\mathbf{G}}^{(j-1)} = ({\mathbf{G}}^{(j)})_{\operatorname{lo}} u_{j}^{-1} + ({\mathbf{G}}^{(j)})_{\operatorname{hi}} u_{j},\end{aligned} so the coefficient of $$G_{i}$$ in the final $$G$$ value is \begin{aligned} s_{i} &= u_{k}^{b(i,k)} \cdots u_1^{b(i,1)},\end{aligned} where $$b(i,j)$$ is either $$-1$$ or $$+1$$, according to whether $$G_{i}$$ appears in the left or right half of $${\mathbf{G}}^{(j)}$$. Since $$G_{i}$$ appears in the $$(i \mod 2^{j})$$-th entry of $${\mathbf{G}}^{j}$$, this is $b(i,j) = \begin{cases} -1 & \text{if (i \mod 2^{j}) < 2^{j-1} }\\ +1 & \text{if (i \mod 2^{j}) \ge 2^{j-1} }\\ \end{cases}.$ But this is exactly $b(i,j) = \begin{cases} -1 & \text{if bit j-1 of i is 0} \\ +1 & \text{if bit j-1 of i is 1} \\ \end{cases}.$ This shows that $$G = {\langle {\mathbf{s}}, {\mathbf{G}} \rangle}$$. This formula differs slightly from the one in the paper, because we index vectors and bits from $$0$$.

Since $$H$$ is computed similarly, but with the roles of $${\mathbf{H}}_{\operatorname{lo}}$$ and $${\mathbf{H}}_{\operatorname{hi}}$$ reversed, a similar argument shows that $$H = {\langle 1/{\mathbf{s}}, {\mathbf{H}} \rangle}$$.

Notice that if $$i'$$ is the bitwise $$\texttt{NOT}$$ of $$i$$, then $$s_{i'} = 1/s_{i}$$, and as $$i$$ runs from $$0$$ to $$(2^k - 1)$$, $$i'$$ runs from $$(2^k - 1)$$ to $$0$$, so the vector of inverses $$1/{\mathbf{s}}$$ is a reversed vector $${\mathbf{s}}$$ and no additional computation is required to obtain the $$1/s_{i}$$.

### Verification equation

The verifier’s computation then becomes \begin{aligned} P' \overset ? =& aG +bH +abQ - \sum_{j=1}^{k} \left( L_{j} u_{j}^{2} + u_{j}^{-2} R_{j} \right) \\ =& {\langle a \cdot {\mathbf{s}}, {\mathbf{G}} \rangle} + {\langle b /{\mathbf{s}}, {\mathbf{H}} \rangle} + abQ - \sum_{j=1}^{k} \left( L_{j} u_{j}^{2} + u_{j}^{-2} R_{j} \right), \end{aligned} a single multiscalar multiplication with $$n + n + 1 + k + k = 2(n+k) + 1$$ points.

In order to combine the computation above with other checks in a parent protocol, we can provide these scalars:

$\{u_{1}^{2}, \dots, u_{k}^{2}, u_{1}^{-2}, \dots, u_{k}^{-2}, s_0, \dots, s_{n-1}\}.$

Use the InnerProductProof::verification_scalars method to produce these scalars for a given inner product proof.

## Structs

 InnerProductProof

## Functions

 inner_product Computes an inner product of two vectors ${\langle {\mathbf{a}}, {\mathbf{b}} \rangle} = \sum_{i=0}^{n-1} a_i \cdot b_i.$ Panics if the lengths of $$\mathbf{a}$$ and $$\mathbf{b}$$ are not equal.