zcash_history/
node_data.rs

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

zcash_history/
node_data.rs
