miden_core/mast/
untrusted.rs

1use alloc::vec::Vec;
2
3use super::{AdviceMap, MastForest, MastForestError, serialization};
4use crate::serde::{BudgetedReader, ByteReader, DeserializationError, SliceReader};
5
6/// A [`MastForest`] deserialized from untrusted input that has not yet been validated.
7///
8/// This type wraps a serialized-backed, decoded MAST representation that has not had its node
9/// hashes verified. Before using the forest, callers must call [`validate()`](Self::validate) to
10/// materialize and verify structural integrity and node hashes.
11///
12/// # Usage
13///
14/// ```ignore
15/// // Deserialize from untrusted bytes
16/// let untrusted = UntrustedMastForest::read_from_bytes(&bytes)?;
17///
18/// // Validate structure and hashes
19/// let forest = untrusted.validate()?;
20///
21/// // Now safe to use
22/// let root = forest.procedure_roots()[0];
23/// ```
24///
25/// # Security
26///
27/// This type exists to provide type-level safety for untrusted deserialization. The validation
28/// performed by [`validate()`](Self::validate) includes:
29///
30/// 1. **Structural validation**: Checks that basic block batch invariants are satisfied.
31/// 2. **Topological ordering**: Verifies that all node references point to nodes that appear
32///    earlier in the forest (no forward references).
33/// 3. **Hash recomputation**: Recomputes the digest for every node and verifies it matches the
34///    stored digest.
35#[derive(Debug, Clone)]
36pub struct UntrustedMastForest {
37    pub(super) bytes: Vec<u8>,
38    pub(super) layout: serialization::ForestLayout,
39    pub(super) advice_map: AdviceMap,
40    pub(super) remaining_allocation_budget: Option<usize>,
41}
42
43/// Options for reading an [`UntrustedMastForest`] from bytes.
44#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
45pub struct UntrustedMastForestReadOptions {
46    wire_byte_budget: Option<usize>,
47    validation_allocation_budget: Option<usize>,
48}
49
50impl UntrustedMastForestReadOptions {
51    /// Creates options that use the default untrusted budgets.
52    pub fn new() -> Self {
53        Self::default()
54    }
55
56    /// Sets the maximum number of serialized bytes consumed while parsing wire data.
57    pub fn with_wire_byte_budget(mut self, budget: usize) -> Self {
58        self.wire_byte_budget = Some(budget);
59        self
60    }
61
62    #[cfg(test)]
63    pub(crate) fn with_validation_allocation_budget(mut self, budget: usize) -> Self {
64        self.validation_allocation_budget = Some(budget);
65        self
66    }
67
68    fn wire_byte_budget(self, bytes_len: usize) -> usize {
69        self.wire_byte_budget.unwrap_or(bytes_len)
70    }
71
72    fn validation_allocation_budget(self, wire_byte_budget: usize) -> usize {
73        self.validation_allocation_budget
74            .unwrap_or_else(|| serialization::default_untrusted_allocation_budget(wire_byte_budget))
75    }
76}
77
78impl UntrustedMastForest {
79    /// Validates the forest by checking structural invariants and recomputing all node hashes.
80    ///
81    /// This method performs a complete validation of the deserialized forest:
82    ///
83    /// 1. If wire node hashes are present, recomputes all non-external node hashes and requires
84    ///    them to match the serialized digests.
85    /// 2. If the payload is hashless, uses the digests rebuilt during materialization.
86    /// 3. Validates structural invariants and topological ordering.
87    ///
88    /// # Returns
89    ///
90    /// - `Ok(MastForest)` if validation succeeds
91    /// - `Err(MastForestError)` with details about the first validation failure
92    ///
93    /// # Errors
94    ///
95    /// Returns an error if:
96    /// - Deferred materialization from serialized form fails ([`MastForestError::Deserialization`])
97    /// - Any basic block has invalid batch structure ([`MastForestError::InvalidBatchPadding`])
98    /// - Any node references a child that appears later in the forest
99    ///   ([`MastForestError::ForwardReference`])
100    /// - Any non-external wire digest does not match the recomputed digest
101    ///   ([`MastForestError::HashMismatch`])
102    /// - Any node's digest cannot be recomputed because structural validation fails first
103    ///
104    /// Security convention:
105    /// - Hashless payloads rebuild non-external digests from structure during materialization.
106    /// - If wire node hashes are present, validation recomputes them and requires them to match.
107    /// - External node digests are marshaled as opaque values and are not semantically resolved
108    ///   here.
109    pub fn validate(self) -> Result<MastForest, MastForestError> {
110        let is_hashless = self.layout.is_hashless();
111        let forest = self.into_materialized().map_err(MastForestError::Deserialization)?;
112
113        // Step 1: Validate over-specified wire hashes instead of silently rewriting them.
114        if !is_hashless {
115            forest.validate_node_hashes()?;
116        }
117
118        // Step 2: Validate the recomputed forest.
119        forest.validate()?;
120
121        Ok(forest)
122    }
123
124    /// Deserializes an [`UntrustedMastForest`] from bytes.
125    ///
126    /// This method uses a [`BudgetedReader`] plus a bounded validation-allocation budget derived
127    /// from the input size to protect against denial-of-service attacks from malicious input.
128    /// The default validation budget includes room for the retained serialized copy used by the
129    /// deferred-validation path, in addition to hashless helper allocations. Concretely,
130    /// the default is `bytes.len()` for parsing and `bytes.len() * 7` for validation allocations.
131    /// That `* 7` factor is a coarse convenience bound, not an exact peak-memory formula.
132    ///
133    /// For an explicit wire parsing limit, use
134    /// [`read_from_bytes_with_options`](Self::read_from_bytes_with_options).
135    ///
136    /// # Example
137    ///
138    /// ```ignore
139    /// // Read from untrusted source
140    /// let untrusted = UntrustedMastForest::read_from_bytes(&bytes)?;
141    ///
142    /// // Validate before use
143    /// let forest = untrusted.validate()?;
144    /// ```
145    pub fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError> {
146        Self::read_from_bytes_with_options(bytes, UntrustedMastForestReadOptions::default())
147    }
148
149    /// Deserializes an [`UntrustedMastForest`] from bytes with explicit options.
150    ///
151    /// The wire byte budget limits wire-driven parsing and collection pre-sizing. The validation
152    /// helper-allocation budget is derived from that wire budget and caps tracked hashless helper
153    /// allocations such as digest slot tables and rebuilt digest tables.
154    pub fn read_from_bytes_with_options(
155        bytes: &[u8],
156        options: UntrustedMastForestReadOptions,
157    ) -> Result<Self, DeserializationError> {
158        let wire_byte_budget = options.wire_byte_budget(bytes.len());
159        let mut reader = BudgetedReader::new(SliceReader::new(bytes), wire_byte_budget);
160        let (forest, _flags) = serialization::read_untrusted_with_flags_and_allocation_budget(
161            &mut reader,
162            options.validation_allocation_budget(wire_byte_budget),
163        )?;
164        if reader.has_more_bytes() {
165            return Err(DeserializationError::InvalidValue(
166                "extra bytes after MastForest payload".into(),
167            ));
168        }
169        Ok(forest)
170    }
171}
miden_core/mast/untrusted.rs

miden_core/mast/
untrusted.rs
