merkletree.py

   1 # Eloipool - Python Bitcoin pool server
   2 # Copyright (C) 2011-2012  Luke Dashjr <luke-jr+eloipool@utopios.org>
   3 #
   4 # This program is free software: you can redistribute it and/or modify
   5 # it under the terms of the GNU Affero General Public License as
   6 # published by the Free Software Foundation, either version 3 of the
   7 # License, or (at your option) any later version.
   8 #
   9 # This program is distributed in the hope that it will be useful,
  10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 # GNU Affero General Public License for more details.
  13 #
  14 # You should have received a copy of the GNU Affero General Public License
  15 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 try:
  18         from bitcoin.txn import Txn
  19 except ImportError:
  20         class Txn:
  21                 pass
  22 from util import dblsha
  23
  24 class MerkleTree:
  25         def __init__(self, data, detailed=False):
  26                 self.data = data
  27                 self.recalculate(detailed)
  28
  29         def recalculate(self, detailed=False):
  30                 L = self.data
  31                 steps = []
  32                 if detailed:
  33                         detail = []
  34                         PreL = []
  35                         StartL = 0
  36                 else:
  37                         detail = None
  38                         PreL = [None]
  39                         StartL = 2
  40                 Ll = len(L)
  41                 if detailed or Ll > 1:
  42                         if isinstance(L[1] if Ll > 1 else L[0], Txn):
  43                                 L = list(map(lambda a: a.txid if a else a, L))
  44                         while True:
  45                                 if detailed:
  46                                         detail += L
  47                                 if Ll == 1:
  48                                         break
  49                                 steps.append(L[1])
  50                                 if Ll % 2:
  51                                         L += [L[-1]]
  52                                 L = PreL + [dblsha(L[i] + L[i + 1]) for i in range(StartL, Ll, 2)]
  53                                 Ll = len(L)
  54                 self._steps = steps
  55                 self.detail = detail
  56
  57         def withFirst(self, f):
  58                 if isinstance(f, Txn):
  59                         f = f.txid
  60                 steps = self._steps
  61                 for s in steps:
  62                         f = dblsha(f + s)
  63                 return f
  64
  65         def merkleRoot(self):
  66                 return self.withFirst(self.data[0])
  67
  68 # MerkleTree tests
  69 def _test():
  70         from binascii import b2a_hex
  71         mt = MerkleTree([None] + [bytes.fromhex(a) for a in [
  72                 '999d2c8bb6bda0bf784d9ebeb631d711dbbbfe1bc006ea13d6ad0d6a2649a971',
  73                 '3f92594d5a3d7b4df29d7dd7c46a0dac39a96e751ba0fc9bab5435ea5e22a19d',
  74                 'a5633f03855f541d8e60a6340fc491d49709dc821f3acb571956a856637adcb6',
  75                 '28d97c850eaf917a4c76c02474b05b70a197eaefb468d21c22ed110afe8ec9e0',
  76         ]])
  77         assert(
  78                 b'82293f182d5db07d08acf334a5a907012bbb9990851557ac0ec028116081bd5a' ==
  79                 b2a_hex(mt.withFirst(bytes.fromhex('d43b669fb42cfa84695b844c0402d410213faa4f3e66cb7248f688ff19d5e5f7')))
  80         )
  81
  82         d = b'\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00'
  83         dh = b"C\xeczW\x9fUa\xa4*~\x967\xadAVg'5\xa6X\xbe'R\x18\x18\x01\xf7#\xba3\x16\xd2"
  84         t = Txn(d)
  85         m = MerkleTree([t])
  86         assert m.merkleRoot() == dh
  87         u = Txn.new()
  88         u.addInput((b' '*32, 0), b'')
  89         u.assemble()
  90         m.data.append(u)
  91         m.recalculate()
  92         mr = b"q\xe1\x9a3'\x0f>\xbfTv\xc8\x90\x81\x802\xe3\xb7u\x96\xddjP4\xe3\x19\xf3\xf0\xc5A4\xc0\xdb"
  93         assert m.merkleRoot() == mr
  94         step = b'\xb0\x91t\x84%\x9dg\x827\xc5\xbf\x94\xf0"\x94\xafN[\x0c\xeelF\xd9\x1b\x13q\xd3\xdf\x83\xe6\x01g'
  95         assert m._steps == [step]
  96         m.recalculate(detailed=True)
  97         assert m.detail == [dh, step, mr]
  98         m = MerkleTree([t.txid, u.txid])
  99         assert m.merkleRoot() == mr
 100         assert m._steps == [step]
 101         m.recalculate(detailed=True)
 102         assert m.detail == [dh, step, mr]
 103
 104 _test()