Achieving Consensus on the Internet Computer
インターネット・コンピューターのビジョンには、セキュリティと信頼性が不可欠です。インターネット・コンピューターは、世界初のウェブスピード、インターネットスケールのパブリックブロックチェーンであり、スマートコントラクトにより、エンドユーザーのブラウザに直接、インタラクティブなウェブコンテンツを安全に提供することができます。インターネット・コンピューターは、パブリックインターネットの機能を拡張し、ソフトウェアをホストできるようにすることで、次世代のDappsやオープンインターネットサービスを可能にします。
インターネット・コンピューターは、世界中のデータセンターに設置されたマシンが、インターネット・コンピューター・プロトコル（ICP）を介して通信することで動作しています。このようにマシンが連携することで、バーチャルのインターネット・コンピューターが形成され、開発者はキャニスター・スマートコントラクトと呼ばれるソフトウェアを安全かつ信頼性の高い方法で記述し、展開することができます。「安全」とは、キャニスターの状態が、キャニスターのルールに従ってのみ変化し、改ざんされないことを意味し、「信頼性」とは、キャニスターが突然停止しないことを意味します。
インターネット・コンピューターは、新しいコンセンサスプロトコルを用いてこれらの特性を実現しています。つまり、異なるマシン（レプリカ）は、どの入力をどのような順序で処理するかについてコンセンサスを得なければならず、その結果、コヒーレントな（首尾一貫した）状態を維持することができます。すべてのソフトウェアは、1台のマシンではなく、世界中の多数のマシンによって実行され、その大多数のマシンがソフトウェアの真の状態を決定します。個々のレプリカが改ざんされた状態を報告したり、接続に問題があったり、あるいは悪意があったりしても、大多数のレプリカが正しくソフトウェアを実行している限り、間違いはありません。
さらに、インターネット・コンピューターには拡張性を持たせようと考えられています。つまり、キャニスター・スマートコントラクトの形で、より多くの分散型アプリケーションをこのプラットフォーム上で実行できるようにしたいということです。このスケーラビリティ要件を達成するために、キャニスターをより小さなグループに分割し、各グループはサブネットと呼ばれる場所で実行されます。サブネットには、世界中のさまざまなレプリカが搭載されており、それらのレプリカはすべて、そのサブネット上で実行されるキャニスターを実行します。異なるサブネット上のキャニスターは、安全に通信することもできます。インターネット・コンピューターには、いつでもサブネットを追加することができ、それによって容量を増やすことができます。
□コンセンサスが重要な理由
いくつものレプリカが利用できなくなったり、悪意を持つという可能性がありますが、大多数のマシンが正常に機能している限り、サブネットの正しいステータスに影響を与えることはありません。レプリカを利用してセキュリティを確保するこの方法には、コンセンサス・プロトコルが必要です。サブネットは異なるメッセージ、すなわちユーザーからキャニスターへのメッセージとキャニスターからキャニスターへのメッセージを処理しなければなりません。そして、すべてのレプリカが常に同じ状態になるように、同じメッセージを同じ順番で処理しなければなりません。しかし、サブネットを構成する各レプリカは、実際には異なる順番でメッセージを見ているかもしれません。そこで、サブネットを構成するすべてのノードが、処理するメッセージの順序に合意できるように、コンセンサス・プロトコルを使用します。
コンセンサスを得るためには、ブロックチェーンを利用します。サブネットが処理すべきメッセージをまとめてブロックに入れ、各ブロックが前のブロックを指し示すことで、ブロックのチェーンを形成します。すべてのレプリカがブロックチェーンに合意することで、実行すべきメッセージの順序付けがなされ、セキュリティの特性が達成されます。
より正確には（第一に）、私たちが「安全性」と呼んでいるものを求めています。つまり、2つの正直なレプリカが、ある時点までのブロックチェーンについて同意していると考えている場合、実際には、その時点までのブロックチェーンについては同じ見解を持っているはずです。
第二に、私たちは「継続性」を求めています。これは、ブロックチェーンが成長し続け、より多くのブロックに合意し続け、追加のメッセージを継続的に処理することを意味しています。
3つ目は、「妥当性」と呼ばれるもので、すべてのブロックとブロック内のメッセージが実際に有効であることを意味しています。例えば、ブロック内のすべてのメッセージが送信者によって正しく署名されていることを保証します。
ここで難しいのは、サブネットを動かしているノードの一部が故障したり、オフラインになったり、あるいは積極的に悪意を持っていたとしても、これらの3つの特性が保たれるようにすることです。正確には、サブネット内のノードの3分の1以下がオフラインになったり、悪意を持っていたりする限り、これらの特性がすべて保たれるようにしたいのです。以下の例では、4つのノードを使用することが多いので、せいぜい1つのノードが悪意を持っていれば、これらのプロパティを満たすことができます。Genesisでは、インターネット・コンピュータが、1つ以上の破損したレプリカを許容できる、より大きなサブネットを使用します。
ここでは、単一のサブネットに注目して、ブロックチェーンを使って合意に達する方法を見ていきますが、インターネット・コンピューターは多くのサブネットで構成されており、したがって多くのブロックチェーンで構成されていることを覚えておくことが重要です。私たちのコンセンサスプロトコルは、ピアツーピアのゴシップネットワークの上に構築して提示します。私たちはよく、レプリカが "このメッセージを送信する "と言います。これは、ゴシップネットワークを使って、サブネット上の他のレプリカとメッセージを交換することを意味しています。また、ここではメッセージの順序にのみ注目します。メッセージの処理は、プロトコルの他の部分で行います。
ここで重要なのは、コンセンサス・プロトコルをインターネット・コンピューターのニーズに合わせて設計したことです。スループット、レイテンシー、そしてプロトコルのシンプルさを最適化しようとしています。このプロトコルには4つの主要部分があります。
・まず、ブロック作成です。この部分では、ブロックチェーンを構築するための候補ブロックを作成します。
・2つ目は、「公証」です。この部分は、有効なブロックチェーンを構築するために、有効なブロックを特定する役割を果たします。
・3つ目は、「ランダムビーコン」です。ランダムビーコンは、プロトコルをさらに強化するために使用できるランダム性を与えてくれます。
・最後に、最終的に合意に達したかどうかを示すファイナライゼーションがあります。
1. ブロック作成
サブネット上のレプリカはブロックメーカーとして、チェーンを拡張するブロックを提案することができます。このサブネット上で動作するキャニスターが処理すべきメッセージが用意されています。それは、ある高さ（例えば、29）までのブロックチェーンを持っているかもしれません。処理を待っているメッセージを集めてブロックにまとめ、このゴシップネットワークで他のレプリカに送ることでブロックチェーンの拡張を提案します。
ここで重要なのは、一部の参加者が実際に悪さをしていても、このプロトコルが機能するようにしたいということです。つまり、ブロックチェーンを拡張するために1人のブロックメーカーを選出することはできません。なぜなら、この1人のブロックメーカーが実際に悪意を持っている可能性があり、我々は立ち往生してしまい、継続性が損なわれてしまうからです。そのため、多くのレプリカがブロックメーカーとしての役割を果たす必要があります。
2. 公証について
同じ理由で、これらのブロック提案は実際には無効かもしれません。これに対処するために、ラウンド制の公証プロセスを採用しており、各ラウンドにおいて、ブロックチェーンを拡張できる有効なブロックが少なくとも1つあることを保証しています。
例えば、Replica 1のブロックチェーンは高さ29まで公証されているとします。ここで、高さ30でブロックチェーンを拡張するブロックを見つけた場合、そのブロックを検証することになります。レプリカ1がこのブロックが有効であると判断した場合、レプリカ1はそのブロックに公証シェアと呼ばれる暗号署名を行います。公証シェアは他のレプリカとサブネットに送信され、レプリカ1がこのブロックを善良なものと考えていることを表現します。
もしかしたら、レプリカ3とレプリカ4も同じブロックに公証シェアを作成するかもしれません。4つのレプリカのうち3つが十分な承認であると定義しましょう。この例では、4つのうち3つが最も高い承認率であることに注意してください。ここでは、1つのノートが誤動作したりオフラインになったりしても、プロトコルが進行するはずです。この3つの公証シェアを1つの成果物にまとめて「公証」と呼びます。つまり、ブロック30が公証されたことになります。公証人は次のラウンドに進み、身長31のブロックを探し始めます。
この「公証」には、「マルチシグネチャ」と呼ばれる特別な署名を使用します。マルチシグネチャには、同じメッセージに対する多くの署名を圧縮して、すべてのノードがメッセージに署名したことを証明する一定サイズの単一の署名にすることができるという優れた特性があります。つまり、非常に大きなサブネットに多くの公証人がいたとしても、公証は小さな成果物になるということです。
公証は、先ほど説明したようにうまくいくとは限りません。レプリカは有効なブロックを見つけ、そのブロックに公証共有を作成するかもしれません。しかし、今度は同じ高さにある別の候補ブロックを見て、それも有効だと判断してしまうかもしれません。レプリカがどちらかのブロックにしか署名しない場合、ある公証人があるブロックを支持し、他の公証人が別のブロックを支持することになり、どちらも十分な承認を得られないため、実際には行き詰まってしまうかもしれません。活性化特性を満たすために、公証人は実際に両方のブロックに署名し、少なくともどちらかのブロックが公証されるようにしています。これは、1つの高さで複数の公証済みブロックを得ることができることを意味します。
3. ランダムビーコン
ブロックメーカーと公証人は有効なブロックを識別することができますが、高さごとに複数の公証されたブロックが存在する可能性があるため、まだ合意に達していません。最終的にブロックチェーン上での合意を得るために、プロトコルに「ランダムビーコン」というものを追加して、ラウンドごとに得られる公証済みブロックの数を減らそうとしています。すべての高さに、ランダムビーコンと呼ばれるランダムな見た目の人工物があり、それは予測不可能な値を持っています。
レプリカは高さ29にランダム・ビーコンを持ち、ラウンド29の公証処理が終わると、次のランダム・ビーコンを作る時期だと判断します。レプリカは前のランダム・ビーコンの値に特別な署名を作成し、これをランダム・ビーコンの共有と呼びます。これは、ゴシップネットワークを介して共有されるもう一つの成果物です。
次に、別のランダム・ビーコン・シェアを得た場合、そのシェアを組み合わせて次のランダム・ビーコン値を構築することができます。これには、特別な署名、すなわち閾値BLS署名を使用します。この署名は一意であるという特別な性質を持っています。つまり、どのレプリカが値を構築するために参加するかは関係ありません。しかし、レプリカが単独でその値を構築することはできないため、予測不可能でもあります。この閾値BLS署名には、秘密鍵を共有する特別な鍵が必要です。この鍵は、非対話型分散鍵生成と呼ばれるプロトコルによって設定されます。
さて、この共通のランダム性を手に入れたので、それを使ってラウンドごとにブロックメーカーをランク付けしていきます。
例えば、ラウンド23で作成したランダムなビーコンを使って、ラウンド24でブロックメーカーの順位を決定します。ラウンド24では、レプリカ1が最優先のブロックメーカー（つまり、ランク0のブロックメーカー）であることが確認できます。もちろん、レプリカ1が適切に仕事をしないかもしれないので、フォールバックが必要です。例えば、レプリカ4がランク1のブロックメーカーとして選ばれ、最初の予備となります。そして、それがうまくいかない場合は、レプリカ3がランク2のブロックメーカーになります。そして最終的には、レプリカ2が最終手段となります。ランダム・ビーコンは共通のランダム性を提供するので、すべてのレプリカはこのブロック・メーカーの順序に同意します。
これから、このブロックメーカーの順位を使って、公証人の行動をさらに強化します。具体的には、公証人がラウンドに参加する際、タイマーをスタートさせます。タイマーの開始時には、ランク0のブロックメーカーによるブロックの公証シェアを作成することだけを考えます。一定時間後にそれが失敗した場合のみ、公証人はランク1のブロックメーカーによるブロック提案に戻ります。さらに一定の時間が経過すると、ランク2やランク3のブロックメーカーへとさらに後退します。
このように、公証人がブロックメーカーのランクを考慮することで、毎ラウンドの公証ブロック数を減らすことが目標となります。一例を見てみましょう。レプリカ1はラウンド30で、高さ30の有効なブロックプロポーザルを受け取りましたが、ブロックメーカーのランクは1しかありませんでした。レプリカ1は、まだランク1のブロックに署名する気はないので、待つことにします。上手くいけば、今度はランク0のブロックメーカーからブロックプロポーザルを受け取るかもしれません。ここで公証人は、ランク1のブロックではなく、このブロックに公証シェアを作成します。他の多くの公証人が同じことをすれば、ランク0のブロックだけが完全に公証されることになります。このシナリオでは、実際に公証されるブロックの数が減りました。これにより、コンセンサスに近づくことができます。
現在、一部のラウンドではまだ複数の公証済みブロックが存在するかもしれませんが、うまくいけばほとんどのラウンドで、ランク0のブロックメーカーの公証済みブロックは1つだけになります。実際、公証人が1人しかいない場合は、すでに合意に達していると考えられます。なぜなら、すべてのラウンドで公証されたブロックの有効なチェーンが存在しなければならず、もし候補となるブロックが1つしかなければ、その地点を通過するすべてのチェーンはそのブロックを経由しなければならないからである。したがって、そのブロックによって暗示されるチェーンは、実際に合意されたものでなければならない。
4. ファイナライゼーション
そこで、課題が残ります。合意に達したことをどうやって知ることができるのか？レプリカはどのようにしてそのチェーンを受け入れることができるのでしょうか？一つの方法は、レプリカがある時間だけ待って、その間に存在するすべての公証されたブロックを見たと仮定し、ある高さに1つだけ公証されたブロックがあれば、その高さまでのチェーンは合意されたとみなすというものです。
しかし、これは非常にリスクの高い方法です。もしかしたら、ネットワークが正常に機能しておらず、単にまだ見ていないだけで、実は他にも公証済みのブロックがあるかもしれません。つまり、十分に待たないと、安全性を侵害してしまう可能性があるのです。つまり、サブネットがユーザーに対応できるように、ブロックが迅速に合意されることを望んでいますが、同時に、安全性を保証するためには長い時間待つ必要があることもわかっています。
このトレードオフを回避するために、合意を監視するための別のメカニズムを使用しています。合意に達したことを検知するために、非同期の最終処理を別途用意しています。公証人は1つのブロックが完全に公証されたことを確認するまで公証シェアを作成し、その時点で次のラウンドに移ることを覚えておいてください。ここでは、公証人が何ブロックを公証したかという情報を共有してもらい、合意に達することを目指します。より正確には、公証人がそのラウンドで受け取った最初の公証済みブロック以外のブロックに対して公証シェアを作成しなかった場合、ファイナライゼーション・シェアと呼ばれる異なるタイプの署名を作成します。
レプリカ1の高さ30のブロックに対するファイナライゼーション・シェアは、基本的に、レプリカ1がこのブロック以外の高さ30のブロックには署名しなかったことを意味する。これもまた、残りのサブネットにゴッソリ入ってしまうアーティファクトです。十分な数のレプリカが同じブロックのファイナライズシェアも作成していれば、それらを1つのファイナライズに集約することができます。ブロックにこのようなファイナライズが表示されると、その時点までのブロックチェーンを信頼できることがわかります。ファイナライズは、その高さの公証済みブロックが他に存在しないことを証明するものだからです。ネットワークがうまく機能していれば、従来のブロックチェーンに比べて、非常に早くブロックの合意に達することができるということです。この非同期型のファイナライズ手法では、ブロックが提案されてから1秒以内にファイナライズすることができます。
また、ネットワーク攻撃のリスクもありません。ネットワークの挙動が悪くても、すべてのメッセージを見たという前提ではなく、署名だけに頼っているので、安全性は確保されています。
完全なファイナライズとは、サブネットのノードの3分の1以下が破損している限り、他の公証されたブロックは存在できないということです。少し理論的に、4つのノードがあるシナリオで実際にそうなる理由を見てみましょう。あるブロックがファイナライズされた場合、ノードが4つあるので、3人の公証人がそのブロックにファイナライズシェアを作成したことになります。そのうちの1つが破損していると仮定しますが、それでも少なくとも2つのレプリカが正直者で、そのブロックにファイナライズシェアを作成したことが確実にわかることになります。また、正直者のレプリカは、その高さのブロックに署名しなかった場合にのみ、このような確定シェアを作成することがわかっています。
つまり、2つのレプリカは、この高さで確定したブロック以外のブロックに対して、公証シェアを作成しなかったことになります。また、公証には3つの公証シェアが必要であることもわかっています。つまり、それに到達するには3つのレプリカが参加しなければなりませんが、サブネット上には4つのレプリカしかありません。さらに、そのうちの2つは間違いなく他のブロックの公証に貢献していないと言いましたが、これでは2つのレプリカしか残りません。そして、2個ではこの公証化の閾値である3個に達することができず、それによって、最終化はその高さに他の公証化されたブロックがないことを意味するという証明を結論づけています。
これは、レプリカの3分の1以下が破損しているという仮定の下での話です。上記のデモンストレーションでは、4つのレプリカのうち破損しているのはせいぜい1つというサブネットサイズを使用しましたが、"n "個のレプリカのうち "f "個が破損している場合でも、"f "が "n "の3分の1以下であれば、同じ議論を簡単に拡張することができます。
以上を要約すると、コンセンサス・プロトコルは以下の４つの要素から成り立っているということになります。
①ブロックメーカーは、ブロックチェーンを拡張するための候補ブロックを作成します。
②有効なブロックを確実に識別するための公証プロセスがあります。
③次に、ランダムなビーコンを追加してブロックメーカーをランク付けし、各ラウンドで得られる公証ブロックの数を減らします。
④最後に、非同期のファイナライジングメカニズムを使用することで、ネットワークの仮定に頼ることなく、ブロックチェーンが実際に合意されたことを知ることができます。
このコンセンサス・プロトコルにより、サブネット内での複製が可能となり、インターネット・コンピュータに求められるセキュリティと信頼性を実現しています。