zcash_history/
node_data.rs

1use alloc::vec::Vec;
2
3use primitive_types::U256;
4use zcash_encoding::CompactSize;
5
6use crate::Version;
7
8/// Maximum serialized size of the node metadata.
9pub const MAX_NODE_DATA_SIZE: usize = 32 + // subtree commitment
10    4 +  // start time
11    4 +  // end time
12    4 +  // start target
13    4 +  // end target
14    32 + // start sapling tree root
15    32 + // end sapling tree root
16    32 + // subtree total work
17    9 +  // start height (compact uint)
18    9 +  // end height (compact uint)
19    9 + // Sapling tx count (compact uint)
20    32 + // start Orchard tree root
21    32 + // end Orchard tree root
22    9 + // Orchard tx count (compact uint)
23    32 + // start Ironwood tree root
24    32 + // end Ironwood tree root
25    9; // Ironwood tx count (compact uint)
26// = total of 317
27
28/// V1 node metadata.
29#[repr(C)]
30#[derive(Debug, Clone, Default)]
31#[cfg_attr(test, derive(PartialEq, Eq))]
32pub struct NodeData {
33    /// Consensus branch id, should be provided by deserializing node.
34    pub consensus_branch_id: u32,
35    /// Subtree commitment - either block hash for leaves or hashsum of children for nodes.
36    pub subtree_commitment: [u8; 32],
37    /// Start time.
38    pub start_time: u32,
39    /// End time.
40    pub end_time: u32,
41    /// Start target.
42    pub start_target: u32,
43    /// End target.
44    pub end_target: u32,
45    /// Start sapling tree root.
46    pub start_sapling_root: [u8; 32],
47    /// End sapling tree root.
48    pub end_sapling_root: [u8; 32],
49    /// Part of tree total work.
50    pub subtree_total_work: U256,
51    /// Start height.
52    pub start_height: u64,
53    /// End height
54    pub end_height: u64,
55    /// Number of Sapling transactions.
56    pub sapling_tx: u64,
57}
58
59impl NodeData {
60    /// Combine two nodes metadata.
61    pub fn combine(left: &NodeData, right: &NodeData) -> NodeData {
62        crate::V1::combine(left, right)
63    }
64
65    pub(crate) fn combine_inner(
66        subtree_commitment: [u8; 32],
67        left: &NodeData,
68        right: &NodeData,
69    ) -> NodeData {
70        NodeData {
71            consensus_branch_id: left.consensus_branch_id,
72            subtree_commitment,
73            start_time: left.start_time,
74            end_time: right.end_time,
75            start_target: left.start_target,
76            end_target: right.end_target,
77            start_sapling_root: left.start_sapling_root,
78            end_sapling_root: right.end_sapling_root,
79            subtree_total_work: left.subtree_total_work + right.subtree_total_work,
80            start_height: left.start_height,
81            end_height: right.end_height,
82            sapling_tx: left.sapling_tx + right.sapling_tx,
83        }
84    }
85
86    /// Write to the byte representation.
87    pub fn write<W: corez::io::Write>(&self, w: &mut W) -> corez::io::Result<()> {
88        w.write_all(&self.subtree_commitment)?;
89        w.write_all(&self.start_time.to_le_bytes())?;
90        w.write_all(&self.end_time.to_le_bytes())?;
91        w.write_all(&self.start_target.to_le_bytes())?;
92        w.write_all(&self.end_target.to_le_bytes())?;
93        w.write_all(&self.start_sapling_root)?;
94        w.write_all(&self.end_sapling_root)?;
95
96        let mut work_buf = [0u8; 32];
97        self.subtree_total_work.to_little_endian(&mut work_buf[..]);
98        w.write_all(&work_buf)?;
99
100        CompactSize::write_unbounded(&mut *w, self.start_height)?;
101        CompactSize::write_unbounded(&mut *w, self.end_height)?;
102        CompactSize::write_unbounded(&mut *w, self.sapling_tx)?;
103        Ok(())
104    }
105
106    /// Read from the byte representation.
107    ///
108    /// # Errors
109    ///
110    /// Returns [`corez::io::ErrorKind::InvalidData`] if a compact-encoded field
111    /// uses a non-canonical encoding, or if the encoded height range is
112    /// descending or contains more blocks than can be represented by a `u64`.
113    pub fn read<R: corez::io::Read>(
114        consensus_branch_id: u32,
115        r: &mut R,
116    ) -> corez::io::Result<Self> {
117        let mut data = NodeData {
118            consensus_branch_id,
119            ..Default::default()
120        };
121        r.read_exact(&mut data.subtree_commitment)?;
122        let mut buf = [0u8; 4];
123        r.read_exact(&mut buf)?;
124        data.start_time = u32::from_le_bytes(buf);
125        r.read_exact(&mut buf)?;
126        data.end_time = u32::from_le_bytes(buf);
127        r.read_exact(&mut buf)?;
128        data.start_target = u32::from_le_bytes(buf);
129        r.read_exact(&mut buf)?;
130        data.end_target = u32::from_le_bytes(buf);
131        r.read_exact(&mut data.start_sapling_root)?;
132        r.read_exact(&mut data.end_sapling_root)?;
133
134        let mut work_buf = [0u8; 32];
135        r.read_exact(&mut work_buf)?;
136        data.subtree_total_work = U256::from_little_endian(&work_buf);
137
138        data.start_height = CompactSize::read_unbounded(&mut *r)?;
139        data.end_height = CompactSize::read_unbounded(&mut *r)?;
140        if data
141            .end_height
142            .checked_sub(data.start_height)
143            .and_then(|height_diff| height_diff.checked_add(1))
144            .is_none()
145        {
146            return Err(corez::io::Error::new(
147                corez::io::ErrorKind::InvalidData,
148                "history node height range does not contain a representable number of blocks",
149            ));
150        }
151        data.sapling_tx = CompactSize::read_unbounded(&mut *r)?;
152
153        Ok(data)
154    }
155
156    /// Convert to byte representation.
157    pub fn to_bytes(&self) -> Vec<u8> {
158        crate::V1::to_bytes(self)
159    }
160
161    /// Convert from byte representation.
162    ///
163    /// # Errors
164    ///
165    /// Returns [`corez::io::ErrorKind::InvalidData`] if a compact-encoded field
166    /// uses a non-canonical encoding, or if the encoded height range is
167    /// descending or contains more blocks than can be represented by a `u64`.
168    pub fn from_bytes<T: AsRef<[u8]>>(consensus_branch_id: u32, buf: T) -> corez::io::Result<Self> {
169        crate::V1::from_bytes(consensus_branch_id, buf)
170    }
171
172    /// Hash node metadata
173    pub fn hash(&self) -> [u8; 32] {
174        crate::V1::hash(self)
175    }
176}
177
178/// V2 node metadata.
179#[derive(Debug, Clone, Default)]
180#[cfg_attr(test, derive(PartialEq, Eq))]
181pub struct V2 {
182    /// The V1 node data retained in V2.
183    pub v1: NodeData,
184    /// Start Orchard tree root.
185    pub start_orchard_root: [u8; 32],
186    /// End Orchard tree root.
187    pub end_orchard_root: [u8; 32],
188    /// Number of Orchard transactions.
189    pub orchard_tx: u64,
190}
191
192impl V2 {
193    pub(crate) fn combine_inner(subtree_commitment: [u8; 32], left: &V2, right: &V2) -> V2 {
194        V2 {
195            v1: NodeData::combine_inner(subtree_commitment, &left.v1, &right.v1),
196            start_orchard_root: left.start_orchard_root,
197            end_orchard_root: right.end_orchard_root,
198            orchard_tx: left.orchard_tx + right.orchard_tx,
199        }
200    }
201
202    /// Write to the byte representation.
203    pub fn write<W: corez::io::Write>(&self, w: &mut W) -> corez::io::Result<()> {
204        self.v1.write(w)?;
205        w.write_all(&self.start_orchard_root)?;
206        w.write_all(&self.end_orchard_root)?;
207        CompactSize::write_unbounded(&mut *w, self.orchard_tx)?;
208        Ok(())
209    }
210
211    /// Read from the byte representation.
212    pub fn read<R: corez::io::Read>(
213        consensus_branch_id: u32,
214        r: &mut R,
215    ) -> corez::io::Result<Self> {
216        let mut data = V2 {
217            v1: NodeData::read(consensus_branch_id, r)?,
218            ..Default::default()
219        };
220        r.read_exact(&mut data.start_orchard_root)?;
221        r.read_exact(&mut data.end_orchard_root)?;
222        data.orchard_tx = CompactSize::read_unbounded(&mut *r)?;
223
224        Ok(data)
225    }
226}
227
228/// V3 node metadata.
229///
230/// This extends the NU5 history node format with metadata for the Ironwood shielded
231/// pool. Ironwood uses an Orchard-shaped note commitment tree, but is represented as a
232/// distinct pool in chain history.
233#[derive(Debug, Clone, Default)]
234#[cfg_attr(test, derive(PartialEq, Eq))]
235pub struct V3 {
236    /// The V2 node data retained in V3.
237    pub v2: V2,
238    /// Ironwood tree root at the start of this node's interval.
239    ///
240    /// Leaf nodes represent a single block, so their start and end roots are both
241    /// the final Ironwood note commitment tree root after the corresponding block.
242    /// Internal nodes carry the start root from their leftmost leaf.
243    pub start_ironwood_root: [u8; 32],
244    /// Ironwood tree root at the end of this node's interval.
245    ///
246    /// Leaf nodes represent a single block, so their start and end roots are both
247    /// the final Ironwood note commitment tree root after the corresponding block.
248    /// Internal nodes carry the end root from their rightmost leaf.
249    pub end_ironwood_root: [u8; 32],
250    /// Number of transactions containing an Ironwood bundle.
251    pub ironwood_tx: u64,
252}
253
254impl V3 {
255    pub(crate) fn combine_inner(subtree_commitment: [u8; 32], left: &V3, right: &V3) -> V3 {
256        V3 {
257            v2: V2::combine_inner(subtree_commitment, &left.v2, &right.v2),
258            start_ironwood_root: left.start_ironwood_root,
259            end_ironwood_root: right.end_ironwood_root,
260            ironwood_tx: left.ironwood_tx + right.ironwood_tx,
261        }
262    }
263
264    /// Write to the byte representation.
265    pub fn write<W: corez::io::Write>(&self, w: &mut W) -> corez::io::Result<()> {
266        self.v2.write(w)?;
267        w.write_all(&self.start_ironwood_root)?;
268        w.write_all(&self.end_ironwood_root)?;
269        CompactSize::write_unbounded(&mut *w, self.ironwood_tx)?;
270        Ok(())
271    }
272
273    /// Read from the byte representation.
274    pub fn read<R: corez::io::Read>(
275        consensus_branch_id: u32,
276        r: &mut R,
277    ) -> corez::io::Result<Self> {
278        let mut data = V3 {
279            v2: V2::read(consensus_branch_id, r)?,
280            ..Default::default()
281        };
282        r.read_exact(&mut data.start_ironwood_root)?;
283        r.read_exact(&mut data.end_ironwood_root)?;
284        data.ironwood_tx = CompactSize::read_unbounded(&mut *r)?;
285
286        Ok(data)
287    }
288}
289
290#[cfg(any(test, feature = "test-dependencies"))]
291pub mod testing {
292    use primitive_types::U256;
293    use proptest::array::uniform32;
294    use proptest::prelude::{any, prop_compose};
295
296    use super::NodeData;
297
298    prop_compose! {
299        pub fn arb_node_data()(
300            subtree_commitment in uniform32(any::<u8>()),
301            start_time in any::<u32>(),
302            end_time in any::<u32>(),
303            start_target in any::<u32>(),
304            end_target in any::<u32>(),
305            start_sapling_root in uniform32(any::<u8>()),
306            end_sapling_root in uniform32(any::<u8>()),
307            subtree_total_work in uniform32(any::<u8>()),
308            start_height in any::<u64>(),
309            end_height in any::<u64>(),
310            sapling_tx in any::<u64>(),
311        ) -> NodeData {
312            NodeData {
313                consensus_branch_id: 0,
314                subtree_commitment,
315                start_time,
316                end_time,
317                start_target,
318                end_target,
319                start_sapling_root,
320                end_sapling_root,
321                subtree_total_work: U256::from_little_endian(&subtree_total_work[..]),
322                start_height,
323                end_height,
324                sapling_tx
325            }
326        }
327    }
328}
329
330#[cfg(test)]
331mod tests {
332    use alloc::vec::Vec;
333
334    use super::testing::arb_node_data;
335    use proptest::prelude::*;
336
337    use primitive_types::U256;
338
339    use crate::{
340        Entry, EntryLink, MAX_ENTRY_SIZE, V1 as HistoryV1, V2 as HistoryV2, V3 as HistoryV3,
341        Version,
342    };
343
344    use super::{MAX_NODE_DATA_SIZE, NodeData, V2, V3};
345
346    fn node_data(start_height: u64, end_height: u64) -> NodeData {
347        NodeData {
348            consensus_branch_id: 1,
349            subtree_commitment: [1; 32],
350            start_time: 2,
351            end_time: 3,
352            start_target: 4,
353            end_target: 5,
354            start_sapling_root: [6; 32],
355            end_sapling_root: [7; 32],
356            subtree_total_work: U256::from(8u64),
357            start_height,
358            end_height,
359            sapling_tx: 9,
360        }
361    }
362
363    fn node_data_v2(start_height: u64, end_height: u64) -> V2 {
364        V2 {
365            v1: node_data(start_height, end_height),
366            start_orchard_root: [10; 32],
367            end_orchard_root: [11; 32],
368            orchard_tx: 12,
369        }
370    }
371
372    fn node_data_v3(start_height: u64, end_height: u64) -> V3 {
373        V3 {
374            v2: node_data_v2(start_height, end_height),
375            start_ironwood_root: [13; 32],
376            end_ironwood_root: [14; 32],
377            ironwood_tx: 15,
378        }
379    }
380
381    fn max_node_data() -> NodeData {
382        NodeData {
383            consensus_branch_id: u32::MAX,
384            subtree_commitment: [1; 32],
385            start_time: u32::MAX,
386            end_time: u32::MAX,
387            start_target: u32::MAX,
388            end_target: u32::MAX,
389            start_sapling_root: [2; 32],
390            end_sapling_root: [3; 32],
391            subtree_total_work: U256::MAX,
392            start_height: u64::MAX,
393            end_height: u64::MAX,
394            sapling_tx: u64::MAX,
395        }
396    }
397
398    fn max_node_data_v2() -> V2 {
399        V2 {
400            v1: max_node_data(),
401            start_orchard_root: [4; 32],
402            end_orchard_root: [5; 32],
403            orchard_tx: u64::MAX,
404        }
405    }
406
407    fn max_node_data_v3() -> V3 {
408        V3 {
409            v2: max_node_data_v2(),
410            start_ironwood_root: [6; 32],
411            end_ironwood_root: [7; 32],
412            ironwood_tx: u64::MAX,
413        }
414    }
415
416    fn v1_fixture_bytes() -> Vec<u8> {
417        let mut expected = vec![];
418        expected.extend_from_slice(&[1; 32]);
419        expected.extend_from_slice(&2u32.to_le_bytes());
420        expected.extend_from_slice(&3u32.to_le_bytes());
421        expected.extend_from_slice(&4u32.to_le_bytes());
422        expected.extend_from_slice(&5u32.to_le_bytes());
423        expected.extend_from_slice(&[6; 32]);
424        expected.extend_from_slice(&[7; 32]);
425        expected.extend_from_slice(&8u64.to_le_bytes());
426        expected.extend_from_slice(&[0; 24]);
427        expected.push(1);
428        expected.push(2);
429        expected.push(9);
430        expected
431    }
432
433    fn v2_fixture_bytes() -> Vec<u8> {
434        let mut expected = v1_fixture_bytes();
435        expected.extend_from_slice(&[10; 32]);
436        expected.extend_from_slice(&[11; 32]);
437        expected.push(12);
438        expected
439    }
440
441    fn v3_fixture_bytes() -> Vec<u8> {
442        let mut expected = v2_fixture_bytes();
443        expected.extend_from_slice(&[13; 32]);
444        expected.extend_from_slice(&[14; 32]);
445        expected.push(15);
446        expected
447    }
448
449    proptest! {
450        #[test]
451        fn serialization_round_trip(node_data in arb_node_data()) {
452            let decoded = NodeData::from_bytes(0, node_data.to_bytes());
453            let leaf_count = node_data
454                .end_height
455                .checked_sub(node_data.start_height)
456                .and_then(|height_diff| height_diff.checked_add(1));
457
458            if leaf_count.is_some() {
459                prop_assert_eq!(decoded.unwrap(), node_data);
460            } else {
461                prop_assert_eq!(
462                    decoded.unwrap_err().kind(),
463                    corez::io::ErrorKind::InvalidData
464                );
465            }
466        }
467    }
468
469    #[test]
470    fn genesis_height_round_trip() {
471        let node_data = NodeData {
472            start_height: 0,
473            end_height: 0,
474            ..Default::default()
475        };
476        let entry = Entry::<HistoryV1>::new_leaf(node_data);
477        let mut encoded = vec![];
478        entry.write(&mut encoded).unwrap();
479
480        assert_eq!(
481            Entry::<HistoryV1>::from_bytes(0, encoded)
482                .unwrap()
483                .leaf_count(),
484            1
485        );
486    }
487
488    #[test]
489    fn zero_start_height_combined_node_round_trip() {
490        // Regtest scenario: Heartwood activates at height 0, so the genesis
491        // leaf has start_height == 0. When two leaves are combined into a
492        // node spanning heights 0..=1, leaf_count() must not underflow.
493        let left = Entry::<HistoryV1>::new_leaf(node_data(0, 0));
494        let right = Entry::<HistoryV1>::new_leaf(node_data(1, 1));
495        let combined = HistoryV1::combine(left.data(), right.data());
496        let entry = Entry::<HistoryV1>::new(combined, EntryLink::Stored(0), EntryLink::Stored(1));
497        let mut encoded = vec![];
498        entry.write(&mut encoded).unwrap();
499
500        let decoded = Entry::<HistoryV1>::from_bytes(0, encoded).unwrap();
501        assert_eq!(decoded.leaf_count(), 2);
502        assert!(decoded.complete());
503    }
504
505    #[test]
506    fn invalid_height_ranges_are_rejected() {
507        for (start_height, end_height) in [
508            // Descending ranges.
509            (200, 5),
510            (u64::MAX, 5),
511            // Ascending, but the leaf count overflows a `u64`.
512            (0, u64::MAX),
513        ] {
514            let node_data = NodeData {
515                start_height,
516                end_height,
517                ..Default::default()
518            };
519            let entry = Entry::<HistoryV1>::new_leaf(node_data);
520            let mut encoded = vec![];
521            entry.write(&mut encoded).unwrap();
522            let error = match Entry::<HistoryV1>::from_bytes(0, encoded) {
523                Ok(_) => panic!("invalid height range was accepted"),
524                Err(error) => error,
525            };
526
527            assert_eq!(error.kind(), corez::io::ErrorKind::InvalidData);
528        }
529    }
530
531    #[test]
532    fn v1_and_v2_serialization_fixtures_are_stable() {
533        assert_eq!(HistoryV1::to_bytes(&node_data(1, 2)), v1_fixture_bytes());
534        assert_eq!(HistoryV2::to_bytes(&node_data_v2(1, 2)), v2_fixture_bytes());
535    }
536
537    #[test]
538    fn v3_serialization_round_trip() {
539        let node_data = node_data_v3(1, 2);
540
541        assert_eq!(
542            HistoryV3::from_bytes(1, v3_fixture_bytes()).unwrap(),
543            node_data
544        );
545        assert_eq!(HistoryV3::to_bytes(&node_data), v3_fixture_bytes());
546    }
547
548    #[test]
549    fn max_serialized_sizes_cover_all_versions() {
550        // ZIP 221 specifies that history nodes are at most 171 bytes before NU5
551        // and 244 bytes after NU5; those bounds require the compact-encoded
552        // fields to span the full `u64` range (a 9-byte compact encoding each).
553        assert_eq!(HistoryV1::to_bytes(&max_node_data()).len(), 171);
554        assert_eq!(HistoryV2::to_bytes(&max_node_data_v2()).len(), 244);
555        let max_v3_bytes = HistoryV3::to_bytes(&max_node_data_v3());
556        assert_eq!(max_v3_bytes.len(), MAX_NODE_DATA_SIZE);
557        assert_eq!(
558            HistoryV3::from_bytes(u32::MAX, &max_v3_bytes).unwrap(),
559            max_node_data_v3()
560        );
561        assert_eq!(MAX_NODE_DATA_SIZE, 317);
562
563        let entry = Entry::<HistoryV3>::new(
564            max_node_data_v3(),
565            EntryLink::Stored(u32::MAX),
566            EntryLink::Stored(u32::MAX),
567        );
568        let mut encoded = vec![];
569        entry.write(&mut encoded).unwrap();
570        assert_eq!(encoded.len(), MAX_ENTRY_SIZE);
571    }
572
573    #[test]
574    fn v3_combine_tracks_ironwood_fields() {
575        let mut left = node_data_v3(1, 1);
576        left.start_ironwood_root = [16; 32];
577        left.end_ironwood_root = [17; 32];
578        left.ironwood_tx = 18;
579
580        let mut right = node_data_v3(2, 2);
581        right.start_ironwood_root = [19; 32];
582        right.end_ironwood_root = [20; 32];
583        right.ironwood_tx = 21;
584
585        let combined = HistoryV3::combine(&left, &right);
586
587        assert_eq!(combined.v2.v1.start_height, 1);
588        assert_eq!(combined.v2.v1.end_height, 2);
589        assert_eq!(combined.start_ironwood_root, [16; 32]);
590        assert_eq!(combined.end_ironwood_root, [20; 32]);
591        assert_eq!(combined.ironwood_tx, 39);
592    }
593
594    #[test]
595    fn v3_combine_hash_commits_to_ironwood_fields() {
596        let left = node_data_v3(1, 1);
597        let right = node_data_v3(2, 2);
598        let base_hash = HistoryV3::combine(&left, &right).v2.v1.subtree_commitment;
599
600        let mut changed_start_root = left.clone();
601        changed_start_root.start_ironwood_root[0] ^= 1;
602        assert_ne!(
603            HistoryV3::combine(&changed_start_root, &right)
604                .v2
605                .v1
606                .subtree_commitment,
607            base_hash
608        );
609
610        let mut changed_left_end_root = left.clone();
611        changed_left_end_root.end_ironwood_root[0] ^= 1;
612        assert_ne!(
613            HistoryV3::combine(&changed_left_end_root, &right)
614                .v2
615                .v1
616                .subtree_commitment,
617            base_hash
618        );
619
620        let mut changed_right_start_root = right.clone();
621        changed_right_start_root.start_ironwood_root[0] ^= 1;
622        assert_ne!(
623            HistoryV3::combine(&left, &changed_right_start_root)
624                .v2
625                .v1
626                .subtree_commitment,
627            base_hash
628        );
629
630        let mut changed_end_root = right.clone();
631        changed_end_root.end_ironwood_root[0] ^= 1;
632        assert_ne!(
633            HistoryV3::combine(&left, &changed_end_root)
634                .v2
635                .v1
636                .subtree_commitment,
637            base_hash
638        );
639
640        let mut changed_tx_count = left.clone();
641        changed_tx_count.ironwood_tx += 1;
642        assert_ne!(
643            HistoryV3::combine(&changed_tx_count, &right)
644                .v2
645                .v1
646                .subtree_commitment,
647            base_hash
648        );
649
650        let mut redistributed_left_tx = left.clone();
651        let mut redistributed_right_tx = right;
652        redistributed_left_tx.ironwood_tx += 1;
653        redistributed_right_tx.ironwood_tx -= 1;
654        assert_ne!(
655            HistoryV3::combine(&redistributed_left_tx, &redistributed_right_tx)
656                .v2
657                .v1
658                .subtree_commitment,
659            base_hash
660        );
661    }
662}
zcash_history/node_data.rs

zcash_history/
node_data.rs
