見出し画像

【超説】インターネットコンピュータ(IC)入門：コンセンサスアルゴリズムをざっくりと解説する

佐藤もとい

難解なインターネットコンピュータのコンセンサスアルゴリズムを厳密性を放棄して誤解をおそれずに超ざっくりと解説します！
これで、あの面倒なICのドキュメントを読みこなせるようになる！を目指します。

関連リンク：

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

本記事は厳密性よりも理解の容易性を重視しています。大きな流れを記述するにとどめ、詳細な手続きについては末尾の参考資料などをもとに各自で確認して下さい。

用語については、以下が参考になります

１．基本の確認

1.1　インターネットコンピュータの基本構成

まずは、インターネットコンピュータの基本構成のおさらい。

ネットワーク構成要素の階層構造[1]

１）サブネット：
・サブネットは、世界中のデータセンターにある複数のサーバ（ノード）で構成されています。
・サブネット内のノードはレプリカと呼ばれ、すべてが同じ実行状態をコピーしたものとなっています。（同じ入力に対して同じ出力をする）
・これは、サブネット内のレプリカのうち、いくつかが故障（クラッシュや悪意のあるノード）しても動作することを保証するためです。
・サブネット１つが、ひとつのコンピュータ（ステートマシン）として動作すると考えると、分かりやすいかと思います。

２）キャニスター：
・キャニスターは、サブネット上（レプリカ上）で動作するプログラム（プログラム＋状態）です。
・インターネットコンピュータ(IC)上で動作する分散アプリケーション（Dapp）は、複数のキャニスターにより構成されます。

３）network nervous system（NNS；神経ネットワーク網）：
・NNSは、インターネットコンピュータの管理を行う特殊な分散アプリケーション（Dapp:ダップ）です。
・NNSは、主に３つのキャニスターで構成されます。

①レジストリ・キャニスター：
ICの構成、すなわちどのレプリカがどのサブネットに属しているか、サブネットや個々のレプリカに関連する公開鍵などを保存します。
②ガバナンス・キャニスター：
・ICをどのように進化させるかについての意思決定と投票を管理します
・ICPユーティリティトークンをロックアップ（ガバナンストークン）した所有者が投票
③台帳・キャニスター：
・ICPユーティリティトークンの管理台帳です

1.2　通常の公開鍵・秘密鍵による「メッセージの暗号化」

コンセンサスアルゴリズムを解説するための基本となる公開鍵・秘密鍵について、一般的なサーバでの概要をおさらいします。

1.2.1　公開鍵・秘密鍵による暗号通信

サーバAからサーバーBにメッセージを送るとき
①サーバBはあらかじめ公開鍵Bを生成しておく
②サーバBは公開鍵Bをもとに秘密鍵Bを生成しておく
③公開鍵Bの取得
サーバAは、あらかじめサーバBから公開鍵Bを取得しておく
（公開鍵Bを盗まれても大きな問題はない）
④メッセージの暗号化
サーバAは公開鍵Bをもとにメッセージを暗号化する
⑤メッセージ（暗号）の送信
サーバAは暗号化したメッセージをサーバBにおくる
⑥メッセージの復号化
サーバBは、秘密鍵Bをもとに暗号化されたメッセージを復号化する

1.2.2　ハッシュ（Hash）によるデータ改変の確認

データ（絵や動画などすべて）に変更が加えられていないかをチェックするためにハッシュ（暗号学的ハッシュ）が使われます。

以下、ハッシュについて簡単に説明します。

①ハッシュMaの生成
ハッシュ「メッセージM」をハッシュ関数に入力すると、出力としてハッシュ=16進数（など）を出力します。
　メッセージM　➡ハッシュ関数➡　a492bd0f…….882c（ハッシュMa）

※出力されたハッシュから元のデータ（メッセージM）を復元することはできません

②メッセージM＋ハッシュの送信
ハッシュとともにサーバAからサーバBにメッセージMとともにハッシュMaを送ります
　サーバA ➡ 「メッセージM」＋「ハッシュMa」　➡サーバB

③ハッシュMbの生成
端末Bは受け取った「メッセージM」からハッシュを作成します
　メッセージM　➡ハッシュ関数　➡　a492bd0f…….882c（ハッシュMb）

④ハッシュMaとハッシュMbの比較
サーバBはハッシュaとハッシュbを比べて、一致していればメッセージMが改変されていないことがわかります。（つまり同じデータをハッシュ関数に入力した際の出力は必ず同じ値になる）
　もし、メッセージMが改変されてメッセージM'となっていると、ハッシュMaとハッシュMbは必ず一致しません

1.2.3　公開鍵・秘密鍵による「署名」

次に、ブロックチェーンで使われている「署名」について確認します。

ハッシュと公開鍵・秘密鍵のメッセージ暗号化の手順を逆にすると、相手からのメッセージの「真正性」を確認できる「署名」を行うことができます。

ビットコインなどで取引を行いたいときに、ビットコイン所有者が秘密鍵を使ってメッセージ（送金情報など）を送るときに、そのメッセージの真正性を受け手が公開鍵を使って確認できます。
・本人確認：秘密鍵を持っているビットコイン所有者であること
・メッセージ確認：署名した後でメッセージが改ざんされていないこと

２．ICの公開鍵・暗号鍵

２．１　「公開鍵と暗号鍵による署名」を概観する

詳細な説明の前に、まずは先に説明したサーバ間の「署名」やりとりに対応させてみます。（実際にはメッセージの署名時にサブネット内でゴニョゴニョするのだが、ちょっと棚にあげておく）


⓪事前処理
・NNSはサブネットA生成時に、公開鍵Aを生成して記憶する
・NNSはサブネットAが消滅するまで公開鍵Aを保持し続ける
・同時にサブネットA内のレプリカは秘密鍵Aを生成し、守秘のため再生成し続ける（実際には秘密鍵は分割・分散配置されるがとりあえず）

レプリカaからレプリカbにメッセージを送る場合
①メッセージのハッシュaの生成

②メッセージへの署名
・レプリカaは、ハッシュ関数によりメッセージのハッシュを生成する
・レプリカaは、送信メッセージの真正性を証明するために、秘密鍵Aを使ってハッシュから生成した「署名」をメッセージに追加する
②「メッセージ＋署名」の送信
レプリカaは、レプリカbに「メッセージ＋署名」を送信する
③公開鍵Aの取得
「メッセージ+署名」を受信したレプリカbは、NNSよりサブネットAの公開鍵Aを取得する
④署名の「真正性」の確認
レプリカbは、署名を公開鍵Aにより復号化して、メッセージの真正性を確認する
・本人（A)確認
　公開鍵Aで復号化により
・メッセージが改ざんされていないことを確認
　ハッシュの比較により

それでは、実際におこなわれているゴニョゴニョ（コンセンサスアルゴリズム）を解説します。

２．２　前提知識

１）サブネットとレプリカ（ノード）
・サブネットは、複数のレプリカ（ノード）で構成される
　- ノードの数は「3の倍数+1」
　- 7台以上、現状アプリケーション（Dapp）は13台で運用されている
・1/3台までのレプリカに「障害」や「悪意のあるノード」があっても正常に動作させる（レプリカ7台の場合2台までの障害）

２）サブネット内のレプリカは同期して動く
・サブネット内のレプリカは、「同じ入力に対して同じ処理を実行し、同じ値を出力する」ように同期して動作する（➡一次的に同期していなくても、最終的には同期して動く）
・このため、レプリカはステートマシン（状態遷移マシン）という構造を利用して、サブネット内のレプリカが同じ状態となるよう状態更新を同期することにより、各複製（レプリカ）が同じ動作となるようにする
　- 各状態は「ある入力」を受けると、規定された「処理」と「出力」を行い、状態を更新する（別の状態に遷移する）
　- ステートマシンは、複数の状態と、その遷移関係が規定されている
　- 一つのアップデートメッセージ（状態更新を起こすメッセージ）により、複数の状態更新が発生する

３）サブネットの公開鍵と秘密鍵
・サブネットが生成されたときに、専用の「サブネット毎に単一の公開鍵」を生成してNNSで保持する。当該サブネットが削除されるまで「公開鍵」は保持され続ける
・各サブネットは、NNSから別サブネットの「公開鍵」を取得することができる
・秘密鍵は、サブネット内の各レプリカに分割・分散して配置され、常に更新し続けることにより守秘性を保持する

※実際は、レプリカ側で分割・分散した秘密鍵（秘密鍵シェア）を生成して、これの正当性を確認できたところで、「サブネット毎に単一の公開鍵」を生成する。常に秘密鍵シェアを更新しても、「サブネット毎に単一の公開鍵」は変わらない。

２．３　メッセージを実行するまでの流れ

１）ピア・トゥ・ピア層
・メッセージをサブネット内のレプリカ（ノード）の間で転送する

２）コンセンサス層
・何をどの順番で実行するかについて、レプリカ（ノード）間で合意する
・フォールトトレランスの実現（1/3台未満までの故障、悪意のあるノードに対処）
・サブネット内で独立して管理されるブロックチェーンを利用する

３）メッセージルーティング層
・メッセージの集配を行う（サブネット内やサブネット間のキャニスターに向けて）

４）実行層
・入力キューに配置されたメッセージをもとに処理を実行（状態を更新）して、出力を出力キューに配置する

インターネットコンピュータ・プロトコルの層構成[5]

例えば、データの更新を伴う「アップデートコール」メッセージMをキャニスタCで実行する場合の一連の処理を概観してみよう。

アップデートメッセージの受信～実行までの流れ：
１）サブネットAのレプリカxが「アップデート」メッセージMを受信する
２）ピア・ツー・ピア層を使って、サブネット内のすべてのレプリカにメッセージMをブロードキャストする
３）メッセージMを受け取ったレプリカaはコンセンサス層を使って「コンセンサスアルゴリズム（後述）」を実行して、ブロックBのペイロード（実行層が実行できるメッセージの束）を形成する
４）ペイロードをメッセージルーティング層に送信、メッセージルーティング層はメッセージMを入力キューに入れる
５）実行層がメッセージM（アップデートメッセージ）を処理して、応答Rを出力キューに配置して、キャニスターCの状態を更新する

２．４　各ノードがどの順序で実行するかを合意する（しきい値署名）

以下でnは
n：サブネット内のレプリカ（ノード）の台数
とします

コンセンサスアルゴリズムは以下を目的として処理を行います

  • サブネット内のレプリカn台のうちn・1/3台までの障害（故障や悪意のあるノード）があっても問題なく動作することを保証する

  • サブネット内のレプリカの障害（故障や悪意のあるノード）を検証する

  • ブロックメーカー：
    -     ブロックメーカーとなったレプリカは、メッセージM（ブロックB）を提案し、「真正性」の検証を公証人（Notary）に依頼する。

  • 公証人（Notary）：
    - リーダー以外のレプリカが「公証人」となる
    - 署名のための秘密鍵は各レプリカで分割・分散して保持している
    - 公証人となったレプリカは、メッセージM（ブロックB）の「真正性」を検証して問題がない場合に公証シェア（暗号化された署名）をブロックBにつける
    - 公証人のうちn・2/3が公証シェアを付与したとき、メッセージM（ブロックB）が真正であるとして公証（暗号化された署名）をブロックBに付与する（これを署名と呼ぶ）

※n・2/3が公証シェアを付与したことを確認できなかった場合への対処としてファイナライズ（ファイナライズシェア）によるプロトコルがあるが、本記事では省略します。

コンセンサス・アルゴリズム（しきい値署名）の大きな流れ
---------------------------------------------------------------
①ブロックメーカーは、ランダム値によりn/3未満+1台のレプリカが選出される。実行順序を付与され、最も値が低いブロックメーカーがリーダーとなる。
②最初のリーダーがブロックBを提案（メッセージMの検証を依頼）する
③各公証人がリーダーからのブロックB（メッセージM）を受取り、検証し、それぞれの「真正性」をみとめたとき公証シェア（暗号化された署名）をブロックBに付与する
④n・2/3の公証人が公証シェアを付与したとき、ブロック（メッセージM）が真正であるとしてファイナライズ＝公証（暗号化された署名）をブロックBに付与する
⑤④の段階で「真正性」がみとめられなかったときは、別のブロックメーカーがリーダーとなり①～③を繰り返す

例えば、サブネット内のレプリカ（ノード）の台数が7台だった場合

①3台がブロックメーカーとなり、そのうちの1台が最初のリーダーとなる。
②リーダーがブロックを提案（メッセージMの検証を依頼）する。
③リーダー以外の6台のレプリカが公証人となり、リーダーからのブロック（メッセージM）を受取り、検証し、それぞれが「真正性」をみとめたとき公証シェア（暗号化された署名）をブロックBに付与する。
④6台の公証人のうち5台が公証シェアを付与したとき、ブロック（メッセージM）が真正であるとして公証（暗号化された署名）をブロックBに付与する。

２．５　署名の確認

サブネット内外のキャニスターでメッセージを送受信する場合など、コンセンサス層の処理をへたメッセージ（ブロック）の「真正性」を確認したい場合には、ブロックに記入されている「署名」を当該サブネットの「公開鍵」で確認することができます。

２．６　専門用語との対応

今回の記事と、コンセンサスアルゴリズムに関連して、技術解説やホワイトペーパーなどで出てくる用語のとの対応をとります[4]。

１）MPC（Multi Party Computation）
・BLSしきい値署名：
 ICプロトコルのコンセンサスアルゴリズム（本記事の分割・分散した秘密鍵を使った署名処理）
（今回は登場しませんが、ビットコインとのインテグレーションとの関係で、「ECDSAしきい値署名」という用語もあります[3][4]）
・秘密分散（秘密鍵シェア）：
サブネット内の各レプリカに秘密鍵を分散させて（秘密鍵シェア）単独では秘密鍵がわからないようにする暗号技術
・VSS（一定の公開鍵）
サブネット毎に割り当てられた「公開鍵（48byte）」。サブネットが消去されないかぎり、一定の値をとり続ける。（便利！）

２）NiDKG
・非対話の乱数から秘密鍵生成
乱数による秘密鍵の生成、ランダムビーコン（ブロックマスターの選出に使う乱数）、ランダムテープ（実行層で使う乱数）で使用される。
・秘密鍵シェアの安全な分配
サブネット内の各ノード（レプリカ）へ秘密鍵シェア（分割・分散した秘密鍵）を閲覧・改ざんされないようにセキュアに分配する。

３）チェイン・エボリューション（Chain-evolution）
・再シェアリング（re-sharing）
一定期間毎に秘密鍵シェアを変更できる機能。
・CUP(catch up package）
サブネットの復旧・アップグレード時に利用する「サブネットレプリカを起動するために必要なすべてのものを含むデータバンドル」。今回の記事では登場しない。
・その他
今回の記事では登場しないので省略しますが、「ガーベッジコレクション」「早送り」「サブネットレプリカ交換」「プロトコルアップデート」などもチェイン・エボリューション関連の用語となります。

コンセンサスアルゴリズムに関する解説は以上です。

参考資料：

[1] インターネットコンピュータの技術的概要
[2] インターネットコンピュータ上でコンセンサスを実現する
[3]【Dfinity】Internet Computer の概要と Bitcoinとの統合についての解説
[4]「【Dfinity】Internet Computer の概要と Bitcoinとの統合についての解説」 を噛み砕いて粉砕する
[5] ホワイトペーパー


いいなと思ったら応援しよう！