zk-SNARKsとzk-STARKsの話

ご存知の方も多いかと思いますが、書きます。

一般の認知度ってどんなもんでしょう？
「zk-SNARK？聞いたことがあるような、無いような」
ま、そうですよね。

もっとご存知の方は
「zk-SNARKs、あー、ゼロ知識証明でどうのこうの、だよね。」

もっともっとご存知の方は
「zk-SNARKsはそのデータ秘匿性だけに焦点を当てるだけでは不十分。ETHでも応用を考えられている通り、スケーラビリティの向上に寄与するからだ。その点においてはMimbleWimbleにも目を向けておきたい。それの実装プロジェクトであるGrinもフォローしてしかるべきであろう。もっと言えば処理速度のとの兼ね合いであり、採用するプロトコルの選定が重要になる。それ次第では先日のZECハードフォークに見られるような大幅なパフォーマンス向上が見られる。（cf;pinocchio protocol）」
こんな感じでしょうか？

私は全く分かりません。新作のアイスか何かですか？zk-SNARKsがバニラでzk-STARKsがチョコみたいな。
なので今回はMWはおいておいて、zk-SNARKsとzk-STARKsについて書きます。

まずはzk-SNARKsからです。zk-SNARKsではゼロ知識証明を利用しています。
なので、ゼロ知識証明を説明します。

ゼロ知識証明とはある知識を持っていることを証明する事です。但し条件があります。それに関する何の情報も明らかにしないのです。
よくわかりませんね。

数学的（？）な表現をすると「f(x)=y」となる「xを知っている事」を証明する、となります。

こちらが面白い切り口ですので紹介します。
上記のたとえ話をざっくりまとめて引用します。

私は白と黒の区別がつきます。相手方は白黒の区別がつきません。その方に区別がつくという事を証明するのですね。
二つのボールを用意します。白のボールと黒のボールです。

１）相手がそれを両手にもち、「私」に一つを提示します。
２）背中越しに入れ替えるかもしれませんし、そのままかもしれません。相手は自分が行う事なのでそれを知っています。
３）相手が再度「私」に一つを提示します。
４）ここで、「私」は「白と黒の区別がつく」事を証明するために、１）と３）で提示されたボールが「同じか否か」を返答します。
５）相手は２）で入れ替えたかどうかは自分で区別がつくので、４）の答えが合っているか否かを判断できます。

１～５）は確率50％。一回ではまぐれ当たりかもしれません。なので繰り返し１～５）が行われ、正当性は確率的に確認されます。

wikipediaでも説明されています。

「洞窟の問題」が具体例としてはメジャーなのでご一読されておくといいかもしれません。

最後の

この例だと、そんな複雑な手続きをせずにVさんがPさんに「片方の道から入って反対の道から戻ってこい」とリクエストするだけで証明ができるようにも思えるが、そうすると、Pさんの合言葉がVさんに盗まれる可能性がある。つまり、VさんがPさんの跡をつけて合言葉を盗み聞きすることができる。VさんがPさんを追跡できないようにすることが、露出する情報を最小限にするために重要な点である。

という点が重要です。上記引用の具体例だと、Vさんが相手、Pさんが「私」、合言葉を盗み聞きする危険性は表現されていないように思います。（だからこそ、ゼロ知識証明の捉え方として二つの具体例を紹介しました）

確率的なものですから複数回の試行が必要です。だから処理は重いです。

INGさんがゼロ知識範囲証明というものを発表しました。あれが（相対的に）早いのは「範囲」の証明で良いからです。
Aさんが世田谷区の○○に住んでいることの証明には相当慎重にやらなくてはいけませんが、Aさんが日本在住であることの証明はそれより簡単で良さそうです。
使い道としては、ローンの対象となる年収をクリアしているかどうか、や、GDPRの対象となる地域に住んでいるかどうか、に使うそうです。
実務との兼ね合いで、性能を向上させた上手な方法だと思います。
上手いバランスのとり方です。

さて、zk-SNARKsの話に進みましょう。
トランザクションの内容は秘匿されたまま、それが正当なものであることだけをブロードキャストできます。匿名化です。
さらには、オフチェーンの機械に承認計算を行ってもらい、その結果をもらうという項増にすることでスケーリングにも使えます。処理が早くなります。

では、zk-STARKsとは何でしょう？
zk-SNARKsの問題を解決したものです。
zk-SNARKsの問題とは何でしょう？

こちらから見てみます。

三つあるようです。
１）仕組みを作る段階で信頼を確保しなくてはいけない
２）スケーラビリティ
３）量子コンピューターに対するぜい弱性

１）仕組みを作る段階で信頼を確保しなくてはいけない

「スマートコントラクトに必要なもの」で私が言う、３）正しいプログラムであったとして、それが実行されているかという問題だと私は認識しています。

zk-STARKsの場合は

In ZK-STARKs, there is no external trusted setup phase and the randomness used is public information.

とある通り、信頼されるべき外部の準備段階は存在しないのだそうです。

２）スケーラビリティ

zk-STARKsの方が早い、ということですね。

３）量子コンピューターに対するぜい弱性

私は量子コンピューターを二つに分けて認識しています。一つは何でもかんでもできるすごいコンピューター。もう一つはある特定のアルゴリズムにおいて、すごい性能を発揮するコンピューター。

現状の暗号は「現状のコンピューターでは現実的な時間で解けないように作られているから安全」なのですね。
だから、その解読が1億年から1分になるのであれば暗号技術に頼るのが危険な事になってしまいます。
zk-STARKsはその耐性があるという事なのです。

耐性について説明しずらいのですが、暗号化技術が違うから、という理解です。

（zk-SNARKsのようなnon-interactiveではないからという理由も）

も読んでみました。

Zk-STARKs, on the other hand, are Post-Quantum systems, meaning that even if Quantum-Computers become powerful and ubiquitous they will not have an advantage, compared to classical computers, in breaking ZK-STARKs (at least with our current knowledge of Quantum algorithms).

暗号化技術の違いであり、相対的に耐性があるというもののようです。

ZK-STARKs are scalable, transparent, have universal application, and currently quantum resistant.

と、いろいろと良い事があるようですが

Currently, ZK-SNARKs are available in the cryptocurrency Zcash, as well as the library libSNARK to build ZK-SNARK programs that can be leveraged in blockchains. ZK-STARKs are a newer technology, and not deployed in production capacity as of 6/2018.

のように、普及していません。

また、

There is a downside to ZK-STARKs, however, in that the proof size is some orders of magnitude larger than for ZK-SNARKs.

プルーフサイズが大きいことが現状のZK-STARKsの欠点のようです。

それは

こちらでも指摘されています。（toxic-waste-freeというのは、本記事でいえば１）に対するランダム性を加味することによる解決です）

普及度合い、実際に使われているという点を加味して、今はzk-SNARKs。

今後はセットアップや耐量子という事でZK-STARKsと言いたいところですが、客観的な第三者による証明を許してもらえるのであればtoxic-waste-freeは解決しうる話ですし、スケーラビリティも冒頭で引用したように改善されてきています。耐量子という事であれば、だめになる仮想通貨はたくさんありそうですので、仮想通貨界隈として解決策を模索するものになるのではないでしょうか？

参考

DIGITAL IDENTITY, PRIVACY, AND ZERO-KNOWLEDGE PROOFS (ZK-SNARKS)

zk-SNARKs — A Realistic Zero-Knowledge Example and Deep Dive

ZK-STARKs — Create Verifiable Trust, even against Quantum Computers

大手銀行INGが独自の「ゼロ知識範囲証明」を開発、通常の証明に比べ高性能かつ幅広い応用が可能に

theory and practice of zk-snarks

Zcash and the Art of Security Theater

Personal notes on ZK-STARKs

Creating fake zkSNARK proofs

2018-02-02-andrew-poelstra-bulletproofs

ではでは

----------------------------------------------------------
・かんがえる、かがんでいる人　
・Steemit 
・Twitter 
----------------------------------------------------------