基于哈希的签名聚合

• 基于哈希的签名聚合
  • 1. 基于哈希的签名参数
  • 2. 方法 - zkVM
  • 2.1. 使用 succinctlabs/sp1 (基于 plonky3)
  • 2.2. 使用 openvm-org/openvm (基于 plonky3)
  • 3. 方法 - 电路
  • 3.1. 使用 plonky3

1. 基于哈希的签名参数

我们使用具有以下参数的 Poseidon2 实例：

• $\textbf{Lifetime}\ L = 2^{20}$
• $\textbf{Encoding} = \mathsf{TSW}$
• $w = 2$
• $\delta = 1$

可以在这里找到这个特定实例的实现。

2. 方法 - zkVM

2.1. 使用 succinctlabs/sp1 (基于 plonky3)

• 源代码：https://github.com/han0110/hash-sig-agg/tree/main/zkvm/sp1

2.2. 使用 openvm-org/openvm (基于 plonky3)

• 源代码：https://github.com/han0110/hash-sig-agg/tree/main/zkvm/openvm

3. 方法 - 电路

3.1. 使用 plonky3

• 源代码：https://github.com/han0110/hash-sig-agg/tree/feature/use-p3-uni-stark-ext/circuit

3.1.1. 介绍

为了有效地处理非统一计算，我们将电路拆分为多个 AIR 追踪，并使用查找来连接彼此的输入/输出。

AIR 追踪是：

• Main
• Chain
• MerkleTree
• Decomposition
• RangeCheck

3.1.1.1. Main

Main 主要用于同步其他 AIR 追踪，它做 3 件事：

1. 将 (sig_idx, msg_hash) 发送到 Decomposition，以确保 x 是从 msg_hash 分解出来的。
2. 将 (sig_idx, parameter) 发送到 Chain，以确保它与其他 AIR 追踪使用相同的 parameter。
3. 将 (sig_idx, parameter, msg_hash, merkle_root) 发送到 MerkleTree，以确保 msg_hash 是从与其他 AIR 追踪相同的 parameter 计算出来的，同时发送到期望的 merkle_root 以检查 sigs[sig_idx]。

parameter 和 merkle_root 部分是这个聚合电路的声明，验证者可以通过 FFT 在 \(O(n\log n)\) 的时间内计算它们的多项式求值。

3.1.1.2. Chain

Chain 从 Decomposition 接收 x（msg_hash 块），如果 i-th 链的 one_time_sig_i 尚未结束，则计算链的其余部分，然后将 one_time_pk_i 发送到 MerkleTree。

如果链已经结束，我们将忽略它，因此签名的行数可以是恒定的（等于目标和）。

一个 x = (0, 2, 1, 3, 3, 0, ..., 1, 3, 3) 的示例追踪可能如下所示：

3.1.1.3. MerkleTree

MerkleTree 接收 2 件事：

1. 它从 Chain 接收 one_time_pk_i，其中 x_i 尚未结束，并将它们与 one_time_pk_i（其中 x_i 已经结束）哈希到 merkle_leaf_hash 中，然后计算 merkle_root 以供稍后使用。
2. 它接收 (parameter, merkle_root, msg_hash) 作为同步，其中 merkle_root 是从 merkle_leaf_hash 和 siblings 计算出来的，parameter 用于所有可调整的哈希，msg_hash 是在下一个相邻行中单独计算的。

一个 epoch = 0b0...01 的示例追踪可能如下所示：

3.1.1.4. Decomposition

Decomposition 接收 msg_hash 作为 values，并计算

(((values[4] * P) + values[3]) * P + ...) * P + values[0]，然后将其分解为基 2w 块，并将非结束块发送到 Chain。

一个 x = (0, 2, 1, 3, 3, 0, ..., 1, 3, 3) 的示例追踪可能如下所示：

3.1.1.5. RangeCheck

RangeCheck 填充了范围 0..212，以从 Decomposition 接收 limb 作为范围检查。

3.1.1.6. chips 中使用的其他 gadget

有关更多详细信息，请参见 https://hackmd.io/@tcoratger/SyWbmVPckx。

3.1.2. 基准测试

• 机器配置
  • CPU：i9-13900K
  • 内存：64GB (2x Crucial DDR5 5600 32GB 双通道)
  • 操作系统：Linux 5.15.0-124-generic x86-64
• FRI 参数：
  • 扩展域位数：124（KoalaBear 的 4 度扩展）
  • 查询次数：256 / R
  • Merkle 树哈希：Poseidon2

该基准测试聚合了 8192 个签名，要重现，请在 <repo>/circuit 中运行以下脚本：

sh bench.sh
python3 render_table.py

R: Log 1/rate T: 线程数 PT: 证明时间 TP: 吞吐量 (sig/s) PS: 证明大小 PM: 峰值证明内存 VT: 验证时间

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