Inner Product Argument

符号约定

定义在

F_{p}

上的椭圆曲线群

G

，标量域为

F_{r}

，从

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} = ⟨ \vec{a}, \vec{b} ⟩ = \sum_{i = 1}^{n} a_{i} b_{i} = a_{1} b_{1} + a_{2} b_{2} + \dots + a_{n} b_{n}

问题

对于某

c \in F_{r}

C \in G

，证明者

P

需要说服验证者

V

，

P

知道两个向量

\vec{a} = (a_{1}, a_{2}, \dots, a_{n})

和

\vec{b} = (b_{1}, b_{2}, \dots, b_{n})

，使得：

C = ⟨ \vec{a}, \vec{G} ⟩ + ⟨ \vec{b}, \vec{H} ⟩ and c = ⟨ \vec{a}, \vec{b} ⟩

一个直观的想法是，

P

直接发送

\vec{a}

和

\vec{b}

给

V

，然后让

V

自行计算验证，但是这样通信量为

2 n

个

F_{r}

的元素。验证者的工作至少是

2 n

个

G

上的标量乘法。

通过 IPA，可以将通信量降低为

2 \log_{2} n

个

G

上的点。验证者的工作没有特别降低，仍然

O (n)

个

G

上的标量乘法。

在

\vec{G}, \vec{H}

之后，新增另一个base，

U \in G

，然后问题转化为：

对于某

C \in G

，证明者

P

需要说服验证者

V

，

P

知道两个向量

\vec{a} = (a_{1}, a_{2}, \dots, a_{n})

和

\vec{b} = (b_{1}, b_{2}, \dots, b_{n})

，使得：

C = ⟨ \vec{a}, \vec{G} ⟩ + ⟨ \vec{b}, \vec{H} ⟩ + ⟨ \vec{a}, \vec{b} ⟩ U

协议描述

Commit

P

计算

C = \vec{a} \cdot \vec{G} + \vec{b} \cdot \vec{H} + \vec{a} \cdot \vec{b} U

并发送给

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})

，其他同理。

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_{L} U$
$C_{R} = {\vec{a}}_{L} \cdot {\vec{G}}_{R} + {\vec{b}}_{R} \cdot {\vec{H}}_{L} + z_{R} U$
并将
$C_{L}, C_{R}$ 发送给
$V$

第
$i$ 轮

V

生成随机挑战值
$x \in F_{r}$ ，发送给
$P$
自己计算:
$C^{'} = x C_{L} + C + x^{- 1} C_{R}$
${\vec{G}}^{'} = {\vec{G}}_{L} + x^{- 1} {\vec{G}}_{R}$
${\vec{H}}^{'} = {\vec{H}}_{L} + x {\vec{H}}_{R}$

P

：

计算：
${\vec{G}}^{'} = {\vec{G}}_{L} + x^{- 1} {\vec{G}}_{R}$
${\vec{H}}^{'} = {\vec{H}}_{L} + x {\vec{H}}_{R}$
${\vec{a}}^{'} = {\vec{a}}_{L} + x {\vec{a}}_{R}$
${\vec{b}}^{'} = {\vec{b}}_{L} + x^{- 1} {\vec{b}}_{R}$

现在需要

P

证明

C^{'} = {\vec{a}}^{'} \cdot {\vec{G}}^{'} + {\vec{b}}^{'} \cdot {\vec{H}}^{'} + {\vec{a}}^{'} \cdot {\vec{b}}^{'} U

所有长度为前一轮的一半。然后替换：

C = C^{'}

\vec{G} = {\vec{G}}^{'}

\vec{H} = {\vec{H}}^{'}

\vec{a} = {\vec{a}}^{'}

\vec{b} = {\vec{b}}^{'}

如果此时

| \vec{a} |

的长度不等于

1

，回到上一步；
否则这是最后一轮：

P

发送
$\vec{a} = (a_{1}), \vec{b} = (b_{1})$ 给
$V$

V

计算
$D = a_{1} G_{1} + b_{1} H_{1} + a_{1} b_{1} U$ ，如果
$D = C$ 则接受，输出 True；否则拒绝，输出 False.

示例

问题

对于

C \in G

，

P

需要向

V

证明，

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_{1} G_{1} + a_{2} G_{2} + b_{1} H_{1} + b_{2} H_{2} + (a_{1} b_{1} + a_{2} b_{2}) U

Commit

P

计算

C

并发送给

P

。

第一轮

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_{2} G_{1} + b_{1} H_{2} + a_{2} b_{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_{1} G_{2} + b_{2} H_{1} + a_{1} b_{2} U$
并将
$C_{L}, C_{R}$ 发送给
$V$

第二轮

V

生成随机挑战值
$x \in F_{r}$ ，发送给
$P$
自己计算：
$C^{'} = x C_{L} + C + x^{- 1} C_{R}$
${\vec{G}}^{'} = {\vec{G}}_{L} + x^{- 1} {\vec{G}}_{R} = (G_{1} + x^{- 1} G_{2})$
${\vec{H}}^{'} = {\vec{H}}_{L} + x {\vec{H}}_{R} = (H_{1} + x H_{2})$

P

计算:
${\vec{G}}^{'} = {\vec{G}}_{L} + x^{- 1} {\vec{G}}_{R} = (G_{1} + x^{- 1} G_{2})$
${\vec{H}}^{'} = {\vec{H}}_{L} + x {\vec{H}}_{R} = (H_{1} + x H_{2})$
${\vec{a}}^{'} = {\vec{a}}_{L} + x {\vec{a}}_{R} = (a_{1} + x a_{2})$
${\vec{b}}^{'} = {\vec{b}}_{L} + x^{- 1} {\vec{b}}_{R} = (b_{1} + x^{- 1} b_{2})$
长度为
$1$ ，这已经是最后一轮，发送
${\vec{a}}^{'}$ ，
${\vec{b}}^{'}$ 给
$V$

V

计算
$\begin{aligned} D & = {\vec{a}}^{'} {\vec{G}}^{'} + {\vec{b}}^{'} {\vec{H}}^{'} + a^{'} b^{'} U \\ = (a_{1} + x a_{2}) (G_{1} + x^{- 1} G_{2}) + (b_{1} + x^{- 1} b_{2}) (H_{1} + x H_{2}) + (a_{1} + x a_{2}) (b_{1} + x^{- 1} b_{2}) U \\ = (a_{1} + x a_{2}) G_{1} + (a_{1} x^{- 1} + a_{2}) G_{2} + (b_{1} + x^{- 1} b_{2}) H_{1} + (b_{1} x + b_{2}) H_{2} + (a_{1} b_{1} + a_{1} x^{- 1} b_{2} + x a_{2} b_{1} + a_{2} b_{2}) U \end{aligned}$
$\begin{aligned} C^{'} & = x C_{L} + C + x^{- 1} C_{R} \\ = (x a_{2} G_{1} + x b_{1} H_{2} + x a_{2} b_{1} U) + (a_{1} G_{1} + a_{2} G_{2} + b_{1} H_{1} + b_{2} H_{2} + (a_{1} b_{1} + a_{2} b_{2}) U) + (x^{- 1} a_{1} G_{2} + x^{- 1} b_{2} H_{1} + x^{- 1} a_{1} b_{2} U) \\ = (a_{1} + x a_{2}) G_{1} + (a_{2} + a_{1} x^{- 1}) G_{2} + (b_{1} + x^{- 1} b_{2}) H_{1} + (b_{2} + x b_{1}) H_{2} + (x a_{2} b_{1} + a_{1} b_{1} + a_{2} b_{2} + x^{- 1} a_{1} b_{2}) U \\ = D \end{aligned}$

因此接受.

安全性分析

correctness

P

按照协议正确执行，那么

V

一定能够输出 True，因为

C

可以扩展为：

\begin{aligned} 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{aligned}

如果

P

正确计算了

{\vec{a}}^{'}

{\vec{b}}^{'}

{\vec{G}}^{'}

{\vec{H}}^{'}

, 那么最后一轮

P

能够得出

D = C^{'}

\begin{aligned} D & = {\vec{a}}^{'} {\vec{G}}^{'} + {\vec{b}}^{'} {\vec{H}}^{'} + {\vec{a}}^{'} {\vec{b}}^{'} 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}}_{R} U) \\ = C + x C_{L} + x^{- 1} C_{R} \\ = C^{'} \end{aligned}

soundness

P

能否作恶来欺骗

V

？

假设

P

提交了

C = \vec{a} \cdot \vec{G} + \vec{b} \cdot \vec{H} + r U

，其中

r \neq \vec{a} \cdot \vec{b}

，

{\vec{a}}^{'} = {\vec{a}}_{L} + x {\vec{a}}_{R}

{\vec{b}}^{'} = {\vec{b}}_{L} + x^{- 1} {\vec{b}}_{R}

{\vec{G}}^{'} = {\vec{G}}_{L} + x^{- 1} {\vec{G}}_{R}

{\vec{H}}^{'} = {\vec{H}}_{L} + x {\vec{H}}_{R}

C^{'} = {\vec{a}}^{'} {\vec{G}}^{'} + {\vec{b}}^{'} {\vec{H}}^{'} + (x z_{L} + r + x^{- 1} z_{R}) U

要想最后成功验证，第二轮的参数需要满足内积形式：

{\vec{a}}^{'} \cdot {\vec{b}}^{'} = x z_{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} = x z_{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

V

是在

P

承诺

r, z_{L}, z_{R}

后选取的随机

x

，因此上面等式成立的概率约为

\frac{2}{| F_{r} |}

，是一个可以忽略的值。

性能优化

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

P

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

V

发送自变量
$z$ 给
$P$

P

计算
$y = f (z)$ ，发送
$y$ 给
$V$ 。

V

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

这里有个问题，

P

可以作弊，比如他提交

F = \vec{a} \cdot \vec{G} + t U

，然后能够证明

f (z) = y - t

。问题的来源是

P

在承诺的时候就知道了base

U

，因此

V

可以在收到

F

和

y

之后重新选择

U = w U

，

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，有

O (n \log n)

次运算，并且要求定义域使用 Root of unity。否则是

O (n^{2})

。

为了避免这项开销，直接对值进行承诺：

F = f (x_{0}) G_{0} + f (x_{1}) G_{1} + \dots + 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^{'} (x_{i})} \frac{1}{z - x_{i}}

如果我们选择

\vec{b}

b_{i} = \frac{A (z)}{A^{'} (x_{i})} \frac{1}{z - x_{i}}

就能得到

\vec{a} \cdot \vec{b} = f (z)

新场景

$P$ 知道
$\vec{a}$ ，
$\vec{b}$ ，
$V$ 知道
$\vec{b}$ ，不知道（不想知道）
$\vec{a}$
base 为
$\vec{G} = (G_{0}, G_{1}, \dots, G_{n - 1})$ 和
$U$

过程：

$C_{a} = \vec{a} \cdot \vec{G}$
$U = w \cdot U$
$C_{0} = C_{a} + \vec{a} \cdot \vec{b} U$
$C_{L 1} = {\vec{a}}_{R 0} \cdot {\vec{G}}_{L 0} + {\vec{a}}_{R 0} \cdot {\vec{b}}_{L 0} U$
$C_{R 1} = {\vec{a}}_{L 0} \cdot {\vec{G}}_{R 0} + {\vec{a}}_{L 0} \cdot {\vec{b}}_{R 0} U$
$C_{1} = C_{0} + x_{1} C_{L 1} + x_{1}^{- 1} C_{R 1}$

一直到

k = \log n

${\vec{a}}_{k} = {\vec{a}}_{L k - 1} + x_{k} {\vec{a}}_{R k - 1}$
${\vec{b}}_{k} = {\vec{b}}_{L k - 1} + x_{k}^{- 1} {\vec{b}}_{R k - 1}$
$C_{L k} = {\vec{a}}_{R k - 1} \cdot {\vec{G}}_{L k - 1} + {\vec{a}}_{R k - 1} \cdot {\vec{b}}_{L k - 1} U$
$C_{R k} = {\vec{a}}_{L k - 1} \cdot {\vec{G}}_{R k - 1} + {\vec{a}}_{L k - 1} \cdot {\vec{b}}_{R k - 1} U$
$C_{k} = C_{k - 1} + x_{k} C_{L k} + x_{k}^{- 1} C_{R k}$

此外，

${\vec{a}}_{k}, {\vec{G}}_{k}$ 长度均为 1

C_{a}, {\vec{a}}_{k}, \vec{a} \cdot \vec{b}, {\vec{C}}_{L}, {\vec{C}}_{R}

发送给

V

V

验证:

$C_{k} = C_{a} + \vec{a} \cdot \vec{b} U + \sum_{i = 1}^{k} (x_{i} C_{L i} + x_{i}^{- 1} C_{R i})$
$C_{k} \overset{?}{=} {\vec{a}}_{k} [0] \cdot {\vec{G}}_{k} [0] + {\vec{a}}_{k} [0] {\vec{b}}_{k} [0] U$

verify_multiexp:

$\sum_{i = 1}^{k} (x_{i} C_{L i} + x_{i}^{- 1} C_{R i}) + C_{a} + (\vec{a} \cdot \vec{b} - {\vec{a}}_{k} [0] {\vec{b}}_{k} [0]) \cdot U - {\vec{a}}_{k} [0] \cdot {\vec{G}}_{k} [0] \overset{?}{=} 0$

\vec{G} = (G_{0}, G_{1}, G_{2}, \dots, G_{255})

C_{w} = \sum_{0}^{255} h_{i} G_{i}

h (x) = \sum_{i = 1}^{255} (h_{i} \cdot \prod_{1 \leq j \leq 255}^{j \neq i} \frac{x - j}{i - j})

用 IPA 证明

h (4) = h_{4}

asdfads

有两个数据 255，1，order+1

C_{1} = \sum_{0}^{254} H_{i} G_{i} + (o r d e r + 1) G_{255}

C_{2} = \sum_{0}^{254} H_{i} G_{i} + 1 G_{255}

Inner Product Argument

符号约定

问题

协议描述

Commit

第一轮

第 i 轮

示例

问题

Commit

第一轮

第二轮

安全性分析

correctness

soundness

性能优化

使用 IPA 验证多项式

承诺的计算

优化

针对点值形式 evaluation format 的多项式

新场景

Read more

Rust-Verkle [in progress]

LeRobot by hand

What is the KZG PCS

PCS Multiproofs

第
$i$ 轮