# 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**.

This document contains notes about implementation optimizations for Verkle Tree proof generation and verification.

11/28/2023This document describes some high-level description of test-vectors to generate.

11/10/2023Last updated: 2023-10-30

11/6/2023This document aims to explore if using batch affine additions is faster than adding in projective form for VKT MSM.

8/20/2023
Published on ** HackMD**