# 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](https://eips.ethereum.org/EIPS/eip-4762#witness-gas-costs). 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](https://notes.ethereum.org/@vbuterin/verkle_tree_eip#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](#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**.