halo2_ecc/fields/
fp2.rs

Help
1use std::fmt::Debug;
2use std::marker::PhantomData;
3
4use crate::ff::PrimeField as _;
5use crate::impl_field_ext_chip_common;
6
7use super::{
8    vector::{FieldVector, FieldVectorChip},
9    BigPrimeField, FieldChip, FieldExtConstructor, PrimeFieldChip,
10};
11use halo2_base::{utils::modulus, AssignedValue, Context};
12use num_bigint::BigUint;
13
14/// Represent Fp2 point as `FieldVector` with degree = 2
15/// `Fp2 = Fp[u] / (u^2 + 1)`
16/// This implementation assumes p = 3 (mod 4) in order for the polynomial u^2 + 1 to be irreducible over Fp; i.e., in order for -1 to not be a square (quadratic residue) in Fp
17/// This means we store an Fp2 point as `a_0 + a_1 * u` where `a_0, a_1 in Fp`
18#[derive(Clone, Copy, Debug)]
19pub struct Fp2Chip<'a, F: BigPrimeField, FpChip: FieldChip<F>, Fp2>(
20    pub FieldVectorChip<'a, F, FpChip>,
21    PhantomData<Fp2>,
22);
23
24impl<'a, F: BigPrimeField, FpChip: PrimeFieldChip<F>, Fp2: crate::ff::Field>
25    Fp2Chip<'a, F, FpChip, Fp2>
26where
27    FpChip::FieldType: BigPrimeField,
28{
29    /// User must construct an `FpChip` first using a config. This is intended so everything shares a single `FlexGateChip`, which is needed for the column allocation to work.
30    pub fn new(fp_chip: &'a FpChip) -> Self {
31        assert_eq!(
32            modulus::<FpChip::FieldType>() % 4usize,
33            BigUint::from(3u64),
34            "p must be 3 (mod 4) for the polynomial u^2 + 1 to be irreducible"
35        );
36        Self(FieldVectorChip::new(fp_chip), PhantomData)
37    }
38
39    pub fn fp_chip(&self) -> &FpChip {
40        self.0.fp_chip
41    }
42
43    pub fn conjugate(
44        &self,
45        ctx: &mut Context<F>,
46        a: FieldVector<FpChip::FieldPoint>,
47    ) -> FieldVector<FpChip::FieldPoint> {
48        let mut a = a.0;
49        assert_eq!(a.len(), 2);
50
51        let neg_a1 = self.fp_chip().negate(ctx, a.pop().unwrap());
52        FieldVector(vec![a.pop().unwrap(), neg_a1])
53    }
54
55    pub fn neg_conjugate(
56        &self,
57        ctx: &mut Context<F>,
58        a: FieldVector<FpChip::FieldPoint>,
59    ) -> FieldVector<FpChip::FieldPoint> {
60        assert_eq!(a.0.len(), 2);
61        let mut a = a.0.into_iter();
62
63        let neg_a0 = self.fp_chip().negate(ctx, a.next().unwrap());
64        FieldVector(vec![neg_a0, a.next().unwrap()])
65    }
66}
67
68impl<F, FpChip, Fp2> FieldChip<F> for Fp2Chip<'_, F, FpChip, Fp2>
69where
70    F: BigPrimeField,
71    FpChip::FieldType: BigPrimeField,
72    FpChip: PrimeFieldChip<F>,
73    Fp2: crate::ff::Field + FieldExtConstructor<FpChip::FieldType, 2>,
74    FieldVector<FpChip::UnsafeFieldPoint>: From<FieldVector<FpChip::FieldPoint>>,
75    FieldVector<FpChip::FieldPoint>: From<FieldVector<FpChip::ReducedFieldPoint>>,
76{
77    const PRIME_FIELD_NUM_BITS: u32 = FpChip::FieldType::NUM_BITS;
78    type UnsafeFieldPoint = FieldVector<FpChip::UnsafeFieldPoint>;
79    type FieldPoint = FieldVector<FpChip::FieldPoint>;
80    type ReducedFieldPoint = FieldVector<FpChip::ReducedFieldPoint>;
81    type FieldType = Fp2;
82    type RangeChip = FpChip::RangeChip;
83
84    fn get_assigned_value(&self, x: &Self::UnsafeFieldPoint) -> Fp2 {
85        assert_eq!(x.0.len(), 2);
86        let c0 = self.fp_chip().get_assigned_value(&x[0]);
87        let c1 = self.fp_chip().get_assigned_value(&x[1]);
88        Fp2::new([c0, c1])
89    }
90
91    fn mul_no_carry(
92        &self,
93        ctx: &mut Context<F>,
94        a: impl Into<Self::UnsafeFieldPoint>,
95        b: impl Into<Self::UnsafeFieldPoint>,
96    ) -> Self::UnsafeFieldPoint {
97        let a = a.into().0;
98        let b = b.into().0;
99        assert_eq!(a.len(), 2);
100        assert_eq!(b.len(), 2);
101        let fp_chip = self.fp_chip();
102        // (a_0 + a_1 * u) * (b_0 + b_1 * u) = (a_0 b_0 - a_1 b_1) + (a_0 b_1 + a_1 b_0) * u
103        let mut ab_coeffs = Vec::with_capacity(4);
104        for a_i in a {
105            for b_j in b.iter() {
106                let coeff = fp_chip.mul_no_carry(ctx, &a_i, b_j);
107                ab_coeffs.push(coeff);
108            }
109        }
110        let a0b0_minus_a1b1 = fp_chip.sub_no_carry(ctx, &ab_coeffs[0], &ab_coeffs[3]);
111        let a0b1_plus_a1b0 = fp_chip.add_no_carry(ctx, &ab_coeffs[1], &ab_coeffs[2]);
112
113        FieldVector(vec![a0b0_minus_a1b1, a0b1_plus_a1b0])
114    }
115
116    // ========= inherited from FieldVectorChip =========
117    impl_field_ext_chip_common!();
118}
119
120mod bn254 {
121    use crate::fields::FieldExtConstructor;
122    use crate::halo2_proofs::halo2curves::bn256::{Fq, Fq2};
123    impl FieldExtConstructor<Fq, 2> for Fq2 {
124        fn new(c: [Fq; 2]) -> Self {
125            Fq2 { c0: c[0], c1: c[1] }
126        }
127
128        fn coeffs(&self) -> Vec<Fq> {
129            vec![self.c0, self.c1]
130        }
131    }
132}
halo2_ecc/fields/fp2.rs

halo2_ecc/fields/
fp2.rs
