認識MMR(Merkle Mountain Range)

MMR是什么

merkle tree一種二叉樹也是區(qū)塊鏈中一種常見的數(shù)據(jù)結(jié)構(gòu)，其特性就是樹的根及中間節(jié)點主要是由其左右子樹的Hash構(gòu)成累舷。Parent = H(0,1)蝇摸，其以密碼學保證其安全性，以相同順序插入才能計算出最終一致的樹根捌袜。

Merkle tree

而mmr(Merkle Mountain Range)是Peter Todd提出的一種Merkle tree说搅，長相類似一組連續(xù)的山峰組成，其被設(shè)計為節(jié)點插入后就不能被修改虏等，支持動態(tài)插入弄唧。

MMR(Merkle Mountain Range)

對于普通Merkle樹對于每個新加入節(jié)點都需要重新計算merkle root,如果節(jié)點數(shù)量很大的話這個計算量會非常巨大，而mmr支持動態(tài)加入新節(jié)點并計算root霍衫。

MMR的組成

mmr構(gòu)造

上圖mmr包含了3個葉子節(jié)點,葉子節(jié)點的插入順序就是葉子節(jié)點的標識(節(jié)點的存儲位置)候引，插入節(jié)點1后由于出現(xiàn)相同高度的樹,則將節(jié)點0，1合并(2 = merge(0,1))生成父節(jié)點2,然后再插入節(jié)點3由于高度不一一致,無需樹的合并敦跌，最后生成如圖所示的MMR澄干。

由上圖可以發(fā)現(xiàn)，以存儲索引位置作為其坐標的二叉樹柠傍，都有左子樹與父節(jié)點的距離(offset)為offset=2^Height,兄弟節(jié)點之間的距離為offset=2^Height - 1,這樣就可以計算出任意節(jié)點的兄弟節(jié)點與父節(jié)點的坐標麸俘。

另外如果我們能夠計算出任意節(jié)點的高度，我們就能計算出任意節(jié)點的父節(jié)點及兄弟節(jié)點的坐標了惧笛，將節(jié)點坐標從1開始并以二進制來表示从媚。如圖：

坐標為二進制表示的mmr

任意高度的最左側(cè)節(jié)點的1的數(shù)量就是其高度，由于最左側(cè)子樹每次合并右子樹生成父節(jié)點增加高度徐紧，實際上是左節(jié)點坐標n計算出父節(jié)點坐標n<<1 + 1静檬，這樣計算任意節(jié)點的高度就可以表示為將節(jié)點向最左側(cè)移動，即當其坐標全為1時并级，其數(shù)量就時其高度拂檩。如下代碼獲取任意坐標的所在高度：

func countZore(num uint64) int {
    return bits.UintSize - bits.OnesCount64(num)
}
func leadingZeros(num uint64) int {
    return bits.LeadingZeros64(num)
}
func allOnes(num uint64) bool {
    return num != 0 && countZore(num) == leadingZeros(num)
}
func jumpLeft(pos uint64) uint64 {
    bitLength := 64 - leadingZeros(pos)
    mostSignificantBits := uint64(1) << uint64(bitLength-1)
    return pos - (mostSignificantBits - 1)
}
func pos_height_in_tree(pos uint64) int {
    pos += 1
    for !allOnes(pos) {
        pos = jumpLeft(pos)
    }
    return 64 - leadingZeros(pos) - 1
}

現(xiàn)在我們可以順序追加節(jié)點了，我們只需要判斷下一個節(jié)點的高度嘲碧，如果大于當前高度則需要合并左右子樹稻励，方法如下:

func (m *mmr) append(n *Node) *Node {
    height, pos := 0, m.cur_size
    n.index = pos
    m.values = append(m.values, n)
    for pos_height_in_tree(pos+1) > height {
        pos++
        // calculate pos of left child and right child
        left_pos := pos - parent_offset(height)
        right_pos := left_pos + sibling_offset(height)
        left, right := m.values[left_pos], m.values[right_pos]
        parent := &Node{index: pos}
        merge(parent, left, right)
        m.values = append(m.values, parent)
        height++
    }
    m.cur_size = pos + 1
    return n
}

MMR的證明

由圖2可以知道，MMR可能會有多個山峰愈涩，而MMR的root是由最右側(cè)的山峰依次向左合并望抽，直到最后形成root,這個操作也被稱為山峰的拱起操作。圖2中的root=Hash(Hash(18,17),14)履婉。

MMR的root是由山峰的拱起得到,那么最左側(cè)的山峰一定一個完全的二叉樹,節(jié)點數(shù)量為2^Height - 1煤篙，由此我們可以在固定節(jié)點數(shù)量下(Count)不斷嘗試左側(cè)山峰的高度,找到2^Height - 1 < Count的最大的樹，如下:

func left_peak_pos_by_height(height int) uint64 {
        // -2 表示獲取從0開始的山峰的坐標
    return (uint64(1) << uint64(height+1)) - 2
}
func left_peak_height_pos(mmrSize uint64) (int, uint64) {
    height := 0
    prev_pos := uint64(0)
    pos := left_peak_pos_by_height(height)
    //不斷增加山峰的高度毁腿，直到最后一次山峰的坐標超過節(jié)點總數(shù)
    for pos < mmrSize {
        height += 1
        prev_pos = pos
        pos = left_peak_pos_by_height(height)
    }
    return height - 1, prev_pos
}

在計算出左側(cè)山峰后辑奈，可以以此為坐標苛茂，依次計算出右側(cè)的所有山峰，如下:

func get_right_peak(height int, peakPos, mmrSize uint64) (int, uint64) {
    //jump to right sibling
    peakPos += sibling_offset(height)
    //jump to left child
    for {
        if peakPos <= mmrSize-1 {
            break
        }
        if height == 0 {
            //no right peak exists
            return height, 0
        }
        height -= 1
        peakPos -= parent_offset(height)
    }
    return height, peakPos
}
func get_peaks(mmrSize uint64) []uint64 {
    res := make([]uint64, 0, 0)
    height, pos := left_peak_height_pos(mmrSize)
    res = append(res, pos)
    for height > 0 {
        height, pos = get_right_peak(height, pos, mmrSize)
        if height == 0 && pos == 0 {
            break
        }
        res = append(res, pos)
    }
    return res
}

獲取到所有山峰后鸠窗，就可以對所有山峰妓羊，由左到右依次拱起，最后得到MMR的root稍计。如下:

func (m *mmr) getRoot() Hash {
    if m.cur_size == 0 {
        return Hash{0}
    }
    if m.cur_size == 1 {
        return m.values[0].getHash()
    }
    return m.bag_rhs_peaks(0, get_peaks(m.cur_size))
}
func (m *mmr) bag_rhs_peaks(pos uint64, peaks []uint64) Hash {
    rhs_peak_hashes := make([]Hash, 0, 0)
    for _, v := range peaks {
        if v > pos {
            rhs_peak_hashes = append(rhs_peak_hashes, m.values[v].getHash())
        }
    }
    for len(rhs_peak_hashes) > 1 {
        last := len(rhs_peak_hashes) - 1
        right := rhs_peak_hashes[last]
        rhs_peak_hashes = rhs_peak_hashes[:last]
        last = len(rhs_peak_hashes) - 1
        left := rhs_peak_hashes[last]
        rhs_peak_hashes = rhs_peak_hashes[:last]
        rhs_peak_hashes = append(rhs_peak_hashes, merge2(right, left))
    }
    if len(rhs_peak_hashes) == 1 {
        return rhs_peak_hashes[0]
    } else {
        return Hash{0}
    }
}

merkle proof

構(gòu)造葉子節(jié)點的 merkle proof躁绸，分三個步驟：

構(gòu)造該葉子到山峰的proof
將右側(cè)的山峰加入proof
將左側(cè)的山峰從右到左加入proof.

如下:

func (m *mmr) gen_proof(pos uint64) *MerkleProof {
    proofs := make([]Hash, 0, 0)
    height := 0
    for pos < m.cur_size {
        pos_height, next_height := pos_height_in_tree(pos), pos_height_in_tree(pos+1)
        if next_height > pos_height {
            // get left child sib
            sib_pos := pos - sibling_offset(height)
            // break if sib is out of mmr
            if sib_pos >= m.cur_size {
                break
            }
            proofs = append(proofs, m.values[sib_pos].getHash())
            // goto parent node
            pos = pos + 1
        } else {
            // get right child
            sib_pos := pos + sibling_offset(height)
            // break if sib is out of mmr
            if sib_pos >= m.cur_size {
                break
            }
            proofs = append(proofs, m.values[sib_pos].getHash())
            // goto parent node
            next_pos := pos + parent_offset(height)
            pos = next_pos
        }
        height += 1
    }
    // now pos is peak of the mountain(because pos can't find a sibling)
    peak_pos := pos
    peaks := get_peaks(m.cur_size)
    // bagging rhs peaks into one hash
    rhs_peak_hash := m.bag_rhs_peaks(peak_pos, peaks)
    if !equal_hash(rhs_peak_hash, Hash{0}) {
        proofs = append(proofs, rhs_peak_hash)
    }
    // put left peaks to proof
    for i := len(peaks) - 1; i >= 0; i-- {
        p := peaks[i]
        if p < pos {
            proofs = append(proofs, m.values[p].getHash())
        }
    }
    return newMerkleProof(m.cur_size, proofs)
}

merkle verify

proof的驗證，以相同的順序重新計算Merkle Root就可以臣嚣，如下:

func (m *MerkleProof) verify(root Hash, pos uint64, leaf_hash Hash) bool {
    peaks := get_peaks(m.mmrSize)
    height := 0
    for _, proof := range m.proofs {
        // verify bagging peaks
        if pos_in_peaks(pos, peaks) {
            if pos == peaks[len(peaks)-1] {
                leaf_hash = merge2(leaf_hash, proof)
            } else {
                leaf_hash = merge2(proof, leaf_hash)
                pos = peaks[len(peaks)-1]
            }
            continue
        }
        // verify merkle path
        pos_height, next_height := pos_height_in_tree(pos), pos_height_in_tree(pos+1)
        if next_height > pos_height {
            // we are in right child
            leaf_hash = merge2(proof, leaf_hash)
            pos += 1
        } else {
            leaf_hash = merge2(leaf_hash, proof)
            pos += parent_offset(height)
        }
        height += 1
    }
    return equal_hash(leaf_hash, root)
}

MMR的作用

MMR可以極大的減少merkle證明的數(shù)據(jù)量净刮，可以大幅度的減輕存儲和網(wǎng)絡(luò)的負擔，提升驗證效率茧球，目前Open timestamp 和 Grin 等項目及Fly client的論文中都使用了MMR的證明庭瑰。