openvm_pairing_guest/pairing/
miller_loop.rs

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
18    // move into 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
60    /// residue witness in the final exponentiation step.
61    ///
62    /// `c` is assumed nonzero.
63    ///
64    /// **Note:** All points in `P` must have non-zero `y` coordinate. Points with `y=0`
65    /// are not on BN254/BLS12-381, but `AffinePoint` does not enforce on-curve membership.
66    /// Passing such points would cause `div_unsafe` on zero, producing unconstrained values.
67    fn multi_miller_loop_embedded_exp(
68        P: &[AffinePoint<Self::Fp>],
69        Q: &[AffinePoint<Self::Fp2>],
70        c: Option<Self::Fp12>,
71    ) -> Self::Fp12 {
72        assert!(!P.is_empty());
73        assert_eq!(P.len(), Q.len());
74
75        // Filter out the pair with infinity points
76        let (P, Q): (Vec<_>, Vec<_>) = zip(P, Q)
77            .filter(|(p, q)| !p.is_infinity() && !q.is_infinity())
78            .map(|(p, q)| (p.clone(), q.clone()))
79            .unzip();
80
81        let xy_fracs = P
82            .iter()
83            .map(|P| ((&P.x).div_unsafe(&P.y), (&Self::Fp::ONE).div_unsafe(&P.y)))
84            .collect::<Vec<(Self::Fp, Self::Fp)>>();
85        let c_inv = if let Some(c) = c.as_ref() {
86            (&Self::Fp12::ONE).div_unsafe(c)
87        } else {
88            Self::Fp12::ONE
89        };
90
91        let mut Q_acc = Q.to_vec();
92
93        let (f_out, Q_acc_out) = Self::pre_loop(Q_acc, &Q, c.clone(), &xy_fracs);
94        let mut f = f_out;
95        Q_acc = Q_acc_out;
96
97        for i in (0..Self::PSEUDO_BINARY_ENCODING.len() - 2).rev() {
98            f.square_assign();
99
100            let mut lines = Vec::with_capacity(xy_fracs.len());
101
102            if Self::PSEUDO_BINARY_ENCODING[i] == 0 {
103                // Run miller double step if \sigma_i == 0
104                // OPT[jpw]: Q_acc could be mutated in-place for better memory allocation
105                let (Q_out, lines_2S) = Q_acc
106                    .iter()
107                    .map(Self::miller_double_step)
108                    .unzip::<_, _, Vec<_>, Vec<_>>();
109                Q_acc = Q_out;
110
111                let lines_iter = izip!(lines_2S.iter(), xy_fracs.iter());
112                for (line_2S, xy_frac) in lines_iter {
113                    let line = line_2S.evaluate(xy_frac);
114                    lines.push(line);
115                }
116            } else {
117                // use embedded exponent technique if c is provided
118                f = if let Some(c) = c.as_ref() {
119                    match Self::PSEUDO_BINARY_ENCODING[i] {
120                        1 => &f * c,
121                        -1 => &f * &c_inv,
122                        _ => panic!("Invalid sigma_i"),
123                    }
124                } else {
125                    f
126                };
127
128                // Run miller double and add if \sigma_i != 0
129                // OPT[jpw]: Q_acc could be mutated in-place for better memory allocation
130                let (Q_out, lines_S_plus_Q, lines_S_plus_Q_plus_S): (Vec<_>, Vec<_>, Vec<_>) =
131                    Q_acc
132                        .iter()
133                        .zip(&Q)
134                        .map(|(Q_acc, q)| {
135                            // OPT[jpw]: cache the neg q outside of the loop
136                            let q_signed = match Self::PSEUDO_BINARY_ENCODING[i] {
137                                1 => q,
138                                -1 => &q.neg_borrow(),
139                                _ => panic!("Invalid sigma_i"),
140                            };
141                            Self::miller_double_and_add_step(Q_acc, q_signed)
142                        })
143                        .multiunzip();
144                Q_acc = Q_out;
145
146                let lines_iter = izip!(
147                    lines_S_plus_Q.iter(),
148                    lines_S_plus_Q_plus_S.iter(),
149                    xy_fracs.iter(),
150                );
151                for (line_S_plus_Q, line_S_plus_Q_plus_S, xy_frac) in lines_iter {
152                    let line0 = line_S_plus_Q.evaluate(xy_frac);
153                    let line1 = line_S_plus_Q_plus_S.evaluate(xy_frac);
154                    lines.push(line0);
155                    lines.push(line1);
156                }
157            };
158
159            f = Self::evaluate_lines_vec(f, lines);
160        }
161
162        let (f_out, _) = Self::post_loop(&f, Q_acc.clone(), &Q, c, &xy_fracs);
163        f = f_out;
164
165        f
166    }
167}
openvm_pairing_guest/pairing/miller_loop.rs

openvm_pairing_guest/pairing/
miller_loop.rs
