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 (1976B)
       ---
            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 electrumobelisk.util import double_sha256
           21 
           22 
           23 def branch_length(hash_count):
           24     """Return the length of a merkle branch given the number of hashes"""
           25     return ceil(log(hash_count, 2))
           26 
           27 
           28 def merkle_branch_and_root(hashes, index):
           29     """Return a (merkle branch, merkle_root) pair given hashes, and the
           30     index of one of those hashes.
           31     """
           32     hashes = list(hashes)
           33     if not isinstance(index, int):
           34         raise TypeError("index must be an integer")
           35     # This also asserts hashes is not empty
           36     if not 0 <= index < len(hashes):
           37         raise ValueError("index out of range")
           38     length = branch_length(len(hashes))
           39 
           40     branch = []
           41     for _ in range(length):
           42         if len(hashes) & 1:
           43             hashes.append(hashes[-1])
           44         branch.append(hashes[index ^ 1])
           45         index >>= 1
           46         hashes = [
           47             double_sha256(hashes[n] + hashes[n + 1])
           48             for n in range(0, len(hashes), 2)
           49         ]
           50     return branch, hashes[0]
           51 
           52 
           53 def merkle_branch(tx_hashes, tx_pos):
           54     """Return a merkle branch given hashes and the tx position"""
           55     branch, _root = merkle_branch_and_root(tx_hashes, tx_pos)
           56     branch = [bytes(reversed(h)).hex() for h in branch]
           57     return branch