halo2_axiom/plonk/
verifier.rs

1use ff::{Field, FromUniformBytes, WithSmallOrderMulGroup};
2use group::Curve;
3use std::iter;
4
5use super::{
6    vanishing, ChallengeBeta, ChallengeGamma, ChallengeTheta, ChallengeX, ChallengeY, Error,
7    VerifyingKey,
8};
9use crate::arithmetic::compute_inner_product;
10use crate::poly::commitment::{CommitmentScheme, Verifier};
11use crate::poly::VerificationStrategy;
12use crate::poly::{
13    commitment::{Blind, Params},
14    VerifierQuery,
15};
16use crate::transcript::{read_n_scalars, EncodedChallenge, TranscriptRead};
17
18#[cfg(feature = "batch")]
19mod batch;
20#[cfg(feature = "batch")]
21pub use batch::BatchVerifier;
22
23/// Returns a boolean indicating whether or not the proof is valid
24pub fn verify_proof<
25    'params,
26    Scheme: CommitmentScheme,
27    V: Verifier<'params, Scheme>,
28    E: EncodedChallenge<Scheme::Curve>,
29    T: TranscriptRead<Scheme::Curve, E>,
30    Strategy: VerificationStrategy<'params, Scheme, V>,
31>(
32    params: &'params Scheme::ParamsVerifier,
33    vk: &VerifyingKey<Scheme::Curve>,
34    strategy: Strategy,
35    instances: &[&[&[Scheme::Scalar]]],
36    transcript: &mut T,
37) -> Result<Strategy::Output, Error>
38where
39    Scheme::Scalar: WithSmallOrderMulGroup<3> + FromUniformBytes<64>,
40{
41    // Check that instances matches the expected number of instance columns
42    for instances in instances.iter() {
43        if instances.len() != vk.cs.num_instance_columns {
44            return Err(Error::InvalidInstances);
45        }
46    }
47
48    let instance_commitments = if V::QUERY_INSTANCE {
49        instances
50            .iter()
51            .map(|instance| {
52                instance
53                    .iter()
54                    .map(|instance| {
55                        if instance.len() > params.n() as usize - (vk.cs.blinding_factors() + 1) {
56                            return Err(Error::InstanceTooLarge);
57                        }
58                        let mut poly = instance.to_vec();
59                        poly.resize(params.n() as usize, Scheme::Scalar::ZERO);
60                        let poly = vk.domain.lagrange_from_vec(poly);
61
62                        Ok(params.commit_lagrange(&poly, Blind::default()).to_affine())
63                    })
64                    .collect::<Result<Vec<_>, _>>()
65            })
66            .collect::<Result<Vec<_>, _>>()?
67    } else {
68        vec![vec![]; instances.len()]
69    };
70
71    let num_proofs = instance_commitments.len();
72
73    // Hash verification key into transcript
74    vk.hash_into(transcript)?;
75
76    if V::QUERY_INSTANCE {
77        for instance_commitments in instance_commitments.iter() {
78            // Hash the instance (external) commitments into the transcript
79            for commitment in instance_commitments {
80                transcript.common_point(*commitment)?
81            }
82        }
83    } else {
84        for instance in instances.iter() {
85            for instance in instance.iter() {
86                for value in instance.iter() {
87                    transcript.common_scalar(*value)?;
88                }
89            }
90        }
91    }
92
93    // Hash the prover's advice commitments into the transcript and squeeze challenges
94    let (advice_commitments, challenges) = {
95        let mut advice_commitments =
96            vec![vec![Scheme::Curve::default(); vk.cs.num_advice_columns]; num_proofs];
97        let mut challenges = vec![Scheme::Scalar::ZERO; vk.cs.num_challenges];
98
99        for current_phase in vk.cs.phases() {
100            for advice_commitments in advice_commitments.iter_mut() {
101                for (phase, commitment) in vk
102                    .cs
103                    .advice_column_phase
104                    .iter()
105                    .zip(advice_commitments.iter_mut())
106                {
107                    if current_phase == *phase {
108                        *commitment = transcript.read_point()?;
109                    }
110                }
111            }
112            for (phase, challenge) in vk.cs.challenge_phase.iter().zip(challenges.iter_mut()) {
113                if current_phase == *phase {
114                    *challenge = *transcript.squeeze_challenge_scalar::<()>();
115                }
116            }
117        }
118
119        (advice_commitments, challenges)
120    };
121
122    // Sample theta challenge for keeping lookup columns linearly independent
123    let theta: ChallengeTheta<_> = transcript.squeeze_challenge_scalar();
124
125    let lookups_permuted = (0..num_proofs)
126        .map(|_| -> Result<Vec<_>, _> {
127            // Hash each lookup permuted commitment
128            vk.cs
129                .lookups
130                .iter()
131                .map(|argument| argument.read_permuted_commitments(transcript))
132                .collect::<Result<Vec<_>, _>>()
133        })
134        .collect::<Result<Vec<_>, _>>()?;
135
136    // Sample beta challenge
137    let beta: ChallengeBeta<_> = transcript.squeeze_challenge_scalar();
138
139    // Sample gamma challenge
140    let gamma: ChallengeGamma<_> = transcript.squeeze_challenge_scalar();
141
142    let permutations_committed = (0..num_proofs)
143        .map(|_| {
144            // Hash each permutation product commitment
145            vk.cs.permutation.read_product_commitments(vk, transcript)
146        })
147        .collect::<Result<Vec<_>, _>>()?;
148
149    let lookups_committed = lookups_permuted
150        .into_iter()
151        .map(|lookups| {
152            // Hash each lookup product commitment
153            lookups
154                .into_iter()
155                .map(|lookup| lookup.read_product_commitment(transcript))
156                .collect::<Result<Vec<_>, _>>()
157        })
158        .collect::<Result<Vec<_>, _>>()?;
159
160    let vanishing = vanishing::Argument::read_commitments_before_y(transcript)?;
161
162    // Sample y challenge, which keeps the gates linearly independent.
163    let y: ChallengeY<_> = transcript.squeeze_challenge_scalar();
164
165    let vanishing = vanishing.read_commitments_after_y(vk, transcript)?;
166
167    // Sample x challenge, which is used to ensure the circuit is
168    // satisfied with high probability.
169    let x: ChallengeX<_> = transcript.squeeze_challenge_scalar();
170    let instance_evals = if V::QUERY_INSTANCE {
171        (0..num_proofs)
172            .map(|_| -> Result<Vec<_>, _> {
173                read_n_scalars(transcript, vk.cs.instance_queries.len())
174            })
175            .collect::<Result<Vec<_>, _>>()?
176    } else {
177        let xn = x.pow([params.n()]);
178        let (min_rotation, max_rotation) =
179            vk.cs
180                .instance_queries
181                .iter()
182                .fold((0, 0), |(min, max), (_, rotation)| {
183                    if rotation.0 < min {
184                        (rotation.0, max)
185                    } else if rotation.0 > max {
186                        (min, rotation.0)
187                    } else {
188                        (min, max)
189                    }
190                });
191        let max_instance_len = instances
192            .iter()
193            .flat_map(|instance| instance.iter().map(|instance| instance.len()))
194            .max_by(Ord::cmp)
195            .unwrap_or_default();
196        let l_i_s = &vk.domain.l_i_range(
197            *x,
198            xn,
199            -max_rotation..max_instance_len as i32 + min_rotation.abs(),
200        );
201        instances
202            .iter()
203            .map(|instances| {
204                vk.cs
205                    .instance_queries
206                    .iter()
207                    .map(|(column, rotation)| {
208                        let instances = instances[column.index()];
209                        let offset = (max_rotation - rotation.0) as usize;
210                        compute_inner_product(instances, &l_i_s[offset..offset + instances.len()])
211                    })
212                    .collect::<Vec<_>>()
213            })
214            .collect::<Vec<_>>()
215    };
216
217    let advice_evals = (0..num_proofs)
218        .map(|_| -> Result<Vec<_>, _> { read_n_scalars(transcript, vk.cs.advice_queries.len()) })
219        .collect::<Result<Vec<_>, _>>()?;
220
221    let fixed_evals = read_n_scalars(transcript, vk.cs.fixed_queries.len())?;
222
223    let vanishing = vanishing.evaluate_after_x(transcript)?;
224
225    let permutations_common = vk.permutation.evaluate(transcript)?;
226
227    let permutations_evaluated = permutations_committed
228        .into_iter()
229        .map(|permutation| permutation.evaluate(transcript))
230        .collect::<Result<Vec<_>, _>>()?;
231
232    let lookups_evaluated = lookups_committed
233        .into_iter()
234        .map(|lookups| -> Result<Vec<_>, _> {
235            lookups
236                .into_iter()
237                .map(|lookup| lookup.evaluate(transcript))
238                .collect::<Result<Vec<_>, _>>()
239        })
240        .collect::<Result<Vec<_>, _>>()?;
241
242    // This check ensures the circuit is satisfied so long as the polynomial
243    // commitments open to the correct values.
244    let vanishing = {
245        // x^n
246        let xn = x.pow([params.n()]);
247
248        let blinding_factors = vk.cs.blinding_factors();
249        let l_evals = vk
250            .domain
251            .l_i_range(*x, xn, (-((blinding_factors + 1) as i32))..=0);
252        assert_eq!(l_evals.len(), 2 + blinding_factors);
253        let l_last = l_evals[0];
254        let l_blind: Scheme::Scalar = l_evals[1..(1 + blinding_factors)]
255            .iter()
256            .fold(Scheme::Scalar::ZERO, |acc, eval| acc + eval);
257        let l_0 = l_evals[1 + blinding_factors];
258
259        // Compute the expected value of h(x)
260        let expressions = advice_evals
261            .iter()
262            .zip(instance_evals.iter())
263            .zip(permutations_evaluated.iter())
264            .zip(lookups_evaluated.iter())
265            .flat_map(|(((advice_evals, instance_evals), permutation), lookups)| {
266                let challenges = &challenges;
267                let fixed_evals = &fixed_evals;
268                std::iter::empty()
269                    // Evaluate the circuit using the custom gates provided
270                    .chain(vk.cs.gates.iter().flat_map(move |gate| {
271                        gate.polynomials().iter().map(move |poly| {
272                            poly.evaluate(
273                                &|scalar| scalar,
274                                &|_| panic!("virtual selectors are removed during optimization"),
275                                &|query| fixed_evals[query.index.unwrap()],
276                                &|query| advice_evals[query.index.unwrap()],
277                                &|query| instance_evals[query.index.unwrap()],
278                                &|challenge| challenges[challenge.index()],
279                                &|a| -a,
280                                &|a, b| a + &b,
281                                &|a, b| a * &b,
282                                &|a, scalar| a * &scalar,
283                            )
284                        })
285                    }))
286                    .chain(permutation.expressions(
287                        vk,
288                        &vk.cs.permutation,
289                        &permutations_common,
290                        advice_evals,
291                        fixed_evals,
292                        instance_evals,
293                        l_0,
294                        l_last,
295                        l_blind,
296                        beta,
297                        gamma,
298                        x,
299                    ))
300                    .chain(lookups.iter().zip(vk.cs.lookups.iter()).flat_map(
301                        move |(p, argument)| {
302                            p.expressions(
303                                l_0,
304                                l_last,
305                                l_blind,
306                                argument,
307                                theta,
308                                beta,
309                                gamma,
310                                advice_evals,
311                                fixed_evals,
312                                instance_evals,
313                                challenges,
314                            )
315                        },
316                    ))
317            });
318
319        vanishing.verify(params, expressions, y, xn)
320    };
321
322    let queries = instance_commitments
323        .iter()
324        .zip(instance_evals.iter())
325        .zip(advice_commitments.iter())
326        .zip(advice_evals.iter())
327        .zip(permutations_evaluated.iter())
328        .zip(lookups_evaluated.iter())
329        .flat_map(
330            |(
331                (
332                    (((instance_commitments, instance_evals), advice_commitments), advice_evals),
333                    permutation,
334                ),
335                lookups,
336            )| {
337                iter::empty()
338                    .chain(
339                        V::QUERY_INSTANCE
340                            .then_some(vk.cs.instance_queries.iter().enumerate().map(
341                                move |(query_index, &(column, at))| {
342                                    VerifierQuery::new_commitment(
343                                        &instance_commitments[column.index()],
344                                        vk.domain.rotate_omega(*x, at),
345                                        instance_evals[query_index],
346                                    )
347                                },
348                            ))
349                            .into_iter()
350                            .flatten(),
351                    )
352                    .chain(vk.cs.advice_queries.iter().enumerate().map(
353                        move |(query_index, &(column, at))| {
354                            VerifierQuery::new_commitment(
355                                &advice_commitments[column.index()],
356                                vk.domain.rotate_omega(*x, at),
357                                advice_evals[query_index],
358                            )
359                        },
360                    ))
361                    .chain(permutation.queries(vk, x))
362                    .chain(lookups.iter().flat_map(move |p| p.queries(vk, x)))
363            },
364        )
365        .chain(
366            vk.cs
367                .fixed_queries
368                .iter()
369                .enumerate()
370                .map(|(query_index, &(column, at))| {
371                    VerifierQuery::new_commitment(
372                        &vk.fixed_commitments[column.index()],
373                        vk.domain.rotate_omega(*x, at),
374                        fixed_evals[query_index],
375                    )
376                }),
377        )
378        .chain(permutations_common.queries(&vk.permutation, x))
379        .chain(vanishing.queries(x));
380
381    // We are now convinced the circuit is satisfied so long as the
382    // polynomial commitments open to the correct values.
383
384    let verifier = V::new(params);
385    strategy.process(|msm| {
386        verifier
387            .verify_proof(transcript, queries, msm)
388            .map_err(|_| Error::Opening)
389    })
390}