Skip to content

Instantly share code, notes, and snippets.

/hash_test.py Secret

Created Apr 13, 2017
Embed
What would you like to do?
Merkle tree - Bitcoin
#!/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'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.