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
23pub 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 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 vk.hash_into(transcript)?;
75
76 if V::QUERY_INSTANCE {
77 for instance_commitments in instance_commitments.iter() {
78 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 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 let theta: ChallengeTheta<_> = transcript.squeeze_challenge_scalar();
124
125 let lookups_permuted = (0..num_proofs)
126 .map(|_| -> Result<Vec<_>, _> {
127 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 let beta: ChallengeBeta<_> = transcript.squeeze_challenge_scalar();
138
139 let gamma: ChallengeGamma<_> = transcript.squeeze_challenge_scalar();
141
142 let permutations_committed = (0..num_proofs)
143 .map(|_| {
144 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 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 let y: ChallengeY<_> = transcript.squeeze_challenge_scalar();
164
165 let vanishing = vanishing.read_commitments_after_y(vk, transcript)?;
166
167 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 let vanishing = {
245 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 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 .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 let verifier = V::new(params);
385 strategy.process(|msm| {
386 verifier
387 .verify_proof(transcript, queries, msm)
388 .map_err(|_| Error::Opening)
389 })
390}