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