zk-SNARKsの概要

#津田の備忘録#数学

はじめに

zk-SNARKSとはZero Knowledge – Succinct Non-interactive ARgument of Knowledgeの略です。

Succinct...実際に実行する計算量よりメッセージのサイズがとても小さいこと

Non-interactive...証明者と承認者がリアルタイムで互いにやり取りをすることなく証明を行えるということ

argument of knowledge...計算による知識の証明のこと

→SNARKとは、承認者が証明者に問いを出すことなく承認作業を短時間かつ少ない計算量で行うことができるという概念

Ethereumとの関係

プライバシー、スケーラビリティ、インターオペラビリティを解決する手段のひとつがzk-SNARKsです。

また、ゼロ知識証明を対話なしに行える点で、データの軽量化、平均処理時間の短縮、検証速度向上、コスト削減が見込めます

Zcashに初めて導入された署名方法でありEthereumのL2において、スケーラビリティ向上のためにZK-Rollupが提案されておりETH2.0-Phase1で使用可能になる予定です

zk-SNARKsのライブラリはほとんどがRustで実装されていて、Ethereum用のライブラリもあるので触っていきたい

Ethereumではハッシュを使った機密化技術は導入されていましたが、デジタルアセットの交換などシンプルな取引でしか使用することができず、かつ効率的ではありませんでした。このようなシンプルな取引において非効率な機密化技術の必要性はほとんどありません。

しかし、zk-SNARKを導入することで匿名化するアルゴリズムをプリコンパイルされたコントラクトとして作りブロックチェーンに追加できるので、効率的で柔軟な機密化をスマートコントラクトでも行うことができるようになることが期待されています。

これにより、位置情報や過去の取引履歴などのプライベートな情報あるいはビジネスでの利用場面で競合他社に知られたくない情報を公開することなくスマートコントラクトを実行することができます。

承認までの基本的な流れ

https://gyazo.com/98578d9297f0a492162c804bd3530a34

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

これらG、P、Vのアルゴリズムを使った実際の流れは以下のようになります。

インプットh(x)はハッシュ関数です。

https://gyazo.com/22bd9c2fdbde006b7d2a08fe6afe686d

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

(送り手と受け手のアドレスを匿名にすることも可能です）

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

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

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

(つまり、鍵生成と証明をオフチェーンで完了することで無駄なトランザクションがオンチェーンに流れることがなくなる(?)

検証のみがオンチェーンで行われる)

この記事より抜粋しました。

数学的実装

検証者に多項式自体を渡さずに命題が正しいかどうかを判断する方法として以下の二つが挙げられる。

1.Circuit-SAT

QAP（quadratic arithmetic programs）を用いた命題の変換を用いて簡素化できます。

演算回路C は検証に用いることになり、関数Fの結果が証明となる????

2.Schwartz-Zippleの補題

・まだ調べてないです

上記2つの実装方法がざっくりこの記事にまとまってます。

(2.の検索結果が21,600件しかなかった...Circuit-SATは151,000,000 件あるのでこっちから掘っていきたい)

詳細

[zk-SNARKSの構築Pinocchioプロトコル]

具体例

Aliceが自分の身元情報を某銀行のオペレータBobに提供せずにある口座から別の口座に送金する方法の一例

簡潔な非対話型ゼロ知識証明の構築には信頼された第三者を介して証明プロセスが行われます。これをCRSモデルと呼びます。

この例では、CRSモデルが使用されています。

CRSモデルとは全ての関係者が、一様分布などの分布から取得した文字列（CRS）にアクセスすることができる信頼されたセットアップが存在するという仮定に基づいたモデルで、強力なセキュリティを持ち、効率的な証明プロセスを構築することができます。証明者と検証者にそのCRSを提供することで、証明者と検証者は一切対話を行わずにゼロ知識証明が可能になります。

zk-SNARKの問題点とその解決策

・証明鍵と承認鍵の再利用

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

このような制限はEthereumでのzk-SNARKを適用した任意のスマートコントラクトを実行するには大きなデメリットとなります。なぜなら、それぞれの新しいコントラクトを行うごとに新しいセットアップを行わなければならないからです。このセットアップはgasを非常に多く消費します。

Ethereumでは、この問題に対処するために2つの対策法が提案されています。1つ目が、上記の一連のセットアップを基本的な考え方としてEthereumでの利用に適するように改善していくという方法です。もう1つが、zk-SNARKのためのVMを用意して、新しく利用するときにセットアップを必要としないようにするという方法です。

zCashでは、信用できる独立したグループが値Rを使ってアルゴリズムGから証明鍵と承認鍵を生成し保持しています。

それにより、証明鍵と承認鍵を再利用できるようにしているのです。

・Rの秘匿化

もうひとつの課題点は、証明者に知られてはいけない値Rを複数の承認者で共有しなければならないことです。

承認者が1人だけであれば値Rを安全に保持しておくだけで不正が起こることはありませんが、承認者が複数の場合は値Rが証明者に知られないように安全性を維持することがより難しくなります。なぜなら、証明者に悪意があった場合、スパイを承認者に送り込み値Rを盗むことが可能になってしまうからです。

そのため、実際にはRの値自体は誰も知ることができず、どこにも保存することができないようにとても安全なプロセスをアルゴリズムGが実行することになります。つまり、プロセスの中で値Rは必ず消去されなければならないのです。

・trusted setup

一連のtrusted setupは、Ethereumではzk-STARKという技術を導入することが実現しています

zk-STARKにより上記のアルゴリズムで楕円曲線などを使うのではなく、ハッシュ関数などを使うことで量子コンピューター対策などのセキュリティ面を高めているのです。また、上述した鍵の再利用による新しいセットアッププロセスの立ち上げもzk-STARKにより改善されています。

Ethereumに導入されたzk-SNARKはgasの大量消費など解決しなければならない部分がいくつかありますが、zk-SNARKが導入されたことでコントラクトにおける柔軟なプライバシー保護を実現できるようになってきています。

参考資料

概念的な資料