ゼロ知識証明：ZK-SNARKとZK-STARKを理解しよう！

Home
知識
ゼロ知識証明：ZK-SNARKとZK-STARKを理解しよう！

2023.08.10
知識

ゼロ知識証明：ZK-SNARKとZK-STARKを理解しよう！

1. ゼロ知識証明とは？

よく言われるのは、

自分が秘密の情報を知っていることを他人に証明することができるが、その情報そのものは明かさない。

ということです。

この記事では、特にZK-SNARKとZK-STARKに注目して、それぞれの特性や違いをわかりやすく解説します。
ゼロ知識証明については前回の記事をご覧ください。

2. zk-SNARKとは？

zk-SNARKは「Zero-Knowledge Succinct Non-interactive Argument of Knowledge」の略で、2012年に発明されました。ゼロ知識証明の根幹である「他者に秘密を明かさずに、秘密を知っていることを証明できる」という機能を有しています。また、非対話型であるため、証明者が一度だけ検証者に証明を送ることで、証明を完了させることができます。

例としては、Zcashがこの技術を使用して、送信者、受信者、金額を非公開にしたシールドトランザクションを作成しています。

3. zk-STARKとは？

zk-STARKは「Zero-Knowledge Scalable Transparent Argument of Knowledge」の略で、2018年に紹介されました。これは、SNARKとは対照的に、信頼されたセットアップの必要がないという点です。信頼されたセットアップとは、証明者と検証者の証明を仲介する第三者のことをいいます。それらが必要がないため、セキュリティ上の弱点が少ないです。また、量子コンピュータに対する耐性があります。

4. zk-SNARKとzk-STARKの比較

	ZK-SNARK	ZK-STARK
証明のサイズ	小さい	大きい
証明時間	短い*	長い
Trusted Setup	必要	不要
量子耐性	脆弱性あり	耐性あり

*ただし、検証の複雑さが増すと時間が増えることがある。

4. ZK-SNARKの仕組み

ZK-SNARKは、以下の3つのアルゴリズムで成り立っています。

Gアルゴリズム：鍵を生成する部分
Pアルゴリズム：証明の作成
Vアルゴリズム：証明の検証

この仕組みを利用することで、情報を公開せずに、その情報を持っていることを第三者に証明することができます。また、これら全てのアルゴリズムはスマートコントラクト内で実行されます。

Gアルゴリズムが鍵を生成する証明鍵と承認鍵を生成します。CのプログラムにRという値を入れることで鍵が出来ます。このRは誰にも知られては行けません。なので、SNARKは信頼された第三者が必要とされています。
Pアルゴリズムを用いて、証明（prf）を生成する。機密情報のXをハッシュ化*したhをPアルゴリズムに渡すことで、証明（prf）を生成します。大切な情報であるXをそのまま渡していないことが特徴です。これによって、「情報そのものを明かさずに証明する」を実現しています。
*ハッシュ化：特定の計算手法を用いて、元のデータを別の文字列に変換すること。同じ文字列を入力した場合は、同じ文字列が返ってくる。
Vアルゴリズムで検証する。Gアルゴリズムで生成された鍵と、Pアルゴリズムで生成されたprf、機密情報のハッシュ値hをVアルゴリズムに入力することで、その情報が正しいかどうかの正誤が返ってきます。

4. ZK-SNARKの問題点

ZK-SNARKは非常に強力な技術ですが、いくつかの問題点が指摘されています。

Trusted Setup：上記のGアルゴリズムとPアルゴリズムが共犯者だった場合、Rを教えることで不正な証明（prf）を作ることが可能になってしまいます。
量子耐性：Gアルゴリズムによって、Rという値から①証明鍵と②承認鍵が作られました。「これらは証明鍵や承認鍵からはRが求められない」という前提があります。しかし、量子コンピュータによって、Rが解読されてしまう可能性があります。