tImplement merkle tree/branch functions. - 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
---
DIR commit 24a277654df91c955e2edc9ec8dc9a20bcf112b4
DIR parent efdd930fa0b7808d663da689d4f0f08824f78c36
HTML Author: parazyd <parazyd@dyne.org>
Date: Wed, 7 Apr 2021 17:21:41 +0200
Implement merkle tree/branch functions.
Diffstat:
A electrumobelisk/hashes.py | 37 +++++++++++++++++++++++++++++++
A electrumobelisk/merkle.py | 57 +++++++++++++++++++++++++++++++
2 files changed, 94 insertions(+), 0 deletions(-)
---
DIR diff --git a/electrumobelisk/hashes.py b/electrumobelisk/hashes.py
t@@ -0,0 +1,37 @@
+#!/usr/bin/env python3
+# Copyright (C) 2020-2021 Ivan J. <parazyd@dyne.org>
+#
+# This file is part of obelisk
+#
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU Affero General Public License version 3
+# as published by the Free Software Foundation.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU Affero General Public License for more details.
+#
+# You should have received a copy of the GNU Affero General Public License
+# along with this program. If not, see <http://www.gnu.org/licenses/>.
+""" Cryptographic hash functions and helpers """
+import hashlib
+
+_sha256 = hashlib.sha256
+
+
+def sha256(inp):
+ """ Simple wrapper of hashlib sha256. """
+ return _sha256(inp).digest()
+
+
+def double_sha256(inp):
+ """ sha256 of sha256, as used extensively in bitcoin """
+ return sha256(sha256(inp))
+
+
+def hash_to_hex_str(inp):
+ """Convert a big-endian binary hash to displayed hex string.
+ Display form of a binary hash is reversed and converted to hex.
+ """
+ return bytes(reversed(inp)).hex()
DIR diff --git a/electrumobelisk/merkle.py b/electrumobelisk/merkle.py
t@@ -0,0 +1,57 @@
+#!/usr/bin/env python3
+# Copyright (C) 2020-2021 Ivan J. <parazyd@dyne.org>
+#
+# This file is part of obelisk
+#
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU Affero General Public License version 3
+# as published by the Free Software Foundation.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU Affero General Public License for more details.
+#
+# You should have received a copy of the GNU Affero General Public License
+# along with this program. If not, see <http://www.gnu.org/licenses/>.
+"""Module for calculating merkle branches"""
+from math import ceil, log
+
+from hashes import double_sha256
+
+
+def branch_length(hash_count):
+ """Return the length of a merkle branch given the number of hashes"""
+ return ceil(log(hash_count, 2))
+
+
+def merkle_branch_and_root(hashes, index):
+ """Return a (merkle branch, merkle_root) pair given hashes, and the
+ index of one of those hashes.
+ """
+ hashes = list(hashes)
+ if not isinstance(index, int):
+ raise TypeError("index must be an integer")
+ # This also asserts hashes is not empty
+ if not 0 <= index < len(hashes):
+ raise ValueError("index out of range")
+ length = branch_length(len(hashes))
+
+ branch = []
+ for _ in range(length):
+ if len(hashes) & 1:
+ hashes.append(hashes[-1])
+ branch.append(hashes[index ^ 1])
+ index >>= 1
+ hashes = [
+ double_sha256(hashes[n] + hashes[n + 1])
+ for n in range(0, len(hashes), 2)
+ ]
+ return branch, hashes[0]
+
+
+def merkle_branch(tx_hashes, tx_pos):
+ """Return a merkle branch given hashes and the tx position"""
+ branch, _root = merkle_branch_and_root(tx_hashes, tx_pos)
+ branch = [bytes(reversed(h)).hex() for h in branch]
+ return branch