1use alloc::vec::Vec;
  2
  3use num::BigUint;
  4use plonky2::field::extension::Extendable;
  5use plonky2::field::types::Field;
  6use plonky2::hash::hash_types::RichField;
  7use plonky2::hash::keccak::KeccakHash;
  8use plonky2::plonk::circuit_builder::CircuitBuilder;
  9use plonky2::plonk::config::{GenericHashOut, Hasher};
 10
 11use crate::curve::curve_types::{AffinePoint, Curve, CurveScalar};
 12use crate::gadgets::curve::{AffinePointTarget, CircuitBuilderCurve};
 13use crate::gadgets::curve_windowed_mul::CircuitBuilderWindowedMul;
 14use crate::gadgets::nonnative::NonNativeTarget;
 15use crate::gadgets::split_nonnative::CircuitBuilderSplit;
 16
 17/// Compute windowed fixed-base scalar multiplication, using a 4-bit window.
 18pub fn fixed_base_curve_mul_circuit<C: Curve, F: RichField + Extendable<D>, const D: usize>(
 19    builder: &mut CircuitBuilder<F, D>,
 20    base: AffinePoint<C>,
 21    scalar: &NonNativeTarget<C::ScalarField>,
 22) -> AffinePointTarget<C> {
 23    // Holds `(16^i) * base` for `i=0..scalar.value.limbs.len() * 8`.
 24    let scaled_base = (0..scalar.value.limbs.len() * 8).scan(base, |acc, _| {
 25        let tmp = *acc;
 26        for _ in 0..4 {
 27            *acc = acc.double();
 28        }
 29        Some(tmp)
 30    });
 31
 32    let limbs = builder.split_nonnative_to_4_bit_limbs(scalar);
 33
 34    let hash_0 = KeccakHash::<32>::hash_no_pad(&[F::ZERO]);
 35    let hash_0_scalar = C::ScalarField::from_noncanonical_biguint(BigUint::from_bytes_le(
 36        &GenericHashOut::<F>::to_bytes(&hash_0),
 37    ));
 38    let rando = (CurveScalar(hash_0_scalar) * C::GENERATOR_PROJECTIVE).to_affine();
 39
 40    let zero = builder.zero();
 41    let mut result = builder.constant_affine_point(rando);
 42    // `s * P = sum s_i * P_i` with `P_i = (16^i) * P` and `s = sum s_i * (16^i)`.
 43    for (limb, point) in limbs.into_iter().zip(scaled_base) {
 44        // `muls_point[t] = t * P_i` for `t=0..16`.
 45        let mut muls_point = (0..16)
 46            .scan(AffinePoint::ZERO, |acc, _| {
 47                let tmp = *acc;
 48                *acc = (point + *acc).to_affine();
 49                Some(tmp)
 50            })
 51            // First element if zero, so we skip it since `constant_affine_point` takes non-zero input.
 52            .skip(1)
 53            .map(|p| builder.constant_affine_point(p))
 54            .collect::<Vec<_>>();
 55        // We add back a point in position 0. `limb == zero` is checked below, so this point can be arbitrary.
 56        muls_point.insert(0, muls_point[0].clone());
 57        let is_zero = builder.is_equal(limb, zero);
 58        let should_add = builder.not(is_zero);
 59        // `r = s_i * P_i`
 60        let r = builder.random_access_curve_points(limb, muls_point);
 61        result = builder.curve_conditional_add(&result, &r, should_add);
 62    }
 63
 64    let to_add = builder.constant_affine_point(-rando);
 65    builder.curve_add(&result, &to_add)
 66}
 67
 68#[cfg(test)]
 69mod tests {
 70    use anyhow::Result;
 71    use plonky2::field::secp256k1_scalar::Secp256K1Scalar;
 72    use plonky2::field::types::{PrimeField, Sample};
 73    use plonky2::iop::witness::PartialWitness;
 74    use plonky2::plonk::circuit_builder::CircuitBuilder;
 75    use plonky2::plonk::circuit_data::CircuitConfig;
 76    use plonky2::plonk::config::{GenericConfig, PoseidonGoldilocksConfig};
 77
 78    use crate::curve::curve_types::{Curve, CurveScalar};
 79    use crate::curve::secp256k1::Secp256K1;
 80    use crate::gadgets::biguint::WitnessBigUint;
 81    use crate::gadgets::curve::CircuitBuilderCurve;
 82    use crate::gadgets::curve_fixed_base::fixed_base_curve_mul_circuit;
 83    use crate::gadgets::nonnative::CircuitBuilderNonNative;
 84
 85    #[test]
 86    #[ignore]
 87    fn test_fixed_base() -> Result<()> {
 88        const D: usize = 2;
 89        type C = PoseidonGoldilocksConfig;
 90        type F = <C as GenericConfig<D>>::F;
 91
 92        let config = CircuitConfig::standard_ecc_config();
 93
 94        let mut pw = PartialWitness::new();
 95        let mut builder = CircuitBuilder::<F, D>::new(config);
 96
 97        let g = Secp256K1::GENERATOR_AFFINE;
 98        let n = Secp256K1Scalar::rand();
 99
100        let res = (CurveScalar(n) * g.to_projective()).to_affine();
101        let res_expected = builder.constant_affine_point(res);
102        builder.curve_assert_valid(&res_expected);
103
104        let n_target = builder.add_virtual_nonnative_target::<Secp256K1Scalar>();
105        pw.set_biguint_target(&n_target.value, &n.to_canonical_biguint());
106
107        let res_target = fixed_base_curve_mul_circuit(&mut builder, g, &n_target);
108        builder.curve_assert_valid(&res_target);
109
110        builder.connect_affine_point(&res_target, &res_expected);
111
112        dbg!(builder.num_gates());
113        let data = builder.build::<C>();
114        let proof = data.prove(pw).unwrap();
115
116        data.verify(proof)
117    }
118}