0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

Bitcoin: 计算Merkle Tree

Last updated at Posted at 2021-06-01

计算Block Hash中,接触到一个变量mrkl_root,即Merkle Tree,默克尔树。

Hash_Tree


                   A               A
                  /  \            /   \
                B     C         B       C
               / \    |        / \     / \
              D   E   F       D   E   F   G
             / \ / \ / \     / \ / \ / \ / \
             1 2 3 4 5 6     1 2 3 4 5 6 7 8

我们计算下 Height 100008的mrkl_root.

这个block只有2个tx:

de2c2e8628ab837ceff3de0217083d9d5feb71f758a5d083ada0b33a36e1b30e
89878bfd69fba52876e5217faec126fc6a20b1845865d4038c12f03200793f48

计算

import hashlib

def hash256(s):
  return hashlib.new('sha256', s).digest()

def dhash256(s):
  return hash256(hash256(s))

tx1="de2c2e8628ab837ceff3de0217083d9d5feb71f758a5d083ada0b33a36e1b30e".decode('hex')[::-1]
tx2="89878bfd69fba52876e5217faec126fc6a20b1845865d4038c12f03200793f48".decode('hex')[::-1]

mrkl_tree = dhash256(tx1+tx2)
result=mrkl_tree[::-1].encode('hex')

print result

result 是 7a059188283323a2ef0e02dd9f8ba1ac550f94646290d0a52a586e5426c956c5

而这个block的mrkl_root呢?

curl https://webbtc.com/block/000000000002dfb177c4acd494b3dd73b9abece24df11c62bb614a8c6c5665e2.json

mrkl_tree: [
"de2c2e8628ab837ceff3de0217083d9d5feb71f758a5d083ada0b33a36e1b30e",
"89878bfd69fba52876e5217faec126fc6a20b1845865d4038c12f03200793f48",
"7a059188283323a2ef0e02dd9f8ba1ac550f94646290d0a52a586e5426c956c5"
]

计算正确, 最需要注意的是大小端的数据转换

如何做大小端数据转换 , 请看 https://www.jianshu.com/p/7623cec7620a

一步步计算 merkle Tree

计算block高度 123456的merkle tree

import hashlib
 
def hash256(s):
  return hashlib.new('sha256', s).digest()
 
def dhash256(s):
  return hash256(hash256(s))
 
tx1="5b75086dafeede555fc8f9a810d8b10df57c46f9f176ccc3dd8d2fa20edd685b".decode('hex')[::-1]
tx2="e3d0425ab346dd5b76f44c222a4bb5d16640a4247050ef82462ab17e229c83b4".decode('hex')[::-1]
tx3="137d247eca8b99dee58e1e9232014183a5c5a9e338001a0109df32794cdcc92e".decode('hex')[::-1]
tx4="5fd167f7b8c417e59106ef5acfe181b09d71b8353a61a55a2f01aa266af5412d".decode('hex')[::-1]
tx5="60925f1948b71f429d514ead7ae7391e0edf965bf5a60331398dae24c6964774".decode('hex')[::-1]
tx6="d4d5fc1529487527e9873256934dfb1e4cdcb39f4c0509577ca19bfad6c5d28f".decode('hex')[::-1]
tx7="7b29d65e5018c56a33652085dbb13f2df39a1a9942bfe1f7e78e97919a6bdea2".decode('hex')[::-1]
tx8="0b89e120efd0a4674c127a76ff5f7590ca304e6a064fbc51adffbd7ce3a3deef".decode('hex')[::-1]
tx9="603f2044da9656084174cfb5812feaf510f862d3addcf70cacce3dc55dab446e".decode('hex')[::-1]
tx10="9a4ed892b43a4df916a7a1213b78e83cd83f5695f635d535c94b2b65ffb144d3".decode('hex')[::-1]
tx11="dda726e3dad9504dce5098dfab5064ecd4a7650bfe854bb2606da3152b60e427".decode('hex')[::-1]
tx12="e46ea8b4d68719b65ead930f07f1f3804cb3701014f8e6d76c4bdbc390893b94".decode('hex')[::-1]
tx13="864a102aeedf53dd9b2baab4eeb898c5083fde6141113e0606b664c41fe15e1f".decode('hex')[::-1]
 
mrkl_tree1 = dhash256(tx1+tx2)
mrkl_tree2 = dhash256(tx3+tx4)
mrkl_tree3 = dhash256(tx5+tx6)
mrkl_tree4 = dhash256(tx7+tx8)
mrkl_tree5 = dhash256(tx9+tx10)
mrkl_tree6 = dhash256(tx11+tx12)
mrkl_tree7 = dhash256(tx13+ tx13) #奇数要重复相加
 
mrkl_tree1_1 = dhash256(mrkl_tree1 + mrkl_tree2)
mrkl_tree2_2 = dhash256(mrkl_tree3 + mrkl_tree4)
mrkl_tree3_3 = dhash256(mrkl_tree5 + mrkl_tree6)
mrkl_tree4_4 = dhash256(mrkl_tree7 + mrkl_tree7)  #奇数个
 
 
mrkl_tree1_1_1 = dhash256(mrkl_tree1_1 + mrkl_tree2_2 )
mrkl_tree2_2_2 = dhash256(mrkl_tree3_3 + mrkl_tree4_4 )
 
result = dhash256(mrkl_tree1_1_1 + mrkl_tree2_2_2 )
 
print("0e60651a9934e8f0decd1c5fde39309e48fca0cd1c84a21ddfde95033762d86c", "ok")
print result[::-1].encode('hex')

####通用代码

#coding: utf-8

import hashlib

def merkle(hashList):
    if len(hashList) == 1:
        return hashList[0]

    newHashList = []

    # Process pairs. For odd length, the last is skipped

    for i in range(0, len(hashList) - 1, 2):
        newHashList.append(dhash256(hashList[i], hashList[i + 1]))

    if len(hashList) % 2 == 1:  # odd, hash last item twice
        newHashList.append(dhash256(hashList[-1], hashList[-1]))
    return merkle(newHashList)


def dhash256(a, b): # a/b 大小端转换后的数据
    # due to big-endian / little-endian nonsense
    concat = a + b
    temp = hashlib.sha256(concat).digest()
    h = hashlib.sha256(temp).digest()
    return h


#高度 123456
#https://btc.com/0000000000002917ed80650c6174aac8dfc46f5fe36480aaef682ff6cd83c3ca
txHashes = [
    '5b75086dafeede555fc8f9a810d8b10df57c46f9f176ccc3dd8d2fa20edd685b'.decode('hex')[::-1],
    'e3d0425ab346dd5b76f44c222a4bb5d16640a4247050ef82462ab17e229c83b4'.decode('hex')[::-1],
    '137d247eca8b99dee58e1e9232014183a5c5a9e338001a0109df32794cdcc92e'.decode('hex')[::-1],
    '5fd167f7b8c417e59106ef5acfe181b09d71b8353a61a55a2f01aa266af5412d'.decode('hex')[::-1],
    '60925f1948b71f429d514ead7ae7391e0edf965bf5a60331398dae24c6964774'.decode('hex')[::-1],
    'd4d5fc1529487527e9873256934dfb1e4cdcb39f4c0509577ca19bfad6c5d28f'.decode('hex')[::-1],
    '7b29d65e5018c56a33652085dbb13f2df39a1a9942bfe1f7e78e97919a6bdea2'.decode('hex')[::-1],
    '0b89e120efd0a4674c127a76ff5f7590ca304e6a064fbc51adffbd7ce3a3deef'.decode('hex')[::-1],
    '603f2044da9656084174cfb5812feaf510f862d3addcf70cacce3dc55dab446e'.decode('hex')[::-1],
    '9a4ed892b43a4df916a7a1213b78e83cd83f5695f635d535c94b2b65ffb144d3'.decode('hex')[::-1],
    'dda726e3dad9504dce5098dfab5064ecd4a7650bfe854bb2606da3152b60e427'.decode('hex')[::-1],
    'e46ea8b4d68719b65ead930f07f1f3804cb3701014f8e6d76c4bdbc390893b94'.decode('hex')[::-1],
    '864a102aeedf53dd9b2baab4eeb898c5083fde6141113e0606b664c41fe15e1f'.decode('hex')[::-1],
    ]

result = merkle(txHashes)
print(result[::-1].encode('hex'))


参考:
merkle-root-bitcoin-step-by-step
https://gist.github.com/shirriff/c9fb5d98e6da79d9a772
http://pythonfiddle.com/merkle-root-bitcoin/
http://www.cnblogs.com/fengzhiwu/p/5524324.html
https://en.wikipedia.org/wiki/Merkle_tree
http://bittorrent.org/beps/bep_0030.html

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?