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            .as_chunks::<{ Self::DATA_CHUNK_FELT_LEN }>()
371            .0
372            .iter()
373            .map(|chunk| core::array::from_fn(|i| chunk[i]))
374            .collect::<Vec<_>>();
375        Self::chunks(chunks).expect("chunks_from_bytes always creates at least one chunk")
376    }
377
378    /// Creates a join-shaped node that references two child digests.
379    pub fn join(tag: Tag, lhs: Digest, rhs: Digest) -> Result<Self, DeferredError> {
380        let tag = Self::require_precompile_tag(tag)?;
381        Ok(Self { tag, payload: Payload::join(lhs, rhs) })
382    }
383
384    /// Creates a pair-list-shaped node that references one or more structural digest pairs.
385    pub fn try_pair_list(
386        tag: Tag,
387        pairs: impl Into<Arc<[(Digest, Digest)]>>,
388    ) -> Result<Self, DeferredError> {
389        let tag = Self::require_precompile_tag(tag)?;
390        Ok(Self {
391            tag,
392            payload: Payload::try_pair_list(pairs)?,
393        })
394    }
395
396    /// Creates a pair-list-shaped node from non-empty chunks encoded as `lhs_digest || rhs_digest`.
397    pub fn try_pair_list_chunks(
398        tag: Tag,
399        chunks: impl Into<Arc<[DataChunk]>>,
400    ) -> Result<Self, DeferredError> {
401        let tag = Self::require_precompile_tag(tag)?;
402        Ok(Self {
403            tag,
404            payload: Payload::try_pair_list_chunks(chunks)?,
405        })
406    }
407
408    /// Creates a structural deferred-root AND step from the previous root and statement digest.
409    pub fn and(lhs: Digest, rhs: Digest) -> Self {
410        Self {
411            tag: Tag::AND,
412            payload: Payload::join(lhs, rhs),
413        }
414    }
415
416    fn require_precompile_tag(tag: Tag) -> Result<Tag, DeferredError> {
417        if tag.is_framework_reserved() {
418            return Err(DeferredError::InvalidTag);
419        }
420        Ok(tag)
421    }
422
423    /// Returns this node's tag.
424    pub fn tag(&self) -> Tag {
425        self.tag
426    }
427
428    /// Returns this node's payload.
429    pub fn payload(&self) -> &Payload {
430        &self.payload
431    }
432
433    /// Returns this node's structural child digests in payload order.
434    ///
435    /// This is infallible because [`Node`] constructors determine the payload representation:
436    ///
437    /// - data and TRUE nodes have no children;
438    /// - join nodes yield `lhs`, then `rhs`;
439    /// - pair-list nodes yield `lhs0`, `rhs0`, `lhs1`, `rhs1`, ...
440    pub(crate) fn children(&self) -> impl Iterator<Item = Digest> + '_ {
441        self.payload.children().into_iter()
442    }
443
444    /// Returns this node's payload if the node has `tag`.
445    pub fn payload_for_tag(&self, tag: Tag) -> Result<&Payload, DeferredError> {
446        if self.tag != tag {
447            return Err(DeferredError::InvalidPayload);
448        }
449        Ok(&self.payload)
450    }
451
452    /// Returns whether this node is structurally the canonical TRUE result.
453    pub fn is_true(&self) -> bool {
454        matches!(&self.payload.0, PayloadRepr::True) && self.tag == Tag::TRUE
455    }
456
457    /// Returns the field-element length of this node's canonical external representation.
458    pub fn felt_len(&self) -> usize {
459        Tag::FELT_LEN
460            .checked_add(
461                Self::DATA_CHUNK_FELT_LEN
462                    .checked_mul(self.payload.as_chunks().len())
463                    .expect("payload felt count overflow"),
464            )
465            .expect("node felt count overflow")
466    }
467
468    /// Returns the storage/budget footprint for durable state accounting.
469    pub(crate) fn storage_felt_len(&self) -> usize {
470        if self.is_true() { 0 } else { self.felt_len() }
471    }
472
473    /// Appends this node's canonical external representation to `target`.
474    pub fn write_into_felts(&self, target: &mut Vec<Felt>) {
475        target.extend_from_slice(&self.tag.as_word());
476        for chunk in self.payload.as_chunks() {
477            target.extend_from_slice(chunk);
478        }
479    }
480
481    /// Returns this node's canonical external representation.
482    pub fn to_felts(&self) -> Vec<Felt> {
483        let mut felts = Vec::with_capacity(self.felt_len());
484        self.write_into_felts(&mut felts);
485        felts
486    }
487
488    /// Computes the canonical digest used by both host code and Miden VM programs.
489    pub fn digest(&self) -> Digest {
490        if matches!(&self.payload.0, PayloadRepr::True) {
491            assert_eq!(self.tag, Tag::TRUE, "TRUE payload is only valid for Node::TRUE");
492            return TRUE_DIGEST;
493        }
494
495        let mut state = [ZERO; 12];
496        state[Self::DATA_CHUNK_FELT_LEN..Self::DATA_CHUNK_FELT_LEN + Tag::FELT_LEN]
497            .copy_from_slice(&self.tag.as_word());
498        for chunk in self.payload.as_chunks() {
499            state[0..Self::DATA_CHUNK_FELT_LEN].copy_from_slice(chunk);
500            Poseidon2::apply_permutation(&mut state);
501        }
502        Word::new([state[0], state[1], state[2], state[3]])
503    }
504}
505
506// NODE TYPE
507// ================================================================================================
508
509/// Framework shape a precompile declares for a recognized tag.
510///
511/// The shape tells registration and wire validation whether a body is non-empty opaque data, two
512/// child digests, or a non-empty list of digest pairs. It intentionally does not carry
513/// data/pair-list arity. Any semantic length encoded by a precompile's tag, such as a hash preimage
514/// byte length, is checked during precompile evaluation. `True` is the framework sentinel owned
515/// exclusively by [`Tag::TRUE`];
516/// precompiles never declare it. Predicate status is not a shape; predicates succeed by evaluating
517/// to [`Node::TRUE`].
518#[derive(Debug, Clone, Copy, PartialEq, Eq)]
519pub enum NodeType {
520    /// The framework TRUE sentinel, with no data payload.
521    True,
522    /// Non-empty opaque data.
523    Data,
524    /// Two child digests.
525    Join,
526    /// Non-empty structural digest pairs.
527    PairList,
528}
529
530impl NodeType {
531    /// Validates that a node's payload matches this declared framework shape.
532    pub(crate) fn validate_node(self, node: &Node) -> Result<(), DeferredError> {
533        match self {
534            Self::True if node.is_true() => Ok(()),
535            Self::Data if node.payload.as_data().is_ok() => Ok(()),
536            Self::Join if node.payload.as_join().is_ok() => Ok(()),
537            Self::PairList if node.payload.pair_list_chunks().is_ok() => Ok(()),
538            _ => Err(DeferredError::InvalidPayload),
539        }
540    }
541}
542
543#[cfg(test)]
544mod tests {
545    use alloc::vec::Vec;
546
547    use super::*;
548
549    const TAG_A: Tag = Tag::from_word([Felt::new_unchecked(42), ZERO, ZERO, ZERO]);
550    const TAG_B: Tag =
551        Tag::from_word([Felt::new_unchecked(42), ZERO, Felt::new_unchecked(1), ZERO]);
552
553    fn block(seed: u64) -> DataChunk {
554        core::array::from_fn(|i| Felt::new_unchecked(seed.wrapping_add(i as u64)))
555    }
556
557    #[test]
558    fn tag_precompile_rejects_framework_reserved_ids_but_from_word_is_raw() {
559        assert_eq!(Tag::precompile(Tag::TRUE.id(), [ZERO; 3]), Err(DeferredError::InvalidTag));
560        assert_eq!(Tag::precompile(Tag::AND.id(), [ZERO; 3]), Err(DeferredError::InvalidTag));
561        assert_eq!(Tag::precompile(Tag::CHUNKS.id(), [ZERO; 3]), Err(DeferredError::InvalidTag));
562        assert_eq!(
563            Tag::precompile(Tag::CHUNKS.id(), [Felt::new_unchecked(9), ZERO, ZERO]),
564            Err(DeferredError::InvalidTag)
565        );
566
567        let raw_true = Tag::from_word([ZERO, Felt::new_unchecked(9), ZERO, ZERO]);
568        assert_eq!(raw_true.id(), Tag::TRUE.id());
569        assert_eq!(raw_true.args(), [Felt::new_unchecked(9), ZERO, ZERO]);
570
571        let raw_chunks = Tag::from_word([Tag::CHUNKS.id(), Felt::new_unchecked(9), ZERO, ZERO]);
572        assert_eq!(raw_chunks.id(), Tag::CHUNKS.id());
573        assert_eq!(raw_chunks.args(), [Felt::new_unchecked(9), ZERO, ZERO]);
574    }
575
576    #[test]
577    fn public_node_constructors_reject_framework_reserved_tags() {
578        let chunk = block(1);
579        assert_eq!(Node::value(Tag::TRUE, chunk), Err(DeferredError::InvalidTag));
580        assert_eq!(Node::try_data(Tag::AND, alloc::vec![chunk]), Err(DeferredError::InvalidTag));
581        assert_eq!(Node::try_data(Tag::CHUNKS, alloc::vec![chunk]), Err(DeferredError::InvalidTag));
582        assert_eq!(Node::join(Tag::AND, TRUE_DIGEST, TRUE_DIGEST), Err(DeferredError::InvalidTag));
583        assert_eq!(
584            Node::try_pair_list(Tag::AND, alloc::vec![(TRUE_DIGEST, TRUE_DIGEST)]),
585            Err(DeferredError::InvalidTag)
586        );
587
588        let and = Node::and(TRUE_DIGEST, TRUE_DIGEST);
589        assert_eq!(and.tag(), Tag::AND);
590        assert_eq!(and.payload().as_join().unwrap(), (TRUE_DIGEST, TRUE_DIGEST));
591    }
592
593    #[test]
594    fn true_node_has_no_data_and_serializes_to_tag_only() {
595        assert_eq!(Tag::TRUE, Tag::from_word([ZERO, ZERO, ZERO, ZERO]));
596        assert_eq!(Tag::AND, Tag::from_word([ONE, ZERO, ZERO, ZERO]));
597        assert_eq!(Tag::CHUNKS, Tag::from_word([Felt::new_unchecked(2), ZERO, ZERO, ZERO]));
598        assert_eq!(Tag::TRUE.as_word(), [ZERO, ZERO, ZERO, ZERO]);
599        assert_eq!(Tag::AND.as_word(), [ONE, ZERO, ZERO, ZERO]);
600        assert_eq!(Tag::CHUNKS.as_word(), [Felt::new_unchecked(2), ZERO, ZERO, ZERO]);
601        assert_eq!(TRUE_DIGEST, Word::new([ZERO; 4]));
602
603        let true_node = Node::TRUE;
604        assert_eq!(true_node.tag(), Tag::TRUE);
605        assert!(true_node.is_true());
606        assert_eq!(true_node.digest(), TRUE_DIGEST);
607        assert_eq!(true_node.felt_len(), Tag::FELT_LEN);
608        assert_eq!(true_node.to_felts(), Tag::TRUE.as_word());
609        assert_eq!(true_node.storage_felt_len(), 0);
610        assert!(true_node.payload().as_data().is_err());
611        assert!(true_node.payload().as_value().is_err());
612    }
613
614    #[test]
615    fn data_is_non_empty() {
616        // Empty data cannot be constructed: TRUE is the only zero-payload node.
617        assert!(Payload::try_data(Vec::<DataChunk>::new()).is_err());
618        assert!(Node::try_data(TAG_A, Vec::<DataChunk>::new()).is_err());
619
620        let node = Node::try_data(TAG_A, alloc::vec![block(1), block(9)]).unwrap();
621        assert_eq!(node.payload().as_data().unwrap(), &[block(1), block(9)][..]);
622        assert!(NodeType::Data.validate_node(&node).is_ok());
623    }
624
625    #[test]
626    fn chunks_is_framework_data_and_non_empty() {
627        assert_eq!(Node::chunks(Vec::<DataChunk>::new()), Err(DeferredError::InvalidPayload));
628
629        let chunks = alloc::vec![block(1), block(9)];
630        let node = Node::chunks(chunks.clone()).unwrap();
631        assert_eq!(node.tag(), Tag::CHUNKS);
632        assert_eq!(node.payload().as_data().unwrap(), &chunks[..]);
633        assert!(NodeType::Data.validate_node(&node).is_ok());
634
635        let mut expected = Tag::CHUNKS.as_word().to_vec();
636        expected.extend_from_slice(&chunks[0]);
637        expected.extend_from_slice(&chunks[1]);
638        assert_eq!(node.to_felts(), expected);
639
640        let precompile_data = Node::try_data(TAG_A, chunks).unwrap();
641        assert_ne!(node.digest(), precompile_data.digest());
642    }
643
644    #[test]
645    fn chunks_from_bytes_packs_little_endian_u32s_and_zero_pads() {
646        assert_eq!(Node::PACKED_BYTES_PER_CHUNK, 32);
647
648        let empty = Node::chunks_from_bytes(&[]);
649        assert_eq!(empty.tag(), Tag::CHUNKS);
650        assert_eq!(empty.payload().as_data().unwrap(), &[[ZERO; 8]][..]);
651
652        let node = Node::chunks_from_bytes(&[1, 2, 3, 4, 5]);
653        let chunks = node.payload().as_data().unwrap();
654        assert_eq!(chunks.len(), 1);
655        assert_eq!(chunks[0][0], Felt::from_u32(u32::from_le_bytes([1, 2, 3, 4])));
656        assert_eq!(chunks[0][1], Felt::from_u32(5));
657        assert_eq!(&chunks[0][2..], &[ZERO; 6]);
658
659        let long_bytes = (0u8..33).collect::<Vec<_>>();
660        let long = Node::chunks_from_bytes(&long_bytes);
661        let chunks = long.payload().as_data().unwrap();
662        assert_eq!(chunks.len(), 2);
663        assert_eq!(chunks[0][0], Felt::from_u32(u32::from_le_bytes([0, 1, 2, 3])));
664        assert_eq!(chunks[0][7], Felt::from_u32(u32::from_le_bytes([28, 29, 30, 31])));
665        assert_eq!(chunks[1][0], Felt::from_u32(32));
666        assert_eq!(&chunks[1][1..], &[ZERO; 7]);
667    }
668
669    #[test]
670    fn value_is_data_one() {
671        let chunk = block(5);
672        let node = Node::value(TAG_A, chunk).unwrap();
673
674        // A value is a single data chunk, not a separate framework shape.
675        assert_eq!(node.payload().as_data().unwrap().len(), 1);
676        assert_eq!(node.payload().as_value().unwrap(), &chunk);
677
678        // Its external representation is `tag || one chunk`.
679        assert_eq!(node.felt_len(), Tag::FELT_LEN + Node::DATA_CHUNK_FELT_LEN);
680        let mut expected = TAG_A.as_word().to_vec();
681        expected.extend_from_slice(&chunk);
682        assert_eq!(node.to_felts(), expected);
683
684        // A single data chunk digests the same way whether constructed through value or data APIs.
685        let multi = Node::try_data(TAG_A, alloc::vec![chunk]).unwrap();
686        assert_eq!(node.digest(), multi.digest());
687    }
688
689    #[test]
690    fn data_shape_does_not_imply_one_chunk() {
691        let node = Node::try_data(TAG_A, alloc::vec![block(1), block(9)]).unwrap();
692        assert!(NodeType::Data.validate_node(&node).is_ok());
693        assert!(node.payload().as_value().is_err());
694        assert_eq!(node.payload().as_data().unwrap().len(), 2);
695        assert_eq!(node.felt_len(), Tag::FELT_LEN + Node::DATA_CHUNK_FELT_LEN * 2);
696    }
697
698    #[test]
699    fn digest_binds_tag_and_payload() {
700        let chunk = block(7);
701        let same = Node::value(TAG_A, chunk).unwrap();
702        let different_tag = Node::value(TAG_B, chunk).unwrap();
703        let different_payload = Node::value(TAG_A, block(8)).unwrap();
704
705        assert_ne!(same.digest(), different_tag.digest());
706        assert_ne!(same.digest(), different_payload.digest());
707    }
708
709    #[test]
710    fn join_round_trips_children_and_serializes() {
711        let lhs = Node::value(TAG_A, block(1)).unwrap().digest();
712        let rhs = Node::value(TAG_A, block(2)).unwrap().digest();
713        let join = Node::join(TAG_B, lhs, rhs).unwrap();
714
715        assert_eq!(join.payload().as_join().unwrap(), (lhs, rhs));
716        assert!(join.payload().as_data().is_err());
717
718        let mut payload = [ZERO; Node::DATA_CHUNK_FELT_LEN];
719        payload[..Word::NUM_ELEMENTS].copy_from_slice(lhs.as_elements());
720        payload[Word::NUM_ELEMENTS..].copy_from_slice(rhs.as_elements());
721
722        // External representation is `tag || lhs || rhs`.
723        assert_eq!(join.felt_len(), Tag::FELT_LEN + Node::DATA_CHUNK_FELT_LEN);
724        let mut expected = TAG_B.as_word().to_vec();
725        expected.extend_from_slice(&payload);
726        assert_eq!(join.to_felts(), expected);
727
728        assert_eq!(join.payload().as_chunks(), &[payload][..]);
729    }
730
731    #[test]
732    fn pair_list_is_non_empty() {
733        assert!(Payload::try_pair_list(Vec::<(Digest, Digest)>::new()).is_err());
734        assert!(Node::try_pair_list(TAG_A, Vec::<(Digest, Digest)>::new()).is_err());
735        assert!(Node::try_pair_list_chunks(TAG_A, Vec::<DataChunk>::new()).is_err());
736
737        let lhs = Node::value(TAG_A, block(1)).unwrap().digest();
738        let rhs = Node::value(TAG_A, block(2)).unwrap().digest();
739        let node = Node::try_pair_list(TAG_A, alloc::vec![(lhs, rhs)]).unwrap();
740        assert_eq!(node.payload().as_pair_list().unwrap(), alloc::vec![(lhs, rhs)]);
741    }
742
743    #[test]
744    fn pair_list_round_trips_pairs_children_and_serializes() {
745        let scalar_0 = Node::value(TAG_A, block(1)).unwrap().digest();
746        let point_0 = Node::value(TAG_A, block(2)).unwrap().digest();
747        let scalar_1 = Node::value(TAG_A, block(3)).unwrap().digest();
748        let point_1 = Node::value(TAG_A, block(4)).unwrap().digest();
749        let pairs = alloc::vec![(scalar_0, point_0), (scalar_1, point_1)];
750        let node = Node::try_pair_list(TAG_B, pairs.clone()).unwrap();
751
752        assert_eq!(node.payload().as_pair_list().unwrap(), pairs);
753        assert!(node.payload().as_data().is_err());
754        assert!(node.payload().as_join().is_err());
755        assert_eq!(
756            node.children().collect::<Vec<_>>(),
757            alloc::vec![scalar_0, point_0, scalar_1, point_1]
758        );
759
760        let mut chunk_0 = [ZERO; Node::DATA_CHUNK_FELT_LEN];
761        chunk_0[..Word::NUM_ELEMENTS].copy_from_slice(scalar_0.as_elements());
762        chunk_0[Word::NUM_ELEMENTS..].copy_from_slice(point_0.as_elements());
763        let mut chunk_1 = [ZERO; Node::DATA_CHUNK_FELT_LEN];
764        chunk_1[..Word::NUM_ELEMENTS].copy_from_slice(scalar_1.as_elements());
765        chunk_1[Word::NUM_ELEMENTS..].copy_from_slice(point_1.as_elements());
766
767        assert_eq!(node.felt_len(), Tag::FELT_LEN + Node::DATA_CHUNK_FELT_LEN * 2);
768        let mut expected = TAG_B.as_word().to_vec();
769        expected.extend_from_slice(&chunk_0);
770        expected.extend_from_slice(&chunk_1);
771        assert_eq!(node.to_felts(), expected);
772        assert_eq!(node.payload().as_chunks(), &[chunk_0, chunk_1][..]);
773
774        let data_node = Node::try_data(TAG_B, alloc::vec![chunk_0, chunk_1]).unwrap();
775        assert_eq!(node.digest(), data_node.digest(), "pair-list digest uses chunk hash layout");
776
777        assert!(NodeType::PairList.validate_node(&node).is_ok());
778        assert!(NodeType::Data.validate_node(&node).is_err());
779    }
780}
miden_core/deferred/node.rs

miden_core/deferred/
node.rs
