Optimise field arithmetic in BaseUltraVerifier.sol

[zac-williamson]

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 call add up to four times before we need to reduce modulo p. 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.

[emirsoyturk]

Hey I would like to help this issue if it is still available. @zac-williamson

[emirsoyturk]

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.

[Maddiaa0]

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

aztec-packages/barretenberg/sol/src/ultra/BaseUltraVerifier.sol

Line 586 in 53eb54f

valid_inputs := and(valid_inputs, lt(input, p_clone))

each element within the proof is forced to be mod q ( for elliptic curve points ) see an example here:

aztec-packages/barretenberg/sol/src/ultra/BaseUltraVerifier.sol

Line 331 in 53eb54f

mstore(W1_X_LOC, mod(calldataload(add(data_ptr, 0x20)), q))

or p ( for points in the scalar field ) see here:

aztec-packages/barretenberg/sol/src/ultra/BaseUltraVerifier.sol

Line 360 in 53eb54f

mstore(W1_EVAL_LOC, mod(calldataload(add(data_ptr, 0x2c0)), p))

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).

[emirsoyturk]

Hey thanks for your response. It makes sense.

[emirsoyturk]

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?

[Maddiaa0]

ah very nice work! These are just debug outputs to std err, and are nothing to worry about!

[emirsoyturk]

I opened a PR with necessary changes. After removing duplicate mload calls gas usage have increased. At least according to forge test.

[emirsoyturk]

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");
}

[LHerskind]

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.

[emirsoyturk]

How can i also print Proof on error? It hard to encounter with this error on random testing. I should reproduce it.

[emirsoyturk]

I fixed the problem and updated the PR.