区块链中的数学(八十三)-- 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<T: Send + Sync>: Clone {
type ProverData<M>;
type Commitment: Clone + Serialize + DeserializeOwned;
type Proof: Clone + Serialize + DeserializeOwned;
type Error: Debug;
fn commit<M: Matrix<T>>(&self, inputs: Vec<M>) -> (Self::Commitment, Self::ProverData<M>);
fn open_batch<M: Matrix<T>>(
&self,
index: usize,
prover_data: &Self::ProverData<M>,
) -> (Vec<Vec<T>>, Self::Proof);
fn verify_batch(
&self,
commit: &Self::Commitment,
dimensions: &[Dimensions],
index: usize,
opened_values: &[Vec<T>],
proof: &Self::Proof,
) -> Result<(), 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<T: Send + Sync>: Clone {
type ProverData<M>;
type Commitment: Clone + Serialize + DeserializeOwned;
type Proof: Clone + Serialize + DeserializeOwned;
type Error: Debug;
fn commit<M: Matrix<T>>(&self, inputs: Vec<M>) -> (Self::Commitment, Self::ProverData<M>);
fn open_batch<M: Matrix<T>>(
&self,
index: usize,
prover_data: &Self::ProverData<M>,
) -> (Vec<Vec<T>>, Self::Proof);
fn verify_batch(
&self,
commit: &Self::Commitment,
dimensions: &[Dimensions],
index: usize,
opened_values: &[Vec<T>],
proof: &Self::Proof,
) -> Result<(), Self::Error>;
}
9.2 MerkleTreeMmcs 实现
// merkle-tree/src/mmcs.rs
impl<P, PW, H, C, const DIGEST_ELEMS: usize> Mmcs<P::Value>
for MerkleTreeMmcs<P, PW, H, C, DIGEST_ELEMS>
{
type ProverData<M> = MerkleTree<P::Value, PW::Value, M, DIGEST_ELEMS>;
type Commitment = Hash<P::Value, PW::Value, DIGEST_ELEMS>;
type Proof = Vec<[PW::Value; DIGEST_ELEMS]>;
type Error = MerkleTreeError;
fn commit<M: Matrix<P::Value>>(
&self,
inputs: Vec<M>,
) -> (Self::Commitment, Self::ProverData<M>) {
let tree = MerkleTree::new::<P, PW, H, C>(&self.hash, &self.compress, inputs);
let root = tree.root();
(root, tree)
}
fn open_batch<M: Matrix<P::Value>>(
&self,
index: usize,
prover_data: &MerkleTree<P::Value, PW::Value, M, DIGEST_ELEMS>,
) -> (Vec<Vec<P::Value>>, Vec<[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<_> = (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<F, W, M, const DIGEST_ELEMS: usize> {
pub(crate) leaves: Vec<M>,
pub(crate) digest_layers: Vec<Vec<[W; DIGEST_ELEMS]>>,
_phantom: PhantomData<F>,
}
10. 实际应用场景
10.1 在 FRI 协议中的应用
// fri/src/two_adic_pcs.rs
pub struct TwoAdicFriPcs<Val, Dft, InputMmcs, FriMmcs> {
dft: Dft,
mmcs: InputMmcs, // 通常是 MerkleTreeMmcs
fri: FriConfig<FriMmcs>,
_phantom: PhantomData<Val>,
}
impl<Val, Dft, InputMmcs, FriMmcs> TwoAdicFriPcs<Val, Dft, InputMmcs, FriMmcs> {
fn commit(&self, evaluations: Vec<(Self::Domain, RowMajorMatrix<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 的设计极大提升了多矩阵承诺的灵活性和效率,主要优势包括:
- 统一接口:支持不同高度、宽度的矩阵批量承诺
- 高效验证:一棵树支持所有矩阵的批量打开和验证,这种设计比单纯的使用多个Merkle Tree 承诺要高效
- 性能优化:支持并行处理和字段打包
- 安全性:基于成熟的 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-->