POSEIDON: A New Hash Function for Zero-Knowledge Proof Systems 学习笔记

1. 引言

Grassi等人2019年论文《POSEIDON: A New Hash Function for Zero-Knowledge Proof Systems》。

前序博客有：

• snark/stark-friendly hash函数
• HADES Strategy

相关代码实现有：

• https://github.com/dusk-network/Poseidon252【Dusk团队】
• https://github.com/arnaucube/poseidon-ark（Rust，与论文贴合度很高。针对BN254 Scalar域，capacity固定为1。）
• https://github.com/shamatar/poseidon_hash
• https://github.com/daira/pasta-hadeshash
• https://github.com/zcash/orchard/blob/main/src/circuit/gadget/poseidon.rs【ZCash团队】
• https://github.com/lovesh/bulletproofs-r1cs-gadgets/blob/master/src/gadget_poseidon.rs【Bulletproofs】
• https://github.com/shamatar/rescue_hash（Rescue hash）
• https://github.com/o1-labs/proof-systems/blob/master/oracle/src/poseidon.rs【Mina团队】
• https://github.com/ingonyama-zk/poseidon-hash【Python，清晰好懂】
• https://github.com/HorizenLabs/poseidon2/blob/main/plain_implementations/src/poseidon/poseidon.rs【Horizen Labs团队，实现了Poseidon和Poseidon2。capacity固定为0。针对babaybear、bls12、bn256、goldilocks、pallas、vesta等域做了相应实现。】

SNARK、STARK、Bulletproofs（PLONK/RedShift）中，若用于proof of knowledge of a preimage under a certain cryptographic hash function时，都需要消耗大量的计算。

所谓proof of knowledge of a preimage under a certain cryptographic hash function，针对的场景为：

• public info： h , H h,H h,H
• private info： x x x
• 待证明relation： h = H ( x ) h=H(x) h=H(x)

其中 H ( ∗ ) H(*) H(∗) 为hash函数。

若hash函数为POSEIDON，其具有8x fewer constraints per message bit than Pedersen Hash。

POSEIDON hash可：

• 紧凑地以circuit表示
• tailored for various proof systems using specially crafted polynomials，从而进一步提升性能。

借助POSEIDON hash，采用Bulletproofs方案来实现1-out-of-10亿 membership proof with Merkle trees，所需的时间少于1秒。

1.1 不同circuit对比

此处主要考虑2种circuit：

• R1CS（rank-1 quadratic constraints）：用于ZK-SNARKs和Bulletproofs中。
• algebraic execution trace (AET) ：用于ZK-STARKs和PLONK中。

1）R1CS（rank-1 quadratic constraints）： Bulletproofs 和 ZK-SNARKs 采用R1CS format（rank-1 quadratic constraints）来描述circuit，表示为一组二次多项式： L 1 ( X ) ⋅ L 2 ( X ) = L 3 ( X ) L_1(X)\cdot L_2(X)=L_3(X) L1​(X)⋅L2​(X)=L3​(X) 其中 X X X为the tuple of internal and input variables， L i L_i Li​为affine forms， ⋅ \cdot ⋅为the field multiplication。 R1CS circuit中的加法门和乘法门都是定义在prime field G F ( p ) GF(p) GF(p)内。 G F ( p ) GF(p) GF(p)为the scalar field of an elliptic curve，对应ZK-SNARKs来说，该椭圆曲线通常需pairing-friendly；对于Bulletproofs来说，该椭圆曲线通常仅需为secure curve即可。 R1CS的proof generation complexity与constraints的数量 T T T成正比，而constraints的数量 T T T通常与乘法门的数量相关。

2）algebraic execution trace (AET)： algebraic execution trace (AET) 将computation 表示为 a set of internal program states related to each other by polynomial equations of degree d d d。该state包含了 w w w field elements，并经历 T T T transformations。 AET的proof generation与 w ⋅ d ⋅ T w\cdot d\cdot T w⋅d⋅T 成比例。The number and sparsity of polynomial constraints do not play a major role。

1.2 实现的POSEIDON家族

POSEIDON采用 HADES 设计策略，基于具有 t t t cells的substitution-permutation networks，使用了名为partial的rounds，采用了non-linear functions only for part of the state。 POSEIDON中在partial rounds中仅使用了1个S-box，但是在所有其它rounds中使用了full non-linear layers（即 t t t个S-box），从而可降低R1CS或AET的开销。

POSEIDON支持80、128、256-bit security：

1.3 POSEIDON性能

• Groth16：

• R1CS 用于Prove a leaf knowledge in the Merkle tree of 2 30 2^{30} 230 elements：

• Bulletproofs 用于Prove a leaf knowledge in the Merkle tree of 2 30 2^{30} 230 elements：

• PLONK 用于证明1-out-of- 2 n 2^n 2n Merkle tree of arity of 4 4 4：

2. Sponge Construction for POSEIDON

Sponge构建与Hades permutation之上，可用于实现：

• encryptiong
• authentication
• hashing

Sponge额外定义了2个参数：

• r r r：为rate。在tree hashing上下文中是指arity。rate定义了吞吐量。
• c c c：capacity。或inner part。capacity则决定了security level。

当将内部的Hades permutation size固定为 N N N bits，则需要在吞吐量和安全性之间做平衡。

以下图为例，用于计算the hash output为 h 1 ∣ ∣ h 2 h_1||h_2 h1​∣∣h2​ of the 4 4 4-block message m 1 ∣ ∣ m 2 ∣ ∣ m 3 ∣ ∣ m 4 m_1||m_2||m_3||m_4 m1​∣∣m2​∣∣m3​∣∣m4​，其中 m i m_i mi​和 h i h_i hi​为 r r r-bit values。初始state I I I为全0，即 I = 0 r ∣ ∣ 0 c I=0^r||0^c I=0r∣∣0c for an r r r-bit rate and a c c c-bit capacity。

3. POSEIDON hash代码解析

https://github.com/arnaucube/poseidon-ark（Rust，与论文贴合度很高。针对BN254 Scalar域，capacity固定为1。），详细见其中的src/lib.rs文件： let t = inp.len() + 1;，默认capacity为1。inp.len()即对应为rate。

4.Dusk POSEIDON hash代码解析

详细参看：

• https://github.com/dusk-network/Poseidon252/blob/master/src/sponge/sponge.rs

其中 messages.chunks(WIDTH - 1) 对应为 m 1 , m 2 , m 3 , m 4 m_1,m_2,m_3,m_4 m1​,m2​,m3​,m4​。 state[0]对应为capacity。

/// The `hash` function takes an arbitrary number of Scalars and returns the
/// hash, using the `Hades` ScalarStragegy.
///
/// As the paper definition, the capacity `c` is set to [`WIDTH`], and `r` is
/// set to `c - 1`.
///
/// Considering `r` is set to `c - 1`, the first bit will be the capacity and
/// will have no message addition, and the remainder bits of the permutation
/// will have the corresponding element of the chunk added.
///
/// The last permutation will append `1` to the message as a padding separator
/// value. The padding values will be zeroes. To avoid collision, the padding
/// will imply one additional permutation in case `|m|` is a multiple of `r`.
pub fn sponge_hash(messages: &[BlsScalar]) -> BlsScalar {
    let mut h = ScalarStrategy::new();
    let mut state = [BlsScalar::zero(); WIDTH];

    // If exists an `m` such as `m · (WIDTH - 1) == l`, then the last iteration
    // index should be `m - 1`.
    //
    // In other words, if `l` is a multiple of `WIDTH - 1`, then the last
    // iteration of the chunk should have an extra appended padding `1`.
    let l = messages.len();
    let m = l / (WIDTH - 1);
    let n = m * (WIDTH - 1);
    let last_iteration = if l == n {
        m.saturating_sub(1)
    } else {
        l / (WIDTH - 1)
    };

    messages
        .chunks(WIDTH - 1)
        .enumerate()
        .for_each(|(i, chunk)| {
            state[1..].iter_mut().zip(chunk.iter()).for_each(|(s, c)| {
                *s += c;
            });

            // Last chunk should have an added `1` followed by zeroes, if there
            // is room for such
            if i == last_iteration && chunk.len()