シャーディングを用いたブロックチェーンプラットフォーム「Zilliqa」について調べたことを簡単にまとめておきます。
Zilliqa設計の非技術的な話
Sebil resistance
※以下、The Zilliqa Design Story Piece by Piece: Part 1 (Network Sharding)より
パーミッションレスなネットワークであるため、セキュリティを確保するために一定以上のノード数が必要。
→ノードになるためにデポジットが必要な設計にすることによって攻撃のコストを高める。
→PoWによる計算を義務付け、計算資源の提供によってノードはエントリーチケットを得るような設計にする。
Shard creation
ノードのシャードへの割当の方法の確立が必要。割当はランダムに行う必要があるため、乱数の発生が重要になる。
→Zilliqaでは最初に「directory service committee (or DS committee)」と呼ばれるノード郡を選定する。選定はPoWに基づいて行われる。DS-epochと呼ばれるインターバルを経て、DS committeeのメンバーの一人が新しいメンバーに入れ替わる（FIFO方式）。故にDS committeeのサイズは一定（※ここの挙動が気になる）。新しくCommitteeに入るメンバーはPoWの計算競争を勝ち抜いた者。他の（DS committeeではない）全てのノードはPoWを行い、DS committeeによって検証される。PoWの提出とランダムネス（※乱数の発生方法は次の記事で触れる予定）に基づいて各ノードはそれぞれのシャードに割り当てられる。提出されたPoWの末尾の数bitがどのノードがどのシャードに割り当てられるかを決定する（※ここの挙動も要確認）。
Shard size
シャードを構成するノードの数には下限がある。例えば10のノードで構成されるシャードは成立するか？シャードを構成するノードの数が少ないと、攻撃者がシャードを乗っ取ることが容易になってしまう。
→適切なシャードサイズの選定は重要。以下のグラフは少なくとも1/3のシャードメンバーが悪意のあるノードである確率を示している。シャードサイズが100の場合は0.04なので、セキュアであるとは言えない。シャードサイズが600の場合、百万分の1になる（図では10^-6と10^-5の間に位置しているように見えるが）。
この計算の根拠はこのペーパーに書いてあるらしいが無料公開されていない。
ハイスループットのためのコンセンサスプロトコル
以下、The Zilliqa Design Story Piece by Piece: Part 2 (Consensus Protocol)より。
ネットワークシャーディングはそれ単体でハイスループットを保証するものではない。スループットは各シャードが如何に早くトランザクションに関する合意に至るかが重要。
ビットコインやEthereumでは数万のノードによってネットワークが構成されているが、それに比べるとZilliqaのシャードサイズは随分と小さい。ZilliqaはビットコインやEthereumと同じコンセンサスプロトコルを使うことはできないのだろうか。
ビットコインやEthereumで使用されているコンセンサスはNakamotoコンセンサスといわれるもの。Nakamotoコンセンサスはシンプルでエレガントな確率的コンセンサスメカニズムで、PoWの計算競争に勝った”リーダー”によって次に生成されるブロックが提案され、他のノードにブロードキャストされる。
このような方式だとトランザクションを確定させるのに時間がかかり、コンセンサスプロトコルをスローダウンさせる。更に、このコンセンサスで重要なのはノードの数ではなく、ネットワーク全体の計算能力の合計になる。Zilliqaにおいて同じ方式を採用した場合、比較的小さなサイズのシャードにおいて有効活用することができない。故に、Zilliqaでは別のコンセンサスが必要。
Practical Byzantine Fault Tolerance (PBFT)
Zilliqaでは各シャードにPBFTを採用。PBFTは悪意のあるノードが全体の1/3以下であることが前提となる。これはNakamotoコンセンサスよりも低い値（Tendermintと同じ）。PBFTではシャード内でPrimary node（リーダー）を選定し、他のノードはバックアップと見なされる。
PBFTのプロセスは以下の3つのフェーズを持つ。
- Pre-prepare phase: リーダーがグループ（シャード内のノード）が合意すべき次の”レコード”をアナウンスする。これは“pre-prepare”メッセージを送ることによってなされる。
- Prepare phase: “pre-prepare”メッセージを受け取ったノードはリーダーによってアナウンスされたレコードの正確さと正当性を検証。その後、“prepare” messageを他のノードにマルチキャストする。
- Commit phase: “prepare” messageをsupermajorityから受け取った各ノードはcommit messageをグループにマルチキャストする。各ノードはsupermaorityからのcommit messageを待ち、十分な数のノードがリーダーによってアナウンスされたレコードに合意していることを確認する。
これら3つの段階を経て、全ての善意のノードはレコードをAcceptするかRejectするかのどちらかになる（※ノード間のコミュニケーションコストが高い印象）。
上記の通り、PBFTではリーダーが決定的な役割を果たすため、Nakamotoコンセンサスに比べると中央集権的で、且つ2/3以上が善意のノードである必要がある。リーダーに悪意がある場合、これらのプロセスは遅々として進まないことになる。
PBFTではこの問題に対処するためにview changeプロトコルという仕組みがあり、悪意のあるリーダーを別のノードに置き換えることができる。各ノードはプロセスに進捗が見られない場合も、単独でリーダー変更の要請を行うことが可能。Supermajorityがリーダーの不能を認めた場合、次のリーダーが引き継ぎを行う（※プロセス詳細は要調査）。
PBFTのみならず各コンセンサスアルゴリズムの比較は以下が詳しい。
A Hitchhiker’s Guide to Consensus Algorithms – Hacker Noon
2/3以上の善意のノードが必要な点はTendermintも同様なので比較しても面白いかもしれない。
次世代のコンセンサスエンジン”Tendermint”の話をしました @blockchain.tokyo #8 – Mercari Engineering Blog
Welcome to Tendermint! — Tendermint documentation
Other Benefits of PBFT
PBFTにはスモールサイズのシャードを活用できることに加えて（スモールサイズがベターなのはコミュニケーションコストの増大を抑えられるから？）、Nakamotoコンセンサスに比較した場合に、以下の利点がある。
Transaction finality
PBFTはコンセンサスにファイナリティをもたらす。ファイナリティはネットワーク内でコンセンサスに至り、ブロックが生成された場合、そのブロックは最終的なもの（後で覆されることのないもの）となる。それ故に、ビットコインにおける6承認のような、確率的ファイナリティにおいては必須となる余計な待ち時間が必要なくなる。
これは中央集権化とのトレードオフで得られるもの。
Low energy footprint
PBFTはコンセンサスに至るために多大な計算能力を必要とするプロトコルではないため、エネルギー消費を抑えることができる。ZilliqaではPoWが用いられているが、それはシビルアタックを防ぎ、ノードのアイデンティティを明確にするためであり、コンセンサスのためではない（※DS committeeに入るためにはPoWの競争を勝ち抜かなくてはならないので、ここは要調査）。
ZilliqaはプラットフォームなのでZILトークンの価値の源泉についてはユーティリティ以上の意味を作らなくても良いかもしれないが、価値創造の過程はトークンにとってクリティカルなので結論を急ぎたくない。
Low reward variance
PBFTではメッセージ署名によるレコードへの投票を通じた集合的な投票が必要。これはリーダー（PoW計算競争の勝者）だけがブロックを提案する仕組みとは対照的。PBFTでは、この仕組みを利用して、全ての参加ノードにインセンティブを与えるようなインセンティブレイヤーの設計が可能。リワード/インセンティブの分配は今後の興味深いテーマだと思う（ただ複雑さが増しそう）。
これはリワードの分散の話であって、合意の分散ではない（であろう）点には注意。Nakamotoコンセンサスは、各マイナーが計算競争の参加して採掘難易度を上げること自体が「合意形成の一環」であると個人的には思うので、Nakamotoコンセンサスに比べてPBFTの方が投票元が分散しているからといって、それがより包括的な合意形成であるとは思わない（まだよく分かってない）。
次回は『The Zilliqa Design Story Piece by Piece: Part 3 (Making Consensus Efficient)』を元に情報を簡単にまとめ、ZilliqaのEthereum ShardingやDfinityとの類似点/相違点を軽く調べたい。
