halo2curves/pluto_eris/
engine.rs

Help
1#![allow(clippy::suspicious_arithmetic_impl)]
2
3use core::{
4    borrow::Borrow,
5    iter::Sum,
6    ops::{Add, Mul, Neg, Sub},
7};
8use std::ops::MulAssign;
9
10use ff::Field;
11use pairing::{Engine, MillerLoopResult, MultiMillerLoop, PairingCurveAffine};
12use rand_core::RngCore;
13use subtle::{Choice, ConditionallySelectable, ConstantTimeEq};
14
15use crate::{
16    ff::PrimeField,
17    ff_ext::{quadratic::QuadSparseMul, ExtField},
18    group::{cofactor::CofactorCurveAffine, Group},
19    pluto_eris::{curve::*, fp::*, fp12::*, fp2::*, fp6::FROBENIUS_COEFF_FP6_C1, fq::Fq},
20};
21
22/// Adaptation of Algorithm 1, https://eprint.iacr.org/2013/722.pdf
23/// the parameter for the curve Pluto: u = -0x4000000000001000008780000000
24const NEG_PLUTO_U: u128 = 0x4000000000001000008780000000;
25
26const NEG_SIX_U_PLUS_2_NAF: [i8; 114] = [
27    0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
28    0, 1, 0, -1, 0, -1, 0, 1, 0, -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
29    -1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
30    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1,
31];
32
33crate::impl_gt!(Gt, Fp12, Fq);
34crate::impl_miller_loop_components!(Pluto, G1, G1Affine, G2, G2Affine, Fp12, Gt, Fq);
35
36pub fn multi_miller_loop(terms: &[(&G1Affine, &G2Affine)]) -> Fp12 {
37    let terms = terms
38        .iter()
39        .filter_map(|&(p, q)| {
40            if bool::from(p.is_identity()) || bool::from(q.is_identity()) {
41                None
42            } else {
43                Some((*p, *q))
44            }
45        })
46        .collect::<Vec<_>>();
47
48    let mut f = Fp12::one();
49    let mut r = terms.iter().map(|(_, q)| q.to_curve()).collect::<Vec<_>>();
50
51    for (i, x) in NEG_SIX_U_PLUS_2_NAF.iter().rev().skip(1).enumerate() {
52        (i != 0).then(|| f.square_assign());
53
54        for ((p, _), r) in terms.iter().zip(r.iter_mut()) {
55            double(&mut f, r, p);
56        }
57
58        match x {
59            &val @ (1 | -1) => {
60                for ((p, q), r) in terms.iter().zip(r.iter_mut()) {
61                    if val == 1 {
62                        add(&mut f, r, q, p);
63                    } else {
64                        add(&mut f, r, &q.neg(), p);
65                    }
66                }
67            }
68            _ => continue,
69        }
70    }
71
72    /// Value of (57/(u + 3))^((p - 1)/2) where u^2 + 5 = 0 in Fp2.
73    const XI_TO_P_MINUS_1_OVER_2: Fp2 = Fp2 {
74        c0: Fp::from_raw([
75            0x54cf5ad1c0926216,
76            0x186c1f3ce4a46d4e,
77            0x9c23800ce9c9452f,
78            0x50e0d09ff6d6c08b,
79            0x7cf421e4d46f6666,
80            0x678664ba4b6d8343,
81            0x21cc26d5de0f80f4,
82        ]),
83
84        c1: Fp::from_raw([
85            0xc0505f4c260e91f4,
86            0xe7bbd15f10723657,
87            0xb4b3e0c35358097e,
88            0x87c56f42a558750d,
89            0x4b7211d23f34f0ae,
90            0xf6839d29e2f0d250,
91            0x16ebe8b2e12a1106,
92        ]),
93    };
94
95    for ((p, q), r) in terms.iter().zip(r.iter_mut()) {
96        let mut q1: G2Affine = *q;
97        q1.x.conjugate();
98        q1.x.mul_assign(&FROBENIUS_COEFF_FP6_C1[1]);
99        q1.y.conjugate();
100        q1.y.mul_assign(&XI_TO_P_MINUS_1_OVER_2);
101        add(&mut f, r, &q1.neg(), p);
102    }
103
104    for ((p, q), r) in terms.iter().zip(r.iter_mut()) {
105        let mut minusq2: G2Affine = *q;
106        minusq2.x.mul_assign(&FROBENIUS_COEFF_FP6_C1[2]);
107        add(&mut f, r, &minusq2.neg(), p);
108    }
109
110    f
111}
112
113impl MillerLoopResult for Fp12 {
114    type Gt = Gt;
115
116    fn final_exponentiation(&self) -> Gt {
117        fn exp_by_x(f: &mut Fp12) {
118            let x = NEG_PLUTO_U;
119            let mut res = Fp12::one();
120            for i in (0..111).rev() {
121                res.cyclotomic_square();
122                if ((x >> i) & 1) == 1 {
123                    res.mul_assign(f);
124                }
125            }
126            res.conjugate();
127            *f = res;
128        }
129
130        let r = *self;
131        let mut f1 = *self;
132        f1.conjugate();
133
134        Gt(r.invert()
135            .map(|mut f2| {
136                let mut r = f1;
137                r.mul_assign(&f2);
138                f2 = r;
139                r.frobenius_map(2);
140                r.mul_assign(&f2);
141
142                let mut fp = r;
143                fp.frobenius_map(1);
144
145                let mut fp2 = r;
146                fp2.frobenius_map(2);
147                let mut fp3 = fp2;
148                fp3.frobenius_map(1);
149
150                let mut fu = r;
151                exp_by_x(&mut fu);
152
153                let mut fu2 = fu;
154                exp_by_x(&mut fu2);
155
156                let mut fu3 = fu2;
157                exp_by_x(&mut fu3);
158
159                let mut y3 = fu;
160                y3.frobenius_map(1);
161
162                let mut fu2p = fu2;
163                fu2p.frobenius_map(1);
164
165                let mut fu3p = fu3;
166                fu3p.frobenius_map(1);
167
168                let mut y2 = fu2;
169                y2.frobenius_map(2);
170
171                let mut y0 = fp;
172                y0.mul_assign(&fp2);
173                y0.mul_assign(&fp3);
174
175                let mut y1 = r;
176                y1.conjugate();
177
178                let mut y5 = fu2;
179                y5.conjugate();
180
181                y3.conjugate();
182
183                let mut y4 = fu;
184                y4.mul_assign(&fu2p);
185                y4.conjugate();
186
187                let mut y6 = fu3;
188                y6.mul_assign(&fu3p);
189                y6.conjugate();
190
191                y6.cyclotomic_square();
192                y6.mul_assign(&y4);
193                y6.mul_assign(&y5);
194
195                let mut t1 = y3;
196                t1.mul_assign(&y5);
197                t1.mul_assign(&y6);
198
199                y6.mul_assign(&y2);
200
201                t1.cyclotomic_square();
202                t1.mul_assign(&y6);
203                t1.cyclotomic_square();
204
205                let mut t0 = t1;
206                t0.mul_assign(&y1);
207
208                t1.mul_assign(&y0);
209
210                t0.cyclotomic_square();
211                t0.mul_assign(&t1);
212
213                t0
214            })
215            .unwrap())
216    }
217}
218
219// Final steps of the line function on prepared coefficients
220fn ell(f: &mut Fp12, coeffs: &(Fp2, Fp2, Fp2), p: &G1Affine) {
221    let mut c0 = coeffs.0;
222    let mut c1 = coeffs.1;
223    c0.c0.mul_assign(&p.y);
224    c0.c1.mul_assign(&p.y);
225    c1.c0.mul_assign(&p.x);
226    c1.c1.mul_assign(&p.x);
227    Fp12::mul_by_034(f, &c0, &c1, &coeffs.2);
228}
229
230#[cfg(test)]
231mod test {
232    use ff::Field;
233    use group::{prime::PrimeCurveAffine, Curve, Group};
234    use pairing::{Engine, MillerLoopResult, PairingCurveAffine};
235    use rand_core::OsRng;
236
237    use super::{
238        super::{Fq, Pluto, G1, G2},
239        multi_miller_loop, Fp12, G1Affine, G2Affine, Gt,
240    };
241    crate::test_pairing!(Pluto, G1, G1Affine, G2, G2Affine, Fp12, Gt, Fq);
242}
halo2curves/pluto_eris/engine.rs

halo2curves/pluto_eris/
engine.rs
