EIP-1895: 支持椭圆曲线循环
| Authors | Alexandre Belling <alexandrebelling8@gmail.com> |
|---|---|
| Created | 2018-03-31 |
| Discussion Link | https://ethresear.ch/t/reducing-the-verification-cost-of-a-snark-through-hierarchical-aggregation/5128 |
简单总结
由于预编译 ecadd 和 ecmul 以及 ecpairing，EVM 当前支持曲线 alt-bn128 的椭圆曲线运算。MNT4 和 6 类包含曲线循环。这些循环使得可以在另一个曲线上的 SNARK 中对一个曲线进行运算（反之亦然）。这个 EIP 建议增加对这些曲线的支持。
摘要
通过预编译添加对以下操作的支持：
- MNT4 上的
ecadd - MNT4 上的
ecmul - MNT4 上的
ecpairing
动机
椭圆曲线是递归 SNARKs 的基本构建块（即：在一个 SNARK 内部验证一个 SNARK），这解决了可扩展零知识的问题。更普遍地说，这部分解决了可扩展性问题，因为 SNARKs 验证在被验证电路的大小上是恒定时间的。
更具体地说，今天如果 EVM 必须处理 1000 多个 SNARK 验证，则需要大约 15 亿 gas，这对于以太坊来说是不切实际的。例如，递归 SNARK 使得可以将多个证明聚合到单个证明中，该证明可以像任何其他 SNARK 一样进行验证。这导致验证成本的大幅降低。
然而，使用 alt-bn128 这是不可能的，据我所知，已知产生循环的唯一配对友好曲线族是 MNT4 和 MNT6。在 配对友好椭圆曲线的循环 中提出了这两个家族之间存在的循环的完整特征。
规范
曲线
所提出的循环已在 通过椭圆曲线循环实现可扩展的零知识 中介绍。
MNT4 定义
群 G_1 和 G_2 是素数阶的循环群：
q = 475922286169261325753349249653048451545124878552823515553267735739164647307408490559963137
G_1 定义在素数阶的域 F_p 上：
p = 475922286169261325753349249653048451545124879242694725395555128576210262817955800483758081
带有生成器 P：
P = (
60760244141852568949126569781626075788424196370144486719385562369396875346601926534016838,
363732850702582978263902770815145784459747722357071843971107674179038674942891694705904306
)
p 和 q 都可以用 298 位表示。
群 G_1 定义在由方程 Y² = X³ + aX + b 定义的曲线上，其中：
a = 2
b = 423894536526684178289416011533888240029318103673896002803341544124054745019340795360841685
扭曲群 G_2 定义在域 F_p^2 = F_p / <<待完成>> 上
扭曲群 G_2 定义在由方程 Y² = X² + aX + b 定义的曲线上，其中：
a = 34 + i * 0
b = 0 + i * 67372828414711144619833451280373307321534573815811166723479321465776723059456513877937430
G_2 生成器由以下生成：
P2 = (
438374926219350099854919100077809681842783509163790991847867546339851681564223481322252708 +
i * 37620953615500480110935514360923278605464476459712393277679280819942849043649216370485641,
37437409008528968268352521034936931842973546441370663118543015118291998305624025037512482 +
i * 424621479598893882672393190337420680597584695892317197646113820787463109735345923009077489
)
操作和 gas 成本
将实现以下操作及其 gas 成本
MNT_X_ADD = <<待评估>>
MNT_X_MUL = <<待评估>>
MNT_X_PAIRING = <<待评估>>
其中 X 为 4。
编码
F_p 上的曲线点 P(X, Y) 以其压缩形式 C(X, Y) 表示：
C = X | s
其中 s 如下表示 Y：
| `s'` | `Y` |
|--------|--------------------------|
| `0x00` | 无穷远点 |
| `0x02` | `y` 为偶数的解 |
| `0x03` | `y` 为奇数的解 |
从仿射坐标的压缩操作是微不足道的：
s = 0x02 | (s & 0x01)
在 EVM 中，压缩形式允许我们用 2 个 uint256 而不是 3 个来表示曲线点。
边缘情况
- 无穷远点的几种可接受的表示形式
理由
该曲线具有 80 位的安全性（而 MNT6 具有 120 位），这可能被认为对于关键安全级别（例如转移数十亿）来说不够，但对于其他级别来说足够。如果事实证明对于采用来说安全性不够，则还有另一种选择：Coda 正在使用另一个循环，但它定义在 753 位大小的字段上，这也可能高得令人望而却步（未找到 Coda 出版物中对该曲线的引用）。
独立于选择的循环，组和字段元素都用大于 256 位的整数表示（即使对于 80 位的安全性），因此可能还需要添加对更大字段大小操作的支持。
我们目前不知道更有效的配对友好循环，也不知道是否存在。但是，通过放宽循环的所有曲线必须都是配对友好的曲线的约束，有可能规避这个问题。如果我们有一个只有一条配对友好曲线的循环，我们仍然可以通过在 SNARK 和任何其他通用零知识密码系统之间交替来组合证明。
假设我们找到了一个方便的循环，我们不需要实现对其包含的所有曲线的支持，只需一个即可。最好的选择是最快的，因为递归 snark 的整体安全性不取决于进行验证的曲线。
将进行适当的基准测试，以便做出此选择并以 gas 定价操作。
测试用例
参考文献
- Eli-Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza, [BCTV14], April 28, 2015, 通过椭圆曲线循环实现可扩展的零知识: https://eprint.iacr.org/2014/595.pdf
- Alessandro Chiesa, Lynn Chua, Matthew Weidner, [CCW18], November 5, 2018, 关于配对友好椭圆曲线的循环: https://arxiv.org/pdf/1803.02067.pdf
实现
版权
版权及相关权利通过 CC0 放弃。
Citation
Please cite this document as:
Alexandre Belling <alexandrebelling8@gmail.com>, "EIP-1895: 支持椭圆曲线循环 [DRAFT]," Ethereum Improvement Proposals, no. 1895, March 2018. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-1895.