openvm_static_verifier/
circuit.rs

1//! Host-fixed parameters for the static verifier Halo2 circuit (see crate `lib.rs`).
2
3use core::cmp::Reverse;
4use std::{borrow::Borrow, fmt, sync::Arc};
5
6use halo2_base::{
7    gates::circuit::builder::BaseCircuitBuilder, halo2_proofs::halo2curves::bn256::Fr, Context,
8};
9use itertools::Itertools;
10use openvm_cpu_backend::CpuBackend;
11use openvm_recursion_circuit::{
12    batch_constraint::expr_eval::DagCommitPvs,
13    system::{VerifierConfig, VerifierSubCircuit, VerifierTraceGen},
14};
15use openvm_stark_sdk::{
16    config::{
17        baby_bear_bn254_poseidon2::BabyBearBn254Poseidon2Config as RootConfig,
18        baby_bear_poseidon2::{BabyBearPoseidon2Config, Digest as InnerDigest},
19    },
20    openvm_stark_backend::{
21        keygen::types::{MultiStarkVerifyingKey, MultiStarkVerifyingKey0},
22        proof::Proof,
23        prover::stacked_pcs::StackedLayout,
24    },
25};
26use openvm_verify_stark_host::pvs::CONSTRAINT_EVAL_AIR_ID;
27use serde::{Deserialize, Serialize};
28
29use crate::{
30    field::baby_bear::{BabyBearChip, BabyBearExtChip},
31    stages::{
32        full_pipeline::{
33            constrained_verify, extract_public_values, load_proof_wire, ProofWire,
34            StaticVerifierPvs,
35        },
36        proof_shape::trace_id_order_from_static_heights,
37    },
38};
39
40/// Builds stacked PCS layouts for the static verifier from VK widths and fixed per-air log heights.
41pub(crate) fn build_stacked_layouts_for_static_vk(
42    mvk0: &MultiStarkVerifyingKey0<RootConfig>,
43    log_heights_per_air: &[usize],
44) -> Vec<StackedLayout> {
45    let l_skip = mvk0.params.l_skip;
46    assert_eq!(
47        log_heights_per_air.len(),
48        mvk0.per_air.len(),
49        "log_heights_per_air length must match VK per_air count"
50    );
51    let mut per_trace = mvk0
52        .per_air
53        .iter()
54        .enumerate()
55        .map(|(air_idx, vk)| (air_idx, vk, log_heights_per_air[air_idx]))
56        .collect::<Vec<_>>();
57    per_trace.sort_by_key(|(_, _, log_height)| Reverse(*log_height));
58
59    let common_main_layout = StackedLayout::new(
60        l_skip,
61        mvk0.params.n_stack + l_skip,
62        per_trace
63            .iter()
64            .map(|(_, vk, log_height)| (vk.params.width.common_main, *log_height))
65            .collect::<Vec<_>>(),
66    )
67    .expect("stacked layout for common main");
68    let other_layouts = per_trace
69        .iter()
70        .flat_map(|(_, vk, log_height)| {
71            vk.params
72                .width
73                .preprocessed
74                .iter()
75                .chain(&vk.params.width.cached_mains)
76                .copied()
77                .map(|width| (width, *log_height))
78                .collect::<Vec<_>>()
79        })
80        .map(|sorted| {
81            StackedLayout::new(l_skip, mvk0.params.n_stack + l_skip, vec![sorted])
82                .expect("stacked layout for auxiliary column")
83        })
84        .collect::<Vec<_>>();
85    core::iter::once(common_main_layout)
86        .chain(other_layouts)
87        .collect::<Vec<_>>()
88}
89
90/// Error building [`StaticVerifierCircuit`] from fixed per-AIR log heights.
91#[derive(Debug, Clone, PartialEq, Eq)]
92pub enum StaticCircuitParamsError {
93    LogHeightsLenMismatch { expected: usize, got: usize },
94}
95
96impl fmt::Display for StaticCircuitParamsError {
97    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
98        match self {
99            Self::LogHeightsLenMismatch { expected, got } => {
100                write!(
101                    f,
102                    "log_heights_per_air length {got} != VK per_air length {expected}"
103                )
104            }
105        }
106    }
107}
108
109impl std::error::Error for StaticCircuitParamsError {}
110
111/// Parameters fixed host-side for the static verifier (child VK, trace heights, AIR permutation).
112#[derive(Clone, Debug, Serialize, Deserialize)]
113pub struct StaticVerifierCircuit {
114    pub root_vk: MultiStarkVerifyingKey<RootConfig>,
115    /// The [RootConfig] hash onion commitment to the internal-recursive verifier circuit's
116    /// symbolic constraints DAG. This is exposed as a public value by the DagCommitSubAir within
117    /// the SymbolicExpressionAir in the RootVerifierCircuit.
118    ///
119    /// This value can be obtained from `cached_trace_record.dag_commit_info.commit` in the
120    /// `RootProver`.
121    pub internal_recursive_dag_onion_commit: InnerDigest,
122    pub log_heights_per_air: Vec<usize>,
123    pub trace_id_to_air_id: Vec<usize>,
124    pub stacked_layouts: Vec<StackedLayout>,
125}
126
127impl StaticVerifierCircuit {
128    /// Build static parameters from a child VK and the per-AIR trace log heights for this circuit.
129    ///
130    /// `log_heights_per_air[i]` is the log₂ trace height for AIR `i` (same indexing as the child
131    /// VK's `per_air`). Trace IDs are ordered by descending height (tie-break: lower `air_id`
132    /// first).
133    pub fn try_new(
134        root_vk: MultiStarkVerifyingKey<RootConfig>,
135        internal_recursive_dag_onion_commit: InnerDigest,
136        log_heights_per_air: &[usize],
137    ) -> Result<Self, StaticCircuitParamsError> {
138        let n = root_vk.inner.per_air.len();
139        if log_heights_per_air.len() != n {
140            return Err(StaticCircuitParamsError::LogHeightsLenMismatch {
141                expected: n,
142                got: log_heights_per_air.len(),
143            });
144        }
145        let log_heights_per_air = log_heights_per_air.to_vec();
146        let trace_id_to_air_id =
147            trace_id_order_from_static_heights(&root_vk.inner, &log_heights_per_air);
148        let stacked_layouts =
149            build_stacked_layouts_for_static_vk(&root_vk.inner, &log_heights_per_air);
150        Ok(Self {
151            root_vk,
152            internal_recursive_dag_onion_commit,
153            log_heights_per_air,
154            trace_id_to_air_id,
155            stacked_layouts,
156        })
157    }
158
159    /// STARK verification constraints only: load the proof witness and run
160    /// `constrained_verify`.
161    ///
162    /// Does **not** check proof public values or cached trace commitments, which requires the proof
163    /// to have a particular shape following the VM Continuations framework.
164    ///
165    /// This function should be used internally or for testing only.
166    /// Production uses with the continuations framework **must** use [`Self::populate`] instead.
167    pub fn populate_verify_stark_constraints(
168        &self,
169        ctx: &mut Context<Fr>,
170        ext_chip: &BabyBearExtChip,
171        proof: &Proof<RootConfig>,
172    ) -> ProofWire {
173        let mut profiler = crate::profiling::CellProfiler::new("static_verifier", ctx.advice.len());
174
175        profiler.push("load_proof_wire", ctx.advice.len());
176        let proof_wire = load_proof_wire(ctx, ext_chip, proof, &self.log_heights_per_air);
177        profiler.pop(ctx.advice.len());
178
179        profiler.push("constrained_verify", ctx.advice.len());
180        constrained_verify(
181            ctx,
182            ext_chip,
183            &self.root_vk,
184            &proof_wire,
185            &self.trace_id_to_air_id,
186            &self.log_heights_per_air,
187            &self.stacked_layouts,
188        );
189        profiler.pop(ctx.advice.len());
190
191        profiler.print(ctx.advice.len());
192
193        #[cfg(feature = "cell-profiling")]
194        if let Ok(dir) = std::env::var("OPENVM_PROFILE_DIR") {
195            let _ = std::fs::create_dir_all(&dir);
196            profiler.write_flamegraph(
197                &format!("{dir}/static_verifier_constraints.svg"),
198                "Static Verifier Constraints",
199                ctx.advice.len(),
200            );
201            profiler.write_flamegraph_reversed(
202                &format!("{dir}/static_verifier_constraints_rev.svg"),
203                "Static Verifier Constraints (reversed)",
204                ctx.advice.len(),
205            );
206        }
207
208        proof_wire
209    }
210
211    /// Populate a builder with the static verifier constraints and return the public values.
212    pub fn populate(
213        &self,
214        builder: &mut BaseCircuitBuilder<Fr>,
215        proof: &Proof<RootConfig>,
216    ) -> StaticVerifierPvs<Fr> {
217        let range = builder.range_chip();
218        let ext_chip = BabyBearExtChip::new(BabyBearChip::new(Arc::new(range)));
219        let ctx = builder.main(0);
220
221        let mut profiler = crate::profiling::CellProfiler::new("populate", ctx.advice.len());
222
223        profiler.push("verify_stark_constraints", ctx.advice.len());
224        let proof_wire = &self.populate_verify_stark_constraints(ctx, &ext_chip, proof);
225        profiler.pop(ctx.advice.len());
226
227        debug_assert!(
228            proof_wire
229                .cached_commitment_roots
230                .iter()
231                .all(|commits| commits.is_empty()),
232            "RootVerifierCircuit has no cached trace"
233        );
234        profiler.push("pin_dag_onion_commit", ctx.advice.len());
235        let &DagCommitPvs::<_> {
236            commit: onion_commit,
237        } = proof_wire.public_values[CONSTRAINT_EVAL_AIR_ID]
238            .as_slice()
239            .borrow();
240        for (bb_wire, bb_const) in onion_commit
241            .into_iter()
242            .zip_eq(self.internal_recursive_dag_onion_commit)
243        {
244            let loaded_const = ext_chip.base().load_constant(ctx, bb_const);
245            ext_chip
246                .base()
247                .assert_equal(ctx, bb_wire.into(), loaded_const);
248        }
249        profiler.pop(ctx.advice.len());
250
251        profiler.push("extract_public_values", ctx.advice.len());
252        let pvs_wire = extract_public_values(ctx, ext_chip.base(), proof_wire);
253        profiler.pop(ctx.advice.len());
254
255        #[cfg(feature = "cell-profiling")]
256        if let Ok(dir) = std::env::var("OPENVM_PROFILE_DIR") {
257            let _ = std::fs::create_dir_all(&dir);
258            profiler.write_flamegraph(
259                &format!("{dir}/populate.svg"),
260                "Static Verifier Populate",
261                ctx.advice.len(),
262            );
263            profiler.write_flamegraph_reversed(
264                &format!("{dir}/populate_rev.svg"),
265                "Static Verifier Populate (reversed)",
266                ctx.advice.len(),
267            );
268        }
269
270        let pvs_vec = pvs_wire.to_vec();
271        let pvs_fr = pvs_vec.iter().map(|v| *v.value()).collect_vec();
272        builder.assigned_instances[0].extend(pvs_vec);
273
274        StaticVerifierPvs::from_slice(&pvs_fr)
275    }
276}
277
278pub fn compute_dag_onion_commit(
279    internal_recursive_vk: &MultiStarkVerifyingKey<BabyBearPoseidon2Config>,
280) -> InnerDigest {
281    // Note: the MAX_NUM_PROOFS const generic does not impact the build_cached_trace_record function
282    // used internally below, but we use 1 to match the root circuit. The internal_recursive circuit
283    // itself uses MAX_NUM_PROOFS = 3, but here it is the child.
284    let verifier_circuit = VerifierSubCircuit::<1>::new_with_options(
285        Arc::new(internal_recursive_vk.clone()),
286        VerifierConfig {
287            continuations_enabled: true,
288            has_cached: false,
289            ..Default::default()
290        },
291    );
292
293    // The ProverBackend and config used here also does not impact the generated CachedTraceRecord
294    let cached_trace_record = VerifierTraceGen::<
295        CpuBackend<BabyBearPoseidon2Config>,
296        BabyBearPoseidon2Config,
297        (),
298    >::cached_trace_record(&verifier_circuit, internal_recursive_vk);
299
300    // Despite the name, this returns the DAG onion commit for when there is no cached trace
301    cached_trace_record.dag_commit_info.unwrap().commit
302}
openvm_static_verifier/circuit.rs

openvm_static_verifier/
circuit.rs
