mattsse
commented
1 year ago The returning account and storage proof array elements have a wrong RLP encoding which cannot be decoded.
can you be more specific here, please?
Closed Artifex1 closed 6 months ago
mattsse
commented
1 year ago The returning account and storage proof array elements have a wrong RLP encoding which cannot be decoded.
can you be more specific here, please?
Artifex1
commented
1 year ago Sure, consider I have a contract at address 0x5fbdb2315678afecb367f032d93f642f64180aa3 with storage value 0x042648680d4eb4bb47f2cd970fbd52a412a106e2ff3a9e67598084b67aead527 at slot 0x6d55970f1749d3181c34cda959776611ed73b92cf77e72b18a770442010e1b02 (among others). Then cast proof for that address and slot returns the following:
{
"address": "0x5fbdb2315678afecb367f032d93f642f64180aa3",
"balance": "0x0",
"codeHash": "0x0baf51d4b6b9c4c112fcdbbf0d258470e5e092f51ddd031716c5651f2bae526f",
"nonce": "0x1",
"storageHash": "0x4b49692943e98ccd66fe6576928535d984b973b085948d07012beb3491747609",
"accountProof": [
"0xfe33cb8023c0d400ea554e87fc49a073583c3e83ff51809dc81bdb915f238ae2eae2eae7807b511c8799e32a00808434087c343511dcd07849cbb5f45a4f275baab66133be80de95769e8293a11da5da78efc96028ffd48f94fdf20e6b41e464c61ced6d649580cdf571019f90d3c2d07736b8b40868a2f8b5e58d1093bec37b3351d4286abfae8072f49529c0f99a3d46e0a0dce3f3527c53a12c96bfcf30db993d18231e12069680792abc6dc5c7876958852dcdcecf5877b5799d474135a9ef08a2cf2a188592eb80fc1cf0b15da7e492537f17aa327f0a4092b1ed815fc4625ff86c8b1b3f5cd02780bcb3ddeda43386163fa796b29e7b02fb1fa1c38197531bcb1a1920fbd25f5883806d460e9154787237da8e007f64d5baca219f96e084f45a14c90b1ee7a5f08bde",
"0x4004e659e60b21cc961f64ad47f20523c1d329d4bbda245ef3940a76dc89d0911b1901f8440180a04b49692943e98ccd66fe6576928535d984b973b085948d07012beb3491747609a00baf51d4b6b9c4c112fcdbbf0d258470e5e092f51ddd031716c5651f2bae526f"
],
"storageProof": [
{
"key": "0x568bf21607c8e6fcea48c26dd9d42250efee29d2f85c09b63e529653b1409126",
"proof": [
"0xfeffff804ea62ea84aec7089a998fe199f8721dfd7ba46ef86bbfb940c9b07c5cfe73b1080d0d2b84e4aeb0ea91fd19acc9d28087a512986ff035aa2fd0b0c4d3d2149aed380428e975a5566e69b020f323e96ff72fbb63acffbb6ce7b3ec96d4f7bab764b818058bc3a3a352b9e193a9bf7b9f6b49cd133d2e9fc44c35e56701e851795776cdb8024dc38da9785c3d749f09e0ad46ca1128fc9ac00a22a923521abc5d362691cdb8028b8ba95dacf1621272f715449879712a2d212be2610de0f0ed79ada569337e58084bb145c5c3024950ce8c729fc0f67da16ac61dff191ca190277938f34f3e2ae80a4df1db1931f3aa807566a4b165e82991facd7b466705de30d4c87600973eb2d80b44672676a3ffe7b61fb902ada1f974c69bfd8c77d9d29d9bd172d19cb2ea0e480e77f6f83dc385ec641063f32553e2a5582ef7c584a79d00a3cd6793dbd77b4de808ff23df2cc8c00fa33dd1fe86ed8a840472bd2f298e7055e3bc93cfc73a33a0e804b7d837177ed80c88c9e0388a28e1be0909f1996ca59477d7b11a0a1a157c23f80bc482970edf4298c7d83ba750af1d06833dda0d5f67d99b2573ca67e1f46d3b5804855aaf27b80e322cbb1832fe45bec6ce3901b66b0df0674df2f00f989e1023380ed2db838f0f5858c320f4a40ad138fa50ed93e02495dfe9d39da81748811a73a801925779e85c71177c6255fd123a42ed9c32908bbe00df4d8417a361cd77c9658",
"0xfe7b8a803d7f81b6beeb519c5e49b824df238e55a0a321689f828c23b0794f15ae01de6280691c0f2b9f918dbc7a60b01a98f629d3e398383993a4b830f0b4cb08ea5438c9808c698f26c5352233b316324c60ff568c522d314a524a2919ae09433f0f16ea4280729984ee5d0a2f303c6896254b84d53e3165de2d9a76a45aae105d7e76a3030180d78ba8ea0eeb210de36dfcecdc150f6fd4bcf0a3a1ee7b422371e6dfb08402418073e4b3cd625130b87e58896ae0c82ecb01797c2ac118b96dc0949d66e416394980a850ca485780908d05af94f8e4ff5910278212c5d4e62656b314c38fc477938380cfa3deaf3c8eb5eca6a1a28157b9aeb2cdda4c86525028a27584a30ea0460434809e566d0e73028f40838805777c8fba3b1134f1f34e7da679dc5f318107330647",
"0xfe001180db41fa988afd65657783828581740e87c2578a016a14caae168f6fc0bda77d6480f29b490dde49949d5e9bfbed8654c8977457eee8135a757a17ec8e321d5daf88",
"0x3e0bf21607c8e6fcea48c26dd9d42250efee29d2f85c09b63e529653b140912684a0042648680d4eb4bb47f2cd970fbd52a412a106e2ff3a9e67598084b67aead527"
],
"value": "0x42648680d4eb4bb47f2cd970fbd52a412a106e2ff3a9e67598084b67aead527"
}
]
}However, the accountProof and storageProof[0].proof elements are not RLP decodable.
mattsse
commented
1 year ago tbh, I don't know, eth_getProof is one of the hardest and confusing endpoints
Arachnid
commented
1 year ago I've just encountered this myself. It'd be really good to see this addressed rather than put in the too-hard basket. Is there anything I can do to help it get fixed?
As a concrete example, here's a valid proof, generated by ganache, for a contract with value 0x2a in slot 1:
"storageProof": [
{
"key": "0x0000000000000000000000000000000000000000000000000000000000000001",
"proof": [
"0xf8718080a04fc5f13ab2f9ba0c2da88b0151ab0e7cf4d85d08cca45ccd923c6ab76323eb288080a01813db5734a0840cf6e5dac777dc05dcceefaffba841b82cd6fadc347be43a548080808080a0e4449cb51d628e6e071cbba31d760efcf09715ce230ac380c7a239722c0f22118080808080",
"0xe2a0310e2d527612073b26eecdfd717e6a320cf44b4afac2b0732d9fcbe2b7fa0cf62a"
],
"value": "0x2a"
}Here's the corresponding proof generated by Anvil, which should be identical:
"storageProof": [
{
"key": "0xb10e2d527612073b26eecdfd717e6a320cf44b4afac2b0732d9fcbe2b7fa0cf6",
"proof": [
"0xfe2408807eb8461ee885b7c27d3fa0581168a345f6d60500b5dba3a03f7fd7ae0465521a806a6ee3ad11fc804c3bfd7b7be5487aa016a84b8b37a1dcd7c03ba172c39a09fe803877ec5dc03be5250214e5047a8a967dc0e024bd967387b51799a5980a3ba7e8",
"0x40010e2d527612073b26eecdfd717e6a320cf44b4afac2b0732d9fcbe2b7fa0cf6042a"
],
"value": "0x2a"
}Note that the key is also incorrect, despite the argument being the same (0x...01) in both cases.
mattsse
commented
1 year ago could you please prepare a repro for this?
Arachnid
commented
1 year ago Sure! Here's a JS snippet; it requires ethers and solc:
const ethers = require('ethers');
const solc = require('solc');
const SecureTrie = require('merkle-patricia-tree').SecureTrie;
const rlp = require('rlp');
// Connect to local Ethereum node
const provider = new ethers.JsonRpcProvider('http://localhost:8545');
// Define the Solidity contract
const source = `
pragma solidity ^0.8.0;
contract SimpleStorage {
uint256 public storedData;
function set(uint256 x) public {
storedData = x;
}
}
`;
// Compile the contract
const input = {
language: 'Solidity',
sources: {
'SimpleStorage.sol': {
content: source,
},
},
settings: {
outputSelection: {
'*': {
'*': ['*'],
},
},
},
};
const compiledContract = JSON.parse(solc.compile(JSON.stringify(input)));
const { abi, evm } = compiledContract.contracts['SimpleStorage.sol'].SimpleStorage;
// Deploy the contract
const deploy = async () => {
const [deployer] = await provider.listAccounts();
const factory = new ethers.ContractFactory(abi, evm.bytecode.object, deployer);
const contract = await factory.deploy();
// Set the storage variable
const tx = await contract.set(42);
await tx.wait();
// Get the storage proof
const proof = await provider.send('eth_getProof', [
await contract.getAddress(),
["0x0000000000000000000000000000000000000000000000000000000000000000"],
'latest',
]);
console.log(proof);
// Verify the proof
const storageHash = Buffer.from(proof.storageHash.slice(2), 'hex');
const storageKey = Buffer.from(proof.storageProof[0].key.slice(2), 'hex');
const result = await SecureTrie.verifyProof(storageHash, storageKey, proof.storageProof[0].proof.map((x) => Buffer.from(x.slice(2), 'hex')));
if(ethers.toNumber(result) == ethers.toNumber(proof.storageProof[0].value)) {
console.log("Storage proof is valid");
} else {
console.log("Invalid storage proof");
}
};
deploy().catch(console.error);Output when run against Ganache:
{
address: '0xe78a0f7e598cc8b0bb87894b0f60dd2a88d6a8ab',
balance: '0x0',
codeHash: '0xc9629525f978277568df79838eda9d2d588380657c140f2ef7bdf04826c53f8e',
nonce: '0x1',
storageHash: '0x81d1fa699f807735499cf6f7df860797cf66f6a66b565cfcda3fae3521eb6861',
accountProof: [
'0xf901d1a0bddaa54ff11e3d79d1aa0f9df7ed9a8f9afbc0cdd35183106c0c3c377fd587cba0ab8cdb808c8303bb61fb48e276217be9770fa83ecf3f90f2234d558885f5abf180a0972d27603c1062c59a3025f1d72d11e69273ece67c55f78c232ca34595114670a0de26cb1b4fd99c4d3ed75d4a67931e3c252605c7d68e0148d5327f341bfd5283a06a4287465bb98d95816304fe3ea98301cd27eb85cd391c25e15812917c45b758a0c2c799b60a0cd6acd42c1015512872e86c186bcf196e85061e76842f3b7cf86080a02e0d86c3befd177f574a20ac63804532889077e955320c9361cd10b7cc6f5809a066cd3ba8af40fe37d4bfa45f61adb46466d589b337893028157f280ecc4d94f0a060ba1f8a43e38893005830b89ec3c4b560575461c3925d183e15aed75f8c6e8fa0bca2657fd15237f0fdc85c3c0739d8d7106530921b368ca73c0df81d51bcadf4a029087b3ba8c5129e161e2cb956640f4d8e31a35f3f133c19a1044993def98b61a06456f0a93d16a9f77ff0d31cf56ef090d81c2c56b12535a27c2c7c036dc8186da0976e998acbf25e2849e52d0733fdb0492be8ba3b527725bc1df98907ec765373a0144540d36e30b250d25bd5c34d819538742dc54c2017c4eb1fabb8e45f72759180',
'0xf869a03b2c95fd2a6e48d2dcb37be554d03b55e31ec582b450211db4e9c3883ffac678b846f8440180a081d1fa699f807735499cf6f7df860797cf66f6a66b565cfcda3fae3521eb6861a0c9629525f978277568df79838eda9d2d588380657c140f2ef7bdf04826c53f8e'
],
storageProof: [
{
key: '0x0000000000000000000000000000000000000000000000000000000000000000',
proof: [Array],
value: '0x2a'
}
]
}
Storage proof is validOutput when run against Anvil:
{
address: '0x9fe46736679d2d9a65f0992f2272de9f3c7fa6e0',
balance: '0x0',
codeHash: '0xc9629525f978277568df79838eda9d2d588380657c140f2ef7bdf04826c53f8e',
nonce: '0x1',
storageHash: '0x347b8ccec3a3104ecb9f147ba8308abe9a9c5452b42705ec59cbc3030568fd24',
accountProof: [
'0xfe33cb80921d08778a8e4d52136ae3ef76f679a13640ab13475139a7b8a7d10ef9038f3e807b511c8799e32a00808434087c343511dcd07849cbb5f45a4f275baab66133be8056105a75916691f0ce356bc90f08f5fefdadf1b84a64e84cc8bb981845d238aa80cdf571019f90d3c2d07736b8b40868a2f8b5e58d1093bec37b3351d4286abfae8072f49529c0f99a3d46e0a0dce3f3527c53a12c96bfcf30db993d18231e12069680792abc6dc5c7876958852dcdcecf5877b5799d474135a9ef08a2cf2a188592eb80fc1cf0b15da7e492537f17aa327f0a4092b1ed815fc4625ff86c8b1b3f5cd02780a39277d146e6ad82379141c262d4691b3fa029b2b891d4e7b124eea20f4042b8806d460e9154787237da8e007f64d5baca219f96e084f45a14c90b1ee7a5f08bde',
'0xfe010180661cfcd621161b30e862dfb5bb4d46f28b54d97730e0be9d2fc8713623cfd74680e7d19647879f37a7de9959bb8bd4d81ce55b3df6288bfa2fa49f74f13832b70a',
'0x3f460e45164e07e0e4df7165de40d5863fb7b8ece896a164bf57a134287c68f51901f8440180a0347b8ccec3a3104ecb9f147ba8308abe9a9c5452b42705ec59cbc3030568fd24a0c9629525f978277568df79838eda9d2d588380657c140f2ef7bdf04826c53f8e'
],
storageProof: [
{
key: '0x290decd9548b62a8d60345a988386fc84ba6bc95484008f6362f93160ef3e563',
proof: [Array],
value: '0x2a'
}
]
}
Error: invalid remainder
at Object.decode (/home/arachnid/Downloads/getproof/node_modules/ethereumjs-util/node_modules/rlp/dist/index.js:63:15)
at decodeNode (/home/arachnid/Downloads/getproof/node_modules/merkle-patricia-tree/dist/trieNode.js:154:39)
at Trie.lookupNode (/home/arachnid/Downloads/getproof/node_modules/merkle-patricia-tree/dist/baseTrie.js:253:51)
at async /home/arachnid/Downloads/getproof/node_modules/merkle-patricia-tree/dist/util/walkController.js:41:24Note that this example only verifies the storage proof; the state proof suffers from the same encoding issues.
mattsse
commented
1 year ago sorry I'm a total js noob and it would take me a while to get this running, could you perhaps please add a repro repo that I can "just run"?
Arachnid
commented
1 year ago Just paste the above script into a new directory and do:
yarn add ethers solc merkle-patricia-trie
node nameOfScript.jsIs there anything else I can do to help diagnose this?
gakonst
commented
10 months ago @Arachnid Nick, could you please confirm whether https://github.com/foundry-rs/foundry/pull/6020 fixed it on latest foundryup? Else we'll take another stab at it in next 2 weeks.
Arachnid
commented
10 months ago I'm afraid I'm still getting invalid proofs using the test script:
$ node merkletest.js
{
address: '0x5fbdb2315678afecb367f032d93f642f64180aa3',
balance: '0x0',
codeHash: '0x3287ed8ed801af798b60ccd56ee955c8381b87d01ca11ec93603b12e58188d4d',
nonce: '0x1',
storageHash: '0x347b8ccec3a3104ecb9f147ba8308abe9a9c5452b42705ec59cbc3030568fd24',
accountProof: [
'0xb9012cfe33cb8023c0d400ea554e87fc49a073583c3e83ff51809dc81bdb915f238ae2eae2eae7807b511c8799e32a00808434087c343511dcd07849cbb5f45a4f275baab66133be802d597a1753a5ac1c372afabd5da5a8e67b9e0f026dfa592a93c6fc74c120c36580cdf571019f90d3c2d07736b8b40868a2f8b5e58d1093bec37b3351d4286abfae8072f49529c0f99a3d46e0a0dce3f3527c53a12c96bfcf30db993d18231e12069680792abc6dc5c7876958852dcdcecf5877b5799d474135a9ef08a2cf2a188592eb80fc1cf0b15da7e492537f17aa327f0a4092b1ed815fc4625ff86c8b1b3f5cd027804718e257dbd523b889aff5a4eaada473c364411e0e568609f0c5034edfb92250806d460e9154787237da8e007f64d5baca219f96e084f45a14c90b1ee7a5f08bde',
'0xb845fe100280efcb92a54a4a2a48f0e530b17fcc7658320db87b577158b3637729e08bf7382f8040ede2795702b7736ac9054f96a5e3d00321149fbd35b9bbc404bd4153da32d6',
'0xb8683fe659e60b21cc961f64ad47f20523c1d329d4bbda245ef3940a76dc89d0911b1901f8440180a0347b8ccec3a3104ecb9f147ba8308abe9a9c5452b42705ec59cbc3030568fd24a03287ed8ed801af798b60ccd56ee955c8381b87d01ca11ec93603b12e58188d4d'
],
storageProof: [
{
key: '0x0000000000000000000000000000000000000000000000000000000000000000',
proof: [Array],
value: '0x2a'
}
]
}
Error: Invalid proof provided
at SecureTrie.verifyProof (/home/arachnid/node_modules/merkle-patricia-tree/dist/baseTrie.js:629:23)
at async deploy (/home/arachnid/Downloads/merkletest.js:63:20)
austinabell
commented
6 months ago So it seems the issue is with the codec of this Trie storage layout. You can see that even with an empty trie, the root node is keccak([]) rather than keccak(rlp([])). https://github.com/paritytech/trie/issues/141 has some context relating to this as to why the trie implementation doesn't match Ethereum/EIP1186.
Unfortunately not super clean to fix this, for the following reasons:
trie_db has an eip1186 crate that has that format for proofs, which is essentially the same as what exists in anvil now, but there isn't actually included the correct codec. It's also not releasedalloy-trie seems like the best candidate, using https://docs.rs/alloy-trie/latest/alloy_trie/hash_builder/struct.HashBuilder.html to generate the proofs instead of trie_db, which is what I would recommend for the next person to pick this upalloy-rlp is missing a bunch of utils for peeking the rlp encoding or just pulling raw bytes, and trie_db types are not derived obviously, so my initial hacky exploration was just adding older libs inI was just exploring for fun, but I'll share my diff for exploring the custom codec, if someone decides to do something similar, as there were a few nuances with how this is setup:
diff --git a/Cargo.lock b/Cargo.lock
index 05a4e79a..d1459ada 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -606,11 +606,15 @@ dependencies = [
"hash-db",
"hash256-std-hasher",
"keccak-hasher",
+ "parity-scale-codec",
"rand 0.8.5",
"reference-trie",
"revm",
+ "rlp",
"serde",
"serde_json",
+ "tracing",
+ "trie-db",
"triehash",
]
diff --git a/crates/anvil/core/Cargo.toml b/crates/anvil/core/Cargo.toml
index 6b6041ce..21add1ac 100644
--- a/crates/anvil/core/Cargo.toml
+++ b/crates/anvil/core/Cargo.toml
@@ -30,6 +30,11 @@ c-kzg = { version = "0.4.2", features = ["serde"] }
# trie
hash-db = { version = "0.15", default-features = false }
+# TODO prob have to patch alloy if using this
+# alloy-trie = "0.3"
+trie-db = "0.23"
+codec = { version = "3.1.3", package = "parity-scale-codec", default-features = false, features = ["derive"] }
+rlp = { version = "0.5.1", default-features = false }
hash256-std-hasher = { version = "0.15", default-features = false }
triehash = { version = "0.8", default-features = false }
reference-trie = "0.25"
@@ -37,6 +42,7 @@ keccak-hasher = "0.15"
# misc
rand = "0.8"
+tracing = "0.1"
[dev-dependencies]
anvil-core = { path = ".", features = ["serde"] }
diff --git a/crates/anvil/core/src/eth/trie.rs b/crates/anvil/core/src/eth/trie.rs
index 5d144a5d..9e8da279 100644
--- a/crates/anvil/core/src/eth/trie.rs
+++ b/crates/anvil/core/src/eth/trie.rs
@@ -1,16 +1,31 @@
//! Utility functions for Ethereum adapted from https://github.dev/rust-blockchain/ethereum/blob/755dffaa4903fbec1269f50cde9863cf86269a14/src/util.rs
-use alloy_primitives::B256;
+use alloy_primitives::{b256, B256};
pub use keccak_hasher::KeccakHasher;
// reexport some trie types
-pub use reference_trie::*;
+// pub use reference_trie::*;
+
+pub type RefTrieDB<'a> = trie_db::TrieDB<'a, EIP1186Layout>;
+pub type RefTrieDBMut<'a> = trie_db::TrieDBMut<'a, EIP1186Layout>;
+pub type RefFatDB<'a> = trie_db::FatDB<'a, EIP1186Layout>;
+pub type RefFatDBMut<'a> = trie_db::FatDBMut<'a, EIP1186Layout>;
+pub type RefSecTrieDB<'a> = trie_db::SecTrieDB<'a, EIP1186Layout>;
+pub type RefSecTrieDBMut<'a> = trie_db::SecTrieDBMut<'a, EIP1186Layout>;
+pub type RefLookup<'a, Q> = trie_db::Lookup<'a, EIP1186Layout, Q>;
+
+use core::{borrow::Borrow, marker::PhantomData};
+use hash_db::Hasher;
+use rlp::{DecoderError, Prototype, Rlp, RlpStream};
+use trie_db::TrieLayout;
+use trie_db::{
+ node::{NibbleSlicePlan, NodeHandlePlan, NodePlan, Value, ValuePlan},
+ ChildReference, NodeCodec, Partial,
+};
/// The KECCAK of the RLP encoding of empty data.
-pub const KECCAK_NULL_RLP: B256 = B256::new([
- 0x56, 0xe8, 0x1f, 0x17, 0x1b, 0xcc, 0x55, 0xa6, 0xff, 0x83, 0x45, 0xe6, 0x92, 0xc0, 0xf8, 0x6e,
- 0x5b, 0x48, 0xe0, 0x1b, 0x99, 0x6c, 0xad, 0xc0, 0x01, 0x62, 0x2f, 0xb5, 0xe3, 0x63, 0xb4, 0x21,
-]);
+pub const KECCAK_NULL_RLP: B256 =
+ b256!("56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421");
/// Generates a trie root hash for a vector of key-value tuples
pub fn trie_root<I, K, V>(input: I) -> B256
@@ -40,3 +55,195 @@ where
{
B256::from(triehash::ordered_trie_root::<KeccakHasher, I>(input))
}
+
+/// Trie layout for EIP-1186 state proof nodes.
+#[derive(Default, Clone)]
+pub struct EIP1186Layout;
+
+impl TrieLayout for EIP1186Layout {
+ const USE_EXTENSION: bool = true;
+ const ALLOW_EMPTY: bool = false;
+ const MAX_INLINE_VALUE: Option<u32> = None;
+ type Hash = KeccakHasher;
+ type Codec = RlpNodeCodec<KeccakHasher>;
+}
+
+/// Concrete implementation of a `NodeCodec` with Rlp encoding, generic over the `Hasher`
+#[derive(Default, Clone)]
+pub struct RlpNodeCodec<H: Hasher> {
+ mark: PhantomData<H>,
+}
+
+impl<H> NodeCodec for RlpNodeCodec<H>
+where
+ H: Hasher<Out = [u8; 32]>,
+{
+ type Error = DecoderError;
+ type HashOut = H::Out;
+
+ fn hashed_null_node() -> H::Out {
+ tracing::debug!("hashed_null_node");
+ KECCAK_NULL_RLP.into()
+ }
+
+ fn decode_plan(data: &[u8]) -> Result<NodePlan, Self::Error> {
+ tracing::debug!("decoding: {:?}", data);
+ if data == &KECCAK_NULL_RLP {
+ // early return if this is == keccak(rlp(null)), aka empty trie root
+ // source: https://ethereum.github.io/execution-specs/diffs/frontier_homestead/trie/index.html#empty-trie-root
+ return Ok(NodePlan::Empty);
+ }
+
+ let r = Rlp::new(data);
+ match r.prototype()? {
+ Prototype::List(2) => {
+ let (rlp, offset) = r.at_with_offset(0)?;
+ let (data, i) = (rlp.data()?, rlp.payload_info()?);
+ match (
+ NibbleSlicePlan::new(
+ (offset + i.header_len)..(offset + i.header_len + i.value_len),
+ if data[0] & 16 == 16 { 1 } else { 2 },
+ ),
+ data[0] & 32 == 32,
+ ) {
+ (slice, true) => Ok(NodePlan::Leaf {
+ partial: slice,
+ value: {
+ let (item, offset) = r.at_with_offset(1)?;
+ let i = item.payload_info()?;
+ ValuePlan::Inline(
+ (offset + i.header_len)..(offset + i.header_len + i.value_len),
+ )
+ },
+ }),
+ (slice, false) => Ok(NodePlan::Extension {
+ partial: slice,
+ child: {
+ let (item, offset) = r.at_with_offset(1)?;
+ let i = item.payload_info()?;
+ NodeHandlePlan::Hash(
+ (offset + i.header_len)..(offset + i.header_len + i.value_len),
+ )
+ },
+ }),
+ }
+ }
+ // branch - first 16 are nodes, 17th is a value (or empty).
+ Prototype::List(17) => {
+ let mut nodes = [
+ None, None, None, None, None, None, None, None, None, None, None, None, None,
+ None, None, None,
+ ];
+
+ for index in 0..16 {
+ let (item, offset) = r.at_with_offset(index)?;
+ let i = item.payload_info()?;
+ if item.is_empty() {
+ nodes[index] = None;
+ } else {
+ nodes[index] = Some(NodeHandlePlan::Hash(
+ (offset + i.header_len)..(offset + i.header_len + i.value_len),
+ ));
+ }
+ }
+
+ Ok(NodePlan::Branch {
+ children: nodes,
+ value: {
+ let (item, offset) = r.at_with_offset(16)?;
+ let i = item.payload_info()?;
+ if item.is_empty() {
+ None
+ } else {
+ Some(ValuePlan::Inline(
+ (offset + i.header_len)..(offset + i.header_len + i.value_len),
+ ))
+ }
+ },
+ })
+ }
+ Prototype::Data(0) => Ok(NodePlan::Empty),
+ _ => Err(DecoderError::Custom("Rlp is not valid.")),
+ }
+ }
+
+ fn is_empty_node(data: &[u8]) -> bool {
+ tracing::debug!("is_empty_node");
+ Rlp::new(data).is_empty()
+ }
+
+ fn empty_node() -> &'static [u8] {
+ tracing::debug!("empty node");
+ &[0x80]
+ }
+
+ fn leaf_node(partial: Partial, value: Value) -> Vec<u8> {
+ tracing::debug!("leaf node: {:?}, {:?}", partial, value);
+ let mut stream = RlpStream::new_list(2);
+ let partial = partial.1.iter().copied().collect::<Vec<_>>();
+ stream.append(&partial);
+ let value = match value {
+ Value::Node(bytes, _) => bytes,
+ Value::Inline(bytes) => bytes,
+ };
+ stream.append(&value);
+ stream.out().to_vec()
+ }
+
+ fn extension_node(
+ partial: impl Iterator<Item = u8>,
+ _number_nibble: usize,
+ child_ref: ChildReference<Self::HashOut>,
+ ) -> Vec<u8> {
+ tracing::debug!("Extension");
+ let mut stream = RlpStream::new_list(2);
+ stream.append(&partial.collect::<Vec<_>>());
+ match child_ref {
+ ChildReference::Hash(h) => stream.append(&h.as_slice()),
+ ChildReference::Inline(inline_data, len) => {
+ let bytes = &AsRef::<[u8]>::as_ref(&inline_data)[..len];
+ stream.append_raw(bytes, 1)
+ }
+ };
+ stream.out().to_vec()
+ }
+
+ fn branch_node(
+ children: impl Iterator<Item = impl Borrow<Option<ChildReference<Self::HashOut>>>>,
+ value: Option<Value>,
+ ) -> Vec<u8> {
+ tracing::debug!("Branch");
+ let mut stream = RlpStream::new_list(17);
+ for child_ref in children {
+ match child_ref.borrow() {
+ Some(c) => match c {
+ ChildReference::Hash(h) => stream.append(&h.as_slice()),
+ ChildReference::Inline(inline_data, len) => {
+ let bytes = &inline_data[..*len];
+ stream.append_raw(bytes, 1)
+ }
+ },
+ None => stream.append_empty_data(),
+ };
+ }
+ if let Some(value) = value {
+ let value = match value {
+ Value::Node(bytes, _) => bytes,
+ Value::Inline(bytes) => bytes,
+ };
+ stream.append(&value);
+ } else {
+ stream.append_empty_data();
+ }
+ stream.out().to_vec()
+ }
+
+ fn branch_node_nibbled(
+ _partial: impl Iterator<Item = u8>,
+ _number_nibble: usize,
+ _children: impl Iterator<Item = impl Borrow<Option<ChildReference<Self::HashOut>>>>,
+ _value: Option<Value>,
+ ) -> Vec<u8> {
+ unimplemented!("Ethereum branch nodes do not have partial key")
+ }
+}
diff --git a/crates/anvil/src/eth/backend/mem/mod.rs b/crates/anvil/src/eth/backend/mem/mod.rs
index a60ba564..19d98b34 100644
--- a/crates/anvil/src/eth/backend/mem/mod.rs
+++ b/crates/anvil/src/eth/backend/mem/mod.rs
@@ -88,7 +88,7 @@ use std::{
};
use storage::{Blockchain, MinedTransaction};
use tokio::sync::RwLock as AsyncRwLock;
-use trie_db::{Recorder, Trie};
+use trie_db::{recorder::Recorder, CError, Result as TrieResult, Trie, TrieHash, TrieLayout};
pub mod cache;
pub mod fork_db;
@@ -614,7 +614,7 @@ impl Backend {
/// Returns an error if op-stack deposits are not active
pub fn ensure_op_deposits_active(&self) -> Result<(), BlockchainError> {
if self.is_optimism() {
- return Ok(())
+ return Ok(());
}
Err(BlockchainError::DepositTransactionUnsupported)
}
@@ -1381,7 +1381,7 @@ impl Backend {
}
if let Some(fork) = self.get_fork() {
- return Ok(fork.block_by_hash_full(hash).await?)
+ return Ok(fork.block_by_hash_full(hash).await?);
}
Ok(None)
@@ -1435,7 +1435,7 @@ impl Backend {
if let Some(fork) = self.get_fork() {
let number = self.convert_block_number(Some(number));
if fork.predates_fork_inclusive(number) {
- return Ok(fork.block_by_number(number).await?)
+ return Ok(fork.block_by_number(number).await?);
}
}
@@ -1454,7 +1454,7 @@ impl Backend {
if let Some(fork) = self.get_fork() {
let number = self.convert_block_number(Some(number));
if fork.predates_fork_inclusive(number) {
- return Ok(fork.block_by_number_full(number).await?)
+ return Ok(fork.block_by_number_full(number).await?);
}
}
@@ -1818,7 +1818,7 @@ impl Backend {
}
if let Some(fork) = self.get_fork() {
- return Ok(fork.trace_transaction(hash).await?)
+ return Ok(fork.trace_transaction(hash).await?);
}
Ok(vec![])
@@ -1862,7 +1862,7 @@ impl Backend {
}
if let Some(fork) = self.get_fork() {
- return Ok(fork.debug_trace_transaction(hash, opts).await?)
+ return Ok(fork.debug_trace_transaction(hash, opts).await?);
}
Ok(GethTrace::Default(Default::default()))
@@ -1888,7 +1888,7 @@ impl Backend {
if let Some(fork) = self.get_fork() {
if fork.predates_fork(number) {
- return Ok(fork.trace_block(number).await?)
+ return Ok(fork.trace_block(number).await?);
}
}
@@ -2085,7 +2085,9 @@ impl Backend {
if let Some(fork) = self.get_fork() {
let number = self.convert_block_number(Some(number));
if fork.predates_fork(number) {
- return Ok(fork.transaction_by_block_number_and_index(number, index.into()).await?)
+ return Ok(fork
+ .transaction_by_block_number_and_index(number, index.into())
+ .await?);
}
}
@@ -2102,7 +2104,7 @@ impl Backend {
}
if let Some(fork) = self.get_fork() {
- return Ok(fork.transaction_by_block_hash_and_index(hash, index.into()).await?)
+ return Ok(fork.transaction_by_block_hash_and_index(hash, index.into()).await?);
}
Ok(None)
@@ -2141,7 +2143,10 @@ impl Backend {
}
if let Some(fork) = self.get_fork() {
- return fork.transaction_by_hash(hash).await.map_err(BlockchainError::AlloyForkProvider)
+ return fork
+ .transaction_by_hash(hash)
+ .await
+ .map_err(BlockchainError::AlloyForkProvider);
}
Ok(None)
@@ -2183,33 +2188,49 @@ impl Backend {
let (db, root) = block_db.maybe_as_hash_db().ok_or(BlockchainError::DataUnavailable)?;
let data: &dyn HashDB<_, _> = db.deref();
- let mut recorder = Recorder::new();
+ // let mut recorder = Recorder::new();
let trie = RefTrieDB::new(&data, &root.0)
.map_err(|err| BlockchainError::TrieError(err.to_string()))?;
+ println!("trie={:?}", trie);
- let maybe_account: Option<BasicAccount> = {
- let acc_decoder = |mut bytes: &[u8]| {
- BasicAccount::decode(&mut bytes).unwrap_or_else(|_| {
- panic!("prove_account_at, could not query trie for account={:?}", &address)
- })
- };
- let query = (&mut recorder, acc_decoder);
- trie.get_with(account_key.as_slice(), query)
- .map_err(|err| BlockchainError::TrieError(err.to_string()))?
+ let (account_proof, maybe_account_bytes) = generate_proof(&trie, &address.as_slice())
+ // generate_proof(&trie, &account_key.as_slice())
+ .map_err(|err| BlockchainError::TrieError(err.to_string()))?;
+ println!("get address={:?}", address);
+ println!("keccak address={:?}", keccak256(address));
+ println!("maybe_account={:?}", maybe_account_bytes);
+
+ let account = if let Some(account_bytes) = maybe_account_bytes {
+ println!("account_bytes={:?}", account_bytes);
+ BasicAccount::decode(&mut account_bytes.as_slice())
+ .map_err(|_| BlockchainError::DataUnavailable)?
+ } else {
+ BasicAccount::default()
};
- let account = maybe_account.unwrap_or_default();
-
- let proof = recorder
- .drain()
- .into_iter()
- .map(|r| r.data)
- .map(|record| {
- // proof is rlp encoded:
- // <https://github.com/foundry-rs/foundry/issues/5004>
- // <https://www.quicknode.com/docs/ethereum/eth_getProof>
- alloy_rlp::encode(record).to_vec().into()
- })
- .collect::<Vec<_>>();
+ // let maybe_account: Option<BasicAccount> = {
+ // let acc_decoder = |mut bytes: &[u8]| {
+ // BasicAccount::decode(&mut bytes).unwrap_or_else(|_| {
+ // panic!("prove_account_at, could not query trie for account={:?}", &address)
+ // })
+ // };
+ // let query = (&mut recorder, acc_decoder);
+ // trie.get_with(account_key.as_slice(), query)
+ // .map_err(|err| BlockchainError::TrieError(err.to_string()))?
+ // };
+ // let account = maybe_account.unwrap_or_default();
+
+ // let proof = recorder
+ // .drain()
+ // .into_iter()
+ // .map(|r| r.data)
+ // .map(|record| {
+ // // proof is rlp encoded:
+ // // <https://github.com/foundry-rs/foundry/issues/5004>
+ // // <https://www.quicknode.com/docs/ethereum/eth_getProof>
+ // // alloy_rlp::encode(record).to_vec().into()
+ // record.into()
+ // })
+ // .collect::<Vec<_>>();
let account_db =
block_db.maybe_account_db(address).ok_or(BlockchainError::DataUnavailable)?;
@@ -2220,7 +2241,11 @@ impl Backend {
nonce: account.nonce.to::<U64>(),
code_hash: account.code_hash,
storage_hash: account.storage_root,
- account_proof: proof,
+ account_proof: account_proof
+ .into_iter()
+ .map(From::from)
+ // .map(|record| alloy_rlp::encode(record).to_vec().into())
+ .collect(),
storage_proof: keys
.into_iter()
.map(|storage_key| {
@@ -2232,12 +2257,8 @@ impl Backend {
value: U256::from_be_bytes(storage_value.0),
proof: storage_proof
.into_iter()
- .map(|proof| {
- // proof is rlp encoded:
- // <https://github.com/foundry-rs/foundry/issues/5004>
- // <https://www.quicknode.com/docs/ethereum/eth_getProof>
- alloy_rlp::encode(proof).to_vec().into()
- })
+ .map(From::from)
+ // .map(|record| alloy_rlp::encode(record).to_vec().into())
.collect(),
},
)
@@ -2272,6 +2293,21 @@ impl Backend {
}
}
+/// Generate an eip-1186 compatible proof for key-value pairs in a trie given a key.
+pub fn generate_proof<T, L>(
+ trie: &T,
+ key: &[u8],
+) -> TrieResult<(Vec<Vec<u8>>, Option<Vec<u8>>), TrieHash<L>, CError<L>>
+where
+ T: Trie<L>,
+ L: TrieLayout,
+{
+ let mut recorder = Recorder::new();
+ let item = trie.get_with(key, &mut recorder)?;
+ let proof: Vec<Vec<u8>> = recorder.drain().into_iter().map(|r| r.data).collect();
+ Ok((proof, item))
+}
+
/// Get max nonce from transaction pool by address
fn get_pool_transactions_nonce(
pool_transactions: &[Arc<PoolTransaction>],
@@ -2284,7 +2320,7 @@ fn get_pool_transactions_nonce(
.max()
{
let tx_count = highest_nonce.saturating_add(U256::from(1));
- return Some(tx_count)
+ return Some(tx_count);
}
None
}
@@ -2314,8 +2350,8 @@ impl TransactionValidator for Backend {
if chain_id.to::<u64>() != tx_chain_id {
if let Some(legacy) = tx.as_legacy() {
// <https://github.com/ethereum/EIPs/blob/master/EIPS/eip-155.md>
- if env.handler_cfg.spec_id >= SpecId::SPURIOUS_DRAGON &&
- !meets_eip155(chain_id.to::<u64>(), legacy.signature().v())
+ if env.handler_cfg.spec_id >= SpecId::SPURIOUS_DRAGON
+ && !meets_eip155(chain_id.to::<u64>(), legacy.signature().v())
{
warn!(target: "backend", ?chain_id, ?tx_chain_id, "incompatible EIP155-based V");
return Err(InvalidTransactionError::IncompatibleEIP155);
@@ -2470,19 +2506,23 @@ pub fn prove_storage(
storage_key: B256,
) -> Result<(Vec<Vec<u8>>, B256), BlockchainError> {
let data: &dyn HashDB<_, _> = data.deref();
- let mut recorder = Recorder::new();
let trie = RefTrieDB::new(&data, &acc.storage_root.0)
.map_err(|err| BlockchainError::TrieError(err.to_string()))
.unwrap();
- let item: U256 = {
- let decode_value =
- |mut bytes: &[u8]| U256::decode(&mut bytes).expect("decoding db value failed");
- let query = (&mut recorder, decode_value);
- trie.get_with(storage_key.as_slice(), query)
- .map_err(|err| BlockchainError::TrieError(err.to_string()))?
- .unwrap_or(U256::ZERO)
- };
-
- Ok((recorder.drain().into_iter().map(|r| r.data).collect(), B256::from(item)))
+ let (proof, bytes) = generate_proof(&trie, &storage_key.as_ref())
+ .map_err(|err| BlockchainError::TrieError(err.to_string()))?;
+ let bytes = bytes.unwrap_or_default();
+
+ // let bytes: Vec<u8> = {
+ // // let decode_value =
+ // // |mut bytes: &[u8]| U256::decode(&mut bytes).expect("decoding db value failed");
+ // // let query = decode_value;
+ // trie
+ // .get(storage_key.as_slice())
+ // .map_err(|err| BlockchainError::TrieError(err.to_string()))?
+ // .unwrap_or_default()
+ // };
+
+ Ok((proof, B256::from(U256::try_from_be_slice(&bytes).unwrap())))
}
diff --git a/crates/anvil/src/eth/backend/mem/state.rs b/crates/anvil/src/eth/backend/mem/state.rs
index 29a774f1..a54e1c1b 100644
--- a/crates/anvil/src/eth/backend/mem/state.rs
+++ b/crates/anvil/src/eth/backend/mem/state.rs
@@ -19,8 +19,11 @@ use trie_db::TrieMut;
pub fn storage_trie_db(storage: &HashMap<U256, U256>) -> (AsHashDB, B256) {
// Populate DB with full trie from entries.
let (db, root) = {
- let mut db = <memory_db::MemoryDB<_, HashKey<_>, _>>::default();
+ let mut db = <memory_db::MemoryDB<_, HashKey<_>, _>>::new([0x80].as_slice());
let mut root = Default::default();
+ // if storage.is_empty() {
+ // return (Box::new(db), KECCAK_NULL_RLP);
+ // }
{
let mut trie = RefSecTrieDBMut::new(&mut db, &mut root);
for (k, v) in storage.iter().filter(|(_k, v)| *v != &U256::from(0)) {
@@ -42,12 +45,19 @@ pub fn trie_hash_db(accounts: &HashMap<Address, DbAccount>) -> (AsHashDB, B256)
// Populate DB with full trie from entries.
let (db, root) = {
- let mut db = <memory_db::MemoryDB<_, HashKey<_>, _>>::default();
+ let mut db = <memory_db::MemoryDB<_, HashKey<_>, _>>::new([0x80].as_slice());
let mut root = Default::default();
+ // if accounts.is_empty() {
+ // return (Box::new(db), KECCAK_NULL_RLP);
+ // }
{
let mut trie = RefSecTrieDBMut::new(&mut db, &mut root);
for (address, value) in accounts {
trie.insert(address.as_ref(), value.as_ref()).unwrap();
+ // NOTE: this succeeds, but for some reason fails when queried outside of this fn
+ let a = trie.get(address.as_ref()).unwrap();
+ println!("address: {:0X?}", address);
+ println!("a: {:0X?}", a);
}
}
(db, root)
diff --git a/crates/anvil/tests/it/proof/mod.rs b/crates/anvil/tests/it/proof/mod.rs
index 85e8c630..938fa858 100644
--- a/crates/anvil/tests/it/proof/mod.rs
+++ b/crates/anvil/tests/it/proof/mod.rs
@@ -5,7 +5,8 @@ use alloy_primitives::{keccak256, Address, B256, U256};
use alloy_rlp::Decodable;
use alloy_rpc_types::EIP1186AccountProofResponse;
use anvil::{spawn, NodeConfig};
-use anvil_core::eth::{proof::BasicAccount, trie::ExtensionLayout};
+use anvil_core::eth::trie::KeccakHasher;
+use anvil_core::eth::{proof::BasicAccount, trie::EIP1186Layout};
use foundry_evm::revm::primitives::KECCAK_EMPTY;
mod eip1186;
@@ -40,7 +41,7 @@ async fn can_get_proof() {
.map(|node| Vec::<u8>::decode(&mut &node[..]).unwrap())
.collect();
- verify_proof::<ExtensionLayout>(
+ verify_proof::<EIP1186Layout<KeccakHasher>>(
&root.0,
&acc_proof,
&keccak256(acc.as_slice())[..],
@@ -54,7 +55,7 @@ async fn can_get_proof() {
let storage_proof: Vec<Vec<u8>> =
proof.proof.into_iter().map(|node| Vec::<u8>::decode(&mut &node[..]).unwrap()).collect();
let key = B256::from(keccak256(proof.key.0 .0));
- verify_proof::<ExtensionLayout>(
+ verify_proof::<EIP1186Layout<KeccakHasher>>(
&account.storage_root.0,
&storage_proof,
key.as_slice(),There is an issue with this as it currently has a broken hash link between the extension and leaf nodes in the trie, trie_db is a bit tedious to debug, and I got bored.
I won't be continuing on with this for the foreseeable future, but hope this context helps if someone gets to this before I have time to come back :)
mattsse
commented
6 months ago thanks for looking into this @austinabell
we're trying to transition to alloy-trie
fyi @klkvr
Component
Anvil
Have you ensured that all of these are up to date?
What version of Foundry are you on?
forge 0.2.0 (31fcf5a 2023-05-19T00:04:19.980323193Z)
What command(s) is the bug in?
anvil
Operating System
Linux
Describe the bug
Steps to reproduce:
anvilcast proof <contract> <slot>The returning account and storage proof array elements have a wrong RLP encoding which cannot be decoded.