bug: error in `secp256k1_add` when adding point at infinity

[enitrat]

thread 'stPreCompiledContracts2::test_CallEcrecover_Overflow_d4g0v0_Cancun' panicked at /Users/msaug/.cargo/registry/src/index.crates.io-6f17d22bba15001f/ark-ec-0.4.2/src/models/short_weierstrass/affine.rs:77:9:
assertion failed: point.is_on_curve()

thread 'stPreCompiledContracts2::test_CallEcrecover_Overflow_d4g0v0_Cancun' panicked at library/core/src/panicking.rs:221:5:
panic in a function that cannot unwind
stack backtrace:

   0:        0x10e82e74c - std::backtrace_rs::backtrace::libunwind::trace::hbebc8679d47bdc2c
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/std/src/../../backtrace/src/backtrace/libunwind.rs:116:5
   1:        0x10e82e74c - std::backtrace_rs::backtrace::trace_unsynchronized::h3a2e9637943241aa
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:        0x10e82e74c - std::sys::backtrace::_print_fmt::he430849680584674
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/std/src/sys/backtrace.rs:65:5
   3:        0x10e82e74c - <std::sys::backtrace::BacktraceLock::print::DisplayBacktrace as core::fmt::Display>::fmt::h243268f17d714c7f
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/std/src/sys/backtrace.rs:40:26
   4:        0x10e84b5ec - core::fmt::rt::Argument::fmt::h0d339881c25f3c31
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/fmt/rt.rs:173:76
   5:        0x10e84b5ec - core::fmt::write::hb3cfb8a30e72d7ff
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/fmt/mod.rs:1182:21
   6:        0x10e82b9e4 - std::io::Write::write_fmt::hfb2314975de9ecf1
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/std/src/io/mod.rs:1827:15
   7:        0x10e82fc74 - std::sys::backtrace::BacktraceLock::print::he14461129ccbfef5
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/std/src/sys/backtrace.rs:43:9
   8:        0x10e82fc74 - std::panicking::default_hook::{{closure}}::h14c7718ccf39d316
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/std/src/panicking.rs:269:22
   9:        0x10e82f898 - std::panicking::default_hook::hc62e60da3be2f352
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/std/src/panicking.rs:296:9
  10:        0x10e830738 - std::panicking::rust_panic_with_hook::h09e8a656f11e82b2
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/std/src/panicking.rs:800:13
  11:        0x10e830060 - std::panicking::begin_panic_handler::{{closure}}::h1230eb3cc91b241c
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/std/src/panicking.rs:667:13
  12:        0x10e82ebd8 - std::sys::backtrace::__rust_end_short_backtrace::hc3491307aceda2c2
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/std/src/sys/backtrace.rs:168:18
  13:        0x10e82fd50 - rust_begin_unwind
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/std/src/panicking.rs:665:5
  14:        0x10ece17ac - core::panicking::panic_nounwind_fmt::runtime::h5290ab2b4897aadc
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/panicking.rs:112:18
  15:        0x10ece17ac - core::panicking::panic_nounwind_fmt::h91ee161184879b56
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/panicking.rs:122:5
  16:        0x10ece1824 - core::panicking::panic_nounwind::heab7ebe7a6cd845c
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/panicking.rs:221:5
  17:        0x10ece1954 - core::panicking::panic_cannot_unwind::hedc43d82620205bf
                               at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/panicking.rs:309:5
  18:        0x104943108 - cairo_native::starknet::handler::StarknetSyscallHandlerCallbacks<T>::wrap_secp256k1_add::hc2142a54f1359a37
                               at /Users/msaug/.cargo/git/checkouts/cairo_native-0bad8506281b7281/f3f6ba2/src/starknet.rs:1476:9
  19:        0x12f7eeebc - _impl$core::starknet::secp256_trait::recover_public_key::<core::starknet::secp256k1::Secp256k1Point, core::starknet::secp256k1::Secp256k1PointDrop, core::starknet::secp256k1::Secp256k1Impl, core::starknet::secp256k1::Secp256k1PointImpl>(f276)
  20:        0x12f7be184 - _impl$evm::precompiles::ec_recover::EcRecover::exec(f240)
  21:        0x12f3eaa04 - _impl$evm::precompiles::PrecompilesImpl::exec_precompile(f134)
  22:        0x12f216f90 - _impl$evm::interpreter::EVMImpl::execute_code(f109)
  23:        0x12f1def10 - _impl$evm::interpreter::EVMImpl::process_message(f79)
  24:        0x12f7d344c - _impl$evm::call_helpers::CallHelpersImpl::generic_call(f254)
  25:        0x12f4d3314 - _impl$evm::instructions::system_operations::SystemOperations::exec_call(f152)
  26:        0x12f346610 - _impl$evm::interpreter::EVMImpl::execute_opcode(f133)
  27:        0x12f210978 - _impl$evm::interpreter::EVMImpl::execute_code(f109)
  28:        0x12f1def10 - _impl$evm::interpreter::EVMImpl::process_message(f79)
  29:        0x12f1babfc - _impl$evm::interpreter::EVMImpl::process_message_call(f61)
  30:        0x12f1a1288 - _impl$evm::interpreter::EVMImpl::process_transaction(f47)
  31:        0x12f18ba04 - _impl$contracts::kakarot_core::eth_rpc::EthRPC::<contracts::kakarot_core::kakarot::KakarotCore::ContractState, contracts::kakarot_core::kakarot::KakarotCore::_KakarotCoreState, contracts::kakarot_core::kakarot::KakarotCore::ContractStateDrop>::eth_send_transaction(f38)
  32:        0x12f180b5c - _impl$contracts::kakarot_core::eth_rpc::__wrapper__EthRPC__eth_send_transaction::<contracts::kakarot_core::kakarot::KakarotCore::ContractState, contracts::kakarot_core::kakarot::KakarotCore::_KakarotCoreState, contracts::kakarot_core::kakarot::KakarotCore::ContractStateDrop, contracts::kakarot_core::kakarot::KakarotCore::ContractStateEthRPC>(f23)
  33:        0x12f181388 - __mlir_ciface_f23
thread caused non-unwinding panic. aborting.

Repro: scarb 2.8.3 clone https://github.com/kkrt-labs/kakarot-ssj on main scarb build -p contracts - builds the required contract with some debug print logs

clone https://github.com/kkrt-labs/ef-tests ensure correct branch git checkout feat/cairo-native make make setup-kakarot copy the contracts built previously:cp ../kakarot-ssj/target/dev/contracts_* build/v1 cargo test test_CallEcrecover_Overflow_d0g0v0_Cancun --features v1,native -- --nocapture

[enitrat]

    /// Constructs a group element from x and y coordinates.
    /// Performs checks to ensure that the point is on the curve and is in the right subgroup.
    pub fn new(x: P::BaseField, y: P::BaseField) -> Self {
        let point = Self {
            x,
            y,
            infinity: false,
        };
        assert!(point.is_on_curve());
        assert!(point.is_in_correct_subgroup_assuming_on_curve());
        point
    }

This is the source code for ark-ec-0.4.2/src/models/short_weierstrass/affine.rs:77:9 Looks like the panic happens when we try to create a group element from x, y that are not on the curve.

test data=4, which corresponds to a test with# S Overflow == secp256k1N The test data is defined as:

# Test limit RS values for EC Recover precompile (R, S == secp256k1n)
# secp256k1n == 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

CallEcrecover_Overflow:

  env:
    currentCoinbase: 2adc25665018aa1fe0e6bc666dac8fc2697ff9ba
    currentDifficulty: '0x20000'
    currentGasLimit: '0xFF112233445566'
    currentNumber: '1'
    currentTimestamp: '1000'

  pre:  

    cccccccccccccccccccccccccccccccccccccccc:
      code: |
        :yul berlin
        {
         // Copy Hash, V, R, S values
         calldatacopy(0x00, 0x04, 0x80)

         // Call the EC Recover Precompile
         sstore(0, call(3000, 1, 0, 0, 0x80, 0x80, 0x20))
         sstore(1, mload(0x80))
        }  
      nonce: '0'
      storage: {}
      balance: 0

    a94f5374fce5edbc8e2a8697c15331677e6ebf0b:
      balance: '1000000000000000000'
      code: 0x
      nonce: '0'
      storage: {}

  transaction:
    data:
    # R Overflow == secp256k1N
    - :label fail     :abi f(uint,uint,uint,uint) 0x18c547e4f7b0f325ad1e56f57e26c745b09a3e503d86e00e5255ff7f715d3d1c 0x1c 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 0x1fffd310ac743f371de3b9f7f9cb56c0b28ad43601b4ab949f53faa07bd2c804
    # R Overflow == secp256k1N + 1
    - :label fail     :abi f(uint,uint,uint,uint) 0x18c547e4f7b0f325ad1e56f57e26c745b09a3e503d86e00e5255ff7f715d3d1c 0x1c 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364142 0x1fffd310ac743f371de3b9f7f9cb56c0b28ad43601b4ab949f53faa07bd2c804
    # R High == secp256k1N - 1 (Fails due to R not being able to be a point on the curve, not due to the secp256k1N limit)
    - :label fail     :abi f(uint,uint,uint,uint) 0x18c547e4f7b0f325ad1e56f57e26c745b09a3e503d86e00e5255ff7f715d3d1c 0x1c 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140 0xefffd310ac743f371de3b9f7f9cb56c0b28ad43601b4ab949f53faa07bd2c804
    # R High == secp256k1N - 2
    - :label pass01   :abi f(uint,uint,uint,uint) 0x18c547e4f7b0f325ad1e56f57e26c745b09a3e503d86e00e5255ff7f715d3d1c 0x1c 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd036413f 0xefffd310ac743f371de3b9f7f9cb56c0b28ad43601b4ab949f53faa07bd2c804
    # S Overflow == secp256k1N
    - :label fail     :abi f(uint,uint,uint,uint) 0x18c547e4f7b0f325ad1e56f57e26c745b09a3e503d86e00e5255ff7f715d3d1c 0x1c 0x48b55bfa915ac795c431978d8a6a992b628d557da5ff759b307d495a36649353 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
    # S Overflow == secp256k1N + 1
    - :label fail     :abi f(uint,uint,uint,uint) 0x18c547e4f7b0f325ad1e56f57e26c745b09a3e503d86e00e5255ff7f715d3d1c 0x1c 0x48b55bfa915ac795c431978d8a6a992b628d557da5ff759b307d495a36649353 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364142
    # S High == secp256k1N - 1
    - :label pass02   :abi f(uint,uint,uint,uint) 0x18c547e4f7b0f325ad1e56f57e26c745b09a3e503d86e00e5255ff7f715d3d1c 0x1c 0x48b55bfa915ac795c431978d8a6a992b628d557da5ff759b307d495a36649353 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140
    # S High == secp256k1N - 2
    - :label pass03   :abi f(uint,uint,uint,uint) 0x18c547e4f7b0f325ad1e56f57e26c745b09a3e503d86e00e5255ff7f715d3d1c 0x1c 0x48b55bfa915ac795c431978d8a6a992b628d557da5ff759b307d495a36649353 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd036413f

    gasLimit:
    - 'F000000000'
    gasPrice: '10'
    nonce: '0'
    secretKey: 45a915e4d060149eb4365960e6a7a45f334393093061116b197e3240065ff2d8
    to: cccccccccccccccccccccccccccccccccccccccc

    value:
    - '100000'

  expect:

  - indexes:
      data: 
      - :label fail
      gas: !!int -1
      value: !!int -1
    network: 
    - ">=Cancun"
    result:
      cccccccccccccccccccccccccccccccccccccccc:
        storage:
          0x00: 0x01
          0x01: 0x00

  - indexes:
      data: 
      - :label pass01
      gas: !!int -1
      value: !!int -1
    network: 
    - ">=Cancun"
    result:
      cccccccccccccccccccccccccccccccccccccccc:
        storage:
          0x00: 0x01
          0x01: 0x2182da748249a933bf737586b80212df19b8f829

  - indexes:
      data: 
      - :label pass02
      gas: !!int -1
      value: !!int -1
    network: 
    - ">=Cancun"
    result:
      cccccccccccccccccccccccccccccccccccccccc:
        storage:
          0x00: 0x01
          0x01: 0x1b85ac3c9b09de43659c5d04a2d9c75457d9abf4

  - indexes:
      data: 
      - :label pass03
      gas: !!int -1
      value: !!int -1
    network: 
    - ">=Cancun"
    result:
      cccccccccccccccccccccccccccccccccccccccc:
        storage:
          0x00: 0x01
          0x01: 0xd0277c8a3eccd462a313fc60161bac36b16e8699

I think the crate used to 'translate' cairo's recover_public_key doesn't have strictly the same behavior and panics if S is not the right value?

[Oppen]

The following documents will probably be relevant to fix: https://github.com/rust-lang/rfcs/blob/master/text/1236-stabilize-catch-panic.md https://doc.rust-lang.org/std/panic/fn.catch_unwind.html

[edg-l]

If i'm reading the backtrace correctly, it looks like it panics here:

  18:        0x104943108 - cairo_native::starknet::handler::StarknetSyscallHandlerCallbacks<T>::wrap_secp256k1_add::hc2142a54f1359a37
                               at /Users/msaug/.cargo/git/checkouts/cairo_native-0bad8506281b7281/f3f6ba2/src/starknet.rs:1476:9
  19:        0x12f7eeebc - _impl$core::starknet::secp256_trait::recover_public_key::<core::starknet::secp256k1::Secp256k1Point, core::starknet::secp256k1::Secp256k1PointDrop, core::starknet::secp256k1::Secp256k1Impl, core::starknet::secp256k1::Secp256k1PointImpl>(f276)
  20:        0x12f7be184 - _impl$evm::precompiles::ec_recover::EcRecover::exec(f240)

In this case, i think it panicked inside the syscall handler implementation, where it's outside cairo-native control, i think the panic should be avoided/fixed in the syscall handler implementation for the secp256k1_add method, in blockifier probably.

[enitrat]

I think the issue would be here:

https://github.com/kkrt-labs/sequencer/blob/313ea8659a0266687d862ecc0c276aef56f519e5/crates/blockifier/src/execution/native/syscall_handler.rs#L1034-L1042

There's no restriction that the point p is a valid point on the curve

In this case, the syscall is called with:

Doing a secp256k1 add with p0: Secp256k1Point { x: U256 { lo: 129003617997021303013218207968950584051, hi: 172311478357886825233335797671820713936 }, y: U256 { lo: 116674903077840365960837368733780265089, hi: 208347267320301613117786355181846465373 } } and p1: Secp256k1Point { x: U256 { lo: 0, hi: 0 }, y: U256 { lo: 0, hi: 0 } }

[xrvdg]

The issue comes to light in the syscall implementation of secp256k1_add in the blockifier, but the problem occurs earlier; the panic is appropiate here.

// cairo_native src/starknet.rs
pub triat StarknetSyscallHandler{
    fn secp256k1_add(
        &mut self,
        p0: Secp256k1Point,
        p1: Secp256k1Point,
        remaining_gas: &mut u128,
    ) -> SyscallResult<Secp256k1Point>;
}

The signature of secp256k1_add states that it takes two valid secp256k1 points, but as we’ve seen at least one of these points can be invalid. My guess is that a Secp256k1Point is created without (implicitely) going through the new syscall.

@enitrat could you please boil it down to a minimal example that we can investigate further.

[enitrat]

@xrvdg yes, here's the relevant code: https://github.com/starkware-libs/cairo/blob/main/corelib/src/starknet/secp256_trait.cairo#L93-L124

Here, because we give s = N we have let u2 = u256_mul_mod_n(s, r_inv, n_nz); = 0, thus: let point2 = r_point.mul(u2).unwrap_syscall() = r_point * 0 = identity

and in secp256k1_add, we pass these two secp256k1 points, one of them being the point at infinity

the add function is defined here: https://github.com/kkrt-labs/sequencer/blob/7c8bd351ecf0c0375d7030466500523a9a924273/crates/blockifier/src/execution/native/syscall_handler.rs#L931-L938

when executing let rhs: Affine<Curve> = p1.into(); we are using the From implementation here: https://github.com/kkrt-labs/sequencer/blob/7c8bd351ecf0c0375d7030466500523a9a924273/crates/blockifier/src/execution/native/syscall_handler.rs#L1034-L1044

this from implementation calls new: https://github.com/nethermindeth/sequencer/blob/native2.8.x/crates/blockifier/src/execution/native/syscall_handler.rs#L1034-L1041

Which fails because x,y = 0 => identity point is not on the curve

[xrvdg]

@enitrat, thank you for the example and the clarification. I think I understand the issue now. I'll dive into it and get back to you.

[enitrat]

repro idea:

#[cfg(test)]
mod tests{
    use core::starknet::secp256_trait::{Signature, Secp256Trait, recover_public_key};
    use core::starknet::secp256k1::{Secp256k1Point};
    #[test]
    fn test_repro_native_bug(){
        let msg_hash = 0x123;
        let signature = Signature {r: 1, s:Secp256Trait::<Secp256k1Point>::get_curve_size(), y_parity: false};
        let public_key = recover_public_key::<Secp256k1Point>(msg_hash, signature);
    }
}

[enitrat]

actually executing the code above fails when doing scarb-native-test (but not with blockifier's native syscall handler)

cc @edg-l: what is the syscall handler used by the "native runner" ?

[edg-l]

actually executing the code above fails when doing scarb-native-test (but not with blockifier's native syscall handler)

cc @edg-l: what is the syscall handler used by the "native runner" ?

It's this: https://github.com/lambdaclass/cairo_native/blob/ae17dd370a7bbf6affeefb9fa6954965e8b52239/src/starknet_stub.rs#L24

maybe its outdated?

[enitrat]

actually, in the case of the snippet above, the failure is un secp256k1_mul:

testing secp256k1_bug ...
running 1 tests
thread 'main' panicked at src/starknet_stub.rs:422:17:
internal error: entered unreachable code
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
thread 'main' panicked at library/core/src/panicking.rs:221:5:
panic in a function that cannot unwind
stack backtrace:
   0:        0x104ef613c - <std::sys::backtrace::BacktraceLock::print::DisplayBacktrace as core::fmt::Display>::fmt::h243268f17d714c7f
   1:        0x104e5edec - core::fmt::write::hb3cfb8a30e72d7ff
   2:        0x104ecb4c4 - std::io::Write::write_fmt::hfb2314975de9ecf1
   3:        0x104ef84ec - std::panicking::default_hook::hc62e60da3be2f352
   4:        0x104ef96c8 - std::panicking::rust_panic_with_hook::h09e8a656f11e82b2
   5:        0x104ef8930 - std::panicking::begin_panic_handler::{{closure}}::h1230eb3cc91b241c
   6:        0x104ef88cc - std::sys::backtrace::__rust_end_short_backtrace::hc3491307aceda2c2
   7:        0x104ef88c0 - _rust_begin_unwind
   8:        0x109aab95c - core::panicking::panic_nounwind_fmt::h91ee161184879b56
   9:        0x109aab9b8 - core::panicking::panic_nounwind::heab7ebe7a6cd845c
  10:        0x109aab970 - core::panicking::panic_cannot_unwind::hedc43d82620205bf
  11:        0x104c81070 - cairo_native::starknet::handler::StarknetSyscallHandlerCallbacks<T>::wrap_secp256k1_mul::h97d0847096d7a54c
thread caused non-unwinding panic. aborting.
[1]    65641 abort      scarb-native-test

perhaps the stub is not entirely reflecting the expected behavior as well

[xrvdg]

@azteca1998 how is the identity point / point at infinity supposed to be represented in Secp256k1Point and Secp256r1Point?

[enitrat]

I think it's just a point where x,y = 0?

[azteca1998]

@azteca1998 how is the identity point / point at infinity supposed to be represented in Secp256k1Point and Secp256r1Point?

If I recall correctly, it's when x and y are its initial state. But I could be wrong since I don't understand 100% how they work internally (I don't know the math).

[xrvdg]

Given the curve parameters of k1 and r1 the point (0,0) can probably be used as a special value to signify infinity, but neither ark-ff nor the secp256k1 implementation in bitcoin-core go for this approach. They do:

typedef struct {
    secp256k1_fe x;
    secp256k1_fe y;
    int infinity; /* whether this represents the point at infinity */
} secp256k1_ge;

Therefore I suggest the following change to native:

struct K1;
struct R1;

pub enum Secp256Point<Curve> {
    Infinity,
    Point(U256, U256, PhantomData<Curve>),
}

type Secp256k1Point = Secp256Point<K1>;
type Secp256r1Point = Secp256Point<R1>;

This also simplifies the implementation in the blockifier.

[edg-l]

Given the curve parameters of k1 and r1 the point (0,0) can probably be used as a special value to signify infinity, but neither ark-ff nor the secp256k1 implementation in bitcoin-core go for this approach. They do:

typedef struct {
    secp256k1_fe x;
    secp256k1_fe y;
    int infinity; /* whether this represents the point at infinity */
} secp256k1_ge;

Therefore I suggest the following change to native:

struct K1;
struct R1;

pub enum Secp256Point<Curve> {
    Infinity,
    Point(U256, U256, PhantomData<Curve>),
}

type Secp256k1Point = Secp256Point<K1>;
type Secp256r1Point = Secp256Point<R1>;

This also simplifies the implementation in the blockifier.

https://github.com/lambdaclass/cairo_native/pull/828

is this what you need?

i'm not sure if the stub has the correct implementation, but it doesnt crash now

[xrvdg]

is this what you need?

That definition of secp256 points works for me.