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

miden_core/deferred/
node.rs
