1use alloc::vec;
  2use alloc::vec::Vec;
  3use core::marker::PhantomData;
  4
  5use num::BigUint;
  6use plonky2::field::extension::Extendable;
  7use plonky2::field::types::{Field, Sample};
  8use plonky2::hash::hash_types::RichField;
  9use plonky2::hash::keccak::KeccakHash;
 10use plonky2::iop::target::{BoolTarget, Target};
 11use plonky2::plonk::circuit_builder::CircuitBuilder;
 12use plonky2::plonk::config::{GenericHashOut, Hasher};
 13use plonky2_u32::gadgets::arithmetic_u32::{CircuitBuilderU32, U32Target};
 14
 15use crate::curve::curve_types::{Curve, CurveScalar};
 16use crate::gadgets::biguint::BigUintTarget;
 17use crate::gadgets::curve::{AffinePointTarget, CircuitBuilderCurve};
 18use crate::gadgets::nonnative::{CircuitBuilderNonNative, NonNativeTarget};
 19use crate::gadgets::split_nonnative::CircuitBuilderSplit;
 20
 21const WINDOW_SIZE: usize = 4;
 22
 23pub trait CircuitBuilderWindowedMul<F: RichField + Extendable<D>, const D: usize> {
 24    fn precompute_window<C: Curve>(
 25        &mut self,
 26        p: &AffinePointTarget<C>,
 27    ) -> Vec<AffinePointTarget<C>>;
 28
 29    fn random_access_curve_points<C: Curve>(
 30        &mut self,
 31        access_index: Target,
 32        v: Vec<AffinePointTarget<C>>,
 33    ) -> AffinePointTarget<C>;
 34
 35    fn if_affine_point<C: Curve>(
 36        &mut self,
 37        b: BoolTarget,
 38        p1: &AffinePointTarget<C>,
 39        p2: &AffinePointTarget<C>,
 40    ) -> AffinePointTarget<C>;
 41
 42    fn curve_scalar_mul_windowed<C: Curve>(
 43        &mut self,
 44        p: &AffinePointTarget<C>,
 45        n: &NonNativeTarget<C::ScalarField>,
 46    ) -> AffinePointTarget<C>;
 47}
 48
 49impl<F: RichField + Extendable<D>, const D: usize> CircuitBuilderWindowedMul<F, D>
 50    for CircuitBuilder<F, D>
 51{
 52    fn precompute_window<C: Curve>(
 53        &mut self,
 54        p: &AffinePointTarget<C>,
 55    ) -> Vec<AffinePointTarget<C>> {
 56        let g = (CurveScalar(C::ScalarField::rand()) * C::GENERATOR_PROJECTIVE).to_affine();
 57        let neg = {
 58            let mut neg = g;
 59            neg.y = -neg.y;
 60            self.constant_affine_point(neg)
 61        };
 62
 63        let mut multiples = vec![self.constant_affine_point(g)];
 64        for i in 1..1 << WINDOW_SIZE {
 65            multiples.push(self.curve_add(p, &multiples[i - 1]));
 66        }
 67        for i in 1..1 << WINDOW_SIZE {
 68            multiples[i] = self.curve_add(&neg, &multiples[i]);
 69        }
 70        multiples
 71    }
 72
 73    fn random_access_curve_points<C: Curve>(
 74        &mut self,
 75        access_index: Target,
 76        v: Vec<AffinePointTarget<C>>,
 77    ) -> AffinePointTarget<C> {
 78        let num_limbs = C::BaseField::BITS / 32;
 79        let zero = self.zero_u32();
 80        let x_limbs: Vec<Vec<_>> = (0..num_limbs)
 81            .map(|i| {
 82                v.iter()
 83                    .map(|p| p.x.value.limbs.get(i).unwrap_or(&zero).0)
 84                    .collect()
 85            })
 86            .collect();
 87        let y_limbs: Vec<Vec<_>> = (0..num_limbs)
 88            .map(|i| {
 89                v.iter()
 90                    .map(|p| p.y.value.limbs.get(i).unwrap_or(&zero).0)
 91                    .collect()
 92            })
 93            .collect();
 94
 95        let selected_x_limbs: Vec<_> = x_limbs
 96            .iter()
 97            .map(|limbs| U32Target(self.random_access(access_index, limbs.clone())))
 98            .collect();
 99        let selected_y_limbs: Vec<_> = y_limbs
100            .iter()
101            .map(|limbs| U32Target(self.random_access(access_index, limbs.clone())))
102            .collect();
103
104        let x = NonNativeTarget {
105            value: BigUintTarget {
106                limbs: selected_x_limbs,
107            },
108            _phantom: PhantomData,
109        };
110        let y = NonNativeTarget {
111            value: BigUintTarget {
112                limbs: selected_y_limbs,
113            },
114            _phantom: PhantomData,
115        };
116        AffinePointTarget { x, y }
117    }
118
119    fn if_affine_point<C: Curve>(
120        &mut self,
121        b: BoolTarget,
122        p1: &AffinePointTarget<C>,
123        p2: &AffinePointTarget<C>,
124    ) -> AffinePointTarget<C> {
125        let new_x = self.if_nonnative(b, &p1.x, &p2.x);
126        let new_y = self.if_nonnative(b, &p1.y, &p2.y);
127        AffinePointTarget { x: new_x, y: new_y }
128    }
129
130    fn curve_scalar_mul_windowed<C: Curve>(
131        &mut self,
132        p: &AffinePointTarget<C>,
133        n: &NonNativeTarget<C::ScalarField>,
134    ) -> AffinePointTarget<C> {
135        let hash_0 = KeccakHash::<25>::hash_no_pad(&[F::ZERO]);
136        let hash_0_scalar = C::ScalarField::from_noncanonical_biguint(BigUint::from_bytes_le(
137            &GenericHashOut::<F>::to_bytes(&hash_0),
138        ));
139        let starting_point = CurveScalar(hash_0_scalar) * C::GENERATOR_PROJECTIVE;
140        let starting_point_multiplied = {
141            let mut cur = starting_point;
142            for _ in 0..C::ScalarField::BITS {
143                cur = cur.double();
144            }
145            cur
146        };
147
148        let mut result = self.constant_affine_point(starting_point.to_affine());
149
150        let precomputation = self.precompute_window(p);
151        let zero = self.zero();
152
153        let windows = self.split_nonnative_to_4_bit_limbs(n);
154        for i in (0..windows.len()).rev() {
155            result = self.curve_repeated_double(&result, WINDOW_SIZE);
156            let window = windows[i];
157
158            let to_add = self.random_access_curve_points(window, precomputation.clone());
159            let is_zero = self.is_equal(window, zero);
160            let should_add = self.not(is_zero);
161            result = self.curve_conditional_add(&result, &to_add, should_add);
162        }
163
164        let to_subtract = self.constant_affine_point(starting_point_multiplied.to_affine());
165        let to_add = self.curve_neg(&to_subtract);
166        result = self.curve_add(&result, &to_add);
167
168        result
169    }
170}
171
172#[cfg(test)]
173mod tests {
174    use core::ops::Neg;
175
176    use anyhow::Result;
177    use plonky2::field::secp256k1_scalar::Secp256K1Scalar;
178    use plonky2::iop::witness::PartialWitness;
179    use plonky2::plonk::circuit_data::CircuitConfig;
180    use plonky2::plonk::config::{GenericConfig, PoseidonGoldilocksConfig};
181    use rand::rngs::OsRng;
182    use rand::Rng;
183
184    use super::*;
185    use crate::curve::secp256k1::Secp256K1;
186
187    #[test]
188    fn test_random_access_curve_points() -> Result<()> {
189        const D: usize = 2;
190        type C = PoseidonGoldilocksConfig;
191        type F = <C as GenericConfig<D>>::F;
192
193        let config = CircuitConfig::standard_ecc_config();
194
195        let pw = PartialWitness::new();
196        let mut builder = CircuitBuilder::<F, D>::new(config);
197
198        let num_points = 16;
199        let points: Vec<_> = (0..num_points)
200            .map(|_| {
201                let g = (CurveScalar(Secp256K1Scalar::rand()) * Secp256K1::GENERATOR_PROJECTIVE)
202                    .to_affine();
203                builder.constant_affine_point(g)
204            })
205            .collect();
206
207        let mut rng = OsRng;
208        let access_index = rng.gen::<usize>() % num_points;
209
210        let access_index_target = builder.constant(F::from_canonical_usize(access_index));
211        let selected = builder.random_access_curve_points(access_index_target, points.clone());
212        let expected = points[access_index].clone();
213        builder.connect_affine_point(&selected, &expected);
214
215        let data = builder.build::<C>();
216        let proof = data.prove(pw).unwrap();
217
218        data.verify(proof)
219    }
220
221    #[test]
222    #[ignore]
223    fn test_curve_windowed_mul() -> Result<()> {
224        const D: usize = 2;
225        type C = PoseidonGoldilocksConfig;
226        type F = <C as GenericConfig<D>>::F;
227
228        let config = CircuitConfig::standard_ecc_config();
229
230        let pw = PartialWitness::new();
231        let mut builder = CircuitBuilder::<F, D>::new(config);
232
233        let g =
234            (CurveScalar(Secp256K1Scalar::rand()) * Secp256K1::GENERATOR_PROJECTIVE).to_affine();
235        let five = Secp256K1Scalar::from_canonical_usize(5);
236        let neg_five = five.neg();
237        let neg_five_scalar = CurveScalar::<Secp256K1>(neg_five);
238        let neg_five_g = (neg_five_scalar * g.to_projective()).to_affine();
239        let neg_five_g_expected = builder.constant_affine_point(neg_five_g);
240        builder.curve_assert_valid(&neg_five_g_expected);
241
242        let g_target = builder.constant_affine_point(g);
243        let neg_five_target = builder.constant_nonnative(neg_five);
244        let neg_five_g_actual = builder.curve_scalar_mul_windowed(&g_target, &neg_five_target);
245        builder.curve_assert_valid(&neg_five_g_actual);
246
247        builder.connect_affine_point(&neg_five_g_expected, &neg_five_g_actual);
248
249        let data = builder.build::<C>();
250        let proof = data.prove(pw).unwrap();
251
252        data.verify(proof)
253    }
254}