openvm_verify_stark_host/
lib.rs

1use std::borrow::Borrow;
2
3use eyre::Result;
4use openvm_circuit::{
5    arch::{hasher::poseidon2::vm_poseidon2_hasher, ExitCode},
6    system::{
7        memory::merkle::public_values::UserPublicValuesProof, program::trace::compute_exe_commit,
8    },
9};
10use openvm_stark_backend::{
11    codec::{Decode, Encode},
12    proof::Proof,
13    StarkEngine,
14};
15use openvm_stark_sdk::config::baby_bear_poseidon2::{
16    BabyBearPoseidon2Config as SC, BabyBearPoseidon2CpuEngine, DuplexSponge, DIGEST_SIZE, F,
17};
18use p3_field::{PrimeCharacteristicRing, PrimeField32};
19
20use crate::{
21    deferral::DeferralMerkleProofs,
22    error::VerifyStarkError,
23    pvs::{
24        DeferralPvs, VerifierBasePvs, VerifierDefPvs, VmPvs, CONSTRAINT_EVAL_AIR_ID,
25        CONSTRAINT_EVAL_CACHED_INDEX, DEF_PVS_AIR_ID, MAX_RECURSION_DEPTH, VERIFIER_PVS_AIR_ID,
26        VM_PVS_AIR_ID,
27    },
28    vk::VmStarkVerifyingKey,
29};
30
31pub mod deferral;
32pub mod error;
33pub mod pvs;
34pub mod vk;
35
36pub(crate) type VkCommit = pvs::VkCommit<F>;
37
38// Final internal recursive STARK proof to be verified against the baseline
39#[derive(Clone, Debug)]
40pub struct VmStarkProof {
41    pub inner: Proof<SC>,
42    pub user_pvs_proof: UserPublicValuesProof<DIGEST_SIZE, F>,
43    pub deferral_merkle_proofs: Option<DeferralMerkleProofs<F>>,
44}
45
46impl Encode for VmStarkProof {
47    fn encode<W: std::io::Write>(&self, writer: &mut W) -> std::io::Result<()> {
48        self.inner.encode(writer)?;
49        self.user_pvs_proof.encode::<SC, _>(writer)?;
50        (self.deferral_merkle_proofs.is_some() as u8).encode(writer)?;
51        if let Some(ref proofs) = self.deferral_merkle_proofs {
52            proofs.encode(writer)?;
53        }
54        Ok(())
55    }
56}
57
58impl Decode for VmStarkProof {
59    fn decode<R: std::io::Read>(reader: &mut R) -> std::io::Result<Self> {
60        let inner = Proof::<SC>::decode(reader)?;
61        let user_pvs_proof = UserPublicValuesProof::decode::<SC, _>(reader)?;
62        let deferral_merkle_proofs = if u8::decode(reader)? != 0 {
63            Some(DeferralMerkleProofs::decode(reader)?)
64        } else {
65            None
66        };
67        Ok(Self {
68            inner,
69            user_pvs_proof,
70            deferral_merkle_proofs,
71        })
72    }
73}
74
75/// Verifies a non-root VM STARK proof (as a byte stream) given the internal-recursive
76/// layer verifying key and VM- and exe-specific baseline artifacts.
77pub fn verify_vm_stark_proof(
78    vk: &VmStarkVerifyingKey,
79    encoded_proof: &[u8],
80) -> Result<(), VerifyStarkError> {
81    let decompressed = zstd::decode_all(encoded_proof)?;
82    verify_vm_stark_proof_decoded(vk, &VmStarkProof::decode_from_bytes(&decompressed)?)
83}
84
85/// Verifies a non-root VM STARK proof given the internal-recursive layer verifying
86/// key and VM- and exe-specific baseline artifacts.
87pub fn verify_vm_stark_proof_decoded(
88    vk: &VmStarkVerifyingKey,
89    proof: &VmStarkProof,
90) -> Result<(), VerifyStarkError> {
91    // Verify the STARK proof.
92    let engine = BabyBearPoseidon2CpuEngine::<DuplexSponge>::new(vk.mvk.inner.params.clone());
93    engine.verify(&vk.mvk, &proof.inner)?;
94    verify_vm_stark_proof_pvs(vk, proof)
95}
96
97pub fn verify_vm_stark_proof_pvs(
98    vk: &VmStarkVerifyingKey,
99    proof: &VmStarkProof,
100) -> Result<(), VerifyStarkError> {
101    let (verifier_base_pvs_slice, verifier_def_pvs_slice) = proof.inner.public_values
102        [VERIFIER_PVS_AIR_ID]
103        .as_slice()
104        .split_at(VerifierBasePvs::<u8>::width());
105
106    let &VerifierBasePvs::<F> {
107        internal_flag,
108        app_vk_commit,
109        leaf_vk_commit,
110        internal_for_leaf_vk_commit,
111        recursion_depth,
112        internal_recursive_vk_commit,
113    } = verifier_base_pvs_slice.borrow();
114
115    let &VmPvs::<F> {
116        program_commit,
117        initial_pc,
118        exit_code,
119        is_terminate,
120        initial_root,
121        final_root,
122        ..
123    } = proof.inner.public_values[VM_PVS_AIR_ID].as_slice().borrow();
124
125    let hasher = vm_poseidon2_hasher();
126
127    // Verify the merkle root proof against final_root.
128    proof
129        .user_pvs_proof
130        .verify(&hasher, vk.baseline.memory_dimensions, final_root)?;
131
132    // Check that user_pvs_proof has the correct number of public values.
133    if proof.user_pvs_proof.public_values.len() != vk.baseline.num_user_pvs {
134        return Err(VerifyStarkError::UserPvsLengthMismatch {
135            expected: vk.baseline.num_user_pvs,
136            actual: proof.user_pvs_proof.public_values.len(),
137        });
138    }
139
140    // Check that the app_commit is as expected.
141    let claimed_app_exe_commit =
142        compute_exe_commit(&hasher, &program_commit, &initial_root, initial_pc);
143    if claimed_app_exe_commit != vk.baseline.app_exe_commit {
144        return Err(VerifyStarkError::AppExeCommitMismatch {
145            expected: vk.baseline.app_exe_commit,
146            actual: claimed_app_exe_commit,
147        });
148    }
149
150    // Check that the program terminated with a successful exit code.
151    if exit_code.as_canonical_u32() != ExitCode::Success as u32 || is_terminate != F::ONE {
152        return Err(VerifyStarkError::ExecutionUnsuccessful(exit_code));
153    }
154
155    // Check that the final proof is computed by the internal recursive prover, i.e.
156    // that internal_flag is 2.
157    if internal_flag != F::TWO {
158        return Err(VerifyStarkError::InvalidInternalFlag(internal_flag));
159    }
160
161    // Check app_vk_commit against expected_commits.
162    if app_vk_commit.cached_commit != vk.baseline.app_vk_commit.cached_commit {
163        return Err(VerifyStarkError::AppVkCachedCommitMismatch {
164            expected: vk.baseline.app_vk_commit.cached_commit,
165            actual: app_vk_commit.cached_commit,
166        });
167    }
168    if app_vk_commit.vk_pre_hash != vk.baseline.app_vk_commit.vk_pre_hash {
169        return Err(VerifyStarkError::AppVkPreHashMismatch {
170            expected: vk.baseline.app_vk_commit.vk_pre_hash,
171            actual: app_vk_commit.vk_pre_hash,
172        });
173    }
174
175    // Check leaf_vk_commit against expected_commits.
176    if leaf_vk_commit.cached_commit != vk.baseline.leaf_vk_commit.cached_commit {
177        return Err(VerifyStarkError::LeafVkCachedCommitMismatch {
178            expected: vk.baseline.leaf_vk_commit.cached_commit,
179            actual: leaf_vk_commit.cached_commit,
180        });
181    }
182    if leaf_vk_commit.vk_pre_hash != vk.baseline.leaf_vk_commit.vk_pre_hash {
183        return Err(VerifyStarkError::LeafVkPreHashMismatch {
184            expected: vk.baseline.leaf_vk_commit.vk_pre_hash,
185            actual: leaf_vk_commit.vk_pre_hash,
186        });
187    }
188
189    // Check internal_for_leaf_vk_commit against expected_commits.
190    if internal_for_leaf_vk_commit.cached_commit
191        != vk.baseline.internal_for_leaf_vk_commit.cached_commit
192    {
193        return Err(VerifyStarkError::InternalForLeafVkCachedCommitMismatch {
194            expected: vk.baseline.internal_for_leaf_vk_commit.cached_commit,
195            actual: internal_for_leaf_vk_commit.cached_commit,
196        });
197    }
198    if internal_for_leaf_vk_commit.vk_pre_hash
199        != vk.baseline.internal_for_leaf_vk_commit.vk_pre_hash
200    {
201        return Err(VerifyStarkError::InternalForLeafVkPreHashMismatch {
202            expected: vk.baseline.internal_for_leaf_vk_commit.vk_pre_hash,
203            actual: internal_for_leaf_vk_commit.vk_pre_hash,
204        });
205    }
206
207    // Check that SymbolicExpressionAir's cached trace exists and extract it.
208    let proof_cached_commit =
209        if let Some(trace_vdata) = proof.inner.trace_vdata[CONSTRAINT_EVAL_AIR_ID].as_ref() {
210            if let Some(proof_cached_commit) = trace_vdata
211                .cached_commitments
212                .get(CONSTRAINT_EVAL_CACHED_INDEX)
213            {
214                *proof_cached_commit
215            } else {
216                return Err(VerifyStarkError::MissingConstraintEvalCachedTrace {
217                    air_idx: CONSTRAINT_EVAL_AIR_ID,
218                    cached_idx: CONSTRAINT_EVAL_CACHED_INDEX,
219                });
220            }
221        } else {
222            return Err(VerifyStarkError::MissingConstraintEvalTraceVdata {
223                air_idx: CONSTRAINT_EVAL_AIR_ID,
224            });
225        };
226
227    // Check that recursion_depth is within [1, MAX_RECURSION_DEPTH]. If
228    // recursion_depth == 1 then the penultimate layer is internal-for-leaf,
229    // else it is internal-recursive.
230    let recursion_depth_u32 = recursion_depth.as_canonical_u32();
231    if recursion_depth_u32 == 0 || recursion_depth_u32 > MAX_RECURSION_DEPTH {
232        return Err(VerifyStarkError::InvalidRecursionDepth {
233            actual: recursion_depth,
234            max: MAX_RECURSION_DEPTH,
235        });
236    }
237
238    // Check that internal_recursive_vk_commit is unset if recursion_depth == 1,
239    // and against expected_commits otherwise.
240    if recursion_depth == F::ONE {
241        if !is_unset(&internal_recursive_vk_commit.cached_commit) {
242            return Err(VerifyStarkError::InternalRecursiveVkCachedCommitSet {
243                actual: internal_recursive_vk_commit.cached_commit,
244            });
245        }
246        if !is_unset(&internal_recursive_vk_commit.vk_pre_hash) {
247            return Err(VerifyStarkError::InternalRecursiveVkPreHashSet {
248                actual: internal_recursive_vk_commit.vk_pre_hash,
249            });
250        }
251        if proof_cached_commit != vk.baseline.internal_for_leaf_vk_commit.cached_commit {
252            return Err(VerifyStarkError::ProofCachedCommitMismatch {
253                expected: vk.baseline.internal_for_leaf_vk_commit.cached_commit,
254                actual: proof_cached_commit,
255            });
256        }
257    } else {
258        if internal_recursive_vk_commit.cached_commit
259            != vk.baseline.internal_recursive_vk_commit.cached_commit
260        {
261            return Err(VerifyStarkError::InternalRecursiveVkCachedCommitMismatch {
262                expected: vk.baseline.internal_recursive_vk_commit.cached_commit,
263                actual: internal_recursive_vk_commit.cached_commit,
264            });
265        }
266        if internal_recursive_vk_commit.vk_pre_hash
267            != vk.baseline.internal_recursive_vk_commit.vk_pre_hash
268        {
269            return Err(VerifyStarkError::InternalRecursiveVkPreHashMismatch {
270                expected: vk.baseline.internal_recursive_vk_commit.vk_pre_hash,
271                actual: internal_recursive_vk_commit.vk_pre_hash,
272            });
273        }
274        if proof_cached_commit != vk.baseline.internal_recursive_vk_commit.cached_commit {
275            return Err(VerifyStarkError::ProofCachedCommitMismatch {
276                expected: vk.baseline.internal_recursive_vk_commit.cached_commit,
277                actual: proof_cached_commit,
278            });
279        }
280    }
281
282    // Deferral verification
283    if let Some(expected_def_hook_commit) = vk.baseline.expected_def_hook_commit {
284        let &VerifierDefPvs {
285            deferral_flag,
286            def_hook_commit,
287        } = verifier_def_pvs_slice.borrow();
288
289        let &DeferralPvs {
290            initial_acc_hash,
291            final_acc_hash,
292            depth,
293            node_idx,
294        } = proof.inner.public_values[DEF_PVS_AIR_ID]
295            .as_slice()
296            .borrow();
297
298        if deferral_flag == F::ZERO {
299            if !is_unset(&def_hook_commit) {
300                return Err(VerifyStarkError::DefHookCommitSet {
301                    actual: def_hook_commit,
302                });
303            } else if !is_unset(&initial_acc_hash) {
304                return Err(VerifyStarkError::DefInitialAccHashCommitSet {
305                    actual: initial_acc_hash,
306                });
307            } else if !is_unset(&final_acc_hash) {
308                return Err(VerifyStarkError::DefFinalAccHashCommitSet {
309                    actual: final_acc_hash,
310                });
311            } else if depth != F::ZERO {
312                return Err(VerifyStarkError::DefDepthSet { actual: depth });
313            }
314        } else if deferral_flag == F::TWO {
315            if def_hook_commit != expected_def_hook_commit {
316                return Err(VerifyStarkError::DefHookCommitMismatch {
317                    expected: expected_def_hook_commit,
318                    actual: def_hook_commit,
319                });
320            }
321        } else {
322            return Err(VerifyStarkError::InvalidDeferralFlag(deferral_flag));
323        }
324
325        if node_idx != F::ZERO {
326            return Err(VerifyStarkError::DefNodeIdxNonZero { actual: node_idx });
327        }
328
329        let deferral_merkle_proofs = proof
330            .deferral_merkle_proofs
331            .as_ref()
332            .ok_or(VerifyStarkError::MissingDeferralMerkleProofs)?;
333        deferral_merkle_proofs.verify(
334            vk.baseline.memory_dimensions,
335            initial_root,
336            final_root,
337            initial_acc_hash,
338            final_acc_hash,
339            depth.as_canonical_u32() as usize,
340        )?;
341    } else if !verifier_def_pvs_slice.is_empty()
342        || !proof.inner.public_values[DEF_PVS_AIR_ID].is_empty()
343        || proof.deferral_merkle_proofs.is_some()
344    {
345        return Err(VerifyStarkError::UnexpectedDeferralDisabled);
346    }
347
348    Ok(())
349}
350
351fn is_unset(slice: &[F]) -> bool {
352    slice.iter().all(|&f| f == F::ZERO)
353}
openvm_verify_stark_host/lib.rs

openvm_verify_stark_host/
lib.rs
