[Deprecated]Darwinia 1.0 Header MMR Spec

Different MMR implementation could diverse in several parts:

• MMR Leaf append

  • The leaf appending to the mmr is parent_hash of current block when on_finalized, the parent_hash type is BlakeTwo256 (type Hashing = ::sp_runtime::traits::BlakeTwo256;)
  • parent_hash is appended as leaf without extra processing such as encoding or hashing

• MMR Merge: How branch parent node are generate from two child node (left_node and right_node)

  • First, left_node and right_node are combined as a tuple (left_node, right_node), this tuple will be encoded using Substrate SCALE before hashing.
  • Second, merge hashing are using BlakeTwo256

pub struct MMRMerge<T>(PhantomData<T>);
impl<T: Trait> merkle_mountain_range::Merge for MMRMerge<T> {
	type Item = <T as frame_system::Trait>::Hash;
	fn merge(lhs: &Self::Item, rhs: &Self::Item) -> Self::Item {
		let encodable = (lhs, rhs);
		<T as frame_system::Trait>::Hashing::hash_of(&encodable)
	}
}

• MMR Peak Bagging: How peaks get bagged before hashing to mmr root

fn bag_rhs_peaks(&self, mut rhs_peaks: Vec<T>) -> Result<Option<T>> {
        while rhs_peaks.len() > 1 {
            let right_peak = rhs_peaks.pop().expect("pop");
            let left_peak = rhs_peaks.pop().expect("pop");
            rhs_peaks.push(M::merge(&right_peak, &left_peak));
        }
        Ok(rhs_peaks.pop())
    }

rhs_peaks here are retrieved by get_peaks from left peak to right. rhs means right hand side.

So if the peaks are [p1, p2, p3, p4, p5], the root will be MMRMerge(MMRMerge(MMRMerge(MMRMerge(p5, p4), p3), p2), p1)

merge(p5,p4) = hashing(scale_encode((p5, p4)))

At last, for testing, here is some sample data written in rust in header mmr module, which can be used as reference.

https://github.com/darwinia-network/darwinia-common/pull/160/files#diff-77027da666100e67f10cf24c60c249beR87

Here is some mmr implemented in solidity from @WoeOm, which might need modification to follow this spec doc.

https://github.com/WoeOm/darwinia-ethereum-relay