0xPolygonMiden / miden-vm

STARK-based virtual machine
MIT License
630 stars 160 forks source link

Memory cannot handle 2 reads at the same addres during the same clock cycle #1560

Open plafer opened 6 days ago

plafer commented 6 days ago

Failing test:

#[test]
fn rcomb_base() {
    const X_PTR: u64 = 42;
    const Z_PTR: u64 = 142;
    const A_PTR: u64 = 1142;
    let asm_op = "begin rcomb_base end";

    let stack_inputs = [1,2,3,4,5,6,7,0,0,X_PTR, Z_PTR, A_PTR];
    let test = build_test!(asm_op, &stack_inputs);
    let _last_state = test.get_last_stack_state();
}
bobbinth commented 6 days ago

Interesting! I though we used it for Falcon signature verification - but I guess we do not.

Al-Kindi-0 commented 6 days ago

Interestingly, we do

bobbinth commented 6 days ago

Hmmm - in that case, we have tests in miden-base that tests execution, proving, and verification of programs with the Falcon signature - and they seem to all pass. Wonder why it doesn't work in this specific context.

Al-Kindi-0 commented 6 days ago

From the error I am seeing, I think it might be because the memory read is happening at 0-th cycle and hence we are getting a subtraction with overflow. In the other tests, with overwhelming probability, this will not happen. Edit: The problem is more related to the pointers Z_PTR and A_PTR being the same which is not the case through out the Falcon MASM code.

plafer commented 6 days ago

From my understanding, the overflow is triggered when we attempt to read the same memory location in the same cycle - not terribly useful, but could happen due to user error (as mentioned in https://github.com/0xPolygonMiden/miden-vm/pull/1561#discussion_r1826016543)

Al-Kindi-0 commented 6 days ago

Are you sure that the input stack is in the right order for RCOMBBASE?

Al-Kindi-0 commented 6 days ago

From my understanding, the overflow is triggered when we attempt to read the same memory location in the same cycle - not terribly useful, but could happen due to user error (as mentioned in #1561 (comment))

Yeah, maybe it is worth adding a disclaimer to the op to specify that the Z_PTR and A_PTR should be different

Al-Kindi-0 commented 6 days ago

Yes, the stack input is not in the expected order i.e., the pointers are not in their correct place. This explains why Falcon tests didn't raise any errors as when the pointers are provided in their right place on the stack and the Z_PTR and A_PTR are different then everything should work well. Thus the problem is only when by mistake the two aforementioned addresses are equal and this is what should be addressed here and in any future ops.

plafer commented 6 days ago

Thus the problem is only when by mistake the two aforementioned addresses are equal and this is what should be addressed here and in any future ops.

Yup, exactly.

Yeah, maybe it is worth adding a disclaimer to the op to specify that the Z_PTR and A_PTR should be different

I don't think so - they're obviously different from the documentation (i.e. one is randomness, the other is $T_i(...)$ etc). As mentioned a few times here, this issue here only addresses the case where there's a use error with RCOMBBASE (and potentially future ops).