--- title: "SNARKsとSTARKS、Recursive SNARKsの比較" description: "ZK-proofsの定義、利点、違い" --- # SNARKsとSTARKS、Recursive SNARKsの比較 ゼロ知識証明とは、ある当事者が別の当事者に対して、情報そのものを明かすことなく、その情報を知っていることを証明できる仕組みである。妥当性証明（validity proof）とも呼ばれ、ZK証明はもともとプライバシー重視のブロックチェーンで取引の詳細を隠すために使われていた。 しかし、ZK証明にはもう一つ重要なユースケースがある。汎用ブロックチェーンのスケーリングだ。妥当性証明を使えば、ブロックチェーンのノードは詳細を保存したり計算を再実行したりすることなく、取引を検証できる。これにより確認時間が短縮され、ネットワークのスループットが向上する。 こうしたスケーラビリティ上の利点から、ZK証明は[ブロックチェーンのスケーリングプロジェクト](https://www.alchemy.com/overviews/ethereum-scaling-solutions)、特に[zero-knowledge rollups](https://www.alchemy.com/blog/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. ゼロ知識（Zero-knowledge）**：検証者は、ある主張の真偽以外については何も知ることができない、という性質を意味する。 **2. 簡潔性（Succinct）**：証明のサイズが十分小さく、検証者が短時間で検証できる。 **3. 非対話性（Non-interactive）**：SNARKが非対話的と呼ばれるのは、証明者と検証者が、最初に提出される証明以上のやり取りを必要としないためである。初期のゼロ知識証明システムでは、主張を検証するために証明者と検証者が複数回メッセージをやり取りする必要があった。 **4. 論証（Argument）**：SNARKは「計算的に健全」な主張であり、厳格な要件を満たすため、不正（すなわち偽の証明の生成）を働くことが困難である。 **5. 知識（Knowledge）**：SNARKに基づく証明は、基となる情報、すなわち_ウィットネス_にアクセスすることなしには作成できない。 ### ブロックチェーンにおけるZK-SNARK パブリックブロックチェーンのような分散コンピューティングシステムは、いわゆる「計算の整合性（computational integrity）問題」を解決する必要がある。計算の整合性（CI）とは、特定の計算から得られる出力の正しさを指す。 パブリックブロックチェーンにおいて、計算の整合性とはネットワーク上で実行される取引の正しさを指す。ほとんどのブロックチェーンは、他のコンピュータ（ノード）に各取引を再実行させることでこれを実現している。 しかし、このアプローチには問題がある。すべてのノードに各取引を再実行させることで、ネットワークが遅くなり、スケーラビリティが制限される。また、ノードは取引データを保存する必要があり（そうでなければ計算を再実行できない）、これによりブロックチェーンのサイズが指数関数的に増大する。 しかし、ノードが計算を再実行することなくその妥当性を確認できるとしたらどうだろうか。これによりネットワークのスループットが向上し、ノードが余分な取引データを保存する必要もなくなる。 そこでZK-SNARKの出番となる。 ZK-SNARKを用いて生成された妥当性証明は、入力情報を明かすことなく取引の妥当性を証明できる。これが、ZcashやMoneroといったプライバシー重視の暗号通貨がSNARKを用いて取引情報を隠す理由である。 SNARKはまた、オフチェーンで実行された計算の正しさを、ノードが計算の各ステップを再実行することなく証明できる。ここにZK-SNARKがブロックチェーンのスケーリングに有用となる理由がある。 SNARKを用いてオフチェーン計算を検証するプロセスは複雑であり、まず計算を数学的な式にエンコードすることから始まる。この数学的な主張が妥当性証明の基礎を成す。 その後、検証者は証明に対して演算を行い、その正しさを確認する。証明がすべてのチェックを通過すれば、基となる計算は妥当であるとみなされる。これがSNARKが_簡潔（succinct）_と呼ばれる理由であり、妥当性証明のサイズは、それが検証する計算に比べてはるかに小さい。 ### ZK-SNARKとZK rollup Rollupとは、オフチェーン実行を通じてLayer 1（L1）ブロックチェーンのスループットを向上させる[Ethereum向けのLayer 2スケーリングソリューション](https://www.alchemy.com/overviews/ethereum-scaling-solutions)である。Rollupは取引をL2チェーン上で処理し、複数のオフチェーン取引をブロックに集約し、それらをL1チェーンに提出する。 計算をベースレイヤーから移すことで、Rollupはネットワークの混雑を減らし、取引をスケールさせる。 しかし、L1チェーンはオフチェーンで実行された取引が妥当かどうかを知る必要がある（すなわち計算の整合性問題）。そうでなければ、悪意ある行為者がRollupを乗っ取り、不正な取引をメインチェーンに提出できてしまう。 あるRollupのタイプ（zero-knowledge rollup）は、ZK-SNARKを用いてオフチェーン取引の真正性をL1チェーンに証明する。SNARK証明は誰でも検証できるため、L1チェーンに取引の妥当性が保証される。 ZK-SNARKを用いるほとんどのZK rollupは、以下と同様の構造を採る。 1. L2チェーン上のユーザーが取引に署名し、バリデーターに提出する。 2. バリデーターは取引をブロックに圧縮し、対応する妥当性証明（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）の生成が必要である。_公開パラメータ（public parameters）_とも呼ばれ、CRSは証明者と検証者の間の安全な通信を可能にする。 もし悪意ある行為者がこの公開パラメータの情報を得た場合、偽の妥当性証明を生成できてしまう。一部のプロジェクトは、複数の個人が関与する[マルチパーティ計算](https://zkproof.org/2021/06/30/setup-ceremonies/amp/)（MPC）を用いてこの問題の解決を試みており、これにより公開パラメータを生成する。 とはいえ、このアプローチはユーザーに、関与者の誠実さを信頼することを求める。ブロックチェーンの目的が権威への信頼の必要性を減らすことにある以上、これはかなり問題である。 #### 2. 量子コンピューティング攻撃への脆弱性 ZK-SNARKは楕円曲線暗号（Elliptic Curve Cryptography、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](https://www.alchemy.com/overviews/what-is-zksync-era)はスマートコントラクト、トークンスワップ、支払い、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マーケットプレイス](https://www.alchemy.com/dapps/best/nft-marketplaces)（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は透明（transparent）とされるが、これはCommon Reference String（CRS）のトラステッドセットアップを必要とせずに機能できるためである。代わりに、STARKプロトコルは公開検証可能なランダム性を用いて、証明者と検証者の間のやり取りをセットアップする。 ZK-STARKは_スケーラブル_である。というのも、証明生成および検証の複雑度は計算の複雑度に対して_準線形（quasilinearly）_にスケールするからである。ZK-SNARKでは、証明生成および検証の複雑度は基となる計算に対して_線形（linearly）_にスケールする。 つまり、検証すべき計算が大きくなるほど、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の分散性とセキュリティを損なうことなく、[分散型アプリケーション](https://www.alchemy.com/dapps/top/defi-dapps)が無制限のスケーラビリティを実現できるようにする。 #### dYdX 暗号資産ユーザーやトレーダーに高速かつ低コストな取引、借入、貸付を提供する、Ethereumベースのzk rollupプロジェクト（分散型取引所も兼ねる）。[dYdX](https://www.alchemy.com/dapps/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つの妥当性証明を提出する。しかし、この「再帰的証明（recursive proof）」は複数のL2ブロックにわたる取引を検証し、オンチェーンのコントラクトが提出された証明を受理すると、それらすべての取引が妥当となる。 ### 再帰的ZK-SNARKはどのような問題を解決するのか **再帰的ZK-SNARKは、複数のL2証明を1つのL1チェーンに提出する証明にまとめることで、ZK証明によって確定できる取引数を劇的に増加させる。この取引数は現在、Ethereumの12～14秒というブロック時間によって制限されている。** ブロック時間とは、Ethereum上で新しい取引ブロックがマイニングされるまでにかかる時間を指す。ZK rollupは1ブロックにつき1件のオンチェーン取引（および対応する妥当性証明）しか提出できず、これが処理できる取引数を制限している。 ### 再帰的ZK-SNARKは通常のZK-SNARKとどう違うのか 再帰的ZK-SNARKが通常のZK-SNARKと異なるのは、異なるL2ブロックに対して生成されたSNARKを1つの妥当性証明にまとめてL1チェーンに提出することで、複数の取引ブロックを検証できる点である。 ZK rollupはメインブロックチェーンに投稿する前に、取引のバッチごとにSNARK証明を作成しており、1つのSNARK証明は、L2 rollup上で行われた取引の1ブロック分しか検証できない。 ZK-SNARKは、元の入力を用いることなく、通常のZK-SNARKによってすでに検証された取引を検証することができる。したがって、オンチェーンのスマートコントラクトは、複数のSNARKを入力として実行することなく、より大きな一連のオフチェーン計算を検証できる。 ### Plonky2とは Plonky2は、Polygon Zeroで使われる新しい証明生成の仕組みであり、Polygon Zeroは再帰的ZK-SNARKを用いて取引数を増加させることを目指す提案中の[**Polygon ZK rollup**](https://www.alchemy.com/overviews/polygon-zk-rollups)である。 再帰的SNARKは複数の証明を1つの再帰的証明に集約することで証明生成プロセスをスケールさせるが、Plonky2は同じ手法を用いて新しいブロック証明の生成にかかる時間を短縮している。 Plonky2の証明生成の仕組みは、数千件の取引に対する証明を並行して生成した後、それらを再帰的に1つのブロック証明に集約する。これは、ブロック証明_全体_を一度に生成しようとする従来の証明生成の仕組みよりも効率的である。 このアプローチの利点は明白である。 **Plonky2は0.17秒で再帰的証明を生成できる**ため、現時点で最速の証明生成の仕組みとなっている。さらに、Plonky2はコンシューマー向けデバイス上で証明を生成できるため、通常のSNARKベースの証明システムが抱えるハードウェアの中央集権化の問題を解決している。 ## 結論 ゼロ知識証明は、プライバシー保護技術から、スケーリング技術の最前線へと発展してきた。ZK rollupの急増を踏まえると、ZK-SNARK、ZK-STARK、そして再帰的SNARKが、Ethereumをスケールさせる取り組みにおいて大きな役割を果たすことは間違いないと言えるだろう。 Web3の開発者は、Alchemyがサポートする、STARKを活用したEthereumのZK rollupである[StarkNet](https://www.alchemy.com/layer2/starknet/?a=cfdfbd6b96)上で構築することで、ゼロ知識技術を活用できる。トレードオフなしにスケールするアプリの構築を、今日から始めよう!