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

p3_commit/
mmcs.rs
