miden_core/mast/untrusted.rs
1use alloc::vec::Vec;
2
3use super::{AdviceMap, DebugInfo, MastForest, MastForestError, serialization};
4use crate::serde::{BudgetedReader, 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 and
31/// procedure names reference valid roots.
32/// 2. **Topological ordering**: Verifies that all node references point to nodes that appear
33/// earlier in the forest (no forward references).
34/// 3. **Hash recomputation**: Recomputes the digest for every node and verifies it matches the
35/// stored digest.
36#[derive(Debug, Clone)]
37pub struct UntrustedMastForest {
38 pub(super) bytes: Vec<u8>,
39 pub(super) layout: serialization::ForestLayout,
40 pub(super) advice_map: AdviceMap,
41 pub(super) debug_info: DebugInfo,
42 pub(super) remaining_allocation_budget: Option<usize>,
43}
44
45impl UntrustedMastForest {
46 /// Validates the forest by checking structural invariants and recomputing all node hashes.
47 ///
48 /// This method performs a complete validation of the deserialized forest:
49 ///
50 /// 1. If wire node hashes are present, recomputes all non-external node hashes and requires
51 /// them to match the serialized digests.
52 /// 2. If the payload is hashless, uses the digests rebuilt during materialization.
53 /// 3. Validates structural invariants, topological ordering, and procedure-name roots.
54 ///
55 /// # Returns
56 ///
57 /// - `Ok(MastForest)` if validation succeeds
58 /// - `Err(MastForestError)` with details about the first validation failure
59 ///
60 /// # Errors
61 ///
62 /// Returns an error if:
63 /// - Deferred materialization from serialized form fails ([`MastForestError::Deserialization`])
64 /// - Any basic block has invalid batch structure ([`MastForestError::InvalidBatchPadding`])
65 /// - Any procedure name references a non-root digest
66 /// ([`MastForestError::InvalidProcedureNameDigest`])
67 /// - Any node references a child that appears later in the forest
68 /// ([`MastForestError::ForwardReference`])
69 /// - Any non-external wire digest does not match the recomputed digest
70 /// ([`MastForestError::HashMismatch`])
71 /// - Any node's digest cannot be recomputed because structural validation fails first
72 ///
73 /// Security convention:
74 /// - Hashless payloads rebuild non-external digests from structure during materialization.
75 /// - If wire node hashes are present, validation recomputes them and requires them to match.
76 /// - External node digests are marshaled as opaque values and are not semantically resolved
77 /// here.
78 pub fn validate(self) -> Result<MastForest, MastForestError> {
79 let is_hashless = self.layout.is_hashless();
80 let forest = self.into_materialized().map_err(MastForestError::Deserialization)?;
81
82 // Step 1: Validate over-specified wire hashes instead of silently rewriting them.
83 if !is_hashless {
84 forest.validate_node_hashes()?;
85 }
86
87 // Step 2: Validate the recomputed forest.
88 forest.validate()?;
89
90 Ok(forest)
91 }
92
93 /// Deserializes an [`UntrustedMastForest`] from bytes.
94 ///
95 /// This method uses a [`BudgetedReader`] plus a bounded validation-allocation budget derived
96 /// from the input size to protect against denial-of-service attacks from malicious input.
97 /// The default validation budget includes room for the retained serialized copy used by the
98 /// deferred-validation path, in addition to stripped/hashless helper allocations. Concretely,
99 /// the default is `bytes.len()` for parsing and `bytes.len() * 7` for validation allocations.
100 /// That `* 7` factor is a coarse convenience bound, not an exact peak-memory formula.
101 ///
102 /// For explicit parsing and validation limits, use
103 /// [`read_from_bytes_with_budgets`](Self::read_from_bytes_with_budgets).
104 ///
105 /// # Example
106 ///
107 /// ```ignore
108 /// // Read from untrusted source
109 /// let untrusted = UntrustedMastForest::read_from_bytes(&bytes)?;
110 ///
111 /// // Validate before use
112 /// let forest = untrusted.validate()?;
113 /// ```
114 pub fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError> {
115 Self::read_from_bytes_with_budgets(
116 bytes,
117 bytes.len(),
118 serialization::default_untrusted_allocation_budget(bytes.len()),
119 )
120 }
121
122 /// Deserializes an [`UntrustedMastForest`] from bytes and returns the raw wire flags.
123 ///
124 /// This enables callers to inspect serializer intent flags (e.g., HASHLESS) without affecting
125 /// the untrusted deserialization path.
126 pub fn read_from_bytes_with_flags(bytes: &[u8]) -> Result<(Self, u8), DeserializationError> {
127 Self::read_from_bytes_with_budgets_and_flags(
128 bytes,
129 bytes.len(),
130 serialization::default_untrusted_allocation_budget(bytes.len()),
131 )
132 }
133
134 /// Deserializes an [`UntrustedMastForest`] from bytes with a byte budget.
135 ///
136 /// This method uses a [`BudgetedReader`] to limit memory consumption during deserialization,
137 /// protecting against denial-of-service attacks from malicious input that claims to contain
138 /// an excessive number of elements.
139 ///
140 /// # Arguments
141 ///
142 /// * `bytes` - The serialized forest bytes
143 /// * `budget` - Maximum bytes to consume while parsing the wire payload and pre-sizing
144 /// wire-driven collections via [`BudgetedReader`]
145 ///
146 /// # Example
147 ///
148 /// ```ignore
149 /// // Read from untrusted source with an explicit parsing budget
150 /// let untrusted = UntrustedMastForest::read_from_bytes_with_budget(&bytes, bytes.len())?;
151 ///
152 /// // Validate before use
153 /// let forest = untrusted.validate()?;
154 /// ```
155 ///
156 /// # Security
157 ///
158 /// The budget limits:
159 /// - Pre-allocation sizes when deserializing collections (via `max_alloc`)
160 /// - Total bytes consumed during deserialization
161 ///
162 /// This prevents attacks where malicious input claims an unrealistic number of elements
163 /// (e.g., `len = 2^60`), causing excessive memory allocation before any data is read.
164 ///
165 /// To also cap stripped/hashless validation helper allocations, use
166 /// [`read_from_bytes_with_budgets`](Self::read_from_bytes_with_budgets).
167 pub fn read_from_bytes_with_budget(
168 bytes: &[u8],
169 budget: usize,
170 ) -> Result<Self, DeserializationError> {
171 let mut reader = BudgetedReader::new(SliceReader::new(bytes), budget);
172 serialization::read_untrusted_with_flags(&mut reader).map(|(forest, _flags)| forest)
173 }
174
175 /// Deserializes an [`UntrustedMastForest`] from bytes with a byte budget and returns flags.
176 pub fn read_from_bytes_with_budget_and_flags(
177 bytes: &[u8],
178 budget: usize,
179 ) -> Result<(Self, u8), DeserializationError> {
180 let mut reader = BudgetedReader::new(SliceReader::new(bytes), budget);
181 serialization::read_untrusted_with_flags(&mut reader)
182 }
183
184 /// Deserializes an [`UntrustedMastForest`] from bytes with separate parsing and validation
185 /// budgets.
186 ///
187 /// `parsing_budget` limits wire-driven parsing and collection pre-sizing. `validation_budget`
188 /// additionally caps tracked stripped/hashless helper allocations such as digest slot tables,
189 /// empty debug-info scaffolding, and rebuilt digest tables.
190 pub fn read_from_bytes_with_budgets(
191 bytes: &[u8],
192 parsing_budget: usize,
193 validation_budget: usize,
194 ) -> Result<Self, DeserializationError> {
195 let mut reader = BudgetedReader::new(SliceReader::new(bytes), parsing_budget);
196 serialization::read_untrusted_with_flags_and_allocation_budget(
197 &mut reader,
198 validation_budget,
199 )
200 .map(|(forest, _flags)| forest)
201 }
202
203 /// Deserializes an [`UntrustedMastForest`] from bytes with separate parsing and validation
204 /// budgets and returns flags.
205 pub fn read_from_bytes_with_budgets_and_flags(
206 bytes: &[u8],
207 parsing_budget: usize,
208 validation_budget: usize,
209 ) -> Result<(Self, u8), DeserializationError> {
210 let mut reader = BudgetedReader::new(SliceReader::new(bytes), parsing_budget);
211 serialization::read_untrusted_with_flags_and_allocation_budget(
212 &mut reader,
213 validation_budget,
214 )
215 }
216}