From 2c8457cd0ba27fbb93e68ec49e91c90f3130e87e Mon Sep 17 00:00:00 2001
From: Forrest Voight <forrest.voight@gmail.com>
Date: Wed, 23 Nov 2011 18:14:52 -0500
Subject: [PATCH] moved new-shares to using normal merkle branches

---
 p2pool/bitcoin/data.py |   36 ++++++++++++++++++++++++++++++++++--
 p2pool/data.py         |    6 +++---
 2 files changed, 37 insertions(+), 5 deletions(-)

diff --git a/p2pool/bitcoin/data.py b/p2pool/bitcoin/data.py
index 2a7914f..fa36848 100644
--- a/p2pool/bitcoin/data.py
+++ b/p2pool/bitcoin/data.py
@@ -439,10 +439,12 @@ tx_type = ComposedType([
     ('lock_time', StructType('<I')),
 ])
 
+merkle_branch_type = ListType(HashType())
+
 merkle_tx_type = ComposedType([
     ('tx', tx_type),
     ('block_hash', HashType()),
-    ('merkle_branch', ListType(HashType())),
+    ('merkle_branch', merkle_branch_type),
     ('index', StructType('<i')),
 ])
 
@@ -462,7 +464,7 @@ block_type = ComposedType([
 
 aux_pow_type = ComposedType([
     ('merkle_tx', merkle_tx_type),
-    ('merkle_branch', ListType(HashType())),
+    ('merkle_branch', merkle_branch_type),
     ('index', StructType('<i')),
     ('parent_block_header', block_header_type),
 ])
@@ -482,6 +484,36 @@ def merkle_hash(tx_list):
             for left, right in zip(hash_list[::2], hash_list[1::2] + [None])]
     return hash_list[0]
 
+def calculate_merkle_branch(txs, index):
+    # XXX optimize this
+    
+    hash_list = [(tx_type.hash256(tx), i == index, []) for i, tx in enumerate(txs)]
+    
+    while len(hash_list) > 1:
+        hash_list = [
+            (
+                merkle_record_type.hash256(dict(left=left, right=right)),
+                left_f or right_f,
+                (left_l if left_f else right_l) + [dict(side=1, hash=right) if left_f else dict(side=0, hash=left)],
+            )
+            for (left, left_f, left_l), (right, right_f, right_l) in
+                zip(hash_list[::2], hash_list[1::2] + [hash_list[::2][-1]])
+        ]
+    
+    res = [x['hash'] for x in hash_list[0][2]]
+    
+    assert hash_list[0][1]
+    assert check_merkle_branch(txs[index], index, res) == hash_list[0][0]
+    assert index == sum(k*2**i for i, k in enumerate([1-x['side'] for x in hash_list[0][2]]))
+    
+    return res
+
+def check_merkle_branch(tx, index, merkle_branch):
+    return reduce(lambda c, (i, h): merkle_record_type.hash256(
+        dict(left=h, right=c) if 2**i & index else
+        dict(left=c, right=h)
+    ), enumerate(merkle_branch), tx_type.hash256(tx))
+
 def target_to_average_attempts(target):
     return 2**256//(target + 1)
 
diff --git a/p2pool/data.py b/p2pool/data.py
index 5f76b3c..6208cc6 100644
--- a/p2pool/data.py
+++ b/p2pool/data.py
@@ -67,7 +67,7 @@ new_share_info_type = bitcoin_data.ComposedType([
 new_share1a_type = bitcoin_data.ComposedType([
     ('header', bitcoin_data.block_header_type),
     ('share_info', new_share_info_type),
-    ('merkle_branch', merkle_branch_type),
+    ('merkle_branch', bitcoin_data.merkle_branch_type),
 ])
 
 new_share1b_type = bitcoin_data.ComposedType([
@@ -241,7 +241,7 @@ class NewShare(Share):
         if merkle_branch is None and other_txs is None:
             raise ValueError('need either merkle_branch or other_txs')
         if other_txs is not None:
-            new_merkle_branch = calculate_merkle_branch([dict(version=0, tx_ins=[], tx_outs=[], lock_time=0)] + other_txs, 0)
+            new_merkle_branch = bitcoin_data.calculate_merkle_branch([dict(version=0, tx_ins=[], tx_outs=[], lock_time=0)] + other_txs, 0)
             if merkle_branch is not None:
                 if merke_branch != new_merkle_branch:
                     raise ValueError('invalid merkle_branch and other_txs')
@@ -309,7 +309,7 @@ class NewShare(Share):
         if len(gentx['tx_ins'][0]['script']) > 100:
             raise ValueError('''coinbase too large! %i bytes''' % (len(gentx['tx_ins'][0]['script']),))
         
-        if check_merkle_branch(gentx, self.merkle_branch) != self.header['merkle_root']:
+        if bitcoin_data.check_merkle_branch(gentx, 0, self.merkle_branch) != self.header['merkle_root']:
             raise ValueError('''gentx doesn't match header via merkle_branch''')
         
         if self.other_txs is not None:
-- 
1.7.1