기술 요약: MHOT – 블록체인 상태 커밋을 위한 높이 최적화 인증 데이터 구조

1. 문제 정의

이더리움을 포함한 현대 블록체인 시스템에서 상태 루트(state root) 계산은 전체 블록 처리 시간의 약 70~80%를 소비한다. 현재의 표준 인증 데이터 구조(ADS)인 머클 패트리샤 트라이(Merkle Patricia Trie, MPT)는 두 가지 결정적인 한계를 갖는다:

1. Nurgle 공격에 대한 구조적 취약성: MPT는 고정 접두사 인덱싱(fixed-prefix indexing)을 사용하며, 여기서 각 트리 레벨은 고정된 개수의 연속적인 키 비트를 소비한다. 이러한 구조는 공격자가 해시 충돌을 통해 긴 공통 접두사를 악용하여 경로 깊이를 인위적으로 늘릴 수 있게 한다. "Nurgle 공격"(S&P '24)은 공격자가 아주 적은 가스 비용으로 압축된 경로를 더 깊은 구조로 실체화하도록 유도함으로써 시스템 성능을 저하시키고 I/O 비용을 증가시킬 수 있음을 보여준다.
2. Span–Proof 트레이드오프: 깊이 증가를 완화하기 위해 "span"(레벨당 소비되는 비트 수)을 늘릴 수 있다. 그러나 접두사 기반 트라이에서 span을 늘리면 팬아웃(fanout, 자식 슬롯의 수, $2^{span}$)이 기하급급수적으로 증가한다. 이는 트레이드오프를 강요한다: 높은 span은 높이를 제한하지만 노드 크기와 증명(proof) 크기를 기하급수적으로 팽창시키며, 낮은 span은 증명을 컴팩트하게 유지하지만 트리를 심화 공격에 취약하게 만든다.

Verkle Trie나 LVMT와 같은 기존 대안들은 벡터 커밋먼트(대수적 기법)를 사용하여 팬아웃과 증명 크기를 분리한다. 그러나 이러한 방식은 신뢰할 수 있는 설정(trusted setup) 의식을 필요로 하고, 더 높은 산술 검증 비용을 초래하며, 상태 동기화에 필수적인 범위 증명(range proofs)에 대한 네이티브 지원이 부족한 경우가 많다.

2. 방법론: MHOT

저자들은 MHOT(Height-Optimized Authenticated Data Structure)를 제안한다. 이는 신뢰할 수 있는 설정이나 특수한 암호 기술 없이도 높이 최적화를 달계하는 지속 가능한 해시 기반 ADS이다. MHOT는 높이 최적화 트라이(Height-Optimized Trie, HOT) 구조를 네 가지 핵심 메커니즘을 통해 블록체인 상태 커밋에 적응시킨다:

A. 판별 비트 인덱싱 (구조적 기초)

고정된 연속 접두사를 소비하는 MPT와 달리, MHOT는 **판별 비트(discriminative bits)**를 기준으로 분기한다. 판별 비트는 서브트리 내에서 적어도 두 개의 키가 서로 달라지는 지점이다.

• 선형 결합: 이 접근 방식은 span과 팬아웃을 기하급수적이 아닌 선형적으로 결합한다. 팬아웃 $k$를 가진 복합 노드는 최대 $k-1$개의 판별 비트를 소비하는 반면, 동일한 팬아웃을 가진 접두사 기반 노드는 $\log_2 k$개의 연속 비트를 필요로 한다.
• 적응형 Span: 노드는 실제 키 분포에 따라 적응한다. 밀집된 영역은 더 적은 비트를 사용하고, 희소한 영역은 더 많은 비트를 사용한다. 이를 통해 임의의 키 집합에 대해 증명 가능한 최소 트리 높이를 보장한다.
• Nurgle 저항성: 구조가 고정된 접두사가 아닌 실제 키의 분기점에 의해 결정되기 때문에, 공통 접두사를 가진 공격적 삽입은 내부 재구조화(예: 리프 푸시다운, 부모 풀업)를 통해 별도의 전역 트리 높이 증가 없이 흡수된다.

B. 계층적 증명 (증명 최적화)

복합 노드에서 $k$개의 자식을 직접 해싱하면 $O(k)$의 증명 오버헤드가 발생한다. MHOT는 2계층 머클 구조를 도입한다:

1. 노드 간 계층 (Inter-node Layer): 복합 노드들을 연결한다.
2. 노드 내 계층 (Intra-node Layer): 각 복합 노드는 $k$개의 자식에 대해 내부 이진 머클 트리를 유지한다.

• 결과: 자식의 멤버십을 증명하는 데는 내부 트리의 $k$개 형제 해시 중 $O(\log k)$개만 필요하므로, 증명 크기를 팬아웃에 대한 선형 의존성에서 로그 의존성으로 줄인다. 이는 증명 크기와 span 사이의 선형적 종속성을 깨뜨린다.

C. 콘텐츠 주소 지정 지속성 (Content-Addressable Persistence)

블록체인 상태 커밋을 지원하기 위해 MHOT는 기존의 인메모리 HOT 설계를 수정한다:

• 결정론적 식별자: 노드는 직렬화된 콘텐츠의 해시에 의해 식별된다(콘텐츠 주소 지정 방식). 이는 구조적 결정성(동일한 키 집합이 동일한 트리를 생성함)을 보장하고 신뢰 최소화를 실현한다.
• Copy-on-Write (CoW): 수정 사항은 새로운 노드를 생성하며 조상 해시를 무효화한다. 이는 블록체인 상태 의미론과 일치한다.

D. 배치 커밋 파이프라인 (Batched Commit Pipeline)

경로를 재해싱하는 계산 비용을 처리하기 위해 다음을 수행한다:

• 지연 해싱 (Deferred Hashing): 해시 계산을 블록 커밋 시점까지 미룬다. 트랜잭션 단계 동안 노드는 임시 ID를 사용한다.
• 높이 계층적 병렬화 (Height-Stratified Parallelism): 커밋 시점에 노드들은 높이 순서(리프에서 루트 방향)에 따라 배치로 최종 확정된다. 동일한 높이에 있는 노드들은 데이터 의존성이 없으므로 해시 계산을 효율적으로 병렬화할 수 있다.
• LSM-Tree 친화적 레이아웃: 스토리지 키는 블록 버전과 높이로 프리픽스되어, 순차적 배치 쓰기와 효율적인 컴팩션(compaction)을 가능하게 한다.

3. 주요 기여

1. Span–Proof 결합 식별: 본 논문은 접두사 기반 트라이에서 span과 팬아웃 사이의 기하급수적 결합이 동시에 경계된 최악의 경우 높이와 컴팩트한 증명을 보장할 수 없는 근본 원인임을 밝혀냈다.
2. MHOT 구현: 판별 비트 추적과 고팬아웃 복합 노드를 통해 공격적인 키 분포에 저항하는 높이 최적화 ADS를 제공함으로써, 표준 해시 커밋먼트만을 사용하여 HOT을 블록체인 용도로 적응시켰다.
3. 계층적 증명: per-node 증명 오버 overhead를 $O(k)$에서 $O(\log k)$로 줄이는 새로운 2계층 머클 구조를 도입하여, 높은 팬아웃에서도 컴팩트한 증명을 가능하게 했다.
4. 지속 가능한 HOT: 콘텐츠 주소 지정 인덱싱과 병렬 커밋 파이프라인을 도입하여 디스크 기반 배포라는 HOT의 난제를 해결했다.
5. 종합적 평가: 이더리움 메인넷 워크로드 및 합성 데이터셋을 통해 MPT, RainBlock, LVMT와 MHOT를 벤치마킹하였다.

4. 실험 결과

이더리움 메인넷 워크로드(블록 13.5M–13.51M) 및 합성 데이터셋에서 평가한 결과:

• 처리량 (Throughput): MHOT는 MPT보다 최대 9배 높은 쓰기 처리량을 달성하였으며(100k 키 기준 260k ops/s vs 29k ops/s), LVMT 및 RainBlock을 상당한 차이로 능가했다.
• 쓰기 증폭 (Write Amplification): 배치 플러싱과 감소된 트리 깊이 덕분에 MPT 대비 쓰기 증폭을 4배 줄였다 (0.9–1.6 vs 2.7–4.8).
• 증명 크기 (Proof Size): 계층적 증명 구조 덕분에 MPT보다 2배 작은 증명을 제공한다 (1.1–1.4 KB vs 2.3–2.9 KB).
• Nurgle 공격 저항성: 공격자가 블록 전체의 가스 예산(약 15,000회 삽입)을 통제하는 최악의 시나리오 하에서:
  • MPT: 타겟 키 깊이를 증가시키는 데 99.97%의 성공률을 보였다.
  • MHOT: 0%의 성공률을 기록했다. 구조가 내부 재구조화를 통해 충돌을 흡수하여 깊이 증가를 전파하지 않았다.
• 검증 지연 시간 (Verification Latency): MHOT 검증은 마이크로초 단위로 작동하여 MPT와 유사한 수준을 유지하는 반면, KZG 페어링에 의존하는 LVMT는 밀리초 단위의 지연 시간(3~4 자릿수 더 느림)을 보인다.

5. 의의 및 주장

본 논문은 단순한 암호학적 프리미티브의 도입이 아니라, **높이 최적화(height optimality)**가 확장 가능하고 공격에 강한 블록체인 상태 커밋을 위한 핵심 추상화임을 주장한다.

• 구조적 vs 암호학적 솔루션: MHOT는 판별 비트 인덱싱을 통한 구조적 설계를 통해 트리 높이, 증명 크기, 공격 저항성 사이의 트레이드오프를 해결할 수 있음을 보여주며, 이를 통해 벡터 커밋먼트 체계(Verkle, LVMT)가 가진 신뢰 가정과 높은 검증 비용을 피한다.
• 즉각적인 배포 가능성: 표준 해시 함수(Keccak-256 또는 Blake3)와 기존 머클 인증 원칙에만 의존하므로, 신뢰할 수 있는 설정 의식이나 대수적 검증 변경을 위한 하드 포크 없이도 성능과 보안을 개선할 수 있는 경로를 제공한다.
• 회복 탄력성: 결과는 데이터 구조의 높이와 적응성을 최적화하는 것만으로도, 기존에 경제적 또는 암호학적 대응책이 필요해 보였던 Nurgle 공격 벡터를 무력화하기에 충분하다는 것을 시사한다.

저자들은 세심한 데이터 구조 설계가 블록체인 상태 커밋의 확장성과 견고함을 근본적으로 개선할 수 있음을 결론짓는다.