search

EspressoSystems / espresso-sequencer

93 stars 63 forks source link

I01: Inefficient memory allocation in transcript generation logic #1738

Closed philippecamacho closed 4 weeks ago

philippecamacho commented 1 month ago

Affected Code: • PlonkVerifier.sol (line 173) • Transcript.sol (line 81)

Summary: The current implementation of the function _computeChallenges in PlonkVerifier.sol and appendVkAndPubInput in Transcript.sol inefficiently manages memory by repeatedly calling abi.encodePacked to concatenate elements to the transcript. Each call to abi.encodePacked results in a new memory allocation and copying of the existing transcript, leading to excessive gas consumption.

Suggestion: Create a struct containing all the fields that are appended to the transcript. Hash the parts of the struct using low-level memory access to generate the relevant challenges. To allow for tight packing of the transcript one can also use a bytes array instead of struct and low-level memory writes to populate the array.

alxiong commented 1 month ago

Completely agree!

Do they already have a PR on this? @philippecamacho

philippecamacho commented 1 month ago

Completely agree!

Do they already have a PR on this? @philippecamacho

Don't think so. The only PR from Common Prefix so far is https://github.com/EspressoSystems/espresso-sequencer/pull/1716

philippecamacho commented 1 month ago

ESTIMATION: HIGH

alxiong commented 1 month ago

I'm working on this, I'm gonna completely write the entire _computeChallenges() using assembly, this should improve gas usage noticeably. Will try to submit a PR tmr (can't finish today)