Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus

Posted Dec 31, 2025

By hwanseok jang

7 min read

Reference

기존 블록체인 프로토콜의 한계: 모놀리식(Monolithic) 구조
- 네트워크에서 리더가 선정되면 거래 수집, 블록 생성, 전파, 합의를 모두 리더 혼자 처리함.
- 합의 알고리즘 자체보다, 대용량 블록 데이터를 리더가 전파하는 과정의 대역폭(Bandwidth)이 시스템 전체의 병목(Bottleneck)이 됨.
해결책: 두 가지 핵심 모듈의 분리
- 나왈(Narwhal): 무거운 거래 데이터를 안정적으로 전파하고 가용성을 보장하는 고성능 데이터 전파 레이어 (Mempool).
- 터스크(Tusk): 전파된 데이터의 순서(Ordering)만 정하는 효율적인 비동기 합의 레이어 (Consensus).
데이터 가용성 증명 (Availability Proof)
- 나왈이 데이터를 전파하면, 네트워크의 일정 수 이상의 검증인이 이를 수신했음을 나타내는 ‘가용성 증명’ 영수증을 발급함.
- 합의 엔진(터스크)은 무거운 실제 데이터 대신, 이 가벼운 영수증들만 모아서 순서를 정함.
- 이 과정을 통해 합의 과정에서 처리해야 할 데이터 용량이 약 1/12,000 수준으로 획기적으로 줄어듦.

DAG (Directed Acyclic Graph) 구조
- 기존 체인 방식과 달리 여러 블록이 서로를 참조하는 그래프 구조를 가짐.
- 라운드(Round)라는 시간 단위로 동작하며, 각 라운드에서 블록을 생성하려면 이전 라운드 블록의 2/3(2f+1) 이상에 대한 가용성 증명을 포함해야 함.
주요 특징
- 2/3 인과적 일관성 (Causal Consistency): 새로 참여하거나 연결이 끊겼던 노드가 최신 라운드의 블록 하나만 받아도, 그 블록이 참조하는 과거 기록의 2/3 이상을 즉시 확보할 수 있어 동기화가 매우 빠름.
- 검열 저항성 (Censorship Resistance): 특정 리더가 거래를 무시하더라도, 정직한 참여자들이 생성하는 블록들이 DAG 내에 2/3 이상 포함되므로 특정 거래가 무시당하는 것을 방지함.
스케일 아웃 (Scale-out) 설계
- 검증인 노드 내부를 Primary(관리)와 여러 개의 Worker(데이터 처리)로 분리함.
- 무거운 데이터를 처리하고 다른 노드의 워커와 공유하는 작업은 워커들이 담당하고, Primary는 워커들이 처리한 데이터 배치의 해시값(증명)만 모아서 관리함.

추가 메시지 오버헤드 없음
- 순서 합의를 위해 노드 간에 추가적인 메시지를 주고받지 않음. 모든 정보는 이미 나왈이 만든 DAG 구조 안에 포함되어 있기 때문임.
DAG 해석 규칙의 집합
- 터스크는 통신 프로토콜이 아니라, 공유된 DAG를 어떻게 읽을 것인가에 대한 규칙(Logic)임. 모든 노드가 동일한 DAG 지도와 규칙을 가지고 있으므로 각자 계산해도 동일한 결론에 도달함.
공유된 무작위성 (Shared Randomness)
- 각 라운드마다 예측 불가능한 난수(Shared Coin)를 생성하여 과거 블록 중 하나를 ‘리더 블록’으로 선정함.
- 특정 노드를 리더로 투표하는 과정이 없으므로, 네트워크 지연이나 일부 노드의 공격에도 합의가 멈추지 않는 강력한 회복 탄력성을 가짐.

처리량 비교
- 기존 HotStuff: 초당 약 1,800건 (전파 병목 발생).
- Narwhal + HotStuff: 초당 약 130,000건 (전파 병목 해결의 효과 입증).
- Narwhal + Tusk: 초당 약 160,000건 이상 (비자 카드의 처리 속도를 상회).
장애 상황 대응 (Fault Tolerance)
- 10명의 검증인 중 3명이 실패하는 상황 가정:
  - HotStuff: 리더에게 의존하므로 처리량이 1/30로 급감하고 응답 시간이 10배 증가하며 시스템이 마비됨.
  - Narwhal + Tusk: 리더가 특정되지 않는 비동기 방식 덕분에 처리량이 그대로 유지되며 시스템이 정상 작동함.

패러다임의 전환: 합의를 ‘데이터 전파’와 ‘순서 결정’으로 완전히 분리함으로써 성능과 안정성을 동시에 확보할 수 있음을 증명함.
남은 과제: 통신(Networking) 단계의 병목이 해결됨에 따라, 이제는 실제 트랜잭션을 처리하는 실행 엔진(Execution Engine) 및 상태 저장(State Storage)의 병목을 해결하는 것이 차세대 블록체인의 핵심 과제가 될 것임.

This post is licensed under CC BY 4.0 by the author.