ark-r1cs-std/crypto-primitives/src/nizk/gm17/constraints.rs
crypto-primitives/src/nizk/gm17/constraints.rsRaw
1use crate::nizk::{gm17::Gm17, NIZKVerifierGadget};
2use algebra::{Field, ToConstraintField, AffineCurve, PairingEngine};
3use r1cs_core::{ConstraintSynthesizer, ConstraintSystem, SynthesisError};
4use r1cs_std::prelude::*;
5
6use gm17::{Proof, VerifyingKey};
7use std::{borrow::Borrow, marker::PhantomData};
8
9#[derive(Derivative)]
10#[derivative(Clone(bound = "P::G1Gadget: Clone, P::G2Gadget: Clone"))]
11pub struct ProofGadget<
12 PairingE: PairingEngine,
13 ConstraintF: Field,
14 P: PairingGadget<PairingE, ConstraintF>,
15> {
16 pub a: P::G1Gadget,
17 pub b: P::G2Gadget,
18 pub c: P::G1Gadget,
19}
20
21#[derive(Derivative)]
22#[derivative(Clone(
23 bound = "P::G1Gadget: Clone, P::GTGadget: Clone, P::G1PreparedGadget: Clone, \
24 P::G2PreparedGadget: Clone, "
25))]
26pub struct VerifyingKeyGadget<
27 PairingE: PairingEngine,
28 ConstraintF: Field,
29 P: PairingGadget<PairingE, ConstraintF>,
30> {
31 pub h_g2: P::G2Gadget,
32 pub g_alpha_g1: P::G1Gadget,
33 pub h_beta_g2: P::G2Gadget,
34 pub g_gamma_g1: P::G1Gadget,
35 pub h_gamma_g2: P::G2Gadget,
36 pub query: Vec<P::G1Gadget>,
37}
38
39impl<
40 PairingE: PairingEngine,
41 ConstraintF: Field,
42 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.clone(), 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<FN, T, CS: ConstraintSystem<ConstraintF>>(
207 mut cs: CS,
208 value_gen: FN,
209 ) -> Result<Self, SynthesisError>
210 where
211 FN: FnOnce() -> Result<T, SynthesisError>,
212 T: Borrow<VerifyingKey<PairingE>>,
213 {
214 value_gen().and_then(|vk| {
215 let VerifyingKey {
216 h_g2,
217 g_alpha_g1,
218 h_beta_g2,
219 g_gamma_g1,
220 h_gamma_g2,
221 query,
222 } = vk.borrow().clone();
223 let h_g2 = P::G2Gadget::alloc(cs.ns(|| "h_g2"), || Ok(h_g2.into_projective()))?;
224 let g_alpha_g1 =
225 P::G1Gadget::alloc(cs.ns(|| "g_alpha"), || Ok(g_alpha_g1.into_projective()))?;
226 let h_beta_g2 =
227 P::G2Gadget::alloc(cs.ns(|| "h_beta"), || Ok(h_beta_g2.into_projective()))?;
228 let g_gamma_g1 =
229 P::G1Gadget::alloc(cs.ns(|| "g_gamma_g1"), || Ok(g_gamma_g1.into_projective()))?;
230 let h_gamma_g2 =
231 P::G2Gadget::alloc(cs.ns(|| "h_gamma_g2"), || Ok(h_gamma_g2.into_projective()))?;
232
233 let query = query
234 .into_iter()
235 .enumerate()
236 .map(|(i, query_i)| {
237 P::G1Gadget::alloc(cs.ns(|| format!("query_{}", i)), || {
238 Ok(query_i.into_projective())
239 })
240 })
241 .collect::<Vec<_>>()
242 .into_iter()
243 .collect::<Result<_, _>>()?;
244 Ok(Self {
245 h_g2,
246 g_alpha_g1,
247 h_beta_g2,
248 g_gamma_g1,
249 h_gamma_g2,
250 query,
251 })
252 })
253 }
254
255 #[inline]
256 fn alloc_input<FN, T, CS: ConstraintSystem<ConstraintF>>(
257 mut cs: CS,
258 value_gen: FN,
259 ) -> Result<Self, SynthesisError>
260 where
261 FN: FnOnce() -> Result<T, SynthesisError>,
262 T: Borrow<VerifyingKey<PairingE>>,
263 {
264 value_gen().and_then(|vk| {
265 let VerifyingKey {
266 h_g2,
267 g_alpha_g1,
268 h_beta_g2,
269 g_gamma_g1,
270 h_gamma_g2,
271 query,
272 } = vk.borrow().clone();
273 let h_g2 = P::G2Gadget::alloc_input(cs.ns(|| "h_g2"), || Ok(h_g2.into_projective()))?;
274 let g_alpha_g1 =
275 P::G1Gadget::alloc_input(cs.ns(|| "g_alpha"), || Ok(g_alpha_g1.into_projective()))?;
276 let h_beta_g2 =
277 P::G2Gadget::alloc_input(cs.ns(|| "h_beta"), || Ok(h_beta_g2.into_projective()))?;
278 let g_gamma_g1 = P::G1Gadget::alloc_input(cs.ns(|| "g_gamma_g1"), || {
279 Ok(g_gamma_g1.into_projective())
280 })?;
281 let h_gamma_g2 = P::G2Gadget::alloc_input(cs.ns(|| "h_gamma_g2"), || {
282 Ok(h_gamma_g2.into_projective())
283 })?;
284
285 let query = query
286 .into_iter()
287 .enumerate()
288 .map(|(i, query_i)| {
289 P::G1Gadget::alloc_input(cs.ns(|| format!("query_{}", i)), || {
290 Ok(query_i.into_projective())
291 })
292 })
293 .collect::<Vec<_>>()
294 .into_iter()
295 .collect::<Result<_, _>>()?;
296 Ok(Self {
297 h_g2,
298 g_alpha_g1,
299 h_beta_g2,
300 g_gamma_g1,
301 h_gamma_g2,
302 query,
303 })
304 })
305 }
306}
307
308impl<PairingE, ConstraintF, P> AllocGadget<Proof<PairingE>, ConstraintF>
309 for ProofGadget<PairingE, ConstraintF, P>
310where
311 PairingE: PairingEngine,
312 ConstraintF: Field,
313 P: PairingGadget<PairingE, ConstraintF>,
314{
315 #[inline]
316 fn alloc<FN, T, CS: ConstraintSystem<ConstraintF>>(
317 mut cs: CS,
318 value_gen: FN,
319 ) -> Result<Self, SynthesisError>
320 where
321 FN: FnOnce() -> Result<T, SynthesisError>,
322 T: Borrow<Proof<PairingE>>,
323 {
324 value_gen().and_then(|proof| {
325 let Proof { a, b, c } = proof.borrow().clone();
326 let a = P::G1Gadget::alloc_checked(cs.ns(|| "a"), || Ok(a.into_projective()))?;
327 let b = P::G2Gadget::alloc_checked(cs.ns(|| "b"), || Ok(b.into_projective()))?;
328 let c = P::G1Gadget::alloc_checked(cs.ns(|| "c"), || Ok(c.into_projective()))?;
329 Ok(Self { a, b, c })
330 })
331 }
332
333 #[inline]
334 fn alloc_input<FN, T, CS: ConstraintSystem<ConstraintF>>(
335 mut cs: CS,
336 value_gen: FN,
337 ) -> Result<Self, SynthesisError>
338 where
339 FN: FnOnce() -> Result<T, SynthesisError>,
340 T: Borrow<Proof<PairingE>>,
341 {
342 value_gen().and_then(|proof| {
343 let Proof { a, b, c } = proof.borrow().clone();
344 // We don't need to check here because the prime order check can be performed
345 // in plain.
346 let a = P::G1Gadget::alloc_input(cs.ns(|| "a"), || Ok(a.into_projective()))?;
347 let b = P::G2Gadget::alloc_input(cs.ns(|| "b"), || Ok(b.into_projective()))?;
348 let c = P::G1Gadget::alloc_input(cs.ns(|| "c"), || Ok(c.into_projective()))?;
349 Ok(Self { a, b, c })
350 })
351 }
352}
353
354impl<PairingE, ConstraintF, P> ToBytesGadget<ConstraintF>
355 for VerifyingKeyGadget<PairingE, ConstraintF, P>
356where
357 PairingE: PairingEngine,
358 ConstraintF: Field,
359 P: PairingGadget<PairingE, ConstraintF>,
360{
361 #[inline]
362 fn to_bytes<CS: ConstraintSystem<ConstraintF>>(
363 &self,
364 mut cs: CS,
365 ) -> Result<Vec<UInt8>, SynthesisError> {
366 let mut bytes = Vec::new();
367 bytes.extend_from_slice(&self.h_g2.to_bytes(&mut cs.ns(|| "h_g2 to bytes"))?);
368 bytes.extend_from_slice(
369 &self
370 .g_alpha_g1
371 .to_bytes(&mut cs.ns(|| "g_alpha_g1 to bytes"))?,
372 );
373 bytes.extend_from_slice(
374 &self
375 .h_beta_g2
376 .to_bytes(&mut cs.ns(|| "h_beta_g2 to bytes"))?,
377 );
378 bytes.extend_from_slice(
379 &self
380 .g_gamma_g1
381 .to_bytes(&mut cs.ns(|| "g_gamma_g1 to bytes"))?,
382 );
383 bytes.extend_from_slice(
384 &self
385 .h_gamma_g2
386 .to_bytes(&mut cs.ns(|| "h_gamma_g2 to bytes"))?,
387 );
388 for (i, q) in self.query.iter().enumerate() {
389 let mut cs = cs.ns(|| format!("Iteration {}", i));
390 bytes.extend_from_slice(&q.to_bytes(&mut cs.ns(|| "q"))?);
391 }
392 Ok(bytes)
393 }
394
395 fn to_bytes_strict<CS: ConstraintSystem<ConstraintF>>(
396 &self,
397 cs: CS,
398 ) -> Result<Vec<UInt8>, SynthesisError> {
399 self.to_bytes(cs)
400 }
401}
402
403#[cfg(test)]
404mod test {
405 use gm17::*;
406 use r1cs_core::{ConstraintSynthesizer, ConstraintSystem, SynthesisError};
407
408 use super::*;
409 use algebra::{
410 curves::bls12_377::Bls12_377,
411 fields::bls12_377::Fr,
412 fields::bls12_377::Fq,
413 BitIterator, PrimeField,
414 };
415 use rand::{thread_rng, Rng};
416 use r1cs_std::{
417 boolean::Boolean, pairing::bls12_377::PairingGadget as Bls12_377PairingGadget,
418 test_constraint_system::TestConstraintSystem,
419 };
420
421 type TestProofSystem = Gm17<Bls12_377, Bench<Fr>, Fr>;
422 type TestVerifierGadget = Gm17VerifierGadget<Bls12_377, Fq, Bls12_377PairingGadget>;
423 type TestProofGadget = ProofGadget<Bls12_377, Fq, Bls12_377PairingGadget>;
424 type TestVkGadget = VerifyingKeyGadget<Bls12_377, Fq, Bls12_377PairingGadget>;
425
426 struct Bench<F: Field> {
427 inputs: Vec<Option<F>>,
428 num_constraints: usize,
429 }
430
431 impl<F: Field> ConstraintSynthesizer<F> for Bench<F> {
432 fn generate_constraints<CS: ConstraintSystem<F>>(self, cs: &mut CS) -> Result<(), SynthesisError> {
433 assert!(self.inputs.len() >= 2);
434 assert!(self.num_constraints >= self.inputs.len());
435
436 let mut variables: Vec<_> = Vec::with_capacity(self.inputs.len());
437 for (i, input) in self.inputs.into_iter().enumerate() {
438 let input_var = cs.alloc_input(
439 || format!("Input {}", i),
440 || input.ok_or(SynthesisError::AssignmentMissing),
441 )?;
442 variables.push((input, input_var));
443 }
444
445 for i in 0..self.num_constraints {
446 let new_entry = {
447 let (input_1_val, input_1_var) = variables[i];
448 let (input_2_val, input_2_var) = variables[i + 1];
449 let result_val = input_1_val
450 .and_then(|input_1| input_2_val.map(|input_2| input_1 * &input_2));
451 let result_var = cs.alloc(
452 || format!("Result {}", i),
453 || result_val.ok_or(SynthesisError::AssignmentMissing),
454 )?;
455 cs.enforce(
456 || format!("Enforce constraint {}", i),
457 |lc| lc + input_1_var,
458 |lc| lc + input_2_var,
459 |lc| lc + result_var,
460 );
461 (result_val, result_var)
462 };
463 variables.push(new_entry);
464 }
465 Ok(())
466 }
467 }
468
469 #[test]
470 fn gm17_verifier_test() {
471 let num_inputs = 100;
472 let num_constraints = num_inputs;
473 let rng = &mut thread_rng();
474 let mut inputs: Vec<Option<Fr>> = Vec::with_capacity(num_inputs);
475 for _ in 0..num_inputs {
476 inputs.push(Some(rng.gen()));
477 }
478 let params = {
479 let c = Bench::<Fr> {
480 inputs: vec![None; num_inputs],
481 num_constraints,
482 };
483
484 generate_random_parameters(c, rng).unwrap()
485 };
486
487 {
488 let proof = {
489 // Create an instance of our circuit (with the
490 // witness)
491 let c = Bench {
492 inputs: inputs.clone(),
493 num_constraints,
494 };
495 // Create a gm17 proof with our parameters.
496 create_random_proof(c, ¶ms, rng).unwrap()
497 };
498
499 // assert!(!verify_proof(&pvk, &proof, &[a]).unwrap());
500 let mut cs = TestConstraintSystem::<Fq>::new();
501
502 let inputs: Vec<_> = inputs.into_iter().map(|input| input.unwrap()).collect();
503 let mut input_gadgets = Vec::new();
504
505 {
506 let mut cs = cs.ns(|| "Allocate Input");
507 for (i, input) in inputs.into_iter().enumerate() {
508 let mut input_bits = BitIterator::new(input.into_repr()).collect::<Vec<_>>();
509 // Input must be in little-endian, but BitIterator outputs in big-endian.
510 input_bits.reverse();
511
512 let input_bits =
513 Vec::<Boolean>::alloc_input(cs.ns(|| format!("Input {}", i)), || {
514 Ok(input_bits)
515 })
516 .unwrap();
517 input_gadgets.push(input_bits);
518 }
519 }
520
521 let vk_gadget = TestVkGadget::alloc_input(cs.ns(|| "Vk"), || Ok(¶ms.vk)).unwrap();
522 let proof_gadget =
523 TestProofGadget::alloc(cs.ns(|| "Proof"), || Ok(proof.clone())).unwrap();
524 println!("Time to verify!\n\n\n\n");
525 <TestVerifierGadget as NIZKVerifierGadget<TestProofSystem, Fq>>::check_verify(
526 cs.ns(|| "Verify"),
527 &vk_gadget,
528 input_gadgets.iter(),
529 &proof_gadget,
530 )
531 .unwrap();
532 if !cs.is_satisfied() {
533 println!("=========================================================");
534 println!("Unsatisfied constraints:");
535 println!("{:?}", cs.which_is_unsatisfied().unwrap());
536 println!("=========================================================");
537 }
538
539 // cs.print_named_objects();
540 assert!(cs.is_satisfied());
541 }
542 }
543}