Mmr hardfork

[peekpi]

Issue

Resolve MMR hardfork, #3872.

Brief

MMR is a series of perfect Merkle trees, from high to low. Each Merkle tree root we call it peak. Concat all peak hash and hash it, will get MMR root hash.

When we build MMR with some leaves, we create the first perfect Merkle tree and let it include as many leaves as possible. and then make the second perfect Merkle tree on the remaining leaves, same rules. repeat it until all leaves in the MMR.

When a new leaf is appended, these Merkle tree is recursively merged from back to front. All nodes in MMR are written to the file in post-order traversal order.

Changes:

1. move MMR code to core/blockchain_mmr.go
2. verify MMRRoot of the block header in the engine.VerifyHeader()
3. store MMR database into dir RootDir/mmr_db_${shard}
4. add a cmd boolean flag to enable MMR file database, if it is false, the MMR would not store in the file database(no additional disk usage, also can not provide historical epoch MMR proof).
5. add RWLock
6. add init and quit logic

Enable MMR file database

1. in cmd line add --mmrDB
2. or in config file:

[General]
  MmrDBEnable = true

Test

Test/Run Logs

test it on localnet, all nodes are synchronized properly.

[peekpi]

Other TODO optimization points:

1. In the current scheme, MMR can only prove block hashes. To prove a receipt, it also needs to provide the block header, then get receiptsRoot from the header. If we add receiptsRoot to the MMR, we can omit the block header.
2. The verification of MMR proof is complicated. To optimize it, we can sort the child nodes when calculating the parent hash, so we don't need to know whether it's a left child or a right child when verifying the proof. This is also what OpenZeppelin does.

[gupadhyaya]

@rlan35 @LeoHChen @MaxMustermann2 could you guys help with review of this PR?

[rlan35]

Other optimization points:

1. In the current scheme, MMR can only prove block hashes. To prove a receipt, it also needs to provide the block header, then get receiptsRoot from the header. If we add receiptsRoot to the MMR, we can omit the block header.
2. The verification of MMR proof is complicated. To optimize it, we can sort the child nodes when calculating the parent hash, so we don't need to know whether it's a left child or a right child when verifying the proof. This is also what OpenZeppelin does.

Do these optimization need hard fork? If yes, we better do it now.

[peekpi]

Other optimization points:

1. In the current scheme, MMR can only prove block hashes. To prove a receipt, it also needs to provide the block header, then get receiptsRoot from the header. If we add receiptsRoot to the MMR, we can omit the block header.
2. The verification of MMR proof is complicated. To optimize it, we can sort the child nodes when calculating the parent hash, so we don't need to know whether it's a left child or a right child when verifying the proof. This is also what OpenZeppelin does.

Do these optimization need hard fork? If yes, we better do it now.

yeah, it needs hard fork. this optimization also needs to do more tests, both go and smart contract. How about we create another pr to do it? we can just merge this pr, but do not enable the feature until the optimization is done.

[gupadhyaya]

Other optimization points:

1. In the current scheme, MMR can only prove block hashes. To prove a receipt, it also needs to provide the block header, then get receiptsRoot from the header. If we add receiptsRoot to the MMR, we can omit the block header.
2. The verification of MMR proof is complicated. To optimize it, we can sort the child nodes when calculating the parent hash, so we don't need to know whether it's a left child or a right child when verifying the proof. This is also what OpenZeppelin does.

@peekpi since these optimizations break the MMRVerifier smart contract in the horizon repo, could you also make a PR there to correctly verify these changes? https://github.com/harmony-one/horizon/blob/main/contracts/lib/MMRVerifier.sol

[peekpi]

@peekpi since these optimizations break the MMRVerifier smart contract in the horizon repo, could you also make a PR there to correctly verify these changes? https://github.com/harmony-one/horizon/blob/main/contracts/lib/MMRVerifier.sol

these optimizations are only my ideas and not have been done in this PR, but I think it can significantly reduce the gas cost. of course, I’ll also change the horizon contract to match the optimizations.