ipa.md

IPA (Inner Product Argument) Commitment Scheme

Overview

This implementation provides an optimized Inner Product Argument (IPA) commitment scheme that only multiplies half of the elements in each vector during each prover round, improving efficiency over naive implementations.

Mathematical Foundation

The IPA scheme operates with the following components:

1. Structured Reference String (SRS): A vector $\vec{G}=(G_0,G_1...,G_{d-1})$ where $G_i ∈ E(\mathbb{F}_p)$ and $\mathbb{F}_r$ is the scalar field of the elliptic curve, along with $G$ as an independent generator on the same curve.

2. Polynomial: $f(x)=\sum_{i=0}^{d-1}f_ix^i$ over field $F_r$, where the polynomial degree $d-1$ is such that $d=2^k$.

The opening and verification procedures expect an existing commitment to $f(x)$, represented as the scalar product $[f(x)]=\langle\vec{f},\vec{G}\rangle$, where $\vec{f}=(f_0, f_1,..., f_{d-1})$.

Key Procedures

Opening Proof (compute_opening_proof_internal)

For a vector $\vec{v}=(v_0,v_1,...,v_{2n-1})$ of length $2n$, we denote:

• $\vec{v}{low}=(v_0,v_1,...,v{n-1})$
• $\vec{v}{high}=(v{n},v_{n+1},...v_{2n-1})$

Procedure:

1. Send degree: Send polynomial degree plus one ($d$) to the verifier

2. Generator setup: Receive generator challenge $u$ from verifier (abort if zero)

   • Compute auxiliary generator $U=u\cdot G$, where $G$ is a generator of $E(\mathbb{F}_p)$

3. Initialize vectors:

   • Set $\vec{G}_{k}=\vec{G}$
   • Set $\vec{a}_{k}=\vec{p}$ (polynomial coefficients)
   • Compute evaluation vector $\vec{b}_{k}=(1,\beta,\beta^2,...,\beta^{d-1})$ where $p(\beta)$ is the evaluation to prove

4. Perform $k$ reduction rounds (for $i \in {k,...,1}$):

   1. Compute $L_{i-1}=\langle\vec{a}{i_low},\vec{G}{i_high}\rangle+\langle\vec{a}{i_low},\vec{b}{i_high}\rangle\cdot U$
   2. Compute $R_{i-1}=\langle\vec{a}{i_high},\vec{G}{i_low}\rangle+\langle\vec{a}{i_high},\vec{b}{i_low}\rangle\cdot U$
   3. Send $L_{i-1}$ and $R_{i-1}$ to verifier
   4. Receive round challenge $u_{i-1}$ from verifier (abort if zero)
   5. Update vectors:
      • $\vec{G}{i-1}=\vec{G}{i_low}+u_{i-1}^{-1}\cdot \vec{G}_{i_high}$
      • $\vec{a}{i-1}=\vec{a}{i_low}+u_{i-1}\cdot \vec{a}_{i_high}$
      • $\vec{b}{i-1}=\vec{b}{i_low}+u_{i-1}^{-1}\cdot \vec{b}_{i_high}$

5. Final step: Send the final $\vec{a}_{0} = (a_0)$ to the verifier

Verification (verify_internal)

Procedure:

1. Receive degree: Get polynomial degree plus one ($d$) from prover

2. Generator setup:

   • Receive generator challenge $u$ (abort if zero)
   • Compute $U=u\cdot G$

3. Compute adjusted commitment: $C'=C+f(\beta)\cdot U$

4. Process rounds:

   • Receive $L_j, R_j$ and compute challenges $u_j$ for $j \in {k-1,..,0}$
   • Abort immediately if any $u_j=0$

5. Compute final commitment: $C_0 = C' + \sum_{j=0}^{k-1}(u_j^{-1}L_j + u_jR_j)$

6. Compute evaluation: $b_0=g(\beta)=\prod_{i=0}^{k-1}(1+u_{i}^{-1}x^{2^{i}})$

7. Compute challenge vector: $\vec{s}=(1,u_{0}^{-1},u_{1}^{-1},u_{0}^{-1}u_{1}^{-1},...,\prod_{i=0}^{k-1}u_{i}^{-1})$

8. Compute final generator: $G_s=\langle \vec{s},\vec{G}\rangle$

9. Receive final value: Get $\vec{a}_{0}$ of length 1 from prover

10. Final verification:

    • Compute $C_{right}=a_{0}G_{s}+a_{0}b_{0}U$
    • Check that $C_{right} = C_0$
    • Return true if they match, false otherwise

Algorithm Intuition

The IPA algorithm can be understood through these key concepts:

1. Problem Setup

• We have two vectors $\vec{a}$ and $\vec{b}$ whose inner product we want to prove
• The prover cannot directly send vector $\vec{a}$ to the verifier
• Instead, the prover provides a commitment $\langle\vec{a},\vec{G}\rangle$

2. Commitment Binding

The verifier computes $C'=C+\langle\vec{a},\vec{b}\rangle\cdot U$ to bind together:

• The commitment: $C=\langle\vec{a},\vec{G}\rangle$
• The evaluation with auxiliary generator: $U=u⋅G$ (independent from $\vec{G}$)

3. Problem Reduction

The prover reduces the inner product verification of vectors $\vec{a}$, $\vec{b}$ of length $n$ to vectors $\vec{a}{new}$, $\vec{b}{new}$ of length $\frac{n}{2}$.

4. Vector Combination

Using the relationships:

• $\vec{a}{new}=\vec{a}{low}+\alpha\cdot \vec{a}_{high}$
• $\vec{b}{new}=\vec{b}{low}+\alpha^{-1}\cdot \vec{b}_{high}$

The inner product becomes: $$\langle \vec{a}{new},\vec{b}{new}\rangle = \langle\vec{a},\vec{b}\rangle+\alpha^{-1}\langle\vec{a}{low},\vec{b}{high}\rangle+\alpha \langle \vec{a}{high},\vec{b}{low}\rangle$$

5. Cross-term Commitments

The prover provides commitments to the cross-terms $\langle\vec{a}{low},\vec{b}{high}\rangle$ and $\langle \vec{a}{high},\vec{b}{low}\rangle$, allowing the verifier to reduce the initial commitment.

6. Generator Reduction

Similarly, with $\vec{G}{new}=\vec{G}{low}+\alpha^{-1}\vec{G}{high}$: $$\langle \vec{a}{new},\vec{G}{new}\rangle = \langle\vec{a},\vec{G}\rangle+\alpha^{-1}\langle\vec{a}{low},\vec{G}{high}\rangle+\alpha \langle \vec{a}{high},\vec{G}_{low}\rangle$$

7. Batched Reduction

The two reductions can be batched together: $$\langle \vec{a}{new},\vec{b}{new}\rangle U + \langle \vec{a}{new},\vec{G}{new}\rangle = \langle\vec{a},\vec{b}\rangle U+ \langle\vec{a},\vec{G}\rangle + \alpha^{-1}(\langle\vec{a}{low},\vec{b}{high}\rangle U +\langle\vec{a}{low},\vec{G}{high}\rangle) +\alpha (\langle \vec{a}{high},\vec{b}{low}\rangle U+\langle \vec{a}{high},\vec{G}{low}\rangle)$$

8. Final Step

After $k$ reduction steps: $$\langle \vec{a}{0},\vec{b}{0}\rangle U + \langle \vec{a}{0},\vec{G}{s}\rangle = a_0 b_0 U+a_0G_s$$

The prover provides $a_0$. The independence of $U$ and $\vec{G}$ ensures:

• $a_0$ is correctly constructed from $\vec{a}_k=\vec{p}$
• $a_0 b_0 U$ confirms the polynomial opening is indeed $f(\beta)$

Template Parameter

• Curve: The elliptic curve type used for the commitment scheme

References

• Previous IPA Documentation

Src:
https://github.com/AztecProtocol/aztec-packages/blob/85b35c7ac58ef9b98930af579f607ce2ace5ee09/barretenberg/cpp/src/barretenberg/commitment_schemes/ipa/ipa.hpp#L97