snark_verifier/pcs/kzg/
decider.rs

Help
1use serde::{Deserialize, Serialize};
2
3use crate::{
4    pcs::kzg::KzgSuccinctVerifyingKey,
5    util::arithmetic::{CurveAffine, MultiMillerLoop},
6};
7use std::marker::PhantomData;
8
9/// KZG deciding key.
10#[derive(Debug, Clone, Copy, Serialize, Deserialize)]
11#[serde(bound(
12    serialize = "M::G1Affine: Serialize, M::G2Affine: Serialize",
13    deserialize = "M::G1Affine: Deserialize<'de>, M::G2Affine: Deserialize<'de>"
14))]
15pub struct KzgDecidingKey<M: MultiMillerLoop> {
16    svk: KzgSuccinctVerifyingKey<M::G1Affine>,
17    /// Generator on G2.
18    g2: M::G2Affine,
19    /// Generator to the trusted-setup secret on G2.
20    s_g2: M::G2Affine,
21    _marker: PhantomData<M>,
22}
23
24impl<M: MultiMillerLoop> KzgDecidingKey<M> {
25    /// Initialize a [`KzgDecidingKey`]
26    pub fn new(
27        svk: impl Into<KzgSuccinctVerifyingKey<M::G1Affine>>,
28        g2: M::G2Affine,
29        s_g2: M::G2Affine,
30    ) -> Self {
31        Self { svk: svk.into(), g2, s_g2, _marker: PhantomData }
32    }
33    /// Succinct verifying key.
34    pub fn svk(&self) -> KzgSuccinctVerifyingKey<M::G1Affine> {
35        self.svk
36    }
37    /// Generator on G2.
38    pub fn g2(&self) -> M::G2Affine {
39        self.g2
40    }
41    /// Generator to the trusted-setup secret on G2.
42    pub fn s_g2(&self) -> M::G2Affine {
43        self.s_g2
44    }
45}
46
47impl<M: MultiMillerLoop> From<(M::G1Affine, M::G2Affine, M::G2Affine)> for KzgDecidingKey<M>
48where
49    M::G1Affine: CurveAffine<ScalarExt = M::Fr, CurveExt = M::G1>,
50{
51    fn from((g1, g2, s_g2): (M::G1Affine, M::G2Affine, M::G2Affine)) -> KzgDecidingKey<M> {
52        KzgDecidingKey::new(g1, g2, s_g2)
53    }
54}
55
56impl<M: MultiMillerLoop> AsRef<KzgSuccinctVerifyingKey<M::G1Affine>> for KzgDecidingKey<M> {
57    fn as_ref(&self) -> &KzgSuccinctVerifyingKey<M::G1Affine> {
58        &self.svk
59    }
60}
61
62mod native {
63    use crate::{
64        loader::native::NativeLoader,
65        pcs::{
66            kzg::{KzgAccumulator, KzgAs, KzgDecidingKey},
67            AccumulationDecider,
68        },
69        util::{
70            arithmetic::{CurveAffine, Group, MillerLoopResult, MultiMillerLoop},
71            Itertools,
72        },
73        Error,
74    };
75    use std::fmt::Debug;
76
77    impl<M, MOS> AccumulationDecider<M::G1Affine, NativeLoader> for KzgAs<M, MOS>
78    where
79        M: MultiMillerLoop,
80        M::G1Affine: CurveAffine<ScalarExt = M::Fr, CurveExt = M::G1>,
81        MOS: Clone + Debug,
82    {
83        type DecidingKey = KzgDecidingKey<M>;
84
85        fn decide(
86            dk: &Self::DecidingKey,
87            KzgAccumulator { lhs, rhs }: KzgAccumulator<M::G1Affine, NativeLoader>,
88        ) -> Result<(), Error> {
89            let terms = [(&lhs, &dk.g2.into()), (&rhs, &(-dk.s_g2).into())];
90            bool::from(M::multi_miller_loop(&terms).final_exponentiation().is_identity())
91                .then_some(())
92                .ok_or_else(|| Error::AssertionFailure("e(lhs, g2)·e(rhs, -s_g2) == O".to_string()))
93        }
94
95        fn decide_all(
96            dk: &Self::DecidingKey,
97            accumulators: Vec<KzgAccumulator<M::G1Affine, NativeLoader>>,
98        ) -> Result<(), Error> {
99            assert!(!accumulators.is_empty());
100            accumulators
101                .into_iter()
102                .map(|accumulator| Self::decide(dk, accumulator))
103                .try_collect::<_, Vec<_>, _>()?;
104            Ok(())
105        }
106    }
107}
108
109#[cfg(feature = "loader_evm")]
110mod evm {
111    use crate::{
112        loader::{
113            evm::{loader::Value, EvmLoader, U256},
114            LoadedScalar,
115        },
116        pcs::{
117            kzg::{KzgAccumulator, KzgAs, KzgDecidingKey},
118            AccumulationDecider,
119        },
120        util::{
121            arithmetic::{CurveAffine, MultiMillerLoop, PrimeField},
122            msm::Msm,
123        },
124        Error,
125    };
126    use std::{fmt::Debug, rc::Rc};
127
128    impl<M, MOS> AccumulationDecider<M::G1Affine, Rc<EvmLoader>> for KzgAs<M, MOS>
129    where
130        M: MultiMillerLoop,
131        M::G1Affine: CurveAffine<ScalarExt = M::Fr, CurveExt = M::G1>,
132        M::G2Affine: CurveAffine<ScalarExt = M::Fr, CurveExt = M::G2>,
133        M::Fr: PrimeField<Repr = [u8; 0x20]>,
134        MOS: Clone + Debug,
135    {
136        type DecidingKey = KzgDecidingKey<M>;
137
138        fn decide(
139            dk: &Self::DecidingKey,
140            KzgAccumulator { lhs, rhs }: KzgAccumulator<M::G1Affine, Rc<EvmLoader>>,
141        ) -> Result<(), Error> {
142            let loader = lhs.loader();
143            let [g2, minus_s_g2] = [dk.g2, -dk.s_g2].map(|ec_point| {
144                let coordinates = ec_point.coordinates().unwrap();
145                let x = coordinates.x().to_repr();
146                let y = coordinates.y().to_repr();
147                (
148                    U256::try_from_le_slice(&x.as_ref()[32..]).unwrap(),
149                    U256::try_from_le_slice(&x.as_ref()[..32]).unwrap(),
150                    U256::try_from_le_slice(&y.as_ref()[32..]).unwrap(),
151                    U256::try_from_le_slice(&y.as_ref()[..32]).unwrap(),
152                )
153            });
154            loader.pairing(&lhs, g2, &rhs, minus_s_g2);
155            Ok(())
156        }
157
158        fn decide_all(
159            dk: &Self::DecidingKey,
160            mut accumulators: Vec<KzgAccumulator<M::G1Affine, Rc<EvmLoader>>>,
161        ) -> Result<(), Error> {
162            assert!(!accumulators.is_empty());
163
164            let accumulator = if accumulators.len() == 1 {
165                accumulators.pop().unwrap()
166            } else {
167                let loader = accumulators[0].lhs.loader();
168                let (lhs, rhs) = accumulators
169                    .iter()
170                    .map(|KzgAccumulator { lhs, rhs }| {
171                        let [lhs, rhs] = [&lhs, &rhs].map(|ec_point| loader.dup_ec_point(ec_point));
172                        (lhs, rhs)
173                    })
174                    .unzip::<_, _, Vec<_>, Vec<_>>();
175
176                let hash_ptr = loader.keccak256(lhs[0].ptr(), lhs.len() * 0x80);
177                let challenge_ptr = loader.allocate(0x20);
178                let code = format!("mstore({challenge_ptr}, mod(mload({hash_ptr}), f_q))");
179                loader.code_mut().runtime_append(code);
180                let challenge = loader.scalar(Value::Memory(challenge_ptr));
181
182                let powers_of_challenge = LoadedScalar::<M::Fr>::powers(&challenge, lhs.len());
183                let [lhs, rhs] = [lhs, rhs].map(|msms| {
184                    msms.iter()
185                        .zip(powers_of_challenge.iter())
186                        .map(|(msm, power_of_challenge)| {
187                            Msm::<M::G1Affine, Rc<EvmLoader>>::base(msm) * power_of_challenge
188                        })
189                        .sum::<Msm<_, _>>()
190                        .evaluate(None)
191                });
192
193                KzgAccumulator::new(lhs, rhs)
194            };
195
196            <Self as AccumulationDecider<M::G1Affine, Rc<EvmLoader>>>::decide(dk, accumulator)
197        }
198    }
199}
snark_verifier/pcs/kzg/decider.rs

snark_verifier/pcs/kzg/
decider.rs
