ゼロ知識証明(ZK-SNARKS) Part2

Junki Yuasa
Acompany
Published in
16 min readJun 10, 2019

はじめに

こんにちは. Acompanyの湯浅です. この記事は「zk-SNARKs — A Realistic Zero-Knowledge Example and Deep Dive」をまとめて翻訳したものです. Part1 を読んでいないからはこちらからお読みください.

復習 : zk-SNARKには、証明者と検証者という2人の主要な当事者がいます. 証明者はzk-SNARKを使用して, 機密情報が何であるかを明らかにせずに, ある事実について検証者に証明したいと考えています.

zk-SNARKとは何ですか?

技術的な話をする前に、zk-SNARKが一番に満たすべき条件について説明しましょう.

  1. Completeness(完全性) : その記述が真実であり, 検証者と証明者が正直であるならば, その証明は受け入れられます.
  2. Soundness(健全性) : その記述が誤っている場合, 悪意のある証明者はそれが真であると確信させることができません.

上の2つに加えて, zk-SNARKは以下のことが求められます.

  1. Zero-knowledge(知識ゼロ) : その記述が真である場合, 検証者はその記述が正しいという事実を超えて何かを知ることはできません.
  2. Succinct(簡潔) : 証明のサイズは数ミリ秒以内に検証されるために十分小さい必要があります.
  3. Non-Interactive(非対話) : 検証者に送信される情報は1セットだけなので, 証明者と検証者の間でやり取りはありません.
  4. ARgument : 計算機科学的に健全な証明 : 多項式時間を行使する証明者に対して健全性は成り立つ.
  5. of Knowledge : 証人(事実を証明するために必要な個人情報)へのアクセスなしに証明を組み立てることはできない.

上記の条件を考慮して, zk-SNARKがブロックチェーンと組み合わせてどのように使用されるのかの例を見ていきましょう. BobとAliceの間の最初の例を使用します. Aliceは自分の銀行口座から別の口座への送金を希望しており, 送金を開始するのにBobが必要です. — そのシナリオをzk-SNARKとブロックチェーンを使ってどのように実装できるかを説明しましょう.

注 : 以下の例はスケーラブルではありませんが, zk-SNARKの概要を理解するには十分です.

このシナリオの4人のアクター:

Alice — 証明者

2.

Acme-Bank — 検証者, 銀行口座認証トランザクションのための信頼できる第三者, およびzk-SNARKのセットアップのための信頼できる第三者

3.

Bob — Acme-Bankコールセンターの代表

4.

Self-Sovereign Identity Solution— Acme Bank アプリへのデジタルID情報のデータプロバイダ, およびzk-SNARKのセットアップのための信頼できる第三者

下の図は, Aliceが自分の身元情報をAcme BankのBobに提供せずにある口座から別の口座に送金する方法の一例を示しています.

  1. スマートコントラクト対応ブロックチェーンを作成します. この例ではEthereumを使用しましょう.
  2. trueと評価された場合に「1」を返すプログラムが作成されます.

2a. インプットには, 複数の当事者(Alice, Self-Sovereign Identity Solution, Acme Bank)が使用するパブリックなインプットと, 証明者(Alice)のみが提供するプライベートなインプット(秘密)が含まれます.

2a_i. 公開: 名前, 電話番号, ブロックチェーンのアドレス, 現在の口座の所有者であるAliceの銀行口座認証, 1時間のタイムアウト(詳細は後述).

2a_ii. 非公開(AliceまたはSelf-Sovereign Identity Solution) : 社会保障番号, 生年月日

2a_iii. 非公開(Aliceのみ) : Secret Pin

b. zk-SNARKパラメータを設定し, 証明者と検証者の鍵を生成します.

2b. Self-Sovereign Identity SolutionとAcme Bankの間でマルチパーティー計算(MPC)を使用して, zk-SNARKをセットアップするためのパブリックパラメーターを生成します. MPCはzk-SNARKのためのパラメータを生成するための信頼されたセットアップフェーズに複数のパーティーが参加することを可能にします — これは1人のパーティーがキーを作成することへのリスクを最小にします. 信頼できるセットアップフェーズに参加しているユーザーの1人が危険にさらされていない場合, 生成されたパラメータは安全です. セットアップに参加したすべてのユーザーが危険にさらされている場合, パラメーターを使用して誤った証明を生成することができるため, zk-SNARKプロセスの価値が無くなります.

2c. 検証者のキーと検証プログラムはEthereumブロックチェーン内のインスタンス化されたスマートコントラクトに埋め込まれます.

3. AliceはAcme Bankのアプリを開き, 自分の指紋を使って自分の身元をアプリに認証してからアプリに入ります.

3a. 彼女はアプリの[Contact Us]エリアに移動し, [Call Acme with Prior Authentication]ボタンをタップします.

3a_i. Aliceが「Call Acme with Prior Authentication」ボタンをタップした後, Aliceが銀行の顧客であるかどうかを尋ねる要求がAcme 銀行に送信されます. 次にAcme BankはブロックチェーンにAliceがまだ現在の顧客であることを示すトランザクションを送信します.

3a_ii. Aliceはアプリ上で次の質問を聞かれます. これらの質問(社会保障番号と生年月日)は銀行アプリにデータを提供するアプリケーション(Self-Sovereign Identity Solution)を介して回答できます.

3a_ii_1. あなたの社会保障番号は何番ですか? 123–45–6789

3a_ii_2. あなたの生年月日は何ですか? 1/1/2000

3a_ii_3. あなたのSecret Pinは何ですか? 7327
なぜSecret Pinを入力するのでしょうか?これは, 誰かが何らかの形でアプリにアクセスし, デジタルIDアプリケーションを利用して社会保障番号と生年月日の回答を入力し, Aliceとして銀行とやり取りするケースに備えています.

4. ゼロ知識証明(zk-SNARK)を生成するためのpublic inputであるAliceの名前, 電話番号, 公開デジタルID, そしてAliceが銀行の顧客であることの認証がアリスの回答(private input)と併合されます.

4a. 証明はブロックチェーンの検証スマートコントラクトに送信されます.

5. スマートコントラクトは”true”を返し, Acme Bankはそれを監視して独自の内部システムに”true”の応答を記録します.

6. Acme Bankのアプリのボタンが, AliceがAcme Bankに電話するために使用可能になりました. アリスは 銀行振込を開始するためにボタンをタップすると, Acme Bankのコール担当者、ボブに繋がります。

上記の例は, Aliceが自分の口座から別の口座への送金を開始するためにAcme Bankに電話をかけたい場合に、zk-SNARKがどのように機能するかを説明しています. 上記の例では, AliceがBobと機密性の高いアイデンティティ情報を共有する必要がなくなり, さらに Acme Bankの平均処理時間が短縮されるため, コストが削減されます.

第三者の信頼と現在の顧客の証明

zk-SNARKの上記の例の1つの重要な要素はAliceがAcme Bankにアカウントを持っているという銀行の証明です. これは意外と見落とされやすい要素です. zk-SNARKプロセスに関与する必要のあるサードパーティがある場合, それはどのように組み込まれるでしょうか?様々な方法が考えられますが, Proof of Current Customerと呼ばれるproof of existenceの形式を組み入れることができます.

Proof of Current CustomerはAcme Bankでは次のように機能します.

  1. Aliceが顧客になった時, またはすでに顧客である時, 銀行はAliceのアドレスにトランザクションを送信することで証明をします. (Aliceが銀行の顧客であることを示すためにAliceのAcme Bankのアプリが読みとる暗号化されたペイロードがトランザクションに含まれます.)
  2. 発行者(Acme Bank)の身元はAcme Bankのパブリックアドレスを確認することによって検証されます. ブロックチェーンではスマートコントラクトにパブリックアドレスのレジストリがあります. レジストリは, 特定の所有者、またはコントラクトのレジストリの作成者によってのみ更新できます.
  3. 次に新しいトランザクションが, AliceがAcme Bankの顧客であるという暗号化されたデータペイロードと共にAcme Bankからアリスのパブリックアドレスに送信され, 彼女は次の60分間事前認証なしでアクメ銀行に電話をかけることができます.

注 : 上記の方法には複数の方法があります. たとえば, 単純なトランザクションを使用する代わりに, 関連するデータを保持している分散型ストレージシステムに保存されているファイルを使用して, 顧客データとAcme Bankのデジタル署名を検証することができます.

上記の例では, Aliceは自分自身についての情報を共有することなくAcme BankのBobと通信し, ある銀行口座から別の銀行口座への送金を承認させることができました. プライバシー, セキュリティ, そして透明性を橋渡しして情報の交換と検証を行うことで, zk-SNARKとブロックチェーンは非常にうまく連携できます.

zk-SNARKのユースケース

上記のシナリオに加えて, zk-SNARKはさまざまな分野で使用できます. 次に例を示します.

  1. 計算の検証
  2. スマートコントラクトにzk-SNARKを使用できるようにすることができる暗号通貨(ユーザーのプライバシー保護). 例: Zcash, Ethereum

3. パブリック・プライベートブロックチェーン間の来歴証明. (プライベートチェーンで発生した全てのトランザクションをパブリックチェーンに記録する代わりに, 証明をパブリックチェーンに記録できます.

4. パスワードなしの認証(上記のAliceとBobの例と同じ)

5. アイデンティティに関する情報を条件付きで共有できます. 例えば, 年齢を明らかにすることなく自分が21歳以上であることを証明できます.

zk-SNARKが広く利用されるようになると, データの保存方法が変わる可能性があります. 会社は現在持っているほど顧客/ユーザーについての多くのデータを保存する必要はないかもしれません. 将来的には, 組織はブロックチェーンと対話し, 現在のプロセスと通信するためにゼロ知識証明を使用することでデータ漏洩を軽減し, ユーザーデータのプライバシーをさらに高め, 組織のリスクを減らすことができます. 人々の間で機密データを共有することもさらに減らすことができます.

zk-SNARKのユーザーに対する信頼を最小にするためにさらに改善することができる重要な領域は, 信頼されたセットアップ段階の削除です. 信頼すべきセットアップ段階を排除し, 知識の証明を提供するためのゼロ知識暗号化の使用プロセスをさらに改善する技術が開発されつつあり, ゼロ知識暗号化に関する研究が進行中です.

zk-SNARKのプログラムの動作

基本的なzk-SNARKプログラムがどのように見えるかに興味があると思う人のために, 下記の例を提供します.

事前認証を使用したアリスとボブの電話 — zk-SNARKプログラムの入力と出力のみ(使用例はZoKrates):

  1. zk-SNARKは数字でうまく動作するので, 文字列入力を数字に変換する必要があります.
  2. Public Name : Alice. Unicodeの10進数への変換プログラムを実行します: => 65 108 105 99 101, 全てのスペースを削除してインプットは6510810599101 です.
  3. Public Phone Number : (555–666–7777); Unicodeの10進数への変換プログラムを実行します: => 53 53 53 45 54 54 54 45 55 55 55 55, 全てのスペースを削除してインプットは535353455454544555555555 です.
  4. Public Blockchain Address : 0x4ef377462b03b750d52140c482394a6703d0d338;
    Unicodeの10進数への変換プログラムを実行します: => 0 48 120 52 101 102 51 55 55 52 54 50 98 48 51 98 55 53 48 100 53 50 49 52 48 99 52 56 50 51 57 52 97 54 55 48 51 100 48 100 51 51 56, 全てのスペースを削除してインプットは0481205210110251555552545098485198555348100535049524899525650515752975455485110048100515156 です.
  5. Public Bank Attestation Setup and Call:
    a. 最初のステップ: Acme BankはAliceが顧客であることを示すデータペイロードとともに, Aliceのパブリックアドレスにトランザクションを送信します. このトランザクションはAliceがアカウントを開くとき, またはAliceが初めてAcme Bankのアプリで自分のアカウントを認証するときに発生します.
    b. Aliceが ”Call with prior Authentication”ボタンをタップすると, 銀行はAliceがAceme Bankの顧客であることを示すAcme Bankから以前に送信したAliceへのトランザクションをチェックします. 見つかった場合, Acme BankはAliceが現在の顧客であることを示す暗号化されたデータペイロードと共に, トランザクションをアリスのパブリックアドレスに送信します. AliceのスマホはAcme Bankからの新しいトランザクションを監視し, 見つかったら最近のトランザクションからデータペイロードを引き出し, データを復号化し, データをハッシュ化します. ハッシュ化されたデータは, 入力用のUnicode 10進数に変換されます:
    49665667686866675454525052495348527066485368517055505368654852505556654849686554556654525655526953566669697056526565555753665670
  6. Private 社会保障番号 : 123–45–6789; インプットは 123456789
  7. Private 生年月日 : 1/1/2000; インプットは 112000
  8. Private Secret Pin(ユーザーが絶対覚えておくべき番号) : 7327
  9. パブリックおよびプライベートなインプットは下記のプログラムに入れられ, パブリックなインプットをzk-SNARKプログラムに書かれているものと比較します. それらが正しい場合, プログラムは次に社会保障番号と生年月日の合計にSecret Pinを掛けてターゲット番号を生成します.その数がzk-SNARKプログラム(905388517003)にあるものと同じである場合, プログラムは1を返します. ZoKratesに書かれた以下のコードは例を提供します:
zk-SNARKの例のZoKratesコード

10.プログラムが実行されると, 下の図のような証明が生成されます.

ZoKratesからのzk-SNARK(ゼロ知識証明)出力

11. 次に, 上記の証明がパブリックなインプット(Aliceの名前, 電話番号, ブロックチェーンのアドレス, 銀行の証明のハッシュ, および予想される出力 ‘1’)と共に検証スマートコントラクトに送信されます. すべての情報が現在のものである場合, コントラクトはコントラクトに保存された出力とともに ‘true’を返すので, AliceのアプリとAcme Bankは結果を見ることができます. 検証コントラクトには検証キーがハードコーディングされているため, パブリックなインプットと提供された証明から, 証明が真と評価されたかどうかを判断できます.

まとめ

zk-SNARKを用いた証明の方法, zk-SNARKのユースケース, zk-SNARKのプログラム(ZoKrates)の動作について見てきました.

zk-SNARKを用いることで機密を明かすことなく簡潔にある事実を証明できることに加えて, 各アプリケーションのデータの保存方法も変わってくるかもしれません.

今後も,Acompanyからブロックチェーンに関する記事を投稿していきますので,ぜひfollowしていただけると嬉しいです.

Happy Hacking 😎!

--

--