halo2_ecc/ecc/
mod.rs

Help
1#![allow(non_snake_case)]
2use crate::ff::Field;
3use crate::fields::{fp::FpChip, FieldChip, Selectable};
4use crate::group::{Curve, Group};
5use crate::halo2_proofs::arithmetic::CurveAffine;
6use halo2_base::gates::flex_gate::threads::SinglePhaseCoreManager;
7use halo2_base::utils::{modulus, BigPrimeField};
8use halo2_base::{
9    gates::{GateInstructions, RangeInstructions},
10    utils::CurveAffineExt,
11    AssignedValue, Context,
12};
13use itertools::Itertools;
14use rand::SeedableRng;
15use rand_chacha::ChaCha20Rng;
16use std::marker::PhantomData;
17
18pub mod ecdsa;
19pub mod fixed_base;
20// pub mod fixed_base_pippenger;
21pub mod pippenger;
22
23// EcPoint and EccChip take in a generic `FieldChip` to implement generic elliptic curve operations on arbitrary field extensions (provided chip exists) for short Weierstrass curves (currently further assuming a4 = 0 for optimization purposes)
24#[derive(Debug)]
25pub struct EcPoint<F: BigPrimeField, FieldPoint> {
26    pub x: FieldPoint,
27    pub y: FieldPoint,
28    _marker: PhantomData<F>,
29}
30
31impl<F: BigPrimeField, FieldPoint: Clone> Clone for EcPoint<F, FieldPoint> {
32    fn clone(&self) -> Self {
33        Self { x: self.x.clone(), y: self.y.clone(), _marker: PhantomData }
34    }
35}
36
37// Improve readability by allowing `&EcPoint` to be converted to `EcPoint` via cloning
38impl<'a, F: BigPrimeField, FieldPoint: Clone> From<&'a EcPoint<F, FieldPoint>>
39    for EcPoint<F, FieldPoint>
40{
41    fn from(value: &'a EcPoint<F, FieldPoint>) -> Self {
42        value.clone()
43    }
44}
45
46impl<F: BigPrimeField, FieldPoint> EcPoint<F, FieldPoint> {
47    pub fn new(x: FieldPoint, y: FieldPoint) -> Self {
48        Self { x, y, _marker: PhantomData }
49    }
50
51    pub fn x(&self) -> &FieldPoint {
52        &self.x
53    }
54
55    pub fn y(&self) -> &FieldPoint {
56        &self.y
57    }
58}
59
60/// An elliptic curve point where it is easy to compare the x-coordinate of two points
61#[derive(Clone, Debug)]
62pub struct StrictEcPoint<F: BigPrimeField, FC: FieldChip<F>> {
63    pub x: FC::ReducedFieldPoint,
64    pub y: FC::FieldPoint,
65    _marker: PhantomData<F>,
66}
67
68impl<F: BigPrimeField, FC: FieldChip<F>> StrictEcPoint<F, FC> {
69    pub fn new(x: FC::ReducedFieldPoint, y: FC::FieldPoint) -> Self {
70        Self { x, y, _marker: PhantomData }
71    }
72}
73
74impl<F: BigPrimeField, FC: FieldChip<F>> From<StrictEcPoint<F, FC>> for EcPoint<F, FC::FieldPoint> {
75    fn from(value: StrictEcPoint<F, FC>) -> Self {
76        Self::new(value.x.into(), value.y)
77    }
78}
79
80impl<'a, F: BigPrimeField, FC: FieldChip<F>> From<&'a StrictEcPoint<F, FC>>
81    for EcPoint<F, FC::FieldPoint>
82{
83    fn from(value: &'a StrictEcPoint<F, FC>) -> Self {
84        value.clone().into()
85    }
86}
87
88/// An elliptic curve point where the x-coordinate has already been constrained to be reduced or not.
89/// In the reduced case one can more optimally compare equality of x-coordinates.
90#[derive(Clone, Debug)]
91pub enum ComparableEcPoint<F: BigPrimeField, FC: FieldChip<F>> {
92    Strict(StrictEcPoint<F, FC>),
93    NonStrict(EcPoint<F, FC::FieldPoint>),
94}
95
96impl<F: BigPrimeField, FC: FieldChip<F>> From<StrictEcPoint<F, FC>> for ComparableEcPoint<F, FC> {
97    fn from(pt: StrictEcPoint<F, FC>) -> Self {
98        Self::Strict(pt)
99    }
100}
101
102impl<F: BigPrimeField, FC: FieldChip<F>> From<EcPoint<F, FC::FieldPoint>>
103    for ComparableEcPoint<F, FC>
104{
105    fn from(pt: EcPoint<F, FC::FieldPoint>) -> Self {
106        Self::NonStrict(pt)
107    }
108}
109
110impl<'a, F: BigPrimeField, FC: FieldChip<F>> From<&'a StrictEcPoint<F, FC>>
111    for ComparableEcPoint<F, FC>
112{
113    fn from(pt: &'a StrictEcPoint<F, FC>) -> Self {
114        Self::Strict(pt.clone())
115    }
116}
117
118impl<'a, F: BigPrimeField, FC: FieldChip<F>> From<&'a EcPoint<F, FC::FieldPoint>>
119    for ComparableEcPoint<F, FC>
120{
121    fn from(pt: &'a EcPoint<F, FC::FieldPoint>) -> Self {
122        Self::NonStrict(pt.clone())
123    }
124}
125
126impl<F: BigPrimeField, FC: FieldChip<F>> From<ComparableEcPoint<F, FC>>
127    for EcPoint<F, FC::FieldPoint>
128{
129    fn from(pt: ComparableEcPoint<F, FC>) -> Self {
130        match pt {
131            ComparableEcPoint::Strict(pt) => Self::new(pt.x.into(), pt.y),
132            ComparableEcPoint::NonStrict(pt) => pt,
133        }
134    }
135}
136
137// Implements:
138//  Given P = (x_1, y_1) and Q = (x_2, y_2), ecc points over the field F_p
139//      assume x_1 != x_2
140//  Find ec addition P + Q = (x_3, y_3)
141// By solving:
142//  lambda = (y_2-y_1)/(x_2-x_1) using constraint
143//  lambda * (x_2 - x_1) = y_2 - y_1
144//  x_3 = lambda^2 - x_1 - x_2 (mod p)
145//  y_3 = lambda (x_1 - x_3) - y_1 mod p
146//
147/// If `is_strict = true`, then this function constrains that `P.x != Q.x`.
148/// If you are calling this with `is_strict = false`, you must ensure that `P.x != Q.x` by some external logic (such
149/// as a mathematical theorem).
150///
151/// # Assumptions
152/// * Neither `P` nor `Q` is the point at infinity (undefined behavior otherwise)
153pub fn ec_add_unequal<F: BigPrimeField, FC: FieldChip<F>>(
154    chip: &FC,
155    ctx: &mut Context<F>,
156    P: impl Into<ComparableEcPoint<F, FC>>,
157    Q: impl Into<ComparableEcPoint<F, FC>>,
158    is_strict: bool,
159) -> EcPoint<F, FC::FieldPoint> {
160    let (P, Q) = check_points_are_unequal(chip, ctx, P, Q, is_strict);
161
162    let dx = chip.sub_no_carry(ctx, &Q.x, &P.x);
163    let dy = chip.sub_no_carry(ctx, Q.y, &P.y);
164    let lambda = chip.divide_unsafe(ctx, dy, dx);
165
166    //  x_3 = lambda^2 - x_1 - x_2 (mod p)
167    let lambda_sq = chip.mul_no_carry(ctx, &lambda, &lambda);
168    let lambda_sq_minus_px = chip.sub_no_carry(ctx, lambda_sq, &P.x);
169    let x_3_no_carry = chip.sub_no_carry(ctx, lambda_sq_minus_px, Q.x);
170    let x_3 = chip.carry_mod(ctx, x_3_no_carry);
171
172    //  y_3 = lambda (x_1 - x_3) - y_1 mod p
173    let dx_13 = chip.sub_no_carry(ctx, P.x, &x_3);
174    let lambda_dx_13 = chip.mul_no_carry(ctx, lambda, dx_13);
175    let y_3_no_carry = chip.sub_no_carry(ctx, lambda_dx_13, P.y);
176    let y_3 = chip.carry_mod(ctx, y_3_no_carry);
177
178    EcPoint::new(x_3, y_3)
179}
180
181/// If `do_check = true`, then this function constrains that `P.x != Q.x`.
182/// Otherwise does nothing.
183fn check_points_are_unequal<F: BigPrimeField, FC: FieldChip<F>>(
184    chip: &FC,
185    ctx: &mut Context<F>,
186    P: impl Into<ComparableEcPoint<F, FC>>,
187    Q: impl Into<ComparableEcPoint<F, FC>>,
188    do_check: bool,
189) -> (EcPoint<F, FC::FieldPoint> /*P */, EcPoint<F, FC::FieldPoint> /*Q */) {
190    let P = P.into();
191    let Q = Q.into();
192    if do_check {
193        // constrains that P.x != Q.x
194        let [x1, x2] = [&P, &Q].map(|pt| match pt {
195            ComparableEcPoint::Strict(pt) => pt.x.clone(),
196            ComparableEcPoint::NonStrict(pt) => chip.enforce_less_than(ctx, pt.x.clone()),
197        });
198        let x_is_equal = chip.is_equal_unenforced(ctx, x1, x2);
199        chip.gate().assert_is_const(ctx, &x_is_equal, &F::ZERO);
200    }
201    (EcPoint::from(P), EcPoint::from(Q))
202}
203
204// Implements:
205//  Given P = (x_1, y_1) and Q = (x_2, y_2), ecc points over the field F_p
206//  Find ecc subtraction P - Q = (x_3, y_3)
207//  -Q = (x_2, -y_2)
208//  lambda = -(y_2+y_1)/(x_2-x_1) using constraint
209//  x_3 = lambda^2 - x_1 - x_2 (mod p)
210//  y_3 = lambda (x_1 - x_3) - y_1 mod p
211//  Assumes that P !=Q and Q != (P - Q)
212//
213/// If `is_strict = true`, then this function constrains that `P.x != Q.x`.
214/// If you are calling this with `is_strict = false`, you must ensure that `P.x != Q.x` by some external logic (such
215/// as a mathematical theorem).
216///
217/// # Assumptions
218/// * Neither `P` nor `Q` is the point at infinity (undefined behavior otherwise)
219pub fn ec_sub_unequal<F: BigPrimeField, FC: FieldChip<F>>(
220    chip: &FC,
221    ctx: &mut Context<F>,
222    P: impl Into<ComparableEcPoint<F, FC>>,
223    Q: impl Into<ComparableEcPoint<F, FC>>,
224    is_strict: bool,
225) -> EcPoint<F, FC::FieldPoint> {
226    let (P, Q) = check_points_are_unequal(chip, ctx, P, Q, is_strict);
227
228    let dx = chip.sub_no_carry(ctx, &Q.x, &P.x);
229    let sy = chip.add_no_carry(ctx, Q.y, &P.y);
230
231    let lambda = chip.neg_divide_unsafe(ctx, sy, dx);
232
233    //  x_3 = lambda^2 - x_1 - x_2 (mod p)
234    let lambda_sq = chip.mul_no_carry(ctx, &lambda, &lambda);
235    let lambda_sq_minus_px = chip.sub_no_carry(ctx, lambda_sq, &P.x);
236    let x_3_no_carry = chip.sub_no_carry(ctx, lambda_sq_minus_px, Q.x);
237    let x_3 = chip.carry_mod(ctx, x_3_no_carry);
238
239    //  y_3 = lambda (x_1 - x_3) - y_1 mod p
240    let dx_13 = chip.sub_no_carry(ctx, P.x, &x_3);
241    let lambda_dx_13 = chip.mul_no_carry(ctx, lambda, dx_13);
242    let y_3_no_carry = chip.sub_no_carry(ctx, lambda_dx_13, P.y);
243    let y_3 = chip.carry_mod(ctx, y_3_no_carry);
244
245    EcPoint::new(x_3, y_3)
246}
247
248/// Constrains `P != -Q` but allows `P == Q`, in which case output is (0,0).
249/// For Weierstrass curves only.
250///
251/// Assumptions
252/// # Neither P or Q is the point at infinity
253pub fn ec_sub_strict<F: BigPrimeField, FC>(
254    chip: &FC,
255    ctx: &mut Context<F>,
256    P: impl Into<EcPoint<F, FC::FieldPoint>>,
257    Q: impl Into<EcPoint<F, FC::FieldPoint>>,
258) -> EcPoint<F, FC::FieldPoint>
259where
260    FC: FieldChip<F> + Selectable<F, FC::FieldPoint>,
261{
262    let mut P = P.into();
263    let Q = Q.into();
264    // Compute curr_point - start_point, allowing for output to be identity point
265    let x_is_eq = chip.is_equal(ctx, P.x(), Q.x());
266    let y_is_eq = chip.is_equal(ctx, P.y(), Q.y());
267    let is_identity = chip.gate().and(ctx, x_is_eq, y_is_eq);
268    // we ONLY allow x_is_eq = true if y_is_eq is also true; this constrains P != -Q
269    ctx.constrain_equal(&x_is_eq, &is_identity);
270
271    // P.x = Q.x and P.y = Q.y
272    // in ec_sub_unequal it will try to do -(P.y + Q.y) / (P.x - Q.x) = -2P.y / 0
273    // this will cause divide_unsafe to panic when P.y != 0
274    // to avoid this, we load a random pair of points and replace P with it *only if* `is_identity == true`
275    // we don't even check (rand_x, rand_y) is on the curve, since we don't care about the output
276    let mut rng = ChaCha20Rng::from_entropy();
277    let [rand_x, rand_y] = [(); 2].map(|_| FC::FieldType::random(&mut rng));
278    let [rand_x, rand_y] = [rand_x, rand_y].map(|x| chip.load_private(ctx, x));
279    let rand_pt = EcPoint::new(rand_x, rand_y);
280    P = ec_select(chip, ctx, rand_pt, P, is_identity);
281
282    let out = ec_sub_unequal(chip, ctx, P, Q, false);
283    let zero = chip.load_constant(ctx, FC::FieldType::ZERO);
284    ec_select(chip, ctx, EcPoint::new(zero.clone(), zero), out, is_identity)
285}
286
287// Implements:
288// computing 2P on elliptic curve E for P = (x, y)
289// formula from https://crypto.stanford.edu/pbc/notes/elliptic/explicit.html
290// assume y != 0 (otherwise 2P = O)
291
292// lamb =  3x^2 / (2 y) % p
293// x_3 = out[0] = lambda^2 - 2 x % p
294// y_3 = out[1] = lambda (x - x_3) - y % p
295
296// we precompute lambda and constrain (2y) * lambda = 3 x^2 (mod p)
297// then we compute x_3 = lambda^2 - 2 x (mod p)
298//                 y_3 = lambda (x - x_3) - y (mod p)
299/// # Assumptions
300/// * `P.y != 0`
301/// * `P` is not the point at infinity (undefined behavior otherwise)
302pub fn ec_double<F: BigPrimeField, FC: FieldChip<F>>(
303    chip: &FC,
304    ctx: &mut Context<F>,
305    P: impl Into<EcPoint<F, FC::FieldPoint>>,
306) -> EcPoint<F, FC::FieldPoint> {
307    let P = P.into();
308    // removed optimization that computes `2 * lambda` while assigning witness to `lambda` simultaneously, in favor of readability. The difference is just copying `lambda` once
309    let two_y = chip.scalar_mul_no_carry(ctx, &P.y, 2);
310    let three_x = chip.scalar_mul_no_carry(ctx, &P.x, 3);
311    let three_x_sq = chip.mul_no_carry(ctx, three_x, &P.x);
312    let lambda = chip.divide_unsafe(ctx, three_x_sq, two_y);
313
314    // x_3 = lambda^2 - 2 x % p
315    let lambda_sq = chip.mul_no_carry(ctx, &lambda, &lambda);
316    let two_x = chip.scalar_mul_no_carry(ctx, &P.x, 2);
317    let x_3_no_carry = chip.sub_no_carry(ctx, lambda_sq, two_x);
318    let x_3 = chip.carry_mod(ctx, x_3_no_carry);
319
320    // y_3 = lambda (x - x_3) - y % p
321    let dx = chip.sub_no_carry(ctx, P.x, &x_3);
322    let lambda_dx = chip.mul_no_carry(ctx, lambda, dx);
323    let y_3_no_carry = chip.sub_no_carry(ctx, lambda_dx, P.y);
324    let y_3 = chip.carry_mod(ctx, y_3_no_carry);
325
326    EcPoint::new(x_3, y_3)
327}
328
329/// Implements:
330/// computing 2P + Q = P + Q + P for P = (x0, y0), Q = (x1, y1)
331// using Montgomery ladder(?) to skip intermediate y computation
332// from halo2wrong: https://hackmd.io/ncuKqRXzR-Cw-Au2fGzsMg?view
333// lambda_0 = (y_1 - y_0) / (x_1 - x_0)
334// x_2 = lambda_0^2 - x_0 - x_1
335// lambda_1 = lambda_0 + 2 * y_0 / (x_2 - x_0)
336// x_res = lambda_1^2 - x_0 - x_2
337// y_res = lambda_1 * (x_res - x_0) - y_0
338///
339/// # Assumptions
340/// * Neither `P` nor `Q` is the point at infinity (undefined behavior otherwise)
341pub fn ec_double_and_add_unequal<F: BigPrimeField, FC: FieldChip<F>>(
342    chip: &FC,
343    ctx: &mut Context<F>,
344    P: impl Into<ComparableEcPoint<F, FC>>,
345    Q: impl Into<ComparableEcPoint<F, FC>>,
346    is_strict: bool,
347) -> EcPoint<F, FC::FieldPoint> {
348    let P = P.into();
349    let Q = Q.into();
350    let mut x_0 = None;
351    if is_strict {
352        // constrains that P.x != Q.x
353        let [x0, x1] = [&P, &Q].map(|pt| match pt {
354            ComparableEcPoint::Strict(pt) => pt.x.clone(),
355            ComparableEcPoint::NonStrict(pt) => chip.enforce_less_than(ctx, pt.x.clone()),
356        });
357        let x_is_equal = chip.is_equal_unenforced(ctx, x0.clone(), x1);
358        chip.gate().assert_is_const(ctx, &x_is_equal, &F::ZERO);
359        x_0 = Some(x0);
360    }
361    let P = EcPoint::from(P);
362    let Q = EcPoint::from(Q);
363
364    let dx = chip.sub_no_carry(ctx, &Q.x, &P.x);
365    let dy = chip.sub_no_carry(ctx, Q.y, &P.y);
366    let lambda_0 = chip.divide_unsafe(ctx, dy, dx);
367
368    //  x_2 = lambda_0^2 - x_0 - x_1 (mod p)
369    let lambda_0_sq = chip.mul_no_carry(ctx, &lambda_0, &lambda_0);
370    let lambda_0_sq_minus_x_0 = chip.sub_no_carry(ctx, lambda_0_sq, &P.x);
371    let x_2_no_carry = chip.sub_no_carry(ctx, lambda_0_sq_minus_x_0, Q.x);
372    let x_2 = chip.carry_mod(ctx, x_2_no_carry);
373
374    if is_strict {
375        let x_2 = chip.enforce_less_than(ctx, x_2.clone());
376        // TODO: when can we remove this check?
377        // constrains that x_2 != x_0
378        let x_is_equal = chip.is_equal_unenforced(ctx, x_0.unwrap(), x_2);
379        chip.range().gate().assert_is_const(ctx, &x_is_equal, &F::ZERO);
380    }
381    // lambda_1 = lambda_0 + 2 * y_0 / (x_2 - x_0)
382    let two_y_0 = chip.scalar_mul_no_carry(ctx, &P.y, 2);
383    let x_2_minus_x_0 = chip.sub_no_carry(ctx, &x_2, &P.x);
384    let lambda_1_minus_lambda_0 = chip.divide_unsafe(ctx, two_y_0, x_2_minus_x_0);
385    let lambda_1_no_carry = chip.add_no_carry(ctx, lambda_0, lambda_1_minus_lambda_0);
386
387    // x_res = lambda_1^2 - x_0 - x_2
388    let lambda_1_sq_nc = chip.mul_no_carry(ctx, &lambda_1_no_carry, &lambda_1_no_carry);
389    let lambda_1_sq_minus_x_0 = chip.sub_no_carry(ctx, lambda_1_sq_nc, &P.x);
390    let x_res_no_carry = chip.sub_no_carry(ctx, lambda_1_sq_minus_x_0, x_2);
391    let x_res = chip.carry_mod(ctx, x_res_no_carry);
392
393    // y_res = lambda_1 * (x_res - x_0) - y_0
394    let x_res_minus_x_0 = chip.sub_no_carry(ctx, &x_res, P.x);
395    let lambda_1_x_res_minus_x_0 = chip.mul_no_carry(ctx, lambda_1_no_carry, x_res_minus_x_0);
396    let y_res_no_carry = chip.sub_no_carry(ctx, lambda_1_x_res_minus_x_0, P.y);
397    let y_res = chip.carry_mod(ctx, y_res_no_carry);
398
399    EcPoint::new(x_res, y_res)
400}
401
402pub fn ec_select<F: BigPrimeField, FC>(
403    chip: &FC,
404    ctx: &mut Context<F>,
405    P: EcPoint<F, FC::FieldPoint>,
406    Q: EcPoint<F, FC::FieldPoint>,
407    sel: AssignedValue<F>,
408) -> EcPoint<F, FC::FieldPoint>
409where
410    FC: FieldChip<F> + Selectable<F, FC::FieldPoint>,
411{
412    let Rx = chip.select(ctx, P.x, Q.x, sel);
413    let Ry = chip.select(ctx, P.y, Q.y, sel);
414    EcPoint::new(Rx, Ry)
415}
416
417// takes the dot product of points with sel, where each is intepreted as
418// a _vector_
419pub fn ec_select_by_indicator<F: BigPrimeField, FC, Pt>(
420    chip: &FC,
421    ctx: &mut Context<F>,
422    points: &[Pt],
423    coeffs: &[AssignedValue<F>],
424) -> EcPoint<F, FC::FieldPoint>
425where
426    FC: FieldChip<F> + Selectable<F, FC::FieldPoint>,
427    Pt: Into<EcPoint<F, FC::FieldPoint>> + Clone,
428{
429    let (x, y): (Vec<_>, Vec<_>) = points
430        .iter()
431        .map(|P| {
432            let P: EcPoint<_, _> = P.clone().into();
433            (P.x, P.y)
434        })
435        .unzip();
436    let Rx = chip.select_by_indicator(ctx, &x, coeffs);
437    let Ry = chip.select_by_indicator(ctx, &y, coeffs);
438    EcPoint::new(Rx, Ry)
439}
440
441// `sel` is little-endian binary
442pub fn ec_select_from_bits<F: BigPrimeField, FC, Pt>(
443    chip: &FC,
444    ctx: &mut Context<F>,
445    points: &[Pt],
446    sel: &[AssignedValue<F>],
447) -> EcPoint<F, FC::FieldPoint>
448where
449    FC: FieldChip<F> + Selectable<F, FC::FieldPoint>,
450    Pt: Into<EcPoint<F, FC::FieldPoint>> + Clone,
451{
452    let w = sel.len();
453    assert_eq!(1 << w, points.len());
454    let coeffs = chip.range().gate().bits_to_indicator(ctx, sel);
455    ec_select_by_indicator(chip, ctx, points, &coeffs)
456}
457
458// `sel` is little-endian binary
459pub fn strict_ec_select_from_bits<F: BigPrimeField, FC>(
460    chip: &FC,
461    ctx: &mut Context<F>,
462    points: &[StrictEcPoint<F, FC>],
463    sel: &[AssignedValue<F>],
464) -> StrictEcPoint<F, FC>
465where
466    FC: FieldChip<F> + Selectable<F, FC::FieldPoint> + Selectable<F, FC::ReducedFieldPoint>,
467{
468    let w = sel.len();
469    assert_eq!(1 << w, points.len());
470    let coeffs = chip.range().gate().bits_to_indicator(ctx, sel);
471    let (x, y): (Vec<_>, Vec<_>) = points.iter().map(|pt| (pt.x.clone(), pt.y.clone())).unzip();
472    let x = chip.select_by_indicator(ctx, &x, &coeffs);
473    let y = chip.select_by_indicator(ctx, &y, &coeffs);
474    StrictEcPoint::new(x, y)
475}
476
477/// Computes `[scalar] * P` on short Weierstrass curve `y^2 = x^3 + b`
478/// - `scalar` is represented as a reference array of `AssignedValue`s
479/// - `scalar = sum_i scalar_i * 2^{max_bits * i}`
480/// - an array of length > 1 is needed when `scalar` exceeds the modulus of scalar field `F`
481///
482/// # Assumptions
483/// - `window_bits != 0`
484/// - The order of `P` is at least `2^{window_bits}` (in particular, `P` is not the point at infinity)
485/// - The curve has no points of order 2.
486/// - `scalar_i < 2^{max_bits} for all i`
487/// - `max_bits <= modulus::<F>.bits()`, and equality only allowed when the order of `P` equals the modulus of `F`
488pub fn scalar_multiply<F: BigPrimeField, FC, C>(
489    chip: &FC,
490    ctx: &mut Context<F>,
491    P: EcPoint<F, FC::FieldPoint>,
492    scalar: Vec<AssignedValue<F>>,
493    max_bits: usize,
494    window_bits: usize,
495) -> EcPoint<F, FC::FieldPoint>
496where
497    FC: FieldChip<F> + Selectable<F, FC::FieldPoint>,
498    C: CurveAffineExt<Base = FC::FieldType>,
499{
500    assert!(!scalar.is_empty());
501    assert!((max_bits as u64) <= modulus::<F>().bits());
502    assert!(window_bits != 0);
503    multi_scalar_multiply::<F, FC, C>(chip, ctx, &[P], vec![scalar], max_bits, window_bits)
504    /*
505    let total_bits = max_bits * scalar.len();
506    let num_windows = (total_bits + window_bits - 1) / window_bits;
507    let rounded_bitlen = num_windows * window_bits;
508
509    let mut bits = Vec::with_capacity(rounded_bitlen);
510    for x in scalar {
511        let mut new_bits = chip.gate().num_to_bits(ctx, x, max_bits);
512        bits.append(&mut new_bits);
513    }
514    let mut rounded_bits = bits;
515    let zero_cell = ctx.load_zero();
516    rounded_bits.resize(rounded_bitlen, zero_cell);
517
518    // is_started[idx] holds whether there is a 1 in bits with index at least (rounded_bitlen - idx)
519    let mut is_started = Vec::with_capacity(rounded_bitlen);
520    is_started.resize(rounded_bitlen - total_bits + 1, zero_cell);
521    for idx in 1..=total_bits {
522        let or = chip.gate().or(ctx, *is_started.last().unwrap(), rounded_bits[total_bits - idx]);
523        is_started.push(or);
524    }
525
526    // is_zero_window[idx] is 0/1 depending on whether bits [rounded_bitlen - window_bits * (idx + 1), rounded_bitlen - window_bits * idx) are all 0
527    let mut is_zero_window = Vec::with_capacity(num_windows);
528    for idx in 0..num_windows {
529        let temp_bits = rounded_bits
530            [rounded_bitlen - window_bits * (idx + 1)..rounded_bitlen - window_bits * idx]
531            .iter()
532            .copied();
533        let bit_sum = chip.gate().sum(ctx, temp_bits);
534        let is_zero = chip.gate().is_zero(ctx, bit_sum);
535        is_zero_window.push(is_zero);
536    }
537
538    let any_point = load_random_point::<F, FC, C>(chip, ctx);
539    // cached_points[idx] stores idx * P, with cached_points[0] = any_point
540    let cache_size = 1usize << window_bits;
541    let mut cached_points = Vec::with_capacity(cache_size);
542    cached_points.push(any_point);
543    cached_points.push(P.clone());
544    for idx in 2..cache_size {
545        if idx == 2 {
546            let double = ec_double(chip, ctx, &P);
547            cached_points.push(double);
548        } else {
549            let new_point = ec_add_unequal(chip, ctx, &cached_points[idx - 1], &P, false);
550            cached_points.push(new_point);
551        }
552    }
553
554    // if all the starting window bits are 0, get start_point = any_point
555    let mut curr_point = ec_select_from_bits(
556        chip,
557        ctx,
558        &cached_points,
559        &rounded_bits[rounded_bitlen - window_bits..rounded_bitlen],
560    );
561
562    for idx in 1..num_windows {
563        let mut mult_point = curr_point.clone();
564        for _ in 0..window_bits {
565            mult_point = ec_double(chip, ctx, mult_point);
566        }
567        let add_point = ec_select_from_bits(
568            chip,
569            ctx,
570            &cached_points,
571            &rounded_bits
572                [rounded_bitlen - window_bits * (idx + 1)..rounded_bitlen - window_bits * idx],
573        );
574        // if is_zero_window[idx] = true, add_point = any_point. We only need any_point to avoid divide by zero in add_unequal
575        // if is_zero_window = true and is_started = false, then mult_point = 2^window_bits * any_point. Since window_bits != 0, we have mult_point != +- any_point
576        let mult_and_add = ec_add_unequal(chip, ctx, &mult_point, &add_point, true);
577        let is_started_point = ec_select(chip, ctx, mult_point, mult_and_add, is_zero_window[idx]);
578
579        curr_point =
580            ec_select(chip, ctx, is_started_point, add_point, is_started[window_bits * idx]);
581    }
582    // if at the end, return identity point (0,0) if still not started
583    let zero = chip.load_constant(ctx, FC::FieldType::zero());
584    ec_select(chip, ctx, curr_point, EcPoint::new(zero.clone(), zero), *is_started.last().unwrap())
585    */
586}
587
588/// Checks that `P` is indeed a point on the elliptic curve `C`.
589pub fn check_is_on_curve<F, FC, C>(chip: &FC, ctx: &mut Context<F>, P: &EcPoint<F, FC::FieldPoint>)
590where
591    F: BigPrimeField,
592    FC: FieldChip<F>,
593    C: CurveAffine<Base = FC::FieldType>,
594{
595    let lhs = chip.mul_no_carry(ctx, &P.y, &P.y);
596    let mut rhs = chip.mul(ctx, &P.x, &P.x).into();
597    rhs = chip.mul_no_carry(ctx, rhs, &P.x);
598
599    rhs = chip.add_constant_no_carry(ctx, rhs, C::b());
600    let diff = chip.sub_no_carry(ctx, lhs, rhs);
601    chip.check_carry_mod_to_zero(ctx, diff)
602}
603
604pub fn load_random_point<F, FC, C>(chip: &FC, ctx: &mut Context<F>) -> EcPoint<F, FC::FieldPoint>
605where
606    F: BigPrimeField,
607    FC: FieldChip<F>,
608    C: CurveAffineExt<Base = FC::FieldType>,
609{
610    let base_point: C = C::CurveExt::random(ChaCha20Rng::from_entropy()).to_affine();
611    let (x, y) = base_point.into_coordinates();
612    let base = {
613        let x_overflow = chip.load_private(ctx, x);
614        let y_overflow = chip.load_private(ctx, y);
615        EcPoint::new(x_overflow, y_overflow)
616    };
617    // for above reason we still need to constrain that the witness is on the curve
618    check_is_on_curve::<F, FC, C>(chip, ctx, &base);
619    base
620}
621
622pub fn into_strict_point<F, FC>(
623    chip: &FC,
624    ctx: &mut Context<F>,
625    pt: EcPoint<F, FC::FieldPoint>,
626) -> StrictEcPoint<F, FC>
627where
628    F: BigPrimeField,
629    FC: FieldChip<F>,
630{
631    let x = chip.enforce_less_than(ctx, pt.x);
632    StrictEcPoint::new(x, pt.y)
633}
634
635// need to supply an extra generic `C` implementing `CurveAffine` trait in order to generate random witness points on the curve in question
636// Using Simultaneous 2^w-Ary Method, see https://www.bmoeller.de/pdf/multiexp-sac2001.pdf
637// Random Accumlation point trick learned from halo2wrong: https://hackmd.io/ncuKqRXzR-Cw-Au2fGzsMg?view
638// Input:
639// - `scalars` is vector of same length as `P`
640// - each `scalar` in `scalars` satisfies same assumptions as in `scalar_multiply` above
641
642/// # Assumptions
643/// * `points.len() == scalars.len()`
644/// * `scalars[i].len() == scalars[j].len()` for all `i, j`
645/// * `scalars[i]` is less than the order of `P`
646/// * `scalars[i][j] < 2^{max_bits} for all j`
647/// * `max_bits <= modulus::<F>.bits()`, and equality only allowed when the order of `P` equals the modulus of `F`
648/// * `points` are all on the curve or the point at infinity
649/// * `points[i]` is allowed to be (0, 0) to represent the point at infinity (identity point)
650/// * Currently implementation assumes that the only point on curve with y-coordinate equal to `0` is identity point
651pub fn multi_scalar_multiply<F: BigPrimeField, FC, C>(
652    chip: &FC,
653    ctx: &mut Context<F>,
654    P: &[EcPoint<F, FC::FieldPoint>],
655    scalars: Vec<Vec<AssignedValue<F>>>,
656    max_bits: usize,
657    window_bits: usize,
658) -> EcPoint<F, FC::FieldPoint>
659where
660    FC: FieldChip<F> + Selectable<F, FC::FieldPoint>,
661    C: CurveAffineExt<Base = FC::FieldType>,
662{
663    let k = P.len();
664    assert_eq!(k, scalars.len());
665    assert_ne!(k, 0);
666    assert!(!scalars[0].is_empty());
667    assert!((max_bits as u32) <= F::NUM_BITS);
668
669    let scalar_len = scalars[0].len();
670    let total_bits = max_bits * scalar_len;
671    let num_windows = total_bits.div_ceil(window_bits);
672    let rounded_bitlen = num_windows * window_bits;
673
674    let zero_cell = ctx.load_zero();
675    let rounded_bits = scalars
676        .into_iter()
677        .flat_map(|scalar| {
678            debug_assert_eq!(scalar.len(), scalar_len);
679            scalar
680                .into_iter()
681                .flat_map(|scalar_chunk| chip.gate().num_to_bits(ctx, scalar_chunk, max_bits))
682                .chain(std::iter::repeat(zero_cell).take(rounded_bitlen - total_bits))
683                .collect_vec()
684        })
685        .collect_vec();
686
687    // load any sufficiently generic C point as witness
688    // note that while we load a random point, an adversary would load a specifically chosen point, so we must carefully handle edge cases with constraints
689    let base = load_random_point::<F, FC, C>(chip, ctx);
690    // contains random base points [A, ..., 2^{w + k - 1} * A]
691    let mut rand_start_vec = Vec::with_capacity(k + window_bits);
692    rand_start_vec.push(base);
693    for idx in 1..(k + window_bits) {
694        let base_mult = ec_double(chip, ctx, &rand_start_vec[idx - 1]);
695        rand_start_vec.push(base_mult);
696    }
697    assert!(rand_start_vec.len() >= k + window_bits);
698
699    let cache_size = 1usize << window_bits;
700    // this is really a 2d array that we store as 1d vec for memory optimization
701    let mut cached_points = Vec::with_capacity(k * cache_size);
702    for (idx, point) in P.iter().enumerate() {
703        // add selector for whether P_i is the point at infinity (aka 0 in elliptic curve group)
704        // this can be checked by P_i.y == 0 iff P_i == O
705        let is_infinity = chip.is_zero(ctx, &point.y);
706        // (1 - 2^w) * [A, ..., 2^(k - 1) * A]
707        let neg_mult_rand_start = ec_sub_unequal(
708            chip,
709            ctx,
710            &rand_start_vec[idx],
711            &rand_start_vec[idx + window_bits],
712            true, // not necessary if we assume (2^w - 1) * A != +- A, but put in for safety
713        );
714        let point = into_strict_point(chip, ctx, point.clone());
715        let neg_mult_rand_start = into_strict_point(chip, ctx, neg_mult_rand_start);
716        // cached_points[i][0..cache_size] stores (1 - 2^w) * 2^i * A + [0..cache_size] * P_i
717        cached_points.push(neg_mult_rand_start);
718        for _ in 0..(cache_size - 1) {
719            let prev = cached_points.last().unwrap().clone();
720            // adversary could pick `A` so add equal case occurs, so we must use strict add_unequal
721            let mut new_point = ec_add_unequal(chip, ctx, &prev, &point, true);
722            // special case for when P[idx] = O
723            new_point = ec_select(chip, ctx, prev.into(), new_point, is_infinity);
724            let new_point = into_strict_point(chip, ctx, new_point);
725            cached_points.push(new_point);
726        }
727    }
728
729    // initialize at (2^{k + 1} - 1) * A
730    // note k can be large (e.g., 800) so 2^{k+1} may be larger than the order of A
731    // random fact: 2^{k + 1} - 1 can be prime: see Mersenne primes
732    // TODO: I don't see a way to rule out 2^{k+1} A = +-A case in general, so will use strict sub_unequal
733    let start_point = ec_sub_unequal(
734        chip,
735        ctx,
736        &rand_start_vec[k],
737        &rand_start_vec[0],
738        true, // k >= F::CAPACITY as usize, // this assumed random points on `C` were of prime order equal to modulus of `F`. Since this is easily missed, we turn on strict mode always
739    );
740    let mut curr_point = start_point.clone();
741
742    // compute \sum_i x_i P_i + (2^{k + 1} - 1) * A
743    for idx in 0..num_windows {
744        for _ in 0..window_bits {
745            curr_point = ec_double(chip, ctx, curr_point);
746        }
747        for (cached_points, rounded_bits) in
748            cached_points.chunks(cache_size).zip(rounded_bits.chunks(rounded_bitlen))
749        {
750            let add_point = ec_select_from_bits(
751                chip,
752                ctx,
753                cached_points,
754                &rounded_bits
755                    [rounded_bitlen - window_bits * (idx + 1)..rounded_bitlen - window_bits * idx],
756            );
757            // this all needs strict add_unequal since A can be non-randomly chosen by adversary
758            curr_point = ec_add_unequal(chip, ctx, curr_point, add_point, true);
759        }
760    }
761    ec_sub_strict(chip, ctx, curr_point, start_point)
762}
763
764pub fn get_naf(mut exp: Vec<u64>) -> Vec<i8> {
765    // https://en.wikipedia.org/wiki/Non-adjacent_form
766    // NAF for exp:
767    let mut naf: Vec<i8> = Vec::with_capacity(64 * exp.len());
768    let len = exp.len();
769
770    // generate the NAF for exp
771    for idx in 0..len {
772        let mut e: u64 = exp[idx];
773        for _ in 0..64 {
774            if e & 1 == 1 {
775                let z = 2i8 - (e % 4) as i8;
776                e /= 2;
777                if z == -1 {
778                    e += 1;
779                }
780                naf.push(z);
781            } else {
782                naf.push(0);
783                e /= 2;
784            }
785        }
786        if e != 0 {
787            assert_eq!(e, 1);
788            let mut j = idx + 1;
789            while j < exp.len() && exp[j] == u64::MAX {
790                exp[j] = 0;
791                j += 1;
792            }
793            if j < exp.len() {
794                exp[j] += 1;
795            } else {
796                exp.push(1);
797            }
798        }
799    }
800    if exp.len() != len {
801        assert_eq!(len, exp.len() + 1);
802        assert!(exp[len] == 1);
803        naf.push(1);
804    }
805    naf
806}
807
808pub type BaseFieldEccChip<'chip, C> = EccChip<
809    'chip,
810    <C as CurveAffine>::ScalarExt,
811    FpChip<'chip, <C as CurveAffine>::ScalarExt, <C as CurveAffine>::Base>,
812>;
813
814#[derive(Clone, Debug)]
815pub struct EccChip<'chip, F: BigPrimeField, FC: FieldChip<F>> {
816    pub field_chip: &'chip FC,
817    _marker: PhantomData<F>,
818}
819
820impl<'chip, F: BigPrimeField, FC: FieldChip<F>> EccChip<'chip, F, FC> {
821    pub fn new(field_chip: &'chip FC) -> Self {
822        Self { field_chip, _marker: PhantomData }
823    }
824
825    pub fn field_chip(&self) -> &FC {
826        self.field_chip
827    }
828
829    /// Load affine point as private witness. Constrains witness to lie on curve. Does not allow (0, 0) point,
830    pub fn load_private<C>(
831        &self,
832        ctx: &mut Context<F>,
833        (x, y): (FC::FieldType, FC::FieldType),
834    ) -> EcPoint<F, FC::FieldPoint>
835    where
836        C: CurveAffineExt<Base = FC::FieldType>,
837    {
838        let pt = self.load_private_unchecked(ctx, (x, y));
839        self.assert_is_on_curve::<C>(ctx, &pt);
840        pt
841    }
842
843    /// Does not constrain witness to lie on curve
844    pub fn load_private_unchecked(
845        &self,
846        ctx: &mut Context<F>,
847        (x, y): (FC::FieldType, FC::FieldType),
848    ) -> EcPoint<F, FC::FieldPoint> {
849        let x_assigned = self.field_chip.load_private(ctx, x);
850        let y_assigned = self.field_chip.load_private(ctx, y);
851
852        EcPoint::new(x_assigned, y_assigned)
853    }
854
855    /// Load affine point as private witness. Constrains witness to either lie on curve or be the point at infinity,
856    /// represented in affine coordinates as (0, 0).
857    pub fn assign_point<C>(&self, ctx: &mut Context<F>, g: C) -> EcPoint<F, FC::FieldPoint>
858    where
859        C: CurveAffineExt<Base = FC::FieldType>,
860        C::Base: crate::ff::PrimeField,
861    {
862        let pt = self.assign_point_unchecked(ctx, g);
863        let is_on_curve = self.is_on_curve_or_infinity::<C>(ctx, &pt);
864        self.field_chip.gate().assert_is_const(ctx, &is_on_curve, &F::ONE);
865        pt
866    }
867
868    /// Does not constrain witness to lie on curve
869    pub fn assign_point_unchecked<C>(
870        &self,
871        ctx: &mut Context<F>,
872        g: C,
873    ) -> EcPoint<F, FC::FieldPoint>
874    where
875        C: CurveAffineExt<Base = FC::FieldType>,
876    {
877        let (x, y) = g.into_coordinates();
878        self.load_private_unchecked(ctx, (x, y))
879    }
880
881    pub fn assign_constant_point<C>(&self, ctx: &mut Context<F>, g: C) -> EcPoint<F, FC::FieldPoint>
882    where
883        C: CurveAffineExt<Base = FC::FieldType>,
884    {
885        let (x, y) = g.into_coordinates();
886        let x = self.field_chip.load_constant(ctx, x);
887        let y = self.field_chip.load_constant(ctx, y);
888
889        EcPoint::new(x, y)
890    }
891
892    pub fn load_random_point<C>(&self, ctx: &mut Context<F>) -> EcPoint<F, FC::FieldPoint>
893    where
894        C: CurveAffineExt<Base = FC::FieldType>,
895    {
896        load_random_point::<F, FC, C>(self.field_chip(), ctx)
897    }
898
899    pub fn assert_is_on_curve<C>(&self, ctx: &mut Context<F>, P: &EcPoint<F, FC::FieldPoint>)
900    where
901        C: CurveAffine<Base = FC::FieldType>,
902    {
903        check_is_on_curve::<F, FC, C>(self.field_chip, ctx, P)
904    }
905
906    pub fn is_on_curve_or_infinity<C>(
907        &self,
908        ctx: &mut Context<F>,
909        P: &EcPoint<F, FC::FieldPoint>,
910    ) -> AssignedValue<F>
911    where
912        C: CurveAffine<Base = FC::FieldType>,
913    {
914        let lhs = self.field_chip.mul_no_carry(ctx, &P.y, &P.y);
915        let mut rhs = self.field_chip.mul(ctx, &P.x, &P.x).into();
916        rhs = self.field_chip.mul_no_carry(ctx, rhs, &P.x);
917
918        rhs = self.field_chip.add_constant_no_carry(ctx, rhs, C::b());
919        let diff = self.field_chip.sub_no_carry(ctx, lhs, rhs);
920        let diff = self.field_chip.carry_mod(ctx, diff);
921
922        let is_on_curve = self.field_chip.is_zero(ctx, diff);
923
924        let x_is_zero = self.field_chip.is_zero(ctx, &P.x);
925        let y_is_zero = self.field_chip.is_zero(ctx, &P.y);
926
927        self.field_chip.range().gate().or_and(ctx, is_on_curve, x_is_zero, y_is_zero)
928    }
929
930    pub fn negate(
931        &self,
932        ctx: &mut Context<F>,
933        P: impl Into<EcPoint<F, FC::FieldPoint>>,
934    ) -> EcPoint<F, FC::FieldPoint> {
935        let P = P.into();
936        EcPoint::new(P.x, self.field_chip.negate(ctx, P.y))
937    }
938
939    /// Assumes that P.x != Q.x
940    /// If `is_strict == true`, then actually constrains that `P.x != Q.x`
941    pub fn add_unequal(
942        &self,
943        ctx: &mut Context<F>,
944        P: impl Into<ComparableEcPoint<F, FC>>,
945        Q: impl Into<ComparableEcPoint<F, FC>>,
946        is_strict: bool,
947    ) -> EcPoint<F, FC::FieldPoint> {
948        ec_add_unequal(self.field_chip, ctx, P, Q, is_strict)
949    }
950
951    /// Assumes that P.x != Q.x
952    /// Otherwise will panic
953    pub fn sub_unequal(
954        &self,
955        ctx: &mut Context<F>,
956        P: impl Into<ComparableEcPoint<F, FC>>,
957        Q: impl Into<ComparableEcPoint<F, FC>>,
958        is_strict: bool,
959    ) -> EcPoint<F, FC::FieldPoint> {
960        ec_sub_unequal(self.field_chip, ctx, P, Q, is_strict)
961    }
962
963    pub fn double(
964        &self,
965        ctx: &mut Context<F>,
966        P: impl Into<EcPoint<F, FC::FieldPoint>>,
967    ) -> EcPoint<F, FC::FieldPoint> {
968        ec_double(self.field_chip, ctx, P)
969    }
970
971    pub fn is_equal(
972        &self,
973        ctx: &mut Context<F>,
974        P: EcPoint<F, FC::FieldPoint>,
975        Q: EcPoint<F, FC::FieldPoint>,
976    ) -> AssignedValue<F> {
977        // TODO: optimize
978        let x_is_equal = self.field_chip.is_equal(ctx, P.x, Q.x);
979        let y_is_equal = self.field_chip.is_equal(ctx, P.y, Q.y);
980        self.field_chip.range().gate().and(ctx, x_is_equal, y_is_equal)
981    }
982
983    pub fn assert_equal(
984        &self,
985        ctx: &mut Context<F>,
986        P: EcPoint<F, FC::FieldPoint>,
987        Q: EcPoint<F, FC::FieldPoint>,
988    ) {
989        self.field_chip.assert_equal(ctx, P.x, Q.x);
990        self.field_chip.assert_equal(ctx, P.y, Q.y);
991    }
992
993    /// None of elements in `points` can be point at infinity.
994    pub fn sum<C>(
995        &self,
996        ctx: &mut Context<F>,
997        points: impl IntoIterator<Item = EcPoint<F, FC::FieldPoint>>,
998    ) -> EcPoint<F, FC::FieldPoint>
999    where
1000        C: CurveAffineExt<Base = FC::FieldType>,
1001    {
1002        let rand_point = self.load_random_point::<C>(ctx);
1003        let rand_point = into_strict_point(self.field_chip, ctx, rand_point);
1004        let mut acc = rand_point.clone();
1005        for point in points {
1006            let _acc = self.add_unequal(ctx, acc, point, true);
1007            acc = into_strict_point(self.field_chip, ctx, _acc);
1008        }
1009        self.sub_unequal(ctx, acc, rand_point, true)
1010    }
1011}
1012
1013impl<F: BigPrimeField, FC: FieldChip<F>> EccChip<'_, F, FC>
1014where
1015    FC: Selectable<F, FC::FieldPoint>,
1016{
1017    pub fn select(
1018        &self,
1019        ctx: &mut Context<F>,
1020        P: EcPoint<F, FC::FieldPoint>,
1021        Q: EcPoint<F, FC::FieldPoint>,
1022        condition: AssignedValue<F>,
1023    ) -> EcPoint<F, FC::FieldPoint> {
1024        ec_select(self.field_chip, ctx, P, Q, condition)
1025    }
1026
1027    /// See [`scalar_multiply`] for more details.
1028    pub fn scalar_mult<C>(
1029        &self,
1030        ctx: &mut Context<F>,
1031        P: EcPoint<F, FC::FieldPoint>,
1032        scalar: Vec<AssignedValue<F>>,
1033        max_bits: usize,
1034        window_bits: usize,
1035    ) -> EcPoint<F, FC::FieldPoint>
1036    where
1037        C: CurveAffineExt<Base = FC::FieldType>,
1038    {
1039        scalar_multiply::<F, FC, C>(self.field_chip, ctx, P, scalar, max_bits, window_bits)
1040    }
1041
1042    // default for most purposes
1043    /// See [`pippenger::multi_exp_par`] for more details.
1044    pub fn variable_base_msm<C>(
1045        &self,
1046        thread_pool: &mut SinglePhaseCoreManager<F>,
1047        P: &[EcPoint<F, FC::FieldPoint>],
1048        scalars: Vec<Vec<AssignedValue<F>>>,
1049        max_bits: usize,
1050    ) -> EcPoint<F, FC::FieldPoint>
1051    where
1052        C: CurveAffineExt<Base = FC::FieldType>,
1053        FC: Selectable<F, FC::ReducedFieldPoint>,
1054    {
1055        // window_bits = 4 is optimal from empirical observations
1056        self.variable_base_msm_custom::<C>(thread_pool, P, scalars, max_bits, 4)
1057    }
1058
1059    // TODO: add asserts to validate input assumptions described in docs
1060    pub fn variable_base_msm_custom<C>(
1061        &self,
1062        builder: &mut SinglePhaseCoreManager<F>,
1063        P: &[EcPoint<F, FC::FieldPoint>],
1064        scalars: Vec<Vec<AssignedValue<F>>>,
1065        max_bits: usize,
1066        window_bits: usize,
1067    ) -> EcPoint<F, FC::FieldPoint>
1068    where
1069        C: CurveAffineExt<Base = FC::FieldType>,
1070        FC: Selectable<F, FC::ReducedFieldPoint>,
1071    {
1072        #[cfg(feature = "display")]
1073        println!("computing length {} MSM", P.len());
1074
1075        if P.len() <= 25 {
1076            multi_scalar_multiply::<F, FC, C>(
1077                self.field_chip,
1078                builder.main(),
1079                P,
1080                scalars,
1081                max_bits,
1082                window_bits,
1083            )
1084        } else {
1085            /*let mut radix = (f64::from((max_bits * scalars[0].len()) as u32)
1086                / f64::from(P.len() as u32))
1087            .sqrt()
1088            .floor() as usize;
1089            if radix == 0 {
1090                radix = 1;
1091            }*/
1092            // guessing that is is always better to use parallelism for >25 points
1093            pippenger::multi_exp_par::<F, FC, C>(
1094                self.field_chip,
1095                builder,
1096                P,
1097                scalars,
1098                max_bits,
1099                window_bits, // clump_factor := window_bits
1100            )
1101        }
1102    }
1103}
1104
1105impl<F: BigPrimeField, FC: FieldChip<F>> EccChip<'_, F, FC> {
1106    /// See [`fixed_base::scalar_multiply`] for more details.
1107    // TODO: put a check in place that scalar is < modulus of C::Scalar
1108    pub fn fixed_base_scalar_mult<C>(
1109        &self,
1110        ctx: &mut Context<F>,
1111        point: &C,
1112        scalar: Vec<AssignedValue<F>>,
1113        max_bits: usize,
1114        window_bits: usize,
1115    ) -> EcPoint<F, FC::FieldPoint>
1116    where
1117        C: CurveAffineExt,
1118        FC: FieldChip<F, FieldType = C::Base> + Selectable<F, FC::FieldPoint>,
1119    {
1120        fixed_base::scalar_multiply::<F, _, _>(
1121            self.field_chip,
1122            ctx,
1123            point,
1124            scalar,
1125            max_bits,
1126            window_bits,
1127        )
1128    }
1129
1130    // default for most purposes
1131    pub fn fixed_base_msm<C>(
1132        &self,
1133        builder: &mut SinglePhaseCoreManager<F>,
1134        points: &[C],
1135        scalars: Vec<Vec<AssignedValue<F>>>,
1136        max_scalar_bits_per_cell: usize,
1137    ) -> EcPoint<F, FC::FieldPoint>
1138    where
1139        C: CurveAffineExt,
1140        FC: FieldChip<F, FieldType = C::Base> + Selectable<F, FC::FieldPoint>,
1141    {
1142        self.fixed_base_msm_custom::<C>(builder, points, scalars, max_scalar_bits_per_cell, 4)
1143    }
1144
1145    // `radix = 0` means auto-calculate
1146    //
1147    /// `clump_factor = 0` means auto-calculate
1148    ///
1149    /// The user should filter out base points that are identity beforehand; we do not separately do this here
1150    pub fn fixed_base_msm_custom<C>(
1151        &self,
1152        builder: &mut SinglePhaseCoreManager<F>,
1153        points: &[C],
1154        scalars: Vec<Vec<AssignedValue<F>>>,
1155        max_scalar_bits_per_cell: usize,
1156        clump_factor: usize,
1157    ) -> EcPoint<F, FC::FieldPoint>
1158    where
1159        C: CurveAffineExt,
1160        FC: FieldChip<F, FieldType = C::Base> + Selectable<F, FC::FieldPoint>,
1161    {
1162        assert_eq!(points.len(), scalars.len());
1163        #[cfg(feature = "display")]
1164        println!("computing length {} fixed base msm", points.len());
1165
1166        fixed_base::msm_par(self, builder, points, scalars, max_scalar_bits_per_cell, clump_factor)
1167
1168        // Empirically does not seem like pippenger is any better for fixed base msm right now, because of the cost of `select_by_indicator`
1169        // Cell usage becomes around comparable when `points.len() > 100`, and `clump_factor` should always be 4
1170        /*
1171        let radix = if radix == 0 {
1172            // auto calculate
1173            (f64::from(FC::FieldType::NUM_BITS) / f64::from(points.len() as u32)).sqrt().ceil()
1174                as usize
1175        } else {
1176            radix
1177        };
1178        assert!(radix > 0);
1179
1180        fixed_base_pippenger::multi_exp::<F, FC, C>(
1181            self.field_chip,
1182            ctx,
1183            points,
1184            scalars,
1185            max_scalar_bits_per_cell,
1186            radix,
1187            clump_factor,
1188        )
1189        */
1190    }
1191}
1192
1193#[cfg(test)]
1194pub(crate) mod tests;
halo2_ecc/ecc/mod.rs

halo2_ecc/ecc/
mod.rs
