electrum

Electrum Bitcoin wallet
git clone https://git.parazyd.org/electrum
Log | Files | Refs | Submodules

merkle.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