SNARKs vs. STARKS vs. Recursive SNARksの比較

ゼロ知識証明とは、ある当事者が情報そのものを明かすことなく、その情報を知っていることを別の当事者に示す仕組みである。妥当性証明とも呼ばれ、ZK証明はもともとプライバシー重視のブロックチェーンで取引の詳細を隠すために使われていた。

しかし、ZK証明にはもう一つ注目すべき用途がある。汎用ブロックチェーンのスケーリングだ。妥当性証明を使えば、ブロックチェーンのノードは取引の詳細を保存したり計算を再実行したりせずに、取引を検証できる。これにより確認時間が短縮され、ネットワークのスループットが向上する。

スケーラビリティ面での利点から、ZK証明はブロックチェーンのスケーリングプロジェクト、特にzero-knowledge rollupsにとって中核的なインフラとなっている。本ガイドでは、ブロックチェーンで使われるZK証明の主要な分類、すなわちZK-SNARK、ZK-STARK、再帰的ZK-SNARKについて解説する。

ZK-SNARKとは何か

ZK-SNARKは、基となるデータを公開することなく情報の真正性を検証するためのゼロ知識証明を生成するプロトコルである。この頭字語はZero-Knowledge Succinct Non-Interactive Argument of Knowledge（ゼロ知識簡潔非対話型知識証明）を意味する。

ZK-SNARKプロトコルには2者が関与する。証明者（Alice）と検証者（Bob）である。証明者（Alice）は主張を行う側であり、検証者（Bob）はその主張を検証する側である。

主張の中で参照される情報はウィットネス、あるいは_秘密情報_と呼ばれる。証明者（Alice）はZK-SNARKの仕組みを使って証明を生成し、参照している情報を明かすことなく、その主張が真であることを検証者（Bob）に示す。

ZK-SNARKが関わる仮想的な例として、ユーザーのアイデンティティ認証が挙げられる。個人は、個人情報（パスポートや社会保障番号など）を明かすことなく、ある命題（「私は米国市民である」）を証明できる。

ZK-SNARKという名称は、以下の性質を備えていることに由来する。

1. ゼロ知識性：検証者は、その命題の真偽以外は何も知ることができないことを意味する。

2. 簡潔性：証明は、検証者が短時間で検証できる程度に小さい。

3. 非対話性：SNARKが非対話型と呼ばれるのは、証明者と検証者が最初に提出される証明以上のやり取りを必要としないためである。初期のゼロ知識証明システムでは、命題を検証するために証明者と検証者が複数のメッセージをやり取りする必要があった。

4. 論証（Argument）：SNARKは「計算的に健全」な命題であり、厳格な要件を満たすため、不正（すなわち偽の証明を生成すること）が困難である。

5. 知識（Knowledge）：SNARKベースの証明は、基となる情報、すなわち_ウィットネス_にアクセスせずに作成することはできない。

ブロックチェーンにおけるZK-SNARK

パブリックブロックチェーンのような分散コンピューティングシステムは、いわゆる「計算的完全性問題」を解決する必要がある。計算的完全性（CI）とは、特定の計算から得られる出力の正しさを指す。

パブリックブロックチェーンにおいて、計算的完全性とはネットワーク上で実行された取引の正しさを指す。ほとんどのブロックチェーンでは、他のコンピュータ（ノード）に各取引を再実行させることで計算的完全性を実現している。

しかし、このアプローチには問題がある。すべてのノードに各取引を再実行させることで、ネットワークの速度が低下し、スケーラビリティが制限される。また、ノードは取引データを保存しなければならず（そうしなければ計算を再実行できない）、これがブロックチェーンのサイズの指数関数的な増大を招く。

しかし、ノードが計算を再実行せずにその妥当性を確認できるとしたらどうだろうか。これによりネットワークのスループットが向上し、ノードが余分な取引データを保存する必要もなくなる。

そこでZK-SNARKの出番となる。

ZK-SNARKを使って生成された妥当性証明は、入力を明かすことなく取引の妥当性を証明できる。これが、Zcashやモネロといったプライバシー重視の暗号資産がSNARKを用いて取引に関する情報を隠蔽している理由である。

SNARKはまた、ノードが計算の全ステップを再実行することなく、オフチェーンで行われた計算の正しさを証明することもできる。これこそが、ZK-SNARKがブロックチェーンのスケーリングに有用となる点である。

SNARKを使ってオフチェーン計算を検証するプロセスは複雑であり、まず計算を数学的表現へとエンコードすることから始まる。この数学的な命題が妥当性証明の基盤となる。

検証者は続いて、その証明に対して演算を行い、正しさを確認する。証明がすべてのチェックを通過すれば、基となる計算は妥当とみなされる。これがSNARKが_簡潔_と呼ばれる理由であり、妥当性証明のサイズは、それが検証する計算そのものよりも何倍も小さい。

ZK-SNARKとZK rollup

rollupとは、Ethereum向けのLayer 2スケーリングソリューションであり、オフチェーン実行によってLayer 1（L1）ブロックチェーンのスループットを向上させる。rollupはL2チェーン上で取引を処理し、複数のオフチェーン取引をブロックにまとめ、L1チェーンに提出する。

計算をベースレイヤーから移すことで、rollupはネットワークの混雑を軽減し、取引をスケールさせる。

ただし、L1チェーンはオフチェーンで実行された取引が妥当かどうかを知る必要がある（すなわち計算的完全性問題）。そうでなければ、悪意ある行為者がrollupを乗っ取り、不正な取引をメインチェーンに提出できてしまう。

あるタイプのrollup（zero-knowledge rollup）は、ZK-SNARKを使って、オフチェーン取引の真正性をL1チェーンに対して証明する。SNARK証明は誰でも検証できるため、L1チェーンは取引の妥当性を確信できる。

ZK-SNARKを使うZK rollupの大半は、以下のような構造に従っている。

1. L2チェーン上のユーザーが取引に署名し、バリデーターに提出する。

2. バリデーターは取引を1つのブロックに圧縮し、対応する妥当性証明（SNARK）を生成する。これにより、新しい状態が妥当な取引の追加によって生じたものであることの暗号学的な保証が得られる。

3. L1チェーン上のスマートコントラクトが妥当性証明に対して演算を行う。この演算の結果によって、バッチ化された取引が検証済みとされ、メインチェーンに投稿されるかどうかが決まる。

ZK-SNARKの利点は何か

ZK-SNARKを使う主な利点は3つある。高いスループット、小さな妥当性証明サイズ、そしてセキュリティである。

1. 高いスループット

ZK-SNARKは、Ethereumのベースレイヤー上の計算量を縮小することでスループットをスケールさせる。ZK-SNARKを使えば、rollupはTPSを数千のオーダーまで引き上げることができる。

ZK-SNARKは通常、それが検証する取引データよりも何倍も小さい。これによりベースとなるブロックチェーンの混雑が軽減され、ガス代の低減と取引の高速化が実現する。

2. 小さな証明サイズ

SNARK証明のサイズが小さいことで、メインチェーン上での検証が容易になる。Ethereumにおいては、これはオフチェーン取引を検証する際のガス代が低くなることを意味し、rollupのエンドユーザーにとってのコストを削減する。

3. セキュリティ

ZK rollupは、他のスケーリングプロジェクトと比べてより安全だとされているが、これは主にZK-SNARKで使われる最先端の暗号学的セキュリティ機構によるものである。

ZK-SNARK証明は計算的に健全であり、検証者を欺いて悪意ある行為をすることが困難である。ZK-SNARKの非対話性はまた、証明が誰でもトラストレスに検証できることを意味する。

ZK-SNARKの欠点は何か

ZK-SNARKを使う主な欠点は3つある。トラステッドセットアップが必要であること、量子コンピューティング攻撃の影響を受けやすいこと、そして専用ハードウェアに依存していることである。

1. トラステッドセットアップ

ZK-SNARKプロトコルのセットアップには、Universal Common Reference String（CRS）の生成が必要である。_公開パラメータ_とも呼ばれるCRSは、証明者と検証者の間の安全な通信を可能にする。

悪意ある行為者がこの公開パラメータを知ってしまえば、偽の妥当性証明を生成できてしまう。一部のプロジェクトは、公開パラメータの生成に複数の個人が関わるマルチパーティ計算（MPC）を用いることでこの問題を解決しようとしている。

とはいえ、このアプローチはユーザーが関与者の誠実さを信頼することを前提とする。ブロックチェーンの目的が権威への信頼の必要性を減らすことにある以上、これはかなり問題含みである。

2. 量子コンピューティング攻撃への脆弱性

ZK-SNARKは、妥当性証明の生成に使われる情報を暗号化するために楕円曲線暗号（ECC）を使用する。ECCは現時点では比較的安全だが、量子コンピューティングの進歩によってそのセキュリティモデルが破られる可能性がある。

3. 専用ハードウェアへの依存

ZK-SNARKを使った妥当性証明の生成は計算負荷の高いプロセスであり、証明者は専用ハードウェアに投資しなければならない。こうしたマシンを購入できる人はごく限られているため、ZK-SNARKの証明生成プロセスは高度に中央集権化されていると考える人も多い。

ZK-SNARKを使っているプロジェクトは何か

ZK-SNARKを使っている代表的な5つのプロジェクトは、ZKSync、Loopring、Aztec、Polygon Hermez、ZKSpaceである。

zkSync

Matter Labsによって開発された、Ethereum Mainnet上で稼働するEVM互換のZK rollup。ZKSyncはスマートコントラクト、トークンスワップ、決済、NFTミントに対応している。

Loopring

SNARKベースのZK rollup技術を利用したEthereum Layer 2（L2）プロジェクト。Loopringはまた、ETHやその他のERC-20トークンを取引するための分散型取引所としても機能しており、Ethereum Mainnet上のDEXで課されるコストのごく一部で取引できる。

Aztec

Ethereumネットワーク上に構築されたオープンソースのL2ネットワーク。AztecはZK-SNARKを活用して取引をスケールさせ、ユーザーの財務プライバシーを高めている。

Polygon hermez

Ethereumブロックチェーン上で動作するZK rollup。Polygon Hermezは、安全で低コストなトークン送金や決済を実現するためにZK-SNARKを使用している。

Zkspace

ZK-SNARKをベースとしたZK rollupプロジェクト。ZKSpaceはEthereumユーザーに対してより低いガス代と高速な取引を提供し、AMM型DEX（ZKSwap v3）、決済ネットワーク（ZKSquare）、NFTマーケットプレイス（ZKSea）で構成されている。

ZK-STARKとは何か

ZK-STARKはZero-Knowledge Scalable Transparent Argument of Knowledge（ゼロ知識スケーラブル透明知識証明）の頭字語である。ZK-SNARKと同様に、ZK-STARKはある命題自体について何も明かすことなく、それが妥当であることを示す。

いくつかの相違点を除けば、STARKはSNARKと同じ性質を持つ。STARKベースの妥当性証明は、検証者には隠された情報の断片を使って生成される。STARKもまた、入力を明かすことなく取引の正しさを検証できる。

ZK-STARKとZK-SNARKの比較

ZK-STARKの主な違いは、そのスケーラブルかつ透明という性質に由来する。

ZK-STARKが透明とされるのは、Common Reference String（CRS）のトラステッドセットアップなしに機能できるためである。その代わり、STARKプロトコルは公開検証可能なランダム性を用いて、証明者と検証者の間のやり取りをセットアップする。

ZK-STARKが_スケーラブル_とされるのは、証明生成および検証の複雑さが計算の複雑さに対して_準線形（quasilinearly）_にスケールするためである。ZK-SNARKでは、証明生成および検証の複雑さは基となる計算に対して_線形_にスケールする。

これは単純に言えば、検証すべき計算がより大きくなった場合、ZK-SNARKプロトコルはZK-STARKよりも証明の生成・検証に長い時間がかかるということである。これが、STARKが大量の取引を扱うアプリケーションにより適している理由である。

ZK-STARKの利点は何か

ZK-STARKを使う主な利点は4つある。トラステッドセットアップが不要であること、スケーラブルであること、最大限のスループットをユーザーにもたらすこと、そして高いセキュリティ保証を持つことである。

1. トラステッドセットアップが不要

ZK-STARKは機能するためにトラステッドセットアップを必要とせず、代わりに公開のランダム性に依存する。これによりユーザー側の信頼前提が減り、STARKベースのプロトコルのセキュリティが向上する。

2. スケーラブルな性質

STARKはSNARKと比べて、大規模な状況下でより高速に計算・検証できる。さらに重要なのは、基となる計算の複雑さが指数関数的に増大しても、ZK-STARKは証明生成・検証の時間を低く保てるという点である。

3. 最大限のスループット

SNARKと同様、STARKは安全で検証可能なオフチェーン計算を可能にすることでブロックチェーンをスケールさせることができる。

L1チェーンに提出される単一のSTARK証明で、メインチェーン外で行われた数千件の取引を検証できる。そのため、いくつかの著名なZK rollupプロジェクトは、オフチェーン計算の完全性を証明するためにZK-SNARKを使用している。

4. より高いセキュリティ保証

ZK-STARKは、ZK-SNARKで使われている楕円曲線方式の代わりに、暗号化に衝突耐性のあるハッシュを使用する。これは量子コンピューティング攻撃に対して耐性があるとされており、SNARKで使われる楕円曲線よりも安全性が高い。

ZK-STARKの欠点は何か

ZK-STARKを使う主な欠点は2つある。証明サイズが大きいことと、ブロックチェーン分野におけるこの技術の採用がまだ進んでいないことである。

1. 大きな証明サイズ

STARKはより高速な証明を提供する一方で、その証明はSNARKベースの証明と比べて大きいという欠点がある。これにより、大きな証明の計算にはより高いガス代がかかるため、Ethereum上でのSTARK証明の検証コストが高くなる。

2. 採用の少なさ

SNARKはブロックチェーンにおけるゼロ知識技術の最初の実用的な応用であり、そのためSTARKよりも市場シェアが大きい。ほとんどのZK rollupはZK-SNARKを使用しており、SNARKベースのZK証明のための開発者エコシステムやツール群もより充実している。

ZK-STARKにもEthereum Foundationなど著名な支持者がいるものの、採用は少ない。そのため、開発者はSTARKでZKプロジェクトを構築する際、サポートやツールが少ないと感じるかもしれない。

ZK-STARKを使っているプロジェクトは何か

StarkNet

Ethereum上でL2ネットワークとして稼働する汎用のZK rollup。StarkNetは、分散型アプリケーションがEthereumの分散性とセキュリティを損なうことなく、無制限のスケーラビリティを実現できるようにする。

dYdX

Ethereumベースの（分散型取引所としても機能する）ZK rollupプロジェクトであり、暗号資産ユーザーやトレーダーに高速かつ低コストな取引、借入、貸付を提供する。dYdXはセキュリティ機構の一部としてSTARK証明を使用しており、ユーザーの資金の安全性を保証している。

Polygon miden

EVM互換のSTARKベースZK rollup。まだ開発中ではあるが、Polygon Midenはローンチ時点でEVM互換の最初のZK-STARKプロトコルとなり、開発者がEthereumネイティブなアプリをL2ネットワーク上でスケーラビリティを享受できるよう移行させることを可能にする。

再帰的ZK-SNARKとは何か

再帰的SNARKシステムは、異なる取引ブロックに対して並行して証明を生成し、それらを1つのブロック証明にまとめてメインブロックチェーンに提出する。すなわち、1つのSNARKが他のSNARKを検証できるということである。

L2 rollupは依然としてEthereum上に1つの妥当性証明を提出する。しかし、この「再帰的証明」は複数のL2ブロックにおける取引を検証し、オンチェーンのコントラクトが提出された証明を受け入れた時点で、それらすべての取引が妥当となる。

再帰的ZK-SNARKはどのような問題を解決するのか

再帰的ZK-SNARKは、L1チェーンに提出される1つの証明の中に複数のL2証明を含めることで、ZK証明によって確定できる取引の数を劇的に増加させる。この数は現状、Ethereumの12〜14秒のブロックタイムによって制限されている。

ブロックタイムとは、Ethereum上で新しい取引ブロックがマイニングされるまでにかかる時間を指す。ZK rollupは1ブロックにつき1つのオンチェーン取引（およびそれに対応する妥当性証明）しか提出できず、これが処理できる取引数を制限している。

再帰的ZK-SNARKは通常のZK-SNARKとどう違うのか

再帰的ZK-SNARKが通常のZK-SNARKと異なるのは、異なるL2ブロックに対して生成されたSNARKを1つの妥当性証明に統合し、それをL1チェーンに提出することで、複数の取引ブロックを検証できる点である。

ZK rollupは、メインブロックチェーンに投稿する前に取引の各バッチに対してSNARK証明を作成するが、単一のSNARK証明は、L2 rollup上で行われた1つの取引ブロックしか検証できない。

再帰的ZK-SNARKは、元の入力を使わずに、通常のZK-SNARKによってすでに検証された取引を検証できる。したがって、オンチェーンのスマートコントラクトは、複数のSNARKを入力として実行することなく、より大規模なオフチェーン計算の集合を検証できる。

plonky2とは何か

Plonky2は、Polygon Zeroで使用される新しい証明生成の仕組みである。Polygon Zeroは、再帰的ZK-SNARKを用いて取引数を増加させることを目指した提案段階のPolygon ZK rollupである。

再帰的SNARKは、複数の証明を再帰的証明に集約することで証明生成プロセスをスケールさせる。Plonky2も同じ手法を用いて、新しいブロック証明の生成にかかる時間を短縮している。

Plonky2の証明生成の仕組みは、数千件の取引に対する証明を並行して生成した後、それらを再帰的に集約して1つのブロック証明にまとめる。これは、ブロック証明_全体_を一度に生成しようとする従来の証明生成の仕組みよりも効率的である。

このアプローチの利点は明白である。

Plonky2は0.17秒で再帰的証明を生成できるため、現時点で最速の証明生成の仕組みとなっている。さらに、Plonky2はコンシューマー向けの機器で証明を生成できるため、通常のSNARKベースの証明システムが抱えるハードウェアの中央集権化の問題を解決している。

まとめ

ゼロ知識証明は、プライバシー保護のための技術から、スケーリング技術の次のフロンティアへと発展してきた。ZK rollupの急増を踏まえれば、ZK-SNARK、ZK-STARK、そして再帰的SNARKが、Ethereumをスケールさせる取り組みにおいて大きな役割を果たすことは間違いないだろう。

Web3開発者は、Alchemyがサポートする、STARKを基盤としたEthereum ZK rollupであるStarkNetの上に構築することで、ゼロ知識技術を活用できる。トレードオフなしにスケールするアプリを、今日から構築しよう！