Category: Bitcoin

p2sh-p2wshは、p2sh-p2wpkhと同様にp2wshに後方互換性を持たせる方法

BIP0141以前
01000000 – version
01 – # of inputs
7082…54 – previous tx hash
00000000 – previous tx index
2322…4c – ScriptSig
ffffffff – sequence
01 – # of outputs
603e…00 – output amount
1600…22 ScriptPubKey
00000000 – locktime

BIP0141以降
01000000 – version
00 – Segwit marker
01 – Segwit flag
01 – # of inputs
7082…54 – previous tx hash
01000000 – previous tx index
2322…4c – ScriptSig
ffffffff – sequence
01 – # of outputs
603e…00 – output amount
1600…22 ScriptPubKey
0400…ae – witness
00000000 – locktime

OP_0, 32-byte hash
WitnessScriptはスクリプトコマンドとして解釈されコマンドセットに配置される
OP_0, signature1, signature2, OP_2, pubkey1, pubkey2, pubkey3, OP_3, OP_CHECKMULTISIG

BIP0141以前
01000000 – version
01 – # of inputs
593a…98 – previous tx hash
00000000 – previous tx index
00 – ScriptSig
ffffffff – sequence
01 – # of outputs
806f…00 …output amount
1976…ac ScriptPubKey
00000000 – locktime

BIP0141以降
01000000 – version
00 – Segwit marker
01 – Segwit flag
01 – # of inputs
593a…98 – previous tx hash
00000000 – previous tx index
00 – ScriptSig
ffffffff – sequence
01 – # of outputs
806f…00 …output amount
1976…ac ScriptPubKey
0400…ac – witness
00000000 – locktime

p2wshスクリプトのScriptPubKeyは OP_0 <32 byte hash>
scriptSigはp2wpkhと同様に空

p2wshのwitnessフィールドは2of3のmulti sig
04 – Number of witness elements
00 – OP_0
47 – Length of
3044…01 –
48 – Length of
3045…01 –
69 – Length of witnessScript
5221…ae – WitnessScript

WitnessScriptはsha256でハッシュすると、ScriptPubKeyにある32bytes hashと一致する
=> Lightning Network用の双方向ペイメントチャネル作成にマリアビリティがないマルチシグトランザクション

p2wpkhはBIP0173で定義されているBech32というアドレス形式を使用する
p2shでp2wpkhをラップする… Segwitスクリプトがp2shのRedeemScriptでネストされる

BIP0141以前
01000000 – version
01 – # of inputs
712e…2f – previous tx hash
00000000 – previous tx index
1715…96 – ScriptSig
feffffff – sequence
02 – # of outputs
3236…00 output amount
1976…ac ScriptPubKey
075a0700 – locktime

BIP0141以降
01000000 – version
00 – Segwit marker
01 – Segwit flag
01 – # of inputs
712e…2f – previous tx hash
00000000 – previous tx index
1716…96 – ScriptSig
feffffff – sequence
02 – # of outputs
3236…00 output amount
1976…ac ScriptPubKey
0248…61 – witness
075a0700 – locktime

p2wpkhとの違いは、ScriptSigが空ではないこと, RedeemScriptがある

    @classmethod
    def parse(cls, s, testnet=False):
        s.read(4)
        if s.read(1) == b'\x00':
            parse_method = cls.parse_segwit
        else:
            parse_method = cls.parse_legacy
        s.seek(-5, 1)
        return parse_method(s, testnet=testnet)
    
    @classmethod
    def parse_legacy(cls, s, testnet=False):
        version = little_endian_to_int(s.read(4))
        num_inputs = read_varint(s)
        inputs = []
        for _ in range(num_inputs):
            inputs.append(TxIn.parse(s))
        num_outputs = read_varint(s)
        outputs = []
        for _ in range(num_outputs):
            outputs.append(TxOut.parse(s))
        locktime = little_endian_to_int(s.read(4))
        return cls(version, inputs, outputs, locktime, testnet=testnet, segwit=False)

    @classmethod
    def parse_segwit(cls, s, testnet=False):
        version = little_endian_to_int(s.read(4))
        marker = s.read(2)
        if marker != b'\x00\x01':
            raise RuntimeError('Not a segwit transaction {}'.format(marker))
        num_inputs = read_varint(s)
        inputs = []
        for _ in range(num_inputs):
            inputs.append(TxIn.parse(s))
        num_outputs = read_varint(s)
        outputs = []
        for _ in range(num_outputs):
            outputs.append(TxOut.parse(s))
        for tx_in in inputs:
            num_items = read_varint(s)
            items = []
            for _ in range(num_items):
                item_len = read_varint(s)
                if item_len == 0:
                    items.append(0)
                else:
                    items.append(s.read(item_len))
            tx_in.witness = items
        locktime = little_endian_to_int(s.read(4))
        return cls(version, inputs, outputs, locktime, testnet=testnet, segwit=True)

    def serialize(self):
        if self.segwit:
            return self.serialize_segwit()
        else:
            return self.serialize_legacy()

    def serialize_legacy(self):
        result = int_to_little_endian(self.version, 4)
        result += encode_varint(len(self.tx_ins))
        for tx_in in self.tx_ins:
            result += tx_in.serialize()
        result += encode_varint(len(self.tx_outs))
        for tx_out in self.tx_outs:
            result += tx_out.serialize()
        result += int_to_little_endian(self.locktime, 4)
        return result   

    def serialize_segwit(self):
        result = int_to_little_endian(self.version, 4)
        result += b'\x00\x01'
        result += encode_varint(len(self.tx_ins))
        for tx_in in self.tx_ins:
            result += tx_in.serialize()
        result += encode_varint(len(self.tx_outs))
        for tx_out in self.tx_outs:
            result += tx_out.serialize()
        for tx_in in self.tx_ins:
            result += int_to_little_endian(len(tx_in.witness), 1)
            for item in tx_in.witness:
                if type(item) == int:
                    result += int_to_little_endian(item, 1)
                else:
                    result += encode_varint(len(item)) + item
        result += int_to_little_endian(self.locktime, 4)
        return result

 //

    def sig_hash_bip143(self, input_index, redeem_script=None, witness_script=None):
        tx_in = self.tx_ins[input_index]
        s = int_to_little_endian(self.version, 4)
        s += self.hash_prevouts() + self.hash_sequence()
        s += tx_in.prev_tx[::-1] + int_to_little_endian(tx_in.prev_index, 4)
        if witness_script:
            script_code = witness_script.serialize()
        elif redeem_script:
            script_code = p2pkh_script(redeem_script.cmds[1]).serialize()
        else:
            script_code = p2pkh_script(tx_in.script_pubkey(self.testnet).cmds[1]).serialize()
        s += script_code
        s += int_to_little_endian(tx_in.value(), 8)
        s += int_to_little_endian(tx_in.sequence, 4)
        s += self.hash_outputs()
        s += int_to_little_endian(self.locktime, 4)
        s += int_to_little_endian(SIGHASH_ALL, 4)
        return int.from_bytes(hash256(s), 'big')

SegwitはSegregated Witnessの略語
Segwitには多数の変更が取り入れられている
– ブロックサイズの増加
– トランザクションマリアビリティの解消
– 明確なアップグレードパスのためのSegwitバージョン管理
– 二次ハッシュの修正
– オフラインウォレット手数料計算のセキュリティ

Segwitトランザクションの最も基本タイプはPay to witness pubkey hash

### p2wpkh
BIP0141, BIP0143で定義されたスクリプトの一つ
p2wpkhは、p2pkhと似ているが、ScriptSigのデータがwitnessフィールドに移動した
マリアビリティとは、取引の内容を変更せずにトランザクションIDを変更できてしまう問題

01000000 – version
00 – Segwit marker
01 – Segwit flag
01 – # of inputs
15e1…56 – previous tx hash
01000000 – previous tx index
00 – ScriptSig
ffffffff – sequence
01 – # of outputs
00b4…output amount
1976…ac ScriptPubKey
0248…ac – witness
00000000 – locktime

marker, flag, witnessのフィールドがある
トランザクションIDの計算に前者のシリアライズが用いられる
witnessフィールドには署名と公開鍵の要素がある
p2wpkhのscriptPubKeyは OP_0 20byte hash

p2wpkhの場合、スクリプトシーケンス OP_0 <20-byte hash>が検出されると、witnessフィールドから公開鍵と署名、20bytesハッシュがp2pkhと同様のシーケンスでコマンドに追加される。
stackの処理はp2pkhとほぼ同じ

SPVはブルームフィルターを作成したら、フィルターの詳細をフルノードに伝える必要がある。
SPVはversionメッセージのオプションにあるリレーフラグを0にする。
その後、フルノードにブルームフィルターを伝える。設定コマンドはfilterload

0a4…0940: bit field, variable field
05000000: Hash count, 4bytes, little endian
63000000: Tweak, 4bytes, little-endian
00: Matched item flag

    def filterload(self, flag=1):
        payload = encode_varint(self.size)
        payload += self.filter_bytes()
        payload += little_endian_to_int(self.function_count, 4)
        payload += little_endian_to_int(self.tweak, 4)
        payload += little_endian_to_int(flag, 1)
        return GenericMessage(b'filterload', payload)

### マークルブロックの取得
getdataでブルームフィルターを通過するトランザクションを要求する
02: Number of data items(varint)
03000000: Type of data item(tx, block, filtered block, compact block), little endian
30…00: Hash identifier

class GetDataMessage:
    command = b'getdata'

    def __int__(self):
        self.data = []

    def add_data(self, data_type, identifier):
        self.data.append((data_type, identifier))

    def serialize(self, identifier):
        result = encode_varint(len(self.data))
        for data_type, identifier in self.data:
            result += int_to_little_endian(data_type, 4)
            result += identifier[::-1]
        return result

Bitcoinで使用されるハッシュ関数はmurmur3と呼ばれ、暗号学的に安全ではないが高速
以下のように定義される
i * 0xfba4c795 + tweak

murmur3

def murmur3(data, seed=0):
    c1 = 0xcc9e2d51
    c2 = 0x1b873593
    length = len(data)
    h1 = seed
    roundedEnd = (length & 0xfffffffc)
    for i in range(0, roundedEnd, 4):
        k1 = (data[i] & 0xff) | ((data[i + 1] & 0xff) << 8) | \
            ((data[i + 2] & 0xff) << 16) | (data[i + 3] << 24)
        k1 *= c1
        k1 = (k1 << 15) | ((k1 & 0xffffffff) >> 17)
        k1 *= c2
        h1 ^= k1
        h1 = (h1 << 13) | ((h1 & 0xffffffff) >> 19)
        h1 = h1 * 5 +  0xe6546b64
    k1 = 0
    val = length & 0x03
    if val == 3:
        k1 = (data[roundedEnd + 2] & 0xff) << 16
    if val in [2, 3]:
        k1 |= (data[roundedEnd + 1] & 0xff) << 8
    if val in [1, 2, 3]:
        k1 |= data[roundedEnd] & 0xff
        k1 *= c1
        k1 = (k1 << 15) | ((k1 & 0xffffffff) >> 17)
        k1 *= c2
        h1 ^= k1
    h1 ^= length
    h1 ^= ((h1 & 0xffffffff) >> 16)
    h1 *= 0x85ebca6b
    h1 ^= ((h1 & 0xffffffff) >> 13)
    h1 *= 0xc2b2ae35
    h1 ^= ((h1 & 0xffffffff) >> 16)
    return h1 & 0xffffffff

BIP37_CONSTANT = 0xfba4c795

from bloomfileter import BloomFilter, BIP37_CONSTANT
from helper import bit_field_to_bytes, murmur3

field_size = 10
function_count = 5
tweak = 99
items = (b'Hello World', b'Goodbye!')
bit_field_size = field_size * 8
bit_field = [0] * bit_field_size
for item in items:
    for i in range(function_count):
        seed = i * BIP37_CONSTANT + tweak
        h = murmur3(item, seed=seed)
        bit = h % bit_field_size
        bit_field[bit] = 1
print(bit_field_to_bytes(bit_field).hex())

    def add(self, item):
        for i in range(self.function_count):
            seed = i * BIP37_CONSTANT + self.tweak
            h = murmur3(item, seed=seed)
            bit = h % (self.size * 8)
            self.bit_field[bit] = 1

対象となるすべてのトランザクションのスーパーセットを作成するのに十分な情報を、軽量クライアントSPVがフルノードに伝える。このスーパーセットを作成するのに、ブルームフィルターを使用する

### ブルームフィルターとは？
対象となり得るすべてのトランザクションを取り出すフィルター
フルノードはブルームフィルターを介してトランザクションを取り扱い、通過するトランザクションに関し、merkleblockコマンドを送信する
=> ハッシュ関数を使用して決定的に数を取得し、モジュロを使用してトランザクションを各入れ物に整理する

集合内の任意のデータに使用可能なコンピュータサイエンスにおける構造
L ビッグエンディアンの整数として解釈し、bit_field_sizeのモジュるを取る

from helper import hash256
bit_field_size = 10
bit_field = [0] * bit_field_size
h = hash256(b'hello world')
bit = int.from_bytes(h, 'big') % bit_field_size
bit_field[bit] = 1
print(bit_field)

$ python3 test.py
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

ブルームフィルターの構成要素は
– ビットフィールドのサイズ
– 使用されるハッシュ関数
– 対象の格納先を示すビットフィールド

複数のアイテムを持つブルームフィルター

from helper import hash256
bit_field_size = 10
bit_field = [0] * bit_field_size
for item in (b'hello world', b'goodbye'):
    h = hash256(item)
    bit = int.from_bytes(h, 'big') % bit_field_size
    bit_field[bit] = 1
print(bit_field)

ハッシュ関数をh160にすると

from helper import hash256, hash160
bit_field_size = 10
bit_field = [0] * bit_field_size
for item in (b'hello world', b'goodbye'):
    h = hash160(item)
    bit = int.from_bytes(h, 'big') % bit_field_size
    bit_field[bit] = 1
print(bit_field)

$ python3 test.py
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]

複数のブルームフィルターをビットフィールドを大幅に短縮できる

from helper import hash256, hash160
bit_field_size = 10
bit_field = [0] * bit_field_size
for item in (b'hello world', b'goodbye'):
    for hash_function in (hash256, hash160):
        h = hash_function(item)
        bit = int.from_bytes(h, 'big') % bit_field_size
        bit_field[bit] = 1
print(bit_field)

$ python3 test.py
[1, 1, 1, 0, 0, 0, 0, 0, 0, 1]

merkleblockの最初の6つ(version, previous block, merkle root, timestamp, bit, nonce)はブロックヘッダーと全く同じ
number of total transaction, number of hashes, hashes, flag bitsが異なる

merkleblockのparse

    @classmethod
    def parse(cls, s):
        version = little_endian_to_int(s.read(4))
        prev_block = s.read(32)[::-1]
        merkle_root = s.read(32)[::-1]
        timestamp = little_endian_to_int(s.read(4))
        bits = s.read(4)
        nonce = s.read(4)
        total = little_endian_to_int(s.read(4))
        num_hashes = read_varint(s)
        hashes = []
        for _ in range(num_hashes):
            hashes.append(s.read(32)[::-1])
        flags_length = read_varint(s)
        flags = s.read(flag_length)
        return cls(version, prev_block, merkle_root, timestamp, bits, nonce, total, hashes, flags)

### フラグビットとハッシュの使用
1. ノード値がハッシュフィールドで指定されている場合、フラグビットは0
2. ノードが内部ノーで、軽量クイライアンとによって計算されている場合、フラッグビットは1
3. ノードがリーフノードで、対象のトランザクションである場合、フラグは1でノード値もハッシュフィールドで指定される

マークルツリーはリーフから上に向かって構築するため、構造を知るために必要なのは存在するリーフの数

from helper import hash256

class MerkleTree:

    def __init__(self, total):
        self.total = total
        self.max_depth = math.ceil(math.log(self.total, 2))
        self.nodes = []
        for depth in range(self.max_depth + 1):
            num_items = math.ceil(self.total / 2**(self.max_depth - depth))
            level_hashes = [None] * num_items
            self.nodes.append(level_hashes)
        self.current_depth = 0
        self.current_index = 0

    def __repr__(self):
        result = []
        for depth, level in enumerate(self.nodes):
            item = []
            for index, h in enumerate(level):
                if h is None:
                    short = 'None'
                else:
                    short = '{}...'.format(h.hex()[:8])
                if depth == self.current_depth and index == self.current_index:
                    items.append('*{}*'.format(short[:-2]))
                else:
                    items.append('{}'.format(short))
            result.append(', '.join(items))
        return '\n'.join(result)

from merkleblock import MerkleTree
from helper import merkle_parent_level
hex_hashes = [
    "9745f7173ef14ee4155722d1cbf13304339fd00d900b759c6f9d58579b5765fb",
    "5573c8ede34936c29cdfdfe743f7f5fdfbd4f54ba0705259e62f39917065cb9b",
    "82a02ecbb6623b4274dfcab82b336dc017a27136e08521091e443e62582e8f05",
    "507ccae5ed9b340363a0e6d765af148be9cb1c8766ccc922f83e4ae681658308",
    "a7a4aec28e7162e1e9ef33dfa30f0bc0526e6cf4b11a576f6c5de58593898330",
    "bb6267664bd833fd9fc82582853ab144fece26b7a8a5bf328f8a059445b59add",
    "ea6d7ac1ee77fbacee58fc717b990c4fcccf1b19af43103c090f601677fd8836",
    "457743861de496c429912558a106b810b0507975a49773228aa788df40730d41",
    "7688029288efc9e9a0011c960a6ed9e5466581abf3e3a6c26ee317461add619a",
    "b1ae7f15836cb2286cdd4e2c37bf9bb7da0a2846d06867a429f654b2e7f383c9",
    "9b74f89fa3f93e71ff2c241f32945d877281a6a50a6bf94adac002980aafe5ab",
    "b3a92b5b255019bdaf754875633c2de9fec2ab03e6b8ce669d07cb5b18804638",
    "b5c0b915312b9bdaedd2b86aa2d0f8feffc73a2d37668fd9010179261e25e263",
    "c9d52c5cb1e557b92c84c52e7c4bfbce859408bedffc8a5560fd6e35e10b8800",
    "c555bc5fc3bc096df0a0c9532f07640bfb76bfe4fc1ace214b8b228a1297a4c2",
    "f9dbfafc3af3400954975da24eb325e326960a25b87fffe23eef3e7ed2fb610e",
]
tree = MerkleTree(len(hex_hashes))
tree.nodes[4] = [bytes.fromhex(h) for h in hex_hashes]
tree.nodes[3] = merkle_parent_level(tree.nodes[4])
tree.nodes[2] = merkle_parent_level(tree.nodes[3])
tree.nodes[1] = merkle_parent_level(tree.nodes[2])
tree.nodes[0] = merkle_parent_level(tree.nodes[1])
print(tree)

$ python3 test.py
*597c4baf.*
6382df3f…, 87cf8fa3…
3ba6c080…, 8e894862…, 7ab01bb6…, 3df760ac…
272945ec…, 9a38d037…, 4a64abd9…, ec7c95e1…, 3b67006c…, 850683df…, d40d268b…, 8636b7a3…
9745f717…, 5573c8ed…, 82a02ecb…, 507ccae5…, a7a4aec2…, bb626766…, ea6d7ac1…, 45774386…, 76880292…, b1ae7f15…, 9b74f89f…, b3a92b5b…, b5c0b915…, c9d52c5c…, c555bc5f…, f9dbfafc…

### Tree traversal

    def up(self):
        self.current_depth -= 1
        self.current_index //= 2

    def left(self):
        self.current_depth += 1
        self.current_index *= 2

    def right(self):
        self.current_depth += 1
        self.current_index = self.current_index * 2 + 1

    def root(self):
        return self.node[0][0]

    def self_current_node(self):
        self.nodes[self.current_depth][self.current_index] = value

    def get_current_node(self):
        return self.nodes[self.current_depth][self.current_index]
    
    def get_left_node(self):
        return self.nodes[self.current_depth + 1][self.current_index * 2]

    def get_right_node(self):
        return self.nodes[self.current_depth + 1][self.current_index * 2 + 1]
    
    def is_leaf(self):
        return self.current_depth == self.max_depth
    
    def right_exists(self):
        return len(self.nodes[self.current_depth + 1]) > self.current_index * 2 + 1

from merkleblock import MerkleTree
from helper import merkle_parent
hex_hashes = [
    "9745f7173ef14ee4155722d1cbf13304339fd00d900b759c6f9d58579b5765fb",
    "5573c8ede34936c29cdfdfe743f7f5fdfbd4f54ba0705259e62f39917065cb9b",
    "82a02ecbb6623b4274dfcab82b336dc017a27136e08521091e443e62582e8f05",
    "507ccae5ed9b340363a0e6d765af148be9cb1c8766ccc922f83e4ae681658308",
    "a7a4aec28e7162e1e9ef33dfa30f0bc0526e6cf4b11a576f6c5de58593898330",
    "bb6267664bd833fd9fc82582853ab144fece26b7a8a5bf328f8a059445b59add",
    "ea6d7ac1ee77fbacee58fc717b990c4fcccf1b19af43103c090f601677fd8836",
    "457743861de496c429912558a106b810b0507975a49773228aa788df40730d41",
    "7688029288efc9e9a0011c960a6ed9e5466581abf3e3a6c26ee317461add619a",
    "b1ae7f15836cb2286cdd4e2c37bf9bb7da0a2846d06867a429f654b2e7f383c9",
    "9b74f89fa3f93e71ff2c241f32945d877281a6a50a6bf94adac002980aafe5ab",
    "b3a92b5b255019bdaf754875633c2de9fec2ab03e6b8ce669d07cb5b18804638",
    "b5c0b915312b9bdaedd2b86aa2d0f8feffc73a2d37668fd9010179261e25e263",
    "c9d52c5cb1e557b92c84c52e7c4bfbce859408bedffc8a5560fd6e35e10b8800",
    "c555bc5fc3bc096df0a0c9532f07640bfb76bfe4fc1ace214b8b228a1297a4c2",
    "f9dbfafc3af3400954975da24eb325e326960a25b87fffe23eef3e7ed2fb610e",
]
tree = MerkleTree(len(hex_hashes))
tree.nodes[4] = [bytes.fromhex(h) for h in hex_hashes]
while tree.root() is None:
    if tree.is_leaf():
        tree.up()
    else:
        left_hash = tree.get_left_node()
        right_hash = tree.get_right_node()
        if left_hash is None:
            tree.left()
        elif right_hash is None:
            tree.right()
        else:
            tree.set_current_node(merkle_parent(left_hash, right_hash))
            tree.up()

print(tree)

奇数の処理
L left_hash, left_hashとする

from merkleblock import MerkleTree
from helper import merkle_parent
hex_hashes = [
    "9745f7173ef14ee4155722d1cbf13304339fd00d900b759c6f9d58579b5765fb",
    "5573c8ede34936c29cdfdfe743f7f5fdfbd4f54ba0705259e62f39917065cb9b",
    "82a02ecbb6623b4274dfcab82b336dc017a27136e08521091e443e62582e8f05",
    "507ccae5ed9b340363a0e6d765af148be9cb1c8766ccc922f83e4ae681658308",
    "a7a4aec28e7162e1e9ef33dfa30f0bc0526e6cf4b11a576f6c5de58593898330",
    "bb6267664bd833fd9fc82582853ab144fece26b7a8a5bf328f8a059445b59add",
    "ea6d7ac1ee77fbacee58fc717b990c4fcccf1b19af43103c090f601677fd8836",
    "457743861de496c429912558a106b810b0507975a49773228aa788df40730d41",
    "7688029288efc9e9a0011c960a6ed9e5466581abf3e3a6c26ee317461add619a",
    "b1ae7f15836cb2286cdd4e2c37bf9bb7da0a2846d06867a429f654b2e7f383c9",
    "9b74f89fa3f93e71ff2c241f32945d877281a6a50a6bf94adac002980aafe5ab",
    "b3a92b5b255019bdaf754875633c2de9fec2ab03e6b8ce669d07cb5b18804638",
    "b5c0b915312b9bdaedd2b86aa2d0f8feffc73a2d37668fd9010179261e25e263",
    "c9d52c5cb1e557b92c84c52e7c4bfbce859408bedffc8a5560fd6e35e10b8800",
    "c555bc5fc3bc096df0a0c9532f07640bfb76bfe4fc1ace214b8b228a1297a4c2",
    "f9dbfafc3af3400954975da24eb325e326960a25b87fffe23eef3e7ed2fb610e",
    "38faf8c811988dff0a7e6080b1771c97bcc0801c64d9068cffb85e6e7aacaf51",
]
tree = MerkleTree(len(hex_hashes))
tree.nodes[5] = [bytes.fromhex(h) for h in hex_hashes]
while tree.root() is None:
    if tree.is_leaf():
        tree.up()
    else:
        left_hash = tree.get_left_node()
        if left_hash is None:
            tree.left()
        elif tree.right_exists():
            right_hash = tree.get_right_node()
            if right_hash is None:
                tree.right()
            else:
                tree.set_current_node(merkle_parent(left_hash, right_hash))
                tree.up()
        else:
            tree.set_current_node(merkle_parent(left_hash, left_hash))
            tree.up()

### マークルペアレント
H = ハッシュ関数
P = 親ハッシュ
L = 左ハッシュ
R = 右ハッシュ

P = H (L||R)

from helper import hash256
hash0 = bytes.fromhex('c117ea8ec828342f4dfb0ad6bd140e03a50720ece40169ee38b\
dc15d9eb64cf5')
hash1 = bytes.fromhex('c131474164b412e3406696da1ee20ab0fc9bf41c8f05fa8ceea\
7a08d672d7cc5')
parent = hash256(hash0+hash1)
print(parent.hex())

$ python3 test.py
8b30c5ba100f6f2e5ad1e2a742e5020491240f8eb514fe97c713c31718ad7ecd

### マークルペアレントレベル
ハッシュの個数が奇数の場合、最後の値を追加してマークルペアレントを計算する

from helper import merkle_parent
hex_hashes = [
     'c117ea8ec828342f4dfb0ad6bd140e03a50720ece40169ee38bdc15d9eb64cf5',
     'c131474164b412e3406696da1ee20ab0fc9bf41c8f05fa8ceea7a08d672d7cc5',
     'f391da6ecfeed1814efae39e7fcb3838ae0b02c02ae7d0a5848a66947c0727b0',
     '3d238a92a94532b946c90e19c49351c763696cff3db400485b813aecb8a13181',
     '10092f2633be5f3ce349bf9ddbde36caa3dd10dfa0ec8106bce23acbff637dae',
]

hashes = [bytes.fromhex(x) for x in hex_hashes]
if len(hashes) % 2 == 1:
    hashes.append(hashes[-1])
parent_level = []
for i in range(0, len(hashes), 2):
    parent = merkle_parent(hashes[i], hashes[i+1])
    parent_level.append(parent)
for item in parent_level:
    print(item.hex())

def_parent_level(hashes):
    if len(hashes) == 1:
        raise RuntimeError('Cannot take a parent level with only 1 item')
    if len(hashes) % 2 == 1:
        hashes.append(hashes[-1])
    parent_level = []
    for i in range(0, len(hashes), 2):
        parent = merkle_parent(hashes[i], hashes[i+1])
        parent_level.append(parent)
    return parent_level

### マークルルート

from helper import merkle_parent_level
hex_hashes = [
    'c117ea8ec828342f4dfb0ad6bd140e03a50720ece40169ee38bdc15d9eb64cf5',
    'c131474164b412e3406696da1ee20ab0fc9bf41c8f05fa8ceea7a08d672d7cc5',
    'f391da6ecfeed1814efae39e7fcb3838ae0b02c02ae7d0a5848a66947c0727b0',
    '3d238a92a94532b946c90e19c49351c763696cff3db400485b813aecb8a13181',
    '10092f2633be5f3ce349bf9ddbde36caa3dd10dfa0ec8106bce23acbff637dae',
    '7d37b3d54fa6a64869084bfd2e831309118b9e833610e6228adacdbd1b4ba161',
    '8118a77e542892fe15ae3fc771a4abfd2f5d5d5997544c3487ac36b5c85170fc',
    'dff6879848c2c9b62fe652720b8df5272093acfaa45a43cdb3696fe2466a3877',
    'b825c0745f46ac58f7d3759e6dc535a1fec7820377f24d4c2c6ad2cc55c0cb59',
    '95513952a04bd8992721e9b7e2937f1c04ba31e0469fbe615a78197f68f52b7c',
    '2e6d722e5e4dbdf2447ddecc9f7dabb8e299bae921c99ad5b0184cd9eb8e5908',
    'b13a750047bc0bdceb2473e5fe488c2596d7a7124b4e716fdd29b046ef99bbf0',
]

hashes = [bytes.fromhex(x) for x in hex_hashes]
current_hashes = hashes
while len(current_hashes) > 1:
    current_hashes = merkle_parent_level(current_hashes)
print(current_hashes[0].hex())

def merkle_root(hashes):
    current_level = hashes
    while len(current_level) > 1:
        current_level = merkle_parent_level(current_level)
    return current_level[0]

### ブロックのマークルルート
マークルツリーのリーフにリトルエンディアンを使い、マークルルートを計算した後、再びリトルエンディアンを使う
文字列のリトルエンディアンは、以下のように実装すれば良いので

print('e8270fb475763bc8d855cfe45ed98060988c1bdcad2ffc8364f783c98999a208'[::-1])

リトルエンディアンでmerkle_rootの計算をした後にリトルエンディアンでreturnする

from helper import merkle_parent_level, merkle_root
tx_hex_hashes = [
    '42f6f52f17620653dcc909e58bb352e0bd4bd1381e2955d19c00959a22122b2e',
    '94c3af34b9667bf787e1c6a0a009201589755d01d02fe2877cc69b929d2418d4',
    '959428d7c48113cb9149d0566bde3d46e98cf028053c522b8fa8f735241aa953',
    'a9f27b99d5d108dede755710d4a1ffa2c74af70b4ca71726fa57d68454e609a2',
    '62af110031e29de1efcad103b3ad4bec7bdcf6cb9c9f4afdd586981795516577',
    '766900590ece194667e9da2984018057512887110bf54fe0aa800157aec796ba',
    'e8270fb475763bc8d855cfe45ed98060988c1bdcad2ffc8364f783c98999a208',
]
tx_hashes = [bytes.fromhex(x) for x in tx_hex_hashes]
hashes = [h[::-1] for h in tx_hashes]
print(merkle_root(hashes)[::-1].hex())

validate merkle root

    def validate_merkle_root(self):
        hashes = [h[::-1] for h in self.tx_hashes]
        root = merkle_root(hashes)
        return root[::-1] == self.merkle_root