halo2_axiom/poly/kzg/
msm.rs

Help
1use std::fmt::Debug;
2
3use super::commitment::ParamsKZG;
4use crate::{
5    arithmetic::{best_multiexp, parallelize, CurveAffine},
6    poly::commitment::MSM,
7};
8use group::{Curve, Group};
9use pairing::{Engine, MillerLoopResult, MultiMillerLoop};
10
11/// A multiscalar multiplication in the polynomial commitment scheme
12#[derive(Clone, Default, Debug)]
13pub struct MSMKZG<E: Engine> {
14    pub(crate) scalars: Vec<E::Fr>,
15    pub(crate) bases: Vec<E::G1>,
16}
17
18impl<E: Engine> MSMKZG<E> {
19    /// Create an empty MSM instance
20    pub fn new() -> Self {
21        MSMKZG {
22            scalars: vec![],
23            bases: vec![],
24        }
25    }
26
27    /// Prepares all scalars in the MSM to linear combination
28    pub fn combine_with_base(&mut self, base: E::Fr) {
29        use ff::Field;
30        let mut acc = E::Fr::ONE;
31        if !self.scalars.is_empty() {
32            for scalar in self.scalars.iter_mut().rev() {
33                *scalar *= &acc;
34                acc *= base;
35            }
36        }
37    }
38}
39
40impl<E> MSM<E::G1Affine> for MSMKZG<E>
41where
42    E: Engine + Debug,
43    E::G1Affine: CurveAffine<ScalarExt = E::Fr, CurveExt = E::G1>,
44{
45    fn append_term(&mut self, scalar: E::Fr, point: E::G1) {
46        self.scalars.push(scalar);
47        self.bases.push(point);
48    }
49
50    fn add_msm(&mut self, other: &Self) {
51        self.scalars.extend(other.scalars().iter());
52        self.bases.extend(other.bases().iter());
53    }
54
55    fn scale(&mut self, factor: E::Fr) {
56        if !self.scalars.is_empty() {
57            parallelize(&mut self.scalars, |scalars, _| {
58                for other_scalar in scalars {
59                    *other_scalar *= &factor;
60                }
61            })
62        }
63    }
64
65    fn check(&self) -> bool {
66        bool::from(self.eval().is_identity())
67    }
68
69    fn eval(&self) -> E::G1 {
70        use group::prime::PrimeCurveAffine;
71        let mut bases = vec![E::G1Affine::identity(); self.scalars.len()];
72        E::G1::batch_normalize(&self.bases, &mut bases);
73        best_multiexp(&self.scalars, &bases)
74    }
75
76    fn bases(&self) -> Vec<E::G1> {
77        self.bases.clone()
78    }
79
80    fn scalars(&self) -> Vec<E::Fr> {
81        self.scalars.clone()
82    }
83}
84
85/// A projective point collector
86#[derive(Debug, Clone)]
87pub(crate) struct PreMSM<E: Engine> {
88    projectives_msms: Vec<MSMKZG<E>>,
89}
90
91impl<E: Engine + Debug> PreMSM<E> {
92    pub(crate) fn new() -> Self {
93        PreMSM {
94            projectives_msms: vec![],
95        }
96    }
97
98    pub(crate) fn normalize(self) -> MSMKZG<E> {
99        let (scalars, bases) = self
100            .projectives_msms
101            .into_iter()
102            .map(|msm| (msm.scalars, msm.bases))
103            .unzip::<_, _, Vec<_>, Vec<_>>();
104
105        MSMKZG {
106            scalars: scalars.into_iter().flatten().collect(),
107            bases: bases.into_iter().flatten().collect(),
108        }
109    }
110
111    pub(crate) fn add_msm(&mut self, other: MSMKZG<E>) {
112        self.projectives_msms.push(other);
113    }
114}
115
116impl<'params, E: MultiMillerLoop + Debug> From<&'params ParamsKZG<E>> for DualMSM<'params, E> {
117    fn from(params: &'params ParamsKZG<E>) -> Self {
118        DualMSM::new(params)
119    }
120}
121
122/// Two channel MSM accumulator
123#[derive(Debug, Clone)]
124pub struct DualMSM<'a, E: Engine> {
125    pub(crate) params: &'a ParamsKZG<E>,
126    pub(crate) left: MSMKZG<E>,
127    pub(crate) right: MSMKZG<E>,
128}
129
130impl<'a, E: MultiMillerLoop + Debug> DualMSM<'a, E> {
131    /// Create a new two channel MSM accumulator instance
132    pub fn new(params: &'a ParamsKZG<E>) -> Self {
133        Self {
134            params,
135            left: MSMKZG::new(),
136            right: MSMKZG::new(),
137        }
138    }
139}
140
141impl<'a, E: MultiMillerLoop + Debug> DualMSM<'a, E>
142where
143    E::G1Affine: CurveAffine<ScalarExt = E::Fr, CurveExt = E::G1>,
144{
145    /// Scale all scalars in the MSM by some scaling factor
146    pub fn scale(&mut self, e: E::Fr) {
147        self.left.scale(e);
148        self.right.scale(e);
149    }
150
151    /// Add another multiexp into this one
152    pub fn add_msm(&mut self, other: Self) {
153        self.left.add_msm(&other.left);
154        self.right.add_msm(&other.right);
155    }
156
157    /// Performs final pairing check with given verifier params and two channel linear combination
158    pub fn check(self) -> bool {
159        let s_g2_prepared = E::G2Prepared::from(self.params.s_g2);
160        let n_g2_prepared = E::G2Prepared::from(-self.params.g2);
161
162        let left = self.left.eval();
163        let right = self.right.eval();
164
165        let (term_1, term_2) = (
166            (&left.into(), &s_g2_prepared),
167            (&right.into(), &n_g2_prepared),
168        );
169        let terms = &[term_1, term_2];
170
171        bool::from(
172            E::multi_miller_loop(&terms[..])
173                .final_exponentiation()
174                .is_identity(),
175        )
176    }
177}
halo2_axiom/poly/kzg/msm.rs

halo2_axiom/poly/kzg/
msm.rs
