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

DAG 기반 BFT는 모든 검증자가 데이터를 병렬로 전파해 리더 중심 전파의 대역폭 한계를 줄이지만, 라운드 진행과 자료 가용성이라는 비용을 더합니다.

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

합의 프로토콜을 고를 때 먼저 정해야 하는 것은 어떤 장애를 견딜지입니다. 크래시 장애 허용(Crash Fault Tolerant, CFT)은 노드가 멈추거나 응답하지 않는 경우를 다룹니다. 비잔틴 장애 허용(Byzantine Fault Tolerant, BFT)은 노드가 자기 키로 모순된 값에 서명하거나 프로토콜을 임의로 어기는 경우까지 다룹니다.

표준 인증 BFT 모델은 공격자가 정상 노드의 서명을 위조할 수 없다고 가정합니다. 정족수 크기는 CFT가 2f+1, BFT가 3f+1이며 비율은 f가 커질수록 1.5배에 가까워집니다. BFT에는 인증과 모순 발언 탐지 비용도 추가됩니다.

리더가 없다는 표현은 두 모델 모두에서 쓰이지만 뜻이 다릅니다. 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의 서명
}

이 계열의 인증 DAG에서는 n-f=2f+1개의 직전 라운드 인증서를 참조해야 다음 라운드 제안이 유효합니다. 정족수에는 정상 노드가 최소 f+1개 들어가고, 두 정족수의 교집합에는 정상 노드가 최소 1개 존재합니다. 따라서 최대 f개의 느리거나 응답하지 않는 노드를 기다리지 않아도 진행할 수 있습니다.

flowchart LR
  subgraph R1["라운드 r-1"]
    A1["검증자 A<br/>vertex"]
    B1["검증자 B<br/>vertex"]
    C1["검증자 C<br/>vertex"]
    D1["검증자 D<br/>vertex"]
  end
  subgraph R2["라운드 r"]
    A2["검증자 A<br/>vertex"]
    B2["검증자 B<br/>vertex"]
  end
  subgraph R3["라운드 r+1"]
    ANC["앵커 vertex"]
  end
  A1 --> A2
  B1 --> A2
  C1 --> A2
  B1 --> B2
  C1 --> B2
  D1 --> B2
  A2 --> ANC
  B2 --> ANC

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

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

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

처리량과 지연의 실측

이 수치는 각 논문 안에서 구성한 기준선과 실험 환경에 대해서만 비교할 수 있습니다. etcd의 단일 데이터센터 CFT 지연과 지리 분산 BFT의 지연을 직접 놓고 한 계열이 압도한다고 결론 내릴 수 없습니다.

Shoal++는 기존 인증 DAG의 지연을 큐잉, 앵커 포함, 앵커 커밋으로 나눕니다. 병렬 전파는 처리량을 높일 수 있지만, 라운드 수와 메시지 지연이 커밋 지연을 정합니다. 따라서 같은 네트워크와 장애 모델에서 측정해야 처리량과 지연의 교환 관계를 판단할 수 있습니다.

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

노드 하나가 느리다고 라운드 전체가 반드시 지연되지는 않습니다. 3f+1개 중 2f+1개의 유효한 제안이나 인증서를 확보하면 최대 f개를 건너뛸 수 있습니다. 지연은 정족수에 필요한 빠른 쪽 2f+1개가 늦거나, 커밋에 필요한 인과 이력이 빠졌을 때 커집니다.

flowchart TD
    A["라운드 제안 수집"] --> B{"유효한 2f+1개 확보?"}
    B -->|예| C["다음 라운드와 커밋 규칙 진행"]
    B -->|아니요| D["누락 자료 요청 또는 타임아웃"]
    D --> B
    C --> E{"필요한 인과 이력 보유?"}
    E -->|예| F["로컬에서 순서 확정"]
    E -->|아니요| D

누락된 vertex를 가져오는 경로도 문제입니다. 참조만 있고 커밋에 필요한 본체가 없으면 노드는 자료를 따로 요청해야 합니다. 인증 DAG는 동기화를 크리티컬 경로 밖에서 처리할 여지가 있지만, 필요한 인과 이력을 제때 얻지 못하면 커밋이 늦어집니다.

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

Shoal++는 더 빠른 앵커 커밋, 동적으로 늘리는 앵커, 서로 엇갈려 진행하는 여러 DAG로 세 지연 구간을 줄입니다. 논문은 Bullshark 대비 일반 케이스 지연을 최대 60% 줄였고, 장애 케이스에서는 Mysticeti 대비 최대 10배 줄였다고 보고합니다. 이 수치는 같은 논문의 테스트베드 안에서 해석해야 합니다.

Angelfish(arXiv 2509.15847, 2025)는 구조 자체를 부하에 맞춰 바꿉니다. 부하가 낮으면 최선 노력 브로드캐스트(best-effort broadcast) 기반의 가벼운 투표로 지연을 낮춥니다.

부하가 높아지면 full DAG vertex 방송으로 전환해 처리량을 끌어올립니다. 리더 기반과 DAG 기반 사이를 부하에 따라 오가는 설계입니다.

무엇을 언제 고르는가

첫 갈림길은 신뢰 경계입니다. 노드를 전부 직접 운영하고 악의적 행위보다 정지 장애만 방어하면 되는 환경에서는 CFT가 요구를 충족할 수 있습니다. 운영 주체가 서로 다르거나 노드의 임의 행위까지 견뎌야 한다면 BFT가 필요합니다.

BFT가 필요하다면 다음 질문은 부하 구간과 데이터 전파 방식입니다. 낮거나 중간 부하에서는 리더 기반 설계가 더 적은 메시지 지연으로 커밋할 수 있습니다. 높은 부하에서 리더 중심 데이터 전파가 포화되면 DAG나 별도 분산 가용성 계층이 처리량을 넓힐 수 있습니다.

DAG 기반 BFT를 검토할 때는 목표 TPS를 논문 수치 하나로 정하지 말아야 합니다. 트랜잭션 크기, 검증자 수, 지역 간 RTT, 패킷 손실이 평가와 비슷한지 확인해야 합니다. 대역폭이 고르지 않거나 자료 누락이 잦으면 병렬 전파의 이점이 줄어듭니다.

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

정리

BFT를 쓸지는 신뢰 경계가 결정하고, BFT 내부의 선택은 부하와 전파 구조가 가릅니다. 리더 중심 전파는 낮은 지연에 유리하지만 리더 대역폭이 포화될 수 있습니다. DAG는 모든 검증자의 전파 대역폭을 쓰는 대신 큐잉과 앵커 커밋 지연을 더합니다.

서로 다른 환경에서 측정한 Raft와 DAG-BFT 수치만으로 두 계열의 우열을 정할 수 없습니다. 2f+1개를 확보할 수 있으면 느린 노드 하나는 건너뛰며, 정족수나 필요한 인과 이력이 부족할 때 라운드가 늦어집니다. 같은 장애 모델과 네트워크에서 부하 곡선을 측정한 뒤 리더 기반, DAG 기반, 하이브리드 방식을 골라야 합니다.