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        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
