Bullshark: Making DAG-based BFT Protocols Practical

Posted Dec 31, 2025

By hwanseok jang

6 min read

Bullshark: DAG BFT Protocols Made Practical

BFT (Byzantine Fault Tolerance): 일부 노드가 신뢰할 수 없거나 장애가 발생한 상황에서도 모든 거래 기록에 대해 합의를 이뤄낼 수 있는 알고리즘.
DAG(Directed Acyclic Graph) 프로토콜
- 장점: 각 블록이 단 하나의 부모가 아닌 여러 개의 이전 블록을 참조함. 참여자들은 공유된 그래프를 해석하는 것만으로도 누가 어떤 정보를 받았는지 알 수 있어, 합의를 위한 별도의 통신 오버헤드가 적음.
DAG-Rider (이전의 SOTA):
- 장점: 네트워크가 완전히 마비되는 최악의 비동기 상황에서도 합의가 가능하도록 설계됨.
- 단점: 정상적인 상황에서도 항상 최악의 시나리오(재난 대비 매뉴얼)로 동작하여 속도가 느림.
- 메모리 문제: 정직한 참여자의 거래가 언젠가는 처리됨을 보장해야 하므로, 아주 느린 참여자의 거래까지 기다려야 함. 이로 인해 운영 시간이 길어질수록 메모리 사용량이 무한정 늘어나는 문제 발생.

Bullshark는 네트워크 상태에 따라 두 가지 모드로 동작하여 성능을 극대화합니다.

정상 상황 (Steady-state) 리더: 미리 정해진 순서에 따라 리더가 블록을 제안하고, 매우 신속하게 합의를 마침 (Fast-path).
장애 상황 (Asynchronous fallback) 리더: 장애 발생 시 대체 리더가 동작하며, 무작위 리더 선출을 통해 느리지만 확실하게 합의가 진행되도록 보장함.
모드 전환 및 웨이브(Wave):
- 합의 단위인 ‘웨이브’가 끝날 때마다 투표를 진행함.
- 이전 웨이브의 리더가 합의에 성공했다면 계속 정상 모드를 유지하고, 문제가 생겼을 때만 비동기 모드로 전환하여 비용을 최적화함.
단순함: 이 복잡한 로직을 단 200줄 내외의 코드로 구현 가능할 만큼 효율적임.

기존 프로토콜: 리더에게 문제가 생기면 시스템이 멈추고 새로운 리더를 선출하는 복잡한 ‘View Change’ 과정이 필요했음.
Bullshark (DAG 기반): DAG 구조 덕분에 다음 단계에 필요한 모든 정보가 공유된 지도로 암호화되어 있음. 모든 참여자가 다른 노드의 상태를 즉시 알 수 있으므로, 별도의 선거 절차 없이도 합의를 이어갈 수 있음.

이론적 한계: 비동기 환경에서 ‘완벽한 공정성’과 ‘유한한 메모리’를 동시에 만족하는 것은 불가능함 (느린 노드를 무한정 기다리면 메모리가 터지고, 지우면 공정성이 깨짐).
해결책 (Timestamp 도입):
- 각 데이터 블록에 타임스탬프를 추가함.
- 특정 라운드의 타임스탬프 중앙값(Median)을 기준으로 너무 오래된 라운드의 데이터는 삭제함.
효과: 네트워크가 안정된 이후 제출된 데이터에 대해서는 100% 공정성을 보장하며, 네트워크 불안정 시에는 느린 참여자의 블록을 적절히 정리하여 메모리 고갈을 방지함.

처리량: * HotStuff 대비 약 2배 이상의 처리량을 기록.
- Tusk 대비 지연 시간(Latency)을 약 33% 단축.
- 50개 노드 기준 초당 약 125,000건 처리, 지연 시간 2초 미만.
회복 탄력성 (Resilience):
- 10개의 노드 중 3개가 고장 난 상황에서도 성능 저하가 거의 없이 동작함.
- 리더 중심의 HotStuff가 시스템 붕괴 수준의 타격을 입는 것과 대조적임.
실제 적용: 현재 Aptos(앱토스) 네트워크의 핵심 합의 엔진으로 채택되어 사용 중임.

자가 적응 능력의 발전: 참여자들이 DAG를 실시간으로 분석하여 과거 웨이브의 성공 여부를 학습하고, 정상/대체 모드 사이의 전환 타이밍을 최적화할 수 있음.
지능형 합의: 단순한 네트워크 상태 변화를 넘어, 공격을 탐지하여 방어하거나 수수료 등 경제적 인센티브에 맞춰 모드 전환을 스스로 학습하는 방향으로 진화할 가능성이 큼.

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