Context

This data is gathered replaying ~200k historical blocks around the Shanghai fork. While they do not give a perfect view of how execution will behave once EIP-4762 is active, it still gives a good indication of what to expect, and how the spec should evolve.

This document is still work in progress, and will be updated as more data is collected and processed.

Witnesses

Size

Research has been conducted, in order to determine the best structure for a witness. We tried three methods:

• The first one, as specified in the current version of the consensus spec, referred to as type 0. This approach uses the SSZ type Optional[T] , that is yet to be officially included in the spec.
• A first variation of the spec, in which prestate values are grouped together in their own list, and poststate values are grouped in their own list as well. This is referred to as type 1.

class SuffixStateDiffs(Container):
    suffixes: bytes
    # None means not currently present
    current_values: List[bytes]
    # None means value not updated
    new_values:     List[bytes]

• A second variation of the spec, in which updates, insertions and reads are grouped in their own separate lists. The suffixes for each of these lists are also grouped as their own byte lists. This is referred to as type 2.

class SuffixStateDiffs(Container):
    updated_suffixes: bytes
    updated_currents: List[Bytes32]
    updated_news: List[Bytes32]

    inserted_suffixes: bytes
    inserted_news: List[Bytes32]

    read_suffixes: bytes
    read_currents: List[Bytes32]

    missing_suffixes: bytes

• A final variation, where update, reads, inserts and proof-of-absences are grouped, along with their suffixes, into their own lists. This is referred to as type 3.

class UpdateDiff(Container):
    suffix: byte
    current: Bytes32
    new: Bytes32

class ReadDiff(Container):
    suffix: byte
    current: Bytes32

class InsertDiff(Container):
    suffix: byte
    new: Bytes32

class MissingDiff(Container):
    suffix byte

class StemStateDiff(Container):
    stem: Bytes31

    updates: List[UpdateDiff]
    reads: List[ReadStateDiff]
    insert: List[InsertStateDiff]
    # TODO: check if this encodes as well as bytes
    missing: List[MissingStateDiff]

Here are our findings after replaying data for 200k blocks:

One can see that the spec is much less efficient than the other types. This is due to the inefficiency of storing Optional[T]. As a result, we didn’t include this method in the rest of the analysis.

When only considering the post-transition witnesses, this is what is found:

The maximum and minimum sizes for each type, are summarized in the following table:

While type 2 and type 3 are quite close, one can see that type 3 has better average and minimum sizes.

Witness size breakdown (type 3)

Replaying past blocks, we generated the witnesses and could provide the following size breakdown for type 3 witnesses. This is averaged over ~134k blocks, as the conversion blocks were skipped.

Takeaways

The key takeaways are:

• Type 3 witnesses offer a great compression
• post-values are of dubious use, and can not be verified without block execution. Although they don’t take much space on average, we suggest dropping them from the witness.

Database

WIP

Looking at a fully converted database (conversion + ~134k blocks replayed), we found that the leaf depths could be broken into :

Gas usage

WIP

Execution performance

WIP

Impact of tree key hashing

In order to estimate the performance impact of Pedersen key hashing, this is a comparison of how long it takes to replay 200k blocks using Pedersen hashes, vs. sha256:

At the end of the sha256 run, so >200k blocks later, the chain was 75072 blocks ahead. This represents a loss of 3 hours per day against sha256. That’s >12% faster.

Coupled to the fact that Pedersen hashes aren’t quantum resistant, it seems like a good idea to reconsider using Pedersen hashes to compute trees.