개요

머클트리는 블록체인에서 거래 집합을 안전하고 효율적으로 요약·검증하기 위해 쓰이는 핵심 자료구조임 블록 헤더에 머클루트가 포함되는 이유는 블록 안의 모든 거래를 고정 크기 해시 하나로 대표해 무결성 확인과 경량 검증을 가능하게 하기 때문임 이 글은 머클트리의 구조와 동작 원리, 블록체인에서의 실무적 의미와 구현 주의사항까지 초보자도 이해할 수 있도록 상세히 설명함

핵심 개념과 구조

  • 머클트리는 보통 이진 트리 형태로 구현함
  • 거래들을 리프(leaf) 로 두고 인접 두 리프의 해시를 이어 붙여 부모 해시를 만들며 이 과정을 반복해 루트 해시를 얻음
  • 해시 함수는 체인별로 다르며 비트코인은 더블 SHA‑256, 이더리움은 트라이 구조에서 Keccak‑256 을 사용함
  • 최상단 해시를 머클루트(Merkle root) 라 부르며 크기는 해시 함수에 따라 고정됨
  • 리프 수가 홀수일 때는 마지막 리프를 복제해 짝을 맞추는 방식이 일반적이며 비트코인은 이 규칙을 사용함
  • 트리 깊이는 리프 수 N에 대해 ⌈log₂ N⌉ 에 비례하므로 대량의 거래를 효율적으로 요약할 수 있음

동작 원리와 장점

  • 인접 노드 해시 H_left || H_right 를 순서대로 연결해 해시를 계산하고 이를 위로 올려가며 루트 해시를 얻음
  • 무결성 검증 단일 거래가 바뀌면 해당 리프에서 루트까지의 모든 경로 해시가 바뀌어 변조를 즉시 탐지할 수 있음
  • 효율적 포함 증명 특정 거래가 블록에 포함되었음을 증명하려면 그 거래와 경로상의 형제 해시들만 있으면 됨 필요한 해시 개수는 O(log N) 으로 작아 대역폭과 검증 비용이 작음
  • 확장성 보조 리프가 1,000,000개여도 증명에 필요한 형제 해시는 약 20개 수준으로 32바이트 해시 기준 약 640바이트에 불과함

블록 헤더와 경량 노드(SPV)

  • 비트코인 블록 헤더는 이전 블록 해시, 머클루트, 난스 등 합의 관련 메타데이터를 포함함
  • 경량 노드(SPV)는 블록 전체가 아니라 헤더 체인만 받아 신뢰성을 확보하고, 개별 거래에 대해서는 풀노드로부터 머클 증명 을 받아 포함 여부를 검증함
  • 이 방식은 모바일·임베디드 환경에서도 실사용이 가능하게 하는 기반이 됨
  • 이더리움은 전통적인 이진 머클트리 대신 머클‑패트리샤 트라이(MPT) 를 사용해 거래·영수증·상태 루트를 헤더에 담아 유사한 목적을 달성함

구현 세부와 체인별 차이

  • 비트코인

    • 리프는 거래 직렬화의 더블 SHA‑256 해시이며 내부 노드도 자식 두 해시를 더블 SHA‑256 으로 결합함
    • 리프가 홀수면 마지막 해시를 복제 해 상위로 올림
    • 과거 중복 거래로 동일 루트가 나올 수 있는 변형(mutated) 리스크 가 보고되어 소프트웨어에서 감지 플래그로 방지함
    • 엔디언 처리와 직렬화 규약을 엄격히 맞추지 않으면 루트가 달라짐

  • 이더리움

    • 거래·영수증·상태는 MPT 로 관리되며 노드 해시는 Keccak‑256 임
    • 구조와 증명 포맷이 이진 머클트리와 다르므로 구현 시 완전히 별도의 로직이 필요함

머클 증명과 검증 절차

  • 입력 요소

    • 대상 거래의 해시 또는 리프 값
    • 루트까지 올라가는 경로의 형제 해시 리스트
    • 각 단계에서 왼쪽·오른쪽 위치를 나타내는 인덱스 또는 방향 정보

  • 검증 절차

    • 리프에서 시작해 단계별로 형제 해시와 정확한 순서 로 결합하며 상위 해시를 계산
    • 최종 계산값이 블록 헤더의 머클루트와 일치하면 포함이 성립

아래는 개념 확인용 파이썬 예시이며 비트코인의 더블 SHA‑256 결합을 가정함

import hashlib

def sha256d(b):
    return hashlib.sha256(hashlib.sha256(b).digest()).digest()

def verify_merkle_proof(leaf, proof, root, index, double_hash=True):
    h = sha256d(leaf) if double_hash else leaf
    for sibling in proof:
        if index & 1 == 0:      # left child
            h = sha256d(h + sibling)
        else:                    # right child
            h = sha256d(sibling + h)
        index >>= 1
    return h == root

코드는 교육 목적의 단순화된 형태이며 실제 네트워크 구현은 직렬화 규약과 엔디언 변환, 오류 처리, 멀티프루프 등 추가 고려가 필요함

실무적 고려사항

  • 직렬화 규약 일치 체인별 바이트 순서와 직렬화 포맷을 정확히 맞추지 않으면 루트가 달라짐
  • 해시 결합 순서 고정 반드시 왼쪽 먼저, 오른쪽 다음 순서를 유지해야 하며 반대로 결합하면 다른 루트가 나옴
  • 홀수 리프 처리 방식 확인 복제 여부와 예외 처리 규칙이 구현마다 다를 수 있으니 사전 합의 필요
  • 머클 증명의 한계 포함 여부만 증명하며 거래의 유효성 자체는 별도 검증이 필요함 비포함 증명이나 동적 집합 갱신에는 스파스 머클트리 또는 벡터 커밋먼트 같은 다른 구조가 더 적합함
  • 멀티프루프와 배치 검증 여러 거래를 한꺼번에 검증할 때 공유 경로를 묶는 멀티프루프 를 사용하면 전송량과 검증 비용을 줄일 수 있음
  • 보안과 신뢰 경계 SPV는 포함 증명과 헤더 체인을 신뢰하지만 전체 상태 전이의 완전 검증은 풀노드가 담당함 운영 환경에서는 풀노드 다변화와 네트워크 지연 모니터링, 헤더 유효성 검사 정책을 병행해야 함

실전 적용 시나리오

  • 모바일 지갑 헤더 동기화와 머클 증명으로 경량 송금 확인을 제공해 UX와 데이터 요건을 동시에 충족함
  • 인덱싱 서비스 특정 주소나 토큰 이벤트를 색인할 때 머클 증명으로 정확한 포함 을 첨부해 무결성을 보장함
  • 브리지·크로스체인 메시지 원체인의 포함 증명을 타 체인에서 검증해 메타데이터 신뢰를 높임
  • 감사·포렌식 오프체인 데이터 스냅샷에 머클 루트를 부여해 변조 불가 로그 로 관리하고 분쟁 시 증명으로 활용함

정리

머클트리는 트리 기반 해싱 으로 대량의 거래를 고정 크기 해시 하나로 요약하고 O(log N) 크기의 증명만으로 포함을 검증하게 해주는 구조임 비트코인처럼 단순 이진 머클트리와 이더리움의 MPT는 구현과 증명 포맷이 다르므로 목적에 맞는 구조를 선택해야 함 현업에서는 직렬화 규약과 결합 순서, 홀수 리프 처리, 증명 포맷 합의, SPV의 신뢰 경계를 명확히 하고 멀티프루프·스파스 구조 등 확장 기법을 상황에 맞게 채택하는 것이 중요함

참고자료