区块链中的数学(八十三)-- MMCS(Mixed Matrix Commitment Scheme)

在零知识证明(如FRI、STARK等)和多项式承诺场景中,我们经常需要对多个矩阵的数据进行批量承诺和验证。

<!--StartFragment-->

写在前面

在零知识证明(如 FRI、STARK 等)和多项式承诺场景中,我们经常需要对多个矩阵的数据进行批量承诺和验证。传统的 Merkle Tree 主要用于向量(单列数据)的承诺,但在实际工程中,我们常常需要对不同高度、不同宽度的多个矩阵进行统一承诺和高效验证。\ 这就是 MMCS(Mixed Matrix Commitment Scheme,多矩阵承诺方案)的设计初衷。

接下来将系统介绍 MMCS 的原理、与 Merkle Tree 的结合方式、核心代码结构,并通过具体例子说明其用途。


1.  What is MMCS ?

MMCS(Mixed Matrix Commitment Scheme)是一种支持批量承诺多个矩阵的通用接口(trait),它的目标是:

  • 支持不同高度、不同宽度的矩阵一起承诺
  • 支持批量打开和验证
  • 高效、安全,适合零知识证明等高性能场景

在 Rust 代码中,MMCS 的 trait 定义如下:\ Note: 本文代码主要基于plonky3代码实现。

pub trait Mmcs&lt;T: Send + Sync>: Clone {
    type ProverData&lt;M>;
    type Commitment: Clone + Serialize + DeserializeOwned;
    type Proof: Clone + Serialize + DeserializeOwned;
    type Error: Debug;

    fn commit&lt;M: Matrix&lt;T>>(&self, inputs: Vec&lt;M>) -> (Self::Commitment, Self::ProverData&lt;M>);
    fn open_batch&lt;M: Matrix&lt;T>>(
        &self,
        index: usize,
        prover_data: &Self::ProverData&lt;M>,
    ) -> (Vec&lt;Vec&lt;T>>, Self::Proof);
    fn verify_batch(
        &self,
        commit: &Self::Commitment,
        dimensions: &[Dimensions],
        index: usize,
        opened_values: &[Vec&lt;T>],
        proof: &Self::Proof,
    ) -> Result&lt;(), Self::Error>;
}

2. Why MMCS ?

为什么要用 MMCS 而不是直接用 Merkle Tree PCS?传统 Merkle Tree 只适合对单个向量(一维数据)做承诺。如果直接用它来承诺多个矩阵,会遇到:

  • 需要管理多棵树,难以批量操作
  • 不同高度、宽度的矩阵难以统一索引和验证
  • 性能和接口都不友好

MMCS 通过抽象接口+灵活实现,让我们可以用一棵 Merkle Tree 承诺多个异构矩阵,并且支持批量打开和验证。


3. How MMCS + Merkle Tree

3.1 叶子节点的构造

  • 每个矩阵的每一行,作为一个叶子节点
  • 不同矩阵的行可以有不同长度(列数)
  • 每个叶子节点整体 hash(如 H([a11, a12, a13])

3.2 不同高度矩阵的"锯齿式"动态注入

  • 先把所有矩阵按高度从大到小排列
  • 构建 Merkle Tree 时,每一层如果有新高度的矩阵,就在该层"注入"它们的行 hash
  • 这样可以保证所有矩阵都被承诺到同一棵树里

3.3 索引对齐

  • 打开第 index 行时,每个矩阵要通过右移(>>)对齐到自己的实际行
  • 例如:最大高度为 4,B 只有 2 行,打开 index=1 时,B 实际取第 1 >> 1 = 0 行

4. Examples

4.1 单列矩阵

假设有:

  • A:4 行
  • B:2 行
  • C:1 行

打开 index=1 时:

  • A:取第 1 行(a2)
  • B:取第 1>>1=0 行(b1)
  • C:取第 1>>2=0 行(c1)

4.2 多列矩阵

假设有:

  • A:4×3
  • B:2×2
  • C:1×5

打开 index=1 时:

  • A:取 [a21, a22, a23]
  • B:取 [b11, b12]
  • C:取 [c11, c12, c13, c14, c15]

每一行整体 hash,作为叶子节点。


5. Merkle Tree build & injection

         ┌───────────── Root ─────────────┐
         │                               │
      compress(hA, hB)                H(c1)
       /           \                    
   hA              hB
  /  \            /  \
hA1  hA2      H(b1) H(b2)
 / \  / \
H(a1) H(a2) H(a3) H(a4)
  • hA1 = compress(H(a1), H(a2))
  • hA2 = compress(H(a3), H(a4))
  • hA = compress(hA1, hA2)
  • hB = compress(H(b1), H(b2))
  • Root = compress(hA, hB),再和 H(c1) 合成最终根

6. open_batch & verify_batch

open_batch

  • 输入:逻辑行索引 index
  • 输出:每个矩阵实际要打开的那一行数据 + Merkle proof
  • 过程:对每个矩阵,计算 reduced_index = index >> (log2(max_height) - log2(matrix.height)),取对应行

verify_batch

  • 输入:承诺(根 hash)、dimensions、index、opened_values、proof
  • 过程:对 opened_values 逐行 hash,和 proof 里的 sibling hash 逐层合成,最终比对根 hash 是否等于承诺

7. 不同宽度(列数)如何处理?

  • 每一行整体 hash,不管有几列
  • hash 函数必须支持变长输入(如 Poseidon、Blake3、SHA256 等)
  • Merkle Tree 的结构和 proof 逻辑不变

8. 代码片段(伪代码)

// 承诺
let (commitment, prover_data) = mmcs.commit(vec![matrix_a, matrix_b, matrix_c]);

// 打开第 index 行
let (opened_values, proof) = mmcs.open_batch(index, &prover_data);

// 验证
mmcs.verify_batch(&commitment, &dimensions, index, &opened_values, &proof)?;

9. 核心代码结构

9.1 MMCS Trait 定义

// commit/src/mmcs.rs
pubtrait Mmcs&lt;T: Send + Sync>: Clone {
    type ProverData&lt;M>;
    type Commitment: Clone + Serialize + DeserializeOwned;
    type Proof: Clone + Serialize + DeserializeOwned;
    type Error: Debug;

    fn commit&lt;M: Matrix&lt;T>>(&self, inputs: Vec&lt;M>) -> (Self::Commitment, Self::ProverData&lt;M>);
    fn open_batch&lt;M: Matrix&lt;T>>(
        &self,
        index: usize,
        prover_data: &Self::ProverData&lt;M>,
    ) -> (Vec&lt;Vec&lt;T>>, Self::Proof);
    fn verify_batch(
        &self,
        commit: &Self::Commitment,
        dimensions: &[Dimensions],
        index: usize,
        opened_values: &[Vec&lt;T>],
        proof: &Self::Proof,
    ) -> Result&lt;(), Self::Error>;
}

9.2 MerkleTreeMmcs 实现

// merkle-tree/src/mmcs.rs
impl&lt;P, PW, H, C, const DIGEST_ELEMS: usize> Mmcs&lt;P::Value>
    for MerkleTreeMmcs&lt;P, PW, H, C, DIGEST_ELEMS>
{
    type ProverData&lt;M> = MerkleTree&lt;P::Value, PW::Value, M, DIGEST_ELEMS>;
    type Commitment = Hash&lt;P::Value, PW::Value, DIGEST_ELEMS>;
    type Proof = Vec&lt;[PW::Value; DIGEST_ELEMS]>;
    type Error = MerkleTreeError;

    fn commit&lt;M: Matrix&lt;P::Value>>(
        &self,
        inputs: Vec&lt;M>,
    ) -> (Self::Commitment, Self::ProverData&lt;M>) {
        let tree = MerkleTree::new::&lt;P, PW, H, C>(&self.hash, &self.compress, inputs);
        let root = tree.root();
        (root, tree)
    }

    fn open_batch&lt;M: Matrix&lt;P::Value>>(
        &self,
        index: usize,
        prover_data: &MerkleTree&lt;P::Value, PW::Value, M, DIGEST_ELEMS>,
    ) -> (Vec&lt;Vec&lt;P::Value>>, Vec&lt;[PW::Value; DIGEST_ELEMS]>) {
        let max_height = self.get_max_height(prover_data);
        let log_max_height = log2_ceil_usize(max_height);

        let openings = prover_data
            .leaves
            .iter()
            .map(|matrix| {
                let log2_height = log2_ceil_usize(matrix.height());
                let bits_reduced = log_max_height - log2_height;
                let reduced_index = index >> bits_reduced;
                matrix.row(reduced_index).collect()
            })
            .collect_vec();

        let proof: Vec&lt;_> = (0..log_max_height)
            .map(|i| prover_data.digest_layers[i][(index >> i) ^ 1])
            .collect();

        (openings, proof)
    }
}

9.3 MerkleTree 数据结构

// merkle-tree/src/merkle_tree.rs
#[derive(Debug, Serialize, Deserialize)]
pub struct MerkleTree&lt;F, W, M, const DIGEST_ELEMS: usize> {
    pub(crate) leaves: Vec&lt;M>,
    pub(crate) digest_layers: Vec&lt;Vec&lt;[W; DIGEST_ELEMS]>>,
    _phantom: PhantomData&lt;F>,
}

10. 实际应用场景

10.1 在 FRI 协议中的应用

// fri/src/two_adic_pcs.rs
pub struct TwoAdicFriPcs&lt;Val, Dft, InputMmcs, FriMmcs> {
    dft: Dft,
    mmcs: InputMmcs,  // 通常是 MerkleTreeMmcs
    fri: FriConfig&lt;FriMmcs>,
    _phantom: PhantomData&lt;Val>,
}

impl&lt;Val, Dft, InputMmcs, FriMmcs> TwoAdicFriPcs&lt;Val, Dft, InputMmcs, FriMmcs> {
    fn commit(&self, evaluations: Vec&lt;(Self::Domain, RowMajorMatrix&lt;Val>)>) -> (Self::Commitment, Self::ProverData) {
        // 使用 MMCS 进行承诺
        self.mmcs.commit(ldes)
    }
}

10.2 在 STARK 中的应用

// 多个多项式评估的批量承诺
let fri_polynomials = vec![
    (domain1, trace_matrix),      // 执行轨迹
    (domain2, constraint_matrix), // 约束多项式
    (domain3, quotient_matrix),   // 商多项式
];

// 使用 MMCS 一次性承诺所有多项式
let (commitment, prover_data) = mmcs.commit(polynomial_matrices);

11. 性能优化

11.1 并行处理

// merkle-tree/src/merkle_tree.rs
digests[0..max_height]
    .par_chunks_exact_mut(width)
    .enumerate()
    .for_each(|(i, digests_chunk)| {
        // 并行计算哈希
        let packed_digest: [PW; DIGEST_ELEMS] = h.hash_iter(
            tallest_matrices
                .iter()
                .flat_map(|m| m.vertically_packed_row(first_row)),
        );
    });

11.2 打包操作

// 支持字段打包,提高内存效率
let packed_digest: [PW; DIGEST_ELEMS] = h.hash_iter(
    tallest_matrices
        .iter()
        .flat_map(|m| m.vertically_packed_row(first_row)),
);

12. 常见问题解答

Q1:MMCS 和 Merkle Tree 是什么关系?

  • MMCS 是抽象接口,Merkle Tree 是一种高效的具体实现。

Q2:为什么不用多个 Merkle Tree?

  • 多个树难以批量操作和统一索引,MMCS 让一棵树就能承诺所有矩阵。

Q3:索引对齐是怎么工作的?

  • 通过右移操作(>>)将逻辑索引映射到每个矩阵的实际行索引。这一点是跟单个Merkle Tree承诺很不同的操作, 是因为多个矩阵可能具有不能的高度(或者称为行数),这个操作决定了每个矩阵在Merkle Tree中的哪一层layer。着就是伪代码中有个dimension结构, 保存了每个matrix的维度信息。

13. 小结

MMCS + Merkle Tree 的设计极大提升了多矩阵承诺的灵活性和效率,主要优势包括:

  1. 统一接口:支持不同高度、宽度的矩阵批量承诺
  2. 高效验证:一棵树支持所有矩阵的批量打开和验证,这种设计比单纯的使用多个Merkle Tree 承诺要高效
  3. 性能优化:支持并行处理和字段打包
  4. 安全性:基于成熟的 Merkle Tree 密码学原理

参考资料

  • [Plonky3 GitHub Repository](https\://github.com/0xPolygonZero/plonky3)
  • [Merkle Tree Wikipedia](https\://en.wikipedia.org/wiki/Merkle_tree)
  • [FRI Protocol Paper](https\://eprint.iacr.org/2017/573)
  • [STARK Protocol Paper](https\://eprint.iacr.org/2018/046)

<!--EndFragment-->

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
blocksight
blocksight
江湖只有他的大名,没有他的介绍。