在Plonky3中构建默克尔树AIR脚本的教程 - HashCloak

Alex

密码学工程师

2026年4月30日

Plonky3 是一个工具包，包含用于实现多项式 IOP（PIOP）的原语（例如多项式承诺方案）。虽然它主要设计用于实现基于 STARK 的 zkVM，但我们发现，通过实现一个简单的 AIR 脚本来理解 Plonky3 的工作原理是很有帮助的。我们使用 Plonky3 仓库 中提供的 Poseidon2 哈希 AIR 脚本，实现了一个 Merkle 树 AIR 脚本。Merkle 树 AIR 脚本的实现可以在这里找到。

在这篇文章中，我们将主要介绍 Merkle 树 AIR 脚本的实现，以及如何使用 SubAirBuilder 将其他 AIR 脚本（本例中的 Poseidon2）集成到我们的脚本中。对于希望了解 Plonky3 其他部分的读者，我们还推荐 Brian Seong 的 Fibonacci AIR 示例 以及 Awesome Plonky3 中的其他资源。

什么是 Merkle 树？

首先，让我们定义在这个例子中将使用的 Merkle 树。在我们的 AIR 脚本中，目标是通过 Merkle 证明来证明一个节点是 Merkle 树的成员。

例如，如果我们想证明 L2 是 Merkle 树的一部分，我们生成一个证明，表明我们知道一个 Merkle 证明（Hash0-0 和 Hash1），同时公开输入 Hash0-1（即 L2 的哈希值），通过从叶子到树根进行哈希计算，可以生成一个与 Top Hash（也是一个公开输入）匹配的根。我们通过检查 H(H(Hash0-0, Hash0-1),Hash1) == Top Hash 是否成立来验证 Merkle 证明。

定义 AIR 脚本

现在，我们来定义 Plonky3 AIR 脚本，即我们的主程序。将这个脚本看作一台带有内存（或 CPU 中的寄存器）的证明机器，它保存了我们所有的证明数据（包括证明过程中的中间结果）。我们的目标是设计最适合我们需求的内存布局。内存布局是一个矩阵，其中一行代表我们程序中的一次迭代。我们还将定义约束，这些约束将应用于每一行，稍后我们会看到。

我们的 AIR 脚本包含三个主要部分。首先是一个主结构体，定义了证明所需的所有数据（见证、公开输入……）。我们的内存布局是一个 n x m 矩阵，其中每一行对应 Merkle 树中的一次哈希迭代。第二是一个 eval() 函数，定义了每次迭代的约束。第三是一个 generate_merkle_proof_trace() 函数，它将生成 Merkle 证明并用见证填充内存矩阵。

pub struct MerkleTreeAir {
    pub root: u32,
    pub leaf_value: u32,
    pub poseidon2_air: Poseidon2Air<
        BabyBear,
        GenericPoseidon2LinearLayersBabyBear,
        WIDTH,
        SBOX_DEGREE,
        SBOX_REGISTERS,
        HALF_FULL_ROUNDS,
        PARTIAL_ROUNDS,
    >,
}
impl<F: Field> BaseAir<F> for MerkleTreeAir {
    fn width(&self) -> usize {
        // is_odd_index + Poseidon2Col2（包括 current_node 和 Merkle 证明的 sibling）
        self.poseidon2_air.width() + 1
    }
}

这里，我们定义了主结构体 MerkleTreeAir。它包含 root 和 leaf_value 作为公开输入。这里我们只是将它们硬编码到约束中。我们也可以使用 AirBuilder 中的 public_values() 函数，这样证明者可以为每个证明提供不同的公开输入。我们还将 Poseidon2Air 脚本包含在主结构体中，因为我们将用它来证明 Merkle 树中哈希的正确性。这里的 width() 函数将返回内存矩阵的宽度。我们程序中的每一行定义如下：

我们将第一个内存槽定义为一个布尔标志，指示当前节点（可以是叶子或其祖先）在与 Merkle 证明进行哈希时，其索引是奇数还是偶数。即，如果叶子的索引是奇数，则哈希输入将是 H(merkle_proof[0], leaf)。第二个到最后一个内存槽用于 Poseidon2 AIR 脚本，包括左输入、右输入、哈希输出以及哈希函数中使用的所有中间数据。如我们所见，行的宽度正好是 poseidon2_air.width() + 1。

约束

接下来，让我们在 eval() 函数中定义约束。我们使用 AirBuilder trait 来帮助我们构建 AIR 脚本。它允许我们访问内存矩阵并定义约束。我们使用 main.row_slice() 来访问每一行，其中索引 0 表示当前迭代的行，1 表示下一次迭代的行。

impl<AB: AirBuilder<F = BabyBear>> Air<AB> for MerkleTreeAir {
    fn eval(&self, builder: &mut AB) {
        let main = builder.main();
        // 当前行
        let local = main.row_slice(0).unwrap();
        // 下一行
        let next = main.row_slice(1).unwrap();

        ...
        // 在此添加约束
    }

我们 AIR 脚本所需的约束如下：

1. 下一次哈希函数的左输入或右输入应该是当前迭代的哈希输出。如果 is_odd_index 为 true，则输入应为 H(merkle_proof, hash_output[i-1])，否则应为 H(hash_output[i-1], merkle_proof)。

如下所示，我们首先使用辅助函数获取哈希结果。然后，我们通过 next[0] * (约束) + (1 - next[0]) * (约束) 来实现 if 条件。next[0] 是下一次迭代的 is_odd_index 标志。builder.when_transition() 表示此条件将应用于除最后一行之外的所有行。

// 使用 Poseidon2Cols 的辅助函数获取哈希结果
// 将切片转换为 Poseidon2Cols（从第 1 列开始）
let p2_cols: &Poseidon2Cols<
    _,
    WIDTH,
    SBOX_DEGREE,
    SBOX_REGISTERS,
    HALF_FULL_ROUNDS,
    PARTIAL_ROUNDS,
> = local[1..].borrow();
let hash_output = p2_cols.ending_full_rounds[HALF_FULL_ROUNDS - 1].post[0];

// 约束：哈希输出 == 下一行的左输入（col[1]）或右输入（col[2]）
// 根据 is_odd_index（col[0]）决定
builder.when_transition().assert_zero(
    (next[0] * (hash_output - next[2]))
        + ((AB::Expr::ONE - next[0]) * (hash_output - next[1])),
);

2. 哈希函数的第一个左输入或右输入应与公开输入中的 leaf_value 匹配。

// 约束：第一个左输入（col[1]）或右输入（col[2]）应为 leaf_value，根据
// is_odd_index（col[0]）决定
builder.when_first_row().assert_zero(
    (local[0] * (AB::Expr::from_u32(self.leaf_value) - local[2]))
        + ((AB::Expr::ONE - local[0])
        * (AB::Expr::from_u32(self.leaf_value) - local[1])),
);

3. 每一行中的 is_odd_index 应为 0 或 1。

// 约束：is_odd 应为布尔值
builder.when_transition().assert_bool(local[0].clone());
builder.when_last_row().assert_bool(local[0].clone());

4. 最后一个哈希输出应与公开输入中的根匹配。

// 约束：最终输出 == root
let root = AB::Expr::from_u32(self.root);
builder.when_last_row().assert_eq(root, hash_output);

除了检查 Merkle 树的约束，我们还需要检查 Poseidon2 哈希函数的约束。我们将使用 SubAirBuilder 来访问另一个 AIR 脚本，并且只向子 AIR 脚本暴露内存矩阵的一部分（这里是 column[1..]）。在 eval 函数中，我们添加：

// 创建 Poseidon2 子 AIR 来评估 Poseidon2 哈希
// 给定输入为列范围 [1..]
let p2_col_count = self.poseidon2_air.width();
let mut sub: SubAirBuilder<AB, Poseidon2AirType, AB::Var> =
    SubAirBuilder::new(builder, 1..1 + p2_col_count);
self.poseidon2_air.eval(&mut sub);

放在内存矩阵的图中，应该看起来像这样：

生成轨迹

在定义好 AIR 脚本之后，我们现在将生成证明见证并如上所述填充内存矩阵。我们定义了一个 generate_merkle_proof_trace() 函数，该函数首先生成 Merkle 证明，然后返回一个填充了满足上述约束的见证的 RowMajorMatrix。

除了 Merkle 证明，我们还需要为 Poseidon2 哈希生成轨迹，以填充矩阵的第二列到最后一列。为此，我们将使用 poseidon2_air 库中的 generate_trace_rows() 函数，该函数将计算哈希结果并返回一行，其中包含我们需要填充矩阵的轨迹。

完整的函数请参见我们的 github 仓库。

运行 ZK 系统

现在所有准备工作都已就绪，我们可以开始配置并运行 ZK 系统了。这里我们不详细介绍 Plonky3 的配置，请参考 Fibonacci AIR 示例 了解有关设置的更多细节。在我们的示例中，我们使用了 Plonky3 的 poseidon2-air 示例 中的配置。

• 原文链接： hashcloak.com/blog/a-tut...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～