Dfinityホワイトペーパー和訳（April 19, 2022）

佐藤もとい

2022年7月27日 18:08

ギークのためのインターネット・コンピュータ(v1.3)

DFINITYチーム
2022年4月19日

元記事：The Internet Computer for Geeks (v1.3)
（https://dfinity.org/whitepaper.pdf）

ざっくりと和訳です。ご了承して利用いただければと思います。

★数式表記については、noteで表現が難しいものがあるため原文参照のうえご利用ください。

概要

スマートコントラクトは、ソフトウェアの記述方法、ITシステムの保守方法、アプリケーションやビジネス全体の構築方法に革命をもたらす、新しい形態のソフトウェアです。スマートコントラクトは、分散型ブロックチェーン上で動作する、構成可能で自律的なソフトウェアの断片であり、改ざんが不可能で止められないものとなっている。

本論文では、従来のブロックチェーン上のスマートコントラクトの速度、ストレージコスト、計算能力に関する制限を克服し、スマートコントラクトの潜在能力を最大限に引き出す、ブロックチェーンの根本的な新しいデザインであるインターネットコンピュータ（IC）について説明します。これにより、スマートコントラクトは初めて、ブロックチェーン上でエンドツーエンドでホストされる完全分散型アプリケーションを実装することができるようになりました。

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

ICは、独立して動作するノードをブロックチェーンの集合体に接続する暗号プロトコルのセットで構成されています。これらのブロックチェーンは、ICのスマートコントラクトの一種である「Canister」をホストし、実行します。Canisterは、データを保存し、そのデータに対して非常に一般的な計算を実行し、完全な技術スタックを提供し、エンドユーザーに直接ウェブページを提供することができます。Canisterの開発者は、ICのネイティブ・トークンであるICPから得られるサイクルでコストを前払いする「リバースガスモデル」によって、計算とストレージのコストをまかなうことができます。ICPトークンはガバナンスにも使用されます。ICは分散型自治組織（DAO）によって統治され、特にネットワークのトポロジーの変更やプロトコルのアップグレードを決定します。

1 はじめに

1.1 スマートコントラクトの実現

スマートコントラクトは、そのユニークな特徴から、アプリケーションがユーザーによって完全に制御され、分散型ブロックチェーンプラットフォーム上で実行されるWebの新しいアプローチであるWeb3を実現する鍵となるものである。

このような分散型アプリケーション（Dapps）は、一般的にトークン化されており、Dappsに参加することでトークンがユーザーに配布されます。参加形態は様々で、モデレーターやコンテンツの提供、ダップの運営、ダップの作成・保守など多岐にわたります。通常、トークンは取引所で購入することができます。実際、トークンの売却は、アプリ開発の資金調達の一般的な方法となっています。また、トークンは、アプリが提供するサービスやコンテンツに対する対価として利用されることもあります。

今日のブロックチェーンプラットフォーム上で動作するスマートコントラクトは、一般的なもの（Ethereumなど）を含め、多くの制限に悩まされています。その結果、多くの一般的なブロックチェーンアプリケーションは完全な分散型ではなく、アプリケーションの大部分を従来のクラウドプラットフォームでホストし、全体の機能のごく一部をブロックチェーン上のスマートコントラクトに呼び出すというハイブリッド型になっています。残念ながら、このようなアプリケーションは非中央集権的であり、クラウドプロバイダーの意のままになり、多くの単一障害点に対して脆弱であるなど、従来のクラウドホスト型アプリケーションの欠点の多くを抱えることになる。

インターネットコンピュータ（IC）は、スマートコントラクトを実行するための新しいプラットフォームです。ここでいう「スマートコントラクト」とは、広義には、非中央集権的な公共ネットワーク上で自律的に実行される、汎用的で改ざんされないコンピュータプログラムである。

・汎用性（general purpose）とは、スマートコントラクトプログラムのクラスがチューリング完全であること（つまり、計算可能なものはすべてスマートコントラクトによって計算可能であること）を意味します。
・ 改ざん防止（tamperproof）とは、プログラムの命令が忠実に実行され、中間結果や最終結果が正確に保存・送信されることを意味します。
・自律的（autonomous）とは、スマートコントラクトがネットワークによって自動的に実行され、個人のアクションが不要であることを意味します。
・非中央集権的な公共ネットワーク（a decentralized public network）とは、一般にアクセス可能で、地理的に分散しており、少数の個人または組織の支配下にないコンピュータのネットワークを意味します。

また、スマートコントラクトは、

・コンポーザブル（Composable）
コンポーザブルであり、互いに相互作用することが可能です
（➡コンポーサブル：アプリケーションをモジュール化することで、アプリケーション全体を変更せずに部分的に変更できるアーキテクチャー）
・トークン化をサポート（support tokenization）
つまり、デジタル・トークンを使用し、取引することができます。

既存のスマートコントラクトプラットフォームと比較して、ICは以下のように設計されています。

・費用対効果（be more cost effective）
特に、アプリケーションの計算とデータ保存を従来の数分の一のコストで可能にします
・スマートコントラクトのトランザクション処理において、より高いスループットと低いレイテンシーを提供する。
・スケーラビリティの向上（be more scalable）
ネットワークにノードを追加することによって容量を増やすことができるので、ICは無限の量のスマートコントラクトデータと計算をネイティブに処理できる

スマートコントラクトが持つもう一つの特性は不変性(immutability)です。これは、一度導入されたスマートコントラクトのコードは、当事者が一方的に変更できないことを意味します。この機能は一部のアプリケーションでは必須ですが、すべてのアプリケーションで必要なわけではありません。また、スマートコントラクトに修正すべきバグがある場合、問題になる可能性もあります。ICは、スマートコントラクトのミュータビリティポリシーとして、純粋なイミュータブルから一方的にアップグレード可能なものまで、様々なオプションを許容しています。

ICは、スマートコントラクトのプラットフォームとしてだけでなく、完全な技術スタックとして機能するように設計されており、IC上で全て動作するシステムやサービスを構築することが可能です。特に、IC上のスマートコントラクトは、エンドユーザーが作成したHTTPリクエストを処理できるため、スマートコントラクトが直接インタラクティブなWebエクスペリエンスを提供することができます。つまり、企業のクラウドホスティングサービスやプライベートサーバーに依存しないシステムやサービスを構築することができ、スマートコントラクトのメリットを真のエンドツーエンドで提供することができるのです。

Web3のビジョンを実現する.
エンドユーザーにとって、ICベースのサービスへのアクセスは、ほぼ透明(transparent)である。個人情報は、パブリッククラウドやプライベートクラウド上のアプリケーションにアクセスする場合よりも安全ですが、アプリケーションとのインタラクションの体験は同じものです。

一方、ICベースのサービスを作成・管理する側にとっては、最新のアプリケーションやマイクロサービスの開発・展開に伴うコスト、リスク、複雑性の多くをICが解消してくれます。

例えば、ICプラットフォームは、インターネットを独占している大規模なテクノロジー企業による統合に代わる選択肢を提供します。さらに、その安全なプロトコルは、ファイアウォール、バックアップ設備、負荷分散サービス、フェイルオーバー・オーケストレーションに頼ることなく、信頼できるメッセージ配信、透明な説明責任、レジリエンス（➡脅威への対応能力）を保証します。

ICの構築は、インターネットをそのオープン、革新的、創造的なルーツに戻すこと、言い換えればWeb3のビジョンを実現することです。いくつかの具体例に焦点を当てると、ICは以下のようなことを行います。

・相互運用性、共有機能、永続的なAPI、オーナーレスアプリケーションをサポートし、これらすべてがプラットフォームのリスクを低減し、イノベーションとコラボレーションを促進する。
・データを自動的にメモリに永続化することで、データベースサーバーやストレージ管理が不要になり、計算効率が向上し、ソフトウェア開発が簡素化される。
・IT組織が統合し管理する必要のある技術スタックを簡素化し、運用効率を向上させる

1.2 インターネット・コンピュータの上位概念

第一近似として、ICは相互作用する複製されたステートマシン（状態遷移マシン）のネットワークであると言えます。複製されたステートマシンの概念は、分散システムにおいてかなり標準的な概念であるが [Sch90]、ここでは、ステートマシンの概念から簡単に紹介する。

ステートマシンは計算の特殊なモデルである。このようなマシンは状態を維持し、それは通常のコンピュータにおけるメインメモリや他の形式のデータストレージに相当する。このようなステートマシンは離散的なラウンドで実行される。各ラウンドでは、入力を受け取り、入力と現在の状態に状態遷移関数を適用して、出力と新しい状態を得る。新しい状態は、次のラウンドで現在の状態となる。

ICの状態遷移関数は普遍関数である。つまり、状態に格納される入力やデータの一部は、他の入力やデータに対して作用する任意のプログラムであってもよいということである。したがって、このようなステートマシンは、計算の一般的な（すなわち、チューリング完全な）モデルを表している。

耐障害性を実現するために、ステートマシンは複製されることがある。複製（replicate）されたステートマシンは、それぞれが同じステートマシンのコピーを実行しているレプリカのサブネットで構成されます。サブネットは、一部のレプリカに不具合があっても機能し続け、正しく機能しなければなりません。サブネット内の各レプリカは、同じ入力を同じ順序で処理することが重要です。これを実現するために、サブネット内のレプリカはコンセンサスプロトコル[Fis83]を実行して、サブネット内の全レプリカが同じ順序で入力を処理することを保証しなければなりません。したがって、各レプリカの内部状態は時間とともに全く同じように変化し、各レプリカは全く同じ順序の出力を生成することになります。IC上の複製されたステートマシンの入力は、外部のユーザーが生成した入力である場合もあれば、別の複製されたステートマシンが生成した出力である場合もあることに注意してください。同様に、複製されたステートマシンの出力は、外部ユーザーに向けられた出力である場合もあれば、別の複製されたステートマシンへの入力である場合もある。

1.3 故障モデル

コンピュータサイエンスの分散システム分野では、通常、クラッシュ故障とビザンチン故障という2種類のレプリカ故障を考える。クラッシュ故障は、レプリカが突然停止し、再開しない場合に発生する。ビザンチン故障とは、レプリカが規定のプロトコルから任意に逸脱する可能性がある故障のことである。さらに、ビザンチン故障では、1つまたは複数のレプリカが悪意のある敵の直接制御下に置かれ、それらのレプリカの振る舞いを調整される可能性がある。この2種類の障害のうち、ビザンチン障害の方がはるかに破壊的である可能性がある。コンセンサスや複製されたステートマシンを実現するためのプロトコルは、通常、どれだけのレプリカに欠陥があるか、どの程度（クラッシュまたはビザンチン）欠陥があるかについて仮定します。ICでは、与えられたサブネットがn個のレプリカを持つ場合、これらのレプリカのうちn/3個未満が故障し、これらの故障はビザンチンかもしれないという仮定があります。

1.4 通信モデル

コンセンサスや複製されたステートマシンを実装するためのプロトコルも、一般に通信モデルを仮定します。これは、敵対者がレプリカ間でメッセージの配送を遅らせる能力を特徴づけるものです。このモデルには、以下のようなものがあります。

・同期モデルでは、送信されたメッセージが時間δ未満で配送されるような、既知の有限時間境界δが存在する。

・非同期モデルでは、敵はどのようなメッセージを送信しても、その配信を任意の有限時間だけ遅らせることができるため、メッセージの配信時間に制限はない。

ICサブネット内のレプリカは世界中に分散しているため、同期通信モデルは非常に非現実的です。実際、攻撃者は、正直なレプリカやレプリカ間の通信を遅延させることで、プロトコルの正しい動作を損なうことが可能です。このような攻撃は、正直なレプリカを制御して破損させるよりも、一般に容易に実行することができます。

グローバルに分散したサブネットの設定において、最も現実的で堅牢なモデルは非同期モデルである。残念ながら、このモデルのコンセンサスプロトコルで本当に実用的なものは知られていません（[MXC+16]のような最近の非同期コンセンサスプロトコルでは、スループットはそれなりにありますが、レイテンシがあまりよくありません）。

そこで、同期通信に依存しない他の多くの実用的なビザンチン耐故障システム（例えば、[CL99, BKM18, YMR+18]）と同様に、ICは妥協案として部分同期通信モデル[DLS88]を選択します。このような部分同期モデルは、様々な方法で定式化することができる。ICが用いる部分同期仮定は、大雑把に言えば、各サブネットについて、そのサブネット内のレプリカ間の通信は短い時間間隔で周期的に同期しており、さらに同期境界δは事前に知る必要がない、というものである。この部分的な同期性の仮定は、コンセンサスプロトコルの進捗を保証するためにのみ必要である（いわゆる活性度特性）。コンセンサスの正しい動作（いわゆる安全性）を保証するためには、部分的な同期の仮定は必要ありませんし、ICプロトコルスタックの他の場所でも必要ありません。部分同期とビザンチン故障の仮定の下で、故障数に関する我々の境界f < n/3が最適であることが知られている。

1.5 パーミッションモデル

コンセンサスのための初期のプロトコル（例えばPBFT [CL99]）はパーミッションモデルであり、複製されたステートマシンを構成するレプリカは、どのエンティティがレプリカを提供するか、ネットワークのトポロジーを決定し、おそらくある種の集中公開鍵基盤を実装する中央の組織によって管理されているという意味において、パーミッションされています。パーミッション付きのコンセンサスプロトコルは一般的に最も効率的で、単一障害点を回避することができますが、集中管理は特定のアプリケーションにとって望ましくなく、急成長するWeb3時代の精神と相反するものです。

最近では、Bitcoin [Nak08]、Ethereum [But13]、Algorand [GHM+17]などの許可不要の合意形成プロトコルの台頭が見られます。このようなプロトコルは、ブロックチェーンとプルーフ・オブ・ワーク（PoW）（例：Bitcoin、Ethereum v2.0以前）またはプルーフ・オブ・ステーク（PoS）（例：Algorand、Ethereum v2.0) に基づいています。このようなプロトコルは完全に分散化されていますが、許可されたプロトコルに比べてはるかに効率が悪いです。また、[PSS17]にあるように、BitcoinのようなPoWベースのコンセンサスプロトコルは、非同期通信ネットワークでは正しさ（＝安全性）を保証できないことを指摘する。

ICの許可モデルはハイブリッドモデルであり、許可プロトコルの効率性を得ながら、分散型PoSプロトコルの多くの利点を提供するものである。このハイブリッドモデルはDAO-controlled networkと呼ばれ、（大まかに言って）次のように動作します。各サブネットは許可制コンセンサスプロトコルを実行しますが、分散型自律組織（DAO）がレプリカを提供するエンティティを決定し、ネットワークのトポロジーを設定し、公開鍵基盤を提供し、レプリカに展開されたプロトコルのバージョンを制御します。

ICのDAOはネットワーク神経系（NNS）と呼ばれ、PoSに基づいています。NNSが行うすべての決定は、ICのネイティブガバナンストークンをNNSにどれだけ賭けたかによって投票権が決まるコミュニティメンバーによって行われます（このトークンについては1.8節を参照）。

このPoSベースのガバナンスシステムを通じて、新しいサブネットの作成、既存のサブネットへのレプリカの追加や削除、ソフトウェアの更新、ICへのその他の変更を行うことができます。NNSは、それ自体が複製されたステートマシンで、PoSベースのガバナンスシステムによってメンバーシップが決定される特定のサブネットで動作します。NNSはレジストリと呼ばれるデータベースを維持し、どのレプリカがどのサブネットに属しているか、レプリカの公開鍵など、ICのトポロジーを記録しています。(このように、ICのDAO制御ネットワークは、許可制ネットワークの利点（より効率的な合意形成）と、分散型ネットワークの利点（DAOによるガバナンス）を同時に実現することが可能です。）

ICプロトコルを実行するレプリカは、地理的に分散し、独立して運営されているデータセンターのサーバーにホストされています。これもまた、ICのセキュリティと非中央集権的な性質を強化するものである。

1.6 チェーンキー暗号

ICのコンセンサスプロトコルはブロックチェーンを利用していますが、公開鍵暗号、特に電子署名も利用しています。NNSが管理するレジストリを利用して、レプリカやサブネット全体に公開鍵を結びつけています。これによって、我々がチェーンキー暗号と呼ぶユニークで強力な技術の集合を可能にし、いくつかの構成要素を持っている。

1.6.1 閾値署名（Threshold signatures）

これはよく知られた暗号技術で、サブネットが公開署名検証鍵を持ち、それに対応する秘密署名鍵が共有鍵に分割されてサブネット内の全レプリカに分配され、不正なレプリカが持つ共有鍵は署名を偽造しないようにし、誠実なレプリカが持つ共有鍵はサブネットがICのポリシーとプロトコルに合致した署名を生成できるようにするものである。

このような閾値署名の重要な応用例として、あるサブネットの個々の出力を、別のサブネットや外部ユーザーが、（最初の）サブネットの公開署名検証鍵に関するデジタル署名を検証するだけで、検証することができるというものがある。

サブネットの公開署名検証鍵はNNSから取得できる。この公開署名検証鍵は、サブネットの存続期間中一定である（サブネットのメンバーシップがその存続期間中に変更されても）ことに注意すること。これは、単一の出力を検証するためにブロックチェーン全体を検証する必要がある多くの非スケーラブルなブロックチェーンベースのプロトコルと対照をなすものです。

後述するように、この閾値署名はICの中で他にも多くの用途があります。その1つが、サブネット内の各レプリカに（このような署名から得られる）予測不可能な疑似ランダムビットにアクセスさせるという用途です。これはコンセンサスで使用されるランダムビーコンと実行で使用されるランダムテープの基礎となるものである。

ICは、閾値署名を安全に導入するために、公開署名検証鍵を構築し、各レプリカに対応する秘密署名鍵のシェアを提供する革新的な分散鍵生成（ distributed key generation：DKG）プロトコルを使用し、我々の障害および通信モデル内で機能します

1.6.2 チェーンエボリューション技術（Chain-evolution technology）

チェーンキー暗号には、ブロックチェーンに基づく複製されたステートマシンを長期間にわたって堅牢かつ安全に維持するための高度な技術の集合体も含まれており、これらをまとめてチェーンエボリューション技術と呼んでいます。各サブネットは、多くのラウンド（通常、数百ラウンドのオーダー）のエポックで動作します。チェーンエボリューション技術では、閾値署名やその他多くの技術を用いることで、多くの重要な保守活動を実装しており、これらはエポックと連動した周期で実行されます。

ガベージコレクション：
エポック終了時に、処理されたすべての入力と、それらの入力を命令するために必要なすべての合意レベルのプロトコルメッセージは、各レプリカのメモリから安全に消去されます。これは、レプリカの記憶容量が無制限に増加するのを防ぐために不可欠な機能です。これは、生成ブロックからブロックチェーン全体を保存しなければならない多くの非スケーラブルなブロックチェーンベースのプロトコルとは対照的です。

早送り：
あるサブネットのレプリカが仲間に大きく遅れをとった場合（ネットワークに長期間接続していなかったりダウンしていた場合）、または新しいレプリカがサブネットに追加された場合、コンセンサスプロトコルを実行してそれまでの入力をすべて処理しなくても、最新のエポックの始まりに早送りすることができる。これは、生成ブロックからブロックチェーン全体を処理しなければならない多くのノンスケーラブルブロックチェーンベースのプロトコルと対照的である。

サブネットのメンバーシップが変更される：
サブネットのメンバーシップは（NNSによって決定されるため）時間の経過とともに変化する可能性があります。これはエポック境界でのみ起こりうることであり、一貫性のある正しい動作を保証するために注意深く行われる必要がある。

プロアクティブな秘密の再共有：
1.6.1節で、ICが出力検証に連鎖鍵暗号、特に閾値署名を用いていることを述べた。これは秘密分散に基づくもので、秘密（この場合は秘密署名鍵）を分割してレプリカ間で共有することにより、単一障害点を回避するものである。各エポックの開始時に、これらの共有は積極的に再共有されます。これにより、2つの目的が達成されます。

①サブネットのメンバーが変更された場合、再共有によって新しいメンバーが適切な秘密鍵を共有することができ、メンバーでなくなったレプリカは秘密鍵を共有することができなくなります。

②あるエポックにおいて、あるいはすべてのエポックにおいて、少数の共有が攻撃者に漏れたとしても、それらの共有は攻撃者にとって何の利益にもならない。

プロトコルのアップグレード：
バグ修正や新機能の追加など、ICプロトコル自体のバージョンアップが必要な場合、エポック開始時に特別なプロトコルを用いて自動的に行うことができる。

1.7 実行モデル

すでに述べたように、IC内の複製されたステートマシンは任意のプログラムを実行することができる。ICの基本的な計算単位はCanisterと呼ばれ、プログラムとその状態（時間的に変化する）の両方から構成されるという点で、プロセスの概念とほぼ同じである。Canisterプログラムは、WebAssembly（略称：Wasm）でエンコードされ、スタックベースの仮想マシン用のバイナリ命令フォーマットです[1]。Wasmはオープンスタンダードです。当初はWebページ上で高性能なアプリケーションを実現するために設計されましたが、実際には汎用的な計算にも非常に適しています。ICは、CanisterでWasmプログラムを実行し、他のCanisterや外部ユーザーと（メッセージパッシングによって）通信するためのランタイム環境を提供します。Canisterプログラムは、原則的にWasmにコンパイル可能な任意の言語で書くことができますが、ICの動作セマンティクスによく合致するMotokoという言語が設計されています。Motokoは強型付けされたアクターベース[2] のプログラミング言語で、直交永続性と非同期メッセージパッシングをビルトインでサポートしています[3]。直交永続性とは、簡単に言えば、Canisterが保持するすべてのメモリが自動的に永続化される（つまり、ファイルに書き込む必要がない）ことを意味します。Motokoは、自動メモリ管理、ジェネリックス、型推論、パターンマッチ、任意精度と固定精度の算術演算など、生産性と安全性に優れた機能を数多く備えています。Motokoに加え、ICは型付き、高水準、言語間相互運用のためにCandidと呼ばれるメッセージングインタフェース定義言語（IDL：インタフェース記述言語）とワイヤーフォーマットを提供します。これにより、たとえ異なる高級言語で書かれた2つのCanisterであっても、容易に相互通信を行うことができるようになりました。特定のプログラミング言語でのCanister開発を完全にサポートするには、その言語用のWasmコンパイラの他に、一定のランタイムサポートも提供する必要があります。現在、ICはMotokoに加え、プログラミング言語RustのCanister開発を全面的にサポートしています。

[1]https://webassembly.org/
[2]https://en.wikipedia.org/wiki/Actor_model. [3]https://en.wikipedia.org/wiki/Persistence_(computer_science)#Orthogonal_or_transparent_persistence.

1.8 ユーティリティ・トークン

本ICでは，ICPと呼ばれるユーティリティ・トークンを使用しています。このトークンは以下のような機能に使用されます。

NNSへのステーク:
1.5で述べたように、ICPトークンはNNSでステークされ、NNSを管理するDAOに参加するための議決権を得ることができる。ICPトークンをNNSに張り付けることで、ICネットワークを管理するDAOに参加するための議決権を取得することができる。IC ネットワークを管理する DAO に参加するための議決権を得ることができる。NNSにICPトークンをステークしているユーザーで NNSガバナンスは、投票報酬として新しく鋳造されたICPトークンも受け取ります。そのその金額は、NNSが確立し実施するポリシーによって決定されます。

サイクルに変換する：
ICPは、ICの使用料を支払うために使用されます。具体的には、ICPトークンはサイクルに変換され（すなわち燃焼され）、このサイクルはキャニスターの作成（1.7節参照）およびキャニスターが使用するリソース（ストレージ、CPU、帯域幅）に対する支払いに使用されます。ICPがサイクルに変換される割合は、NNSによって決定される。

ノードプロバイダへの支払い：
ICPトークンは、ノードプロバイダー（ICを構成するレプリカをホストするコンピューティングノードを所有・運用する事業者）への支払いに使用されます。NNSは一定期間ごとに（現在は毎月）、各ノードプロバイダーが受け取るべき新しく鋳造されたトークンの数を決定し、トークンをノードプロバイダーのアカウントに送ります。トークンの支払いは、NNSが設定し実施する特定のポリシーに従って、ICに信頼できるサービスを提供することを条件とする。

1.9 バウンダリノード

バウンダリノードは，ICのネットワークエッジサービスを提供する．特に、

- ICへの明確なエントリポイント
- ICのサービス拒否保護
- レガシークライアント（ウェブブラウザなど）からのICへのシームレスなアクセスを提供する。

レガシークライアントからICへのシームレスなアクセスを容易にするために、バウンダリノードは、ユーザからの標準的なHTTPSリクエストをIC上のCanisterに向けたingressメッセージに変換し、このCanisterが存在するサブネット上の特定のレプリカにingressメッセージを転送する機能を提供する。

さらに、バウンダリノードは、キャッシュ、ロードバランシング、レート制限、レガシークライアントがICからの応答を認証する機能など、ユーザー体験を向上させるための追加サービスを提供します。Canisterは、ic0.appドメイン上のURLで識別されます。最初に、レガシークライアントはそのURLに対応するDNSレコードを検索し、境界ノードのIPアドレスを取得し、このアドレスに最初のHTTPSリクエストを送信します。バウンダリノードは、レガシークライアントで実行されるJavaScriptベースの「サービスワーカー」を返します。

この後、レガシークライアントとバウンダリーノード間のすべてのインタラクションは、このサービスワーカーを介して行われることになる。サービスワーカーによって実行される重要なタスクの1つは、連鎖鍵暗号を使用してICからの応答を認証することです(セクション1.6を参照)。これを行うために、NNSの公開検証鍵はサービスワーカーにハードコードされている。バウンダリノード自身は、指定されたCanisterがホストされているサブネット上のレプリカにリクエストをルーティングする責任を負う。このルーティングを実行するために必要な情報は、バウンダリノードがNNSから取得する。バウンダリノードは、タイムリーな応答を提供するレプリカのリストを保持し、このリストからランダムにレプリカを選択する。レガシークライアントとバウンダリノード，バウンダリノードとレプリカの間の通信はすべてTLSで保護される（https://en.wikipedia.org/wiki/Transport_Layer_Security.）。

レガシークライアントに加え，サービスワーカーロジックをすでに含む「ICネイティブ」クライアントを使ってバウンダリノードとやり取りすることも可能で，この場合はバウンダリノードからサービスワーカープログラムを取得する必要はない．レプリカと同様、バウンダリノードの配置と設定はNNSによって制御されます。

1.10 NNSの詳細

1.5節で述べたように，ネットワーク神経系(NNS)はICを制御するアルゴリズム的な統治システムである．これは、特別なシステムサブネット上のCanisterのセットによって実現される。このサブネットは他のサブネットと同様ですが、多少異なる構成になっています（一例として、システムサブネット上のCanisterは、使用するサイクルに対して課金されません）。

レジストリCanister：
ICの構成、すなわちどのレプリカがどのサブネットに属しているか、サブネットや個々のレプリカに関連する公開鍵などを保存します。
ガバナンスCanister：
ICをどのように進化させるかについての意思決定と投票を管理します
台帳Canister：
ユーザのICP実用新案権アカウントとそれらの間のトランザクションを追跡します。

1.10.1 NNSでの意思決定

誰もが、いわゆるニューロンにICPトークンを賭けることでNNSのガバナンスに参加することができます。そして、ニューロン保有者は、ICをどのように変更すべきか、例えば、サブネットトポロジーやプロトコルをどのように変更すべきかに関する提案であるプロポーザルを提案し、投票することができます。意思決定のためのニューロンの投票力は、プルーフ・オブ・ステークに基づいています。直感的には、より多くのステークされたICPトークンを持つニューロンは、より多くの投票力を持つ。しかし、投票権は他のいくつかのニューロン特性にも依存する。例えば、トークンをより長い期間ステークしておくことを約束したニューロンホルダーには、より多くの投票権が与えられる。各提案には決められた投票期間がある。投票期間の終了時に、総投票力の単純過半数がその提案に賛成し、これらの賛成票が総投票力の所定の定足数（現在は3%）を構成していれば、その提案は採択されます。それ以外の場合は、その議案は否決されます。また、絶対過半数（総議決権数の半数以上）が賛成または反対した場合は、いかなる時点でもその議案は可決または否決されます。提案が採択された場合、ガバナンスCanisterは自動的にその決定を実行する。例えば、ネットワークトポロジーの変更を提案し、それが採用された場合、ガバナンスCanisterは自動的に新しい構成でレジストリを更新する。

1.11 進行中の作業

ICのアーキテクチャはまだ進化・拡大中である。ここでは、近々展開されるであろう新機能をいくつか紹介します。
DAOコントロールされたCanister：
ICの全体的な構成がNNSによって制御されるのと同様に、どのCanisterもサービス神経系（SNS）と呼ばれる独自のDAOによって制御される可能性があります。Canisterを制御するDAOは、Canisterのロジックに対する更新を制御することができ、また、Canisterが実行する特権的なコマンドを発行することもできます。
スレッショルドECDSA：
ECDSA署名[JMV01]は、ビットコインやイーサリアムのような暗号通貨や、他の多くのアプリケーションで使用されています。閾値署名はすでにICに不可欠な要素となっていますが、これは閾値ECDSA署名ではありません。この新機能により、個々のCanisterがECDSA署名鍵を制御し、Canisterをホストするサブネット上の全レプリカに安全に分散させることができるようになります。
ビットコインとイーサリアムの統合：
新しいスレッショルドECDSA機能をベースに、この機能により、Canisterはビットコインやイーサリアムのブロックチェーンとやり取りできるようになり、取引に署名する機能も含まれます。
HTTP統合：
この機能により、Canisterは任意のウェブページ（ICの外部）を読み取ることができるようになります。

2 アーキテクチャの概要

図1に示すように、インターネット・コンピュータ・プロトコルは、4つの層で構成されています。

ピアツーピア層（4項参照）
コンセンサス層（5項参照）
ルーティング層（6項参照）
実行層（7項参照）

連鎖鍵暗号はいくつかの層に影響を与えるが、その詳細についてはセクション3（閾値署名）とセクション8（連鎖進化技術）で説明する。

2.1 ピアツーピア層

ピアツーピア層のタスクは、サブネット内のレプリカ間でプロトコル・メッセージを伝送することである。

これらのプロトコル・メッセージは、

コンセンサスを実現するためのメッセージ
外部ユーザーによって生成された入力メッセージ

から構成されます。

基本的に、peer-to-peerが提供するサービスは "best effort "ブロードキャストチャンネルです。
正直なレプリカがメッセージをブロードキャストすれば、そのメッセージは最終的にサブネット内のすべての正直なレプリカによって受信されます。

設計目標は以下の通りです。

制限されたリソース
すべてのアルゴリズムは、制限されたリソース（メモリ、帯域幅、CPU）で動作しなければなりません。
優先順位付け
特定の属性（タイプ、サイズ、ラウンドなど）に応じて、異なるメッセージは異なる優先順位で扱われ、これらの優先順位は時間の経過とともに変化する可能性があります。
効率性
高いスループットは、低いレイテンシーよりも重要です。
DOS/SPAM耐性
破損したレプリカが、誠実なレプリカ同士の通信を妨げてはならない。

2.2 コンセンサス層

ICのコンセンサス層の仕事は、サブネット内のすべてのレプリカが同じ順序で入力を処理するように、入力を順番に並べることである。この問題に対しては、多くのプロトコルが文献に記載されています。ICは新しいコンセンサスプロトコルを使用しており、ここではその高レベルな内容を説明します。安全なコンセンサスプロトコルは、（大まかに言って）次の2つの性質を保証する必要があります。

安全性：
すべてのレプリカが同じ入力順序に同意すること
活性：
すべてのレプリカが着実に進歩すること。

ICコンセンサスプロトコルは、

極めてシンプルであること、
堅牢であること
（一部のレプリカに悪意がある場合、性能が緩やかに低下する）を目的として設計されています。

上述のように、f < n/3の欠陥レプリカ（つまりビザンチン）を想定しています。また、完全な非同期ネットワークにおいても安全性が保証される一方で、部分的な同期性の仮定下で有効性が保持される。

多くのコンセンサスプロトコルと同様に、ICコンセンサスプロトコルはブロックチェーンをベースにしています。プロトコルの進行に伴い、ブロックの木が成長し、木の根である特別な創始ブロックから始まる。ツリー内の特別なgenesis blockはそれぞれ、一連の入力からなるペイロードと、ツリー内のブロックの親のハッシュを含んでいる（他の要素も含む）。各レプリカはこのツリーについて異なる部分的な見解を持っているかもしれませんが、すべてのレプリカは同じツリーについて見解を持っています。さらに、プロトコルの進行に伴い、このツリーには常に確定したブロックのパスが存在します。各レプリカはこのパスについて異なる部分的な見解を持っているかもしれませんが、すべてのレプリカは同じパスについて見解を持っています。このパスに沿ったブロックのペイロードの入力は、インターネットコンピュータの実行層で処理される順序の入力である。

プロトコルはラウンドで進行する。プロトコルのラウンドhでは、高さhの1つまたは複数のブロックがツリーに追加される。つまり、ラウンドhで追加されるブロックは、常にルートからちょうどhの距離にある。各ラウンドでは，擬似乱数処理により各レプリカに固有のランクを割り当てる．ランクは0，．, n - 1. この擬似ランダム処理は、ランダムビーコンを使って実装される (これは、セクション1.6.1で前述し、セクション3でより詳細に議論する閾値署名を利用したものである)。最も低いランクのレプリカがそのラウンドのリーダーとなる。リーダーが正直者であり、ネットワークが同期している場合、リーダーはブロックを提案し、それがツリーに追加される。リーダーが誠実でない場合やネットワークが同期していない場合、他の上位のレプリカもブロックを提案し、そのブロックがツリーに追加されることがある。いずれにせよ、プロトコルのロジックはリーダーの提案したブロックを最優先し、このラウンドで何らかのブロックがこのツリーに追加されることになる。この結果、レプリカの欠陥やネットワーク遅延の増大により遅延が増大することがあっても、プロトコルのスループットは一定に保たれます。コンセンサスプロトコルは、レプリカ間で送信されるメッセージの認証に電子署名を利用しています。

このプロトコルを実現するために、各レプリカには署名方式の公開検証鍵が割り当てられます。レプリカと公開鍵の関連付けは、NNSが管理するレジストリから取得される。

2.3 メッセージルーティング

1.7節で述べたように、ICの基本的な計算単位はCanisterと呼ばれる。ICはCanister内のプログラムを実行し、他のCanisterや外部ユーザと通信するためのランタイム環境を提供する（メッセージパッシングによる）。

コンセンサス層は入力をペイロードに束ね、ブロックに配置し、ブロックが確定すると、対応するペイロードをメッセージルーティング層に配信し、実行環境で処理し、複製されたステートマシンのキャニスターの状態を更新して、ブロックに配置する。

実行環境は複製されたステートマシン上でのCanisterの状態を更新して出力を生成し、これらの出力はメッセージルーティング層で処理される。

2種類の入力を区別することは有用である。

イングレスメッセージ：
外部ユーザーからのメッセージ
クロスサブネットメッセージ：
他のサブネット上のCanisterからのメッセージです。

また、2種類の出力を区別することができます。

イングレスメッセージ応答：
イングレスメッセージに対する応答（外部ユーザーによって取得される場合がある）、
クロスサブネットメッセージ：
他のサブネット上のCanisterに対するメッセージです。

コンセンサスからペイロードを受信すると、そのペイロードの入力は、さまざまな入力キューに入れられる。サブネット上で動作する各CanisterCには、いくつかの入力キューがあります。Cへのイングレスメッセージ専用のキューが1つあり、Cが通信する他の各CanisterC'は、それ自身のキューを取得します（C'がサブネット上のCanisterである場合、そのキューは1つのキューとなります）。(C'がCと同じサブネット上にない場合、これらはクロスサブネットメッセージである）。各ラウンドで、実行層はこれらのキュー内の入力の一部を消費し、関連するCanisterの複製された状態を更新し、様々な出力キューに出力を配置することになる。

サブネット上で動作する各CanisterCには、いくつかの出力キューがあります。Cが通信する他の各CanisterC'は、それ自身のキューを取得します。(C' が C と同じサブネット上にない場合、これらはクロスサブネットメッセージとなる)。メッセージルーティング層は、これらの出力キューにあるメッセージを受け取り、それらをサブネット間のストリームに配置して、クロスネット転送プロトコルによって処理されるようにしますが、その仕事は、これらのメッセージを他のサブネットに実際に転送することです。

これらの出力キューに加えて、イングレス履歴データ構造も存在します。Canisterによってイングレスメッセージが処理されると、そのイングレスメッセージに対する応答がこのデータ構造に記録されます。その時点で、イングレスメッセージを提供した外部ユーザーは、対応するレスポンスを取得することができるようになる。(ingress historyは、すべてのingressメッセージの完全な履歴を保持するわけではないことに注意）。

複製された状態は、Canisterの状態、上記のキューやストリームを含む「システム状態」、およびイングレス履歴データ構造からなることに注意してください。このように、メッセージルーティング層と実行層の両方が、サブネットの複製された状態の更新と維持に関与しています。この状態のすべてが完全に決定論的な方法で更新され、すべてのレプリカがまったく同じ状態を維持することが不可欠です。また、コンセンサス層はメッセージルーティング層および実行層から切り離されていることに注意してください。

つまり、コンセンサスブロックチェーンにおけるフォークは、そのペイロードがメッセージルーティングに渡される前に解決され、実際、コンセンサスはメッセージルーティングとコンセンサスに同期する必要がなく、少し先に実行することが許されているのです。

2.3.1 ラウンドごとの認証状態

各ラウンドで、サブネットの状態の一部が認証される。ラウンドごとの認証された状態は、連鎖鍵暗号を使用して認証される。

特にあるラウンドの認証状態は、

最近サブネット間のストリームに追加されたクロスサブネットメッセージ
イングレス履歴データ構造を含むその他のメタデータ

から構成される。

ラウンドごとの認証済み状態は、閾値署名を使用して認証される(セクション1.6.1参照)。ラウンドごとの認証済み状態は、ICの中でいくつかの方法で使用される。

出力認証
クロスサブネットメッセージおよびイングレスメッセージへの応答は、ラウンドごとの認証済み状態を使用して認証されます。
非決定性の防止と検出
コンセンサスは、各レプリカが同じ順序で入力を処理することを保証しています。各レプリカはこれらの入力を決定論的に処理するため、各レプリカは同じ状態を得るはずである。しかし、ICは(偶発的な)非決定論的な計算が発生した場合に、それを防止・検出するための堅牢性を付加して設計されています。ラウンドごとの認証状態は、このために用いられる機構の一つである。
コンセンサスとの調整
ラウンドごとの認証状態は、2つの異なる方法で、実行層とコンセンサス層を調整するためにも使用されます。
- コンセンサスが実行より先に進んでいる場合（その進捗は、ラウンドごとの認証状態によって決定されます）、コンセンサスは "スロットル "されます。
- コンセンサスへの入力は、特定の有効性チェックを通過する必要があり、これらの有効性チェックは、すべてのレプリカが合意しなければならない認証済み状態に依存する場合があります。

2.3.2 クエリーコールとアップデートコール

これまでに説明したように、受信メッセージは、サブネット上のすべてのレプリカで同じ順序で処理されるよう、コンセンサスを通過する必要があります。しかし、サブネットの複製状態を変更しない処理を行うingressメッセージには、重要な最適化が可能です。これはクエリコールと呼ばれ、他のイングレスメッセージがアップデートコールと呼ばれるのとは対照的です。

クエリコールは、Canisterの状態を読み取り、場合によっては更新する計算を行うことができますが、Canisterの状態に対する更新がレプリケートされた状態にコミットされることは決してありません。そのため、クエリコールは、コンセンサスを経由せずに、単一のレプリカによって直接処理されることがあります。これは、クエリコールから応答を得るための待ち時間を大幅に短縮します。

一般に、クエリコールに対する応答は、イングレス履歴データ構造に記録されないため、上述のラウンド毎の認証状態メカニズムを用いて認証することはできない。しかし、IC は、Canisterがアップデートコールを処理する際に、特別な認証済み変数にデータを格納することを可能にしており、このメカニズムによって認証することができる。このように、認証済み変数を値として返すクエリコールは、認証することができる。

2.3.3 外部ユーザー認証

イングレスメッセージとクロスサブネットメッセージの主な違いの1つは、これらのメッセージを認証するために使用されるメカニズムである。

クロスサブネット・メッセージの認証にはチェーンキー暗号が使用されるが、外部ユーザーからのイングレス・メッセージの認証には別のメカニズムが使用される。外部ユーザーを登録する中央レジストリは存在しない。

外部ユーザーは、公開署名検証キーのハッシュであるユーザー識別子（別名プリンシパル）を使用してCanisterに自分自身を識別します。このユーザーは対応する秘密署名鍵を持っており、この鍵はイングレスメッセージに署名するために使用されます。このような署名と対応する公開鍵は、イングレスメッセージと一緒に送信されます。ICは自動的に署名を認証し、ユーザー識別子を適切なCanisterに渡します。Canisterは、ユーザー識別子と、イングレスメッセージで指定された操作の他のパラメータに基づいて、要求された操作を承認することができる。初回利用者は、ICとの最初のやり取りの際に、鍵ペアを生成し、公開鍵から利用者識別子を導出する。再来訪ユーザは，ユーザエージェントが記憶している秘密鍵を用いて認証される．ユーザは、署名委任を利用して、1つのユーザIDに複数のキー・ペアを関連付けることができます。これは，一人のユーザが複数のデバイスから同一のユーザ ID を用いて IC にアクセスすることを可能にするためです。

2.4 実行層

実行層は一度に一つの入力を処理する。この入力は、入力キューの1つから取り出され、1つのCanisterに向けられる。この入力とCanisterの状態に基づいて、実行環境はCanisterの状態を更新し、さらに出力キューにメッセージを追加し、（おそらく以前の入力メッセージに対する応答で）入力履歴を更新することができる。

各サブネットは分散型擬似乱数発生器（PRG）にアクセスすることができる。疑似乱数ビットは、それ自体がランダムテープと呼ばれる閾値署名である種から導かれる(セクション1.6.1およびセクション3での詳細を参照)。コンセンサスプロトコルの各ラウンドには、異なるランダムテープが存在する。

ランダムテープの基本的な特性は以下の通りである。

1. 高さhのブロックが任意の正直なレプリカによって確定される前に、高さh + 1のランダムテープは予測不可能であることが保証される。
2. 高さh + 1のブロックが完成するまでに、レプリカは高さh + 1のランダムテープを作成するために必要なすべての共有を持っている必要がある。

疑似ランダムビットを得るには、サブネットは実行レイヤーの「システムコール」によって、あるラウンド（たとえばh）でこれらのビットの要求を行う必要がある。上記（1）の性質により、要求された疑似乱数ビットは、要求された時点では予測不可能であることが保証される。コンセンサスは、実際にはランダムテープとh + 1のペイロードの両方を同時にメッセージルーティングに配信する。上記の特性（2）により、これは通常、追加の遅延を発生させない。

2.5 まとめ

IC上のユーザーリクエストを処理する典型的なフローをたどってみる。

クエリコール
１．ユーザーのクライアントからバウンダリノード(セクション1.9参照)に、CanisterCに対するユーザーのクエリーコールMが送られ、バウンダリノードはCanisterCをホストするサブネットのレプリカにMを送る。

アップデートコール
１． CanisterCに対するユーザーのリクエストMは、ユーザーのクライアントからバウンダリノード(セクション1.9参照)に送られ、バウンダリノードはCanisterCをホストするサブネット上のレプリカにMを送信します。

２．Mを受信すると、このレプリカはピアツーピア層を使って、サブネット上の他のすべてのレプリカにMをブロードキャストします(セクション2.1参照)。

３． Mを受け取ったコンセンサスの次のラウンドのリーダー(セクション2.2参照)は、Mを他の入力とバンドルし、リーダーが提案するブロックBのペイロードを形成する。

４．しばらくして、ブロックBが確定され、ペイロードがメッセージルーティング層 (セクション2.3参照)に送信されて処理される。ピアツーピア層は、このブロックを確定するためにコンセンサスによっても使用されることに注意してください。

５．メッセージルーティング層は、MをキャニスタCの入力キューに入れる。

６．しばらくして、実行層(セクション2.4参照)はMを処理し、キャニスターCの内部状態を更新します。
ある状況では、CanisterCはリクエストMに対する応答R を直ちに計算することができる。他の状況では、リクエストMを処理するために、他のCanisterにリクエストをする必要があるかもしれません。この例では、この特定の要求Mを処理するために、CanisterCが、別のサブネットに存在する別のCanisterC'に要求M'をしなければならないと仮定しよう。この第2の要求M'は、Cの出力キューに入れられ、その後、次のステップが実行される。

７．しばらくしてから、メッセージルーティングによって、M'は適切なクロスサブネットストリームに移動し、これは最終的にC'をホストするサブネットに転送される。

８．第二サブネットでは、リクエストM'は第一サブネットから取得され、最終的に第二サブネット上のコンセンサスとメッセージルーティングを通過し、実行によって処理されることになる。実行層は、CanisterC'の内部状態を更新し、リクエストM'に対するレスポンスR'を生成する。応答R'は、CanisterC'の出力キューに入り、最終的にクロスサブネットストリームに置かれ、最初のサブネットに輸送される。

９．第1のサブネットに戻ると、応答R'は第2のサブネットから取得され、最終的に第1のサブネット上のコンセンサスとメッセージルーティングを通過し、実行によって処理される。

実行層は、CanisterCの内部状態17を更新し、元の要求メッセージMに対する応答Rを生成し、この応答は、イングレス履歴データ構造に記録される。どの実行パスが取られるかに関係なく、リクエストMに対する応答Rは、最終的に、CanisterCをホストするサブネット上のイングレス履歴データ構造に記録される。この応答を得るために、ユーザーのクライアントは、一種の「クエリコール」(セクション2.3.2参照)を実行する必要がある。セクション2.3.1で議論したように、この応答は連鎖鍵暗号方式で認証される (具体的には、閾値署名を使用する)。認証ロジック自体(すなわち、閾値署名の検証)は、クライアントが元々境界ノードから取得したサービスワーカーを使用して、クライアントによって実行される。

3 連鎖鍵暗号方式

ICの連鎖鍵暗号の重要な構成要素は、閾値署名方式[Des87]である。ICは閾値署名を様々な目的で使用する。サブネット内のレプリカの数をnとし、破損したレプリカの数の上限をfとする。

コンセンサス層は(f + 1)out-of-n 閾値署名を用いてランダムビーコンを実現する（5.5節参照）。
実行層は、(f + 1)-out-of-n閾値署名を用いてランダムテープを実現し、Canisterに予測不可能な疑似乱数を提供する（7.1項参照）。
実行層は、複製された状態を証明するために、(n - f)-out-of-nの閾値署名を利用する。これは、サブネットの出力を認証するため(6.1節参照)と、ICのチェーンエボリューション技術の高速転送機能を実装するため(8.2節参照)の両方に使用されている。

最初の2つのアプリケーション（ランダムビーコンとランダムテープ）では、閾値署名が一意であること、すなわち、与えられた公開鍵とメッセージに対して、有効な署名が1つだけ存在することが不可欠である。これは、署名を擬似乱数生成器の種として使用し、そのような閾値署名を計算するすべてのレプリカが同じ種に同意しなければならないため、必要である。

3.1 閾値BLS署名

★本節は数式をnoteで変換困難なため、原文と合わせて見て下さい

我々はBLS署名方式[BLS01]に基づいて閾値署名を実装しており、閾値設定に適応させるのは容易である。

通常の（すなわち、非しきい値の）BLS署名方式は、素数階qの2つのグループ、GとG'を用いる。Gはg∈Gによって生成され、G'はg'∈G'によって生成されると仮定する。また、入力をG'に写すハッシュ関数HG'（ランダムオラクルとしてモデル化されている）を仮定する。秘密署名鍵は要素x∈Zqであり、公開検証鍵はV := g x∈Gである。

非閾値設定において、メッセージmに署名するために、署名者はh' ← HG'(m) ∈ G'を計算し、署名σ := (h ' ) x ∈ G' を計算する。このような署名が有効であることを検証するためには、logh'σ = logg V かどうかをテストしなければならない。この検証を効率的に行うために、BLS方式18では、群Gと群G'にペアリングという概念を用いており、これは、GとG'が特殊な型の楕円曲線の場合に利用できる代数的な演算である。ペアリングと楕円曲線の詳細についてはここでは触れないことにする。詳しくは[BLS01]を参照。BLS署名には、署名が一意であるという（前述した）素晴らしい性質がある。

t-out-of-nの閾値の設定では、n個のレプリカがあり、そのうちの任意の t個を使ってメッセージに対する署名を生成することができる。より詳細には、各レプリカPjは秘密署名鍵x∈Zqの共有xj∈Zqを持ち、これはPjが私的に保有し、グループ要素Vj := g xjは公的に利用可能である。(x1、...、xn）はxのt-out-of-n秘密分散である（3.4節参照）。

メッセージmが与えられると、レプリカPjは署名共有

ここでh ' := HG'(m) を前と同じように生成することができる。このような署名共有が有効であることを検証するには、logh' σj = logg Vj かどうかをテストする必要があります。離散対数の計算は困難であるが、これはペアリングを用いて確認することができる。実際、これは公開鍵Vjを用いた通常のBLS署名の有効性テストと全く同じである。

この方式は、以下の再構成特性を満たす。

メッセージmに対する任意のt個の有効な署名共有σjのコレクション（異なるレプリカによって提供される）が与えられると、公開検証鍵の下で、mに対する有効なBLS署名σを効率的に計算することが可能である。

実際、σは次のように計算することができ、

λjは寄与したt個のレプリカのインデックスから効率的に計算することができる。

Gの合理的な難易度の仮定の下で、HG'をランダムオラクルとしてモデル化すると、この方式は以下の安全性特性を満足する。

最大でf個のレプリカが敵によって破壊される可能性があると仮定する。このとき、敵対者は少なくともt-f個の正直なレプリカからメッセージに対する署名の共有を得なければ、メッセージに対する有効な署名を計算することは不可能である。

3.2 鍵の分散配布

閾値BLSを実装するためには、秘密署名鍵のシェアをレプリカに分散する方法が必要である。これを実現する一つの方法として、信頼できる人物がこれらの共有鍵のすべてを直接計算し、すべてのレプリカに配布することが考えられます。残念ながら、これでは単一障害点が発生してしまいます。その代わりに、私たちは分散鍵生成（DKG）プロトコルを使用し、安全な分散プロトコルを使用して、レプリカが本質的に信頼できるパーティーの論理を実行することを可能にします。

現在実装されているプロトコルの高レベルなアイデアをスケッチする。詳細については[Gro21]を参照してください。使用されるDKGプロトコルは、基本的に非対話的である。このプロトコルは2つの本質的な要素を使用している。

PVSS (Publicly Verifiable Secret Sharing) スキーム
コンセンサスプロトコル

コンセンサスプロトコルはどのようなものでも使用できるが、驚くことではないが、我々が使用するのはセクション5のものである（セクション8も参照）。

3.3 前提条件

基本的な前提条件は、セクション1で説明したものと同じである。

非同期通信、および、
f < n/3

我々は、コンセンサスプロトコルの有効性を保証するために、(セクション5.1のように)部分的な同期性の仮定を間接的に利用するのみである。また、t-out-of-n閾値署名方式において、

f < t ≤ n - f
を仮定する。

これは、（特に）（1）破損したレプリカが単独で署名できないことと、（2）正直なレプリカが単独で署名できることを保証するものである。

また、各レプリカはいくつかの公開鍵に関連付けられ、各レプリカは対応する秘密鍵も持っているとする。公開鍵の1つは署名鍵である（5.4節と同じ）。もう一つの公開鍵は、PVSS方式を実現するために必要な特定の公開鍵暗号化方式の公開暗号鍵である(詳細は後述)。

3.4 PVSS方式

上で紹介したg∈Gが生成する素数位数qの群をGとする。s∈Zqを秘密とする。sのt-out-of-n Shamir秘密分散は、ベクトル（s1, ... , sn）∈Z n q 、

ここで

はa0 := sでt未満の次の多項式であることを思い出してください。

このような秘密分散の重要な特性は、

sj 's の任意の t のコレクションから、秘密 s = a0 = a(0) を（多項式補間により）効率的に計算できる、
a1, ..., at-1 が一様に選ばれ、かつ、その次数が t より小さい場合、 - a0 :s となることである。

PVSS方式では，ディーラーと呼ばれる1台のレプリカPiがこのような共有を行い，ディーリングと呼ばれるオブジェクトを計算することができる。

暗号文のベクトル (c1, ... , cn), ここで cj は Pj の公開暗号鍵による sj の暗号化、
各 cj が本当にそのようなシェアを暗号化していること、より正確には、各 cj は

を満たす値 sj を復号化しているという非インタラクティブゼロ知識証明π、を含む。

(2）DKGプロトコルの全体的な安全性を確立するために、PVSS方式は適切なレベルの選択暗号文の安全性を提供しなければならないことに注意する。具体的には、ディーラーは自身のアイデンティティを関連データとしてディーリングに埋め込む必要があり、敵対者がディーリングの作成に使用した関連データとは異なる関連データの下で復号された任意のディーリングを復号することを許される選択暗号文攻撃下でも、暗号化された株式は隠されたままでなければならない。

効率をあまり気にしなければ、PVSS方式を実現するのは簡単である。そのアイデアは、ElGamalのような暗号化方式を使って各sjをビット毎に暗号化し、関係(2)に対して、Fiat-Shamir変換(［FS86］)を適切なSigmaプロトコル（［CDS94］参照）に標準的に適用した非インタラクティブなゼロ知識証明を用いることであろう。これは多項式時間のスキームをもたらしますが、それほど実用的ではありません。しかし、この種の方式を最適化する方法は数多く存在します。本 IC で使用されている高度に最適化された PVSS スキームの詳細については [Gro21] を参照されたい。

3.5 基本的なDKGプロトコル

PVSS方式とコンセンサスプロトコルを用いて、基本的なDKGプロトコルは非常にシンプルである。

各レプリカはランダムシークレットの署名付きディーリングを他の全レプリカにブロードキャストする。このような署名付きディーリングは、ディーラーの身元とディーラーの公開署名鍵の下でのディーリングに対する署名とともに、ディーリングを含む。このような署名付きディーリングは、それが正しい構文形式を持ち、署名と非対話的ゼロ知識証明が有効である場合、有効であると呼ばれる。
コンセンサスを用いて、レプリカは(異なるディーラーからの)f + 1個の有効な署名付きディーリングの集合Sに合意する。
集合Sにおけるi番目の取引が、グループ要素のベクトル(Ai,0, ... , Ai,t-1)と暗号文のベクトル(ci,1, ... , ci,n) を含むと仮定する。

そして、閾値署名方式の公開検証鍵は、

となる。

秘密署名鍵は暗黙のうちに

と定義されていることに注意。

Pjの秘密署名鍵xのシェアは

ここでsi,jはPjの秘密復号鍵でci,jを復号化したものである。
レプリカPjの公開検証鍵は，

である．

xjはxのt-out-of-n Shamir秘密分散を構成することに注意。これにより、3.1節で述べた再構成の性質が成立する。3.1節で述べた安全性については、HG’をランダムオラクルとモデル化し、PVSS方式が安全であり、グループGとG'（ペアリングあり）がある種のワンモアDiffie-Hellman硬度仮定を満たすと仮定すると、次のゲームに効率的敵対者が無視できない確率で勝利できないことを述べると、これが成り立つことが立証できる。

挑戦者はμ1、．µ1, ... µk∈Zq および ν1, ... ... ν` ∈ Zq をランダムに選び、{g µi} k i=1 と {(g' ) νj } を敵に渡す。j=1 を敵対者に渡す。敵は挑戦者に{κi,j}i,j の形のベクトルを連続的に問い合わせ、挑戦者は

で応答する。

ゲーム終了時、敵はベクトル{λi,j}i,j と群要素 h'∈G' を出力し、

かつ出力ベクトル {λi,j}i,j が問合せベクトルの線形結合でなければゲームに勝利となる。

このようなワンモアDiffie-Hellman仮定はt > f + 1の場合に必要であるが、t = f + 1の場合はより弱い仮定（いわゆるco-CDH仮定、通常のBLS方式の安全性はこれに基づく）でやりすごすことが可能である。

3.6 再共有プロトコル

基本的なDKGプロトコルは、新しいランダムな秘密xの共有を作成する代わりに、以前に共有した秘密の新しいランダムな共有を作成するように簡単に変更することができる。

基本プロトコルのステップ1は、各レプリカがその既存の共有を署名付きでブロードキャストするように変更される。
ステップ2は、有効な署名付きディーリングのセットtが合意されるように変更される。また、各ディーリングは、それが本当に適切な既存シェアのディーリングであることを確認するために検証される（これは、i番目のディーリングにおけるAi,0の値がViの旧値と等しくなければならないことを意味する）。
ステップ3では、新しいxj （およびVj ）値の計算は、i個のラグランジュ補間係数の和（および積）に重みをかける。

4 ピアツーピア層

ピアツーピア層のタスクは、サブネット内のレプリカ間でプロトコル・メッセージを伝送することである。

ブロックプロポーザル、公証など、コンセンサスを実現するために使用されるメッセージ（セクション5参照）。
イングレスメッセージ（セクション6参照）で構成されています

基本的に、peer-to-peerが提供するサービスは「ベストエフォート」ブロードキャストチャネルである。

正直なレプリカがメッセージをブロードキャストした場合、そのメッセージは最終的にサブネット内のすべての正直なレプリカによって受信されることになる。

設計目標は以下の通りです。

制限されたリソース：　すべてのアルゴリズムは、制限されたリソース（メモリ、帯域幅、CPU）で動作しなければなりません。
優先順位付け：　特定の属性（タイプ、サイズ、ラウンドなど）に応じて、異なるメッセージは異なる優先順位で扱われ、これらの優先順位は時間の経過とともに変化する可能性があります。
効率性：　高いスループットは、低いレイテンシーよりも重要です。
DOS/SPAM耐性：　破損したレプリカが、正直なレプリカ同士の通信を妨げてはならない。

コンセンサス・プロトコルでは、いくつかのメッセージ、特にブロック・プロポーザル（かなり大きくなる可能性があります）が、すべてのレプリカによって再ブロードキャストされることに留意してください。これは、このプロトコルの正しい動作を保証するために必要なことです。しかし、素朴に実装した場合、これはリソースの大きな浪費になります。すべてのレプリカが同じメッセージをブロードキャストすることを避けるために、ピアツーピア層はadvertise-request-deliverメカニズムを利用する。レプリカがこのような広告を受信し、まだ受信しておらず、かつそのメッセージが重要であると判断した場合、そのメッセージの配信を要求するのです。この戦略は、帯域幅の使用量を減らす一方で、レイテンシーを増加させるという代償をもたらします。小さなメッセージの場合、このトレードオフは価値がなく、アドバタイズではなく、メッセージを直接送信する方がより理にかなっている。

比較的小さなサブネットの場合、メッセージをブロードキャストしたいレプリカは、サブネット内のすべてのレプリカにアドバタイズを送信し、各レプリカはメッセージの配信を要求することができます。

より大きなサブネットでは、このadvertise-request-deliverメカニズムは、オーバーレイネットワーク上で動作することがあります。オーバーレイネットワークは、サブネット内のレプリカを頂点とする連結無向グラフである。2つのレプリカは、このグラフに接続するエッジがあればピアであり、レプリカはそのピアとのみ通信を行う。そのため、レプリカはメッセージをブロードキャストしたい場合、そのメッセージの広告をピアに送ります。それらのピアはメッセージの配信を要求することができ、メッセージを受信した後、ある条件が満たされれば、それらのピアは自分のピアにメッセージをアドバタイズします。これは本質的にゴシップネットワークである。この戦略もまた、帯域幅の利用を減少させるが、その代償としてさらに高いレイテンシが発生する。

5 コンセンサス層

ICのコンセンサス層の仕事は、サブネット内のすべてのレプリカが同じ順序で入力を処理するように、入力を順番に並べることである。この問題に対しては、多くのプロトコルが文献に記載されています。ICは新しいコンセンサスプロトコルを使用しており、ここではその高レベルなものを説明します。詳細については、論文[CDH+21]（特に、その中のプロトコルICC1）を参照してください。安全なコンセンサスプロトコルは、（大まかに言って）次の2つの性質を保証する必要があります。

安全性：
すべてのレプリカが入力の同じ順序に同意すること
活性：
すべてのレプリカが着実に進歩すること

この論文[CDH+21]は、ICコンセンサスプロトコルがこの二つの性質を満たすことを証明しています。

ICコンセンサスプロトコルは、

極めてシンプルであり、
一部のレプリカに悪意がある場合に性能が緩やかに低下する

という設計になっています。

5.1 前提条件

はじめに述べたように、

サブネットがn個のレプリカから構成され、
そのうち最大でf < n/3個のレプリカに欠陥がある

と仮定します。

欠陥のあるレプリカは、任意の、悪意のある（すなわちビザンチン）動作を示すかもしれない。通信は非同期であり、レプリカ間で送信されるメッセージの遅延に先験的な制限はないと仮定する。実際、メッセージ配送のスケジューリングは完全に敵対的な制御下にある可能性がある。ICコンセンサスプロトコルは、この非常に弱い通信の仮定下で安全性を保証する。しかし、生存性を保証するためには、部分的な同期を仮定する必要があります。これは、（大まかに言えば）ネットワークが短い時間間隔で周期的に同期することを意味します。この境界δは事前に知る必要はない（プロトコルは妥当な境界で初期化されるが、小さすぎる場合は動的に適応し、この境界を増加させる）。非同期ネットワークか部分同期ネットワークかにかかわらず、ある正直なレプリカから別のレプリカに送信されたすべてのメッセージは、最終的に配信されると仮定する。

5.2 プロトコルの概要

多くのコンセンサスプロトコルと同様に、ICコンセンサスプロトコルはブロックチェーンをベースにしている。プロトコルの進行に伴い、ツリーのルートである特別なジェネシスブロックから始まるブロックのツリーが成長する。ツリー内の非ジェネシスブロックはそれぞれ、一連の入力からなるペイロードと、ツリー内のブロックの親のハッシュを含んでいる（他の要素も含む）。各レプリカはこのツリーについて異なる部分的な見解を持っているかもしれませんが、すべてのレプリカは同じツリーについて見解を持っています。さらに、プロトコルの進行に伴い、このツリーには常に確定したブロックのパスが存在します。各レプリカはこのパスについて異なる部分的な見解を持っているかもしれませんが、すべてのレプリカは同じパスについて見解を持っています。このパスに沿ったブロックのペイロードの入力は、インターネットコンピュータの実行レイヤーで処理される順序の入力である(セクション7参照)。

プロトコルはラウンドで進行する。プロトコルのラウンドhでは、高さhの1つまたは複数のブロックがツリーに追加される。つまり、ラウンドhで追加されるブロックは、常にルートからちょうどhの距離にある。各ラウンドでは，擬似乱数処理により各レプリカに固有のランクを割り当てる．ランクは0，．, n - 1. この擬似ランダム処理はランダムビーコンを用いて実装される(下記5.5節参照)。最も低いランクのレプリカがそのラウンドのリーダーとなる。リーダーが正直でネットワークが同期している場合、リーダーはブロックを提案し、それがツリーに追加される。リーダーが誠実でない場合やネットワークが同期していない場合、他の上位のレプリカもブロックを提案し、そのブロックがツリーに追加されることがある。いずれにせよ、プロトコルのロジックはリーダーの提案したブロックを最優先し、このラウンドで何らかのブロックがこのツリーに追加されることになる。この結果、レプリカの欠陥やネットワーク遅延の増大により遅延が増大することがあっても、プロトコルのスループットは基本的に一定である。

5.3 その他の特性

ICコンセンサスプロトコルのその他の特性（PBFT [CL99]やHotStuff [YMR+18]と同様、またTendermint [BKM18]などの他のものとは異なる）は楽観的反応性[PS18]で、リーダーが正直であればネットワーク遅延の上界ではなく、実際のネットワーク遅延に応じたペースでプロトコルが進められる可能性があるということである。ICコンセンサスプロトコルのシンプルな設計は、ビザンチン障害が実際に発生した場合、その性能が非常に優雅に低下することも保証していることに留意してください。CWA+09]で指摘されているように、最近のコンセンサスに関する研究の多くは、障害が発生しない「楽観的な場合」の性能を向上させることに集中しており、その結果、プロトコルは危険なほど脆弱で、障害が発生すると事実上使用できなくなる可能性があります。例えば、[CWA+09]は、既存のPBFTの実装が、ある種のビザンチン行動（非常に単純な）の下でスループットがゼロになることを示しました。論文[CWA+09]では、ロバストコンセンサスを提唱し、一部のパーティが実際に破損したときに妥当なパフォーマンスを確保するために、最適条件でのピークパフォーマンスを一部犠牲にします（ただし、ネットワークは同期しているものと仮定します）。ICコンセンサスプロトコルは、[CWA+09]の意味において確かに堅牢である。リーダーが破損したラウンドでは（それ自体は1/3以下の確率で起こる）、プロトコルは効果的に他のパーティにそのラウンドのリーダーを引き継がせ、ほとんど大騒ぎをせずに、タイムリーに次のラウンドに移行させることが可能である。

5.4 公開鍵

プロトコルを実装するために、各レプリカはBLS署名方式[BLS01]の公開鍵と関連付けられ、各レプリカは対応する秘密署名鍵も持っている。レプリカと公開鍵の関連付けは、NNSが管理するレジストリから取得する(セクション1.5参照)。これらのBLS署名はレプリカが送信するメッセージの認証に使用される。また、このプロトコルでは、BLS署名の署名集約機能[BGLS03]を利用して、同じメッセージに対する多数の署名を集約してコンパクトなマルチシグネチャにすることができる。プロトコルは、公証(セクション5.7参照)と確定(セクション5.8参照)にこれらのマルチ署名を使用する。これは、ある形式のメッセージに対するn-f個の署名の集合体である。

5.5 ランダム・ビーコン

前述のBLS署名、マルチ署名に加え、BLS閾値署名方式を利用し、前述のランダム・ビーコンを実現する。高さhのランダムビーコンは、高さhに固有のメッセージに対する(f + 1)閾値署名である。プロトコルの各ラウンドで、各レプリカは次のラウンドのビーコンのシェアを放送するため、次のラウンドが始まるときに、すべてのレプリカはそのラウンドのビーコンを再構成するのに十分なシェアを持っているはずである。上述したように、高さhのランダムビーコンは、プロトコルのラウンドhで使用される各レプリカに擬似ランダムランクを割り当てるために使用される。閾値署名のセキュリティ特性のため、敵対者は1ラウンド以上前にレプリカの順位を予測することができず、これらの順位は事実上ランダムと同じになる。BLSの閾値署名の詳細についてはセクション3を参照。

5.6 ブロック作成

各レプリカは異なる時点でブロック作成者の役割を果たすことができる。ラウンドhのブロック作成者として、レプリカはブロックの木において、高さhのブロックBを高さh - 1のブロックB’の子として提案する。そのために、ブロックメーカーはまず、自分が知っているすべての入力からなるペイロードを集める（ただし、B’で終わる木の経路のブロックのペイロードにすでに含まれているものは含まれない）。ブロックBは、

ペイロード
B’のハッシュ、
ブロックメーカーのランク、
ブロックの高さh、

から構成される。

ブロックBの形成後、ブロックメーカーはブロックプロポーザルを形成する。ブロックプロポーザルは、

ブロックB、
ブロックメーカーのアイデンティティ
Bに対するブロックメーカーの署名

からなる。

5.7 公証

ブロックが公証されると、ブロックの木に事実上追加されます。ブロックが公証されるには、n - f個のレプリカがその公証をサポートする必要がある。高さhのブロックBが提案されたとき、レプリカはその提案が有効かどうかを判断する。これはBが前述の構文形式を持つことを意味する。特に、Bはブロックの木にすでにある(すなわち、すでに公証されている)高さh'のブロックB'のハッシュを含んでいなければならない。さらに、Bのペイロードはある条件を満たす必要がある（特に、ペイロードのすべての入力が様々な制約を満たす必要があるが、これらの制約は一般にコンセンサスプロトコルに依存しない）。また、ブロック作成者のランク（ブロックBに記録されている）は、ラウンドhでランダムビーコンがブロックを提案したレプリカに割り当てたランク（ブロック提案に記録されている）と一致しなければならない。

ブロックが有効であり、他の制約がある場合、レプリカは

Bのハッシュ、
Bの高さh、
サポートするレプリカのID、
Bのハッシュと高さh

からなるBの公証シェアをブロードキャストすることによって、ブロックの公証をサポートします。

Bに関する任意のn - f個の公証株集合を集約して、

Bのハッシュ
Bの高さh、
n-f個のサポートレプリカのID
Bのハッシュと高さhからなるメッセージへのn-f個の署名

からなるBの公証を形成することができる。

レプリカは、高さhの公証済みブロックを取得するとすぐに、ラウンドhを終了し、その後、高さhの他のブロックの公証をサポートしないことになる。この時点で、そのようなレプリカはこの公証を他のすべてのレプリカに中継します。このレプリカは、(1)他のレプリカから公証を受け取る、または(2)受け取った公証をn-f個集約する、のいずれかによって公証を得ることができることに注意してください。

成長不変性とは、各正直なレプリカが最終的に各ラウンドを終了し、次のラウンドを開始することで、公証済みブロックのツリーが成長し続けるというものです（これは部分同期ではなく、非同期の最終配送のみを仮定しています）。この成長不変性を以下で証明する(セクション5.11.4参照)。

5.8 最終化

ある高さhに複数の公証済みブロックが存在する可能性がある。しかし、あるブロックが最終化された場合、高さhに他の公証済みブロックが存在しないことが保証される。

これを安全不変量と呼ぶことにする。あるブロックが確定するためには、n - f 個のレプリカがその確定を支持しなければならない。あるレプリカが高さhの公証済みブロックBを獲得したとき、そのレプリカのラウンドhが終了することを思い出してください。その時点で、レプリカはブロックB以外の高さhのブロックの公証をサポートしているかどうかを確認します(B自体の公証をサポートしていてもいなくてもかまいません)。確定共有は公証共有とまったく同じフォーマットです (ただし、公証共有と確定共有が混同されないようにタグ付けされています)。Bに関する任意のn - f個の最終化共有のセットは、公証とまったく同じ形式を持つBの最終化を形成するために集約されることがあります (ただし、ここでも適切なタグが付けられています)。確定したブロックを取得したレプリカは、他のすべてのレプリカにその確定をブロードキャストします。

以下、安全不変性を証明する(セクション5.11.5参照)。安全不変性の一つの帰結は以下の通りである。Bは高さh、B'は高さh' ≤ hである。このとき、安全不変量は、B'で終わる公証済みブロックの木の経路がBで終わる経路の接頭辞であることを意味する（そうでなければ、高さh'の公証済みブロックが2つ存在し、最終化不変量に矛盾する）。したがって、レプリカが確定ブロックBを見るときはいつでも、Bのすべての祖先を暗黙のうちに確定しているとみなすことができる。安全不変量のため、これらの（明示的および暗黙の）確定ブロックに対して安全特性が保証される、つまり、すべてのレプリカがこれらの確定ブロックの順序に同意する。

5.9 遅延関数

このプロトコルでは、ブロック作成と公証活動のタイミングを制御する2つの遅延関数∆mと∆nを使用する。これらの関数はいずれも提案レプリカのランクrを非負の遅延量に対応付け、各関数はrにおいて単調増加し、すべてのr = 0, ... , n - 1に対して∆m（r）≤ ∆n（r）であると仮定されている。, n - 1.

これらの関数の推奨定義は、∆m(r) = 2δr および ∆n(r) = 2δr + 、δはある正直なレプリカから別のレプリカにメッセージを届ける時間の上限、≥0はプロトコルが速くなりすぎないようにするための「ガバナー」である。

これらの定義により、(1)リーダーが誠実であり、(2)誠実なレプリカ間で時間δ内に本当にメッセージが配送されるラウンドでは、有効性が保証される。実際、あるラウンドで(1)(2)がともに成立すれば、そのラウンドでリーダーが提案したブロックは最終決定されることになる。これを活性化不変量と呼ぶことにする。以下、これを証明する（5.11.6節参照）。

5.10 例

図 2 はブロックツリーである。

各ブロックには高さ(30, 31, 32, ... )とブロックメーカのランクが付けられている。また、この図では、♦N記号で示すように、ツリー内の各ブロックが公証されていることが示されている。これは、ツリー内の各公証済みブロックに対して、少なくともn - f個の異なるレプリカがその公証をサポートしていることを意味する。このように、ある高さのツリーには、複数の公証済みブロックが存在する可能性があります。例えば、高さ31では、ランク1と2のブロックメーカーが提案した2つの公証済みブロックが存在することがわかります。同じことが高さ34でも起こっている。また、高さ36のブロックは、♦F記号で示されるように、明示的に確定されていることがわかる。これは、n - f個の別個のレプリカがこのブロックの公証を支持したことを意味し、これらのレプリカ（または少なくともこれらの中の正直なレプリカ）は他のブロックの公証を支持しなかったことを意味します。このブロックの先祖はすべて、灰色の影がついていますが、暗黙のうちに確定されたと考えられます。

5.11 まとめ

それでは、このプロトコルがどのように機能するかをより詳しく説明します。具体的には、レプリカがいつブロックを提案し、レプリカがいつブロックの公証をサポートするかをより正確に説明します。ラウンドhのランダム・ビーコンが決定されたので、Pは自身のランクrPと、ラウンドhの他のレプリカQのランクrQを決定することができる。

5.11.1 ランダムビーコンの詳細

ラウンドhのランダムビーコン、またはラウンドhのランダムビーコンを構築するのに十分なシェアを受信するとすぐに、レプリカはラウンドhのランダムビーコンを他のすべてのレプリカにリレーする。レプリカはラウンドhに入るとすぐに、ラウンドh+1でのランダムビーコンを生成し、ブロードキャストします。

5.11.2 ブロック生成の詳細

レプリカPは、(1)ラウンドの開始から少なくとも∆m(rP ) 時間単位が経過し、 (2)P が現在見ている下位の有効なブロックがない場合にのみ、自分自身のブロックBPを提案する。Pはラウンドhに入ったときに高さh - 1の公証済みブロックを持つことが保証されているので、提案するブロックはこの公証済みブロックの子 (もしあれば他の高さh -1の公証済みブロック) とできることに注意すること。また、pがBPを提案する際には、BPの親の公証をすべてのレプリカに中継しなければならないことにも注意しましょう。レプリカQがランクrP < rQのレプリカPから有効なブロック提案を見た場合、(1)ラウンド開始から少なくとも∆m(rP ) 時間単位が経過し、(2)Qが現在見ているランクrP未満のブロックがない。

5.11.3 公証の詳細

レプリカPは、ランクrQのレプリカQが提案した有効なブロックBQの公証をサポートする。ただし、 (1) ラウンドの開始から少なくとも∆n(rQ)時間単位が経過し、 (2) Pが現在見ているランクrQ未満のブロックが存在しない場合に限る。

5.11.4 成長不変性の証明

成長不変性は、それぞれの公正なレプリカがいずれはそれぞれのラウンドを完了し次のラウンドを始めることを示す。すべての正直なレプリカがラウンドhを開始したと仮定する。ラウンドhにおける最下位の正直なレプリカPのランクをr ＊とする。いずれの場合も、あるブロックは最終的にすべての正直なレプリカに支持されなければなりません。つまり、あるブロックは公証され、すべての正直なレプリカはラウンドhを終了します。すべての正直なレプリカは、ラウンドh + 1のランダムビーコンの構築に必要なシェアを受け取り、ラウンドh + 1を開始することになります。

5.11.5 安全不変性の証明

安全不変性は、あるラウンドでブロックが確定した場合、そのラウンドでは他のブロックは公証されないというものである。安全不変量の証明を以下に示す。 1. 破損したレプリカの数がちょうどf ∗≦f < n/3であるとする。 2. ブロックBが公証された場合、その公証は少なくともn-f -f ∗個の正直なレプリカの集合Sによってサポートされていなければならない（集約署名の安全特性によって）。3. 3. (矛盾するが)別のブロックB' 6= Bが公証されたとする。その場合、その公証は少なくともn - f - f ∗個の正直なレプリカの集合S'によってサポートされていなければならない（ここでも集約署名のセキュリティ特性によって）。4. 4. 集合SとS'は不連続である(finalization logicによる)。5. したがって、n - f ∗ ≥ |S∪S' | = |S| + |S' | ≥ 2(n - f - f ∗ ) であり、n ≤ 3f となり、矛盾が発生する。

5.11.6 活性度不変性の証明

誠実なレプリカが時刻t以前に送信したすべてのメッセージが時刻t＋δ以前に宛先に到着するとき、ネットワークは時刻tにδ同期していると言う。Δn(1)≧Δm(0)+2δであるとする。

また、あるラウンドhにおいて、

ラウンドhのリーダーPは正直である
ラウンドhに最初に入る正直なレプリカQは時刻tに入る
ネットワークは時刻tとt＋δ＋δm（0）においてδ-同期である、

と仮定する。このとき、ラウンドhでPが提案したブロックは確定する。以下、活性不変性を証明する。

時刻tの部分同期では、すべての正直レプリカは時刻t+δ前にラウンドhに入る（Qのラウンドh-1を終えた公証とラウンドhのランダムビーコンは、この時間前にすべての正直レプリカに到着する）
ラウンドhのリーダーPは時刻t＋δ＋δm（0）前にブロックBを提案し、やはり部分同期により、このブロック提案は時刻t＋2δ＋δm（0）前に他のすべてのレプリカに配信されます。
∆n(1) ≥ ∆m(0) + 2δなので、プロトコル論理は各正直なレプリカがブロックBの公証をサポートし、他のブロックはサポートしないことを保証し、したがってBは公証され確定されることになる。

5.12 その他の問題

5.12.1 成長遅延時間

部分的な同期性の仮定のもとで、成長不変量の定量的バージョンを定式化し証明することも可能である。簡単のために、遅延関数が上記で推奨されたように定義されているとする： ∆m(r) = 2δr, ∆n(r) = 2δr + , さらに ≤ δ とする。時刻tにおいて、任意の正直レプリカが入ったラウンドの最高番号をhとする。最後に、ネットワークが区間[t, t + (3r ∗ + 2)δ]において常にδ同期であると仮定する。このとき、すべての正直なレプリカは時刻t + 3(r ∗ + 1)δより前にラウンドh + 1を開始する。

5.12.2 ローカルに調整された遅延関数

あるレプリカが数ラウンドに渡って確定したブロックを見ない場合、そのレプリカは公証のために自身の遅延関数∆nを増加し始める。レプリカは、ローカルに調整された公証遅延関数に同意する必要はない。

また、レプリカは遅延関数∆pを明示的に調整しないが、両方の遅延関数を局所的に調整することで、局所的なクロックドリフトを数学的にモデル化することができる。

このように、レプリカとラウンドによってパラメータ化された多くの遅延関数が存在する。このとき、活性化のために必要な臨界条件∆n(1) ≥ ∆m(0) + 2δは、max ∆n(1) ≥ min ∆m(0) + 2δとなり、最大値と最小値は与えられたラウンドのすべての正直なレプリカに対して取られている。このように、ファイナライゼーションが十分なラウンド数失敗した場合、すべての正直なレプリカは、最終的にこれが成立するまで公証遅延を増加させ、その後ファイナライゼーションを再開することになります。一部の正直なレプリカが他のレプリカよりも公証遅延関数を大きくしても、活性という点ではペナルティはありません（ただし、成長遅延という点ではあるかもしれません）。

5.12.3 公正性

コンセンサス・プロトコルで重要なもう一つの性質は、公正性です。一般的な定義をするよりも、活性不変性が有用な公平性特性を意味することを観察するのが先決です。活性不変性とは、基本的に、リーダーが正直でネットワークが同期しているラウンドでは、リーダーが提案したブロックが確定されることを意味する。このようなラウンドでは、リーダーが正直であるという事実により、そのブロックのペイロードに、リーダーが知っているすべての入力を含めることが保証される（ペイロードサイズに制限を設ける）。つまり、非常に大雑把に言えば、十分な数のレプリカに広められた入力は、高い確率で妥当な時間内に最終的なブロックに含まれることになる。

6 メッセージルーティング層

1.7節で述べたように、ICの基本的な計算単位はCanisterと呼ばれ、プログラムとその状態からなる点でプロセスの概念とほぼ同じである。ICは、Canister内のプログラムを実行し、他のCanisterや外部ユーザと通信するためのランタイム環境を提供する（メッセージパッシングにより）。コンセンサス層（セクション5参照）は入力をペイロードに束ね、それをブロックに配置し、ブロックが確定すると、対応するペイロードをメッセージルーティング層に配信し、実行環境で処理し、複製したステートマシン上でCanisterの状態を更新して出力を生成し、これらの出力がメッセージルーティング層で処理される。

イングレスメッセージ：これは外部ユーザーからのメッセージ、
クロスサブネットメッセージ：これは他のサブネット上のCanisterからのメッセージという2種類の入力を区別することが有用です。また、2つのタイプの出力を区別することができます：イングレスメッセージレスポンス。
イングレスメッセージレスポンス：イングレスメッセージに対するレスポンス（外部ユーザが取得可能）
クロスサブネットメッセージ：他のサブネット上のキャニスターへのメッセージです。

コンセンサスからペイロードを受け取ると、そのペイロードの入力はさまざまな入力キューに入れられる。サブネット上で動作する各CanisterCには、いくつかの入力キューがあります。Cへのイングレスメッセージ専用のキューが1つあり、Cが通信する他の各CanisterC'は、それ自身のキューを取得します（C'がサブネット上のCanisterである場合、そのキューは1つのキューとなります）。(C'がCと同じサブネット上にない場合、これらはクロスサブネットメッセージとなります）。

以下に詳述するように、各ラウンドにおいて、実行層はこれらのキュー内の入力の一部を消費し、関連するCanisterの複製された状態を更新し、様々な出力キューに出力を配置することになる。サブネット上で動作する各CanisterCには、いくつかの出力キューがあり、Cが通信する他の各CanisterC'は、それ自身のキューを取得する。(C'が C と同じサブネット上にない場合、これらはクロスサブネットメッセージとなる)。メッセージルーティング層は、これらの出力キューにあるメッセージを受け取り、それらをサブネット間のストリームに配置して、クロスネット転送プロトコルによって処理されるようにしますが、その仕事は、これらのメッセージを他のサブネットに実際に転送することです。

これらの出力キューに加えて、イングレス履歴データ構造も存在します。Canisterによってイングレスメッセージが処理されると、そのイングレスメッセージに対する応答がこのデータ構造に記録されます。その時点で、イングレスメッセージを提供した外部ユーザーは、対応するレスポンスを取得することができるようになる。(なお、着信履歴はすべての着信メッセージの完全な履歴を保持しているわけではありません)。また、クロスサブネットメッセージに加えて、イントラサブネットメッセージも存在することを述べておきます。これは、あるCanisterから同じサブネット上の別のCanisterへのメッセージです。メッセージルーティング層は、このようなメッセージを出力キューから対応する入力キューに直接移動させる。

図3は、メッセージルーティング層と実行層の基本的な機能を示しています。複製された状態は、Canisterの状態、前述のキューやストリームを含む「システム33の状態」、および入庫履歴データ構造からなることに注意してください。このように、メッセージルーティング層と実行層の両方が、サブネットの複製された状態の更新と維持に関与しています。この状態のすべてが完全に決定論的な方法で更新され、すべてのレプリカがまったく同じ状態を維持することが不可欠です。

また、コンセンサス層はメッセージルーティング層および実行層から切り離されていることに注意してください。つまり、コンセンサスブロックチェーンにおけるフォークは、そのペイロードがメッセージルーティングに渡される前に解決され、実際、コンセンサスはメッセージルーティングとコンセンサスに同期する必要がなく、少し先に実行することが許されているのです。

6.1 ラウンドごとの認証状態

各ラウンドで、サブネットの状態の一部が認証されます。ラウンドごとの認証状態は、連鎖鍵暗号 (セクション 1.6 参照) を用いて、具体的にはセクション 3 で述べた (n - f)-out-of-n 閾値署名スキームを用いて認証される。より詳細には、各レプリカは与えられたラウンドのラウンドごとの認証状態を生成した後、対応する閾値署名のシェアを生成し、これをそのサブネット内の他のすべてのレプリカにブロードキャストします。このような共有をn-f個集めると、各レプリカは結果として閾値署名を構築することができ、これがそのラウンドのラウンドごとの認証済み状態の証明書となります。署名の前に、ラウンドごとの認証状態は、Merkle木[Mer87]としてハッシュ化されることに注意してください。

あるラウンドのラウンドごとの認証状態は、以下のように構成される。

1. 最近サブネット間ストリームに追加されたクロスサブネットメッセージ、
2. イングレス履歴データ構造を含むその他のメタデータ、
3. 前ラウンドのラウンドごとの認証状態のMerkle木ルートハッシュから構成される。

ラウンドごとの認証済み状態には、サブネットの複製された状態全体は含まれないことに注意してください。これは、一般にこの状態が非常に巨大になり、ラウンドごとにこの状態のすべてを認証することは非現実的だからです（8.2参照）。ツリーの最初のブランチは、各Canisterに関するさまざまなメタデータを格納します(ただし、Canisterの複製された状態全体ではありません)。2番目のブランチは、イングレス履歴データ構造を格納します。3番目のブランチは、各ストリームの最近追加されたクロスサブネットメッセージの「ウィンドウ」を含む、サブネット間ストリームに関する情報を格納する。他のブランチは、ここでは説明しない他のタイプのメタデータを格納する。このツリー構造をハッシュ化してMerkleツリーにすることもできるが、このツリーは基本的にこのツリーと同じサイズと形状を持つ。ラウンドごとの認証状態は、ICの中でいくつかの方法で使用される。

出力認証
クロスサブネットメッセージとイングレスメッセージへの応答は、ラウンドごとの認証状態を使用して認証されます。Merkle木構造を使用し、Merkle木のルート上の閾値署名と、ルートからその出力を表すリーフまでのMerkle木のパス上の（およびそれに隣接する）ハッシュ値を提供することによって、個々の出力（クロスサブネットメッセージまたはイングレスメッセージ応答）を任意のパーティに認証することができる。したがって、個々の出力を認証するために必要なハッシュ値の数は、Merkle木の深さに比例し、Merkle木のサイズが非常に大きくても、通常は非常に小さくなる。したがって、1つの閾値署名で多くの個別出力を効率的に認証することができる。

非決定性の防止と検出
コンセンサスは、各レプリカが同じ順序で入力を処理することを保証している。各レプリカはこれらの入力を決定論的に処理するため、各レプリカは同じ状態を得るはずである。しかし、ICは(偶発的な)非決定論的な計算が発生した場合に、それを防止・検出するための堅牢性を付加して設計されています。ラウンドごとの認証状態は、このために用いられる機構の一つである。我々は認証に(n - f)-out-of-n閾値署名を使用し、f < n/3なので、認証される状態のシーケンスは1つだけである可能性があります。なぜ状態の連鎖が重要なのかを知るために、次のような例を考えてみましょう。4つのレプリカP1, P2, P3, P4があり、1つが破損しているとします（P4とします）。各レプリカP1,P2,P3は同じ状態からスタートします。- ラウンド1では、非決定論的な計算のため、P1、P2はサブネットAに送信するメッセージm1を計算し、P3はサブネットAに送信するメッセージm' 1を計算する。- ラウンド3では、P2、P3はサブネットCに送信するメッセージm3を計算し、P1はサブネットCに送信するメッセージm'3を計算する。P1 m1 → A m2 → B m'3 → C P2 m1 → A m' 2 → B m3 → C P3 m'1 → A m2 → B m3 → C ここではレプリカP1、P2、P3はそれぞれ有効な計算シーケンスを実行するが、非決定性によりこれらのシーケンスは同一ではないと仮定する（非決定性とは、レプリカP1、P2、およびP3がそれぞれ独立に計算し、その結果、複製P1、P2、P3がそれぞれ有効なシーケンスを実行し、その結果、複製のレプリカP1、複製のレプリカP3 がそれぞれ有効なシーケンスを実行すると仮定する）。(非決定性はないはずなのに、この例ではあると仮定しているのである）。ここで、状態を連鎖させなかったとする。P4は堕落しており、どんな署名をしてもよいので、ラウンド1の状態「m1 → A」、ラウンド2の状態「m2 → B」、ラウンド3の状態「m3 → C」に対して、3/4 の署名をすることができる、ただし対応するシーケンスm1 → A, m2 → B, m3 → Cはどんな有効な計算のシーケンスとも一致しない可能性がある。さらに悪いことに、そのような無効な計算の列は、他のサブネット上で矛盾した状態を引き起こす可能性があります。連鎖によって、たとえ非決定性があったとしても、認証された状態のシーケンスは、正直なレプリカによって実際に実行された有効な計算シーケンスに対応することが保証されます。- コンセンサスによる調整ラウンドごとの認証状態は、2つの異なる方法で、実行層とコンセンサス層を調整するためにも使用されます。- コンセンサス調整（Consensus throttling）。各レプリカは、そのレプリカが認証済みである最新のラウンドを記録しています。また、公証されたブロックを持つ最新のラウンドも記録します（これは公証済み高さと呼ばれます）。公証済み高さが公証済み高さより大幅に大きい場合、これは実行が合意に遅れていることを示す信号であり、合意を調整する必要があることを意味します。この遅れは、非決定論的な計算によるものかもしれませんし、単にレイヤー間の性能の不一致によるものかもしれません。具体的には、公証された高さと認証された高さの差が大きくなると、各レプリカは「govern」値を増加させる(これは、セクション5.12.2の「局所調整遅延関数」の概念を利用したものである)。- 州固有のペイロード検証。セクション 5.7 で説明したように、ペイロードの入力は、特定の有効性チェックを通過しなければならない。実際には、これらの有効性チェックは、ある程度、状態に依存する可能性がある。我々が省略した詳細は、各ブロックがラウンド番号を含み、これらの有効性チェックは、そのラウンド番号の認証済みステートに関して行われるべきであると理解していることである。この検証を行う必要があるレプリカは、そのラウンド番号の状態が認証されるまで待ち、そのラウンドの認証された状態を使用して検証を行います。これにより、非決定論的な計算でも、すべてのレプリカが同じ有効性テストを実行することが保証されます(そうしないと、コンセンサスに行き詰まる可能性があるため)。

6.2 クエリコールとアップデートコール

これまで説明してきたように、受信メッセージは、サブネット上のすべてのレプリカで同じ順序で処理されるように、コンセンサスを通過する必要があります。しかし、サブネットの複製状態を変更しない処理を行うingressメッセージには、重要な最適化が可能です。これはクエリコールと呼ばれ、他のイングレスメッセージがアップデートコールと呼ばれるのとは対照的です。クエリコールは、Canisterの状態を読み取り、場合によっては更新する計算を行うことができますが、Canisterの状態に対する更新がレプリケートされた状態にコミットされることは決してありません。そのため、クエリコールはコンセンサスを経ずに直接1つのレプリカで処理することができ、クエリコールからの応答を得るまでの待ち時間を大幅に短縮することができます。なお、クエリに対する応答は、イングレス履歴データ構造には記録されません。そのため、ラウンドごとの認証済み状態メカニズムを、クエリコールに対する応答の認証に直接使用することはできない。ただし、そのような応答を認証するための別のメカニズムとして、認証済み変数が提供されている。ラウンドごとの認証状態の一部として、サブネット上の各Canisterは、そのCanisterの認証変数である小さなバイト数を割り当てられ、その値は更新コールによって更新され、ラウンドごとの認証状態メカニズムを使用して認証される可能性がある。さらに、Canisterはその認証変数を使用して、Merkle木のルートを保存することができる。このように、Canisterへのクエリコールに対する応答は、そのCanisterの認証変数をルートとするMerkleツリーのリーフである限り、認証される可能性がある。

6.3 外部ユーザー認証

イングレスメッセージとクロスサブネットメッセージの主な違いの1つは、これらのメッセージを認証するために使用されるメカニズムである。クロスサブネットメッセージの認証に閾値署名が使用されることは、すでに前述（セクション6.1参照）したとおりである。NNSのレジストリ（セクション1.5参照）は、クロスサブネットメッセージの認証に使用される閾値署名の公開検証鍵を保持する。外部ユーザーのためのセントラル・レジストリは存在しない。むしろ、外部ユーザーは、公開署名検証キーのハッシュであるユーザー識別子(別名プリンシパル)を使用して、Canisterに自分自身を識別する。このユーザーは対応する秘密署名鍵を持っており、この鍵はイングレスメッセージに署名するために使用されます。このような署名と対応する公開鍵は、イングレスメッセージと一緒に送信されます。ICは自動的に署名を認証し、ユーザー識別子を適切なCanisterに渡します。Canisterは、ユーザー識別子と、イングレスメッセージで指定された操作の他のパラメータに基づいて、要求された操作を承認することができる。初回利用者は、ICとの最初のやり取りの際に、鍵ペアを生成し、公開鍵から利用者識別子を導出する。再来訪ユーザは，ユーザエージェントが記憶している秘密鍵を用いて認証される．ユーザは、署名委任を利用して、1つのユーザIDに複数のキー・ペアを関連付けることができます。これは，一人のユーザが複数のデバイスから同一のユーザ ID を用いて IC にアクセスすることを可能にするためである．37

7 実行層

実行環境は一度に一つの入力を処理する。この入力は、入力キューの1つから取り出され、1つのCanisterに向けられる。この入力とCanisterの状態に基づいて、実行環境はCanisterの状態を更新し、さらに出力キューにメッセージを追加し、（おそらく以前の入力メッセージに対する応答で）入力履歴を更新することができる。あるラウンドでは、実行環境は複数の入力を処理する。スケジューラは、あるラウンドでどの入力をどのような順序で実行するかを決定する。スケジューラの詳細には触れないが、いくつかの目標を挙げておく。

決定論的でなければならない、すなわち、与えられたデータのみに依存しなければならない
Canister間でワークロードを公平に分配しなければならない（ただし、待ち時間よりもスループットを最適化する）
各ラウンドで行われる作業の総量は、サイクル（セクション1.8参照）で測定され、ある事前決定量に近いものでなければなりません

実行環境が（メッセージ・ルーターとともに）対処しなければならないもう1つの課題は、あるサブネット上のCanisterが、他のサブネット上のCanisterが消費できるよりも速くクロスサブネットのメッセージを生成している状況です。このため、生成するCanisterを調整する自己調整メカニズムが実装されています。その他にも、実行環境によって処理される多くのリソース管理および帳簿管理タスクがあります。しかし、これらのタスクはすべて決定論的に処理されなければならない。

7.1 ランダムテープ

各サブネットは分散型擬似ランダム生成器（PRG）にアクセスすることができる。セクション3で述べたように、擬似乱数ビットは、それ自体が（f + 1）out-of-n BLS署名であるシードから導出され、これをランダムテープと呼ぶ。

コンセンサスプロトコルの各ラウンドには、異なるランダムテープが存在する。このBLS署名はコンセンサスで使用されるランダムビーコンに使用されるものと似ているが（セクション5.5参照）、その仕組みは多少異なる。コンセンサスプロトコルでは、高さhのブロックが確定するとすぐに、各正直なレプリカは高さh + 1のランダムテープのシェアを解放する。これには二つの意味がある。

高さhのブロックが確定する前に、高さh + 1のランダムテープは予測不可能であることが保証されています。
高さh + 1のブロックが完成するまでに、レプリカは高さh + 1のランダムテープを作成するために必要なすべての共有を持っている。

疑似ランダムビットを得るためには、サブネットはこれらのビットの要求を行う必要がある。このような疑似ランダムビットの要求は、あるラウンド、例えばhにおいて実行層からの「システムコール」として行われる。そしてシステムは、後で高さh + 1のランダムテープが利用可能になったときに、その要求に応答する。上記（1）の性質により、要求された疑似乱数ビットは、要求された時点では予測不可能であることが保証される。

上記特性（2）により、要求されたランダムビットは、通常、次のブロックが確定される時点で利用可能である。実際、現在の実装では、高さhのブロックが確定した時点で、コンセンサス層（セクション5参照）は高さhのブロック（のペイロード）と高さh＋1のランダムテープを同時にメッセージルーティング層に配信して処理することになる。

8 連鎖鍵暗号 II: チェインエボリューション・テクノロジー

1.6.2 節で述べたように、連鎖鍵暗号には、ブロックチェーンに基づく複製状態マシンを堅牢かつ安全に経時的に維持する技術の集合体であり、これらをまとめて chain-evolution technology と呼んでいる。各サブネットは、多くのラウンドのエポック（通常、数百ラウンドのオーダー）で動作します。ガベージコレクション、早送り、サブネットのメンバー変更、秘密の積極的な再共有、プロトコルのアップグレードなど、エポックと連動した周期で実行される多くの重要な保守活動がチェーンエボリューション技術によって実装されています。チェーンエボリューション技術には、サマリーブロックとキャッチアップパッケージ（CUP）という2つの本質的な要素がある。

8.1 サマリーブロック

各エポックの最初のブロックはサマリーブロックである。サマリーブロックは、様々な閾値署名方式(セクション3参照)のシェアを管理するために使用される特別なデータを含んでいる。2つの閾値スキームがある。

(f + 1)-out-of-n方式。エポック毎に新しい署名鍵が生成される
(n - f)-out-of-n方式。エポック毎に署名鍵が再共有される

低閾値方式はランダムビーコンとランダムテープに使用され、高閾値方式はサブネットの複製された状態を証明するために使用される。DKGプロトコル(セクション3.5参照)は、各署名鍵について、取引のセットを持ち、各レプリカはこの取引のセットから署名鍵のシェアを非対話的に取得できることを要求していることを想起してほしい。また、NNSは、特にサブネットのメンバーシップを決定するレジストリを維持していることを思い出してほしい(セクション1.5参照)。レジストリ(およびサブネットメンバーシップ)は時間の経過とともに変化する可能性がある。したがって、サブネットは、さまざまな目的でさまざまな時間にどのレジストリのバージョンを使用するかについて合意しなければなりません。この情報もサマリーブロックに格納される。

エポックiのサマリーブロックは、以下のデータフィールドを含んでいます。

currentRegistryVersion：　このレジストリバージョンは、エポックiを通して使用されるコンセンサス委員会を決定する。コンセンサス層が行うすべてのタスク（ブロック作成、公証、最終化）は、この委員会によって実行される。
nextRegistryVersion：　コンセンサスの各ラウンドで、ブロック作成者は自分の知っている最新のレジストリバージョン（提案されたブロックが拡張するブロックより前のものであってはならない）を提案に含めることになる。これにより、エポックiの要約ブロックのnextRegistryVersionの値がかなり最新のものになる。エポックiのcurrentRegistryVersionの値は、エポックi - 1のnextRegistryVersionの値に設定される。
currentDealingSets：　後述するように、エポックiの閾値署名委員会(すなわち、対応する閾値署名鍵のシェアを保持するレプリカ)は、エポックi - 1の合意委員会である。
nextDealingSets：　エポック i の currentDealingSets の値は、エポック i - 1 の nextDealingSets の値（エポック i - 2 で収集された取引からなる）に設定される（※6）。
collectDealingParams：　エポックiの間に、ブロックメーカーは、これらのパラメータに関連して検証されたディーリングセットを、提案されたブロックに含める。低しきい値方式では、ディーリング委員会はエポックi のnextRegistryVersionの値に基づき、再共有される株式はエポックi のnextDealingSetsの値に基づき、エポックi - 1の受信委員会であり、エポックi の合意委員会となる。また、エポック i の閾値署名委員会は、エポック i - 2 の受信委員会であり、エポック i - 1 のコンセンサス委員会であることに注意してください。

※6. 詳細は省略するが、エポックi - 1で必要な取引をすべて収集できなかった場合、フォールバックとして、エポックiのnextDealingSetsの値は、事実上エポックiのcurrentDealingSetsの値となる。この場合、プロトコルでは、さらに過去の取引委員会と閾値署名委員会を適切に利用することになる。

特に、consensus committeeの構成はcurrentRegistryVersionに基づき、コンセンサスに使用されるランダムビーコンはcurrentDealingSetsに基づき、エポックiにおけるコンセンサスはcurrentRegistryVersionとcurrentDealingSetsの値に依存する。さらに、他のブロックと同様に、エポックiの開始時に公証された複数の要約ブロックが存在する可能性があり、そのあいまいさはエポックiの合意によって解決される必要がある。この循環しているように見える問題は、新しい要約ブロックの関連する値が古い要約ブロックから直接コピーされているので、エポック i-1の開始時に要約ブロックがエポックiの開始前に確定していることを主張することによって解決される。これは暗黙の同期性の仮定であるが、非常に学術的な仮定である。実際、セクション5.12で説明した "consensus throttling "があるためです。 2で説明した「コンセンサス調整」のため、またエポックの長さが非常に大きいため、実際にはこのようなことは起こりえません。エポックi - 1の要約ブロックを確定せずにコンセンサスがエポックi - 1の終わりに到達する前に、公証遅延関数が天文学的に大きくなるので、我々が省略した詳細は、エポックi - 1で必要なすべての取引を収集できない場合、予備として、エポックiのnextDealingSetsの値は事実上エポックiの現在のDealingSetsの値に設定されているというものである。この場合、プロトコルはさらに過去のディーリング委員会や閾値署名委員会を適宜利用することになる。ファイナライゼーションに必要な部分的同期性の仮定は、(すべての実用的な目的のために)基本的に確実に満たされることになる（※7）。

※7. また、エポックiで収集される取引は、エポックiのサマリーブロックのデータ、特にnextDealingSetsとnextRegistryVersionの値に依存することに注意してください。そのため、これらの取引はエポックiのサマリーブロックが確定するまで生成されるべきではなく、また検証することもできない。

8.2 CUPs

CUPを説明する前に、まずランダムビーコンの詳細を一つ指摘しておこう。これは本質的な特徴ではないが、CUPの設計に影響を与える。CUPは（ブロックチェーン上にはない）特別なメッセージで、レプリカがあるエポックで作業を開始するために必要な（ほとんど）すべてを持ち、以前のエポックについては何も知らない状態になっています。以下のデータフィールドで構成されています。

複製された状態全体に対するMerkleハッシュツリーのルート(セクション6.1のようなラウンドごとの部分的な認証状態とは対照的)。
エポックの要約ブロック
エポックの最初のラウンドのためのランダムビーコン
サブネットの(n - f)-out-of-n閾値署名鍵の下での上記フィールドへの署名

あるエポックのCUPを生成するために、レプリカは、そのエポックのサマリーブロックが確定し、対応するラウンドごとの状態が認証されるまで待たなければならない。すでに述べたように、複製された状態全体をMerkle木としてハッシュ化する必要があります。このプロセスを高速化するために多くの技術が使用されていますが、それでもかなりのコストがかかるため、エポックごとに1回だけ実行されます。

CUPはこのMerkleツリーのルートのみを含むため、レプリカがそのピアから必要なステートを取得できるように、特別なステート同期サブプロトコルが使用されます。CUPに高閾値署名を使用しているため、有効なCUPはどのエポックでも1つだけであり、さらに状態を取得できるピアが多数存在することが確認されています。また、閾値署名方式の公開鍵は時間経過後も一定であるため、サブネットの現在の参加者を知らなくてもCUPを検証することができる。

8.3 チェーン・エボリューション技術の実装

ガベージコレクション：
あるエポックのCUPに含まれる情報のため、各レプリカはそのエポック以前に処理されたすべての入力と、それらの入力を順序付けるために必要なすべてのコンセンサスレベルプロトコルメッセージをパージしても安全である。

早送り
あるサブネットのレプリカが仲間から大きく遅れてしまった場合（ネットワークに長時間接続していなかったり、接続されていなかったりしたため）、または新しいレプリカがサブネットに追加された場合、コンセンサスプロトコルを実行してその時点までのすべての入力を処理しなくても、最新のエポックの最初に早送りすることができます。

このようなレプリカは、直近のCUPを取得することで行うことができる。CUPに含まれるサマリーブロックとランダムビーコン、および（まだ消去されていない）他のレプリカからのプロトコルメッセージを用いて、このレプリカは対応するエポックの初めからコンセンサスプロトコルを前方に実行することができます。また、レプリカは状態同期サブプロトコルを使用して、エポックの先頭に対応する複製された状態を取得し、コンセンサスによって生成された入力を処理することもできます。

図5は、早送りを説明する図である。ここでは、追いつく必要のあるレプリカが、エポック開始時にCUPを有すると仮定する（例えば、高さ101から始まる）。CUPには、高さ101で複製された状態のメルクルツリーのルート、高さ101のサマリーブロック（緑で表示）、高さ101のランダムビーコンが含まれています。このレプリカは、状態同期サブプロトコルを使用して、高さ101の完全な複製状態をピアから取得し、この状態を検証するためにCUPのMerkleツリーのルートを使用します。この状態を取得した後、レプリカはプロトコルに参加し、高さ102、103などのブロック（および合意に関連する他のメッセージ）をピアから取得し、複製された状態のコピーを更新することができます。このレプリカは、そのピアからブロック（およびその公証と確定）を取得できる限り迅速に（実行レイヤーが許す限り迅速に）、それらの確定されたブロックを処理します。

サブネットメンバーシップの変更：
あるエポックにおいてレジストリのどのバージョンが有効かを暗号化するためにサマリーブロックがどのように使われるか、またサブネットメンバーシップ、より具体的には様々なタスクのメンバーシップ委員会を決定するためにどのように使われるかは、すでに説明しました。レプリカがサブネットから削除された後でも、(可能であれば)さらに1エポック間は割り当てられた委員会の職務に参加する必要があることに注意してください。

積極的な秘密の再共有：
署名鍵の生成と再共有にサマリーブロックがどのように使用されるかについて、すでに議論した。必要であれば、必要なサマリーブロックをCUPから取得してもよい。

プロトコルのアップグレード：
CUPは、プロトコルのアップグレードを実施するためにも使用される。プロトコルのアップグレードはNNSによって開始される(セクション1.5参照)。詳細は省くが、基本的な考え方は次のとおりである。

プロトコルの新バージョンをインストールするとき、エポック開始時のサマリーブロックはそのことを示す。
旧バージョンのプロトコルを実行しているレプリカは、サマリーブロックを完成させ、対応するCUPを作成するのに十分な時間、コンセンサスの実行を継続します。ただし、空のブロックのみを作成し、メッセージルーティングと実行にペイロードを渡すことはありません。
新バージョンのプロトコルがインストールされ、新バージョンのプロトコルを実行しているレプリカは、上記のCUPから完全なプロトコルの実行を再開します。

参考文献：

[BGLS03] D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. In E. Biham, editor, Advances in Cryptology - EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003, Proceedings, volume 2656 of Lecture Notes in Computer Science, pages 416– 432. Springer, 2003.

[BKM18] E. Buchman, J. Kwon, and Z. Milosevic. The latest gossip on BFT consensus, 2018. arXiv:1807.04938, http://arxiv.org/abs/1807.04938.

[BLS01] D. Boneh, B. Lynn, and H. Shacham. Short Signatures from the Weil Pairing. In C. Boyd, editor, Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, December 9-13, 2001, Proceedings, volume 2248 of Lecture Notes in Computer Science, pages 514–532. Springer, 2001.

[But13] V. Buterin. Ethereum whitepaper, 2013. https://ethereum.org/en/ whitepaper/.

[CDH+21] J. Camenisch, M. Drijvers, T. Hanke, Y.-A. Pignolet, V. Shoup, and D. Williams. Internet Computer Consensus. Cryptology ePrint Archive, Report 2021/632, 2021. https://ia.cr/2021/632.

[CDS94] R. Cramer, I. Damg˚ard, and B. Schoenmakers. Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols. In Advances in Cryptology - CRYPTO ’94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings, volume 839 of Lecture Notes in Computer Science, pages 174–187. Springer, 1994.

[CL99] M. Castro and B. Liskov. Practical Byzantine Fault Tolerance. In M. I. Seltzer and P. J. Leach, editors, Proceedings of the Third USENIX Symposium on Operating Systems Design and Implementation (OSDI), New Orleans, Louisiana, USA, February 22-25, 1999, pages 173–186. USENIX Association, 1999.

[CWA+09] A. Clement, E. L. Wong, L. Alvisi, M. Dahlin, and M. Marchetti. Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults. In J. Rexford and E. G. Sirer, editors, Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2009, April 22-24, 2009, Boston, MA, USA, pages 153–168. USENIX Association, 2009. http://www.usenix. org/events/nsdi09/tech/full_papers/clement/clement.pdf.

[Des87] Y. Desmedt. Society and Group Oriented Cryptography: A New Concept. In C. Pomerance, editor, Advances in Cryptology - CRYPTO ’87, A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16-20, 1987, Proceedings, volume 293 of Lecture Notes in Computer Science, pages 120–127. Springer, 1987

[DLS88] C. Dwork, N. A. Lynch, and L. J. Stockmeyer. Consensus in the presence of partial synchrony. J. ACM, 35(2):288–323, 1988.

[Fis83] M. J. Fischer. The Consensus Problem in Unreliable Distributed Systems (A Brief Survey). In Fundamentals of Computation Theory, Proceedings of the 1983 International FCT-Conference, Borgholm, Sweden, August 21-27, 1983, volume 158 of Lecture Notes in Computer Science, pages 127–140. Springer, 1983.

[FS86] A. Fiat and A. Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In Advances in Cryptology - CRYPTO ’86, Santa Barbara, California, USA, 1986, Proceedings, volume 263 of Lecture Notes in Computer Science, pages 186–194. Springer, 1986.

[GHM+17] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich. Algorand: Scaling Byzantine Agreements for Cryptocurrencies. Cryptology ePrint Archive, Report 2017/454, 2017. https://eprint.iacr.org/2017/454.

[Gro21] J. Groth. Non-interactive distributed key generation and key resharing. Cryptology ePrint Archive, Report 2021/339, 2021. https://ia.cr/2021/339.

[JMV01] D. Johnson, A. Menezes, and S. A. Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA). Int. J. Inf. Sec., 1(1):36–63, 2001.

[Mer87] R. C. Merkle. A Digital Signature Based on a Conventional Encryption Function. In Advances in Cryptology - CRYPTO ’87, A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16-20, 1987, Proceedings, volume 293 of Lecture Notes in Computer Science, pages 369–378. Springer, 1987.

[MXC+16] A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song. The Honey Badger of BFT Protocols. In E. R. Weippl, S. Katzenbeisser, C. Kruegel, A. C. Myers, and S. Halevi, editors, Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, pages 31–42. ACM, 2016.

[Nak08] S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008. https: //bitcoin.org/bitcoin.pdf.

[PS18] R. Pass and E. Shi. Thunderella: Blockchains with Optimistic Instant Confirmation. In J. B. Nielsen and V. Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part II, volume 10821 of Lecture Notes in Computer Science, pages 3–33. Springer, 2018

[PSS17] R. Pass, L. Seeman, and A. Shelat. Analysis of the Blockchain Protocol in Asynchronous Networks. In Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part II, volume 10211 of Lecture Notes in Computer Science, pages 643–673, 2017.

[Sch90] F. B. Schneider. Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Comput. Surv., 22(4):299–319, 1990.

[YMR+18] M. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta, and I. Abraham. HotStuff: BFT Consensus in the Lens of Blockchain, 2018. arXiv:1803.05069, http://arxiv. org/abs/1803.05069.

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