fix: extension trie node incorrectly ignored

Fixes #2.

Fixes an issue causing block state root mismatches. It turns out to be a rather common case, but most of the time the code panics on the unimplemented Merkle Patricia Trie code path way before a state root can be calculated, and therefore hiding the issue.

The issue

The current code fails with a state root mismatch error when running against certain blocks. A quick reproducer is the Optimism block 122853548:

RUST_LOG=info cargo run --bin rsp-host --release -- --block-number 122853548 --rpc-url <OPTIMISM_MAINNET_RPC_URL>

which fails with:

2024-08-12T06:38:41.224368Z  INFO rsp_host_executor: validating the block post execution
2024-08-12T06:38:41.224517Z  INFO rsp_host_executor: accumulating the logs bloom
2024-08-12T06:38:45.829783Z  INFO rsp_host_executor: verifying the state root
thread 'main' panicked at bin/host/src/main.rs:37:56:
failed to execute host: mismatched state root

This clearly has nothing to do with the unimplemented Merkle Patricia Trie code path as the application fails without hitting that.

The cause

After investigating the block triggering the issue, it's discovered that a particular segment of the trie is causing the error.

Before the block is executed, the account 0x416b433906b1B72FA758e166e239c43d68dC6F29 has a storage trie where the key path 9af4 is an extension node with an extension path of a single nibble of 3:

Prefix: 9af4

Trie 0x91cf159a69e5a61f4d791695d2364d43e662a28fb122f0a7d921c63e3d2d12e2

e2 => list len = 34
   13 => odd extension
   a0 => child hash
      f92634945114f8ac524bf09a56f74223a63bb8df55defd2734b59fdce4d70248

Its child node 0xf92634945114f8ac524bf09a56f74223a63bb8df55defd2734b59fdce4d70248 is a branch node containing 2 children:

Prefix: 9af43

Trie 0xf92634945114f8ac524bf09a56f74223a63bb8df55defd2734b59fdce4d70248

f8 => list len of len = 1
   51 => list len = 81
      a0 => branch hash
         3db3f8341d2524837bd538f16151b676e64ff51ebb727e9eb736d646cd803f97
      80
      80
      80
      80
      a0 => branch hash
         e961bcb48f8488b8607f59cb1c99dd246e3a910e5908adb12a6818565ccbc506
      80
      80
      80
      80
      80
      80
      80
      80
      80
      80
      80

The block 122853548 happens to insert a new storage slot for the contract at 0x000eac6c145f53034b578395b3a255d6857f4f0080ca09ab51b48a2c6cf32ab0, which has a trie key path of 0x9af4e02f635a28804513a73b51d5730e278082b0a3f822da05532af776cf4429. Note how this new node shares the prefix of the previous extension node of 9af4, but not the extension nibble of 3 itself (the new leaf node has e next in its path instead). This should normally turn the extension node into a branch node to host 2 immediate children.

Instead, the locally built trie contains this node:

Prefix: 9af

Trie 0x0584025a8aa202ccf5cad00ea2ff83fe637cc9887109f61a0da230d1e90d709a

f8 => list len of len = 1
   d1 => list len = 209
      80
      a0 => branch hash
         9c0f4a5cfaddae7a376075bcd7591178bbe308460bdc3f2a4114bd2fec8d8d81
      80
      80
      a0 => branch hash
         2c8b6573848863843451f7c74c13a6064b95db0cf922ea88796439a98f11d703
      80
      80
      80
      80
      80
      a0 => branch hash
         82c2b22d9732231cad5eca1e32d0f1ec7cddd4d341be3e812b93402d10311e60
      a0 => branch hash
         76a7b66d9e1811ea4a70788697ed821fbdde0fb46b4fb1bd88fad0c57e711a9d
      a0 => branch hash
         ddb29810ee7f703b68f974ecbadbceb07d3ea8b42d1aba8f2913aadd26228a0f
      80
      a0 => branch hash
         78804494676510d69983bdb93ad4b61bcbab1cf9def243d6d180e1465a508cdd
      80
      80

where the child at index 4 is the new node:

Prefix: 9af4

Trie 0x2c8b6573848863843451f7c74c13a6064b95db0cf922ea88796439a98f11d703

f8 => list len of len = 1
   3b => list len = 59
      9f => string len = 31
         20e02f635a28804513a73b51d5730e278082b0a3f822da05532af776cf4429 => even leaf
      9a => string len = 26
         99 => string len = 25
            18981f7bd1a2d5499104375d04375c00000000000000000014

Clearly the extension node is missing.

This is caused by these lines:

https://github.com/succinctlabs/rsp/blob/a171bfbe9cf6a3cb6466f95289ed11ff499bd402/crates/mpt/src/lib.rs#L127-L129

Here the program naively expects that whenever we encounter an extension node in a Merkle proof, the next node in the proof will "accept" the extension and get added to the trie. However, this is not true when the extension node itself is the last item in the proof, which can happen when proving the absence of a node.

Therefore, this bug is triggered only when:

setting a storage slot from zero to non-zero; and
there are at least 2 existing storage slots that share a key path prefix with the new node; and
all these existing slots share a longer prefix than is shared with the new node.

This does not always happen but is not uncommon.

The fix

The fix is simple. We simply check whether there's another item in the Merlke proof. If there's none, the extension node itself should be added to the trie.

succinctlabs / rsp