这篇文章上次修改于 210 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
承诺
承诺分为 3 个步骤：承诺，打开承诺，验证承诺
- 承诺：发送方将某个值 x 封装为 y 发送给接收方。1）发送方不能改变信封中的值；2）接收方无法知道 x
- 打开承诺：发送方揭露 x
- 校验承诺：接收方校验打开的值 x 与 y 中封装的 x 是否相同。
承诺一个值
- 承诺：选择 x，计算 y = f(x)，发送 y
- 打开承诺：发送原象 x
- 校验承诺：函数一致性 y = f(x)
对函数有要求：
- 求逆是 NP 困难的
- 校验简单
- 函数通常是哈希函数等
承诺一个多项式
承诺：选择 n + 1 个随机数 $a_0, .. a_n$，构造多项式 $f(x) = \sum^n_{i=0}{a_i}x^i$，计算每个系数的椭圆曲线点
$$ A_i = a_i \cdot G, i = 0,..n $$
发送 $A_i$
- 打开承诺：打开一个随机点 k，计算 $f(k) = \sum^n_{i=0}a_ik^i$，发送 $(k, f(k))$
校验承诺：基于 $A_i$ 校验 $(k, f(k))$ 的正确性：$f(k)\cdot G = \sum^n_{i=0}(k^i \cdot A_i)$
公式推导：$f(k)\cdot G = \sum^n_{i=0}(a_ik^i \cdot G) = \sum^n_{i=0}(k^i \cdot A_i)$
Kate 承诺（KZG）
初始化
椭圆曲线双线性群为 $T = (e, G_{1}, G_{2})$，随机秘密数 $s \in Z_p^*$，$t + 1$ 元组 $<g, sg, ..., s^tg>$，令输出为
$$ PK = (T, g, sg, ..., s^tg) $$
承诺
对于多项式 $f(x) = \sum^n_{i=0}a_i \cdot x^i$，计算承诺
$$ C = f(s) \cdot g = \sum^n_{i=0}a_i \cdot s^i g $$
打开承诺
不需要把多项式的系数全部打开，这样的话数据量太大，验证计算的复杂度也比较高。
只需要打开一个随机点即可，计算商多项式
$$ h(x) = \frac{f(x) - f(z)}{x - z} $$
基于多项式系数和 PK，计算商多项式承诺
$$ W = h(s)\cdot g $$
输出 $(z, f(z), W)$
校验随机点
由于椭圆曲线群只支持加法同态，无法支持多项式之间的乘法，这是就需要通过配对函数解决。
如果以下等式成立，则接受，否则拒绝
$$ e(C, g) = e(W, sg-zg) \cdot e(g, g)^{f(z)} $$
推导如下：
$$ \begin{align} & e(W, sg-zg) \cdot e(g, g)^{f(z)} \\ &= e(h(s) \cdot g, (s - z) \cdot g) \cdot e(g, g)^{f(z)} \\ &= e(\frac{f(s) - f(z)}{s - z} \cdot g, (s - z) \cdot g) \cdot e(g, g)^{f(z)} \\ &= e(g, g)^{f(s) - f(z)} \cdot e(g, g)^{f(z)} \\ &= e(f(s) \cdot g, g) \\ &= e(C, g) \end{align} $$
商多项式存在，等价于双线性映射成立。而商多项式存在的前提，是在 z 处多项式的值确实是 f(z)。
所以如果双线性映射验证成功，说明数据满足电路板（多项式），那么商多项式的承诺 $W$ 就不必打开了。
以上函数中，只有 $C$ 是未知的，需要 prover 发送过来，所以 $C$ 会被称为承诺。
双线性映射
$G_1, G_2$ 都是阶为 p 的循环群，映射 e: $G_1 \times G_1 \rightarrow G_2$
- $e(P + P', Q) = e(P, Q) \cdot e(P', Q)$
- $e(P, Q + Q') = e(P, Q) \cdot e(P, Q')$
双线性
对于任意 $a, b \in Z_p$ 和 $P, Q \in G_1$，有 $e(aP, bQ) = e(P, Q)^{ab}$
非退化性
存在 $P, Q \in G_1$ 使得 $e(P, Q) \neq 1_{G_2}$，$1_{G_2}$ 是 $G_2$ 的单位元
- 可计算性
存在有效的算法对任意的 $P, Q \in G_1$，计算 e(P, Q) 的值
KZG 批量验证 A
t 个多项式，打开 1 个随机点
初始化
双线性群为 $T = (e, G_1, G_2, G_T)$，随机数秘密数 $s \in Z_p^*$，$d+2$ 元组 $<g_1, sg_1, s^{d-1}g_1; g_2, sg_2>$，令输出为
$$ PK = (T, g_1, sg_1, s^{d-1}g_1; g_2, sg_2) $$
承诺
对 t 个多项式 $f_i(x) = \sum^n_{j=0}a_{i,j}x^j$ 分别计算 t 个多项式承诺
$$ C_i = f_i(s)g_1 = \sum^n_{j=0}a_{i,j} \cdot s^jg_1 $$
会得到 t 个椭圆曲线离散对数点
打开承诺
基于上述多项式与承诺，根据 transcript 算出随机数 $\gamma$ ，计算商多项式
$$ h_z(x) = \sum^t_{i=1}\gamma^{i-1} \cdot \frac{f_i(x) - f_i(z)}{x-z} $$
计算商多项式承诺
$$ W_z = h_z(s) \cdot g_1 $$
输出 $(z, f_i(z)， W_z)$
验证随机点
基于上述多项式与承诺，根据 transcript 算出随机数 $\gamma$ 。分别算出 t 个承诺 $C_i$ 和函数值承诺的累加值。
$$ \begin{align} & F = \sum^t_{i=1}\gamma^{i-1}C_i = \sum^t_{i=1}\gamma^{i-1}f_i(s) \cdot g_1 \\ & V = \sum^t_{i=1}\gamma^{i-1}f_i(z) \cdot g_1 \end{align} $$
如果以下等式成立，则接受
$$ e(F - V, g_2) \cdot e(-W_z, sg_2 - zg_2) = 1 $$
公式推导：
$$ \begin{align} & e(F-V, g_2) \cdot e(-W, sg_2-zg_2) \\ & = e(\sum^t_{i=1}\gamma^{i-1} \cdot (f_i(s) - f_i(z)) \cdot g_1, g_2) \cdot e(-h_z(s) \cdot g_1, (s-z)g_2) \\ & = e(g_1, g_2)^{\sum^t_{i=1}\gamma^{i-1} \cdot (f_i(s) - f_i(z))} \cdot e(g_1, g_2)^{-h_z(s)(s-z)} \\ & = e(g_1, g_2)^{\sum^t_{i=1}\gamma^{i-1} \cdot (f_i(s) - f_i(z))} \cdot e(g_1, g_2)^{-\sum^t_{i=1}\gamma^{i-1} \cdot \frac{(f_i(s) - f_i(z))}{s-z}(s-z)} \\ & = 1 \end{align} $$
KZG 批量验证 B
t 个多项式，打开 2 个随机点
以下是 KZG 承诺在不同横坐标 $z_1, z_2$ 上的批量验证。
承诺
对 $t_1$ 个多项式 $f_i(x) = \sum_{j=0}^na_{i, j} \cdot x^j$，计算 $t_1$ 个承诺：
$$ C_i = f_i(s)g_1 = \sum_{j=0}^na_{i, j} \cdot s^jg_1 $$
对于对 $t_2$ 个多项式 $f'_i(x) = \sum_{j=0}^na'_{i, j} \cdot x^j$，计算 $t_2$ 个承诺：
$$ C'_i = f'_i(s)g_1 = \sum_{j=0}^na'_{i, j} \cdot s^jg_1 $$
打开 2 个随机点
基于上述多项式与承诺，根据 transcript 计算 2 个随机数 $\gamma, \gamma'$。计算商多项式
$$ \begin{align} & h_z(x) = \sum^t_{i=1}\gamma^{i-1} \cdot \frac{f_i(x) - f_i(z_1)}{x-z_1} \\ & h_z'(x) = \sum^t_{i=1}\gamma'^{i-1} \cdot \frac{f_i'(x) - f_i'(z_2)}{x-z_2} \end{align} $$
计算 2 个商多项式承诺
$$ \begin{align} & W_{z_1} = h_{z}(s) \cdot g_1 \\ & W_{z_2} = h'_{z}(s) \cdot g_1 \\ \end{align} $$
输出 $(z_1, f_i(z_1), W_{z_1}); (z_2, f'_i(z_2), W_{z_2})$
验证 2 个随机点
基于上述多项式与承诺，根据 transcript 计算 2 个随机数 $\gamma, \gamma'$。选择随机数 $r \in Z_P^*$，分别计算 $t_1, t_2$ 个承诺和函数值承诺的累加值
$$ \begin{align} & F_1 = \sum^{t_1}_{i=1}\gamma^{i-1}C_i = \sum^{t_1}_{i=1}\gamma^{i-1}f_i(s) \cdot g_1 \\ & F_2 = \sum^{t_2}_{i=1}\gamma^{i-1}C_i = \sum^{t_2}_{i=1}\gamma'^{i-1}f'_i(s) \cdot g_1 \\ & V_1 = \sum^{t_1}_{i=1}\gamma^{i-1}f_i(z_1) \cdot g_1 \\ & V_2 = \sum^{t_2}_{i=1}\gamma^{i-1}f'_i(z_2) \cdot g_1 \\ & F = F_1 - V_1 + r \cdot (F_2 - V_2) \end{align} $$
如果以下等式成立，则接受，否则拒绝
$$ e(F + z_1 \cdot W_{z_1} + rz_2 \cdot W_{z_2}, \space g_2) \cdot e(-W_{z_1} - r \cdot W_{z_2}, \space s \cdot g_2) = 1 $$
公式推导：
$$ \begin{align} & e(F + z_1 \cdot W_{z_1} + rz_2 \cdot W_{z_2}, \space g_2) \\ & = e(F_1 - V_1 + r \cdot (F_2 - V_2) + z_1 \cdot W_{z_1} + rz_2 \cdot W_{z_2}, \space g_2) \\ &= e(( \sum^{t_1}_{i=1}\gamma^{i-1} \cdot (f_i(s) - f_i(z_1)) + r \sum^{t_2}_{i=1}\gamma'^{i-1} \cdot (f'_i(s) - f'_i(z_2)) + z_1h_{z1}(s) + rz_2h'_{z_2}(s)) \cdot g_1, \space g_2) \\ & = e(g_1, g_2)^{\sum^{t_1}_{i=1}\gamma^{i-1} \cdot (f_i(s) - f_i(z_1)) + r \sum^{t_2}_{i=1}\gamma'^{i-1} \cdot (f'_i(s) - f'_i(z_2)) + z_1h_{z1}(s) + rz_2h'_{z_2}(s)} \\ &\\ & e(-W_{z_1} - r \cdot W_{z_2}, \space s \cdot g_2) \\ & = e((-h_{z1}(s) - rh'_{z_2}(s)) \cdot g_1, \space s \cdot g_2) \\ & = e(g_1, g_2)^{-(h_{z1}(s) + rh'_{z_2}(s)) \cdot s} \\ &\\ & \sum^{t_1}_{i=1}\gamma^{i-1} \cdot (f_i(s) - f_i(z_1)) + r \sum^{t_2}_{i=1}\gamma'^{i-1} \cdot (f'_i(s) - f'_i(z_2)) + z_1h_{z1}(s) + rz_2h'_{z_2}(s) \\ & -(h_{z_1}(s) + rh'_{z_2}(s)) \cdot s \\ & = \sum^{t_1}_{i=1}\gamma^{i-1} \cdot (f_i(s) - f_i(z_1)) + r \sum^{t_2}_{i=1}\gamma'^{i-1} \cdot (f'_i(s) - f'_i(z_2)) - (s-z_1)h_{z_1}(s) - r(s-z_2)h'_{z_2}(s) \\ & = (\sum^{t_1}_{i=1}\gamma^{i-1} \cdot (f_i(s) - f_i(z_1)) - (s-z_1)h_{z_1}(s)) + (r \sum^{t_2}_{i=1}\gamma'^{i-1} \cdot (f'_i(s) - f'_i(z_2)) - r(s-z_2)h'_{z_2}(s) )\\ & = 0 + 0 \\ & = 0 \end{align} $$
KZG 承诺缺点：验证复杂度与打开点数相关。打开点数越多，倍点运算越多。可通过 Fflonk 把多个多项式单点打开等价转换为 1 个多项式多点打开。
Dan Boneh 承诺：验证复杂度仅与多项式个数相关，与随机打开点数无关。
没有评论