zk-SNARKs、zk-STARKsとは？

暗号資産（仮想通貨）やパブリックブロックチェーン技術は、利用者が増えることでシステムが耐えきれなくなるスケーラビリティ問題や、取引履歴がブロックチェーンを介してすべてパブリックに公開されてしまうプライバシーの問題を抱えてきました。

こうした問題を解決する方法の一つとして、昨今、暗号学におけるゼロ知識証明という理論をベースにした技術として、zk-SNARKsやzk-STARKsといった応用技術が注目されています。すでにイーサリアム（ETH）にも実装され始めているzk-SNARKsやzk-STARKsとは、どのような技術なのでしょうか。

本記事ではzk-SNARKsやzk-STARKsについて詳細を説明します。また、そのベースとなるゼロ知識証明についても詳しく解説します。

ゼロ知識証明を応用したzk-SNARKsおよびzk-STARKsとは？

暗号学の分野にゼロ知識証明（Zero-Knowledge Proofs）という技術があります。ゼロ知識証明は、ある人が特定の事柄を証明したいときに、機密情報を明かさずにそれを証明する技術の総称です。その応用例にzk-SNARKsとzk-STARKsという技術があります。

zk-SNARKsは、プライバシー保護技術としてすでにイーサリアムにも実装されていますが、これらゼロ知識証明の技術は、次世代のプライバシー強化技術として注目されており、暗号資産（仮想通貨）やブロックチェーン技術のプライバシー、スケーラビリティ、インターオペラビリティ（相互運用性）など様々な課題を解決すると期待されています。

暗号学においてゼロ知識証明は、ある人が他の人に、自分の持っている（通常、数学的な）命題が真であることを伝えるのに、真であること以外の何の知識も伝えることなく証明できるようなやりとりの手法と表現されています（詳細は後述します）。

ゼロ知識証明の技術の応用例には、公開鍵暗号、デジタル署名、ユーザ認証などがあります。具体的な応用方法として、ある人がパスワードを所持していることで本人であるということを他人に証明するにあたり、そのパスワード自体を他人に開示せずに本人であることを証明する認証方式を実現できます。こうしたパスワード認証というのはゼロ知識証明そのものの技術としては一般的なものではありませんが、ゼロ知識証明を応用することでそうしたことにも利用できるという例の一つです。

zk-SNARKsやzk-STARKsといった技術を理解するには、まずはゼロ知識証明を理解する必要があります。

ゼロ知識証明とは

ゼロ知識証明は、1985年に最初に定式化された比較的新しい理論です。それ以来、多くの研究者によって研究が続けられ、ゼロ知識証明は暗号学にとって重要な概念の一つとなりました。

ゼロ知識証明は、ある「知識（情報）」を持つ証明者（Prover）が、お金を払ってでも「知識」を知りたい検証者（Verifier）に対して、その「知識」を証明者が本当に持っているのか、そして正しい「知識」なのかを、「知識」の中身は教えずに正しい「知識」を持っていることを証明できます。すなわちゼロ知識のゼロは、知識の中身なしでも証明ができるという意味のゼロです。

ゼロ知識証明には、完全性、健全性、ゼロ知識性の3つの満たすべき条件があります。

完全性とは、真であることを確認する検証者側は、証明者の持っている命題が真であるならば、真であることが必ずわかることです。

次に健全性とは、もしも証明者の持つ命題が偽であるなら、検証者は高い確率でそれが偽であると見抜けることです。

そして、ゼロ知識性とは、証明者の持つ命題が真であるなら、検証者が不正して証明者から「知識」を盗んだとしても「命題が真である」以外の「知識」が得られずに秘密が守られることです。具体例でいうと、ゼロ知識性とは盗んだ知識からは「正しいパスワードを入力すればログインができる」ということは得られるが、パスワード自体はわからないという状況を意味します。

ではゼロ知識証明は具体的に、どのようにこれらを証明するのでしょうか。

たとえば、それぞれにドアがある101号室と102号室のように隣接する部屋のある建物があったとします。101号室と102号室は壁で仕切られていますが、実は中でパスワードのような暗号鍵によって開けることができる秘密の扉があるとします。部屋は秘密の扉を開けることによって、両部屋が利用できるようになります。この秘密の扉を開けることができるパスワードを知っているAさんは、部屋を借りたいというBさんに有償でパスワードを教えてもいいといいました。

Bさんは、Aさんが本当にパスワードを知っているのか不安です。Aさんは、本当にパスワードを持っていることを証明するために、パスワードを教えて秘密の扉を開けてみせるのではなく、どちらかの部屋に入り待機し、外にいるBさんの指示に従い101号室または102号室から出てくることでそれを証明します。このとき、Bさんが指示した部屋から必ずAさんが出てくることができれば、Aさんは秘密の扉のパスワードをBさんに教えることなくそのパスワードを知っていることを証明できます。これが、完全性です。

ただし、Bさんの1回の指示だけでは証明は不完全です。もしもAさんが最初に101号室にいてBさんが101号室から出てきてほしいと指示した場合は、正答率は50％です。パスワードを使用せずに出て行くことができました。しかし、これを何度も繰り返し、必ずAさんがBさんの指示通りに出てくることができれば、正答率は上がり限りなく正しいことが証明できます。つまりこれが健全性の証明です。

では、BさんがAさんに対して101号室から入って102号室から出てきてほしいと指示した場合はどうなるでしょう。これは確かに1回でAさんが秘密の扉のパスワードを知っていることが証明できますが、もしBさんがAさんのあとをこっそりとついていきパスワードを入力するところを盗み見たとしたらどうなるでしょう。つまりパスワード自体がばれてしまうことになります。これはゼロ知識性の条件を満たしていないことになります。

このようにゼロ知識証明は、AさんとBさんすなわち証明者と検証者による幾度かの対話を繰り返すことで、その証明を行うことができる仕組みなのです。

ちなみに、ゼロ知識証明は証明者と確認をしたい検証者との間で幾度かやり取りをすることで相手を納得させる証明方法であることから、ゼロ知識対話証明（Zero Knowledge Interactive Proof、ZKIP）と呼ばれることもあります。

また、近年はゼロ知識証明を対話せずに実行する証明者が「証明」を作成して一方的に検証者に送りつけるだけで完了するような証明方法として、非対話ゼロ知識証明（non-interactive zero-knowledge proof、NIZK) と呼ばれる応用例も出てきました。ゼロ知識証明の分野は、発展途中といってもよいでしょう。

zk-SNARKsとは

それでは暗号資産（仮想通貨）やブロックチェーンに実際に実装されているゼロ知識証明の応用例を確認してみましょう。

まず、2017年にイーサリアムにも実装されたzk-SNARKsについてです。zk-SNARKsとはZero Knowledge Succinct Non-interactive Argument of Knowledgeの略です。

Zero Knowledgeは、ゼロ知識証明のことです。Succinctとは、簡潔という意味ですが実際に実行する計算量よりメッセージのサイズがとても小さいということを意味します。Non-interactiveとは、証明者と検証者がリアルタイムで互いにやり取りをすることなく証明を行えるということ、最後のArgument of Knowledgeは知識の証明という意味です。

つまり、zk-SNARKsとは秘密鍵などの特定の知識を開示せず、証明者と検証者のいずれとも対話せずに、その知識の所有権を短時間かつ少ない計算量で証明できる非対話ゼロ知識証明の技術ということになります。

ゼロ知識証明を本格的に暗号資産・ブロックチェーンに実装した最初のプロジェクトはZcashです。ゼロ知識証明を行う際に計算量やメッセージサイズが大きくなってしまうと、ブロックチェーンにおいてトランザクション手数料が膨大になってしまう問題が発生しますが、zk-SNARKsは、非常に大きなプログラムに関する記述であっても、数百バイトで、数ミリ秒以内に検証できます。

zk-SNARKsは、トランザクション情報を暗号化された状態でブロックチェーンに記録するにも関わらず、その金額の受取手はその残高を使用できます。

例えばAさんがBさんに10ETHを送金するような場合、多くの暗号資産やパブリックブロックチェーンのように匿名化されていないトランザクションにおいては、「送金者Aさん」「受金者Bさん」「送金額10ETH」という情報は誰でも見ることができてしまいます。しかし、zk-SNARKsで匿名化することによって、パブリックブロックチェーンであってもトランザクション情報からは送金者、受金者、送金額の情報を第三者は確認できません。さらに、その上でトランザクションに不正がないということを証明することができます。

ただし、zk-SNARKsにはいくつかの課題もあります。zk-SNARKsは証明者と検証者の間で最初に信頼できる手動による設定（Trusted Setup）が必要です。このTrusted Setupがきちんと行われていない可能性があります。証明者と検証者の設定は完全に両者の信頼に依存しており、Trusted Setupの段階でききちんと情報が破棄されるなど、信頼の元で安全であるということが大前提にあります。この前提が守られなければ、Trusted Setupは逆にプライバシーを危険にさらすということになってしまいます。

またzk-SNARKsの証明についてはシステムに対する不正行為が成功する可能性は、計算上は非常に低く健全だとされていますが、理論的には量子コンピュータのような十分に計算能力を備えた証明者であれば偽の証明を作成できる可能性があるといわれています。

zk-STARKsとは

前述のzk-SNARKsの課題を解決する新しいプロトコルがzk-STARKsです。課題のあるzk-SNARKsの代替提案として開発されました。zk-STARKsは、Zero Knowledge Scalable Transparent Argument of Knowledgeの略です。

zk-STARKsのScalable Transparent Argument of Knowledgeは、スケーラブルかつ透明性のある知識の証明という意味になります。zk-STARKsは、より効率的な計算コストで実行可能であり、何よりも大きな特徴はTrusted Setupを必要としていないことが挙げられます。

zk-STARKsは、2018年3月にイスラエル工科大学のエリ・ベン・サソン教授によって提案されました。エリ・ベン・サソン教授は、ゼロ知識証明やzk-STARKsを実際のアプリケーションに実装するブロックチェーン企業StarkWareを創業し、ブロックチェーンの課題解決に取り組んでいます。

zk-STARKsは、大規模な計算処理を実行し、その計算の正しさの証明を生成し、証明を非常に少ないステップで検証することが可能です。

zk-STARKsは、大規模な計算処理を安価なオフチェーンで行い、検証が必要とする計算の一部だけをオンチェーンに残すことで、ブロックチェーンのスケーラビリティを向上させます。つまり、zk-STARKsは検証者がオンチェーンでごくわずかなステップを実行することで、オフチェーンで行われたより大規模な計算の完全性を保証できます。

また、zk-STARKsではパブリックなランダム性が利用されます。これは、人々がゼロ知識証明システムを信頼する上で非常に重要な要素です。zk-SNARKsのようにあらかじめTrusted Setupのようなパラメータを設定するフェーズがなく、パブリックで検証可能なランダム性が利用されるため、zk-STARKsを用いたシステムはより信頼できるものになるといいます。

しかし、zk-STARKsにも課題はあります。それは、zk-SNARKsと比較すると証明サイズがzk-SNARKsよりも大きくなることです。計算量や証明サイズが大きくなればなるほど、ブロックチェーンにおいてはトランザクション手数料が増えてしまいますので、これがzk-STARKsの課題の一つになっています。

まとめ

zk-SNARKsはZcashですでに利用できるほか、zk-SNARKsはイーサリアムにも実装されています。

StarkWareによって提案されたzk-STARKsは、zk-SNARKsよりもさらに新しい技術です。ただし、まだまだ研究中の実験的なアイデアでもあります。StarkWareによるzk-STARKs研究は、最初にスケーラビリティに焦点を当て、その後プライバシーに焦点を当てて研究を進めていくことが表明されています。

提案後のzk-STARKsは、イーサリアムのスケーリングテクノロジーの一つであるZK-Rollupsにも大きく貢献しました。zk-STARKsは、2019年にはイーサリアムのメインネット上でも利用できるようになり、2020年にはzk-STARKsを応用したStarkWareのレイヤー2スケーラビリティエンジンStarkExがイーサリアムのメインネット上で稼働しています。

さらにStarkWareは、パーミッションレスの分散型Validity-Rollups (ZK-Rollupsとも呼ばれます）StarkNetの開発を進めています。StarkNetは、イーサリアム上のレイヤー2ネットワークとして動作し、イーサリアムのセキュリティを損なうことなく、ゼロ知識証明を用いたスケーラブルなDAppsの開発が可能になります。

zk-STARKsを始めゼロ知識証明の応用技術をリードするStarkWareがさらに研究を進めているこの分野は、スケーラブルかつよりプライバシーが強化された分野になるのではないでしょうか。