Update memory locations in verifiers to save gas

[qpzm]

participants: @qpzm, @rkdud007

Description

Verifier contracts specify memory addresses to load constants from the trusted setup.
It starts from 0x220 in GrandSumVerifier and from \0x200 in InclusionVerifier.
However, it can start from 0x180.

POC

I installed foundry to see memory and added two tests.
https://github.com/qpzm/summa-solvency/blob/v2-fix-verifier-memory/contracts/test/GrandSumVerifier.t.sol
https://github.com/qpzm/summa-solvency/blob/v2-fix-verifier-memory/contracts/test/InclusionVerifier.t.sol

Run forge test --debug "test_verify_grandsum_proof" and you can see memory from 0x000 to 0x180 is used in function parameters to calculate pairing. It is the blue part.

I changed the memory location constants to start from 0x180 and compared the test results.

GrandSumVerifier

15 gas saved.

before

$ forge test --match-test test_verify_grandsum_proof --gas-report

Ran 1 test for test/GrandSumVerifier.t.sol:GrandSumVerifierTest
[PASS] test_verify_grandsum_proof() (gas: 285231)
Suite result: ok. 1 passed; 0 failed; 0 skipped; finished in 13.47ms (8.14ms CPU time)
| src/GrandSumVerifier.sol:GrandSumVerifier contract |                 |        |        |        |         |
|----------------------------------------------------|-----------------|--------|--------|--------|---------|
| Deployment Cost                                    | Deployment Size |        |        |        |         |
| 277055                                             | 1068            |        |        |        |         |
| Function Name                                      | min             | avg    | median | max    | # calls |
| verifyProof                                        | 271155          | 271155 | 271155 | 271155 | 1       |

Memory expansion: 960 bytes

after

| src/GrandSumVerifier.sol:GrandSumVerifier contract |                 |        |        |        |         |
|----------------------------------------------------|-----------------|--------|--------|--------|---------|
| Deployment Cost                                    | Deployment Size |        |        |        |         |
| 277043                                             | 1068            |        |        |        |         |
| Function Name                                      | min             | avg    | median | max    | # calls |
| verifyProof                                        | 271140          | 271140 | 271140 | 271140 | 1       |

Memory expansion: 800 bytes

InclusionVerifier

12 gas saved.

before

$ forge test --match-test test_verify_inclusion_proof --gas-report

[PASS] test_verify_inclusion_proof() (gas: 384077)
Suite result: ok. 1 passed; 0 failed; 0 skipped; finished in 15.34ms (10.88ms CPU time)
| src/InclusionVerifier.sol:InclusionVerifier contract |                 |        |        |        |         |
|------------------------------------------------------|-----------------|--------|--------|--------|---------|
| Deployment Cost                                      | Deployment Size |        |        |        |         |
| 284813                                               | 1104            |        |        |        |         |
| Function Name                                        | min             | avg    | median | max    | # calls |
| verifyProof                                          | 365492          | 365492 | 365492 | 365492 | 1       |

Memory expansion: 896 bytes
(The source view of foundry debugger is unreliable)

after

| src/InclusionVerifier.sol:InclusionVerifier contract |                 |        |        |        |         |
|------------------------------------------------------|-----------------|--------|--------|--------|---------|
| Deployment Cost                                      | Deployment Size |        |        |        |         |
| 284849                                               | 1104            |        |        |        |         |
| Function Name                                        | min             | avg    | median | max    | # calls |
| verifyProof                                          | 365480          | 365480 | 365480 | 365480 | 1       |

Memory expansion: 768 bytes

Recommendation

The maximum memory size used in both verifiers is 0x180, so I recommend to save constants from memory 0x180.
The saved memory is 160 and 128 bytes respectively.

The gas cost for memory is increasing in a quadratic way.

• memory_size_word = (memory_byte_size + 31) / 32
• gas_cost = (new_mem_size_words ^ 2 // 512) + (3 * new_mem_size_words)

Reference: https://www.evm.codes/about#memoryexpansion

Therefore if we reduce 64 memory bytes, we can make new_mem_size_words ^ 2 // 512 in memory gas cost to 0.
I will further think about the way.

1. GrandSumVerifier https://github.com/summa-dev/summa-solvency/blob/fec83a747ead213261aecfaf4a01b43fff9731ee/contracts/src/GrandSumVerifier.sol#L11-L24

    // The memory location starts at 0x180 due to the maximum operation on the ec_pairing function being 0x180, marking the maximum memory location used
    uint256 internal constant             N_INV_MPTR = 0x180;
    uint256 internal constant             LHS_X_MPTR = 0x1a0;
    uint256 internal constant             LHS_Y_MPTR = 0x1c0;
    uint256 internal constant              G1_X_MPTR = 0x1e0;
    uint256 internal constant              G1_Y_MPTR = 0x200;
    uint256 internal constant            G2_X_1_MPTR = 0x220;
    uint256 internal constant            G2_X_2_MPTR = 0x240;
    uint256 internal constant            G2_Y_1_MPTR = 0x260;
    uint256 internal constant            G2_Y_2_MPTR = 0x280;
    uint256 internal constant      NEG_S_G2_X_1_MPTR = 0x2a0;
    uint256 internal constant      NEG_S_G2_X_2_MPTR = 0x2c0;
    uint256 internal constant      NEG_S_G2_Y_1_MPTR = 0x2e0;
    uint256 internal constant      NEG_S_G2_Y_2_MPTR = 0x300;

2. InclusionVerifier https://github.com/summa-dev/summa-solvency/blob/fec83a747ead213261aecfaf4a01b43fff9731ee/contracts/src/InclusionVerifier.sol#L10-L22

    // The memory location starts at 0x180 due to the maximum operation on the ec_pairing function being 0x180.
    uint256 internal constant             LHS_X_MPTR = 0x180;
    uint256 internal constant             LHS_Y_MPTR = 0x1a0;
    uint256 internal constant              G1_X_MPTR = 0x1c0;
    uint256 internal constant              G1_Y_MPTR = 0x1e0;
    uint256 internal constant            G2_X_1_MPTR = 0x200;
    uint256 internal constant            G2_X_2_MPTR = 0x220;
    uint256 internal constant            G2_Y_1_MPTR = 0x240;
    uint256 internal constant            G2_Y_2_MPTR = 0x260;
    uint256 internal constant      NEG_S_G2_X_1_MPTR = 0x280;
    uint256 internal constant      NEG_S_G2_X_2_MPTR = 0x2a0;
    uint256 internal constant      NEG_S_G2_Y_1_MPTR = 0x2c0;
    uint256 internal constant      NEG_S_G2_Y_2_MPTR = 0x2e0;