(Take 1) - Using the Inner Product Argument as a Polynomial Commitment Scheme

4-minute read

Preamble

This was the first scheme that I derived, unfortunately it scales linearly. Skip to the next post to see the actual scheme used.

Problem

Given $m$ IPA commitments $C_0 = [f_0(X)] … C_{m-1} = [f_{m-1}(X)]$, prove evaluations:

$$ f_0(z_0) = y_0 \\vdots \f_{m-1}(z_{m-1}) = y_{m-1} $$

where $z_i \in {0,…,d-1}$

Unless we change from Bls12-381 to Bls12-377 or use the pasta curves, the embedded curve does not have a high 2-adicity ($2^7$), so we must use indices 0 to d-1 instead of the roots of unity.

Proof Outline

The proof will proceed in two steps:

  • First we form a polynomial that will assert the correctness of the above evaluations. We will call this polynomial $g(x)$
  • We then prove a random evaluation of this polynomial using the IPA.

Building g(x)

First we group all of the polynomials which are evaluated at the same point together. At most we will have $d$ groups.

To make the proof simpler, we make the following assumptions without loss of generality:

  • Assume that there are only two evaluation points $z_0$ and $z_1$.
  • Assume that the first half of the polymomials are evaluated at $z_0$ and the other half at $z_0$. ie ${f_0,…f_{\frac{m}{2}}}$ are evaluated at $z_0$ and ${f_{\frac{m}{2} +1},…f_{(m-1)}}$ are evaluated at $z_1$
  1. Let $r \leftarrow H(C_0,…C_{m-1}, z_0, …, z_{m-1}, y_0, …, y_{m-1})$

The prover linearly combines the polynomials in each group using $r$.

$g_1(X) = f_0(X) + r \cdot f_1(X) + r^2 \cdot f_2(X) +… + r^{\frac{m}{2}} \cdot f_{\frac{m}{2}}(X)$

$g_2(X) = f_{\frac{m}{2} +1}(X) + r \cdot f_{\frac{m}{2} +2}(X) + r^2 \cdot f_{\frac{m}{2} +3}(X) +… + r^{\frac{m}{2}} \cdot f_{m-1}(X)$

  1. Let $k \leftarrow H(r)$

Now we form polynomials that assert the correctness of $g_1(X)$ and $g_2(X)$

$w_1(X) = \frac{g_1(X) - g_1(z_0)}{X - z_0}$

$w_2(X) = \frac{g_2(X) - g_1(z_1)}{X - z_1}$

Combine these witness polynomials and the linearly combined input polynomials using $k$

$e(X) = w_1(X) + k \cdot w_2(X)$

Commit to $e(X)$ , we denote this commitment $[e(X)]$ as $E$

  1. Let $q = H(k, E)$

We need to link those witness polynomials to the original input polynomials, we do this by linearly combining them together:

$g(X) = e(x) + q \cdot g_1(X) + q^2 \cdot g_2(X)$

We do not commit to this polynomial, however it is the polynomial that we will run the IPA sub-protocol on.

Random Evaluation of $g(X)$

  1. Let $t \leftarrow H(q)$

The prover now runs a IPA_Prove protocol on $g(X)$ on the point $t$. If we assume that we are in the monomial basis, the first vector will be the coefficients of $g(X)$ and the second vector will be powers of $t$

The prover now computes $g_1(t)$, $g_2(t)$. Note that the verifier only needs this auxillary information to compute $g(t)$

Overview

The prover sends the verifier:

  • $C_0,…,C_{m-1}$
  • $y_0,…, y_{m-1}$
  • $E = [e(X)]$
  • $g_1(t), g_2(t)$
  • IPA_PROOF

Verification

We assume the verifier gets $z_0, … z_m$ from a higher level protocol, just like the KZG protocol. This is stated here because it was not included in the proof.

Compute $[g(X)]$

  1. Let $r \leftarrow H(C_0,…C_{m-1}, z_0, …, z_{m-1}, y_0, …, y_{m-1})$

Compute $[g_1(X)]$ and $[g_2(X)]$

$[g_1(X)] = C_0 + r \cdot C_1 + r^2 \cdot c_2 +… + r^{\frac{m}{2}} \cdot C_{\frac{m}{2}}$

$[g_2(X)] = C_{\frac{m}{2} +1} + r \cdot C_{\frac{m}{2} +2} + r^2 \cdot C_{\frac{m}{2} +3} +… + r^{\frac{m}{2}} \cdot C_{m-1}$

  1. Let $k \leftarrow H(r)$

The verifier cannot compute $[w_1(X)]$ and $[w_2(X)]$, but this is fine because they can compute $w_1(t)$ and $w_2(t)$ and check it’s consistency against $[h(X)]$

  1. Let $q = H(k, E)$

The verifier now has all the components to compute [g(X)]

$[g(X)] = E + q \cdot [g_1(X)] + q^2 \cdot [g_2(X)]$

Compute $g(t)$

  1. Let $t = H(q)$

Compute $w_1(t)$ and $w_2(t)$

$w_1(t) = \frac{g_1(t) - g_1(z_0)}{t - z_0}$

$w_2(t) = \frac{g_2(t) - g_1(z_1)}{t - z_1}$

Note: $g_1(z_0)$ and $g_2(z_1)$can be computed by the verifier, since they have $y_i$

The verifier is now able to compute $g(t) = w_1(t) + k \cdot w_2(t)$

Now They can run IPA_VERIFY using $[g(x)]$, $g(t)$ and the IPA_PROOF

Complexity

We will now analyse the communication complexity of the protocol in the worse case, first notice that the more different points we have, the more $w_i(X)$ and $g_i(X)$ polynomials there are. There are in total $d$ different points. So our proof size in the worse case will contain $d$ $g_i(t)$ scalars. The $w_i(X)$ polynomials are aggregated and do not contribute to the proof size.