本稿について
本稿では、Tendermint： Consensus without Miningの第6章「Consensus」のうち6.1「On Byzantine Consensus」、6.2「Algorithm」の日本語訳を掲載します。
原文はこちらになります。
※Tendermintホワイトペーパーの翻訳は第5回までで終了しますが、未完の部分があったり説明が簡潔過ぎると感じる部分があります。2016年6月にTendermintのCTOであるEthan Buchmanが発表している詳細な論文があるので、後日その論文からいくつか仕組み的に重要そうな部分を抜粋して翻訳するかもしれません。
スポンサードサーチ
6.コンセンサス
6.1 ビザンチンコンセンサスについて
Fischerらはその多大な影響を与えた論文[9]で、決定論的なプロセスの非同期システム（時間については何らの仮定も置かれていない）において、1つでも故障しているプロセスがある場合にコンセンサスを必ず形成できるプロトコルは存在しないことを示した。これは、FLP不可能性の結果と呼ばれる。問題のドメインを僅かに変更することでFLP不可能性の結果を回避する手段を解するべく多くの研究がなされた。例えば、決定性を犠牲にしたり、時間を追加したり、オラクルを加えたりなどの方法がそれにあたる[10]。Bitcoinはネットワークの同期と時間に関するいくつかの仮定（例：ノードはすぐにネットワークと同期する、マイナーは有限の時間とリソースを最良のブロックチェーンに費やす）を置くことでFLP不可能性の結果を迂回している。
Tendermintのアルゴリズムは、文献[4]（Dworkらによる）の第4章のアルゴリズム2'に基づいている。これは、部分的同期のネットワークを仮定していて、メッセージの伝送時間について何らかの未知の上界Δが存在すると仮定している。直観的に、ネットワークには任意だが有限のレイテンシが存在するだろう。また、Tendermintでは全てのビザンチンでないノードは、次のブロックについてのコンセンサスが形成されるまでの短い間、十分な正確性を維持できる内部時計を利用できるものと仮定する。このアルゴリズムは、ゴシップネットワーク上のブロックチェーンと協働するように適合させる。Dworkらが提案したアルゴリズムと同様に、最大1/3のビザンチンな投票パワーに対して耐性を持つことができる。
6.2 アルゴリズム
バリデータはブロックに対する投票に署名することでコンセンサスプロセスに参加する。投票には3つのタイプがある。すなわち、「事前投票（prevote）」「事前コミット（precommit）」「コミット（commit）」である。「2/3より多くのコミットを受け取る（receive more than 2/3 commits）」ことは、バリデータの2/3を占める集団からコミットを受け取ったことを意味する。バリデータの2/3を占める集団があるブロックに対して署名してブロードキャストした場合、そのブロックは「ネットワークによりコミットされた（be committed by the network）」という。
ブロックチェーンの各高さで、ラウンドベースのプロトコルが実行されて次のブロックが決定する。各ラウンドは3つのステップ（「提案（propose）」「事前投票」「事前コミット」）で構成されており、さらに2つの特別なステップ「コミット」と「新たなブロック高（NewHeight）」が伴う。「提案」「事前投票」「事前コミット」ステップそれぞれには、当該のラウンドに割り当てられている合計時間の1/3ずつかかる。各ラウンドは前のラウンドよりも小さいながら一定で増加する時間の分だけ長い。これにより、ネットワークは部分的同期のネットワークにおいて最終的にコンセンサスを形成できるようになる。
各ラウンドには、バリデータを投票パワーに比例する頻度で選ぶべく、ラウンドロビン方式で選ばれる指定の「提案者（proposer）」がいる[TODO: add algorithm to appendix]（筆者注：まだappendixに追加していないようです）。ブロック高Hのブロックチェーンと決定論的ラウンドロビンアルゴリズムを考えると、全てのノードが全てのラウンドに関する一連の提案者に合意することは明らかである。
最初のステップは「提案」ステップである。「提案」ステップの始めに、そのラウンドの指定の提案者はゴシップを介してピアに提案をブロードキャストする。もし提案者が過去のラウンドからのブロックにロックされている場合、提案者はそのロックされたブロックを提案するとともにその提案に「ロックの証明（proof-of-lock）」を含める（詳しくは後述）。「提案」ステップの間、全てのノードは隣接するピアに提案をゴシップで伝える。
「事前投票」ステップの始めに、各バリデータは意思決定を行う。もしバリデータが過去のラウンドからのブロックにロックされている場合、バリデータはそのロックされているブロックに対する事前投票に署名してブロードキャストする。もしくは、バリデータがその時点のラウンドについての受容可能な提案を受け取った場合、バリデータはその提案ブロックに対する事前投票に署名してブロードキャストする。バリデータが提案を受け取っていないかあるいは無効なブロックを受け取った場合、バリデータは特別な「空の（nil）」事前投票に署名する。「事前投票」ステップの間はロックは発生しない。「事前投票」の間、全てのノードはそのラウンドについての事前投票全てを隣接するピアにゴシップで伝える。
「事前コミット」ステップの始めに、各バリデータは意思決定を行う。もしバリデータが特定の受容可能なブロックに対する2/3より多くの事前投票を受け取った場合、バリデータはそのブロックに対する事前コミットに署名してブロードキャストする。また、バリデータはそのブロックをロックし、あらゆる過去のロックを解放する。ノードが一度にロックできるのは最大で1ブロックまでである。もしノードが2/3より多くの「空の」事前投票を受け取った場合、単純にロックを解除する。ロック（またはロック解除）をすると、ノードはロックしたブロック（または「空」）に対する事前投票を集めて「ロックの証明」に入れておき提案の順番が回ってくるまでとっておく。もしノードが2/3より多くの特定のブロック（または「空」）に対する事前投票を受け取らなかった場合、ノードは一切署名もロックもしない。「事前コミット」ステップの間、全てのノードはそのラウンドについての事前コミット全てを隣接するピアにゴシップで伝える。
「事前コミット」ステップの終わりに、各ノードは意思決定を行う。もしノードが特定のブロックに対する2/3より多くの事前コミットを受け取った場合、ノードは「コミット」ステップに突入する。そうでない場合は次ラウンドの「提案」ステップを継続する。ノードがネットワークにより事前コミットされたブロックをまだ受け取っていない場合であっても、ノードは「コミット」ステップに突入する。
「コミット」ステップは特別なステップである。2つの並列な条件があり、ラウンドをファイナライズする前にどちらも満たさなくてはならない。1つ目は、ノードがネットワークによりコミットされたブロックをまだ受け取っていない場合、それを受け取らねばならないというものである。バリデータがブロックを受け取ると、そのブロックに対するコミットに署名してブロードキャストする。2つ目は、ノードはネットワークによる事前コミットされたブロックに対して少なくとも2/3のコミットを受け取るまで待たねばならないというものである。両方の条件を満たすと、ノードはその時点の時間に「コミットタイム（CommitTime）」を設定し、「新たなブロック高」ステップに移行する。所与のブロック高のコンセンサスプロセスの間で時計が十分に正確であり続ける限り、時計に微妙に誤差が生じるにもかかわらず「コミットタイム」の非同期性とローカル性によりネットワークはコンセンサスを維持できるようになる。
ブロック高Hの最初のラウンド（ラウンド0）の前が「新たなブロック高」ステップで、このステップの目的はブロック高H-1で過去にコミットされたブロックに対する追加のコミットを集めることにある。ノードは「コミットタイム」を過ぎてから一定時間このステップに留まる。これによりブロック提案は最小値の2/3より多くのコミットを含めることができるようになるので、遅めのバリデータのコミットをブロックチェーンに含めることができる。
コンセンサスプロセスの任意の時点で、もしノードが特定のブロックに対する2/3より多くのコミットを受け取った場合、まだ「コミット」ステップに突入していなければすぐに突入する。ゆえに、「コミット」ステップへの入り方は2通りある。ラウンドRのブロックに対するコミット投票は、R < R'である全てのラウンドR'に対する事前投票や事前コミットとしてカウントする。コミット投票はその時点のラウンドやステップにかかわらず、バックグラウンドで隣接するピアにゴシップで伝える。
コンセンサスプロセスの任意の時点で、もしノードがラウンドRからのブロックにロックされていてR < R'であるラウンドR'の「ロックの証明」を受け取った場合、そのノードはロック解除される。
（Tendermintホワイトペーパー日本語訳2 ←← 前）｜（次 →→ Tendermintホワイトペーパー日本語訳4）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。