tmerkle.py - electrum - Electrum Bitcoin wallet
HTML git clone https://git.parazyd.org/electrum
DIR Log
DIR Files
DIR Refs
DIR Submodules
---
tmerkle.py (2402B)
---
1 #!/usr/bin/env python
2 #
3 # Electrum -lightweight Bitcoin client
4 # Copyright (C) 2021 Ivan J. <parazyd@dyne.org>
5 #
6 # Permission is hereby granted, free of charge, to any person
7 # obtaining a copy of this software and associated documentation files
8 # (the "Software"), to deal in the Software without restriction,
9 # including without limitation the rights to use, copy, modify, merge,
10 # publish, distribute, sublicense, and/or sell copies of the Software,
11 # and to permit persons to whom the Software is furnished to do so,
12 # subject to the following conditions:
13 #
14 # The above copyright notice and this permission notice shall be
15 # included in all copies or substantial portions of the Software.
16 #
17 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
21 # BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
22 # ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
23 # CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24 # SOFTWARE.
25 """Module for calculating merkle branches"""
26 from math import ceil, log
27
28 from .crypto import sha256d
29
30
31 def branch_length(hash_count):
32 """Return the length of a merkle branch given the number of hashes"""
33 return ceil(log(hash_count, 2))
34
35
36 def merkle_branch_and_root(hashes, index):
37 """Return a (merkle branch, merkle_root) pair given hashes, and the
38 index of one of those hashes.
39 """
40 hashes = list(hashes)
41 if not isinstance(index, int):
42 raise TypeError('index must be an integer')
43 # This also asserts hashes is not empty
44 if not 0 <= index < len(hashes):
45 raise ValueError('index out of range')
46 length = branch_length(len(hashes))
47
48 branch = []
49 for _ in range(length):
50 if len(hashes) & 1:
51 hashes.append(hashes[-1])
52 branch.append(hashes[index ^ 1])
53 index >>= 1
54 hashes = [sha256d(hashes[n] + hashes[n+1])
55 for n in range(0, len(hashes), 2)]
56 return branch, hashes[0]
57
58 def merkle_branch(tx_hashes, tx_pos):
59 """Return a merkle branch given hashes and the tx position"""
60 branch, _root = merkle_branch_and_root(tx_hashes, tx_pos)
61 branch = [bytes(reversed(h)).hex() for h in branch]
62 return branch