owned this note changed a year ago
Linked with GitHub

Block roots permanent cache (EIP-4788 plugin)

Preface

A buffer of beacon block roots proposed in EIP-4788 has a limited capacity. 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 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[1] 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:

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:

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 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 Nth root down the tree. The only thing we need is the index[2] 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[3].

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. 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. see curve-merkle-oracle ↩︎

  2. i.e. generalized index ↩︎

  3. see concat_generalized indices ↩︎

Select a repo