owned this note
owned this note
Published
Linked with GitHub
## Block roots permanent cache (EIP-4788 plugin)
### Preface
A buffer of beacon block roots proposed in [EIP-4788](https://eips.ethereum.org/EIPS/eip-4788) has a [limited capacity](https://eips.ethereum.org/EIPS/eip-4788#size-of-ring-buffers). At the moment, it is designed to keep 8191 values. There are 7200 roots generated daily. It means there are about 27 hours to use a proof against any beacon block root. In some situations, it can be insufficient or might affect the reliability of the methods relying on beacon root usage. Hence, a separate solution is required to retrieve the required beacon block root in a trustless manner.
### Proposed solution
A storage cache with (timestamp, root) permanent "checkpoints" is proposed. The cache is populated by calling the [EIP-presented contract](https://eips.ethereum.org/EIPS/eip-4788#specification) via a permissionless method.
Additionally, anyone can bring proof of any arbitrary beacon block root against the closest available checkpoint in the cache, effectively adding a new checkpoint to the cache.
The contract interface may look like this:
```python
interface Cache {
# returns parent root for the block at timestamp `ts`
# in the same way the EIP-contract does it
def parent_root(ts: uint64) -> bytes32: view
# simply put, pull the parent_root for the given `ts`
# from the EIP-contract and save it to the storage
def add_root_from_EIP(ts: uint64 = block.timestamp) nonpayable
# add root for the block that is not available in the EIP-contract
# and wasn't saved in the storage by proving EIP-contract state
# for a block in the past
def add_root_by_buffer_storage_proof(
checkpoint_timestamp: uint64,
timestamp: uint64,
state_root: bytes32,
state_root_proof: list[bytes32],
eip_cache_account_proof: bytes,
timestamp_proof: bytes,
root_proof: bytes
): nonpayable
# add root for the block that is not available in the EIP-contract
# and wasn't saved in the storage by parent roots chain
def add_root_by_parent_root_proof(
checkpoint_timestamp: uint64,
header_root: bytes32,
header_root_proof: list[bytes32],
header_parent_root: bytes32,
header_parent_root_proof: list[bytes32],
header_slot: uint64,
header_slot_proof: list[bytes32],
depth: uint8 = 1 # blocks count
): nonpayable
}
```
#### Roots for blocks added after EIP-4788
For any block after the hardfork with EIP-4788 enabled it's possible to bring a Merkle Patricia Trie proof[^mpt-oracle] of the EIP buffer storage at the given block. To verify this proof, `state_root` of the block should be known, and it could be retrieved from the execution payload of the corresponding beacon block.
Currently, block structure looks like [this](https://github.com/prysmaticlabs/prysm/blob/33410a0ec1df85c97f1af936efdfa7ee4c282450/consensus-types/blocks/types.go):
```go
type BeaconBlock struct {
version int
slot primitives.Slot
proposerIndex primitives.ValidatorIndex
parentRoot [field_params.RootLength]byte // 32 bytes
stateRoot [field_params.RootLength]byte // 32 bytes
body *BeaconBlockBody
}
type BeaconBlockBody struct {
...
executionPayload interfaces.ExecutionData
...
}
```
, and `executionPayload` includes `state_root` [field](https://github.com/prysmaticlabs/prysm/blob/33410a0ec1df85c97f1af936efdfa7ee4c282450/api/client/builder/types.go#L571-L587):
```go
type ExecutionPayload struct {
...
StateRoot hexutil.Bytes `json:"state_root"`
...
}
```
It means, one can provide a proof of the `state_root` against a beacon block root of a "checkpoint". It effectively gives an ability to bring a proof for any timestamp existed in the EIP buffer.
Since the EIP buffer stores just a limited amount of roots, the storage trie of the buffer is compact. It means it's pretty cheap to prove any root within the buffer and fulfill the historical roots in hops of `HISTORY_BUFFER_LENGTH` length.
##### Pseudocode
```python
def add_root_by_buffer_storage_proof(
checkpoint_timestamp: uint64,
timestamp: uint64,
state_root: bytes32,
state_root_proof: list[bytes32],
eip_cache_account_proof: bytes,
timestamp_proof: bytes,
root_proof: bytes
): nonpayable
known_root = parent_roots[checkpoint_timestamp]
assert known_root, "checkpoint not found"
assert not parent_roots[timestamp], "the header parent root already stored"
assert validate_proof(
state_root_proof,
state_root,
known_root,
STATE_ROOT_GINDEX,
), "provided state_root is not valid"
storage_root = storage_root_from_account_proof(
keccak256(BEACON_ROOTS_ADDRESS),
eip_cache_account_proof,
state_root
)
assert storage_root
timestamp_idx = timestamp % HISTORY_BUFFER_LENGTH
root_idx = timestamp_idx + HISTORY_BUFFER_LENGTH
s_timestamp = slot_value_from_storage_proof(
keccak256(timestamp_idx),
timestamp_proof,
storage_root
)
assert s_timestamp == timestamp, "wrong timestamp given"
root = slot_value_from_storage_proof(
keccak256(root_idx),
root_proof,
storage_root
)
assert root
parent_roots[timestamp] = root
```
#### Roots for blocks before EIP-4788
Since there was no EIP buffer, an alternative approach should be used, like zk-STARK. However, the naive approach of using plain Merkle proofs described below is applicable despite the high cost of including aged roots.
Given that `parentRoot` in a beacon block is a merkle tree root of the [merkleized](https://github.com/ethereum/consensus-specs/blob/dev/ssz/simple-serialize.md#merkleization) `BeaconBlock` structure corresponding to the preceding block in the beacon chain.
Since a `parentRoot` field is a **bytes32** value, the result of merkleization of this field is the field value itself. It means two `BeaconBlock` Merkle trees corresponding to adjacent beacon blocks can be combined one on top of the other:
```
Given the chain of block with roots x, y, z such that: z -> y -> x
x
/\
. .
/\ /\
. . y . <- y in the `parentRoot` position of the block with root x
/\
. .
/\ /\
. . z . <- z in the `parentRoot` position of block with root y
/\
```
It means we can use this tree to prove the **N**th root down the tree. The only thing we need is the index[^1] of the root in the tree.
By knowing how many blocks down the tree located the root we want to prove to the contract, we can then determine the index[^2].
##### Pseudocode
The following pseudocode describes the idea of proving a `parentRoot` with the corresponding `slot` against a "checkpoint", i.e., a `parentRoot` known to the contract. Since it's required to check proofs for two fields of the `BeaconBlock` structure, the method below does it in two phases:
1. Given an existing **header** stored in the beacon chain before some known checkpoint, it checks the proof of this **header** root against the checkpoint.
2. It checks proof for `slot` and `parentRoot` of this **header** against the **header** root accepted previously.
```
`known_root`
/\
. .
~~~~ <- `depth` hops to the header collapsed
x <- `header_root`
/\
. .
/\ /\
`slot` `parentRoot`
```
```python
def add_root_by_parent_root_proof(
checkpoint_timestamp: uint64,
header_root: bytes32,
header_root_proof: list[bytes32],
header_parent_root: bytes32,
header_parent_root_proof: list[bytes32],
header_slot: uint64,
header_slot_proof: list[bytes32],
depth: uint8 = 1 # blocks count
):
assert depth, "zero depth means rewriting existing root with the same value"
known_root = parent_roots[checkpoint_timestamp]
assert known_root, "checkpoint not found"
timestamp = slot_to_timestamp(header_slot)
assert not parent_roots[timestamp], "the header parent root already stored"
# To simplify the flow, verify the header root first and then
# verify the header properties against this root.
g_index = concat_generalized_indices(
# depth - 1 because the checkpoint_timestamp stores root of the preceding block
*[PARENT_ROOT_GINDEX] * depth - 1
)
assert validate_proof(
header_root_proof,
header_root,
known_root,
g_index,
), "provided header's root is not valid"
assert validate_proof(
header_slot_proof
hash_tree_root(header_slot),
header_root,
SLOT_GINDEX,
), "slot value is not valid"
assert validate_proof(
header_parent_root_proof,
header_parent_root,
header_root,
PARENT_ROOT_GINDEX,
), "parent root is not valid"
parent_roots[timestamp] = header_parent_root
```
### Considerations
#### What to do with changing generalized indices?
Hard forks can alter the beacon block structure, causing changes in [generalized indices](https://github.com/ethereum/consensus-specs/blob/dev/ssz/merkle-proofs.md#generalized-merkle-tree-index). These generalized indices are not directly given by the network on the execution layer, so they need a reliable source of truth.
This becomes an issue when we attempt to provide proof for beacon blocks corresponding to different hard forks with altered indices.
To ensure that the stored roots in the contract match a single fork, the maximum acceptable timestamp may be set, via a permissioned method, to the timestamp of the next fork as soon as it becomes known. Alternatively if the execution number could return a number of the current hard fork, the contract could rely on this data instead. To preserve the contract state it's possible to delegate the global indices storage to a dedicated contract.
#### How much costs proving blocks roots before EIP-4788
We can roughly estimate gas usage for the proposed solution to store 24 hours old missing root:
```
7200 * (160 * 3 + 32 * 16) = 7'142'400
^___________________________________ numbers of entries for 24 hours
^______________________________ gas per sha256 operation
^________________________ tree depth for single root proof
^____________________ size of root in bytes
^_______________ gas per byte of calldata
```
Verifying of a proof has O(N) gas complexity and depends on the depth of the tree, hence the cost grows linearly.
[^1]: i.e. [generalized index](https://github.com/ethereum/consensus-specs/blob/dev/ssz/merkle-proofs.md#generalized-merkle-tree-index)
[^2]: see [concat_generalized indices](https://github.com/ethereum/consensus-specs/blob/dev/ssz/merkle-proofs.md#concat_generalized_indices)
[^mpt-oracle]: see [curve-merkle-oracle](https://github.com/lidofinance/curve-merkle-oracle)
Sign in with Wallet
