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