ark-r1cs-std/crypto-primitives/src/nizk/groth16/constraints.rs
crypto-primitives/src/nizk/groth16/constraints.rsRaw
1use crate::{
2 nizk::{groth16::Groth16, NIZKVerifierGadget},
3 Vec,
4};
5use algebra_core::{AffineCurve, Field, PairingEngine, ToConstraintField};
6use r1cs_core::{ConstraintSynthesizer, ConstraintSystem, SynthesisError};
7use r1cs_std::prelude::*;
8
9use core::{borrow::Borrow, marker::PhantomData};
10use groth16::{PreparedVerifyingKey, Proof, VerifyingKey};
11
12#[derive(Derivative)]
13#[derivative(Clone(bound = "P::G1Gadget: Clone, P::G2Gadget: Clone"))]
14pub struct ProofGadget<
15 PairingE: PairingEngine,
16 ConstraintF: Field,
17 P: PairingGadget<PairingE, ConstraintF>,
18> {
19 pub a: P::G1Gadget,
20 pub b: P::G2Gadget,
21 pub c: P::G1Gadget,
22}
23
24#[derive(Derivative)]
25#[derivative(Clone(
26 bound = "P::G1Gadget: Clone, P::GTGadget: Clone, P::G1PreparedGadget: Clone, \
27 P::G2PreparedGadget: Clone, "
28))]
29pub struct VerifyingKeyGadget<
30 PairingE: PairingEngine,
31 ConstraintF: Field,
32 P: PairingGadget<PairingE, ConstraintF>,
33> {
34 pub alpha_g1: P::G1Gadget,
35 pub beta_g2: P::G2Gadget,
36 pub gamma_g2: P::G2Gadget,
37 pub delta_g2: P::G2Gadget,
38 pub gamma_abc_g1: Vec<P::G1Gadget>,
39}
40
41impl<PairingE: PairingEngine, ConstraintF: Field, P: PairingGadget<PairingE, ConstraintF>>
42 VerifyingKeyGadget<PairingE, ConstraintF, P>
43{
44 pub fn prepare<CS: ConstraintSystem<ConstraintF>>(
45 &self,
46 mut cs: CS,
47 ) -> Result<PreparedVerifyingKeyGadget<PairingE, ConstraintF, P>, SynthesisError> {
48 let mut cs = cs.ns(|| "Preparing verifying key");
49 let alpha_g1_pc = P::prepare_g1(&mut cs.ns(|| "Prepare alpha_g1"), &self.alpha_g1)?;
50 let beta_g2_pc = P::prepare_g2(&mut cs.ns(|| "Prepare beta_g2"), &self.beta_g2)?;
51
52 let alpha_g1_beta_g2 = P::pairing(
53 &mut cs.ns(|| "Precompute e(alpha_g1, beta_g2)"),
54 alpha_g1_pc,
55 beta_g2_pc,
56 )?;
57
58 let gamma_g2_neg = self.gamma_g2.negate(&mut cs.ns(|| "Negate gamma_g2"))?;
59 let gamma_g2_neg_pc = P::prepare_g2(&mut cs.ns(|| "Prepare gamma_g2_neg"), &gamma_g2_neg)?;
60
61 let delta_g2_neg = self.delta_g2.negate(&mut cs.ns(|| "Negate delta_g2"))?;
62 let delta_g2_neg_pc = P::prepare_g2(&mut cs.ns(|| "Prepare delta_g2_neg"), &delta_g2_neg)?;
63
64 Ok(PreparedVerifyingKeyGadget {
65 alpha_g1_beta_g2,
66 gamma_g2_neg_pc,
67 delta_g2_neg_pc,
68 gamma_abc_g1: self.gamma_abc_g1.clone(),
69 })
70 }
71}
72
73#[derive(Derivative)]
74#[derivative(Clone(
75 bound = "P::G1Gadget: Clone, P::GTGadget: Clone, P::G1PreparedGadget: Clone, \
76 P::G2PreparedGadget: Clone, "
77))]
78pub struct PreparedVerifyingKeyGadget<
79 PairingE: PairingEngine,
80 ConstraintF: Field,
81 P: PairingGadget<PairingE, ConstraintF>,
82> {
83 pub alpha_g1_beta_g2: P::GTGadget,
84 pub gamma_g2_neg_pc: P::G2PreparedGadget,
85 pub delta_g2_neg_pc: P::G2PreparedGadget,
86 pub gamma_abc_g1: Vec<P::G1Gadget>,
87}
88
89pub struct Groth16VerifierGadget<PairingE, ConstraintF, P>
90where
91 PairingE: PairingEngine,
92 ConstraintF: Field,
93 P: PairingGadget<PairingE, ConstraintF>,
94{
95 _pairing_engine: PhantomData<PairingE>,
96 _engine: PhantomData<ConstraintF>,
97 _pairing_gadget: PhantomData<P>,
98}
99
100impl<PairingE, ConstraintF, P, C, V> NIZKVerifierGadget<Groth16<PairingE, C, V>, ConstraintF>
101 for Groth16VerifierGadget<PairingE, ConstraintF, P>
102where
103 PairingE: PairingEngine,
104 ConstraintF: Field,
105 C: ConstraintSynthesizer<PairingE::Fr>,
106 V: ToConstraintField<PairingE::Fr>,
107 P: PairingGadget<PairingE, ConstraintF>,
108{
109 type PreparedVerificationKeyGadget = PreparedVerifyingKeyGadget<PairingE, ConstraintF, P>;
110 type VerificationKeyGadget = VerifyingKeyGadget<PairingE, ConstraintF, P>;
111 type ProofGadget = ProofGadget<PairingE, ConstraintF, P>;
112
113 fn check_verify<'a, CS, I, T>(
114 cs: CS,
115 vk: &Self::VerificationKeyGadget,
116 public_inputs: I,
117 proof: &Self::ProofGadget,
118 ) -> Result<(), SynthesisError>
119 where
120 CS: ConstraintSystem<ConstraintF>,
121 I: Iterator<Item = &'a T>,
122 T: 'a + ToBitsGadget<ConstraintF> + ?Sized,
123 {
124 <Self as NIZKVerifierGadget<Groth16<PairingE, C, V>, ConstraintF>>::conditional_check_verify(
125 cs,
126 vk,
127 public_inputs,
128 proof,
129 &Boolean::constant(true),
130 )
131 }
132
133 fn conditional_check_verify<'a, CS, I, T>(
134 mut cs: CS,
135 vk: &Self::VerificationKeyGadget,
136 public_inputs: I,
137 proof: &Self::ProofGadget,
138 condition: &Boolean,
139 ) -> Result<(), SynthesisError>
140 where
141 CS: ConstraintSystem<ConstraintF>,
142 I: Iterator<Item = &'a T>,
143 T: 'a + ToBitsGadget<ConstraintF> + ?Sized,
144 {
145 let pvk = vk.prepare(&mut cs.ns(|| "Prepare vk"))?;
146 <Self as NIZKVerifierGadget<Groth16<PairingE, C, V>, ConstraintF>>::conditional_check_verify_prepared(cs, &pvk, public_inputs, proof, condition)
147 }
148
149 fn conditional_check_verify_prepared<'a, CS, I, T>(
150 mut cs: CS,
151 pvk: &Self::PreparedVerificationKeyGadget,
152 mut public_inputs: I,
153 proof: &Self::ProofGadget,
154 condition: &Boolean,
155 ) -> Result<(), SynthesisError>
156 where
157 CS: ConstraintSystem<ConstraintF>,
158 I: Iterator<Item = &'a T>,
159 T: 'a + ToBitsGadget<ConstraintF> + ?Sized,
160 {
161 let pvk = pvk.clone();
162
163 let g_ic = {
164 let mut cs = cs.ns(|| "Process input");
165 let mut g_ic = pvk.gamma_abc_g1[0].clone();
166 let mut input_len = 1;
167 for (i, (input, b)) in public_inputs
168 .by_ref()
169 .zip(pvk.gamma_abc_g1.iter().skip(1))
170 .enumerate()
171 {
172 let input_bits = input.to_bits(cs.ns(|| format!("Input {}", i)))?;
173 g_ic = b.mul_bits(cs.ns(|| format!("Mul {}", i)), &g_ic, input_bits.iter())?;
174 input_len += 1;
175 }
176 // Check that the input and the query in the verification are of the
177 // same length.
178 assert!(input_len == pvk.gamma_abc_g1.len() && public_inputs.next().is_none());
179 g_ic
180 };
181
182 let test_exp = {
183 let proof_a_prep = P::prepare_g1(cs.ns(|| "Prepare proof a"), &proof.a)?;
184 let proof_b_prep = P::prepare_g2(cs.ns(|| "Prepare proof b"), &proof.b)?;
185 let proof_c_prep = P::prepare_g1(cs.ns(|| "Prepare proof c"), &proof.c)?;
186
187 let g_ic_prep = P::prepare_g1(cs.ns(|| "Prepare g_ic"), &g_ic)?;
188
189 P::miller_loop(
190 cs.ns(|| "Miller loop 1"),
191 &[proof_a_prep, g_ic_prep, proof_c_prep],
192 &[
193 proof_b_prep,
194 pvk.gamma_g2_neg_pc.clone(),
195 pvk.delta_g2_neg_pc.clone(),
196 ],
197 )?
198 };
199
200 let test = P::final_exponentiation(cs.ns(|| "Final Exp"), &test_exp).unwrap();
201
202 test.conditional_enforce_equal(cs.ns(|| "Test 1"), &pvk.alpha_g1_beta_g2, condition)?;
203 Ok(())
204 }
205}
206
207impl<PairingE, ConstraintF, P> AllocGadget<PreparedVerifyingKey<PairingE>, ConstraintF>
208 for PreparedVerifyingKeyGadget<PairingE, ConstraintF, P>
209where
210 PairingE: PairingEngine,
211 ConstraintF: Field,
212 P: PairingGadget<PairingE, ConstraintF>,
213 P::G2PreparedGadget: AllocGadget<PairingE::G2Prepared, ConstraintF>,
214{
215 fn alloc_constant<T, CS: ConstraintSystem<ConstraintF>>(
216 mut cs: CS,
217 val: T,
218 ) -> Result<Self, SynthesisError>
219 where
220 T: Borrow<PreparedVerifyingKey<PairingE>>,
221 {
222 let pvk = val.borrow().clone();
223
224 let alpha_g1_beta_g2 =
225 P::GTGadget::alloc_constant(cs.ns(|| "alpha_g1_beta_g2"), pvk.alpha_g1_beta_g2)?;
226
227 let gamma_g2_neg_pc =
228 P::G2PreparedGadget::alloc_constant(cs.ns(|| "gamma_g2_neg_pc"), pvk.gamma_g2_neg_pc)?;
229
230 let delta_g2_neg_pc =
231 P::G2PreparedGadget::alloc_constant(cs.ns(|| "delta_g2_neg_pc"), pvk.delta_g2_neg_pc)?;
232
233 let mut gamma_abc_g1 = Vec::<P::G1Gadget>::new();
234 for (i, item) in pvk.gamma_abc_g1.iter().enumerate() {
235 gamma_abc_g1.push(P::G1Gadget::alloc_constant(
236 cs.ns(|| format!("query_{}", i)),
237 item.borrow().into_projective(),
238 )?);
239 }
240
241 Ok(Self {
242 alpha_g1_beta_g2,
243 gamma_g2_neg_pc,
244 delta_g2_neg_pc,
245 gamma_abc_g1,
246 })
247 }
248
249 fn alloc<F, T, CS: ConstraintSystem<ConstraintF>>(
250 mut cs: CS,
251 f: F,
252 ) -> Result<Self, SynthesisError>
253 where
254 F: FnOnce() -> Result<T, SynthesisError>,
255 T: Borrow<PreparedVerifyingKey<PairingE>>,
256 {
257 let pvk = f()?.borrow().clone();
258
259 let alpha_g1_beta_g2 =
260 P::GTGadget::alloc(cs.ns(|| "alpha_g1_beta_g2"), || Ok(pvk.alpha_g1_beta_g2))?;
261
262 let gamma_g2_neg_pc =
263 P::G2PreparedGadget::alloc(cs.ns(|| "gamma_g2_neg_pc"), || Ok(&pvk.gamma_g2_neg_pc))?;
264
265 let delta_g2_neg_pc =
266 P::G2PreparedGadget::alloc(cs.ns(|| "delta_g2_neg_pc"), || Ok(&pvk.delta_g2_neg_pc))?;
267
268 let mut gamma_abc_g1 = Vec::<P::G1Gadget>::new();
269 for (i, item) in pvk.gamma_abc_g1.iter().enumerate() {
270 gamma_abc_g1.push(P::G1Gadget::alloc(
271 cs.ns(|| format!("query_{}", i)),
272 || Ok(item.borrow().into_projective()),
273 )?);
274 }
275
276 Ok(Self {
277 alpha_g1_beta_g2,
278 gamma_g2_neg_pc,
279 delta_g2_neg_pc,
280 gamma_abc_g1,
281 })
282 }
283
284 fn alloc_input<F, T, CS: ConstraintSystem<ConstraintF>>(
285 mut cs: CS,
286 f: F,
287 ) -> Result<Self, SynthesisError>
288 where
289 F: FnOnce() -> Result<T, SynthesisError>,
290 T: Borrow<PreparedVerifyingKey<PairingE>>,
291 {
292 let pvk = f()?.borrow().clone();
293
294 let alpha_g1_beta_g2 =
295 P::GTGadget::alloc_input(cs.ns(|| "alpha_g1_beta_g2"), || Ok(pvk.alpha_g1_beta_g2))?;
296
297 let gamma_g2_neg_pc =
298 P::G2PreparedGadget::alloc_input(cs.ns(|| "gamma_g2_neg_pc"), || {
299 Ok(&pvk.gamma_g2_neg_pc)
300 })?;
301
302 let delta_g2_neg_pc =
303 P::G2PreparedGadget::alloc_input(cs.ns(|| "delta_g2_neg_pc"), || {
304 Ok(&pvk.delta_g2_neg_pc)
305 })?;
306
307 let mut gamma_abc_g1 = Vec::<P::G1Gadget>::new();
308 for (i, item) in pvk.gamma_abc_g1.iter().enumerate() {
309 gamma_abc_g1.push(P::G1Gadget::alloc_input(
310 cs.ns(|| format!("query_{}", i)),
311 || Ok(item.borrow().into_projective()),
312 )?);
313 }
314
315 Ok(Self {
316 alpha_g1_beta_g2,
317 gamma_g2_neg_pc,
318 delta_g2_neg_pc,
319 gamma_abc_g1,
320 })
321 }
322}
323
324impl<PairingE, ConstraintF, P> AllocGadget<VerifyingKey<PairingE>, ConstraintF>
325 for VerifyingKeyGadget<PairingE, ConstraintF, P>
326where
327 PairingE: PairingEngine,
328 ConstraintF: Field,
329 P: PairingGadget<PairingE, ConstraintF>,
330{
331 #[inline]
332 fn alloc_constant<T, CS: ConstraintSystem<ConstraintF>>(
333 mut cs: CS,
334 val: T,
335 ) -> Result<Self, SynthesisError>
336 where
337 T: Borrow<VerifyingKey<PairingE>>,
338 {
339 let VerifyingKey {
340 alpha_g1,
341 beta_g2,
342 gamma_g2,
343 delta_g2,
344 gamma_abc_g1,
345 } = val.borrow().clone();
346 let alpha_g1 =
347 P::G1Gadget::alloc_constant(cs.ns(|| "alpha_g1"), alpha_g1.into_projective())?;
348 let beta_g2 = P::G2Gadget::alloc_constant(cs.ns(|| "beta_g2"), beta_g2.into_projective())?;
349 let gamma_g2 =
350 P::G2Gadget::alloc_constant(cs.ns(|| "gamma_g2"), gamma_g2.into_projective())?;
351 let delta_g2 =
352 P::G2Gadget::alloc_constant(cs.ns(|| "delta_g2"), delta_g2.into_projective())?;
353
354 let gamma_abc_g1 = gamma_abc_g1
355 .into_iter()
356 .enumerate()
357 .map(|(i, gamma_abc_i)| {
358 P::G1Gadget::alloc_constant(
359 cs.ns(|| format!("gamma_abc_{}", i)),
360 gamma_abc_i.into_projective(),
361 )
362 })
363 .collect::<Vec<_>>()
364 .into_iter()
365 .collect::<Result<_, _>>()?;
366 Ok(Self {
367 alpha_g1,
368 beta_g2,
369 gamma_g2,
370 delta_g2,
371 gamma_abc_g1,
372 })
373 }
374
375 #[inline]
376 fn alloc<FN, T, CS: ConstraintSystem<ConstraintF>>(
377 mut cs: CS,
378 value_gen: FN,
379 ) -> Result<Self, SynthesisError>
380 where
381 FN: FnOnce() -> Result<T, SynthesisError>,
382 T: Borrow<VerifyingKey<PairingE>>,
383 {
384 value_gen().and_then(|vk| {
385 let VerifyingKey {
386 alpha_g1,
387 beta_g2,
388 gamma_g2,
389 delta_g2,
390 gamma_abc_g1,
391 } = vk.borrow().clone();
392 let alpha_g1 =
393 P::G1Gadget::alloc(cs.ns(|| "alpha_g1"), || Ok(alpha_g1.into_projective()))?;
394 let beta_g2 =
395 P::G2Gadget::alloc(cs.ns(|| "beta_g2"), || Ok(beta_g2.into_projective()))?;
396 let gamma_g2 =
397 P::G2Gadget::alloc(cs.ns(|| "gamma_g2"), || Ok(gamma_g2.into_projective()))?;
398 let delta_g2 =
399 P::G2Gadget::alloc(cs.ns(|| "delta_g2"), || Ok(delta_g2.into_projective()))?;
400
401 let gamma_abc_g1 = gamma_abc_g1
402 .into_iter()
403 .enumerate()
404 .map(|(i, gamma_abc_i)| {
405 P::G1Gadget::alloc(cs.ns(|| format!("gamma_abc_{}", i)), || {
406 Ok(gamma_abc_i.into_projective())
407 })
408 })
409 .collect::<Vec<_>>()
410 .into_iter()
411 .collect::<Result<_, _>>()?;
412 Ok(Self {
413 alpha_g1,
414 beta_g2,
415 gamma_g2,
416 delta_g2,
417 gamma_abc_g1,
418 })
419 })
420 }
421
422 #[inline]
423 fn alloc_input<FN, T, CS: ConstraintSystem<ConstraintF>>(
424 mut cs: CS,
425 value_gen: FN,
426 ) -> Result<Self, SynthesisError>
427 where
428 FN: FnOnce() -> Result<T, SynthesisError>,
429 T: Borrow<VerifyingKey<PairingE>>,
430 {
431 value_gen().and_then(|vk| {
432 let VerifyingKey {
433 alpha_g1,
434 beta_g2,
435 gamma_g2,
436 delta_g2,
437 gamma_abc_g1,
438 } = vk.borrow().clone();
439 let alpha_g1 =
440 P::G1Gadget::alloc_input(cs.ns(|| "alpha_g1"), || Ok(alpha_g1.into_projective()))?;
441 let beta_g2 =
442 P::G2Gadget::alloc_input(cs.ns(|| "beta_g2"), || Ok(beta_g2.into_projective()))?;
443 let gamma_g2 =
444 P::G2Gadget::alloc_input(cs.ns(|| "gamma_g2"), || Ok(gamma_g2.into_projective()))?;
445 let delta_g2 =
446 P::G2Gadget::alloc_input(cs.ns(|| "delta_g2"), || Ok(delta_g2.into_projective()))?;
447
448 let gamma_abc_g1 = gamma_abc_g1
449 .into_iter()
450 .enumerate()
451 .map(|(i, gamma_abc_i)| {
452 P::G1Gadget::alloc_input(cs.ns(|| format!("gamma_abc_{}", i)), || {
453 Ok(gamma_abc_i.into_projective())
454 })
455 })
456 .collect::<Vec<_>>()
457 .into_iter()
458 .collect::<Result<_, _>>()?;
459
460 Ok(Self {
461 alpha_g1,
462 beta_g2,
463 gamma_g2,
464 delta_g2,
465 gamma_abc_g1,
466 })
467 })
468 }
469}
470
471impl<PairingE, ConstraintF, P> AllocGadget<Proof<PairingE>, ConstraintF>
472 for ProofGadget<PairingE, ConstraintF, P>
473where
474 PairingE: PairingEngine,
475 ConstraintF: Field,
476 P: PairingGadget<PairingE, ConstraintF>,
477{
478 #[inline]
479 fn alloc_constant<T, CS: ConstraintSystem<ConstraintF>>(
480 mut cs: CS,
481 val: T,
482 ) -> Result<Self, SynthesisError>
483 where
484 T: Borrow<Proof<PairingE>>,
485 {
486 let Proof { a, b, c } = val.borrow().clone();
487 let a = P::G1Gadget::alloc_constant(cs.ns(|| "a"), a.into_projective())?;
488 let b = P::G2Gadget::alloc_constant(cs.ns(|| "b"), b.into_projective())?;
489 let c = P::G1Gadget::alloc_constant(cs.ns(|| "c"), c.into_projective())?;
490 Ok(Self { a, b, c })
491 }
492
493 #[inline]
494 fn alloc<FN, T, CS: ConstraintSystem<ConstraintF>>(
495 mut cs: CS,
496 value_gen: FN,
497 ) -> Result<Self, SynthesisError>
498 where
499 FN: FnOnce() -> Result<T, SynthesisError>,
500 T: Borrow<Proof<PairingE>>,
501 {
502 value_gen().and_then(|proof| {
503 let Proof { a, b, c } = proof.borrow().clone();
504 let a = P::G1Gadget::alloc_checked(cs.ns(|| "a"), || Ok(a.into_projective()))?;
505 let b = P::G2Gadget::alloc_checked(cs.ns(|| "b"), || Ok(b.into_projective()))?;
506 let c = P::G1Gadget::alloc_checked(cs.ns(|| "c"), || Ok(c.into_projective()))?;
507 Ok(Self { a, b, c })
508 })
509 }
510
511 #[inline]
512 fn alloc_input<FN, T, CS: ConstraintSystem<ConstraintF>>(
513 mut cs: CS,
514 value_gen: FN,
515 ) -> Result<Self, SynthesisError>
516 where
517 FN: FnOnce() -> Result<T, SynthesisError>,
518 T: Borrow<Proof<PairingE>>,
519 {
520 value_gen().and_then(|proof| {
521 let Proof { a, b, c } = proof.borrow().clone();
522 // We don't need to check here because the prime order check can be performed
523 // in plain.
524 let a = P::G1Gadget::alloc_input(cs.ns(|| "a"), || Ok(a.into_projective()))?;
525 let b = P::G2Gadget::alloc_input(cs.ns(|| "b"), || Ok(b.into_projective()))?;
526 let c = P::G1Gadget::alloc_input(cs.ns(|| "c"), || Ok(c.into_projective()))?;
527 Ok(Self { a, b, c })
528 })
529 }
530}
531
532impl<PairingE, ConstraintF, P> ToBytesGadget<ConstraintF>
533 for VerifyingKeyGadget<PairingE, ConstraintF, P>
534where
535 PairingE: PairingEngine,
536 ConstraintF: Field,
537 P: PairingGadget<PairingE, ConstraintF>,
538{
539 #[inline]
540 fn to_bytes<CS: ConstraintSystem<ConstraintF>>(
541 &self,
542 mut cs: CS,
543 ) -> Result<Vec<UInt8>, SynthesisError> {
544 let mut bytes = Vec::new();
545 bytes.extend_from_slice(&self.alpha_g1.to_bytes(&mut cs.ns(|| "alpha_g1 to bytes"))?);
546 bytes.extend_from_slice(&self.beta_g2.to_bytes(&mut cs.ns(|| "beta_g2 to bytes"))?);
547 bytes.extend_from_slice(&self.gamma_g2.to_bytes(&mut cs.ns(|| "gamma_g2 to bytes"))?);
548 bytes.extend_from_slice(&self.delta_g2.to_bytes(&mut cs.ns(|| "delta_g2 to bytes"))?);
549 for (i, g) in self.gamma_abc_g1.iter().enumerate() {
550 let mut cs = cs.ns(|| format!("Iteration {}", i));
551 bytes.extend_from_slice(&g.to_bytes(&mut cs.ns(|| "g"))?);
552 }
553 Ok(bytes)
554 }
555}
556
557#[cfg(test)]
558mod test {
559 use groth16::*;
560 use r1cs_core::{ConstraintSynthesizer, ConstraintSystem, SynthesisError};
561
562 use super::*;
563 use algebra::{
564 bls12_377::{Bls12_377, Fq, Fr},
565 test_rng, BitIterator, PrimeField,
566 };
567 use r1cs_std::{
568 bls12_377::PairingGadget as Bls12_377PairingGadget, boolean::Boolean,
569 test_constraint_system::TestConstraintSystem,
570 };
571 use rand::Rng;
572
573 type TestProofSystem = Groth16<Bls12_377, Bench<Fr>, Fr>;
574 type TestVerifierGadget = Groth16VerifierGadget<Bls12_377, Fq, Bls12_377PairingGadget>;
575 type TestProofGadget = ProofGadget<Bls12_377, Fq, Bls12_377PairingGadget>;
576 type TestVkGadget = VerifyingKeyGadget<Bls12_377, Fq, Bls12_377PairingGadget>;
577
578 struct Bench<F: Field> {
579 inputs: Vec<Option<F>>,
580 num_constraints: usize,
581 }
582
583 impl<F: Field> ConstraintSynthesizer<F> for Bench<F> {
584 fn generate_constraints<CS: ConstraintSystem<F>>(
585 self,
586 cs: &mut CS,
587 ) -> Result<(), SynthesisError> {
588 assert!(self.inputs.len() >= 2);
589 assert!(self.num_constraints >= self.inputs.len());
590
591 let mut variables: Vec<_> = Vec::with_capacity(self.inputs.len());
592 for (i, input) in self.inputs.into_iter().enumerate() {
593 let input_var = cs.alloc_input(
594 || format!("Input {}", i),
595 || input.ok_or(SynthesisError::AssignmentMissing),
596 )?;
597 variables.push((input, input_var));
598 }
599
600 for i in 0..self.num_constraints {
601 let new_entry = {
602 let (input_1_val, input_1_var) = variables[i];
603 let (input_2_val, input_2_var) = variables[i + 1];
604 let result_val = input_1_val
605 .and_then(|input_1| input_2_val.map(|input_2| input_1 * &input_2));
606 let result_var = cs.alloc(
607 || format!("Result {}", i),
608 || result_val.ok_or(SynthesisError::AssignmentMissing),
609 )?;
610 cs.enforce(
611 || format!("Enforce constraint {}", i),
612 |lc| lc + input_1_var,
613 |lc| lc + input_2_var,
614 |lc| lc + result_var,
615 );
616 (result_val, result_var)
617 };
618 variables.push(new_entry);
619 }
620 Ok(())
621 }
622 }
623
624 #[test]
625 fn groth16_verifier_test() {
626 let num_inputs = 100;
627 let num_constraints = num_inputs;
628 let rng = &mut test_rng();
629 let mut inputs: Vec<Option<Fr>> = Vec::with_capacity(num_inputs);
630 for _ in 0..num_inputs {
631 inputs.push(Some(rng.gen()));
632 }
633 let params = {
634 let c = Bench::<Fr> {
635 inputs: vec![None; num_inputs],
636 num_constraints,
637 };
638
639 generate_random_parameters(c, rng).unwrap()
640 };
641
642 {
643 let proof = {
644 // Create an instance of our circuit (with the
645 // witness)
646 let c = Bench {
647 inputs: inputs.clone(),
648 num_constraints,
649 };
650 // Create a groth16 proof with our parameters.
651 create_random_proof(c, ¶ms, rng).unwrap()
652 };
653
654 // assert!(!verify_proof(&pvk, &proof, &[a]).unwrap());
655 let mut cs = TestConstraintSystem::<Fq>::new();
656
657 let inputs: Vec<_> = inputs.into_iter().map(|input| input.unwrap()).collect();
658 let mut input_gadgets = Vec::new();
659
660 {
661 let mut cs = cs.ns(|| "Allocate Input");
662 for (i, input) in inputs.into_iter().enumerate() {
663 let mut input_bits = BitIterator::new(input.into_repr()).collect::<Vec<_>>();
664 // Input must be in little-endian, but BitIterator outputs in big-endian.
665 input_bits.reverse();
666
667 let input_bits =
668 Vec::<Boolean>::alloc_input(cs.ns(|| format!("Input {}", i)), || {
669 Ok(input_bits)
670 })
671 .unwrap();
672 input_gadgets.push(input_bits);
673 }
674 }
675
676 let vk_gadget = TestVkGadget::alloc_input(cs.ns(|| "Vk"), || Ok(¶ms.vk)).unwrap();
677 let proof_gadget =
678 TestProofGadget::alloc(cs.ns(|| "Proof"), || Ok(proof.clone())).unwrap();
679 println!("Time to verify!\n\n\n\n");
680 <TestVerifierGadget as NIZKVerifierGadget<TestProofSystem, Fq>>::check_verify(
681 cs.ns(|| "Verify"),
682 &vk_gadget,
683 input_gadgets.iter(),
684 &proof_gadget,
685 )
686 .unwrap();
687 if !cs.is_satisfied() {
688 println!("=========================================================");
689 println!("Unsatisfied constraints:");
690 println!("{:?}", cs.which_is_unsatisfied().unwrap());
691 println!("=========================================================");
692 }
693
694 // cs.print_named_objects();
695 assert!(cs.is_satisfied());
696 }
697 }
698}
699
700#[cfg(test)]
701mod test_recursive {
702 use groth16::*;
703 use r1cs_core::{ConstraintSynthesizer, ConstraintSystem, SynthesisError};
704
705 use super::*;
706 use algebra::{
707 fields::{FftParameters, FpParameters},
708 mnt4_298::{Fq as MNT4Fq, FqParameters as MNT4FqParameters, Fr as MNT4Fr, MNT4_298},
709 mnt6_298::{Fq as MNT6Fq, FqParameters as MNT6FqParameters, Fr as MNT6Fr, MNT6_298},
710 test_rng, BigInteger, PrimeField,
711 };
712 use r1cs_std::{
713 fields::fp::FpGadget, mnt4_298::PairingGadget as MNT4_298PairingGadget,
714 mnt6_298::PairingGadget as MNT6_298PairingGadget,
715 test_constraint_system::TestConstraintSystem, uint8::UInt8,
716 };
717 use rand::Rng;
718
719 type TestProofSystem1 = Groth16<MNT6_298, Bench<MNT4Fq>, MNT6Fr>;
720 type TestVerifierGadget1 = Groth16VerifierGadget<MNT6_298, MNT6Fq, MNT6_298PairingGadget>;
721 type TestProofGadget1 = ProofGadget<MNT6_298, MNT6Fq, MNT6_298PairingGadget>;
722 type TestVkGadget1 = VerifyingKeyGadget<MNT6_298, MNT6Fq, MNT6_298PairingGadget>;
723
724 type TestProofSystem2 = Groth16<MNT4_298, Wrapper, MNT4Fr>;
725 type TestVerifierGadget2 = Groth16VerifierGadget<MNT4_298, MNT4Fq, MNT4_298PairingGadget>;
726 type TestProofGadget2 = ProofGadget<MNT4_298, MNT4Fq, MNT4_298PairingGadget>;
727 type TestVkGadget2 = VerifyingKeyGadget<MNT4_298, MNT4Fq, MNT4_298PairingGadget>;
728
729 #[derive(Clone)]
730 struct Bench<F: Field> {
731 inputs: Vec<Option<F>>,
732 num_constraints: usize,
733 }
734
735 impl<F: Field> ConstraintSynthesizer<F> for Bench<F> {
736 fn generate_constraints<CS: ConstraintSystem<F>>(
737 self,
738 cs: &mut CS,
739 ) -> Result<(), SynthesisError> {
740 assert!(self.inputs.len() >= 2);
741 assert!(self.num_constraints >= self.inputs.len());
742
743 let mut variables: Vec<_> = Vec::with_capacity(self.inputs.len());
744 for (i, input) in self.inputs.into_iter().enumerate() {
745 let input_var = cs.alloc_input(
746 || format!("Input {}", i),
747 || input.ok_or(SynthesisError::AssignmentMissing),
748 )?;
749 variables.push((input, input_var));
750 }
751
752 for i in 0..self.num_constraints {
753 let new_entry = {
754 let (input_1_val, input_1_var) = variables[i];
755 let (input_2_val, input_2_var) = variables[i + 1];
756 let result_val = input_1_val
757 .and_then(|input_1| input_2_val.map(|input_2| input_1 * &input_2));
758 let result_var = cs.alloc(
759 || format!("Result {}", i),
760 || result_val.ok_or(SynthesisError::AssignmentMissing),
761 )?;
762 cs.enforce(
763 || format!("Enforce constraint {}", i),
764 |lc| lc + input_1_var,
765 |lc| lc + input_2_var,
766 |lc| lc + result_var,
767 );
768 (result_val, result_var)
769 };
770 variables.push(new_entry);
771 }
772 Ok(())
773 }
774 }
775
776 struct Wrapper {
777 inputs: Vec<Option<MNT4Fq>>,
778 params: Parameters<MNT6_298>,
779 proof: Proof<MNT6_298>,
780 }
781
782 impl ConstraintSynthesizer<MNT6Fq> for Wrapper {
783 fn generate_constraints<CS: ConstraintSystem<MNT6Fq>>(
784 self,
785 cs: &mut CS,
786 ) -> Result<(), SynthesisError> {
787 let params = self.params;
788 let proof = self.proof;
789 let inputs: Vec<_> = self
790 .inputs
791 .into_iter()
792 .map(|input| input.unwrap())
793 .collect();
794 let input_gadgets;
795
796 {
797 let mut cs = cs.ns(|| "Allocate Input");
798 // Chain all input values in one large byte array.
799 let input_bytes = inputs
800 .clone()
801 .into_iter()
802 .flat_map(|input| {
803 input
804 .into_repr()
805 .as_ref()
806 .iter()
807 .flat_map(|l| l.to_le_bytes().to_vec())
808 .collect::<Vec<_>>()
809 })
810 .collect::<Vec<_>>();
811
812 // Allocate this byte array as input packed into field elements.
813 let input_bytes = UInt8::alloc_input_vec(cs.ns(|| "Input"), &input_bytes[..])?;
814 // 40 byte
815 let element_size = <MNT4FqParameters as FftParameters>::BigInt::NUM_LIMBS * 8;
816 input_gadgets = input_bytes
817 .chunks(element_size)
818 .map(|chunk| {
819 chunk
820 .iter()
821 .flat_map(|byte| byte.into_bits_le())
822 .collect::<Vec<_>>()
823 })
824 .collect::<Vec<_>>();
825 }
826
827 let vk_gadget = TestVkGadget1::alloc(cs.ns(|| "Vk"), || Ok(¶ms.vk))?;
828 let proof_gadget =
829 TestProofGadget1::alloc(cs.ns(|| "Proof"), || Ok(proof.clone())).unwrap();
830 <TestVerifierGadget1 as NIZKVerifierGadget<TestProofSystem1, MNT6Fq>>::check_verify(
831 cs.ns(|| "Verify"),
832 &vk_gadget,
833 input_gadgets.iter(),
834 &proof_gadget,
835 )?;
836 Ok(())
837 }
838 }
839
840 #[test]
841 fn groth16_recursive_verifier_test() {
842 let num_inputs = 5;
843 let num_constraints = num_inputs;
844 let rng = &mut test_rng();
845 let mut inputs: Vec<Option<MNT4Fq>> = Vec::with_capacity(num_inputs);
846 for _ in 0..num_inputs {
847 inputs.push(Some(rng.gen()));
848 }
849
850 // Generate inner params and proof.
851 let inner_params = {
852 let c = Bench::<MNT4Fq> {
853 inputs: vec![None; num_inputs],
854 num_constraints,
855 };
856
857 generate_random_parameters(c, rng).unwrap()
858 };
859
860 let inner_proof = {
861 // Create an instance of our circuit (with the
862 // witness)
863 let c = Bench {
864 inputs: inputs.clone(),
865 num_constraints,
866 };
867 // Create a groth16 proof with our parameters.
868 create_random_proof(c, &inner_params, rng).unwrap()
869 };
870
871 // Generate outer params and proof.
872 let params = {
873 let c = Wrapper {
874 inputs: inputs.clone(),
875 params: inner_params.clone(),
876 proof: inner_proof.clone(),
877 };
878
879 generate_random_parameters(c, rng).unwrap()
880 };
881
882 {
883 let proof = {
884 // Create an instance of our circuit (with the
885 // witness)
886 let c = Wrapper {
887 inputs: inputs.clone(),
888 params: inner_params.clone(),
889 proof: inner_proof.clone(),
890 };
891 // Create a groth16 proof with our parameters.
892 create_random_proof(c, ¶ms, rng).unwrap()
893 };
894
895 let mut cs = TestConstraintSystem::<MNT4Fq>::new();
896
897 let inputs: Vec<_> = inputs.into_iter().map(|input| input.unwrap()).collect();
898 let mut input_gadgets = Vec::new();
899
900 {
901 let bigint_size = <MNT4FqParameters as FftParameters>::BigInt::NUM_LIMBS * 64;
902 let mut input_bits = Vec::new();
903 let mut cs = cs.ns(|| "Allocate Input");
904 for (i, input) in inputs.into_iter().enumerate() {
905 let input_gadget =
906 FpGadget::alloc_input(cs.ns(|| format!("Input {}", i)), || Ok(input))
907 .unwrap();
908 let mut fp_bits = input_gadget
909 .to_bits(cs.ns(|| format!("To bits {}", i)))
910 .unwrap();
911
912 // FpGadget::to_bits outputs a big-endian binary representation of
913 // fe_gadget's value, so we have to reverse it to get the little-endian
914 // form.
915 fp_bits.reverse();
916
917 // Use 320 bits per element.
918 for _ in fp_bits.len()..bigint_size {
919 fp_bits.push(Boolean::constant(false));
920 }
921 input_bits.extend_from_slice(&fp_bits);
922 }
923
924 // Pack input bits into field elements of the underlying circuit.
925 let max_size = 8 * (<MNT6FqParameters as FpParameters>::CAPACITY / 8) as usize;
926 let max_size = max_size as usize;
927 let bigint_size = <MNT6FqParameters as FftParameters>::BigInt::NUM_LIMBS * 64;
928 for chunk in input_bits.chunks(max_size) {
929 let mut chunk = chunk.to_vec();
930 let len = chunk.len();
931 for _ in len..bigint_size {
932 chunk.push(Boolean::constant(false));
933 }
934 input_gadgets.push(chunk);
935 }
936 // assert!(!verify_proof(&pvk, &proof, &[a]).unwrap());
937 }
938
939 let vk_gadget = TestVkGadget2::alloc_input(cs.ns(|| "Vk"), || Ok(¶ms.vk)).unwrap();
940 let proof_gadget =
941 TestProofGadget2::alloc(cs.ns(|| "Proof"), || Ok(proof.clone())).unwrap();
942 println!("Time to verify!\n\n\n\n");
943 <TestVerifierGadget2 as NIZKVerifierGadget<TestProofSystem2, MNT4Fq>>::check_verify(
944 cs.ns(|| "Verify"),
945 &vk_gadget,
946 input_gadgets.iter(),
947 &proof_gadget,
948 )
949 .unwrap();
950 if !cs.is_satisfied() {
951 println!("=========================================================");
952 println!("Unsatisfied constraints:");
953 println!("{:?}", cs.which_is_unsatisfied().unwrap());
954 println!("=========================================================");
955 }
956
957 // cs.print_named_objects();
958 assert!(cs.is_satisfied());
959 }
960 }
961}