# What is an inner product argument? posted 14 hours ago

The inner product argument is the following construction: given the commitments (for now let's say the hash) of two vectors $\vec{a}$ and $\vec{b}$ of size $n$ and with entries in some field $\mathbb{F}$, prove that their inner product $\langle \vec{a}, \vec{b} \rangle$ is equal to $z$.

There exist different variants of this inner product argument. In some versions, none of the values ($\vec{a}$, $\vec{b}$ and $z$) are given, only commitments. In some other version, which is interesting to us and that I will explain here, only $\vec{a}$ is unknown.

## How is that useful?

Inner products arguments are useful for several things, but what we're using them for in Mina is polynomial commitments. The rest of this post won't make too much sense if you don't know what a polynomial commitment is, but briefly: it allows you to commit to a polynomial $f$ and then later prove its evaluation at some point $s$. Check my post on Kate polynomial commitments for more on polynomial commitment schemes.

How does that translate to the inner product argument though? First, let's see our polynomial $f$ as a vector of coefficients:

$$ \vec{f} = (f_0, \cdots, f_n) \text{ such that } f(x) = f_0 + f_1 x + f_2 x^2 + \cdots + f_n x^n $$

Then notice that

$$ f(s) = \langle \vec{f}, (1, s, s^2, \cdots, s^{n}) \rangle $$

And here's our inner product again.

## The idea behind Bootleproof-type of inner product argument

The inner product argument protocol I'm about to explain was invented by Bootle et al. It was later optimized in the Bulletproof paper (hence why we unofficially call the first paper bootleproof), and then some more in the Halo paper. It's the later optimization that I'll explain here.

### A naive approach

So before I get into the weeds, what's the high-level? Well first, what's a naive way to prove that we know the pre-image of a hash $h$, the vector $\vec{a}$, such that $\langle\vec{a}, \vec{b}\rangle = z$? We could just reveal $\vec{a}$ and let anyone verify that indeed, hashing it gives out $h$, and that it also verifies the equation $\langle\vec{a}, \vec{b}\rangle = z$.

$$ \boxed{ \begin{align} & \langle \vec{a}, \vec{b} \rangle = z\ & \text{given } \vec{b} \text{, } z \text{, and a hash of } \vec{a} \end{align} } \; \overleftarrow{\text{open proof}} \; \boxed{\vec{a}} $$

Obliviously, we have to reveal $\vec{a}$ itself, which is not great. **But we'll deal with that later, trust me**. What we want to tackle first here is the proof size, which is the size of the vector $\vec{a}$. Can we do better?

### Reducing the problem to a smaller problem to prove

The inner product argument reduces the opening proof by using an intermediate reduction proof:

$$ \boxed{\begin{aligned} & \langle \vec{a}, \vec{b} \rangle = z\\ & \text{given } \vec{b} \text{, } z \text{, and a hash of } \vec{a} \end{aligned}} \; \overleftarrow{\text{reduction proof}} \; \boxed{\begin{aligned} & \langle \vec{a'}, \vec{b'} \rangle = z'\\ & \text{ given } \vec{b'} \text{, } z' \text{, and a hash of } \vec{a'} \end{aligned}} \; \overleftarrow{\text{open proof}} \; \boxed{\vec{a'}} $$

Where the size of $\vec{a'}$ is half the size of $\vec{a}$, and as such the final opening proof ($\vec{a'}$) is half the size of our naive approach.

The reduction proof is where most of the magic happens, and this reduction can be applied many times ($log_2(n)$ times to be exact) to get a final opening proof of size 1. Of course the entire proof is not just the final opening proof of size 1, but all the elements involved in the reduction proofs. It can still be much smaller than the original proof of size $n$.

So most of the proof size comes from the multiple reduction subproofs that you'll end up creating on the way. **Our proof is really a collection of miniproofs or subproofs.**

## One last thing before we get started: Pedersen hashing and commitments

To understand the protocol, you need to understand commitments. I've used hashing so far, but hashing with a hash function like SHA-3 is not great as it has no convenient mathematical structure. We need algebraic commitments, which will allow us to prove things on the committed value without revealing the value committed. Usually what we want is some homomorphic property that will allow us to either add commitments together or/and multiply them together.

For now, let's see a simple non-hiding commitment: a Pedersen hash. To commit to a single value $x$ simply compute:

$$ x G $$

where the discrete logarithm of $G$ is unknown. To open the commitment, simply reveal the value $x$.

We can also perform multi-commitments with Pedersen hashing. For a vector of values $(x_1, \cdots, x_k)$, compute:

$$ x_1 G_1 + \cdots + x_k G_k $$

where each $G_i$ is distinct and has an unknown discrete logarithm as well. I'll often shorten the last formula as the inner product $\langle \vec{x}, \vec{G} \rangle$ for $\vec{x} = (x_1, \cdots, x_k)$ and $\vec{G} = (G_1, \cdots, G_k)$. To reveal a commitment, simply reveal the values $x_i$.

Pedersen hashing allow commitents that are non-hiding, but binding, as you can't open them to a different value than the originally comitted one. And as you can see, adding the commitment of $x$ and $y$ gives us the commitment of $x+y$:

$$xG + yG = (x+y)G$$

which will be handy in our inner product argument protocol

## The protocol

### Set up

Here are the settings of our protocol. Known only to the prover, is the secret vector

$$\vec{a} = (a_1, a_2, a_3, a_4)$$

The rest is known to both:

- $\vec{G} = (G_1, G_2, G_3, G_4)$, a basis for Pedersen hashing
- $A = \langle \vec{a}, \vec{G} \rangle$, the commitment of $\vec{a}$
- $\vec{b} = (b_1, b_2, b_3, b_4)$, the powers of some value $s$ such that $\vec{b} = (1, s, s^2, s^3)$
- the result of the inner product $z = \langle \vec{a}, \vec{b} \rangle$

For the sake of simplicity, let's pretend that this is our problem, and we just want to halve the size of our secret vector $\vec{a}$ before revealing it. As such, we will only perform a single round of reduction. But you can also think of this step as being already the reduction of another problem twice as large.

We can picture the protocol as follows:

- The prover first sends a commitment to the polynomial $f$.
- The verifier sends a point $s$, asking for the value $f(s)$. To help the prover perform a proof of correct evaluation, they also send a random challenge $x$.
- The prover sends the result of the evaluation, $z$, as well as a proof.