Merkle Tree란 무엇인가?
Merkle Tree는 큰 레코드 집합을 하나의 짧은 지문으로 압축하는 데이터 구조입니다. 전체를 모두 확인하는 대신 아주 작은 조각들만 확인해 아이템이 거대 리스트에 포함되어 있는지 증명하게 해 줍니다. 부모가 자식의 요약인 가족 계보를 생각하면 이해하기 쉽습니다. 결국 하나의 최종 조상이 되도록 모두 모이는 구조죠.
Merkle Tree가 모든 트랜잭션을 자체적으로 “저장”하는 것은 아닙니다. 실제로는 이들의 압축된 지문만 저장되며, 필요할 때 원시 레코드로부터 트리를 재구성할 수 있습니다.
Merkle Tree가 작동하는 방식
빠르고 검증 가능한 요약이 필요한 지불 블록을 상상해 보세요. 여기서 Merkle Tree의 작동 원리를 쉽게 설명합니다:
- Step 1: 트랜잭션처럼 항목 목록을 시작으로, 각 항목을 트리의 리프(잎)로 둡니다.
- Step 2: 각 항목을 해시 함수를 사용해 짧은 지문으로 만듭니다.
- Step 3: 인접한 지문을 짝지어 서로 합친 뒤 다시 해시하여 부모를 만듭니다.
- Step 4: 짝짓기와 해싱 사다리를 반복해 단일 최상위 지문이 남을 때까지 진행합니다. 이것이 이 세트의 Merkle 루트입니다.
- Step 5: 어떤 항목이 집합에 속한다는 것을 증명하려면 해당 항목과 짝인 지문들의 짧은 경로만 필요합니다. 빠르고 아주 작습니다.
그 아이디어는 이렇습니다: 작은 증거들, 큰 확신.
Merkle Tree가 중요한 이유
거대한 거래 데이터를 하나의 압축된 지문으로 요약함으로써, Merkle Tree는 검증을 빠르고 저렴하게 만듭니다.
- 장점: 전체 블록을 다운받지 않고 포함 여부를 확인할 수 있어 시간과 대역폭을 절약합니다.
- 관점: 지금 인터넷의 분위기에 맞는 신뢰하되 검증하라(trust but verify) 접근법으로, 로렉스가 레딧 스레드를 만납니다.
- 관련성: 비트코인 블록, 이더리움 영수증, NFT 허용 목록, 에어드랍 및 롤업에서 접하게 됩니다.
리프의 수가 홀수인 경우 많은 설계가 마지막 것을 해싱하기 전에 하나를 더 복제합니다. 또한 체인이나 라이브러리가 사용하는 정확한 해싱 과정을 다시 확인해 보세요. 아주 작은 규칙 차이가 증명을 바꿀 수 있습니다.
Merkle Tree의 주요 특징
다음은 그것을 특별하고 유용하게 만드는 점들입니다:
- 효율성: 데이터 집합이 커져도 증거가 작게 유지되어 경량 클라이언트도 가볍습니다.
- 무결성: 리프의 한 바이트를 바꾸면 최상단까지 변화가 파급되어 변조가 명확해집니다.
- 루트: 모든 것이 하나의 Merkle 루트로 수렴되어 보관하거나 나중에 확인을 위해 서명할 수 있습니다.
Variations
Merkle Tree에는 자주 보게 되는 몇 가지 인기 있는 변형이 있습니다:
- Binary: 비트코인 블록에서 쓰이는 클래식한 짝 기반 트리.
- Merkle Patricia: 이더리움 상태와 영수증에 쓰이는 키-값 데이터용 트라이 기반 버전.
- Sparse: 대부분의 리프가 비어 있는 거대한 인덱스 트리로, 간결한 멤버십 및 비멤버십 증거에 좋습니다.
- Verkle: 훨씬 큰 분기로 짧은 증거를 제공하는 더 새로운 사촌으로, 향후 업그레이드에 대해 탐구 중입니다.
Merkle Tree 증거는 당신이 수락하는 헤더나 체크포인트만큼만 신뢰할 수 있습니다. 잘못된 루트를 신뢰하면 가장 깔끔한 증거도 아무 것도 말해 주지 못합니다.
예시
비트코인 스타일의 라이트 월렛은 거래를 확인하기 위해 트랜잭션에서 블록 헤더까지의 짧은 해시 경로를 확인함으로써 전체 거래 기록를 다운로드하지 않고도 결제를 검증할 수 있습니다.
재미있는 사실
Ralph Merkle은 1970년대 말에 학생 프로젝트로 이 아이디어를 스케치했고, 수년간 학계에서 머물다 Satoshi가 비트코인에 이를 사용하기 전까지 알려지지 않았습니다. 좋은 아이디어는 시대를 초월한다는 증거죠.
정리
결론은 무엇일까요? Merkle Tree는 거대한 집합에 속하는지 여부를 빠르고 아주 작은 증거로 확인할 수 있게 해 주며, 과도한 다운로드 없이도 확인이 가능합니다.