openvm_pairing_guest/pairing/
miller_loop.rs

Help
1use alloc::vec::Vec;
2use core::{
3    iter::zip,
4    ops::{Mul, Neg},
5};
6
7use itertools::{izip, Itertools};
8use openvm_algebra_guest::{field::FieldExtension, DivUnsafe, Field};
9use openvm_ecc_guest::AffinePoint;
10
11use super::{Evaluatable, EvaluatedLine, MillerStep, UnevaluatedLine};
12
13#[allow(non_snake_case)]
14pub trait MultiMillerLoop: MillerStep
15where
16    <Self as MillerStep>::Fp2: Field + FieldExtension<Self::Fp>,
17    // these trait bounds are needed for `multi_miller_loop_embedded_exp`. It would be better to move into
18    // a macro so the trait stays clean
19    UnevaluatedLine<Self::Fp2>: Evaluatable<Self::Fp, Self::Fp2>,
20    for<'a> &'a Self::Fp: DivUnsafe<&'a Self::Fp, Output = Self::Fp>,
21    for<'a> &'a Self::Fp2: Neg<Output = Self::Fp2>,
22    for<'a> &'a Self::Fp12: Mul<&'a Self::Fp12, Output = Self::Fp12>,
23    for<'a> &'a Self::Fp12: DivUnsafe<&'a Self::Fp12, Output = Self::Fp12>,
24{
25    type Fp: Field;
26    type Fp12: Field + FieldExtension<Self::Fp2>;
27
28    const SEED_ABS: u64;
29    const PSEUDO_BINARY_ENCODING: &[i8];
30
31    /// Function to evaluate the line functions of the Miller loop
32    fn evaluate_lines_vec(f: Self::Fp12, lines: Vec<EvaluatedLine<Self::Fp2>>) -> Self::Fp12;
33
34    /// Runs before the main loop in the Miller loop function
35    ///
36    /// xy_fracs consists of (x/y, 1/y) pairs for each point P
37    fn pre_loop(
38        Q_acc: Vec<AffinePoint<Self::Fp2>>,
39        Q: &[AffinePoint<Self::Fp2>],
40        c: Option<Self::Fp12>,
41        xy_fracs: &[(Self::Fp, Self::Fp)],
42    ) -> (Self::Fp12, Vec<AffinePoint<Self::Fp2>>);
43
44    /// Runs after the main loop in the Miller loop function
45    fn post_loop(
46        f: &Self::Fp12,
47        Q_acc: Vec<AffinePoint<Self::Fp2>>,
48        Q: &[AffinePoint<Self::Fp2>],
49        c: Option<Self::Fp12>,
50        xy_fracs: &[(Self::Fp, Self::Fp)],
51    ) -> (Self::Fp12, Vec<AffinePoint<Self::Fp2>>);
52
53    /// Runs the multi-Miller loop with no embedded exponent
54    #[allow(non_snake_case)]
55    fn multi_miller_loop(P: &[AffinePoint<Self::Fp>], Q: &[AffinePoint<Self::Fp2>]) -> Self::Fp12 {
56        Self::multi_miller_loop_embedded_exp(P, Q, None)
57    }
58
59    /// Runs the multi-Miller loop with an embedded exponent, removing the need to calculate the residue witness
60    /// in the final exponentiation step
61    ///
62    /// `c` is assumed nonzero.
63    fn multi_miller_loop_embedded_exp(
64        P: &[AffinePoint<Self::Fp>],
65        Q: &[AffinePoint<Self::Fp2>],
66        c: Option<Self::Fp12>,
67    ) -> Self::Fp12 {
68        assert!(!P.is_empty());
69        assert_eq!(P.len(), Q.len());
70
71        // Filter out the pair with infinity points
72        let (P, Q): (Vec<_>, Vec<_>) = zip(P, Q)
73            .filter(|(p, q)| !p.is_infinity() && !q.is_infinity())
74            .map(|(p, q)| (p.clone(), q.clone()))
75            .unzip();
76
77        let xy_fracs = P
78            .iter()
79            .map(|P| ((&P.x).div_unsafe(&P.y), (&Self::Fp::ONE).div_unsafe(&P.y)))
80            .collect::<Vec<(Self::Fp, Self::Fp)>>();
81        let c_inv = if let Some(c) = c.as_ref() {
82            (&Self::Fp12::ONE).div_unsafe(c)
83        } else {
84            Self::Fp12::ONE
85        };
86
87        let mut Q_acc = Q.to_vec();
88
89        let (f_out, Q_acc_out) = Self::pre_loop(Q_acc, &Q, c.clone(), &xy_fracs);
90        let mut f = f_out;
91        Q_acc = Q_acc_out;
92
93        for i in (0..Self::PSEUDO_BINARY_ENCODING.len() - 2).rev() {
94            f.square_assign();
95
96            let mut lines = Vec::with_capacity(xy_fracs.len());
97
98            if Self::PSEUDO_BINARY_ENCODING[i] == 0 {
99                // Run miller double step if \sigma_i == 0
100                // OPT[jpw]: Q_acc could be mutated in-place for better memory allocation
101                let (Q_out, lines_2S) = Q_acc
102                    .iter()
103                    .map(Self::miller_double_step)
104                    .unzip::<_, _, Vec<_>, Vec<_>>();
105                Q_acc = Q_out;
106
107                let lines_iter = izip!(lines_2S.iter(), xy_fracs.iter());
108                for (line_2S, xy_frac) in lines_iter {
109                    let line = line_2S.evaluate(xy_frac);
110                    lines.push(line);
111                }
112            } else {
113                // use embedded exponent technique if c is provided
114                f = if let Some(c) = c.as_ref() {
115                    match Self::PSEUDO_BINARY_ENCODING[i] {
116                        1 => &f * c,
117                        -1 => &f * &c_inv,
118                        _ => panic!("Invalid sigma_i"),
119                    }
120                } else {
121                    f
122                };
123
124                // Run miller double and add if \sigma_i != 0
125                // OPT[jpw]: Q_acc could be mutated in-place for better memory allocation
126                let (Q_out, lines_S_plus_Q, lines_S_plus_Q_plus_S): (Vec<_>, Vec<_>, Vec<_>) =
127                    Q_acc
128                        .iter()
129                        .zip(&Q)
130                        .map(|(Q_acc, q)| {
131                            // OPT[jpw]: cache the neg q outside of the loop
132                            let q_signed = match Self::PSEUDO_BINARY_ENCODING[i] {
133                                1 => q,
134                                -1 => &q.neg_borrow(),
135                                _ => panic!("Invalid sigma_i"),
136                            };
137                            Self::miller_double_and_add_step(Q_acc, q_signed)
138                        })
139                        .multiunzip();
140                Q_acc = Q_out;
141
142                let lines_iter = izip!(
143                    lines_S_plus_Q.iter(),
144                    lines_S_plus_Q_plus_S.iter(),
145                    xy_fracs.iter(),
146                );
147                for (line_S_plus_Q, line_S_plus_Q_plus_S, xy_frac) in lines_iter {
148                    let line0 = line_S_plus_Q.evaluate(xy_frac);
149                    let line1 = line_S_plus_Q_plus_S.evaluate(xy_frac);
150                    lines.push(line0);
151                    lines.push(line1);
152                }
153            };
154
155            f = Self::evaluate_lines_vec(f, lines);
156        }
157
158        let (f_out, _) = Self::post_loop(&f, Q_acc.clone(), &Q, c, &xy_fracs);
159        f = f_out;
160
161        f
162    }
163}
openvm_pairing_guest/pairing/miller_loop.rs

openvm_pairing_guest/pairing/
miller_loop.rs
