💬
ZKVM開発記録 Day. 1

2025/06/30に公開
 ZKVM開発の記録ZKVMをゼロから開発する記録としてここに残しておきます。

 ZKVMのレシピNovaのFolding-BaseのZKVMを作るのに必要な実装はこんな感じです。
Circuit Synthesizer
AST Recording
Operator Overloading
Compilation to R1CS
Augmented Circuit
Input Consistency
Poseidon Hash
Carrying Commitment

ZeroFold
Proving
Binary-Fold Closure
Power Check
Gamma Linear Combination
Rho Linear Combination
Polynomial Interpolation

Verification
Transcript
Univariate Sum-Check


CycleFold
Proving
Nova Fold

Verification
Foreign-Field Arithmetization
Scalar Multiplication
Point Addition


Step Circuit
Memory Consistency
Fingerprint
Grand Product

Switchboard
Main Loop
Zero-Check Reduction
Power-of-Tau Challenge

Commitment
IS/FS Iteration
Carrying-Commitment Consistency
Compressing Proof

 Circuit Synthesizerark-works の ark-relations では ConstraintSynthesizer トレイトが必須ですが、generate_constraints() はselfの不変参照しか取れないため
引数は全てselfからとる
回路内で計算した値を外に返せない
外で用意した値に制約を付けるしかない
同じロジックを回路内外で二度書く羽目になる
という問題がありました。

そこで回路を関数スタイルで書ける独自ツール CSWire を作りました。特徴は次のとおりです。
ユーザがトレイトを実装しなくてよい
入力 → 回路計算 → 出力 を一つの関数で完結
制約定義と Witness 計算を分けずに書ける
自分にはこちらの方が扱いやすいので、この ZKVM では CSWire を使います。

回路定義を明確に分離したい場合は、ark-relations をぜひ使ってください。

 Augmented CircuitAugmented Circuit はFoldingで畳み込む最終的な回路です。内部では、CPUのそれぞれの命令を実行したり、前の二つのステップをfoldしたりなど行っていますが、実際にこの回路がFoldされて行きます。

step_synthesizer: このステップで本来行いたい回路がここに定義されます。ほとんどはCPUの命令の実行です。

fold_synthesizer: foldingに必要な回路が定義されます。NeutronNovaのZerofoldやHyperNovaなどです。
他には、前のステップの出力などを次のステップに伝える仕組みや、折りたたむべきインスタンスがない初回などのケースを扱う処理が書かれます。

個人的には、この Input Consistency が結構重要で、最初の頃はこれが分からず、頭を悩ませていました。
下の図の通りですが、Augmented回路の中で畳み込まれたインスタンスをRunning Instanceとして次に渡し、その回路自体を新しいインスタンスとして次のステップで畳み込みます。これをHashを使って上手いことやるのですが、詳しくは実装を読んでみてください。
//   ┌───────┐ Running Inst ┌───────┐
//   │Circuit│─────────────►│Circuit│
//   └───────┘              └───▲───┘
//  └────┬────┘                 │
//       │       i-th Inst      │
//       └──────────────────────┘
//
// Suffix
// _r: running
// _i: i-th
// _n: next
// _b: base
pub fn augmented_synthesizer<'a, F: PrimeField>(
    cs: &'a CSWire<F>,
    s_i: &F,
    z_0: &StepInput<F>,
    z_i: &StepInput<F>,
    u_r: &Instance<F>,
    u_i: &Instance<F>,
    memory: &mut HashMap<F, (F, F)>,
    r1cs: &Option<R1CS<F>>,
) -> (V<'a, F>, F, StepInput<F>, Instance<F>) {
    // todo: transcript

    /* 1. count step */
    let s_i = cs.alloc(*s_i);
    let s_n = &s_i + cs.one();

    /* 2. step circuit */
    let z_0 = z_0.alloc(cs);
    let z_i = z_i.alloc(cs);
    let z_n = step_synthesizer(cs, &z_i, memory);

    /* 3. select base or non-base */
    let is_base = is_zero(cs, &s_i);
    let u_b = InstanceVar::base_constant(cs); // 回路定数としてのデフォルト
    let u_r = select_instance_var(cs, &is_base, &u_b, &u_r.alloc(cs));
    let u_i = select_instance_var(cs, &is_base, &u_b, &u_i.alloc(cs));

    /* 4. input consistency */
    let x_i = hash(&s_i, &z_0, &z_i, &u_r) * (cs.one() - is_base);
    cs.equal(x_i, &u_i.zerofold.x.0);

    /* 5. fold instances */
    let u_n = fold_synthesizer(cs, &u_r, &u_i, r1cs);

    /* 6. output */
    let x_n = hash(&s_n, &z_0, &z_n, &u_n); // return as a circuit output(input)
    let s_n = s_n.raw();
    let z_n = z_n.raw();
    let u_n = u_n.raw();

    /* 7. return */
    (x_n, s_n, z_n, u_n)
}


 Step Circuitステップ回路はZKVMのVMの部分に相当します。回路の中には、プログラムカウンターの更新、命令のフェッチ・デコード・実行、メモリの読み書き、が定義されます。

Novaベースでは楕円曲線を使ったコミットメントを使うので、ゼロに対するコミットメントのコストがゼロというのをうまく使って、実際に実行したい命令をスイッチすることができます。メモリの読み書きもメモリのダイジェストを使うこと扱うことで可変長のステートを扱うことができます。
このステップ回路以外は全てSNARKでループを表現するためだけの処理で、この回路では実際のデータ型や演算と、SNARKの演算をどう対応付けるかをよく考える必要があります。

気をつけるべきこととしては、１ステップ１命令だとFoldingしたい回路よりもFoldingに必要な回路の方が圧倒的に多くなってしまい非常に非効率なので、1ステップには複数回の命令を連続して実行できるようにする必要があります。
pub fn step_synthesizer<'a, F: Field>(
    cs: &'a CSWire<F>,
    z_i: &StepInputVar<'a, F>,
    memory: &mut HashMap<F, (F, F)>,
) -> StepInputVar<'a, F> {
    todo!()
}

 ZKVMの開発私のZKVMの開発は主に三つに別れています。
回路合成ツールの開発
Folding回路の実装
VM回路の実装
それぞれはおおよそ、CSWire、augmented_synthesizer、step_synthesizerに対応するわけですが、回路合成ツールの開発はほとんど終わっているので、この記事では残りの二つの開発記録をつけて行ければと思います。
ZKVM開発の記録

ZKVMのレシピ

Circuit Synthesizer

Augmented Circuit

Step Circuit

ZKVMの開発

Discussion
