Extend MerkleProof to support verifying proof from eth_getProof

[makoto]

🧐 Motivation

The current MerkleProof only works with binary trees, not with eth’s Patricia trees. Supporting Patricia trees will be useful so that it can be used to verify account and storage proof via eth_getProof

📝 Details

There is a similar solution existing on web3.py and optimism

[frangio]

We've considered this in the past. The issue is that this code would break with the introduction of Verkle trees. To be future proof, this should be included in the EVM as a precompile that could be upgraded to support them in the future.

We can still consider offering this code, but it would come with the caveat that it isn't future proof.

Can you share the use cases you have in mind?

[gballet]

Chiming in about the verkle tree concerns: I can't promise that there will be a verification precompile at this stage, as you know these are frowned upon due to their maintenance cost.

I was wondering: given that proofs are widely different, it would be possible to determine if a proof is an MPT proof or a verkle one. Even simpler, the call to MerkleProof could receive an extra parameter, that specifies if the user wants a verkle or merkle proof. Then there could be some sort of table that can be updated, that will delegate the verkle verification to an external contract. I think this should be feasible if the verification precompile isn't an option.

Happy to discuss this further, and I will also investigate the feasability of a verification precompile in the meantime.

[Amxx]

This would have usage beyond proving "mainnet" proofs. I could be usefull to prove statement about other chains providing that the root hash is known. I can foresee this being used to prove statements about the polygon state on mainnet. Even after mainnet moves to verkle trees, this would still prove usefull if the other chain doesn't operate the same transition.

I would personally love to include this, will all the warning and disclaimers needed about Patricia trees possibly being deprecated in the future.

[frangio]

Even simpler, the call to MerkleProof could receive an extra parameter, that specifies if the user wants a verkle or merkle proof.

In the ideal scenario, the code would be forward compatible, i.e. automatically adapt to verkle proofs. Unless the contract is upgradeable, this can only be reliably achieved by a precompile, which is why I think there should be one.

I can foresee this being used to prove statements about the polygon state on mainnet.

Yeah, I think this is already how the Polygon bridge works in that direction.

In general I'm skeptical about the need for Patricia trees given that there are probably other bridges in place that may be more efficient. In rollups this is clearly the case.

[makoto]

From the use case I have in mind, we can upgrade the contract so no need to have precompiled just for forward compatibility.

[frangio]

@makoto Is that a use case you could share? It helps us prioritize the work.

[makoto]

Sure. Here are the two places I am using storage verifications. The use case is to verify l2 storage slot on l1. Even though how you verify l2 state on l1 is different to each l2 chains, the way to verify storage is almost identical.

https://github.com/ensdomains/op-resolver/blob/master/packages/contracts/contracts/l1/OptimismResolverStub.sol#L135 https://github.com/ensdomains/arb-resolver/blob/master/packages/contracts/contracts/l1/ArbitrumResolverStub.sol#L166

Optimism's library works perfectly fine so we will be using that for non-Optimism chains, but I thought it would be nice if OZ libraries has the support, too.

[Amxx]

IMO we would want two things:

• first, a "mathematical" implementation of the merkle-proof verification (as a mathematical primitive) that correpond to eth_getProof proofs.
• maybe later, a wrapper that process an arbitrary proof using different algorithm (the one above & other) depending on the proof structure. Note that there have been discussion for a precompile that does that.

I believe there is real added value to providing the first element, come with specific warning, because I view it as a "pure" mathemical function that can be usefull I many context and needs a "standard" solidity implementation.

It will have to come with comments stating that the mathematical structure being verified might not be used forever, and that there are plans to transition away from it. Maybe linking to this article about evm-equivalence:

There are a small number of exceptions. One incompatibility arises for applications that verify Merkle proofs of historical Ethereum blocks to verify claims about historical transactions, receipts or state (eg. bridges sometimes do this). A ZK-EVM that replaces Keccak with a different hash function would break these proofs. However, I usually recommend against building applications this way anyway, because future Ethereum changes (eg. Verkle trees) will break such applications even on Ethereum itself. A better alternative would be for Ethereum itself to add future-proof history access precompiles.

[Amxx]

Note that the precompile mentioned by Vitalik would not render this implementation useless, as this implementation might be used in a post-verge ethereum, to prove properties about other blockchains (Matic, BNB, ...)

[frangio]

Well in an ideal world the precompile would be compatible with other blockchains as well but this is where it starts to become harder to justify to client development teams.

I don't know if it makes sense to completely disentangle it from the context of Ethereum, but I see the argument that "mathematically" a Merkle Patricia Tree verifier makes sense on its own. And this has been requested a few times so it would make sense for us to offer it.

[Amxx]

From my understanding, any eth_getProof verification algorithm would need to do some RLP decoding. As we don't want to have any dependencies, a first step would be to build a library for manipulating RLP bytes.