lib/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 from hashlib import sha256
  18 from util import doublesha
  19
  20 class MerkleTree:
  21     def __init__(self, data, detailed=False):
  22         self.data = data
  23         self.recalculate(detailed)
  24         self._hash_steps = None
  25
  26     def recalculate(self, detailed=False):
  27         L = self.data
  28         steps = []
  29         if detailed:
  30             detail = []
  31             PreL = []
  32             StartL = 0
  33         else:
  34             detail = None
  35             PreL = [None]
  36             StartL = 2
  37         Ll = len(L)
  38         if detailed or Ll > 1:
  39             while True:
  40                 if detailed:
  41                     detail += L
  42                 if Ll == 1:
  43                     break
  44                 steps.append(L[1])
  45                 if Ll % 2:
  46                     L += [L[-1]]
  47                 L = PreL + [doublesha(L[i] + L[i + 1]) for i in range(StartL, Ll, 2)]
  48                 Ll = len(L)
  49         self._steps = steps
  50         self.detail = detail
  51
  52     def hash_steps(self):
  53         if self._hash_steps == None:
  54             self._hash_steps = doublesha(''.join(self._steps))
  55         return self._hash_steps
  56
  57     def withFirst(self, f):
  58         steps = self._steps
  59         for s in steps:
  60             f = doublesha(f + s)
  61         return f
  62
  63     def merkleRoot(self):
  64         return self.withFirst(self.data[0])
  65
  66 # MerkleTree tests
  67 def _test():
  68     import binascii
  69     import time
  70
  71     mt = MerkleTree([None] + [binascii.unhexlify(a) for a in [
  72         '999d2c8bb6bda0bf784d9ebeb631d711dbbbfe1bc006ea13d6ad0d6a2649a971',
  73         '3f92594d5a3d7b4df29d7dd7c46a0dac39a96e751ba0fc9bab5435ea5e22a19d',
  74         'a5633f03855f541d8e60a6340fc491d49709dc821f3acb571956a856637adcb6',
  75         '28d97c850eaf917a4c76c02474b05b70a197eaefb468d21c22ed110afe8ec9e0',
  76     ]])
  77     assert(
  78         b'82293f182d5db07d08acf334a5a907012bbb9990851557ac0ec028116081bd5a' ==
  79         binascii.b2a_hex(mt.withFirst(binascii.unhexlify('d43b669fb42cfa84695b844c0402d410213faa4f3e66cb7248f688ff19d5e5f7')))
  80     )
  81
  82     print '82293f182d5db07d08acf334a5a907012bbb9990851557ac0ec028116081bd5a'
  83     txes = [binascii.unhexlify(a) for a in [
  84         'd43b669fb42cfa84695b844c0402d410213faa4f3e66cb7248f688ff19d5e5f7',
  85         '999d2c8bb6bda0bf784d9ebeb631d711dbbbfe1bc006ea13d6ad0d6a2649a971',
  86         '3f92594d5a3d7b4df29d7dd7c46a0dac39a96e751ba0fc9bab5435ea5e22a19d',
  87         'a5633f03855f541d8e60a6340fc491d49709dc821f3acb571956a856637adcb6',
  88         '28d97c850eaf917a4c76c02474b05b70a197eaefb468d21c22ed110afe8ec9e0',
  89     ]]
  90
  91     s = time.time()
  92     mt = MerkleTree(txes)
  93     for x in range(100):
  94         y = int('d43b669fb42cfa84695b844c0402d410213faa4f3e66cb7248f688ff19d5e5f7', 16)
  95         #y += x
  96         coinbasehash = binascii.unhexlify("%x" % y)
  97         x = binascii.b2a_hex(mt.withFirst(coinbasehash))
  98
  99     print x
 100     print time.time() - s
 101
 102 if __name__ == '__main__':
 103     _test()