miden_core/deferred/
node.rs

1//! Deferred node model: tags, payloads, shapes, and content-addressed digests.
2
3use alloc::{sync::Arc, vec::Vec};
4use core::mem::size_of;
5
6use miden_crypto::{ONE, ZERO, hash::poseidon2::Poseidon2};
7
8use super::DeferredError;
9use crate::{
10    Felt, Word,
11    serde::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable},
12    utils::bytes_to_packed_u32_elements,
13};
14
15/// Stable address of a deferred [`Node`], computed as a 4-felt Poseidon2 digest.
16pub type Digest = Word;
17
18/// One Poseidon2 rate block, used as the unit of deferred data payloads.
19pub type DataChunk = [Felt; 8];
20
21/// Digest of [`Node::TRUE`], root for an empty deferred state, and terminal of the AND-chain.
22///
23/// TRUE is an always-present framework node with digest zero. Wire encoding reserves index 0 for
24/// this digest instead of serializing TRUE as an explicit entry.
25pub const TRUE_DIGEST: Digest = Word::new([ZERO; 4]);
26
27// TAG
28// ================================================================================================
29
30/// Identifies the precompile that owns a node and carries its local immediates.
31///
32/// Framework ids are reserved for built-in nodes: `0` is TRUE, `1` is semantic AND, and
33/// `2` is opaque framework chunks. The remaining three felts are opaque to the framework and are
34/// decoded only by the owning [`super::Precompile`]. The canonical layout is
35/// `[id, arg0, arg1, arg2]` for hashing and wire encoding.
36#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
37pub struct Tag {
38    id: Felt,
39    args: [Felt; 3],
40}
41
42impl Tag {
43    pub(crate) const FELT_LEN: usize = 4;
44    const CHUNKS_ID: Felt = Felt::new_unchecked(2);
45
46    /// Framework-owned tag for the canonical TRUE node.
47    pub const TRUE: Tag = Tag { id: ZERO, args: [ZERO; 3] };
48
49    /// Framework-owned tag for semantic conjunction nodes.
50    pub const AND: Tag = Tag { id: ONE, args: [ZERO; 3] };
51
52    /// Framework-owned tag for opaque chunk-list data nodes.
53    pub const CHUNKS: Tag = Tag { id: Self::CHUNKS_ID, args: [ZERO; 3] };
54
55    /// Returns whether an id is reserved by the deferred framework.
56    pub(crate) fn is_framework_reserved_id(id: Felt) -> bool {
57        id == ZERO || id == ONE || id == Self::CHUNKS_ID
58    }
59
60    /// Returns whether this tag belongs to the framework namespace.
61    pub(crate) fn is_framework_reserved(&self) -> bool {
62        Self::is_framework_reserved_id(self.id)
63    }
64
65    /// Creates a tag from a precompile id and its three local immediates.
66    ///
67    /// Framework ids are reserved for [`Tag::TRUE`], [`Tag::AND`], and [`Tag::CHUNKS`]. Use
68    /// [`Tag::from_word`] only for raw stack/wire decoding that must preserve untrusted tags before
69    /// validation.
70    pub fn precompile(id: Felt, args: [Felt; 3]) -> Result<Self, DeferredError> {
71        if Self::is_framework_reserved_id(id) {
72            return Err(DeferredError::InvalidTag);
73        }
74        Ok(Self { id, args })
75    }
76
77    /// Returns the precompile/framework id component.
78    pub const fn id(&self) -> Felt {
79        self.id
80    }
81
82    /// Returns the three local immediate arguments.
83    pub const fn args(&self) -> [Felt; 3] {
84        self.args
85    }
86
87    /// Returns the canonical layout used by hashing and wire encoding.
88    pub const fn as_word(&self) -> [Felt; 4] {
89        [self.id, self.args[0], self.args[1], self.args[2]]
90    }
91
92    /// Restores a tag from the canonical 4-felt layout without validation.
93    pub const fn from_word(w: [Felt; 4]) -> Self {
94        Self { id: w[0], args: [w[1], w[2], w[3]] }
95    }
96}
97
98impl Serializable for Tag {
99    fn write_into<W: ByteWriter>(&self, target: &mut W) {
100        for felt in &self.as_word() {
101            felt.write_into(target);
102        }
103    }
104}
105
106impl Deserializable for Tag {
107    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
108        Ok(Self::from_word([
109            Felt::read_from(source)?,
110            Felt::read_from(source)?,
111            Felt::read_from(source)?,
112            Felt::read_from(source)?,
113        ]))
114    }
115
116    fn min_serialized_size() -> usize {
117        Self::FELT_LEN * Felt::min_serialized_size()
118    }
119}
120
121// PAYLOAD
122// ================================================================================================
123
124/// In-memory body of a deferred node.
125///
126/// Payloads have four representations:
127///
128/// - TRUE: the framework sentinel, carrying no data.
129/// - Data: one or more opaque [`DataChunk`]s.
130/// - Join: one [`DataChunk`] containing two child digests (`lhs || rhs`).
131/// - PairList: one or more structural digest pairs, each chunked as `lhs || rhs`.
132///
133/// The representation is private: external precompiles can inspect payloads through accessors, but
134/// cannot fabricate framework TRUE, empty data, or unchecked structural payloads.
135#[derive(Debug, Clone, PartialEq, Eq)]
136pub struct Payload(PayloadRepr);
137
138#[derive(Debug, Clone, PartialEq, Eq)]
139enum PayloadRepr {
140    /// The framework TRUE sentinel; carries no data.
141    True,
142    /// Non-empty opaque data.
143    Data(Arc<[DataChunk]>),
144    /// Two child digests encoded as `lhs || rhs`.
145    Join(DataChunk),
146    /// Non-empty structural digest pairs, stored as chunks `lhs || rhs`.
147    PairList(Arc<[DataChunk]>),
148}
149
150impl Payload {
151    /// Creates a single-chunk data payload.
152    fn value(chunk: DataChunk) -> Self {
153        Self(PayloadRepr::Data(alloc::vec![chunk].into()))
154    }
155
156    /// Creates a data payload from a non-empty chunk collection.
157    ///
158    /// Returns [`DeferredError::InvalidPayload`] if `chunks` is empty.
159    fn try_data(chunks: impl Into<Arc<[DataChunk]>>) -> Result<Self, DeferredError> {
160        let chunks = chunks.into();
161        if chunks.is_empty() {
162            return Err(DeferredError::InvalidPayload);
163        }
164        Ok(Self(PayloadRepr::Data(chunks)))
165    }
166
167    /// Creates a join payload that references two child digests.
168    fn join(lhs: Digest, rhs: Digest) -> Self {
169        let [l0, l1, l2, l3] = lhs.into_elements();
170        let [r0, r1, r2, r3] = rhs.into_elements();
171        Self(PayloadRepr::Join([l0, l1, l2, l3, r0, r1, r2, r3]))
172    }
173
174    /// Creates a pair-list payload from a non-empty collection of structural digest pairs.
175    ///
176    /// Returns [`DeferredError::InvalidPayload`] if `pairs` is empty.
177    fn try_pair_list(pairs: impl Into<Arc<[(Digest, Digest)]>>) -> Result<Self, DeferredError> {
178        let pairs = pairs.into();
179        let chunks = pairs
180            .iter()
181            .map(|(lhs, rhs)| Self::pair_to_chunk(*lhs, *rhs))
182            .collect::<Vec<_>>();
183        Self::try_pair_list_chunks(chunks)
184    }
185
186    /// Creates a pair-list payload from non-empty chunks encoded as `lhs || rhs`.
187    ///
188    /// Returns [`DeferredError::InvalidPayload`] if `chunks` is empty.
189    fn try_pair_list_chunks(chunks: impl Into<Arc<[DataChunk]>>) -> Result<Self, DeferredError> {
190        let chunks = chunks.into();
191        if chunks.is_empty() {
192            return Err(DeferredError::InvalidPayload);
193        }
194        Ok(Self(PayloadRepr::PairList(chunks)))
195    }
196
197    fn pair_to_chunk(lhs: Digest, rhs: Digest) -> DataChunk {
198        let [l0, l1, l2, l3] = lhs.into_elements();
199        let [r0, r1, r2, r3] = rhs.into_elements();
200        [l0, l1, l2, l3, r0, r1, r2, r3]
201    }
202
203    fn chunk_to_pair([l0, l1, l2, l3, r0, r1, r2, r3]: DataChunk) -> (Digest, Digest) {
204        (Digest::new([l0, l1, l2, l3]), Digest::new([r0, r1, r2, r3]))
205    }
206
207    /// Returns this payload's canonical 8-felt blocks.
208    ///
209    /// - TRUE returns no blocks.
210    /// - Data returns its stored chunks.
211    /// - Join returns one block containing `lhs || rhs`.
212    /// - PairList returns one block per pair, each containing `lhs || rhs`.
213    pub fn as_chunks(&self) -> &[DataChunk] {
214        match &self.0 {
215            PayloadRepr::True => &[],
216            PayloadRepr::Data(chunks) | PayloadRepr::PairList(chunks) => chunks,
217            PayloadRepr::Join(chunk) => core::slice::from_ref(chunk),
218        }
219    }
220
221    /// Returns this payload's data chunks.
222    ///
223    /// - Data returns its stored chunks.
224    /// - TRUE, Join, and PairList return [`DeferredError::InvalidPayload`].
225    pub fn as_data(&self) -> Result<&[DataChunk], DeferredError> {
226        match &self.0 {
227            PayloadRepr::Data(chunks) => Ok(chunks),
228            PayloadRepr::True | PayloadRepr::Join(_) | PayloadRepr::PairList(_) => {
229                Err(DeferredError::InvalidPayload)
230            },
231        }
232    }
233
234    /// Returns the single data chunk for value-like payloads.
235    ///
236    /// - One-chunk Data returns that chunk.
237    /// - Multi-chunk Data, TRUE, Join, and PairList return [`DeferredError::InvalidPayload`].
238    pub fn as_value(&self) -> Result<&DataChunk, DeferredError> {
239        match self.as_data()? {
240            [chunk] => Ok(chunk),
241            _ => Err(DeferredError::InvalidPayload),
242        }
243    }
244
245    /// Returns the child digests for join payloads.
246    ///
247    /// - Join returns `(lhs, rhs)`.
248    /// - TRUE, Data, and PairList return [`DeferredError::InvalidPayload`].
249    pub fn as_join(&self) -> Result<(Digest, Digest), DeferredError> {
250        match &self.0 {
251            PayloadRepr::Join([l0, l1, l2, l3, r0, r1, r2, r3]) => {
252                Ok((Digest::new([*l0, *l1, *l2, *l3]), Digest::new([*r0, *r1, *r2, *r3])))
253            },
254            PayloadRepr::True | PayloadRepr::Data(_) | PayloadRepr::PairList(_) => {
255                Err(DeferredError::InvalidPayload)
256            },
257        }
258    }
259
260    fn pair_list_chunks(&self) -> Result<&[DataChunk], DeferredError> {
261        match &self.0 {
262            PayloadRepr::PairList(chunks) => Ok(chunks),
263            PayloadRepr::True | PayloadRepr::Data(_) | PayloadRepr::Join(_) => {
264                Err(DeferredError::InvalidPayload)
265            },
266        }
267    }
268
269    /// Returns the structural digest pairs for pair-list payloads.
270    ///
271    /// - PairList decodes and returns its pairs in payload order.
272    /// - TRUE, Data, and Join return [`DeferredError::InvalidPayload`].
273    pub fn as_pair_list(&self) -> Result<Vec<(Digest, Digest)>, DeferredError> {
274        Ok(self
275            .pair_list_chunks()?
276            .iter()
277            .map(|chunk| Self::chunk_to_pair(*chunk))
278            .collect())
279    }
280
281    /// Returns this payload's structural child digests in payload order.
282    ///
283    /// - TRUE and Data return no children.
284    /// - Join returns `lhs`, then `rhs`.
285    /// - PairList returns `lhs0`, `rhs0`, `lhs1`, `rhs1`, ...
286    fn children(&self) -> Vec<Digest> {
287        match &self.0 {
288            PayloadRepr::Join([l0, l1, l2, l3, r0, r1, r2, r3]) => {
289                alloc::vec![Digest::new([*l0, *l1, *l2, *l3]), Digest::new([*r0, *r1, *r2, *r3]),]
290            },
291            PayloadRepr::PairList(chunks) => chunks
292                .iter()
293                .flat_map(|chunk| {
294                    let (lhs, rhs) = Self::chunk_to_pair(*chunk);
295                    [lhs, rhs]
296                })
297                .collect(),
298            PayloadRepr::True | PayloadRepr::Data(_) => Vec::new(),
299        }
300    }
301}
302
303// NODE
304// ================================================================================================
305
306/// A deferred DAG entry whose meaning is supplied by a framework tag or owning
307/// [`super::Precompile`].
308///
309/// The framework validates only the declared [`NodeType`]. Value semantics, producing ops, and
310/// predicates all live in the owning [`super::Precompile`]. A predicate succeeds by evaluating to
311/// [`Node::TRUE`], so callers can handle every canonical result as an ordinary node.
312#[derive(Clone, Debug, PartialEq, Eq)]
313pub struct Node {
314    tag: Tag,
315    payload: Payload,
316}
317
318impl Node {
319    pub(crate) const DATA_CHUNK_FELT_LEN: usize = 8;
320
321    /// Number of little-endian bytes represented by one [`DataChunk`].
322    ///
323    /// Each of the eight field elements stores one packed `u32`, so a chunk carries 32 bytes.
324    pub const PACKED_BYTES_PER_CHUNK: usize = Self::DATA_CHUNK_FELT_LEN * size_of::<u32>();
325
326    /// Canonical TRUE node returned by predicates that verify successfully.
327    pub const TRUE: Node = Node {
328        tag: Tag::TRUE,
329        payload: Payload(PayloadRepr::True),
330    };
331
332    /// Creates a value-like single-chunk data node.
333    pub fn value(tag: Tag, chunk: DataChunk) -> Result<Self, DeferredError> {
334        let tag = Self::require_precompile_tag(tag)?;
335        Ok(Self { tag, payload: Payload::value(chunk) })
336    }
337
338    /// Creates a data node from a non-empty chunk collection.
339    ///
340    /// Returns [`DeferredError::InvalidPayload`] if `chunks` is empty and
341    /// [`DeferredError::InvalidTag`] if `tag` uses a framework-reserved id.
342    pub fn try_data(tag: Tag, chunks: impl Into<Arc<[DataChunk]>>) -> Result<Self, DeferredError> {
343        let tag = Self::require_precompile_tag(tag)?;
344        Ok(Self { tag, payload: Payload::try_data(chunks)? })
345    }
346
347    /// Creates a framework-owned opaque chunk-list data node.
348    ///
349    /// Returns [`DeferredError::InvalidPayload`] if `chunks` is empty.
350    pub fn chunks(chunks: impl Into<Arc<[DataChunk]>>) -> Result<Self, DeferredError> {
351        Ok(Self {
352            tag: Tag::CHUNKS,
353            payload: Payload::try_data(chunks)?,
354        })
355    }
356
357    /// Creates a framework-owned opaque chunk-list data node from bytes.
358    ///
359    /// Bytes are packed little-endian into `u32` field elements, padded with zero felts to a
360    /// non-empty multiple of one [`DataChunk`], and wrapped in the framework [`Tag::CHUNKS`] node.
361    /// Empty byte strings therefore encode as a single all-zero chunk.
362    pub fn chunks_from_bytes(bytes: &[u8]) -> Self {
363        let mut felts = bytes_to_packed_u32_elements(bytes);
364        let n_chunks = felts.len().div_ceil(Self::DATA_CHUNK_FELT_LEN).max(1);
365        felts.resize(n_chunks * Self::DATA_CHUNK_FELT_LEN, ZERO);
366        #[allow(clippy::chunks_exact_to_as_chunks)]
367        let chunks = felts
368            .as_chunks::<{ Self::DATA_CHUNK_FELT_LEN }>()
369            .0
370            .iter()
371            .map(|chunk| core::array::from_fn(|i| chunk[i]))
372            .collect::<Vec<_>>();
373        Self::chunks(chunks).expect("chunks_from_bytes always creates at least one chunk")
374    }
375
376    /// Creates a join-shaped node that references two child digests.
377    pub fn join(tag: Tag, lhs: Digest, rhs: Digest) -> Result<Self, DeferredError> {
378        let tag = Self::require_precompile_tag(tag)?;
379        Ok(Self { tag, payload: Payload::join(lhs, rhs) })
380    }
381
382    /// Creates a pair-list-shaped node that references one or more structural digest pairs.
383    pub fn try_pair_list(
384        tag: Tag,
385        pairs: impl Into<Arc<[(Digest, Digest)]>>,
386    ) -> Result<Self, DeferredError> {
387        let tag = Self::require_precompile_tag(tag)?;
388        Ok(Self {
389            tag,
390            payload: Payload::try_pair_list(pairs)?,
391        })
392    }
393
394    /// Creates a pair-list-shaped node from non-empty chunks encoded as `lhs_digest || rhs_digest`.
395    pub fn try_pair_list_chunks(
396        tag: Tag,
397        chunks: impl Into<Arc<[DataChunk]>>,
398    ) -> Result<Self, DeferredError> {
399        let tag = Self::require_precompile_tag(tag)?;
400        Ok(Self {
401            tag,
402            payload: Payload::try_pair_list_chunks(chunks)?,
403        })
404    }
405
406    /// Creates a structural deferred-root AND step from the previous root and statement digest.
407    pub fn and(lhs: Digest, rhs: Digest) -> Self {
408        Self {
409            tag: Tag::AND,
410            payload: Payload::join(lhs, rhs),
411        }
412    }
413
414    fn require_precompile_tag(tag: Tag) -> Result<Tag, DeferredError> {
415        if tag.is_framework_reserved() {
416            return Err(DeferredError::InvalidTag);
417        }
418        Ok(tag)
419    }
420
421    /// Returns this node's tag.
422    pub fn tag(&self) -> Tag {
423        self.tag
424    }
425
426    /// Returns this node's payload.
427    pub fn payload(&self) -> &Payload {
428        &self.payload
429    }
430
431    /// Returns this node's structural child digests in payload order.
432    ///
433    /// This is infallible because [`Node`] constructors determine the payload representation:
434    ///
435    /// - data and TRUE nodes have no children;
436    /// - join nodes yield `lhs`, then `rhs`;
437    /// - pair-list nodes yield `lhs0`, `rhs0`, `lhs1`, `rhs1`, ...
438    pub(crate) fn children(&self) -> impl Iterator<Item = Digest> + '_ {
439        self.payload.children().into_iter()
440    }
441
442    /// Returns this node's payload if the node has `tag`.
443    pub fn payload_for_tag(&self, tag: Tag) -> Result<&Payload, DeferredError> {
444        if self.tag != tag {
445            return Err(DeferredError::InvalidPayload);
446        }
447        Ok(&self.payload)
448    }
449
450    /// Returns whether this node is structurally the canonical TRUE result.
451    pub fn is_true(&self) -> bool {
452        matches!(&self.payload.0, PayloadRepr::True) && self.tag == Tag::TRUE
453    }
454
455    /// Returns the field-element length of this node's canonical external representation.
456    pub fn felt_len(&self) -> usize {
457        Tag::FELT_LEN
458            .checked_add(
459                Self::DATA_CHUNK_FELT_LEN
460                    .checked_mul(self.payload.as_chunks().len())
461                    .expect("payload felt count overflow"),
462            )
463            .expect("node felt count overflow")
464    }
465
466    /// Returns the storage/budget footprint for durable state accounting.
467    pub(crate) fn storage_felt_len(&self) -> usize {
468        if self.is_true() { 0 } else { self.felt_len() }
469    }
470
471    /// Appends this node's canonical external representation to `target`.
472    pub fn write_into_felts(&self, target: &mut Vec<Felt>) {
473        target.extend_from_slice(&self.tag.as_word());
474        for chunk in self.payload.as_chunks() {
475            target.extend_from_slice(chunk);
476        }
477    }
478
479    /// Returns this node's canonical external representation.
480    pub fn to_felts(&self) -> Vec<Felt> {
481        let mut felts = Vec::with_capacity(self.felt_len());
482        self.write_into_felts(&mut felts);
483        felts
484    }
485
486    /// Computes the canonical digest used by both host code and Miden VM programs.
487    pub fn digest(&self) -> Digest {
488        if matches!(&self.payload.0, PayloadRepr::True) {
489            assert_eq!(self.tag, Tag::TRUE, "TRUE payload is only valid for Node::TRUE");
490            return TRUE_DIGEST;
491        }
492
493        hash_payload(self.tag, self.payload.as_chunks().iter().copied())
494    }
495}
496
497/// Hashes the shared tag-and-chunks commitment layout without constructing a runtime node.
498pub(super) fn hash_payload(tag: Tag, chunks: impl IntoIterator<Item = DataChunk>) -> Digest {
499    let mut state = [ZERO; 12];
500    state[Node::DATA_CHUNK_FELT_LEN..Node::DATA_CHUNK_FELT_LEN + Tag::FELT_LEN]
501        .copy_from_slice(&tag.as_word());
502    for chunk in chunks {
503        state[0..Node::DATA_CHUNK_FELT_LEN].copy_from_slice(&chunk);
504        Poseidon2::apply_permutation(&mut state);
505    }
506    Word::new([state[0], state[1], state[2], state[3]])
507}
508
509// NODE TYPE
510// ================================================================================================
511
512/// Framework shape a precompile declares for a recognized tag.
513///
514/// The shape tells registration and wire validation whether a body is non-empty opaque data, two
515/// child digests, or a non-empty list of digest pairs. It intentionally does not carry
516/// data/pair-list arity. Any semantic length encoded by a precompile's tag, such as a hash preimage
517/// byte length, is checked during precompile evaluation. `True` is the framework sentinel owned
518/// exclusively by [`Tag::TRUE`];
519/// precompiles never declare it. Predicate status is not a shape; predicates succeed by evaluating
520/// to [`Node::TRUE`].
521#[derive(Debug, Clone, Copy, PartialEq, Eq)]
522pub enum NodeType {
523    /// The framework TRUE sentinel, with no data payload.
524    True,
525    /// Non-empty opaque data.
526    Data,
527    /// Two child digests.
528    Join,
529    /// Non-empty structural digest pairs.
530    PairList,
531}
532
533impl NodeType {
534    /// Validates that a node's payload matches this declared framework shape.
535    pub(crate) fn validate_node(self, node: &Node) -> Result<(), DeferredError> {
536        match self {
537            Self::True if node.is_true() => Ok(()),
538            Self::Data if node.payload.as_data().is_ok() => Ok(()),
539            Self::Join if node.payload.as_join().is_ok() => Ok(()),
540            Self::PairList if node.payload.pair_list_chunks().is_ok() => Ok(()),
541            _ => Err(DeferredError::InvalidPayload),
542        }
543    }
544}
545
546#[cfg(test)]
547mod tests {
548    use alloc::vec::Vec;
549
550    use super::*;
551
552    const TAG_A: Tag = Tag::from_word([Felt::new_unchecked(42), ZERO, ZERO, ZERO]);
553    const TAG_B: Tag =
554        Tag::from_word([Felt::new_unchecked(42), ZERO, Felt::new_unchecked(1), ZERO]);
555
556    fn block(seed: u64) -> DataChunk {
557        core::array::from_fn(|i| Felt::new_unchecked(seed.wrapping_add(i as u64)))
558    }
559
560    #[test]
561    fn tag_precompile_rejects_framework_reserved_ids_but_from_word_is_raw() {
562        assert_eq!(Tag::precompile(Tag::TRUE.id(), [ZERO; 3]), Err(DeferredError::InvalidTag));
563        assert_eq!(Tag::precompile(Tag::AND.id(), [ZERO; 3]), Err(DeferredError::InvalidTag));
564        assert_eq!(Tag::precompile(Tag::CHUNKS.id(), [ZERO; 3]), Err(DeferredError::InvalidTag));
565        assert_eq!(
566            Tag::precompile(Tag::CHUNKS.id(), [Felt::new_unchecked(9), ZERO, ZERO]),
567            Err(DeferredError::InvalidTag)
568        );
569
570        let raw_true = Tag::from_word([ZERO, Felt::new_unchecked(9), ZERO, ZERO]);
571        assert_eq!(raw_true.id(), Tag::TRUE.id());
572        assert_eq!(raw_true.args(), [Felt::new_unchecked(9), ZERO, ZERO]);
573
574        let raw_chunks = Tag::from_word([Tag::CHUNKS.id(), Felt::new_unchecked(9), ZERO, ZERO]);
575        assert_eq!(raw_chunks.id(), Tag::CHUNKS.id());
576        assert_eq!(raw_chunks.args(), [Felt::new_unchecked(9), ZERO, ZERO]);
577    }
578
579    #[test]
580    fn public_node_constructors_reject_framework_reserved_tags() {
581        let chunk = block(1);
582        assert_eq!(Node::value(Tag::TRUE, chunk), Err(DeferredError::InvalidTag));
583        assert_eq!(Node::try_data(Tag::AND, alloc::vec![chunk]), Err(DeferredError::InvalidTag));
584        assert_eq!(Node::try_data(Tag::CHUNKS, alloc::vec![chunk]), Err(DeferredError::InvalidTag));
585        assert_eq!(Node::join(Tag::AND, TRUE_DIGEST, TRUE_DIGEST), Err(DeferredError::InvalidTag));
586        assert_eq!(
587            Node::try_pair_list(Tag::AND, alloc::vec![(TRUE_DIGEST, TRUE_DIGEST)]),
588            Err(DeferredError::InvalidTag)
589        );
590
591        let and = Node::and(TRUE_DIGEST, TRUE_DIGEST);
592        assert_eq!(and.tag(), Tag::AND);
593        assert_eq!(and.payload().as_join().unwrap(), (TRUE_DIGEST, TRUE_DIGEST));
594    }
595
596    #[test]
597    fn true_node_has_no_data_and_serializes_to_tag_only() {
598        assert_eq!(Tag::TRUE, Tag::from_word([ZERO, ZERO, ZERO, ZERO]));
599        assert_eq!(Tag::AND, Tag::from_word([ONE, ZERO, ZERO, ZERO]));
600        assert_eq!(Tag::CHUNKS, Tag::from_word([Felt::new_unchecked(2), ZERO, ZERO, ZERO]));
601        assert_eq!(Tag::TRUE.as_word(), [ZERO, ZERO, ZERO, ZERO]);
602        assert_eq!(Tag::AND.as_word(), [ONE, ZERO, ZERO, ZERO]);
603        assert_eq!(Tag::CHUNKS.as_word(), [Felt::new_unchecked(2), ZERO, ZERO, ZERO]);
604        assert_eq!(TRUE_DIGEST, Word::new([ZERO; 4]));
605
606        let true_node = Node::TRUE;
607        assert_eq!(true_node.tag(), Tag::TRUE);
608        assert!(true_node.is_true());
609        assert_eq!(true_node.digest(), TRUE_DIGEST);
610        assert_eq!(true_node.felt_len(), Tag::FELT_LEN);
611        assert_eq!(true_node.to_felts(), Tag::TRUE.as_word());
612        assert_eq!(true_node.storage_felt_len(), 0);
613        assert!(true_node.payload().as_data().is_err());
614        assert!(true_node.payload().as_value().is_err());
615    }
616
617    #[test]
618    fn data_is_non_empty() {
619        // Empty data cannot be constructed: TRUE is the only zero-payload node.
620        assert!(Payload::try_data(Vec::<DataChunk>::new()).is_err());
621        assert!(Node::try_data(TAG_A, Vec::<DataChunk>::new()).is_err());
622
623        let node = Node::try_data(TAG_A, alloc::vec![block(1), block(9)]).unwrap();
624        assert_eq!(node.payload().as_data().unwrap(), &[block(1), block(9)][..]);
625        assert!(NodeType::Data.validate_node(&node).is_ok());
626    }
627
628    #[test]
629    fn chunks_is_framework_data_and_non_empty() {
630        assert_eq!(Node::chunks(Vec::<DataChunk>::new()), Err(DeferredError::InvalidPayload));
631
632        let chunks = alloc::vec![block(1), block(9)];
633        let node = Node::chunks(chunks.clone()).unwrap();
634        assert_eq!(node.tag(), Tag::CHUNKS);
635        assert_eq!(node.payload().as_data().unwrap(), &chunks[..]);
636        assert!(NodeType::Data.validate_node(&node).is_ok());
637
638        let mut expected = Tag::CHUNKS.as_word().to_vec();
639        expected.extend_from_slice(&chunks[0]);
640        expected.extend_from_slice(&chunks[1]);
641        assert_eq!(node.to_felts(), expected);
642
643        let precompile_data = Node::try_data(TAG_A, chunks).unwrap();
644        assert_ne!(node.digest(), precompile_data.digest());
645    }
646
647    #[test]
648    fn chunks_from_bytes_packs_little_endian_u32s_and_zero_pads() {
649        assert_eq!(Node::PACKED_BYTES_PER_CHUNK, 32);
650
651        let empty = Node::chunks_from_bytes(&[]);
652        assert_eq!(empty.tag(), Tag::CHUNKS);
653        assert_eq!(empty.payload().as_data().unwrap(), &[[ZERO; 8]][..]);
654
655        let node = Node::chunks_from_bytes(&[1, 2, 3, 4, 5]);
656        let chunks = node.payload().as_data().unwrap();
657        assert_eq!(chunks.len(), 1);
658        assert_eq!(chunks[0][0], Felt::from_u32(u32::from_le_bytes([1, 2, 3, 4])));
659        assert_eq!(chunks[0][1], Felt::from_u32(5));
660        assert_eq!(&chunks[0][2..], &[ZERO; 6]);
661
662        let long_bytes = (0u8..33).collect::<Vec<_>>();
663        let long = Node::chunks_from_bytes(&long_bytes);
664        let chunks = long.payload().as_data().unwrap();
665        assert_eq!(chunks.len(), 2);
666        assert_eq!(chunks[0][0], Felt::from_u32(u32::from_le_bytes([0, 1, 2, 3])));
667        assert_eq!(chunks[0][7], Felt::from_u32(u32::from_le_bytes([28, 29, 30, 31])));
668        assert_eq!(chunks[1][0], Felt::from_u32(32));
669        assert_eq!(&chunks[1][1..], &[ZERO; 7]);
670    }
671
672    #[test]
673    fn value_is_data_one() {
674        let chunk = block(5);
675        let node = Node::value(TAG_A, chunk).unwrap();
676
677        // A value is a single data chunk, not a separate framework shape.
678        assert_eq!(node.payload().as_data().unwrap().len(), 1);
679        assert_eq!(node.payload().as_value().unwrap(), &chunk);
680
681        // Its external representation is `tag || one chunk`.
682        assert_eq!(node.felt_len(), Tag::FELT_LEN + Node::DATA_CHUNK_FELT_LEN);
683        let mut expected = TAG_A.as_word().to_vec();
684        expected.extend_from_slice(&chunk);
685        assert_eq!(node.to_felts(), expected);
686
687        // A single data chunk digests the same way whether constructed through value or data APIs.
688        let multi = Node::try_data(TAG_A, alloc::vec![chunk]).unwrap();
689        assert_eq!(node.digest(), multi.digest());
690    }
691
692    #[test]
693    fn data_shape_does_not_imply_one_chunk() {
694        let node = Node::try_data(TAG_A, alloc::vec![block(1), block(9)]).unwrap();
695        assert!(NodeType::Data.validate_node(&node).is_ok());
696        assert!(node.payload().as_value().is_err());
697        assert_eq!(node.payload().as_data().unwrap().len(), 2);
698        assert_eq!(node.felt_len(), Tag::FELT_LEN + Node::DATA_CHUNK_FELT_LEN * 2);
699    }
700
701    #[test]
702    fn digest_binds_tag_and_payload() {
703        let chunk = block(7);
704        let same = Node::value(TAG_A, chunk).unwrap();
705        let different_tag = Node::value(TAG_B, chunk).unwrap();
706        let different_payload = Node::value(TAG_A, block(8)).unwrap();
707
708        assert_ne!(same.digest(), different_tag.digest());
709        assert_ne!(same.digest(), different_payload.digest());
710    }
711
712    #[test]
713    fn join_round_trips_children_and_serializes() {
714        let lhs = Node::value(TAG_A, block(1)).unwrap().digest();
715        let rhs = Node::value(TAG_A, block(2)).unwrap().digest();
716        let join = Node::join(TAG_B, lhs, rhs).unwrap();
717
718        assert_eq!(join.payload().as_join().unwrap(), (lhs, rhs));
719        assert!(join.payload().as_data().is_err());
720
721        let mut payload = [ZERO; Node::DATA_CHUNK_FELT_LEN];
722        payload[..Word::NUM_ELEMENTS].copy_from_slice(lhs.as_elements());
723        payload[Word::NUM_ELEMENTS..].copy_from_slice(rhs.as_elements());
724
725        // External representation is `tag || lhs || rhs`.
726        assert_eq!(join.felt_len(), Tag::FELT_LEN + Node::DATA_CHUNK_FELT_LEN);
727        let mut expected = TAG_B.as_word().to_vec();
728        expected.extend_from_slice(&payload);
729        assert_eq!(join.to_felts(), expected);
730
731        assert_eq!(join.payload().as_chunks(), &[payload][..]);
732    }
733
734    #[test]
735    fn pair_list_is_non_empty() {
736        assert!(Payload::try_pair_list(Vec::<(Digest, Digest)>::new()).is_err());
737        assert!(Node::try_pair_list(TAG_A, Vec::<(Digest, Digest)>::new()).is_err());
738        assert!(Node::try_pair_list_chunks(TAG_A, Vec::<DataChunk>::new()).is_err());
739
740        let lhs = Node::value(TAG_A, block(1)).unwrap().digest();
741        let rhs = Node::value(TAG_A, block(2)).unwrap().digest();
742        let node = Node::try_pair_list(TAG_A, alloc::vec![(lhs, rhs)]).unwrap();
743        assert_eq!(node.payload().as_pair_list().unwrap(), alloc::vec![(lhs, rhs)]);
744    }
745
746    #[test]
747    fn pair_list_round_trips_pairs_children_and_serializes() {
748        let scalar_0 = Node::value(TAG_A, block(1)).unwrap().digest();
749        let point_0 = Node::value(TAG_A, block(2)).unwrap().digest();
750        let scalar_1 = Node::value(TAG_A, block(3)).unwrap().digest();
751        let point_1 = Node::value(TAG_A, block(4)).unwrap().digest();
752        let pairs = alloc::vec![(scalar_0, point_0), (scalar_1, point_1)];
753        let node = Node::try_pair_list(TAG_B, pairs.clone()).unwrap();
754
755        assert_eq!(node.payload().as_pair_list().unwrap(), pairs);
756        assert!(node.payload().as_data().is_err());
757        assert!(node.payload().as_join().is_err());
758        assert_eq!(
759            node.children().collect::<Vec<_>>(),
760            alloc::vec![scalar_0, point_0, scalar_1, point_1]
761        );
762
763        let mut chunk_0 = [ZERO; Node::DATA_CHUNK_FELT_LEN];
764        chunk_0[..Word::NUM_ELEMENTS].copy_from_slice(scalar_0.as_elements());
765        chunk_0[Word::NUM_ELEMENTS..].copy_from_slice(point_0.as_elements());
766        let mut chunk_1 = [ZERO; Node::DATA_CHUNK_FELT_LEN];
767        chunk_1[..Word::NUM_ELEMENTS].copy_from_slice(scalar_1.as_elements());
768        chunk_1[Word::NUM_ELEMENTS..].copy_from_slice(point_1.as_elements());
769
770        assert_eq!(node.felt_len(), Tag::FELT_LEN + Node::DATA_CHUNK_FELT_LEN * 2);
771        let mut expected = TAG_B.as_word().to_vec();
772        expected.extend_from_slice(&chunk_0);
773        expected.extend_from_slice(&chunk_1);
774        assert_eq!(node.to_felts(), expected);
775        assert_eq!(node.payload().as_chunks(), &[chunk_0, chunk_1][..]);
776
777        let data_node = Node::try_data(TAG_B, alloc::vec![chunk_0, chunk_1]).unwrap();
778        assert_eq!(node.digest(), data_node.digest(), "pair-list digest uses chunk hash layout");
779
780        assert!(NodeType::PairList.validate_node(&node).is_ok());
781        assert!(NodeType::Data.validate_node(&node).is_err());
782    }
783}
miden_core/deferred/node.rs

miden_core/deferred/
node.rs
