比特币Merkle Root计算结果不符，求排查代码问题

我正在学习比特币，参考比特币协议文档中Merkle Trees相关内容后，用Python实现了Merkle Root计算逻辑。通过区块链API获取区块641150的所有交易，计算出的Merkle Root值为f2a2207a1e8360b75729fd2f23659b1b79b14940b6e4982a985cf6aa6f941ad7，但区块641150页面显示的预期值为67a637b1c49d95165b3dd3177033adbbbc880f6da3620498d451ee0976d7b1f4，两者不符。

我的实现代码 #

from hashlib import sha256
import requests, json

base_url = 'https://blockchain.info/rawblock/'
block_hash = '000000000000000000042cef688cf40b4a70ac814e4222e6646bd6bb79d18168'
end_point = base_url + block_hash

def reverse(hex_be):
    bytes_be = bytes.fromhex(hex_be)
    bytes_le = bytes_be[::-1]
    hex_le = bytes_le.hex()
    return hex_le
    
def dhash(hash):
    return sha256(sha256(hash.encode('utf-8')).hexdigest().encode('utf-8')).hexdigest()

def culculate_merkle(hash_list):

    if len(hash_list) == 1:
        return dhash(hash_list[0])

    hashed_list = list(map(dhash, hash_list))

    if len(hashed_list) % 2 == 1:
        hashed_list.append(hashed_list[-1])
    
    parent_hash_list = []
        
    it = iter(hashed_list)
    for hash1, hash2 in zip(it, it):
        parent_hash_list.append(hash1 + hash2)

    hashed_list = list(map(dhash, hash_list))
    return culculate_merkle(parent_hash_list)

data = requests.get(end_point)
jsondata = json.loads(data.text)
tx_list = list(map(lambda tx_object: tx_object['hash'], jsondata['tx']))

markleroot = '67a637b1c49d95165b3dd3177033adbbbc880f6da3620498d451ee0976d7b1f4'

tx_list = list(map(reverse, tx_list))

output = culculate_merkle(tx_list)
output = reverse(output)
print(output)

运行结果 #

$ python merkleTree.py
f2a2207a1e8360b75729fd2f23659b1b79b14940b6e4982a985cf6aa6f941ad7

期望得到的结果是67a637b1c49d95165b3dd3177033adbbbc880f6da3620498d451ee0976d7b1f4，请问问题出在哪里？

问题分析与修正 #

你的代码存在三个核心错误：

1. 双哈希（dhash）实现逻辑错误
   比特币的双SHA256哈希是直接对字节数据运算，而非将十六进制字符串转UTF-8编码后哈希。当前dhash函数错误地将十六进制字符串转UTF-8、哈希、转十六进制、再转UTF-8哈希，完全不符合比特币的哈希规则。

正确的双哈希实现：

def dhash(hex_str):
    data = bytes.fromhex(hex_str)
    hash1 = sha256(data).digest()
    return sha256(hash1).hexdigest()

2. Merkle树递归计算逻辑错误
   在culculate_merkle函数中，你重复执行了hashed_list = list(map(dhash, hash_list))，导致每一层都重新对原始交易哈希列表哈希，而非基于上一层的父节点列表计算。此外，合并子哈希时应直接操作字节数据，而非拼接十六进制字符串。

修正后的Merkle树计算函数：

def calculate_merkle(hash_list):
    if len(hash_list) == 1:
        return hash_list[0]

    # 奇数长度时补全最后一个哈希
    if len(hash_list) % 2 != 0:
        hash_list.append(hash_list[-1])
    
    parent_hash_list = []
    it = iter(hash_list)
    for hash1, hash2 in zip(it, it):
        # 合并两个哈希的字节数据
        combined = bytes.fromhex(hash1) + bytes.fromhex(hash2)
        # 计算双哈希
        parent_hash = sha256(sha256(combined).digest()).hexdigest()
        parent_hash_list.append(parent_hash)
    
    return calculate_merkle(parent_hash_list)

3. 递归终止条件错误
   原函数中当列表长度为1时，还会再执行一次dhash，但实际上此时的哈希已经是最终的Merkle Root，无需再次哈希。

完整修正后的代码 #

from hashlib import sha256
import requests, json

base_url = 'https://blockchain.info/rawblock/'
block_hash = '000000000000000000042cef688cf40b4a70ac814e4222e6646bd6bb79d18168'
end_point = base_url + block_hash

def reverse_hex(hex_str):
    bytes_data = bytes.fromhex(hex_str)
    reversed_bytes = bytes_data[::-1]
    return reversed_bytes.hex()

def calculate_merkle(hash_list):
    if len(hash_list) == 1:
        return hash_list[0]

    if len(hash_list) % 2 != 0:
        hash_list.append(hash_list[-1])
    
    parent_hash_list = []
    it = iter(hash_list)
    for hash1, hash2 in zip(it, it):
        combined = bytes.fromhex(hash1) + bytes.fromhex(hash2)
        double_hash = sha256(sha256(combined).digest()).hexdigest()
        parent_hash_list.append(double_hash)
    
    return calculate_merkle(parent_hash_list)

# 获取区块交易哈希
response = requests.get(end_point)
block_data = response.json()
tx_hashes = [tx['hash'] for tx in block_data['tx']]

# 转换为小端字节序（比特币内部存储格式）
tx_hashes_le = list(map(reverse_hex, tx_hashes))

# 计算Merkle Root并转换为页面展示的小端格式
merkle_root_be = calculate_merkle(tx_hashes_le)
merkle_root_le = reverse_hex(merkle_root_be)

print(f"计算结果: {merkle_root_le}")
print(f"预期结果: 67a637b1c49d95165b3dd3177033adbbbc880f6da3620498d451ee0976d7b1f4")

修正后运行结果 #

计算结果: 67a637b1c49d95165b3dd3177033adbbbc880f6da3620498d451ee0976d7b1f4
预期结果: 67a637b1c49d95165b3dd3177033adbbbc880f6da3620498d451ee0976d7b1f4

内容的提问来源于stack exchange，提问作者六本木智