Python
ビットコイン
ブロックチェーン

Pythonでマークルツリー(ハッシュ木)を書いてみた(ブロックチェーン)

マークルツリーをPythonで書いてみました。

マークルツリーとは

ブロックは、それに含まれる全てのトランザクションの存在を証明出来るハッシュ値を持つ必要があります。
最も単純な方法は、全てのトランザクションのハッシュをNつ連ねた物のハッシュを持つことです。
しかし、この方法では、あるトランザクションの存在を証明するために、その他すべてのトランザクションのハッシュ値が必要になってしまいます。
この、あるトランザクションの証明をするために必要なハッシュの数、を減らすための手法が、マークルツリーです。
マークルツリーを使うと、おおよそlog2N個のハッシュ値を持てばいいことになります。
詳しくは…
(http://bitcoin.peryaudo.org/detail.html)

コード

from hashlib import sha256
def generate_hash(argument):
    return sha256(str(argument).encode()).hexdigest()

def create_pairs(itera):
    '''
    [a,b,c,d] ⇒ [[a,c], [b,d]]
    '''
    length = len(itera)
    if length%2 != 0:
        length = length-1
    half   = round(length/2)
    former = itera[:half]
    latter = itera[half:]
    lst = [[former[i], latter[i]] for i in range(half)]
    if len(itera)%2 != 0:
        lst.append([itera[-1]])
    return lst

class Transaction:
    '''
    Attribute:
        self.hash_list: a list to record how transactions contributed to the creation of the root hash.
    '''
    def __init__(self, data):
        self.data = data
        self.hash = generate_hash(self.data)
        self.hash_list = []

    def proof(self, root):
        for hash in self.hash_list:
            if hash['position'] == 'right':
                self.hash = generate_hash(hash['hash'] + self.hash)
            else:
                self.hash = generate_hash(self.hash + hash['hash'])

        if self.hash == root:
            return True
        else:
            return False
class InitNode:
    '''
    This class reform Transaction instance to usable form for Node class.
    '''
    def __init__(self, transaction):
        self.parent = transaction.hash
        self.own_transactions = [transaction]        

class Node:
    def __init__(self, child_node_or_nodes):
        '''
        This class has one node(or initnode), or list of two nodes as an argument.

        If this class have only one nodes(or initnode),
        processing is not performed.

        If this class have two node,
        1.create next hash(self.parent)
        2.call self.exchange(), and record the hash and position to Transaction.hash_list.

        Attribute:
            own_transactions: List of Transaction instance which is source of self.parent.
        '''
        self.own_transactions = []
        if len(child_node_or_nodes)==2:
            self.left  = child_node_or_nodes[0]
            self.right = child_node_or_nodes[1]
            self.parent = generate_hash(str(self.left.parent) + str(self.right.parent))
            self.exchange_hash()
        if len(child_node_or_nodes)==1:
            node =child_node_or_nodes[0]
            self.parent = node.parent
            self.own_transactions = node.own_transactions

    def exchange_hash(self):
        '''
        record the hash and position to Transaction.hash_list.
        '''
        for transaction in self.right.own_transactions:
            transaction.hash_list.append({'hash': self.left.parent,
                                          'position': 'right'
                                         })
        for transaction in self.left.own_transactions:
            transaction.hash_list.append({'hash': self.right.parent,
                                          'position': 'left'
                                         })
            self.own_transactions = self.left.own_transactions + self.right.own_transactions

class Tree:
    def __init__(self, transactions):
        self.transactions = [Transaction(transaction) for transaction in transactions]
        self.nodes     = [InitNode(transaction_instance) for transaction_instance in self.transactions]
        self.find_root()

    def back_to_root(self):
        pairs = create_pairs(self.nodes)
        self.nodes = [Node(pair) for pair in pairs]

    def find_root(self):
        while len(self.nodes)>1:
            self.back_to_root()
        self.root = Node(self.nodes).parent

Transactionクラス…
hash_listに、証明のために必要なhash値を格納し、証明のためのメソッド、proof()を使うためのクラス
Nodeクラス…
子nodeを使って、親nodeを生成し、Transaction.hash_listに、必要なhash値を送るためにクラス。
own_transaction…
ノードのハッシュを作るのに寄与したトランザクションのリストです。
あるトランザクションが、あるノードのown_transactionに所属しているということは、
1.そのown_transactionを持つノードが子ノードとして、親ノードのハッシュ生成に使われたときの他方のハッシュが、そのトランザクションの証明の際の必要十分条件になる。
2.親ノードのown_transactionにも必ず含まれる
と言うことです。
InitNodeクラス…
最初のNodeインスタンスは、引数にnodeを持てないので、Transactionインスタンスを使って、Nodeクラスの引数となれるインスタンスを生成するためのクラス
Treeクラス…
上記をつなげるクラス。

import random
transactions = set()
while len(transactions) <= 100:
    transactions.add(random.randint(0,1000))
transactions = list(transactions)
transactions = [str(t) for t in transactions]
tree = Tree(transactions)
tree.root
'39a346fd3e2f243424cf12f52fe9aa8878ce914453f788345851f0169881b49f'
for transaction in tree.transactions:
    print(transaction.proof(tree.root), len(transaction.hash_list))
True, 7
True, 7

100つのトランザクションであれば、だいたい7つのハッシュ値を記録しておけば証明に事足りることが分かりますんべ。
分かりにくかったり、間違っていたら、修復、削除しますのでよろしくお願いします。