Block Access List

Simple Summary

A proposal to build a block's access_list and include its fingerprint AccessListRoot in the block header.

Abstract

EIP-2929/EIP-2930 centers around normalizing the (low) gas costs of data/storage accesses made by a transaction as well as providing for (and encouraging) a new transaction type format:

0x01 || rlp([chainId, nonce, gasPrice, gasLimit, to, value, data, access_list, yParity, senderR, senderS])

that makes upfront access_list declarations, where access_list is some [[{20 bytes}, [{32 bytes}...]]...] map of AccessedAddress=> AccessedStorageKeys.

The first accesses of these upfront declarations are charged at discounted price (roughly ~10%) and first accesses outside this list are charged higher price. Reason is upfront access declaration provides for a way to preload/optimize/batch loading these locations while executing the transaction. This inadvertently leads to generation of transaction access_list that has all (first) accesses (declared or not) made by a transaction. This proposal is to collate these transaction access_lists for all the transactions in a block access_list document and include its fingerprint in the block header.

Motivation

Motivation for collating the transaction access_lists for all the transactions in a block’s access_list is to have an access index of the block with following benefits:

1. Block execution/validation optimizations/parallelization/cache warm-up by enabling construction of a partial order for access and hence execution (hint: chains in this poset can be parallelized).
2. Enabling partial inspection and fetching/serving of a block data/state by light sync or fast sync protocols concerned with a subset of addresses.
3. Possible future extension of this list to serve as index for bundling, serving and fetching witness data for stateless protocols.

Specification

A block access_list represents:

Set [ 
    AccessedAddress, 
    List [AccessedStorageKeys] , 
    Set  [ AccessedInBlockTransactionNumber, List [ AccessedStorageKeys ]]  
]

A canonical construction of such an access_list is specified as below.

Canonical Block Access List

An access_list is defined to be comprised of many access_list_entry elements:

access_list   :=  [access_list_entry, ...]

An access_list_entry is a 3-tuple of:

• address
• sorted list of storage keys of the address accessed across the entire block
• sorted list of 2-tuples of:
  • transaction index in which the address or any of its storage keys were accessed
  • sorted list of storage keys which were accessed

access_list                 := [access_list_entry, ...]
access_list_entry           := [address, storage_keys, accesses_by_txn_index]
address                     := bytes20
accesses_by_txn_index       := [txn_index_and_keys, ...]
txn_index_and_keys          := [txn_index, storage_keys]
txn_index                   := uint64  # or uint256 or whatever
storage_keys                := [storage_key, ...]
storage_key                 := bytes32

Additional sorting rules for the above are that:

• access_list is sorted by the address
• storage_keys is sorted
• accesses_by_txn_index is sorted by txn_index

Additional validation rules for the above are that:

• Each unique address may only appear at most once in access_list
• Each storage_key may only appear at most once in storage_keys
• Each txn_index may only appear at most once in txn_index_and_keys

All sorting is in increasing order.

AccessListRoot

An AccessListRoot is a URN like encoding Hash/Commitment of the canonical access_list as well as the construction type ( sha256 ) and serialization type ( json ), i.e.

AccessListRoot := "urn:sha256:json:0x${ SHA256( access_list.toJSONString('utf8') ).toHexString() }"

where 0x${ SHA256 (...)...} is the SHA256 hashed 32 bytes hex string as indicated by leading 0x.

Additional Block Validation

Validating a new block requires an additional validation check that the block’s AccessListRoot matches the one generated by executing the block using the construction as defined by the AccessListRoot URN.

Rationale

Sorting of canonical access_list

It is specified to be sorted in lexicographic ordering or integer sorting wherever applicable and specified. Sorting with respect to access time was considered but didn't seem to provide any additional benefit at the cost of adding implementation complexity and bookkeeping.

AccessListRoot

AccessListRoot is generated to prevent any griefing attacks and hence will need to be included (and validated) in the block header. Even though AccessListRoot is currently specified to be a simple sha256 hash of the canonical access_list, it would be beneficial to consider other constructions

• a tree structure (merkle/verkle). It will be a bit more expensive but will enable partial downloading, inspection and validation of the access_list.
• a normal kate commitment can also be generated to enable this partial capability and is recommended as validating partial fetch of access list chunks would be very simple.

Also serialization of the access_list is currently specified as a normal JSON String dump and these parameters could vary from construction to construction, but for the sake of simplicity, it can always be sha256 hashed to get a consistent 32 bytes hex string root.

So this AccessListRoot could evolve to urn:merkle:ssz:... or to urn:kate:... or to any other scheme as per requirement. And the idea of having the AccessListRoot as URN like structure is to enable upgradation to these paths without affecting block structure.

Future extensions of access_list

We can extend the notion of a block’s access_list to include witnesses:

access_list := Set[ 
    Address,
    List [ AddressWitnesses ],
    Set  [ AccessedStorageKey, List [ StorageKeyWitnesses] ],        
    Set  [ AccessedInBlockTransactionNumber, List [ AccessedStorageKeys ] ]
]

and then get to define the a canonical specification for building the fingerprint. This will allow an incremental path to partial or full statelessness, where it would be easy to bundle/request witnesses using this access_list.

Backwards Compatibility

The extra block validation will only be mandatory post the block number this EIP comes into effect, but the clients can still provide a way to generate (and possibly store) this access list on request (via the JSON/RPC api). However this is optional and client dependent.

Security Considerations

There are no known security issues as a result of this change.

Copyright

Copyright and related rights waived via CC0.