ブロックチェーンエンジニアになろう。 (コンセンサスアルゴリズム編)

2019年12月7日 05:58

今回は、ブロックチェーンの中で一番話されるトピックと思われるコンセンサスアルゴリズムについて話していきたいと思います。
まだ、以前の基礎編を読んでいない方は、是非読んでみてください。

コンセンサス・アルゴリズムとは、日本語では合意形成アルゴリズムになると思いますが、ブロックチェーンはP2Pネットワーク上で動く分散システム
ですので、各ノードがどの情報が正しいかを合意しないといけません。
ブロックチェーンでは、主に2つの大きな問題が存在しています。

- 誰が新しいブロックをを作るのか
- どのチェーンが正しいのか

また、多くの場合は、ブロックを生成する権利は、ネットワーク維持のための報酬設計にも組み込まれています。
これには、経済学やゲーム理論など複数の事柄を合わせて考えられています。
例えば、多くのブロックチェーンプロジェクトでは、ブロックから報酬が一定期間で減少していきます。
ブロックの報酬の減少率などはプロジェクトごとによって大きく変わってきて、技術的には主に定数、もしくは、設定で変更するのでそれにより、どのような経済効果やネットワーク報酬になっているかは変わってきます。

多くの方は、Cryptocurrencyを投資/投機目的で購入し、価格変動で利益を得ていますが、
それ以外にも、プロジェクトによっては、ネットワークに参加し、保守をすることによって
利益を得ることが出来ます。こちらは、基本的には次項の誰がブロックを生成出来るかによって
どのように報酬が得れるかが変わってきますのでそこで書きたいと思います。
また、Liskでは、LIP-0022とLIP-0023で提案されているDPoSの変更により、アルゴリズムが大きく変わりさらに多くの人が報酬を得る機会があります。以下で、その違いも紹介しています。

誰がブロックを生成するのか

ブロックチェーンは、新たな情報更新するためには、常に新しいブロックを生成しないといけません。しかし、分散的にいつ誰が新しいブロックを作るかはとても難しい問題です。
日常的な例で言うと、リーダーのいない会議で会議メンバーの一人の案が採用され、その人には報酬が与えられます。その一人が誰なのかを全員で合意をとらなければいけない。さらに、難しいのは、この会議には誰でも参加出来るので、この会社に不利益をもたらそうとする人も参加する可能性があります。というような問題になります。
この問題を、合理的に解決するために様々なアルゴリズムが開発されました。
上記の問題を考えると、

* 単一の参加者を分散的に選ぶ
* ネットワークに不利益をもたらす参加者を選ばない

がアルゴリズムの主な目的となっていると思います。
以下は、最も有名な4つのアルゴリズムになっています。詳細には、各プロジェクトで少しづつ違いますが、大きくは同じなので解説していきます。

PoW (Proof of Work)

Proof of Workを使っている代表は、言わずもがなBlockchainの代表Bitcoinです。
Bitcoinでは、ブロック生成者はMinor(採掘者)と呼ばれ、ブロックを生成することをMining(採掘)と言います。

Proof of workでは、採掘出来る人は基本的には早い者がちになっています。ただし、新しいブロックは10分毎にしか生成されません。これは、速さだけではなくもう一つの条件によって制御されています。
その前に、簡単にHash関数について説明します。BitcoinではSHA256が使われていますが、これは任意の長さバイナリーデータをdeterministic(決定的)に固定な長さのバイナリーデータに変換します。
例えば、

crypto.hash('123', 'utf8').toString('hex')
'a665a45920422f9d417e4867efdc4fb8a04a1f3fff1fa07e998e86f7f7a27ae3'

crypto.hash('abc'.repeat(10000), 'utf8').toString('hex')
'13b77af908a78a94f2e21cf8fc137ea16c8020873eeee7b6b96b6b0975555a02'

Proof of Workでは、BlockをHashした最初のX桁が”0”でないといけないという条件があります。X桁は、その時点での難易度によって変わります。この、難易度調整によって10分という時間がコントロールされています。
また、Blockが同じであればHashはdeterministic(決定的)なので、1回しかチャンスがなさそうですが、実際は、Nonceというフィールドは任意のデータが許可されているので、このnonceを変えながら、hash関数で計算を繰り返し、最初のX桁が0になるのを狙っていきます。

let block = {
 version: 1,
 previousBlockHash: xxx,
 Timestamp: 123,
 difficulty: 8,
}
let nonce = 1;
while(true) {
 block.nonce = nonce;
 const hash = crypto.hash(block);
 if (hash.slice(0, block.difficulty).every(v => v === '0')) break;
 nonce += 1;
}

この計算をするために、莫大な設備や電気がかかります。しかし、一度生成されたものは、難易度さえわかっていれば、正しいブロックかどうかは1回のHash関数でわかるので、効率的に確認することが出来ます。正しいHashを見つける計算をすることをWork(仕事)と呼び、それだけの投資をした参加者だから、不正な行為はしないであろうという論理で動いています。

ちなみに、このhash競争には誰でも(ラズベリーパイくらいのマシンでも)参加出来ますし、試してみるのも面白いかもしれません。

また、hashの結果は1回で見つかるかもしれないですし、何度も繰り返さないといけない宝クジ要素があります。どこかで確立を計算したブログを見た気がしますが、宝クジを買ったほうがいいという結果だったと思います。ただ、ラズベリーパイを1台家において一攫千金12.5BTC (2019.12現在)を夢見て動かしておくといいかもしれません。

PoA (Proof of Authority)

PoAは、情報が公開されていない、もしくは、自由に参加することが出来ないブロックチェーン(プライベートなブロックチェーン)でよく使われています。
プライベートブロックチェーンでは、ネットワーク維持は、中央集権的に行われることが多いので、任意のブロック作成者がネットワーク管理者に選ばれます。

基本的には、ブロック作成の頻度が決まっていて、その時間割を、順番にブロック作成者の権利を持っている人が持ち回って作成します。

例えば、3つのkey(public-private keyペア)が新しいブロックを10秒毎に作れるとした場合、

const keys = [‘key-1’, ‘key-2’, ‘key-3’];
const block = {
 timestamp: 123,
 generatorPublicKey: ‘key-2’,
 signature: ‘sign’,
}
const slot = Math.ceil(block.timestamp / 10); // 13
const index = slot % 3;
Keys[index] === block.generatorPublicKey // true

上記のような計算で、どの時間のブロックがどのKeyで生成されるべきかが計算できます。
この場合のkeysは、ほぼ定数扱いになります。
また、この方法により、単一の参加者を分散的に決めることが出来、任意の参加者しか生成に参加できないので、不利益をもたらす参加者を考慮する必要はありません。

PoS (Proof of Stake)

Proof of Stakeは、Networkに対してどれだけ賭けているかが重視されるアルゴリズムです。代表的なプロジェクトとしてEthereum 2.0がPoSに移行しようとしています。ここで言う賭けとは主にどれだけネットワークのトークンを所持しているかになります。
PoSでは、

* 膨大な計算は必要ではないので、電気代も多くかかりません。
* 電気代がかからないということは、そこまで多くのコインを発行し続ける必要もありません。(PoWの場合は採掘を正当化するだけのコインを発行し続けないと成り立ちません。)
* PoWと比べて中央集権化しずらい面があります。(PoWは電気代の安い国に集中しがちになります)

PoSにおける大きな問題は、

* ブロック作成候補者の中から一人を選ぶ方法 (Stake grinding対策)
* Nothing at Stake問題

Stake grindingとは、ブロック作成候補者の中から一人を選ぶ際のパラメータをうまく利用して自分に有利に働くようにすることです。
例えば、単純にアカウントの所持トークンだけがパラメータになっていたとすると、自分のアカウントや他人のアカウントを自分が有利になるように変更するトランザクションを発行することが出来ます。
ですので、この選択方法は攻撃されにくいようにする必要があります。

Nothing at Stake問題とは、フォークが発生した場合に、複数のチェーンでブロックを生成することにコストがかからないということです。これは、フォークが解決するのが遅れたり、解決できなくなったりする大きな原因の一つです。PoWの場合は、複数のチェーンでブロックを生成しようとすると、その分の電気代がかかりこの問題は発生しません。
Liskでは、ダブルフォージング問題としてとりあげられています。

Stake grindingに代表される攻撃などを避けて、候補者の中から一人を選ぶ方法というのは、どのようにしてランダム関数のシード(種)を作り選ぶかというのが重要になってきます。
ただ、このランダムシードの作り方は、今でも活発に議論されている最中のトピックとなっています。

LIP-0022でも紹介されていますが、一つの例がこちらです。

またNothing at Stake問題を解決するために多くのプロジェクトでは、候補者になるためにデポジット(保証金)を必要としています。そして、複数のチェーンで同時にブロックを作るなどの違反行為をした場合は、その保証金が消えてしまいます。
基本的には、

1. 候補者リストを作る (候補者になるためのトランザクションを発行する、もしくは全ての保持者を候補者とする)
2. 候補者のトークン保持数をベースにランダム関数や条件などで分散的に一人のブロック作成者を選ぶ

この2ステップが大きな概念となっています。ブロック生成のタイミングは、上記のPoAと同じロジックで作ることが出来ます。

DPoS (Delegated Proof of Stake)

Delegated Proof of Stake は、PoSの派生です。Liskも、このアルゴリズムを採用しているプロジェクトですが、その他にもSteemやBitsharesなども採用しています。
PoSでの基本的な考え方は、どれだけTokenを保持しているかで生成者を決めるでしたが、それだと、より分散的になる一方候補者が無数に増えてします欠点があります。その欠点を補って、直接選挙制のように、候補者に対して投票をして、その投票をもってブロック作成者を決めるというのがDPoSの考え方です。
DPoSの問題点は、基本的にはPoSと同じですが、候補者が投票で決まるので、政治的要素が強くなり、上記の問題は政治的に解決出来るという側面もあります。

PoSに対してのDPoSの欠点は、より中央集権型に近づくというのが一番大きいところです。その代わりに、候補者の選択肢が少なくなり、パフォーマンスやスケーラビリティが変わってきます。

DPoSの大きな流れは、

1. 候補者になりたい人が立候補する
2. 立候補者に対して、他の人達が投票をする
3. 投票率に応じてブロック作成者を決める。

というようになっています。PoSに比べて、人為的要素ができますが、その代わりに、システムもシンプルになり、攻撃要素も少なくなります。

Lisk DPoS

ここまでは、アルゴリズムの概要を話してきましたが、Lisk DPoSが具体的にどう動くのかを話していきたいと思います。
また、ここで話すLisk DPoSは、未実装でLIP-0022とLIP-0023にて実装される予定です。
2019年11月に行われたLisk.jsでもその話にふれているのでこちらも参照してください。

また、LiskでVote報酬を得ている人やLisk Tokenを保持している人にも影響してくる話になります。

この変更を通じて、さらに平等に候補者になる機会が出来て、システムのパフォーマンスも上がるという内容になっています。上記の、大きな流れを元に順に説明していきます。

候補者になりたい人が立候補する
こちらは立候補をする(Delegate Registration)のトランザクションですることが出来ます。
トランザクションの実装はシンプルで、ユーザー名を決めるだけのアクションです。

{
 username: 'genesis_1',
}

立候補者に対して、他の人達が投票をする
こちらも、トランザクションでの実装で、誰に対して、どれだけのトークンで支持するかというデータのトランザクションを作ります。ただし、このトランザクションを発行した後で、このトークンを他のアドレスに移動して再度支持するというようなことが出来てしまうので、このトークンは使えない用にロックする必要があります。

{
 votes: [{ address: '123L', amount: '+10000' }]
}

さらに、ここで、Nothing at stake問題も関連してきます。立候補者は自分に対して投票をしないといけないルールが追加されました。そして、この投票に使われたトークンもロックされるので、立候補者はネットワークに対してデポジット(保証金)を積んでいるのと同じような効果があります。
ただし、Liskにおいては、なにか悪い行動を起こした場合でも、保証金を消すというルールではなく、保証金のロック期間を延長するという対処をしています。
また、立候補者と同じではないですが、投票者も、もし立候補者が悪い行動を起こした場合は、ある程度保証金のロック期間が伸びるので、注意して投票をしなければいけません。

投票率に応じてブロック作成者を決める。
Liskでは候補者が101アカウントありますが、それに加えてランダムに選ばれる2アカウントが追加されて合計103のアカウントがブロックの生成者になります。
この103の候補者リストは103ブロック毎に変更されていきます。
まず、101アカウントは、ランキング方式で投票率順で選んでいきます。残りの2アカウントは、トップ101を除いた全ての1000LSK以上投票されている立候補者を対象に投票率を加味したランダムで選んでいきます。
ここで使われるランダムシードは、LIP-0022で説明されているように、Randao schemeと呼ばれる分散的にランダムシードを作る手法が取られています。これは、ランダムシードが使用されるまでの202のブロックでブロック作成者がそれぞれランダムな数字を提案していきます。
そして、各作成者が提案したランダムな数字を計算式にいれてランダムシードを作ります。
この方法では、少なくとも101人中一人正直なブロック作成者がいれば良いランダムシードが作れるようになっています。

今までのLisk DPoSとの違い

* 投票時にトークンがロックされる。つまり、Liskの流通量が下がる
* 1Voteの価値が1LSKになる。以前は1Voteは101LSKの価値があった。
* チーム(カルテル)を作る意味がなくなった。
* TOP101でなくても、ブロックを作成出来るようになった。LIPでは、もし10000LSKの投票があった場合、50ブロック/月に作成出来ると予想されている
* 計算パフォーマンスが100倍以上あがっている

フォークが起きた場合、どのチェーンを選ぶのか

ブロック作成以外の時にコンセンサスが重要になってくるのは、フォークが起きた時です。
フォークが起きるパターンはいろいろありますが、例えば、ある作成者Aが間違って2つの内容が異なるブロックBとCを同時に作ってしまった場合
一定の他のノードは、Bを先に受け取りその他はCを先に受け取る
BとCの両方正しい作成者が作っている
このような場合に、次の作成者が、Bを先に受け取っていた場合はBの次にブロックを作りますが逆の場合は、Cの次にブロックを作ります。
そうした場合、

A <= B <= D
A <= C <= E

という2本のチェーンが出来上がります。これをフォークと呼びます。

以下ではこの問題を解決する、いくつかの有名なプロトコルを紹介していきます。

Longest chain rule

Longest chain rule は、PoWとのコンビネーションでよく使われています。とても、シンプルなルールで自分の知る限りで一番長いチェーンを選択します。
これは、PoWのブロックを作るためには計算量に伴う電気代を支払わなければいけません。ですので、一番コストがかかっているチェーンが一番支持されているチェーンとして成り立つのでLongest chain ruleが成り立ちます。

しかし、PoW以外のアルゴリズムでは、ブロックを作成するのに大きなコストはかかりません。ですので、Longest chain ruleを使用することは出来なくなります。

また、Longest chain ruleの不利な点として、ファイナリティ(ブロックが永久に消去されない)性質が確立的な保証しかありません。ブロックが、繋がれていくたびに確立が上がっていきますが100%にはなりません。

PoW以外のアルゴルズムでは、基本的に他のビザンティンフォールトトレランス(BFT)のアルゴリズムが使われています。

ビザンティンフォールトトレランス(BFT)とは

BFTとは、ビザンティン将軍問題を解決しているシステムを指します。LinkのWikipediaに詳しい解説が書いていますが、簡単に説明するとある都市を包囲している複数の将軍がその都市を攻略しようとしていますが、直接話すことは出来ません。そして、その中に裏切り者がいるかもしれないですし、伝達者が伝達に失敗する可能性があります。また、都市を攻略するためには一定の割合の将軍が同時に攻略する必要があります。その状況で、他の将軍と合意をして、都市に攻め入るのか攻め入らないかを決めなければなりません。
そして、BFTとはその伝達方法を決めたルールです。

これをブロックチェーンのシステムと置き換えると、情報がBlockで各ノードが将軍になり、Blockが遅延して届いたり、もしくは届かなかったり、悪意のあるノードであったりすると言えます。その中で、どのようにして正しくチェーンを繋いでいくかを決めているのがBFTのプロトコルになります。

Tendermint

Tendermintは、CosmosSDKにも使われている汎用的なBFTのプロトコルです。他との一番の大きな違いは、フォークフリーのプロトコルであるということです。つまり、新しいブロックをチェーンに繋ぐ前に合意形成を行い、合意が取れた場合のみ、新しいブロックをチェーンに繋ぐということをします。
このプロトコルは3つのフェーズによって行われます。

1. 誰かがブロックを提案する (propose)
2. 第1段階の投票をする (pre-vote)
3. 第2段階の投票をする (pre-commit)

全てのフェーズをパスしたものがチェーンに繋がれて、新しいブロックとされます。そして、新しいブロックはファイナリティがあり、どのようなケースでも消されることはありません。

このTendermintプロトコルの利点は、常にファイナリティがあるということです。しかし、逆に欠点は、毎ブロック最低1回はこの3フェーズが行われるので、ブロックを進めるのに時間がかかるということです。

Casper the Friendly Finality Gadget

Casper the Friendly Finality Gadget (Caspter FFG)は、Ethereum 2.0で提案されているBFTプロトコルです。こちらは、Tendermintにインスパイアされており基本的な考えは似ていますが、ブロックが止まることはありません。つまりフォークフル、Tendermintと違いフォークが存在するプロトコルになっています。
つまり、上記のフェーズ1(propose)とフェーズ2,3(pre-vote, pre-commit)が別れているプロトコルになっています。
投票フェーズ(2,3)は、毎ブロック行うと時間がかかりすぎてしまうので、チェックポイントごとにブロックに投票していきます。現状は、100ブロック毎という案がでているようです。

Lisk BFT

Lisk BFTは、もちろんLiskで採用しているBFTのプロトコルです。基本的な考え方自体は、TendermintやCapsterFFGと同じですが、EOSのBFTプロトコルにインスパイアされていて、ブロック自体にフェーズ2とフェーズ3の情報を書き込む手法をとっています。
実際には、ブロックに書き込まれている以下の2つのプロパティが重要で、
maxHeightPreviouslyForgedはフェーズ2の値を、maxHeightPrevotedはフェーズ3の値を計算するのに使われています。

{
　maxHeightPreviouslyForged: 300,
　maxHeightPrevoted: 200,
}

それにより、別のメッセージで投票フェーズをする必要がなくなり、ネットワークに対しての依存は他のプロトコルより少なくなります。
ただし、Lisk BFTはしばらくは同じブロックの作成者が続くというDPoSの特性の前提の上で成り立っているので、200ブロック内のブロック作成者が全員違うなどのケースでは上手くファイナリティを計算することが出来ません。

出典

あとがき

かなり、長くなりましたが以上がコンセンサスの回になります。
わかりにくいところ、もっと詳しく書いて欲しいところ等あれば、是非フィードバックをいただけると、追記、修正などをいたします。
実際、BFTのプロトコル周りは、論文を読み込んで読み込んで理解したつもりになれるレベルの複雑な話なので、僕自身も、Lisk BFT以外は概要レベルまでしか理解できていません。ただ、全体像がわかってしまえば、必要な時に都度、詳しく調べていけると思うのでブロックチェーンエンジニアを名乗る上では、概要と一つのプロトコルを深くわかっていれば十分かなと思います。

自己紹介

現在、LiskというNode.jsベースのブロックチェーンプロジェクトでリードエンジニアをしています。
今はベルリンに住んでいますが、大学の頃は、アメリカのシアトルとカナダのバンクーバーに住んでいて
ブリティッシュコロンビア大学の医療工学科を卒業しています。
大学の頃に、Web技術を学び始め、のめり込んで、日本のCyberagentという会社で、ゲームを中心に作っていました。
その後に、Liskに入る直前までは、ベルリンで会社を作るチャンスを日本のAPCという会社からからいただき、
レストランの電子メニューを作る事業をベルギーのスタートアップと共同で行っていました。

HTML, CSS、React, ReduxなどのWeb Front技術から、Unityなどを使ったゲーム開発、Node.js, Java, Golangなどを中心とした
モノリシックなサーバー開発やKubernates, Dockerなどを使ったマイクロサービスな基盤の準備、開発など
硬い技術から最新の技術までいろいろ触れる機会がありプロジェクトに恵まれ続けてここまで来ています。

仕事の依頼

仕事の依頼や質問等あればTwitterやDMでお願いします

この記事が気に入ったらサポートをしてみませんか？