Merkle Tree及其实现

Merkle Tree简介

Merkle Tree实际上就是 树+Hash,具有树的性质,树的每个节点都是Hash值。Merkle Tree有以下特点:

  1. Merkle Tree可以是二叉树,也可以是多叉树,不管是什么树,它都具有树结构的所有特点。
  2. Merkel Tree的叶子节点的Value是数据集合的单元数据 或 单元数据的Hash值。
  3. Merkel Tree所有非叶子节点的Value是所有子节点Value的Hash值。

Merkle Tree的应用

Merkel Tree多用在数据验证,其中最有名的应用领域可能就属加密货币了。矿机在挖矿实际上就是在运算一组复杂的公式:

SHA256(SHA256(version + prevHash + merkleRoot + time + currentDifficulty + nonce )) < TARGET

这里不必深究公式的意义,只需要关注其中的一个“merkleRoot”参数,这个“merkleRoot”就是Merkle Tree的根节点的值。想要算出根节点的值,必须要从叶子节点出发(在加密货币中,叶子节点通常为各区块内从n个交易提取的n个Hash值),最后由根节点的两个子节点的Hash计算出根节点的Hash。这只是挖矿的一个小环节。

Merkle Tree的实现

  • 使用python语言,用到hashlib
  • 为了简便,这里的Merkle Tree为二叉树
  • 简单的将子节点Hash相加来生成父节点的Hash
  • 假设初始有八个叶子节点,输出结果为二叉树各节点的值
    import hashlib
    
    
    class Merkle():  #Merkle Tree
        Merkle_tree = list([])
        
        def __init__(self, values):  # 将字符串初始化为叶子节点的Hash值
            child_node_start_index = len(values)
            total_length = len(values) * 2 - 1
            sha256 = hashlib.sha256()
            self.Merkle_tree = ["" for i in range(total_length)]
            
            for each in values:
                sha256.update(each.encode('utf-8'))
                self.Merkle_tree[child_node_start_index - 1] = sha256.hexdigest()
                child_node_start_index += 1
            
        def merkel_yourself(self):  # 生成Merkle Tree
            node_index = len(self.Merkle_tree) - 1  # 由叶子节点末尾向前计算非叶子节点的Hash
            sha256 = hashlib.sha256()
            
            while node_index > 0:
                sha256.update(self.Merkle_tree[node_index].encode('utf-8') + self.Merkle_tree[node_index - 1].encode('utf-8'))
                self.Merkle_tree[node_index // 2 - 1] = sha256.hexdigest()
                node_index -= 2
            
        def show_yourself(self):
            for each in self.Merkle_tree:
                print(each)
        
    
    def main():
        values = list([])  # 测试数据
        values.append("azhuge233")
        values.append("332eguhza")
        values.append("second-hand video card")
        values.append("brand-new video card")
        values.append("huge drop for bitcoin")
        values.append("wot i cant trans btc to bch")
        values.append("crypto currency is great")
        values.append("i lost my money but im happy")
        
        tree = Merkle(values=values)
        tree.merkel_yourself()
        tree.show_yourself()
        
    
    if __name__ == "__main__":
        main()
  • 输出(红色框内为根节点,子节点依次向下):测试数据的Hash: