merkle.py (3096B)
1 #!/usr/bin/env python3 2 # electrum-obelisk 3 # Copyright (C) 2020-2021 Ivan J. <parazyd@dyne.org> 4 # Copyright (C) 2018 Neil Booth (MIT License) 5 # 6 # This program is free software: you can redistribute it and/or modify 7 # it under the terms of the GNU Affero General Public License as published by 8 # the Free Software Foundation, either version 3 of the License, or 9 # (at your option) any later version. 10 # 11 # This program is distributed in the hope that it will be useful, 12 # but WITHOUT ANY WARRANTY; without even the implied warranty of 13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 # GNU Affero General Public License for more details. 15 # 16 # You should have received a copy of the GNU Affero General Public License 17 # along with this program. If not, see <http://www.gnu.org/licenses/>. 18 """ Merkle trees, branches, proofs and roots """ 19 from binascii import unhexlify 20 from math import ceil, log 21 22 from electrumobelisk.bx import bx_json 23 from electrumobelisk.hash import double_sha256, hash_to_hex_str 24 25 26 def branch_length(hash_count): 27 """ Return the length of a merkle branch given the number of hashes """ 28 return ceil(log(hash_count, 2)) 29 30 31 def merkle_branch_and_root(hashes, index): 32 """ Return a (merkle branch, merkle_root) pair given hashes, and the 33 index of one of those hashes. """ 34 hashes = list(hashes) 35 if not isinstance(index, int): 36 raise TypeError('index must be an integer') 37 # This also asserts hashes is not empty 38 if not 0 <= index < len(hashes): 39 raise ValueError('index out of range') 40 length = branch_length(len(hashes)) 41 42 branch = [] 43 for _ in range(length): 44 if len(hashes) & 1: 45 hashes.append(hashes[-1]) 46 branch.append(hashes[index ^ 1]) 47 index >>= 1 48 hashes = [double_sha256(hashes[n] + hashes[n+1]) 49 for n in range(0, len(hashes), 2)] 50 return branch, hashes[0] 51 52 def _merkle_branch(tx_hashes, tx_pos): 53 branch, _root = merkle_branch_and_root(tx_hashes, tx_pos) 54 branch = [hash_to_hex_str(hash) for hash in branch] 55 return branch 56 57 def merkle_branch_for_tx_hash(height, tx_hash): 58 """ Return merkle branch and tx_position for given height/tx_hash """ 59 metadata = bx_json(['fetch-tx-index', tx_hash]) 60 if not metadata: 61 return None, None 62 tx_pos = int(metadata['metadata']['index']) 63 block = bx_json(['fetch-block', '--height', str(height)]) 64 if not block: 65 return None, None 66 #tx_hashes = [i['hash'] for i in block['block']['transactions']] 67 tx_hashes = [unhexlify(i['hash'])[::-1] 68 for i in block['block']['transactions']] 69 return _merkle_branch(tx_hashes, tx_pos), tx_pos 70 71 72 def merkle_branch_for_tx_pos(height, tx_pos): 73 """ Return merkle branch for given height/tx_pos """ 74 block = bx_json(['fetch-block', '--height', str(height)]) 75 if not block: 76 return None, None 77 txid = block['block']['transactions'][tx_pos] 78 tx_hashes = [reversed(unhexlify(i['hash'])) 79 for i in block['block']['transactions']] 80 return _merkle_branch(tx_hashes, tx_pos), txid