bellman/groth16/
mod.rs

1//! The [Groth16] proving system.
2//!
3//! [Groth16]: https://eprint.iacr.org/2016/260
4
5use group::{prime::PrimeCurveAffine, GroupEncoding, UncompressedEncoding};
6use pairing::{Engine, MultiMillerLoop};
7
8use crate::SynthesisError;
9
10use crate::multiexp::SourceBuilder;
11use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt};
12use std::io::{self, Read, Write};
13use std::sync::Arc;
14
15#[cfg(test)]
16mod tests;
17
18mod generator;
19mod prover;
20mod verifier;
21
22pub use self::generator::*;
23pub use self::prover::*;
24pub use self::verifier::*;
25
26#[derive(Clone, Debug)]
27pub struct Proof<E: Engine> {
28    pub a: E::G1Affine,
29    pub b: E::G2Affine,
30    pub c: E::G1Affine,
31}
32
33impl<E: Engine> PartialEq for Proof<E> {
34    fn eq(&self, other: &Self) -> bool {
35        self.a == other.a && self.b == other.b && self.c == other.c
36    }
37}
38
39impl<E: Engine> Proof<E> {
40    pub fn write<W: Write>(&self, mut writer: W) -> io::Result<()> {
41        writer.write_all(self.a.to_bytes().as_ref())?;
42        writer.write_all(self.b.to_bytes().as_ref())?;
43        writer.write_all(self.c.to_bytes().as_ref())?;
44
45        Ok(())
46    }
47
48    pub fn read<R: Read>(mut reader: R) -> io::Result<Self> {
49        let read_g1 = |reader: &mut R| -> io::Result<E::G1Affine> {
50            let mut g1_repr = <E::G1Affine as GroupEncoding>::Repr::default();
51            reader.read_exact(g1_repr.as_mut())?;
52
53            let affine = E::G1Affine::from_bytes(&g1_repr);
54            let affine = if affine.is_some().into() {
55                Ok(affine.unwrap())
56            } else {
57                Err(io::Error::new(io::ErrorKind::InvalidData, "invalid G1"))
58            };
59
60            affine.and_then(|e| {
61                if e.is_identity().into() {
62                    Err(io::Error::new(
63                        io::ErrorKind::InvalidData,
64                        "point at infinity",
65                    ))
66                } else {
67                    Ok(e)
68                }
69            })
70        };
71
72        let read_g2 = |reader: &mut R| -> io::Result<E::G2Affine> {
73            let mut g2_repr = <E::G2Affine as GroupEncoding>::Repr::default();
74            reader.read_exact(g2_repr.as_mut())?;
75
76            let affine = E::G2Affine::from_bytes(&g2_repr);
77            let affine = if affine.is_some().into() {
78                Ok(affine.unwrap())
79            } else {
80                Err(io::Error::new(io::ErrorKind::InvalidData, "invalid G2"))
81            };
82
83            affine.and_then(|e| {
84                if e.is_identity().into() {
85                    Err(io::Error::new(
86                        io::ErrorKind::InvalidData,
87                        "point at infinity",
88                    ))
89                } else {
90                    Ok(e)
91                }
92            })
93        };
94
95        let a = read_g1(&mut reader)?;
96        let b = read_g2(&mut reader)?;
97        let c = read_g1(&mut reader)?;
98
99        Ok(Proof { a, b, c })
100    }
101}
102
103#[derive(Clone)]
104pub struct VerifyingKey<E: Engine> {
105    // alpha in g1 for verifying and for creating A/C elements of
106    // proof. Never the point at infinity.
107    pub alpha_g1: E::G1Affine,
108
109    // beta in g1 and g2 for verifying and for creating B/C elements
110    // of proof. Never the point at infinity.
111    pub beta_g1: E::G1Affine,
112    pub beta_g2: E::G2Affine,
113
114    // gamma in g2 for verifying. Never the point at infinity.
115    pub gamma_g2: E::G2Affine,
116
117    // delta in g1/g2 for verifying and proving, essentially the magic
118    // trapdoor that forces the prover to evaluate the C element of the
119    // proof with only components from the CRS. Never the point at
120    // infinity.
121    pub delta_g1: E::G1Affine,
122    pub delta_g2: E::G2Affine,
123
124    // Elements of the form (beta * u_i(tau) + alpha v_i(tau) + w_i(tau)) / gamma
125    // for all public inputs. Because all public inputs have a dummy constraint,
126    // this is the same size as the number of inputs, and never contains points
127    // at infinity.
128    pub ic: Vec<E::G1Affine>,
129}
130
131impl<E: Engine> PartialEq for VerifyingKey<E> {
132    fn eq(&self, other: &Self) -> bool {
133        self.alpha_g1 == other.alpha_g1
134            && self.beta_g1 == other.beta_g1
135            && self.beta_g2 == other.beta_g2
136            && self.gamma_g2 == other.gamma_g2
137            && self.delta_g1 == other.delta_g1
138            && self.delta_g2 == other.delta_g2
139            && self.ic == other.ic
140    }
141}
142
143impl<E: Engine> VerifyingKey<E> {
144    pub fn write<W: Write>(&self, mut writer: W) -> io::Result<()> {
145        writer.write_all(self.alpha_g1.to_uncompressed().as_ref())?;
146        writer.write_all(self.beta_g1.to_uncompressed().as_ref())?;
147        writer.write_all(self.beta_g2.to_uncompressed().as_ref())?;
148        writer.write_all(self.gamma_g2.to_uncompressed().as_ref())?;
149        writer.write_all(self.delta_g1.to_uncompressed().as_ref())?;
150        writer.write_all(self.delta_g2.to_uncompressed().as_ref())?;
151        writer.write_u32::<BigEndian>(self.ic.len() as u32)?;
152        for ic in &self.ic {
153            writer.write_all(ic.to_uncompressed().as_ref())?;
154        }
155
156        Ok(())
157    }
158
159    pub fn read<R: Read>(mut reader: R) -> io::Result<Self> {
160        let read_g1 = |reader: &mut R| -> io::Result<E::G1Affine> {
161            let mut g1_repr = <E::G1Affine as UncompressedEncoding>::Uncompressed::default();
162            reader.read_exact(g1_repr.as_mut())?;
163
164            let affine = E::G1Affine::from_uncompressed(&g1_repr);
165            if affine.is_some().into() {
166                Ok(affine.unwrap())
167            } else {
168                Err(io::Error::new(io::ErrorKind::InvalidData, "invalid G1"))
169            }
170        };
171
172        let read_g2 = |reader: &mut R| -> io::Result<E::G2Affine> {
173            let mut g2_repr = <E::G2Affine as UncompressedEncoding>::Uncompressed::default();
174            reader.read_exact(g2_repr.as_mut())?;
175
176            let affine = E::G2Affine::from_uncompressed(&g2_repr);
177            if affine.is_some().into() {
178                Ok(affine.unwrap())
179            } else {
180                Err(io::Error::new(io::ErrorKind::InvalidData, "invalid G2"))
181            }
182        };
183
184        let alpha_g1 = read_g1(&mut reader)?;
185        let beta_g1 = read_g1(&mut reader)?;
186        let beta_g2 = read_g2(&mut reader)?;
187        let gamma_g2 = read_g2(&mut reader)?;
188        let delta_g1 = read_g1(&mut reader)?;
189        let delta_g2 = read_g2(&mut reader)?;
190
191        let ic_len = reader.read_u32::<BigEndian>()? as usize;
192
193        let mut ic = vec![];
194
195        for _ in 0..ic_len {
196            let g1 = read_g1(&mut reader).and_then(|e| {
197                if e.is_identity().into() {
198                    Err(io::Error::new(
199                        io::ErrorKind::InvalidData,
200                        "point at infinity",
201                    ))
202                } else {
203                    Ok(e)
204                }
205            })?;
206
207            ic.push(g1);
208        }
209
210        Ok(VerifyingKey {
211            alpha_g1,
212            beta_g1,
213            beta_g2,
214            gamma_g2,
215            delta_g1,
216            delta_g2,
217            ic,
218        })
219    }
220}
221
222#[derive(Clone)]
223pub struct Parameters<E: Engine> {
224    pub vk: VerifyingKey<E>,
225
226    // Elements of the form ((tau^i * t(tau)) / delta) for i between 0 and
227    // m-2 inclusive. Never contains points at infinity.
228    pub h: Arc<Vec<E::G1Affine>>,
229
230    // Elements of the form (beta * u_i(tau) + alpha v_i(tau) + w_i(tau)) / delta
231    // for all auxiliary inputs. Variables can never be unconstrained, so this
232    // never contains points at infinity.
233    pub l: Arc<Vec<E::G1Affine>>,
234
235    // QAP "A" polynomials evaluated at tau in the Lagrange basis. Never contains
236    // points at infinity: polynomials that evaluate to zero are omitted from
237    // the CRS and the prover can deterministically skip their evaluation.
238    pub a: Arc<Vec<E::G1Affine>>,
239
240    // QAP "B" polynomials evaluated at tau in the Lagrange basis. Needed in
241    // G1 and G2 for C/B queries, respectively. Never contains points at
242    // infinity for the same reason as the "A" polynomials.
243    pub b_g1: Arc<Vec<E::G1Affine>>,
244    pub b_g2: Arc<Vec<E::G2Affine>>,
245}
246
247impl<E: Engine> PartialEq for Parameters<E> {
248    fn eq(&self, other: &Self) -> bool {
249        self.vk == other.vk
250            && self.h == other.h
251            && self.l == other.l
252            && self.a == other.a
253            && self.b_g1 == other.b_g1
254            && self.b_g2 == other.b_g2
255    }
256}
257
258impl<E: Engine> Parameters<E> {
259    pub fn write<W: Write>(&self, mut writer: W) -> io::Result<()> {
260        self.vk.write(&mut writer)?;
261
262        writer.write_u32::<BigEndian>(self.h.len() as u32)?;
263        for g in &self.h[..] {
264            writer.write_all(g.to_uncompressed().as_ref())?;
265        }
266
267        writer.write_u32::<BigEndian>(self.l.len() as u32)?;
268        for g in &self.l[..] {
269            writer.write_all(g.to_uncompressed().as_ref())?;
270        }
271
272        writer.write_u32::<BigEndian>(self.a.len() as u32)?;
273        for g in &self.a[..] {
274            writer.write_all(g.to_uncompressed().as_ref())?;
275        }
276
277        writer.write_u32::<BigEndian>(self.b_g1.len() as u32)?;
278        for g in &self.b_g1[..] {
279            writer.write_all(g.to_uncompressed().as_ref())?;
280        }
281
282        writer.write_u32::<BigEndian>(self.b_g2.len() as u32)?;
283        for g in &self.b_g2[..] {
284            writer.write_all(g.to_uncompressed().as_ref())?;
285        }
286
287        Ok(())
288    }
289
290    pub fn read<R: Read>(mut reader: R, checked: bool) -> io::Result<Self> {
291        let read_g1 = |reader: &mut R| -> io::Result<E::G1Affine> {
292            let mut repr = <E::G1Affine as UncompressedEncoding>::Uncompressed::default();
293            reader.read_exact(repr.as_mut())?;
294
295            let affine = if checked {
296                E::G1Affine::from_uncompressed(&repr)
297            } else {
298                E::G1Affine::from_uncompressed_unchecked(&repr)
299            };
300
301            let affine = if affine.is_some().into() {
302                Ok(affine.unwrap())
303            } else {
304                Err(io::Error::new(io::ErrorKind::InvalidData, "invalid G1"))
305            };
306
307            affine.and_then(|e| {
308                if e.is_identity().into() {
309                    Err(io::Error::new(
310                        io::ErrorKind::InvalidData,
311                        "point at infinity",
312                    ))
313                } else {
314                    Ok(e)
315                }
316            })
317        };
318
319        let read_g2 = |reader: &mut R| -> io::Result<E::G2Affine> {
320            let mut repr = <E::G2Affine as UncompressedEncoding>::Uncompressed::default();
321            reader.read_exact(repr.as_mut())?;
322
323            let affine = if checked {
324                E::G2Affine::from_uncompressed(&repr)
325            } else {
326                E::G2Affine::from_uncompressed_unchecked(&repr)
327            };
328
329            let affine = if affine.is_some().into() {
330                Ok(affine.unwrap())
331            } else {
332                Err(io::Error::new(io::ErrorKind::InvalidData, "invalid G2"))
333            };
334
335            affine.and_then(|e| {
336                if e.is_identity().into() {
337                    Err(io::Error::new(
338                        io::ErrorKind::InvalidData,
339                        "point at infinity",
340                    ))
341                } else {
342                    Ok(e)
343                }
344            })
345        };
346
347        let vk = VerifyingKey::<E>::read(&mut reader)?;
348
349        let mut h = vec![];
350        let mut l = vec![];
351        let mut a = vec![];
352        let mut b_g1 = vec![];
353        let mut b_g2 = vec![];
354
355        {
356            let len = reader.read_u32::<BigEndian>()? as usize;
357            for _ in 0..len {
358                h.push(read_g1(&mut reader)?);
359            }
360        }
361
362        {
363            let len = reader.read_u32::<BigEndian>()? as usize;
364            for _ in 0..len {
365                l.push(read_g1(&mut reader)?);
366            }
367        }
368
369        {
370            let len = reader.read_u32::<BigEndian>()? as usize;
371            for _ in 0..len {
372                a.push(read_g1(&mut reader)?);
373            }
374        }
375
376        {
377            let len = reader.read_u32::<BigEndian>()? as usize;
378            for _ in 0..len {
379                b_g1.push(read_g1(&mut reader)?);
380            }
381        }
382
383        {
384            let len = reader.read_u32::<BigEndian>()? as usize;
385            for _ in 0..len {
386                b_g2.push(read_g2(&mut reader)?);
387            }
388        }
389
390        Ok(Parameters {
391            vk,
392            h: Arc::new(h),
393            l: Arc::new(l),
394            a: Arc::new(a),
395            b_g1: Arc::new(b_g1),
396            b_g2: Arc::new(b_g2),
397        })
398    }
399}
400
401pub struct PreparedVerifyingKey<E: MultiMillerLoop> {
402    /// Pairing result of alpha*beta
403    alpha_g1_beta_g2: E::Gt,
404    /// -gamma in G2
405    neg_gamma_g2: E::G2Prepared,
406    /// -delta in G2
407    neg_delta_g2: E::G2Prepared,
408    /// Copy of IC from `VerifiyingKey`.
409    ic: Vec<E::G1Affine>,
410}
411
412pub trait ParameterSource<E: Engine> {
413    type G1Builder: SourceBuilder<E::G1Affine>;
414    type G2Builder: SourceBuilder<E::G2Affine>;
415
416    fn get_vk(&mut self, num_ic: usize) -> Result<VerifyingKey<E>, SynthesisError>;
417    fn get_h(&mut self, num_h: usize) -> Result<Self::G1Builder, SynthesisError>;
418    fn get_l(&mut self, num_l: usize) -> Result<Self::G1Builder, SynthesisError>;
419    fn get_a(
420        &mut self,
421        num_inputs: usize,
422        num_aux: usize,
423    ) -> Result<(Self::G1Builder, Self::G1Builder), SynthesisError>;
424    fn get_b_g1(
425        &mut self,
426        num_inputs: usize,
427        num_aux: usize,
428    ) -> Result<(Self::G1Builder, Self::G1Builder), SynthesisError>;
429    fn get_b_g2(
430        &mut self,
431        num_inputs: usize,
432        num_aux: usize,
433    ) -> Result<(Self::G2Builder, Self::G2Builder), SynthesisError>;
434}
435
436impl<'a, E: Engine> ParameterSource<E> for &'a Parameters<E> {
437    type G1Builder = (Arc<Vec<E::G1Affine>>, usize);
438    type G2Builder = (Arc<Vec<E::G2Affine>>, usize);
439
440    fn get_vk(&mut self, _: usize) -> Result<VerifyingKey<E>, SynthesisError> {
441        Ok(self.vk.clone())
442    }
443
444    fn get_h(&mut self, _: usize) -> Result<Self::G1Builder, SynthesisError> {
445        Ok((self.h.clone(), 0))
446    }
447
448    fn get_l(&mut self, _: usize) -> Result<Self::G1Builder, SynthesisError> {
449        Ok((self.l.clone(), 0))
450    }
451
452    fn get_a(
453        &mut self,
454        num_inputs: usize,
455        _: usize,
456    ) -> Result<(Self::G1Builder, Self::G1Builder), SynthesisError> {
457        Ok(((self.a.clone(), 0), (self.a.clone(), num_inputs)))
458    }
459
460    fn get_b_g1(
461        &mut self,
462        num_inputs: usize,
463        _: usize,
464    ) -> Result<(Self::G1Builder, Self::G1Builder), SynthesisError> {
465        Ok(((self.b_g1.clone(), 0), (self.b_g1.clone(), num_inputs)))
466    }
467
468    fn get_b_g2(
469        &mut self,
470        num_inputs: usize,
471        _: usize,
472    ) -> Result<(Self::G2Builder, Self::G2Builder), SynthesisError> {
473        Ok(((self.b_g2.clone(), 0), (self.b_g2.clone(), num_inputs)))
474    }
475}
476
477#[cfg(test)]
478mod test_with_bls12_381 {
479    use super::*;
480    use crate::{Circuit, ConstraintSystem, SynthesisError};
481
482    use bls12_381::{Bls12, Scalar};
483    use ff::{Field, PrimeField};
484    use rand::thread_rng;
485    use std::ops::MulAssign;
486
487    #[test]
488    fn serialization() {
489        struct MySillyCircuit<Scalar: PrimeField> {
490            a: Option<Scalar>,
491            b: Option<Scalar>,
492        }
493
494        impl<Scalar: PrimeField> Circuit<Scalar> for MySillyCircuit<Scalar> {
495            fn synthesize<CS: ConstraintSystem<Scalar>>(
496                self,
497                cs: &mut CS,
498            ) -> Result<(), SynthesisError> {
499                let a = cs.alloc(|| "a", || self.a.ok_or(SynthesisError::AssignmentMissing))?;
500                let b = cs.alloc(|| "b", || self.b.ok_or(SynthesisError::AssignmentMissing))?;
501                let c = cs.alloc_input(
502                    || "c",
503                    || {
504                        let mut a = self.a.ok_or(SynthesisError::AssignmentMissing)?;
505                        let b = self.b.ok_or(SynthesisError::AssignmentMissing)?;
506
507                        a.mul_assign(&b);
508                        Ok(a)
509                    },
510                )?;
511
512                cs.enforce(|| "a*b=c", |lc| lc + a, |lc| lc + b, |lc| lc + c);
513
514                Ok(())
515            }
516        }
517
518        let mut rng = thread_rng();
519
520        let params = generate_random_parameters::<Bls12, _, _>(
521            MySillyCircuit { a: None, b: None },
522            &mut rng,
523        )
524        .unwrap();
525
526        {
527            let mut v = vec![];
528
529            params.write(&mut v).unwrap();
530            assert_eq!(v.len(), 2136);
531
532            let de_params = Parameters::read(&v[..], true).unwrap();
533            assert!(params == de_params);
534
535            let de_params = Parameters::read(&v[..], false).unwrap();
536            assert!(params == de_params);
537        }
538
539        let pvk = prepare_verifying_key::<Bls12>(&params.vk);
540
541        for _ in 0..100 {
542            let a = Scalar::random(&mut rng);
543            let b = Scalar::random(&mut rng);
544            let mut c = a;
545            c.mul_assign(&b);
546
547            let proof = create_random_proof(
548                MySillyCircuit {
549                    a: Some(a),
550                    b: Some(b),
551                },
552                &params,
553                &mut rng,
554            )
555            .unwrap();
556
557            let mut v = vec![];
558            proof.write(&mut v).unwrap();
559
560            assert_eq!(v.len(), 192);
561
562            let de_proof = Proof::read(&v[..]).unwrap();
563            assert!(proof == de_proof);
564
565            assert!(verify_proof(&pvk, &proof, &[c]).is_ok());
566            assert!(verify_proof(&pvk, &proof, &[a]).is_err());
567        }
568    }
569}
bellman/groth16/mod.rs

bellman/groth16/
mod.rs
