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    ///
46    /// ## Assumption
47    /// This function assumes all input points have already been validated by the caller. In
48    /// particular, externally supplied points must be checked for canonical field representation,
49    /// curve membership, and membership in the correct prime-order subgroup before being passed to
50    /// this function. Callers must also enforce any protocol-specific policy about whether identity
51    /// points are allowed. `AffinePoint` itself does not enforce these properties.
52    fn pairing_check_hint(
53        P: &[AffinePoint<Self::Fp>],
54        Q: &[AffinePoint<Self::Fp2>],
55    ) -> (Self::Fp12, Self::Fp12);
56
57    /// Checks whether the product of pairings over `(P[i], Q[i])` evaluates to one.
58    ///
59    /// ## Assumption
60    /// This function assumes all input points have already been validated by the caller. In
61    /// particular, externally supplied points must be checked for canonical field representation,
62    /// curve membership, and membership in the correct prime-order subgroup before being passed to
63    /// this function. Callers must also enforce any protocol-specific policy about whether identity
64    /// points are allowed. `AffinePoint` itself does not enforce these properties.
65    fn pairing_check(
66        P: &[AffinePoint<Self::Fp>],
67        Q: &[AffinePoint<Self::Fp2>],
68    ) -> Result<(), PairingCheckError>;
69}
70
71// Square and multiply implementation of final exponentiation. Used if the hint fails to prove
72// the pairing check.
73// `exp` should be big-endian.
74pub fn exp_check_fallback<F: Field + ExpBytes>(f: &F, exp: &[u8]) -> Result<(), PairingCheckError>
75where
76    for<'a> &'a F: core::ops::Mul<&'a F, Output = F>,
77{
78    if f.exp_bytes(true, exp) == F::ONE {
79        Ok(())
80    } else {
81        Err(PairingCheckError)
82    }
83}
84
85pub const fn shifted_funct7<P: PairingIntrinsics>(funct7: PairingBaseFunct7) -> usize {
86    P::PAIRING_IDX * (PairingBaseFunct7::PAIRING_MAX_KINDS as usize) + funct7 as usize
87}
88
89#[derive(Debug, Clone, PartialEq)]
90pub struct PairingCheckError;
91
92impl core::error::Error for PairingCheckError {}
93impl core::fmt::Display for PairingCheckError {
94    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
95        write!(f, "Pairing check failed")
96    }
97}
98
99#[cfg(all(test, not(target_os = "zkvm")))]
100mod tests {
101    use num_bigint::BigUint;
102    use openvm_algebra_moduli_macros::{moduli_declare, moduli_init};
103
104    use super::*;
105
106    moduli_declare! {
107        F13 { modulus = "13" },
108    }
109
110    moduli_init! {
111        "13",
112    }
113
114    #[test]
115    fn test_pairing_check_fallback() {
116        let a = F13::from_u8(2);
117        let b = BigUint::from(12u32);
118        let result = exp_check_fallback(&a, &b.to_bytes_be());
119        assert_eq!(result, Ok(()));
120
121        let b = BigUint::from(11u32);
122        let result = exp_check_fallback(&a, &b.to_bytes_be());
123        assert_eq!(result, Err(PairingCheckError));
124    }
125}
openvm_pairing_guest/pairing/mod.rs

openvm_pairing_guest/pairing/
mod.rs
