p3_commit/
mmcs.rs

1use alloc::vec;
2use alloc::vec::Vec;
3use core::fmt::Debug;
4
5use p3_matrix::dense::RowMajorMatrix;
6use p3_matrix::{Dimensions, Matrix};
7use serde::de::DeserializeOwned;
8use serde::Serialize;
9
10/// A "Mixed Matrix Commitment Scheme" (MMCS) is a generalization of a vector commitment scheme.
11///
12/// It supports committing to matrices and then opening rows. It is also batch-oriented; one can commit
13/// to a batch of matrices at once even if their widths and heights differ.
14///
15/// When a particular row index is opened, it is interpreted directly as a row index for matrices
16/// with the largest height. For matrices with smaller heights, some bits of the row index are
17/// removed (from the least-significant side) to get the effective row index. These semantics are
18/// useful in the FRI protocol. See the documentation for `open_batch` for more details.
19pub trait Mmcs<T: Send + Sync>: Clone {
20    type ProverData<M>;
21    type Commitment: Clone + Serialize + DeserializeOwned;
22    type Proof: Clone + Serialize + DeserializeOwned;
23    type Error: Debug;
24
25    fn commit<M: Matrix<T>>(&self, inputs: Vec<M>) -> (Self::Commitment, Self::ProverData<M>);
26
27    fn commit_matrix<M: Matrix<T>>(&self, input: M) -> (Self::Commitment, Self::ProverData<M>) {
28        self.commit(vec![input])
29    }
30
31    fn commit_vec(&self, input: Vec<T>) -> (Self::Commitment, Self::ProverData<RowMajorMatrix<T>>)
32    where
33        T: Clone + Send + Sync,
34    {
35        self.commit_matrix(RowMajorMatrix::new_col(input))
36    }
37
38    /// Opens a batch of rows from committed matrices
39    /// returns `(openings, proof)`
40    /// where `openings` is a vector whose `i`th element is the `j`th row of the ith matrix `M[i]`,
41    /// and `j = index >> (log2_ceil(max_height) - log2_ceil(M[i].height))`.
42    fn open_batch<M: Matrix<T>>(
43        &self,
44        index: usize,
45        prover_data: &Self::ProverData<M>,
46    ) -> (Vec<Vec<T>>, Self::Proof);
47
48    /// Get the matrices that were committed to.
49    fn get_matrices<'a, M: Matrix<T>>(&self, prover_data: &'a Self::ProverData<M>) -> Vec<&'a M>;
50
51    fn get_matrix_heights<M: Matrix<T>>(&self, prover_data: &Self::ProverData<M>) -> Vec<usize> {
52        self.get_matrices(prover_data)
53            .iter()
54            .map(|matrix| matrix.height())
55            .collect()
56    }
57
58    /// Get the largest height of any committed matrix.
59    fn get_max_height<M: Matrix<T>>(&self, prover_data: &Self::ProverData<M>) -> usize {
60        self.get_matrix_heights(prover_data)
61            .into_iter()
62            .max()
63            .unwrap_or_else(|| panic!("No committed matrices?"))
64    }
65
66    /// Verify a batch opening.
67    /// `index` is the row index we're opening for each matrix, following the same
68    /// semantics as `open_batch`.
69    /// `dimensions` is a slice whose ith element is the dimensions of the matrix being opened
70    /// in the ith opening
71    fn verify_batch(
72        &self,
73        commit: &Self::Commitment,
74        dimensions: &[Dimensions],
75        index: usize,
76        opened_values: &[Vec<T>],
77        proof: &Self::Proof,
78    ) -> Result<(), Self::Error>;
79}
p3_commit/mmcs.rs

p3_commit/
mmcs.rs
