1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
use crate::halo2_proofs::arithmetic::Field;
use halo2_base::{
    gates::{GateInstructions, RangeInstructions},
    utils::{BigPrimeField, ScalarField},
    AssignedValue, Context,
};
use num_bigint::BigUint;
use serde::{Deserialize, Serialize};
use std::fmt::Debug;

pub mod fp;
pub mod fp12;
pub mod fp2;
pub mod vector;

#[cfg(test)]
mod tests;

pub trait PrimeField = BigPrimeField;

/// Trait for common functionality for finite field chips.
/// Primarily intended to emulate a "non-native" finite field using "native" values in a prime field `F`.
/// Most functions are designed for the case when the non-native field is larger than the native field, but
/// the trait can still be implemented and used in other cases.
pub trait FieldChip<F: PrimeField>: Clone + Send + Sync {
    const PRIME_FIELD_NUM_BITS: u32;

    /// A representation of a field element that is used for intermediate computations.
    /// The representation can have "overflows" (e.g., overflow limbs or negative limbs).
    type UnsafeFieldPoint: Clone
        + Debug
        + Send
        + Sync
        + From<Self::FieldPoint>
        + for<'a> From<&'a Self::UnsafeFieldPoint>
        + for<'a> From<&'a Self::FieldPoint>; // Cloning all the time impacts readability, so we allow references to be cloned into owned values

    /// The "proper" representation of a field element. Allowed to be a non-unique representation of a field element (e.g., can be greater than modulus)
    type FieldPoint: Clone
        + Debug
        + Send
        + Sync
        + From<Self::ReducedFieldPoint>
        + for<'a> From<&'a Self::FieldPoint>;

    /// A proper representation of field elements that guarantees a unique representation of each field element. Typically this means Uints that are less than the modulus.
    type ReducedFieldPoint: Clone + Debug + Send + Sync;

    /// A type implementing `Field` trait to help with witness generation (for example with inverse)
    type FieldType: Field;
    type RangeChip: RangeInstructions<F>;

    fn native_modulus(&self) -> &BigUint;
    fn gate(&self) -> &<Self::RangeChip as RangeInstructions<F>>::Gate {
        self.range().gate()
    }
    fn range(&self) -> &Self::RangeChip;
    fn limb_bits(&self) -> usize;

    fn get_assigned_value(&self, x: &Self::UnsafeFieldPoint) -> Self::FieldType;

    /// Assigns `fe` as private witness. Note that the witness may **not** be constrained to be a unique representation of the field element `fe`.
    fn load_private(&self, ctx: &mut Context<F>, fe: Self::FieldType) -> Self::FieldPoint;

    /// Assigns `fe` as private witness and contrains the witness to be in reduced form.
    fn load_private_reduced(
        &self,
        ctx: &mut Context<F>,
        fe: Self::FieldType,
    ) -> Self::ReducedFieldPoint {
        let fe = self.load_private(ctx, fe);
        self.enforce_less_than(ctx, fe)
    }

    /// Assigns `fe` as constant.
    fn load_constant(&self, ctx: &mut Context<F>, fe: Self::FieldType) -> Self::FieldPoint;

    fn add_no_carry(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::UnsafeFieldPoint>,
        b: impl Into<Self::UnsafeFieldPoint>,
    ) -> Self::UnsafeFieldPoint;

    /// output: `a + c`
    fn add_constant_no_carry(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::UnsafeFieldPoint>,
        c: Self::FieldType,
    ) -> Self::UnsafeFieldPoint;

    fn sub_no_carry(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::UnsafeFieldPoint>,
        b: impl Into<Self::UnsafeFieldPoint>,
    ) -> Self::UnsafeFieldPoint;

    fn negate(&self, ctx: &mut Context<F>, a: Self::FieldPoint) -> Self::FieldPoint;

    /// a * c
    fn scalar_mul_no_carry(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::UnsafeFieldPoint>,
        c: i64,
    ) -> Self::UnsafeFieldPoint;

    /// a * c + b
    fn scalar_mul_and_add_no_carry(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::UnsafeFieldPoint>,
        b: impl Into<Self::UnsafeFieldPoint>,
        c: i64,
    ) -> Self::UnsafeFieldPoint;

    fn mul_no_carry(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::UnsafeFieldPoint>,
        b: impl Into<Self::UnsafeFieldPoint>,
    ) -> Self::UnsafeFieldPoint;

    fn check_carry_mod_to_zero(&self, ctx: &mut Context<F>, a: Self::UnsafeFieldPoint);

    fn carry_mod(&self, ctx: &mut Context<F>, a: Self::UnsafeFieldPoint) -> Self::FieldPoint;

    fn range_check(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::UnsafeFieldPoint>,
        max_bits: usize,
    );

    /// Constrains that `a` is a reduced representation and returns the wrapped `a`.
    fn enforce_less_than(
        &self,
        ctx: &mut Context<F>,
        a: Self::FieldPoint,
    ) -> Self::ReducedFieldPoint;

    // Returns 1 iff the underlying big integer for `a` is 0. Otherwise returns 0.
    // For field extensions, checks coordinate-wise.
    fn is_soft_zero(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::FieldPoint>,
    ) -> AssignedValue<F>;

    // Constrains that the underlying big integer is in [0, p - 1].
    // Then returns 1 iff the underlying big integer for `a` is 0. Otherwise returns 0.
    // For field extensions, checks coordinate-wise.
    fn is_soft_nonzero(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::FieldPoint>,
    ) -> AssignedValue<F>;

    fn is_zero(&self, ctx: &mut Context<F>, a: impl Into<Self::FieldPoint>) -> AssignedValue<F>;

    fn is_equal_unenforced(
        &self,
        ctx: &mut Context<F>,
        a: Self::ReducedFieldPoint,
        b: Self::ReducedFieldPoint,
    ) -> AssignedValue<F>;

    fn assert_equal(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::FieldPoint>,
        b: impl Into<Self::FieldPoint>,
    );

    // =========== default implementations =============

    // assuming `a, b` have been range checked to be a proper BigInt
    // constrain the witnesses `a, b` to be `< p`
    // then check `a == b` as BigInts
    fn is_equal(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::FieldPoint>,
        b: impl Into<Self::FieldPoint>,
    ) -> AssignedValue<F> {
        let a = self.enforce_less_than(ctx, a.into());
        let b = self.enforce_less_than(ctx, b.into());
        // a.native and b.native are derived from `a.truncation, b.truncation`, so no need to check if they're equal
        self.is_equal_unenforced(ctx, a, b)
    }

    /// If using `UnsafeFieldPoint`, make sure multiplication does not cause overflow.
    fn mul(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::UnsafeFieldPoint>,
        b: impl Into<Self::UnsafeFieldPoint>,
    ) -> Self::FieldPoint {
        let no_carry = self.mul_no_carry(ctx, a, b);
        self.carry_mod(ctx, no_carry)
    }

    /// Constrains that `b` is nonzero as a field element and then returns `a / b`.
    fn divide(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::FieldPoint>,
        b: impl Into<Self::FieldPoint>,
    ) -> Self::FieldPoint {
        let b = b.into();
        let b_is_zero = self.is_zero(ctx, b.clone());
        self.gate().assert_is_const(ctx, &b_is_zero, &F::zero());

        self.divide_unsafe(ctx, a.into(), b)
    }

    /// Returns `a / b` without constraining `b` to be nonzero.
    ///
    /// Warning: undefined behavior when `b` is zero.
    ///
    /// `a, b` must be such that `quot * b - a` without carry does not overflow, where `quot` is the output.
    fn divide_unsafe(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::UnsafeFieldPoint>,
        b: impl Into<Self::UnsafeFieldPoint>,
    ) -> Self::FieldPoint {
        let a = a.into();
        let b = b.into();
        let a_val = self.get_assigned_value(&a);
        let b_val = self.get_assigned_value(&b);
        let b_inv: Self::FieldType = Option::from(b_val.invert()).unwrap_or_default();
        let quot_val = a_val * b_inv;

        let quot = self.load_private(ctx, quot_val);

        // constrain quot * b - a = 0 mod p
        let quot_b = self.mul_no_carry(ctx, quot.clone(), b);
        let quot_constraint = self.sub_no_carry(ctx, quot_b, a);
        self.check_carry_mod_to_zero(ctx, quot_constraint);

        quot
    }

    /// Constrains that `b` is nonzero as a field element and then returns `-a / b`.
    fn neg_divide(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::FieldPoint>,
        b: impl Into<Self::FieldPoint>,
    ) -> Self::FieldPoint {
        let b = b.into();
        let b_is_zero = self.is_zero(ctx, b.clone());
        self.gate().assert_is_const(ctx, &b_is_zero, &F::zero());

        self.neg_divide_unsafe(ctx, a.into(), b)
    }

    // Returns `-a / b` without constraining `b` to be nonzero.
    // this is usually cheaper constraint-wise than computing -a and then (-a) / b separately
    fn neg_divide_unsafe(
        &self,
        ctx: &mut Context<F>,
        a: impl Into<Self::UnsafeFieldPoint>,
        b: impl Into<Self::UnsafeFieldPoint>,
    ) -> Self::FieldPoint {
        let a = a.into();
        let b = b.into();
        let a_val = self.get_assigned_value(&a);
        let b_val = self.get_assigned_value(&b);
        let b_inv: Self::FieldType = Option::from(b_val.invert()).unwrap_or_default();
        let quot_val = -a_val * b_inv;

        let quot = self.load_private(ctx, quot_val);

        // constrain quot * b + a = 0 mod p
        let quot_b = self.mul_no_carry(ctx, quot.clone(), b);
        let quot_constraint = self.add_no_carry(ctx, quot_b, a);
        self.check_carry_mod_to_zero(ctx, quot_constraint);

        quot
    }
}

pub trait Selectable<F: ScalarField, Pt> {
    fn select(&self, ctx: &mut Context<F>, a: Pt, b: Pt, sel: AssignedValue<F>) -> Pt;

    fn select_by_indicator(
        &self,
        ctx: &mut Context<F>,
        a: &impl AsRef<[Pt]>,
        coeffs: &[AssignedValue<F>],
    ) -> Pt;
}

// Common functionality for prime field chips
pub trait PrimeFieldChip<F: PrimeField>: FieldChip<F>
where
    Self::FieldType: PrimeField,
{
    fn num_limbs(&self) -> usize;
    fn limb_mask(&self) -> &BigUint;
    fn limb_bases(&self) -> &[F];
}

// helper trait so we can actually construct and read the Fp2 struct
// needs to be implemented for Fp2 struct for use cases below
pub trait FieldExtConstructor<Fp: ff::PrimeField, const DEGREE: usize> {
    fn new(c: [Fp; DEGREE]) -> Self;

    fn coeffs(&self) -> Vec<Fp>;
}

#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
pub enum FpStrategy {
    Simple,
}