摘要：本文简单介绍了多项式承诺的发展现状以及哈希函数在零知识证明（zk）中的应用。然后对 Plonky2 和 Plonky3 中使用的两代 Poseidon 哈希函数进行了详细研究和比较。最后，我们给出了一些基准结果，以验证 Poseidon2 的计算性能。

关键词：Plonky3；多项式承诺；散列；Poseidon2

1. Introdution

为了保证系统的数据完整性，目前大多数零知识证明采用多项式承诺方案，它的主要作用在于：

• 数据完整性验证：多项式承诺可以用来承诺某些数据，确保数据在传输或存储过程中不被篡改。接收方可以通过验证承诺是否正确来验证数据的完整性。
• 隐藏数据：多项式承诺允许将某些数据进行隐藏，而不需要将实际数据公开。只有知道对应的承诺值的人才能获得实际数据。
• 证明系统的构造：在某些零知识证明系统中，需要证明某个值在多项式中的存在性或特性。多项式承诺可以用来实现对多项式中的值的承诺，并且可以在证明过程中验证这些值的正确性。
• 随机数生成：多项式承诺可以用来生成随机数，确保生成的随机数的不可预测性和随机性。这在一些零知识证明系统中是必需的，例如在密码学协议中生成安全的随机数。
• 保护隐私：多项式承诺可以帮助保护数据的隐私，因为只有知道对应承诺值的人才能获得实际数据，而其他人无法获知实际数据内容。

多项式承诺有多种方式，比如最直接的就是把多项式系数承诺出去，这样多项式在承诺后就不能再改变了。显然，当系数比较多时，承诺结果就会比较大，增加存储与传输的代价，不符合零知识证明系统的简洁性要求。因此，当前的零知识证明系统所采用的是点值承诺方案，其中较为常见的包括：

①Pedersen Commitment: Pederson Commitment 是密码学中承诺的一种，1992 年被提出[1]。Pedersen Commitment 主要搭配椭圆曲线密码学使用（当然也可以结合指数运算）。它基于离散对数假设，通过将多项式的系数和随机值进行混合来生成承诺，并利用离散对数性质实现隐藏和完整性。。目前 Pedersen Commitment 在区块链中的应用主要在隐私币中，如 Zcash, MimbleWimble, Monero 等。

②IPA Commitment [2] :严格来说 IPA（Inner Product Argument）是一种技术，用于验证两个向量的内积是否满足某些特定的性质。它允许证明者承诺一个多项式，同时提供证明该多项式满足某些特定性质的证据，例如，其对另一个向量的内积为零。在证明过程中，证明者可以使用 IPA 多项式承诺来隐藏多项式的具体系数，同时确保证明的正确性和完整性。

②KZG Commitment：KZG Commitment 是一种更高效的多项式承诺方案，基于区间验证的方法。它具有快速生成和验证的特点，适用于对效率要求较高的应用场景。使用 KZG Commitment 的系统主要有：Groth16、Sonic、StarkWare。

③BCH Commitment：BCH（Benaloh-Cohen-Horvitz）Commitment 是一种具有非交互性质的多项式承诺方案，它允许生成承诺后不需要进一步的交互就可以完成验证。BCH 承诺的基本思想是使用同态性质来验证承诺。具体来说，它基于对数同态（log homomorphism）和幂同态（power homomorphism），通过利用这些同态性质使得验证承诺时只需进行一次幂运算和一次对数运算即可完成，而无需逐项验证多项式的系数，这种特性使得 BCH 承诺在一些特定的零知识证明系统中具有优势。

④Fiat-Shamir Commitment：Fiat-Shamir Commitment 是基于 Fiat-Shamir 转换的 Merkle 树承诺方案。Fiat-Shamir 转换是一种将交互式的零知识证明协议转换为非交互式形式的技术。在 Fiat-Shamir Commitment 中，承诺者可以在不与验证者进行交互的情况下生成和验证承诺，从而实现了非交互性质。它可以与其他多项式承诺方案结合使用，以实现非交互式的零知识证明系统。

⑤FRI 承诺：FRI 承诺是一种基于 Reed-Solomon 码 (BCH 码的子集 ) 的承诺方案，它可以用于构建高效的零知识证明系统。该方案的优点是承诺值的大小与多项式的次数成线性关系，并且可以被有效地验证。但是，FRI 承诺方案需要可信设置，这在某些应用场景中可能是一个缺点。

在各类多项式承诺方案中，基于配对密码学或 Reed-Solomon 码的承诺方案的安全性基于更强的假设，例如 Pedersen 承诺、KZG 承诺。因此，这些方案在理论上更加安全；使用 Merkle 树来实现多项式承诺方案的优点是简单易懂，并且可以被有效地实现。但是，Merkle 树是基于哈希函数实现的，它的安全性通常依赖于随机预言机模型，而随机预言机模型在现实世界中是不存在的。因此，基于 Merkle 树的承诺方案在安全性上存在一些争议。

2. Polynomial Commitment in Plonky

Plonky 起源于 zk-SNARKs 证明系统，起初大多数 zk-SNARKs 使用的是 KZG 承诺方案，而 Plonky1 使用的是 Halo 的 IPA 承诺方案，这样使得 Plonky1 在证明时间上取得了一定优势，但它并非是真正的在计算递归证明，而是对于检验的证明。

Plonky2 的一个重要革新就是使用了 STARKs 的底层协议 -FRI 承诺方案，它不涉及任何椭圆曲线，而是使用哈希算法来实现多项式的承诺和验证过程。这是因为哈希的两个重要特性：第一，通常来说哈希计算很快，第二，只在一个域上定义，所以一个哈希的输入和输出是同一个域上的一系列域元素，这样证明系统使用一个小域 (Goldilocks 域 ) 即可完成快速证明。此外，FRI 多项式承诺还具有一个重要优势，它是完全递归的，在任意时间点都有完全的对之前的链或树的递归证明，这使它在工程上很简单，就是将完整的验证者在电路中实现。

相较之下，Binius 使用的是另一种新的基于 Brakedown 的承诺方案 ( 使用了 Merkle trees 和 Reed-Solomon 编码 )。相比于 FRI，该方案具有更大的 proofs 和更长的验证时间，但 Prover time 能够大幅降低。

Plonky3 目前仍然处于开发阶段，但它已经比 Plonky2 有了显著的性能提升。Plonky3 中仍然使用了 FRI 多项式承诺方案，也加入了 Brakedown 的承诺方案。它在 FRI 实现细节上进行了改进，这些改进包括：使用优化的数据结构来存储和操作 FRI 协议所需的数据；使用并行计算来进一步提高 FRI 协议的效率；使用更加友好的哈希函数和更小的域（Mersenne31 素数域）。The focus of this article is to conduct an in-depth analysis of poseidon2 hash functions.

3. Hash Function in ZK

在密码学中，哈希函数是一种将任意大小的数据映射到固定大小的输出的函数。哈希函数的输出称为哈希值或哈希码。哈希函数具有单向性和抗碰撞性。一些常见的哈希函数包括 MD5、SHA-1、SHA-256 和 SHA-3。例如，假设您要验证一个文件的完整性。您可以使用哈希函数来计算该文件的哈希值。然后，您可以将该哈希值与文件的预期哈希值进行比较。如果两个哈希值相匹配，则可以确信文件没有被篡改。

在零知识证明领域中，使用抗碰撞 Hash 函数能够有效消除对可信任设置或椭圆曲线运算的需要，使 Hash 函数成为零知识证明系统中不可或缺的一部分。哈希函数在零知识证明系统中的发展过程可以总结为以下几个阶段：

•第一阶段：通用哈希函数

在零知识证明的早期阶段，主要使用通用哈希函数，例如 SHA-256 和 MD5。这些哈希函数被设计用于各种应用，包括数字签名和消息认证。然而，它们并不一定适合零知识证明系统的特定需求。

•第二阶段：基于 Merkle 树的承诺方案

随着零知识证明技术的发展，许多零知识证明系统开始开发专门用于零知识证明的哈希函数。一个重要的标志是基于 Merkle 树的承诺方案。Merkle 树是一种二叉树，它使用哈希函数来构建。Merkle 树可以用来构建多项式承诺，承诺值是 Merkle 树的根哈希值。基于 Merkle 树的承诺方案的优点是简单易懂，并且可以被有效地实现。然而，这些方案的安全性通常依赖于随机预言机模型，而随机预言机模型在现实世界中是不存在的。因此，基于 Merkle 树的承诺方案的安全性在理论上存在争议。

•第三阶段：基于专用哈希函数

随着更加高效的多项式承诺方案的出现和发展，出现了专门用于零知识证明的哈希函数，例如 Poseidon[7]和 Rescue-Prime[8]。这些专用哈希函数针对零知识证明系统的特定需求进行了优化，例如高效的计算和抵抗特定类型的攻击。

在 Plonky2 中就使用了 Poseidon 哈希函数作为多项式承诺的节点生成方式。Poseidon 采用 sponge/squeeze 结构，该结构吸纳万物并生成固定大小的输出，内部有一个状态 ，初始状态为 0，状态 S 可分为外部状态和内部状态，即 和。

图 1 Plonky2 中的 Poseidon 哈希函数实现

Poseidon 哈希计算主要包括三步：第一次 Full Rounds、Partial Rounds 和第二次 Full Rounds，具体流程如下图所示。

图 2 Construction of the Poseidon permutation in Plonky2

Full Rounds 中每次循环中需要对 state 向量的所有元素依次完成 Add Round Constant，S-Box 和 MDS Mixing( The Linear Layer/MixLayer) 操作，其中 Add Round Constants 需要完成一次常数加法，S-Box 需要计算一个 7 次方的模幂，MDS Mixng 计算的是 state 向量和常数矩阵 M 相乘。

图 3 Full Rounds in Plonky2

Partial Rounds 和 Full Rounds 的计算流程基本一致，不同点在于 Partial Rounds 在 S-Box 阶段只需完成第一个元素的模幂运算。

图 4 Partial Rounds in Plonky2

Plonky2 中使用的 Poseidon 共有 12 个 state 输入，共 3 个 Rounds，每个 Round 执行 30 次，总共执行 90 次 Rounds。简化后的 Poseidon 计算流程如下所示。

图 5 The Poseidon Construction in [7]

Poseidon 哈希函数是专门基于 Goldilocks 域开发的，目的在于减轻零知识证明系统中证明者和验证者的计算复杂度。相比于 Keccak 哈希函数，不需要使用大的 circuit 表示（Keccak 在约束设计时会引入大量复杂度），因此在 Plonky2 中表现出很好的计算性能。

4. Poseidon2 in Plonky3

Plonky3 相比于 Plonky2 来说更像一个构建零知识证明系统的工具包。其开源代码中加入了许多新特性，几个重要特性包括:

•增加了 RISC Zero 项目使用的 BabyBear 域 ( ) 和运算速度更快的 Mersenne31 素数域 ( )[9]；

•在已有的 Reed-Solomon 编码基础上增加了 Brakedown 编码[10];

•针对 Mersenne31 素数域，实现了速度更快的 circle FFT；

•更丰富的哈希函数，如新加入的 Rescue、Poseidon2、Monolith，加上原来的 Poseidon、Blake3、Keccak，目前更有六种哈希函数。

由这些变化可知，哈希函数在 Plonky3 工具包中占有举足轻重的地位，本章节重点分析其中的 Poseidon2 哈希函数。

2023 年，Lorenzo Grassi 等人对 Poseidon 哈希函数进行了改进，推出了 Poseidon2[11]。相比于，主要有以下几个改进 ( 如图 6)：

(1) A linear layer is applied at the input of Poseidon2；

(2) Two different linear layers with  and  are used in Poseidon2 for t ≥ 4.；

(3) Only one round constant is applied in each internal round；

图 6 Poseidon(left) and Poseidon2(right) with changes in red

Plonky3 中针对 t ≥ 4 的情况做了优化，并参考了[12]的实现，核心代码实现如下（伽罗域，width=12），图中红色框中的代码为改进内容。

图 7 core code with changes in red

线性层中有两个常量矩阵 M and M₁。其中 , 这里

The advantages of the constant matrices are that we can compute the multiplication of 4 input elements with M₄ by using only additions( 总共 t-1 次加法 ).

图 8 The multiplication of 4 input elements with M₄

第二个矩阵 M₁ 构造为：

 当然，适当选择某些特殊元素可以使乘法变得更加快捷。矩阵 M₁带来的好处是，只需要存储 t 个数，就可通过 2t−1 次元素加法和 t 次元素乘法实现向量与矩阵的乘法。

总之，改进后的 Poseidon2 哈希比 Poseidon 更简单并且使用的内存更少。As shown in the figure below, the number of operations and Plonk constraints needed for the linear layers in Poseidon2 is less than that in Poseidon.

图 9 Number of operations and Plonk constraints needed for the linear layers of Poseidon and Poseidon2 , where p ≈ 2^64

5. Benchmarks of Poseidon2

我们对 Poseidon2 的性能做了测试。测试代码参考[13]。The rust code focus only on primitives without any high-degree components. 测试平台如下。

操作系统：Ubuntu22.04

CPU: Intel i7-13700H 2.40 GHz

内存：64.0 GB DDR5 4800 

In the benchmarks we focus on two different primes used in Plonky3, namely the 64-bit Goldilocks and the 31-bit Babybear. The results are shown in Table 1. We can see that Poseidon2 has a significant performance improvement over Poseidon. Additionally, the advantage increases for larger state sizes, due to the expensive matrix multiplication in the external rounds of Poseidon.

References：

[1]     Pedersen, T. (1992). "Non-interactive and information-theoretic secure verifiable secret sharing." Advances in Cryptology—CRYPTO'91. Springer Berlin Heidelberg..

[2]     Groth, J., & Sahai, A. (2008, July). Efficient non-interactive proof systems for bilinear groups. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 415-432). Springer, Berlin, Heidelberg.

[3]     Kate, A., Zaverucha, G. M., & Goldberg, I. (2010, May). Constant-size commitments to polynomials and their applications. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 177-194). Springer, Berlin, Heidelberg.

[4]     .Benaloh, J., Cohen, N., & Horvitz, S. (1988). Multi-Exponentiation Cryptosystems. In CRYPTO'88 Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology (pp. 195-210). Springer-Verlag.

[5]     Fiat, A., & Shamir, A. (1986). How to prove yourself: Practical solutions to identification and signature problems. In Conference on the theory and application of cryptographic techniques (pp. 186-194). Springer, Berlin, Heidelberg.

[6]     Fiat, A., & Shamir, A. (1986). How to prove yourself: Practical solutions to identification and signature problems. In Conference on the theory and application of cryptographic techniques (pp. 186-194). Springer, Berlin, Heidelberg.

[7]     Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, et al. POSEIDON: A New Hash Function for Zero-Knowledge Proof Systems. https://eprint.iacr.org/2019/458.pdf. 2019.

[8]     Alan Szepieniec1 , Tomer Ashur2,3 , and Siemen Dhooghe. Rescue-Prime: a Standard Specification (SoK). https://eprint.iacr.org/2020/1143.pdf. 2020.

[9]     Ulrich Habock, Daniel Lubarov, Jacqueline Nabaglo. Reed-Solomon codes over the circle group. https://eprint.iacr.org/2023/824.pdf. 2023.

[10]  Alexander Golovnev, Jonathan Lee, Srinath Setty，et al. Brakedown: Linear-time and field-agnostic SNARKs for R1CS.  https://eprint.iacr.org/2021/1043.pdf. 2021.

[11]  Lorenzo Grassi, Dmitry Khovratovich, and Markus Schofnegger. Poseidon2: A Faster Version of the Poseidon Hash Function. 323.pdf (iacr.org). 2023.

[12]  https://github.com/HorizenLabs/poseidon2/blob/main/plain_implementations/src/poseidon2/poseidon2_instance_goldilocks.rs

[13]  GitHub - HorizenLabs/poseidon2