# Polynomial commitments with the inner product argument

Joseph Spadavecchia \<[e-mail]\>

X:1
T:Inner Product Symphony
M: 4/4
C:Trad.
K:G
|:c1G1 c2G2|c3G3 c4G4|c5G5 c6G6|c7G7 c8G8|

$$
\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\group}[1]{\mathbb{#1}}
\newcommand{\vcom}[1]{\mathsf{Com}(\vec{#1})}
\newcommand{\com}[1]{\mathsf{Com}(#1)}
\newcommand{\ip}[2]{\langle \vec{#1}, \vec{#2} \rangle}
\newcommand{\pip}[2]{\langle #1, #2 \rangle}
\newcommand{\ewsum}[2]{\vec{#1} + \vec{#2}}
\newcommand{\pewsum}[2]{#1 + #2}
\newcommand{\hash}[1]{\mathtt{#1}}
\newcommand{\left}[1]{\mathcal{L}_{\vec{#1}}}
\newcommand{\right}[1]{\mathcal{R}_{\vec{#1}}}
\newcommand{\fold}[2]{\mathsf{fold}(\vec{#1}, #2)}
\newcommand{\transcript}[0]{\mathtt{transcript}}
$$

Inner product arguments are useful for polynomial commitments.

Disclaimer: some stuff in here is wrong (this is personal learning material)

## Polynomials

A polynomial $p(x)$ of degree $n$ can be represented as a vector of $n + 1$ coefficients: $(c_0, \ldots, c_n)$ such that

$$
p(x) = c_0 + c_2x + c_3x^2 + \cdots + c_nx^n
$$

## Inner product

Given two vectors $\vec{a}, \vec{b}$ the inner product is defined as

$$
\ip{a}{b} = a_0b_0 + a_1b_1 + \cdots + a_nb_n
$$

## Inner product argument

The inner product argument is used to prove the evaluation of a polynomial at a given point, optionally without revealing what the polynomial is (i.e. whilst keeping the coefficients private).

More formally, given a secret polynomial $p(X)$, represented as a vector of coefficients

$$
\vec{p} = (c_0, c_1, \ldots, c_n)
$$

and the evaluation point $x$, which when substituted into the polynomial is also represented as a vector of powers of $x$

$$
\vec{x} = (x^0, x^1, \ldots, x^n),
$$

we wish to prove

\begin{aligned}
y &= p(x) \\
&= c_0 + c_2x + c_3x^2 + \cdots + c_nx^n \\
&= \ip{p}{x}
\end{aligned}

without disclosing $\vec{p}$.

We prove the inner product $\ip{p}{x} = y$ using something called the inner product argument. It is called an argument because it is a proof that is only computationally binding under the discrete logarithm problem hardness assumption.

To understand how to construct an inner product argument we need to understand a few primitives: cryptographic commitments, a simple zero-knowledge protocol, the Fiat–Shamir heuristic and vector commitments.

## Cryptographic commitments

A cryptographic commitment is a way for you to bind to a value without revealing it and then later use the value to prove something. The process of later proving the commitment or using it in a proof is called *opening the commitment*.

**Analogy:** A good way to think of a commitment is like putting a letter into an envelope and sealing it, such that only you know the contents of the letter. For example, perhaps your letter contains who you think will win a tennis match. After the game is complete and the winner is known, you can open your letter and prove to everyone what your prediction about the match was.

**Properties:** Cryptographic commitments have two important properties

* **Binding** - It is not possible for the committer to open the commitment to any value other than the one committed to
* **Hiding** - A commitment reveals nothing about the comitted value

The hiding property is optional. A commitment scheme that does not have this property is sometimes called a non-hiding commitment scheme.

**Construction:** The simplest kind of a commitment scheme is one in which opening reveals all of the underlying data. Here's a construction of such a scheme for committing to field elements using elliptic curve scalar multiplication. Suppose we have

- $\mathbb{F}_p$ a prime order field, with very large $p$ (e.g. $2^{256}$).
- $G$ a publically agreed generator point over an elliptic curve group $E(\mathbb{F}_p)$

Then the commitment scheme consists of three operations.

$$
\mathsf{commit}(x) \Rightarrow xG \\
\mathsf{open}(c) \Rightarrow x \\
\mathsf{verify}(c, x) \Rightarrow c \stackrel{?}= xG
$$

where $x \in \mathbb{F}_p$ is the value being committed to and the commitment $c = \mathsf{commit}(x)$ is a curve point.

The argument $x$ of the $\mathsf{commit}$ function is data that is only known to the committer (until the commitment is opened). To open the commitment $c$, they simply provide the committed value.

Finally, given the commitment and the opening, we can verify whether the input was the value originally committed to using the $\mathsf{verify}$ function.

**Properties:** In terms of the binding property, here scalar multiplication is used like a one-way function based on the hardness assumption of the elliptic curve discrete logarithm problem (ECDLP).

This commitment scheme is non-hiding because the opening proof reveals the value committed to, but if we wanted to add the hiding property we would use another publicly agreed curve point $H$ (for which no one knows the discrete logarithm), define $\mathsf{commit}(x, r) = xG + rH$ and then update $\mathsf{commit}$ and $\mathsf{verify}$ accordingly. This is discussed in later sections.

**Algebraic and homomorphic properties:** These commitments are algebraic (i.e. they do not use a boolean-based cryptographic hash function) and have homomorphic properties: you can add commitments together to form another commitment of the added committed values. For example, if you have commitments $A$ and $B$, you can perform:

$$
\begin{aligned}
A + B &= \mathsf{commit}(a) + \mathsf{commit}(b) \\
&= aG + bG \\
&= (a + b)G \\
&= \mathsf{commit}(a + b)
\end{aligned}
$$

In other words, the sum of commitments $A$ and $B$ is equal to the commitment of the sum of the two committed values $a$ and $b$. This is possible because in such a scheme because scaling distributes over addition.

**Protocols:** Commitments are often used in protocols between provers and verifiers. The following illustration provides an example with a prover named Peggy and a verifier named Victor.
$$
\begin{array}{lcll}
\textbf{Peggy} & \textbf{ } & \textbf{Victor} & ~ \\
\begin{aligned}\mathsf{\small input} \\ \mathsf{\small blinder}\end{aligned} ~\Bigg\} \rightarrow \boxed{\mathsf{\small commit}} & \longrightarrow & \mathsf{\small commitment} & ~ \\
~ & \vdots & ~ & ~ \\
~ & ~ & ~ & ~ \\
\mathsf{\small commitment} \rightarrow \boxed{\mathsf{\small open}} & \longrightarrow & \mathsf{\small input, blinder} & ~ \\
~ & \vdots & ~ & ~ \\
~ & ~ & \begin{aligned}\mathsf{\small commitment} \\ \mathsf{\small input} \\ \mathsf{\small blinder}\end{aligned} ~\Bigg\} \rightarrow \boxed{\mathsf{\small verify}} \rightarrow \mathsf{\small true/false}
\end{array}
$$

Here Peggy commits to an input using a blinder, obtains the commitment and sends it to Victor. The interlocutors continue their protocol, but eventually
to convince Victor of her claims, Peggy must send the opening proof to her earlier commitment. Victor verifies the opening (i.e. the input and blinder) against the commitment.

If the verification fails, then Victor knows that Peggy was trying to trick him, otherwise Victor has sufficient assurances that Peggy was telling the truth.

Note: The protocol given here is interactive, but as we will see later protocols like this can be made non-interactive.

## A simple zero-knowledge protocol

Going back to our inner product argument, how can we prove the inner product $\ip{p}{x} = y$ without disclosing $\vec{p}$?

This is where zero-knowledge protocols come to the rescue! Perhaps one of the most fundamental zero-knowledge protocols can be constructed with *Schnorr's Identity Protocol*.

This protocol is best understood in the context of a protocol between a prover (Peggy) and a verifier (Victor).

Firstly, the two interlocutors must aggree on some shared information.

* $\field{F}_p$ a prime order field, where $p$ is large (e.g. $2^{256}$)
* Publically agreed generator point $G$ over elliptic curve $E(\field{F_p})$.

Suppose Peggy wants to prove to Victor knowledge of the discrete logarithm of $P = sG$ while keeping $s$ secret, where $s$ is a randomly selected element of $\field{F_p}$ only known to Peggy and $P$ is publically known to both parties.

**Protocol 1:** The simplest protocol would be for Peggy to send $s$ to Victor, who would then verify $sG = P$,

$$
\begin{array}{lcll}
\textbf{Peggy} & \textbf{ } & \textbf{Victor} & ~ \\
\begin{aligned} s, P & \end{aligned} & \stackrel{~\boxed{s}}\longrightarrow &~ \begin{aligned} P&,s \\ P &\stackrel{?}{=} sG ~\big\} \mathsf{verify} \end{aligned} &~ \\
\end{array}
$$

but Victor would learn $s$, so this protocol would fail to deliver the hiding property.

**Protocol 2:** Because of this shortcoming, Peggy could mask $s$ by adding another randomly selected value from $r \in \field{F_p}$.

$$
\begin{array}{lcll}
\textbf{Peggy} & \textbf{ } & \textbf{Victor} & ~ \\
\begin{aligned} &s,P ~ \\ &r \leftarrowtail \field{F_p} \\ \pi &= s + r ~\big\} ~\mathsf{prove} \end{aligned} & \stackrel{\boxed{\pi}}\longrightarrow & ~ \begin{aligned} &P,\pi \\ &\begin{aligned} \pi G &\stackrel{?}{=} (s + r)G \\ &= P + rG \end {aligned} ~\bigg\} \mathsf{verify}
\end{aligned} \\
\end{array}
$$

but Victor would have no way of verifying her proof because he doesn't know $r$.

**Protocol 3:** Peggy observes that she cannot send both $r$ and $\pi$ to Victor -- if she did he could easily compute the secret $s = \pi - r$. She also notices that all Victor really needs to verify her proof is $rG$ since he already knows $P$. Furthermore, because of the discrete logarithm problem hardness assumption, by sending $rG$ Victor cannot learn $r$ and, thus, cannot solve for $s$. Therefore, Peggy updates her protocol to send $R = rG$ instead.

$$
\begin{array}{lcll}
\textbf{Peggy} & \textbf{ } & \textbf{Victor} & ~ \\
\begin{aligned} &s,P ~ \\ &r \leftarrowtail \field{F_p} \\ &R = rG \end{aligned} & \stackrel{\boxed{R}}\longrightarrow & ~ \begin{aligned} &P,R\end{aligned} \\
\begin{aligned} &s,P,r,R \\ &\pi = r + s ~\big\} ~\mathsf{prove} \end{aligned} & \stackrel{\boxed{\pi}}\longrightarrow & ~ \begin{aligned} &P,R,\pi \\ &\begin{aligned}\pi G &\stackrel{?}{=} (r + s)G \\ &= R + P \end{aligned} ~\bigg\} \mathsf{verify}
\end{aligned}
\end{array}
$$

Victor is initially happy with this approach because he is able to use the homomorphic property $(r + s)G = rG + sG$ to perform verification.

Unfortunately, Victor becomes unconvinced of Peggy's proof when he realizes Peggy can cheat. He attests that Peggy doesn't really need to know $s$ to provide a proof this way. Indeed, Peggy could have just selected a random $\pi \in \field{F_p}$ and then computed $R = \pi G - P$. We say that this protocol fails to deliver the *soundness* property because Peggy can cheat.

Victor suggests that he can sample a challenge in order to assure that Peggy cannot cheat.

**Protocol 4:** Peggy incorporates a random challenge $c$ by Victor into her protocol and updates her proof to $(R, \pi = r + cs)$.

$$
\begin{array}{lcll}
\textbf{Peggy} & \textbf{ } & \textbf{Victor} & ~ \\
\begin{aligned} &s,P ~ \\ &r \leftarrowtail \field{F_p} \\ &R = rG \end{aligned} & \stackrel{\boxed{R}}\longrightarrow & ~ \begin{aligned} &P,R,\end{aligned} \\
\begin{aligned} &s,P,r,R,c \end{aligned} & \stackrel{\boxed{c}}\longleftarrow & ~ \begin{aligned} &P,R \\ &c \leftarrowtail \field{F_p}
\end{aligned} \\
\begin{aligned} &s,P,r,R,c \\ &\pi = r + cs ~\big\} ~\mathsf{prove} \end{aligned} & \stackrel{\boxed{\pi}}\longrightarrow & ~ \begin{aligned} &P,R,c,\pi \\ &\begin{aligned}\pi G &\stackrel{?}{=} (r + cs)G \\ &= R + cP \end{aligned} ~\Bigg\} \mathsf{verify}
\end{aligned}
\end{array}
$$

Victor is unable to compute $s = \frac{\pi - r}{c}$ because he doesn't know $r$. Futhermore, if Peggy didn't know $s$ and selected a random $\pi$ then she was unable to compute $R = \pi G - cP$ because she wouldn't know $c$ at the time she computed $R$. Thus, Victor is convinced by the proof and Peggy has proved knowledge of $s$ without disclosing it.

There are two main ingredients that make this protocol possible.

* **Interactivity:** We let the verifier become active in the proof with a challenge
* **Homomorphic commitments:** The prover is able to bind to a value $r$ without revealing it (i.e. a commitment) and then later the verifier can use the commitment homomorphically to verify the proof without learning $r$

This protocol is an example of a so-called *sigma protocol* because the steps of communication (commit, challenge, prove) can be imagined to trace out a sigma symbol. Some people say it looks more like a Z.

**Trust assumptions:** This protocol makes an *honest verifier* assumption. That is, the protocol is secure as long as the verifier is benign. If the verifier were malicious it could return a non-random challenge, which could be used to learn something about the secret $s$. In the next section we will convert this protocol to a non-interactive protocol and this problem will be fixed.

## Fiat–Shamir heuristic

The zero-knowledge protocol given above is interactive, but if we want to use it in non-interactive settings there is an easy way to do this called the *Fiat–Shamir heuristic*.

The Fiat–Shamir heuristic says that any public-coin interactive proof of knowledge can be converted into a non-interactive proof of knowledge.

One way to do this is through the use of a cryptographic hash function $H$.

The idea is to replace the random values selected by the verifier with values obtained by applying a cryptographic hash function to public inputs. By doing this we assure that:

* There is no way for the prover to cheat, since the prover gives full control to the cryptographic hash function
* The verifier no longer needs to be involved in the protocol and, thus, the protocol becomes non-interactive

**Transcript:** The Fiat–Shamir heuristic works by fixing a *transcript* to the zero-knowledge protocol. The transcript inputs values from the protocol and hashes them to obtain outputs used in subsequent steps of the protocol.

We can make the zero-knowledge protocol from previous section non-interactive by making a transcript $\mathcal{T}$ accessible to both the prover and the verifier and then using it to generate any random values or challenges.

Here's the updated non-interactive protocol.

**Non-interactive ZK protocol:**

$$
\begin{array}{lcll}
\textbf{Peggy} & \textbf{ } & \textbf{Victor} & ~ \\
\begin{aligned}
&s,P \\ &\mathcal{T}.\mathtt{update(P)} \\ &r \leftarrow \mathcal{T}.\mathtt{digest}() \\
&R = rG \\
&\mathcal{T}.\mathtt{update}(R) \end{aligned} &\stackrel{\boxed{R}}\longrightarrow & ~ \begin{aligned} &P,R \end{aligned} \\
\begin{aligned} &s,P,r,R,c \end{aligned} & \stackrel{\boxed{c}}\longleftarrow & ~ \begin{aligned} &P,R \\ &c \leftarrow \mathcal{T}.\mathtt{digest}()
\end{aligned} \\
\begin{aligned} &s,P,r,R,c \\ &\pi = r + cs ~\big\} ~\mathsf{prove} \end{aligned} & \stackrel{\boxed{\pi}}\longrightarrow & ~ \begin{aligned} &P,R,c,\pi \\ &\begin{aligned}\pi G &\stackrel{?}{=} (r + cs)G \\ &= R + cP \end{aligned} ~\Bigg\} \mathsf{verify}
\end{aligned}
\end{array}
$$

**Bad:**
$$
\begin{array}{lcll}
\textbf{Peggy} & \textbf{ } & \textbf{Victor} & ~ \\
\begin{aligned}
&s,P \\ &\mathcal{T}.\mathtt{update(P)} \\ &r \leftarrow \mathcal{T}.\mathtt{digest}() \\
&R = rG \\
&c \leftarrow \mathcal{T}.\mathtt{digest}() \end{aligned} & & ~ \\
\begin{aligned} &\pi = r + cs ~\big\} ~\mathsf{prove} \end{aligned} & \stackrel{\boxed{\pi}}\longrightarrow & ~ \begin{aligned} &P \\ &\mathcal{T}.\mathtt{update(P)} \\ &r \leftarrow \mathcal{T}.\mathtt{digest}() \\
&R = rG \\
&c \leftarrow \mathcal{T}.\mathtt{digest}() \\ &\begin{aligned} \pi G &\stackrel{?}{=} (r + cs)G \\ &= R + cP
\end{aligned} ~\Bigg\} \mathsf{verify} \end{aligned}
\end{array}
$$

**OK:**
$$
\begin{array}{lcll}
\textbf{Peggy} & \textbf{ } & \textbf{Victor} & ~ \\
\begin{aligned}
&s,P \\ &\mathcal{T}.\mathtt{update(P)} \\ &r \leftarrowtail \field{F_p} \\
&R = rG \\
&\mathcal{T}.\mathtt{update(R)} \\
&c \leftarrow \mathcal{T}.\mathtt{digest}() \end{aligned} & & ~ \\
\begin{aligned} &\pi = r + cs ~\big\} ~\mathsf{prove} \end{aligned} & \stackrel{\boxed{R, \pi}}\longrightarrow & ~ \begin{aligned} &P \\ &\mathcal{T}.\mathtt{update(P)} \\ &\mathcal{T}.\mathtt{update(R)} \\
&c \leftarrow \mathcal{T}.\mathtt{digest}() \\ &\begin{aligned} \pi G &\stackrel{?}{=} (r + cs)G \\ &= R + cP
\end{aligned} ~\Bigg\} \mathsf{verify} \end{aligned}
\end{array}
$$

First we initialize a new transcipt $\mathcal{T}$ and update it by hashing the public input $P$ into it. Next, we obtain the prover's random value $r$ by taking $\mathcal{T}$'s digest and converting it to a scalar field element. After that, we update the transcript again, this time by hashing $R$. Finally, we generate the verifiers challenge $c$ by taking the transcript's digest once more.

If the transcript's cryptographic hash function is secure, then there is no way for any party to tamper with the protocol. As mentioned earlier, this updated non-interactive protocol has the additional benefit that it does not make the honest verifier assumption.

## Vector commitments

The next primitive we require is the ability to commit not to a single value, but a vector of values $\vec{v} = (v_0, \ldots, v_{n-1}) \in \field{F_p}^n$. This could be done with $n$ independent commitments

\begin{aligned}
V_0 &= v_0G, \\
V_1 &= v_1G, \\
&~~ \vdots \\
V_{n-1} &= v_{n-1}G,
\end{aligned}

where $V_i = \mathsf{commit}(v_i)$, but this requires $n$ points.

A more efficient approach is to create a linear combination of these commitments with $n$ independent base points $G_0, \ldots, G_{n-1} \stackrel{}\leftarrow E(\field{F_p})$.

$$
V = \mathsf{commit}(\vec{v}) = \sum_{i=0}^{n-1} v_iG_i
$$

where for $G_0, \ldots, G_{n-1}$ the discrete logarithms are unknown to everyone.

This allows us to commit to a vector of length $n$ with only a single curve point.

There is actually a lot going on in the above definition, so let's unpack it.

**Unknown discrete logarithms:** We can obtain points whose discrete logarithms are unknown by a *hash to curve* algorithm.

Suppose we have $\field{F}_p$ a prime order field, where $p$ is large (e.g. $2^{256}$), and a publically agreed generator point $G$ over elliptic curve $E(\field{F_p})$.

The hash to curve algorithm finds a point $H$ whose discrete logarithm is unknown as follows.

> Perform rejection sampling by cryptographically hashing $G$ (or, respectively, its hash output), using the output as the $x$-coordinate of a candidate point on $E$ and checking whether it's valid. The first valid curve point obtained is $H$ and by the hardness assumption of the ECDLP, no one knows it.

Since approximately half of the hash outputs will be valid curve points on $E$, sampling will terminate very quickly. Indeed, this process can be used to sample many public curve points $G_1, \ldots, G_n$ for which the discrete logarithms are unknown.

**Generators and base points:** The terms generator and base (sometimes called a base point) are synonymous.

A generator is an element of the group that is used to generate the group. In the case of ECC, the generator point is added to itself $k$ times to generate the $k^{\mathsf{th}}$ element. We call the number of elements in a group the *order* of the group.

According to *Lagrange's theorem in group theory*, for any finite group $\mathcal{G}$, the order of every subgroup divides the order of $\mathcal{G}$. This means that with the exception of the identity element (whose order is 1) all other points can be generators of some subgroup of some size.

The *cofactor* of a generator (or base point) is the order of $\mathcal{G}$ divided by the order of the subgroup generated by the generator.

For security in cryptographic applications generators must have a large order, roughly equal to $p$.

**Independence:** In the above definition of a vector commitment the $n$ base points must be independent. This means that there should be no known relationship between them, for example, $G_1 \ne \alpha G_0$ and so on. Randomly selecting them from a large group is sound approach to obtaining independent base points.

This approach is based on the discrete logarithm relation assumption, which states that an adversary cannot find a non-trivial relation between randomly selected group elements. More formally, given adversary $\mathcal{A}$ and negligible probability $\lambda$

$$
Pr \Bigg[ \begin{aligned} &G_0, \ldots, G_{n-1} \stackrel{}\leftarrow E(\field{F_p}); \\ &A = (a_0, \ldots, a_{n-1}) \in \field{F_p} \leftarrow \mathcal{A}(g_1, \ldots, g_n) \end{aligned} : \forall a_i \in A, a_i \ne 0 \wedge \sum_{i=0}^{n-1}a_iG_i = 1 \Bigg] \le \lambda
$$

where $\sum_{i=0}^{n-1} a_iG_i$ is a non-trivial discrete logarithm relation between $G_1, \ldots, G_n$.

## Opening proofs for vector commitments

In the previous section we learned an efficient and simple way to commit to a vector of length $n$ that requires only a single curve point. What is not clear, however, is how to create an efficient opening proof for a vector commitment.

This section will explain an efficient interactive protocol for a specific type of vector commitment opening proof called Bulletproofs. As usual, it will be described as a protocol between the prover and verifier.

To start, we need some public parameters
* $\field{F}_p$ a prime order field, where $p$ is large (e.g. $2^{256}$)
* $\vec{G} = (G_1, \ldots, G_n) \in \mathbb{G}^n$ independent base points over elliptic curve $E(\field{F_p})$ for which the discrete logarithms are unknown

Recall our definition of a non-hiding vector commitment and make the vector of base points a parameter:

\begin{aligned}
\mathsf{commit}(\vec{v}, \vec{G}) &= \sum_{i=1}^n v_iG_i \\
&= v_1G_1 + v_1x + \cdots + v_nG_n \\
&= \ip{v}{G}
\end{aligned}

The naïve solution for an opening proof is to reveal $\vec{v}$ to the verifier.

**Protocol 1:** Naïve solution
$$
\begin{array}{lcll}
\textbf{Prover} & \textbf{ } & \textbf{Verifier} & ~ \\
\begin{aligned} &\vec{v}, \vec{G} \\ &V = \ip{v}{G} ~\big\} ~\mathsf{commit} \end{aligned} & \stackrel{~\boxed{V}}\longrightarrow &~ \begin{aligned} V, \vec{G} \end{aligned} &~ \\
\begin{aligned} &\vdots \end{aligned} & \vdots &~ \vdots &~ \\
\begin{aligned} &\vec{v},\vec{G},V \\ &\vec{v} ~\big\} ~\mathsf{open} \end{aligned} & \stackrel{~\boxed{\vec{v}}}\longrightarrow &~ \begin{aligned} &V,\vec{G},\vec{v}\\ &\ip{v}{G} \stackrel{?}{=} V \end{aligned} &~ \\
\end{array}
$$

However, the proof size is equal to the number of elements in the vector, which could be huge.

Fortunately, there is a more compact way to do this!

The idea is, with the help of the verifier, to employ a divide a conquer algorithm to recursively halve the size of the problem, including the proof $\vec{\pi}$.

**Base case:** In order to understand this algorithm it is helpful to start with the base case. That is, the case where $n=2$ and we have a vector of two elements. This case is also useful to consider from a soundness perspective.

*Step 1:* Let's say the verifier commits to $\vec{v} = (v_1, v_2)$, then

$$
\begin{aligned}
V &= v_1G_1 + v_2G_2.
\end{aligned}
$$

For the naïve solution the prover would have to reveal both $v_1$ and $v_2$ for the opening, but our aim is instead to recusively split this problem in half. We do not expect any gains yet, but when used recursively for large $n$ we expect to see huge gains.

Abstractly, splitting the problem in half also means halving the number of base points, so let's start with a new base point $G'$ somehow derived from $G_1$ and $G_2$ (more on this later).

Simply adding the values together under a commitment would not work because it would not be a vector commitment. Concretely, computing commitment

$$
C' = (v_0 + v_1)G'
$$

is only a commitment to the sum $v_0 + v_1$, which could be $v_0' = (v_0 + \alpha)$ and $v_1' = (v_1 - \alpha)$ for any $\alpha \in \field{F_p}$, so as a vector commitment it would fail to provide the binding property.

Instead let's get the verifier involved by allowing it to send a challenge $c$.

*Step 2:* Verifier sends a challenge $c$ randomly selected from $\field{F_p}$.

*Step 3:* Now the prover uses the challenge to compute the subproblem of half the size. Specifically, the prover computes

\begin{aligned}
\vec{G'} &= (c^{-1}G_1 + cG_2) \\
&= (G'_1) \\
\vec{v'} &= (v_1c + v_2c^{-1}) \\
&= (v'_1)
\end{aligned}

where $\vec{G'}$ and $\vec{v}$ are the subproblem of half size, i.e., instead of vectors of length 2 they are now vectors of length 1. Note that the verifier can also compute $\vec{G'}$ without any help from the prover, whilst only the prover can compute $\vec{v}$.

In addition to having a subproblem of half size, the vector $\vec{v'}$ is simultanously the proof that is sent to the verifier.

To be useful, the proof $\vec{v}$ must
* Bind to the commitment $V$ so that the prover cannot cheat
* Recusively link to the orignal problem of proving the opening of $\vec{v}$
* Allow the verifier to check it

Let's see if that's the case.

*Step 4:* The verifier checks the proof.

\begin{aligned}
\ip{v}{G'} &\stackrel{?}= (v'_1)(G'_1) \\
&= (v_1c + v_2c^{-1})(c^{-1}G_1 + cG_2) \\
&= v_1G_1 + c^2v_1G_2 + c^{-2}v_2G_1 + v_2G_2 \\
&= V + c^2v_1G_2 + c^{-2}v_2G_1
\end{aligned}

Great -- since the prover computes $V$ before known $c$ cheating is not possible. The subproblem's proof also contains the original commitment $V$ so the recursive requirement is satisfied. Unfortunately, the verifier doesn't have all of the information it needs to check the proof. Specifically, although it knows $c$ it is missing the last two terms.

Good news! These two additional curve points can be sent by the prover along with the original commitment $V$. If $n$ was very large the overhead of these two additional points is negligible.

Let's call these values $L$ and $R$.

\begin{aligned}
L &= v_1G_2 \\
R &= v_2G_1
\end{aligned}

The verification check is now

$$
\ip{v'}{G'} \stackrel{?}= V + c^2L + c^{-2}R
$$

But since $\vec{G'}$ and $\vec{v}$ are both single elements, i.e. $G' = G'_1$ and $v' = v'_1$ from above, we can rewrite to explicitly show this important outcome.

$$
v'G' \stackrel{?}= V + c^2L + c^{-2}R
$$

This fact is very important, as we will see later, because it means the base case check involves a single field element and base point and, thus, only computing a single exponentiation for $v'G'$.

For clarity, let us review this as a special base case protocol.

**Protocol 2:** The protocol for halving the problem size, shown for the base case when $n=2$.
$$
\begin{array}{lcll}
\textbf{Prover} & \textbf{ } & \textbf{Verifier} & ~ \\
\begin{aligned} &\vec{v} = (v_1, v_2), \vec{G} = (G_1, G_2) \\ &\begin{aligned} V &= \ip{v}{G} \\ L &= v_1G_2 \\ R &= v_2G_1 \end{aligned} ~\Bigg\} ~\mathsf{commit} \end{aligned} & \stackrel{~\boxed{V, L, R}}\longrightarrow &~ \begin{aligned} \vec{G},V,L,R \end{aligned} &~ \\
\begin{aligned} &\vec{v},\vec{G},V,L,R,c \end{aligned} & \stackrel{~\boxed{c}}\longleftarrow &~ \begin{aligned} &\vec{G},V,L,R \\&c \leftarrow \field{F_p} ~\big\} ~\mathsf{challenge} \end{aligned} &~ \\
\begin{aligned} &\vec{v},\vec{G},V,L,R,c \\ &\begin{aligned} v' &= v_1c + v_2c^{-1} \end{aligned} ~\big\} ~\mathsf{open} \end{aligned} & \stackrel{~\boxed{v'}}\longrightarrow &~ \begin{aligned} &\vec{G},V,L,R,c,v' \\
&G' = c^{-1}G_1 + cG_2 \\ &v'G' \stackrel{?}{=} V + c^2L + c^{-2}R ~\big\} ~\mathsf{verify} \end{aligned} &~ \\
\end{array}
$$

**Analysis:** For the base case, the opening proof $v'$ is a single field elements instead of 2 as in the naïve solution. So we have acheived our goal of halving the size of the opening proof, at least in the base case. However, overall the protocol now requires 3 commitments instead of 1.

You may be wondering if it is worth it.

Definitely! For large $n$ this divide on conquer approach will reduced the size of the proof to $n/2$ at the expense of only 2 curve points for $L$ and $R$. So let's see how it works for the general case.

**General case:** Now we are ready to describe the general case for vectors of length $n$. For simplicity we can assume $n$ is a power of two.

We define some notation. For vector $\vec{v} = (v_1, \ldots, v_n) \in \field{F_p}^n$ and $c \in \field{F_p}$ let

* $c \cdot \vec{v} = (cv_1, \ldots cv_n)$
* $\left{v} = (v_1, \ldots, v_{n/2})$
* $\right{v} = (v_{n/2 + 1}, \ldots, v_n)$
* $\ewsum{v}{w} = (v_1 + w_1, \ldots, v_n + w_n)$
* $\fold{v}{c} = \pewsum{c \cdot \left{v}}{c^{-1} \cdot \right{v}} = (cv_1 + c^{-1}v_{n/2+1}, \ldots, cv_{n/2} + c^{-1}v_n)$

Given the inputs
* Vector $\vec{v}_0 = (v_1, \ldots, v_n) \in \field{F_p}^n$
* Vector of base points $\vec{G}_0 = (G_1, \ldots, G_n) \in \mathbb{G}^n$
* Commitment $V_0$ to vector $\vec{v}_0$, computed $V_0 = \mathsf{commit}(\vec{v_0}, \vec{G}_0) = \ip{v_0}{G_0} = (v_1G_1 + \ldots v_nG_n)$

The opening proof is generated with the following algorithm.

*Initialization:*

* Prover sends commitment $V_0$ to the verifier
* Prover runs $\mathtt{Prove}(\vec{v}_0, \vec{G}_0, V_0)$ and verifier runs $\mathtt{Verify}(\vec{G}_0, V_0)$, recursive functions

\begin{aligned}
\mathtt{Prove}(\vec{v}_i \in \field{F_p}^n, \vec{G}_i \in \mathbb{G}^n, V_i \in \field{F_p}) ~&~&~&~&~&
\mathtt{Verify}(\vec{G}_i \in \mathbb{G}^n, V_i \in \field{F_p}) ~&~&~&~&~&~&
\end{aligned}

> Prove and verify recursive algorithms.
* *Step 1:* $\mathtt{if} ~n == 1 ~\mathtt{then}$ (base case)
* Prover and verifier run the following final base case protocol
* In this case $i=\log_2(n)$, so we have $\vec{G}_{log_2(n)}$ and $\vec{v}_{log_2(n)}$ that are vectors or length 1
$$
\begin{array}{lcll}
\textbf{Prover} & \textbf{ } & \textbf{Verifier} & ~ \\
\begin{aligned} &\vec{v}_{log_2(n)}, \vec{G}_{log_2(n)},V \\ &\vec{v}_{log_2(n)} = (v_1) \\ &v_1 ~\big\} ~\mathsf{prove} \end{aligned} & \stackrel{~\boxed{v_1}}\longrightarrow &~ \begin{aligned} &\vec{G}_{log_2(n)},V_{log_2(n)},v_1 \\
&\vec{G}_{log_2(n)} = (G_1) \\
&v_1 G_1 \stackrel{?}{=} V_{log_2(n)} ~\} ~\mathsf{verify} \end{aligned} &~ \\
\mathit{finito} & \textbf{ } & \mathit{finito} & ~ \\
\end{array}
$$
* The verifier returns the verification result $\mathtt{true/false}$ and both the prover and verifier terminate the algorithm.

Note that $v_{log_2(n)}, G_{log_2(n)}$ and $V_{log_2(n)}$ are the final values computed from all $log_2(n)$ rounds.

* *Step 2:* $\mathtt{else}$ (inductive case)
* Prover and verifier perform round $i$ of the following recursive protocol
* Note that they compute
* $L_i$ and $R_i$ (prover only)
* Halved vectors $\vec{v}_{i+1}$ (prover only)
* Halved vector $\vec{G}_{i+1}$
* Next commitment $V_{i+1}$
$$
\begin{array}{lcll}
\textbf{Prover} & \textbf{ } & \textbf{Verifier} & ~ \\
\begin{aligned} &\vec{v}_i,\vec{G}_i,V_i \\ &\begin{aligned} L_i &= \pip{\left{v_i}}{\right{G_i}} \\ R_i &= \pip{\right{v_i}}{\left{G_i}} \end{aligned} ~\Bigg\} ~\mathsf{commit} \end{aligned} & \stackrel{~\boxed{L_i, R_i}}\longrightarrow &~ \begin{aligned} \vec{G}_i,V_i,L_i,R_i \end{aligned} &~ \\
\begin{aligned} &\vec{v},\vec{G}_i,V_i,L_i,R_i,c_i \end{aligned} & \stackrel{~\boxed{c_i}}\longleftarrow &~ \begin{aligned} &\vec{G}_i,V_i,L_i,R_i \\&c_i \leftarrow \field{F_p} ~\big\} ~\mathsf{challenge} \end{aligned} &~ \\
\begin{aligned} &\vec{v},\vec{G}_i,V_i,L_i,R_i,c_i \\ &\begin{aligned} \vec{G}_{i+1} &= \fold{G_i}{c_i^{-1}} \\ \vec{v}_{i+1} &= \fold{v_i}{c_i} \\ V_{i+1} &= V_i + c_i^2L_i + c_i^{-2}R_i \end{aligned} ~\Bigg\} ~\mathsf{halve} \\
&\mathtt{Prove}(\vec{v}_{i+1}, \vec{G}_{i+1}, V_{i+1})
&\end{aligned} & ~ &~ \begin{aligned} &\vec{G}_i,V_i,L_i,R_i,c_i \\
&\begin{aligned} \vec{G}_{i+1} &= \fold{G}{c_i^{-1}} \\ V_{i+1} &= V_i + c_i^2L_i + c_i^{-2}R_i \end{aligned} ~\Bigg\} ~\mathsf{halve} \\
&\mathtt{Verify}(\vec{G}_{i+1}, V_{i+1})\end{aligned} &~ \\
\end{array}
$$

**Analysis:** You may notice something that seems odd. During the protocol for the inductive case, the prover does not transmit the proof $\vec{v}_{i+1}$ to the prover. The only place were a proof is transmitted is in the base case where a single field element is sent to the verifier.

This is great for efficiency, but how can it be?

Amazingly, this is possible because proof for round $i$ is equal to the (now half sized) vector for round $i+1$. Therefore, instead of sending the proof $\vec{v}_{i+1}$ to the verifier and then the verifier checking it against $V_i$, the prover can instead tell the verifier that the commitment to $\vec{v}_{i+1}$ is $V_{i+1}$ and use the same protocol recursively to create and opening proof for $\vec{v}_{i+1}$. More formally, we have

$$
\mathtt{Prove}(\vec{v}_i, \vec{G}_i, V_i) = \mathtt{Prove}(\vec{v}_{i+1}, \vec{G}_{i+1}, V_{i+1})
$$

where $\vec{v}_{i+1}, \vec{G}_{i+1}$ and $V_{i+1}$ are computed as specified in the above protocol.

But wait! Couldn't the prover lie about the commitment to $V_{i + 1}$ or vector $\vec{v}_i$?

Fortunately, the verifier is in control!

Thanks to the verifier's random challenge $c_i$, the next vector $\vec{v}_{i+1}$ (which is the opening proof for $\vec{v_i}$) cannot be faked because (as we will see below) in order for to be valid against the commitment it must incorporate the challenge $c_i$.

Remarkably, the verifier does not even require the prover to send $V_{i+1}$ because she can derive it from $V_i, c, L_i$ and $R_i$. To see why this is, we need the verification check for the general length $n$ protocol. Recall our base case protocol verification check from earlier

$$
v'G' \stackrel{?}{=} V + c^2L + c^{-2}R
$$

where $v'G' = \ip{v'}{G'}$. Working backwards and integrating our new notations we can see that

\begin{aligned}
\ip{v'}{G'} &\stackrel{?}{=} V + c^2L + c^{-2}R \\
&= V + c^2v_1G_2 + v^{-2}v_2G_1 \\
&= V + c^2\pip{\left{v}}{\right{G}} + c^{-2}\pip{\right{v}}{\left{G}}
\end{aligned}

For the length $n$ vector case (where $n$ is a power of two), the check is

\begin{aligned}
\pip{\vec{v}_{i+1}}{\vec{G}_{i+1}} \stackrel{?}{=} V_i + c_i^2\pip{\left{v_i}}{\right{G_i}} + c_i^{-2}\pip{\right{v_i}}{\left{G_i}}
\end{aligned}

Let's work it out from the left side to see this is indeed true

\begin{aligned}
\pip{\vec{v}_{i+1}}{\vec{G}_{i+1}} &= \pip{\fold{v_i}{c_i}}{\fold{G_i}{c_i^{-1}}} \\
&= \pip{\pewsum{c_i \cdot \left{v_i}}{c_i^{-1} \cdot \right{v_i}}}{\pewsum{c_i^{-1} \cdot \left{G_i}}{c_i \cdot \right{G_i}}} \\
&= \pip{(c_iv_1 + c_i^{-1}v_{n/2 + 1}), \ldots, (c_iv_{n/2} + c_i^{-1}v_{n})}{(c_i^{-1}G_1 + c_iG_{n/2 + 1}), \ldots, (c_i^{-1}G_{n/2} + c_iG_{n})} \\
&= (c_iv_1 + c_i^{-1}v_{n/2 + 1})(c_i^{-1}G_1 + c_iG_{n/2 + 1}) + \ldots + (c_iv_{n/2} + c_i^{-1}v_{n})(c_i^{-1}G_{n/2} + c_iG_{n}) \\
&= v_1G_1 + c_i^2v_1G_{n/2 + 1} + v_2G_2 + c_i^2v_2G_{n/2 + 2} + \ldots + v_{n/2}G_{n/2} + c^2v_{n/2}G_n \\
&+ c_i^{-2}v_{n/2 + 1}G_1 + v_{n/2 + 1}G_{n/2 + 1} + c_i^{-2}v_{n/2 + 2}G_2 + v_{n/2 + 2}G_{n/2 + 2} + \ldots + c_i^{-2}v_nG_{n/2} + v_nG_n \\
&= v_1G_1 + \ldots + v_nG_n \\
&+ c_i^2(v_1G_{n/2 + 1} + v_2G_{n/2 + 2} + \ldots + v_{n/2}G_n) \\
&+ c_i^{-2}(v_{n/2 + 1}G_1 + v_{n/2 + 2}G_2 + \ldots + v_nG_{n/2}) \\
&= V_i + c_i^2\pip{\left{v_i}}{\right{G_i}} + c_i^{-2}\pip{\right{v_i}}{\left{G_i}}
\end{aligned}

Therefore, with $L_i = \pip{\left{v_i}}{\right{G_i}}$ and $R_i = \pip{\right{v_i}}{\left{G_i}}$ in hand before the challenge $c$ was sent the verifier can safely compute $\pip{\vec{v}_{i+1}}{\vec{G}_{i+1}}$ without knowing $\vec{v}_{i+1}$.

$$
\pip{\vec{v}_{i+1}}{\vec{G}_{i+1}} = V_i + c_i^2L_i + c_i^{-2}R_i
$$

But, our original problem was for the verifier compute $V_{i + 1}$ without knowing $\vec{v}_{i+1}$. How's that going to happen?

Since $\vec{v}_{i+1}$ and $\vec{G}_{i+1}$ are the next vectors for the subproblem of half size, the commitment to vector $\vec{v}_{i+1}$ is therefore

\begin{aligned}
V_{i+1} &= \mathsf{commit}(\vec{v_{i+1}}, \vec{G}_{i+1}) \\
&= \pip{\vec{v}_{i+1}}{\vec{G}_{i+1}} \\
&= V_i + c_i^2L_i + c_i^{-2}R_i
\end{aligned}

Therefore the verifier can verify round $i$ by computing $V_{i+1}$ from $V_i, c, L_i, R_i$ and coordinating with the prover to recursively verify round $i+1$ on the halved (i.e. folded) vectors $\vec{v}_{i+1}$ and $\vec{G}_{i+1}$. This process continues recursively until the base case when the prover finally sends the proof as a single element to the verifier, who verifies it with a single exponentiation.

**In a bullet shell:** The essence of bulletproofs is perhaps that the proof for round $i$ is equivalent to the subproblem for round $i+1$. This can be distilled into the following equality.

\begin{aligned}
V_{i+1} &= \pip{\mathsf{proof}(\vec{v}_i, c_i)}{\vec{G}_{i+1}} = V_i +c_i^2L_i + c_i^{-2}R_i \\
\mathsf{commit}(\vec{v}_{i+1}, \vec{G}_{i+1}) &= \mathsf{commit}(\mathsf{proof}(\vec{v}_i, c_i),\vec{G}_{i+1}) = \mathsf{commit}(\vec{v}_i, \vec{G}_i) + c_i^2L_i + c_i^{-2}R_i
\end{aligned}

We can expand this further to express the entire idea, which is an interesting relationship between the inner product and folds.

> $$
\underbrace{\pip{\vec{v}_{i+1}}{\vec{G}_{i+1}}}_{\mathsf{commit}~i + 1} = \underbrace{\pip{c_i \cdot \left{v_i} + c_i^{-1} \cdot \right{v_i}}{\vec{G}_{i+1}}}_{\mathsf{commit ~ proof} ~i} = \underbrace{\ip{v_i}{G_i}}_{\mathsf{commit} ~i} + \underbrace{c_i^2 \ip{\left{v_i}}{\right{G_i}} + c_i^{-2}\ip{\right{v_i}}{\left{G_i}}}_{\mathsf{unfortunate}}
$$

It looks beautiful! Perhaps it would be catchy printed on a T-shirt. The last two terms are "unfortunate" because if they didn't exist (or if only one didn't exist) then bulletproofs would be constant size (or half the size, respectively) .

**Complexity:** If we assume commitment points and field elements to be the same size (which is probably not a bad assumption if we used compressed curve points) and that challenges are ephemeral, the recurrence relation for the communication cost is

\begin{aligned}
S(1) &= 1 \\
S(n) &= S(n/2) + 2 \\
&= 2\log_2(n) + 1,
\end{aligned}

where $S(1)$ corresponds to the final protocol where the prover only sends a single field element. Thus, the total communication cost for an opening proof for a vector of length $n$ is $2\log_2(n) + 1$ elements.

**Honest verifier model:** The presented protocol uses the honest verifier model. If the verifier selected a non-random challenge, for example, $c=1$, then information may leak.

For example, by using challenge $c=1$ in the base case protocol the verifier would learn $w = v_1 + v_2$ and then could compute $v_1$ and $v_2$. Specifically, verifier would know that

\begin{aligned}
V &= v_1G_1 + v_2G_2 \\
L &= v_1G_2 \\
R &= v_2G_1 \\
w &= v_1 + v_2 \\
W_1 &= wG_1 \\
W_2 &= wG_2.
\end{aligned}

Therefore,

\begin{aligned}
v_2 &= \frac{V + R - W_1}{G_2} ~ &\hbox{and} & ~ & ~ & v_1 = \frac{V + L - W_2}{G_1}.
\end{aligned}

If the verifier provided 1 for all challenges then it could work backwards to discover the entire initial vector of $n$ elements.

One way to fix this is to switch to a non-interactive protocol using the Fiat–Shamir heuristic.

**Non-iteractivity:** If the protocol was made non-interactive with the Fiat–Shamir heuristic, then the proof would be $\pi = (v_{\log_2(n)}, [(L_i, R_i) ~|~ 0 \le i < \log_2(n)])$.

Starting with an initial vector $\vec{v}$ of length $n = 2^k$, then the final check in the base case is

$$
v_{\log_2(n)}G_{\log_2(n)} \stackrel{?}= V_{\log_2(n)}
$$

The values $G_{\log_2(n)}$ and $V_{\log_2(n)}$ must be computed by the verifier using the challenges obtained from the Fiat–Shamir heuristic. The value $V_{\log_2(n)}$ can be derived from the recurrence relation

\begin{aligned}
V_{k} &= V_{k-1} + c_{k-1}^2L_{k-1} + c_{k-1}^{-2}R_{k-1} \\
&= V_{k-2} + c_{k-2}^2L_i + c_{k-2}^{-2}R_i + c_{k-1}^2L_{k-1} + c_{k-1}^{-2}R_{k-1} \\
&= V_0 + \sum_{i=0}^{k-1} c_i^2L_i + c_i^{-2}R_i
\end{aligned}

Thus, the non-interactive check is now

$$
v_{\log_2(n)}G_{\log_2(n)} \stackrel{?}= V_0 + \sum_{i=0}^{\log_2(n)-1} c_i^2L_i + c_i^{-2}R_i
$$

The verifier can compute $G_{\log_2(n)}$ with the recurrence

\begin{aligned}
\vec{G}_{k} &= \mathsf{fold}(\vec{G}, c_i^{-1}) \\
&= \ewsum{c_i^{-1} \left{G_{k-1}}}{c_i\right{G_{k-1}}} \\
&= \mathtt{TODO}
\end{aligned}

**Multi-exponentiation:** TODO!!!

## Hiding vector commitments

## Polynomial commitment scheme

We are now ready to explain a polynomial commitment scheme using the inner product argument.

Our polynomial commitment scheme for field $\field{F_p}$ is a method for committing to a polynomial $p(X)$ defined over $\field{F_p}$ so that you can provide an opening proof $\pi$ that $y = p(x)$ for any $x\in \field{F_p}$ and that $p$ is the polynomial committed to.

Since we are going to use the inner product argument for our proof, so we must reframe our problem in terms of vectors.

As discussed earlier, recall that

* The polynomial $p(X)$ of degree $n$ can represented as a vector of coefficients $\vec{p} = (c_0, \ldots, c_n)$.
* The value $x$ can be represented as a vector $x = (x^0, \ldots, x^n)$, corresponding to its expansion when substituted for $X$ in $p(X)$
* The evaluation of $p(x)$ equals the inner product of $\vec{p}$ and $\vec{x}$. That is $p(x) = c_0 + c_1x + \cdots + c_nx^n = \ip{p}{x}$

Thus, our polynomial commitment scheme will: commit to $\vec{p}$, publicly select a random $x$, prove that $y = \ip{p}{x}$ and then verify the proof against the commitment.

It consists of four algorithms: $\mathsf{setup}(), \mathsf{commit}(p(X)), \mathsf{open}(c)$ and $\mathsf{verify}(c, x)$.

Firstly, we define $\mathsf{setup}()$, which initializes some public parameters

* $\field{F}_p$ a prime order field, where $p$ is large (e.g. $2^{256}$)
* $G_0, \ldots, G_n$ independent base points over elliptic curve $E(\field{F_p})$ for which the discrete logarithms are unknown
* $H$ another independent base point (for hiding) for which the discrete logarithm is also unknown

The remaining algorithms will be described under the context of a zero-knowledge protocol.

**Protocol:** As we have done previously, we present this as an interactive protocol that can be made non-interactive using the Fiat–Shamir heuristic. Similar to the zero-knowledge protocol described earlier (i.e. the Schnorr Identity Protocol) our protocol follows the $\Sigma$ protocol pattern: *commit*, *challenge*, *prove*.

Here, the prover (Peggy) has a secret polynomial $p(X)$ that only she knows.

The verifier (Victor) selects a random element $x \in \field{F_p}$ and tells it to Peggy.

Peggy wants to prove to Victor that she knows $y = p(x)$ without revealing $p(X)$.

The easiest algorithm to explain is the commit algorithm.

$$
\mathsf{commit}(\vec{p}) = \sum_{i=0}^n c_iG_i = \ip{p}{G}
$$

**Step 1:** Peggy commits to $\vec{p}$ using a vector commitment.

$$
\begin{array}{lcll}
\textbf{Peggy} & \textbf{ } & \textbf{Victor} & ~ \\
\begin{aligned} &\vec{p} \\ &P = \ip{p}{G} ~\big\} ~\mathsf{commit} \end{aligned} & \stackrel{~\boxed{P}}\longrightarrow &~ \begin{aligned} P\end{aligned} &~ \\
\end{array}
$$

Now Victor must provide the challenge.

**Step 2:** Victor provides a random challenge $x \in \field{F_p}$.

$$
\begin{array}{lcll}
\textbf{Peggy} & \textbf{ } & \textbf{Victor} & ~ \\
\begin{aligned} &\vec{p},P,x \end{aligned} & \stackrel{~\boxed{x}}\longleftarrow &~ \begin{aligned} &P \\ &x \leftarrow \field{F_p} ~\big\} ~\mathsf{challenge} \end{aligned} &~ \\
\end{array}
$$

Next Peggy must provide an opening proof $\pi$ that $\ip{p}{x} = y$ and that this corresponds to the polynomial commited to by $P$.

To reason about this, let's review what Victor knows. He knows $P$ the commitment to $p(X)$ and he knows $\vec{x}$ the challenge.

The main idea behind the inner product argument is a divide an conquer algorithm to halve the size of the problem.