머클루트 구하기

트랜잭션의 유효성 검증을 하기위해 머클루트가 사용되는데, 이 머클루트를 구하는 방법을 한번 알아보도록 하겠습니다.

머클트리는 이전 포스팅에서 설명을 한것처럼 다음 그림과 같은 구조를 가지고 있습니다.

하위 노드를 더한값을 해쉬하여 상위노드의 값을 만들고, 이과정을 반복하여 최상위 root hash를 생성합니다.

그럼 이 과정을 수행하는 python 코드를 사용하여 실제 머클루트를 생성해보도록 하겠습니다.

import hashlib
# Hash pairs of items recursively until a single value is obtained
def merkle(hashList):
    if len(hashList) == 1:
        return hashList[0]
    newHashList = []
    # Process pairs. For odd length, the last is skipped
    for i in range(0, len(hashList)-1, 2):
        newHashList.append(hash2(hashList[i], hashList[i+1]))
    if len(hashList) % 2 == 1: # odd, hash last item twice
        newHashList.append(hash2(hashList[-1], hashList[-1]))
    return merkle(newHashList)
def hash2(a, b):
    # Reverse inputs before and after hashing
    # due to big-endian / little-endian nonsense
    a1 = a.decode('hex')[::-1]
    b1 = b.decode('hex')[::-1]
    h = hashlib.sha256(hashlib.sha256(a1+b1).digest()).digest()
    return h[::-1].encode('hex')
# https://www.blockchain.com/en/btc/block/000000000003ba27aa200b1cecaad478d2b00432346c3f1f3986da1afd33e506
txHashes = [
"8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87",
"fff2525b8931402dd09222c50775608f75787bd2b87e56995a7bdd30f79702c4",
"6359f0868171b1d194cbee1af2f16ea598ae8fad666d9b012c8ed2b79a236ec4",
"e9a66845e05d5abc0ad04ec80f774a7e585c6e8db975962d069a522137b80c1d",
]
 
print merkle(txHashes)

연산을 위한 데이타는 숫자값은 기본적으로 little endian으로 표현이 되어야 하고, hex값은 reverse ordering 되어야 합니다.

그리고, hash 연산을 위해서는 hex 포맷이 아닌 bin 포맷으로 변환이 되어야 합니다.

즉, 연산에 필요한 데이타를 little endian으로 변환한후에 hex를 bin으로 변환하여 double hash 연산을 수행하고 다시 반대로 hex 포맷으로 변경후 big endian으로 변경을 하여야 합니다.

결과를 한번 확인해보도록 하겠습니다.

위의 코드는 100000번째 블록의 트랜잭션정보를 가지고 머클루트를 계산한 결과이며 다음과 같이 계산결과와 실제 블록의 머클루트값이 일치합니다.

https://www.blockchain.com/en/btc/block/000000000003ba27aa200b1cecaad478d2b00432346c3f1f3986da1afd33e506