[学习笔记]Merkle Tree go语言实现

梅克尔树的结构比较简单，其设计思想比较巧妙，它是SPV实现的关键。
梅克尔树是二叉树，节点存储哈希指针，叶子节点保存数据。

1. Merkle Tree节点结构体

type MerkleNode struct {
    Left *MerkleNode
    Right *MerkleNode
    Data []byte
}

2. 创建Merkle Tree节点

func NewMerkleNode(left,right *MerkleNode, data []byte) *MerkleNode {
    mNode := MerkleNode{}

    if left == nil && right == nil {
        hash := sha256.Sum256(data)
        mNode.Data = hash[:]
    }else {
        prevHashes := append(left.Data,right.Data...)
        hash := sha256.Sum256(prevHashes)
        mNode.Data = hash[:]
    }

    mNode.Left = left
    mNode.Right = right

    return &mNode
}

3. 构建Merkle Tree

func NewMerkleTree(data [][]byte) *MerkleTree  {
    var nodes []MerkleNode

    if len(data) % 2 != 0 {
        data = append(data, data[len(data) - 1])
    }

    for _, dataitem := range data {
        node := NewMerkleNode(nil, nil, dataitem)
        nodes = append(nodes, *node)        
    }

    for i := 0; i<len(data)/2; i++ {
        var newNodes []MerkleNode

        for j := 0; j < len(nodes); j += 2 {
            node := NewMerkleNode(&nodes[j], &nodes[j+1], nil)
            newNodes = append(newNodes , *node)
        }

        nodes = newNodes 
    }

    mTree := MerkleTree{&nodes[0]}

    return &mTree
}