Gas cost reduction

[storojs72]

This is the meta-issue, dedicated specifically to reducing the gas cost of our e2e verification.

So far we have two contracts based on a different curve cycle:

• Pasta-based contract (https://github.com/lurk-lab/solidity-verifier/blob/grumpkin/src/NovaVerifierContractPasta.sol);
• Grumping-based contract (https://github.com/lurk-lab/solidity-verifier/blob/grumpkin/src/NovaVerifierContractGrumpkin.sol).

Below is basic estimations of gas cost for each contract (a0ed4b7) using cast estimate utility:

Pasta contract:

% cast estimate 0x8198f5d8F8CfFE8f9C413d98a0A55aEB8ab9FbB7 "verify(uint32,uint256[],uint256[],bool)(bool)" "3" "[1]" "[0]" "true" --rpc-url http://127.0.0.1:8545
224028756

Grumpkin contract:

% cast estimate 0xE6E340D132b5f46d1e472DebcD681B2aBc16e57E "verify(uint32,uint256[],uint256[],bool)(bool)" "3" "[1]" "[0]" "false" --rpc-url http://127.0.0.1:8545
259058951

Important note: these estimations DO NOT include final step of verification (IPA / Zeromorph).

While our internal discussions, @johnchandlerburnham mentioned that the desired gas cost of the verifier should not exceed 500k of gas, so we need some strategy for gas cost reduction.

Here is a short-term roadmap for this development direction:

1. The first obvious step is estimating the gas cost using some alternative tools. Having 2-3 estimations produced by different independent tools should give us some average point, that we can enforce it by CI and prevent committing any code that increases this point.

2. We need to have more fine-grained estimations of every sequential step of e2e verification and gas cost for every building block execution. Ideally we should come up to understanding of the cost of every primitive operation (addition, multiplication, points addition, negation, etc.), then the cost of every building block can be expressed as a number of primitive operations multiplied on the cost of one. And, finally, cost of every sequential step of e2e verification can be expressed in terms of building blocks involved. For now we have 7 sequential steps in our flow, so tentatively this can visualised as following:

Every contract consists from set of steps, where each step has its own cost:

Steps	Total Cost
Step 1	X
Step 2	X
Step 3	X
Step 4	X
Step 5	X
Step 6	X
Step 7	X
. . .
Step N (Zeromorph)	X

Every single step consist from set of operations which include either building blocks or more primitive operations. So we should 1 following table for each step:

Operation	Amount	Cost	Total cost
1) KeccakTranscript	5	?	5 * ?
2) Sumcheck	2	?	2 * ?
3) EqPolynomial	2	?	2 * ?
...

And finally every building block always consists from primitive operations. So we should have 1 following table for each building block:

Primitive operation	Amount	Cost	Total cost
Multiplication	200	?	5 * ?
Addition	300	?	2 * ?
Negation	10	?	2 * ?
...

Once we build mentioned tables, we will have clear picture - what is most / less expensive step / building block / primitive operation and we can effectively split and prioritise the optimisation of this or that part of the codebase.

3. Apply following possible engineering approaches to gas cost optimisations (this doesn't include algorithmic optimisations, where we change the logic of the verification), focusing on most expensive steps / building blocks:

• Remove redundant points uncompressions which are currently part of Rust reference implementation;
• Remove internal data conversions in Solidity;
• Exploring Weierstrudel / Huff (https://aztec-protocol.gitbook.io/aztec-documentation/huff/smart-contract-programming-in-huff/huffing-for-crypto-with-weierstrudel) and re-implementing some parts of contract or entirely;
• Ad-hoc experimenting with particular blocks of Solidity code - trying to reimplement it with smaller number of operations;
• Exclude poseidon constants from public parameters and use hardcoded ones (probably);

[storojs72]

In #31, there is a useful link to the gist, dedicated to gas cost reduction:

https://gist.github.com/grGred/9bab8b9bad0cd42fc23d4e31e7347144#for-loops-improvement

Duplicating here to keep it in mind

[0xScratch]

As this issue was kind of opened last week, Are these two contracts made gas redundant or not?

Although, I noticed that a lot of changes can be made inside the function verifyStep3PrecomputePrimary of NovaVerifierContractPasta.sol

[storojs72]

The primary goal was providing compatibility with reference Rust implementation of the verifier, so for now there are various options for gas cost optimisation indeed. The systematic approach would imply evaluating current libraries (building blocks of the end-to-end verification flow) and identify what parts of the code are most / least expensive in order to prioritise the optimisation efforts. At the same time, any contribution that reduces overall gas cast is welcomed!

[storojs72]

Current gas cost profile (for each individual step):

	Pasta	Grumpkin	Grumpkin (assembly)
Transcripts initialization	341,639	341,703	-
Step 1	1,016,352	1,016,500	146
Step 2	15,028,491	52,162,145	-
Step 3	63,218,699	67,437,489	-
Step 4	108,660	102,491	-
Step 5	103,402,132	97,268,900	-
Step 6	282,456	364,568	-
Step 7	40,351,919	40,377,190	-
Total	223,750,348	259,070,986	-
cast estimate	223,811,814	259,132,452	-

Contracts from this branch were used: https://github.com/lurk-lab/solidity-verifier/commits/gas-optimizing

[storojs72]

Poseidon hashing

In ba09754 there is an assembly implementation of Poseidon hashing. Comparing to previous non-assembly one, which takes 1,839,096 gas, assembly implementation takes 533,652 which is ~3.5x improvement. In current reference implementation of Nova e2e verification, Poseidon is used 3 times (twice in Step 2 and once in Step 3)

Note: one can further reduce gas cost if we avoid extracting limbs from r_U_primary / r_U_secondary (https://github.com/lurk-lab/Nova/blob/solidity-verifier-pp-spartan/src/r1cs.rs#L554). This potentially allows reducing Poseidon arity to U21.

[storojs72]

KeccakTranscript

In 9e9d7eb there is an assembly implementation of KeccakTranscript. Comparing to previous non-assembly implementation, which takes 443,399 gas, assembly implementation takes 19814 (for a 32 bytes input processing), which is ~22x improvement. In current reference implementation of Nova e2e verification, KeccakTranscript is being used more than 150 times while sumcheck verification of Spartan (more precise number can be obtained later, after implementing steps in assembly).

Note: one can further reduce gas cost if we use single keccak256 hashing inside the transcript and reduce the state to 32 bytes. In such case we will need to perform only single Montgomery reduction stage while squeezing.

[storojs72]

EqPolynomial (evaluate)

In ca4cfe2 there is an assembly implementation of EqPolynomial (evaluate). Comparing to previous non-assembly implementation, which takes 14968 gas, assembly implementation takes 5114 gas (for r / rx size = 17), which is ~3x improvement.

[storojs72]

IdentityPolynomial

In 024abb6 there is an assembly implementation of IdentityPolynomial building block. Comparing to previous non-assembly implementation, which takes 17092 gas, assembly implementation takes 2690 gas (for r with size = 17), which is ~6x improvement

[storojs72]

SparsePolynomial

In c7336f3 there is an assembly implementation of SparsePolynomial building block. Comparing to previous non-assembly implementation, which takes 27703 gas, assembly implementation takes 8784 gas (for num_vars = 14, poly_X size = 3), which is ~3x improvement

[storojs72]

PolyEvalInstance

In 1b8b38c there is an assembly implementation of PolyEvalInstance building block. Comparing to previous, Grumpkin-based non-assembly (or partially assembly) implementation, which takes 21,871,794 gas, assembly implementation takes 12,208,521 gas (for comm_vec / eval_vec with size = 9). Regarding comparison of Bn256-based implementations: non-assembly one, takes 121,422 gas, while pure assembly one takes 77,181. Scalar multiplication and points addition precompiles for BN256 do their job!

[storojs72]

Sumcheck verification

In eebac31 there is an assembly implementation of Sumcheck building block. Comparing to previous, non-assembly implementation, which takes 7,346,586 gas, assembly implementation takes 320,499 (for sumcheck proof that holds 17 polynomials, with 2 coefficients each), which is ~22x improvement (essentially due to utilising assembly KeccakTranscript).

[storojs72]

Step 1

In fd1989d there is an assembly implementation of Step1 library as a one-line assembly function. Comparing to previous non-assembly implementation, which takes 57448 gas, assembly implementation takes only 262 gas.

Step 2

In fd1989d there is an assembly implementation of Step2 as well. Comparing to previous non-assembly implementation, which takes 34,193,872 gas, assembly implementation takes 11,656,035 gas. Important note is that for a given specific proving example (that uses TrivialTestCircuit and CubicCircuit) where Poseidon hashing is invoked only 2 times (1 for primary check and 1 for secondary check), This number can be further reduced to actually pure hashing cost (with small overhead required for composing input), which is ~534,106. Rest of the gas currently is spent on: 1) constants preprocessing; 2) computing pValue (service value required for domain separation, which occupies 0th place at Poseidon's input); 3) decompressing points.

[storojs72]

https://github.com/harendra-shakya/solidity-gas-optimization

[wd021]

hey @storojs72, great work here! is this still being worked on? would love to be able to use this verifier on ethereum.

[storojs72]

Hi, @wd021!
This is not a priority for ACC at the moment, however I believe this work can be continued when we find customer interesting in landing Nova proofs on chain