risc0_zkp/verify/
mod.rs

1// Copyright 2026 RISC Zero, Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Cryptographic algorithms for verifying a ZK proof of compute
16
17mod fri;
18mod merkle;
19mod read_iop;
20
21use alloc::{vec, vec::Vec};
22use core::{
23    cell::{RefCell, RefMut},
24    fmt,
25    iter::zip,
26    ops::DerefMut,
27};
28
29pub(crate) use merkle::MerkleTreeVerifier;
30pub use read_iop::ReadIOP;
31use risc0_core::field::{Elem, ExtElem, Field, RootsOfUnity};
32
33use crate::{
34    adapter::{
35        CircuitCoreDef, ProtocolInfo, PROOF_SYSTEM_INFO, REGISTER_GROUP_ACCUM, REGISTER_GROUP_CODE,
36        REGISTER_GROUP_DATA,
37    },
38    core::{digest::Digest, hash::HashSuite, log2_ceil},
39    taps::TapSet,
40    INV_RATE, MAX_CYCLES_PO2, QUERIES,
41};
42
43// If true, enable tracing of verifier internals.
44const VERIFY_TRACE_ENABLED: bool = false;
45
46macro_rules! trace_if_enabled {
47    ($($args:tt)*) => {
48        if VERIFY_TRACE_ENABLED {
49            #[cfg(not(target_os = "zkvm"))]
50            tracing::debug!($($args)*);
51        }
52    }
53}
54
55#[derive(PartialEq)]
56#[non_exhaustive]
57pub enum VerificationError {
58    ReceiptFormatError,
59    ControlVerificationError {
60        control_id: Digest,
61    },
62    ImageVerificationError,
63    MerkleQueryOutOfRange {
64        idx: usize,
65        rows: usize,
66    },
67    InvalidProof,
68    JournalDigestMismatch,
69    ClaimDigestMismatch {
70        expected: Digest,
71        received: Digest,
72    },
73    UnexpectedExitCode,
74    InvalidHashSuite,
75    VerifierParametersMissing,
76    VerifierParametersMismatch {
77        expected: Digest,
78        received: Digest,
79    },
80    ProofSystemInfoMismatch {
81        expected: ProtocolInfo,
82        received: ProtocolInfo,
83    },
84    CircuitInfoMismatch {
85        expected: ProtocolInfo,
86        received: ProtocolInfo,
87    },
88    UnresolvedAssumption {
89        digest: Digest,
90    },
91}
92
93impl fmt::Debug for VerificationError {
94    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
95        fmt::Display::fmt(&self, f)
96    }
97}
98
99impl fmt::Display for VerificationError {
100    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
101        match self {
102            VerificationError::ReceiptFormatError => write!(f, "invalid receipt format"),
103            VerificationError::ControlVerificationError { control_id } => {
104                write!(f, "control_id mismatch: {control_id}")
105            }
106            VerificationError::ImageVerificationError => write!(f, "image_id mismatch"),
107            VerificationError::MerkleQueryOutOfRange { idx, rows } => write!(
108                f,
109                "requested Merkle validation on row {idx}, but only {rows} rows exist",
110            ),
111            VerificationError::InvalidProof => write!(f, "verification indicates proof is invalid"),
112            VerificationError::JournalDigestMismatch => {
113                write!(f, "journal digest mismatch detected")
114            }
115            VerificationError::ClaimDigestMismatch { expected, received } => {
116                write!(f, "claim digest does not match the expected digest {received}; expected {expected}")
117            }
118            VerificationError::UnexpectedExitCode => write!(f, "unexpected exit_code"),
119            VerificationError::InvalidHashSuite => write!(f, "invalid hash suite"),
120            VerificationError::VerifierParametersMissing => {
121                write!(f, "verifier parameters were not found in verifier context for the given receipt type")
122            }
123            VerificationError::VerifierParametersMismatch { expected, received } => {
124                write!(f, "receipt was produced for a version of the verifier with parameters digest {received}; expected {expected}")
125            }
126            VerificationError::ProofSystemInfoMismatch { expected, received } => {
127                write!(f, "receipt was produced for a version of the verifier with proof system info {received}; expected {expected}")
128            }
129            VerificationError::CircuitInfoMismatch { expected, received } => {
130                write!(f, "receipt was produced for a version of the verifier with circuit info {received}; expected {expected}")
131            }
132            VerificationError::UnresolvedAssumption { digest } => {
133                write!(f, "receipt contains an unresolved assumption: {digest}")
134            }
135        }
136    }
137}
138
139#[cfg(feature = "std")]
140impl std::error::Error for VerificationError {}
141
142trait VerifyParams<F: Field> {
143    const CHECK_SIZE: usize = INV_RATE * F::ExtElem::EXT_SIZE;
144}
145
146#[stability::unstable]
147pub struct Verifier<'a, F>
148where
149    F: Field,
150{
151    taps: &'a TapSet<'a>,
152    suite: &'a HashSuite<F>,
153    iop: RefCell<ReadIOP<'a, F>>,
154    po2: usize,
155    tot_cycles: usize,
156    // Merkle tree verifiers, indexed by register group id
157    merkle_verifiers: Vec<Option<MerkleTreeVerifier<'a>>>,
158}
159
160impl<F: Field> VerifyParams<F> for Verifier<'_, F> {}
161
162impl<'a, F: Field> Verifier<'a, F> {
163    /// Start a new verification session.
164    #[stability::unstable]
165    pub fn new(taps: &'a TapSet<'a>, suite: &'a HashSuite<F>, seal: &'a [u32]) -> Self {
166        trace_if_enabled!("Starting verify");
167        Self {
168            taps,
169            suite,
170            po2: 0,
171            tot_cycles: 0,
172            iop: RefCell::new(ReadIOP::new(seal, suite.rng.as_ref())),
173            merkle_verifiers: core::iter::repeat_with(|| None)
174                .take(taps.num_groups())
175                .collect(),
176        }
177    }
178
179    #[stability::unstable]
180    pub fn iop(&self) -> RefMut<'_, ReadIOP<'a, F>> {
181        self.iop.borrow_mut()
182    }
183
184    #[stability::unstable]
185    pub fn commit_circuit_info(&mut self, circuit_info: &ProtocolInfo) {
186        trace_if_enabled!("Verifying protocol={PROOF_SYSTEM_INFO} circuit {circuit_info}");
187        // At the start of the protocol, seed the Fiat-Shamir transcript with context information
188        // about the proof system and circuit.
189        let hashfn = self.suite.hashfn.as_ref();
190        self.iop()
191            .commit(&hashfn.hash_elem_slice(&PROOF_SYSTEM_INFO.encode()));
192        self.iop()
193            .commit(&hashfn.hash_elem_slice(&circuit_info.encode()));
194    }
195
196    /// Read in the next merkle group in the seal.  `reg_group_id` should be the group ID
197    /// as specified in the taps.
198    #[stability::unstable]
199    pub fn verify_group(&mut self, reg_group_id: usize) -> Result<&Digest, VerificationError> {
200        // NOTE: reg_group_id is from a set of constants associated with a circuit and protocol.
201        // It is not controlled by the prover.
202        if self.merkle_verifiers[reg_group_id].is_some() {
203            tracing::debug!(
204                "Reg group id {reg_group_id} ({}) may only occur once",
205                self.taps.group_name(reg_group_id)
206            );
207            return Err(VerificationError::ReceiptFormatError);
208        }
209        let group_size = self.taps.group_size(reg_group_id);
210        let domain = INV_RATE * self.tot_cycles;
211        let hashfn = self.suite.hashfn.as_ref();
212
213        let merkle =
214            MerkleTreeVerifier::new(self.iop().deref_mut(), hashfn, domain, group_size, QUERIES)?;
215        self.merkle_verifiers[reg_group_id] = Some(merkle);
216        let root = self.merkle_verifiers[reg_group_id].as_ref().unwrap().root();
217        trace_if_enabled!(
218            "{} (group id={reg_group_id}) root: {root:?}",
219            self.taps.group_name(reg_group_id)
220        );
221        Ok(root)
222    }
223
224    /// Reads `elems` field elements of randomness from the IOP
225    #[stability::unstable]
226    pub fn read_rng(&mut self, elems: usize) -> Vec<F::Elem> {
227        let mix = (0..elems).map(|_| self.iop().random_elem()).collect();
228        trace_if_enabled!("Got mix values from IOP: {mix:?}");
229        mix
230    }
231
232    #[allow(clippy::too_many_arguments)]
233    // Compute the FRI verify taps sum.
234    fn fri_eval_taps(
235        &self,
236        combo_u: &[F::ExtElem],
237        check_row: &[F::Elem],
238        back_one: F::Elem,
239        x: F::Elem,
240        z: F::ExtElem,
241        rows: &[&[F::Elem]],
242        tap_mix_pows: &[F::ExtElem],
243        check_mix_pows: &[F::ExtElem],
244    ) -> F::ExtElem {
245        let mut tot = vec![F::ExtElem::ZERO; self.taps.combos_size() + 1];
246        let combo_count = self.taps.combos_size();
247        let x = F::ExtElem::from_subfield(&x);
248
249        for (reg, cur) in zip(self.taps.regs(), tap_mix_pows.iter()) {
250            tot[reg.combo_id()] += *cur * rows[reg.group()][reg.offset()];
251        }
252        for (i, cur) in zip(0..Self::CHECK_SIZE, check_mix_pows.iter()) {
253            tot[combo_count] += *cur * check_row[i];
254        }
255        let mut ret = F::ExtElem::ZERO;
256        for i in 0..combo_count {
257            let num = tot[i]
258                - self.poly_eval(
259                    &combo_u
260                        [self.taps.combo_begin[i] as usize..self.taps.combo_begin[i + 1] as usize],
261                    x,
262                );
263            let mut divisor = F::ExtElem::ONE;
264            for back in self.taps.get_combo(i).slice() {
265                divisor *= x - z * back_one.pow(*back as usize);
266            }
267            ret += num * divisor.inv();
268        }
269        let check_num = tot[combo_count] - combo_u[self.taps.tot_combo_backs];
270        let check_div = x - z.pow(INV_RATE);
271        ret += check_num * check_div.inv();
272        ret
273    }
274
275    /// Execute the IOP protocol to verify the validity polynomial
276    /// such that all the constraints are satisfied.  This is
277    /// currently only supported when called exactly once at the end
278    /// of the verification.
279    #[stability::unstable]
280    pub fn verify_validity(
281        &mut self,
282        validity_fn: impl Fn(&F::ExtElem, &[F::ExtElem]) -> F::ExtElem,
283    ) -> Result<(), VerificationError> {
284        // Ensure that we were given verifiers for all tap groups
285        for (reg_group_id, verifier) in self.merkle_verifiers.iter().enumerate() {
286            if !verifier.is_some() {
287                panic!(
288                    "Missing merkle verifier for reg group {reg_group_id} ({})",
289                    self.taps.group_name(reg_group_id)
290                );
291            }
292        }
293
294        // Get a pseudorandom value with which to mix the constraint polynomials.
295        // See DEEP-ALI protocol from DEEP-FRI paper for details on constraint mixing.
296        let poly_mix = self.iop().random_ext_elem();
297        trace_if_enabled!("Poly mix: {poly_mix:?}");
298
299        let hashfn = self.suite.hashfn.as_ref();
300        let domain = INV_RATE * self.tot_cycles;
301        let check_merkle = MerkleTreeVerifier::new(
302            self.iop().deref_mut(),
303            hashfn,
304            domain,
305            Self::CHECK_SIZE,
306            QUERIES,
307        )?;
308        trace_if_enabled!("Check merkle root: {}", check_merkle.root());
309
310        // Get a pseudorandom DEEP query point
311        // See DEEP-ALI protocol from DEEP-FRI paper for details on DEEP query.
312        cfg_if::cfg_if! {
313            if #[cfg(feature = "circuit_debug")] {
314                let z_slice = self.iop().read_field_elem_slice(F::ExtElem::EXT_SIZE);
315                let z = F::ExtElem::from_subelems(z_slice.iter().cloned());
316            } else {
317                let z = self.iop().random_ext_elem();
318            }
319        }
320
321        // NOTE: There is one ROU for each po2. If not, this will panic.
322        trace_if_enabled!("Z = {z:?}");
323        let back_one = F::Elem::ROU_REV[self.po2];
324
325        // Read the U coeffs (the interpolations of the taps) + commit their hash.
326        let num_taps = self.taps.tap_size();
327        let coeff_u = self
328            .iop()
329            .read_field_elem_slice(num_taps + Self::CHECK_SIZE)?;
330        let hash_u = hashfn.hash_ext_elem_slice(coeff_u);
331        self.iop().commit(&hash_u);
332
333        // Now, convert U polynomials from coefficient form to evaluation form
334        let mut cur_pos = 0;
335        let mut eval_u = Vec::with_capacity(num_taps);
336        for reg in self.taps.regs() {
337            for i in 0..reg.size() {
338                let x = z * back_one.pow(reg.back(i));
339                let fx = self.poly_eval(&coeff_u[cur_pos..(cur_pos + reg.size())], x);
340                eval_u.push(fx);
341            }
342            cur_pos += reg.size();
343        }
344        assert_eq!(eval_u.len(), num_taps, "Miscalculated capacity for eval_us");
345
346        // Compute the core constraint polynomial.
347        // I.e. the set of all constraints mixed by poly_mix
348        #[cfg(not(target_os = "zkvm"))]
349        tracing::debug!("> compute_polynomial");
350
351        let result = validity_fn(&poly_mix, &eval_u);
352        trace_if_enabled!("Computed polynomial: {result:?}");
353
354        // Now generate the check polynomial
355        // TODO: This currently treats the extension degree as hardcoded at 4, with
356        // the structure of the code and the value of `remap` (and how it is
357        // accessed) only working in the extension degree = 4 case.
358        // However, for generic fields the extension degree may be different
359        // TODO: Therefore just using the to/from baby bear shims for now
360        let mut check = F::ExtElem::default();
361        let remap = [0, 2, 1, 3];
362        let fp0 = F::Elem::ZERO;
363        let fp1 = F::Elem::ONE;
364        for (i, rmi) in remap.iter().enumerate() {
365            check += coeff_u[num_taps + rmi]
366                * z.pow(i)
367                * F::ExtElem::from_subelems([fp1, fp0, fp0, fp0]);
368            check += coeff_u[num_taps + rmi + 4]
369                * z.pow(i)
370                * F::ExtElem::from_subelems([fp0, fp1, fp0, fp0]);
371            check += coeff_u[num_taps + rmi + 8]
372                * z.pow(i)
373                * F::ExtElem::from_subelems([fp0, fp0, fp1, fp0]);
374            check += coeff_u[num_taps + rmi + 12]
375                * z.pow(i)
376                * F::ExtElem::from_subelems([fp0, fp0, fp0, fp1]);
377        }
378        let three = F::Elem::from_u64(3);
379        check *= (F::ExtElem::from_subfield(&three) * z).pow(self.tot_cycles) - F::ExtElem::ONE;
380        trace_if_enabled!("Check = {check:?}");
381        if check != result {
382            tracing::debug!("check != result");
383            return Err(VerificationError::InvalidProof);
384        }
385
386        // Set the mix value, pseudorandom value used for FRI batching
387        let mix = self.iop().random_ext_elem();
388        trace_if_enabled!("FRI mix = {mix:?}");
389
390        // Fill in
391
392        // Make the mixed U polynomials.
393        // combo_u has one element for each column with the same set of taps.
394        // These columns share a denominator in the DEEP-ALI equation.
395        // We group these terms together to reduce the number of inverses we
396        // need to compute.
397        let mut combo_u: Vec<F::ExtElem> = vec![F::ExtElem::ZERO; self.taps.tot_combo_backs + 1];
398        let mut cur_mix = F::ExtElem::ONE;
399        cur_pos = 0;
400        let mut tap_mix_pows = Vec::with_capacity(self.taps.reg_count());
401        for reg in self.taps.regs() {
402            for i in 0..reg.size() {
403                combo_u[self.taps.combo_begin[reg.combo_id()] as usize + i] +=
404                    cur_mix * coeff_u[cur_pos + i];
405            }
406            tap_mix_pows.push(cur_mix);
407            cur_mix *= mix;
408            cur_pos += reg.size();
409        }
410        assert_eq!(
411            tap_mix_pows.len(),
412            self.taps.reg_count(),
413            "Miscalculated capacity for tap_mix_pows"
414        );
415        trace_if_enabled!("cur_mix: {cur_mix:?}, cur_pos: {cur_pos}");
416        // Handle check group
417        let mut check_mix_pows = Vec::with_capacity(Self::CHECK_SIZE);
418        for _ in 0..Self::CHECK_SIZE {
419            combo_u[self.taps.tot_combo_backs] += cur_mix * coeff_u[cur_pos];
420            cur_pos += 1;
421            check_mix_pows.push(cur_mix);
422            cur_mix *= mix;
423        }
424        assert_eq!(
425            check_mix_pows.len(),
426            Self::CHECK_SIZE,
427            "Miscalculated capacity for check_mix_pows"
428        );
429        let gen = <F::Elem as RootsOfUnity>::ROU_FWD[log2_ceil(domain)];
430        let hashfn = self.suite.hashfn.as_ref();
431        self.fri_verify(|idx| {
432            let x = gen.pow(idx);
433            let rows= self
434                .merkle_verifiers
435                .iter()
436                .map(|merkle: &Option<MerkleTreeVerifier>| -> Result<&'a [F::Elem], VerificationError> {
437                    merkle.as_ref()
438                        .unwrap()
439                        .verify(self.iop().deref_mut(), hashfn, idx)
440                })
441                .collect::<Result<Vec<_>,_>>()?;
442            let check_row = check_merkle.verify(self.iop().deref_mut(), hashfn, idx)?;
443            let ret = self.fri_eval_taps(&combo_u, check_row, back_one, x, z, &rows, &tap_mix_pows, &check_mix_pows);
444            Ok(ret)
445        })?;
446        Ok(())
447    }
448
449    /// Reads a slice of `size` field elements from the IOP along with
450    /// the po2 of the number of cycles the circuit ran for, and
451    /// commits to them.  This is typically used at the beginning of
452    /// the seal to encode the globals of the circuit.
453    #[stability::unstable]
454    pub fn read_slice_with_po2(
455        &mut self,
456        size: usize,
457    ) -> Result<(&'a [F::Elem], usize), VerificationError> {
458        let slice = self.iop().read_field_elem_slice(size + 1)?;
459        self.iop().commit(&self.suite.hashfn.hash_elem_slice(slice));
460
461        // Extract the out buffer and po2 from slice while checking sizes.
462        let (out, &[po2_elem]) = slice.split_at(size) else {
463            unreachable!("slice returned by read_field_elem_slice is wrong size");
464        };
465        let (&[po2], &[]) = po2_elem.to_u32_words().split_at(1) else {
466            unreachable!("po2 elem is larger than u32");
467        };
468        if po2 as usize > MAX_CYCLES_PO2 {
469            tracing::error!("po2 in seal is larger than the max po2: {po2} > {MAX_CYCLES_PO2}");
470            return Err(VerificationError::ReceiptFormatError);
471        }
472        self.po2 = po2 as usize;
473        self.tot_cycles = 1usize.checked_shl(po2).unwrap();
474        Ok((out, self.po2))
475    }
476
477    /// Evaluate a polynomial whose coefficients are in the extension field at a
478    /// point.
479    fn poly_eval(&self, coeffs: &[F::ExtElem], x: F::ExtElem) -> F::ExtElem {
480        let mut mul_x = F::ExtElem::ONE;
481        let mut tot = F::ExtElem::ZERO;
482        for coeff in coeffs {
483            tot += *coeff * mul_x;
484            mul_x *= x;
485        }
486        tot
487    }
488}
489
490/// Verify a seal is valid for the given circuit, and code checking function.
491///
492/// This version of `verify` has a fixed IOP protocol that's used by
493/// multiple circuits.
494// Circuits that don't share this protocol may use [Verifier] directly once it's stabilized.
495pub fn verify<F, C, CheckCode>(
496    circuit: &C,
497    suite: &HashSuite<F>,
498    seal: &[u32],
499    check_code: CheckCode,
500) -> Result<(), VerificationError>
501where
502    F: Field,
503    C: CircuitCoreDef<F>,
504    CheckCode: Fn(u32, &Digest) -> Result<(), VerificationError>,
505{
506    if seal.is_empty() {
507        return Err(VerificationError::ReceiptFormatError);
508    }
509
510    let mut verifier = Verifier::<F>::new(circuit.get_taps(), suite, seal);
511    verifier.commit_circuit_info(&C::CIRCUIT_INFO);
512
513    // Read the globals (i.e. outputs) from the IOP, and mix them into the Fiat-Shamir state.
514    //
515    // NOTE: The globals are the only values known to the verifier, and constitute the public
516    // statement of the prover. In many scenarios, they are the first values sent to the
517    // verifier by the prover, and therefore should be committed at the start of verification.
518    let (out, po2) = verifier.read_slice_with_po2(C::OUTPUT_SIZE)?;
519
520    // Get merkle root for the code merkle tree.
521    // The code merkle tree contains the control instructions for the zkVM.
522    let code_root = verifier.verify_group(REGISTER_GROUP_CODE)?;
523
524    // Invoke the user-supplied verification function to ensure that
525    // the code root of the merkle tree is as expected.
526    check_code(po2 as u32, code_root)?;
527
528    // Get merkle root for the data merkle tree.
529    // The data merkle tree contains the execution trace of the program being run,
530    // including memory accesses as well as the permutation of those memory
531    // accesses sorted by location used by PLONK.
532    verifier.verify_group(REGISTER_GROUP_DATA)?;
533
534    // Fill in accum mix
535    let mix = verifier.read_rng(C::MIX_SIZE);
536
537    // Get merkle root for the accum merkle tree.
538    // The accum merkle tree contains the accumulations for two permutation check
539    // arguments: Each permutation check consists of a pre-permutation
540    // accumulation and a post-permutation accumulation.
541    // The first permutation check uses memory-based values (see PLONK paper for
542    // details). This permutation is used to re-order memory accesses for
543    // quicker verification. The second permutation check uses bytes-based
544    // values (see PLOOKUP paper for details). This permutation is used to
545    // implement a look-up table.
546    verifier.verify_group(REGISTER_GROUP_ACCUM)?;
547
548    // Verify the evaluation of the validity polynomial to make sure
549    // the constraints were not violated.
550    verifier
551        .verify_validity(|poly_mix, eval_u| circuit.poly_ext(poly_mix, eval_u, &[out, &mix]).tot)?;
552
553    // There should be nothing else in the IOP, so verify that's the case.
554    verifier.iop().verify_complete()?;
555    Ok(())
556}
risc0_zkp/verify/mod.rs

risc0_zkp/verify/
mod.rs
