MPT extension node turns into branch issue detected by light client

[miha-stopar]

What command(s) is the bug in?

No response

Describe the bug

Mainnet test with block 18363441 fails with

panic: runtime error: index out of range [35] with length 35

goroutine 17 [running, locked to thread]:
github.com/privacy-scaling-explorations/mpt-witness-generator/witness.getDriftedPosition({0x14005112ed0, 0x23, 0x2?}, 0x0)

The issue is there is an extension node
[226 29 160 217 96 198 67 216 20 103 173 8 242 218 197 154 41 240 104 151 164 226 76 167 89 156 221 241 114 184 233 63 208 17 10]
in the S proof, which gets replaced by a branch
[248 81 128 128 128 128 128 128 128 128 128 128 128 128 128 160 217 96 198 67 216 20 103 173 8 242 218 197 154 41 240 104 151 164 226 76 167 89 156 221 241 114 184 233 63 208 17 10 160 141 70 158 90 135 150 17 215 30 146 98 157 197 214 148 52 70 144 37 56 64 111 28 57 252 62 114 96 129 79 37 127 128 128]. This branch contains the above mentioned extension node and a leaf. The issue appears when getDriftedPosition tries to compute the drifted position out of the extension node.

[miha-stopar]

Once getDriftedPosition issue was resolved, a further one appeared with a "wrong" extension node.

The problem with the wrong extension node is that in this case we don’t get the underlying branch and leaf with GetProof/GetStorageProof. If we could get the underlying branch and any of its leaves, we could (with some slight additions) reuse the WrongGadget. However, to obtain one of the underlying leaves we would need to call PrefetchAccount/PrefetchStorage to get this leaf - but we don’t know its preimage (when we are querying for the key that does not exist, we get the extension node, to get the underlying nodes we need to modify the querying key accordingly, but this is not possible because we cannot know the hash preimage).

That means we cannot an underlying branch and a leaf in the proof. An alternative is check that the key RLC up until the end of the extension node is different from the RLC of the first num_nibbles key nibbles. For example:

Wrong extension node E is at path 2 2 2 and it has three nibbles 3 4 5 (in this case num_nibbles = 6).
We are querying the key 2 2 2 5 7 7 …. Such a leaf doesn’t exist, because at path 2 2 2 5 nothing exists and the extension node E is returned (found at 2 2 2).

The problem with comparing the RLC of 2 2 2 3 4 5 and 2 2 2 5 7 7 is that num_nibbles is dynamic (different from case to case). The solution might be to add split the querying key into two rows in the witness generator (two additional rows) - one row containing 2 2 2 3 4 5, the other row the remaining nibbles (compressed into bytes, which brings another problems though - even/oddness of nibbles).

In that case we can compute the RLC of the first num_nibbles using the first row and compare it to be different of E key_data RLC. And we need to ensure that the RLC of the both two rows is the same as the querying key RLC. Note that the “dynamic” problem of num_nibbles is solved this way, because using the RLP bytes (specifying the length) we can check that after some position there are only zeros in the row (using a fixed table and is_two_byte_lookup_enabled in mpt_circuit.rs).

We also need to ensure there RLP bytes correspond to the num_nibbles.