python实现Merkle树验证

使用 Merkle树 对链是否合法进行验证

• 呈现少量节点即可证明分支的有效性
  • 任何改变 Merkle 树任何部分的尝试都会导致链上某个地方的不一致
• 每个节点都是其两个子节点的哈希值

import hashlib

# 构建Merkle树
def build_tree(data):
    tree = []
    # 将所有数据块的哈希值存到叶子节点
    for d in data:
        tree.append(hashlib.sha256(d.encode()).hexdigest())
    # 逐层生成父节点
    while len(tree) > 1:
        parent_level = []
        for i in range(0, len(tree), 2):
            # 如果当前节点只有一个子节点，将其复制一遍作为另一个子节点
            if i == len(tree) - 1:
                parent_level.append(tree[i] + tree[i])
            else:
                parent_level.append(tree[i] + tree[i+1])
        # 将当前层的父节点加入树中
        tree = parent_level
    return tree[0]

添加验证数据的完整性的函数

# 验证数据完整性
def validate(hash, data):
    # 如果当前节点是叶子节点，直接与数据块的哈希比较
    if len(hash) == 64:
        return hash == hashlib.sha256(data.encode()).hexdigest()
    # 如果当前节点是父节点，递归验证子节点
    left = hash[0:64]
    right = hash[64:]
    return validate(left, data) or validate(right, data)

主函数中添加

import Merkel_Tree

对 create_blocks 函数进行补充：除了补充注释以外新增了 ret_hash 变量，用于填充 Merkle树 的列表

def create_blocks(block_chains,i):
    print("Input the transaction information for block {}:".format(i))
    # 提示输入交易信息
    
    input_sender = input("Please input the sender:")    #输入发送者
    input_receiver = input("Please input the receiver:")    #输入接收者
    input_amount = input("Please input the amount:")    #输入金额
    
    transaction = {"sender":input_sender,"receiver":input_receiver,"amount":input_amount}
    
    block_chains.append(Block(block_chains[i-1].hash, transaction , datetime.datetime.now()))
    # 前一个区块的哈希，交易信息，时间戳
    
    print("Block {} is created, and the transaction is: {} transfer {} BTC to {}".format(i,input_sender,input_amount,input_receiver))
    print("The hash of block {} is: {}".format(i,block_chains[i].hash))
    ret_hash = block_chains[i].get_hash()
    i += 1
    return block_chains,i,ret_hash

同时对主函数进行扩充：补充了一些注释，同时在初始化中添加了 Merkel树 的初始数据 以及 根节点 。此外，添加了分支选项来进行操作选择，选择内容包括 创建新区块 和 检查区块链的有效性

如果是 创建新区块，每次都要更新 Merkel树 的数据并且再次计算根节点，算出 root 以供验证

if __name__ == '__main__':
    print("Welcome")
    
    #初始化
    i = 1
    block_chains = [Block.create_genesis_block()]
    merkel_data = [block_chains[0].hash]        # 创建 Merkel树 的初始数据
    root_hash = Merkel_Tree.build_tree(merkel_data)     #根节点
    print("Genesis Block is created.Hash is: ",block_chains[0].hash)
    
    while True:
        print("Please choose the operation:")
        print("1.Create a new block")       #创建新区块
        print("2.Check the validity of the chain")   #检查区块链的有效性
		
        #输入选择
        input_choice = input()
        
        if input_choice == "1":
            block_chains,i,ret_hash = create_blocks(block_chains,i)  #创建新区块
            merkel_data.append(ret_hash)     #更新 Merkel树 的数据
            root_hash = Merkel_Tree.build_tree(merkel_data)     #再次计算根节点
        elif input_choice == "2":       #检查区块链的有效性，通过检查最后一个区块的哈希来实现
            if Merkel_Tree.validate(root_hash,merkel_data[-1]):
                print("The chain is valid")
            else:
                print("The chain is invalid")