snark_verifier/pcs/kzg/
accumulator.rs

Help
1use crate::{loader::Loader, util::arithmetic::CurveAffine};
2use std::fmt::Debug;
3
4/// KZG accumulator, containing lhs G1 and rhs G1 of pairing.
5#[derive(Clone, Debug)]
6pub struct KzgAccumulator<C, L>
7where
8    C: CurveAffine,
9    L: Loader<C>,
10{
11    /// Left-hand side G1 of pairing.
12    pub lhs: L::LoadedEcPoint,
13    /// Right-hand side G1 of pairing.
14    pub rhs: L::LoadedEcPoint,
15}
16
17impl<C, L> KzgAccumulator<C, L>
18where
19    C: CurveAffine,
20    L: Loader<C>,
21{
22    /// Initialize a [`KzgAccumulator`].
23    pub fn new(lhs: L::LoadedEcPoint, rhs: L::LoadedEcPoint) -> Self {
24        Self { lhs, rhs }
25    }
26}
27
28/// `AccumulatorEncoding` that encodes `Accumulator` into limbs.
29///
30/// Since in circuit everything are in scalar field, but `Accumulator` might contain base field elements, so we split them into limbs.
31/// The const generic `LIMBS` and `BITS` respectively represents how many limbs
32/// a base field element are split into and how many bits each limbs could have.
33#[derive(Clone, Debug)]
34pub struct LimbsEncoding<const LIMBS: usize, const BITS: usize>;
35
36mod native {
37    use crate::{
38        loader::native::NativeLoader,
39        pcs::{
40            kzg::{KzgAccumulator, LimbsEncoding},
41            AccumulatorEncoding,
42        },
43        util::{
44            arithmetic::{fe_from_limbs, CurveAffine},
45            Itertools,
46        },
47        Error,
48    };
49
50    impl<C, const LIMBS: usize, const BITS: usize> AccumulatorEncoding<C, NativeLoader>
51        for LimbsEncoding<LIMBS, BITS>
52    where
53        C: CurveAffine,
54    {
55        type Accumulator = KzgAccumulator<C, NativeLoader>;
56
57        fn from_repr(limbs: &[&C::Scalar]) -> Result<Self::Accumulator, Error> {
58            assert_eq!(limbs.len(), 4 * LIMBS);
59
60            let [lhs_x, lhs_y, rhs_x, rhs_y]: [_; 4] = limbs
61                .chunks(LIMBS)
62                .map(|limbs| {
63                    fe_from_limbs::<_, _, LIMBS, BITS>(
64                        limbs.iter().map(|limb| **limb).collect_vec().try_into().unwrap(),
65                    )
66                })
67                .collect_vec()
68                .try_into()
69                .unwrap();
70            let accumulator = KzgAccumulator::new(
71                C::from_xy(lhs_x, lhs_y).unwrap(),
72                C::from_xy(rhs_x, rhs_y).unwrap(),
73            );
74
75            Ok(accumulator)
76        }
77    }
78}
79
80#[cfg(feature = "loader_evm")]
81mod evm {
82    use crate::{
83        loader::evm::{EvmLoader, Scalar},
84        pcs::{
85            kzg::{KzgAccumulator, LimbsEncoding},
86            AccumulatorEncoding,
87        },
88        util::{
89            arithmetic::{CurveAffine, PrimeField},
90            Itertools,
91        },
92        Error,
93    };
94    use std::rc::Rc;
95
96    impl<C, const LIMBS: usize, const BITS: usize> AccumulatorEncoding<C, Rc<EvmLoader>>
97        for LimbsEncoding<LIMBS, BITS>
98    where
99        C: CurveAffine,
100        C::Scalar: PrimeField<Repr = [u8; 0x20]>,
101    {
102        type Accumulator = KzgAccumulator<C, Rc<EvmLoader>>;
103
104        fn from_repr(limbs: &[&Scalar]) -> Result<Self::Accumulator, Error> {
105            assert_eq!(limbs.len(), 4 * LIMBS);
106
107            let loader = limbs[0].loader();
108
109            let [lhs_x, lhs_y, rhs_x, rhs_y]: [[_; LIMBS]; 4] = limbs
110                .chunks(LIMBS)
111                .map(|limbs| limbs.to_vec().try_into().unwrap())
112                .collect_vec()
113                .try_into()
114                .unwrap();
115            let accumulator = KzgAccumulator::new(
116                loader.ec_point_from_limbs::<LIMBS, BITS>(lhs_x, lhs_y),
117                loader.ec_point_from_limbs::<LIMBS, BITS>(rhs_x, rhs_y),
118            );
119
120            Ok(accumulator)
121        }
122    }
123}
124
125#[cfg(feature = "loader_halo2")]
126pub use halo2::LimbsEncodingInstructions;
127
128#[cfg(feature = "loader_halo2")]
129mod halo2 {
130    use crate::{
131        loader::halo2::{EccInstructions, Halo2Loader, Scalar},
132        pcs::{
133            kzg::{KzgAccumulator, LimbsEncoding},
134            AccumulatorEncoding,
135        },
136        util::{
137            arithmetic::{fe_from_limbs, CurveAffine},
138            Itertools,
139        },
140        Error,
141    };
142    use std::{iter, ops::Deref, rc::Rc};
143
144    fn ec_point_from_limbs<C: CurveAffine, const LIMBS: usize, const BITS: usize>(
145        limbs: &[&C::Scalar],
146    ) -> C {
147        assert_eq!(limbs.len(), 2 * LIMBS);
148
149        let [x, y] = [&limbs[..LIMBS], &limbs[LIMBS..]].map(|limbs| {
150            fe_from_limbs::<_, _, LIMBS, BITS>(
151                limbs.iter().map(|limb| **limb).collect_vec().try_into().unwrap(),
152            )
153        });
154
155        C::from_xy(x, y).unwrap()
156    }
157
158    /// Instructions to encode/decode a elliptic curve point into/from limbs.
159    pub trait LimbsEncodingInstructions<C: CurveAffine, const LIMBS: usize, const BITS: usize>:
160        EccInstructions<C>
161    {
162        /// Decode and assign an elliptic curve point from limbs.
163        fn assign_ec_point_from_limbs(
164            &self,
165            ctx: &mut Self::Context,
166            limbs: &[impl Deref<Target = Self::AssignedScalar>],
167        ) -> Self::AssignedEcPoint;
168
169        /// Encode an elliptic curve point into limbs.
170        fn assign_ec_point_to_limbs(
171            &self,
172            ctx: &mut Self::Context,
173            ec_point: impl Deref<Target = Self::AssignedEcPoint>,
174        ) -> Vec<Self::AssignedCell>;
175    }
176
177    impl<C, EccChip, const LIMBS: usize, const BITS: usize>
178        AccumulatorEncoding<C, Rc<Halo2Loader<C, EccChip>>> for LimbsEncoding<LIMBS, BITS>
179    where
180        C: CurveAffine,
181        EccChip: LimbsEncodingInstructions<C, LIMBS, BITS>,
182    {
183        type Accumulator = KzgAccumulator<C, Rc<Halo2Loader<C, EccChip>>>;
184
185        fn from_repr(limbs: &[&Scalar<C, EccChip>]) -> Result<Self::Accumulator, Error> {
186            assert_eq!(limbs.len(), 4 * LIMBS);
187
188            let loader = limbs[0].loader();
189
190            let [lhs, rhs] = [&limbs[..2 * LIMBS], &limbs[2 * LIMBS..]].map(|limbs| {
191                let assigned = loader.ecc_chip().assign_ec_point_from_limbs(
192                    &mut loader.ctx_mut(),
193                    &limbs.iter().map(|limb| limb.assigned()).collect_vec(),
194                );
195                loader.ec_point_from_assigned(assigned)
196            });
197
198            Ok(KzgAccumulator::new(lhs, rhs))
199        }
200    }
201
202    mod halo2_lib {
203        use super::*;
204        use halo2_base::utils::BigPrimeField;
205        use halo2_base::utils::CurveAffineExt;
206        use halo2_ecc::ecc::BaseFieldEccChip;
207
208        impl<C, const LIMBS: usize, const BITS: usize>
209            LimbsEncodingInstructions<C, LIMBS, BITS> for BaseFieldEccChip<'_, C>
210        where
211            C: CurveAffineExt,
212            C::ScalarExt: BigPrimeField,
213            C::Base: BigPrimeField,
214        {
215            fn assign_ec_point_from_limbs(
216                &self,
217                ctx: &mut Self::Context,
218                limbs: &[impl Deref<Target = Self::AssignedScalar>],
219            ) -> Self::AssignedEcPoint {
220                assert_eq!(limbs.len(), 2 * LIMBS);
221
222                let ec_point = self.assign_point::<C>(
223                    ctx.main(),
224                    ec_point_from_limbs::<_, LIMBS, BITS>(
225                        &limbs.iter().map(|limb| limb.value()).collect_vec(),
226                    ),
227                );
228
229                for (src, dst) in limbs
230                    .iter()
231                    .zip_eq(iter::empty().chain(ec_point.x().limbs()).chain(ec_point.y().limbs()))
232                {
233                    ctx.main().constrain_equal(src, dst);
234                }
235
236                ec_point
237            }
238
239            fn assign_ec_point_to_limbs(
240                &self,
241                _: &mut Self::Context,
242                ec_point: impl Deref<Target = Self::AssignedEcPoint>,
243            ) -> Vec<Self::AssignedCell> {
244                iter::empty()
245                    .chain(ec_point.x().limbs())
246                    .chain(ec_point.y().limbs())
247                    .copied()
248                    .collect()
249            }
250        }
251    }
252}
snark_verifier/pcs/kzg/accumulator.rs

snark_verifier/pcs/kzg/
accumulator.rs
