search

harmony-one / horizon

Horizon - a trustless harmony to ethereum bridge
MIT License
36 stars 29 forks source link

merge LayerZero MPT library and add unit test #35

Closed peekpi closed 2 years ago

peekpi commented 2 years ago

resolve #28

Layer Zero improvements

Layer Zero uses the key index instead of the original proof key. for example, if an MPT has 2 elements, its proof key is "abc0" and "abc1". The proof data of the elements would be :

  1. ExtensionNode： ['abc', hash of next layer]
  2. BranchNode: [hash0, hash1, ...]
  3. LeafNode: ['', element]

To prove an element in the MPT, it requires the proof data and mpt-key 'abc0' or 'abc1'. according to the mpt-key, assume it is 'abc0', it selects:

  1. the second element from the ExtensionNode. (check and consume key 'abc')
  2. the first element from the BranchNode. (consume remain key '0')
  3. the second element from the LeafNode.

so the select indexes is [1,0,1]. Layer Zero uses the indexes instead of the original key 'abc0'

Further optimization

I also made further optimizations to LayerZero's library.

1. Change the type of mpt-key from unit[] to unit

In our project, mpt-key is the index of tx or receipt. the length of the mpt-key for 1000000 is 8, so we can encode a mpt-key to a uint256 value.

2. Use rlp to encode the proof data

The bytes or array encoded by SolidityABI are 32-byte aligned(both data and data size), using rlp encoding can save more gas and storage.

3. Avoid data coping

Avoid data copying during verifying proofs.

Gas

After optimization gas is reduced by 37-50%. validateProofOptimize validateProof verifyTrieProof validateMPTProof
43432 51321 80354 76624
71866 79749 119583 113455
57021 69711 113982 110083

Unit test

run npx hardhat test test/MPT.test.js

gupadhyaya commented 2 years ago

@peekpi the numbers look great. can you also migrate EthereumProver and HarmonyProver to use the validateProofOptimize?

peekpi commented 2 years ago

@peekpi the numbers look great. can you also migrate EthereumProver and HarmonyProver to use the validateProofOptimize?

migrated. but should we keep the other 2 MPT libraries?

peekpi commented 2 years ago

The changes look good in principle. I haven't gone through all the details of the new implementation for MPT verification. Would it be possible to have it in the tests to show the new implementation is equivalent to the old ones using multiple examples, for both success and failure cases? Also, can we mark the deprecated implementations in comments (ones that are no longer used by any contract or javascript calls except for equivalency verification)?

In the previous commit, there are unit tests to check all the MTP libraries, but only success cases. run npx hardhat test test/MPT.test.js.

brucdarc commented 2 years ago

How does the CLI run after these changes? Do the map and cross commands execute successfully?

peekpi commented 2 years ago

How does the CLI run after these changes? Do the map and cross commands execute successfully?

I haven't tested the cli yet, but the corresponding scripts have been modified and adapted. And the CLI script does not match well because the contract has been modified so much(especially TokenLockerOnEthereum).

brucdarc commented 2 years ago

@peekpi I've been getting some mismatched transaction proofs using the txProof.js file, if I could bother you could you take a look at it sometime? I believe Ganesha has requested to add you to a telegram group where I explain the issue in detail. I've used both the version in the main branch as well as your updated version in this branch and the issue still persists. Tx hash is 0x95f6998ff7c767a0b0d2f2cef4e6975cd5b9d3177dbee35f7b15e54e782ec688 on ropsten. Again, more details in the telegram chat, it would be greatly appreciated because this is currently blocking me from writing tests for https://github.com/harmony-one/horizon/pull/36!

peekpi commented 2 years ago

@peekpi I've been getting some mismatched transaction proofs using the txProof.js file, if I could bother you could you take a look at it sometime? I believe Ganesha has requested to add you to a telegram group where I explain the issue in detail. I've used both the version in the main branch as well as your updated version in this branch and the issue still persists. Tx hash is 0x95f6998ff7c767a0b0d2f2cef4e6975cd5b9d3177dbee35f7b15e54e782ec688 on ropsten. Again, more details in the telegram chat, it would be greatly appreciated because this is currently blocking me from writing tests for #36!

it's because EIP-2718(https://eips.ethereum.org/EIPS/eip-2718#receipts), the struct of the receipt changed a little. both contract and js script should be fixed.

peekpi commented 2 years ago

@peekpi I've been getting some mismatched transaction proofs using the txProof.js file, if I could bother you could you take a look at it sometime? I believe Ganesha has requested to add you to a telegram group where I explain the issue in detail. I've used both the version in the main branch as well as your updated version in this branch and the issue still persists. Tx hash is 0x95f6998ff7c767a0b0d2f2cef4e6975cd5b9d3177dbee35f7b15e54e782ec688 on ropsten. Again, more details in the telegram chat, it would be greatly appreciated because this is currently blocking me from writing tests for #36!

fixed, try it again.

brucdarc commented 2 years ago

That seems to have fixed it, thanks! I'll work on updating my implementation to work with these changes now.