cairo-vm-go
cairo-vm-go copied to clipboard
NethermindEth
feat: Replace secp_utils usage of `big.Int` with uint256 library.
@rodrigo-pino i have a few questions :
should i also modify SecPPacked and SecPSplit functions?
Also, GetSecPBig for example now returns a uint256.Int, i guess i should also modify the code where this utils is used (i.e., zerohint_ec.go and zerohint_signature(s).go ) ?
Hey @TAdev0! Yes please add both functions since their values are never bigger than the 256 bits space. Regarding the code that uses them, it must be updated as well since we need the CI to pass in order to merge.
In case the consecuences of using uint64 library are very hard to integrate we can do smth good enough now and follow it up with another PR focused on that
@rodrigo-pino ready for a first review. Not sure everything is correct with my syntax.
There are some errors. Especially compilations one. Could you please fix them.
Also you can test most of the CI by doing make unit.
This will compile & run all unit tests.
@rodrigo-pino I have residual mismatch issues, for example:
zerohint_utils_test.go:163: value scope value mismatch:
have: 25711014748331347274616151948719391133326249308066029554892800
want: 25711014748331348032841661176477624755444844903972403171819520
I double checked that i correctly defined constants in GetSecP , getBase and GetSecp256R1_P.
I suspect that the issue comes from SecPPacked as it is the common denominator for all failing tests. But i'm struggling debugging efficiently, i checked if it could come from DivMod which behaves differently with BigInt and uint256, but it seems ok.
I suspect that the issue comes from SecPPacked as it is the common denominator for all failing tests. But i'm struggling debugging efficiently, i checked if it could come from DivMod which behaves differently with BigInt and uint256, but it seems ok.
I see that's weird, maybe something to do with references? My tip for debugging would be testing the failing functions one by one with some prints scattered around. You'll eventually find the wrong piece of code
Ok left some other small ones, regarding the issue, I'll try to look it later. Can you debug it manually with prints?
@rodrigo-pino ok so basically, i fail for all EcNegate tests (and others, but i think the root cause is the same). These tests call newEcNegateHint , which will use GetSecPUint256 and SecPPacked among other stuff i didnt change.
GetSecPUint256 returns a const which should be fine.
I tried printing different variables and indeed, the result value of newEcNegateHint, which is yBig , is always a little bit different, with generally 8 identical bytes and the rest different.
yBig is the NEG + MOD result of SecPPacked , and SecPPacked seems ok as well, using getBaseUint256 .
I even tried keeping BigInt for SecPPacked computation, without any modification, and i still have these errors.
I did a super quick check. In SecPPacked before returning the packedBig variable I tried converting it to a uint256 and then back to a big.Int and tests failed.
Before:
return *packedBig, nil
After:
packedUint256 := new(uint256.Int)
packedUint256.SetFromBig(packedBig)
return *packedUint256.ToBig(), nil
The failing tests seem to be using quite large values though. Could it be the test values are just unrealistic? Though I would say the results should match the python vm regardless.
By looking at the python VM code you immediately realize that input values are always less than 256 bits, and output values are always smaller as well. This means that assuming the current implementation is correct, the one with big.Ints was flawed. It is possible the tests are actually not returning a correct value by using wrong inputs.
The python and the go vm should always return the same value, but if the python vm expect always it's input to be in the 256 bits range, whatever we throw at it bigger than it is not valid for comparison. We are loooking to match the python vm in the 256 bit range not on bigger stuff, assuming of course, that to the python VM you could feed bigger stuff, to which there is not test to show it.
If there is a test that inputs a number bigger than 256 bits or returns as an output a number bigger than 256 bits, that test is not correct.
If there is a test that inputs a number bigger than 256 bits or returns as an output a number bigger than 256 bits, that test is not correct.
The inputs are not larger than 256 bits in the tests. The outputs can be. The output can be a scope value and not a memory value.
If there is a test that inputs a number bigger than 256 bits or returns as an output a number bigger than 256 bits, that test is not correct.
The inputs are not larger than 256 bits in the tests. The outputs can be. The output can be a scope value and not a memory value.
If it works like this, then it is also problematic in terms of replacing scope any interface with the new struct, if the values are bigger then 256 bits, but that is not relevant in this scope.
The weird thing is that my impl with uint256 is supposed to be the same. I guess there is some issue related to bigint to uint256 conversion for the output if all inputs are indeed < 256bits
Or I did something wrong
The inputs are not larger than 256 bits in the tests. The outputs can be. The output can be a scope value and not a memory value.
How can they be? The only way to get a higher than 256 bits is in packed right? Looking at the Cairo VM description it is stated that the number that needs to be formed needs to be in that range.
That Python doesn't have statically typed values doesn't mean we have to follow through if it doesn't make sense. I haven't studied this part long enough, but it feels to me that both pack and split are meant to use in tandem. So I don't see why the inputs forpack should be bigger than 256 bits
... The output can be a scope value and not a memory value.
I am not convinced either that a scope value can be bigger than 256 bits. Obviously the python VM allows it (python allows many things by itself). The question is, is there any Cairo 0 code that could be written that could create a number bigger than 256 bits in the scope.
Also, remember that the Scope was defined by us as well, so using it as an argument of what it can have inside or not is not valid since we can always redefine it.
The weird thing is that my impl with uint256 is supposed to be the same. I guess there is some issue related to bigint to uint256 conversion for the output if all inputs are indeed < 256bits ...
I think you've solved it correctly and we are finding some inconsistencies unrelated with them. After this PR the VM will be better
The inputs are not larger than 256 bits in the tests. The outputs can be. The output can be a scope value and not a memory value.
How can they be? The only way to get a higher than 256 bits is in packed right? Looking at the Cairo VM description it is stated that the number that needs to be formed needs to be in that range.
That Python doesn't have statically typed values doesn't mean we have to follow through if it doesn't make sense. I haven't studied this part long enough, but it feels to me that both
packandsplitare meant to use in tandem. So I don't see why the inputs forpackshould be bigger than 256 bits
- No input in the tests are larger than 256 bits.
- It's possible that the 3 values passed to pack is resulting in a value greater than 256 bits in the tests. I haven't checked this.
- I'm guessing the programmer must assert the input ranges of the arguments to
packin the cairo code. If they don't then the python vm and our vm will result in differing results written to the scope. I don't know if any programmer will have a valid reason for doing something like this.
If we remove test cases where the 3 values passed to pack can result in a value > 256 bits then everything should be fine. But I am a bit uncomfortable with how our vm will silently write the wrong result to the scope in case the inputs aren't validated properly. I'd rather throw an error than silently fail? Not sure if that makes sense.
@har777 indeed if i replace SecPPacked with the previous version using bigInt, tests for ec pass. I confirm that the value after exponentiation, mul , add and packing in SecPPacked will be greater than type(uint256).max . But i still have 2 tests failing in this configuration:
--- FAIL: TestZeroHintEc (0.00s)
--- FAIL: TestZeroHintEc/NondetBigint3V1_3 (0.00s)
zerohint_utils_test.go:195: expected an error containing "num != 0", got nil err
--- FAIL: TestVerifyZeroHint (0.00s)
--- FAIL: TestVerifyZeroHint/VerifyZero_1 (0.00s)
zerohint_utils_test.go:197:
Error Trace: /Users/tristan/Desktop/Dev/cairo-vm-go/pkg/hintrunner/zero/zerohint_utils_test.go:197
/Users/tristan/Desktop/Dev/cairo-vm-go/pkg/hintrunner/zero/zerohint_test.go:255
/Users/tristan/Desktop/Dev/cairo-vm-go/pkg/hintrunner/zero/zerohint_test.go:267
Error: Error "verify_zero: Invalid input (1, 1, 1)" does not contain "verify_zero: Invalid input (1, 1, 1)."
Test: TestVerifyZeroHint/VerifyZero_1
```
The first failing seems to be related to this code:
if num.Cmp(uint256.NewInt(0)) != 0 {
return nil, fmt.Errorf("num != 0")
}
error is not thrown while it should The 2nd error is related to this code:
if rUint256.Cmp(uint256.NewInt(0)) != 0 {
return fmt.Errorf("verify_zero: Invalid input (%v, %v, %v)", valValues[0], valValues[1], valValues[2])
}
Their might be an issue related to the Cmp version for uint256?
I dont think so. I tried changing just that part:
num2 := new(uint256.Int)
num2.SetFromBig(num)
if num2.Cmp(uint256.NewInt(0)) != 0 {
return nil, fmt.Errorf("num != 0")
}
And it passed.
Lets just remove the test. I was trying to make the results always be consistent with the python vm. If we are using uint256 then might as well assume the value will always be a uint256 written to scope. The test which fails makes no sense in that context.
@har777 you want to remove all failing tests? what is the reason for the 2 others failing? I cannot find any reason for now.
@har777 you want to remove all failing tests? what is the reason for the 2 others failing? I cannot find any reason for now.
Just this one:
--- FAIL: TestZeroHintEc/NondetBigint3V1_3 (0.00s)
zerohint_utils_test.go:195: expected an error containing "num != 0", got nil err
mmh i dont understand. If i remove this test, i still have many tests failing.