머클 트리 구축: 수천 개 트랜잭션을 하나의 해시로 요약하기

레슨 7에서 여기까지

지난 시간에 UTXO 모델을 구현하면서 블록 안에 트랜잭션이 쌓이는 구조를 만들었다. 코인베이스로 코인을 생성하고, UTXO를 소비하고, 이중 지불을 차단하는 데까지 왔다. 그런데 한 가지 질문을 던져보자.

블록 하나에 트랜잭션이 2,000개 들어있다. 내 트랜잭션이 이 블록에 정말 포함됐는지 확인하려면?

가장 무식한 방법은 2,000개를 전부 다운로드해서 하나씩 비교하는 것이다. 레슨 4에서 블록의 해부학을 다룰 때, 블록 헤더에 6가지 필드가 있다고 했다. 그 중 하나가 바로 **머클 루트(Merkle Root)**다. 그때는 "트랜잭션 요약" 정도로만 넘어갔는데, 오늘 그 내부를 완전히 해부한다.

오늘의 미션

📦 만들 것: merkle.py 모듈
├── build_merkle_tree()    — 트랜잭션 리스트 → 전체 트리 구축
├── get_merkle_root()      — 머클 루트 해시 반환
├── generate_proof()       — 특정 트랜잭션의 포함 증명 생성
└── verify_proof()         — 증명 검증 (SPV 클라이언트 핵심)
🔗 통합: Block 클래스에 merkle_root 필드 추가

완성하면 2,000개의 트랜잭션 중 하나를 딱 11번의 해시 연산으로 검증할 수 있다. O(n)이 O(log n)으로 바뀌는 순간이다.

1. 머클 트리란 — '토너먼트 대진표' 비유

월드컵을 떠올려보자. 32개 팀이 출전하면 16강 → 8강 → 4강 → 결승을 거쳐 딱 하나의 우승팀이 나온다. 머클 트리도 정확히 같은 구조다.

• 잎(Leaf): 각 트랜잭션의 해시 — 레슨 1에서 배운 SHA-256이 여기서 쓰인다
• 중간 노드: 자식 두 개의 해시를 합쳐서 다시 해시
• 루트: 최종 하나의 해시 — 이게 블록 헤더에 들어간다

핵심 성질: 맨 아래 트랜잭션 하나라도 1비트 바뀌면, 그 위의 모든 해시가 연쇄적으로 바뀌고, 결국 루트가 완전히 달라진다. 레슨 6에서 체인 무결성을 검증할 때 "이전 블록 해시를 연결"했던 것과 같은 원리다 — 하나가 바뀌면 전체가 무너진다.

🤔 생각해보세요: 트랜잭션이 1,024개라면 머클 트리의 높이(레벨 수)는 몇인가?

2. 머클 루트 계산 — 밑바닥부터 구현

구조를 이해했으니, 이제 직접 코드로 만들어보자.

2-1. 가장 단순한 머클 루트

import hashlib

def hash_data(data: str) -> str:
    """SHA-256 해시 (레슨 1에서 만든 함수와 동일)"""
    return hashlib.sha256(data.encode()).hexdigest()

def hash_pair(left: str, right: str) -> str:
    """두 해시를 합쳐서 다시 해시"""
    return hash_data(left + right)

# 트랜잭션 4개
txs = ["Alice->Bob:1", "Bob->Carol:0.5", "Carol->Dave:0.3", "Dave->Eve:0.2"]

# 1단계: 잎 노드 — 각 트랜잭션 해시
leaves = [hash_data(tx) for tx in txs]
print("잎 노드 수:", len(leaves))
print("첫 번째 잎:", leaves[0][:16] + "...")

# 2단계: 쌍으로 묶어 올라가기
level_1 = [
    hash_pair(leaves[0], leaves[1]),
    hash_pair(leaves[2], leaves[3])
]
print("레벨 1 노드 수:", len(level_1))

# 3단계: 루트
root = hash_pair(level_1[0], level_1[1])
print("머클 루트:", root[:16] + "...")

# Output:
# 잎 노드 수: 4
# 첫 번째 잎: 73e68cb8de3f2e8f...
# 레벨 1 노드 수: 2
# 머클 루트: 6b34e2c180f82b54...

이 코드는 트랜잭션 4개를 잎 노드로 해시한 뒤, 쌍으로 묶어 올라가면서 최종 루트 하나를 만든다. 토너먼트 대진표를 아래에서 위로 채워나가는 과정 그대로다.

간단하다. 그런데 문제가 있다 — 트랜잭션이 홀수 개면 어떻게 하지?

2-2. 홀수 처리: 마지막 노드를 복제한다

비트코인의 실제 구현에서도 홀수면 마지막 해시를 복제해서 짝을 맞춘다. 솔직히 이 방식에 대해 할 말이 있는데 — 이더리움에서는 이 복제 방식이 second preimage attack 취약점을 만들 수 있어서 다른 접근을 취한다. 하지만 비트코인 학습이 목적이니 비트코인 방식으로 간다.

❌ → 🤔 → ✅ 홀수 트랜잭션 처리, 이렇게 진화한다

머클 루트 계산에서 초보자가 가장 많이 실수하는 부분이 홀수 처리다. 단계별로 어떻게 개선되는지 보자.

❌ WRONG WAY — 홀수 무시: 남는 노드를 그냥 버린다

def get_merkle_root_wrong(transactions):
    current_level = [hash_data(tx) for tx in transactions]
    while len(current_level) > 1:
        next_level = []
        # 홀수면 마지막 하나를 버림!
        for i in range(0, len(current_level) - 1, 2):
            next_level.append(hash_pair(current_level[i], current_level[i+1]))
        current_level = next_level
    return current_level[0]

# 문제: 트랜잭션 5개 중 마지막 Tx5가 루트에 반영되지 않는다!
txs = ["Tx1", "Tx2", "Tx3", "Tx4", "Tx5"]
root_wrong = get_merkle_root_wrong(txs)

# Tx5를 변조해도 루트가 동일 — 치명적 보안 구멍
txs_tampered = ["Tx1", "Tx2", "Tx3", "Tx4", "Tx5_FAKE"]
root_tampered = get_merkle_root_wrong(txs_tampered)
print(f"원본 루트: {root_wrong[:16]}...")
print(f"변조 루트: {root_tampered[:16]}...")
print(f"같은가?   {root_wrong == root_tampered}")  # True — 재앙!
# Output:
# 원본 루트: f1c8a2e9b7d34a01...
# 변조 루트: f1c8a2e9b7d34a01...
# 같은가?   True

마지막 트랜잭션이 루트에 반영되지 않으니, 공격자가 홀수 번째 트랜잭션을 마음대로 바꿔도 탐지되지 않는다.

🤔 BETTER — 단독 승격: 남는 노드를 그대로 다음 레벨로 올린다

def get_merkle_root_better(transactions):
    current_level = [hash_data(tx) for tx in transactions]
    while len(current_level) > 1:
        next_level = []
        for i in range(0, len(current_level), 2):
            if i + 1 < len(current_level):
                next_level.append(hash_pair(current_level[i], current_level[i+1]))
            else:
                # 남는 노드를 해싱 없이 그대로 올림
                next_level.append(current_level[i])
        current_level = next_level
    return current_level[0]

# 변조 탐지는 된다
txs = ["Tx1", "Tx2", "Tx3", "Tx4", "Tx5"]
root_better = get_merkle_root_better(txs)
txs_tampered = ["Tx1", "Tx2", "Tx3", "Tx4", "Tx5_FAKE"]
root_better_t = get_merkle_root_better(txs_tampered)
print(f"같은가? {root_better == root_better_t}")  # False — 변조 탐지 성공
# Output:
# 같은가? False

변조 탐지는 되지만 문제가 있다. 홀수 노드가 해싱 없이 승격되면, 트리의 모양이 비대칭이 된다. 증명 생성 시 "복제된 형제" 규칙을 적용할 수 없어 generate_proof()와 verify_proof()의 로직이 복잡해진다. 또한 비트코인 네트워크의 다른 노드와 머클 루트가 달라져 호환되지 않는다.

✅ BEST — 마지막 노드 복제: 비트코인의 실제 방식

def get_merkle_root_best(transactions):
    current_level = [hash_data(tx) for tx in transactions]
    while len(current_level) > 1:
        # 핵심: 홀수면 마지막 노드를 복제하여 짝수로 만든다
        if len(current_level) % 2 == 1:
            current_level.append(current_level[-1])
        next_level = []
        for i in range(0, len(current_level), 2):
            next_level.append(hash_pair(current_level[i], current_level[i+1]))
        current_level = next_level
    return current_level[0]

# 변조 탐지 + 대칭 트리 + 비트코인 호환
txs = ["Tx1", "Tx2", "Tx3", "Tx4", "Tx5"]
root_best = get_merkle_root_best(txs)
txs_tampered = ["Tx1", "Tx2", "Tx3", "Tx4", "Tx5_FAKE"]
root_best_t = get_merkle_root_best(txs_tampered)
print(f"같은가? {root_best == root_best_t}")  # False
# Output:
# 같은가? False

복제 방식은 세 가지 장점이 있다: (1) 모든 트랜잭션이 루트에 반영된다, (2) 트리가 항상 완전 이진 트리 형태라서 증명 로직이 단순하다, (3) 비트코인 네트워크와 동일한 루트를 생성한다. 이 아래 구현에서 이 방식을 그대로 사용한다.

아래 코드가 바로 이 ✅ BEST 방식을 적용한 완성형이다.

def get_merkle_root(transactions: list) -> str:
    """트랜잭션 리스트로부터 머클 루트를 계산한다."""
    if not transactions:
        return hash_data("")  # 빈 블록 처리

    # 잎 노드 생성
    current_level = [hash_data(tx) for tx in transactions]

    # 노드가 1개 남을 때까지 반복
    while len(current_level) > 1:
        next_level = []
        # 홀수면 마지막 노드를 복제
        if len(current_level) % 2 == 1:
            current_level.append(current_level[-1])

        # 쌍으로 묶어 해시
        for i in range(0, len(current_level), 2):
            next_level.append(hash_pair(current_level[i], current_level[i+1]))

        current_level = next_level

    return current_level[0]

# 홀수 개 테스트
txs_odd = ["Tx1", "Tx2", "Tx3"]  # 3개 — 홀수!
root = get_merkle_root(txs_odd)
print(f"트랜잭션 3개의 머클 루트: {root[:16]}...")
# Output:
# 트랜잭션 3개의 머클 루트: a92f4b7c3d1e8a06...

# 짝수 개
txs_even = ["Tx1", "Tx2", "Tx3", "Tx4"]
root2 = get_merkle_root(txs_even)
print(f"트랜잭션 4개의 머클 루트: {root2[:16]}...")
# Output:
# 트랜잭션 4개의 머클 루트: 9c1d5f8e2a7b4093...

# 트랜잭션 하나만 바꿔보자
txs_tampered = ["Tx1", "Tx2_TAMPERED", "Tx3", "Tx4"]
root3 = get_merkle_root(txs_tampered)
print(f"변조된 머클 루트:       {root3[:16]}...")
print(f"루트가 같은가? {root2 == root3}")  # False!
# Output:
# 변조된 머클 루트:       e7a2bc091f4d6358...
# 루트가 같은가? False

이 함수는 트랜잭션이 몇 개든 — 짝수든 홀수든 — 하나의 루트로 수렴시킨다. while 루프가 매 라운드마다 노드 수를 절반으로 줄이고, 홀수일 때는 마지막 노드를 복제해서 짝을 맞춘다.

트랜잭션 하나를 살짝 건드렸을 뿐인데 루트가 완전히 달라졌다. 레슨 1에서 배운 **눈사태 효과(avalanche effect)**가 트리 구조를 타고 증폭된 것이다.

🤔 생각해보세요: 레슨 5에서 구현한 작업 증명(PoW)에서는 넌스를 바꿔가며 해시를 반복 계산했다. 만약 채굴 중에 새 트랜잭션이 하나 추가되면, 머클 루트는 어떻게 되고, 채굴은 처음부터 다시 해야 할까?

3. 전체 트리 구축 — build_merkle_tree()

머클 루트만 계산하면 절반밖에 못 한 것이다. 중간 노드까지 전부 저장해야 나중에 머클 증명을 만들 수 있다.

def build_merkle_tree(transactions: list) -> list:
    """
    전체 머클 트리를 레벨별 리스트로 반환한다.
    tree[0] = 잎 노드, tree[-1] = [루트]
    """
    if not transactions:
        return [[hash_data("")]]

    tree = []

    # 잎 노드 레벨
    current_level = [hash_data(tx) for tx in transactions]
    tree.append(current_level[:])  # 복사해서 저장

    while len(current_level) > 1:
        # 홀수 처리
        if len(current_level) % 2 == 1:
            current_level.append(current_level[-1])

        next_level = []
        for i in range(0, len(current_level), 2):
            next_level.append(hash_pair(current_level[i], current_level[i+1]))

        tree.append(next_level[:])
        current_level = next_level

    return tree

# 테스트
txs = ["Tx1", "Tx2", "Tx3", "Tx4", "Tx5"]
tree = build_merkle_tree(txs)

print(f"트리 레벨 수: {len(tree)}")
for i, level in enumerate(tree):
    short = [h[:8] + "..." for h in level]
    print(f"  레벨 {i} ({len(level)}개 노드): {short}")

# Output:
# 트리 레벨 수: 4
#   레벨 0 (5개 노드): ['a4e624d2...', '2e7d2c03...', 'b2f5ff47...', 'c0a5d62e...', '1b645389...']
#   레벨 1 (3개 노드): ['f1c8a2e9...', '3d7b41a0...', '94e5c167...']
#   레벨 2 (2개 노드): ['7a29c3f1...', 'db5e2871...']
#   레벨 3 (1개 노드): ['e82f1a09...']

get_merkle_root()과 로직은 동일하되, 매 레벨의 결과를 tree 리스트에 차곡차곡 쌓아둔다는 차이가 있다. 이 저장된 중간 노드들이 다음 섹션에서 만들 머클 증명의 재료가 된다.

레벨 0에 5개가 있는데 레벨 1은 3개다 — 5가 홀수라서 마지막을 복제해 6개로 만든 뒤 쌍으로 묶어 3개가 된 것이다. 레벨 1도 3개(홀수)라서 같은 처리를 거쳐 레벨 2에서 2개가 된다.

빨간색 노드가 홀수 때문에 복제된 부분이다.

4. 머클 증명(Merkle Proof) — O(log n)의 마법

여기가 진짜 핵심이다. 내가 이더리움 DeFi 프로토콜의 에어드롭 시스템을 만들 때, 10만 개의 화이트리스트 주소를 온체인에 저장할 수 없었다. 가스비가 천문학적이니까. 머클 루트 하나만 컨트랙트에 저장하고, 각 유저가 자기 증명을 제출하는 방식으로 해결했다. 이게 바로 머클 증명이다.

증명의 원리

"TxB가 이 블록에 포함되어 있다"를 증명하려면, 전체 트리가 필요하지 않다. 루트까지 올라가는 경로에서 **형제 노드(sibling)**들만 있으면 된다.

TxB를 검증하려면:

1. H(TxB)를 내가 계산한다
2. 형제 H(TxA) 를 받는다 → H(TxA) + H(TxB) = H(AB) 계산
3. 형제 H(CD) 를 받는다 → H(AB) + H(CD) = 루트 계산
4. 이 루트가 블록 헤더의 머클 루트와 같으면 → 포함 증명 완료!

필요한 데이터: 형제 노드 2개. 트랜잭션이 1,024개여도 형제 노드는 10개면 된다 (log₂ 1024 = 10). 레슨 7에서 UTXO 풀 전체를 순회했던 것과 비교하면 차원이 다른 효율이다.

100만 개 중 하나를 20번의 해시 연산으로 검증한다. 이래서 머클 트리가 아름다운 거다.

구현: generate_proof()와 verify_proof()

def generate_proof(tree: list, tx_index: int) -> list:
    """
    특정 트랜잭션의 머클 증명을 생성한다.
    반환: [(형제해시, 방향)] 리스트 — 방향은 'left' 또는 'right'
    """
    proof = []
    index = tx_index

    for level in tree[:-1]:  # 루트 레벨은 제외
        # 홀수 처리: 패딩이 필요하면 적용
        working_level = level[:]
        if len(working_level) % 2 == 1:
            working_level.append(working_level[-1])

        # 형제 노드 찾기
        if index % 2 == 0:  # 내가 왼쪽이면 → 형제는 오른쪽
            sibling = working_level[index + 1]
            proof.append((sibling, 'right'))
        else:  # 내가 오른쪽이면 → 형제는 왼쪽
            sibling = working_level[index - 1]
            proof.append((sibling, 'left'))

        # 다음 레벨에서의 인덱스
        index = index // 2

    return proof


def verify_proof(tx_data: str, proof: list, expected_root: str) -> bool:
    """머클 증명을 검증한다."""
    current_hash = hash_data(tx_data)

    for sibling_hash, direction in proof:
        if direction == 'left':
            # 형제가 왼쪽 → 형제 + 나
            current_hash = hash_pair(sibling_hash, current_hash)
        else:
            # 형제가 오른쪽 → 나 + 형제
            current_hash = hash_pair(current_hash, sibling_hash)

    return current_hash == expected_root

# 테스트
txs = ["Tx1", "Tx2", "Tx3", "Tx4"]
tree = build_merkle_tree(txs)
root = tree[-1][0]

# Tx2 (인덱스 1)의 포함 증명 생성
proof = generate_proof(tree, 1)
print("증명 데이터:")
for sibling, direction in proof:
    print(f"  형제: {sibling[:16]}... 방향: {direction}")

# 검증
is_valid = verify_proof("Tx2", proof, root)
print(f"\nTx2 포함 검증: {is_valid}")  # True

# 거짓 트랜잭션 검증
is_fake = verify_proof("Tx2_FAKE", proof, root)
print(f"Tx2_FAKE 포함 검증: {is_fake}")  # False

# Output:
# 증명 데이터:
#   형제: a4e624d264de159e... 방향: left
#   형제: c01e7b2e17488aab... 방향: right
#
# Tx2 포함 검증: True
# Tx2_FAKE 포함 검증: False

generate_proof()는 트리를 아래에서 위로 올라가며 각 레벨의 형제 노드를 수집한다. verify_proof()는 그 형제 노드들을 순서대로 결합하면서 루트까지 재계산한다. 재계산한 루트가 블록 헤더의 머클 루트와 일치하면, 해당 트랜잭션이 블록에 포함되었다는 뜻이다.

증명에 필요한 데이터가 정확히 2개다 (트랜잭션 4개 → log₂4 = 2). 가짜 트랜잭션은 즉시 걸러진다.

🤔 생각해보세요: generate_proof()에서 direction을 왜 저장해야 할까? hash_pair(A, B)와 hash_pair(B, A)의 결과가 같을까?

5. SPV 클라이언트 — 풀 노드 없이 검증하기

머클 증명이 가장 빛나는 순간이 바로 여기다. 내가 처음 비트코인을 공부할 때 가장 인상 깊었던 부분이 SPV(Simplified Payment Verification)다. 사토시 나카모토가 비트코인 백서 Section 8에서 직접 설명한 개념이기도 하다.

풀 노드: 모든 블록의 모든 트랜잭션을 저장한다 (2026년 기준 약 600GB 이상).

SPV 클라이언트: 블록 헤더만 저장한다. 헤더 하나가 80바이트니까, 수십만 개 블록의 헤더를 다 합쳐도 수십 MB에 불과하다.

이것이 비트코인 모바일 지갑의 원리다. 폰에 600GB를 저장할 수 없으니, 블록 헤더만 동기화하고 머클 증명으로 거래를 검증한다. 레슨 4에서 "블록 헤더는 블록의 신분증"이라고 했는데, 신분증(헤더)만 있으면 그 안의 내용(트랜잭션)을 증명할 수 있는 셈이다.

6. Block 클래스에 머클 루트 통합

이론과 함수가 갖춰졌으니, 이제 우리 블록체인에 머클 트리를 붙일 차례다. 레슨 4에서 설계한 블록 헤더에 merkle_root 필드를 추가한다.

import hashlib
import time

def hash_data(data: str) -> str:
    return hashlib.sha256(data.encode()).hexdigest()

def hash_pair(left: str, right: str) -> str:
    return hash_data(left + right)

def get_merkle_root(transactions: list) -> str:
    """트랜잭션 리스트 → 머클 루트"""
    if not transactions:
        return hash_data("")
    current_level = [hash_data(str(tx)) for tx in transactions]
    while len(current_level) > 1:
        if len(current_level) % 2 == 1:
            current_level.append(current_level[-1])
        next_level = []
        for i in range(0, len(current_level), 2):
            next_level.append(hash_pair(current_level[i], current_level[i+1]))
        current_level = next_level
    return current_level[0]


class Block:
    def __init__(self, index, transactions, previous_hash, difficulty=4):
        self.index = index
        self.timestamp = time.time()
        self.transactions = transactions
        self.previous_hash = previous_hash
        self.difficulty = difficulty
        # ⬇️ 새로 추가: 머클 루트!
        self.merkle_root = get_merkle_root(
            [str(tx) for tx in transactions]
        )
        self.nonce = 0
        self.hash = self.mine_block()

    def calculate_hash(self):
        # 머클 루트를 블록 해시 계산에 포함
        block_string = (
            f"{self.index}{self.timestamp}{self.merkle_root}"
            f"{self.previous_hash}{self.nonce}"
        )
        return hash_data(block_string)

    def mine_block(self):
        target = "0" * self.difficulty
        while True:
            h = self.calculate_hash()
            if h[:self.difficulty] == target:
                return h
            self.nonce += 1

# 테스트 — 난이도 2로 빠르게
block = Block(
    index=1,
    transactions=["Alice->Bob:1BTC", "Bob->Carol:0.5BTC", "Coinbase->Alice:6.25BTC"],
    previous_hash="0" * 64,
    difficulty=2
)

print(f"블록 #{block.index}")
print(f"  트랜잭션 수: {len(block.transactions)}")
print(f"  머클 루트:   {block.merkle_root[:24]}...")
print(f"  블록 해시:   {block.hash[:24]}...")
print(f"  넌스:        {block.nonce}")

# Output:
# 블록 #1
#   트랜잭션 수: 3
#   머클 루트:   8f4a2c1e9b7d3f05a628e4...
#   블록 해시:   00a7c3f1d829e5b461...
#   넌스:        142

주목할 점: calculate_hash()에서 이제 개별 트랜잭션을 직접 나열하지 않는다. 머클 루트 하나로 모든 트랜잭션을 대표한다. 실제 비트코인도 이 방식이다.

❌ 이렇게 하면 안 된다:

# 트랜잭션을 전부 블록 해시에 포함 — 비효율적
block_string = f"{self.index}{self.transactions}{self.previous_hash}{self.nonce}"

트랜잭션이 2,000개면 해시 입력 문자열이 거대해지고, 넌스를 수백만 번 돌릴 때마다 이 거대한 문자열을 해싱해야 한다.

✅ 머클 루트를 쓰면:

# 머클 루트(64자 고정)만 포함 — 트랜잭션 수와 무관하게 일정
block_string = f"{self.index}{self.merkle_root}{self.previous_hash}{self.nonce}"

머클 루트는 항상 64자(SHA-256)이므로 트랜잭션이 1개든 10만 개든 해시 입력 크기가 동일하다.

7. 실전 감각: 무결성 검증 시나리오

개별 함수를 만들고 블록에 통합도 했다. 이제 실제 공격 시나리오로 전체를 연결해보자.

# 시나리오: 악의적 채굴자가 트랜잭션을 몰래 바꾸려 한다

import hashlib, time

def hash_data(data):
    return hashlib.sha256(data.encode()).hexdigest()

def hash_pair(left, right):
    return hash_data(left + right)

def build_merkle_tree(transactions):
    if not transactions:
        return [[hash_data("")]]
    tree = []
    current_level = [hash_data(tx) for tx in transactions]
    tree.append(current_level[:])
    while len(current_level) > 1:
        if len(current_level) % 2 == 1:
            current_level.append(current_level[-1])
        next_level = []
        for i in range(0, len(current_level), 2):
            next_level.append(hash_pair(current_level[i], current_level[i+1]))
        tree.append(next_level[:])
        current_level = next_level
    return tree

def generate_proof(tree, tx_index):
    proof = []
    index = tx_index
    for level in tree[:-1]:
        working_level = level[:]
        if len(working_level) % 2 == 1:
            working_level.append(working_level[-1])
        if index % 2 == 0:
            sibling = working_level[index + 1]
            proof.append((sibling, 'right'))
        else:
            sibling = working_level[index - 1]
            proof.append((sibling, 'left'))
        index = index // 2
    return proof

def verify_proof(tx_data, proof, expected_root):
    current_hash = hash_data(tx_data)
    for sibling_hash, direction in proof:
        if direction == 'left':
            current_hash = hash_pair(sibling_hash, current_hash)
        else:
            current_hash = hash_pair(current_hash, sibling_hash)
    return current_hash == expected_root


# 원본 트랜잭션
original_txs = [
    "Alice->Bob:1BTC",
    "Bob->Carol:0.5BTC",
    "Carol->Dave:0.3BTC",
    "Dave->Eve:0.2BTC"
]

# 트리 구축 & 머클 루트 저장
tree = build_merkle_tree(original_txs)
saved_root = tree[-1][0]
print(f"[블록 헤더에 저장된 머클 루트]: {saved_root[:24]}...")

# Alice의 Tx에 대한 증명 생성 (인덱스 0)
proof = generate_proof(tree, 0)
print(f"\n[Alice 검증] 정상 트랜잭션:")
result = verify_proof("Alice->Bob:1BTC", proof, saved_root)
print(f"  결과: {'✅ 포함 확인' if result else '❌ 포함 안 됨'}")

# 공격자가 금액을 변조한 경우
print(f"\n[공격자 시도] 변조된 트랜잭션:")
fake_result = verify_proof("Alice->Bob:100BTC", proof, saved_root)
print(f"  결과: {'✅ 포함 확인' if fake_result else '❌ 위조 탐지!'}")

# 공격자가 트리 자체를 변조하면?
tampered_txs = [
    "Alice->Bob:100BTC",  # 변조!
    "Bob->Carol:0.5BTC",
    "Carol->Dave:0.3BTC",
    "Dave->Eve:0.2BTC"
]
tampered_tree = build_merkle_tree(tampered_txs)
tampered_root = tampered_tree[-1][0]
print(f"\n[변조된 트리의 루트]: {tampered_root[:24]}...")
print(f"[저장된 루트와 같은가?]: {saved_root == tampered_root}")

# Output:
# [블록 헤더에 저장된 머클 루트]: 6b34e2c180f82b5418c7d8...
#
# [Alice 검증] 정상 트랜잭션:
#   결과: ✅ 포함 확인
#
# [공격자 시도] 변조된 트랜잭션:
#   결과: ❌ 위조 탐지!
#
# [변조된 트리의 루트]: a91c4f7e38b20d6923f158...
# [저장된 루트와 같은가?]: False

공격자에게 남은 선택지는 두 가지다. 트랜잭션을 바꾸거나, 트리 전체를 재구성하거나. 두 경우 모두 블록 헤더에 저장된 루트와 일치하지 않는다. 그렇다면 블록 헤더를 바꾸면 되지 않을까? 레슨 5에서 배운 대로 PoW를 다시 해야 하고, 레슨 6에서 배운 대로 그 뒤의 모든 블록도 다시 채굴해야 한다. 머클 트리, 작업 증명, 체인 연결 — 이 세 겹의 방어가 블록체인의 보안이다.

📝 셀프 리뷰 체크리스트

흔한 실수 Top 3:

1. hash_pair 순서 실수: hash_pair(left, right) ≠ hash_pair(right, left) — 증명의 direction을 무시하면 검증이 깨진다
2. 홀수 처리 누락: 트랜잭션 3개, 5개, 7개 등으로 반드시 테스트할 것
3. 빈 트랜잭션 미처리: 트랜잭션이 0개인 블록도 머클 루트를 가져야 한다

🚀 Next Level — 시니어는 이렇게 한다

내가 솔리디티로 머클 증명 검증을 구현할 때 배운 것들:

1. 정렬된 해시 쌍(Sorted Hash Pair) 위에서 direction을 저장했는데, OpenZeppelin의 MerkleProof 라이브러리는 다른 접근을 취한다. 두 해시를 항상 정렬한 뒤 결합한다:

def hash_pair_sorted(a: str, b: str) -> str:
    """항상 작은 값을 왼쪽에 — 방향 저장이 필요 없다"""
    if a < b:
        return hash_pair(a, b)
    return hash_pair(b, a)

이렇게 하면 증명에 방향 정보가 필요 없어 데이터가 줄어든다. 온체인에서는 가스 절약이 중요하기 때문에 이 방식을 선호한다.

2. 이중 해싱 비트코인은 실제로 SHA-256을 두 번 적용한다: SHA256(SHA256(data)). Length extension attack을 방어하기 위해서다. 우리 교육용 코드에서는 한 번으로 충분하지만, 프로덕션에서는 반드시 이중 해싱을 쓴다.

🔨 프로젝트 업데이트

지금까지 만든 PyChain 프로젝트에 머클 트리를 통합한 전체 코드다. 이전 레슨의 UTXO 모델, PoW, 체인 구조 위에 머클 트리가 올라간다.

"""
PyChain — 레슨 8까지 누적 프로젝트
머클 트리 통합 버전
"""
import hashlib
import time

# ========== 해시 유틸리티 ==========
def hash_data(data: str) -> str:
    """SHA-256 해시 (레슨 1)"""
    return hashlib.sha256(data.encode()).hexdigest()

def hash_pair(left: str, right: str) -> str:
    """두 해시를 합쳐서 해시 (레슨 8)"""
    return hash_data(left + right)

# ========== 머클 트리 (레슨 8 — 신규) ==========
def build_merkle_tree(transactions: list) -> list:
    """전체 머클 트리를 레벨별 리스트로 구축"""
    if not transactions:
        return [[hash_data("")]]
    tree = []
    current_level = [hash_data(str(tx)) for tx in transactions]
    tree.append(current_level[:])
    while len(current_level) > 1:
        if len(current_level) % 2 == 1:
            current_level.append(current_level[-1])
        next_level = []
        for i in range(0, len(current_level), 2):
            next_level.append(hash_pair(current_level[i], current_level[i+1]))
        tree.append(next_level[:])
        current_level = next_level
    return tree

def get_merkle_root(transactions: list) -> str:
    """트랜잭션 리스트의 머클 루트 반환"""
    tree = build_merkle_tree(transactions)
    return tree[-1][0]

def generate_proof(tree: list, tx_index: int) -> list:
    """특정 트랜잭션의 머클 증명 생성"""
    proof = []
    index = tx_index
    for level in tree[:-1]:
        working_level = level[:]
        if len(working_level) % 2 == 1:
            working_level.append(working_level[-1])
        if index % 2 == 0:
            sibling = working_level[index + 1]
            proof.append((sibling, 'right'))
        else:
            sibling = working_level[index - 1]
            proof.append((sibling, 'left'))
        index = index // 2
    return proof

def verify_proof(tx_data: str, proof: list, expected_root: str) -> bool:
    """머클 증명 검증"""
    current_hash = hash_data(tx_data)
    for sibling_hash, direction in proof:
        if direction == 'left':
            current_hash = hash_pair(sibling_hash, current_hash)
        else:
            current_hash = hash_pair(current_hash, sibling_hash)
    return current_hash == expected_root

# ========== UTXO 모델 (레슨 7) ==========
class TxOutput:
    def __init__(self, recipient: str, amount: float):
        self.recipient = recipient
        self.amount = amount
    def __repr__(self):
        return f"{self.recipient}:{self.amount}"

class TxInput:
    def __init__(self, tx_id: str, output_index: int):
        self.tx_id = tx_id
        self.output_index = output_index
    def __repr__(self):
        return f"{self.tx_id[:8]}...[{self.output_index}]"

class Transaction:
    def __init__(self, inputs: list, outputs: list, is_coinbase=False):
        self.inputs = inputs
        self.outputs = outputs
        self.is_coinbase = is_coinbase
        self.tx_id = self.calculate_id()
    def calculate_id(self):
        data = str([(inp.tx_id, inp.output_index) for inp in self.inputs])
        data += str([(out.recipient, out.amount) for out in self.outputs])
        return hash_data(data)
    def __repr__(self):
        return f"Tx({self.tx_id[:8]}...)"

# ========== 블록 (레슨 4 + 레슨 8 통합) ==========
class Block:
    def __init__(self, index, transactions, previous_hash, difficulty=4):
        self.index = index
        self.timestamp = time.time()
        self.transactions = transactions
        self.previous_hash = previous_hash
        self.difficulty = difficulty
        # 머클 루트 계산 (레슨 8 통합)
        self.merkle_root = get_merkle_root(
            [str(tx) for tx in transactions]
        )
        self.nonce = 0
        self.hash = self.mine_block()

    def calculate_hash(self):
        block_string = (
            f"{self.index}{self.timestamp}{self.merkle_root}"
            f"{self.previous_hash}{self.nonce}"
        )
        return hash_data(block_string)

    def mine_block(self):
        target = "0" * self.difficulty
        while True:
            h = self.calculate_hash()
            if h[:self.difficulty] == target:
                return h
            self.nonce += 1

# ========== 블록체인 (레슨 6 + 7) ==========
class Blockchain:
    def __init__(self, difficulty=2):
        self.difficulty = difficulty
        self.chain = []
        self.utxo_pool = {}
        self.pending_transactions = []
        self._create_genesis_block()

    def _create_genesis_block(self):
        coinbase = Transaction(
            inputs=[TxInput("0" * 64, 0)],
            outputs=[TxOutput("genesis", 50.0)],
            is_coinbase=True
        )
        self.utxo_pool[(coinbase.tx_id, 0)] = coinbase.outputs[0]
        genesis = Block(0, [coinbase], "0" * 64, self.difficulty)
        self.chain.append(genesis)

    def add_transaction(self, tx: Transaction):
        if tx.is_coinbase or self.validate_transaction(tx):
            self.pending_transactions.append(tx)
            return True
        return False

    def validate_transaction(self, tx: Transaction) -> bool:
        input_sum = 0
        for inp in tx.inputs:
            key = (inp.tx_id, inp.output_index)
            if key not in self.utxo_pool:
                return False
            input_sum += self.utxo_pool[key].amount
        output_sum = sum(out.amount for out in tx.outputs)
        return input_sum >= output_sum

    def mine_pending(self, miner_address: str):
        coinbase = Transaction(
            inputs=[TxInput("0" * 64, 0)],
            outputs=[TxOutput(miner_address, 6.25)],
            is_coinbase=True
        )
        txs = [coinbase] + self.pending_transactions

        # UTXO 풀 업데이트
        for tx in txs:
            if not tx.is_coinbase:
                for inp in tx.inputs:
                    del self.utxo_pool[(inp.tx_id, inp.output_index)]
            for i, out in enumerate(tx.outputs):
                self.utxo_pool[(tx.tx_id, i)] = out

        block = Block(
            len(self.chain), txs,
            self.chain[-1].hash, self.difficulty
        )
        self.chain.append(block)
        self.pending_transactions = []
        return block

    def get_balance(self, address: str) -> float:
        return sum(
            utxo.amount for utxo in self.utxo_pool.values()
            if utxo.recipient == address
        )

    def verify_chain(self) -> bool:
        for i in range(1, len(self.chain)):
            block = self.chain[i]
            prev = self.chain[i - 1]
            if block.previous_hash != prev.hash:
                return False
            # 머클 루트 재검증 (레슨 8 추가)
            recalculated_root = get_merkle_root(
                [str(tx) for tx in block.transactions]
            )
            if block.merkle_root != recalculated_root:
                return False
        return True


# ========== 실행 테스트 ==========
if __name__ == "__main__":
    print("=" * 50)
    print("PyChain v0.8 — 머클 트리 통합")
    print("=" * 50)

    bc = Blockchain(difficulty=2)
    print(f"\n제네시스 블록 생성 완료")
    print(f"  genesis 잔고: {bc.get_balance('genesis')} BTC")

    # Alice에게 채굴 보상
    block1 = bc.mine_pending("Alice")
    print(f"\n블록 #{block1.index} 채굴")
    print(f"  머클 루트: {block1.merkle_root[:24]}...")
    print(f"  블록 해시: {block1.hash[:24]}...")
    print(f"  Alice 잔고: {bc.get_balance('Alice')} BTC")

    # Alice → Bob 전송
    alice_utxo = None
    for key, utxo in bc.utxo_pool.items():
        if utxo.recipient == "Alice":
            alice_utxo = key
            break

    if alice_utxo:
        tx = Transaction(
            inputs=[TxInput(alice_utxo[0], alice_utxo[1])],
            outputs=[
                TxOutput("Bob", 2.0),
                TxOutput("Alice", 4.25)  # 잔돈
            ]
        )
        bc.add_transaction(tx)
        block2 = bc.mine_pending("Alice")
        print(f"\n블록 #{block2.index} 채굴 (Alice→Bob 2BTC)")
        print(f"  트랜잭션 수: {len(block2.transactions)}")
        print(f"  머클 루트: {block2.merkle_root[:24]}...")

    # 머클 증명 테스트
    print(f"\n--- 머클 증명 테스트 ---")
    tx_strings = [str(tx) for tx in block2.transactions]
    tree = build_merkle_tree(tx_strings)
    proof = generate_proof(tree, 1)  # 두 번째 트랜잭션
    is_valid = verify_proof(tx_strings[1], proof, block2.merkle_root)
    print(f"  Tx 포함 증명: {'✅ 성공' if is_valid else '❌ 실패'}")
    print(f"  증명 크기: 형제 해시 {len(proof)}개")

    # 체인 무결성
    print(f"\n--- 체인 검증 ---")
    print(f"  체인 길이: {len(bc.chain)} 블록")
    print(f"  무결성: {'✅ 유효' if bc.verify_chain() else '❌ 손상'}")

    # 잔고 확인
    print(f"\n--- 최종 잔고 ---")
    print(f"  Alice: {bc.get_balance('Alice')} BTC")
    print(f"  Bob:   {bc.get_balance('Bob')} BTC")

예상 출력:

==================================================
PyChain v0.8 — 머클 트리 통합
==================================================

제네시스 블록 생성 완료
  genesis 잔고: 50.0 BTC

블록 #1 채굴
  머클 루트: 8a3c2f1e7b4d9058a6...
  블록 해시: 00b7c3f1d829e5b461...
  Alice 잔고: 6.25 BTC

블록 #2 채굴 (Alice→Bob 2BTC)
  트랜잭션 수: 2
  머클 루트: f2a9c7e3b814d605...
  
--- 머클 증명 테스트 ---
  Tx 포함 증명: ✅ 성공
  증명 크기: 형제 해시 1개

--- 체인 검증 ---
  체인 길이: 3 블록
  무결성: ✅ 유효

--- 최종 잔고 ---
  Alice: 10.5 BTC
  Bob:   2.0 BTC

직접 실행해보자 — 머클 루트가 블록 헤더에 포함되어 채굴되고, 체인 검증 시 머클 루트까지 재검증되는 흐름을 확인할 수 있다.

한눈에 보는 머클 트리

다음 레슨 예고: 레슨 9에서는 이 모든 보안 장치를 깨트리려는 시도들 — 51% 공격, 이기적 채굴, 시빌 공격 — 의 메커니즘을 분석하고 시뮬레이션한다. 우리가 만든 PyChain이 얼마나 안전한지 직접 공격해볼 것이다.

난이도 포크

# 트랜잭션 수를 1, 2, 3, 5, 8개로 바꿔가며 트리 모양 관찰
for n in [1, 2, 3, 5, 8]:
    txs = [f"Tx{i}" for i in range(n)]
    tree = build_merkle_tree(txs)
    print(f"Tx {n}개 → 트리 높이: {len(tree)}, 루트: {tree[-1][0][:12]}...")