비트코인 블록에서 머클 루트 계산

블록을 구성하는 트랜잭션들의 해시 값들로부터 계산하는 머클 루트는 블록 헤더에 포함됩니다. 이 문서에서는 머클 루트를 계산하는 과정을 소개하고 이를 구현하는 파이썬 소스 코드를 제시합니다.

배경 지식

엔디언

출처: 위키피디어: 엔디언

비트코인 블록 정보

다음은 2개의 트랜잭션으로 이루어진 비트코인 블록 99,997의 머클 루트 값과 두 트랜잭션의 해시 값입니다.

이 블록의 머클 루트 값은 다음과 같습니다.

5140e5972f672bf8e81bc189894c55a410723b095716eaeec845490aed785f0e

두 트랜잭션의 해시 값은 다음과 같습니다.

0: b86f5ef1da8ddbdb29ec269b535810ee61289eeac7bf2b2523b494551f03897c
1: 80c6f121c3e9fe0a59177e49874d8c703cbadee0700a782e4002e87d862373c6

머클 루트 계산 과정

아래의 1번과 4번 과정은 비트코인 도구가 해시 값을 빅 엔디안으로 표현하고 있기 때문에 필요한 처리 과정입니다. 해시 문자열에서 연속하는 2개의 문자가 한 바이트에 대한 16진 표현에 해당합니다.

1. 트랜잭션의 해시 값을 리틀 엔디안으로 변환하기 (바이트 배열로 표현했을 때 역순으로 재배열)

0: 7c89031f5594b423252bbfc7ea9e2861ee1058539b26ec29dbdb8ddaf15e6fb8
1: c67323867de802402e780a70e0deba3c708c4d87497e17590afee9c321f1c680

2. 두 해시 이어 붙이기

7c89031f5594b423252bbfc7ea9e2861ee1058539b26ec29dbdb8ddaf15e6fb8c67323867de802402e780a70e0deba3c708c4d87497e17590afee9c321f1c680

3. 이어 붙인 해시에 대하여 두 번 연속 SHA256 해시 계산하기

0e5f78ed0a4945c8eeea1657093b7210a4554c8989c11be8f82b672f97e54051

4. 해시 값을 빅 엔디안으로 변환하기 (바이트 배열로 표현했을 때 역순으로 재배열)

5140e5972f672bf8e81bc189894c55a410723b095716eaeec845490aed785f0e

위의 4번 과정의 결과가 머클 루트입니다.

완전한 파이썬 코드

################################################################################

# Calculate Merkle Root                                                        #

################################################################################

import os, sys, traceback

import binascii

import hashlib

################################################################################

# Functions                                                                    #

################################################################################

def double_hash(hex):

   bin = binascii.unhexlify(hex)

   hash = hashlib.sha256(bin).digest()

   hash2 = hashlib.sha256(hash).digest()

   return binascii.hexlify(hash2)

def calculate_merkle_root(left, right):

    # Convert them in little-endian hex notation

    left  = binascii.hexlify(binascii.unhexlify(left)[::-1])

    right = binascii.hexlify(binascii.unhexlify(right)[::-1])

    # Concatenate the pair

    hex = left + right

   

    # Take double SHA256 hash

    hash = double_hash(hex)

   

    # Convert result to big-endian hex notation

    root = binascii.hexlify(binascii.unhexlify(hash)[::-1])

    root = str(root, "ascii")

   

    return root

def main():

    # Transaction hashes of BTC block # 99997

    h1 = 'b86f5ef1da8ddbdb29ec269b535810ee61289eeac7bf2b2523b494551f03897c'

    h2 = '80c6f121c3e9fe0a59177e49874d8c703cbadee0700a782e4002e87d862373c6'

    merkle_root = calculate_merkle_root(h1, h2)

    print(merkle_root)

################################################################################

# Main                                                                         #

################################################################################

if __name__ == '__main__':

    try:

        main()

    except:

        traceback.print_exc(file=sys.stdout)