수많은 데이터를 하나로 묶는, 머클 트리

한 블록에는 수천 건의 거래가 담길 수 있습니다. 누군가 "내 거래가 정말 이 블록에 들어 있나요?"라고 물을 때마다 블록 전체를 내려받아 뒤지는 것은 너무 무겁습니다. 이 문제를 우아하게 푸는 자료구조가 머클 트리(Merkle Tree)입니다.

해시를 둘씩 묶어 올라가기

앞에서 해시는 어떤 데이터든 고유한 '지문'으로 바꾸는 함수라고 했습니다. 아래에서 해시에 대해 다시 한 번 짚고 넘어가겠습니다.

해시 체험하기

🔬 직접 해보기: 글자를 한 개만 바꿔보세요. 해시가 어떻게 변하나요?

SHA-256 해시 (지문)

계산 중…

한 글자만 바꿔도 결과가 통째로 달라집니다. 그래서 데이터에 손을 대면 곧바로 티가 나죠. 이 “지문” 덕분에 블록체인은 위변조를 바로 잡아냅니다.

머클 트리는 이 해시를 계단처럼 쌓아 올립니다.

먼저 각 거래를 해시해 잎(leaf) 지문을 만듭니다.
잎들을 둘씩 짝지어 이어 붙인 뒤 다시 해시해 한 칸 위의 지문을 만듭니다.
이 과정을 반복하면 가지가 점점 줄어들어, 마침내 단 하나의 지문만 남습니다. 이것이 머클 루트(Merkle Root)입니다.

            Merkle Root  ← 블록 전체 거래를 요약한 하나의 지문
           /          \
      H(AB)            H(CD)
      /    \           /    \
   H(A)   H(B)      H(C)   H(D)   ← 각 거래의 해시(잎)
    |      |          |      |
   거래A  거래B      거래C  거래D

머클 루트는 그 블록에 담긴 모든 거래를 한 개의 값으로 요약합니다.

블록 헤더에는 루트만 담는다

블록은 크게 헤더(머리말)와 본문(거래 목록)으로 나뉩니다. 영리하게도 블록 헤더에는 거래 전체가 아니라 머클 루트만 들어갑니다.

헤더는 작고(보통 수십 바이트의 머클 루트 + 앞 블록 해시 + 시각 등), 본문(거래 목록)은 큽니다. 가벼운 기기는 헤더만 따라가면서도, 필요할 때 특정 거래의 포함 여부를 검증할 수 있습니다.

머클 증명: 전체 없이도 포함을 증명한다

핵심은 여기 있습니다. "거래 C가 이 블록에 들어 있다"를 증명하는 데 다른 거래 전부는 필요 없습니다. 트리에서 루트까지 올라가는 길목의 형제 지문 몇 개만 있으면 됩니다. 이것을 머클 증명(Merkle Proof)이라 합니다.

위 그림에서 거래 C의 포함을 증명하려면:

검증자는 거래C를 해시해 H(C)를 직접 구합니다.
형제인 H(D)를 받아 H(C)와 이어 해시 → H(CD).
그 형제인 H(AB)를 받아 이어 해시 → 루트 후보.
이 루트 후보가 블록 헤더의 머클 루트와 같으면 거래 C는 확실히 포함된 것입니다.

거래가 100만 건이어도 필요한 형제 지문은 약 20개(log 규모)뿐입니다. 전체를 내려받지 않고도 검증이 되는 이유가 여기 있습니다. 가벼운 지갑(라이트 클라이언트)이 이 방식을 사용합니다.

위변조하면 루트가 바뀐다

머클 트리는 무결성도 지켜 줍니다. 거래 하나라도 몰래 고치면 그 잎의 해시가 바뀌고, 위로 올라가며 부모 지문이 줄줄이 바뀌어 결국 머클 루트가 달라집니다. 앞 수업에서 본 블록 사슬 붕괴와 같은 원리입니다.

헤더의 머클 루트는 블록끼리 해시로 연결된 사슬에 묶여 있습니다. 따라서 거래 하나를 고치려면 루트가 바뀌고, 그러면 그 블록의 해시가 바뀌어 뒤따르는 모든 블록을 다시 계산해야 합니다. 전 세계 복제본까지 함께 바꿔야 하니 사실상 불가능합니다.

머클 트리는 많은 데이터를 하나의 지문(루트)으로 요약해 두고, 전체를 보지 않고도 특정 항목의 포함과 무결성을 짧은 증명만으로 확인하게 해 주는 구조입니다.

공개키 서명이 '누가 보냈는가'를 증명한다면, 머클 트리는 '무엇이 어디에 담겼는가'를 효율적으로 증명합니다. 이 두 암호 도구가 합쳐져, 중앙 관리자 없이도 믿을 수 있는 장부가 완성됩니다.