見出し画像

インターネット・コンピュータ上でコンセンサスを実現する（和訳）

佐藤もとい

ブロックチェーンの新しいコンセンサスプロトコルの非同期最終化は信じられないほど速く、最終化は2秒以内に行われる。

元記事：Achieving Consensus on the Internet Computer

関連リンク：

Twitter：https://mobile.twitter.com/c3f_iu
まとめサイト：https://dfinity-c3f.softr.app/
イベント：https://c3f.connpass.com/event/

はじめに

インターネットコンピュータは、世界初のウェブスピード、インターネットスケールのパブリックブロックチェーンで、スマートコントラクトによりインタラクティブなウェブコンテンツをエンドユーザーのブラウザに直接安全に提供することを可能にします。インターネットコンピューターは、公共インターネットの機能を拡張し、ソフトウェアをホストできるようにすることで、次世代のDappsやオープンなインターネットサービスを実現します。
　
インターネットコンピューターは、世界中のデータセンターに設置されたマシンがICP（Internet Computer Protocol）を介して通信することで動作しています。このようにマシンが連携することで、仮想的なインターネット・コンピュータを形成し、開発者はキャニスター・スマートコントラクトと呼ばれるソフトウェアを安全かつ確実に作成・展開できるようになります。「安全」とは、キャニスターの状態がキャニスターのルールに従ってのみ変化し、改ざんされないことを意味し、「信頼性」とは、キャニスターが突然動かなくなることがないことを意味します。

インターネットコンピュータは、新しいコンセンサスプロトコルによってこれらの特性を実現しています。異なるマシン（レプリカ）は、どの入力をどのような順序で処理するかについて、首尾一貫した状態を維持するようなコンセンサスに達しなければなりません。各ソフトウェアは1台のマシンではなく、世界中の多くのマシンによって実行され、そのマシンの大多数がソフトウェアの真の状態を定義する。個々のレプリカが改ざんされた状態を報告したり、接続に問題があったり、悪意があったりしても、大多数のレプリカがソフトウェアを正しく実行している限り、違いは生じません。

さらに、Internet Computerのスケーラビリティ、つまり、キャニスター型スマートコントラクトの形で、より多くの分散型アプリケーションをプラットフォーム上で実行できるようにしたいと考えています。このスケーラビリティの要件を達成するために、私たちはキャニスターを小さなグループに分割し、各グループは私たちがサブネットと呼んでいる上で実行されます。サブネットは世界中のさまざまなレプリカによって運営されており、それらはすべてそのサブネット上で実行されているキャニスターを実行します。また、異なるサブネット上のキャニスターは安全に通信することができます。インターネット・コンピュータには、いつでもサブネットを追加することができ、それによってその容量を増やすことができるのです。

コンセンサスが重要な理由

大多数のマシンが正しく機能する限り、サブネットの正しい状態に影響を与えることなく、いくつものレプリカが利用できなくなったり、悪意をもったりする可能性があります。このようにレプリケーションを利用してセキュリティを確保するアプローチには、コンセンサスプロトコルが必要です。サブネットは異なるメッセージ、すなわちユーザーからキャニスターへのメッセージ、キャニスターからキャニスターへのメッセージを処理しなければならない。そして、すべてのレプリカが常に同じ状態になるように、同じメッセージを同じ順序で処理しなければなりません。しかし、サブネットを動かす各レプリカは、実際には異なる順序でメッセージを見ているかもしれません。そこで、サブネットを構成するすべてのノードが、処理するメッセージの順序に合意できるよう、コンセンサス・プロトコルを使用します。

ブロックチェーンを使ってコンセンサスを得ようとするのです。サブネットが処理すべきメッセージをまとめてブロックに入れ、各ブロックが前のブロックを指すことで、ブロックの連鎖が形成されます。すべてのレプリカがブロックチェーンに合意することで、実行すべきメッセージの順序が決まり、安全性が確保されます。

より正確には、私たちが「安全性」と呼ぶものが必要です。つまり、もし2人の正直なレプリカがある時点までのブロックチェーンに同意していると考えるなら、実際にはその時点までのブロックチェーンについて同じ見方をしているはずだということです。

2つ目は、ブロックチェーンが成長し続け、より多くのブロックに合意し続け、継続的に追加のメッセージを処理することを意味する「liveness」です。

3つ目は「有効性」で、これはすべてのブロックとブロック内のメッセージが実際に有効であることを意味します。例えば、ブロック内のすべてのメッセージが送信者によって正しく署名されていることを保証するものです。
ここで難しいのは、サブネットを構成するノードの一部が故障したり、オフラインになったり、あるいは積極的に悪意を持ったりしても、これら3つの特性が維持されるようにすることです。より正確には、サブネット内のノードの3分の1以下がオフラインまたは悪意を持っている限り、これらの特性はすべて維持されることが望まれます。以下の例では、4つのノードを使用することが多いので、そのうちの1つでも悪意があれば、これらのプロパティを満たすことになります。Genesisでは、インターネット・コンピュータは、1つ以上の破損したレプリカを許容できる、より大きなサブネットを使用する予定です。

➡連鎖鍵暗号方式:インターネット・コンピュータを支える科学的ブレークスルー

これから一つのサブネットにズームインし、ブロックチェーンを使ってどのようにコンセンサスを得るかを見ていきますが、インターネット・コンピュータは多くのサブネット、つまり多くのブロックチェーンで構成されていることを覚えておくことが重要です。私たちは、ピアツーピアのゴシップネットワークの上に構築されたものによって、私たちのコンセンサスプロトコルを紹介します。私たちはしばしば、レプリカが "このメッセージを送る "と言うでしょう。これは、ゴシップネットワークを使って、サブネット上の他のレプリカとメッセージを交換することを意味します。また、ここではメッセージの順序にのみ焦点を当てます。メッセージの処理については、プロトコルの他の部分が担当します。

コンセンサス・プロトコルは、インターネット・コンピュータのニーズに合わせて設計されたことに留意することが重要です。スループット、レイテンシー、そしてプロトコルのシンプルさを最適化しようとしているのです。このプロトコルは4つの主要な部分から構成されています。

  • まず、ブロック作成です。このパートでは、ブロックチェーンを構築するための候補となるブロックを作成します。

  • 2つ目は、公証です。この部分は、有効なブロックチェーンを構築するために、有効なブロックを識別する役割を担っています。

  • 3つ目は、ランダム・ビーコンです。ランダム・ビーコンは、私たちのプロトコルをさらに強化するために使用できるランダム性を与えてくれます。

  • 最後に、最終化です。これは、実際に合意に達したときに教えてくれるものです。

ブロック作成

サブネット上のレプリカはブロックメーカーとなり、チェーンを拡張するためのブロックを提案することができます。このサブネット上で動作するキャニスターが処理すべき、利用可能ないくつかのメッセージを持っていることでしょう。ある高さ（例えば29）までのブロックチェーンを持っているかもしれません。処理待ちのメッセージを集め、ブロックにまとめ、このゴシップネットワークで他のレプリカに送ることでブロックチェーンの拡張を提案します。

ここで重要なのは、一部の参加者が実際に悪さをしたとしても、このプロトコルが機能するようにしたい、ということです。つまり、ブロックチェーンを拡張するために1人のブロック製造者を選ぶことはできません。この1人のブロック製造者が実際に悪意を持っている可能性があり、私たちは動けなくなる可能性があるため、私たちのlivenessを損なうことになります。したがって、ブロックメーカーとなるレプリカを多数用意する必要があるのです。

公証、(レプリカがあるブロックを検証して有効だと確認すると公証シェア=暗号化された署名を当該ブロックにつける)

同じ理由で、これらのブロックプロポーザルは実際には無効である可能性があります。そのため、ラウンドごとに公証プロセスを行い、ブロックチェーンを拡張できる有効なブロックが少なくとも1つあることを保証しています。

例えば、レプリカ1が高さ29までの公証済みブロックチェーンを持っているとします。ここで、高さ30でブロックチェーンを拡張するブロックが見つかった場合、そのブロックを検証します。レプリカ1はこのブロックが有効であることを確認すると、公証シェアと呼ばれる暗号化された署名をこのブロックに付けます。公証シェアは他のレプリカとサブネットに送信され、レプリカ1がこのブロックを有効だと考えていることを表明します。

もしかしたら、レプリカ3とレプリカ4も同じブロックに公証シェアを作成するかもしれません。4つのレプリカのうち3つが十分な承認であると定義しておきましょう。この例では、4つのうち3つが、ノートの1つが誤動作したりオフラインになったりしてもプロトコルが進行するはずの、期待できる最高の承認率であることに注意してください。この3つの公証を1つの成果物にまとめ、これを公証と呼びます（ブロック30が公証されたことを意味します）。公証人は次のラウンドに進み、高さ31のブロックの検索を開始します。

この公証シェアには、マルチシグネチャと呼ばれる特別な署名を使用します。マルチシグネチャには、同じメッセージに対する多くの署名を、すべてのノードが署名したことを証明する単一の一定サイズの署名に圧縮できるという優れた性質がある。つまり、非常に大きなサブネットに多くの公証人がいたとしても、公証は小さな成果物となるのです。

公証は常に今説明したようにうまくいくとは限りません。レプリカは有効なブロックを見て、そのブロックに公証シェアを作成するかもしれません。しかし、同じ高さにある別の候補ブロックが表示され、それも有効である可能性があります。レプリカがどちらかのブロックにしか署名しない場合、ある公証人はあるブロックを支持し、別の公証人は別のブロックを支持し、どちらも十分な承認を得られないため、実際には行き詰まるかもしれません。このため、公証人は両方のブロックに実際に署名し、少なくともどちらかが公証されるようにします。つまり、1つの高さで複数の公証済みブロックを得ることができる。

ランダムビーコン

ブロックメーカーと公証人は有効なブロックを識別することができますが、すべての高さに複数の公証済みブロックが存在する可能性があるため、まだ合意には至っていません。最終的にブロックチェーン上で合意を得るために、私たちはランダムビーコンというものをプロトコルに追加することで、毎ラウンド得られる公証済みブロックの数を減らそうと考えています。

すべての高さで、ランダムビーコンと呼ぶ、予測できない値を持つランダムな外観のアーティファクトを持っています。
レプリカは高さ29にランダムビーコンを持ち、ラウンド29の公証処理が終了すると、次のランダムビーコンを作成する時が来たと判断します。レプリカは、前のランダム・ビーコンの値に対して、ランダム・ビーコン・シェアと呼ばれる特別な署名を作成します。これもゴシップネットワークを通じて共有するアーティファクトです。

もし、別のランダムビーコン共有が得られたら、次のランダムビーコン値を構築するために共有を結合することになる。これは特殊な署名、すなわち閾値BLS署名を用いて行われる。この署名は、どのレプリカが値を構成するのに参加しても一意であるという特殊な性質を持っている。しかし、レプリカが自分自身でその値を構成するため、予測不可能でもある。この閾値BLS署名には、当事者間で秘密鍵を共有する特殊な鍵素材が必要であり、我々は非対話型分散鍵生成と呼ばれるプロトコルを用いてこれを設定した。

このように共通のランダム性を得ることができたので、これを用いてブロックメーカーを毎ラウンドランク付けします。

例えば、23ラウンド目で作成したランダムビーコンを使って、24ラウンド目でブロックメーカーをランク付けします。ラウンド24では、レプリカ1が最優先のブロックメーカー（つまりランク0のブロックメーカー）であることに合意します。もちろん、Replica 1がうまく機能しないので、フォールバックが必要です。例えば、Replica 4をランク1のブロックメーカとして選択し、最初のフォールバックとします。そして、それがうまくいかない場合は、Replica 3をランク2のブロックメーカーにします。そして、最後の手段としてReplica 2が選ばれます。ランダム・ビーコンは共通のランダム性を提供するので、すべてのレプリカはこのブロック・メーカーの順序に同意します。

このブロックメーカーランキングを利用して、さらに公証人の動作を強化する。より正確には、公証人がラウンドに入ると、タイマーをスタートさせる。タイマーが始まると、ランク0の公証人がそのブロックの公証シェアを作成することだけを考えます。一定時間が経過して失敗した場合のみ、公証人はランク1のブロックメーカーからのブロック提案にフォールバックします。さらに時間が経つと、ランク2やランク3のブロックメーカーにフォールバックします。

公証人がブロック作成者のランクを考慮することで、毎ラウンド公証されるブロックの数を減らすことを目的としています。レプリカ1のラウンド30で、高さ30の有効なブロック案を受け取りましたが、ランク1のブロック作成者しかいませんでした。しかし、ランク1のブロックメーカーだけは、まだ署名する意志がないため、待つことになる。うまくいけば、ランク0のブロックメーカーからブロック案を受け取ることができます。さて、公証人はランク1のブロックではなく、このブロックに公証人のシェアを作りに行きます。もし、他の公証人も同じことをすれば、ランク0のブロックだけが完全に公証されることになります。このシナリオでは、公証されるブロックの数を実際に減らすことができます。これにより、合意形成に近づくことができます。

しかし、ほとんどのラウンドでは、ランク0のブロックメーカーから公証されたブロックは1つだけであることを期待します。実際、もし公証人が一人しかいなければ、私たちはすでに合意に達していないことになります。なぜなら、すべてのラウンドで公証されたブロックが有効な鎖として存在しなければならず、もしブロック候補が一人しかいなければ、その地点を通過するすべての鎖はそのブロックを経由しなければならないからです。したがって、そのブロックが暗示する連鎖は、実際に合意されたものでなければならないのです。

最終決定

だから、課題は残されている。合意に至らなかったことをどうやって知るか？レプリカがそのチェーンを受け入れることをどうやって確認するのか？一つの選択肢は、レプリカがある時間待つだけで、その時間後にはすべての公証済みブロックが存在しないと仮定し、ある高さで公証済みブロックが一つしかない場合、その高さまでで合意が得られたと見なすというものです。

しかし、これは非常に危険な方法です。もしかしたら、ネットワークが正常に機能しておらず、我々がまだ見ていない他の公証済みブロックが実際に存在するかもしれないのだ。つまり、十分に待たないと、安全性に問題が生じる可能性があるのです。このため、私たちは非常に難しい立場に立たされます。私たちは、ブロックが迅速に合意され、サブネットがユーザーのために反応することを望んでいますが、同時に、安全性を保証するために長い時間待つ必要があることも知っています。

そこで、合意を監視するために別のメカニズムを使用することで、トレードオフを実現しました。非同期の最終化プロセスを別途用意し、合意に達したことを検出するのに役立てます。公証人は、1つのブロックが完全に公証されたことを確認するまで公証シェアを行い、その時点で次のラウンドに移ることを思い出してください。ここで、公証人が何ブロック公証したかという情報を共有することで、合意形成に役立てることができます。より正確には、公証人が、そのラウンドで受け取った最初の公証ブロック以外のブロックについて公証シェアを作成しない場合、ファイナライズシェアと呼ぶ別の種類の署名を作成することになります。

レプリカ1からのHeight-30ブロックに対するファイナライズシェアは、レプリカ1がこのブロック以外のHeight-30ブロックに公証署名していないことを本質的に意味します。これは、残りのサブネットにゴマをする別のアーティファクトです。十分な数のレプリカが同じブロックのファイナライズシェアを作成した場合、それらを1つの最終化として集約することができます。ブロック上でこのようなファイナライズを見るたびに、その時点までのブロックチェーンを信頼できることがわかります。ファイナライズは、その高さの公証済みブロックが他に存在し得ないことを証明するものだからです。ネットワークがうまく振る舞えば、このようなファイナリゼーションシェアを素早く作って合意に至ることができるので、従来のブロックチェーンに比べて、実は非常に早くブロックの合意に至ることができることを意味します。この非同期ファイナライズのアプローチでは、提案されてから2秒以内にブロックをファイナライズすることができます。

さらに、ネットワーク攻撃のリスクもありません。ネットワークがうまく動作しなくても、署名にのみ依存し、すべてのメッセージを見たという仮定に依存しないため、安全であることが分かっています。

完全な最終化とは、サブネットのノードの3分の1以下が破損している限り、他の公証されたブロックが存在しないことを意味します。ブロックが確定した場合、4つのノードがあるため、3人の公証人がこのブロックにファイナライズシェアを作成したことになります。しかし、少なくとも2つのレプリカが正直で、そのブロックにファイナライズシェアを作成したことは確かです。また、正直なレプリカは、その高さの他のブロックに署名していない場合にのみ、そのようなファイナライズシェアを作成することも分かっています。

つまり、2つのレプリカは、この高さで確定したブロック以外のブロックの公証シェアを作成しなかったということです。また、公証には3つの公証シェアが必要なことも分かっています。つまり、3つのレプリカが参加しなければならないのですが、サブネットには4つのレプリカしかありません。さらに、そのうちの2つは他のブロックの公証に貢献していないことが明らかで、残り2つのレプリカしかありません。そして、この3つの公証のしきい値に達するには2つでは不十分で、それによって、最終化はその高さで他のブロックが公証されないことを意味するという証明を結論づけることになるのです。

これは、レプリカの3分の1以下が破損しているという仮定のもとで行われます。上記のデモでは、サブネットのサイズが4つで、破損したレプリカが最大1つであることを示しましたが、"f "が "n "の3分の1以下であれば、"f "が破損したレプリカのうち "n "に同じ議論を容易に拡張することができます。

まとめると、4つの要素からなるコンセンサスプロトコルを得ることができます。

  • ブロックメーカーがブロックチェーンを拡張するための候補ブロックを作成する。

  • 有効なブロックの識別を保証する公証プロセスを得る。

  • そしてランダムビーコンを使ってブロックメーカーをランク付けし、各ラウンドで得られる公証済みブロックの数を減らす。

  • 最後に、非同期ファイナライゼーション機構により、ネットワーク上の仮定に依存することなく、ブロックチェーンが実際に合意するタイミングを知ることができます。

このコンセンサス・プロトコルは、サブネット内での複製を可能にし、インターネットに求められるセキュリティと信頼性を達成することができるのです。

インターネット・コンピュータを支える技術の詳細については、今後のリリースにご期待ください。


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