DAG 기반 BFT 합의와 리더 기반 BFT

비잔틴 환경에서 처리량 상한을 정하는 것은 합의 알고리즘이 아니라 리더 한 대의 업링크입니다.

크래시 장애와 비잔틴 장애의 갈림길

합의 프로토콜을 고를 때 먼저 정해야 하는 것은 어떤 장애를 견딜지입니다. 크래시 장애 허용(Crash Fault Tolerant, CFT)은 노드가 멈추거나 응답하지 않는 경우만 다룹니다. 비잔틴 장애 허용(Byzantine Fault Tolerant, BFT)은 노드가 서명을 위조하거나 상대마다 다른 값을 보내는 경우까지 다룹니다.

차이는 정족수 크기에서 바로 드러납니다. CFT는 f개 장애를 견디는 데 2f+1 노드면 충분하지만, BFT는 3f+1 노드가 필요합니다. 같은 내결함성에 노드를 1.5배 쓰고, 메시지마다 서명 검증 비용을 더 냅니다.

리더가 없다는 표현은 두 모델 모두에서 쓰이지만 뜻이 다릅니다. EPaxos나 Accord 같은 크래시 모델의 리더리스는 정족수 응답이 모이면 그 내용을 그대로 믿습니다. 비잔틴 모델에서는 응답 자체가 거짓일 수 있고, 한 노드가 상대마다 다른 값을 보내는 모순 발언(equivocation)까지 막아야 합니다. 이 글이 다루는 것은 후자입니다.

리더 한 대가 정하는 처리량 상한

리더 기반 BFT의 원형은 PBFT입니다. Castro와 Liskov가 1999년 OSDI에서 발표했고, 프라이머리가 요청에 순서 번호를 붙인 뒤 pre-prepare, prepare, commit 세 단계를 돕니다. 뒤 두 단계에서 복제본끼리 서로 통신하므로 정상 경로 메시지가 O(n²)로 늘어납니다.

HotStuff(Yin 외, PODC 2019)는 이 비용을 낮췄습니다. 임계 서명(threshold signature)으로 정족수의 투표를 인증서(quorum certificate) 하나에 압축합니다. 그 결과 단계별 메시지가 O(n)으로 줄고 리더 교체 비용도 선형이 됐습니다. Diem의 합의 계층이 이 구조에서 나왔습니다.

메시지 개수는 줄었지만 통신 형태는 그대로입니다. 모든 메시지가 리더를 중심으로 오가는 별 모양이고, 트랜잭션 본문도 리더가 나머지 복제본에 뿌립니다. 클러스터 처리량은 리더 한 대의 업링크 대역폭에서 멈추고, 나머지 노드의 업링크는 대부분 놀게 됩니다.

전파와 순서를 분리하는 DAG

Narwhal(Danezis 외, EuroSys 2022)은 이 병목을 계층 분리로 풉니다. 트랜잭션 배치를 퍼뜨리는 mempool 계층과 순서를 정하는 합의 계층을 나눕니다. mempool 계층에서는 모든 검증자가 동시에 자기 배치를 방송하므로 네트워크 전체 대역폭을 씁니다.

이때 쌓이는 자료 구조가 유향 비순환 그래프(Directed Acyclic Graph, DAG)입니다. 라운드마다 검증자가 vertex를 하나 만들고, vertex는 배치 해시와 직전 라운드 vertex 참조를 담습니다.

vertex(v, r) = {
  트랜잭션 배치 해시,
  라운드 r-1 vertex 참조 2f+1개,
  검증자 v의 서명
}

참조가 2f+1개 모여야 다음 라운드로 넘어갑니다. 이 수는 정직한 노드 다수가 그 vertex를 이미 봤다는 것을 보장하는 최소치입니다. 응답이 느린 f개 노드는 기다리지 않고 지나칩니다.

순서는 이 그래프를 읽어서 정합니다. Bullshark(Spiegelman 외, CCS 2022)는 라운드마다 결정적 규칙으로 앵커(anchor) vertex를 하나 고릅니다. 앵커가 확정되면 그 앵커가 직간접으로 참조하는 모든 vertex, 곧 인과 이력(causal history) 전체가 한 번에 확정 순서로 들어갑니다.

이 계산에는 추가 메시지가 들지 않습니다. 정직한 노드는 결국 같은 DAG를 보게 되므로, 같은 규칙을 각자 돌리면 같은 순서가 나옵니다. 순서 결정이 통신 문제에서 로컬 해석 문제로 바뀝니다.

Mysticeti(arXiv 2310.14821, NDSS 2025)는 여기서 인증서를 뺐습니다. vertex마다 정족수 서명을 모아 인증서를 만드는 과정을 생략하고, 인증되지 않은 DAG 위에서 바로 판정합니다. 인증 오버헤드가 사라진 만큼 커밋 지연이 줄었습니다.

처리량과 지연의 실측

각 논문의 실험 환경이 다르므로 절대 비교가 아니라 자릿수 비교로 읽어야 합니다. Raft 행은 비잔틴 장애를 가정하지 않은 CFT 수치라는 점도 함께 감안해야 합니다.

복제본이 10개에서 50개로 늘 때 두 DAG 프로토콜의 방향이 갈립니다. Bullshark는 처리량을 유지하는 반면 Mysticeti는 약 300K tps에서 약 100K tps로 떨어집니다. 인증서를 없앤 이득이 검증자 수가 커질수록 줄어든다는 뜻입니다.

지연 축에서는 CFT 쪽이 압도합니다. etcd의 Raft가 p50 약 5 ms를 내는 자리에서 DAG 계열은 수백 밀리초대에 있습니다. DAG는 라운드 단위로 진행하고 앵커가 확정될 때까지 여러 라운드를 기다리므로, 커밋 지연이 라운드 시간의 배수로 쌓입니다.

두 축을 겹쳐 보면 DAG는 처리량을 얻는 대가로 지연을 내주는 구조입니다. 초당 수십만 건을 넘겨야 하는 워크로드가 아니라면 이 교환은 손해입니다.

장애가 났을 때 드러나는 비용

DAG의 라운드 구조는 정상 상황에서 강하고 장애 상황에서 약합니다. 노드 하나가 느려지거나 멈추면 다음 라운드 vertex가 그 노드의 참조를 기다리게 되고, 라운드 전체가 그만큼 밀립니다. 2f+1 참조 규칙이 f개까지는 건너뛰게 해 주지만, 그 이상이 흔들리면 진행 자체가 막힙니다.

누락된 vertex를 가져오는 경로도 문제입니다. 참조는 받았는데 vertex 본체를 아직 못 받은 노드는 그것을 따로 요청해야 하고, 이 왕복이 크리티컬 경로에 들어옵니다. 결과적으로 네트워크 신뢰성과 노드 간 동기화 수준이 프로토콜 자체보다 성능을 크게 좌우합니다.

앵커 선택 빈도에도 같은 긴장이 있습니다. 앵커를 자주 고르면 커밋 지연이 줄지만, 검증자 사이 DAG 구조가 어긋날 확률이 높아져 누락 vertex 재전송이 늘어납니다. Shoal++(arXiv 2405.20488)는 앵커를 파이프라인으로 겹쳐 이 긴장을 완화합니다.

Shoal++가 보고한 개선폭은 두 방향입니다. Bullshark 대비 일반 케이스 지연을 최대 60% 줄였습니다. 느린 노드를 타임아웃으로 우회하는 낙관적 경로(optimistic fast path)를 더해, 장애 케이스 지연은 Mysticeti 대비 최대 10배 줄였습니다. 장애 케이스 쪽 격차가 더 큰 것이 DAG 계열의 약점이 어디였는지 보여 줍니다.

Angelfish(arXiv 2509.15847, 2025)는 구조 자체를 부하에 맞춰 바꿉니다. 부하가 낮으면 최선 노력 브로드캐스트(best-effort broadcast) 기반의 가벼운 투표로 지연을 낮춥니다. 부하가 높아지면 full DAG vertex 방송으로 전환해 처리량을 끌어올립니다. 리더 기반과 DAG 기반 사이를 부하에 따라 오가는 설계입니다.

무엇을 언제 고르는가

첫 갈림길은 신뢰 경계입니다. 노드를 전부 직접 운영하는 사내 인프라나 단일 클라우드 계정이라면 BFT가 필요 없습니다. etcd나 ZooKeeper 같은 CFT 기반 저장소를 쓰고, 3f+1 노드와 서명 검증에 들어갈 비용을 아끼는 편이 낫습니다.

BFT가 필요하다면 다음 질문은 목표 처리량입니다. 검증자가 수십 개 규모이고 초당 수만 건 이하라면 HotStuff 계열 리더 기반 BFT가 구현과 운영에서 유리합니다. 상태 기계가 하나뿐이라 추론과 디버깅이 쉽고, 커밋 지연도 DAG 계열보다 짧습니다.

초당 수십만 건을 넘겨야 하거나 검증자가 지리적으로 흩어져 있으면 DAG 기반 BFT가 현실적인 선택입니다. 이때 인프라를 알고리즘보다 먼저 확인해야 합니다. 검증자 간 대역폭이 고르지 않거나 패킷 손실이 잦으면 누락 vertex 요청이 잦아져 DAG의 이점이 사라집니다.

부하가 시간대에 따라 크게 요동친다면 Angelfish 같은 하이브리드 방향을 지켜볼 만합니다. 다만 DAG 계열은 대부분 연구 단계이거나 특정 체인 구현에 묶여 있어, 채택 전에 구현체의 성숙도를 따로 확인해야 합니다. 계열 전체를 훑을 때는 SoK: DAG-based Consensus Protocols(arXiv 2411.10026)가 출발점으로 적당합니다.

정리

BFT를 쓸지는 신뢰 경계가, 그중 어떤 BFT를 쓸지는 목표 처리량이 결정합니다. 리더 기반 BFT는 HotStuff가 메시지 복잡도를 O(n)으로 줄였지만 트랜잭션 본문이 리더를 거치는 구조는 그대로라, 리더 업링크가 처리량 상한이 됩니다. DAG 기반 BFT는 전파와 순서 결정을 분리해 그 상한을 걷어내고, 순서를 추가 통신 없이 로컬 계산으로 얻습니다. 대가는 지연이며, Raft가 p50 약 5 ms를 내는 자리에서 DAG 계열은 수백 밀리초를 쓰고 노드 하나가 느려지면 라운드 전체가 밀립니다. Shoal++와 Angelfish는 그 대가를 줄이는 두 갈래 시도이고, 어느 쪽을 고르든 검증자 사이 네트워크 품질이 논문 수치의 재현 여부를 가릅니다.