plonky2/plonk/
get_challenges.rs

1#[cfg(not(feature = "std"))]
2use alloc::{vec, vec::Vec};
3
4use hashbrown::HashSet;
5
6use super::circuit_builder::NUM_COINS_LOOKUP;
7use crate::field::extension::Extendable;
8use crate::field::polynomial::PolynomialCoeffs;
9use crate::fri::proof::{CompressedFriProof, FriChallenges, FriProof, FriProofTarget};
10use crate::fri::verifier::{compute_evaluation, fri_combine_initial, PrecomputedReducedOpenings};
11use crate::gadgets::polynomial::PolynomialCoeffsExtTarget;
12use crate::hash::hash_types::{HashOutTarget, MerkleCapTarget, RichField};
13use crate::hash::merkle_tree::MerkleCap;
14use crate::iop::challenger::{Challenger, RecursiveChallenger};
15use crate::iop::target::Target;
16use crate::plonk::circuit_builder::CircuitBuilder;
17use crate::plonk::circuit_data::CommonCircuitData;
18use crate::plonk::config::{AlgebraicHasher, GenericConfig, Hasher};
19use crate::plonk::proof::{
20    CompressedProof, CompressedProofWithPublicInputs, FriInferredElements, OpeningSet,
21    OpeningSetTarget, Proof, ProofChallenges, ProofChallengesTarget, ProofTarget,
22    ProofWithPublicInputs, ProofWithPublicInputsTarget,
23};
24use crate::util::reverse_bits;
25
26fn get_challenges<F: RichField + Extendable<D>, C: GenericConfig<D, F = F>, const D: usize>(
27    public_inputs_hash: <<C as GenericConfig<D>>::InnerHasher as Hasher<F>>::Hash,
28    wires_cap: &MerkleCap<F, C::Hasher>,
29    plonk_zs_partial_products_cap: &MerkleCap<F, C::Hasher>,
30    quotient_polys_cap: &MerkleCap<F, C::Hasher>,
31    openings: &OpeningSet<F, D>,
32    commit_phase_merkle_caps: &[MerkleCap<F, C::Hasher>],
33    final_poly: &PolynomialCoeffs<F::Extension>,
34    pow_witness: F,
35    circuit_digest: &<<C as GenericConfig<D>>::Hasher as Hasher<C::F>>::Hash,
36    common_data: &CommonCircuitData<F, D>,
37) -> anyhow::Result<ProofChallenges<F, D>> {
38    let config = &common_data.config;
39    let num_challenges = config.num_challenges;
40
41    let mut challenger = Challenger::<F, C::Hasher>::new();
42    let has_lookup = common_data.num_lookup_polys != 0;
43
44    // Observe the FRI config
45    common_data.fri_params.observe(&mut challenger);
46
47    // Observe the instance.
48    challenger.observe_hash::<C::Hasher>(*circuit_digest);
49    challenger.observe_hash::<C::InnerHasher>(public_inputs_hash);
50
51    challenger.observe_cap::<C::Hasher>(wires_cap);
52    let plonk_betas = challenger.get_n_challenges(num_challenges);
53    let plonk_gammas = challenger.get_n_challenges(num_challenges);
54
55    // If there are lookups in the circuit, we should get delta challenges as well.
56    // But we can use the already generated `plonk_betas` and `plonk_gammas` as the first `plonk_deltas` challenges.
57    let plonk_deltas = if has_lookup {
58        let num_lookup_challenges = NUM_COINS_LOOKUP * num_challenges;
59        let mut deltas = Vec::with_capacity(num_lookup_challenges);
60        let num_additional_challenges = num_lookup_challenges - 2 * num_challenges;
61        let additional = challenger.get_n_challenges(num_additional_challenges);
62        deltas.extend(&plonk_betas);
63        deltas.extend(&plonk_gammas);
64        deltas.extend(additional);
65        deltas
66    } else {
67        vec![]
68    };
69
70    // `plonk_zs_partial_products_cap` also contains the commitment to lookup polynomials.
71    challenger.observe_cap::<C::Hasher>(plonk_zs_partial_products_cap);
72    let plonk_alphas = challenger.get_n_challenges(num_challenges);
73
74    challenger.observe_cap::<C::Hasher>(quotient_polys_cap);
75    let plonk_zeta = challenger.get_extension_challenge::<D>();
76
77    challenger.observe_openings(&openings.to_fri_openings());
78
79    Ok(ProofChallenges {
80        plonk_betas,
81        plonk_gammas,
82        plonk_alphas,
83        plonk_deltas,
84        plonk_zeta,
85        fri_challenges: challenger.fri_challenges::<C, D>(
86            commit_phase_merkle_caps,
87            final_poly,
88            pow_witness,
89            common_data.degree_bits(),
90            &config.fri_config,
91            None,
92            None,
93        ),
94    })
95}
96
97impl<F: RichField + Extendable<D>, C: GenericConfig<D, F = F>, const D: usize>
98    ProofWithPublicInputs<F, C, D>
99{
100    pub(crate) fn fri_query_indices(
101        &self,
102        circuit_digest: &<<C as GenericConfig<D>>::Hasher as Hasher<C::F>>::Hash,
103        common_data: &CommonCircuitData<F, D>,
104    ) -> anyhow::Result<Vec<usize>> {
105        Ok(self
106            .get_challenges(self.get_public_inputs_hash(), circuit_digest, common_data)?
107            .fri_challenges
108            .fri_query_indices)
109    }
110
111    /// Computes all Fiat-Shamir challenges used in the Plonk proof.
112    pub fn get_challenges(
113        &self,
114        public_inputs_hash: <<C as GenericConfig<D>>::InnerHasher as Hasher<F>>::Hash,
115        circuit_digest: &<<C as GenericConfig<D>>::Hasher as Hasher<C::F>>::Hash,
116        common_data: &CommonCircuitData<F, D>,
117    ) -> anyhow::Result<ProofChallenges<F, D>> {
118        let Proof {
119            wires_cap,
120            plonk_zs_partial_products_cap,
121            quotient_polys_cap,
122            openings,
123            opening_proof:
124                FriProof {
125                    commit_phase_merkle_caps,
126                    final_poly,
127                    pow_witness,
128                    ..
129                },
130        } = &self.proof;
131
132        get_challenges::<F, C, D>(
133            public_inputs_hash,
134            wires_cap,
135            plonk_zs_partial_products_cap,
136            quotient_polys_cap,
137            openings,
138            commit_phase_merkle_caps,
139            final_poly,
140            *pow_witness,
141            circuit_digest,
142            common_data,
143        )
144    }
145}
146
147impl<F: RichField + Extendable<D>, C: GenericConfig<D, F = F>, const D: usize>
148    CompressedProofWithPublicInputs<F, C, D>
149{
150    /// Computes all Fiat-Shamir challenges used in the Plonk proof.
151    pub(crate) fn get_challenges(
152        &self,
153        public_inputs_hash: <<C as GenericConfig<D>>::InnerHasher as Hasher<F>>::Hash,
154        circuit_digest: &<<C as GenericConfig<D>>::Hasher as Hasher<C::F>>::Hash,
155        common_data: &CommonCircuitData<F, D>,
156    ) -> anyhow::Result<ProofChallenges<F, D>> {
157        let CompressedProof {
158            wires_cap,
159            plonk_zs_partial_products_cap,
160            quotient_polys_cap,
161            openings,
162            opening_proof:
163                CompressedFriProof {
164                    commit_phase_merkle_caps,
165                    final_poly,
166                    pow_witness,
167                    ..
168                },
169        } = &self.proof;
170
171        get_challenges::<F, C, D>(
172            public_inputs_hash,
173            wires_cap,
174            plonk_zs_partial_products_cap,
175            quotient_polys_cap,
176            openings,
177            commit_phase_merkle_caps,
178            final_poly,
179            *pow_witness,
180            circuit_digest,
181            common_data,
182        )
183    }
184
185    /// Computes all coset elements that can be inferred in the FRI reduction steps.
186    pub(crate) fn get_inferred_elements(
187        &self,
188        challenges: &ProofChallenges<F, D>,
189        common_data: &CommonCircuitData<F, D>,
190    ) -> FriInferredElements<F, D> {
191        let ProofChallenges {
192            plonk_zeta,
193            fri_challenges:
194                FriChallenges {
195                    fri_alpha,
196                    fri_betas,
197                    fri_query_indices,
198                    ..
199                },
200            ..
201        } = challenges;
202        let mut fri_inferred_elements = Vec::new();
203        // Holds the indices that have already been seen at each reduction depth.
204        let mut seen_indices_by_depth =
205            vec![HashSet::new(); common_data.fri_params.reduction_arity_bits.len()];
206        let precomputed_reduced_evals = PrecomputedReducedOpenings::from_os_and_alpha(
207            &self.proof.openings.to_fri_openings(),
208            *fri_alpha,
209        );
210        let log_n = common_data.degree_bits() + common_data.config.fri_config.rate_bits;
211        // Simulate the proof verification and collect the inferred elements.
212        // The content of the loop is basically the same as the `fri_verifier_query_round` function.
213        for &(mut x_index) in fri_query_indices {
214            let mut subgroup_x = F::MULTIPLICATIVE_GROUP_GENERATOR
215                * F::primitive_root_of_unity(log_n).exp_u64(reverse_bits(x_index, log_n) as u64);
216            let mut old_eval = fri_combine_initial::<F, C, D>(
217                &common_data.get_fri_instance(*plonk_zeta),
218                &self
219                    .proof
220                    .opening_proof
221                    .query_round_proofs
222                    .initial_trees_proofs[&x_index],
223                *fri_alpha,
224                subgroup_x,
225                &precomputed_reduced_evals,
226                &common_data.fri_params,
227            );
228            for (i, &arity_bits) in common_data
229                .fri_params
230                .reduction_arity_bits
231                .iter()
232                .enumerate()
233            {
234                let coset_index = x_index >> arity_bits;
235                if !seen_indices_by_depth[i].insert(coset_index) {
236                    // If this index has already been seen, we can skip the rest of the reductions.
237                    break;
238                }
239                fri_inferred_elements.push(old_eval);
240                let arity = 1 << arity_bits;
241                let mut evals = self.proof.opening_proof.query_round_proofs.steps[i][&coset_index]
242                    .evals
243                    .clone();
244                let x_index_within_coset = x_index & (arity - 1);
245                evals.insert(x_index_within_coset, old_eval);
246                old_eval = compute_evaluation(
247                    subgroup_x,
248                    x_index_within_coset,
249                    arity_bits,
250                    &evals,
251                    fri_betas[i],
252                );
253                subgroup_x = subgroup_x.exp_power_of_2(arity_bits);
254                x_index = coset_index;
255            }
256        }
257        FriInferredElements(fri_inferred_elements)
258    }
259}
260
261impl<F: RichField + Extendable<D>, const D: usize> CircuitBuilder<F, D> {
262    fn get_challenges<C: GenericConfig<D, F = F>>(
263        &mut self,
264        public_inputs_hash: HashOutTarget,
265        wires_cap: &MerkleCapTarget,
266        plonk_zs_partial_products_cap: &MerkleCapTarget,
267        quotient_polys_cap: &MerkleCapTarget,
268        openings: &OpeningSetTarget<D>,
269        commit_phase_merkle_caps: &[MerkleCapTarget],
270        final_poly: &PolynomialCoeffsExtTarget<D>,
271        pow_witness: Target,
272        inner_circuit_digest: HashOutTarget,
273        inner_common_data: &CommonCircuitData<F, D>,
274    ) -> ProofChallengesTarget<D>
275    where
276        C::Hasher: AlgebraicHasher<F>,
277    {
278        let config = &inner_common_data.config;
279        let num_challenges = config.num_challenges;
280
281        let mut challenger = RecursiveChallenger::<F, C::Hasher, D>::new(self);
282        let has_lookup = inner_common_data.num_lookup_polys != 0;
283
284        // Observe the FRI config
285        inner_common_data
286            .fri_params
287            .observe_target(self, &mut challenger);
288
289        // Observe the instance.
290        challenger.observe_hash(&inner_circuit_digest);
291        challenger.observe_hash(&public_inputs_hash);
292
293        challenger.observe_cap(wires_cap);
294
295        let plonk_betas = challenger.get_n_challenges(self, num_challenges);
296        let plonk_gammas = challenger.get_n_challenges(self, num_challenges);
297
298        // If there are lookups in the circuit, we should get delta challenges as well.
299        // But we can use the already generated `plonk_betas` and `plonk_gammas` as the first `plonk_deltas` challenges.
300        let plonk_deltas = if has_lookup {
301            let num_lookup_challenges = NUM_COINS_LOOKUP * num_challenges;
302            let mut deltas = Vec::with_capacity(num_lookup_challenges);
303            let num_additional_challenges = num_lookup_challenges - 2 * num_challenges;
304            let additional = challenger.get_n_challenges(self, num_additional_challenges);
305            deltas.extend(&plonk_betas);
306            deltas.extend(&plonk_gammas);
307            deltas.extend(additional);
308            deltas
309        } else {
310            vec![]
311        };
312
313        challenger.observe_cap(plonk_zs_partial_products_cap);
314        let plonk_alphas = challenger.get_n_challenges(self, num_challenges);
315
316        challenger.observe_cap(quotient_polys_cap);
317        let plonk_zeta = challenger.get_extension_challenge(self);
318
319        challenger.observe_openings(&openings.to_fri_openings());
320
321        ProofChallengesTarget {
322            plonk_betas,
323            plonk_gammas,
324            plonk_alphas,
325            plonk_deltas,
326            plonk_zeta,
327            fri_challenges: challenger.fri_challenges(
328                self,
329                commit_phase_merkle_caps,
330                final_poly,
331                pow_witness,
332                &inner_common_data.config.fri_config,
333            ),
334        }
335    }
336}
337
338impl<const D: usize> ProofWithPublicInputsTarget<D> {
339    pub(crate) fn get_challenges<F: RichField + Extendable<D>, C: GenericConfig<D, F = F>>(
340        &self,
341        builder: &mut CircuitBuilder<F, D>,
342        public_inputs_hash: HashOutTarget,
343        inner_circuit_digest: HashOutTarget,
344        inner_common_data: &CommonCircuitData<F, D>,
345    ) -> ProofChallengesTarget<D>
346    where
347        C::Hasher: AlgebraicHasher<F>,
348    {
349        let ProofTarget {
350            wires_cap,
351            plonk_zs_partial_products_cap,
352            quotient_polys_cap,
353            openings,
354            opening_proof:
355                FriProofTarget {
356                    commit_phase_merkle_caps,
357                    final_poly,
358                    pow_witness,
359                    ..
360                },
361        } = &self.proof;
362
363        builder.get_challenges::<C>(
364            public_inputs_hash,
365            wires_cap,
366            plonk_zs_partial_products_cap,
367            quotient_polys_cap,
368            openings,
369            commit_phase_merkle_caps,
370            final_poly,
371            *pow_witness,
372            inner_circuit_digest,
373            inner_common_data,
374        )
375    }
376}
plonky2/plonk/get_challenges.rs

plonky2/plonk/
get_challenges.rs
