🚧 Stagnant Standards Track: ERC

ERC-2494: Baby Jubjub 椭圆曲线

Authors	Barry WhiteHat (@barryWhiteHat), Marta Bellés (@bellesmarta), Jordi Baylina (@jbaylina)
Created	2020-01-29
Discussion Link	https://ethereum-magicians.org/t/eip-2494-baby-jubjub-elliptic-curve/3968

简单总结
摘要
动机
规范
- 定义
- 阶
- 生成器点
- 基点
- 算术
理由
向后兼容性
- 曲线形式
- 点的转换
安全注意事项
测试用例
实现
版权

简单总结

本提案定义了 Baby Jubjub，一种设计用于在以太坊的 zk-SNARK 电路中工作的椭圆曲线。

摘要

区块链技术未被个人和行业广泛使用的两个主要问题是可扩展性和隐私保证。通过一组称为零知识证明 (ZKP) 的加密工具，可以解决这两个问题。更具体地说，最适合区块链的协议被称为 zk-SNARK（零知识简洁非交互式知识论证），因为它们是非交互式的，具有简洁的证明大小和亚线性验证时间。这些类型的协议允许证明可以使用在有限域（也称为 zk-SNARK 电路）上定义的算术电路建模的通用计算语句。

为了验证 zk-SNARK 证明，必须使用椭圆曲线。在以太坊中，该曲线是 alt_bn128（也称为 BN254），其主要阶数为 r。使用此曲线，可以生成和验证任何 F_r 算术电路的证明。此 EIP 描述了 Baby Jubjub，一个在有限域 F_r 上定义的椭圆曲线，可以在任何 zk-SNARK 电路中使用，从而允许实现使用椭圆曲线的加密原语，例如 Pedersen 哈希或 Edwards 数字签名算法 (EdDSA)。

动机

零知识证明 (ZKP) 是一种协议，它使一方（证明者）能够说服另一方（验证者）某个陈述是真实的，而不会泄露超出该陈述真实性的任何信息。非交互式 ZKP (NIZK) 是一种特殊的零知识证明，其中证明者可以生成证明而无需与验证者交互。NIZK 协议非常适合以太坊应用程序，因为它们允许智能合约充当验证者。这样，任何人都可以生成一个证明并将其作为交易的一部分发送到智能合约，智能合约可以根据证明是否有效来执行某些操作。在这种情况下，最受欢迎的 NIZK 是 zk-SNARK（零知识简洁非交互式知识论证），这是一组非交互式零知识协议，具有简洁的证明大小和亚线性验证时间。这些协议的重要性是双重的：一方面，它们有助于提高隐私保证，另一方面，它们是可扩展性问题的一种可能的解决方案（例如，参见 zk-Rollup 项目）。

像大多数 ZKP 一样，zk-SNARK 允许证明计算语句。例如，可以证明诸如以下内容：与某个公钥关联的私钥的知识、交易的正确计算或特定哈希的原像的知识。重要的是，可以做到这些事情，而不会泄露有关相关语句的任何信息。换句话说，不泄露有关私钥、交易详细信息或原像值的任何信息。更具体地说，zk-SNARK 允许证明可以使用 F_r 算术电路建模的任何计算语句，该电路由一组导线组成，这些导线携带来自域 F_r 的值并将它们连接到加法和乘法门 mod r。这种类型的电路通常称为 zk-SNARK 电路。

大多数 zk-SNARK 协议（例如 [Pinnochio] 和 [Groth16]）的实现使用椭圆曲线来验证证明。在以太坊中，使用的曲线是 alt_bn128（也称为 BN254），其主要阶数为 r。虽然可以使用 BN254 生成和验证 F_r 算术电路的证明，但无法使用 BN254 在这些电路中实现椭圆曲线密码学。为了在 zk-SNARK 电路中实现需要使用椭圆曲线的函数，例如 Pedersen Hash 或 Edwards Digital Signature Algorithm (EdDSA)，需要一条坐标在 F_r 中的新曲线。为此，我们在此 EIP 中提出了 Baby Jubjub，一个在 F_r 上定义的椭圆曲线，可以在任何 F_r 算术电路中使用。在接下来的部分中，我们将详细描述曲线的特征、它是如何生成的以及采取了哪些安全注意事项。

    inputs                zk-SNARK (alt_bn128)             output
            +--------------------------------------------+
            |   +--------------------+                   |
        --->|   | EdDSA (Baby Jubjub)|                   |
            |   +--------------------+                   |
        --->|                                            |--->
            |          +-----------------------------+   |
        --->|          | Pedersen Hash (Baby Jubjub) |   |
            |          +-----------------------------+   |
            +--------------------------------------------+

规范

定义

设 F_r 为具有 r 个元素的素数有限域，其中

r = 21888242871839275222246405745257275088548364400416034343698204186575808495617

设 E 为在 F_r 上定义的扭曲 Edwards 椭圆曲线，由以下公式描述

ax^2 + y^2 = 1 + dx^2y^2

参数为

a = 168700
d = 168696

我们称 Baby Jubjub 为曲线 E(F_r)，即 E 的 F_r 有理点的子群。

阶

Baby Jubjub 的阶为

n = 21888242871839275222246405745257275088614511777268538073601725287587578984328

它分解为

n = h x l

其中

h = 8
l = 2736030358979909402780800718157159386076813972158567259200215660948447373041

参数 h 称为 cofactor，l 是一个 251 位的素数。

生成器点

坐标为 G = (x,y) 的点

x = 995203441582195749578291179787384436505546430278305826713579947235728471134
y = 5472060717959818805561601436314318772137091100104008585924551046643952123905

生成曲线的所有 n 个点。

基点

坐标为 B = (x,y) 的点

x = 5299619240641551281634865583518297030282874472190772894086521144482721001553
y = 16950150798460657717958625567821834550301663161624707787222815936182638968203

生成 Baby Jubjub 的点的子群 P，满足 l * P = O。也就是说，它生成阶数为 l 且原点为 O 的点的集合。

算术

设 P1 = (x1, y1) 和 P2 = (x2, y2) 为 Baby Jubjub 的两个任意点。那么 P1 + P2 = (x3, y3) 的计算方式如下：

x3 = (x1*y2 + y1*x2)/(1 + d*x1*x2*y1*y2)
y3 = (y1*y2 - a*x1*x2)/(1 - d*x1*x2*y1*y2)

请注意，可以使用单个公式计算点的加法和倍加。

理由

寻找 Baby Jubjub 的动机是需要一种允许在 F_r 算术电路中实现椭圆曲线密码学的椭圆曲线。曲线的选择基于三个主要因素：曲线类型、生成过程和安全标准。本节介绍如何解决这些因素。

曲线形式

Baby Jubjub 是一条与 Montgomery 曲线双向有理等价的 扭曲 Edwards 曲线。选择这种形式的曲线是基于以下事实：

Edwards 曲线数字签名方案基于扭曲 Edwards 曲线。
扭曲 Edwards 曲线对于点的加法有一个完整的公式，这使得在电路中实现群法则非常有效 [Crypto08/013, 第 6 节]。
由于扭曲 Edwards 曲线通常与 Montgomery 曲线双向有理等价 [Crypto08/13, 定理 3.2]，因此可以轻松地将曲线从一种形式转换为另一种形式。由于 Montgomery 曲线中点的加法和倍加可以非常有效地执行，因此可以使用这种形式更快地完成电路外的计算，并通过将其与扭曲 Edwards 形式相结合来加速电路内的计算（有关更多详细信息，请参见此处）。

曲线的生成

Baby Jubjub 被认为是需要椭圆曲线的密码方案的电路实现的解决方案。与任何密码协议一样，重要的是减少后门存在的可能性。因此，我们将生成过程设计为 透明的 和 确定性的 ―― 为了明确表示没有考虑外部因素，并确保该过程可以由任何希望这样做的人复制和遵循。

用于生成 Baby Jubjub 的算法基于 [RFC7748, 附录 A.1] 中定义的标准，可以在此 github 存储库中找到。本质上，该算法采用一个素数 p = 1 mod 4，并返回最低的 A>0，使得 A-2 是 4 的倍数，并且 y^2 = x^3 + Ax^2 + x 在 F_p 中的解集定义了一个余因子为 8 的 Montgomery 曲线。

Baby Jubjub 是通过使用素数运行算法生成的

r = 21888242871839275222246405745257275088548364400416034343698204186575808495617，

它是 alt_bn128 的阶数，alt_bn128 是用于在以太坊中验证 zk-SNARK 证明的曲线。该算法的输出为 A=168698。之后，相应的 Montgomery 曲线被转换为扭曲 Edwards 形式。使用 SAGE 曲线库，计算了曲线的阶数 n 及其因式分解 n = 8*l。

生成器的选择：生成器点 G 是 F_r 中具有最小正 x 坐标的阶数 n 的点。
基点的选择：选择基点 B 为 B = 8*G，其阶数为 l。

安全标准

至关重要的是，Baby Jubjub 能够安全地防御众所周知的攻击。为此，我们决定该曲线应通过 SafeCurves 安全测试，因为它们以收集针对椭圆曲线的最佳已知攻击而闻名。可以在此处找到 Baby Jubjub 满足 SafeCurves 标准的支持证据。

向后兼容性

Baby Jubjub 是一条双向有理于不同曲线的扭曲 Edwards 椭圆曲线。到目前为止，该曲线主要以其原始形式、Montomgery 形式和另一种（不同的表示形式）扭曲 Edwards 形式使用 ―― 我们称之为简化扭曲 Edwards 形式。

以下是三种表示形式和双向有理映射，这些映射使映射曲线从一种形式到另一种形式的点成为可能。在所有情况下，生成器和基点都以 (x,y) 的形式书写。

曲线形式

所有生成器和基点都以 (x,y) 的形式书写。

扭曲 Edwards 形式（标准）

方程：ax^2 + y^2 = 1 + dx^2y^2
参数：a = 168700, d = 168696

生成器点：

  (995203441582195749578291179787384436505546430278305826713579947235728471134, 5472060717959818805561601436314318772137091100104008585924551046643952123905)

基点：

  (5299619240641551281634865583518297030282874472190772894086521144482721001553, 16950150798460657717958625567821834550301663161624707787222815936182638968203)

Montgomery 形式

方程：By^2 = x^3 + A x^2 + x
参数：A = 168698, B = 1

生成器点：

  (7, 4258727773875940690362607550498304598101071202821725296872974770776423442226)

基点：

  (7117928050407583618111176421555214756675765419608405867398403713213306743542, 14577268218881899420966779687690205425227431577728659819975198491127179315626)

简化扭曲 Edwards 形式

方程：a' x^2 + y^2 = 1 + d' x^2y^2

参数：

  a' = -1
  d' = 12181644023421730124874158521699555681764249180949974110617291017600649128846

生成器点：

  (4986949742063700372957640167352107234059678269330781000560194578601267663727, 5472060717959818805561601436314318772137091100104008585924551046643952123905)

基点：

  (9671717474070082183213120605117400219616337014328744928644933853176787189663, 16950150798460657717958625567821834550301663161624707787222815936182638968203)

点的转换

以下公式允许将点从一种曲线形式转换为另一种形式。我们将表示坐标

*(u, v) 表示 Montgomery 形式的点， *(x, y) 表示扭曲 Edwards 形式的点， *(x', y') 表示简化扭曲 Edwards 形式的点。

请注意，在上次转换中 ―― 从扭曲 Edwards 转换为简化扭曲 Edwards 及其转换回 ―― 我们还使用了比例因子 f，其中：

f = 6360561867910373094066688120553762416144456282423235903351243436111059670888

在表达式中，也可以直接使用 -f，其中：

-f = 15527681003928902128179717624703512672403908117992798440346960750464748824729

Montgomery –> 扭曲 Edwards

(u, v) --> (x, y)

x = u/v
y = (u-1)/(u+1)

扭曲 Edwards –> Montgomery

(x, y) --> (u, v)

u = (1+y)/(1-y)
v = (1+y)/((1-y)x)

Montgomery –> 简化扭曲 Edwards

(u, v) --> (x', y')

x' = u*(-f)/v
y' = (u-1)/(u+1)

简化扭曲 Edwards –> Montgomery

(x', y') --> (u, v)

u = (1+y')/(1-y')
v = (-f)*(1+y')/((1-y')*x')

扭曲 Edwards –> 简化扭曲 Edwards

(x, y) --> (x', y')

x' = x*(-f)
y' = y

简化扭曲 Edwards –> 扭曲 Edwards

(x', y') --> (x, y)

x = x'/(-f)
y = y'

安全注意事项

本节指定了对 Baby Jubjub 进行的安全检查。安全参数的选择基于 SafeCurves 标准，并且可以在此处找到 Baby Jubjub 满足以下要求的支持证据。

曲线参数

检查曲线规范中的所有参数是否描述了在素数有限域上定义明确的椭圆曲线。

数字 r 是素数。
参数 a 和 d 定义了一个对应于椭圆曲线的方程。
h 和 l 的乘积导致曲线的阶，并且 G 点是生成器。
数字 l 是素数，并且 B 点的阶数为 l。

椭圆曲线离散对数问题

检查离散对数问题在给定的曲线上是否仍然困难。我们检查了 Baby Jubjub 是否能抵抗以下已知攻击。

Rho 方法 [Blake-Seroussi-Smart, 第 V.1 节]：我们要求 rho 方法的成本（平均需要大约 0.886*sqrt(l) 次加法）高于 2^100。
加法和乘法传输 [Blake-Seroussi-Smart, 第 V.2 节]：我们要求嵌入度至少为 (l − 1)/100。
高判别式 [Blake-Seroussi-Smart, 第 IX.3 节]：我们要求复数乘法字段判别式 D 大于 2^100。

椭圆曲线密码学

阶梯 [Montgomery]：检查曲线是否支持 Montgomery 阶梯。
扭曲 [SafeCurves, 扭曲]：检查它是否能抵抗小群攻击、无效曲线攻击和扭曲攻击。
完整性 [SafeCurves, 完整]：检查该曲线是否具有完整的单标量和多标量公式。
不可区分性 [IACR2013/325]：检查是否存在将椭圆曲线点与均匀随机字符串区分开来的映射。

测试用例

测试 1（加法）

考虑具有以下坐标的点 P1 = (x1, y1) 和 P2 = (x2, y2) ：

x1 = 17777552123799933955779906779655732241715742912184938656739573121738514868268
y1 = 2626589144620713026669568689430873010625803728049924121243784502389097019475

x2 = 16540640123574156134436876038791482806971768689494387082833631921987005038935
y2 = 20819045374670962167435360035096875258406992893633759881276124905556507972311

那么它们的和 P1+P2 = (x3, y3) 等于：

x3 = 7916061937171219682591368294088513039687205273691143098332585753343424131937
y3 = 14035240266687799601661095864649209771790948434046947201833777492504781204499

测试 2（倍加）

考虑具有以下坐标的点 P1 = (x1, y1) 和 P2 = (x2, y2) ：

x1 = 17777552123799933955779906779655732241715742912184938656739573121738514868268,
y1 = 2626589144620713026669568689430873010625803728049924121243784502389097019475

x2 = 17777552123799933955779906779655732241715742912184938656739573121738514868268
y2 = 2626589144620713026669568689430873010625803728049924121243784502389097019475

那么它们的和 P1+P2 = (x3, y3) 等于：

x3 = 6890855772600357754907169075114257697580319025794532037257385534741338397365
y3 = 4338620300185947561074059802482547481416142213883829469920100239455078257889

测试 3（倍加单位元）

考虑具有以下坐标的点 P1 = (x1, y1) 和 P2 = (x2, y2) ：

x1 = 0
y1 = 1

x2 = 0
y2 = 1

那么它们的和 P1+P2 = (x3, y3) 导致相同的点：

x3 = 0
y3 = 1

测试 4（曲线成员资格）

点 (0,1) 是 Baby Jubjub 上的一个点。

点 (1,0) 不是 Baby Jubjub 上的一个点。

测试 5（基点选择）

检查坐标为

Bx = 5299619240641551281634865583518297030282874472190772894086521144482721001553
By = 16950150798460657717958625567821834550301663161624707787222815936182638968203

的基点 B = (Bx, By) 是生成器点 G = (Gx, Gy) 的 8 倍，其中

Gx = 995203441582195749578291179787384436505546430278305826713579947235728471134
Gy = 5472060717959818805561601436314318772137091100104008585924551046643952123905

也就是说，检查 B = 8 x G。

测试 6（基点阶数）

检查坐标为

Bx = 5299619240641551281634865583518297030282874472190772894086521144482721001553
By = 16950150798460657717958625567821834550301663161624707787222815936182638968203

的基点 B = (Bx, By) 乘以 l，其中

l = 2736030358979909402780800718157159386076813972158567259200215660948447373041

会导致原点 O = (0, 1)。此测试检查基点 B 的阶数为 l。

实现

Baby Jubjub 的算术和使用该曲线的一些加密原语已经用不同的语言实现。以下是一些这样的实现：

Python: https://github.com/barryWhiteHat/baby_jubjub_ecc
JavaScript: https://github.com/iden3/circomlib/blob/master/src/babyjub.js
Circuit (circom): https://github.com/iden3/circomlib/blob/master/circuits/babyjub.circom
Rust: https://github.com/arnaucube/babyjubjub-rs
Solidity: https://github.com/yondonfu/sol-baby-jubjub
Go: https://github.com/iden3/go-iden3-crypto/tree/master/babyjub

版权

通过 CC0 放弃版权及相关权利。

Citation

Please cite this document as:

Barry WhiteHat (@barryWhiteHat), Marta Bellés (@bellesmarta), Jordi Baylina (@jbaylina), "ERC-2494: Baby Jubjub 椭圆曲线 [DRAFT]," Ethereum Improvement Proposals, no. 2494, January 2020. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-2494.

ERC-2494: Baby Jubjub 椭圆曲线

Table of Contents

简单总结

摘要

动机

规范

定义

阶

生成器点

基点

算术

理由

向后兼容性

曲线形式

点的转换

安全注意事项

测试用例

实现

版权

Citation