Plonky方案

2021-04-23 本文已影响0人雪落无留痕

通过利用Plonk的置换，Halo的多项式承诺，和多参数的电路模型，Plonky能够实现 $2^{14}$ 量级的递归证明，代码库为plonky, 目前开发尚不完善。理解本文内容需要
Plonk, Halo和Rescue的知识背景。

Plonk优化

多项式承诺

设定 $\mathbb{F}$ 为素数阶域， $\mathbb{G}$ 为阶为 $\left|\mathbb{F}\right|$ , $\mathbf{G} \colon \mathbb{G}^d$ 是一组随机群元素。

若对次数为 $d$ 的多项式 $f_1, \cdots, f_n$ 承诺，可以把多项式当作一个系数向量，每个 $f_i$ 可以看作 $\mathbb{F}$ 上的一组长度为 $d+1$ 的向量，定义：

$\mathbf{pows}(x) := (1, x, x^2, x^3, \dots, x^d)$
则 $< f_i, {pows(\alpha)}>=f_i(\alpha)$ .

定义 $[f_i]:=<f_i, \mathbf{G}>$ ， $[f_i]$ 为多项式 $f_i$ 的承诺。在Bulletproofs中，对于 $f_i(\alpha)=\beta$ , 需要在承诺 $[f_i]$ 条件下证明 $<f_i, {pows}(\alpha)>=\beta$ .

对于 $\alpha_1:\mathbb{F}$ 和 $f_i(\alpha_1)=\beta_{i,1}$ , 可以通过随便值 $\xi$ 证明 $f_i(\alpha_1)=\beta_{i,1}$ , 即证明 $(\sum_i\xi^i f_i)(\alpha_1)=\sum_i\xi^i\beta_{i,1}$ 。

由此可以将多个多项式在多个点的承诺转换为一个多项式在单点的承诺。假如要证明所有的多项式 $f_i$ 在多点 $\alpha_1, \cdots, \alpha_n$ 的值，即证明 $f_i(\alpha_j)=\beta_{i,j}$ 。

随机选取 $\xi$ , 定义 $F:=\sum_i\xi^if_i$ ，随机选取 $r: \mathbb{F}$ , 令 $F_j:=\sum_i\xi^i\beta_{i,j}$ ， $F_j=F(\alpha_j)$ , 可以利用内积证明 $<F, \sum_jr^j{pows(\alpha_j)}>=\sum_jr^jF_j$ 。

批量多项式承诺

设 $G$ 是一系列随机的群元素， $X=(x^0, x^1, x^2,\cdots)$ ， $Y=(y^0, y^1,y^2,\cdots)$ 。证明者首先发送每个多项式的承诺 $c(f_i)=<f_i, G>$ , 并且值为 $z_i=<f_i, X>, w_i=<f_i, Y>$ 。验证者随机选取 $\alpha, \beta\in \mathbb{F}$ ，并计算：
$Z=\sum_i\alpha^iz_i \\ W=\sum_i\alpha^iw_i \\ c(F)=\sum_i\alpha^ic(f_i)$
其中 $F=\sum_i\alpha^if_i$ . 证明者需要证明 $F(x)=Z, F(y)=W$ ，即归为内积的形式：
$<F, X+\beta Y>=Z+\beta W$
验证过程需要计算 $<s, G>$ 和 $<s, X+\beta Y>$ , 其中 $s$ 由Halo中定义，需要采用Halo中的技术。

Halo中点乘的瓶颈

在Halo中，验证多项式承诺涉及到计算：
$Q=\sum_{j=1}^k([u_j^2]L_j)+P'+\sum_{j=1}^k([u_j^{-2}]R_j)$
其中 $L_j$ 和 $R_j$ 由证明者发送， $u_j\in \{0,1\}^\lambda$ 为随机挑战值。

点乘通过 $[r]P$ 通过 "double-and-add"方法计算，汲及 $\lambda$ 次点加和 $\lambda$ 次倍点运算。 Halo通过自同态技术将其约减为 $\lambda/2$ 次加法和 $\lambda/2$ 次倍点运算。

Plonky通过MSM 技术优化，约减为 $(k+1/2)\lambda$ 次群操作。

广义Plonk电路模型

Plonk标准电路模型为：
$q_La+q_Rb+q_Oc+q_Mab+q_C=0$
其中 $q$ 为电路的相关配置， $a, b, c$ 为用户输入值。

Plonk电路简单，但会导致很多的电路门数，例如椭圆曲线点运算需要7个门电路。可以优化Plonk电路，减少电路门数。

（1）可以采用多参数(high-arity) 门电路，若想要一个门电路执行椭圆曲线操作，需要6个参数，但这会增加证明者的计算代价；

（2）可以增加约束，而非仅局限于一种，但这会要求证明者做更多的FFT运算；

（3）在Routed wire的基础上，增加Advice wire, 用来作为中间变量的值，减少Plonk中置换多项式的次数。

（4）添加移位的点 $gx$ , 使当前门电路关联后续更多电路，减少复制约束。

椭圆曲线门电路

在MSM优化算法中，主要涉及点逆运算，自同态 $\phi((x,y))=(\zeta x, y)$ , 点加运算，可以表示为：
$\begin{aligned} x_1 & \leftarrow (1 + (\zeta - 1) r_\mathrm{high}) x, \\ y_1 &\leftarrow (2 r_\mathrm{low} - 1) y, \\ (x_3, y_3) & \leftarrow (x_1, y_1) + (x_2, y_2), \end{aligned}$
其中 $(x,y)$ 是要乘的点， $r_\mathrm{high}, r_\mathrm{low}$ 为标量两个连续的bit， $(x_2,y_2)$ 要加的点， $(x_3,y_3)$ 是点加的结果。

对于Weierstrass形式曲线，加法公式为：
$\begin{aligned} inv & = 1/(x_1-x_2) \\ \lambda & = (y_1-y_2)inv \\ x_3 & = \lambda^2-x_1-x_2 \\ y_3 & = \lambda(x_1-x_3)-y_1 \end{aligned}$
可以引入 advice wire处理像 $\lambda$ 类似的中间变量，门电路定义形式如下：

Routed wires: $x, y, x_2, y_2, x_3, y_3, r_\mathrm{low}, r_\mathrm{high}$
Advice wires: $x_1,y_1, inv, \lambda$
约束条件为：
$\begin{aligned} r_\mathrm{low} (r_\mathrm{low} - 1) &= 0, \\ r_\mathrm{high} (r_\mathrm{high} - 1) &= 0, \\ x_1 &= (1 + (\zeta - 1) r_\mathrm{high}) x, \\ y_1 &= (2 r_\mathrm{low} - 1) y, \\ (x_1 - x_2) \mathrm{inv} &= 1, \\ \lambda &= (y_1 - y_2) \mathrm{inv}, \\ x_3 &= \lambda^2 - x_1 - x_2, \\ y_3 &= \lambda(x_1 - x_3) - y_1. \end{aligned}$
Plonky实际实现只用一个门电路实现椭圆曲线运算。

Rescue

设定 $M = \bigl( \begin{smallmatrix}A & B \\ C & D\end{smallmatrix}\bigr)$ 为Rescue中MDS矩阵，一个宽度为2的Rescue置换定义如下：
$\begin{aligned} \operatorname{step}_{i,1}\left(\begin{bmatrix}x_1 \\ x_2\end{bmatrix}\right) &= M \begin{bmatrix}x_1^{1/\alpha} \\ x_2^{1/\alpha}\end{bmatrix} + \begin{bmatrix}r_{i,1} \\ r_{i,2}\end{bmatrix}, \\ \operatorname{step}_{i,2}\left(\begin{bmatrix}x_1 \\ x_2\end{bmatrix}\right) &= M \begin{bmatrix}x_1^{\alpha} \\ x_2^{\alpha}\end{bmatrix} + \begin{bmatrix}r_{i,3} \\ r_{i,4}\end{bmatrix}, \\ \operatorname{round}_i &= \operatorname{step}_{i,2} \circ \operatorname{step}_{i,1}, \end{aligned}$
其中 $r_{i,1}\cdots r_{i,4}$ 为轮变换常量。

计算 $\alpha th$ 计算代码比较大，需要证明者提供 advice wire $y_1, y_2$ . $z_1, z_2$ 表示轮函数的输出，最终门电路定义如下：

Routed wires: $x_1,x_2, z_2, z_2$
Advice wires: $y_1, y_2$
Constants:
$\begin{aligned} x_1 & = y_1^\alpha, \\ x_2 & = y_2^\alpha, \\ z_1 & = A(Ay_1+By_2+r_{i,1})^\alpha+B(Cy_1+Dy_2+r_{i,2})^\alpha+r_{i,3}, \\ z_2 & = C(Ay_1+By_2+r_{i,1})^\alpha+D(Cy_1+Dy_2+r_{i,2})^\alpha+r_{i,4} \end{aligned}$

Plonky甚至可以在一个门电路执行多轮Rescue置换，实际中受每个门电路中常量的限制。Rescue一轮中有4个常量： $r_{i,1}\cdots r_{i,4}$ ，添加更多常量意味着处理更多的多项式。作为后期优化，可以把Rescue门电路和其它不需要常量的电路放在一起，例如椭圆曲线操作。或者对其进行更改，使它不需要那么多常量配置。

约束集

Plonk 只使用了一种约束，Plonky可以使用多种约束集，使用各种不同的定制门电路，并将其组织成二叉树的形式，如下所示：

未来优化

Plonky后续将持续优化，全面提升算法性能。

零知识证明特性

Plonk论文中对零知识证明特性缺少证明，plonky可以展示其零知识证明属性，并描述另一种适合Halo多项式承诺风格的盲化方法。

基础定义

对于 $S\subseteq [1\cdots H]$ , 定义多项式 $L_S(x)\in \mathbb{F}_{<|H|}[x]$ 为：
$L_S(g^i) = \begin{cases} 1 & \text{if } i \in S, \\ 0 & \text{otherwise}, \end{cases}$
或者等价表示为：
$L_S(x)=\sum_{i\in S}L_i(x)$
其中 $L_i(x)$ 为Plonk中定义的Lagrange 基。

Plonk盲化方案

设 $s(x)\in \mathbb{F}_{<d}[x]$ 为witess多项式， $C=\{c_1, \cdots, c_k\}$ 为挑战点的值，且 $C\subseteq \mathbb{F}$ .

设 $b(x)$ 为盲化多项式，从 $\mathbb{F}_{<k}[x]$ 中随机选择，Plonk中重新定义：
$s'(x) = s(x) + b(x) Z_H(x).$
$s$ 和 $s'$ 在 $H$ 定义一致，因此可以用 $s'$ 替换 $s$ 。

当 $c_i\in H$ , $s'(c_i)= s(c_i)$ , 导致信息泄露。为了实现零知识证明特性，需要选择 $\mathbb{C}\subseteq \mathbb{F} \setminus H$ 。若 $c_i \notin H$ , 可知 $Z_H(c_i)=0$ , 可以得到：
$b(c_i)=\frac{s'(c_i)-s(c_i)}{Z_H(c_i)}$
对于秘密多项式 $s$ ， $(s'(c_1), \cdots, s'(c_2))$ 不会泄露 $s$ 的任何信息。

Halo盲化

上述盲化不适合于Halo中的多项式承诺，因为 $deg(s')=|H|+deg(b)$ 超过了2的幂次方法次数。

Plonky采用Lagrange基的形式盲化witness多项式，则盲化多项式 $s'$ 定义如下:
$s'(x)=s(x)+b(x)L_{[d+1\cdots d+k]}(x)$
由于 $L_{[d+1\cdots d+k]}$ 的次数为 $|H|-1$ ，至多有 $|H|-1$ 个根。因此可以选择不包括根元素的集合 $\mathbb{C}$ , 对于 $c_i \in C$ ，可以得到：
$b(c_i)=\frac{s'(c_i)-s(c_i)}{L_{[d+1\cdots d+k]}(c_i)}$
对于 $(s'(c_1),\cdots, s'(c_k))$ 不会泄露 $s$ 的信息。

盲化 $Z$

Plonk 涉及置换多项式 $Z$ ，即 $Z(a)f'(a)=g'(a)Z(ag)$ , 若直接给出 $Z$ 的值，将会泄露witness的信息，

<strong> Lemma 1.</strong> 若限制 $\sigma$ 为 $[1 \cdots \ i-1]$ 上的置换，则 $Z(g^i)=1$ ;

<strong>Lemma 2. </strong> 对于 $i\notin \{d+4, d+6\}, Z(g^i)=Z'(g^i)$

在 $H$ 的其它点上 $Z'(g^i)=Z(g^i)$ , 可以将 $Z'$ 写作：
$Z'(x)=Z(x)+L_{d+4, d+6}(x)(m(x)-1)$
$m$ 为 $\mathbb{F}_{<2}[x]$ 上的多项式, 满足：
$m(g^{d+4}) = \frac{b_1 + \beta (d + 3) + \gamma}{b_1 + \beta (d + 4) + \gamma},$