risc0_zkp/verify/
mod.rs

1// Copyright 2025 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            // TODO: change this to core::iter::repeat_n once it's stablabized.
174            merkle_verifiers: core::iter::repeat_with(|| None)
175                .take(taps.num_groups())
176                .collect(),
177        }
178    }
179
180    #[stability::unstable]
181    pub fn iop(&self) -> RefMut<'_, ReadIOP<'a, F>> {
182        self.iop.borrow_mut()
183    }
184
185    #[stability::unstable]
186    pub fn commit_circuit_info(&mut self, circuit_info: &ProtocolInfo) {
187        trace_if_enabled!("Verifying protocol={PROOF_SYSTEM_INFO} circuit {circuit_info}");
188        // At the start of the protocol, seed the Fiat-Shamir transcript with context information
189        // about the proof system and circuit.
190        let hashfn = self.suite.hashfn.as_ref();
191        self.iop()
192            .commit(&hashfn.hash_elem_slice(&PROOF_SYSTEM_INFO.encode()));
193        self.iop()
194            .commit(&hashfn.hash_elem_slice(&circuit_info.encode()));
195    }
196
197    /// Read in the next merkle group in the seal.  `reg_group_id` should be the group ID
198    /// as specified in the taps.
199    #[stability::unstable]
200    pub fn verify_group(&mut self, reg_group_id: usize) -> Result<&Digest, VerificationError> {
201        assert!(
202            self.merkle_verifiers[reg_group_id].is_none(),
203            "Reg group id {reg_group_id} ({}) may only occur once",
204            self.taps.group_name(reg_group_id)
205        );
206        let group_size = self.taps.group_size(reg_group_id);
207        let domain = INV_RATE * self.tot_cycles;
208        let hashfn = self.suite.hashfn.as_ref();
209
210        let merkle =
211            MerkleTreeVerifier::new(self.iop().deref_mut(), hashfn, domain, group_size, QUERIES);
212        self.merkle_verifiers[reg_group_id] = Some(merkle);
213        let root = self.merkle_verifiers[reg_group_id].as_ref().unwrap().root();
214        trace_if_enabled!(
215            "{} (group id={reg_group_id}) root: {root:?}",
216            self.taps.group_name(reg_group_id)
217        );
218        Ok(root)
219    }
220
221    /// Reads `elems` field elements of randomness from the IOP
222    #[stability::unstable]
223    pub fn read_rng(&mut self, elems: usize) -> Vec<F::Elem> {
224        let mix = (0..elems).map(|_| self.iop().random_elem()).collect();
225        trace_if_enabled!("Got mix values from IOP: {mix:?}");
226        mix
227    }
228
229    #[allow(clippy::too_many_arguments)]
230    // Compute the FRI verify taps sum.
231    fn fri_eval_taps(
232        &self,
233        combo_u: &[F::ExtElem],
234        check_row: &[F::Elem],
235        back_one: F::Elem,
236        x: F::Elem,
237        z: F::ExtElem,
238        rows: &[&[F::Elem]],
239        tap_mix_pows: &[F::ExtElem],
240        check_mix_pows: &[F::ExtElem],
241    ) -> F::ExtElem {
242        let mut tot = vec![F::ExtElem::ZERO; self.taps.combos_size() + 1];
243        let combo_count = self.taps.combos_size();
244        let x = F::ExtElem::from_subfield(&x);
245
246        for (reg, cur) in zip(self.taps.regs(), tap_mix_pows.iter()) {
247            tot[reg.combo_id()] += *cur * rows[reg.group()][reg.offset()];
248        }
249        for (i, cur) in zip(0..Self::CHECK_SIZE, check_mix_pows.iter()) {
250            tot[combo_count] += *cur * check_row[i];
251        }
252        let mut ret = F::ExtElem::ZERO;
253        for i in 0..combo_count {
254            let num = tot[i]
255                - self.poly_eval(
256                    &combo_u
257                        [self.taps.combo_begin[i] as usize..self.taps.combo_begin[i + 1] as usize],
258                    x,
259                );
260            let mut divisor = F::ExtElem::ONE;
261            for back in self.taps.get_combo(i).slice() {
262                divisor *= x - z * back_one.pow(*back as usize);
263            }
264            ret += num * divisor.inv();
265        }
266        let check_num = tot[combo_count] - combo_u[self.taps.tot_combo_backs];
267        let check_div = x - z.pow(INV_RATE);
268        ret += check_num * check_div.inv();
269        ret
270    }
271
272    /// Execute the IOP protocol to verify the validity polynomial
273    /// such that all the constraints are satisfied.  This is
274    /// currently only supported when called exactly once at the end
275    /// of the verification.
276    #[stability::unstable]
277    pub fn verify_validity(
278        &mut self,
279        validity_fn: impl Fn(&F::ExtElem, &[F::ExtElem]) -> F::ExtElem,
280    ) -> Result<(), VerificationError> {
281        // Ensure that we were given verifiers for all tap groups
282        for (reg_group_id, verifier) in self.merkle_verifiers.iter().enumerate() {
283            if !verifier.is_some() {
284                panic!(
285                    "Missing merkle verifier for reg group {reg_group_id} ({})",
286                    self.taps.group_name(reg_group_id)
287                );
288            }
289        }
290
291        // Get a pseudorandom value with which to mix the constraint polynomials.
292        // See DEEP-ALI protocol from DEEP-FRI paper for details on constraint mixing.
293        let poly_mix = self.iop().random_ext_elem();
294        trace_if_enabled!("Poly mix: {poly_mix:?}");
295
296        let hashfn = self.suite.hashfn.as_ref();
297        let domain = INV_RATE * self.tot_cycles;
298        let check_merkle = MerkleTreeVerifier::new(
299            self.iop().deref_mut(),
300            hashfn,
301            domain,
302            Self::CHECK_SIZE,
303            QUERIES,
304        );
305        trace_if_enabled!("Check merkle root: {}", check_merkle.root());
306
307        // Get a pseudorandom DEEP query point
308        // See DEEP-ALI protocol from DEEP-FRI paper for details on DEEP query.
309        cfg_if::cfg_if! {
310            if #[cfg(feature = "circuit_debug")] {
311                let z_slice = self.iop().read_field_elem_slice(F::ExtElem::EXT_SIZE);
312                let z = F::ExtElem::from_subelems(z_slice.iter().cloned());
313            } else {
314                let z = self.iop().random_ext_elem();
315            }
316        }
317
318        trace_if_enabled!("Z = {z:?}");
319        let back_one = F::Elem::ROU_REV[self.po2];
320
321        // Read the U coeffs (the interpolations of the taps) + commit their hash.
322        let num_taps = self.taps.tap_size();
323        let coeff_u = self
324            .iop()
325            .read_field_elem_slice(num_taps + Self::CHECK_SIZE);
326        let hash_u = hashfn.hash_ext_elem_slice(coeff_u);
327        self.iop().commit(&hash_u);
328
329        // Now, convert U polynomials from coefficient form to evaluation form
330        let mut cur_pos = 0;
331        let mut eval_u = Vec::with_capacity(num_taps);
332        for reg in self.taps.regs() {
333            for i in 0..reg.size() {
334                let x = z * back_one.pow(reg.back(i));
335                let fx = self.poly_eval(&coeff_u[cur_pos..(cur_pos + reg.size())], x);
336                eval_u.push(fx);
337            }
338            cur_pos += reg.size();
339        }
340        assert_eq!(eval_u.len(), num_taps, "Miscalculated capacity for eval_us");
341
342        // Compute the core constraint polynomial.
343        // I.e. the set of all constraints mixed by poly_mix
344        #[cfg(not(target_os = "zkvm"))]
345        tracing::debug!("> compute_polynomial");
346
347        let result = validity_fn(&poly_mix, &eval_u);
348        trace_if_enabled!("Computed polynomial: {result:?}");
349
350        // Now generate the check polynomial
351        // TODO: This currently treats the extension degree as hardcoded at 4, with
352        // the structure of the code and the value of `remap` (and how it is
353        // accessed) only working in the extension degree = 4 case.
354        // However, for generic fields the extension degree may be different
355        // TODO: Therefore just using the to/from baby bear shims for now
356        let mut check = F::ExtElem::default();
357        let remap = [0, 2, 1, 3];
358        let fp0 = F::Elem::ZERO;
359        let fp1 = F::Elem::ONE;
360        for (i, rmi) in remap.iter().enumerate() {
361            check += coeff_u[num_taps + rmi]
362                * z.pow(i)
363                * F::ExtElem::from_subelems([fp1, fp0, fp0, fp0]);
364            check += coeff_u[num_taps + rmi + 4]
365                * z.pow(i)
366                * F::ExtElem::from_subelems([fp0, fp1, fp0, fp0]);
367            check += coeff_u[num_taps + rmi + 8]
368                * z.pow(i)
369                * F::ExtElem::from_subelems([fp0, fp0, fp1, fp0]);
370            check += coeff_u[num_taps + rmi + 12]
371                * z.pow(i)
372                * F::ExtElem::from_subelems([fp0, fp0, fp0, fp1]);
373        }
374        let three = F::Elem::from_u64(3);
375        check *= (F::ExtElem::from_subfield(&three) * z).pow(self.tot_cycles) - F::ExtElem::ONE;
376        trace_if_enabled!("Check = {check:?}");
377        if check != result {
378            tracing::debug!("check != result");
379            return Err(VerificationError::InvalidProof);
380        }
381
382        // Set the mix value, pseudorandom value used for FRI batching
383        let mix = self.iop().random_ext_elem();
384        trace_if_enabled!("FRI mix = {mix:?}");
385
386        // Fill in
387
388        // Make the mixed U polynomials.
389        // combo_u has one element for each column with the same set of taps.
390        // These columns share a denominator in the DEEP-ALI equation.
391        // We group these terms together to reduce the number of inverses we
392        // need to compute.
393        let mut combo_u: Vec<F::ExtElem> = vec![F::ExtElem::ZERO; self.taps.tot_combo_backs + 1];
394        let mut cur_mix = F::ExtElem::ONE;
395        cur_pos = 0;
396        let mut tap_mix_pows = Vec::with_capacity(self.taps.reg_count());
397        for reg in self.taps.regs() {
398            for i in 0..reg.size() {
399                combo_u[self.taps.combo_begin[reg.combo_id()] as usize + i] +=
400                    cur_mix * coeff_u[cur_pos + i];
401            }
402            tap_mix_pows.push(cur_mix);
403            cur_mix *= mix;
404            cur_pos += reg.size();
405        }
406        assert_eq!(
407            tap_mix_pows.len(),
408            self.taps.reg_count(),
409            "Miscalculated capacity for tap_mix_pows"
410        );
411        trace_if_enabled!("cur_mix: {cur_mix:?}, cur_pos: {cur_pos}");
412        // Handle check group
413        let mut check_mix_pows = Vec::with_capacity(Self::CHECK_SIZE);
414        for _ in 0..Self::CHECK_SIZE {
415            combo_u[self.taps.tot_combo_backs] += cur_mix * coeff_u[cur_pos];
416            cur_pos += 1;
417            check_mix_pows.push(cur_mix);
418            cur_mix *= mix;
419        }
420        assert_eq!(
421            check_mix_pows.len(),
422            Self::CHECK_SIZE,
423            "Miscalculated capacity for check_mix_pows"
424        );
425        let gen = <F::Elem as RootsOfUnity>::ROU_FWD[log2_ceil(domain)];
426        let hashfn = self.suite.hashfn.as_ref();
427        self.fri_verify(|idx| {
428            let x = gen.pow(idx);
429            let rows= self
430                .merkle_verifiers
431                .iter()
432                .map(|merkle: &Option<MerkleTreeVerifier>| -> Result<&'a [F::Elem], VerificationError> {
433                    merkle.as_ref()
434                        .unwrap()
435                        .verify(self.iop().deref_mut(), hashfn, idx)
436                })
437                .collect::<Result<Vec<_>,_>>()?;
438            let check_row = check_merkle.verify(self.iop().deref_mut(),hashfn, idx)?;
439            let ret = self.fri_eval_taps(&combo_u, check_row, back_one, x, z, &rows, &tap_mix_pows, &check_mix_pows);
440            Ok(ret)
441        })?;
442        Ok(())
443    }
444
445    /// Reads a slice of `size` field elements from the IOP along with
446    /// the po2 of the number of cycles the circuit ran for, and
447    /// commits to them.  This is typically used at the beginning of
448    /// the seal to encode the globals of the circuit.
449    #[stability::unstable]
450    pub fn read_slice_with_po2(&mut self, size: usize) -> (&'a [F::Elem], usize) {
451        let slice = self.iop().read_field_elem_slice(size + 1);
452        self.iop().commit(&self.suite.hashfn.hash_elem_slice(slice));
453
454        // Extract the out buffer and po2 from slice while checking sizes.
455        let (out, &[po2_elem]) = slice.split_at(size) else {
456            unreachable!()
457        };
458        let (&[po2], &[]) = po2_elem.to_u32_words().split_at(1) else {
459            panic!("po2 elem is larger than u32");
460        };
461        self.po2 = po2 as usize;
462        assert!(self.po2 <= MAX_CYCLES_PO2);
463        self.tot_cycles = 1usize.checked_shl(po2).unwrap();
464        (out, self.po2)
465    }
466
467    /// Evaluate a polynomial whose coefficients are in the extension field at a
468    /// point.
469    fn poly_eval(&self, coeffs: &[F::ExtElem], x: F::ExtElem) -> F::ExtElem {
470        let mut mul_x = F::ExtElem::ONE;
471        let mut tot = F::ExtElem::ZERO;
472        for coeff in coeffs {
473            tot += *coeff * mul_x;
474            mul_x *= x;
475        }
476        tot
477    }
478}
479
480/// Verify a seal is valid for the given circuit, and code checking function.
481///
482/// This version of `verify` has a fixed IOP protocol that's used by
483/// multiple circuits.
484// Circuits that don't share this protocol may use [Verifier] directly once it's stabilized.
485pub fn verify<F, C, CheckCode>(
486    circuit: &C,
487    suite: &HashSuite<F>,
488    seal: &[u32],
489    check_code: CheckCode,
490) -> Result<(), VerificationError>
491where
492    F: Field,
493    C: CircuitCoreDef<F>,
494    CheckCode: Fn(u32, &Digest) -> Result<(), VerificationError>,
495{
496    if seal.is_empty() {
497        return Err(VerificationError::ReceiptFormatError);
498    }
499
500    let mut verifier = Verifier::<F>::new(circuit.get_taps(), suite, seal);
501    verifier.commit_circuit_info(&C::CIRCUIT_INFO);
502
503    // Read the globals (i.e. outputs) from the IOP, and mix them into the Fiat-Shamir state.
504    //
505    // NOTE: The globals are the only values known to the verifier, and constitute the public
506    // statement of the prover. In many scenarios, they are the first values sent to the
507    // verifier by the prover, and therefore should be committed at the start of verification.
508    let (out, po2) = verifier.read_slice_with_po2(C::OUTPUT_SIZE);
509
510    // Get merkle root for the code merkle tree.
511    // The code merkle tree contains the control instructions for the zkVM.
512    let code_root = verifier.verify_group(REGISTER_GROUP_CODE)?;
513
514    // Invoke the user-supplied verification function to ensure that
515    // the code root of the merkle tree is as expected.
516    check_code(po2 as u32, code_root)?;
517
518    // Get merkle root for the data merkle tree.
519    // The data merkle tree contains the execution trace of the program being run,
520    // including memory accesses as well as the permutation of those memory
521    // accesses sorted by location used by PLONK.
522    verifier.verify_group(REGISTER_GROUP_DATA)?;
523
524    // Fill in accum mix
525    let mix = verifier.read_rng(C::MIX_SIZE);
526
527    // Get merkle root for the accum merkle tree.
528    // The accum merkle tree contains the accumulations for two permutation check
529    // arguments: Each permutation check consists of a pre-permutation
530    // accumulation and a post-permutation accumulation.
531    // The first permutation check uses memory-based values (see PLONK paper for
532    // details). This permutation is used to re-order memory accesses for
533    // quicker verification. The second permutation check uses bytes-based
534    // values (see PLOOKUP paper for details). This permutation is used to
535    // implement a look-up table.
536    verifier.verify_group(REGISTER_GROUP_ACCUM)?;
537
538    // Verify the evaluation of the validity polynomial to make sure
539    // the constraints were not violated.
540    verifier
541        .verify_validity(|poly_mix, eval_u| circuit.poly_ext(poly_mix, eval_u, &[out, &mix]).tot)?;
542
543    // There should be nothing else in the IOP, so verify that's the case.
544    verifier.iop().verify_complete();
545    Ok(())
546}
risc0_zkp/verify/mod.rs

risc0_zkp/verify/
mod.rs
