Tendermint Consensus overview

storemymem·2022년 5월 10일
1

앞선 글에서 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'단계가 종료되는 조건

  • nil에 대한 2/3이상 precommit 후 'Propose(H,R+1)'로 이동
  • 2/3이상 precommit 수신후 'timeoutPrecommit'이후 'Propose(H,R+1)'로 이동
  • 공통 종료 조건 이후

Common exite conditions

  • 특정 블록에 대한 2/3이상 precommit 후 'Commit(H)'로 이동
  • (H,R+x)에서 받은 2/3이상 prevote 후 'Prevote(H,R+x)'로 이동
  • (H,R+x)에서 받은 2/3이상 precommit 후 'Precommit(H,R+x)'로 이동

Commit step(height:H)

  • 'CommitTime = now()'로 설정
  • 블록이 수신될 때까지 기다린 후 'NewHeight(H+1)'로 이동

NewHeight step(height:H)

  • 'Precommits'를 'LastCommit'으로 이동 후 height 증가
  • 'StartTime = CommitTime+timeoutCommit'으로 설정
  • 낙오(straggler)된 commit 수신하기 위해 'StartTime'까지 대기한 후 'Propose(H,0)'으로 이동

Conclusion

Consensus process에 대해 조금 더 확인해보기 위하여 docs를 봤는데 아직까지 머리속에 명확하게 정립은 되지 않는것 같다. 다음번에는 Tendermint core 코드 상에서 돌아가는 방식을 보고 한번 더 확인해봐야겠다.

참고
https://github.com/tendermint/tendermint/blob/master/spec/consensus/consensus.md

profile
ConsensusMyMemoies

2개의 댓글

comment-user-thumbnail
2022년 7월 4일

공유 감사합니다. 밸리데이터 운영중에 많은 도움이 될 것 같습니다.

답글 달기
comment-user-thumbnail
5일 전

감사합니다

답글 달기