HomeEIPs
EIPsEIP-3584
EIP-3584

Block Access List

StagnantStandards Track: Core
Created: 2021-05-22
Requires: EIP-2929, EIP-2930
Gajinder Singh (@g11in), Piper Merriam (@pipermerriam)
DiscussionsOriginal linkEdit
1 min read

EIP-3584 proposes the implementation of a Block Access List in Ethereum, which is an extension of the existing access list concept. The Block Access List allows for witnesses to be included in a block's access list, which can be used to build a fingerprint for partial or full statelessness. The proposal also includes a signature that signs over the transaction type and data to prevent the transaction from being re-interpreted as a different type.

The Block Access List is designed to maximize simplicity and avoid questions of duplication prevention. It does not lead to extra chain bloat in practice because gas is charged per item, and there is no gain in including a value in the access list twice. However, it does make applications that heavily rely on storage access less economically viable.

Access list generation is difficult in real-time situations, but the proposal includes a 10% initial discount to access lists, making it almost costless to not bother with access list generation and only make a simple transaction. The cost of accessing state outside the access list is expected to be ramped up in future hard forks as access list generation becomes more mature.

The Block Access List will increase the average block size, but the per-byte cost of access lists is much more expensive than calldata, making worst-case block size increase unlikely. Additionally, the ability to pre-fetch storage at the time of receiving a transaction and/or load storage in parallel upon receiving a block will partially compensate for the increase in average block size.

Video
Anyone may contribute to propose contents.
Go propose
Original

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 and related rights waived via CC0.

Further reading
Anyone may contribute to propose contents.
Go propose
Adopted by projects
Anyone may contribute to propose contents.
Go propose

Not miss a beat of EIPs' update?

Subscribe EIPs Fun to receive the latest updates of EIPs Good for Buidlers to follow up.

View all
Serve EIP builders, scale Ethereum.
Resources
GitHub
Supported by