ZCash、Ethereumでも使われているゼロ知識証明とは?

仮想通貨全般

最近話題沸騰の「ゼロ知識証明」、またの名を「Zk-Snark」を簡単にですが調べてみました。
参考ページの引用部分は全て

blockquote

で囲んでいます。
参考ページについては後述します。

Sponsored Link


ゼロ知識証明とは?

ゼロ知識証明の概要

以下参考ページより引用です。

ある人(証明者)が別のある人(承認者)に対して、与えられた情報が「真実である」ということ以外の情報を相手に与えずに、その情報が実際に「真実」であることを証明する手法のことです。

数学的には「命題が真であることを、それ以外の情報を与えずに証明する」といいます。

ゼロ知識証明の例

色のついたボールをあてる

参考にしたページの理解を踏まえ、目隠しをされた人が、色のあるボールを見分けることを説明する、ということを例にゼロ知識証明を説明してみます。(ほぼ例がいっしょではあります汗)

1. 目隠しをされた人が色のあるボールとないボールを相手に見せます。
2. 見せられた方は、色があるかどうかを答えます。
3. 1,2を何度か繰り返す

目隠しをされた人は、どちらのボールを出しているかは理解しています。
このため、色がついているかはわかりませんが、どちらが色をついているボールかどう答えられたかは判断できます。

上記前提と手順を繰り返す事によって、目隠しをされた方はどちらのボールが色
「色を分からせるなら1回でいいじゃん」と最初思ったんですが、1回だと相手が嘘をいっている可能性があるため、この試行(上記1〜3)を何度か繰り返す事によって、本当にボールの区別がつくのかどうか、ようは本当に情報の区別がつくかどうかを確認しているわけです。

これは、情報の中身を伝えずに公開せずに知っている事を伝える、という事と同じ事になります。

以下参考ページより引用です。

暗号通貨領域におけるゼロ知識証明では、このボールの色ではなく、ランダムな文字列である「ハッシュ」という情報を用います。証明者(ボールの判別をする人)は、承認者(目隠しの人)に対して、試行を通して実際のハッシュの値を公開することなく、ハッシュに関する知識の証明をします。

例えば、アリスだけが知っているXという情報についてアリスは直接Xを提示して知っていることを証明するのではなく、Xをハッシュ関数に通してH(X)というハッシュ値を提示することで、ボブはアリスがXを知っていることが分かります。

この例において、アリスは「その情報を知っていること」を証明しているので証明者(prover)と呼び、ボブは「相手がその情報を知っていること」を確かめることができているので承認者(verifier)と呼びます。

ノンインタラクティブ型

証明者Xさんと、検証者Yさんが直接のやり取りを必要としない場合を、ノンインタラクティブ型といいます。

ゼロ知識証明のルール

ゼロ知識証明には、証明者による不正を最小限に抑えるために守るべきルールが定義されています。

完全性(completeness)

証明者が秘密を持っていることが本当ならば、検証者はそれが本当であることが必ずわかること

健全性(soundness)

証明者が秘密を持っているという嘘をついている場合、検証者は高確率でその嘘を見抜ける

ゼロ知識性(zero-knowledge)

検証者が証明の結果得られる知識は、証明者の命題が真であることのみである。

zk-SNARKsとは

zk-SNARKsは以下の略です。

Zero Knowledge – Succinct Non-interactive ARgument of Knowledge
Zero Knowledgeはゼロ知識を意味し、SNARKは以下の略称です。

また、Succinct Non-interactive ARgument of Knowledge はそれぞれ以下の意味です。

– Succinct (簡潔) – 証明結果は証明のプロセス(計算)に比べサイズが軽い。証明プロセスをノンインタラクティブ型にすることで、証明結果の容量を節約できる。
– Non-interactive (ノンインタラクティブ) – トランザクションの正当性を確認したい検証者が、証明者と直接やり取りせずに証明を確認できる。
– ARgument – 証明者の計算能力には限りがある。並外れた計算能力を持つ証明者は、力づくで暗号を解き、虚偽の証明を提出できてしまう。
– of Knowledge – 証明者は、取引に関与するウォレットのアドレスなどといった知識を前もって知っていない限り、証明を作成することはできない。

証明が簡潔かつノンインタラクティブ(証明者から検証者へメッセージを送るだけ)であることで、ブロックチェーン上に記録する内容を少なく抑えることができる、ということになります。

なんのために使うのか?

匿名性

不必要なデータをpublicにしなくてよくなるんです。

ブロックチェーンネットワークにおいて送信者(証明者)はトランザクションの内容を明らかにすることなくネットワークのノード(承認者)はそのトランザクションが正当であると承認することができるのです。
何がよいかというと、AさんがBさんにあるコインを送金したいけど普通に送金すると残高やら送った額などがわかってしまうと。
ただ、ゼロ証明の仕組みをつかえばそれら情報(残高やら送った額など)を公開せずにトランザクションを承認させることができる、と。
プライバシーの観点から重要になってくるはずです。

承認時間の短縮にもなります。一連のプロセスがプログラムされていることから、不必要な手続きが必要なくなります。

zk-SNARKsの例

これはOsukeさんの記事がわかりやすいです。

zk-SNARKは、以下の3つのアルゴリズムから成っています。

G:鍵を生成するアルゴリズム(ある秘密の値RとプログラムCから証明鍵(pk)と承認鍵(vk)を生成する。(pk, vk) = G(R,C) )

P:証明者が証明をするアルゴリズム(証明鍵(pk)と証明する情報(X)とプログラムCへのインプット(h)から証明(prf)を生成する。prf = P(pk, X, h) )

V:承認者が証明を正当かどうか承認するアルゴリズム(承認鍵(vk)とプログラムCへのインプット(h)と証明(prf)から「正当か不正か」を返す。 V(vk, h, prf) = True or False )

Osukeさんの記事内の図を拝借して説明文のコメントを図に入れてみる。

ちなみに上記のある秘密の値がRが証明者にばれると、自由自在に証明する情報を操作できてしまうようです。
値Rはそもそも再利用できないと。
理由は証明者が自分で2つの鍵を作れてしまい、証明すべきXの値がなんであろうと、承認をさせてしまうことができるため、とかそのような意味だと思います。

zk-SNARKの具体的な使用例

Osukeさんの記事からの引用です。とてもわかりやすいです。

アリスがボブに10ETH送金するというトランザクションを考えていきます。ここで、アリスとボブのアカウント残高と送金額10ETHはビジネス上の競合他社に知られたくない機密情報となります。この機密情報をXとします。(送り手と受け手のアドレスを匿名にすることも可能です)

この場合、2つのzk-SNARKが使われます。つまりアリスとボブそれぞれがzk-SNARKを実行するのです。

アリスとボブは、それぞれの取引前のアカウント残高と取引額を機密情報X(証明する値)とします。そして、それぞれの取引前のアカウント残高と取引後のアカウント残高と取引額のハッシュ値をhとして上記のセットアッププロセスを実行するのです。

また、アルゴリズムGはオフチェーンで実行され証明鍵と承認鍵を生成します。そして、証明者も同様にオフチェーンでアルゴリズムPを実行し、証明を生成します。アルゴリズムVはスマートコントラクト内で実行され、その出力(承認or不承認)に合わせて次のオンチェーンでのコントラクトが実行されるのです。

数学的な説明

参考にしたページ



これらのページが非常に参考になりました。

結局zk-SNARKって何やってるか?を考えてみたが数式見ないとよくわからない説

すごくざっくりした言い方をすると
証明すべき値を証明鍵を使って複雑な値にして、その複雑な値が正しいかどうかを承認鍵で検証し、問題なければ承認する
とかそんな感じでしょうか、、、

証明鍵を使って秘匿化されたデータを署名し、承認鍵を使って検証すると。

あれ、、、だとすると承認鍵publicにしても良い理由がよくわからないな、、、

PrivateにするのはGアルゴリズムにいれる秘匿の値Rのみ。
例えば、悪意を持ったユーザーがいるとして、証明鍵、承認鍵を知っていると。

そして、Xを適当な悪意のある値を入れたとして、証明鍵で prf を作ると。
その場合、承認鍵で検証する際に、対応する証明鍵であれば、承認OKにしてしまわないんだろうか?

ただ、それはできないはず、ただし、秘匿の値Rを知らなければ、の話。
逆に言うとRを知っていたらこれができる、、、と。

どういうことだ?

Rを知っている = 自在に鍵を作れる
Rを知らない = 自在に鍵を作れない。作れたとしても偽物になってしまう。

とすると、承認する際にRの値を知っているかどうかで、承認有無がかわってくる、と。

V:承認者が証明を正当かどうか承認するアルゴリズム

の仕組みが重要になりそうだ。

Rの値ってなんでもよくない説。一定の法則にしたがったものでないとだめ。 -> 法則わかったらアウト。
適当にRの値を作って、鍵を作ってやってみた場合は?

おそらく、VアルゴリズムがRの値が正しいものでない承認鍵での承認は弾くものと思われる。

Vアルゴリズムであらかじめ「正しいRの値」を把握している必要があるはずだが、、、
– 事前にVアルゴリズムでRを把握できている?
– Rは何かしらの法則でできるため、事前にRを把握しなくてもOK?

この解説からだけだとわからないので、数式見る必要があるんかな、これは。
自分の理解が足りないだけかもしれないが、、、
数式理解できるようにならねば。

理解したら追記しよう。

[追記]
まだ、理解していないのですが、、、

Osukeさんの記事で

なぜなら値Rは安全性のためプロセス中に破棄してしまうからです。もし同じ値Rを再利用することができれば、同じ証明鍵と承認鍵を生成することができるので、1回のセットアップで複数の情報をゼロ知識証明することができます。

と記載があるから、Rは一時的な値なのか。プロセス中になくなってしまうと、役目を終えたら。

このため、Rがそのタイミングでしか生成できないものであれば、上記の疑問で

> 逆に言うとRを知っていたらこれができる、、、と。

と書いたけど、Rは証明実行時にしか生成されないワンタイムパスワードみたいなものだから、そもそも知ることは難しいのか。
Rを作った人と承認者はいっしょ、もしくは同じグループである必要があると。
承認する際に

また、証明鍵と承認鍵の再利用の段落で

このセットアップはgas(イーサリアムでの手数料)を非常に多く消費します。

と記載がありますが、Ethereumへのブロードキャストは最終的な時だけで、全部サイドチェーンでやる仕組みになればGasの消費少なくなりそうですね。

ただ、承認鍵と証明鍵2つをしっていたら、証明者が承認できないか?
いや、そもそも証明者は承認できないのか。
なんで、正しい承認鍵と証明鍵を作る必要があって、それはRをしらないとできないと。
しかも、Rは一時的にしか存在しない(1処理1R?)その処理だけようのR。

データAをデータBにすり替えて送ろうとしたと。
通常の場合、prf(証明)がinvalidなものになるんだろうね、この場合承認者が否認できて何事もないと。

ただ、これを証明者がRの値を知り得た場合、、、
RとプログラムCから証明鍵と承認鍵を作るけど、、、結局データをBにすり替えたら、否認されるんじゃないか・・・?

やっぱり数式とかちゃんと文献読まなきゃダメか涙

Sponsored Link
コメントはまだありません

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA


仮想通貨全般
Dharma code schoolを試してみる

前回の記事からの続きで以下を試してみました。 チュートリアルでは簡単なローンのスマートコントラクトを …

仮想通貨全般
Dharma CDO発行プラットフォーム?

DharmaがCDO発行プラットフォームなる事をhoryさんが以下ツイートでつぶやいていたので、気に …

Dapps
Plasma Porker をとりあえず動かす

最近、Plasma界隈で賑わしている Plasma Prime。 Plasma Prime desi …