SNARK中哈希的基准测试

用例

• 基于哈希的签名的聚合
  • 乐观要求：50万个哈希/秒[1]
• STARKed 二叉哈希树
  • 最坏情况要求：10万个哈希/秒[2]

要求

• 后量子友好
• 可证明的可靠性
• 编写规范不太复杂

基准候选

• plonky3 - FRI + AIR
  • 实现了 Blake3 电路、Keccak 电路 和 Poseidon2 电路
• stwo - FRI + AIR
  • 实现了 Blake2s 电路 和 Poseidon2 电路
• binius
  • 实现了 Keccak 电路 和 Vision 电路
• hashcaster - 二进制域上的 GKR
  • 实现了 Keccak 电路，但尚未连接 PCS
• expander - GKR
  • 实现了 Keccak 电路 和 Poseidon 电路

基准

• 机器配置

  • CPU：i9-13900K
  • 内存：64GB (2x Crucial DDR5 5600 32GB 双通道)
  • 操作系统：Linux 5.15.0-124-generic x86-64
  • 环境：
  • RAYON_NUM_THREADS: 4

• 代码: https://github.com/han0110/bench-hash-in-snark/tree/3398a8c

• 输出

  • perm: 证明的置换次数 (210..20)
  • time: 10 个样本的平均证明时间
  • throughput: 10 个样本的平均吞吐量 (= perm / time)
  • proof_size: 10 个样本的平均证明大小
  • peak_memory: 由 /usr/bin/time 度量的证明命令的峰值内存使用量（如果进程由于 OOM 被终止，该行将填充 -）

• 所有软件包的实现都是具有固定初始状态的一轮置换，如果实际输入长度大于哈希函数的块长度，则需要基于构造对实现施加更多约束，但与置换相比，成本应该可以忽略不计。

• • *

plonky3

FRI 参数：

• 域大小：124（31 位域的 4 度扩展）

• 速率：1/2

• 查询次数：256

• Poseidon2 参数（符号遵循 https://eprint.iacr.org/2023/323.pdf）

  • n=31t=16d=3RF=8RP=20
  • p=231−224+1 (KoalaBear)

• 124 位域太小，无法达到 128 位可证明的可靠性，我们需要大约 192 位域，但目前没有可用的选项。

这使得下面的 throughput 有点乐观。

• 查询次数也需要稍微增加才能达到准确的 128 位可证明的可靠性，但不会与当前值相差太远。

这使得下面的 proof_size 有点乐观。

要重现，请进入代码存储库并运行：

for i in $(seq 10 20); do
    RAYON_NUM_THREADS=4 ./bench.sh plonky3 blake3 $i
    RAYON_NUM_THREADS=4 ./bench.sh plonky3 keccak $i
    RAYON_NUM_THREADS=4 ./bench.sh plonky3 poseidon2 $i
done;
python3 render_table.py

相同的 FRI 参数，但速率 = 1/4

要重现，请进入代码存储库并运行：

for i in $(seq 10 20); do
    RAYON_NUM_THREADS=4 PCS_LOG_INV_RATE=2 ./bench.sh plonky3 blake3 $i
    RAYON_NUM_THREADS=4 PCS_LOG_INV_RATE=2 ./bench.sh plonky3 keccak $i
    RAYON_NUM_THREADS=4 PCS_LOG_INV_RATE=2 ./bench.sh plonky3 poseidon2 $i
done;
python3 render_table.py

stwo

FRI 参数：

• 域大小：124（31 位域的 4 度扩展）

• 速率：1/2

• 查询次数：256

• Poseidon2 参数（符号遵循 https://eprint.iacr.org/2023/323.pdf）

  • n=31t=16d=5RF=8RP=14
  • p=231−1 (Mersenne31)

• 124 位域太小，无法达到 128 位可证明的可靠性，我们需要大约 192 位域，但目前没有可用的选项。

这使得下面的 throughput 有点乐观。

• 查询次数也需要稍微增加才能达到准确的 128 位可证明的可靠性，但不会与当前值相差太远。

这使得下面的 proof_size 有点乐观。

要重现，请进入代码存储库并运行：

for i in $(seq 10 20); do
    RAYON_NUM_THREADS=4 ./bench.sh stwo blake2s $i
    RAYON_NUM_THREADS=4 ./bench.sh stwo poseidon2 $i
done;
python3 render_table.py

相同的 FRI 参数，但速率 = 1/4

要重现，请进入代码存储库并运行：

for i in $(seq 10 20); do
    RAYON_NUM_THREADS=4 PCS_LOG_INV_RATE=2 ./bench.sh stwo blake2s $i
    RAYON_NUM_THREADS=4 PCS_LOG_INV_RATE=2 ./bench.sh stwo poseidon2 $i
done;
python3 render_table.py

binius

FRI 参数：

• 域大小：128

• 速率：1/2

• 查询次数：241

• 可证明的可靠性：100 位

• 128 位域太小，无法达到 128 位可证明的可靠性，我们需要大约 150 位域，但目前没有可用的选项。

这使得下面的 throughput 有点乐观。

要重现，请进入代码存储库并运行：

for i in $(seq 10 20); do
    RAYON_NUM_THREADS=4 ./bench.sh binius keccak $i
    RAYON_NUM_THREADS=4 ./bench.sh binius vision $i
done;
python3 render_table.py

hashcaster

由于 hashcaster 仅实现了 PIOP 部分，因此下面的基准测试使用 Binius 承诺方案来完成它。

FRI 参数：

• 字段大小：128

• 速率：1/2

• 查询数量：241

• 可证明的可靠性：100 位

• 128 位字段太小，无法达到 128 位可证明的可靠性，我们Roughly需要 150 位字段，但目前没有可用的选项。

这使得下面的 throughput 有点乐观。

• keccak-f 中的 iota 步骤尚未实现，但它应该是可以忽略不计的，因为它可以延迟并合并到线性层中。

这使得下面的 throughput 有点乐观。

要重现，请进入代码仓库并运行：

for i in $(seq 10 20); do
    RAYON_NUM_THREADS=4 ./bench.sh hashcaster keccak $i
done;
python3 render_table.py

expander

• 波塞冬参数（符号遵循 https://eprint.iacr.org/2023/323.pdf）

  • n=31t=16d=5RF=8RP=14
  • p=231−1 (Mersenne31)

• PCS 尚未完成，因此承诺只是原始见证。

这使得下面的 proof_size 比预期的大得多。

• GKR 中使用的 93 位字段太小，无法达到 128 位可证明的可靠性。

这使得下面的 throughput 有点乐观。

要重现，请进入代码仓库并运行：

cd expander/circuit/
go run gf2_keccak.go
go run m31_poseidon.go
cd ../../
for i in $(seq 10 20); do
    RAYON_NUM_THREADS=4 ./bench.sh expander keccak $i
    RAYON_NUM_THREADS=4 ./bench.sh expander poseidon $i
done
python3 render_table.py

可能的进一步优化

• hashcaster

  • 直接在 polyval 字段上使用 binius PCS
• • *

1. 8k 签名 * 每个签名 250 个哈希，在乐观情况下为 4 秒。↩︎

2. https://learnblockchain.cn/article/11633#starked-binary-hash-trees

https://ethresear.ch/t/proposal-delay-stateroot-reference-to-increase-throughput-and-reduce-latency/20490 ↩︎

• 原文链接： hackmd.io/@han/bench-has...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～