本ブログではブロックチェーン領域においてセキュリティ担保のために用いられることのあるゼロ知識証明と呼ばれる技術について理屈を理解することを目的としています。

ゼロ知識証明の特性の直感的な理解

ゼロ知識証明には「完全性、健全性、ゼロ知識性」が求められる。

• ゼロ知識性
  • 検証者は、証明者が持っている命題が真である場合、真であることが必ずわかる
• 健全性
  • 検証者は、証明者が持っている命題が偽である場合、高い確率でそれが偽であると見抜ける
• ゼロ知識性
  • 証明者の持つ命題が真であるなら、検証者が証明者から知識を盗もうとしても「命題が真である」事以外の何の知識も得ることができない

ゼロ知識証明の例（シュノアプロトコル）

y = g^x mod p （pは素数、gは正の整数）の時に、yからxを求める問題は離散対数問題と呼ばれている。一般にxからyを求めることは簡単だが、yからxを求めることは困難であることが知られている。（p, gは十分に大きくする必要あり）

シュノアプロトコルを利用することで、証明者は、離散対数問題y = g^x mod pの答えを知っていることを検証者に対してゼロ知識証明で証明することができる。

1. フェーズ1: 命題の数学的表現への変換
   1. 「証明者はパスワードxを知っている」という命題を「離散対数問題 y = g^x mod pの答えを知っている」という命題に変換する。
2. フェーズ2: 対話型知識証明の構成（完全性、健全性の付加）
   1. 証明プロセス1
      1. 証明者と検証者の間でやり取りを行い、命題の証明に必要なデータを生成する。証明者は、0から(q – 1)の範囲で乱数rを選び、c = g^r mod pを計算し、cを検証者に送る。ここで、乱数rの範囲が0から(q – 1)と制限されているのは、y = g^x mod pが取り得る値が0から(q – 1)となっているからである。c = g^r, g^q = 1 mod pが成立していることから、c * 1 = g^(r + q) mod pが成立する。つまり、yはrの時とr + qの時で同じであり、その後もq回ごとに同じ値が繰り返される。
   2. 証明プロセス2
      1. 検証者は、証明者がコントロールできない乱数を送信する。検証者は、0から(q – 1)の範囲で乱数eを選び、eを検証者に送る。
3. フェーズ3: ゼロ知識性の付加
   1. 証明プロセス3
      1. 命題の真偽以外の情報が分からなくなるように乱数を付加する。証明者は、z = r + ex mod qを計算し、zを検証者に送る。
   2. 検証プロセス
      1. 検証者は、g^z = g^(r+ex) = g^r*(g^x)^e = cy^e mod pが成立しているか確かめる。

ここで、シュノアプロトコルがゼロ知識証明である事を示すために完全性、健全性、ゼロ知識性の観点からそれぞれの性質を満たしているか否かを記す。

• 完全性：「証明者が知識xを持っているとき、検証者は必ず承認する」
  • g^z = cy^e mod pが成り立てば、証明者が正しく証明を作成したことを検証者は信じることが出来る。
• 健全性：「証明者が知識xを持っていない時、検証者は証明者が知識を持っていないと高い確率で分かる」
  • 知識xを知らない証明者が検証プロセスを突破できると仮定すると、
    • 異なるeに対してともに検証をパスできなければならない。
    • g^z1 = cy^e1, g^z2 = cy^e2 mod pが成り立つので辺々を割ると、
    • g^(z1-z2) = y^(e1-e2) mod p → y = g^{(z1-z2)/(e1-e2)} mod p
    • x = (z1-z2)/(e1-e2)とすると、y = g^x mod pとなり、これは「証明者がy = g^x mod pを満たすxを知っている」と判断できるので「知識xを知らない証明者が検証プロセスを突破できる」という仮定が誤りである事が分かり、健全性を満たす
• ゼロ知識性：「検証者は、証明者が知識xを持っていること以外のいかなる情報も得られない」
  • 検証者は下記の(c, z）に関する知識を証明者から受け取る
    • r ← {0, … , q – 1｝
    • c = g^r mod p, z = r + ex mod q
  • 一方、検証者は証明者から(c, z)を受け取らくとも下記のようにして(c, z)を作り出せる
    • z ← {0, … , q – 1｝
    • c = g^r * y^(-e) mod p
  • したがって、ゼロ知識性も満たす。

ゼロ知識証明の一般化したモデル

zk-SNARK, zk-STARK, Bulletproof等のゼロ知識証明の主な実現方法

実際には証明者と検証者の間でやり取りを行う「対話型」ではなく、ゼロ知識証明を「非対話型」に変換して利用する。（ペアリング写像、Fiat-Samir等の手法がある）

About うみのこ 4 Articles

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