20190613コンセンサスアルゴリズム勉強会
はじめるよ
2019.6.13 (Thr)
スライドモードがおすすめだよ
本日の目的
コンセンサスアルゴリズムの基礎を分散システムという歴史ある学問の視点から学ぶ
コンソーシアムチェーンを使う時に役立つ(pBFTなど古典的アルゴリズムが多いので)
次回以降の勉強会への橋渡し
Layer1最前線
第二回CBC Casper勉強会
アジェンダ
Consensus, SMR, public ledger
Network synchrony
PBFT
Blockchain consensus inspired by PBFT
References
いきなり問題
Q. この中でコンセンサスアルゴリズムと言えるのはどれ？
1. Proof of work
2. シャーディング
3. ETH2.0
4. フォークチョイスルール
5. Casper
6. Ethereum virtual machine
コンセンサスアルゴリズムとは
https://gyazo.com/3a299e6e44aac2f2daf382a2a1939c79
乱暴にいうとAgreementはSafety, TerminationはLivenessとも言われる
もっと広いくくりだと分散アルゴリズムの一種だよ
ノードの色々な故障に耐える必要があるよ
→でも、これだけでは分散台帳は実現できそうにない。。。！
State machine replication (SMR)
決定的なステートマシンを複製するアルゴリズム
決定的: 同じ命令列なら同じ状態に遷移する
コンセンサスアルゴリズムを繰り返し使って、命令列に合意する
分散台帳の場合
命令はトランザクションの形式
EVMなどは状態遷移のルール
→分散台帳に少し近づいた
Layer1の構成要素
Layer1の個人的な定義: 分散台帳を実現するプロトコル全体
シビルコントロール e.g. PoW, PoS
コンセンサスノードのローテーション: 乱数生成, etc.
インセンティブ設計: reward, slashing
他にも色々あるが、要はコンセンサスアルゴリズムはその一部品でしかない
答え合わせ
Q. この中でコンセンサスアルゴリズムと言えるのはどれ？
1. Proof of work: シビルコントロール兼ブロック提案ルール(頻度調整等)
2. シャーディング: 複数のSMRで分散台帳を実現する技術
3. ETH2.0: Layer1のアップデートプロジェクト
4. フォークチョイスルール: (Chain-based) consensusの一部品、メインチェーンを決める関数
5. Casper: コンセンサス + 色々(slashingとか)
6. Ethereum virtual machine: 状態遷移のルール
余談: トリレンマ
CAP定理: あんまり気にしなくていいよ (乱暴)
スケーラビリティのトリレンマ: ブロックチェーン作るのむずいよね、うん、そうだねくらいの意味しかないので気にしなくていいと思います
Message overhead / Latency to finality / Number of validators: Vitalik & Vladが良く言うやつ。色々強い仮定が入ってるけど大まかな方向性は正しい。
※トリレンマではないが後述するFLP impossibilityはとても大事です
具体的にコンセンサスアルゴリズムを見ていこう！
まず事前準備: どんな仮定をおいて議論するのかの話
1. ネットワーク
2. 故障
ネットワークのモデル
ノード間のメッセージがどれくらい遅延するかの仮定
(Full) synchrony: all messages are delivered within known$ \Delta
Partial synchrony
1. After unknown time GST, the network gets synchronous (Eventual synchrony)
GST = Global Stabilization Time
2. all messages are delivered within unknown$ \Delta
Asynchronous: all messages are eventually delivered
※ 他にも分類の仕方はあります (e.g. weak synchrony, semi synchrony, etc.)
ネットワークとsafety & liveness
FLP impossibility: 決定的なコンセンサスプロコルはasynchronyで故障耐性持ちつつsafety liveness両方満たすの無理だよ
回避方法: (1) synchrony仮定を入れる (2) 非決定的にする(高い確率で満たす、に留める)
Nakamoto (PoW): 確率的safety in full synchrony, 確率的liveness in asynchrony
(Parial synchronyと言ってる論文もあるが...)
PBFT, Tendermint, Casper FFG: 決定的、safe in asynchrony, live in partial synchrony
FFGは作り方によってはlive in full synchronyかも
Honeybadger BFT: 確率的safety & livenes in asynchrony
Randomized consensusと呼ばれるカテゴリ
故障のモデル
Honest: プロトコルに従う。
Omission failure: メッセージの受信・送信に失敗
Asynchronyにおいては、network latencyと区別ができない(FLP impossibilityの本質)
Byzantine failure: なんでも。二重投票とか。
※ 他にも分類の仕方はあります (failureから復活するかどうか分けたり)
アルゴリズムと故障耐性
Fail-stop
3-phase commit, Primary-backup, etc
Crash-recovery
Paxos, Raft, Viewstamped-replication, etc.
Byzantine fault tolerance
PBFT, Byzantine paxos, etc.
PBFT
PBFTから学び始める人向けのポイント
3つのフェーズ (2回の投票)
Byzantine quorum:$ 2f + 1
View change
3つのフェーズ
https://gyazo.com/e673e02330b66e9de19c8f54933491f1
Prepare: 提案がユニークであることを保証するため
Commit: 最終決定する
否定の投票とかはないよ
Byzantine quorum
全ノード数$ n = 3f + 1
よく$ n = 4の例がイラストになる
後述する投票の閾値(quorum)は$ 2f + 1
二つのquorumがあると仮定すると、必ずoverlapする
https://gyazo.com/9361ae9e15d273017c38a10198ad6a2a
でもなぜ$ 2f + 1が最適なのか
View-change
Primaryが故障した場合のため、タイムアウトするとview changeを実行する
view-change message: $ 2f + 1のcheckpoint messagesと$ 2f + 1のprepare messages
Checkpointing: 定期的に最新のstateに合意してログを消す
Checkpoint messageを送り合い、$ 2f + 1に達したらcheckpointing
$ 2f + 1のview-changeを集め、新しいprimaryがnew-view messageを全員に送る
Message overheadが$ O(n^3)→ Public chainでそのまま使うのはキビシイ
Improvements of PBFT
Zyzzyva (Kotla et al, 2009)
All-to-allでメッセージ送り合うのではなく、"Collector"が代わりに集めてみんなに届ける
Optimistic execution: network latencyが低くて故障がないときは
Message size reduction (最近はBLS署名とか)
Blockchain inspired by PBFT
pBFTがそもままBlockchainになるわけではない
Public系: Tendermint (実は結構違う, タイムアウトを入れてview-changeが$ O(n^2))
Private系: IBFT2.0, SBFT (PBFTに近いが色々な改善提案を取り込んでいる)
余談: "PoA"の定義
個人的にはPoA = Permissioned = Private
しかし、「単一ノードがひたすらブロックを作る」仕組みのことをPoAと呼んでいる人々がいる気がする(要出典)
少なくともこれはコンセンサスアルゴリズムではないよ
PoAアルゴリズムまとめ
Parity PoA: Aura (国内だとALISさんが使ってる) Quorum: Raft or IBFT
Corda (notaries): Raft?
Hyperledger Fabric: PBFT (~v0.6?) -> Non-BFT consensus (v1.0~)
最後に
〜これから勉強する人に向けての言霊〜zq
勉強のコツ
まず体系的に説明されているものにあたり、とにかく疑問を整理する、コツコツ潰す
本当に調べるべきものを見失わない
全部理解しようとすると時間がいくらあっても足りないので優先順位をつける
とはいえ、本質的な部分の理解を飛ばすと急がば回れになる
プロトコルを理解するとはどういうことか
必要性と十分性がわかるということ
1. そのプロトコルが満たすべき性質がわかる
2. そのプロトコルが要求を満たすことがわかる
3. 要求を満たすためのそのプロトコルの任意のパーツについて、それが必要不可欠であるとわかる
おしまい