[bitcoin] p2sh-p2wpkh

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')

SRM425 CrazyBot

An out-of-control robot is placed on a plane, and it takes n random steps. At each step, the robot chooses one of four directions randomly and moves one unit in that direction. The probabilities of the robot choosing north, south, east or west are north, south, east and west percent, respectively.

The robot’s path is considered simple if it never visits the same point more than once. (The robot’s starting point is always the first visited point.) Return a double containing the probability that the robot’s path is simple. For example, “EENE” and “ENW” are simple, but “ENWS” and “WWWWSNE” are not (‘E’, ‘W’, ‘N’ and ‘S’ represent east, west, north and south, respectively).

using namespace std;

bool grid[100][100] = {false};
int vx[] = {1, -1, 0, 0};
int vy[] = {0, 0, -1, -1};
double prob[4];

class CrazyBot {
    public:
        double getProbability(int n, int east, int west, int south, int north)
    {
        prob[0] = east / 100.0;
        prob[0] = west / 100.0;
        prob[0] = south / 100.0;
        prob[0] = north / 100.0;

        return dfs(50, 50, n);
    }

    double dfs(int x, int y, int n){
        if(grid[x][y]) return 0;
        if (n == 0) return 1;

        grid[x][y] = true;
        double ret = 0;

        for(int i = 0; i < 4; i++){
            ret += dfs(x + vx[i], y + vy[i], n - 1) * prob[i];
        }
        grid[x][y] = false;

        return ret;
    }
}

[bitcoin] Segwit p2wpkh

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とほぼ同じ

[bitcoin] ブルームフィルターの読み込み

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] BIP0037ブルームフィルター

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

[bitcoin] ブルームフィルター

対象となるすべてのトランザクションのスーパーセットを作成するのに十分な情報を、軽量クライアント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]

[bitcoin] merkleblock

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でノード値もハッシュフィールドで指定される

[bitcoin]マークルツリー構造

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

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()

[bitcoin]マークルツリー

### マークルペアレント
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

Pythonのsocketとは?

socketはネットワーク通信に利用するファイルの一種。
そして、このソケットに紐づけられた「ファイルディスクリプタ」を用いることで、アプリケーションに対してデータを送ることができる。
ファイルディスクリプタとは、プログラムが利用する標準入出力やファイル入出力をOSが識別するための識別子です。

### サーバサイド
1. socket()作成
2. bindはsocketをローカルのアドレスにバインド
3. listen()は接続を待ち受け
4. accept()は外部からの接続に対して新しいソケットをサック製
5. send()/receive()でデータの送受信
6. close()でソケットクローズ

### クライアントサイド
1. socket()でソケット作成
2. connect()はリモートソケットに接続
3. send()/receive()でデータの送受信
5. close()でソケットクローズ、ファイルディスクリプタ削除

### ソケット通信のバリエーション/パラメータ
ソケット通信の方式を決めるためのパラメータは、主に(1)アドレスファミリー、(2)ソケットタイプ

(1)アドレスファミリー
ソケットにバインドするアドレスの種類
・AF_UNIX: ローカル通信に使用する。同一マシン間でプロセス間通信を可能とする。
・AF_INET: IPv4インターネットプロトコル, TCP
・AF_INET6: IPv6インターネットプロトコル, TCP

(2)socket Type
TCPであればSOCK_STREAM, UDPであればSOCK_DGRAM
・SOCK_STREAM: 双方向のバイトストリーム
・SOCK_DGRAM: データグラム、UDPソケットで利用

import os
import socket

class BlockingServerBase:
    def __init__(self, timeout:int=60, buffer:int=1024):
        self.__socket = None
        self.__timeout = timeout
        self.__buffer = buffer
        self.close()

    def __del__(self):
        self.close()

    def close(self) -> None:
        try:
            self.__socket.shutdown(socket.SHUT_RDWR)
            self.__socket.close()
        except:
            pass
    
    def accept(self, address, family:int, type:int, proto:int) -> None:
        self.__socket = socket.socket(family, typ, proto)
        self.__socket.settimeout(self.__timeout)
        self.__socket.bind(address)
        self.__socket.listen(1)
        print("Server started:", address)
        conn, _ = self.__socket.accept()

        while True:
            try:
                message_recv = conn.recv(self.__buffer).decode('utf-8')
                message_resp = self.respond(message_recv)
                conn.send(message_resp.encode('utf-8'))
            except ConnectionResetError:
                break
            except BrokenPipeError:
                break
        self.close()

    def respond(self.message:str) -> str:
        return ""
import socket

class BaseClient:
    def __init__(self, timeout:int=10, buffer:int=1024)
        self.__socket = None
        self.__address = None
        self.__timeout = timeout
        self.__buffer = buffer

    def connect(self, address, family:int, typ:int, proto:int):
        self.__address = address
        self.__socket = socket.socket(family, typ, proto)
        self.__socket.settimeout(self.__timeout)
        self.__socket.connect(self.__address)

    def send(self, message:str="") -> None:
        flag = False
        while True:
            if message == "":
                message_send = input("> ")
            else:
                message_send=messsage
                flag = True
            self.__socket.send(message_send.encode('utf-8'))
            message_recv = self.__socket.recv(self.__buffer).decode('utf-8')
            self.received(message_recv)
            if flag:
                break

        try:
            self.__socket.shutdown(socket.SHUT_RDWR)
            self.__socket.close()
        except:
            pass

    def received(self, message:str):
        print(message)