mrsmkl/eth-patricia

Checking Merkle proofs of modified patricia trees used by Ethereum

Implementation of verifying Merkle proofs for modified merkle patricia trees used in Ethereum blocks

Based on https://github.com/GridPlus/cryptobridge-contracts and https://github.com/ethereumjs/merkle-patricia-tree/blob/master/proof.js

Description of these trees, including RLP and hex-prefixes: http://yellowpaper.io

Related:

• Complete implementation of RLP: https://github.com/androlo/standard-contracts/blob/master/contracts/src/codec/RLP.sol
• Reading Ethereum block headers: https://github.com/figs999/Ethereum

eth-patricia's Issues

Merkle Proof verification failed for a valid proof.

eth-patricia/MerklePatriciaProof.sol

Line 21 in b4e84e7

function verify(bytes32 value, bytes encodedPath, bytes rlpParentNodes, bytes32 root) internal pure returns (bool) {

We are using MerklePatriciaProof.sol library in Mosaic-contracts. While testing, we came across a use case where verification of Merkle proof failed for a valid proof.

After debugging, a scenario is observed for the Merkle proof which has an extension node in between.

On L55,_nibblesToTraverse function increases pathPtr with the size of the extension node key.

pathPtr += _nibblesToTraverse(RLP.toData(currentNodeList[0]), path, pathPtr);

Then on L65, updated pathPtr is passed. Here _nibblesToTraverse will return 0 because the key of the extension node will not match this time. Hence false is returned from the function and Merkle proof verification will fail.

Possible fix for the issue is to preserve pathPtr before updating on L55 and pass the preserved pathPtr on L65. Refer this commit.

Below are the parameters which were passed to the verify function.

value : 0x5fe7f977e71dba2ea1a68e21057beebb9be2ac30c6410aa38d4f3fbe41dcffd2

encodedPath : 0x40769c9cc6db1aff35e37923897950227d2a87c95ef0101b2a0233740f2ce00d

rlpParentNodes : 0xf9022cf9019180a0320ce86e317f7e61e7890a6671338aa79374e5ec3206fc38496b5b3719788fc4a07642cb37fbbc28c4c2e8367a93bb491013223d266543c0e42db6a580cc274beea0ad8732b76b5befaa3c523633abdafb8b410b8e1140526255c839a7225e2b2f3ea060b926526a0a95873151f96f0c4aa7746dd1cc51242b4893d43554acd2716cda80a03e819a317d72fa7445677a4104b74899547b424aec05ae303b605f7d78aa9dc4a0c9980a15de3258be2f1dcf5d0657c256f7e7aebe83b736aada89aa02dee3853ea0747f61b4309342612ee827a5930678c61bd54a2c85e207144c265912351d46f4a070256c377a27b7c7cdf605559f21f20f54d147abce914c3b1ac36815fd8f2b8080a0b7a25a664618fb58b0754dd3c9665402787704d11169240bccf8e7c34feb0167a0e78c6966deeb91437d0c2cbf66bde64fd4dbb76d22a9885679a3cf9e5fd84394a02a74dc63db6f6f5f79d6cadbb2b348771d3bcd1913f9319cfa0c5fea4353db47a0e53cc96cd3fe0910d63b48800ac824d7f0e094548d259d6342da2189ca3c0e238080e210a0094e521c10bbb9291d38d4aebd6c6722a4763451011f97f24709b28611831699f8518080808080a0460b29d4cbb31e3680769b8ece024e6e35e9c9c3d9c7c207873e93b8c43cff1980a0fe9627f9a9fb3323465824fc6fdfd87f907332a17f6ed39bfdcd94c76b548eee808080808080808080e19f369c9cc6db1aff35e37923897950227d2a87c95ef0101b2a0233740f2ce00d01

root : 0xa506e7e444fc636360bb593a808f41f126a8813ea71410d4515987eacc594380