Merkle 트리: 대규모 트랜잭션 무결성

Bitcoin 블록에는 약 2000개의 거래가 포함됩니다. 2000개의 거래를 모두 다운로드하지 않고 거래 T가 포함되어 있음을 증명하려면 간결한 증명이 필요합니다. Merkle 트리가 이를 해결합니다. 증명 크기는 O(n)개의 거래가 아니라 O(log n)개의 해시입니다.

리프: 각 거래의 SHA256d(이중 SHA256)입니다. 부모: SHA256d(left_child_hash || right_child_hash)입니다. 하나의 루트 해시가 남을 때까지 반복합니다. 노드 수가 홀수이면 마지막 노드를 복제합니다. 루트는 블록 헤더에 저장되는 Merkle root(32바이트)입니다.

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

거래 T가 위치 i에 있음을 증명하려면 T의 리프에서 루트까지 각 수준의 형제 해시를 제공합니다(O(log n)개의 해시). 검증자는 T와 형제 경로를 사용해 루트를 다시 계산합니다. 계산된 루트가 블록 헤더의 Merkle root와 일치하면 T가 포함되었음이 증명됩니다.

1024개의 거래 → Merkle 증명 = 해시 10개 = 320바이트입니다. 전체 블록 = 약 1 MB입니다. SPV 클라이언트는 관심 있는 각 거래에 대해 80바이트 헤더와 320바이트 Merkle 증명만 다운로드하므로 전체 블록을 다운로드하는 것보다 대역폭을 99.97% 절약할 수 있습니다.

트리의 거래가 하나라도 변경되면 해당 리프 해시가 변경되고, 그 변경이 위로 전파되어 Merkle root가 바뀝니다. 변경된 루트는 더 이상 PoW로 봉인된 블록 헤더와 일치하지 않습니다. 거래에서 루트를 계산하면 모든 수정 사항을 탐지할 수 있습니다.

Ethereum은 트라이를 사용해 Merkle 트리를 확장합니다(Patricia Merkle Trie). 이는 각 노드에 Merkle 해시를 적용하는 16진수 접두사 인코딩 기수 트라이입니다. 상태 트라이(계정 잔액), 거래 트라이, 영수증 트라이에 사용됩니다. 전체 노드 데이터를 보유하지 않고도 계정 상태를 효율적으로 증명할 수 있습니다.

Merkle Mountain Range(MMR)는 로그와 유사한 데이터를 위한 추가 전용 Merkle 구조입니다. 새 요소를 추가하면서 2의 거듭제곱 크기 부분 트리의 루트인 피크를 유지합니다. Grin/MimbleWimble과 ZCash에서 추가 전용 로그에 대한 효율적이고 간결한 증명을 제공하는 데 사용됩니다.

Ethereum의 로드맵에서는 Merkle 트리를 Verkle 트리로 대체합니다(EIP-6800). 해시 대신 벡터 커밋먼트(KZG 다항식 커밋먼트)를 사용합니다. 증명 크기는 Merkle 트리의 O(log n)에서 O(1)로 줄어듭니다. 이를 통해 상태 비저장 클라이언트가 전체 트라이를 저장하지 않고도 상태를 검증할 수 있습니다.

인증서 투명성(RFC 6962)은 추가 전용 Merkle 로그를 사용하며, CA가 발급한 각 인증서가 리프가 됩니다. 포함 증명은 인증서가 로그에 기록되었음을 검증합니다. 일관성 증명은 로그가 추가 전용인지, 즉 삭제나 삽입이 없었는지를 검증합니다. 브라우저 공급업체는 이 로그를 통해 SCT를 검증합니다.

Git 트리(디렉터리 스냅샷)는 Merkle 트리입니다. 각 트리 노드는 파일 데이터 객체와 하위 트리의 해시를 계산합니다. 커밋 해시는 전체 코드베이스 상태를 고유하게 식별합니다. 따라서 git checkout 를 실행하면 항상 정확히 동일한 파일을 얻습니다.

리프가 1024개인 트리에서 포함을 증명하려면 Merkle 증명에 해시가 몇 개 필요합니까?

Merkle 트리는 O(log n) 크기의 포함 증명을 가능하게 합니다. Bitcoin은 블록 헤더에 Merkle root를 저장하고 SPV 클라이언트는 증명을 사용합니다. Ethereum은 이를 Patricia Merkle Trie로 확장합니다. Verkle 트리는 O(1) 증명을 위해 Merkle 트리를 대체할 예정입니다. 다음 주제: Proof of Work 채굴과 난이도입니다.