pythonsha256bitcoinmerkle-tree

My Merkle Tree calculation does not match the actual one


I am studying bitcoin.

https://en.bitcoin.it/wiki/Protocol_documentation#Merkle_Trees

I read the above URL and implemented Merkle root in Python.

Using the API below, I collected all transactions in block 641150 and calculated the Merkle Root.

https://www.blockchain.com/explorer/api/blockchain_api

The following is the expected value 67a637b1c49d95165b3dd3177033adbbbc880f6da3620498d451ee0976d7b1f4 (https://www.blockchain.com/btc/block/641150 )

The values I calculated were as follows f2a2207a1e8360b75729fd2f23659b1b79b14940b6e4982a985cf6aa6f941ad7

What is wrong?

My python code is;

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)

result

$ python merkleTree.py
f2a2207a1e8360b75729fd2f23659b1b79b14940b6e4982a985cf6aa6f941ad7

I expect the following output as a result

67a637b1c49d95165b3dd3177033adbbbc880f6da3620498d451ee0976d7b1f4


Solution

  • self solving

    first: There was mistake in the dhash calculation method. second: The hash list obtained from the API had already had the dhash applied once. ā‡’ The first time dhash was performed without this perspective

    The complete source code is summarized in the following blog (in Japanese) https://tec.tecotec.co.jp/entry/2022/12/25/000000