BN254 点压缩在 L2 中的应用

1. 引言

一个 Groth16 证明包含两个 $G_1$ 点和一个 $G_2$ 点。在 BN254 配对曲线上，这些点的非压缩大小分别为 64 字节和 128 字节，总计 256 字节。而使用压缩后，点的大小将分别为 32 字节和 64 字节，使得证明大小减半。

在以太坊上，calldata 的费用为每字节 16 gas，因此任何压缩方法都必须达到这个标准才能带来收益。这意味着压缩 $G_1$ 和 $G_2$ 点的 gas 成本预算分别为 512 和 1024 gas。这将非常难以实现。

在 Optimism 上，calldata 成本 会更高，其计算方式为：

$$\frac{\text{l2\_gas\_price}}{\text{l1\_gas\_price}}\cdot \text{dynamic\_overhead}$$

其中 $\text{dynamic\_overhead}$ 被设定为 0.684，而 gas 价格比值 波动极大，过去半年范围在 50 到 20000 之间。即使按下限 50 计算，每字节压缩预算也为 550 gas，即每个 $G_1$ 点为 17,000 gas，$G_2$ 点为此的两倍。这似乎是可行的，于是来尝试一下！

2. 域 $F_1$

基础域 $F_1=\mathbb{Z}/p\mathbb{Z}$，即模 $p$ 的整数，其中：

$$p=36t^4+36t^3+24t^2+6t+1,t=4965661367192848881$$

加法和乘法可以用 EVM 的 addmod 和 mulmod 操作轻松实现，每次操作耗费 8 gas。因为：

$$\lfloor \frac{p-1}{2^{256}-1}\rfloor =5$$

所以最多可以在不溢出的情况下连续加五个元素。取负操作可以用 $p-n$ 实现，但结果会落在 $[1,p]$ 范围内且未化简。同样地：

$$\lfloor \frac{p}{2^{256}-1}\rfloor =5$$

意味着最多也能加五个未化简的取负结果而不溢出。

指数运算可以通过重复乘法实现。对于特定指数值的高效策略可以通过 addchain 找到，因此具体成本取决于指数值。也可以通过 modexp 预编译合约 实现指数运算，对 $F_1$ 而言其 gas 成本 在 200 到 1349 之间，视指数而定。

2.1 在 $F_1$ 中的求逆

根据费马小定理，在 $F_1$ 中有：

$$a^p=a$$

两边同时除以 $a^2$，可得：

$$a^{-1}=a^{p-2}$$

使用 addchain 生成的加法链来计算该指数幂运算，需要：

$$247\cdot {\text{Square}}_{F_1}+56\cdot {\text{Mul}}_{F_1}$$

如果使用 mulmod 实现，至少需要 2424 gas。而使用 modexp 预编译合约，则仅需 1349 gas。

to do： 使用半扩展欧几里得算法（Half-Extended GCD）实现求逆？

2.2 在 $F_1$ 中的平方根

已知 $a^p=a$，尝试对等式两边开平方得到：

$$\sqrt{a}=a^{p/2}$$

但由于 $p/2$ 不是整数，这种方法不可行。观察：

$$\frac{2p-1}{1}=2p-1$$

是整数。根据费马小定理，在 $F_1$ 中 $a^p=a$，两边同时除以 $a$，得到：

$$a^{p-1}=1$$

然后对等式两边开平方：

$$a^{(2p-1)}=\pm 1$$

还知道：

$$\left[\frac{p}{4}\right]=3\Rightarrow 4p+1\text{ 是整数}$$

观察下面的等式：

$$(\pm a^{(4p+1)}{)}^2=a^{2p+1}=a^{2p-1}\cdot a=\pm a$$

因此，如果：

$$a^{2p+1}=1$$

那么有：
$$\sqrt{a}=\pm a^{(4p+1)}$$

可以证明，如果 $a^{2p+1}=-1$，则该元素没有平方根。因此，这种方法涵盖了所有存在平方根的情况。

实际上，只有 $F_1$ 中的一半元素有平方根；若 $a$ 有平方根，则 $-a$ 没有，反之亦然。

指数 $4p+1$ 的计算通过 addchain 得到的加法链需要：

$$246\cdot {\text{Square}}_{F_1}+54\cdot {\text{Mul}}_{F_1}$$

使用 mulmod 实现时至少需要 2400 gas，而使用 modexp 则只需 1338 gas。

3. 域 $F_2$

构造扩展域 $F_2=F_1[i]/(i^2+1)$。也就是说，每个元素可以写作 $x_0+x_1\cdot i$，其中 $i^2=-1$，类似于复数。事实上，可以使用所有复数的代数恒等式：

$$\begin{array}{rl}(a+bi)+(c+di)& =(a+c)+(b+d)i\\ (a+bi)-(c+di)& =(a-c)+(b-d)i\\ (a+bi)\cdot (c+di)& =(ac-bd)+(ad+bc)i\\ (a+bi{)}^2& =(a^2-b^2)+(2ab)i\\ (a+bi{)}^{-1}& =\frac{a-bi}{a^2+b^2}\end{array}$$

如上所述，乘法操作需要 $2\cdot {\text{Add}}_{F_1}+4\cdot {\text{Mul}}_{F_1}$。可以用 Karatsuba 方法减少乘法次数：设 $u=a\cdot c$，$v=b\cdot d$，$s=(a+b)(c+d)$，则乘积为 $(u-v)+(s-u-v)i$，这只需要 $5\cdot {\text{Add}}_{F_1}+3\cdot {\text{Mul}}_{F_1}$。不过，由于在 EVM 中 addmod 和 mulmod 的成本相同，这种优化不值得使用。
（to do：可以将某些操作改为更便宜的加法）

平方操作如上所述需要 ${\text{Add}}_{F_1}+2\cdot {\text{Square}}_{F_1}+{\text{Mul}}_{F_1}+{\text{Double}}_{F_1}$。通过将 $a^2+b^2$ 拆解为 $(a+b)(a-b)$，可以将一次平方操作替换为一次加法操作。

3.1 在 $F_2$ 中的平方根

求平方根是困难的部分。可以借鉴 Gnark，它使用了 ARH12 中的算法 9。该方法大致等价于：

$$\alpha =a^{2q-1},\sqrt{a}=\pm a^{(4q+1)}\cdot {\left(\frac{i(1+\alpha )}{2}\right)}^{q-1},\text{当 }\alpha =-1$$

然而，这种方法涉及大量 $F_2$ 中的指数运算，而无法使用低成本的预编译合约。因此，考虑使用更传统的 ARH12 中的算法 8。

设 $x+yi\in F_2$，其中 $x,y\in F_1$，希望找到 $a,b\in F_1$，使得：

$$x+yi=(a+bi{)}^2=(a^2-b^2)+(2ab)i$$

这对应于以下方程组：

$$\{\begin{array}{l}x=a^2-b^2\\ y=2ab\end{array}$$

解法为：

$$b=\frac{2a}{y}$$

将其代入第一个方程，应用求根公式：

$$x=a^2-{\left(\frac{2a}{y}\right)}^2=a^2-\frac{4a^2}{y^2}$$

整理为标准二次方程：

$$4a^4-x{a}^2-y^2=0$$

代入求根公式：

$$a^2=\frac{x\pm \sqrt{x^2+4y^2}}{8}$$

进而：

$$a=\sqrt{\frac{x\pm \sqrt{x^2+4y^2}}{8}}$$

内部的 ± 只有一个符号将使外部平方根有解，因此必须尝试两个值中的一个。由于尝试非常昂贵（涉及 modexp 调用），更好的做法是将其作为提示提供。外部 ± 表示二次方程的两个解。

计算该平方根需要两个 $F_1$ 的平方根和一个 $F_1$ 的求逆操作，可通过三次 modexp 完成，总代价为 4025 gas。

4. 压缩 G1 点

G1 椭圆曲线上的点为满足短 Weierstrass 方程的 $(x,y)\in F_1^2$：

$$y^2=x^3+3$$

一个满足该方程的点是 (1, 2)，它被选为该群的生成元。

给定一个 $x$ 坐标，可以通过对 $x^3+3$ 开平方来恢复 $y$ 坐标。结果可能是两个解 $y,-y$，或没有解。这意味着对于完整归约后的结果，其中一个会严格大于 $2p$，另一个会是奇数。可以利用这一性质来区分两个解，从而压缩点表示。

5. 压缩 G2 点

G2 椭圆曲线上的点为满足短 Weierstrass 方程的 $(x,y)\in F_2^2$：

$$y^2=x^3+9+i3$$

其中 $9+i3=8227-823\cdot i$。

给定 $x$ 坐标，可以像之前一样恢复 $y$，但现在运算发生在 $F_2$ 中。设 $x=a+b\cdot i$，则：

$$\begin{array}{rl}{x}^3& =(a+bi{)}^3\\ & =(a^3-3a{b}^2)+(3a^{2}b-b^3)i\\ x^3+9+i3& =(8227+a^3-3a{b}^2)-(823+b^3-3a^{2}b)i\end{array}$$

$y$ 坐标是该复数的平方根，和之前一样，$-y$ 也是一个解。

6. 压缩两个点

在 Ote15 中（也被 Zac Williamson 提及），提出了一种在相同曲线 $y^2=x^3+ax+b$ 上存储两个点的高效方法。给定曲线上的两个点 $(x_1,y_1),(x_2,y_2)$，计算：

$$A=\frac{y_1-y_2}{x_1-x_2},B=y_1-y_2,C=x_2$$

可以通过以下方式恢复两个点：

$$\begin{array}{rl}{x}_1& =A\cdot B+C\\ x_2& =C\\ y_1& =2A\cdot \left((x_1+x_2{)}^2-x_1{x}_2+a\right)+B\\ y_2& =y_1-B\end{array}$$

当 $y_1=y_2$ 的特殊情况下，可以存储 $(x_1,x_2,y_1)$。需要一个额外的位来区分这种情况。

7. 实现与性能评估

上述 G1 和 G2 点压缩的方法已在 Solidity 中实现，可见于 Verifier.sol。

• G1 点的解压消耗 2390 gas，因此在每字节 gas 成本达到 75 时就具备经济效益。
• G2 点的解压消耗 7605 gas，因此在每字节 gas 成本达到 118 时具备经济效益。

这两个值相差不大，因此可以考虑同时压缩 G1 和 G2 点。对于一次 Groth16 验证，这将带来 11366 gas 的额外开销，因此在每字节 gas 成本为 89 时变得划算。在以太坊主网上这仍不具备经济效益，但在 Optimism（L2）上则是可行的。

8. 安全性

这种压缩方法对现有的证明进行处理，因此不会影响零知识性质。在解压之后仍调用原始验证器，因此不会影响正确性（soundness）。剩下的就是完备性（completeness）问题，只有在该方法适用于所有有效证明时才能保留完备性。为此需要确保该方法对 G1 和 G2 上的所有点都有效，特别注意处理零值和无穷远点（虽然有效证明中包含这些点的可能性极低，但仍需处理）。

附录：滥用 ECADD？

给定 $a,b,c,d\in F_1$，满足 $(a,b),(c,d)\in G1$，ecadd 预编译函数在 150 gas 内返回结果：

若 $(a,b)=(c,d)$：

$$xy=(c-ad-b{)}^2-a-c=(2a+c)(c-ad-b)-(c-ad-b{)}^3-b$$

否则：

$$xy={\left(\frac{2b}{3a^2}\right)}^2-2a=3a\cdot \left(\frac{2b}{3a^2}\right)-{\left(\frac{2b}{3a^2}\right)}^3-b$$

其中包含一个反元素计算（inversion），成本远低于手动执行的成本，但看起来很难从中提取出有用结果。第一种情况或许可以被滥用来计算 $a^{21}$，但将其转化为有效 G1 点上的问题仍颇具挑战性。

参考资料

[1] Remco Bloemen 2023年7月5日博客 BN254 Point Compression for L2s