openvm_stark_backend/prover/cpu/
opener.rs

Help
1use std::fmt::Debug;
2
3use itertools::Itertools;
4use p3_commit::{Pcs, PolynomialSpace};
5use tracing::instrument;
6
7use crate::{
8    config::{Domain, PcsProof, PcsProverData, StarkGenericConfig},
9    proof::{AdjacentOpenedValues, OpenedValues, OpeningProof},
10};
11
12pub struct OpeningProver<'pcs, SC: StarkGenericConfig> {
13    pcs: &'pcs SC::Pcs,
14    zeta: SC::Challenge,
15}
16
17impl<'pcs, SC: StarkGenericConfig> OpeningProver<'pcs, SC> {
18    pub fn new(pcs: &'pcs SC::Pcs, zeta: SC::Challenge) -> Self {
19        Self { pcs, zeta }
20    }
21
22    /// Opening proof for multiple RAP matrices, where
23    /// - (for now) each preprocessed trace matrix has a separate commitment
24    /// - main trace matrices can have multiple commitments
25    /// - for each after_challenge phase, all matrices in the phase share a commitment
26    /// - quotient poly chunks are all committed together
27    #[instrument(name = "PCS opening proofs", skip_all)]
28    pub fn open(
29        &self,
30        challenger: &mut SC::Challenger,
31        // For each preprocessed trace commitment, the prover data and
32        // the domain of the matrix, in order
33        preprocessed: Vec<(&PcsProverData<SC>, Domain<SC>)>,
34        // For each main trace commitment, the prover data and
35        // the domain of each matrix, in order
36        main: Vec<(&PcsProverData<SC>, Vec<Domain<SC>>)>,
37        // after_challenge[i] has shared commitment prover data for all matrices in that phase, and domains of those matrices, in order
38        after_challenge: Vec<(&PcsProverData<SC>, Vec<Domain<SC>>)>,
39        // Quotient poly commitment prover data
40        quotient_data: &PcsProverData<SC>,
41        // Quotient degree for each RAP committed in quotient_data, in order
42        quotient_degrees: &[u8],
43    ) -> OpeningProof<PcsProof<SC>, SC::Challenge> {
44        let preprocessed: Vec<_> = preprocessed
45            .into_iter()
46            .map(|(data, domain)| (data, vec![domain]))
47            .collect();
48
49        let zeta = self.zeta;
50        let mut rounds = preprocessed
51            .iter()
52            .chain(main.iter())
53            .chain(after_challenge.iter())
54            .map(|(data, domains)| {
55                let points_per_mat = domains
56                    .iter()
57                    .map(|domain| vec![zeta, domain.next_point(zeta).unwrap()])
58                    .collect_vec();
59                (*data, points_per_mat)
60            })
61            .collect_vec();
62
63        // open every quotient chunk at zeta
64        let num_chunks = quotient_degrees.iter().sum::<u8>() as usize;
65        let quotient_opening_points = vec![vec![zeta]; num_chunks];
66        rounds.push((quotient_data, quotient_opening_points));
67
68        let (mut opening_values, opening_proof) = self.pcs.open(rounds, challenger);
69
70        // Unflatten opening_values
71        let mut quotient_openings = opening_values.pop().expect("Should have quotient opening");
72
73        let num_after_challenge = after_challenge.len();
74        let after_challenge_openings = opening_values
75            .split_off(opening_values.len() - num_after_challenge)
76            .into_iter()
77            .map(collect_trace_openings)
78            .collect_vec();
79        assert_eq!(
80            after_challenge_openings.len(),
81            num_after_challenge,
82            "Incorrect number of after challenge trace openings"
83        );
84
85        let main_openings = opening_values
86            .split_off(preprocessed.len())
87            .into_iter()
88            .map(collect_trace_openings)
89            .collect_vec();
90        assert_eq!(
91            main_openings.len(),
92            main.len(),
93            "Incorrect number of main trace openings"
94        );
95
96        let preprocessed_openings = opening_values
97            .into_iter()
98            .map(|values| {
99                let mut openings = collect_trace_openings(values);
100                openings
101                    .pop()
102                    .expect("Preprocessed trace should be opened at 1 point")
103            })
104            .collect_vec();
105        assert_eq!(
106            preprocessed_openings.len(),
107            preprocessed.len(),
108            "Incorrect number of preprocessed trace openings"
109        );
110
111        // Unflatten quotient openings
112        let quotient_openings = quotient_degrees
113            .iter()
114            .map(|&chunk_size| {
115                quotient_openings
116                    .drain(..chunk_size as usize)
117                    .map(|mut op| {
118                        op.pop()
119                            .expect("quotient chunk should be opened at 1 point")
120                    })
121                    .collect_vec()
122            })
123            .collect_vec();
124
125        OpeningProof {
126            proof: opening_proof,
127            values: OpenedValues {
128                preprocessed: preprocessed_openings,
129                main: main_openings,
130                after_challenge: after_challenge_openings,
131                quotient: quotient_openings,
132            },
133        }
134    }
135}
136
137fn collect_trace_openings<Challenge: Debug>(
138    ops: Vec<Vec<Vec<Challenge>>>,
139) -> Vec<AdjacentOpenedValues<Challenge>> {
140    ops.into_iter()
141        .map(|op| {
142            let [local, next] = op.try_into().expect("Should have 2 openings");
143            AdjacentOpenedValues { local, next }
144        })
145        .collect()
146}
openvm_stark_backend/prover/cpu/opener.rs

openvm_stark_backend/prover/cpu/
opener.rs
