ゼロ知識証明の主要な実現方法

こちらの続きとなっています。

ゼロ知識証明の設計手順

命題の数学的表現への変換

例：「4より大きな数xを知っていること」→「x – 4 > 0を満たす入力値wを知っていること」

上記の例は「範囲の証明」である。命題の種類を分類すると以下の3つに分類できます。

「範囲の証明」：一定の範囲内であること

「知識の証明」：あることを知っていること

「演算の証明」：演算結果が正しいこと

対話型知識証明の構成

このフェーズで「完全性、健全性」を付与する。

初期設定プロセス、証明プロセス、検証プロセスに必要な鍵情報や、証明者と検証者やり取りする方式（シュノアプロトコル等のアルゴリズム）を構成する。

知識証明において健全性付与のために、証明者自身がコントロールできない乱数が必要になる。

その方法として

1. 信頼できる第三者が証明者、検証者に乱数を共有する
2. 検証者が乱数を生成して証明者に送る

の2パターンがある。

1は効率悪いが、データサイズが少ない。

2は効率良いが、データサイズが多い。

ゼロ知識性の付加

命題が正しいか否か以外の情報を削除するために、証明者は乱数を利用して秘匿すべき情報（例えばパスワード）にマスキングを行います。

非対話型への変換

証明者と検証者の間でやり取りを行う必要がある「対話型」では非同期で行われる分散システムなどでは利用が難しいため、非対話型への変換が行われます。

各方式の相違点

zk-SNARK

命題の数学的表現への変換

証明者は「演算の証明」を「多項式の係数を知っていること」に変換して示すことにより証明します。

対話型知識証明の構成

LIPと呼ばれるモデルに基づく知識証明を構成します。LIPは計算能力に制限のある証明者を想定した方法です。証明者と検証者間でやり取りするデータをベクトル形式で線形変換を行うことによって命題の難易度に関わらず一定にできます。

ゼロ知識性の付加・非対話型への変換

証明に必要なデータである「多項式の係数」を乱数でマスキングしつつ、ペアリング写像を利用して非対話型へ変換を行います。ここでは乱数生成、共有を信頼できる第三者に任せます。

zk-STARK

命題の数学的表現への変換

証明者は「演算の証明」を「演算の過程（グラフ構造で表現される）を知っていること」に変換して示すことにより証明します。

対話型知識証明の構成

IOPと呼ばれるモデルに基づく知識証明を構成します。IOPはLIPと同様に計算能力に制限のある証明者を想定した方法です。検証者は公開されているランダム性に基づいて乱数を生成し、乱数を利用した問い合わせを証明者に対して複数回行います。問い合わせに対する証明全てが正しければ検証成功となります。

ゼロ知識性の付加・非対話型への変換

証明者がハッシュ関数を利用して検証者の代わりに自身で乱数を生成し、それらに対応する証明を検証者へ送信する仕組みへと変換することによって非対話型へ変換する。

Bulletproof

命題の数学的表現への変換

証明者は「範囲の証明」をコミットメントという技術を使い「演算の証明」に変換して示すことにより証明します。

対話型知識証明の構成

Bulletproofという内積証明に基づいて知識証明を構成します。証明者はコミットメントに基づいて、入力値と出力値の関係性を表す2つのベクトルを構成し、それらの内積がある性質を満たすことを検証者が検証できるような知識証明を構成します。Bulletproofでは、証明者が公開されてるランダム性と検証者から送信される乱数を利用して証明を構成するため信頼できる第三者が不要です。

ゼロ知識性の付加・非対話型への変換

zk-STARKと同様です。

各方式の比較

About うみのこ 4 Articles

vscode大好きな人です。新しい技術に触れるのが好きで三度の飯と同じくらいコーディングが好きです。