## 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:

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):

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):

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

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`

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)