EIP-5988: 添加 Poseidon 哈希函数预编译
添加一个预编译合约，该合约实现 Poseidon 密码哈希算法中使用的哈希函数
| Authors | Abdelhamid Bakhta (@abdelhamidbakhta), Eli Ben Sasson (@Elistark), Avihu Levy (@avihu28), David Levit Gurevich (@DavidLevitGurevich) |
|---|---|
| Created | 2022-11-15 |
| Discussion Link | https://ethereum-magicians.org/t/eip-5988-add-poseidon-hash-function-precompile/11772 |
摘要
本 EIP 引入了一个新的预编译合约，该合约实现了 Poseidon 密码哈希算法中使用的哈希函数，目的是允许 EVM 和 ZK / 有效性 Rollup 之间的互操作性，并向 EVM 引入更灵活的密码哈希原语。
动机
Poseidon 是一种算术哈希函数，旨在提高零知识证明系统的效率。 以太坊采用以 Rollup 为中心的路线图，因此必须采用一些机制，使 L2 能够以最佳方式与 EVM 通信。
ZK-Rollup 对密码哈希函数有特殊需求，这些哈希函数可以有效地验证证明。
Poseidon 哈希函数是一组在素数域上的排列，这使其特别适合在以太坊上构建高效的 ZK / 有效性 Rollup。
Poseidon 是可以在此上下文中使用的最有效的哈希算法之一。 此外，它与所有主要的证明系统（SNARK、STARK、Bulletproof 等）兼容。 这使其成为一个很好的预编译候选对象，可以被许多不同的 ZK-Rollup 使用。
需要注意的重要一点是，使用 Poseidon 的 ZK Rollup 选择了不同的参数集，这使得为所有 Rollup 构建单个预编译变得更加困难。
但是，我们仍然可以构建一个支持任意参数的通用预编译，并允许 ZK Rollup 选择他们想要使用的参数。
这就是我们在本 EIP 中采用的方法。
规范
本文档中的关键词“必须”，“不得”，“必需”，“应该”，“不应该”，“推荐”，“可以”和“可选”应按照 RFC 2119 中的描述进行解释。
参数
| 常量 | 值 |
|---|---|
FORK_BLKNUM |
TBD |
GAS_COST |
TBD |
POSEIDON_PRECOMPILE_ADDRESS |
0xA |
以下是预编译将支持的 Poseidon 参数：
| 参数名 | 描述 | 编码大小（以字节为单位） | 评论 |
|---|---|---|---|
p |
素数域模数 | 32 | |
security_level |
以比特为单位测量的安全级别。在 Poseidon 论文中表示为 M |
2 | |
alpha |
S盒的幂 | 1 | |
input_rate |
输入大小 | 2 | |
t |
状态大小 | 1 | |
full_round |
完全轮数。在 Poseidon 论文中表示为 R_F |
1 | |
partial_round |
部分轮数。在 Poseidon 论文中表示为 R_P |
1 | |
input |
哈希函数的输入 | input_rate * 32 |
预编译输入的编码如下：
[32 bytes for p][2 bytes for security_level][1 byte for alpha][2 bytes for input_rate][1 byte for t][1 byte for full_round][1 byte for partial_round][input_rate * 32 bytes for input]
预编译应计算哈希函数，如 Poseidon 论文中指定的 并返回哈希输出。
理由
TODO: 添加理由
TODO: 添加 gas 成本的理由，例如基准测试和计算成本估算。
向后兼容性
此 EIP 破坏向后兼容性的风险很小，唯一的问题是是否有人构建了一个依赖于 0xPOSEIDON_PRECOMPILE_ADDRESS 处地址为空的合约。 这种可能性很小，如果出现特定实例，可以选择该地址为任何任意值，而碰撞风险可以忽略不计。
测试用例
Poseidon 参考实现包含可用于测试预编译的测试向量。 这些测试可在此处获得 here。
安全考虑
引用 Vitalik Buterin 在 EthResearch 上 用于 proto-danksharding 的基于算法哈希的 KZG 替代方案 线程中的话：
Poseidon 哈希函数于 2019 年正式推出。从那时起，它经历了大量的密码分析和优化尝试。 然而，与流行的“传统”哈希函数（例如 SHA256 和 Keccak）相比，它仍然非常年轻，并且它接受高度代数结构以最大限度地减少约束计数的通用方法相对未经测试。 以太坊网络上和已经依赖这些哈希来保证其安全性的其他系统上存在第 2 层系统，到目前为止，它们还没有因此而出现任何错误。 与经过数十年尝试和测试的哈希函数相比，在生产中使用 Poseidon 仍然有些“勇敢”，但应权衡这种风险与提议的替代方案（例如，具有可信设置的配对）的风险以及可能因依赖强大的证明者而产生的集中化风险，这些证明者可以证明 SHA256。
确实，与传统哈希函数相比，算术哈希函数相对未经测试。 但是，Poseidon 经过了彻底的测试，并被多个独立的研究小组认为安全，并且第 2 层系统已经在生产中使用它（StarkWare、Polygon、Loopring），其他项目（例如 Filecoin）也在使用它。
此外，Poseidon 哈希函数中潜在漏洞的影响将仅限于使用它的 Rollup。
我们可以在 EIP-4844 中看到针对 KZG 仪式的相同理由，理由是 KZG 仪式中存在漏洞的风险仅限于使用它的 Rollup。
使用 Poseidon 的项目列表（非详尽）：
- StarkWare 计划使用 Poseidon 作为 StarkNet 的主要哈希函数，并在 Cairo 中添加一个 Poseidon 内置函数。
- Filecoin 采用 POSEIDON 进行具有不同元数的 Merkle 树证明和双值承诺。
- Dusk Network 使用 POSEIDON 构建类似 Zcash 的证券交易协议。11 它还使用 POSEIDON 用于上述加密。
- Sovrin 使用 POSEIDON 进行基于 Merkle 树的撤销。
- Loopring 使用 POSEIDON 在以太坊上进行私人交易。
- Polygon 将 Poseidon 用于 Hermez ZK-EVM。
在安全性方面，参数的选择非常重要。
Poseidon 参数的安全性
MDS 矩阵的选择
MDS 矩阵是大小为 t * t 的方阵，用于混合状态。
此矩阵在 Poseidon 哈希函数的 MixLayer 阶段使用。
必须选择该矩阵，以便不能为超过 t -1 轮设置具有非活动/活动 S 盒的子空间轨迹。
有一些有效的算法可以检测弱 MDS 矩阵。
这些算法在 证明抵抗无限长子空间轨迹：如何选择线性层 论文中进行了描述。
正如 Poseidon 论文中建议的那样，矩阵的生成过程应如下所示：
- 生成一个随机矩阵。
- 使用 证明抵抗无限长子空间轨迹：如何选择线性层 论文中提供的算法 1、算法 2 和算法 3 检查矩阵是否安全。
- 如果矩阵不安全，请返回到步骤 1。
与 Poseidon 安全相关的论文和研究
- Poseidon：一种用于零知识证明系统的新型哈希函数
- Poseidon 哈希函数对非二进制差分和线性攻击的安全性的研究
- 关于 STARK 友好哈希函数安全性的报告
- 针对某些面向算术化的哈希函数的实用代数攻击
版权
版权及相关权利通过 CC0 放弃。
Citation
Please cite this document as:
Abdelhamid Bakhta (@abdelhamidbakhta), Eli Ben Sasson (@Elistark), Avihu Levy (@avihu28), David Levit Gurevich (@DavidLevitGurevich), "EIP-5988: 添加 Poseidon 哈希函数预编译 [DRAFT]," Ethereum Improvement Proposals, no. 5988, November 2022. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-5988.