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

openvm_stark_backend/prover/cpu/
opener.rs
