SP1
SP1はRISC-V の命令セットをサポートしているzkVMです。
Last updated
SP1はRISC-V の命令セットをサポートしているzkVMです。
Last updated
開発者は Rust で記述した任意のプログラムを SP1 zkVM でコンパイルし、実行することでそのプログラムの excution proof を作成することができます。
例えば zkTLS(Webproof)を SP1 で実装したりできます。
基本的な Proof システムは以下のような Risc 0 のアーキテクチャを模倣しています。
なぜ STARK Proof System なのかは次の項で説明します。
そして黄色の Proof の部分で以下の順序に従った処理が行われます。
RISC-V Prooving
Aggregation Prooving
STARK-to-SNARK Prooving
大まかなアーキテクチャと実行順序このようになります。詳細を見ていく前に SP1 の STARK Proof System(Plonky3)について解説します。
Plonky3 は Plonky2 の Field size(64bit)を 32bit に小さくしたもので、ハードウェアフレンドリーなフィールドサイズを持ちながら Plonky2 と同等の安全性を保っています。
この Plonky3(および Plonky2)は Plonkish な証明システムに zk-STARKs の FRI コミットメントを適応させたものであり、R1CS とは異なる AIR(Arithmetic Intermediate Representation)という形でステートメントを表現します。
記事内で記述されている用に、繰り返し処理や条件分岐といった複雑な状態遷移を表現する上で、zk-STARKs ベースな証明システムは zkVM において zk-SNARKs よりも効率的と言えます。
VM を構成する要素は Chip と呼ばれています。
各 chip は MachineAir Trait と依存関係を持っており、STARK Machine における実行内容を AIR のステートメントとして変換する処理が行われます。
zkEVM 開発者側から見ると zkEVM そのものを作る場合に発生する仕様変更への対応コストを削減することができるため、良いこの設計思想だと思います。
ちなみに SP1 はオープンソースなので自由に Precompiled Chip を追加できます。
任意の命令実行に対し各 Chips は他の Chips と相互にやり取りする場合あり、CpuChip を中心にこの相互接続関係を制約しています。
ではどのように相互通信の順列を保証しているのでしょうか？
命令の割り込みなどが発生していないことを保証するためには、メモリーの一貫性を保証する必要があります。
つまり「メモリが読み出すデータは前に書き込まれたデータである」という保証が欲しいのです。
Logup や Lookup を使った Permutation check は Chip の相互接続の保証だけでなく、メモリアクセスの一貫性を保証するためにも使うことができます。これはデータの読み出しと書き込みが順列化されていることを証明する問題に置き換えるというテクニックです。
実行トレースはシャード化されており、シャード内の各チップのロジックやチップ間の相互接続が正しいことを証明している。複数の異なるシーケンスの順列(Permutation)は Logup によって解消される。
もう少し深く見ていくと下図のように Rust のプログラムをコンパイルして得られる File を元に Excution が始まります。
SP1 の STARK Proof System にはを使用しています。
このようにField Size を小さくしつつ安全性を保つというアイデアはやでも共通しており、昨今のトレンドとも言えます。
AIR や FRI の具体的な仕組みついてはをご参照ください。
ここでの Chip とはハードウェア的な意味ではありません。特定の機能の効率的な組み込み済み zk 実装と捉えるとわかりやすいかと思います。Halo2 に馴染みがある方であれば、ピンと来るかもです。そうではない人はを読むとイメージつくかと思います。
この図で注目して欲しいのが Precompiled Chips の存在です。 これらは EVM で言うところののような存在だと考えられます。 つまり、SP1 は汎用的な zkVM でありながら zkEVM への応用も見越しているようです。
この課題を解決しているのがという仕組みです。これは証明者が「自分の持つ秘密の値が特定のテーブルの中に存在すること」をゼロ知識証明で示すものです。元々という仕組みがあり、Logup はこれを応用しています。これは zkVM のように複雑で大規模な証明システムにおいて証明サイズ(および証明時間)の大幅な削減につながります。
どんなに複雑な Circuit でも Lookup ベースで構築可能であるというアイデアはと呼ばれており、barry whitehat が残した功績の中でも特に大きいものです。
SP1 が生成する STARK proof は on-chain で検証するにはコストがかかるため、一つの STARK proof にした上でそれを SNARK proof として再帰的に証明するテクニックが用いられています。これにより STARK proof は groth16 もしくは Plonk の SNARK proof に変換され、on-chain で現実的なコストで検証できるようになります。このように、SNARK proof でラップするテクニックは始まりでも採用されています。
SP1 では gnark を用いて SNARK proof に変換しています。は Groth16/Plonk とそれらの Solidity Verifier をサポートした Go 実装のライブラリであり Polygon zkEVM で採用されているです。
SP1 では Ethereum などのスマートコントラクトを使って onchain で Proof 検証できるようにしています。この機能自体は Circom などでも広くサポートされている機能であり、一般的にこれは必要とします。
SP1 ではと呼ばれる GPU-accelerated なライブラリをすることで、prooving time のさらなる高速化を目指しています。に書いてある通り、gnark+ICICLE の組み合わせは現時点のベストプラクティスに思えます。
しかし SP1(および Plonky3)は Rust 実装なので Rust->Go のを実行する必要があり、オーバーヘッドが Prooving Time に影響する可能性がありそうです。
