Inner-product arguments (IPAs)

tl;dr: A list of (related) works on inner-product arguments.

Bootle et al.¹

Bootle et al. ¹ introduce a logarithmic-sized inner-product argument and use it to build a transparent, logarithmic-sized zero-knowledge argument for arithmetic circuit satisfiability in the discrete log setting. Both the prover and the verifier time are linear.

The first idea behind Bootle et al. is to evenly-split $\u$ and $\v$ into left and right halves: \begin{align} \u &= \u_L || \u_R \\
\v &= \v_L || \v_R\\
\end{align}

The second ideas is to pick a random challenge $x$ and fold $\u$ and $\v$ as: \begin{align} \u’ &= x\u_L +\u_R \\
\v’ &= x^{-1}\v_L + \v_R\\
\end{align}

This way:

\begin{align} \langle \u’, \v’ \rangle &= \langle x\cdot \u_L + \u_R,\ x^{-1}\v_L + \v_R \rangle\\
&= \langle x\cdot \u_L,\ x^{-1}\v_L + \v_R \rangle + \langle \u_R,\ x^{-1}\v_L + \v_R \rangle\\
&= \langle x\cdot \u_L,\ x^{-1}\v_L \rangle + \langle x\cdot \u_L,\ \v_R \rangle + \langle \u_R,\ x^{-1}\v_L \rangle + \langle \u_R,\ \v_R \rangle\\
&= x\cdot x^{-1}\langle \u_L,\ \v_L \rangle + x\langle \u_L,\ \v_R \rangle + x^{-1}\langle \u_R,\ \v_L \rangle + \langle \u_R,\ \v_R \rangle\\
&= \underbrace{\langle \u_L, \v_L \rangle + \langle \u_R, \v_R \rangle}_{\langle \u, \v \rangle} + x\langle \u_L, \v_R \rangle + x^{-1}\langle \u_R, \v_L \rangle\\
&= \langle \u, \v \rangle + x\langle \u_L, \v_R \rangle + x^{-1}\langle \u_R, \v_L \rangle \end{align}

Note that there are these nasty cross terms next to the $\langle \u,\v\rangle$ inner product.

The third idea is to have the prover send (commitments to) $L = \langle \u_R, \v_L \rangle$ and $R = \langle \u_L, \v_R \rangle$ before the challenge $x$ is chosen, and the verifier updates the target to $\langle \u’, \v’ \rangle = x^{-1}L + \langle \u, \v \rangle + xR$.

Related work

• Bünz et al. ² improve upon the concrete efficiency of Bootle et al.’s inner-product argument¹ and use it to get a highly-efficient, transparent, zero-knowledge range proof, known as Bulletproofs.
  • They reduce the proof size from $\approx 6\log{n}$ to $\approx 2\log{n}$
  • They propose batching techniques for the IPA and thus the ZK range proof
• Linear-map Vector Commitments³ constructs vector commitments with linear-map openings (LVCs).
  • They build two pairing-based LVC constructions for inner products (monomial and Lagrange basis), but these are vector commitment schemes that support inner-product openings, not inner-product arguments in the Bootle et al. sense.
  • They use existing Inner Pairing Product (IPP) arguments as a building block.
• Lipmaa et al.⁴ propose a new univariate sumcheck argument called “Count” and use it to build an updatable zk-SNARK called “Vampire.”
  • Count is built on top of the existing inner-product commitment scheme⁵
  • The paper doesn’t propose a new IPA, but instead uses inner-product commitments as a tool for the sumcheck.

References

For cited works, see below 👇👇