tmerkle.py - obelisk - Electrum server using libbitcoin as its backend
HTML git clone https://git.parazyd.org/obelisk
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
tmerkle.py (2484B)
---
1 #!/usr/bin/env python3
2 # Copyright (C) 2020-2021 Ivan J. <parazyd@dyne.org>
3 #
4 # This file is part of obelisk
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 version 3
8 # as published by the Free Software Foundation.
9 #
10 # This program is distributed in the hope that it will be useful,
11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 # GNU Affero General Public License for more details.
14 #
15 # You should have received a copy of the GNU Affero General Public License
16 # along with this program. If not, see <http://www.gnu.org/licenses/>.
17 """Module for calculating merkle branches"""
18 from math import ceil, log
19
20 from obelisk.util import double_sha256, hash_to_hex_str
21
22
23 def branch_length(hash_count): # pragma: no cover
24 """Return the length of a merkle branch given the number of hashes"""
25 if not isinstance(hash_count, int):
26 raise TypeError("hash_count must be an integer")
27 if hash_count < 1:
28 raise ValueError("hash_count must be at least 1")
29 return ceil(log(hash_count, 2))
30
31
32 def merkle_branch_and_root(hashes, index, length=None):
33 """Return a (merkle branch, merkle_root) pair given hashes, and the
34 index of one of those hashes.
35 """
36 hashes = list(hashes)
37 if not isinstance(index, int):
38 raise TypeError("index must be an integer") # pragma: no cover
39 # This also asserts hashes is not empty
40 if not 0 <= index < len(hashes):
41 raise ValueError("index out of range") # pragma: no cover
42 natural_length = branch_length(len(hashes))
43 if length is None:
44 length = natural_length
45 else: # pragma: no cover
46 if not isinstance(length, int):
47 raise TypeError("length must be an integer")
48 if length < natural_length:
49 raise ValueError("length out of range")
50
51 branch = []
52 for _ in range(length):
53 if len(hashes) & 1:
54 hashes.append(hashes[-1])
55 branch.append(hashes[index ^ 1])
56 index >>= 1
57 hashes = [
58 double_sha256(hashes[n] + hashes[n + 1])
59 for n in range(0, len(hashes), 2)
60 ]
61 return branch, hashes[0]
62
63
64 def merkle_branch(tx_hashes, tx_pos):
65 """Return a merkle branch given hashes and the tx position"""
66 branch, _ = merkle_branch_and_root(tx_hashes, tx_pos)
67 return [hash_to_hex_str(h) for h in branch]