[Bug] Observed discrepancy in the behavior of the compute_doubling_slope function

[whichqua]

Describe the bug

When investigating a discrepancy in the behavior of the compute_doubling_slope function, I was able to isolate a potential bug. The issue arises when compiling and running the following Cairo program:

from starkware.cairo.common.cairo_secp.bigint3 import BigInt3
from starkware.cairo.common.secp256r1.ec import (
     EcPoint, 
     compute_doubling_slope,
)

let test_point = EcPoint(
    BigInt3(-1, -5, -10), 
    BigInt3(2, 4, 20)
);
let (slope_k) = compute_doubling_slope(test_point);

To Reproduce

Compile and run the program with both VMs
Rust VM: The program runs successfully without any issues.
Python VM: The program fails with the following error:

let (slope_k) = compute_doubling_slope(test_point);
                ^********************************^
cairo-vm/cairo-vm-env/lib/python3.9/site-packages/starkware/cairo/common/secp256r1/ec.cairo:49:5: (pc=0:176)
    verify_zero(
    ^**********^

Traceback (most recent call last):
  File "cairo-vm/cairo-vm-env/lib/python3.9/site-packages/starkware/cairo/common/secp256r1/field.cairo", line 130, in <module>
    assert r == 0, f"verify_zero: Invalid input {ids.val.d0, ids.val.d1, ids.val.d2}."
AssertionError: verify_zero: Invalid input (3618502788666131213697322783095069128085273774818029388902779187248654918653, 1000998741443085759556365127856636729742657698, 1024993258929947376774861639509083549149264010799).

Expected behavior

Both VMs should behave the same way.

What version/commit are you on?

Rust version: 2.0.0-rc0
Python version: 0.13.2

Additional context

• The failing hint was introduced in this PR and reuses the existing compute_slope function from the Rust VM implementation.
• No significant differences are apparent in the hint's logic, suggesting the issue might stem from subtle differences in VM handling or edge cases in the inputs.
• The issue manifests only with the Python VM.
• [Question] Is it possible to have scenarios that have negative limbs?

Relevant PRs

#1706
#1829

[ilyalesokhin-starkware]

Yes, negative limbs are possible:
https://github.com/starkware-libs/cairo-lang/blob/master/src/starkware/cairo/common/cairo_secp/bigint3.cairo#L4

[FrancoGiachetta]

Hi @whichqua!
Took a look at this. I was able to reproduce both cases. Do you know what should be the correct output? That would be a little to check if the issue comes from the Rust VM.

Talking about you question: Yes, limbs can be negative. You can check BigInt in Python VM for references on that.

[whichqua]

Do you know what should be the correct output?

I am not sure. I can spend a little more time on this but it might be good to have pointers on what to check.

[FrancoGiachetta]

How are you compiling and running that program?

[whichqua]

Compiling via cairo-compile:
This was the command I was using

cairo-compile --cairo_path="cairo_programs/proof_programs:cairo_programs/benchmarks" cairo_programs/secp_cairo0_ec.cairo --output cairo_programs/proof_programs/secp_cairo0_ec.json --proof_mode"

For running I was using run_program_simple

fn run_program_simple(data: &[u8]) {
    run_program(data, false, None, None, None)
}

[whichqua]

@FrancoGiachetta any updates?

[FrancoGiachetta]

Hi @whichqua!
Sorry for the absence. I think I've found the issue here. The method verify_zero, referenced in the error, executes a hint:

%{
        from starkware.cairo.common.cairo_secp.secp_utils import SECP_P, pack

        q, r = divmod(pack(ids.val, PRIME), SECP_P)
        assert r == 0, f"verify_zero: Invalid input {ids.val.d0, ids.val.d1, ids.val.d2}."
        ids.q = q % PRIME
    %}

The problem here is that, to mimic the divmod inside the hint from rust, we use div_rem:

pub fn verify_zero(
    vm: &mut VirtualMachine,
    exec_scopes: &mut ExecutionScopes,
    ids_data: &HashMap<String, HintReference>,
    ap_tracking: &ApTracking,
    secp_p: &BigInt,
) -> Result<(), HintError> {
    exec_scopes.insert_value("SECP_P", secp_p.clone());
    let val = Uint384::from_var_name("val", vm, ids_data, ap_tracking)?.pack86();
    let (q, r) = val.div_rem(&secp_p);
    if !r.is_zero() {
        return Err(HintError::SecpVerifyZero(Box::new(val)));
    }

    insert_value_from_var_name("q", Felt252::from(&q), vm, ids_data, ap_tracking)
}

An so div_rem does not provide the same behaviour as divmod in cases were negative values are used. To solve this, we you could use div_mod_floor instead.
A PR will be created to make this change. However, I've also found that the code you've provided uses a variant of the same hint (which uses SECP256R1_P instead of SECP_P) and so is not implemented in the rust vm.

Running the example above with this little change should provide with same result in both VMs.

[whichqua]

@FrancoGiachetta I will look at the hint at hand, and get back! Thanks for your speedy response and PR