EIP-3068: 用于 BN256 HashToCurve 算法的预编译

简述

本 EIP 定义了一个用于 BN256 的 hash-to-curve 预编译， 并允许更廉价的 BLS 签名验证。

摘要

目前还没有廉价的方法来执行任意消息的 BLS 签名验证。 这源于 EVM 中没有用于 BN256 椭圆曲线的 hash-to-curve 算法的预编译合约。 用 Solidity 编写的确定性 hash-to-curve 算法的 gas 成本大约是一个配对检查的成本， 尽管后者需要高一个数量级的计算。 本 EIP 通过实现 BN256 G1 曲线的 hash-to-curve 算法来解决这个问题， 这将把签名验证的成本降低到与配对检查预编译合约基本相同的水平。 我们还包括一个用于 BN256 G2 群的 hash-to-curve 算法。

动机

EIP-198 和 EIP-1108 中的预编译合约通过降低 gas 成本增加了 EVM 中密码操作的使用。 特别是，EIP-1108 的成本降低有助于通过椭圆曲线配对检查增加以太坊中 SNARK 的使用； 然而，一种支持在 EVM 上进行任意 BLS 签名验证的 BN256 hash-to-curve 算法明显缺失。 人们有兴趣拥有一个允许签名验证的预编译合约，如 此处所述。

目前，我们能够在 BN256 中执行加法、标量乘法和配对检查。 降低 EIP-1108 中的这些成本使得 ETHDKG， 一种以太坊中的分布式密钥生成协议，变得更便宜。 ETHDKG 本身是有用的；然而，它所缺少的是验证任意 BLS 签名的能力。 通过聚合部分签名来创建群签名是 DKG 协议的一个目标。 DKG 使得部分签名的计算能够离线组合成群签名，但是没有 简单的方法来验证 EVM 中的部分签名或群签名。

为了执行 BLS 签名验证，需要一种 hash-to-curve 算法。 虽然最初在原始 BLS 论文 中讨论的 MapToGroup 方法在实践中有效，但该算法的不确定性 留下了一些不足之处，因为我们希望限制 EVM 中的总体计算成本。 一种用于映射到 BN 曲线的确定性方法在 此处给出； 在论文中，Fouque 和 Tibouchi 证明了他们的映射 与随机预言机是不可区分的。 这给了我们想要的算法。

规范

以下是 HashToG1 函数的伪代码：

function HashToG1(msg)
    fieldElement0 = HashToBase(msg, 0x00, 0x01)
    fieldElement1 = HashToBase(msg, 0x02, 0x03)
    curveElement0 = BaseToG1(fieldElement0)
    curveElement1 = BaseToG1(fieldElement1)
    g1Element = ECAdd(curveElement0, curveElement1)
    return g1Element
end function

以下是 HashToBase 的伪代码； msg 是要散列的字节切片，而 dsp1 和 dsp2 是域分离参数。 fieldPrime 是底层域的素数。

function HashToBase(msg, dsp1, dsp2)
    hashResult0 = uint256(Keccak256(dsp1||msg))
    hashResult1 = uint256(Keccak256(dsp2||msg))
    constant = 2^256 mod fieldPrime
    fieldElement0 = hashResult0*constant          mod fieldPrime
    fieldElement1 = hashResult1                   mod fieldPrime
    fieldElement  = fieldElement0 + fieldElement1 mod fieldPrime
    return fieldElement
end function

以下是 BaseToG1 的伪代码。 所有这些操作都在有限域中执行。 inverse 计算底层 有限域中的乘法逆元；我们约定 inverse(0) == 0。 is_square(a) 计算元素的勒让德符号， 如果 a 是一个平方，则返回 1，如果 a 不是一个平方，则返回 -1， 如果 a 是 0，则返回 0。 sqrt 计算有限域中元素的平方根； 假设存在平方根。 sign0 返回有限域元素的符号。

function BaseToG1(t)
    # 所有操作都在有限域 GF(fieldPrime) 中完成
    # 在这里，椭圆曲线满足方程
    #       y^2 == g(x) == x^3 + curveB
    constant1 = (-1 + sqrt(-3))/2
    constant2 = -3
    constant3 = 1/3
    constant4 = g(1)
    s = (constant4 + t^2)^3
    alpha = inverse(t^2*(constant4 + t^2))
    x1 = constant1 - constant2*t^4*alpha
    x2 = -1 - x1
    x3 = 1 - constant3*s*alpha
    a1 = x1^3 + curveB
    a2 = x2^3 + curveB
    residue1 = is_square(a1)
    residue2 = is_square(a2)
    index = (residue1 - 1)*(residue2 - 3)/4 + 1
    coef1 = ConstantTimeEquality(1, index)
    coef2 = ConstantTimeEquality(2, index)
    coef3 = ConstantTimeEquality(3, index)
    x = coef1*x1 + coef2*x2 + coef3*x3
    y = sign0(t)*sqrt(x^3 + curveB)
    return (x, y)
end function

function sign0(t)
    if t <= (fieldPrime-1)/2
        return 1
    else
        return fieldPrime-1
    end if
end function

function ConstantTimeEquality(a, b)
    # 此函数以恒定时间运行
    if a == b
        return 1
    else
        return 0
    end if
end function

在 HashToG2 中，我们首先映射到底层的扭曲曲线， 然后清除辅因子以映射到 G2。 以下是 HashToG2 的伪代码：

function HashToG2(msg)
    fieldElement00 = HashToBase(msg, 0x04, 0x05)
    fieldElement01 = HashToBase(msg, 0x06, 0x07)
    fieldElement10 = HashToBase(msg, 0x08, 0x09)
    fieldElement11 = HashToBase(msg, 0x0a, 0x0b)
    fieldElement0 = (fieldElement00, fieldElement01)
    fieldElement1 = (fieldElement10, fieldElement11)
    twistElement0 = BaseToTwist(fieldElement0)
    twistElement1 = BaseToTwist(fieldElement1)
    twistElement = ECAdd(twistElement0, twistElement1)
    g2Element = ClearCofactor(twistElement)
    return g2Element
end function

function ClearCofactor(twistElement)
    return ECMul(twistElement, cofactor)
end function

以下是 BaseToTwist 的伪代码。

function BaseToTwist(t)
    # 所有操作都在有限域 GF(fieldPrime^2) 中完成
    # 在这里，扭曲曲线满足方程
    #       y^2 == g'(x) == x^3 + curveBPrime
    constant1 = (-1 + sqrt(-3))/2
    constant2 = -3
    constant3 = 1/3
    constant4 = g'(1)
    s = (constant4 + t^2)^3
    alpha = inverse(t^2*(constant4 + t^2))
    x1 = constant1 - constant2*t^4*alpha
    x2 = -1 - x1
    x3 = 1 - constant3*s*alpha
    a1 = x1^3 + curveBPrime
    a2 = x2^3 + curveBPrime
    residue1 = is_square(a1)
    residue2 = is_square(a2)
    index = (residue1 - 1)*(residue2 - 3)/4 + 1
    coef1 = ConstantTimeEquality(1, index)
    coef2 = ConstantTimeEquality(2, index)
    coef3 = ConstantTimeEquality(3, index)
    x = coef1*x1 + coef2*x2 + coef3*x3
    y = sign0(t)*sqrt(x^3 + curveBPrime)
    return (x, y)
end function

原理

BaseToG1 算法基于 Fouque 和 Tibouchi 的原始 论文， 并根据 Wahby 和 Boneh 的 论文进行了修改。 可以自由选择 HashToBase 函数， 这很容易更改。 在 HashToBase 中，特定的哈希算法 （在我们的例子中是 Keccak256）也可以修改。 可能希望在 BaseToG1 和 BaseToTwist 的末尾更改对 sign0 的调用，使用 is_square， 因为这将导致与 Fouque 和 Tibouchi 论文 中相同的确定性映射到曲线，并确保 HashToG1 与随机预言机不可区分； 他们在论文中证明了这个结果。 有可能证明将 is_square 调用与 sign0 切换不会影响不可区分性， 尽管这尚未得到证实。

HashToG2 算法遵循 Wahby 和 Boneh 论文。 可以在 此处找到 在有限域 GF(fieldPrime^2) 中计算 inverse、is_square 和 sqrt 的算法。

我们现在讨论 HashToG1 和 HashToG2 操作的潜在 gas 成本。 在一台本地机器上，ECMul 的时钟频率为每次操作 68 微秒。 当将 32 字节散列到 G1 中时，同一台机器上 HashToG1 的时钟频率为每次操作 94 微秒，当将 1024 字节散列到 G1 中时，时钟频率为每次操作 105 微秒。 鉴于目前 ECMul 的 gas 成本为 6000，这使我们 估计 HashToG1 的 gas 成本为 8500 + len(bytes)。 同样，当将 32 字节散列到 G2 中时，HashToG2 的时钟频率为每次操作 886 微秒，当 将 1024 字节散列到 G2 中时，时钟频率为每次操作 912 微秒。 这使我们能够估计 gas 成本为 80000 + 3*len(bytes)。

向后兼容性

没有向后兼容性问题。

测试用例

待定

实现

待定

安全注意事项

由于最近的工作， BN256 椭圆曲线承诺的 128 位安全性不再适用； 这在 Cloudflare BN256 库中提到过。 关于这一进展导致的确切安全降低程度，已经进行了一些讨论；请参阅 这两篇 论文 以获得不同的估计。 更保守的估计将 BN256 的安全性设定为 100 位。 虽然这对于许多对手来说可能仍然遥不可及， 但它应该让我们停下来。 MadNet 最近的白皮书 中指出了这种安全性的降低， 并且通过要求部分群签名的 Secp256k1 签名 以使这些部分签名有效，从而部分缓解了这种安全问题。 完全披露：本 EIP 的作者为 MadHive 工作， 协助了 MadNet 的开发，并且 帮助撰写了 MadNet 白皮书。

BN256 椭圆曲线的安全问题 影响任何使用配对检查的操作，因为它与椭圆曲线配对相关； 它们与本 EIP 无关。

版权

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

Citation

Please cite this document as:

Christopher Gorman 博士 (@chgormanMH), "EIP-3068: 用于 BN256 HashToCurve 算法的预编译 [DRAFT]," Ethereum Improvement Proposals, no. 3068, October 2020. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-3068.