用python代码实现Merkle树

Merkle树，也称为哈希树或散列树，是一种数据结构，用于验证大量数据的完整性。它的每个节点都是由其下级节点的哈希值计算得出的，最顶层的根节点包含了所有数据的摘要信息。在Python中，我们可以使用内置的hashlib模块来实现Merkle树。以下是一个简单的Merkle Tree的构建和验证示例：

import hashlib

class Node:
    def __init__(self, value=None):
        self.value = value
        self.left = None
        self.right = None

def hash_value(value):
    return hashlib.sha256(value.encode()).hexdigest()

def create_merkle_tree(values):
    if len(values) == 0:
        return None

    nodes = [Node(value) for value in values]
    while len(nodes) > 1:
        new_nodes = []
        for i in range(0, len(nodes), 2):
            left = nodes[i] if i+1 < len(nodes) else None
            right = nodes[i+1] if i+2 < len(nodes) else None
            combined_value = hash_value(left.value + (right.value if right else ''))
            new_node = Node(combined_value)
            new_node.left = left
            new_node.right = right
            new_nodes.append(new_node)

        nodes = new_nodes

    return nodes[0]

# 示例数据
data = ['a', 'b', 'c', 'd']

root = create_merkle_tree(data)

# 验证
def verify_data(root, data):
    current_node = root
    for value in reversed(data):
        combined_value = hash_value(current_node.value + value)
        if hash_value(combined_value) != current_node.value:
            return False
        current_node = Node(combined_value)

    return True

verified = verify_data(root, data)
print(f"Data verified: {verified}")

在这个例子中，我们首先创建了一个`Node`类，然后定义了`hash_value`函数用于计算哈希。`create_merkle_tree`函数递归地合并节点直到只剩下一个，这就是根节点。`verify_data`函数则从根节点开始逐层对比原始数据的哈希值。