(PODC '19) HotStuff-BFT Consensus with Linearity and Responsiveness

Motivation

PBFT: Scaling Challenge

기존 PBFT 시스템은 two-phase paradigm으로 구성되어 있다. 첫번째 phase는 $(n-f)$ 개의 quorum certificate(QC)를 수집하여 proposal uniqueness를 보장하는 것이다. 두번째는 레플리카들이 리더의 제안에 투표를 하는 단계이다.

Note

여기서 Two-phase 합의라고 하는 것은 우리가 일반적으로 알고있는 다음 그림과는 충돌되는 설명처럼보일 수 있다. 실제로 request, reply 단계는 합의 과정의 일부로 포함하지 않으며, 합의 과정은 pre-prepare, prepare, commit에 해당한다. 이를 two-phase라고 부르는 이유는 pre-prepare 과 prepare를 합쳐서 하나의 phase로 치기 때문이다. 많은 분산 합의 알고리즘을 분류할 때 vote가 몇번 일어나는가를 기준으로 phase의 수를 결정한다.

보다 구체적으로 첫 번째 단계에서 proposal의 uniqueness를 보장한다는 말의 의미는 해당 뷰에 proposal이 단 하나 존재한다는 사실을 검증한다는 뜻이다. 레플리카들은 pre-prepare 메시지를 받으면 prepare 메시지를 보내기 이전에 뷰 번호, pre-prepare 메시지의 integrity(서명을 통해), proposal의 유일성 등을 체크한다.

Two-phase 패러다임의 문제는 view change의 communication cost가 $O(n^3)$으로 너무 크다는 것이다. View change는 다음 과정을 포함한다.

1. 새로운 리더는 $(n-f)$개 레플리카들로부터 각자가 가지고 있는 highest QC(즉, 가장 최근에 합의된 블록에 대한 QC)를 수집해야 한다.
2. 그 후 리더가 새로운 proposal을 전달할 때 자신이 수집한 모든 QC를 전송해야 한다. 하나의 QC가 $O(n)$개의 서명으로 이루어져 있고, 이를 $O(n)$개 레플리카로부터 수집해야 하며, 이후 $O(n)$개 레플리카들에게 수집한 정보를 모두 보내야 한다는 점을 고려해 보면, 리더는 새로운 제안을 위해서 총 $O(n^3)$ 개의 서명을 전송해야 하는 것이다! Threshold signature 등의 기술을 사용하면 $O(n^2)$개로 줄일수는 있겠지만 여전히 많다.

Tendermint, Casper: Lack of Optimistic Responsiveness

Tendermint나 Casper같은 알고리즘이 블록체인에서 많이 사용되고 있지만, 이는 synchronous network model을 가정하고 있기 때문에 optimistic responsiveness를 보장하지 못한다. 우선 두 알고리즘은 동기적 환경(메시지가 어떤 상한 $\Delta$ 내에 모두 도착하는 환경)을 가정하기 때문에 한 슬롯에 소모되는 시간이 정해져 있다. 예를 들어 이더리움은 12초이다. 어떤 비콘 블록도 12초보다 더 빨리 만들어질 수 없고, 더 늦게 만들어질 수도 없다. 설령 리더가 12초 이전에 모든 레플리카로부터 vote를 받았다고 하더라도 해당 비콘 블록이 12초 이전에 만들어질 수는 없다. 그렇다면 일부 실행에서 시스템에 정해진 최대지연상한 $\Delta$ 보다 빠르게 commit할 수는 없을까? Optimistic responsiveness를 허용하는 시스템이라면 가능하다. Responsiveness는 BFT SMR 시스템의 성질 중 하나로, 정직한 리더가 합의에 성공하는 데에 걸리는 시간이 오직 실제 메시지 딜레이에만 의존하는 성질이다. 즉 실제 메시지 딜레이가 짧으면 그만큼 빠르게 합의에 도달한다. Optimistic responsiveness는 이러한 responsiveness를 오직 이득이 있는 상황에만 제공하는 것을 말한다. 이득이 있는 상황이 언제인지를 판단하는 것도 중요한 문제이지만, 본 논문의 목적은 아니다. 본 논문에서는 GST(Global Stabilization Time) 이후, 즉 모든 레플리카가 동기화된 시점 이후로 가정하였다.

Note

• Δ는 네트워크가 동기적 상태일 때, 메시지가 전달될 최대 시간을 의미한다. 특히 동기 모델에서 상수로 결정되어 있으며, Δ 시간 내에 모든 메시지가 도착할 것이 가정된다.
• **GST(Gobal Stabilization Time)**는 네트워크가 비동기적 상태에서 동기적 상태로 전환되는 시점을 의미한다. 부분 동기 모델에서 주로 사용되며, GST 이전에는 메시지 전달 시간에 대한 보장이 없고(비동기적이고), GST 이후에야 동기적으로 작동한다고 가정된다. GST 이후에는 동기 모델과 동일하게 Δ 시간 내에 모든 메시지가 도착한다고 가정된다.

Contribution

Linear View change

GST 이후, 리더는 $O(n)$ 개의 서명(앞으로 이것을 authenticator라고 부르자)을 통해 합의를 달성한다. 이는 리더가 바뀌는 경우도 포함한다. 따라서 리더가 계속해서 변경되는 최악의 경우에도 총 $O(n^2)$개의 서명만 필요하다.

Optimistic Responsiveness

GST 이후, 리더는 첫 $n-f$ 개의 응답(QC)만을 기다리면 해당 합의를 완료할 수 있다(새로운 제안을 만들고 계속 합의를 진행할 수 있다). 이 역시 리더가 교체되었을 때를 포함한다.

Hotstuff는 새로운 리더가 합의를 진행하는 것이 현재 리더가 하는 것보다 더 비효율적이지 않다는 것을 보장한다. 따라서 리더가 자주 바뀌는 상황을 지원하며, 이는 블록체인에서 chain quality를 높이는 데에 도움을 줄 것이다. Hotstuff는 앞서 설명한 장점들을 제공하기 위해 새로운 phase를 도입하는데, 추가되는 latency는 매우 적고 대신 view change protocol을 훨씬 간단히 만들 수 있다. 이 latency는 또한 실제 네트워크의 응답성에만 의존하므로, Casper나 Tendermint가 대기하는 $\Delta$ 보다는 훨씬 짧다. 또한, 파이프라인을 도입해 throughput에는 영향이 가지 않는다. 10,000,000 21,133,619

System architecture

Data Structure

Messages

메시지는 아래의 필드를 가진다

• m.viewNumber: 타임스탬프로서의 viewNumber
• m.type: {new-view, prepare, pre-commit, commit, decide} 중 하나
• m.node: 제안된 노드 (제안된 분기의 리프 노드. 커맨드가 트리 형태로 구성된다는 점을 감안)
• (optional) m.justify: 리더는 각 단계에 대한 QC(Quorum certificate)를 전달 / 레플리카는 new-view에서 가장 높은 prepareQC를 전달
• m.partialSig: 튜플 <m.type, m.viewNumber, m.node>에 대한 부분 서명

Quorum certificates

동일한 튜플 <type, viewNumber, node> 에 대한 $(n-f)$ 개의 서명 집합.

Tree and branches

모든 command가 트리의 노드로 표현되며, 노드 내에는 parent link(이전에 커밋된 command 혹은 그 집합)가 포함된다. 모든 레플리카는 로컬 트리를 유지하며, 리더로부터 받은 메시지가 자신의 로컬 분기의 확장이 아니면(로컬에서 따르고 있는 브랜치의 리프노드가 아니면) 충돌하는 것으로 간주한다.

Bookkeeping variables

Bookkeeping variable이란 레플리카가 프로토콜 상태를 추적하기 위해 관리하는 로컬 변수이다.

• viewNumber
• locked quorum certificate(locked QC)
  • 레플리카가 commit에 투표한 가장 높은 QC
• prepare quorum certificate(prepare QC)
  • 레플리카가 pre-commit에 투표한 가장 높은 QC
  • 레플리카가 new-view에서 리더에게 전달하는 값
  • 왜 이름을 prepareQC로 지었는지 모르겠다
• Command가 실행된 가장 높은 노드

Phases

제안하는 노드를 commit하기 위해 리더는 매 phase마다 $(n-f)$ 개 레플리카의 vote를 받아 quorum certificate를 만들 수 있어야 한다. 이 때 QC는 여러 vote를 threshold signature 방식으로 합친 하나의 서명이 된다.

Prepare phase

Prepare phase 에서는 새로운 리더가 1) 어떤 새로운 노드를 추가할지 2) 해당 노드의 parent를 무엇으로 할지 결정한다. View change가 일어나도 이와 같은 과정이 일어난다.

1. 리더는 다른 노드들로부터 $(n-f)$ 개의 prepareQC를 수집한다. 이 중 가장 높은 뷰의 prepareQC를 채택하여 highQC 라고 명명하고, 해당 node가 commit되었다고 가정한다.
2. 리더는 새로운 노드를 만들어 highQC 노드의 확장으로 만든다.
3. highQC와 새로운 노드 newNode를 브로드캐스트한다
4. 이를 받은 레플리카들은 그림에 있는 TEST를 수행하여 통과하는 경우에만 prepare vote를 전송한다.
5. 리더는 $(n-f)$ 개의 prepare vote를 모아 prepareQC로 합친다. 여기서 prepareQC가 증명하는 것은 리더가 레플리카들에게 동일한 proposal을 보냈다는 사실, 즉 proposal의 uniqueness이다. (이는 key로도 불린다.)

Note

이 시점에서 View change가 발생하면 newNode는 무시된다. 즉, 현재 뷰 이전의 뷰에서 시작하는 노드를 이어나간다.

Precommit phase ← NEW!

Precommit phase는 liveness를 보장하기 위해 핫스터프에 추가된 phase이다. 이 단계에서는 리더가 레플리카에게 prepareQC를 전달하고, $n-f$ 개 레플리카가 이를 받았다는 증거(precommitQC)를 수집한다. 여기서 precommitQC가 증명하는 것은 $n-f$ 개의 레플리카가 prepareQC 를 가지고 있다는 사실이다. 이는 liveness를 보장하는 데에 중요한 역할을 한다. $n-f$ 개의 레플리카가 prepareQC 를 가지고 있으면, 이후 view change가 발생했을 때 최소 하나의 정직한 레플리카가 올바른 prepareQC를 보고할 수 있기 때문이다. (2f+1개 중 f개가 faulty node이고 f개 메시지가 그들에 의해 변조되었다 하더라도 하나가 남는다.) 따라서 이 단계가 liveness를 보장하는 핵심적인 단계라고 할 수 있다.

Note

이 시점에서 View change가 발생하면, prepareQC가 리더에게 전달되는지 여부에 따라 그 결과가 달라지지만 어느 경우든 아직 newNode에 lock이 걸린 레플리카는 없을 것이기 때문에 괜찮다.

Commit phase

모든 레플리카들은 이 node가 다음 view에서 취소되지 않는다는 보장이 있어야 lock을 건다. precommitQC가 증명하는 바($n-f$ 개 레플리카가 prepareQC를 가지고 있음)가 다음 view에서 취소되지 않을 것임을 보장한다. 따라서 precommitQC를 확인할 수 있는 commit 단계에 와서야 lock을 걸 수 있다.

Note

이 시점에서 View change가 발생하면 newNode를 이어서 커밋하는 방향으로 진행된다.

Decide phase

사실 여기서는 어떠한 vote도 일어나지 않으므로 phase로 간주되지 않는다. 따라서 핫스터프를 3-phase 라고 부르지만, 막상 합의의 전체 순서를 설명할 때는 phase로 치는 경우가 많아 decide phase로 부른다. 이 단계에서는 commitQC를 받은 레플리카들이 실행한다.

Chained-hotstuff

앞서 살펴보았듯, 모든 phase의 구조가 동일하기 때문에 phase끼리의 파이프라이닝이 가능하다. 예를 들어 첫번째 뷰에서 뷰 v1에 대한 prepare단계가 끝났다면, 해당 단계에서 수집한 QC는 다음 뷰의 리더에게 넘어간다. 다음 뷰의 리더는 뷰 v1에 대한 pre-commit을 진행함과 동시에, 뷰 v2에 대한 prepare 단계를 진행한다. 그리고 그 결과 수집된 QC1과 QC2를 다음 리더에게 넘기고, 다음 리더는 뷰 v1에 대한 commit, 뷰 v2에 대한 pre-commit, 뷰 v3에 대한 prepare를 진행하는 식이다. 이런 식으로 파이프라이닝을 통해 throughput을 증가시킬 수 있으며, 처리하는 단계의 수가 n개이면 n-chain hotstuff 라는 식으로 이름붙인