Verkle Trees - Proof worst-case scenario

This document tries to show the maximum number of polynomial openings that a block proof might contain.

Rationale

The logic is the following:

1. Maximum gas per block is 30M (i.e: 15M*ELASTICITY_MULTIPLIER).
2. A freshly accessed LeafNode incurs in 1900 of gas cost.
3. Max storage-slot accesses (approx): 30M/1900 ~= 16k.
4. Assuming a worst-case scenario of storage-slot access being random, that would mean 16k uniquely accessed LeafNodes.
5. The number of openings that only involve the relevant LeafNodes is 5 openings:
   • 3 openings from the extension node (see illustration)
     • 1 for position 0 (i.e: 1)
     • 1 for stem
     • 1 for C1 or C2
   • 2 openings for the storage-slot value
     • 1 for value_lower
     • 1 for value_higher
6. This means that at leaf node "levels" we have up to 16k*5 ~= 80k openings.
7. We have to also count internal nodes openings, which are ~48k openings (approx):
   • Assume the Verkle Tree has a depth of 4 (maybe 5 would be more correct?)
   • Level 0: The root node is shared in all 16k leaf node paths, so all of them share a single opening. (See Comments section for a comment)
   • Levels 1, 2, and 3: Each leaf node would add three openings, one for each level. That means 3*16k ~= 48k openings.
8. The total number of openings is: 80k (point 6.) + 48k (point 7.) ~= 128k openings.

Comments

• At step 7. I mention the root node having to do 256 openings. Despite not changing much the big numbers, could the verifier recompute the commitment instead of verifying the proof?

Conclusion

In this worst-case scenario, we'd need to create a multiproof of 128k polynomial openings.