Open zac-williamson opened 11 months ago
Hey I would like to help this issue if it is still available. @zac-williamson
I am currently dealing with this issue. But I have a question regarding to addmod
part. How can we be sure that add is not going to overflow before 4 add
calls. Most of the addmod
calls can be converted to add
without error but i couldn't be sure about edge cases. Lets say
let a := 2^255
let b := 2^255
let c := add(a, b)
or
let a := bn254 field
let b := 1
let c := add(a, b)
in that case they exceed bn254 field. public inputs are bytes32 so they can be up to 2^256 and proof is bytes so it can be also up to 2^256. Am i missing something.
Thanks.
Hey! Really appreciate you picking up this issue!
I'll have to double check on the edge case front, ill follow up if there are any to be aware of, however i can answet the second part; public inputs although bytes32, are checked to be less than p (254 bits) on line 586
each element within the proof is forced to be mod q ( for elliptic curve points ) see an example here: https://github.com/AztecProtocol/aztec-packages/blob/53eb54fb3416711dbc411e6037bc2da18d523cc3/barretenberg/sol/src/ultra/BaseUltraVerifier.sol#L331
or p ( for points in the scalar field ) see here: https://github.com/AztecProtocol/aztec-packages/blob/53eb54fb3416711dbc411e6037bc2da18d523cc3/barretenberg/sol/src/ultra/BaseUltraVerifier.sol#L360
for the non public inputs the rationale being that if they are greater than the modulus, the rest of the verifier will fail ( so we just force them to be in range).
Hey thanks for your response. It makes sense.
Hey I made some changes about addmod
calls. Most of the tests executes correctly. There is approximately ~1300 gas saving.
> sudo forge test --no-match-contract TestBase
Running 2 tests for test/ultra/Add2.t.sol:Add2UltraTest
[PASS] testFuzzProof(uint16,uint16) (runs: 1000, μ: 447002, ~: 447986)
[PASS] testValidProof() (gas: 434301)
Test result: ok. 2 passed; 0 failed; 0 skipped; finished in 94.19ms
Running 2 tests for test/ultra/Blake.t.sol:BlakeUltraTest
[PASS] testFuzzProof(uint256,uint256,uint256,uint256) (runs: 1, μ: 459481, ~: 459481)
[PASS] testValidProof() (gas: 440644)
Test result: ok. 2 passed; 0 failed; 0 skipped; finished in 3.22s
2023-12-13T10:57:26.633033Z ERROR cheatcodes: non-empty stderr input=["./scripts/run_fuzzer.sh", "ultra", "recursive", "0x1668,0x1687,0x2cef"] stderr="checked circuit before add_recursive_proof\n"
2023-12-13T10:57:26.636836Z ERROR cheatcodes: non-empty stderr input=["./scripts/run_fuzzer.sh", "ultra", "recursive", "0x05,0x0a,0x0f"] stderr="checked circuit before add_recursive_proof\n"
Running 2 tests for test/ultra/ECDSA.t.sol:EcdsaUltraTest
[PASS] testFuzzProof() (gas: 456285)
[PASS] testValidProof() (gas: 451425)
Test result: ok. 2 passed; 0 failed; 0 skipped; finished in 16.30s
Running 2 tests for test/ultra/Recursive.t.sol:RecursiveUltraTest
[PASS] testFuzzProof(uint16,uint16) (runs: 1, μ: 472207, ~: 472207)
[PASS] testValidProof() (gas: 458521)
Test result: ok. 2 passed; 0 failed; 0 skipped; finished in 16.30s
As you can see Recursive test is giving 2 errors before running correctly. It also same without any changes.
Is it normal and is there anything i can do about this problem?
ah very nice work! These are just debug outputs to std err, and are nothing to worry about!
I opened a PR with necessary changes. After removing duplicate mload
calls gas usage have increased. At least according to forge test
.
I was running tests to make sure everything is working correctly. But i received PROOF_FAILURE
error.
Running 1 test for test/ultra/Add2.t.sol:Add2UltraTest
[FAIL. Reason: PROOF_FAILURE(); counterexample: calldata=0x03911ac500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001f55 args=[0, 8021]] testFuzzProof(uint16,uint16) (runs: 8607, μ: 446894, ~: 448005)
Test result: FAILED. 0 passed; 1 failed; 0 skipped; finished in 430.98s
How can i reproduce the error with same inputs. I tried to hard code in contract. But it didn't work.
function testFuzzProof(uint16 input1, uint16 input2) public {
uint256[] memory inputs = new uint256[](3);
inputs[0] = uint256(0);
inputs[1] = uint256(8021);
inputs[2] = inputs[0] + inputs[1];
bytes memory proofData = fuzzer.with_inputs(inputs).generate_proof();
(bytes32[] memory publicInputs, bytes memory proof) = splitProof(proofData, PUBLIC_INPUT_COUNT);
assertTrue(verifier.verify(proof, publicInputs), "The proof is not valid");
}
The failure depends on both the inputs and the proof, so if you are rerunning it, it could simply be the proof that differs from the old one making it pass the case it hit earlier.
How can i also print Proof on error? It hard to encounter with this error on random testing. I should reproduce it.
I fixed the problem and updated the PR.
Much of the verification field arithmetic in BaseUltraVerifier.sol can be optimised.
There is currently a lot of duplication of MLOAD operations, we did this so that the code is straightforward to read and reason about, but it is more expensive.
We also have redundant uses of
addmod
. The BN254 field size is <2^254, meaning that we can calladd
up to four times before we need to reduce modulop
. This could save some more gas.Overall gas savings would be very small, ~2,000 tops. Not worth prioritising but could be good for a newcomer who knows Yul and wants to make a contribution to the codebase.