Benchmark merkelization of inputs

[guidanoli]

Context

Currently, inputs are merkelized by Dave PRT contracts.
However, it could be merkelized by the InputBox contract instead.
Also, @edubart gave the idea of increasing the leaf size from 32 bytes to 128 bytes.
There is also the possibility for 4 KB leaves, which I will also test.
Let's see how the gas varies by payload length and leaf size.
Let us also compare with the current cost (just hashing the input).

Methodology

I've copied the Merkle-related contracts from Dave PRT, and made some adjustments.
Most notably, I had to adapt the code that calculates the hash of leaves, because the data being Merkelized is in memory, not calldata. This required some low-level EVM assembly to the rescue.

I then described the addition of inputs with payload of size $n$ as a Cannonfile, where $n$ is parameterized, so that it can be passed as a parameter to the cannon build command. I then ran the Cannonfile on a local devnet while varying $n$ from powers of 2, from 1 B to 128 KB.

Results

Below is the raw data. The branch in which each experiment was run is also specified below.

Payload size	Hash (main)	Merkelize (32-byte leaves, feature/merkelize-inputs-32-byte-leaves)	Merkelize (128-byte leaves, feature/merkelize-inputs-128-byte-leaves)	Merkelize (4 KB leaves, feature/merkelize-inputs-4kb-leaves)
1	55210	77167	63336	59685
2	55222	77179	63348	59697
4	55246	77203	63372	59721
8	55294	77251	63420	59769
16	55390	77347	63516	59865
32	55582	77539	63708	60057
64	56369	77128	64491	60841
128	57941	81386	64915	62410
256	61086	96553	75328	65485
512	67378	109946	80820	71761
1024	79963	146884	102193	84277
2048	105146	217590	141564	109335
4096	155560	355976	217221	162778
8192	256580	630062	365678	269612
16384	459388	1178245	661431	483752
32768	868076	2284284	1258058	915805
65536	1697740	4543369	2481545	1805345
131072	3406220	9256091	5056198	3693011

[guidanoli]

As discussed in this Discord thread, we will postpone any breaking changes to the machine state hash calculation (such as altering the data block size or the arity of the Merkle tree) until a later release. For v3, we decided to calculate the Merkle root of inputs on the InputBox contract using the same Merkle tree structure.