Tendermint Consensus overview

storemymem·2022년 5월 10일

앞선 글에서 Tendermint의 consensus algorithm에 대한 대략적인 프로세스를 확인하였다. 해당 프로세스에 대해 조금 더 디테일하게 확인해보고 싶어 관련 안내 문서를 확인했다.

Byzantine Consensus algorithm

Terms

네트워크는 선택적으로 연결된 노드로 구성된다. 특정 노드에 직접 연결된 노드를 peers라고 한다.
다음 블록(height H)을 결정할 때의 합의 프로세스는 하나 또는 여러 round로 구성된다.
'NewHeight','Propose', 'Prevote', 'Precommit' 및 'Commit'은 라운드의 state machine 상태를 나타낸다. (aka RoundStep or 'step')
노드는 주어진 height, round, step에 대한 것을 (H,R,S)로 표현하며, step을 생략하여 (H,R)로 표현한다.
Prevote 또는 Precommit 하는 것은 prevote vote 또는 first precommit vote를 브로드캐스트 하는 과정이다.
(H,R) 단계에서의 투표는 sign-bytes에 포함된 H 및 R에 대한 바이트로 서명된 투표이다.
특정 블록에 대한 사전 투표의 2/3이상의 set 또는, (H,R)의 'nil'을 proof-of-lock-change 또는 PoLC라 한다.

State machine overview

블록체인의 각 height에서 round-based 프로토콜은 다음 블록을 결정하기 위해 실행된다. 각 round는 3 step으로 이루어져 있으며(Propose, Prevote, Precommit) Commit과 NewHeight의 step도 존재한다.

최적의 시나리오는

NewHeight -> (Propose -> Prevote -> Precommit)+ -> Commit -> NewHeight ->...

위와 같으며, 가운데 propose부터 precommit을 한 round라 칭한다. 블록을 생성하기 위해 한번의 round를 진행하지만 블록이 생성되지 않을 시 여러번의 round를 진행한다. 다음과 같은 상황일 시 여러번의 round가 일어날 수 있다.

Designated proposer(지정된 제안자)가 오프라인일 시
Designated proposer에 의해 제안된 블록이 invalid 할 시
Designated proposer에 의해 제안된 블록이 시간안에 전달되지 않을 시
블록이 유효(valid)하지만 충분한 validator가 Precommit 단계에 도달해도 제안된 블록을 위한 prevote의 2/3 이상이 시간내에 받아들여지지 않을 시
제안된 블록이 유효했고, 충분한 node의 prevote가 2/3 이상 수신되었지만 제안 블록에 대한 precommit의 2/3 이상이 충분한 validator에 대해 수신되지 못했을 시

State machine diagram

                         +-------------------------------------+
                         v                                     |(Wait til `CommmitTime+timeoutCommit`)
                   +-----------+                         +-----+-----+
      +----------> |  Propose  +--------------+          | NewHeight |
      |            +-----------+              |          +-----------+
      |                                       |                ^
      |(Else, after timeoutPrecommit)         v                |
+-----+-----+                           +-----------+          |
| Precommit |  <------------------------+  Prevote  |          |
+-----+-----+                           +-----------+          |
      |(When +2/3 Precommits for block found)                  |
      v                                                        |
+--------------------------------------------------------------------+
|  Commit                                                            |
|                                                                    |
|  * Set CommitTime = now;                                           |
|  * Wait for block, then stage/save/commit block;                   |
+--------------------------------------------------------------------+

Background Gossip

어떤 노드에는 validator 역할을 위한 private key가 없을 수 있지만, meta-data, proposals, blocks 및 votes를 피어에게 중계함으로써 consensus protocol에서 적극적인 역할을 가진다. Active validator의 개인키가 있고 투표 서명에 참여하는 노드를 validator-nodes라고 한다. Validator node를 포함한 모든 노드는 state를 가지고 있으며(height, round, step) 다음 단계 진행을 위한 작업을 실시한다.

두 노드 사이에는 'connection'이 있으며 이 connection위에 다중화되어 정보의 'channel'이 제한된다. Channel 중 일부는 epidemic gossip protocol이 구현되어 주변 노드에게 가장 최근의 합의 상태를 알릴 수 있다.
For example,

노드는 현재 round의 proposer(제안자)가 제안한 블록의 'PartSet' 부분을 gossip 한다. (블록을 빠르게 broadcast 하는데 사용)
노드는 prevote/precommit 투표를 gossip한다. NodeB보다 앞서있는 NodeA는 NodeB의 현재(or 미래) 라운드에 대해 NodeB의 prevote or precommit을 전달하여 다음단계로 진행될 수 있다.
노드 gossip은 제안된 PoLC(Proof of Lock Change) 라운드가 제안된 경우 해당 라운드에 대해 우선 투표한다.
노드는 오래된 블록에 대한 블록 commits로 블록 체인 높이가 뒤처진 노드에 대해 gossip 한다.
노드는 ReceivedVote 메시지를 gossip하여 피어에게 이미 투표한 내용에 대해 힌트를 준다.
노드는 현재 상태를 모든 이웃 피어에게 브로드캐스트 하며 더 이상 gossip하지 않는다.

Proposals

Proposal은 각 라운드에 지정된 proposer가 서명하고 publish한다. Proposer는 voting power에 비례하여 라운드 로빈 선택 알고리즘에 의해 선택된다. (동작방식)

'(H,R)'의 proposal은 블록과 proposer가 알고있는 경우 포함되는 최신 'PoLC-Round < R'로 구성된다. 노드가 안전할 때 잠금을 해제할 수 있도록 네트워크에 암시하여 활성속성(liveness property)를 보장한다.

State machine spec

Proposer step(height:H, round:R)

'Propose' 입력 시

designated proposer(지정된 제안자)은 '(H,R)'에 대한 블록을 제안한다.

'Propose'가 종료되는 조건

'Propose'가 입력이 되고, 'timeoutProposeR' 후에 'Prevote(H,R)'로 이동
PoLC-Round에서 제안 블록 및 모든 prevote를 받은 후 'Prevote(H,R)'로 이동
공통 종료 조건 이후

Prevote step(height:H, round:R)

'Prevote'를 단계에서 각 validator들은 prevote 투표를 브로드캐스트 한다.

만약 validator가 'LastLockRound' 이후 블록에 잠겨 있지만(locked) 'PoCL-Round'에서 어떤것에 대한 PoLC를 가지고 있는 경우 (where 'LastLockRound < PoLC-Round < R') 락이 해제된다(unlocked).
만약 Validator가 여전히 locked된 상태이면 그것을 prevote한다.
그렇지 않으면 'Propose(H,R)'에서 제안된 블록이 이상 없으면 그것을 prevote한다.
Propose가 유효하지 않거나 시간안에 received 되지 않은경우 nil을 prevote한다.

'Prevote'단계가 종료되는 조건

특정 블록 또는 nil에 대한 2/3이상 prevote 이후 'Precommit(H,R)'로 이동
2/3 이상 prevote 받은 후 'timeoutPrevote' 이후 'Precommit(H,R)'로 이동
공통 종료 조건 이후

Precommit step(height:H, round:R)

'Precommit' 단계에서 각 validator들은 precommit 투표를 브로드캐스트 한다.

Validator가 특정 블록 B에 대해 (H,R)에 PoLC가 있는 경우 (재)잠금 (또는 잠금 변경)하고 B를 precommit 후 'LastLockRound = R'로 설정한다.
Validator가 nil에 대한 (H,R)에 PoLC가 있으면 잠금을 해제하고 nil을 precommit한다.
잠금을 변경하지 않고 nil을 precommit한다.

이 nil에 대한 precommit은 "이 round에 대한 PoLC를 확인하지 못했지만 2/3이상 prevote를 얻었고 조금 기다렸다"를 의미한다.

'Precommit'단계가 종료되는 조건