1use alloc::string::String;
  2use alloc::vec::Vec;
  3use anyhow::Result;
  4use core::marker::PhantomData;
  5use plonky2::plonk::circuit_data::CommonCircuitData;
  6use plonky2::util::serialization::{Buffer, IoResult, Read, Write};
  7
  8use plonky2::field::extension::Extendable;
  9use plonky2::field::secp256k1_base::Secp256K1Base;
 10use plonky2::field::secp256k1_scalar::Secp256K1Scalar;
 11use plonky2::field::types::{Field, PrimeField};
 12use plonky2::hash::hash_types::RichField;
 13use plonky2::iop::generator::{GeneratedValues, SimpleGenerator};
 14use plonky2::iop::target::{BoolTarget, Target};
 15use plonky2::iop::witness::{PartitionWitness, WitnessWrite};
 16use plonky2::plonk::circuit_builder::CircuitBuilder;
 17
 18use crate::curve::glv::{decompose_secp256k1_scalar, GLV_BETA, GLV_S};
 19use crate::curve::secp256k1::Secp256K1;
 20use crate::gadgets::biguint::{GeneratedValuesBigUint, WitnessBigUint};
 21use crate::gadgets::curve::{AffinePointTarget, CircuitBuilderCurve};
 22use crate::gadgets::curve_msm::curve_msm_circuit;
 23use crate::gadgets::nonnative::{CircuitBuilderNonNative, NonNativeTarget};
 24
 25pub trait CircuitBuilderGlv<F: RichField + Extendable<D>, const D: usize> {
 26    fn secp256k1_glv_beta(&mut self) -> NonNativeTarget<Secp256K1Base>;
 27
 28    fn decompose_secp256k1_scalar(
 29        &mut self,
 30        k: &NonNativeTarget<Secp256K1Scalar>,
 31    ) -> (
 32        NonNativeTarget<Secp256K1Scalar>,
 33        NonNativeTarget<Secp256K1Scalar>,
 34        BoolTarget,
 35        BoolTarget,
 36    );
 37
 38    fn glv_mul(
 39        &mut self,
 40        p: &AffinePointTarget<Secp256K1>,
 41        k: &NonNativeTarget<Secp256K1Scalar>,
 42    ) -> AffinePointTarget<Secp256K1>;
 43}
 44
 45impl<F: RichField + Extendable<D>, const D: usize> CircuitBuilderGlv<F, D>
 46    for CircuitBuilder<F, D>
 47{
 48    fn secp256k1_glv_beta(&mut self) -> NonNativeTarget<Secp256K1Base> {
 49        self.constant_nonnative(GLV_BETA)
 50    }
 51
 52    fn decompose_secp256k1_scalar(
 53        &mut self,
 54        k: &NonNativeTarget<Secp256K1Scalar>,
 55    ) -> (
 56        NonNativeTarget<Secp256K1Scalar>,
 57        NonNativeTarget<Secp256K1Scalar>,
 58        BoolTarget,
 59        BoolTarget,
 60    ) {
 61        let k1 = self.add_virtual_nonnative_target_sized::<Secp256K1Scalar>(4);
 62        let k2 = self.add_virtual_nonnative_target_sized::<Secp256K1Scalar>(4);
 63        let k1_neg = self.add_virtual_bool_target_unsafe();
 64        let k2_neg = self.add_virtual_bool_target_unsafe();
 65
 66        self.add_simple_generator(GLVDecompositionGenerator::<F, D> {
 67            k: k.clone(),
 68            k1: k1.clone(),
 69            k2: k2.clone(),
 70            k1_neg,
 71            k2_neg,
 72            _phantom: PhantomData,
 73        });
 74
 75        // Check that `k1_raw + GLV_S * k2_raw == k`.
 76        let k1_raw = self.nonnative_conditional_neg(&k1, k1_neg);
 77        let k2_raw = self.nonnative_conditional_neg(&k2, k2_neg);
 78        let s = self.constant_nonnative(GLV_S);
 79        let mut should_be_k = self.mul_nonnative(&s, &k2_raw);
 80        should_be_k = self.add_nonnative(&should_be_k, &k1_raw);
 81        self.connect_nonnative(&should_be_k, k);
 82
 83        (k1, k2, k1_neg, k2_neg)
 84    }
 85
 86    fn glv_mul(
 87        &mut self,
 88        p: &AffinePointTarget<Secp256K1>,
 89        k: &NonNativeTarget<Secp256K1Scalar>,
 90    ) -> AffinePointTarget<Secp256K1> {
 91        let (k1, k2, k1_neg, k2_neg) = self.decompose_secp256k1_scalar(k);
 92
 93        let beta = self.secp256k1_glv_beta();
 94        let beta_px = self.mul_nonnative(&beta, &p.x);
 95        let sp = AffinePointTarget::<Secp256K1> {
 96            x: beta_px,
 97            y: p.y.clone(),
 98        };
 99
100        let p_neg = self.curve_conditional_neg(p, k1_neg);
101        let sp_neg = self.curve_conditional_neg(&sp, k2_neg);
102        curve_msm_circuit(self, &p_neg, &sp_neg, &k1, &k2)
103    }
104}
105
106#[derive(Debug)]
107struct GLVDecompositionGenerator<F: RichField + Extendable<D>, const D: usize> {
108    k: NonNativeTarget<Secp256K1Scalar>,
109    k1: NonNativeTarget<Secp256K1Scalar>,
110    k2: NonNativeTarget<Secp256K1Scalar>,
111    k1_neg: BoolTarget,
112    k2_neg: BoolTarget,
113    _phantom: PhantomData<F>,
114}
115
116impl<F: RichField + Extendable<D>, const D: usize> SimpleGenerator<F, D>
117    for GLVDecompositionGenerator<F, D>
118{
119    fn id(&self) -> String {
120        "GLVDecompositionGenerator".into()
121    }
122
123    fn dependencies(&self) -> Vec<Target> {
124        self.k.value.limbs.iter().map(|l| l.0).collect()
125    }
126
127    fn run_once(
128        &self,
129        witness: &PartitionWitness<F>,
130        out_buffer: &mut GeneratedValues<F>,
131    ) -> Result<()> {
132        let k = Secp256K1Scalar::from_noncanonical_biguint(
133            witness.get_biguint_target(self.k.value.clone()),
134        );
135
136        let (k1, k2, k1_neg, k2_neg) = decompose_secp256k1_scalar(k);
137
138        out_buffer.set_biguint_target(&self.k1.value, &k1.to_canonical_biguint())?;
139        out_buffer.set_biguint_target(&self.k2.value, &k2.to_canonical_biguint())?;
140        out_buffer.set_bool_target(self.k1_neg, k1_neg)?;
141        out_buffer.set_bool_target(self.k2_neg, k2_neg)
142    }
143
144    fn serialize(&self, dst: &mut Vec<u8>, _common_data: &CommonCircuitData<F, D>) -> IoResult<()> {
145        dst.write_target_vec(&self.k.to_target_vec())?;
146        dst.write_target_vec(&self.k1.to_target_vec())?;
147        dst.write_target_vec(&self.k2.to_target_vec())?;
148        dst.write_target_bool(self.k1_neg)?;
149        dst.write_target_bool(self.k2_neg)
150    }
151
152    fn deserialize(src: &mut Buffer, _common_data: &CommonCircuitData<F, D>) -> IoResult<Self>
153    where
154        Self: Sized,
155    {
156        let k = NonNativeTarget::from_target_vec(&src.read_target_vec()?);
157        let k1 = NonNativeTarget::from_target_vec(&src.read_target_vec()?);
158        let k2 = NonNativeTarget::from_target_vec(&src.read_target_vec()?);
159        let k1_neg = src.read_target_bool()?;
160        let k2_neg = src.read_target_bool()?;
161
162        Ok(Self {
163            k,
164            k1,
165            k2,
166            k1_neg,
167            k2_neg,
168            _phantom: PhantomData,
169        })
170    }
171}
172
173#[cfg(test)]
174mod tests {
175    use anyhow::Result;
176    use plonky2::field::secp256k1_scalar::Secp256K1Scalar;
177    use plonky2::field::types::Sample;
178    use plonky2::iop::witness::PartialWitness;
179    use plonky2::plonk::circuit_builder::CircuitBuilder;
180    use plonky2::plonk::circuit_data::CircuitConfig;
181    use plonky2::plonk::config::{GenericConfig, PoseidonGoldilocksConfig};
182
183    use crate::curve::curve_types::{Curve, CurveScalar};
184    use crate::curve::glv::glv_mul;
185    use crate::curve::secp256k1::Secp256K1;
186    use crate::gadgets::curve::CircuitBuilderCurve;
187    use crate::gadgets::glv::CircuitBuilderGlv;
188    use crate::gadgets::nonnative::CircuitBuilderNonNative;
189
190    #[test]
191    #[ignore]
192    fn test_glv_gadget() -> Result<()> {
193        const D: usize = 2;
194        type C = PoseidonGoldilocksConfig;
195        type F = <C as GenericConfig<D>>::F;
196
197        let config = CircuitConfig::standard_ecc_config();
198
199        let pw = PartialWitness::new();
200        let mut builder = CircuitBuilder::<F, D>::new(config);
201
202        let rando =
203            (CurveScalar(Secp256K1Scalar::rand()) * Secp256K1::GENERATOR_PROJECTIVE).to_affine();
204        let randot = builder.constant_affine_point(rando);
205
206        let scalar = Secp256K1Scalar::rand();
207        let scalar_target = builder.constant_nonnative(scalar);
208
209        let rando_glv_scalar = glv_mul(rando.to_projective(), scalar);
210        let expected = builder.constant_affine_point(rando_glv_scalar.to_affine());
211        let actual = builder.glv_mul(&randot, &scalar_target);
212        builder.connect_affine_point(&expected, &actual);
213
214        dbg!(builder.num_gates());
215        let data = builder.build::<C>();
216        let proof = data.prove(pw).unwrap();
217
218        data.verify(proof)
219    }
220}