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    precompile::PrecompileRequest,
14    serde::{
15        BudgetedReader, ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable,
16        SliceReader,
17    },
18};
19
20// EXECUTION PROOF
21// ================================================================================================
22
23/// A proof of correct execution of Miden VM.
24///
25/// The proof contains the STARK proof, the hash function used during proof generation, and a set
26/// of precompile requests deferred during proof generation. However, the proof does not contain
27/// public inputs needed to verify the proof.
28#[derive(Debug, Clone, PartialEq, Eq)]
29#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
30pub struct ExecutionProof {
31    pub proof: Vec<u8>,
32    pub hash_fn: HashFunction,
33    pub pc_requests: Vec<PrecompileRequest>,
34}
35
36impl ExecutionProof {
37    // CONSTRUCTOR
38    // --------------------------------------------------------------------------------------------
39
40    /// Creates a new instance of [ExecutionProof] from the specified STARK proof, hash function,
41    /// and list of all deferred [PrecompileRequest]s.
42    pub const fn new(
43        proof: Vec<u8>,
44        hash_fn: HashFunction,
45        pc_requests: Vec<PrecompileRequest>,
46    ) -> Self {
47        Self { proof, hash_fn, pc_requests }
48    }
49
50    // PUBLIC ACCESSORS
51    // --------------------------------------------------------------------------------------------
52
53    /// Returns the underlying STARK proof.
54    pub fn stark_proof(&self) -> &[u8] {
55        &self.proof
56    }
57
58    /// Returns the hash function used during proof generation process.
59    pub const fn hash_fn(&self) -> HashFunction {
60        self.hash_fn
61    }
62
63    /// Returns the list of precompile requests made during the execution of the program.
64    pub fn precompile_requests(&self) -> &[PrecompileRequest] {
65        &self.pc_requests
66    }
67
68    /// Returns conjectured security level of this proof in bits.
69    ///
70    /// Currently returns a hardcoded 96 bits. Once the security estimator is implemented
71    /// in Plonky3, this should calculate the actual conjectured security level based on:
72    /// - Proof parameters (FRI folding factor, number of queries, etc.)
73    /// - Hash function collision resistance
74    /// - Field size and extension degree
75    pub fn security_level(&self) -> u32 {
76        96
77    }
78
79    // SERIALIZATION / DESERIALIZATION
80    // --------------------------------------------------------------------------------------------
81
82    /// Serializes this proof into a vector of bytes.
83    pub fn to_bytes(&self) -> Vec<u8> {
84        let mut bytes = Vec::new();
85        self.write_into(&mut bytes);
86        bytes
87    }
88
89    /// Reads the source bytes, parsing a new proof instance.
90    ///
91    /// The serialization layout matches the [`Serializable`] implementation of [`ExecutionProof`].
92    pub fn from_bytes(source: &[u8]) -> Result<Self, DeserializationError> {
93        <Self as Deserializable>::read_from_bytes(source)
94    }
95
96    // DESTRUCTOR
97    // --------------------------------------------------------------------------------------------
98
99    /// Returns the hash function, proof bytes, and precompile requests.
100    pub fn into_parts(self) -> (HashFunction, Vec<u8>, Vec<PrecompileRequest>) {
101        (self.hash_fn, self.proof, self.pc_requests)
102    }
103}
104
105// HASH FUNCTION
106// ================================================================================================
107
108/// A hash function used during STARK proof generation.
109#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
110#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
111#[cfg_attr(
112    all(feature = "arbitrary", test),
113    miden_test_serde_macros::serde_test(binary_serde(true))
114)]
115#[repr(u8)]
116pub enum HashFunction {
117    /// BLAKE3 hash function with 256-bit output.
118    Blake3_256 = 0x01,
119    /// RPO hash function with 256-bit output.
120    Rpo256 = 0x02,
121    /// RPX hash function with 256-bit output.
122    Rpx256 = 0x03,
123    /// Poseidon2 hash function with 256-bit output.
124    Poseidon2 = 0x04,
125    /// Keccak hash function with 256-bit output.
126    Keccak = 0x05,
127}
128
129impl HashFunction {
130    /// Returns the collision resistance level (in bits) of this hash function.
131    pub const fn collision_resistance(&self) -> u32 {
132        match self {
133            HashFunction::Blake3_256 => Blake3_256::COLLISION_RESISTANCE,
134            HashFunction::Rpo256 => Rpo256::COLLISION_RESISTANCE,
135            HashFunction::Rpx256 => Rpx256::COLLISION_RESISTANCE,
136            HashFunction::Poseidon2 => Poseidon2::COLLISION_RESISTANCE,
137            HashFunction::Keccak => 128,
138        }
139    }
140}
141
142impl TryFrom<u8> for HashFunction {
143    type Error = DeserializationError;
144
145    fn try_from(repr: u8) -> Result<Self, Self::Error> {
146        match repr {
147            0x01 => Ok(Self::Blake3_256),
148            0x02 => Ok(Self::Rpo256),
149            0x03 => Ok(Self::Rpx256),
150            0x04 => Ok(Self::Poseidon2),
151            0x05 => Ok(Self::Keccak),
152            _ => Err(DeserializationError::InvalidValue(format!(
153                "the hash function representation {repr} is not valid!"
154            ))),
155        }
156    }
157}
158
159impl TryFrom<&str> for HashFunction {
160    type Error = InvalidHashFunctionError;
161
162    fn try_from(hash_fn_str: &str) -> Result<Self, Self::Error> {
163        match hash_fn_str {
164            "blake3-256" => Ok(Self::Blake3_256),
165            "rpo" => Ok(Self::Rpo256),
166            "rpx" => Ok(Self::Rpx256),
167            "poseidon2" => Ok(Self::Poseidon2),
168            "keccak" => Ok(Self::Keccak),
169            _ => Err(InvalidHashFunctionError { hash_function: hash_fn_str.to_string() }),
170        }
171    }
172}
173
174#[cfg(feature = "arbitrary")]
175impl Arbitrary for HashFunction {
176    type Parameters = ();
177    type Strategy = BoxedStrategy<Self>;
178
179    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
180        any::<u8>()
181            .prop_map(|tag| match tag % 5 {
182                0 => Self::Blake3_256,
183                1 => Self::Rpo256,
184                2 => Self::Rpx256,
185                3 => Self::Poseidon2,
186                _ => Self::Keccak,
187            })
188            .boxed()
189    }
190}
191
192// SERIALIZATION
193// ================================================================================================
194
195impl Serializable for HashFunction {
196    fn write_into<W: ByteWriter>(&self, target: &mut W) {
197        target.write_u8(*self as u8);
198    }
199}
200
201impl Deserializable for HashFunction {
202    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
203        source.read_u8()?.try_into()
204    }
205}
206
207impl Serializable for ExecutionProof {
208    fn write_into<W: ByteWriter>(&self, target: &mut W) {
209        self.proof.write_into(target);
210        self.hash_fn.write_into(target);
211        self.pc_requests.write_into(target);
212    }
213}
214
215impl Deserializable for ExecutionProof {
216    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
217        let proof = Vec::<u8>::read_from(source)?;
218        let hash_fn = HashFunction::read_from(source)?;
219        let pc_requests = Vec::<PrecompileRequest>::read_from(source)?;
220
221        Ok(ExecutionProof { proof, hash_fn, pc_requests })
222    }
223
224    fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError> {
225        let mut reader = BudgetedReader::new(SliceReader::new(bytes), bytes.len());
226        Self::read_from(&mut reader)
227    }
228}
229
230// HASH FUNCTION ERROR
231// ================================================================================================
232
233/// Error type for invalid hash function strings.
234#[derive(Debug, thiserror::Error)]
235#[error(
236    "invalid hash function '{hash_function}'. Valid options are: blake3-256, rpo, rpx, poseidon2, keccak"
237)]
238pub struct InvalidHashFunctionError {
239    pub hash_function: String,
240}
241
242// TESTING UTILS
243// ================================================================================================
244
245#[cfg(any(test, feature = "testing"))]
246impl ExecutionProof {
247    /// Creates a dummy `ExecutionProof` for testing purposes only.
248    ///
249    /// A proof created in this way will not be verifiable against any verifier.
250    pub fn new_dummy() -> Self {
251        ExecutionProof {
252            proof: Vec::new(),
253            hash_fn: HashFunction::Blake3_256,
254            pc_requests: Vec::new(),
255        }
256    }
257}
258
259#[cfg(test)]
260mod tests {
261    use super::*;
262    use crate::{
263        events::EventId,
264        serde::{BudgetedReader, ByteWriter, DeserializationError, SliceReader},
265    };
266
267    #[test]
268    fn execution_proof_from_bytes_rejects_unbounded_proof_len() {
269        let mut bytes = Vec::new();
270        bytes.write_usize(usize::MAX);
271
272        let err = ExecutionProof::from_bytes(&bytes).unwrap_err();
273        let DeserializationError::InvalidValue(message) = err else {
274            panic!("expected InvalidValue error");
275        };
276        assert!(message.contains("requested"));
277        assert!(message.contains("reader can provide at most"));
278    }
279
280    #[test]
281    fn execution_proof_read_from_bytes_rejects_unbounded_proof_len() {
282        let mut bytes = Vec::new();
283        bytes.write_usize(usize::MAX);
284
285        let err = ExecutionProof::read_from_bytes(&bytes).unwrap_err();
286        let DeserializationError::InvalidValue(message) = err else {
287            panic!("expected InvalidValue error");
288        };
289        assert!(message.contains("requested"));
290        assert!(message.contains("reader can provide at most"));
291    }
292
293    #[test]
294    fn execution_proof_from_bytes_accepts_many_minimal_precompile_requests() {
295        let pc_requests = (0..64)
296            .map(|event_id| PrecompileRequest::new(EventId::from_u64(event_id), Vec::new()))
297            .collect();
298        let proof = ExecutionProof::new(vec![1, 2, 3], HashFunction::Blake3_256, pc_requests);
299
300        let decoded = ExecutionProof::from_bytes(&proof.to_bytes()).unwrap();
301
302        assert_eq!(decoded, proof);
303    }
304
305    #[test]
306    fn execution_proof_rejects_over_budget_proof_len() {
307        let mut bytes = Vec::new();
308        bytes.write_usize(5);
309
310        let budget = bytes.len() + 4;
311        let mut reader = BudgetedReader::new(SliceReader::new(&bytes), budget);
312        let err = ExecutionProof::read_from(&mut reader).unwrap_err();
313        let DeserializationError::InvalidValue(message) = err else {
314            panic!("expected InvalidValue error");
315        };
316        assert!(message.contains("requested 5 elements"));
317    }
318
319    #[test]
320    fn execution_proof_rejects_over_budget_pc_requests_len() {
321        let mut bytes = Vec::new();
322        bytes.write_usize(0);
323        bytes.write_u8(HashFunction::Blake3_256 as u8);
324        bytes.write_usize(2);
325
326        let budget = bytes.len() + 1;
327        let mut reader = BudgetedReader::new(SliceReader::new(&bytes), budget);
328        let err = ExecutionProof::read_from(&mut reader).unwrap_err();
329        let DeserializationError::InvalidValue(message) = err else {
330            panic!("expected InvalidValue error");
331        };
332        assert!(message.contains("requested 2 elements"));
333    }
334}
miden_core/proof.rs

miden_core/
proof.rs
