Merkel Tree In Bitcoin
비트코인에서 Merkle Root는 블록체인 내에서 블록의 모든 트랜잭션을 요약하여 제공하는 해시 값입니다. Merkle Root는 블록 헤더의 일부로 포함되며, 트랜잭션의 무결성과 일관성을 검증하는 데 중요한 역할을 합니다.
Merkle Root를 검증하게 되면 트리를 구성하는 모든 노드의 해시 값이 검증되기 때문에 효율성 측면에서도 중요한 역할을 합니다.
머클트리는 위 사진과 같은 구조를 가지고 있습니다. 리프노드의 data를 해시한 값들을 2개씩 묶어 sha-256으로 해싱해 부모 노드를 만들며 단 하나의 해시 값만이 남을 때까지 과정을 반복합니다.
만약 노드의 개수가 홀수라면 마지막 노드는 해당 노드를 더 한뒤 해싱을 진행하면 됩니다.(짝수개로 맞춰 줍니다.)
여기서 노드들을 더해서 해싱할 때 중요한 사실이 하나 있습니다. sha256을 두번 써줘야 합니다. 따라서 아래의 코드 처럼 두개의 해시 값을 합쳐 부모 노드를 생성할 때 sha256을 이중으로 적용해 두번 해싱해 주어야 합니다.
def double_sha256(s):
return hashlib.sha256(hashlib.sha256(s).digest()).digest()그리고 한가지 더 유의해야 할 점은 bitcoin은 트랜잭션 해시 값이 주어질 때 little endian 형식으로 표시되기 때문에 임의의 트랜잭션 해시 값을 생성할 때 반드시 little endian 방식으로 생성해야 합니다.
Little Endian
리틀 엔디언(Little Endian) 방식은 데이터의 바이트 순서를 저장하는 방법 중 하나입니다. 주로 컴퓨터 시스템에서 데이터를 메모리에 저장하거나 전송할 때 사용됩니다. 리틀 엔디언 방식에서는 가장 낮은 의미의 바이트(LSB, Least Significant Byte)가 먼저 저장되고, 가장 높은 의미의 바이트(MSB, Most Significant Byte)가 나중에 저장됩니다.
예시. 0x12345678을 little endain 방식으로 저장하는 경우
메모리 주소: | 0x00 | 0x01 | 0x02 | 0x03 |
값: | 0x78 | 0x56 | 0x34 | 0x12 |작은 값 부터 저장하기 때문에 위와 같이 저장됩니다.
따라서 임의의 트랜잭션 값을 만들어 줄 경우 little endian 방식으로 생성해 주어야 합니다.
trial_hash = hashlib.sha256(i.to_bytes(2, byteorder='little')).digest()[::-1].hex()아래는 위 규칙을 지켜 비트코인 블록 헤더에 포함되어 있는 머클루트를 구하는 코드입니다.
import requests
import hashlib
def double_sha256(s):
return hashlib.sha256(hashlib.sha256(s).digest()).digest()
def calculate_merkle_root(tx_hashes):
tx_hashes = [bytes.fromhex(tx)[::-1] for tx in tx_hashes]
while len(tx_hashes) > 1:
if len(tx_hashes) % 2 != 0:
tx_hashes.append(tx_hashes[-1])
new_level = []
for i in range(0, len(tx_hashes), 2):
combined = tx_hashes[i] + tx_hashes[i + 1]
new_level.append(double_sha256(combined))
tx_hashes = new_level
return tx_hashes[0][::-1].hex()
tx_list = [
'transacions'
]
result = calculate_merkle_root(tx_list)
비트코인 머클트리 : https://www.investopedia.com/terms/m/merkle-tree.asp
