openvm_pairing_guest/pairing/
mod.rs

1mod final_exp;
2mod line;
3mod miller_loop;
4mod miller_step;
5
6pub use final_exp::*;
7pub use line::*;
8pub use miller_loop::*;
9pub use miller_step::*;
10use openvm_algebra_guest::{
11    field::{ComplexConjugate, FieldExtension},
12    ExpBytes, Field, IntMod,
13};
14use openvm_ecc_guest::AffinePoint;
15
16use crate::PairingBaseFunct7;
17
18pub trait PairingIntrinsics {
19    type Fp: Field + IntMod;
20    type Fp2: Field + FieldExtension<Self::Fp> + ComplexConjugate;
21    type Fp12: FieldExtension<Self::Fp2> + ComplexConjugate;
22
23    /// Index for custom intrinsic opcode determination.
24    const PAIRING_IDX: usize;
25    /// The sextic extension `Fp12` is `Fp2[X] / (X^6 - \xi)`, where `\xi` is a non-residue.
26    const XI: Self::Fp2;
27    /// Multiplication constants for the Frobenius map for coefficients in Fp2 c1..=c5 for powers
28    /// 0..12 FROBENIUS_COEFFS\[i\]\[j\] = \xi^{(j + 1) * (p^i - 1)/6} when p = 1 (mod 6)
29    const FROBENIUS_COEFFS: [[Self::Fp2; 5]; 12];
30
31    const FP2_TWO: Self::Fp2;
32    const FP2_THREE: Self::Fp2;
33}
34
35#[allow(non_snake_case)]
36pub trait PairingCheck {
37    type Fp: Field;
38    type Fp2: Field + FieldExtension<Self::Fp> + ComplexConjugate;
39    type Fp12: FieldExtension<Self::Fp2> + ComplexConjugate;
40
41    /// Given points P[], Q[], computes the multi-Miller loop and then returns
42    /// the final exponentiation hint from Novakovic-Eagon <https://eprint.iacr.org/2024/640.pdf>.
43    ///
44    /// Output is c (residue witness inverse) and u (cubic nonresidue power).
45    fn pairing_check_hint(
46        P: &[AffinePoint<Self::Fp>],
47        Q: &[AffinePoint<Self::Fp2>],
48    ) -> (Self::Fp12, Self::Fp12);
49
50    fn pairing_check(
51        P: &[AffinePoint<Self::Fp>],
52        Q: &[AffinePoint<Self::Fp2>],
53    ) -> Result<(), PairingCheckError>;
54}
55
56// Square and multiply implementation of final exponentiation. Used if the hint fails to prove
57// the pairing check.
58// `exp` should be big-endian.
59pub fn exp_check_fallback<F: Field + ExpBytes>(f: &F, exp: &[u8]) -> Result<(), PairingCheckError>
60where
61    for<'a> &'a F: core::ops::Mul<&'a F, Output = F>,
62{
63    if f.exp_bytes(true, exp) == F::ONE {
64        Ok(())
65    } else {
66        Err(PairingCheckError)
67    }
68}
69
70pub const fn shifted_funct7<P: PairingIntrinsics>(funct7: PairingBaseFunct7) -> usize {
71    P::PAIRING_IDX * (PairingBaseFunct7::PAIRING_MAX_KINDS as usize) + funct7 as usize
72}
73
74#[derive(Debug, Clone, PartialEq)]
75pub struct PairingCheckError;
76
77impl core::error::Error for PairingCheckError {}
78impl core::fmt::Display for PairingCheckError {
79    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
80        write!(f, "Pairing check failed")
81    }
82}
83
84#[cfg(all(test, not(target_os = "zkvm")))]
85mod tests {
86    use num_bigint::BigUint;
87    use openvm_algebra_moduli_macros::{moduli_declare, moduli_init};
88
89    use super::*;
90
91    moduli_declare! {
92        F13 { modulus = "13" },
93    }
94
95    moduli_init! {
96        "13",
97    }
98
99    #[test]
100    fn test_pairing_check_fallback() {
101        let a = F13::from_u8(2);
102        let b = BigUint::from(12u32);
103        let result = exp_check_fallback(&a, &b.to_bytes_be());
104        assert_eq!(result, Ok(()));
105
106        let b = BigUint::from(11u32);
107        let result = exp_check_fallback(&a, &b.to_bytes_be());
108        assert_eq!(result, Err(PairingCheckError));
109    }
110}
openvm_pairing_guest/pairing/mod.rs

openvm_pairing_guest/pairing/
mod.rs
