Merkle tree - Bitcoin

hash_test.py

#!/bin/env python
# -*- coding: utf-8 -*-

import hashlib

def merkle_root(lst):
    # Биткойн использует для склеивания хешей два прогона SHA-256 и изменение
    # порядка байтов. Зачем, не до конца понятно.
    sha256d = lambda x: hashlib.sha256(hashlib.sha256(x).digest()).digest()
    hash_pair = lambda x, y: sha256d(x[::-1] + y[::-1])[::-1]

    if len(lst) == 1: return lst[0]
    
    # Дублирование элементов в дереве приводит к интересной уязвимости -
    # получается, что различные списки транзакций могут иметь один и тот же хеш.
    # По этой причине в биткойне даже есть специальный комментарий,
    # предостерегающий разработчиков новых криптовалют:
    # https://github.com/bitcoin/bitcoin/blob/master/src/consensus/merkle.cpp#L9
    if len(lst) % 2 == 1:
        lst.append(lst[-1])
    return merkle_root([ hash_pair(x, y) 
        for x, y in zip(*[iter(lst)] * 2) ])

# Блок 100000:
# https://blockchain.info/block/000000000003ba27aa200b1cecaad478d2b00432346c3f1f3986da1afd33e506
tx_hashes = [
    '8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87',
    'fff2525b8931402dd09222c50775608f75787bd2b87e56995a7bdd30f79702c4',
    '6359f0868171b1d194cbee1af2f16ea598ae8fad666d9b012c8ed2b79a236ec4',
    'e9a66845e05d5abc0ad04ec80f774a7e585c6e8db975962d069a522137b80c1d'
]
tx_hashes = [ h.decode('hex') for h in tx_hashes ]
assert merkle_root(tx_hashes).encode('hex') == \
   'f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766'
   
# Блок 111111:
# https://blockchain.info/block/000000000000679c158c35a47eecb6352402baeedd22d0385b7c9d14a922f218
tx_hashes = [
    'e7c6a5c20318e99e7a2fe7e9c534fae52d402ef6544afd85a0a1a22a8d09783a',
    '3fe7ac92b9d20c9b5fb1ba21008b41eb1208af50a7021694f7f73fd37e914b67',
    'b3a37d774cd5f15be1ee472e8c877bcc54ab8ea00f25d34ef11e76a17ecbb67c',
    'dcc75a59bcee8a4617b8f0fc66d1444fea3574addf9ed1e0631ae85ff6c65939',
    '59639ffc15ef30860d11da02733c2f910c43e600640996ee17f0b12fd0cb51e9',
    '0e942bb178dbf7ae40d36d238d559427429641689a379fc43929f15275a75fa6',
    '5ea33197f7b956644d75261e3c03eefeeea43823b3de771e92371f3d630d4c56',
    '55696d0a3686df2eb51aae49ca0a0ae42043ea5591aa0b6d755020bdb64887f6',
    '2255724fd367389c2aabfff9d5eb51d08eda0d7fed01f3f9d0527693572c08f6',
    'c8329c18492c5f6ee61eb56dab52576b1de48bbb1d7f6aa7f0387f9b3b63722e',
    '34b7f053f77406456676fdd3d1e4ac858b69b54daf3949806c2c92ca70d3b88d'
]
tx_hashes = [ h.decode('hex') for h in tx_hashes ]
assert merkle_root(tx_hashes).encode('hex') == \
   'a09442e76a15a77694b31c20a105ff5e2000ee4ec4d7db42ecec1b56e041da32'