Blockchain: HotStuff, BFT

PBFT는 오랫동안 BFT의 교과서였다. 그런데 왜 Diem, Aptos, Monad 같은 최근 체인들은 PBFT가 아닌 HotStuff를 가져다 쓰고 있을까.

분산 합의는 노드 일부가 거짓말을 해도 정직한 노드들끼리 같은 결정을 내리도록 하는 문제다. 비잔틴 장군 문제부터 Raft까지의 큰 그림은 합의 알고리즘과 Raft 글에서 다뤘다.

BFT와 PBFT

비잔틴 장애 허용(Byzantine Fault Tolerance, BFT)은 합의를 “악의적인 노드가 섞여 있어도” 보장하는 강한 형태다. 수학적으로는 전체 n명 중 비잔틴 노드가 f명일 때 n ≥ 3f + 1이면 안전하게 합의할 수 있다. 즉 검증자의 1/3 미만이 거짓말을 해도 시스템은 진실에 도달한다.

PBFT(Practical Byzantine Fault Tolerance)는 이를 처음 실용적인 구현으로 만든 알고리즘이다. 한 라운드 안에서 pre-prepare → prepare → commit 세 단계를 거치고, 각 단계마다 모든 노드가 모든 노드와 메시지를 주고받기 때문에 통신 비용은 O(n²)다. 리더가 죽어 view change가 일어나면 O(n³)까지 치솟는다.

블록체인이 다시 끄집어낸 문제

PBFT 이후로 BFT는 “이론적으로는 가능한데 실전에는 부담스러운” 영역에 머물렀다. 노드 수가 적은 시스템에서는 O(n²)이 큰 문제가 아니었기 때문이다.

블록체인은 이 비용을 다시 끄집어냈다. 검증자가 100명을 넘기는 PoS 체인에서 PBFT를 그대로 쓰면 한 라운드에 1만 건 가까운 인증 메시지가 오간다. n = 100이면 n² = 10,000, view change가 일어나는 순간 n³ = 1,000,000이다.

HotStuff의 해결

HotStuff가 이 비용을 정직하게 깎아낸 첫 BFT 프로토콜이다. 핵심 트릭은 n - f = 2f + 1 개 서명을 임계 서명(threshold signature)으로 묶어 QC(Quorum Certificate)라는 단일 객체로 압축하는 것이다.

각 노드는 자기 vote를 리더에게만 보내고, 리더가 정족수 2f+1 개를 모아 QC 하나를 만들면 그 QC가 “정족수가 동의했다”는 사실을 단일 메시지로 증명한다. 한 라운드의 통신이 O(n²)개 인증 메시지에서 O(n)개로 줄어들고, view change도 같은 O(n)에 처리된다. 그 대가로 단계 하나를 더 추가했다.

Diem(전 Libra)이 LibraBFT라는 이름으로 채택했고, Aptos, Monad, Sui 같은 고성능 L1들이 모두 HotStuff 계열을 변형해 쓴다.

이 글에서는 HotStuff가 어떻게 동작하는지, 왜 3-phase가 되었는지, 그리고 후속작 HotStuff-2가 다시 2-phase로 돌아간 이유까지 살펴본다.

BFT 합의 비용 모델

부분 동기(partial synchrony) 모델 위에서 BFT 합의는 두 가지 경로를 가진다. 하나는 정상 흐름(normal case)이고, 다른 하나는 리더가 의심받을 때 새 리더로 넘기는 view change다. 두 경로 모두에서 통신 복잡도가 프로토콜의 운명을 가른다.

프로토콜	정상 흐름 통신	view change 통신	단계 수	Responsive
PBFT	O(n²)	O(n³)	3	Yes
Tendermint	O(n²)	O(n²)	3	No
HotStuff	O(n)	O(n)	3	Yes
HotStuff-2	O(n) optimistic / O(n²) worst	O(n²) worst	2	Yes

PBFT의 view change가 O(n³)인 이유는 단순하다. 새 리더가 모든 노드의 “내가 마지막으로 본 prepared 값” 증거를 다 모아 다시 모두에게 broadcast해야 하는데, 그 증거 자체가 O(n²) 크기를 가지기 때문이다.

Tendermint는 round-robin으로 리더를 매번 돌려 view change 비용을 줄였지만, 대신 non-responsiveness라는 대가를 치렀다. 리더는 매 라운드 일정 시간을 기다려야 안전하게 다음 단계로 갈 수 있다. 네트워크가 빠르든 느리든 그 대기 시간만큼은 항상 깎인다.

Responsive하다는 건 “정직한 리더가 결정되면 합의가 실제 네트워크 지연 속도로 진행된다”는 의미다. 최악의 가정 시간 Δ를 기다리는 게 아니라, 가장 빠른 2f+1 응답이 도착하는 즉시 다음 단계로 넘어간다는 뜻이다.

HotStuff는 통신 비용과 responsiveness를 동시에 노렸다. 통신을 선형으로 줄이면서, responsiveness도 잃지 않는 것. 그러려면 단계를 하나 더 늘려야 했다.

Basic HotStuff

HotStuff의 한 view는 네 메시지로 나뉜다. prepare, pre-commit, commit, decide 네 라운드가 한 묶음이다.

sequenceDiagram
    participant L as Leader
    participant R as Replicas (n-f)

    Note over L,R: View v 시작
    L->>R: prepare(block, highQC)
    R->>L: prepare-vote
    Note over L: prepareQC 형성
    L->>R: pre-commit(prepareQC)
    R->>L: pre-commit-vote
    Note over L,R: 여기서 lock 갱신
    L->>R: commit(precommitQC)
    R->>L: commit-vote
    L->>R: decide(commitQC)
    Note over R: 블록 실행 + 확정

각 단계가 무슨 일을 하는지 풀어보자.

prepare 단계

리더가 새 블록을 제안한다. 이때 자기가 본 가장 높은 QC(highQC)를 함께 첨부한다. QC(Quorum Certificate)는 n - f = 2f + 1 개 서명을 임계 서명(threshold signature)으로 묶은 단일 객체다.

레플리카는 SafeNode rule로 투표 여부를 결정한다.

제안된 블록이 자기가 잠근(lockedQC) 블록을 확장하거나
제안의 highQC.view가 자기 lockedQC.view보다 크면

투표한다. 첫 번째 조건이 안전성(safety)을 지키고, 두 번째 조건이 활성성(liveness)을 푼다.

pre-commit 단계

리더가 2f+1 개 prepare-vote를 모아 prepareQC로 압축한다. 이걸 다시 broadcast하면 레플리카는 “이 블록을 정족수가 한 번 인정했다”는 사실을 확인하고 다시 투표한다.

commit 단계 (lock)

핵심 단계다. 리더가 precommitQC를 broadcast하면, 레플리카는 자기 lockedQC를 이 새 QC로 갱신한다. 이 시점부터 이 레플리카는 더 낮은 view의 블록에는 절대 투표하지 않는다.

lock은 PBFT의 prepared certificate와 비슷한 역할이지만 한 가지 다른 점이 있다. PBFT는 lock을 풀려면 모든 노드의 “내 lock은 이거야” 증거를 다 모아야 하는데, HotStuff는 그냥 더 높은 view의 QC 하나만 보면 된다. 이게 view change의 O(n)을 가능하게 만든 핵심 트릭이다.

decide 단계

마지막으로 리더가 commitQC를 broadcast한다. 레플리카는 이 시점에 블록을 실행하고 클라이언트에게 응답한다. 합의는 여기서 종료된다.

hidden lock 문제

“PBFT도 3단계인데 왜 HotStuff는 또 다른 3단계가 필요했나”라는 질문이 자연스럽다.

답은 partial synchrony에서 발생하는 hidden lock 문제 때문이다.

리더가 죽고 새 리더가 들어왔다고 하자. 새 리더는 안전하게 “현재 잠긴 가장 높은 QC”를 고르려 한다. 그런데 정직한 노드 일부가 lock을 가졌더라도, 새 리더가 그 사실을 알 수 있는 보장이 없다.

PBFT는 이 문제를 view change 메시지로 푼다. 모든 노드가 자기 상태를 새 리더에게 보내는 거대한 증거 묶음이다. 비용은 O(n²)다.

HotStuff는 다른 길을 택했다. lock을 만들기 전에 한 단계 더 둬서, lock이 형성되는 순간 정족수가 그 사실을 이미 안다는 invariant를 만들었다.

prepare → pre-commit: “정족수가 이 블록을 봤다”는 상태(prepareQC)
pre-commit → commit: “정족수가 정족수의 인지 사실을 안다”는 상태(lock 형성)
commit → decide: “정족수가 lock 형성 사실을 안다”는 상태(확정)

이 세 단계 invariant 덕분에, view change 시 새 리더는 그냥 자기가 본 가장 높은 QC를 들고 다음 라운드를 시작하면 된다. 정직한 노드 하나라도 그보다 높은 lock을 가졌다는 사실 자체가 모순이기 때문이다.

이 통찰을 한 줄로 줄이면 이렇다. “lock 형성 직전에 한 단계를 더 두면, lock의 존재 자체가 정족수에게 알려진다. 그러면 view change에서 그 사실을 따로 모을 필요가 없다.”

Chained HotStuff

지금까지 본 게 Basic HotStuff다. 한 블록을 합의하는 데 4번의 메시지 라운드가 필요하다. 솔직히 너무 길다.

여기서 파이프라이닝이 등장한다. 각 단계의 메시지 형태가 모두 동일하다는 점에 주목하면, 한 view의 prepareQC가 동시에 다른 view의 precommitQC, 또 다른 view의 commitQC 역할을 할 수 있다.

graph LR
    B1["블록 v=1<br/>(자체 prepare)"] -->|QC| B2["블록 v=2<br/>(B1 pre-commit)"]
    B2 -->|QC| B3["블록 v=3<br/>(B1 commit, B2 pre-commit)"]
    B3 -->|QC| B4["블록 v=4<br/>(B1 decide, B2 commit)"]
    B4 -->|QC| B5["블록 v=5<br/>..."]

블록이 하나 추가될 때마다 파이프라인의 모든 단계가 한 칸씩 전진한다.

B1의 QC가 B2 헤더에 박힘 → B1 prepare 확정
B2의 QC가 B3에 박힘 → B1 pre-commit, B2 prepare 동시 확정
B3의 QC가 B4에 박힘 → B1 commit (lock), B2 pre-commit, B3 prepare
B4의 QC가 B5에 박힘 → B1 decide(execute), B2 commit, B3 pre-commit, B4 prepare

이를 3-chain 규칙이라 한다. 어떤 블록 B가 자기를 직간접적으로 확장하는 후속 블록 3개(B → B' → B'' → B''')를 가지면, B는 commit된다.

이 구조 덕분에 매 라운드마다 새 블록이 하나씩 확정된다. 라운드당 메시지는 여전히 O(n)이고, 처리량은 단순 Basic HotStuff의 4배가 된다.

Chained HotStuff는 사실상 모든 production 구현이 채택한 형태다. Diem의 LibraBFT, Aptos의 AptosBFT, Monad의 MonadBFT가 모두 이 chained 변형을 베이스로 한다.

HotStuff-2

HotStuff-2는 의외의 결론을 내놓았다. “사실 두 단계면 충분하다.”

핵심 아이디어는 leader handover rule의 정교화다. 새 리더가 전임자의 lock을 어떻게 안전하게 이어받는지 다시 정의했다.

원래 HotStuff의 3단계는 hidden lock을 막기 위한 안전망이었다. HotStuff-2는 view change 시 새 리더가 추가 라운드 한 번을 통해 정족수의 lock 상태를 명시적으로 수집하게 한다. 정상 흐름에서는 2단계, 리더 교체 시에만 추가 라운드가 발생하는 구조다.

항목	HotStuff	HotStuff-2
정상 흐름 단계	3	2
정상 흐름 통신	O(n)	O(n)
view change 통신	O(n) 균일	O(n) 낙관적, O(n²) 최악
Responsiveness	보장	보장
Tail-forking 저항	약함	강함 (HotStuff-1, Carry 등 후속)

HotStuff-2의 트레이드오프는 분명하다. 정상 흐름은 더 빨라졌지만, 최악의 경우 view change 비용이 다시 O(n²)로 올라간다. 다만 부분 동기 모델에서 view change는 GST 이후에는 거의 발생하지 않으므로 실전 영향은 작다는 게 저자의 주장이다.

후속으로 등장한 HotStuff-1은 client에게 더 이른 confirmation을 제공하고 tail-forking과 leader-slowness(MEV) 영향을 줄였다. Carry-the-Tail 같은 변형이 chained 패밀리에 적용되며 leader-induced stall을 더 줄이는 방향으로 진화하고 있다.

실제 채택 사례

HotStuff 패밀리가 실전에서 어떻게 변형되어 쓰이는지 짚어본다.

LibraBFT / DiemBFT

Libra(현 Diem) 프로젝트가 가장 먼저 production에 가져다 썼다. Chained HotStuff를 거의 그대로 따르되, BLS aggregate signature로 QC를 압축하고 view 동기화를 위한 별도의 Pacemaker 모듈을 분리했다.

AptosBFT

Aptos는 Diem 코드베이스를 포크해 발전시켰다. 두 가지 차별점이 있다.

VRF 기반 leader 선택 — round-robin 대신 검증자 평판과 VRF로 다음 리더를 선출한다. 특정 검증자가 반복적으로 죽거나 느린 경우 자동으로 회전에서 제외된다.
Quorum Store — 트랜잭션 데이터와 합의를 분리해 리더가 데이터 전파 병목이 되지 않도록 한다.

MonadBFT

Monad는 1초 finality를 목표로 HotStuff를 베이스에 두고 통신 단계를 더 압축했다. 흔한 장애 시나리오에서 빠른 회복을 위한 개선이 추가됐고, MONAD_NINE 업그레이드로 이어졌다.

Mysticeti (Sui)

Sui는 흥미롭게도 HotStuff 직계가 아니다. DAG 기반 Mysticeti를 쓴다. 다만 Mysticeti도 HotStuff에서 가져온 통찰(linear view change, threshold signature 압축)을 흡수했다. v2 업그레이드로 finality를 1초 미만으로 끌어내렸다.

Sui의 선택이 보여주는 지점이 있다. HotStuff 패밀리가 chain 구조의 BFT를 표준화한 동안, DAG 기반 합의는 한 라운드에 여러 리더가 동시에 블록을 만들 수 있게 해 처리량을 한 단계 더 끌어올린다. HotStuff와 DAG 합의는 경쟁이라기보다는 다른 트레이드오프 곡선 위에 있다.

정리

HotStuff가 한 일은 BFT 합의의 비용을 그래프에서 정직하게 깎아낸 작업이다.

PBFT가 표준이었던 동안 누구도 view change의 O(n³)을 진지하게 줄여보려 하지 않았다. 노드 수가 적은 시스템에서는 큰 문제가 아니었기 때문이다.

블록체인이 검증자 수백 명을 다루는 도메인을 만들어내자 그 비용을 더는 무시할 수 없게 됐고, HotStuff는 “lock 형성 전에 한 단계만 더 두면 view change가 거의 공짜가 된다”는 통찰로 그 매듭을 풀었다.

이후 HotStuff-2는 그 단계를 다시 줄였고, Aptos와 Monad는 leader 선택과 데이터 전파 병목을 손봤고, Sui는 아예 chain을 버리고 DAG로 갔다.

앞으로의 BFT 합의 연구는 chain과 DAG의 경계, 그리고 leader-handover의 안전성과 throughput 사이의 미세 조정에서 갈린다. HotStuff는 그 출발점에 있는 프로토콜이다.