miden_core/mast/serialization/
sparse.rs

1use alloc::{collections::BTreeMap, format, string::ToString, vec::Vec};
2
3use super::{
4    TRUSTED_BYTE_READ_BUDGET_MULTIPLIER,
5    basic_blocks::{BasicBlockDataBuilder, BasicBlockDataDecoder},
6};
7use crate::{
8    Word,
9    advice::AdviceMap,
10    mast::{
11        BasicBlockNodeBuilder, CallNodeBuilder, DynNodeBuilder, ExternalNodeBuilder,
12        JoinNodeBuilder, LoopNodeBuilder, MastForest, MastForestContributor, MastNode, MastNodeExt,
13        MastNodeId, SparseMastForest, SplitNodeBuilder,
14    },
15    serde::{
16        BudgetedReader, ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable,
17        SliceReader, read_bounded_len,
18    },
19};
20
21const SPARSE_BLOCK: u8 = 0;
22const SPARSE_JOIN: u8 = 1;
23const SPARSE_SPLIT: u8 = 2;
24const SPARSE_LOOP: u8 = 3;
25const SPARSE_CALL: u8 = 4;
26const SPARSE_SYSCALL: u8 = 5;
27const SPARSE_DYN: u8 = 6;
28const SPARSE_DYNCALL: u8 = 7;
29const SPARSE_EXTERNAL: u8 = 8;
30
31// WRITER
32// ================================================================================================
33
34/// Writes trusted sparse trace replay data.
35///
36/// This format preserves the sparse maps produced by execution tracing. It does not prove that
37/// this sparse view is a subset of a committed [`MastForest`], and it does not share the dense
38/// [`MastForest`] wire format. Callers must only read these bytes from a trusted producer, or after
39/// an outer transport/authentication layer has accepted them.
40fn write_sparse_into<W: ByteWriter>(forest: &SparseMastForest, target: &mut W) {
41    write_node_ids(forest.procedure_roots(), target);
42    write_sparse_nodes(forest.nodes(), target);
43    write_digest_entries(forest.digest_entries(), target);
44    forest.advice_map().write_into(target);
45}
46
47fn write_node_ids<W: ByteWriter>(ids: &[MastNodeId], target: &mut W) {
48    target.write_usize(ids.len());
49    for id in ids {
50        id.write_into(target);
51    }
52}
53
54fn write_sparse_nodes<W: ByteWriter>(nodes: &BTreeMap<MastNodeId, MastNode>, target: &mut W) {
55    target.write_usize(nodes.len());
56    for (&id, node) in nodes {
57        id.write_into(target);
58        write_sparse_node(node, target);
59    }
60}
61
62fn write_digest_entries<W: ByteWriter>(digests: &BTreeMap<MastNodeId, Word>, target: &mut W) {
63    target.write_usize(digests.len());
64    for (&id, &digest) in digests {
65        id.write_into(target);
66        digest.write_into(target);
67    }
68}
69
70fn write_sparse_node<W: ByteWriter>(node: &MastNode, target: &mut W) {
71    match node {
72        MastNode::Block(block) => {
73            target.write_u8(SPARSE_BLOCK);
74            node.digest().write_into(target);
75
76            let mut basic_block_data = BasicBlockDataBuilder::new();
77            let ops_offset = basic_block_data.encode_basic_block(block);
78            debug_assert_eq!(ops_offset, 0);
79            let basic_block_data = basic_block_data.finalize();
80            target.write_usize(basic_block_data.len());
81            target.write_bytes(&basic_block_data);
82        },
83        MastNode::Join(join) => {
84            target.write_u8(SPARSE_JOIN);
85            node.digest().write_into(target);
86            join.first().write_into(target);
87            join.second().write_into(target);
88        },
89        MastNode::Split(split) => {
90            target.write_u8(SPARSE_SPLIT);
91            node.digest().write_into(target);
92            split.on_true().write_into(target);
93            split.on_false().write_into(target);
94        },
95        MastNode::Loop(loop_node) => {
96            target.write_u8(SPARSE_LOOP);
97            node.digest().write_into(target);
98            loop_node.body().write_into(target);
99        },
100        MastNode::Call(call) => {
101            target.write_u8(if call.is_syscall() { SPARSE_SYSCALL } else { SPARSE_CALL });
102            node.digest().write_into(target);
103            call.callee().write_into(target);
104        },
105        MastNode::Dyn(dyn_node) => {
106            target.write_u8(if dyn_node.is_dyncall() {
107                SPARSE_DYNCALL
108            } else {
109                SPARSE_DYN
110            });
111            node.digest().write_into(target);
112        },
113        MastNode::External(_) => {
114            target.write_u8(SPARSE_EXTERNAL);
115            node.digest().write_into(target);
116        },
117    }
118}
119
120// TRAIT IMPLS
121// ================================================================================================
122
123impl Serializable for SparseMastForest {
124    fn write_into<W: ByteWriter>(&self, target: &mut W) {
125        write_sparse_into(self, target);
126    }
127}
128
129impl Deserializable for SparseMastForest {
130    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
131        read_sparse_from(source)
132    }
133
134    fn min_serialized_size() -> usize {
135        usize::min_serialized_size()
136    }
137
138    /// Reads one trusted sparse replay payload and rejects trailing bytes.
139    ///
140    /// This is not an untrusted input format. The reader performs cheap structural checks, but a
141    /// producer controls collection lengths and can drive allocation. Callers must only read these
142    /// bytes from a trusted producer, or after an outer transport/authentication layer has accepted
143    /// them.
144    fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError> {
145        let budget = bytes.len().saturating_mul(TRUSTED_BYTE_READ_BUDGET_MULTIPLIER);
146        let mut reader = BudgetedReader::new(SliceReader::new(bytes), budget);
147        let forest = read_sparse_from(&mut reader)?;
148        if reader.has_more_bytes() {
149            return Err(DeserializationError::InvalidValue(
150                "extra bytes after SparseMastForest payload".to_string(),
151            ));
152        }
153        Ok(forest)
154    }
155}
156
157// READER
158// ================================================================================================
159
160fn read_sparse_from<R: ByteReader>(
161    source: &mut R,
162) -> Result<SparseMastForest, DeserializationError> {
163    let roots = read_node_ids(source, "procedure root")?;
164    let nodes = read_sparse_nodes(source)?;
165    let digest_entries = read_digest_entries(source)?;
166    let advice_map = read_empty_advice_map(source)?;
167
168    SparseMastForest::from_serialized_parts(nodes, digest_entries, roots, advice_map)
169}
170
171fn read_empty_advice_map<R: ByteReader>(source: &mut R) -> Result<AdviceMap, DeserializationError> {
172    let count = source.read_usize()?;
173    if count != 0 {
174        return Err(DeserializationError::InvalidValue(
175            "sparse MAST replay payload must not carry advice map entries".to_string(),
176        ));
177    }
178
179    Ok(AdviceMap::default())
180}
181
182fn read_node_ids<R: ByteReader>(
183    source: &mut R,
184    label: &str,
185) -> Result<Vec<MastNodeId>, DeserializationError> {
186    let count = read_bounded_count(source, u32::min_serialized_size(), label)?;
187    let mut ids = Vec::with_capacity(count);
188    for _ in 0..count {
189        ids.push(read_node_id(source, label)?);
190    }
191    Ok(ids)
192}
193
194fn read_sparse_nodes<R: ByteReader>(
195    source: &mut R,
196) -> Result<Vec<(MastNodeId, MastNode)>, DeserializationError> {
197    let count = read_bounded_count(source, sparse_node_min_size(), "full node count")?;
198    let mut nodes = Vec::with_capacity(count);
199    let mut previous_id = None;
200
201    for _ in 0..count {
202        let id = read_node_id(source, "full node")?;
203        validate_strictly_increasing_id(previous_id, id, "full node")?;
204        let node = read_sparse_node(source, id)?;
205        nodes.push((id, node));
206        previous_id = Some(id);
207    }
208
209    Ok(nodes)
210}
211
212fn read_digest_entries<R: ByteReader>(
213    source: &mut R,
214) -> Result<Vec<(MastNodeId, Word)>, DeserializationError> {
215    let count =
216        read_bounded_count(source, sparse_digest_entry_min_size(), "digest-only node count")?;
217    let mut digests = Vec::with_capacity(count);
218    let mut previous_id = None;
219
220    for _ in 0..count {
221        let id = read_node_id(source, "digest-only node")?;
222        validate_strictly_increasing_id(previous_id, id, "digest-only node")?;
223        let digest = Word::read_from(source)?;
224        digests.push((id, digest));
225        previous_id = Some(id);
226    }
227
228    Ok(digests)
229}
230
231fn read_sparse_node<R: ByteReader>(
232    source: &mut R,
233    node_id: MastNodeId,
234) -> Result<MastNode, DeserializationError> {
235    let tag = source.read_u8()?;
236    let digest = Word::read_from(source)?;
237
238    let result = match tag {
239        SPARSE_BLOCK => {
240            let len = read_bounded_count(source, 1, "basic block data length")?;
241            let data = source.read_vec(len)?;
242            let decoder = BasicBlockDataDecoder::new(&data);
243            let op_batches = decoder.decode_operations(0)?;
244            BasicBlockNodeBuilder::from_op_batches(op_batches, digest)
245                .build()
246                .map(Into::into)
247        },
248        SPARSE_JOIN => {
249            let first = read_node_id(source, "join first child")?;
250            let second = read_node_id(source, "join second child")?;
251            JoinNodeBuilder::new([first, second])
252                .with_digest(digest)
253                .build_linked()
254                .map(Into::into)
255        },
256        SPARSE_SPLIT => {
257            let on_true = read_node_id(source, "split true child")?;
258            let on_false = read_node_id(source, "split false child")?;
259            SplitNodeBuilder::new([on_true, on_false])
260                .with_digest(digest)
261                .build_linked()
262                .map(Into::into)
263        },
264        SPARSE_LOOP => {
265            let body = read_node_id(source, "loop body")?;
266            LoopNodeBuilder::new(body).with_digest(digest).build_linked().map(Into::into)
267        },
268        SPARSE_CALL | SPARSE_SYSCALL => {
269            let callee = read_node_id(source, "call callee")?;
270            let builder = if tag == SPARSE_SYSCALL {
271                CallNodeBuilder::new_syscall(callee)
272            } else {
273                CallNodeBuilder::new(callee)
274            };
275            builder.with_digest(digest).build_linked().map(Into::into)
276        },
277        SPARSE_DYN | SPARSE_DYNCALL => {
278            let builder = if tag == SPARSE_DYNCALL {
279                DynNodeBuilder::new_dyncall()
280            } else {
281                DynNodeBuilder::new_dyn()
282            };
283            Ok(builder.with_digest(digest).build().into())
284        },
285        SPARSE_EXTERNAL => Ok(ExternalNodeBuilder::new(digest).build().into()),
286        _ => {
287            return Err(DeserializationError::InvalidValue(format!(
288                "invalid sparse MAST node tag {tag}"
289            )));
290        },
291    };
292
293    result.map_err(|err| {
294        DeserializationError::InvalidValue(format!(
295            "failed to build sparse MAST node {}: {}",
296            node_id.0, err
297        ))
298    })
299}
300
301fn read_bounded_count<R: ByteReader>(
302    source: &mut R,
303    element_size: usize,
304    label: &str,
305) -> Result<usize, DeserializationError> {
306    read_bounded_len(source, label, element_size)
307}
308
309fn sparse_node_min_size() -> usize {
310    u32::min_serialized_size() + u8::min_serialized_size() + Word::min_serialized_size()
311}
312
313fn sparse_digest_entry_min_size() -> usize {
314    u32::min_serialized_size() + Word::min_serialized_size()
315}
316
317fn read_node_id<R: ByteReader>(
318    source: &mut R,
319    label: &str,
320) -> Result<MastNodeId, DeserializationError> {
321    let raw = u32::read_from(source)?;
322    MastNodeId::from_u32_with_node_count(raw, MastForest::MAX_NODES).map_err(|err| {
323        DeserializationError::InvalidValue(format!("invalid {label} id {raw}: {err}"))
324    })
325}
326
327fn validate_strictly_increasing_id(
328    previous: Option<MastNodeId>,
329    current: MastNodeId,
330    label: &str,
331) -> Result<(), DeserializationError> {
332    if previous.is_some_and(|previous| previous >= current) {
333        return Err(DeserializationError::InvalidValue(format!(
334            "{label} ids must be strictly increasing"
335        )));
336    }
337    Ok(())
338}
miden_core/mast/serialization/sparse.rs

miden_core/mast/serialization/
sparse.rs
