search

darwinia-network / darwinia-messages-sol

Darwinia cross-chain messages gateway and protocol for EVM developers 💌
MIT License
29 stars 8 forks source link

Using incremental Merkle tree algorithm in message commitment. #150

Closed hujw77 closed 2 years ago

hujw77 commented 2 years ago

Improvement

To reduce both time and space complexities, thus saving the gas cost significantly, Eth2.0 deposit contract implements an incremental Merkle tree algorithm. The incremental algorithm enjoys O(h) time and space complexities to reconstruct (more precisely, compute the root of) a Merkle tree of height h, while a naive algorithm would require O(2^h) time or space complexity.

Naive algorithm

https://github.com/darwinia-network/darwinia-bridges-sol/blob/3d6c6d32f758dfe045ce7121907e9361caa26c40/contracts/bridge/src/truth/darwinia/ChainMessageCommitter.sol#L51

Incremental Merkle tree algorithm

https://github.com/ethereum/research/blob/master/beacon_chain_impl/progressive_merkle_tree.py https://etherscan.io/address/0x00000000219ab540356cbb839cbe05303d7705fa#code

hujw77 commented 2 years ago

Because of Incremental Merkle tree algorithm is only supported incremental value, but committer's all leaves is always change. thus the algorithm is not applicable for message committer.