Fixes a state root computation edge case that involves inserting a new trie node that happens to have an immediate lower neighbour whose value is being updated.
When proving the absence of a node (and hence an insertion), there are cases where instead of proving a dead end on the parent branch, a neighbour node is proven instead. This happens when the neighbour node shares the same extra prefix with the node being inserted. Consider this simple trie:
node path: 11a
node path: 2a
Before any insertion, the root node is a branch node with children at slot 1 and 2, both of which are leaf nodes.
Now, consider inserting 12b. In order to prove its previous absence, the proof would contain the root branch node and the preimage of 11a to show that while the slot 1 fits the new node, it actually points to the path of 11 instead of 12, and thus proving the absence of the new node.
When walking the proof for 12b, the current implementation always collects everything alongside the proof, including the 11a preimage that's included solely to prove the absence of 12b.
There's only one problem: the proof for 12b contains the old value of the 11a. If 11a itself is updated and its proof is walked before12b, then its updated value gets overwritten.
The fix is simple: when walking a proof and collecting neighbour nodes, do not overwrite if there's already a value set. It might have been set by a previous neighbour collection but that's fine as walking 11a always overwrites it.
A new test case has been added to accompany the fix. A real world Ethereum mainnet block affected is 20526020.
Fixes a state root computation edge case that involves inserting a new trie node that happens to have an immediate lower neighbour whose value is being updated.
When proving the absence of a node (and hence an insertion), there are cases where instead of proving a dead end on the parent branch, a neighbour node is proven instead. This happens when the neighbour node shares the same extra prefix with the node being inserted. Consider this simple trie:
11a2aBefore any insertion, the root node is a branch node with children at slot
1and2, both of which are leaf nodes.Now, consider inserting
12b. In order to prove its previous absence, the proof would contain the root branch node and the preimage of11ato show that while the slot1fits the new node, it actually points to the path of11instead of12, and thus proving the absence of the new node.When walking the proof for
12b, the current implementation always collects everything alongside the proof, including the11apreimage that's included solely to prove the absence of12b.There's only one problem: the proof for
12bcontains the old value of the11a. If11aitself is updated and its proof is walked before12b, then its updated value gets overwritten.The fix is simple: when walking a proof and collecting neighbour nodes, do not overwrite if there's already a value set. It might have been set by a previous neighbour collection but that's fine as walking
11aalways overwrites it.A new test case has been added to accompany the fix. A real world Ethereum mainnet block affected is
20526020.