# 머클 트리 (Merkle Tree)

**머클 트리**(Merkle tree, 해시 트리)는 모든 리프 노드에는 데이터 블록의 해시가, 리프가 아닌 모든 노드에는 자식 노드 해시들을 이어 붙여 다시 해시한 값이 붙는 트리 구조입니다. 어떤 변경이든 위로 전파되므로 최상단의 해시(머클 루트)만 확인하면 전체 데이터의 무결성을 검증할 수 있고, 덕분에 블록체인의 내용을 효율적이고 안전하게 검증할 수 있습니다. 1979년 랠프 머클(Ralph Merkle)이 제안했습니다.

## 트리 구축

1. 각 데이터 블록(예: 블록 안의 트랜잭션)의 해시를 계산해 리프로 둡니다.
2. 이웃한 두 해시를 이어 붙여 다시 해시해 부모 노드를 만듭니다. 비트코인은 이때 SHA-256을 두 번 적용하며, 한 층의 노드 수가 홀수이면 마지막 해시를 복제해 짝을 맞춥니다.
3. 이 과정을 반복해 해시가 하나 남으면 그것이 머클 루트입니다.

## 머클 증명

특정 데이터가 트리에 포함되어 있음을 보이려면 전체 데이터를 보낼 필요 없이, 그 리프에서 루트까지 올라가는 경로의 형제 해시들만 제시하면 됩니다. 리프가 n개인 이진 트리에서 이 머클 증명의 길이는 약 log2 n개의 해시입니다. 예를 들어 트랜잭션이 4,000개인 블록에서도 포함 여부는 해시 12개 정도로 검증할 수 있습니다. 데이터가 아주 조금만 바뀌어도 경로의 해시와 루트가 달라지므로 변조를 쉽게 감지할 수 있습니다.

## 장점과 한계

- **효율적인 검증:** 대규모 데이터에서도 일부 데이터의 포함 여부와 무결성을 로그 크기의 정보로 확인할 수 있습니다.
- **공간 효율성:** 검증자는 전체 데이터 세트 대신 루트 해시만 보관해도 됩니다.
- **구현 부담:** 크고 자주 바뀌는 데이터 세트에서는 트리를 갱신하고 유지하는 작업이 복잡할 수 있습니다.

## 응용 분야

- **블록체인:** 비트코인 등 많은 블록체인은 블록 안의 트랜잭션을 머클 트리로 요약해 블록 헤더에 머클 루트를 기록합니다. 전체 블록을 내려받지 않는 경량 클라이언트(SPV)는 블록 헤더와 머클 증명만으로 트랜잭션 포함 여부를 확인합니다.
- **BitTorrent:** P2P 파일 공유 프로토콜로, BitTorrent v2(BEP 52) 등에서 내려받은 데이터 조각을 검증하는 데 머클 트리를 사용합니다.
- **분산 데이터베이스:** 복제본 사이의 데이터가 일치하는지 비교할 때 서로 다른 하위 트리만 찾아 동기화하는 데 쓰입니다.

---
출처: https://achivx.kr/glossary/merkle-tree-%EB%A8%B8%ED%81%B4-%ED%8A%B8%EB%A6%AC/ · ACHIVX 용어 사전 · 수정일 2026-10-20