Inner-Product Arguments: A Step-by-Step Algebraic Walkthrough

Suppose a prover holds two vectors and claims that their inner product is a particular value. How can commitments and a verifier's challenge connect that claim to an algebraic check?

The construction below starts with two vector-valued linear polynomials. Their inner product gives a scalar quadratic polynomial. By committing to the coefficients first, the prover can later provide evaluations at a challenge chosen by the verifier. The verifier checks that these evaluations match the commitments and satisfy the claimed inner-product relation.

We will work through the polynomial expansion, the commitments, the challenge and response, and all four verification equations.

This post derives the uncompressed random-evaluation check and establishes only its honest-prover completeness. It does not prove soundness, knowledge extraction, or zero knowledge. A logarithmic inner-product argument that replaces transmission of the two evaluated vectors, such as the construction in Bulletproofs, is a separate construction outside this walkthrough.

1. Set up the notation

Let the vector entries and all other scalars belong to a finite field $\mathbb{F}_q$ . Let $\mathbb{G}$ be an additive group of large prime order $q$ .

We use the following public group elements:

$\mathbf{G} = (G_1, \ldots, G_n)$ for vector commitments.
$G$ for scalar commitments.
$H$ for the blinding term in both kinds of commitment.

Here, every commitment generator is assumed to be a nonidentity group element, and the prover is assumed unable to efficiently find any nontrivial linear relation among $G_1, \ldots, G_n, G,$ and $H$ . This is the computational-binding assumption that prevents the prover from changing a commitment's opening.

For two scalar vectors, angle brackets denote the usual inner product:

\langle \mathbf{a}, \mathbf{b} \rangle = \sum_{i=1}^{n} a_i b_i \in \mathbb{F}_q.

When the second argument is a vector of group elements, the same notation denotes a linear combination in the group:

\langle \mathbf{a}, \mathbf{G} \rangle = \sum_{i=1}^{n} a_i G_i \in \mathbb{G}.

This distinction matters: an inner product of two scalar vectors produces a scalar, while a vector commitment produces a group element.

We write $X$ for the formal polynomial variable and $u$ for the verifier's eventual challenge.

2. Turn the inner product into a polynomial

Take four vectors $\mathbf{f}_0, \mathbf{f}_1, \mathbf{g}_0, \mathbf{g}_1 \in \mathbb{F}_q^n$ and define

\begin{aligned} \mathbf{f}(X) &= \mathbf{f}_1 X + \mathbf{f}_0, \\ \mathbf{g}(X) &= \mathbf{g}_1 X + \mathbf{g}_0. \end{aligned}

We also use the names

\boldsymbol{\ell}(X) = \mathbf{f}(X), \qquad \mathbf{r}(X) = \mathbf{g}(X).

The claimed relation between the constant vectors is

v = \langle \mathbf{f}_0, \mathbf{g}_0 \rangle.

The algebra below holds for any choice of the linear coefficients. If those coefficients are intended to mask the constant vectors, sample $\mathbf{f}_1$ and $\mathbf{g}_1$ independently and uniformly for each interaction, and use a nonzero challenge as specified below. This describes the masking step; a zero-knowledge claim for the entire transcript still needs its own proof.

Define the scalar polynomial

t(X) = \langle \boldsymbol{\ell}(X), \mathbf{r}(X) \rangle.

Expanding by bilinearity gives

\begin{aligned} t(X) &= \langle \mathbf{f}_1 X + \mathbf{f}_0, \mathbf{g}_1 X + \mathbf{g}_0 \rangle \\ &= \langle \mathbf{f}_1, \mathbf{g}_1 \rangle X^2 \\ &\quad + \bigl( \langle \mathbf{f}_0, \mathbf{g}_1 \rangle + \langle \mathbf{f}_1, \mathbf{g}_0 \rangle \bigr) X \\ &\quad + \langle \mathbf{f}_0, \mathbf{g}_0 \rangle. \end{aligned}

Therefore,

t(X) = t_2 X^2 + t_1 X + t_0,

with coefficients

\begin{aligned} t_0 &= v = \langle \mathbf{f}_0, \mathbf{g}_0 \rangle, \\ t_1 &= \langle \mathbf{f}_0, \mathbf{g}_1 \rangle + \langle \mathbf{f}_1, \mathbf{g}_0 \rangle, \\ t_2 &= \langle \mathbf{f}_1, \mathbf{g}_1 \rangle. \end{aligned}

The constant coefficient is the original inner-product claim. The linear coefficient collects the two cross terms, and the quadratic coefficient comes from multiplying the two linear terms.

3. Commit to the coefficients

A vector commitment combines a vector with a scalar blinding factor:

C_{\mathrm{vec}}(\mathbf{a}; \rho) = \langle \mathbf{a}, \mathbf{G} \rangle + \rho H.

A scalar commitment uses the same pattern:

C_{\mathrm{scalar}}(a; \rho) = aG + \rho H.

For newly created commitments, the prover samples scalar blinding factors $\alpha_1, \alpha_2, \beta_1, \beta_2, \gamma_0, \gamma_1, \gamma_2$ independently and uniformly from $\mathbb{F}_q$ and constructs four vector commitments:

\begin{aligned} A &= \langle \mathbf{f}_0, \mathbf{G} \rangle + \alpha_1 H, \\ B &= \langle \mathbf{g}_0, \mathbf{G} \rangle + \alpha_2 H, \\ L &= \langle \mathbf{f}_1, \mathbf{G} \rangle + \beta_1 H, \\ R &= \langle \mathbf{g}_1, \mathbf{G} \rangle + \beta_2 H. \end{aligned}

The scalar coefficients receive their own commitments:

\begin{aligned} V &= vG + \gamma_0 H, \\ T_1 &= t_1G + \gamma_1 H, \\ T_2 &= t_2G + \gamma_2 H. \end{aligned}

Thus $A$ and $B$ commit to the constant vectors, $L$ and $R$ commit to the linear coefficients, and $V$ , $T_1$ , and $T_2$ commit to the scalar polynomial's coefficients.

All these commitments are fixed before the verifier chooses the challenge. The commitments $A$ , $B$ , and $V$ identify the statement being checked. If they already exist, the prover uses their existing openings, while generating fresh masks and blinding factors for $L$ , $R$ , $T_1$ , and $T_2$ . The verifier must use the intended statement commitments throughout the interaction.

Here $v$ is committed through $V$ . If an application claims that $v$ equals a separately advertised public number, it must also connect $V$ to that number, for example by verifying its opening. The four checks below relate the committed values to one another.

4. Exchange the challenge and response

The interaction has three steps.

The prover sends the commitments. The verifier receives $A$ , $B$ , $L$ , $R$ , $V$ , $T_1$ , and $T_2$ .
The verifier chooses a challenge. After all commitments are fixed, the verifier uses cryptographically secure randomness to sample an unpredictable $u \in \mathbb{F}_q^{\times}$ uniformly from the nonzero field elements and sends it to the prover.
The prover opens the evaluations. The prover computes the two vector evaluations, the scalar evaluation, and their combined blinding factors.

The evaluations are

\begin{aligned} \boldsymbol{\ell}(u) &= \mathbf{f}_1 u + \mathbf{f}_0, \\ \mathbf{r}(u) &= \mathbf{g}_1 u + \mathbf{g}_0, \\ t(u) &= t_2 u^2 + t_1 u + v. \end{aligned}

The combined blinding factors follow the same polynomial weights:

\begin{aligned} \pi_{\ell} &= \alpha_1 + u\beta_1, \\ \pi_r &= \alpha_2 + u\beta_2, \\ \pi_t &= \gamma_0 + u\gamma_1 + u^2\gamma_2. \end{aligned}

The complete response is

\bigl( \boldsymbol{\ell}(u),\, \mathbf{r}(u),\, t(u),\, \pi_{\ell},\, \pi_r,\, \pi_t \bigr).

Here, the $\pi$ values are scalar opening information. Their role is to account for the blinding terms when commitments are combined.

The prover must reject a zero challenge: it would give $\boldsymbol{\ell}(0)=\mathbf{f}_0$ and $\mathbf{r}(0)=\mathbf{g}_0$ , directly disclosing both constant vectors. The prover must also answer at most one challenge for each set of masks. Two distinct challenges with the same linear polynomial reveal its coefficients by interpolation.

5. Check the scalar polynomial commitment

The verifier first checks

\boxed{ t(u)G + \pi_t H = V + uT_1 + u^2T_2. }

Why does this hold for the intended construction? Expand the right-hand side:

\begin{aligned} V + uT_1 + u^2T_2 &= (vG + \gamma_0 H) \\ &\quad + u(t_1G + \gamma_1 H) \\ &\quad + u^2(t_2G + \gamma_2 H) \\ &= (v + ut_1 + u^2t_2)G \\ &\quad + (\gamma_0 + u\gamma_1 + u^2\gamma_2)H \\ &= t(u)G + \pi_t H. \end{aligned}

Equivalently, subtracting the combined blinding term yields

\begin{aligned} V + uT_1 + u^2T_2 - \pi_t H &= (v + ut_1 + u^2t_2)G \\ &= t(u)G. \end{aligned}

This check connects the submitted scalar evaluation to the committed coefficients.

6. Check the two vector commitments

The verifier performs an analogous check for each vector evaluation.

The right vector

The right-vector equation is

\boxed{ \langle \mathbf{r}(u), \mathbf{G} \rangle + \pi_r H = B + uR. }

Expanding the commitments gives

\begin{aligned} B + uR &= \langle \mathbf{g}_0, \mathbf{G} \rangle + \alpha_2 H \\ &\quad + u\bigl( \langle \mathbf{g}_1, \mathbf{G} \rangle + \beta_2 H \bigr) \\ &= \langle \mathbf{g}_0 + u\mathbf{g}_1, \mathbf{G} \rangle \\ &\quad + (\alpha_2 + u\beta_2)H \\ &= \langle \mathbf{r}(u), \mathbf{G} \rangle + \pi_r H. \end{aligned}

After subtracting the blinding term, the same calculation reads

\begin{aligned} B + uR - \pi_r H &= \langle \mathbf{g}_0, \mathbf{G} \rangle + u\langle \mathbf{g}_1, \mathbf{G} \rangle \\ &= \langle \mathbf{r}(u), \mathbf{G} \rangle. \end{aligned}

The left vector

The left-vector equation is

\boxed{ \langle \boldsymbol{\ell}(u), \mathbf{G} \rangle + \pi_{\ell} H = A + uL. }

Its expansion follows the same pattern:

\begin{aligned} A + uL &= \langle \mathbf{f}_0, \mathbf{G} \rangle + \alpha_1 H \\ &\quad + u\bigl( \langle \mathbf{f}_1, \mathbf{G} \rangle + \beta_1 H \bigr) \\ &= \langle \mathbf{f}_0 + u\mathbf{f}_1, \mathbf{G} \rangle \\ &\quad + (\alpha_1 + u\beta_1)H \\ &= \langle \boldsymbol{\ell}(u), \mathbf{G} \rangle + \pi_{\ell} H. \end{aligned}

Subtracting the blinding term gives

\begin{aligned} A + uL - \pi_{\ell} H &= \langle \mathbf{f}_0, \mathbf{G} \rangle + u\langle \mathbf{f}_1, \mathbf{G} \rangle \\ &= \langle \boldsymbol{\ell}(u), \mathbf{G} \rangle. \end{aligned}

Both vector checks rely on the linearity of the commitment: the vector entries and their blinding factors combine with the same weights.

7. Check the inner-product relation

The final check connects the two opened vectors to the opened scalar:

\boxed{ t(u) = \langle \boldsymbol{\ell}(u), \mathbf{r}(u) \rangle. }

Start with the scalar polynomial:

\begin{aligned} t(u) &= t_2u^2 + t_1u + v \\ &= \langle \mathbf{f}_1, \mathbf{g}_1 \rangle u^2 \\ &\quad + \bigl( \langle \mathbf{f}_0, \mathbf{g}_1 \rangle + \langle \mathbf{f}_1, \mathbf{g}_0 \rangle \bigr)u \\ &\quad + \langle \mathbf{f}_0, \mathbf{g}_0 \rangle. \end{aligned}

Now expand the inner product of the evaluated vectors independently:

\begin{aligned} \langle \boldsymbol{\ell}(u), \mathbf{r}(u) \rangle &= \langle \mathbf{f}_1u + \mathbf{f}_0, \mathbf{g}_1u + \mathbf{g}_0 \rangle \\ &= \langle \mathbf{f}_1, \mathbf{g}_1 \rangle u^2 \\ &\quad + \langle \mathbf{f}_1, \mathbf{g}_0 \rangle u \\ &\quad + \langle \mathbf{f}_0, \mathbf{g}_1 \rangle u \\ &\quad + \langle \mathbf{f}_0, \mathbf{g}_0 \rangle. \end{aligned}

The quadratic terms agree. The two linear terms agree after collecting them. The constant terms also agree. Therefore, an honestly constructed response satisfies

t(u) = \langle \boldsymbol{\ell}(u), \mathbf{r}(u) \rangle.

8. What the verifier accepts

The verifier accepts only when all four equations hold:

\begin{aligned} t(u)G + \pi_t H &= V + uT_1 + u^2T_2, \\ \langle \mathbf{r}(u), \mathbf{G} \rangle + \pi_r H &= B + uR, \\ \langle \boldsymbol{\ell}(u), \mathbf{G} \rangle + \pi_{\ell} H &= A + uL, \\ \langle \boldsymbol{\ell}(u), \mathbf{r}(u) \rangle &= t(u). \end{aligned}

The first three equations connect the evaluations to the previously sent commitments. The fourth checks the relation between those evaluations.

This derivation establishes completeness: when the prover constructs the commitments and responses as described, every check succeeds. Soundness, knowledge extraction, and zero knowledge require separate arguments. The response here also includes both full vectors, so the construction as written has communication that grows linearly with the vector length. Replacing those explicit vectors with a logarithmic inner-product argument is a separate construction.

The central algebraic observation is that the same challenge weights apply to the values, their commitments, and their blinding factors. That shared structure lets the verifier check each opening and then compare the resulting inner product.

Editorial note: This post adapts the three-page handwritten inner-product notes. The polynomial initially called $h$ is written consistently as $t$ . The blinding generator is renamed $H$ to distinguish it from commitment $B$ , and the left-vector expansion uses $\beta_1$ , matching the definition of $L$ . The original cross term $\langle \mathbf{g}_0, \mathbf{f}_1 \rangle$ is written equivalently as $\langle \mathbf{f}_1, \mathbf{g}_0 \rangle$ . The review also makes fresh randomness, statement binding, and the nonzero, single-response challenge rule explicit. These operational clarifications extend the notes without changing their algebra.