Jolt
Lookup Tableを利用したzkVM
Jolt (Just one Lookup Table)はa16z CryptoのArasu Arun、Srinath Setty、Justin Thalerによって開発されたRISC-V命令セットアーキテクチャ用のゼロ知識仮想マシン(zkVM)です。SP1やRISC-Zeroと比べ実装がシンプルです。
JoltのコアアイデアはルックアップテーブルとSumcheck Protocolで、それらを組み合わせることで回路サイズを抑え、証明を高速化しています。
JoltにおけるRustプログラム実行と証明生成の流れ
Joltが証明するRISC-Vのプログラムは、Jolt自身によりコンパイルされ、内部のループでインタプリタ実行されます。ここで重要なのは、実行トレースを取る部分まではゼロ知識証明は使わず、普通のRustプログラムとして書かれており、最後の実行トレースの状態遷移を証明だけがゼロ知識証明です。
そのため、JoltはRustで書かれたプログラムに対して
RISC-V用のバイトコード(ELF形式)へのコンパイル
内部のインタプリタによる実行トレースの取得
全ての状態遷移の証明
を行う機能を提供します。
具体的には、Joltのattribute-macroは、ホスト環境へのコンパイル時にguestクレートに定義されたRustプログラムを動的にRISC-V用のELFへコンパイルして保存、その実行・証明・検証を行う関数を生成します。
例えば、次のadd/guest/src/lib.rsにはmain.rsで呼ばれているbuild_add()は定義されていませんが、この関数はマクロによってコンパイル時に定義されます。Joltを使った開発者は、証明したいプログラムに#[jolt::provable]をつけるだけで良いのです。
// add/guest/src/lib.rs
#![cfg_attr(feature = "guest", no_std)]
#![no_main]
#[jolt::provable]
fn add(a: u32, b: u32) -> u32 {
let c = a + b;
c
}// add/src/main.rs
use guest::build_add;
pub fn main() {
let (prove_add, verify_add) = build_add();
let (output, proof) = prove_add(1, 2);
let is_valid = verify_add(proof);
}コンパイル時に得られたELFは、生成されたprove_hoge()内のループで１命令ずつ実行され、プログラムカウンタ・レジスタ・メモリの読み書き、が全て記録されます。これが実行トレースです。
また、各実行では、以下が命令ごとに繰り返されます。
メモリのコード領域から命令をフェッチ
命令をデコード
命令を実行
実行結果をレジスタ/メモリのデータ領域に書き込み
Proveの流れを可視化した図: https://miro.com/app/board/uXjVLHocNvY=/?share_link_id=405357987329
Joltのコンポーネント
VMにおける上記の(1)~(4)の処理が正しく行われていることを証明するために、4つのコンポーネントがあります。
追加のR1CS: プログラムカウンタを更新し正しい命令をフェッチするR1CSインスタンスを用意してSpartanで証明する
オフラインメモリチェック1: バイトコードのデコード結果が正しいことを保証する
Lassoによる命令のルックアップ: 命令の実行結果を事前実行されたテーブルから検索して結果を返す
オフラインメモリチェック2: メモリへの読み込み/書き出し一貫性を保証する
上記を3つの証明にして、それを命令ごとに繰り返しています。さらに、命令毎の状態の遷移は、オフラインメモリチェックにより一貫性が保たれます。
アーキテクチャに関する詳細はこちらを参考にしてください。
Joltの一番の工夫は命令のルックアップテーブルを分解可能(decomposable)にし、サブテーブルに分割したことです。これにより、命令のサイズにかかわらずテーブルのサイズを一定にすることが可能になりました。
https://a16zcrypto.com/posts/article/building-on-lasso-and-jolt/
Joltの実装
ソースコードをビルドしてローカルでSHA-3を実行してみたところ、実行時間はsetupが20s、proveが2s、verifyが0.5s程度でした。メモリ利用料は3GBほどでした。setupでの実行内容にはcommitmentサイズを定義、preprocess、commitment schemeのsetupなどがあり、ほとんどの時間はcommitment schemeのsetupに費やされていました。
ブログによれば、実行時間のうち1/5はコミットメントの計算に費やされ、残りの半分はSumcheck Protocolに費やされます。そして残りの時間は、メモリ割り当て、witness生成、メモリのシリアル化などのさまざまなタスクに分散されます。
Joltは現在は32bitの整数にのみ対応しています。論文では浮動小数点の手法も紹介されています。
また、ブログによるとJoltはオーバーヘッドが 6 桁未満で、RISC-ZeroやSP1(8コア)よりも高速です。
Joltの今後の開発ロードマップ
https://jolt.a16zcrypto.com/tasks.html
コミットメントスキームのBiniusへの移行
より小さいフィールドサイズでのコミットメント実行が可能となる
GitHubではすでに実装している
プリコンパイル
keccakなどのEVMでよく使われる機能をプリコンパイルとして提供し、実行を高速化させる
...
参考文献
Last updated