p3_fri/
hiding_pcs.rs

Help
1use alloc::vec::Vec;
2use core::cell::RefCell;
3use core::fmt::Debug;
4
5use p3_challenger::{CanObserve, FieldChallenger, GrindingChallenger};
6use p3_commit::{Mmcs, OpenedValues, Pcs, TwoAdicMultiplicativeCoset};
7use p3_dft::TwoAdicSubgroupDft;
8use p3_field::{ExtensionField, Field, TwoAdicField};
9use p3_matrix::bitrev::BitReversalPerm;
10use p3_matrix::dense::{DenseMatrix, RowMajorMatrix};
11use p3_matrix::horizontally_truncated::HorizontallyTruncated;
12use p3_matrix::row_index_mapped::RowIndexMappedView;
13use p3_matrix::Matrix;
14use p3_util::zip_eq::zip_eq;
15use rand::distributions::{Distribution, Standard};
16use rand::Rng;
17use tracing::instrument;
18
19use crate::verifier::FriError;
20use crate::{BatchOpening, FriConfig, FriProof, TwoAdicFriPcs};
21
22/// A hiding FRI PCS. Both MMCSs must also be hiding; this is not enforced at compile time so it's
23/// the user's responsibility to configure.
24#[derive(Debug)]
25pub struct HidingFriPcs<Val, Dft, InputMmcs, FriMmcs, R> {
26    inner: TwoAdicFriPcs<Val, Dft, InputMmcs, FriMmcs>,
27    num_random_codewords: usize,
28    rng: RefCell<R>,
29}
30
31impl<Val, Dft, InputMmcs, FriMmcs, R> HidingFriPcs<Val, Dft, InputMmcs, FriMmcs, R> {
32    pub fn new(
33        dft: Dft,
34        mmcs: InputMmcs,
35        fri: FriConfig<FriMmcs>,
36        num_random_codewords: usize,
37        rng: R,
38    ) -> Self {
39        let inner = TwoAdicFriPcs::new(dft, mmcs, fri);
40        Self {
41            inner,
42            num_random_codewords,
43            rng: rng.into(),
44        }
45    }
46}
47
48impl<Val, Dft, InputMmcs, FriMmcs, Challenge, Challenger, R> Pcs<Challenge, Challenger>
49    for HidingFriPcs<Val, Dft, InputMmcs, FriMmcs, R>
50where
51    Val: TwoAdicField,
52    Standard: Distribution<Val>,
53    Dft: TwoAdicSubgroupDft<Val>,
54    InputMmcs: Mmcs<Val>,
55    FriMmcs: Mmcs<Challenge>,
56    Challenge: TwoAdicField + ExtensionField<Val>,
57    Challenger:
58        FieldChallenger<Val> + CanObserve<FriMmcs::Commitment> + GrindingChallenger<Witness = Val>,
59    R: Rng + Send + Sync,
60{
61    type Domain = TwoAdicMultiplicativeCoset<Val>;
62    type Commitment = InputMmcs::Commitment;
63    type ProverData = InputMmcs::ProverData<RowMajorMatrix<Val>>;
64    type EvaluationsOnDomain<'a> = HorizontallyTruncated<
65        Val,
66        RowIndexMappedView<BitReversalPerm, DenseMatrix<Val, &'a [Val]>>,
67    >;
68    /// The first item contains the openings of the random polynomials added by this wrapper.
69    /// The second item is the usual FRI proof.
70    type Proof = (
71        OpenedValues<Challenge>,
72        FriProof<Challenge, FriMmcs, Val, Vec<BatchOpening<Val, InputMmcs>>>,
73    );
74    type Error = FriError<FriMmcs::Error, InputMmcs::Error>;
75
76    fn natural_domain_for_degree(&self, degree: usize) -> Self::Domain {
77        <TwoAdicFriPcs<Val, Dft, InputMmcs, FriMmcs> as Pcs<Challenge, Challenger>>::natural_domain_for_degree(
78            &self.inner, degree)
79    }
80
81    fn commit(
82        &self,
83        evaluations: Vec<(Self::Domain, RowMajorMatrix<Val>)>,
84    ) -> (Self::Commitment, Self::ProverData) {
85        let randomized_evaluations = evaluations
86            .into_iter()
87            .map(|(domain, mat)| {
88                (
89                    domain,
90                    add_random_cols(mat, self.num_random_codewords, &mut *self.rng.borrow_mut()),
91                )
92            })
93            .collect();
94        <TwoAdicFriPcs<Val, Dft, InputMmcs, FriMmcs> as Pcs<Challenge, Challenger>>::commit(
95            &self.inner,
96            randomized_evaluations,
97        )
98    }
99
100    fn get_evaluations_on_domain<'a>(
101        &self,
102        prover_data: &'a Self::ProverData,
103        idx: usize,
104        domain: Self::Domain,
105    ) -> Self::EvaluationsOnDomain<'a> {
106        let inner_evals = <TwoAdicFriPcs<Val, Dft, InputMmcs, FriMmcs> as Pcs<
107            Challenge,
108            Challenger,
109        >>::get_evaluations_on_domain(
110            &self.inner, prover_data, idx, domain
111        );
112        let inner_width = inner_evals.width();
113        // Truncate off the columns representing random codewords we added in `commit` above.
114        HorizontallyTruncated::new(inner_evals, inner_width - self.num_random_codewords)
115    }
116
117    fn open(
118        &self,
119        // For each round,
120        rounds: Vec<(
121            &Self::ProverData,
122            // for each matrix,
123            Vec<
124                // points to open
125                Vec<Challenge>,
126            >,
127        )>,
128        challenger: &mut Challenger,
129    ) -> (OpenedValues<Challenge>, Self::Proof) {
130        let (mut inner_opened_values, inner_proof) = self.inner.open(rounds, challenger);
131
132        // inner_opened_values includes opened values for the random codewords. Those should be
133        // hidden from our caller, so we split them off and store them in the proof.
134        let opened_values_rand = inner_opened_values
135            .iter_mut()
136            .map(|opened_values_for_round| {
137                opened_values_for_round
138                    .iter_mut()
139                    .map(|opened_values_for_mat| {
140                        opened_values_for_mat
141                            .iter_mut()
142                            .map(|opened_values_for_point| {
143                                let split =
144                                    opened_values_for_point.len() - self.num_random_codewords;
145                                opened_values_for_point.drain(split..).collect()
146                            })
147                            .collect()
148                    })
149                    .collect()
150            })
151            .collect();
152
153        (inner_opened_values, (opened_values_rand, inner_proof))
154    }
155
156    fn verify(
157        &self,
158        // For each round:
159        mut rounds: Vec<(
160            Self::Commitment,
161            // for each matrix:
162            Vec<(
163                // its domain,
164                Self::Domain,
165                // for each point:
166                Vec<(
167                    // the point,
168                    Challenge,
169                    // values at the point
170                    Vec<Challenge>,
171                )>,
172            )>,
173        )>,
174        proof: &Self::Proof,
175        challenger: &mut Challenger,
176    ) -> Result<(), Self::Error> {
177        let (opened_values_for_rand_cws, inner_proof) = proof;
178        // Now we merge `opened_values_for_rand_cws` into the opened values in `rounds`, undoing
179        // the split that we did in `open`, to get a complete set of opened values for the inner PCS
180        // to check.
181        for (round, rand_round) in zip_eq(
182            rounds.iter_mut(),
183            opened_values_for_rand_cws,
184            FriError::InvalidProofShape,
185        )? {
186            for (mat, rand_mat) in
187                zip_eq(round.1.iter_mut(), rand_round, FriError::InvalidProofShape)?
188            {
189                for (point, rand_point) in
190                    zip_eq(mat.1.iter_mut(), rand_mat, FriError::InvalidProofShape)?
191                {
192                    point.1.extend(rand_point);
193                }
194            }
195        }
196        self.inner.verify(rounds, inner_proof, challenger)
197    }
198}
199
200#[instrument(level = "debug", skip_all)]
201fn add_random_cols<Val, R>(
202    mat: RowMajorMatrix<Val>,
203    num_random_codewords: usize,
204    mut rng: R,
205) -> RowMajorMatrix<Val>
206where
207    Val: Field,
208    R: Rng + Send + Sync,
209    Standard: Distribution<Val>,
210{
211    let old_w = mat.width();
212    let new_w = old_w + num_random_codewords;
213    let h = mat.height();
214
215    let new_values = Val::zero_vec(new_w * h);
216    let mut result = RowMajorMatrix::new(new_values, new_w);
217    // Can be parallelized by adding par_, but there are some complications with the RNG.
218    // We could just use thread_rng(), but ideally we want to keep it generic...
219    result
220        .rows_mut()
221        .zip(mat.row_slices())
222        .for_each(|(new_row, old_row)| {
223            new_row[..old_w].copy_from_slice(old_row);
224            new_row[old_w..].iter_mut().for_each(|v| *v = rng.gen());
225        });
226    result
227}
p3_fri/hiding_pcs.rs

p3_fri/
hiding_pcs.rs
