GitHub - consensus-study/HotStuff-study: this is HotStuff Study Repositry

본 글은 2019년 PODC에 발표된 "HotStuff: BFT Consensus with Linearity and Responsiveness" 논문을 심층 분석한 글입니다. PBFT를 이미 알고 있다는 전제 하에 작성되었습니다.

들어가며

분산 시스템을 공부하다 보면 반드시 마주치는 것이 비잔틴 장애 허용(BFT) 합의 프로토콜이다. 1999년 Castro와 Liskov가 발표한 PBFT는 20년이 넘는 시간 동안 BFT 합의의 표준으로 자리잡았다. 실용적이었고, 증명이 탄탄했으며, 실제로 동작했다.

그런데 블록체인 시대가 오면서 문제가 생겼다. PBFT는 노드 수가 늘어날수록 통신량이 제곱으로 증가한다. 노드가 100개만 되어도 한 번의 합의에 수만 개의 메시지가 오간다. 더 큰 문제는 리더가 장애를 일으킬 때다. View-Change 과정에서 통신량이 폭발적으로 증가하여, 최악의 경우 O(n^3)에 달한다.

HotStuff는 이 문제를 정면으로 해결한다. 저자들은 논문에서 다음과 같이 주장한다:

"HotStuff는 부분 동기 모델에서 선형 통신 복잡도와 낙관적 응답성을 동시에 달성하는 최초의 BFT 프로토콜이다."

과연 어떻게 이것이 가능한지, 논문을 하나하나 뜯어보자.

1. 문제 정의: PBFT는 왜 느린가

1.1 PBFT의 통신 구조

PBFT의 정상 동작을 떠올려보자. 클라이언트 요청이 들어오면:

Primary가 PRE-PREPARE를 모든 Replica에게 전송 (n-1개)
모든 노드가 PREPARE를 모든 다른 노드에게 전송 (n(n-1)개)
모든 노드가 COMMIT을 모든 다른 노드에게 전송 (n(n-1)개)

여기서 2번과 3번이 문제다. All-to-All 통신이 두 번 발생한다. 노드가 4개일 때는 12+12=24개로 감당할 만하지만, 100개가 되면 9,900+9,900=19,800개의 메시지가 필요하다.

1.2 View-Change의 재앙

정상 동작도 문제지만, 진짜 재앙은 View-Change에서 일어난다. PBFT에서 리더가 장애를 일으키면:

각 Replica가 자신의 상태를 담은 VIEW-CHANGE 메시지를 새 Primary에게 전송
새 Primary가 수집한 VIEW-CHANGE들을 모아 NEW-VIEW를 모든 노드에게 전송

문제는 VIEW-CHANGE 메시지의 크기다. 이 메시지에는 해당 Replica가 prepared 상태인 모든 요청에 대한 증명이 포함되어야 한다. 각 증명은 2f+1개의 서명을 포함하므로 O(n) 크기다. 이런 메시지를 n개 모아서 다시 n개 노드에게 보내면? O(n^2) 통신량이다.

연속으로 f개의 리더가 장애를 일으키면 O(n^3)까지 치솟는다. 노드 100개, 연속 장애 33번이면 약 1억 개의 메시지다. 현실적으로 시스템이 멈춘다.

1.3 왜 이렇게 설계되었나

PBFT가 이렇게 설계된 데는 이유가 있다. 새 Primary가 "안전한 값"을 제안하려면, 이전 view에서 무엇이 committed 또는 prepared 되었는지 알아야 한다. 이를 위해 2f+1개 노드의 상태를 모두 확인해야 하고, 다른 노드들도 이를 검증할 수 있어야 한다. 그래서 전체 상태를 담은 큰 메시지를 주고받는 것이다.

HotStuff의 핵심 통찰은 여기서 출발한다: 상태 전체를 보내지 않고도 안전성을 보장할 수 있는 방법이 있을까?

2. HotStuff의 핵심 아이디어

2.1 Quorum Certificate (QC)

HotStuff의 첫 번째 혁신은 QC(Quorum Certificate)다. PBFT에서 "2f+1개의 동의"를 증명하려면 2f+1개의 개별 서명을 모두 포함해야 했다. 메시지 크기가 O(n)이 될 수밖에 없다.

HotStuff는 Threshold Signature를 사용한다. 2f+1개의 부분 서명(partial signature)을 하나의 집계 서명으로 합칠 수 있다. 결과물인 QC의 크기는 O(1)이다. 서명이 100개든 1000개든, 최종 QC 크기는 동일하다.

이것만으로도 큰 변화다. View-Change 시 각 노드가 보내는 메시지에 자신의 최고 QC만 포함하면 된다. 메시지 크기가 O(n)에서 O(1)로 줄어든다.

2.2 Star Topology

두 번째 혁신은 통신 패턴의 변경이다. PBFT는 All-to-All 통신을 사용한다. 모든 노드가 PREPARE와 COMMIT을 서로에게 보낸다. 이것이 O(n^2)의 근본 원인이다.

HotStuff는 Star Topology를 사용한다. 모든 통신이 리더를 중심으로 이루어진다:

리더 -> 모든 Replica: 제안 전송 (n-1개)
모든 Replica -> 리더: 투표 전송 (n-1개)

Replica 간의 직접 통신이 없다. 한 라운드에 2(n-1)개의 메시지만 필요하다. O(n^2)가 O(n)이 되었다.

2.3 Three-Chain Commit Rule

그런데 여기서 의문이 생긴다. PBFT에서 All-to-All 통신을 한 이유가 있다. 모든 노드가 "2f+1개가 동의했다"는 사실을 직접 확인해야 하기 때문이다. Star Topology에서는 리더만 이 정보를 안다. 다른 노드들은 어떻게 확인하는가?

HotStuff의 답은 "추가 phase"다. PBFT가 2 phase(PREPARE, COMMIT)인 반면, HotStuff는 3 phase(PREPARE, PRE-COMMIT, COMMIT)를 사용한다.

각 phase에서 리더는 이전 phase의 QC를 모든 노드에게 전파한다. 노드들은 QC를 보고 "아, 2f+1개가 동의했구나"를 확인한다. All-to-All 대신 리더가 정보를 중계하는 것이다.

세 번의 연속된 QC가 형성되면(이것이 Three-Chain이다) 블록이 commit된다:

B1 <-- B2 <-- B3
|      |      |
QC1   QC2    QC3

QC3가 형성되면 B1이 commit된다.

왜 세 번인가? 각 QC의 역할을 보자:

QC1 (PREPARE): "2f+1이 B1을 보았다"
QC2 (PRE-COMMIT): "2f+1이 QC1을 보았다" -> 이 시점에 Lock
QC3 (COMMIT): "2f+1이 QC2를 보았다" -> 이 시점에 Commit

Lock이 중요하다. QC2를 본 노드는 B1에 "잠긴다". 이후 B1과 충돌하는 블록에는 투표하지 않는다. 2f+1개 노드가 잠기면, 충돌 블록이 QC를 얻을 수 없다. 안전성이 보장된다.

3. 프로토콜 상세 분석

3.1 데이터 구조

HotStuff는 블록체인 구조를 사용한다. 각 블록은 다음을 포함한다:

Block = {
    parent:  이전 블록의 해시,
    payload: 트랜잭션 데이터,
    height:  체인에서의 높이,
    justify: 부모 블록의 QC
}

justify 필드가 핵심이다. 블록을 제안할 때 부모 블록의 QC를 포함시킨다. 이것이 "이 블록이 유효한 체인 위에 있다"는 증거다.

3.2 투표 규칙: safeNode

Replica가 블록에 투표할지 결정하는 규칙이다. 논문에서는 safeNode라 부른다:

safeNode(block, qc) = 
    (qc.view > lockedQC.view) OR (block extends lockedQC.block)

두 조건 중 하나만 만족하면 투표한다:

제안에 포함된 QC의 view가 내가 잠긴 QC보다 높다
제안된 블록이 내가 잠긴 블록을 확장한다

첫 번째 조건은 "더 최신 정보가 있으면 그것을 따른다"는 의미다. 두 번째 조건은 "같은 체인을 따라가는 것은 안전하다"는 의미다.

이 규칙이 안전성과 활성성을 동시에 보장한다. 잠긴 값과 충돌하는 블록에는 투표하지 않으므로 안전하고, 더 높은 view의 QC가 오면 잠금을 해제할 수 있으므로 시스템이 멈추지 않는다.

3.3 Basic HotStuff 프로토콜

한 view에서의 동작을 단계별로 보자:

Phase 1: PREPARE

리더가 새 블록을 제안한다. 블록에는 자신이 아는 최고 QC가 포함된다.
Replica들은 safeNode 검사를 통과하면 투표(부분 서명)를 리더에게 보낸다.
리더가 2f+1개의 투표를 모으면 prepareQC를 생성한다.

Phase 2: PRE-COMMIT

리더가 prepareQC를 모든 노드에게 전송한다.
Replica들은 prepareQC를 받으면 해당 블록에 Lock한다. 그리고 투표를 보낸다.
리더가 2f+1개의 투표를 모으면 precommitQC를 생성한다.

Phase 3: COMMIT

리더가 precommitQC를 모든 노드에게 전송한다.
Replica들은 투표를 보낸다.
리더가 2f+1개의 투표를 모으면 commitQC를 생성한다.

Phase 4: DECIDE

리더가 commitQC를 모든 노드에게 전송한다.
모든 노드가 해당 블록을 commit하고 실행한다.

3.4 View-Change

리더가 장애를 일으키면 어떻게 되는가? HotStuff의 View-Change는 놀랍도록 단순하다:

타임아웃이 발생하면 각 노드가 자신의 highQC(가장 높은 QC)를 새 리더에게 전송한다.
새 리더는 2f+1개의 메시지를 수집하고, 그 중 가장 높은 QC를 선택한다.
새 리더는 이 QC를 확장하는 새 블록을 제안한다.

끝이다. PBFT처럼 복잡한 상태 동기화가 없다. QC 자체가 "2f+1이 동의했다"는 완전한 증거이기 때문이다. 가장 높은 QC를 선택하면, 그것이 가장 최신의 "합의된 상태"다.

메시지 복잡도는 O(n)이다. 각 노드가 O(1) 크기의 QC를 새 리더에게 보내고(n-1개), 새 리더가 제안을 broadcast한다(n-1개). 총 2(n-1)개의 O(1) 메시지.

4. 안전성과 활성성

4.1 안전성 증명 개요

논문의 핵심 정리는 다음과 같다:

Theorem (Safety): 두 정직한 노드가 같은 높이에서 서로 다른 블록을 commit하는 일은 없다.

증명의 핵심은 Lock 메커니즘이다. 블록 B가 commit되려면 B에 대한 precommitQC가 형성되어야 한다. 이 시점에 2f+1개 노드가 B에 Lock된다.

이제 B와 충돌하는 B'가 commit되려면, B'에 대한 prepareQC가 먼저 형성되어야 한다. 하지만 Lock된 노드들은 B'에 투표하지 않는다(safeNode 규칙). Lock된 노드가 2f+1개이고, 새 QC도 2f+1개 투표가 필요하므로, 교집합에 최소 1개의 정직한 노드가 있다. 이 노드가 B'에 투표하지 않으므로 B'는 QC를 얻을 수 없다.

4.2 활성성 증명 개요

Theorem (Liveness): GST 이후 정직한 리더가 있으면, 유한 시간 내에 새로운 블록이 commit된다.

증명의 핵심은 "가장 높은 QC를 가진 리더는 항상 진전을 만들 수 있다"는 것이다.

정직한 리더 L이 view v를 시작한다고 하자. L은 2f+1개 노드로부터 highQC를 수집한다. 이 중 가장 높은 것을 선택하여 그것을 확장하는 블록을 제안한다.

핵심 관찰: 이 QC는 어떤 정직한 노드의 lockedQC보다 높거나 같다. 따라서 모든 정직한 노드가 safeNode 검사를 통과하고 투표할 수 있다.

GST 이후이므로 메시지가 제때 도착한다. 2f+1개 투표가 모이고 QC가 형성된다. 세 번 연속 성공하면 commit이다.

4.3 Liveness Attack과 3-Phase의 필요성

논문에서 흥미로운 부분은 "왜 2-phase로는 안 되는가"에 대한 설명이다.

2-phase를 시도해보자. PREPARE에서 QC를 얻으면 바로 commit한다고 가정하자.

시나리오:

View v에서 리더가 블록 B를 제안한다.
일부 노드만 prepareQC를 받고 B에 Lock한다. 리더가 crash.
View v+1에서 새 리더가 다른 블록 B'를 제안한다.

문제: B에 Lock된 노드는 어떻게 해야 하는가?

B가 commit되었을 수도 있다(다른 노드들이 commitQC까지 받았을 수도)
B가 commit되지 않았을 수도 있다(리더가 prepareQC 전파 중 crash)

Lock된 노드는 이를 구분할 수 없다. B'에 투표하면 safety 위반 가능성, 투표하지 않으면 liveness 위반 가능성. 이것이 "Livelessness Attack"이다.

3-phase는 이 문제를 해결한다. PRE-COMMIT phase에서 prepareQC가 전파되고, 이것을 본 노드만 Lock한다. COMMIT phase에서 precommitQC가 전파되어야 commit이다.

이렇게 하면:

precommitQC가 형성되면: 2f+1이 Lock되었음이 보장. 새 리더가 이들 중 한 명이라도 만나면 이 사실을 알 수 있음.
precommitQC가 형성되지 않으면: 아무도 Lock되지 않음. 새 리더가 다른 블록을 제안해도 안전.

Lock과 non-Lock 상태가 명확히 구분된다. 이것이 3-phase가 필요한 이유다.

5. Chained HotStuff: 파이프라이닝

5.1 기본 아이디어

Basic HotStuff는 한 블록을 commit하는 데 4번의 round-trip이 필요하다. 논문은 이를 개선하는 Chained HotStuff를 제안한다.

핵심 관찰: 각 phase에서 하는 일이 사실상 같다. 리더가 메시지를 보내고, Replica가 투표하고, QC가 형성된다. 다른 것은 QC의 "의미"뿐이다.

Chained HotStuff는 이를 파이프라이닝한다. 각 view에서:

새 블록을 제안한다 (PREPARE)
이전 블록이 PRE-COMMIT된다 (prepareQC 형성)
그 이전 블록이 COMMIT된다 (precommitQC 형성)
그 이전 블록이 DECIDE된다 (commitQC 형성)

View 1: B1 제안
View 2: B2 제안, B1 pre-commit
View 3: B3 제안, B2 pre-commit, B1 commit
View 4: B4 제안, B3 pre-commit, B2 commit, B1 decide

5.2 Three-Chain Commit Rule

Chained HotStuff의 commit 규칙은 간단하다:

Three-Chain: 블록 B가 commit되려면, B를 확장하는 연속 세 블록(B, B', B'')이 있고 각각 QC를 가져야 한다. 그리고 이 세 블록이 연속된 view에서 생성되어야 한다.

B (view v) <-- B' (view v+1) <-- B'' (view v+2)
|              |                 |
QC            QC'               QC''

QC''가 형성되면 B가 commit된다.

연속 view 조건이 중요하다. 중간에 view가 건너뛰어지면 Three-Chain이 깨진다. 이는 리더 장애가 있었다는 의미이고, Lock 상태가 불확실할 수 있다.

5.3 성능 향상

Basic HotStuff: 블록당 7 message delay (3 phase + decide) Chained HotStuff: 블록당 2 message delay (steady state)

처리량이 약 3.5배 향상된다. 첫 블록은 여전히 7 delay가 필요하지만, 이후 블록들은 파이프라인을 타고 2 delay마다 commit된다.

6. PBFT와의 비교

6.1 통신 복잡도

항목	PBFT	HotStuff
Normal-case	O(n^2)	O(n)
View-change	O(n^2) ~ O(n^3)	O(n)
f consecutive failures	O(n^3)	O(n^2)

100개 노드에서:

PBFT normal-case: ~20,000 메시지
HotStuff normal-case: ~700 메시지

차이가 30배에 달한다. 노드가 많아질수록 격차는 더 벌어진다.

6.2 지연 시간

항목	PBFT	HotStuff (Basic)	HotStuff (Chained)
Single commit	5 delay	7 delay	7 delay (first)
Steady-state	5 delay	7 delay	2 delay

단일 합의만 보면 PBFT가 더 빠르다. 하지만 Chained HotStuff의 파이프라이닝을 적용하면 처리량은 HotStuff가 앞선다.

6.3 설계 철학의 차이

PBFT는 "모든 노드가 모든 것을 안다"는 철학이다. 각 노드가 독립적으로 합의 상태를 판단할 수 있다. 대신 통신량이 많다.

HotStuff는 "리더가 중재한다"는 철학이다. 정보가 리더를 통해 흐른다. 통신량은 적지만, 리더 의존도가 높다.

두 접근 모두 장단점이 있다. 소규모 네트워크에서는 PBFT의 단순함이 유리할 수 있다. 대규모 네트워크, 특히 블록체인처럼 노드가 많고 리더 교체가 빈번한 환경에서는 HotStuff가 유리하다.

7. 실제 적용과 영향

7.1 Libra/Diem

HotStuff의 가장 유명한 적용 사례는 Facebook(현 Meta)의 Libra 프로젝트다. 2019년 발표된 Libra 백서는 HotStuff를 합의 프로토콜로 채택했다.

LibraBFT는 HotStuff를 기반으로 몇 가지 실용적 개선을 추가했다:

더 정교한 Pacemaker (리더 선출 및 타임아웃 관리)
메모리풀 통합
상태 동기화 프로토콜

프로젝트는 규제 문제로 Diem으로 이름이 바뀌고 결국 중단되었지만, HotStuff가 산업계에서 검증받은 계기가 되었다.

7.2 후속 연구

HotStuff 이후 수많은 변형이 등장했다:

Fast-HotStuff: Optimistic path에서 latency 개선
Jolteon/Ditto: 비동기 fallback 추가
HotStuff-2: 3-phase를 2-phase로 줄임 (2023년)

특히 HotStuff-2는 주목할 만하다. 같은 저자(Malkhi)가 참여하여 "이전 view의 QC가 있으면 추가 phase가 필요 없다"는 통찰을 제시했다. 결국 2-phase로도 선형 통신과 응답성을 동시에 달성할 수 있음이 밝혀졌다.

7.3 블록체인에 미친 영향

HotStuff는 BFT 기반 블록체인의 설계 패턴을 바꾸었다. 이전에는 PBFT 변형을 사용하거나, Tendermint처럼 응답성을 포기해야 했다. HotStuff는 둘 다 가능함을 보여주었다.

현재 많은 블록체인 프로젝트가 HotStuff 또는 그 변형을 사용한다:

Flow
Cypherium
Thunder
다수의 프라이빗 블록체인

8. 비판적 검토

8.1 장점

확장성: O(n) 통신은 대규모 네트워크에 필수적이다.
단순성: 프로토콜 로직이 명확하다. 투표 규칙(safeNode)이 하나뿐이다.
모듈성: Pacemaker가 분리되어 있어 다양한 리더 선출 방식을 적용할 수 있다.
파이프라이닝: Chained 버전으로 처리량을 높일 수 있다.

8.2 한계

추가 Phase: PBFT보다 한 phase가 더 필요하다. 단일 합의 지연이 증가한다.
리더 의존성: Star topology로 인해 리더 부하가 크다. 리더가 병목이 될 수 있다.
Threshold Signature 의존: 실제 구현에서 threshold signature의 오버헤드가 있다.
Pacemaker 복잡성: 논문에서 Pacemaker를 "분리"했다고 하지만, 실제로는 Pacemaker 설계가 복잡하고 중요하다.

8.3 열린 문제

논문 발표 이후에도 여러 문제가 연구되고 있다:

최적의 Pacemaker 설계
비동기 환경에서의 성능
Threshold signature 없이 선형 통신 달성
2-phase로의 추가 최적화 (HotStuff-2가 일부 해결)

마치며

HotStuff는 BFT 합의 연구에서 하나의 전환점이다. 20년간 표준이었던 PBFT의 한계를 극복하고, 선형 통신과 응답성을 동시에 달성했다.

논문을 읽으면서 가장 인상적인 것은 핵심 아이디어의 단순함이다. QC를 통해 증명 크기를 상수로 만들고, Star topology로 통신을 선형으로 만들고, 추가 phase로 정보 비대칭을 해결한다. 각각은 어렵지 않은 아이디어지만, 이를 조합하여 오래된 문제를 해결한 것이 논문의 가치다.

물론 HotStuff가 완벽한 것은 아니다. 추가 phase로 인한 지연, 리더 의존성, Pacemaker의 복잡성 등 여전히 개선의 여지가 있다. 후속 연구들이 이를 하나씩 해결해가고 있다.

분산 합의를 공부하는 사람이라면 HotStuff는 반드시 읽어야 할 논문이다. PBFT를 알고 있다면 몇 시간이면 핵심을 파악할 수 있다. 블록체인 시대의 BFT 합의가 어디로 가고 있는지 이해하는 좋은 출발점이 될 것이다.

참고 자료

Yin, M., Malkhi, D., Reiter, M. K., Gueta, G. G., & Abraham, I. (2019). HotStuff: BFT Consensus with Linearity and Responsiveness. PODC 2019.
Castro, M., & Liskov, B. (1999). Practical Byzantine Fault Tolerance. OSDI 1999.
Malkhi, D., & Nayak, K. (2023). HotStuff-2: Optimal Two-Phase Responsive BFT.
libhotstuff GitHub: https://github.com/hot-stuff/libhotstuff

Name		Name	Last commit message	Last commit date
Latest commit History 2 Commits
Readme.md		Readme.md

consensus-study/HotStuff-study

Folders and files

Latest commit

History

Repository files navigation