openvm_stark_backend/prover/cpu/
opener.rs

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

openvm_stark_backend/prover/cpu/
opener.rs
