miden_core/
proof.rs

1use alloc::{
2    string::{String, ToString},
3    vec::Vec,
4};
5
6#[cfg(feature = "arbitrary")]
7use proptest::prelude::*;
8#[cfg(feature = "serde")]
9use serde::{Deserialize, Serialize};
10
11use crate::{
12    crypto::hash::{Blake3_256, Poseidon2, Rpo256, Rpx256},
13    deferred::{DeferredRoot, DeferredStateWire},
14    serde::{
15        BudgetedReader, ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable,
16        SliceReader,
17    },
18};
19
20// HASH FUNCTION
21// ================================================================================================
22
23/// A hash function used during STARK proof generation.
24#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
25#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
26#[cfg_attr(
27    all(feature = "arbitrary", test),
28    miden_test_serde_macros::serde_test(binary_serde(true))
29)]
30#[repr(u8)]
31pub enum HashFunction {
32    /// BLAKE3 hash function with 256-bit output.
33    Blake3_256 = 0x01,
34    /// RPO hash function with 256-bit output.
35    Rpo256 = 0x02,
36    /// RPX hash function with 256-bit output.
37    Rpx256 = 0x03,
38    /// Poseidon2 hash function with 256-bit output.
39    Poseidon2 = 0x04,
40    /// Keccak hash function with 256-bit output.
41    Keccak = 0x05,
42}
43
44impl HashFunction {
45    /// Returns the collision resistance level (in bits) of this hash function.
46    pub const fn collision_resistance(&self) -> u32 {
47        match self {
48            HashFunction::Blake3_256 => Blake3_256::COLLISION_RESISTANCE,
49            HashFunction::Rpo256 => Rpo256::COLLISION_RESISTANCE,
50            HashFunction::Rpx256 => Rpx256::COLLISION_RESISTANCE,
51            HashFunction::Poseidon2 => Poseidon2::COLLISION_RESISTANCE,
52            HashFunction::Keccak => 128,
53        }
54    }
55}
56
57/// Error type for invalid hash function strings.
58#[derive(Debug, thiserror::Error)]
59#[error(
60    "invalid hash function '{hash_function}'. Valid options are: blake3-256, rpo, rpx, poseidon2, keccak"
61)]
62pub struct InvalidHashFunctionError {
63    pub hash_function: String,
64}
65
66impl TryFrom<u8> for HashFunction {
67    type Error = DeserializationError;
68
69    fn try_from(repr: u8) -> Result<Self, Self::Error> {
70        match repr {
71            0x01 => Ok(Self::Blake3_256),
72            0x02 => Ok(Self::Rpo256),
73            0x03 => Ok(Self::Rpx256),
74            0x04 => Ok(Self::Poseidon2),
75            0x05 => Ok(Self::Keccak),
76            _ => Err(DeserializationError::InvalidValue(format!(
77                "the hash function representation {repr} is not valid!"
78            ))),
79        }
80    }
81}
82
83impl TryFrom<&str> for HashFunction {
84    type Error = InvalidHashFunctionError;
85
86    fn try_from(hash_fn_str: &str) -> Result<Self, Self::Error> {
87        match hash_fn_str {
88            "blake3-256" => Ok(Self::Blake3_256),
89            "rpo" => Ok(Self::Rpo256),
90            "rpx" => Ok(Self::Rpx256),
91            "poseidon2" => Ok(Self::Poseidon2),
92            "keccak" => Ok(Self::Keccak),
93            _ => Err(InvalidHashFunctionError { hash_function: hash_fn_str.to_string() }),
94        }
95    }
96}
97
98#[cfg(feature = "arbitrary")]
99impl Arbitrary for HashFunction {
100    type Parameters = ();
101    type Strategy = BoxedStrategy<Self>;
102
103    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
104        any::<u8>()
105            .prop_map(|tag| match tag % 5 {
106                0 => Self::Blake3_256,
107                1 => Self::Rpo256,
108                2 => Self::Rpx256,
109                3 => Self::Poseidon2,
110                _ => Self::Keccak,
111            })
112            .boxed()
113    }
114}
115
116impl Serializable for HashFunction {
117    fn write_into<W: ByteWriter>(&self, target: &mut W) {
118        target.write_u8(*self as u8);
119    }
120}
121
122impl Deserializable for HashFunction {
123    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
124        source.read_u8()?.try_into()
125    }
126}
127
128// EXECUTION PROOF
129// ================================================================================================
130
131/// A proof of correct execution of Miden VM.
132///
133/// The proof contains the Miden VM STARK proof and deferred proof material for the execution's
134/// precompile claims. Verifying the deferred proof returns the root used to check the VM STARK
135/// public inputs.
136///
137/// `Empty` and STARK-backed deferred proofs are final form; wire-backed proofs are partial form.
138#[derive(Debug, Clone, PartialEq, Eq)]
139#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
140pub struct ExecutionProof {
141    miden: StarkProof,
142    deferred: DeferredProof,
143}
144
145impl ExecutionProof {
146    // CONSTRUCTOR
147    // --------------------------------------------------------------------------------------------
148
149    /// Creates a new instance of [ExecutionProof] from a Miden VM STARK proof envelope and deferred
150    /// proof material.
151    pub const fn new(miden: StarkProof, deferred: DeferredProof) -> Self {
152        Self { miden, deferred }
153    }
154
155    /// Creates a new instance of [ExecutionProof] from serialized Miden VM STARK proof bytes, hash
156    /// function, and deferred proof material.
157    pub fn from_parts(
158        miden_proof_bytes: Vec<u8>,
159        hash_fn: HashFunction,
160        deferred: impl Into<DeferredProof>,
161    ) -> Self {
162        Self::new(StarkProof::new(miden_proof_bytes, hash_fn), deferred.into())
163    }
164
165    // PUBLIC ACCESSORS
166    // --------------------------------------------------------------------------------------------
167
168    /// Returns the Miden VM STARK proof envelope.
169    pub const fn miden_proof(&self) -> &StarkProof {
170        &self.miden
171    }
172
173    /// Returns the deferred proof material associated with the Miden VM proof.
174    pub const fn deferred_proof(&self) -> &DeferredProof {
175        &self.deferred
176    }
177
178    /// Returns `true` if this proof is in final form.
179    ///
180    /// This is a shape check only: it means the deferred proof is empty or STARK-backed, not that
181    /// either the VM STARK proof or the deferred proof has been verified.
182    pub const fn is_final(&self) -> bool {
183        self.deferred.is_final()
184    }
185
186    /// Returns conjectured security level of this proof in bits.
187    ///
188    /// TODO: this is a placeholder returning a hardcoded 96 (honest only for the current
189    /// parameter preset). The conjectured estimator now exists as
190    /// `miden_air::config::conjectured_security_level`, but this method cannot call it —
191    /// `miden-air` depends on `miden-core`, not the reverse. The intended fix is to stop having
192    /// the proof self-report a security level and instead grade it in the verifier (which does
193    /// depend on `miden-air`).
194    pub fn security_level(&self) -> u32 {
195        96
196    }
197
198    // SERIALIZATION / DESERIALIZATION
199    // --------------------------------------------------------------------------------------------
200
201    /// Serializes this proof into a vector of bytes.
202    pub fn to_bytes(&self) -> Vec<u8> {
203        let mut bytes = Vec::new();
204        self.write_into(&mut bytes);
205        bytes
206    }
207
208    /// Reads the source bytes, parsing a new proof instance.
209    ///
210    /// The serialization layout matches the [`Serializable`] implementation of [`ExecutionProof`].
211    pub fn from_bytes(source: &[u8]) -> Result<Self, DeserializationError> {
212        <Self as Deserializable>::read_from_bytes(source)
213    }
214}
215
216impl Serializable for ExecutionProof {
217    fn write_into<W: ByteWriter>(&self, target: &mut W) {
218        self.miden.write_into(target);
219        self.deferred.write_into(target);
220    }
221}
222
223impl Deserializable for ExecutionProof {
224    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
225        let miden = StarkProof::read_from(source)?;
226        let deferred = DeferredProof::read_from(source)?;
227
228        Ok(ExecutionProof::new(miden, deferred))
229    }
230
231    fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError> {
232        let mut reader = BudgetedReader::new(SliceReader::new(bytes), bytes.len());
233        Self::read_from(&mut reader)
234    }
235}
236
237#[cfg(any(test, feature = "testing"))]
238impl ExecutionProof {
239    /// Creates a dummy `ExecutionProof` for testing purposes only.
240    ///
241    /// A proof created in this way will not be verifiable against any verifier.
242    pub fn new_dummy() -> Self {
243        ExecutionProof::new(
244            StarkProof::new(Vec::new(), HashFunction::Blake3_256),
245            DeferredProof::Empty,
246        )
247    }
248}
249
250// DEFERRED PROOF
251// ================================================================================================
252
253/// Proof material for the precompile claims associated with an execution proof.
254///
255/// Verification returns the deferred root used to check the VM STARK proof. `Wire` is the partial
256/// form; `Empty` and `Stark` are final forms.
257///
258/// Variants are public so callers can construct and inspect deferred proof material directly.
259#[derive(Debug, Clone, PartialEq, Eq)]
260#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
261pub enum DeferredProof {
262    /// No precompile claims were produced. Verifiers resolve this to
263    /// [`crate::deferred::TRUE_DIGEST`].
264    Empty,
265    /// Canonical deferred-state wire for a partial proof.
266    Wire(DeferredStateWire),
267    /// A precompile VM STARK proof for this execution's exact deferred root.
268    ///
269    /// After `proof` verifies against `public_root`, that root is used to verify the VM STARK
270    /// proof.
271    Stark {
272        proof: StarkProof,
273        public_root: DeferredRoot,
274    },
275}
276
277impl DeferredProof {
278    const EMPTY_TAG: u8 = 0;
279    pub(crate) const WIRE_TAG: u8 = 1;
280    const STARK_TAG: u8 = 2;
281
282    /// Creates an empty deferred proof.
283    pub const fn empty() -> Self {
284        Self::Empty
285    }
286
287    /// Creates a deferred proof backed by a wire opening.
288    pub const fn wire(wire: DeferredStateWire) -> Self {
289        Self::Wire(wire)
290    }
291
292    /// Creates a deferred proof backed by a precompile VM STARK proof.
293    pub const fn stark(proof: StarkProof, public_root: DeferredRoot) -> Self {
294        Self::Stark { proof, public_root }
295    }
296
297    /// Returns `true` if this deferred proof is [`DeferredProof::Empty`].
298    pub const fn is_empty(&self) -> bool {
299        matches!(self, Self::Empty)
300    }
301
302    /// Returns `true` if this deferred proof is in final form.
303    ///
304    /// This is a shape check only: it accepts empty and STARK-backed proofs and rejects wire-backed
305    /// partial proofs. It does not verify the contained proof material.
306    pub const fn is_final(&self) -> bool {
307        matches!(self, Self::Empty | Self::Stark { .. })
308    }
309
310    /// Returns the wire opening if this deferred proof is [`DeferredProof::Wire`].
311    pub const fn as_wire(&self) -> Option<&DeferredStateWire> {
312        match self {
313            Self::Wire(wire) => Some(wire),
314            _ => None,
315        }
316    }
317
318    /// Returns the nested proof and public root if this proof is [`DeferredProof::Stark`].
319    pub const fn as_stark(&self) -> Option<(&StarkProof, DeferredRoot)> {
320        match self {
321            Self::Stark { proof, public_root } => Some((proof, *public_root)),
322            _ => None,
323        }
324    }
325}
326
327impl From<DeferredStateWire> for DeferredProof {
328    fn from(wire: DeferredStateWire) -> Self {
329        Self::wire(wire)
330    }
331}
332
333impl Serializable for DeferredProof {
334    fn write_into<W: ByteWriter>(&self, target: &mut W) {
335        match self {
336            Self::Empty => target.write_u8(Self::EMPTY_TAG),
337            Self::Wire(wire) => {
338                target.write_u8(Self::WIRE_TAG);
339                wire.write_into(target);
340            },
341            Self::Stark { proof, public_root } => {
342                target.write_u8(Self::STARK_TAG);
343                proof.write_into(target);
344                public_root.write_into(target);
345            },
346        }
347    }
348}
349
350impl Deserializable for DeferredProof {
351    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
352        let tag = source.read_u8()?;
353        match tag {
354            Self::EMPTY_TAG => Ok(Self::Empty),
355            Self::WIRE_TAG => Ok(Self::Wire(DeferredStateWire::read_from(source)?)),
356            Self::STARK_TAG => {
357                let proof = StarkProof::read_from(source)?;
358                let public_root = <DeferredRoot as Deserializable>::read_from(source)?;
359                Ok(Self::Stark { proof, public_root })
360            },
361            other => Err(DeserializationError::InvalidValue(format!(
362                "invalid deferred proof discriminant: {other}"
363            ))),
364        }
365    }
366
367    fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError> {
368        let mut reader = BudgetedReader::new(SliceReader::new(bytes), bytes.len());
369        Self::read_from(&mut reader)
370    }
371
372    fn min_serialized_size() -> usize {
373        1
374    }
375}
376
377// STARK PROOF
378// ================================================================================================
379
380/// A serialized STARK proof and the hash function used during proof generation.
381#[derive(Debug, Clone, PartialEq, Eq)]
382#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
383pub struct StarkProof {
384    bytes: Vec<u8>,
385    hash_fn: HashFunction,
386}
387
388impl StarkProof {
389    /// Creates a new instance of [StarkProof] from proof bytes and hash function.
390    pub const fn new(bytes: Vec<u8>, hash_fn: HashFunction) -> Self {
391        Self { bytes, hash_fn }
392    }
393
394    /// Returns the serialized STARK proof bytes.
395    pub fn bytes(&self) -> &[u8] {
396        &self.bytes
397    }
398
399    /// Returns the hash function used during proof generation process.
400    pub const fn hash_fn(&self) -> HashFunction {
401        self.hash_fn
402    }
403
404    /// Returns the serialized STARK proof bytes and hash function.
405    pub fn into_parts(self) -> (Vec<u8>, HashFunction) {
406        (self.bytes, self.hash_fn)
407    }
408}
409
410impl Serializable for StarkProof {
411    fn write_into<W: ByteWriter>(&self, target: &mut W) {
412        self.bytes.write_into(target);
413        self.hash_fn.write_into(target);
414    }
415}
416
417impl Deserializable for StarkProof {
418    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
419        let bytes = Vec::<u8>::read_from(source)?;
420        let hash_fn = HashFunction::read_from(source)?;
421        Ok(Self::new(bytes, hash_fn))
422    }
423
424    fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError> {
425        let mut reader = BudgetedReader::new(SliceReader::new(bytes), bytes.len());
426        Self::read_from(&mut reader)
427    }
428}
429
430#[cfg(test)]
431mod tests {
432    use super::*;
433    use crate::{
434        Felt,
435        deferred::{DeferredRoot, TRUE_INDEX, Tag, WireEntry},
436        serde::{BudgetedReader, ByteWriter, DeserializationError, SliceReader},
437    };
438
439    #[test]
440    fn execution_proof_from_bytes_rejects_unbounded_proof_len() {
441        let mut bytes = Vec::new();
442        bytes.write_usize(usize::MAX);
443
444        let err = ExecutionProof::from_bytes(&bytes).unwrap_err();
445        let DeserializationError::InvalidValue(message) = err else {
446            panic!("expected InvalidValue error");
447        };
448        assert!(message.contains("requested"));
449        assert!(message.contains("reader can provide at most"));
450    }
451
452    #[test]
453    fn execution_proof_read_from_bytes_rejects_unbounded_proof_len() {
454        let mut bytes = Vec::new();
455        bytes.write_usize(usize::MAX);
456
457        let err = ExecutionProof::read_from_bytes(&bytes).unwrap_err();
458        let DeserializationError::InvalidValue(message) = err else {
459            panic!("expected InvalidValue error");
460        };
461        assert!(message.contains("requested"));
462        assert!(message.contains("reader can provide at most"));
463    }
464
465    #[test]
466    fn execution_proof_round_trips_empty_deferred_proof() {
467        let proof = ExecutionProof::new(
468            StarkProof::new(alloc::vec![1, 2, 3], HashFunction::Blake3_256),
469            DeferredProof::empty(),
470        );
471
472        let decoded = ExecutionProof::from_bytes(&proof.to_bytes()).unwrap();
473
474        assert_eq!(decoded, proof);
475        assert_eq!(decoded.miden_proof().bytes(), &[1, 2, 3]);
476        assert_eq!(decoded.miden_proof().hash_fn(), HashFunction::Blake3_256);
477        assert!(decoded.deferred_proof().is_empty());
478        assert!(decoded.is_final());
479    }
480
481    #[test]
482    fn execution_proof_round_trips_empty_deferred_wire() {
483        let proof = ExecutionProof::from_parts(
484            alloc::vec![1, 2, 3],
485            HashFunction::Blake3_256,
486            DeferredProof::wire(DeferredStateWire::default()),
487        );
488
489        let decoded = ExecutionProof::from_bytes(&proof.to_bytes()).unwrap();
490
491        assert_eq!(decoded, proof);
492        assert_eq!(decoded.deferred_proof().as_wire(), Some(&DeferredStateWire::default()));
493        assert!(!decoded.is_final());
494    }
495
496    #[test]
497    fn execution_proof_round_trips_non_empty_deferred_wire() {
498        let tag = Tag::from_word([
499            Felt::new_unchecked(7),
500            Felt::new_unchecked(1),
501            Felt::new_unchecked(2),
502            Felt::new_unchecked(3),
503        ]);
504        let deferred_wire = DeferredStateWire {
505            entries: alloc::vec![
506                WireEntry::Data {
507                    tag,
508                    chunks: alloc::vec![[Felt::new_unchecked(1); 8]],
509                },
510                WireEntry::Join { tag, lhs: TRUE_INDEX, rhs: 1 },
511            ],
512        };
513        let proof = ExecutionProof::from_parts(
514            alloc::vec![1, 2, 3],
515            HashFunction::Blake3_256,
516            deferred_wire,
517        );
518
519        let decoded = ExecutionProof::from_bytes(&proof.to_bytes()).unwrap();
520
521        assert_eq!(decoded, proof);
522        assert!(!decoded.is_final());
523    }
524
525    #[test]
526    fn execution_proof_round_trips_stark_deferred_proof() {
527        let public_root: DeferredRoot = [
528            Felt::new_unchecked(9),
529            Felt::new_unchecked(8),
530            Felt::new_unchecked(7),
531            Felt::new_unchecked(6),
532        ]
533        .into();
534        let deferred_stark_proof = StarkProof::new(alloc::vec![4, 5, 6], HashFunction::Poseidon2);
535        let deferred = DeferredProof::stark(deferred_stark_proof.clone(), public_root);
536        let proof = ExecutionProof::new(
537            StarkProof::new(alloc::vec![1, 2, 3], HashFunction::Blake3_256),
538            deferred,
539        );
540
541        let decoded = ExecutionProof::from_bytes(&proof.to_bytes()).unwrap();
542
543        assert_eq!(decoded, proof);
544        assert_eq!(decoded.deferred_proof().as_stark(), Some((&deferred_stark_proof, public_root)));
545        assert!(decoded.is_final());
546    }
547
548    #[test]
549    fn execution_proof_rejects_invalid_deferred_variant() {
550        let mut bytes = Vec::new();
551        bytes.write_usize(0);
552        bytes.write_u8(HashFunction::Blake3_256 as u8);
553        bytes.write_u8(255);
554
555        let err = ExecutionProof::from_bytes(&bytes).unwrap_err();
556        let DeserializationError::InvalidValue(message) = err else {
557            panic!("expected InvalidValue error");
558        };
559        assert!(message.contains("invalid deferred proof discriminant: 255"));
560    }
561
562    #[test]
563    fn execution_proof_rejects_over_budget_proof_len() {
564        let mut bytes = Vec::new();
565        bytes.write_usize(5);
566
567        let budget = bytes.len() + 4;
568        let mut reader = BudgetedReader::new(SliceReader::new(&bytes), budget);
569        let err = ExecutionProof::read_from(&mut reader).unwrap_err();
570        let DeserializationError::InvalidValue(message) = err else {
571            panic!("expected InvalidValue error");
572        };
573        assert!(message.contains("requested 5 elements"));
574    }
575
576    #[test]
577    fn execution_proof_rejects_over_budget_deferred_wire_entries_len() {
578        let mut bytes = Vec::new();
579        bytes.write_usize(0);
580        bytes.write_u8(HashFunction::Blake3_256 as u8);
581        bytes.write_u8(DeferredProof::WIRE_TAG);
582        bytes.write_usize(2);
583
584        let budget = bytes.len() + 1;
585        let mut reader = BudgetedReader::new(SliceReader::new(&bytes), budget);
586        let err = ExecutionProof::read_from(&mut reader).unwrap_err();
587        let DeserializationError::InvalidValue(message) = err else {
588            panic!("expected InvalidValue error");
589        };
590        assert!(message.contains("requested 2 elements"));
591    }
592}
miden_core/proof.rs

miden_core/
proof.rs
