From ca4894f20355ab6d62ae6d432b6c0bfaadc6c3cb Mon Sep 17 00:00:00 2001 From: Nikolay Yakimov Date: Thu, 7 Dec 2023 22:36:41 +0300 Subject: [PATCH] MIR: implement PAIRING_CHECK --- contrib/mir/src/ast.rs | 1 + contrib/mir/src/bls.rs | 1 + contrib/mir/src/bls/g1.rs | 6 +- contrib/mir/src/bls/g2.rs | 6 +- contrib/mir/src/bls/pairing.rs | 120 +++++++++++++++++++++++++++++++++ contrib/mir/src/gas.rs | 4 ++ contrib/mir/src/interpreter.rs | 30 +++++++++ contrib/mir/src/typechecker.rs | 65 ++++++++++++++++++ 8 files changed, 227 insertions(+), 6 deletions(-) create mode 100644 contrib/mir/src/bls/pairing.rs diff --git a/contrib/mir/src/ast.rs b/contrib/mir/src/ast.rs index ecfd9d778d92..bbece0653953 100644 --- a/contrib/mir/src/ast.rs +++ b/contrib/mir/src/ast.rs @@ -479,6 +479,7 @@ pub enum Instruction<'a> { /// in concrete syntax, so we can assume that if the entrypoint is the default entrypoint, then /// no explicit entrypoint was specified in the instruction. Contract(Type, Entrypoint), + PairingCheck, } #[derive(Debug, Clone, PartialEq, Eq)] diff --git a/contrib/mir/src/bls.rs b/contrib/mir/src/bls.rs index 6790b92acc4d..16880ba6d526 100644 --- a/contrib/mir/src/bls.rs +++ b/contrib/mir/src/bls.rs @@ -9,5 +9,6 @@ pub mod fr; pub mod g1; pub mod g2; mod instances; +pub mod pairing; pub use self::{fr::Fr, g1::G1, g2::G2}; diff --git a/contrib/mir/src/bls/g1.rs b/contrib/mir/src/bls/g1.rs index 0100e79a4c77..2abc9cbdce62 100644 --- a/contrib/mir/src/bls/g1.rs +++ b/contrib/mir/src/bls/g1.rs @@ -130,7 +130,7 @@ impl Neg for G1 { } #[cfg(test)] -mod tests { +pub(super) mod tests { use std::str::FromStr; use num_bigint::BigInt; @@ -142,7 +142,7 @@ mod tests { G1::from_bytes(&hex::decode(s).unwrap()).unwrap() } - fn some_val() -> G1 { + pub fn some_val() -> G1 { let s = "026fcea34d1a4c5125142dfa3b616086309cab49e60e548d95de658af4d9329c269dc132bd5d884617e8767600daeee90c6f5d25f3d63540f3b799d291e5df4a90244346ed780d5c9d3afa8f3c9a196e089fa4edc4a9806592e8561d626579e3"; G1::from_bytes(&hex::decode(s).unwrap()).unwrap() } @@ -152,7 +152,7 @@ mod tests { G1::from_bytes(&hex::decode(s).unwrap()).unwrap() } - fn neg_some_val() -> G1 { + pub fn neg_some_val() -> G1 { let s = "026fcea34d1a4c5125142dfa3b616086309cab49e60e548d95de658af4d9329c269dc132bd5d884617e8767600daeee90d91b4c445a9b15957640de3b165cd8cd453083e060d0562c9f5d811ba16dcb6160c5b10ecaa7f9a2716a9e29d9a30c8"; G1::from_bytes(&hex::decode(s).unwrap()).unwrap() } diff --git a/contrib/mir/src/bls/g2.rs b/contrib/mir/src/bls/g2.rs index 4aa4bf349fc4..ce803474a09c 100644 --- a/contrib/mir/src/bls/g2.rs +++ b/contrib/mir/src/bls/g2.rs @@ -133,7 +133,7 @@ impl Neg for G2 { } #[cfg(test)] -mod tests { +pub(super) mod tests { use std::str::FromStr; use num_bigint::BigInt; @@ -145,7 +145,7 @@ mod tests { G2::from_bytes(&hex::decode(s).unwrap()).unwrap() } - fn some_val() -> G2 { + pub fn some_val() -> G2 { let s = "14e9b22683a66543ec447b7aa76e4404424709728507581d0b3f60a8062c3f7c7d3365197c59f7c961fa9731084f5be60d0a936e93d556bdef2032cdcae2fa9902dcbe105e01d7ab7126d83486d882c4efd2fc1ac55044157333be19acf0cb7a10bc41c8081c9babd8d5b41b645badd4a679b3d4e1b3ea2c0e1f53b39c00b3889a40306c9b9ee2da5831e90148334d91016474d07e0f4e36d2d51b5ca11b633b9a940b9c126aebf4a2537c18fdc6967fb677824bfa902157e53cb499a021e57b"; G2::from_bytes(&hex::decode(s).unwrap()).unwrap() } @@ -155,7 +155,7 @@ mod tests { G2::from_bytes(&hex::decode(s).unwrap()).unwrap() } - fn neg_some_val() -> G2 { + pub fn neg_some_val() -> G2 { let s = "14e9b22683a66543ec447b7aa76e4404424709728507581d0b3f60a8062c3f7c7d3365197c59f7c961fa9731084f5be60d0a936e93d556bdef2032cdcae2fa9902dcbe105e01d7ab7126d83486d882c4efd2fc1ac55044157333be19acf0cb7a0944d02231634aee7245f39adeefff02bdfd97b011d1289359117eed5ab0429b846bcf9215b51d2561cd16feb7cc5d1a189c9d19bb70986378468c59a230499bc9e33fe8e11a26cac4dd5687f8ea5fa468347db2b6c3dea7d4c24b665fddc530"; G2::from_bytes(&hex::decode(s).unwrap()).unwrap() } diff --git a/contrib/mir/src/bls/pairing.rs b/contrib/mir/src/bls/pairing.rs new file mode 100644 index 000000000000..11f199561a9d --- /dev/null +++ b/contrib/mir/src/bls/pairing.rs @@ -0,0 +1,120 @@ +/******************************************************************************/ +/* */ +/* SPDX-License-Identifier: MIT */ +/* Copyright (c) [2023] Serokell */ +/* */ +/******************************************************************************/ + +use std::borrow::Borrow; + +use blst::*; + +use super::{G1, G2}; + +const BLST_FP12_ZERO: blst_fp12 = blst_fp12 { + fp6: [blst_fp6 { + fp2: [blst_fp2 { + fp: [blst_fp { l: [0; 6] }; 2], + }; 3], + }; 2], +}; + +/// Verify that the product of pairings of the given list of points is equal to +/// 1 in the field Fq12. Returns `true` if the list is empty. The signature may +/// seem overly generic, but we want to accept both owned and borrowed +/// items, as there's no easy way to convert an owning iterator to iterator +/// over references. +pub fn pairing_check(pairs: impl IntoIterator) -> bool +where + TG1: Borrow, + TG2: Borrow, + Item: Borrow<(TG1, TG2)>, +{ + let mut x = blst_fp12::default(); // defaults to blst_fp12_one + + for i in pairs { + let tmp_p1 = i.borrow().0.borrow().to_affine(); + let tmp_p2 = i.borrow().1.borrow().to_affine(); + let tmp = blst_fp12::miller_loop(&tmp_p2, &tmp_p1); + unsafe { + blst_fp12_mul(&mut x, &x, &tmp); + } + } + + if x == BLST_FP12_ZERO { + false + } else { + let fin = x.final_exp(); + unsafe { blst_fp12_is_one(&fin) } + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn empty_list() { + assert!(pairing_check::<&_, &_, _>(&[])) + } + + #[test] + fn one_elt() { + assert!(pairing_check([(G1::zero(), G2::zero())])); + assert!(pairing_check([(G1::zero(), G2::one())])); + assert!(pairing_check([(G1::one(), G2::zero())])); + assert!(!pairing_check([(G1::one(), G2::one())])); + } + + #[test] + fn two_elts() { + use super::super::{g1, g2}; + + assert!(pairing_check([ + (G1::one(), G2::one()), + (G1::one(), G2::neg_one()) + ])); + assert!(pairing_check([ + (G1::neg_one(), G2::one()), + (G1::one(), G2::one()) + ])); + + assert!(pairing_check([ + (g1::tests::some_val(), g2::tests::some_val()), + (g1::tests::some_val(), g2::tests::neg_some_val()), + ])); + + assert!(pairing_check([ + (g1::tests::some_val(), g2::tests::some_val()), + (g1::tests::neg_some_val(), g2::tests::some_val()), + ])); + + // failing checks + assert!(!pairing_check([ + (G1::one(), G2::one()), + (G1::neg_one(), G2::neg_one()) + ])); + assert!(!pairing_check([ + (G1::neg_one(), G2::neg_one()), + (G1::one(), G2::one()) + ])); + assert!(!pairing_check([ + (G1::one(), G2::one()), + (G1::one(), G2::one()) + ])); + assert!(!pairing_check([ + (G1::neg_one(), G2::neg_one()), + (G1::neg_one(), G2::neg_one()) + ])); + + assert!(!pairing_check([ + (g1::tests::some_val(), g2::tests::some_val()), + (g1::tests::neg_some_val(), g2::tests::neg_some_val()), + ])); + + assert!(!pairing_check([ + (g1::tests::some_val(), g2::tests::some_val()), + (g1::tests::some_val(), g2::tests::some_val()), + ])); + } +} diff --git a/contrib/mir/src/gas.rs b/contrib/mir/src/gas.rs index e78927a08bd4..d281e1947ff1 100644 --- a/contrib/mir/src/gas.rs +++ b/contrib/mir/src/gas.rs @@ -681,6 +681,10 @@ pub mod interpret_cost { let size = Checked::from(msg.len()); (Checked::from(680) + (size * 3)).as_gas_cost() } + + pub fn pairing_check(size: usize) -> Result { + (450_000 + 342_500 * Checked::from(size)).as_gas_cost() + } } #[cfg(test)] diff --git a/contrib/mir/src/interpreter.rs b/contrib/mir/src/interpreter.rs index 72eb248e77ad..579967fc379f 100644 --- a/contrib/mir/src/interpreter.rs +++ b/contrib/mir/src/interpreter.rs @@ -15,6 +15,7 @@ use std::rc::Rc; use typed_arena::Arena; use crate::ast::*; +use crate::bls; use crate::context::Ctx; use crate::gas::{interpret_cost, OutOfGas}; use crate::irrefutable_match::irrefutable_match; @@ -991,6 +992,20 @@ fn interpret_one<'a>( ctx.gas.consume(interpret_cost::TOTAL_VOTING_POWER)?; stack.push(TypedValue::Nat(ctx.total_voting_power.clone())) } + I::PairingCheck => { + let list = pop!(V::List); + ctx.gas + .consume(interpret_cost::pairing_check(list.len())?)?; + let it = list.iter().map(|elt| { + let (g1, g2) = irrefutable_match!(elt; V::Pair).as_ref(); + ( + irrefutable_match!(g1; V::Bls12381G1), + irrefutable_match!(g2; V::Bls12381G2), + ) + }); + let res = bls::pairing::pairing_check(it); + stack.push(V::Bool(res)); + } I::Seq(nested) => interpret(nested, ctx, stack)?, } Ok(()) @@ -3755,4 +3770,19 @@ mod interpreter_tests { interpret_cost::TOTAL_VOTING_POWER + interpret_cost::INTERPRET_RET ); } + + #[test] + fn pairing_check() { + let mut stack = stk![V::List(MichelsonList::from(vec![ + V::new_pair(V::Bls12381G1(bls::G1::one()), V::Bls12381G2(bls::G2::one())), + V::new_pair( + V::Bls12381G1(bls::G1::one()), + V::Bls12381G2(bls::G2::neg_one()) + ) + ]))]; + let ctx = &mut Ctx::default(); + assert_eq!(interpret_one(&PairingCheck, ctx, &mut stack), Ok(())); + assert_eq!(stack, stk![V::Bool(true)]); + assert!(Ctx::default().gas.milligas() > ctx.gas.milligas()); + } } diff --git a/contrib/mir/src/typechecker.rs b/contrib/mir/src/typechecker.rs index d4bb72569993..378e8dad9030 100644 --- a/contrib/mir/src/typechecker.rs +++ b/contrib/mir/src/typechecker.rs @@ -1479,6 +1479,25 @@ pub(crate) fn typecheck_instruction<'a>( (App(VOTING_POWER, [], _), []) => no_overload!(VOTING_POWER, len 1), (App(VOTING_POWER, expect_args!(0), _), _) => unexpected_micheline!(), + (App(PAIRING_CHECK, [], _), [.., T::List(ty)]) + if match ty.as_ref() { + T::Pair(p) => matches!(p.as_ref(), (T::Bls12381G1, T::Bls12381G2)), + _ => false, + } => + { + stack[0] = T::Bool; + I::PairingCheck + } + (App(PAIRING_CHECK, [], _), [.., t]) => no_overload!( + PAIRING_CHECK, + TypesNotEqual( + T::new_list(T::new_pair(T::Bls12381G1, T::Bls12381G2)), + t.clone() + ) + ), + (App(PAIRING_CHECK, [], _), []) => no_overload!(PAIRING_CHECK, len 1), + (App(PAIRING_CHECK, expect_args!(0), _), _) => unexpected_micheline!(), + (App(other, ..), _) => todo!("Unhandled instruction {other}"), (Seq(nested), _) => I::Seq(typecheck(nested, ctx, self_entrypoints, opt_stack)?), @@ -4962,6 +4981,52 @@ mod typecheck_tests { too_short_test(&app!(CHECK_SIGNATURE), Prim::CHECK_SIGNATURE, 3) } + #[test] + fn pairing_check() { + assert_eq!( + parse("PAIRING_CHECK").unwrap().typecheck_instruction( + &mut Ctx::default(), + None, + &[app!( + list[app!(pair[app!(bls12_381_g1), app!(bls12_381_g2)])] + )] + ), + Ok(PairingCheck) + ); + } + + #[test] + fn pairing_check_wrong_type() { + assert_eq!( + parse("PAIRING_CHECK").unwrap().typecheck_instruction( + &mut Ctx::default(), + None, + &[app!( + list[app!(pair[app!(bls12_381_g1), app!(bls12_381_g1)])] + )] + ), + Err(TcError::NoMatchingOverload { + instr: Prim::PAIRING_CHECK, + stack: stk![Type::new_list(Type::new_pair( + Type::Bls12381G1, + Type::Bls12381G1 + ))], + reason: Some( + TypesNotEqual( + Type::new_list(Type::new_pair(Type::Bls12381G1, Type::Bls12381G2)), + Type::new_list(Type::new_pair(Type::Bls12381G1, Type::Bls12381G1)) + ) + .into() + ) + }) + ); + } + + #[test] + fn pairing_check_too_short() { + too_short_test(&app!(PAIRING_CHECK), Prim::PAIRING_CHECK, 1) + } + #[test] fn transfer_tokens() { let stk = &mut tc_stk![Type::new_contract(Type::Nat), Type::Mutez, Type::Int]; -- GitLab