merkletree.py

   1 try:
   2         from bitcoin.txn import Txn
   3 except ImportError:
   4         class Txn:
   5                 pass
   6 from util import dblsha
   7
   8 class MerkleTree:
   9         def __init__(self, data, detailed=False):
  10                 self.data = data
  11                 self.recalculate(detailed)
  12
  13         def recalculate(self, detailed=False):
  14                 L = self.data
  15                 steps = []
  16                 if detailed:
  17                         detail = []
  18                         PreL = []
  19                         StartL = 0
  20                 else:
  21                         detail = None
  22                         PreL = [None]
  23                         StartL = 2
  24                 Ll = len(L)
  25                 if detailed or Ll > 1:
  26                         if isinstance(L[1] if Ll > 1 else L[0], Txn):
  27                                 L = list(map(lambda a: a.txid if a else a, L))
  28                         while True:
  29                                 if detailed:
  30                                         detail += L
  31                                 if Ll == 1:
  32                                         break
  33                                 steps.append(L[1])
  34                                 if Ll % 2:
  35                                         L += [L[-1]]
  36                                 L = PreL + [dblsha(L[i] + L[i + 1]) for i in range(StartL, Ll, 2)]
  37                                 Ll = len(L)
  38                 self._steps = steps
  39                 self.detail = detail
  40
  41         def withFirst(self, f):
  42                 if isinstance(f, Txn):
  43                         f = f.txid
  44                 steps = self._steps
  45                 for s in steps:
  46                         f = dblsha(f + s)
  47                 return f
  48
  49         def merkleRoot(self):
  50                 return self.withFirst(self.data[0])
  51
  52 # MerkleTree test case
  53 from binascii import a2b_hex, b2a_hex
  54 mt = MerkleTree([None] + [a2b_hex(a) for a in [
  55         b'999d2c8bb6bda0bf784d9ebeb631d711dbbbfe1bc006ea13d6ad0d6a2649a971',
  56         b'3f92594d5a3d7b4df29d7dd7c46a0dac39a96e751ba0fc9bab5435ea5e22a19d',
  57         b'a5633f03855f541d8e60a6340fc491d49709dc821f3acb571956a856637adcb6',
  58         b'28d97c850eaf917a4c76c02474b05b70a197eaefb468d21c22ed110afe8ec9e0',
  59 ]])
  60 assert(
  61         b'82293f182d5db07d08acf334a5a907012bbb9990851557ac0ec028116081bd5a' ==
  62         b2a_hex(mt.withFirst(a2b_hex(b'd43b669fb42cfa84695b844c0402d410213faa4f3e66cb7248f688ff19d5e5f7')))
  63 )