Implement transaction Merkle proof in Solidity and add tests

[alex-miller-0]

Background: A relay system has two contracts (one on each of two chains), which have mappings between pairs of tokens. A user with a given token may deposit it into the relay contract on that chain and withdraw its copy on the other chain. The withdrawal is a two step process, with the first part being the formation of a Merkle proof to show the transaction (deposit) was in the transaction tree. This issue only covers this first part.

The function prepWithdrawal in Relay.sol takes a set of parameters (token, fromChain, and amount) and forms a transaction. It uses this transaction to make a Merkle proof that it was included in a given transaction root in withdraw. I am having trouble reconstructing the transaction and forming the proof -- this is where you come in!

To claim the bounty:

1. Rewrite the prepWithdraw, withdraw, and merkleProof Solidity functions to perform a proper Merkle proof. Use the parameters token, fromChain, and amount to form the transaction data that goes into making the proof. You can pass the transaction root from a given block into the function and match it with the proof.
2. Add test(s) to relay.js using this functionality. At a minimum, it should a) make the deposit to get the transaction hash, b) get the block from the transaction hash and make the Merkle proof in Javascript, c) pass the relevant data to Solidity to make the same proof.
3. Be concise with your Solidity functions. We want the user to pay as little gas as possible and for the contract to take as little gas as possible to deploy. For example, if you don't need to RLP encode data in Solidity and you can do it in Javascript instead, push that functionality out to the tests.
4. Document everything you write. If something is non-obvious, please explain your thinking - there is no such thing as too many comments!

These repos may help:

https://github.com/ConsenSys/rb-relay

https://github.com/ethereumjs/merkle-patricia-tree

https://github.com/zmitton/eth-proof

[gitcoinbot]

This issue now has a funding of 0.74 ETH (875.79 USD) attached to it.

• If you would like to work on this issue you can claim it here.
• If you've completed this issue and want to claim the bounty you can do so here
• Questions? Get help on the Gitcoin Slack
• $17799.74 more Funded OSS Work Available at: https://gitcoin.co/explorer

[subramanianv]

Hi @alex-miller-0 I would like to work on this issue. Let me clone the repo and get everything setup

[subramanianv]

So from my understanding so far, We need to construct the deposit function transaction that happened on the other chain and verify its merkle proof using the data passed in the arguments to prepWithdraw

[alex-miller-0]

@subramanianv correct. You need to form the raw transaction (ideally in assembly) using the amount, fromChain, and token parameters and verify it using a Merkle proof. If that proof works, you store the transaction root hash and other parameters as a pendingWithdrawal for the user.

[subramanianv]

Transaction hashes are stored on the leaves of the Patricia Merkle Trees. I think we are missing 1 step here. The raw transaction has to be rlpencoded and sha3 hashed. Then sent to the MerklePatriciaProof.verify function. RLPEncoding and Sha3 hashing in the prepWithdrawal function is missing

[alex-miller-0]

That was my thought as well, but I couldn't reproduce the root.

The existing (unfinished) implementation basically replicates this function, but instead of passing the raw transaction as an input, we are reconstructing it from a parameter set. This test from the same repo shows how you can get the path and parentNodes using eth-proof

[subramanianv]

@alex-miller-0 MerklePatriciaProof.verify takes in the hash. The constructed transaction from the input has to rlp-encoded and keccak256 and that has to passed into the verify function. The input to https://github.com/ConsenSys/rb-relay/blob/master/contracts/rbrelay.sol#L112 has to rlp encoded

[subramanianv]

I am looking at this file https://github.com/ConsenSys/rb-relay/blob/master/contracts/RLPEncode.sol to find out how to do rlp encoding in solidity

[alex-miller-0]

Right, you know the root hash ahead of time (we don't need to form that root in prepWithdraw), but rawTx is the entire transaction payload, which goes to verify as a bytes array. If you run the test in rb-relay you can look at what the rawTx is before it's passed to Solidity.

[subramanianv]

The raw Tx is for eg: var rawTx = { nonce: web3.toHex(0), gasPrice: web3.toHex(20000000000), gasLimit: web3.toHex(100000), to: '0x687422eEA2cB73B5d3e242bA5456b782919AFc85', value: web3.toHex(1000), data: '0xc0de', v : , r: , s: , };

This has to be rlp-encoded as shown in this function Am I right ?

[subramanianv]

@alex-miller-0 Is the transaction payload already rlp-encoded ?

[HarryR]

@subramanianv yes the payload is RLP encoded

https://github.com/ConsenSys/ethjsonrpc/blob/master/ethjsonrpc/client.py#L116

In python the arguments are encoded using from ethereum.abi import encode_abi

[owocki]

@subramanianv @alex-miller-0 is it ok if subramanian claims this issue on gitcoin? just want to work out early who's gonna birddog it !

[alex-miller-0]

@owocki Sure that's fine. Do I need to do anything on my side?

[owocki]

nope @subramanianv pls just claim on gitcoin!

[subramanianv]

@owocki I did. Here is the transaction https://etherscan.io/tx/0x2934cc6c92cb2a1ad8a1c0c70a5caafb8a38a5294c7b122123e265ef778437be I dont see anything on the gitcoin website about this claim

[gitcoinbot]

The funding of 0.74 ETH (930.78 USD) attached has been claimed by @subramanianv.

@subramanianv, please leave a comment to let the funder (@alex-miller-0) and the other parties involved your implementation plan. If you don't leave a comment, the funder may expire your claim at their discretion.

• Learn more on the gitcoin issue page
• Questions? Get help on the Gitcoin Slack
• $19540.13 more Funded OSS Work Available at: https://gitcoin.co/explorer

[owocki]

@subramanianv processsed now.. thanks for your patience.. https://gitcoin.co/funding/details?url=https://github.com/GridPlus/trustless-relay/issues/1

@alex-miller-0 have a great vacation.. and see you after!

[subramanianv]

@alex-miller-0 @HarryR The nonce, gasPrice, gasLimit, etc can be up to 32 bytes in length and not always 32 bytes. So we cannot (mstore(tx, mload(add(txParams, 0x20))) 32 bytes all the time. We need to pass in the length of the nonce, etc. Any comments on how to refactor the function ?

[alex-miller-0]

@subramanianv Sorry I've been away and will have spotty internet for a few more days.

Any method to extract chunks of data from a bytes array is okay. I actually don't know assembly in Solidity very well -- the original block was basically just pseudocode.

@GNSPS has a library that copies bytes in assembly so you may want to look at that: https://github.com/GNSPS/solidity-bytes-utils

[subramanianv]

@alex-miller-0 I am working on a PR. Will update you shortly

[vs77bb]

@subramanianv @alex-miller-0 🍿 🙂 cc @owocki

[subramanianv]

@alex-miller-0 I made an PR for initial Review.

[alex-miller-0]

Thanks. Commented.

[vs77bb]

@subramanianv Is this in your hands right now? CC @owocki

[alex-miller-0]

I'm going to close this as it expired a while ago. I think I made this too hard for a 1 week bounty. I eventually figured it out myself, but it took a while. Will scope these better in the future.

[gitcoinbot]

The funding of 0.74 ETH (605.59 USD) attached to this issue has been approved & issued to @subramanianv.

• Learn more at on the gitcoin issue page
• Questions? Get help on the Gitcoin Slack
• $7820.28 more Funded OSS Work Available at: https://gitcoin.co/explorer

[abdelshok]

@alex-miller-0 Apologies if this is reopening the issue but here I am, 5 years later, reading this thread to understand areas previously confusing relating to Merkle Tree proofs and hash verification. Thank you for keeping this conversation public. :)