컴퓨터공학
Merkle Tree머클 트리
머클 트리(Merkle Tree)는 데이터 집합을 효율적으로 검증하기 위한 해시 기반 트리 구조다. 1979년 Ralph Merkle이 제안했으며, 블록체인에서 트랜잭션의 무결성을 검증하는 핵심 자료구조로 사용된다.
구조
- •리프 노드: 각 트랜잭션의 해시
- •부모 노드: 두 자식 해시를 합쳐 해시
- •루트 해시(Merkle Root): 트리 전체를 대표하는 단일 해시
블록체인에서의 역할
블록 헤더에 포함
Bitcoin과 Ethereum 블록 헤더에 Merkle Root가 포함된다. 이를 통해:
- •블록 내 임의 트랜잭션의 포함 여부를 전체 블록 다운로드 없이 검증 가능
간편 결제 검증 (SPV)
모바일 등 경량 클라이언트는 전체 블록체인 대신 블록 헤더만 다운로드하고, Merkle Proof로 특정 거래가 블록에 포함됐는지 증명받을 수 있다.
효율성
| N개 트랜잭션 검증 | 일반 방식 | 머클 트리 |
|---|---|---|
| 데이터 다운로드 | N개 전체 | log₂(N) 해시 |
| 1,000개 TXN | 1,000개 | 10개 해시 |
Ethereum Patricia Merkle Trie
이더리움은 단순 Merkle Tree 대신 Patricia Merkle Trie(MPT)를 사용한다. 계정 상태, 트랜잭션, 스토리지를 모두 트라이 구조로 관리해 상태 변경 시 효율적인 업데이트와 증명이 가능하다.
Merkle Proof 실제 활용
| 활용 | 설명 |
|---|---|
| SPV(경량 클라이언트) | 전체 블록체인 없이 트랜잭션 포함 증명 |
| NFT Allowlist | 허용 주소 목록의 Merkle Root만 컨트랙트에 저장 |
| 에어드롭 검증 | 수령 자격을 Merkle Proof로 검증, 가스 절감 |
| ZK 증명 | 머클 경로를 ZK-SNARK 입력으로 활용 |
관련 개념
참고문헌
- •Merkle, R. (1987). A Digital Signature Based on a Conventional Encryption Function
- •Nakamoto, S. (2008). Bitcoin Whitepaper §8 Simplified Payment Verification
