[Deprecated] Darwinia 1.0 Ethereum Header MMR Spec

Ethereum does not describe the detail spec related to MMR struct, so we need to define them for the eth relay we will develop.

There are basically several parts need define:

• Hashing Algorithm type Hashing: Hash<Output = Self::Hash>;

type Hashing = BlakeTwo256; pub type Hash = sp_core::H256; Note: For easier library reuse and less developement effort considerations, only befinifit to the MMR related functions for those chains that are does not have MMR included in header.

• Leaf Append If the value(Ethereum Header Hash) is already H256, then directly append as leaf, if not, hashing to H256 using Hashing Algorithm.

• Branch Merge

Using MMR Merge same with Darwinia Header MMR Spec:

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)
	}
}

Note: (lhs, rhs) is encoded in SCALE codec before hasing.

• Root's child peaks bagging Using same bagging algorithm with Darwinia Header MMR Spec:

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())
    }

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

Related Issues

#163