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

There exist different variants of this inner product argument. In some versions, none of the values ($\overrightarrow{a}$, $\overrightarrow{b}$ and $z$) are given, only commitments. In some other version, which is interesting to us and that I will explain here, only $\overrightarrow{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:

Then notice that

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 $\overrightarrow{a}$, such that $⟨\overrightarrow{a},\overrightarrow{b}⟩=z$? We could just reveal $\overrightarrow{a}$ and let anyone verify that indeed, hashing it gives out $h$, and that it also verifies the equation $⟨\overrightarrow{a},\overrightarrow{b}⟩=z$.

Obliviously, we have to reveal $\overrightarrow{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 $\overrightarrow{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:

Where the size of $\overrightarrow{a^{\prime }}$ is half the size of $\overrightarrow{a}$, and as such the final opening proof ($\overrightarrow{a^{\prime }}$) 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 ($lo{g}_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:

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:

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 $⟨\overrightarrow{x},\overrightarrow{G}⟩$ for $\overrightarrow{x}=(x_1,\cdots ,x_k)$ and $\overrightarrow{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$:

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

The rest is known to both:

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

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 $\overrightarrow{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:

1. The prover first sends a commitment to the polynomial $f$.
2. 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$.
3. The prover sends the result of the evaluation, $z$, as well as a proof.

Does that make sense? Of course what’s interesting to us is the proof, and how the prover uses that random $x$.

Reduced problem

First, the prover cuts everything in half. Then they use $x$ to construct linear combinations of these cuts:

• $\overrightarrow{a^{\prime }}=x^{-1}\left(\begin{array}{c}{a}_1\\ a_2\end{array}\right)+x\left(\begin{array}{c}{a}_3\\ a_4\end{array}\right)$
• $\overrightarrow{b^{\prime }}=x\left(\begin{array}{c}{b}_1\\ b_2\end{array}\right)+x^{-1}\left(\begin{array}{c}{b}_3\\ b_4\end{array}\right)$
• $\overrightarrow{G^{\prime }}=x\left(\begin{array}{c}{G}_1\\ G_2\end{array}\right)+x^{-1}\left(\begin{array}{c}{G}_3\\ G_4\end{array}\right)$

This is how the problem is reduced to $⟨\overrightarrow{a^{\prime }},\overrightarrow{b^{\prime }}⟩=z^{\prime }$.

At this point, the prover can send $\overrightarrow{a^{\prime }}$, $\overrightarrow{b^{\prime }}$, and $z^{\prime }$ and the verifier can check if indeed $⟨\overrightarrow{a^{\prime }},\overrightarrow{b^{\prime }}⟩=z^{\prime }$. But that wouldn’t make much sense would it? Here we also want:

• a proof that proving that statement is the same as proving the previous statement ($⟨\overrightarrow{a},\overrightarrow{b}⟩=z$)
• a way for the verifier to compute $z^{\prime }$ and $b^{\prime }$ and $A^{\prime }$ (the new commitment) by themselves.

The actual proof

The verifier can compute $\overrightarrow{b^{\prime }}$ as they have everything they need to do so.

What about $A^{\prime }$, the commitment of $\overrightarrow{a^{\prime }}$ which uses the new $\overrightarrow{G^{\prime }}$ basis. It should be the following value:

So to compute this new commitment, the verifier needs:

• the previous commitment $A$, which they already have
• some powers of $x$, which they can compute
• two curve points $L_a$ and $R_a$, which the prover will have to provide to them

What about $z^{\prime }$? Recall:

• $\overrightarrow{a^{\prime }}=\left(\begin{array}{c}{x}^{-1}{a}_1+x{a}_3\\ x^{-1}{a}_2+x{a}_4\end{array}\right)$
• $\overrightarrow{b^{\prime }}=\left(\begin{array}{c}x{b}_1+x^{-1}{b}_3\\ x{b}_2+x^{-1}{b}_4\end{array}\right)$

So the new inner product should be:

Similarly to $A^{\prime }$, the verifier can recompute $z^{\prime }$ from the previous value $z$ and two scalar values $L_z$ and $R_z$ which the prover needs to provide.

So in the end, the proof has becomes:

• the vector $\overrightarrow{a^{\prime }}$ which is half the size of $\overrightarrow{a}$
• the $L_a,R_a$ curve points (around two field elements, if compressed)
• the $L_z,R_z$ scalar values

We can update our previous diagram:

In our example, the naive proof was to reveal $\overrightarrow{a}$ which was 4 field elements. We are now revealing instead 2 + 2 + 2 = 6 field elements. This is not great, but if $\overrightarrow{a}$ was much larger (let’s say 128), the reduction in half would still be of 64 + 2 + 2 = 68 field elements. Not bad no? We can do better though… Stay tuned for the next post.