halo2_proofs/poly/
commitment.rs

Help
1//! This module contains an implementation of the polynomial commitment scheme
2//! described in the [Halo][halo] paper.
3//!
4//! [halo]: https://eprint.iacr.org/2019/1021
5
6use super::{Coeff, LagrangeCoeff, Polynomial};
7use crate::arithmetic::{
8    best_fft, best_multiexp, parallelize, CurveAffine, CurveExt, FieldExt, Group,
9};
10use crate::helpers::CurveRead;
11
12use ff::{Field, PrimeField};
13use group::{prime::PrimeCurveAffine, Curve, Group as _};
14use std::ops::{Add, AddAssign, Mul, MulAssign};
15
16mod msm;
17mod prover;
18mod verifier;
19
20pub use msm::MSM;
21pub use prover::create_proof;
22pub use verifier::{verify_proof, Accumulator, Guard};
23
24use std::io;
25
26/// These are the public parameters for the polynomial commitment scheme.
27#[derive(Clone, Debug)]
28pub struct Params<C: CurveAffine> {
29    pub(crate) k: u32,
30    pub(crate) n: u64,
31    pub(crate) g: Vec<C>,
32    pub(crate) g_lagrange: Vec<C>,
33    pub(crate) w: C,
34    pub(crate) u: C,
35}
36
37impl<C: CurveAffine> Params<C> {
38    /// Initializes parameters for the curve, given a random oracle to draw
39    /// points from.
40    pub fn new(k: u32) -> Self {
41        // This is usually a limitation on the curve, but we also want 32-bit
42        // architectures to be supported.
43        assert!(k < 32);
44
45        // In src/arithmetic/fields.rs we ensure that usize is at least 32 bits.
46
47        let n: u64 = 1 << k;
48
49        let g_projective = {
50            let mut g = Vec::with_capacity(n as usize);
51            g.resize(n as usize, C::Curve::identity());
52
53            parallelize(&mut g, move |g, start| {
54                let hasher = C::CurveExt::hash_to_curve("Halo2-Parameters");
55
56                for (i, g) in g.iter_mut().enumerate() {
57                    let i = (i + start) as u32;
58
59                    let mut message = [0u8; 5];
60                    message[1..5].copy_from_slice(&i.to_le_bytes());
61
62                    *g = hasher(&message);
63                }
64            });
65
66            g
67        };
68
69        let g = {
70            let mut g = vec![C::identity(); n as usize];
71            parallelize(&mut g, |g, starts| {
72                C::Curve::batch_normalize(&g_projective[starts..(starts + g.len())], g);
73            });
74            g
75        };
76
77        // Let's evaluate all of the Lagrange basis polynomials
78        // using an inverse FFT.
79        let mut alpha_inv = <<C as PrimeCurveAffine>::Curve as Group>::Scalar::ROOT_OF_UNITY_INV;
80        for _ in k..C::Scalar::S {
81            alpha_inv = alpha_inv.square();
82        }
83        let mut g_lagrange_projective = g_projective;
84        best_fft(&mut g_lagrange_projective, alpha_inv, k);
85        let minv = C::Scalar::TWO_INV.pow_vartime(&[k as u64, 0, 0, 0]);
86        parallelize(&mut g_lagrange_projective, |g, _| {
87            for g in g.iter_mut() {
88                *g *= minv;
89            }
90        });
91
92        let g_lagrange = {
93            let mut g_lagrange = vec![C::identity(); n as usize];
94            parallelize(&mut g_lagrange, |g_lagrange, starts| {
95                C::Curve::batch_normalize(
96                    &g_lagrange_projective[starts..(starts + g_lagrange.len())],
97                    g_lagrange,
98                );
99            });
100            drop(g_lagrange_projective);
101            g_lagrange
102        };
103
104        let hasher = C::CurveExt::hash_to_curve("Halo2-Parameters");
105        let w = hasher(&[1]).to_affine();
106        let u = hasher(&[2]).to_affine();
107
108        Params {
109            k,
110            n,
111            g,
112            g_lagrange,
113            w,
114            u,
115        }
116    }
117
118    /// This computes a commitment to a polynomial described by the provided
119    /// slice of coefficients. The commitment will be blinded by the blinding
120    /// factor `r`.
121    pub fn commit(&self, poly: &Polynomial<C::Scalar, Coeff>, r: Blind<C::Scalar>) -> C::Curve {
122        let mut tmp_scalars = Vec::with_capacity(poly.len() + 1);
123        let mut tmp_bases = Vec::with_capacity(poly.len() + 1);
124
125        tmp_scalars.extend(poly.iter());
126        tmp_scalars.push(r.0);
127
128        tmp_bases.extend(self.g.iter());
129        tmp_bases.push(self.w);
130
131        best_multiexp::<C>(&tmp_scalars, &tmp_bases)
132    }
133
134    /// This commits to a polynomial using its evaluations over the $2^k$ size
135    /// evaluation domain. The commitment will be blinded by the blinding factor
136    /// `r`.
137    pub fn commit_lagrange(
138        &self,
139        poly: &Polynomial<C::Scalar, LagrangeCoeff>,
140        r: Blind<C::Scalar>,
141    ) -> C::Curve {
142        let mut tmp_scalars = Vec::with_capacity(poly.len() + 1);
143        let mut tmp_bases = Vec::with_capacity(poly.len() + 1);
144
145        tmp_scalars.extend(poly.iter());
146        tmp_scalars.push(r.0);
147
148        tmp_bases.extend(self.g_lagrange.iter());
149        tmp_bases.push(self.w);
150
151        best_multiexp::<C>(&tmp_scalars, &tmp_bases)
152    }
153
154    /// Generates an empty multiscalar multiplication struct using the
155    /// appropriate params.
156    pub fn empty_msm(&self) -> MSM<C> {
157        MSM::new(self)
158    }
159
160    /// Getter for g generators
161    pub fn get_g(&self) -> Vec<C> {
162        self.g.clone()
163    }
164
165    /// Writes params to a buffer.
166    pub fn write<W: io::Write>(&self, writer: &mut W) -> io::Result<()> {
167        writer.write_all(&self.k.to_le_bytes())?;
168        for g_element in &self.g {
169            writer.write_all(g_element.to_bytes().as_ref())?;
170        }
171        for g_lagrange_element in &self.g_lagrange {
172            writer.write_all(g_lagrange_element.to_bytes().as_ref())?;
173        }
174        writer.write_all(self.w.to_bytes().as_ref())?;
175        writer.write_all(self.u.to_bytes().as_ref())?;
176
177        Ok(())
178    }
179
180    /// Reads params from a buffer.
181    pub fn read<R: io::Read>(reader: &mut R) -> io::Result<Self> {
182        let mut k = [0u8; 4];
183        reader.read_exact(&mut k[..])?;
184        let k = u32::from_le_bytes(k);
185
186        let n: u64 = 1 << k;
187
188        let g: Vec<_> = (0..n).map(|_| C::read(reader)).collect::<Result<_, _>>()?;
189        let g_lagrange: Vec<_> = (0..n).map(|_| C::read(reader)).collect::<Result<_, _>>()?;
190
191        let w = C::read(reader)?;
192        let u = C::read(reader)?;
193
194        Ok(Params {
195            k,
196            n,
197            g,
198            g_lagrange,
199            w,
200            u,
201        })
202    }
203}
204
205/// Wrapper type around a blinding factor.
206#[derive(Copy, Clone, Eq, PartialEq, Debug)]
207pub struct Blind<F>(pub F);
208
209impl<F: FieldExt> Default for Blind<F> {
210    fn default() -> Self {
211        Blind(F::one())
212    }
213}
214
215impl<F: FieldExt> Add for Blind<F> {
216    type Output = Self;
217
218    fn add(self, rhs: Blind<F>) -> Self {
219        Blind(self.0 + rhs.0)
220    }
221}
222
223impl<F: FieldExt> Mul for Blind<F> {
224    type Output = Self;
225
226    fn mul(self, rhs: Blind<F>) -> Self {
227        Blind(self.0 * rhs.0)
228    }
229}
230
231impl<F: FieldExt> AddAssign for Blind<F> {
232    fn add_assign(&mut self, rhs: Blind<F>) {
233        self.0 += rhs.0;
234    }
235}
236
237impl<F: FieldExt> MulAssign for Blind<F> {
238    fn mul_assign(&mut self, rhs: Blind<F>) {
239        self.0 *= rhs.0;
240    }
241}
242
243impl<F: FieldExt> AddAssign<F> for Blind<F> {
244    fn add_assign(&mut self, rhs: F) {
245        self.0 += rhs;
246    }
247}
248
249impl<F: FieldExt> MulAssign<F> for Blind<F> {
250    fn mul_assign(&mut self, rhs: F) {
251        self.0 *= rhs;
252    }
253}
254
255#[test]
256fn test_commit_lagrange_epaffine() {
257    const K: u32 = 6;
258
259    use rand_core::OsRng;
260
261    use crate::pasta::{EpAffine, Fq};
262    let params = Params::<EpAffine>::new(K);
263    let domain = super::EvaluationDomain::new(1, K);
264
265    let mut a = domain.empty_lagrange();
266
267    for (i, a) in a.iter_mut().enumerate() {
268        *a = Fq::from(i as u64);
269    }
270
271    let b = domain.lagrange_to_coeff(a.clone());
272
273    let alpha = Blind(Fq::random(OsRng));
274
275    assert_eq!(params.commit(&b, alpha), params.commit_lagrange(&a, alpha));
276}
277
278#[test]
279fn test_commit_lagrange_eqaffine() {
280    const K: u32 = 6;
281
282    use rand_core::OsRng;
283
284    use crate::pasta::{EqAffine, Fp};
285    let params = Params::<EqAffine>::new(K);
286    let domain = super::EvaluationDomain::new(1, K);
287
288    let mut a = domain.empty_lagrange();
289
290    for (i, a) in a.iter_mut().enumerate() {
291        *a = Fp::from(i as u64);
292    }
293
294    let b = domain.lagrange_to_coeff(a.clone());
295
296    let alpha = Blind(Fp::random(OsRng));
297
298    assert_eq!(params.commit(&b, alpha), params.commit_lagrange(&a, alpha));
299}
300
301#[test]
302fn test_opening_proof() {
303    const K: u32 = 6;
304
305    use ff::Field;
306    use rand_core::OsRng;
307
308    use super::{
309        commitment::{Blind, Params},
310        EvaluationDomain,
311    };
312    use crate::arithmetic::{eval_polynomial, FieldExt};
313    use crate::pasta::{EpAffine, Fq};
314    use crate::transcript::{
315        Blake2bRead, Blake2bWrite, Challenge255, Transcript, TranscriptRead, TranscriptWrite,
316    };
317
318    let rng = OsRng;
319
320    let params = Params::<EpAffine>::new(K);
321    let mut params_buffer = vec![];
322    params.write(&mut params_buffer).unwrap();
323    let params: Params<EpAffine> = Params::read::<_>(&mut &params_buffer[..]).unwrap();
324
325    let domain = EvaluationDomain::new(1, K);
326
327    let mut px = domain.empty_coeff();
328
329    for (i, a) in px.iter_mut().enumerate() {
330        *a = Fq::from(i as u64);
331    }
332
333    let blind = Blind(Fq::random(rng));
334
335    let p = params.commit(&px, blind).to_affine();
336
337    let mut transcript = Blake2bWrite::<Vec<u8>, EpAffine, Challenge255<EpAffine>>::init(vec![]);
338    transcript.write_point(p).unwrap();
339    let x = transcript.squeeze_challenge_scalar::<()>();
340    // Evaluate the polynomial
341    let v = eval_polynomial(&px, *x);
342    transcript.write_scalar(v).unwrap();
343
344    let (proof, ch_prover) = {
345        create_proof(&params, rng, &mut transcript, &px, blind, *x).unwrap();
346        let ch_prover = transcript.squeeze_challenge();
347        (transcript.finalize(), ch_prover)
348    };
349
350    // Verify the opening proof
351    let mut transcript = Blake2bRead::<&[u8], EpAffine, Challenge255<EpAffine>>::init(&proof[..]);
352    let p_prime = transcript.read_point().unwrap();
353    assert_eq!(p, p_prime);
354    let x_prime = transcript.squeeze_challenge_scalar::<()>();
355    assert_eq!(*x, *x_prime);
356    let v_prime = transcript.read_scalar().unwrap();
357    assert_eq!(v, v_prime);
358
359    let mut commitment_msm = params.empty_msm();
360    commitment_msm.append_term(Field::one(), p);
361    let guard = verify_proof(&params, commitment_msm, &mut transcript, *x, v).unwrap();
362    let ch_verifier = transcript.squeeze_challenge();
363    assert_eq!(*ch_prover, *ch_verifier);
364
365    // Test guard behavior prior to checking another proof
366    {
367        // Test use_challenges()
368        let msm_challenges = guard.clone().use_challenges();
369        assert!(msm_challenges.eval());
370
371        // Test use_g()
372        let g = guard.compute_g();
373        let (msm_g, _accumulator) = guard.clone().use_g(g);
374        assert!(msm_g.eval());
375    }
376}
halo2_proofs/poly/commitment.rs

halo2_proofs/poly/
commitment.rs
