stwo_gpu/core/pcs/
verifier.rs

1use core::iter::zip;
2
3use itertools::Itertools;
4use std_shims::Vec;
5
6use super::super::circle::CirclePoint;
7use super::super::fields::qm31::SecureField;
8use super::super::fri::{CirclePolyDegreeBound, FriVerifier};
9use super::quotients::{fri_answers, PointSample};
10use super::utils::TreeVec;
11use super::PcsConfig;
12use crate::core::channel::{Channel, MerkleChannel};
13use crate::core::pcs::quotients::CommitmentSchemeProof;
14use crate::core::pcs::utils::prepare_preprocessed_query_positions;
15use crate::core::vcs_lifted::merkle_hasher::MerkleHasherLifted;
16use crate::core::vcs_lifted::verifier::MerkleVerifierLifted;
17use crate::core::verifier::VerificationError;
18use crate::core::ColumnVec;
19
20/// The verifier side of a FRI polynomial commitment scheme. See [super].
21#[derive(Default)]
22pub struct CommitmentSchemeVerifier<MC: MerkleChannel> {
23    pub trees: TreeVec<MerkleVerifierLifted<MC::H>>,
24    pub config: PcsConfig,
25}
26
27impl<MC: MerkleChannel> CommitmentSchemeVerifier<MC> {
28    pub fn new(config: PcsConfig) -> Self {
29        Self {
30            trees: TreeVec::default(),
31            config,
32        }
33    }
34
35    /// A [TreeVec<ColumnVec>] of the log sizes of each column in each commitment tree.
36    fn column_log_sizes(&self) -> TreeVec<ColumnVec<u32>> {
37        self.trees
38            .as_ref()
39            .map(|tree| tree.column_log_sizes.clone())
40    }
41
42    /// Reads a commitment from the prover.
43    pub fn commit(
44        &mut self,
45        commitment: <MC::H as MerkleHasherLifted>::Hash,
46        log_sizes: &[u32],
47        channel: &mut MC::C,
48    ) {
49        MC::mix_root(channel, commitment);
50        let extended_log_sizes = log_sizes
51            .iter()
52            .map(|&log_size| log_size + self.config.fri_config.log_blowup_factor)
53            .collect();
54        let verifier = MerkleVerifierLifted::new(commitment, extended_log_sizes);
55        self.trees.push(verifier);
56    }
57
58    pub fn verify_values(
59        &self,
60        sampled_points: TreeVec<ColumnVec<Vec<CirclePoint<SecureField>>>>,
61        proof: CommitmentSchemeProof<MC::H>,
62        channel: &mut MC::C,
63    ) -> Result<(), VerificationError> {
64        channel.mix_felts(&proof.sampled_values.clone().flatten_cols());
65        let random_coeff = channel.draw_secure_felt();
66        // The lifting log size is the length of the longest column which has at least one sample
67        // (i.e. a column which is actually used in the constraints). Usually, the only columns
68        // that have an empty vector of samples are among the preprocessed columns.
69        let lifting_log_size = self
70            .column_log_sizes()
71            .zip_cols(&sampled_points)
72            .flatten()
73            .iter()
74            .filter(|(_, sampled_points)| !sampled_points.is_empty())
75            .map(|(log_size, _)| *log_size)
76            .max()
77            .unwrap();
78
79        let bound =
80            CirclePolyDegreeBound::new(lifting_log_size - self.config.fri_config.log_blowup_factor);
81
82        // FRI commitment phase on OODS quotients.
83        let mut fri_verifier =
84            FriVerifier::<MC>::commit(channel, self.config.fri_config, proof.fri_proof, bound)?;
85
86        // Verify proof of work.
87        if !channel.verify_pow_nonce(self.config.pow_bits, proof.proof_of_work) {
88            return Err(VerificationError::ProofOfWork);
89        }
90        channel.mix_u64(proof.proof_of_work);
91        // Get FRI query positions.
92        let query_positions = fri_verifier.sample_query_positions(channel);
93        let preprocessed_query_positions = prepare_preprocessed_query_positions(
94            &query_positions,
95            lifting_log_size,
96            self.column_log_sizes()[0]
97                .iter()
98                .max()
99                .copied()
100                .unwrap_or_default(),
101        );
102
103        // Build the query positions tree: the preprocessed tree needs a different treatment than
104        // the other trees.
105        let query_positions_tree = TreeVec::new(
106            self.trees
107                .iter()
108                .enumerate()
109                .map(|(i, _)| {
110                    if i == 0 {
111                        preprocessed_query_positions.as_slice()
112                    } else {
113                        query_positions.as_slice()
114                    }
115                })
116                .collect::<Vec<_>>(),
117        );
118        // Verify decommitments.
119        self.trees
120            .as_ref()
121            .zip_eq(proof.decommitments)
122            .zip_eq(proof.queried_values.clone())
123            .zip_eq(query_positions_tree)
124            .map(
125                |(((tree, decommitment), queried_values), query_positions)| {
126                    tree.verify(query_positions, queried_values, decommitment)
127                },
128            )
129            .0
130            .into_iter()
131            .collect::<Result<(), _>>()?;
132        // Answer FRI queries.
133        let samples = sampled_points.zip_cols(proof.sampled_values).map_cols(
134            |(sampled_points, sampled_values)| {
135                zip(sampled_points, sampled_values)
136                    .map(|(point, value)| PointSample { point, value })
137                    .collect_vec()
138            },
139        );
140
141        let fri_answers = fri_answers(
142            self.column_log_sizes(),
143            samples,
144            random_coeff,
145            &query_positions,
146            proof.queried_values,
147            lifting_log_size,
148        )?;
149
150        fri_verifier.decommit(fri_answers)?;
151
152        Ok(())
153    }
154}
stwo_gpu/core/pcs/verifier.rs

stwo_gpu/core/pcs/
verifier.rs
