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