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