在零知识证明(如FRI、STARK等)和多项式承诺场景中,我们经常需要对多个矩阵的数据进行批量承诺和验证。
<!--StartFragment-->
在零知识证明(如 FRI、STARK 等)和多项式承诺场景中,我们经常需要对多个矩阵的数据进行批量承诺和验证。传统的 Merkle Tree 主要用于向量(单列数据)的承诺,但在实际工程中,我们常常需要对不同高度、不同宽度的多个矩阵进行统一承诺和高效验证。\ 这就是 MMCS(Mixed Matrix Commitment Scheme,多矩阵承诺方案)的设计初衷。
接下来将系统介绍 MMCS 的原理、与 Merkle Tree 的结合方式、核心代码结构,并通过具体例子说明其用途。
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>;
}
为什么要用 MMCS 而不是直接用 Merkle Tree PCS?传统 Merkle Tree 只适合对单个向量(一维数据)做承诺。如果直接用它来承诺多个矩阵,会遇到:
MMCS 通过抽象接口+灵活实现,让我们可以用一棵 Merkle Tree 承诺多个异构矩阵,并且支持批量打开和验证。
H([a11, a12, a13])
)index
行时,每个矩阵要通过右移(>>
)对齐到自己的实际行1 >> 1 = 0
行假设有:
打开 index=1 时:
假设有:
打开 index=1 时:
[a21, a22, a23]
[b11, b12]
[c11, c12, c13, c14, c15]
每一行整体 hash,作为叶子节点。
┌───────────── Root ─────────────┐
│ │
compress(hA, hB) H(c1)
/ \
hA hB
/ \ / \
hA1 hA2 H(b1) H(b2)
/ \ / \
H(a1) H(a2) H(a3) H(a4)
// 承诺
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)?;
// 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>;
}
// 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)
}
}
// 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>,
}
// 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)
}
}
// 多个多项式评估的批量承诺
let fri_polynomials = vec![
(domain1, trace_matrix), // 执行轨迹
(domain2, constraint_matrix), // 约束多项式
(domain3, quotient_matrix), // 商多项式
];
// 使用 MMCS 一次性承诺所有多项式
let (commitment, prover_data) = mmcs.commit(polynomial_matrices);
// 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)),
);
});
// 支持字段打包,提高内存效率
let packed_digest: [PW; DIGEST_ELEMS] = h.hash_iter(
tallest_matrices
.iter()
.flat_map(|m| m.vertically_packed_row(first_row)),
);
MMCS + Merkle Tree 的设计极大提升了多矩阵承诺的灵活性和效率,主要优势包括:
<!--EndFragment-->
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!