検証可能なコンピューティング

検証可能なコンピューティング（または検証済み計算、検証済みコンピューティング）は、コンピュータが検証可能な結果を​​維持しながら、ある関数の計算を、おそらく信頼できない他のクライアントにオフロードすることを可能にします。他のクライアントは関数を評価し、関数の計算が正しく実行されたことの証明とともに結果を返します。この概念の導入は、SETI@homeのようなプロジェクトで信頼できないユーザーに計算を「アウトソーシング」するという現象がますます一般的になっていること、また、クラウド コンピューティングのように、計算能力の低いデバイスが計算タスクをより強力な計算サービスにアウトソーシングできるようにしたいという要望が高まっていることに起因しています。この概念は、Babai らの研究^{[ 1 ]}に遡り、「計算のチェック」（Babai ら）、「計算の委任」^{[ 2 ]} 、 「認証済み計算」^{[ 3 ]}、検証可能なコンピューティングなど、さまざまな用語で研究されてきました。検証可能なコンピューティングという用語自体は、ロザリオ・ジェンナロ、クレイグ・ジェントリー、ブライアン・パルノによって形式化され^{[ 4 ]}、ミカリの「認証済み計算」^{[ 3 ]を反映している。}

比較的弱い計算デバイス（クライアント）からより強力な計算サービス（ワーカー）へ計算タスクをアウトソーシングしたいという願望の高まりと、実際の作業を行わずにクライアントのソフトウェアを改変してもっともらしい結果を返す不正なワーカーの問題^{[ 5 ]}が、検証可能な計算の概念の形式化を促した。^{[ 4 ]}

検証可能なコンピューティングは、クライアントの入力に基づいてアウトソーシングされた関数の結果を取得し、その正当性を証明することだけでなく、クライアントが関数をゼロから計算する場合よりもはるかに少ない計算量で証明を検証できることにも関係しています。

信頼できないワーカーによって実行される関数の計算の検証には、セキュア コプロセッサの使用^{[ 6 ] [ 7 ]} 、トラステッド プラットフォーム モジュール(TPM) ^{[ 8 ]} 、対話型証明^{[ 9 ] [ 10 ]}、確率的に検証可能な証明^{[ 11 ] [ 12 ]}、効率的な引数^{[ 13 ] [ 14 ]}、および Micali の CS 証明^{[ 15 ]}など、かなりの注意が払われてきました。これらの検証は、クライアントがワーカーと対話して正当性の証明を検証する必要がある対話型^{[ 13 ] [ 14 ]}か、ランダム オラクルモデルで証明できる非対話型プロトコル^{[ 15 ]}のいずれかです。

検証済みの計算の中で最大規模のもの（SETI@home）は、複製による検証を採用している。

SETI @homeの検証プロセスは、1台のクライアントマシンと多数のワーカーマシンで構成されます。クライアントマシンは、同一の作業単位を複数のコンピュータ（少なくとも2台）に送信します。

機械の電源が誤って切れたり、通信障害が発生したりして、妥当な時間内に十分な結果が得られない場合、または計算エラーや、実際に作業を行わずに虚偽のデータを提出するなどの不正行為によって結果が一致しない場合、クライアントマシンは他のワーカーマシンにさらに同一の作業単位を送信します。結果の最小クォーラム（多くの場合2）が一致すると、クライアントはそれらの結果（およびその作業単位の他の同一の結果）が正しいとみなします。クライアントは、正しい結果を返したすべてのマシンに報酬を与えます。

Gennaro ら^{[ 4 ] は}、検証可能な計算スキームの概念を、関数 F: {0,1} ⁿ → {0,1} ^mの計算で協力する 2 つの多項式時間当事者間のプロトコルとして定義した。このスキームは、主に次の 3 つのフェーズから構成される。

1. 前処理。この段階は、Fに関連付けられた補助情報を計算するために、クライアントによって一度だけ実行されます。この情報の一部はワーカーと共有される公開情報であり、残りはクライアントが保持する非公開情報です。
2. 入力準備。この段階では、クライアントは関数の入力に関する補助情報を計算します。この情報の一部は公開され、残りは非公開としてクライアント内に保持されます。公開された情報はワーカーに送信され、入力データに基づいて関数Fが計算されます。
3. 出力の計算と検証。この段階では、ワーカーは前の2つのフェーズで計算された関数Fと入力に関連付けられた公開情報を使用して、提供された入力に対する関数Fのエンコードされた出力を計算します。この結果はクライアントに返され、クライアントは前のフェーズで計算されたプライベート情報を使用してワーカーから返された結果をデコードし、出力の実際の値を計算することで、その正しさを検証します。

検証可能な計算スキームの定義概念は、クライアントとワーカー間のやり取りをちょうど2つのメッセージに最小限に抑え、プロトコルのさまざまなフェーズで各当事者から相手方へ1つのメッセージが送信されます。^{[ 4 ]}

検証可能な計算は理論的には可能であることが示されているものの（完全準同型暗号や確率的に検証可能な証明を用いる場合）、既知の構成のほとんどは実際には非常にコストがかかる。最近、検証可能な計算を実用化しようとする研究者がいくつか現れている。その一つがテキサス大学オースティン校の研究者による研究である。^{[ 18 ]}著者らは、確率的に検証可能な証明に基づく議論システムから始め、そのコストを10 ²⁰分の1に削減した。また、 Pepperシステムにこの技術を実装した。著者らは、「これまでのところ、安全なシステムを構築するためのツールとして、PCPと議論システムは無駄なものではないという結論に至っている」と述べている。

現在ではさまざまなグループによる多数の実装を含む全体的な領域が調査された。^{[ 19 ]}

2010年代には、検証可能なコンピューティング技術がブロックチェーン技術において実用的な応用例が増加した。^{[ 20 ]}