Is there a way to get the proof verifier to work for Ethereum MPT proofs?

[kevincheng96]

After playing around with this library, seems like the proof verifier may be incompatible with Ethereum merkle proofs generated thorough EIP-1186's eth_getProof method. Curious if I am missing something and if there is out-of-the-box support for Ethereum merkle proofs?

[cheme]

That is how it is use with ethereum https://github.com/openethereum/openethereum/blob/582bca385fedb1af682e989e5bcc6b3b2cf53028/crates/ethcore/src/state/account.rs#L652
Note that this is only for building the 'proof' field in the eip.

[lightyear15]

Hi @kevincheng96 ,
I am also interested in making trie-db proof verification function work with ethereum EIP-1186 proofs, did you manage to write a proper NodeCodec to make it work?

It looks like the incompatibility is due to eth_getProof including nodes that, for trie_db::proof::verify_proof should be omitted.
The decode function for RlpNodeCodec

fn decode(data: &[u8]) -> Result<Node, rlp::DecoderError> {
    const HASHLEN: usize = H256::len_bytes();
    let r = rlp::Rlp::new(data);
    match r.prototype()? {
        rlp::Prototype::List(2) => {
            //https://eth.wiki/fundamentals/patricia-tree#specification-compact-encoding-of-hex-sequence-with-optional-terminator
            let offset = if data[0] & 0x10 == 0x10 { 1 } else { 2 };
            let is_leaf = data[0] & 0x20 == 0x20;
            let nib = NibbleSlice::new_offset(data, offset);
            if is_leaf && data.len() == HASHLEN {
                Ok(Node::Leaf(nib, Value::Node(data, None)))
            } else if is_leaf && data.len() != HASHLEN {
                Ok(Node::Leaf(nib, Value::Inline(data)))
            } else if !is_leaf && data.len() == HASHLEN {
                Ok(Node::Extension(nib, NodeHandle::Hash(data)))
            } else if !is_leaf && data.len() != HASHLEN {
                Ok(Node::Extension(nib, NodeHandle::Inline(data)))
            } else {
                panic!("uncovered case?!?!");
            }
        }
        rlp::Prototype::List(17) => {
            let mut nodes: [Option<NodeHandle>; 16] = Default::default();
            for i in 0..16 {
                match r.at(i)?.prototype()? {
                    rlp::Prototype::Null => {
                        nodes[i] = None;
                    }
                    rlp::Prototype::Data(HASHLEN) => {
                        let hash = r.at(i)?.data()?;
                        nodes[i] = Some(NodeHandle::Hash(hash));
                    }
                    rlp::Prototype::Data(_) => {
                        let data = r.at(i)?.data()?;
                        nodes[i] = Some(NodeHandle::Inline(data));
                    }
                    _ => {
                        panic!("unexpected type");
                    }
                }
            }
            let val = if r.at(16)?.is_empty() {
                None
            } else {
                Some(Value::Inline(r.at(16)?.data()?))
            };
            Ok(Node::Branch(nodes, val))
        }
        rlp::Prototype::Data(0) => {
            Ok(Node::Empty)
        }
        rlp::Prototype::Data(32) => {
            let slice = NibbleSlice::new(&[]);
            let data = r.data()?;
            Ok(Node::Leaf(slice, Value::Node(data, None)))
        }
        rlp::Prototype::Data(_) => {
            let slice = NibbleSlice::new(&[]);
            let data = r.data()?;
            Ok(Node::Leaf(slice, Value::Inline(data)))
        }
        _ => Err(Self::Error::Custom("Rlp is not valid.")),
    }
}

The a test case for account_proof:

 fn account_proof() {
        let account_proof : Vec<Vec<u8>> = vec![ hex::decode("f90211a0a6b203d03e6160308d4edbea463a3e89a98f6ad55579615de44753172b7e080fa02da1004d634d6a204c6cacb9794b4181ceaae224da2513b9fd7d9f75f7605472a07df74ee2b471865ceaf1028f21fade15a49e2c4b3638eddb4106f343410b5a93a0796b3116a946f85211bae3113ab2f5f6642051fbcdfbf5e8874baddf9156a088a0ec67bda0f451dff9dece308182c517135b06260aa7ea4a7e3b100a458c135e56a0f48d496dc91261272696fc3c68170f9754eeb3218ee642f43d3813b8ee134463a0e0003f0ae99357565d9a9b7bc79eeeac44963f11ab1080188691aea39dd23dbba094cfa78a4f1191e32fbdf089b69cfc968788e85be886cc06ee3631beab14633ea0b70869825d2765c0ed3aa3ba15cdde5858784109dbaf2476c3e6e0a32fc455ada07c969835d595a457413f21c2c67004f8793fcc4fd2e4a2fbbc7f9c9cd0ee2bf5a0feb8b98f78d3af5461fe2515f1580c9e6e89061a746f9bfd5bf8076b09af0b05a0b0ee957c117111181d8f8acff3339f4d61c3f1cc07781e9586d0da8af3db1823a0173684012b0494ff75cd6a1dca4418bc75e60ebb9e73314c549cdd0eb6b002b5a01c304dd836cee502cfb38554f47a605a259eb3aeaed84531b66395d133e58231a04915bfd12d615c96c39c15b8e24b4232257fd612cb55bb7cf3933e5de9d813aea01e0cfbda9f92ee28efba984e6da08cce0beeba96e5f13e2a1d31cc486e0c4cf380").unwrap(),
        hex::decode("f90151a0bb72481591186bf9e006d707b43f67e36ab1ab95957f410247500fc2056804e1a0ce948128ab579f541f6d2dba4be7aa1490a19bcea1493c52b247ae60713ee0d880a0e26621ae9dd5ba1a1230e34b6dd023d7cd4354853b4771da4b91c53598769b12a0d51824a605770cf6a35da33ed63f5ac67d7dce7bdbe4cbbf9605dde010feaff6a0f7a9dff8a8ffece564e0b1248a02417aafc8913b14e170b7a5b6bc810c540821808080a08b336dbd56e000633bcae0e0a646de12b47e55ff410f1422bc9950b13cc2c9c0a0b998f51850c85abae65303e76bacb07883acec5b8b696dce020499087d7b25e48080a01731b08d5dc7b27cfbc0b9bcd4c46dce7e0a524069a9addbf8949a7122fa83b3a09a303c3da858fa1d877372dfcb84f66e6ae79b18493b65163572df77df88c34ba00ec14eb0e7e6d717f66f1d0fa83d2e8bb51ba5a726a81fd8112808fca33eb65880").unwrap(),
        hex::decode("f869a0209069305ae778ce2c9816610236ab598ba13cee0efe0da0ce44df071a470f43b846f8440180a0f71ede3448bf24915e2ae95d51c1f0edb47872b749ff5b58f6231d4f231ce991a09f2a70fec0637bf64166411e82cb5c3f4a022c83eeace48ea212424132f4cc37").unwrap()];

        let account = Account {
            nonce: U64::from(0x1),
            balance: U64::from(0x0),
            storage_hash: H256::from_str(
                "0xf71ede3448bf24915e2ae95d51c1f0edb47872b749ff5b58f6231d4f231ce991",
            )
            .unwrap(),
            code_hash: H256::from_str(
                "0x9f2a70fec0637bf64166411e82cb5c3f4a022c83eeace48ea212424132f4cc37",
            )
            .unwrap(),
        };
        let rlp_account = rlp::encode(&account);
        let account_address =
            Address::from_str("0xfdd8bd58115ffbf04e47411c1d228ecc45e93075").unwrap();
        let root =
            H256::from_str("0x49c26d9ea3367b9c8c655fbea4a3b0181526b6482c3b68edb1921ee6ecfddbca")
                .unwrap();
        let res = trie_db::proof::verify_proof::<Layout, _, _, _>(
            &root,
            &account_proof,
            &[(account_address.as_bytes(), Some(rlp_account))],
        );
        assert!(res.is_ok(), "{}", res.err().unwrap());
    }

The unit test fails with

panicked at 'Extraneous hash reference found in proof should have been omitted: hash=0x1e0cfbda9f92ee28efba984e6da08cce0beeba96e5f13e2a1d31cc486e0c4cf3'

[lightyear15]

... Maybe @jimpo
can give me an hint 🥲

[jimpo]

The trie_db::proof module was not designed to be compatible with EIP-1186, it was designed for space efficiency. From the module documentation: "The trie nodes are not included in their entirety as data which the verifier can compute for themself is omitted. In particular, the values of included keys and and hashes of other trie nodes in the proof are omitted."

It's somewhere in the Ethereum code but IIRC the way of verifying EIP-1186 proofs was to dump the nodes in the trie-db and do a lookup. Though EIP-1186 specifies an order and the verifier would have to check that separately.

API-wise, maybe it'd make sense to add a module for EIP-1186 proofs (full trie nodes), and rename or alias trie_db::proof to trie_db::compact_proof or something.

[lightyear15]

Thanks a lot @jimpo ,
I will explore your idea.
I would rather create a module called extended_proof or a sub-module called eip1186 though, so I won't break any existing code

[cheme]

It's somewhere in the Ethereum code

see my previous comment :)

[seunlanlege]

So i found this crate: https://github.com/openethereum/openethereum/tree/582bca385fedb1af682e989e5bcc6b3b2cf53028/crates/db/patricia-trie-ethereum in open-ethereum but it looks like its no longer compatible with the latest version of this library.

What needs to be updated to make this compatible? Pseudo code is also fine 🙏🏿

cc @cheme

[cheme]

Yes parity-ethereum looks a lot behind head, and project is not maintain anymore afaik.
The current master should work but it requires to upgrade all needed component:

• add a TrieLayout instance (should be pretty much this layout (this is what we test to try to remain eth compatibility) but replacing the codec with the rlp one.
• use builders to instanciate triedb and triedbmut.

Generally I would not hope that the compatibility with eth stays long term (mainly support the exstension nodes), since openeth stopped, I don't know of good reason in doing so. There is a point where this crate would be probably forked to a pure no-extension, limited rocksdb support one (first would require substrate to switch to rocksdb which could actually take some time:)

But with current state of code it should be supported.

[cheme]

forgot the link to the test layout :

trie/test-support/reference-trie/src/lib.rs

Line 78 in 48fcfa9

impl TrieLayout for ExtensionLayout {

[lightyear15]

Hello @seunlanlege and @cheme
is this what you are looking for
#146 ?

[seunlanlege]

is this what you are looking for
#146 ?

So this looks really good, but i just have a question. Why did you opt to not use TrieDb + HashDb ?

[lightyear15]

is this what you are looking for
#146 ?

So this looks really good, but i just have a question. Why did you opt to not use TrieDb + HashDb ?

I did use it
https://github.com/ChorusOne/trie/blob/44a3c5e9c269111110537287aec8cc9050824446/trie-eip1186/test/src/eip1186.rs#L17

[seunlanlege]

I did use it
https://github.com/ChorusOne/trie/blob/44a3c5e9c269111110537287aec8cc9050824446/trie-eip1186/test/src/eip1186.rs#L17

Hmm, i guess my real question is: where's your NodeCodec implementation for Rlp?

[lightyear15]

Ah I see what you mean
no NodeCodec implementation.
The problem with trie-db is the way the proof is generated, not the way nodes are coded/decoded.
So the trie-db::proof functions are of no use here

[seunlanlege]

Ended up implementing a NodeCodec for EIP-1186 here, if anyone ends up on this issue

https://github.com/polytope-labs/hyperbridge/blob/main/modules/trees/ethereum/README.md