# Inner Product Argument

https://dankradfeist.de/ethereum/2021/11/18/inner-product-arguments-mandarin.html

https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html

https://eprint.iacr.org/2017/1066.pdf

## 符号约定

定义在 $\mathbb{F}_p$ 上的椭圆曲线群 $\mathbb{G}$，标量域为 $\mathbb{F}_r$，从 $\mathbb{G}$ 中选取两组独立的点作为 base：
$\vec{G} = (G_1, G_2, \dots, G_n)$
$\vec{H} = (H_1, H_2, \dots, H_n)$

两个向量的内积定义为：
$$\vec{a} \cdot \vec{b} = \langle \vec{a}, \vec{b} \rangle = \sum_{i=1}^n a_ib_i = a_1b_1+ a_2b_2 + \cdots + a_nb_n$$

## 问题
对于某 $c \in \mathbb{F}_r$, $C \in \mathbb{G}$，证明者 $\mathcal{P}$ 需要说服验证者 $\mathcal{V}$，$\mathcal{P}$ 知道两个向量 $\vec{a} = (a_1, a_2, \dots, a_n)$ 和 $\vec{b} = (b_1, b_2, \dots, b_n)$，使得：$$C = \langle \vec{a}, \vec{G} \rangle + \langle \vec{b}, \vec{H} \rangle \quad \text{and} \quad c = \langle \vec{a}, \vec{b} \rangle$$

一个直观的想法是，$\mathcal{P}$ 直接发送 $\vec{a}$ 和 $\vec{b}$ 给 $\mathcal{V}$，然后让 $\mathcal{V}$ 自行计算验证，但是这样通信量为 $2n$ 个 $\mathbb{F}_r$ 的元素。验证者的工作至少是 $2n$ 个 $\mathbb{G}$ 上的标量乘法。

通过 IPA，可以将通信量降低为 $2 \log_2 n$ 个 $\mathbb{G}$ 上的点。验证者的工作没有特别降低，仍然 $\mathcal{O}(n)$ 个 $\mathbb{G}$ 上的标量乘法。

在 $\vec{G}, \vec{H}$ 之后，新增另一个base，$U \in \mathbb{G}$，然后问题转化为：

对于某 $C \in \mathbb{G}$，证明者 $\mathcal{P}$ 需要说服验证者 $\mathcal{V}$，$\mathcal{P}$ 知道两个向量 $\vec{a} = (a_1, a_2, \dots, a_n)$ 和 $\vec{b} = (b_1, b_2, \dots, b_n)$，使得：$$C = \langle \vec{a}, \vec{G} \rangle + \langle \vec{b}, \vec{H} \rangle + \langle \vec{a}, \vec{b} \rangle U$$

## 协议描述

### Commit

$\mathcal{P}$ 计算 $C = \vec{a} \cdot \vec{G} + \vec{b} \cdot \vec{H} + \vec{a} \cdot \vec{b} \ U$ 并发送给 $\mathcal{V}$

### 第一轮
假设 $m = \frac{n}{2}$，令 $\vec{a}_L = (a_1, a_2, \dots, a_m)$，$\vec{a}_R = (a_m, a_{m+1}, \dots, a_n)$，其他同理。

$\mathcal{P}$：
- 计算：
- $z_L= \vec{a}_R \cdot \vec{b}_L$
- $z_R= \vec{a}_L \cdot \vec{b}_R$
- $C_L= \vec{a}_R \cdot \vec{G}_L + \vec{b}_L \cdot \vec{H}_R + z_LU$
- $C_R= \vec{a}_L \cdot \vec{G}_R + \vec{b}_R \cdot \vec{H}_L + z_RU$
- 并将 $C_L, C_R$ 发送给 $\mathcal{V}$

### 第 $i$ 轮

$\mathcal{V}$:
- 生成随机挑战值 $x \in \mathbb{F}_r$，发送给 $\mathcal{P}$
- 自己计算:
- $C^\prime = x C_L + C + x^{-1} C_R$
- $\vec{G}^\prime = \vec{G}_L + x^{-1}\vec{G}_R$
- $\vec{H}^\prime = \vec{H}_L + x \vec{H}_R$

$\mathcal{P}$：
- 计算：
- $\vec{G}^\prime = \vec{G}_L + x^{-1}\vec{G}_R$
- $\vec{H}^\prime = \vec{H}_L + x \vec{H}_R$
- $\vec{a}^\prime = \vec{a}_L + x \vec{a}_R$
- $\vec{b}^\prime = \vec{b}_L + x^{-1} \vec{b}_R$

现在需要 $\mathcal{P}$ 证明 $C^\prime = \vec{a}^\prime \cdot \vec{G}^\prime + \vec{b}^\prime \cdot \vec{H}^\prime + \vec{a}^\prime \cdot \vec{b}^\prime \ U$

所有长度为前一轮的一半。然后替换：
$C = C^\prime$
$\vec{G} = \vec{G}^\prime$
$\vec{H} = \vec{H}^\prime$
$\vec{a} = \vec{a}^\prime$
$\vec{b} = \vec{b}^\prime$

如果此时 $|\vec{a}|$ 的长度不等于 $1$，回到上一步；
否则这是最后一轮：

$\mathcal{P}$:
- 发送 $\vec{a} = (a_1), \vec{b} = (b_1)$ 给 $\mathcal{V}$

$\mathcal{V}$:
- 计算 $D = a_1 G_1 + b_1 H_1 + a_1 b_1 U$，如果 $D = C$ 则接受，输出 True；否则拒绝，输出 False.

## 示例

### 问题

对于 $C \in \mathbb{G}$，$\mathcal{P}$ 需要向 $\mathcal{V}$ 证明，$\mathcal{P}$ 知道 $\vec{a} = (a_1, a_2)$ 和 $\vec{b} = (b_1, b_2)$， 使得 $C = \vec{a} \cdot \vec{G} + \vec{b} \cdot \vec{H} + \vec{a} \cdot \vec{b} \ U = a_1G_1 + a_2G_2 + b_1H_1 + b_2H_2 + (a_1b_1 + a_2 b_2)U$

### Commit
$\mathcal{P}$ 计算 $C$ 并发送给 $\mathcal{P}$。

### 第一轮
$\mathcal{P}$：
- 从 $\vec{a}$ 中获取 $\vec{a}_{L} = (a_1)$，$\vec{a}_{R} = (a_2)$
- 从 $\vec{b}$ 中获取 $\vec{b}_{L} = (b_1)$，$\vec{b}_{R} = (b_2)$
- 从 $\vec{G}$ 中获取 $\vec{G}_{L} = (G_1)$，$\vec{G}_{R} = (G_2)$
- 从 $\vec{H}$ 中获取 $\vec{H}_{L} = (H_1)$，$\vec{H}_{R} = (H_2)$
- 计算 $C_L = \vec{a}_{R} \cdot \vec{G}_{L} + \vec{b}_{L} \cdot \vec{H}_{R} + \vec{a}_{R} \cdot \vec{b}_{L} \ U = a_2G_1 + b_1H_2 + a_2b_1 U$
- 计算 $C_R = \vec{a}_{L} \cdot \vec{G}_{R} + \vec{b}_{R} \cdot \vec{H}_{L} + \vec{a}_{L} \cdot \vec{b}_{R} \ U = a_1G_2 + b_2H_1 + a_1b_2 U$
- 并将 $C_L, C_R$ 发送给 $\mathcal{V}$

### 第二轮

$\mathcal{V}$:
- 生成随机挑战值 $x \in \mathbb{F}_r$，发送给 $\mathcal{P}$
- 自己计算：
- $C^\prime = xC_L + C + x^{-1}C_R$
- $\vec{G}^\prime = \vec{G}_L + x^{-1}\vec{G}_R= (G_1 + x^{-1}G_2)$
- $\vec{H}^\prime = \vec{H}_L + x\vec{H}_R = (H_1 + xH_2)$

$\mathcal{P}$:
- 计算:
- $\vec{G}^\prime = \vec{G}_L + x^{-1}\vec{G}_R= (G_1 + x^{-1}G_2)$
- $\vec{H}^\prime = \vec{H}_L + x\vec{H}_R = (H_1 + xH_2)$
- $\vec{a}^\prime = \vec{a}_L + x\vec{a}_R= (a_1 + xa_2)$
- $\vec{b}^\prime = \vec{b}_L + x^{-1}\vec{b}_R = (b_1 + x^{-1}b_2)$
- 长度为 $1$，这已经是最后一轮，发送 $\vec{a}^\prime$，$\vec{b}^\prime$ 给 $\mathcal{V}$

$\mathcal{V}$:
- 计算 $$\begin{align*} D &= \vec{a}^\prime \vec{G}^\prime + \vec{b}^\prime \vec{H}^\prime + a^\prime b^\prime U \\ &= (a_1 + xa_2)(G_1 + x^{-1}G_2) + (b_1 + x^{-1}b_2)(H_1 + xH_2) + (a_1+xa_2)(b_1 + x^{-1}b_2) U \\ &= (a_1 + xa_2)G_1 + (a_1x^{-1} + a_2)G_2 + (b_1+x^{-1}b_2)H_1 + (b_1x + b_2)H_2 + (a_1b_1 + a_1x^{-1}b_2 + xa_2b_1 + a_2b_2)U \end{align*}$$

- $\begin{align*} C^\prime &= xC_L + C + x^{-1}C_R \\ & = (xa_2G_1 + xb_1H_2 + xa_2b_1U) + (a_1G_1 + a_2G_2 + b_1H_1 + b_2H_2 + (a_1b_1+a_2b_2)U) + (x^{-1} a_1G_2 + x^{-1}b_2H_1 + x^{-1}a_1b_2U) \\ &= (a_1 + xa_2)G_1 + (a_2 + a_1x^{-1})G_2 + (b_1 + x^{-1}b_2)H_1 + (b_2 + xb_1)H_2 + (xa_2b_1 + a_1b_1 + a_2b_2 + x^{-1}a_1b_2)U \\ &= D \end{align*}$

因此接受.

## 安全性分析

### correctness

$\mathcal{P}$ 按照协议正确执行，那么 $\mathcal{V}$ 一定能够输出 True，因为

$C$ 可以扩展为：
$$\begin{align*} C & = \vec{a} \cdot \vec{G} + \vec{b} \cdot \vec{H} + \vec{a} \cdot \vec{b} \ U \\ & = \vec{a}_L \cdot \vec{G}_L + \vec{a}_R \cdot \vec{G}_R + \vec{b}_L \cdot \vec{H}_L + \vec{b}_R \cdot \vec{H}_R + (\vec{a}_L \cdot \vec{b}_L + \vec{a}_R \cdot \vec{b}_R) \ U \end{align*}$$

如果 $\mathcal{P}$ 正确计算了 $\vec{a}^\prime$, $\vec{b}^\prime$, $\vec{G}^\prime$, $\vec{H}^\prime$, 那么最后一轮 $\mathcal{P}$ 能够得出 $D = C^\prime$

$$\begin{align*} D &= \vec{a}^\prime\vec{G}^\prime + \vec{b}^\prime \vec{H}^\prime + \vec{a}^\prime\vec{b}^\prime U \\ & = (\vec{a}_L + x \vec{a}_R)(\vec{G}_L + x^{-1} \vec{G}_R) + (\vec{b}_L + x^{-1}\vec{b}_R)(\vec{H}_L + x \vec{H}_R) + (\vec{a}_L + x\vec{a}_R)(\vec{b}_L + x^{-1}\vec{b}_R)U \\ &= \vec{a}_L \vec{G}_L + x\vec{a}_R\vec{G}_L + \vec{a}_L x^{-1}\vec{G}_R + \vec{a}_R\vec{G}_R + \vec{b_L}\vec{H}_L + x\vec{b}_L\vec{H}_R + x^{-1} \vec{b}_R \vec{H}_L + \vec{b}_R\vec{H}_R + (\vec{a}_L \vec{b}_L + x\vec{a}_R\vec{b}_L + x^{-1}\vec{a}_L \vec{b}_R + \vec{a}_R\vec{b}_R)U \\ & = (\vec{a}_L\vec{G}_L + \vec{a}_R\vec{G}_R + \vec{b}_L\vec{H}_L + \vec{b}_R\vec{H}_R + (\vec{a}_L\vec{b}_L + \vec{a}_R\vec{b}_R)U) + x(\vec{a}_R\vec{G}_L + \vec{b}_L\vec{H}_R + \vec{a}_R\vec{b}_L U) + x^{-1}(\vec{a}_L\vec{G}_R + \vec{b}_R\vec{H}_L + \vec{a}_L\vec{b}_RU) \\ & = C + xC_L + x^{-1}C_R \\ & = C^\prime \end{align*}$$

### soundness
$\mathcal{P}$ 能否作恶来欺骗 $\mathcal{V}$？

假设 $\mathcal{P}$ 提交了 $C = \vec{a} \cdot \vec{G} + \vec{b} \cdot \vec{H} + r U$，其中 $r \neq \vec{a} \cdot \vec{b}$，

$\vec{a}^\prime =\vec{a}_L + x\vec{a}_R$
$\vec{b}^\prime =\vec{b}_L + x^{-1}\vec{b}_R$
$\vec{G}^\prime =\vec{G}_L + x^{-1}\vec{G}_R$
$\vec{H}^\prime =\vec{H}_L + x\vec{H}_R$

$C^\prime = \vec{a}^\prime\vec{G}^\prime + \vec{b}^\prime\vec{H}^\prime + (xz_L+ r + x^{-1}z_R)U$

要想最后成功验证，第二轮的参数需要满足内积形式：
$\vec{a}^\prime \cdot \vec{b}^\prime = xz_L+ r + x^{-1}z_R$
$\vec{a}_L\vec{b}_L + \vec{a}_R\vec{b}_R + x^{-1}\vec{a}_L\vec{b}_R + x\vec{a}_R\vec{b}_L = xz_L+ r + x^{-1}z_R$
$(\vec{a}_R\vec{b}_L - z_L)x^2 + (\vec{a}\cdot\vec{b}-r)x + (\vec{a}_L\vec{b}_R - z_R) = 0$

$\mathcal{V}$ 是在 $\mathcal{P}$ 承诺 $r, z_L, z_R$ 后选取的随机 $x$，因此上面等式成立的概率约为 $\frac{2}{|\mathbb{F}_r|}$，是一个可以忽略的值。

## 性能优化

$\mathcal{V}$ 每轮都需要更新 base $\vec{G}, \vec{H}$，但是他其实只需要每轮把 $x_i$ 发送过去，只有最后的时候需要验证，因此可以把 base 更新放到最后，并且使用标量之间的运算替代中间步骤的 msm。

$\vec{G}$: $(G_1, G_2, G_3, G_4, G_5, G_6, G_7, G_8)$
$\vec{H}$: $(H_1, H_2, H_3, H_4, G_5, H_6, H_7, H_8)$

$(G_1 + x_1^{-1}G_5, G_2 + x_1^{-1}G_6, G_3 + x_1^{-1}G_7, G_4 + x_1^{-1}G_8)$

$(G_1 + x_1^{-1}G_5 + x_2^{-1}G_3 + x_1^{-1}x_2^{-1}G_7, G_2+ x_1^{-1}G_6 + x_2^{-1}G_4 + x_1^{-1}x_2^{-1}G_8)$

$G_1 + x_3^{-1}G_2 + x_2^{-1}G_3 + x_2^{-1}x_3^{-1}G_4 + x_1^{-1}G_5 + x_1^{-1}x_3^{-1}G_6 + x_1^{-1}x_2^{-1}G_7 + x_1^{-1}x_2^{-1}x_3^{-1}G_8$

$$f_G(X) = \prod_{j=0}^{k-1}(1 + x_{k-j}^{-1} X^{2^j})$$

$f_G(X)$ 的 $X^i$ 系数对应 $G_{i+1}$的标量乘法。

$$f_H(X) = \prod_{j=0}^{k-1}(1 + x_{k-j} X^{2^j})$$

$f_H(X)$ 的 $X^i$ 系数对应 $H_{i+1}$的标量乘法。

## 使用 IPA 验证多项式

### 承诺的计算
场景：
- 验证 $f(x) = \sum_{i=0}^{n-1} a_i x^i$ 在 $z$ 处的取值。
- 令 $\vec{a} = (a_0, a_1, \dots, a_{n-1})$, $\vec{b} = (1, z, z^2, \dots, z^{n-1})$，则我们可以通过 IPA 验证承诺 $C$ 具体“内积属性”。并且通过改进，还能验证 $f(z) = \sum_{i=0}^{n-1} a_i z^i = \vec{a}\cdot\vec{b}$ 的结果

内积属性的含义是：$C = \vec{a} \cdot \vec{G} + \vec{b} \cdot \vec{H} + \vec{a}\cdot\vec{b} U$

$\mathcal{P}$:
- 计算承诺 $F = \vec{a} \cdot \vec{G}$
- 发送承诺 $F$ 给 $\mathcal{V}$

$\mathcal{V}$:
- 发送自变量 $z$ 给 $\mathcal{P}$

$\mathcal{P}$:
- 计算 $y = f(z)$，发送 $y$ 给 $\mathcal{V}$。

$\mathcal{V}$:
- 计算
- $C = \vec{a} \cdot \vec{G} + \vec{b} \cdot \vec{H} + \vec{a} \cdot \vec{b} U = F + \vec{b} \cdot \vec{H} + yU$
- 因为 $\vec{b} = (1, z, z^2, \dots, z^{n-1})$ 对 $\mathcal{V}$ 来说是已知的。

这里有个问题，$\mathcal{P}$ 可以作弊，比如他提交 $F = \vec{a} \cdot \vec{G} + t U$，然后能够证明 $f(z) = y -t$。问题的来源是 $\mathcal{P}$ 在承诺的时候就知道了base $U$，因此 $\mathcal{V}$ 可以在收到 $F$ 和 $y$ 之后重新选择 $U = wU$，$w$ 为一个随机标量。
- 后面的交互式流程就和前面描述的 IPA 一样了。

### 优化
$\vec{b} = (1, z, z^2, \dots, z^{n-1})$ 是已知的，可以参考前面对 $\vec{G}, \vec{H}$ 的优化。由 $f_G(Z)$ 给出系数。

### 针对点值形式 evaluation format 的多项式
前面给出了系数形式的 IPA

虽然给定 $n$ 个系数或者 $n$ 个点都能唯一确定 $n-1$ 次多项式，但是点值形式转系数形式需要 FFT，有 $\mathcal{O}(n \log n)$ 次运算，并且要求定义域使用 Root of unity。否则是 $\mathcal{O}(n^2)$。

为了避免这项开销，直接对值进行承诺：
$$F = f(x_0) G_0 + f(x_1)G_1 + \cdots + f(x_{n-1})G_{n-1}$$
这表示 $\vec{a} = (f(x_0), f(x_1), f(x_2), \dots, f(x_{n-1}))$
使用重心公式：

$$f(z) = A(z)\sum_{i=0}^{n-1}\frac{f(x_i)}{A^\prime(x_i)} \frac{1}{z-x_i}$$
如果我们选择 $\vec{b}$:
$$b_i = \frac{A(z)}{A^\prime(x_i)} \frac{1}{z-x_i}$$

就能得到 $\vec{a} \cdot \vec{b} = f(z)$