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

openvm_static_verifier/
circuit.rs
