{
    "Function": "get",
    "File": "packages/protocol/contracts/thirdparty/optimism/trie/MerkleTrie.sol",
    "Parent Contracts": [],
    "High-Level Calls": [
        "Bytes",
        "RLPReader",
        "Bytes",
        "Bytes",
        "Bytes",
        "RLPReader",
        "Bytes",
        "Bytes"
    ],
    "Internal Calls": [
        "abi.encodePacked()",
        "abi.encodePacked()",
        "require(bool,string)",
        "_getNodeID",
        "_getSharedNibbleLength",
        "require(bool,string)",
        "revert(string)",
        "require(bool,string)",
        "revert(string)",
        "require(bool,string)",
        "_parseProof",
        "require(bool,string)",
        "require(bool,string)",
        "keccak256(bytes)",
        "require(bool,string)",
        "require(bool,string)",
        "keccak256(bytes)",
        "revert(string)",
        "require(bool,string)",
        "_getNodeID",
        "abi.encodePacked()",
        "_getNodePath",
        "require(bool,string)",
        "require(bool,string)"
    ],
    "Library Calls": [
        "equal",
        "slice",
        "toNibbles",
        "equal",
        "readBytes",
        "readBytes",
        "equal",
        "slice"
    ],
    "Low-Level Calls": [],
    "Code": "function get(\n        bytes memory _key,\n        bytes[] memory _proof,\n        bytes32 _root\n    )\n        internal\n        pure\n        returns (bytes memory value_)\n    {\n        require(_key.length > 0, \"MerkleTrie: empty key\");\n\n        TrieNode[] memory proof = _parseProof(_proof);\n        bytes memory key = Bytes.toNibbles(_key);\n        bytes memory currentNodeID = abi.encodePacked(_root);\n        uint256 currentKeyIndex = 0;\n\n        // Proof is top-down, so we start at the first element (root).\n        for (uint256 i = 0; i < proof.length; i++) {\n            TrieNode memory currentNode = proof[i];\n\n            // Key index should never exceed total key length or we'll be out of bounds.\n            require(currentKeyIndex <= key.length, \"MerkleTrie: key index exceeds total key length\");\n\n            if (currentKeyIndex == 0) {\n                // First proof element is always the root node.\n                require(\n                    Bytes.equal(abi.encodePacked(keccak256(currentNode.encoded)), currentNodeID),\n                    \"MerkleTrie: invalid root hash\"\n                );\n            } else if (currentNode.encoded.length >= 32) {\n                // Nodes 32 bytes or larger are hashed inside branch nodes.\n                require(\n                    Bytes.equal(abi.encodePacked(keccak256(currentNode.encoded)), currentNodeID),\n                    \"MerkleTrie: invalid large internal hash\"\n                );\n            } else {\n                // Nodes smaller than 32 bytes aren't hashed.\n                require(\n                    Bytes.equal(currentNode.encoded, currentNodeID),\n                    \"MerkleTrie: invalid internal node hash\"\n                );\n            }\n\n            if (currentNode.decoded.length == BRANCH_NODE_LENGTH) {\n                if (currentKeyIndex == key.length) {\n                    // Value is the last element of the decoded list (for branch nodes). There's\n                    // some ambiguity in the Merkle trie specification because bytes(0) is a\n                    // valid value to place into the trie, but for branch nodes bytes(0) can exist\n                    // even when the value wasn't explicitly placed there. Geth treats a value of\n                    // bytes(0) as \"key does not exist\" and so we do the same.\n                    value_ = RLPReader.readBytes(currentNode.decoded[TREE_RADIX]);\n                    require(\n                        value_.length > 0,\n                        \"MerkleTrie: value length must be greater than zero (branch)\"\n                    );\n\n                    // Extra proof elements are not allowed.\n                    require(\n                        i == proof.length - 1,\n                        \"MerkleTrie: value node must be last node in proof (branch)\"\n                    );\n\n                    return value_;\n                } else {\n                    // We're not at the end of the key yet.\n                    // Figure out what the next node ID should be and continue.\n                    uint8 branchKey = uint8(key[currentKeyIndex]);\n                    RLPReader.RLPItem memory nextNode = currentNode.decoded[branchKey];\n                    currentNodeID = _getNodeID(nextNode);\n                    currentKeyIndex += 1;\n                }\n            } else if (currentNode.decoded.length == LEAF_OR_EXTENSION_NODE_LENGTH) {\n                bytes memory path = _getNodePath(currentNode);\n                uint8 prefix = uint8(path[0]);\n                uint8 offset = 2 - (prefix % 2);\n                bytes memory pathRemainder = Bytes.slice(path, offset);\n                bytes memory keyRemainder = Bytes.slice(key, currentKeyIndex);\n                uint256 sharedNibbleLength = _getSharedNibbleLength(pathRemainder, keyRemainder);\n\n                // Whether this is a leaf node or an extension node, the path remainder MUST be a\n                // prefix of the key remainder (or be equal to the key remainder) or the proof is\n                // considered invalid.\n                require(\n                    pathRemainder.length == sharedNibbleLength,\n                    \"MerkleTrie: path remainder must share all nibbles with key\"\n                );\n\n                if (prefix == PREFIX_LEAF_EVEN || prefix == PREFIX_LEAF_ODD) {\n                    // Prefix of 2 or 3 means this is a leaf node. For the leaf node to be valid,\n                    // the key remainder must be exactly equal to the path remainder. We already\n                    // did the necessary byte comparison, so it's more efficient here to check that\n                    // the key remainder length equals the shared nibble length, which implies\n                    // equality with the path remainder (since we already did the same check with\n                    // the path remainder and the shared nibble length).\n                    require(\n                        keyRemainder.length == sharedNibbleLength,\n                        \"MerkleTrie: key remainder must be identical to path remainder\"\n                    );\n\n                    // Our Merkle Trie is designed specifically for the purposes of the Ethereum\n                    // state trie. Empty values are not allowed in the state trie, so we can safely\n                    // say that if the value is empty, the key should not exist and the proof is\n                    // invalid.\n                    value_ = RLPReader.readBytes(currentNode.decoded[1]);\n                    require(\n                        value_.length > 0,\n                        \"MerkleTrie: value length must be greater than zero (leaf)\"\n                    );\n\n                    // Extra proof elements are not allowed.\n                    require(\n                        i == proof.length - 1,\n                        \"MerkleTrie: value node must be last node in proof (leaf)\"\n                    );\n\n                    return value_;\n                } else if (prefix == PREFIX_EXTENSION_EVEN || prefix == PREFIX_EXTENSION_ODD) {\n                    // Prefix of 0 or 1 means this is an extension node. We move onto the next node\n                    // in the proof and increment the key index by the length of the path remainder\n                    // which is equal to the shared nibble length.\n                    currentNodeID = _getNodeID(currentNode.decoded[1]);\n                    currentKeyIndex += sharedNibbleLength;\n                } else {\n                    revert(\"MerkleTrie: received a node with an unknown prefix\");\n                }\n            } else {\n                revert(\"MerkleTrie: received an unparseable node\");\n            }\n        }\n\n        revert(\"MerkleTrie: ran out of proof elements\");\n    }"
}