perama-v / archors Goto Github PK

Problem

When executing a block using proof-based state data:

• IF there is a key present (inclusion proof) that is deleted (converted to exclusion proof)
• AND the key belongs to a parent branch with exactly 2 children
• AND the sibling node is an extension
• AND the grandparent node is an extension
• THEN there is insufficient information to update the trie to get the new root.

Explanation

There appears to be insufficient information to construct post-block state root.

There are situations where a key is being removed from the trie during block execution. When a leaf node is
one of two children of a branch node, that branch node is now not required.

It can be seen that branch A would only have one child if the leaf were removed.

flowchart TD
    A[some traversal ...] --> B[extension 'abc'] --> F[branch A]
    F --item 1--> C[extension '2345'] --> D[branch B]
    F --item d--> E[leaf being deleted with path '...abcdef']

The updated trie needs:

• Branch A deleted
• Extension nodes combined

flowchart TD
    A[some traversal ...] --> B[extension 'abc12345'] --> D[branch B]

However, the trie is represented as a merkle multiproof, either for

• all the accounts accessed in a block or
• all the storage slots accessed for an account in a block

Nodes not accessed during block execution, such as branch A and extension '2345' are not present.
Here is what is present:

flowchart TD
    A[some traversal ...] --> B[extension 'abc'] --> F[branch A]
    F -.item 1.-> C[hash of extension '2345']
    F --item d--> E[leaf being deleted with path '...abcdef']

So it is not possible to know the contents of extension '2345' (perhaps it is '2', or '23456'). Hence
the two extensions cannot be combined. This prevents hashes from being known all the way back to the root.

Impact

One could execute a block without trusting a third party, but verification of the post-block state root would not be possible locally.

As blocks are deterministic this represents a loss of a nice sanity check for correct local block execution.

However the results of the EVM execution (full block trace) can still be obtained completely.

Description

To create the set of archival block state proofs both debug_traceTransaction and eth_getProof are required.

Discussion

Roles:

• debug_traceTransaction with prestateTracer applied to all transactions in a block allows the full set of required states to be computed. These are the "accessed states" and includes storage slots for each account, aggregated for the block.
• eth_getProof can be passed the "accessed states" for accounts individually. The result includes the account storage proofs that are used for that block. The proofs are then used to construct the final state proof for the block.

Tracking

• Erigon eth_getProof
  • 🚧 erigontech/erigon#1349
  • ✅ debug_traceTransaction with prestateTracer

The EVM has access to the blockhash of the prior 256 blocks.

Need to handle how the tracing works when thus opcode is encountered. Options:

• include accessed blockhash headers in proof. The recipient already must have a header accumulator/oracle to verify the proof.
• make the evm pause and await the blockhash, which could be fetched from a peer.

There is a bug in the state transition or state root update logic. Applying the block 17190873 transactions and updating the multiproof results in a hash that does not match that present in the header for 17190873.

State access count is likely linearly related to gas used. This metric would give more extrapolatable findings

archors describes an architecture where an archive node is distributed at the block level (bundles containing all the state required to execute the bloc, and accompanying proofs).

A user can just download the blocks that are relevant to them.

How do they know which blocks? This is a discovery problem cleverly solved by the UnchainedIndex https://github.com/TrueBlocks/trueblocks-core:

chifra list my_address

Related, if the discovery problem is solved by a JSON-RPC method on archive nodes themselves (https://github.com/perama-v/eth_getAddressAppearances), then whatever distribution system
for distributing the archive node data (e.g., portal network), may also want to include a native version of this index of address appearances (holding a portion of the index, as determined by their node_id).

This should be included in docs

At present the state data (proof) is for the block prior to the current block. The block transactions are applied to this state. That
results in the state root in the current block.

The proof from the prior block can be updated by tracking the state changes after each transaction. After the last
transaction the state root can be checked to match that which is in the header.