Merkle Tree (머클 트리)

Merkle Tree (머클 트리)

리프 노드가 데이터 블록의 해시이고 비리프 노드가 자식 해시의 해시인 이진 트리 구조로, 대용량 데이터의 무결성을 효율적으로 검증하고 동기화 가능

목적: 데이터 무결성 검증, 효율적 동기화, 변조 탐지, 부분 검증

특징: 해시 트리, O(log n) 검증, 경로 증명, 변경 탐지

구조

• •리프 노드: 데이터 블록의 해시 H(data_i)
• •내부 노드: 자식 해시의 연결 해시 H(H_left || H_right)
• •루트: 전체 데이터를 대표하는 단일 해시(Merkle Root)

검증 과정

• •루트 해시 비교로 전체 무결성 즉시 확인
• •특정 데이터 검증: 경로상의 해시만 필요 O(log n)
• •차이점 탐지: 루트→하위로 탐색하여 변경된 블록 식별

Merkle Proof: 특정 데이터가 트리에 포함됨을 증명, O(log n) 크기

동기화 활용: 루트 비교 → 다르면 자식 비교 → 차이 부분만 동기화

장점: 효율적 검증 O(log n), 부분 검증 가능, 변조 즉시 탐지, 대역폭 절약

단점: 트리 구축 오버헤드, 해시 계산 비용, 추가 저장 공간

적용사례: 블록체인(비트코인, 이더리움), Git, IPFS, Amazon S3, 분산 DB

비교: Merkle Tree(O(log n)검증) vs 전체해시(O(n)검증) vs 체크섬(무결성만)

연관: 블록체인, 해시 함수, Git, 분산 시스템, 무결성 검증