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

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

どのノードも初めてネットワークに接続する際、取得して検証すべき最も重要なデータはブロックヘッダーである。
ブロックヘッダーをダウンロード数ルト、複数のノードに完全なブロック非同期に要求してブロックのダウンロードを並列化できる
ブロックヘッダーを取得するコマンドはgetheadersと呼ばれる

7f110100: Protocol version, 4bytes, little-endian, 70015
01: Number of hashes, varint
a35b…00: Starting block, little-endian
0000…00: Ending block, little-endian

class GetHeaderMessage:
    command = b'getheaders'

    def __init__(self, version=70015, num_hashes=1,
        start_block=None, end_block=None):
        self.version = version
        self.num_hashes = num_hashes
        if start_block is None:
            raise RuntimeError('a start block is required')
        self.start_block = start_block
        if end_block is None:
            self.end_block = b'\x00' * 32
        else:
            self.end_block = end_block

    def serialize(self):
        result = int_to_little_endian(self.version, 4)
        result += encode_varint(self.num_hashes)
        result += self.start_block[::-1]
        result += self.end_block[::-1]
        return result

### ヘッダーレスポンス
ノードを作成し、ハンドシェイクした後、ヘッダーを要求できる

from io import BytesIO
from block import Block, GENESIS_BLOCK
from network import SimpleNode, GetHeadersMessage
node = SimpleNone('', testnet=False)
node.handshake()
genesis = Block.parse(BytesIO(GENESIS_BLOCK))
getheaders = GetHeadersMessage(start_block=genesis.hash())
node.send(getheaders)

## headrsメッセージ
02: Number of block headers
00…67: Block header
00: Number of transactions (always 0)

headersメッセージはvarintのヘッダー数(1~2000)
各ブロックヘッダーは80bytes

class HeadersMessage:
    command = b'headers'

    def __init__(self, blocks):
        self.blocks = blocks

    @classmethod
    def parse(cls, stream):
        num_headers = read_varint(stream)
        blocks = []
        for _ in range(num_headers):
            blocks.append(Block.parse(stream))
            num_txs = read_varint(stream)
            if num_txs != 0:
                raise RuntimeError('number of txs not 0')
        return cls(blocks)

from io import BytesIO
from network import SimpleNode, GetHeaderMessage, HeadersMessage
from block import Block, GENESIS_BLOCK, LOWEST_BITS
from helper import calculate_new_bits
previous = Block.parse(BytesIO(GENESIS_BLOCK))
first_epoch_timestamp = previous.timestamp
expected_bits = LOWEST_BITS
count = 1
node = SimpleNode('', testnet=False)
node.handshake()
for _ in range(19):
    getheaders = GetHeadersMessage(start_block=previous.hash())
    node.send(getheaders)
    headers = node.wait_for(HeadersMessage)
    for header in headers.blocks:
        if not header.check_pow():
            raise RuntimeError('bad PoW at block {}'.format(count))
        if header.prev_block != previous.hash():
            raise RuntimeError('discontinuous block at {}'.format(count))
        if count % 2016 == 0:
            time_diff = previous.timestamp - first_epoch_timestamp
            expected_bits = calculate_new_bits(previous.bits, time_diff)
            print(expected_bits.hex())
            first_epoch_timestamp = header.timestamp
        if header.bits != expected_bits:
            raise RuntimeError('bad bits at block {}'.format(count))
        previous = header
        count += 1

VerAckMessageは最小のネットワークメッセージ。AckはAcknoldgeの略称で確認の意味
VerAckMessage :The verack message acknowledges a previously-received version message, informing the connecting node that it can begin to send other messages.
※https://bitcoin-s.org/api/org/bitcoins/core/p2p/index.html

### ネットワークハンドシェイク
ネットワークハンドシェイクの方法
– AがBに接続するためにversionメッセージを送信
– Bがversionメッセージを受信し、verackメッセージで応答し、自身のversionメッセージを送信
※verackはボディー（ペイロード）が無く、メッセージ名だけのメッセージ
– Aはversionメッセージとverackメッセージを受信し、verackメッセージを送信
– Bはverackメッセージを受信し、通信を継続
ハンドシェイク後に通信できる
不正なトランザクションまたはブロックを送信した場合、通信が禁止または切断される可能性がある

### ネットワークへの接続

import socket
from network immport NetworkEnvelop, VersionMessage
host = ''
port = 18333
socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
socket.connect((host, port))
stream = socket.makefile('rb', None)
version = VersionMessage()
envelop = NetworkEnvelop(version.command, version.serialize())
socket.sendall(envelop.serialize())
while True:
    new_message = NetworkEnvelope.parse(stream)
    print(new_message)

class VerAckMessage:
    command = b'verack'

    def __init__(self):
        pass
    
    @classmethod
    def parse(cls, s):
        return cls()
    
    def serialize(self):
        return b''

SimpleNone

class SimpleNone:

    def __init__(self, host, port=None, testnet=False, logging=False):
        if port is None:
            if testnet:
                port = 18333
            else:
                port = 8333
        self.testnet = testnet
        self.logging = logging
        self.socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        self.socket.connect((host, port))
        self.stream = self.socket.makefile('rb', None)
    
    def send(self, message):
        envelope = NetworkEnvelop(
            message.command, message.serialize(), testnet=self.testnet)
        if self.logging:
            print('sending: {}'.format(envelop))
        self.socket.sendall(envelope.serialize())
    
    def read(self):
        envelop = NetworkEnvelop.parse(self.stream, testnet=self.testnet)
        if self.logging:
            print('receiving: {}'.format(envelop))
        return envelope

    def wait_for(self, *message_classes):
        command = None
        command_to_class = {m.command: m for m in message_classes}
        while command not in command_to_class.keys():
            envelope = self.read()
            command = envelop.command
            if command == VersionMessage.command:
                self.send(VerAckMessage())
            elif command == PingMessage.command:
                self.send(PongMessage(envelope.payload))
        return command_to_class[command].parse(envelope.stream())

他のNodeとのハンドシェイク

from network import SimpleNode, VersionMessage
node = SimpleNone('', testnet=True)
version = VersionMessage()
node.send(version)
verack_received = False
version_received = False
while not verack_received and not version_received:
    message = node.wait_for(VersionMessage, VerArckMessage)
    if message.command == VerArckMessage.command:
        verack_received = True
    else:
        version_received = True
        node.sed(VerAckMessage())

handshake

   def handshake(self):
        version = VersionMessage()
        node.send(version)
        self.wait_for(VerAckMessage)

ペイロードとはメッセージを送受信するデータ本体

Protocol version: 4bytes, little-endian
Network services of sender: 8bytes, little-endian
Timestamp, 8bytes, little-endian
Network service of receiver: 8bytes, little-endian
Network address of receiver, 16bytes, IPv4

Network port of receiver: 2bytes
Network services of sender: 8bytes, little-endian
Network address of sender: 16bytes, IPv4

Network port of sender: 2bytes
Nonce: 8bytes, used for communicating response
User agent
Optional flag of relay, based on BIP37(ブルームフィルターで使用)

VersionMessageクラス

class VersionMessage:
    command = b'version'

    def __init__(self, version=70015, services=0, timestamp=None,
                receiver_services=0,
                receiver_ip=b'\x00\x00\x00\x00', receiver_port=8333,
                sender_services=0,
                sender_ip=b'\x00\x00\x00\x00', sender_port=8333,
                nonce=None, user_agent=b'/programmingbitcoin:0.1/',
                latest_block=0, relay=False):
        self.version = version
        self.service = service
        if timestamp is None:
            self.timestamp = int(time.time())
        else:
            self.timestamp = timestamp
        self.receiver_services = receiver_services
        self.receiver_ip = receiver_ip
        self.receiver_port = receiver_port
        self.sender_services = sender_services
        self.sender_ip = sender_ip
        self.sender_port = sender_port
        if nonce is None:
            self.nonce = int_to_little_endian(randint(0, 2**64), 8)
        else:
            self.nonce = nonce
        self.user_agent = user_agent
        self.latest_block = latest_block
        self.relay

serialize

    def serialize(self):
        result = int_to_little_endian(self.version, 4)
        result += int_to_little_endian(self.services, 8)
        result += int_to_little_endian(self.timestamp, 8)
        result += int_to_little_endian(self.receiver_services, 8)
        result += b'\x00' * 10 + b'\xff\xff' + self.receiver_ip
        result += self.receiver_port.to_bytes(2, 'big')
        result += int_to_little_endian(self.sender_services, 8)
        result += b'\x00' * 10 + b'\xff\xff' + self.sender_ip
        result += self.sender_port.to_bytes(2, 'big')
        result += self.nonce
        result += encode_varint(len(self.user_agent))
        result += self.user_agent
        result += int_to_little_endian(self.latest_block, 4)
        if self.relay:
            result += b'\x01'
        else:
            result += b'\x00'
        return result

ネットワークプロトコルを使用してブロックヘッダーを要求、受信、検証している
最初の4bytesは常に同じでネットワークマジックと呼ばれる(通信が中断した場合などに再開の目印になる)
Litecoinノードとbitcoinでは異なるマジックバイト
L bitcoin: 0b110907(testnet)
L bitcoin: f9beb4d9(mainnet)

ネットワークメッセージ
f9beb4d9 – network magic
76657273696f6e00000000 – command
65000000 payload length, 4bytes, little-endian
5f1a69d2 – payload checksum, first 4 bytes of hash256 of payload
7211…01 – payload

bitcoin Protocol documentation
https://en.bitcoin.it/wiki/Protocol_documentation

NETWORK_MAGIC = b'\xf9\xbe\xb4\xd9'
TESTNET_NETWORK_MAGIC = b'\x0b\x11\x09\x07'

class NetworkEnvelop:

    def __init__(self, command, payload, testnet=False):
        self.command = command
        self.palyad = payload
        if testnet:
            self.magic = TESTNET_NETWORK_MAGIC
        else:
            self.magic = NETWORK_MAGIC 

    def __repr__(self):
        return '{}: {}'.format(
            self.command.decode('ascii'),
            self.payload.hex(),
        )

parse

    @classmethod
    def parse(cls, s, testnet=False):
        magic = s.read(4)
        if magic == b'':
            raise IOError('Connection reset!')
        if testnet:
            expected_magic = TESTNET_NETWORK_MAGIC
        else:
            expected_magic = NETWORK_MAGIC
        if magic != expected_magic
            raise SyntaxError('magic is not right {} vs {}'.format(magic.hex(), expected_magic.hex()))
        command = s.read(12)
        command = command.strip(b'\x00')
        payload_length =  little_endian_to_int(s.read(4))
        checksum = s.read(4)
        payload = s.read(payload_length)
        calculated_checksum = hash256(payload)[:4]
        if calculated_checksum != checksum:
            raise IOError('checksum does not match')
        return cls(command, payload, testnet=testnet)

parse sample

from network import NetworkEnvelope
from io import BytesIO
message_hex = 'f9beb4d976657261636b000000000000000000005df6e0e2'
stream = BytesIO(bytes.fromhex(message_hex))
envelope = NetworkEnvelope.parse(stream)
print(envelope.command)
print(envelope.payload)

serialize

    def serialize(self):
        result = self.magic
        result += self.command + b'\x00' * (12 - len(self.command))
        result += int_to_little_endian(len(self.payload), 4)
        result += hash256(self.payload)[:4]
        result += self.payload
        return result

from helper import hash256
block_id = hash256(bytes.fromhex('020000208ec39428b17323fa0ddec8e887b4a7c5\
3b8c0a0a220cfd0000000000000000005b0750fce0a889502d40508d39576821155e9c9e3f5c31\
57f961db38fd8b25be1e77a759e93c0118a4ffd71d'))[::-1]
print('{}'.format(block_id.hex()).zfill(64))

$ python3 test.py
0000000000000000007e9e4c586439b0cdbe13b1370bdd9435d76a644d047523

proof of workはビットコイン全てのブロックヘッダーのハッシュが一定のターゲットを下回らなければならないという要件
ターゲットはビットフィールドから計算される256ビットの数値
exponent(最後の1バイト)とcoefficient(残りの3バイト)
target = coefficient * 256^(exponent-3)

from helper import little_endian_to_int
bits = bytes.fromhex('e93c0118')
exponent = bits[-1]
coefficient = little_endian_to_int(bits[:-1])
target = coefficient * 256**(exponent - 3)
print('{:x}'.format(target).zfill(64))

$ python3 test.py
0000000000000000013ce9000000000000000000000000000000000000000000

有効なProof-of-workはブロックヘッダーハッシュでリトルエンディアン整数として解釈した時にターゲットを下回った時。

proof = little_endian_to_int(hash256(bytes.fromhex('020000208ec39428b17323\
fa0ddec8e887b4a7c53b8c0a0a220cfd0000000000000000005b0750fce0a889502d40508d3957\
6821155e9c9e3f5c3157f961db38fd8b25be1e77a759e93c0118a4ffd71d')))
print(proof < target)

def bits_to_target(bits):
    exponent = bits[-1]
    coefficient = little_endian_to_int(bit[:-1])
    return coefficient * 256**(exponent - 3)

### difficulty
difficulty = 0xffff * 256 ** (0x1d – 3) / target

from helper import little_endian_to_int, hash256
bits = bytes.fromhex('e93c0118')
exponent = bits[-1]
coefficient = little_endian_to_int(bits[:-1])
target = coefficient * 256**(exponent - 3)
difficulty = 0xffff * 256**(0x1d - 3) / target
print(difficulty)

    def target(self):
        return bits_to_target(self.bits)

    def difficulty(self):
        lowest = 0xffff * 256**(0x1d - 3)
        return lowest / self.target

### Proof-of-Workが十分であることの確認
Proof-of-Workはブロックヘッダーのhash256を計算し、これをリトルエンディアン整数として解釈することで求める
これがターゲットより小さい場合、Proof-of-workは有効

    def check_pow(self):
        sha = hash256(self.serialize())
        proof = little_endian_to_int(sha)
        return proof < self.target

### ディフィカルティ調整(difficulty adjustment period)
2016ブロックごとに変更
new_target = previous_target * time_differential/(2週間)

from io import BytesIO
from block import Block
from helper import TWO_WEEKS
last_block = Block.parse(BytesIO(bytes.fromhex('00000020fdf740b0e49cf75bb3\
d5168fb3586f7613dcc5cd89675b0100000000000000002e37b144c0baced07eb7e7b64da916cd\
3121f2427005551aeb0ec6a6402ac7d7f0e4235954d801187f5da9f5')))
first_block = Block.parse(BytesIO(bytes.fromhex('000000201ecd89664fd205a37\
566e694269ed76e425803003628ab010000000000000000bfcade29d080d9aae8fd461254b0418\
05ae442749f2a40100440fc0e3d5868e55019345954d80118a1721b2e')))
time_differential = last_block.timestamp - first_block.timestamp
if time_differential > TWO_WEEKS * 4:
    time_differential = TWO_WEEKS * 4
if time_differential < TWO_WEEKS // 4:
    time_differential = TWO_WEEKS // 4
new_target = last_block.target() * time_differential // TWO_WEEKS
print('{:x}'.format(new_target).zfill(64))

$ python3 test.py
0000000000000000007615000000000000000000000000000000000000000000

最後の2015ブロックを見つけるのに8週間以上かかる場合は、difficultyを減らしすぎないようにする
最後の2015ブロックを見つけるのに3.5日より短い場合は、difficultyを増やしすぎないようにする

def target_to_bits(target):
    raw_bytes = target.to_bytes(32, 'big')
    raw_bytes = raw_bytes.lstrip(b'\x00')
    if raw_bytes[0] > 0x7f:
        exponent = len(raw_bytes) + 1
        coefficient = b'\x00' + raw_bytes[:2]
    else:
        exponent = len(raw_bytes)
        coefficient = raw_bytes[:3]
    new_bits = coefficient[::-1] + bytes([exponent])
    return new_bits

ディフィカルティ調整期間の最初のblock idと最後のblock id
Block 471744
000000203471101bbda3fe307664b3283a9ef0e97d9a38a7eacd88000000000000000000
10c8aba8479bbaa5e0848152fd3c2289ca50e1c3e58c9a4faaafbdf5803c5448ddb84559
7e8b0118e43a81d3

Block 473759
02000020f1472d9db4b563c35f97c428ac903f23b7fc055d1cfc26000000000000000000
b3f449fcbe1bc4cfbcb8283a0d2c037f961a3fdf2b8bedc144973735eea707e126425859
7e8b0118e5f00474

これから、新しいbitを計算する

from io import BytesIO
from block import Block
from helper import TWO_WEEKS, target_to_bits
last_block = Block.parse(BytesIO(bytes.fromhex('000000203471101bbda3fe307664b3283a9ef0e97d9a38a7eacd88000000000000000000\
10c8aba8479bbaa5e0848152fd3c2289ca50e1c3e58c9a4faaafbdf5803c5448ddb84559\
7e8b0118e43a81d3')))
first_block = Block.parse(BytesIO(bytes.fromhex('02000020f1472d9db4b563c35f97c428ac903f23b7fc055d1cfc26000000000000000000\
b3f449fcbe1bc4cfbcb8283a0d2c037f961a3fdf2b8bedc144973735eea707e126425859\
7e8b0118e5f00474')))
time_differential = last_block.timestamp - first_block.timestamp
if time_differential > TWO_WEEKS * 4:
    time_differential = TWO_WEEKS * 4
if time_differential < TWO_WEEKS // 4:
    time_differential = TWO_WEEKS // 4
new_target = last_block.target() * time_differential // TWO_WEEKS
new_bits = target_to_bits(new_target)
print(new_bits.hex())

$ python3 test.py
80df6217

def calculate_new_bits(previous_bits, time_differential):
    if time_differential > TWO_WEEKS * 4:
        time_differential = TWO_WEEKS * 4
    if time_differential < TWO_WEEKS // 4:
        time_differential = TWO_WEEKS // 4
    new_target = bits_to_target(previous_bits) * time_differential // TWO_WEEKS
    return target_to_bits(new_target)

### coinbase transaction
01000000 – version
01 – # of inputs
000…00 – previous tx hash
ffffffff – previous tx index
5e0…00 ScriptSig
ffffffff – sequence
01 – # of outputs
faf20b58…00 – output amount
1976…ac – p2pkh ScriptPubKey
00000000 – locktime

coinbase transactionのインプットは必ず1つになる。
その一つのインプットの前のトランザクションIDは32バイトの00
トランザクションインデックスはffffffff 出なければならない

### Txクラスのis_coinbaseメソッド

class Tx:
  //
      def is_coinbase(self):
        if len(self.tx_ins) != 1:
            return False
        first_input = self.tx_ins[0]
        if first_input.prev_tx != b'\x00' * 32:
            return False
        if first_input.prev_index != 0xffffffff:
            return False
        return True

### Coinbase TxのScriptSig
ScriptSigはマイニングした人によって設定される
2バイト以上、100バイト以下の制限がある

from io import BytesIO
from script import Script
stream = BytesIO(bytes.fromhex('4d04ffff001d0104455468652054696d6573203033\
2f4a616e2f32303039204368616e63656c6c6f72206f6e206272696e6b206f66207365636f6e64\
206261696c6f757420666f722062616e6b73'))
s = Script.parse(stream)
print(s.cmds[2])

$ python3 test.py
b’The Times 03/Jan/2009 Chancellor on brink of second bailout for banks’

### BIP0034
Coinbase transactionのScriptSigの先頭要素を規定する
トランザクションIDの重複を防ぐため、BIP0034が作成されている
BIP0034はソフトフォークルールで、マイニングされたブロックの高さをコインベースのScriptSigの先頭要素に追加する
リトルエンディアン整数として解釈され、ブロックの高さと同じ

コインベーストランザクションから高さをパースする方法

from io import BytesIO
from script import Script
from helper import little_endian_to_int
stream = BytesIO(bytes.fromhex('5e03d71b07254d696e656420627920416e74506f6f\
6c20626a31312f4542312f4144362f43205914293101fabe6d6d678e2c8c34afc36896e7d94028\
24ed38e856676ee94bfdb0c6c4bcd8b2e5666a0400000000000000c7270000a5e00e00'))
script_sig = Script.parse(stream)
print(little_endian_to_int(script_sig.cmds[0]))

    def coinbase_height(self):
        if not self.is_coinbase():
            return None
        element = self.tx_ins[0].script_sig.cmds[0]
        return little_endian_to_int(element)

ScriptSigの先頭cmdsにCoinbase　ブロックヘッダーの高さが入ってるのね。

### ブロックヘッダー
ブロックヘッダーは以下で構成されている
– Version、Previous Block, Merkle Root, Timestamp, Bits, Nonce
02000020 – version
8ec3…00 – previous block
5b07…be – merkle root
1e77a759 – timestamp
e93c0118 – bits
a4ffd71d – nonce

ブロックIDはヘッダーのhash256のリトルエンディアンの16進数表記

version, prev_block, merkle_root, timestampはlittle_endian, bitsとnonceはそのまま。

    @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)
        return cls(version, prev_block, merkle_root, timestamp, bits, nonce)

    def serialize(self):
        result = int_to_little_endian(self.version, 4)
        result += self.prev_block[::-1]
        result += self.merkle_root[::-1]
        result += int_to_little_endian(self.timestamp, 4)
        result += self.bits
        result += self.nonce
        return result

    def hash(self):
        s = self.serialize()
        sha = hash256(s)
        return sha[::-1]

### ブロックのバージョンについて
バージョン2は、コインベース・トランザクションにブロック高を指定するBIP0034にソフトウェアが対応していることを意味する
バージョン3はDERエンコーディングを強制するBIP0066に対応していることを意味する
バージョン4はOP_CHECKLOCKTIMEVERIFYを規定するBIP0065に対応していることを意味する

BIP0009は4バイトヘッダーのうち、先頭3ビットを001に固定してマイナーがBIP0009に対応していることを示す

from io import BytesIO
from block import Block
b = Block.parse(BytesIO(bytes.fromhex('020000208ec39428b17323fa0ddec8e887b\
4a7c53b8c0a0a220cfd0000000000000000005b0750fce0a889502d40508d39576821155e9c9e3\
f5c3157f961db38fd8b25be1e77a759e93c0118a4ffd71d')))
print('BIP9: {}'.format(b.version >> 29 == 0b001))
print('BIP91: {}'.format(b.version >> 4 & 1 == 1))
print('BIP9: {}'.format(b.version >> 1 & 1 == 1))

$ python3 test.py
BIP9: True
BIP91: False
BIP9: True

上記をclassに含める。if ~ return trueではなく、そのままreturnと書いてしまって良い
[class]
def bip9(self):
return self.version >> 29 == 0b001

def bip91(self):
return self.version >> 4 & 1 == 1

def bip141(self):
return self.version >> 1 & 1 == 1
[/code]

### 前のブロック
全てのブロックは前のブロックを指している必要がある

### マークルルート
全てのトランザクションを32バイトハッシュにエンコードする

### timestamp
unix形式の4bytes。Unixタイムスタンプは1970年1月1日からの秒数

### bits
BitsはそのブロックのProof of Workに必要な値をエンコードするフィールド

### Nonce(number used only once)
一度だけ使われる数値の略

### ブロックの構造と識別子
Block Size: 4bytes
Block Header: 80
Transaction Counter: 1~9 (ブロックに含まれているトランザクション数)
Transactions: 可変(トランザクションのリスト)

### ブロックヘッダの構造
Version: 4bytes
Previous Block Hash: 32
Merkle Root: 32
Timestamp: 4
Difficulty Target: 4
Nonce: 4

ブロックヘッダだけ保持するノードをSPV(Simplified Payment Verification)ノードという
ブルームフィルタとは、「このトランザクションを確認できるマークルパスをrequest」という要求を粗い要求に転換することで、どのトランザクションに関心があるかを特定しにくくするもの(BIP0037)

### 通常のトランザクションとcoinbaseトランザクション
通常のトランザクション
Transaction Hash: 32bytes
Output Index: 4
Unlockking Script Size: 1~9
Unlocking Script: 可変

coinbaseトランザクション
Transaction Hash: 32(他のトランザクションを参照しないため、全てのビットが「0」固定)
Output Index: 4 全てのビットが1固定
Coinbase Data Size: 1~9　(coinbase data sizeは2~100bytes)
Coinbase Data: 可変 (Extra NonceやMining Tagに使われる)
Sequence Number: 4(0x00000000)

### Segregated Witness
Segregated Witnessはトランザクションの署名をトランザクションインプットから切り離し別の領域に移す仕様で、2017年8月にアクティベートされた
サイズの大きい署名部分をトランザクションから切り離してwitnessに格納する
Lightning Netowrokとは、最初のトランザクションと最後のトランザクションのみをビットコインネットワークのブロックに記録して、その間のトランザクションはライトニングネットワーク内でのみ記録する

– SegWitのトランザクションの構造
Version no: 4bytes
Marker: 1 ★追加
Flag: 1
Input Counter: 1~9 (インプットの数)
Inputのリスト: 可変
Output Counter: 1~9 (アウトプットの数)
Outputのリスト: 可変
Script Witness: 可変 (witnessの要素の数とwitnessが設定される)
Locktime:4

### ブロックサイズの計算方法
block wight = ベースサイズ(全トランザクションのバイト数) * 3 + トータルサイズ(witnessを含むSegwit構造での全トランザクションバイト数)

P2WPKHでは
Locking Script: OP_0

m: 署名対象のメッセージ
Q = dG : Q公開鍵、dは秘密鍵、Gはsecp256k1ベースポイント
n: secp256k1の位数

### ECDSA署名の生成
1. ハッシュ関数にメッセージmを渡し、ハッシュ値m’を取得する(m’=H(m))
2. [1, n-1]の範囲からkを選択し、楕円曲線上の点Rを k*Gで求める (R = kG)
3. R= rx, ry とする。Rのx座標rxを位数nで割った余剰を求める r = rx mod n
4. s = (m'(ハッシュしたメッセージ) + d(秘密鍵)*r(Rのx座標)) / k(任意の点) mod n
5. (r, s)が m に対する署名となる

### ECDSA署名の検証
1. P = (px, py)とする
P = m’/s * G + r / s * Q (公開鍵)(mod n)
この時、Px = r(mod n) となるとき、署名検証に成功

パラメータkを生成
$ openssl ecparam -genkey -name secp256k1 -out k.pem; ls k.pem
$ openssl ec -in k.pem -outform DER | tail -c +8 | head -c 32 | xxd -p -c 32
read EC key
writing EC key
a891fce013c907a3ce5e157d1edc474bbdf7efc0c133b41cad14aca3566c914c
$ k=a891fce013c907a3ce5e157d1edc474bbdf7efc0c133b41cad14aca3566c914c

Rを生成
$ openssl ec -in k.pem -pubout -outform DER | tail -c 65 | xxd -p -c 65
read EC key
writing EC key
042ce7c2a48e71ad11e4445b3901d4afe715c0298ed1504cb4ce47b426d83bfaa7bb4665d4c92b9484c4b0ce5cfcabe089e1e2a7c8e32a3c6b5f2d2c0ba301fb97
$ R=042ce7c2a48e71ad11e4445b3901d4afe715c0298ed1504cb4ce47b426d83bfaa7bb4665d4c92b9484c4b0ce5cfcabe089e1e2a7c8e32a3c6b5f2d2c0ba301fb97

Rからrxを取り出し、変数rxに格納
$ rx=`echo $R | cut -c3-66`; echo $rx
2ce7c2a48e71ad11e4445b3901d4afe715c0298ed1504cb4ce47b426d83bfaa7

メッセージのハッシュ値を生成し、変数mhに格納
$ mh=`cat message.txt | xxd -r -p | openssl dgst -sha256 | cut -c10-`; echo $mh
stdin)= 45f83d17e10b34fca01eb8f4454dac34a777d9404a464e732cf4abf2c0da94c4

公開鍵をQに格納
$ Q=$pubKey; echo $Q
047a2b8a7974ed6f4b7817b0f354c6c81ceacb210e53e093eadcd4d4ece0bb4d60a0864e802eb58b813183cd4bae108588e062ec61e6bff36f68ad530ee11cff15

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def multiply_inv(a, m):
    if a < 0:
        a = a % m
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('multiply modular inverse does not exist')
    else:
        return x % m