Inner Product Arguments

中文版本: 内积证明

Introduction

You might have heard of Bulletproofs: It’s a type of zero knowledge proof that is used for example by Monero, and that does not require a trusted setup. The core of this proof system is the Inner Product Argument ¹, a trick that allows a prover to convince a verifier of the correctness of an “inner product”. An inner product is the component by component product of two vectors:

$$\vec a \cdot \vec b = a_0 b_0 + a_1 b_1 + a_2 b_2 + \cdots + a_{n-1} b_{n-1}$$

where $\vec a = (a_0, a_1, \ldots, a_{n-1})$ and $\vec b = (b_0, b_1, \ldots, b_{n-1})$.

One interesting case is where we set the vector $\vec b$ to be the powers of some number $z$, i.e. $\vec b = (1, z, z^2, \ldots, z^{n-1})$. Then the inner product becomes the evaluation of the polynomial

$$f(X) = \sum_{i=1}^{n-1} a_i X^i$$

at $z$.

Inner Product Arguments work on Pedersen Commitments. I have previously written about KZG commitments, and Pedersen commitments are similar in that the commitment is in an elliptic curve. However a difference is that they do not require a trusted setup. Here is a comparison of the KZG commitment scheme and using Pedersen combined with an Inner Product Argument as a Polynomial Commitment Scheme (PCS):

	Pedersen+IPA	KZG
Assumption	Discrete log	Bilinear group
Trusted setup	No	Yes
Commitment size	1 Group element	1 Group element
Proof size	2 log n Group elements	1 Group element
Verification	O(n) group operations	1 Pairing

Basically, compared to KZG commitments, our commitment scheme is less efficient. Proofs are larger ($O(\log n)$), which wouldn’t be the end of the world as logarithmic is still very small. But unfortunately, the verifier has to do a linear amount of work, so they are not succinct. This makes them impractical for some applications. However in some cases this can be worked around.

• One example is my writeup on multiopenings. In this case, the trick is that you can aggregate many openings into a single one.
• The Halo system ², where the linear cost of many openings is aggregated

In both of these examples, the trick is to amortize many openings. If you only want to open a single polynomial, then it’s tough and you have to incur the full cost, though.

However, the big advantage is that Pedersen and Inner Product Arguments come with much fewer assumptions, in particular a pairing is not needed and they don’t require a trusted setup.

Pedersen commitments

Before we can discuss Inner Product Arguments, we need to discuss the data structure that they operate on: Pedersen commitments. In order to use Pedersen commitments, we need an elliptic curve $G$. Let’s quickly remind ourselves what you can do in an elliptic curve (I will use additive notation because I think it is the more natural one):

1. You can add two elliptic curve elements $g_0 \in G$ and $g_1 \in G$: $h = g_0 + g_1$
2. You can multiply an element $g \in G$ with a scalar $a \in \mathbb F_p$, where $p$ is the curve order of $G$ (i.e. the number of elements): $h = a g$

There is no way to compute the “product” of two curve elements: the operation “$h * h$” is not defined, so you cannot compute “$h * h = a g * a g = a^2 g$”; as opposed to multiplying by a scalar; so $2 h = 2 a g$, for example, is easy to compute.

Another important property is that there is no efficient algorithm to compute “discrete logarithms”. The meaning of this is that given $h$ and $g$ with the property that $h=ag$, if you don’t know $a$ it is computationally infeasible to find $a$. We call $a$ the discrete logarithm of $h$ with respect to $g$.

Pedersen commitments make use of this infeasibility to construct a commitment scheme. Let’s say you have two points $g_0$ and $g_1$ and their discrete logarithm with respect to each other (i.e. the $x \in \mathbb F_p$ such that $g_1 = x g_0$) is unknown, then we can commit to two numbers $a_0, a_1 \in \mathbb F_p$:

$$C = a_0 g_0 + a_1 g_1$$

$C$ is an element of the elliptic curve $G$.

To reveal the commitment, the prover gives the verifier the numbers $a_0$ and $a_1$. The verifier computes $C$ and if it matches will accept.

The central property of a commitment scheme is that it is binding. So given $C=a_0 g_0 + a_1 g_1$, could a cheating prover come up with $b_0, b_1 \in \mathbb F_p$ such that the verifier will accept them, i.e. such that $C = b_0 g_0 + b_1 g_1$ but with $b_0, b_1 \not= a_0, a_1$?

If someone can do this, then they could also find the discrete logarithm. Here is why: We know that $a_0 g_0 + a_1 g_1 = b_0 g_0 + b_1 g_1$, and by regrouping the terms on both sides of the equation we get

$$(a_0 - b_0) g_0 = (b_1 - a_1) g_1$$

Either $a_0 - b_0$ or $b_1 - a_1$ have to be not equal to zero. Let’s say it’s $a_0 - b_0$, then we get:

$$g_0 = \frac{b_1 - a_1}{a_0 - b_0} g_1 = x g_1$$

for $x = \frac{b_1 - a_1}{a_0 - b_0}$. Thus we’ve found $x$. Since we know this is a hard problem, in practice no attacker can perform this.

This means it’s computationally infeasible for an attacker to find alternative $b_0, b_1$ to reveal for the commitment $C$. (They definitely do exist, they are just computationally infeasible to find – similar to finding a collision for a hash function).

We can generalize this and commit to a vector, i.e. a list of scalars $a_0, a_1, \ldots, a_{n-1} \in \mathbb F_p$. We just need a “basis”, i.e. an equal number of group elements that don’t have known discrete logarithms between them. Then we can compute the commitment

$$C = a_0 g_0 + a_1 g_1 + a_2 g_2 + \ldots + a_{n-1} g_{n-1}$$

This gives us a vector commitment, although with quite a bad complexity: In order to reveal any element, all elements of the vector have to be revealed. But there is one redeeming property: The commitment scheme is additively homomorphic. This means that if we have another commitment $D = b_0 g_0 + b_1 g_1 + b_2 g_2 + \ldots + b_{n-1} g_{n-1}$, then it’s possible to just add the two commitments to get a new commitment to the sum of the two vectors $\vec a$ and $\vec b$:

$$C + D = (a_0 + b_0) g_0 + (a_1 + b_1) g_1 + (a_1 + b_1) g_2 + \ldots + (a_{n-1} + b_{n-1}) g_{n-1}$$

Thanks to this additive homomorphic property, this vector commitment actually turns out to be useful.

Inner Product Argument

The basic strategy of the Inner Product Argument is “divide and conquer”: Take the problem and instead of completely solving it, turn it into a smaller one of the same type. At some point, it becomes so small that you can simply reveal everything and prove that the instance is correct.

At each step, the problem size halves. This ensures that after $\log n$ steps, the problem is reduced to size one, so it can be proved trivially.

The idea is that we want to prove that a commitment $C$ is of the form

$$C = \vec a \cdot \vec g + \vec b \cdot \vec h + (\vec a \cdot \vec b) q$$

where $\vec g = (g_0, g_1, \ldots, g_{n-1})$ and $\vec h = (h_0, h_1, \ldots, h_{n-1})$ as well as $q$ are our “basis”, i.e. they are group elements in $G$ and none of their discrete logarithms with respect to each other are known. We also introduced the new notation $\vec a \cdot \vec g$ for a product between a vector of scalars ($\vec a$) and another vector of group elements ($\vec g$), and it is defined as

$$\vec a \cdot \vec g = a_0 g_0 + a_1 g_1 + \cdots + a_{n-1} g_{n-1}$$

So essentially, we are proving that $C$ is a commitment to

• a vector $\vec a$ with basis $\vec g$
• a vector $\vec b$ with basis $\vec h$ and
• their inner product $\vec a \cdot \vec b$ with respect to the basis $q$.

This in itself does not seem very useful – in most applications we want the verifier to know $\vec a \cdot \vec b$, and not just have it hidden in some commitment. But this can be remedied with a small trick which I will come to below.

The argument

We want the prover to convince the verifier that $C$ is of the form $C = \vec a \cdot \vec g + \vec b \cdot \vec h + (\vec a \cdot \vec b) q$. As I mentioned before, instead of doing this outright, we will only reduce the problem by computing another commitment $C'$ in such a way that if the property holds for $C'$, then it also holds for $C$.

In order to do this, the prover and the verifier play a little game. The prover commits to certain properties, after which the verifier sends a challenge, which leads to the next commitment $C'$. Describing it as a game does not mean the proof has to be interactive though: The Fiat-Shamir construction allows us to turn interactive proofs into non-interactive one, by replacing the challenge with a collision-resistant hash function of the commitments.

Statement to prove

The commitment $C$ has the form $C = \vec a \cdot \vec g + \vec b \cdot \vec h + (\vec a \cdot \vec b) q$ with respect to the basis given by $\vec g, \vec h, q$. We call the fact that $C$ has this form the “Inner Product Property”.

Reduction step

Let $m = \frac{n}{2}$

The prover computes

$$z_L = a_m b_0 + a_{m+1} b_1 + \cdots + a_{n-1} b_{m-1} = \vec a_R \cdot \vec b_L \\ z_R = a_0 b_m + a_{1} b_{m+1} + \cdots + a_{m-1} b_{n-1} = \vec a_L \cdot \vec b_R$$

where we’ve defined $\vec a_L$ as the “left half” of the vector $\vec a$ and $\vec a_R$ the “right half” and analogously for $\vec b$.

Then the prover computes the following commitments:

$$C_L = \vec a_R \cdot \vec g_L + \vec b_L \cdot \vec h_R + z_L q \\ C_R = \vec a_L \cdot \vec g_R + \vec b_R \cdot \vec h_L + z_R q \\$$

and send them to the verifier. Then the verifier sends the challenge $x \in \mathbb F_p$ (when using the Fiat-Shamir construction to make this non-interactive, this means that $x$ would be the hash of $C_L$ and $C_R$). The prover uses this to compute the updated vectors

$$\vec a' = \vec a_L + x \vec a_R \\ \vec b' = \vec b_L + x^{-1} \vec b_R$$

which have half the length.

Now the verifier computes the new commitment:

$$C' = x C_L + C + x^{-1} C_R$$

as well as the updated basis

$$\vec g' = \vec g_L + x^{-1} \vec g_R \\ \vec h' = \vec h_L + x \vec h_R$$

Now, if the new commitment $C'$ has the property that it is of the form $C' = \vec a' \cdot \vec g' +\vec b' \cdot \vec h' + \vec a' \cdot \vec b' q$ – then the commitment $C$ fulfills the originall claim.

All the vectors have halved in size – so we have achieved something. From here we replace $C:=C'$, $\vec g := \vec g'$ and $\vec h := \vec h'$ and repeat this step.

I will below go through the maths on why this works, but Vitalik also made a nice visual representation that I recommend to get an intuition.

Final step

When we repeat the step above, we will reduce $n$ by a factor of two each time. At some point, we will encounter $n=1$. At this point we don’t repeat the step anymore. Instead the prover will send $\vec a$ and $\vec b$, which in fact are now only a single scalar each. Then the verifier can simply compute

$$D = a g + b h + a b q$$

and accept the statement if this is indeed equal to $C$, or reject if it is not.

Correctness and soundness

Above I claimed that if $C'$ has the desired form, then it follows that $C$ also has it. I now want to show why this is the case. In order to do this, we need to look at two things:

• Correctness – i.e. given a prover who follows the protocol, can they always convince the verifier that the statement is correct; and
• Soundness – i.e. a dishonest prover cannot convince the verifier of an incorrect statement, except with a very small probability.

Let’s start with correctness. This assumes that the prover is doing everything according to the protocol. Since the prover is following the protocol, we know that $C = \vec a \cdot \vec g + \vec b \cdot \vec h + (\vec a \cdot \vec b) q$ with respect to the basis given by $\vec g, \vec h, q$. We need to show that then $C'= \vec a' \cdot \vec g' +\vec b' \cdot \vec h' + \vec a' \cdot \vec b' q$.

The verifier computes $C' = x C_L + C + x^{-1} C_R$.

$$C' = x C_L + C + x^{-1} C_R \\ = x ( \vec a_R \cdot \vec g_L + \vec b_L \cdot \vec h_R + z_L q) \\ + \vec a_L \cdot \vec g_L + \vec a_R \cdot \vec g_R + \vec b_L \cdot \vec h_L + \vec b_R \cdot \vec h_R + \vec a \cdot \vec b q \\ + x^{-1} (\vec a_L \cdot \vec g_R + \vec b_R \cdot \vec h_L + z_R q)\\ = (x \vec a_R + \vec a_L)\cdot(\vec g_L + x^{-1} \vec g_R) \\ + (\vec b_L + x^{-1} \vec b_R)\cdot(\vec h_L + x \vec h_R) \\ + (x z_L + \vec a \cdot \vec b + x^{-1} z_R) q \\ = (x \vec a_R + \vec a_L)\cdot \vec g' + (\vec b_L + x^{-1} \vec b_R)\cdot \vec h' + (x z_L + \vec a \cdot \vec b + x^{-1} z_R) q$$

So in order for the commitment to have the Inner Product Property, we need to verify that $(x \vec a_R + \vec a_L) \cdot (\vec b_L + x^{-1} \vec b_R) = x z_L + \vec a \cdot \vec b + x^{-1} z_R$. This is true because

$$(x \vec a_R + \vec a_L) \cdot (\vec b_L + x^{-1} \vec b_R) \\ = x \vec a_R \cdot \vec b_L + \vec a_L \cdot \vec b_L + \vec a_R \cdot \vec b_R + x^{-1} \vec a_L \cdot \vec b_R \\ = x z_L + \vec a \cdot \vec b + x^{-1} z_R$$

This concludes the proof of correctness. Now in order to prove soundness, we need the property that a prover can’t start with a commitment $C$ that does not fulfill the Inner Product Property and end up with a $C'$ that does by going through the reduction step.

So let’s assume that the prover committed to $C=\vec a \cdot \vec g + \vec b \cdot \vec h + r q$ for some $r \not= \vec a \cdot \vec b$. If we go through the same process as before, we find

$$C' = (x \vec a_R + \vec a_L)\cdot \vec g' + (\vec b_L + x^{-1} \vec b_R)\cdot \vec h' + (x z_L + r + x^{-1} z_R) q$$

So now let’s assume that the prover managed to cheat, and thus $C'$ fulfills the Inner Product Property. That means that

$$(x \vec a_R + \vec a_L) \cdot (\vec b_L + x^{-1} \vec b_R) = x z_L + r + x^{-1} z_R$$

Expanding the left hand side, we get

$$x \vec a_R \cdot \vec b_L + \vec a \cdot \vec b + x^{-1} \vec a_L \cdot \vec b_R = x z_L + r + x^{-1} z_R$$

Note that the prover can choose $z_L$ and $z_R$ freely, so we cannot assume that they will be according to the above definitions.

Multiplying by $x$ and moving everything to one side we get a quadratic equation in $x$:

$$x^2 ( \vec a_R \cdot \vec b_L - z_L) + x (\vec a \cdot \vec b - r) + (\vec a_L \cdot \vec b_R - z_R )$$

Unless all the terms are zero, this equation has at most two solutions $x \in \mathbb F_p$. But the verifier chooses $x$ after the prover has already committed to their values $r$, $z_L$ and $z_R$. The probability that the prover can successfully cheat is thus extremely small; we typically choose the field $\mathbb F_p$ to be of size ca. $2^{256}$, so the probability that the verifier chooses a value for $x$ such that this equation holds, when the values were not chosen according to the protocol, is vanishingly small.

This concludes the soundness proof.

Only compute basis changes at the end

The verifier has to do two things each round: Compute the challenge $x$ and compute the updates bases $\vec g'$ and $\vec h'$. However, updating the basis $g$ at every round is inefficient. Instead the verifier can simply keep track of the challenge values $x_1$, $x_2$, up to $x_{\ell}$ that they will encounter during the $\ell$ rounds.

Let’s call the basis after round $k$ $\vec g_k, \vec h_k$. The elements $g_\ell$ and $h_\ell$ are scalars (or vectors of length one) because we end the protocol once our vectors have reached length one. Computing $g_\ell$ from $\vec g_0$ is a multiscalar multiplication (MSM) of length $n$. The scalar factors for $\vec g_0$ are the coefficients of the polynomial

$$f_g(X) = \prod_{i=0}^\ell \left(1+x^{-1}_{\ell-i} X^{2^{i}}\right)$$

and the scalar factors for $\vec h_0$ are given by

$$f_h(X) = \prod_{i=0}^\ell \left(1+x_{\ell-i} X^{2^{i}}\right)$$

Using Inner Product Arguments to evaluate polynomials

For our main application – evaluating a polynomial defined by $f(x) = \sum_{i=1}^{n-1} a_i x^i$ at a point $z$ – we want to make some small additions to this protocol.

• Most importantly, we want to know the result $f(z) = \vec a \cdot \vec b$, and not just that $C$ has the “Inner Product Property”
• $\vec b = (1, z, z^2, ..., z^{n-1})$ is known to the verifier. We can thus make things a bit easier by removing it from the commitment

How to construct the commitment

If we want to verify a polynomial evaluation for the polynomial $f(x) = \sum_{i=1}^{n-1} a_i x^i$, then we are typically working from a commitment $F = \vec a \cdot \vec g$. The prover would send the verifier the evaluation $y=f(z)$.

So it seems like the verifier can just compute the initial commitment $C=\vec a \cdot \vec g + \vec b \cdot \vec h + \vec a \cdot \vec b q = F + \vec b \cdot \vec h + f(z) q$, since they know $\vec b = (1, z, z^2, ..., z^{n-1})$, and start the protocol.

But not so fast. In most cases, $F$ will be a commitment that is generated by the prover. A malicious prover could cheat by, for example, committing to $F = \vec a \cdot \vec g + tq$. In this case, they would be able to prove that $f(z) = y - t$, because they have effectively shifted the result.

To prevent this, we need to do a small change to the protocol. After receiving the commitment $F$ and the evaluation $y$, the verifier generates a scalar $w$ and rescales the basis $q:=wq$. Afterwards the protocol can proceed as usual. Because the prover can’t predict what $w$ is going to be, they can’t succeed (except with very small probability) at manipulating the result to be something other then $f(z)$.

Note that we also need to stop the prover from manipulating the vector $\vec b$ if what we want is a generic inner product – but for a polynomial evaluation, we can simply get rid of that part alltogether so I won’t go into the details.

How to get rid of the second vector

Note that the verifier knows the vector $\vec b = (1, z, z^2, ..., z^{n-1})$ if what we want is to compute a polynomial evaluation. Given the challenges $x_0, x_1, \ldots, x_\ell$ they can simply compute the final result $b_\ell$ using the same technique as demonstrated in “compute the basis change at the end”.

We can thus remove the second vector from all commitments and simply compute $b_\ell$. This means the verifier has to be able to compute the final version $b_\ell$ from the initial vector $\vec b_0 = (1, z, z^2, ..., z^{n-1})$. Since the folding process for $\vec b$ is the same as that for the basis vector $\vec g$, the coefficients of the previously defined polynomial $f_g$ will define the linear combination, in other words $b_\ell=f_g(z)$.

Creating an IPA for a polynomial in coefficient form

So far, we have used an Inner Product Argument to evaluate a polynomial that is committed to by its coefficients, which are the $f_i$ for a polynomial defined by $f(X) = \sum_{i=0}^{n-1} f_i X^i$. However, often we want to work with a polynomial that is defined using its evaluations on a domain $x_0, x_1, \ldots, x_{n-1}$. Since any polynomial of degree less than $n-1$ is uniquely defined by the evaluations $f(x_0), f(x_1), \ldots, f(x_{n-1})$ these two are completely equivalent. However, transforming between the two can be computationally expensive: it costs $O(n \log n)$ operations if the domain admits an efficient Fast Fourier Transform, and otherwise it’s $O(n^2)$.

To avoid this cost, we try to simply never change to coefficient form. This can be done by changing the commitment to $f$ by committing to the evaluations instead of the coefficients:

$$C = f(x_0) g_0 + f(x_1) g_1 + \cdots + f(x_{n-1}) g_{n-1}$$

This means that our $\vec a$ vector in the IPA is now given by $\vec a = (f(x_0), f(x_1), \ldots, f(x_{n-1}))$

The barycentric formula allows us now to compute an IPA to evaluate a polynomial using this new commitment. It says that

$$f(z) = A(z)\sum_{i=0}^{n-1} \frac{f(x_i)}{A'(x_i)} \frac{1}{z-x_i}$$

If we choose the vector $\vec b$ to be

$$b_i = \frac{A(z)}{A'(x_i)} \frac{1}{z-x_i}$$

we get that $\vec a \cdot \vec b = f(z)$, and thus an IPA with this vector can be used to prove the evaluation of a polynomial which is itself in evaluation form. Other than this, the strategy is exactly the same.

1. Bootle, Cerulli, Chaidos, Groth, Petit: Efficient Zero-Knowledge Arguments forArithmetic Circuits in the Discrete Log Setting ↩

2. Bowe, Grigg, Hopwood: Recursive Proof Composition without a Trusted setup ↩