p3_commit/
testing.rs

Help
1use alloc::vec;
2use alloc::vec::Vec;
3use core::marker::PhantomData;
4
5use p3_challenger::CanSample;
6use p3_dft::TwoAdicSubgroupDft;
7use p3_field::{ExtensionField, Field, TwoAdicField};
8use p3_matrix::dense::RowMajorMatrix;
9use p3_matrix::Matrix;
10use p3_util::log2_strict_usize;
11use p3_util::zip_eq::zip_eq;
12use serde::{Deserialize, Serialize};
13
14use crate::{OpenedValues, Pcs, PolynomialSpace, TwoAdicMultiplicativeCoset};
15
16/// A trivial PCS: its commitment is simply the coefficients of each poly.
17#[derive(Debug)]
18pub struct TrivialPcs<Val: TwoAdicField, Dft: TwoAdicSubgroupDft<Val>> {
19    pub dft: Dft,
20    // degree bound
21    pub log_n: usize,
22    pub _phantom: PhantomData<Val>,
23}
24
25pub fn eval_coeffs_at_pt<F: Field, EF: ExtensionField<F>>(
26    coeffs: &RowMajorMatrix<F>,
27    x: EF,
28) -> Vec<EF> {
29    let mut acc = vec![EF::ZERO; coeffs.width()];
30    for r in (0..coeffs.height()).rev() {
31        let row = coeffs.row_slice(r);
32        for (acc_c, row_c) in acc.iter_mut().zip(row.as_ref().iter()) {
33            *acc_c *= x;
34            *acc_c += *row_c;
35        }
36    }
37    acc
38}
39
40impl<Val, Dft, Challenge, Challenger> Pcs<Challenge, Challenger> for TrivialPcs<Val, Dft>
41where
42    Val: TwoAdicField,
43    Challenge: ExtensionField<Val>,
44    Challenger: CanSample<Challenge>,
45
46    Dft: TwoAdicSubgroupDft<Val>,
47
48    Vec<Vec<Val>>: Serialize + for<'de> Deserialize<'de>,
49{
50    type Domain = TwoAdicMultiplicativeCoset<Val>;
51    type Commitment = Vec<Vec<Val>>;
52    type ProverData = Vec<RowMajorMatrix<Val>>;
53    type EvaluationsOnDomain<'a> = Dft::Evaluations;
54    type Proof = ();
55    type Error = ();
56
57    fn natural_domain_for_degree(&self, degree: usize) -> Self::Domain {
58        TwoAdicMultiplicativeCoset {
59            log_n: log2_strict_usize(degree),
60            shift: Val::ONE,
61        }
62    }
63
64    fn commit(
65        &self,
66        evaluations: Vec<(Self::Domain, RowMajorMatrix<Val>)>,
67    ) -> (Self::Commitment, Self::ProverData) {
68        let coeffs: Vec<_> = evaluations
69            .into_iter()
70            .map(|(domain, evals)| {
71                let log_domain_size = log2_strict_usize(domain.size());
72                // for now, only commit on larger domain than natural
73                assert!(log_domain_size >= self.log_n);
74                assert_eq!(domain.size(), evals.height());
75                // coset_idft_batch
76                let mut coeffs = self.dft.idft_batch(evals);
77                coeffs
78                    .rows_mut()
79                    .zip(domain.shift.inverse().powers())
80                    .for_each(|(row, weight)| {
81                        row.iter_mut().for_each(|coeff| {
82                            *coeff *= weight;
83                        })
84                    });
85                coeffs
86            })
87            .collect();
88        (
89            coeffs.clone().into_iter().map(|m| m.values).collect(),
90            coeffs,
91        )
92    }
93
94    fn get_evaluations_on_domain<'a>(
95        &self,
96        prover_data: &'a Self::ProverData,
97        idx: usize,
98        domain: Self::Domain,
99    ) -> Self::EvaluationsOnDomain<'a> {
100        let mut coeffs = prover_data[idx].clone();
101        assert!(domain.log_n >= self.log_n);
102        coeffs.values.resize(
103            coeffs.values.len() << (domain.log_n - self.log_n),
104            Val::ZERO,
105        );
106        self.dft.coset_dft_batch(coeffs, domain.shift)
107    }
108
109    fn open(
110        &self,
111        // For each round,
112        rounds: Vec<(
113            &Self::ProverData,
114            // for each matrix,
115            Vec<
116                // points to open
117                Vec<Challenge>,
118            >,
119        )>,
120        _challenger: &mut Challenger,
121    ) -> (OpenedValues<Challenge>, Self::Proof) {
122        (
123            rounds
124                .into_iter()
125                .map(|(coeffs_for_round, points_for_round)| {
126                    // ensure that each matrix corresponds to a set of opening points
127                    debug_assert_eq!(coeffs_for_round.len(), points_for_round.len());
128                    coeffs_for_round
129                        .iter()
130                        .zip(points_for_round)
131                        .map(|(coeffs_for_mat, points_for_mat)| {
132                            points_for_mat
133                                .into_iter()
134                                .map(|pt| eval_coeffs_at_pt(coeffs_for_mat, pt))
135                                .collect()
136                        })
137                        .collect()
138                })
139                .collect(),
140            (),
141        )
142    }
143
144    // This is a testing function, so we allow panics for convenience.
145    #[allow(clippy::panic_in_result_fn)]
146    fn verify(
147        &self,
148        // For each round:
149        rounds: Vec<(
150            Self::Commitment,
151            // for each matrix:
152            Vec<(
153                // its domain,
154                Self::Domain,
155                // for each point:
156                Vec<(
157                    Challenge,
158                    // values at this point
159                    Vec<Challenge>,
160                )>,
161            )>,
162        )>,
163        _proof: &Self::Proof,
164        _challenger: &mut Challenger,
165    ) -> Result<(), Self::Error> {
166        for (comm, round_opening) in rounds {
167            for (coeff_vec, (domain, points_and_values)) in zip_eq(comm, round_opening, ())? {
168                let width = coeff_vec.len() / domain.size();
169                assert_eq!(width * domain.size(), coeff_vec.len());
170                let coeffs = RowMajorMatrix::new(coeff_vec, width);
171                for (pt, values) in points_and_values {
172                    assert_eq!(eval_coeffs_at_pt(&coeffs, pt), values);
173                }
174            }
175        }
176        Ok(())
177    }
178}
p3_commit/testing.rs

p3_commit/
testing.rs
