上期回顾
代码实现
示意图
Root Hash (H1)
/ \
Hash (H2) Hash (H3)
/ \ / \
Hash (H4) Hash (H5) Hash (H6) Hash (H7)
/ \ / \ / \ / \
Data1 Data2 Data3 Data4 Data5 Data6 Data7 Data8
## 图中的Data1表示Data1的哈希值
使用Python实现
import hashlib
# 用来保存层层hash过程中产生的hash array
hashed_array = []
# 计算数据的哈希值
def calculate_hash(data):
return hashlib.sha256(data.encode()).hexdigest()
# 构建默克尔树
def build_merkle_tree(hashed_data_list):
if len(hashed_data_list) == 1:
return hashed_data_list[0]
new_data_list = []
for i in range(0, len(hashed_data_list), 2):
if i + 1 < len(hashed_data_list):
new_data_list.append(calculate_hash(hashed_data_list[i] + hashed_data_list[i + 1]))
else:
# 如果数据列表长度为奇数,最后两个数据保持一致
new_data_list.append(calculate_hash(hashed_data_list[i] + hashed_data_list[i]))
hashed_array.append(new_data_list)
return build_merkle_tree(new_data_list)
# 验证默克尔树的有效性
def verify_merkle_tree(root_hash, leaf_hash, merkle_path):
current_hash = leaf_hash
for sibling_hash in merkle_path:
if sibling_hash[0] == 'L':
current_hash = calculate_hash(sibling_hash[1:] + current_hash)
else:
current_hash = calculate_hash(current_hash + sibling_hash[1:])
return current_hash == root_hash
运行:
# 示例数据
data_list = ["Data1", "Data2", "Data3", "Data4", "Data5", "Data6", "Data7", "Data8"]
# 构建默克尔树
merkle_root = build_merkle_tree([calculate_hash(data) for data in data_list])
print("Merkle Root:", merkle_root)
print("All Hashed:", hashed_array)
=================
Merkle Root: d782faebfd951af2a2414b6c4620a9efe4a67446e8ad651624cd6c9c5ea1e5aa
All Hashed: [
['cf0b9cdb1edeadabb048527c9bb9397df128750d14b1edd99f3e02f68710bb97', '66ef77b9b7e40dff5ec301805213cc0f4a5c415439f71e2eebef87705c909971', '1a12e1ca904a8a5640834f86dd292f65c13a7a4c91dc3be03d485cb9e012108f', '16b0e1acdf8fb7738ef213106be8024a3a3bcb0a74aba89b25d20095b549cff1'], ['2450d8c5928639a51a7a7ff2b8cbbe0044d06cf82551617ec4e81ec3d8873331', '9052142b14bbbe41f7a484d87e071dffd07463f8c6fabad5ea308f8bcb72b996'], ['d782faebfd951af2a2414b6c4620a9efe4a67446e8ad651624cd6c9c5ea1e5aa']]
验证叶子节点有效性
路径分析
[Root Hash (H1)]
/ \
Hash (H2) [Hash (H3)]
/ \ / \
[Hash (H4)] Hash (H5) Hash (H6) Hash (H7)
/ \ / \ / \ / \
Data1 Data2 [Data3] [Data4] Data5 Data6 Data7 Data8
## [] 代表验证Data3所需要知道的merkle路径
代码实现
# 验证叶子节点的有效性
data3_index = 2
data3_hash = calculate_hash(data_list[data3_index])
merkle_path = ['R' + calculate_hash(data_list[3]), 'L' + hashed_array[0][0], 'R' + hashed_array[1][1]]
print("Leaf Hash:", data3_hash)
print("Merkle Path:", merkle_path)
print("Is Valid:", verify_merkle_tree(merkle_root, data3_hash, merkle_path))
========================
Leaf Hash: 72e667e0d1ecab7fbccd927e3436b0a2a913015ff702f4ea80a4135ca3c8eb3e
# 路径有左右之分,所有第一个字母R表示路径在待验证节点的右边,L表示路径在待验证节点的左边
Merkle Path: ['R1834d0c44c3680eca266c8d03ed6857c9955e4349327e08430b5e02f8466afcb', 'Lcf0b9cdb1edeadabb048527c9bb9397df128750d14b1edd99f3e02f68710bb97', 'R9052142b14bbbe41f7a484d87e071dffd07463f8c6fabad5ea308f8bcb72b996']
Is Valid: True