obelisk

Electrum server using libbitcoin as its backend
git clone https://git.parazyd.org/obelisk
Log | Files | Refs | README | LICENSE

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