에듀테크 프로젝트 대시보드
머클 트리 (Merkle Tree)
1979년 랠프 머클이 고안한 해시 트리다. 여러 데이터 조각을 각각 해시한 값을 잎(leaf)으로 두고,
두 개씩 이어붙여 다시 해시하기를 반복해 하나의 루트 해시(root hash)로 요약한다.
데이터가 아무리 많아도 단 하나의 해시값만 비교하면 전체가 그대로인지 알 수 있고,
한 조각만 검증하고 싶을 때는 루트까지의 형제 해시 log₂N개만 있으면 된다.
Git, 비트코인, IPFS, BitTorrent, 인증서 투명성 로그가 모두 이 구조를 쓴다.
해시는 설명용으로 축약한 32비트 해시를 16진수 8자리로 표시합니다. 실제 시스템은 SHA-256 같은 암호학적 해시를 씁니다.
검증자는 전체 데이터를 몰라도 됩니다. 초록색 형제 해시 몇 개와 블록 하나만 받아 위로 해시를 이어 올라가서, 이미 알고 있던 루트 해시와 같은지만 확인하면 됩니다.
# 잎: 각 데이터 블록의 해시 def build_merkle(blocks): level = [hash(b) for b in blocks] tree = [level] while len(level) > 1: if len(level) % 2: level.append(level[-1]) # 홀수면 마지막 복제 level = [hash(level[i] + level[i+1]) for i in range(0, len(level), 2)] tree.append(level) return tree # tree[-1][0] == 루트 해시 # 증명: index 블록 → 루트까지 형제 해시만 모은다 (O(log N)) def proof(tree, index): path = [] for level in tree[:-1]: sib = index ^ 1 # 짝꿍 인덱스 path.append((level[sib], "L" if sib < index else "R")) index //= 2 return path # 검증: 블록 + 형제 해시들 → 루트를 재구성해 비교 def verify(block, path, root): h = hash(block) for sib, side in path: h = hash(sib + h) if side == "L" else hash(h + sib) return h == root
커밋의 tree 객체가 머클 트리다. 파일 하나만 바뀌어도 상위 tree·커밋 해시가 전부 바뀌어 이력이 변조 불가능해진다.
블록 헤더에는 거래들의 머클 루트만 담긴다. 가벼운 지갑(SPV)은 거래 1건 + 형제 해시만으로 포함 여부를 검증한다.
큰 파일을 조각내 해시 트리로 묶는다. 손상된 조각만 골라 다시 받고, 여러 피어에서 병렬로 받아도 무결성이 보장된다.
발급된 모든 TLS 인증서를 추가 전용 머클 로그에 기록한다. 몰래 끼워 넣거나 지우면 루트가 어긋나 들킨다.
DynamoDB·Cassandra의 anti-entropy: 노드끼리 머클 트리를 비교해 실제로 다른 구간만 찾아 전송량을 줄인다.
ZFS, rsync류 도구가 블록 해시를 트리로 관리해 바뀐 블록만 빠르게 찾아낸다.
O(1) 비교로 판정.log₂N개면 루트까지 재구성 가능 → 대역폭·저장공간 절약.CVE-2012-2459 같은 취약점도 있었다.