Polygon Miden VM中的哈希函数对比

1. 引言

在Polygon Miden VM中，使用了多个不同的哈希函数：

Polygon Miden团队对多个哈希函数进行了benchmark，并对比了其在其它证明系统中所采用的构建。具体benchmark内容为：

1）BLAKE3：见 BLAKE3规范，基于https://github.com/BLAKE3-team/BLAKE3 crate所暴露的wrapper来bench。
2）SHA3：见 SHA3规范，基于https://github.com/facebook/winterfell/blob/46dce1adf0/crypto/src/hash/sha/mod.rs 代码来bench。
3）Poseidon：见 2019年Poseidon论文，基于https://github.com/0xPolygonZero/plonky2/blob/806b88d7d6e69a30dc0b4775f7ba275c45e8b63b/plonky2/src/hash/poseidon_goldilocks.rs 纯rust代码来bench，而无vectorized instructions。
4）Rescue Prime（RP）：见 2020年Rescue-Prime: a Standard Specification (SoK) 论文，基于https://github.com/facebook/winterfell/blob/46dce1adf0/crypto/src/hash/rescue/rp64_256/mod.rs 代码来bench。
5）Rescue Prime Optimized（RPO）：见 2022年Rescue-Prime Optimized论文，基于https://github.com/0xPolygonMiden/crypto/blob/next/src/hash/rescue/rpo/mod.rs 代码来bench。
6）Rescue Prime Extended（RPX）：见 2023年XHash8 and XHash12: Efficient STARK-friendly Hash Functions论文，为xHash哈希函数的变种，基于https://github.com/0xPolygonMiden/crypto/blob/next/src/hash/rescue/rpx/mod.rs 代码来bench。

实际，对RPO和BLAKE3的bench流程为：

git clone https://github.com/0xPolygonMiden/crypto
cd crypto
cargo bench hash

对Rescue Prime、Poseidon和SHA3的bench流程为：

git clone https://github.com/Dominik1999/winterfell
cd winterfell
git checkout hash-functions-benches
cargo bench hash

实际在对以上哈希函数做bench时，分了2种场景：【注意，在Amazon Graviton 3服务器上，运行RPO256和RPX256时，均启用了SVE加速。】

1）场景一：2-to-1 $(a,b)\mapsto h(a,b)$ 哈希，其中 $a, b, h (a, b)$ 均为每个哈希函数的digest。
2）场景二：序列哈希，对100个域元素所组成的序列做哈希，以生成单个digest：
- 对Poseidon、Rescue Prime和RPO来说，该digest为素数域 $2^{64}-2^{32}+1$ 内的4个域元素（即，32个字节）。
- 对SHA3和BLAKE3来说，该digest为数组[u8; 32]。