Ethereum2.0を例にしてコンセンサスアルゴリズムとは何か説明する

この記事は、[Ethereum Advent Calendar 2019](https://qiita.com/advent-calendar/2019/ethereum)の 17 日目です。

## はじめに

Bitcoin や Ethereum などのブロックチェーンでは,中央管理者が存在しない。
だから,ネットワークに参加しているノードで非中央集権的に不正な取引を監視し正当性について合意形成する必要がある。

非中央集権で合意形成するメリット

1. 障害耐性: 単一障害点がないためある部分が故障しても全体が動かなくなるリスクを回避できる。
2. 攻撃耐性: 分散システムでは多数の攻撃対象を同時に攻撃する必要があるため,攻撃コストが大きくなり攻撃しづらくなる。
3. 共謀耐性: 独占などの全体の利益を犠牲にしてまである特定の団体または個人にのみ都合のいい行動をとることを防ぐことができる。

## どのように合意形成しているのか?

一般的なコンセンサスアルゴリズムの流れ

1. 新しいトランザクションが全てのノードに伝播される
2. それぞれの候補ノードが有効な新規トランザクションでブロックを生成する
3. 候補ノードの中から適当に選択され, そのブロックをネットワークに伝播する
4. 他のノードはブロックの有効性を確認し正しければ, チェーンに追加する
5. ノードの大多数が承認すれば, ブロックは絶対的に承認される

上の流れを実現するために以下のような要素がある。

| 要素                     | 目的                                                           | 選択肢                                                                                                                                                               |
| ------------------------ | -------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| ブロック提案             | ブロックを生成する                                             | Proof of work (PoW), proof of stake (PoS), proof of authority (PoA), proof of retrievability (PoR), proof of elapsed time (PoET), round robin, committee-based, etc. |
| 情報伝達                 | ネットワークにブロックとトランザクションを伝播                 | Advertisement-based gossiping, block header soliciting, unsolicited block push (broadcast), relay network (for mining pools), etc                                  |
| ブロック検証　           | ブロック生成証明とその中のトランザクションをチェック           | Proof checking (for proof-of-X block proposal), digital signature & eligibility checking (for committee-based block proposal), etc.                                  |
| ブロックファイナライズ   | 分岐するブロックチェーンでどのチェーンをメインチェーンとするか | Longest-chain rule, GHOST rule, PBFT, other Byzantine agreements, checkpointing, etc.                                                                                |
| インセンティブメカニズム | 正直な参加を奨励し、システムを前進させます                     | Block rewards, transaction fees, eligibility for issuing new transactions, etc.                                                                                      |

Ref: [Y. Xiao, N. Zhang, W. Lou, and Y. T. Hou, “A survey of distributed consensus protocols for blockchain networks,” arXiv preprint. arXiv: 1904.04098.](https://arxiv.org/abs/1904.04098)

例えば、Bitcoin(Nakamoto Consensus)では

| ブロック提案 | ブロック検証 | 情報伝達 |ブロックファイナライズ|インセンティブメカニズム|
|-----------------|------------------|------------------|------|------|
| PoW| PoW check| Gossiping |Longest-chain rule|Block reward and transaction fee|

Proof of Work = コンセンサスアルゴリズムとよく言われますが、厳密には Proof of Work はコンセンサスアルゴリズムの一部であってコンセンサスアルゴリズムではない。Nakamoto Consensus についての詳しい説明は本題から外れるので省きますが、特徴としてはブロックファイナライズが Longest-chain rule なので確率的ファイナリティーしかなく 51%攻撃のリスクが大きいことである。詳しくはこちら[モナコインへの攻撃から、ブロックチェーンへの攻撃やマイニングを深掘りする](https://blockchain.gunosy.io/entry/2018/05/18/164219)

現在の Ethereum も Nakamoto Consensus にしたがっている。
しかし、Ethereum は今後 PoS から PoS に移行するにあたって、コンセンサスアルゴリズムを徐々に変えていく予定があります。アップデート後の Ethereum を Ethereum 2.0 という。

## Ethereum 2.0 のコンセンサスアルゴリズム

CasperFFG と CasperCBC が存在しますが、CasperFFG が適応されるみたいなのでこちらについて説明する。
CasperFFG は BFT-based PoS と言われる種類のコンセンサスアルゴリズムになる。
BFT-based PoS の特徴は、BFT な感じでファイナリティーを与えることである。
例えば、CasperFFG ではステークによる重み付け投票を用いてファイナリティーを与える。
それぞれの要素については以下のようになる。

| ブロック提案 | ブロック検証                | 情報伝達                   | ブロックファイナライズ | インセンティブメカニズム               |
| ------------ | --------------------------- | -------------------------- | ---------------------- | -------------------------------------- |
| PoW          | PoW & Checkpoint tree check | Broadcast among validators | BFT(with staked votes) | Block reward for miners and vilidators |

それぞれについて見ていく。

### PoW

Bitcoin にも用いられている最も有名なブロック提案方法の Proof of Work である。
簡単に言うと、Hash(ブロック+x) < difficulty となる x を探す作業である。
ブロックに x と書き込むと、ブロックができたということになる。
そのブロックの正当性もハッシュの計算をして実際に difficulty 以下になるか確認するだけなので簡単であり、ハッシュ化をうまく利用している。
difficulty はブロックの生成間隔が暗号通貨ごとの指定の時間になるようにうまく調整されている。CasperFFG ではハッシュ関数に Ethash が用いられる。

### PoW & Checkpoint tree check

PoW では、上で述べたようにハッシュを計算するだけで正しい x かどうか検証できる。
その x を見つけるためには莫大な計算量が求められれるため「仕事の証明」と言われる。
また、CasperFFG ではブロックチェーンの 100 ブロックごとにチェックポイントが存在する。
このチェックポイントごとに検証者はチェックポイントがあるブロックチェーンは正当か投票を行う。
以下の図ではb1,b2,b3のチェックポイントが存在しており、徐々にブロックチェーンが検証されていくイメージである。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/181220/97a834c5-087b-3bd7-2eef-e12ce4a44d4a.png)
Ref: [Buterin, Vitalik, and Virgil Griffith. "Casper the friendly finality gadget." arXiv preprint arXiv:1710.09437 (2017).](https://arxiv.org/abs/1710.09437)

### Broadcast among validators
いい感じに検証者にブロードキャストする(あんまり詳しくないから略)

### BFT(with staked votes)
> ビザンチン将軍問題とは何かを簡潔に説明すると、「相互に通信し合うP2Pネットワーク上で、通信そのものや個々のノードが故障、または故意に偽の情報を伝達する可能性がある場合に、全体として正しい合意が形成できるかを問う問題」です。この問題を解決し、P2Pネットワークが正常に稼働するシステムは、ビザンチン・フォールト・トレランス性（Byzantine Fault Tolerance：BFT）を持つと言われます。

https://gaiax-blockchain.com/byzantine-generals-problem

CasperFFGでは、ステーク量による重み付けの投票によってBFTが実現され、それによってブロックファイナライズを行っています。チェックポイントごとに検証者が投票を行う。正当なブロックチェーンと思った検証者は投票を行い、不正なブロックチェーンと思った検証者は投票を行わない。不正なブロックチェーンであるのに投票した検証者は検証者になるためにデポジットした賭け金を没収されてしまう。中央集権者がいないのに何を持って判断されるかと言うと、検証者がお互いに判断する。この仕組みをSlasherという。詳しくはこちら。[イーサリアムのPoS「Casper」で使われるSlasherとは何なのか
](https://zoom-blc.com/slasher-in-ethereum-proof-of-stake)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/181220/c6075e41-eb0c-5aa2-a802-d18a1f0bd2f9.png)

### Block Reward for miners and validatos
インセンティブメカニズムとしてはブロック生成報酬とブロック検証報酬が存在する。


## まとめ
CasperFFGはPoWとPoSのいいとこ取りをしたようなコンセンサスアルゴリズムになっている。
PoWでブロック生成をするものの、PoSでブロックファイナライズを行う。
ブロックファイナライズがあるPoWといった感じである。
これによって、51%攻撃のリスクはなくなりビットコインの弱点が補われたという印象である。

また、PoSでどのように検証者のステーク量など保持したり、ステーク量による擬似ランダムの計算を誰が行うのか疑問だったが、そのためのBeaconChainと言うものがあってそちらのチェーンで別途行っているみたい。


[Ethereum Advent Calendar 2019](https://qiita.com/advent-calendar/2019/ethereum)の 18 日目はまた僕です。CasperFFGのブロック検証に関する論文について書きます。

おすすめ書籍
Ethereumの本ではないが、ブロックチェーンについて詳しい解説がされている「ビットコインとブロックチェーン:暗号通貨を支える技術」という本はわかりやすくおすすめ。