zebra_chain/primitives/
zcash_history.rs

1//! Contains code that interfaces with the zcash_history crate from
2//! librustzcash.
3
4// TODO: remove after this module gets to be used
5#![allow(missing_docs)]
6
7mod tests;
8
9use std::{collections::BTreeMap, io, sync::Arc};
10
11use serde_big_array::BigArray;
12pub use zcash_history::{V1, V2};
13
14use crate::{
15    block::{Block, ChainHistoryMmrRootHash},
16    orchard,
17    parameters::{Network, NetworkUpgrade},
18    sapling,
19};
20
21/// A trait to represent a version of `Tree`.
22pub trait Version: zcash_history::Version {
23    /// Convert a Block into the NodeData for this version.
24    fn block_to_history_node(
25        block: Arc<Block>,
26        network: &Network,
27        sapling_root: &sapling::tree::Root,
28        orchard_root: &orchard::tree::Root,
29    ) -> Self::NodeData;
30}
31
32/// A MMR Tree using zcash_history::Tree.
33///
34/// Currently it should not be used as a long-term data structure because it
35/// may grow without limits.
36pub struct Tree<V: zcash_history::Version> {
37    network: Network,
38    network_upgrade: NetworkUpgrade,
39    inner: zcash_history::Tree<V>,
40}
41
42/// An encoded tree node data.
43pub struct NodeData {
44    inner: [u8; zcash_history::MAX_NODE_DATA_SIZE],
45}
46
47impl From<&zcash_history::NodeData> for NodeData {
48    /// Convert from librustzcash.
49    fn from(inner_node: &zcash_history::NodeData) -> Self {
50        let mut node = NodeData {
51            inner: [0; zcash_history::MAX_NODE_DATA_SIZE],
52        };
53        inner_node
54            .write(&mut &mut node.inner[..])
55            .expect("buffer has the proper size");
56        node
57    }
58}
59
60/// An encoded entry in the tree.
61///
62/// Contains the node data and information about its position in the tree.
63#[derive(Clone, Debug, Serialize, Deserialize)]
64pub struct Entry {
65    #[serde(with = "BigArray")]
66    inner: [u8; zcash_history::MAX_ENTRY_SIZE],
67}
68
69impl Entry {
70    /// Create a leaf Entry for the given block, its network, and the root of its
71    /// note commitment trees.
72    ///
73    /// `sapling_root` is the root of the Sapling note commitment tree of the block.
74    /// `orchard_root` is the root of the Orchard note commitment tree of the block;
75    ///  (ignored for V1 trees).
76    fn new_leaf<V: Version>(
77        block: Arc<Block>,
78        network: &Network,
79        sapling_root: &sapling::tree::Root,
80        orchard_root: &orchard::tree::Root,
81    ) -> Self {
82        let node_data = V::block_to_history_node(block, network, sapling_root, orchard_root);
83        let inner_entry = zcash_history::Entry::<V>::new_leaf(node_data);
84        let mut entry = Entry {
85            inner: [0; zcash_history::MAX_ENTRY_SIZE],
86        };
87        inner_entry
88            .write(&mut &mut entry.inner[..])
89            .expect("buffer has the proper size");
90        entry
91    }
92}
93
94impl<V: Version> Tree<V> {
95    /// Create a MMR tree with the given length from the given cache of nodes.
96    ///
97    /// The `peaks` are the peaks of the MMR tree to build and their position in the
98    /// array representation of the tree.
99    /// The `extra` are extra nodes that enable removing nodes from the tree, and their position.
100    ///
101    /// Note that the length is usually larger than the length of `peaks` and `extra`, since
102    /// you don't need to pass every node, just the peaks of the tree (plus extra).
103    ///
104    /// # Panics
105    ///
106    /// Will panic if `peaks` is empty.
107    #[allow(clippy::unwrap_in_result)]
108    pub fn new_from_cache(
109        network: &Network,
110        network_upgrade: NetworkUpgrade,
111        length: u32,
112        peaks: &BTreeMap<u32, Entry>,
113        extra: &BTreeMap<u32, Entry>,
114    ) -> Result<Self, io::Error> {
115        let branch_id = network_upgrade
116            .branch_id()
117            .expect("unexpected pre-Overwinter MMR history tree");
118        let mut peaks_vec = Vec::new();
119        for (idx, entry) in peaks {
120            let inner_entry = zcash_history::Entry::from_bytes(branch_id.into(), entry.inner)?;
121            peaks_vec.push((*idx, inner_entry));
122        }
123        let mut extra_vec = Vec::new();
124        for (idx, entry) in extra {
125            let inner_entry = zcash_history::Entry::from_bytes(branch_id.into(), entry.inner)?;
126            extra_vec.push((*idx, inner_entry));
127        }
128        let inner = zcash_history::Tree::new(length, peaks_vec, extra_vec);
129        Ok(Tree {
130            network: network.clone(),
131            network_upgrade,
132            inner,
133        })
134    }
135
136    /// Create a single-node MMR tree for the given block.
137    ///
138    /// `sapling_root` is the root of the Sapling note commitment tree of the block.
139    /// `orchard_root` is the root of the Orchard note commitment tree of the block;
140    ///  (ignored for V1 trees).
141    #[allow(clippy::unwrap_in_result)]
142    pub fn new_from_block(
143        network: &Network,
144        block: Arc<Block>,
145        sapling_root: &sapling::tree::Root,
146        orchard_root: &orchard::tree::Root,
147    ) -> Result<(Self, Entry), io::Error> {
148        let height = block
149            .coinbase_height()
150            .expect("block must have coinbase height during contextual verification");
151        let network_upgrade = NetworkUpgrade::current(network, height);
152        let entry0 = Entry::new_leaf::<V>(block, network, sapling_root, orchard_root);
153        let mut peaks = BTreeMap::new();
154        peaks.insert(0u32, entry0);
155        Ok((
156            Tree::new_from_cache(network, network_upgrade, 1, &peaks, &BTreeMap::new())?,
157            peaks
158                .remove(&0u32)
159                .expect("must work since it was just added"),
160        ))
161    }
162
163    /// Append a new block to the tree, as a new leaf.
164    ///
165    /// `sapling_root` is the root of the Sapling note commitment tree of the block.
166    /// `orchard_root` is the root of the Orchard note commitment tree of the block;
167    ///  (ignored for V1 trees).
168    ///
169    /// Returns a vector of nodes added to the tree (leaf + internal nodes).
170    ///
171    /// # Panics
172    ///
173    /// Panics if the network upgrade of the given block is different from
174    /// the network upgrade of the other blocks in the tree.
175    #[allow(clippy::unwrap_in_result)]
176    pub fn append_leaf(
177        &mut self,
178        block: Arc<Block>,
179        sapling_root: &sapling::tree::Root,
180        orchard_root: &orchard::tree::Root,
181    ) -> Result<Vec<Entry>, zcash_history::Error> {
182        let height = block
183            .coinbase_height()
184            .expect("block must have coinbase height during contextual verification");
185        let network_upgrade = NetworkUpgrade::current(&self.network, height);
186
187        assert!(
188            network_upgrade == self.network_upgrade,
189            "added block from network upgrade {:?} but history tree is restricted to {:?}",
190            network_upgrade,
191            self.network_upgrade
192        );
193
194        let node_data = V::block_to_history_node(block, &self.network, sapling_root, orchard_root);
195        let appended = self.inner.append_leaf(node_data)?;
196
197        let mut new_nodes = Vec::new();
198        for entry_link in appended {
199            let mut entry = Entry {
200                inner: [0; zcash_history::MAX_ENTRY_SIZE],
201            };
202            self.inner
203                .resolve_link(entry_link)
204                .expect("entry was just generated so it must be valid")
205                .node()
206                .write(&mut &mut entry.inner[..])
207                .expect("buffer was created with enough capacity");
208            new_nodes.push(entry);
209        }
210        Ok(new_nodes)
211    }
212    /// Return the root hash of the tree, i.e. `hashChainHistoryRoot`.
213    pub fn hash(&self) -> ChainHistoryMmrRootHash {
214        // Both append_leaf() and truncate_leaf() leave a root node, so it should
215        // always exist.
216        V::hash(self.inner.root_node().expect("must have root node").data()).into()
217    }
218}
219
220impl<V: zcash_history::Version> std::fmt::Debug for Tree<V> {
221    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
222        f.debug_struct("Tree")
223            .field("network", &self.network)
224            .field("network_upgrade", &self.network_upgrade)
225            .finish()
226    }
227}
228
229impl Version for zcash_history::V1 {
230    /// Convert a Block into a V1::NodeData used in the MMR tree.
231    ///
232    /// `sapling_root` is the root of the Sapling note commitment tree of the block.
233    /// `orchard_root` is ignored.
234    fn block_to_history_node(
235        block: Arc<Block>,
236        network: &Network,
237        sapling_root: &sapling::tree::Root,
238        _orchard_root: &orchard::tree::Root,
239    ) -> Self::NodeData {
240        let height = block
241            .coinbase_height()
242            .expect("block must have coinbase height during contextual verification");
243        let network_upgrade = NetworkUpgrade::current(network, height);
244        let branch_id = network_upgrade
245            .branch_id()
246            .expect("must have branch ID for chain history network upgrades");
247        let block_hash = block.hash().0;
248        let time: u32 = block
249            .header
250            .time
251            .timestamp()
252            .try_into()
253            .expect("deserialized and generated timestamps are u32 values");
254        let target = block.header.difficulty_threshold.0;
255        let sapling_root: [u8; 32] = sapling_root.into();
256        let work = block
257            .header
258            .difficulty_threshold
259            .to_work()
260            .expect("work must be valid during contextual verification");
261        // There is no direct `std::primitive::u128` to `bigint::U256` conversion
262        let work = primitive_types::U256::from_big_endian(&work.as_u128().to_be_bytes());
263
264        let sapling_tx_count = block.sapling_transactions_count();
265
266        match network_upgrade {
267            NetworkUpgrade::Genesis
268            | NetworkUpgrade::BeforeOverwinter
269            | NetworkUpgrade::Overwinter
270            | NetworkUpgrade::Sapling
271            | NetworkUpgrade::Blossom => {
272                panic!("HistoryTree does not exist for pre-Heartwood upgrades")
273            }
274            // Nu5 is included because this function is called by the V2 implementation
275            // since the V1::NodeData is included inside the V2::NodeData.
276            NetworkUpgrade::Heartwood
277            | NetworkUpgrade::Canopy
278            | NetworkUpgrade::Nu5
279            | NetworkUpgrade::Nu6
280            | NetworkUpgrade::Nu6_1
281            | NetworkUpgrade::Nu7 => zcash_history::NodeData {
282                consensus_branch_id: branch_id.into(),
283                subtree_commitment: block_hash,
284                start_time: time,
285                end_time: time,
286                start_target: target,
287                end_target: target,
288                start_sapling_root: sapling_root,
289                end_sapling_root: sapling_root,
290                subtree_total_work: work,
291                start_height: height.0 as u64,
292                end_height: height.0 as u64,
293                sapling_tx: sapling_tx_count,
294            },
295        }
296    }
297}
298
299impl Version for V2 {
300    /// Convert a Block into a V1::NodeData used in the MMR tree.
301    ///
302    /// `sapling_root` is the root of the Sapling note commitment tree of the block.
303    /// `orchard_root` is the root of the Orchard note commitment tree of the block.
304    fn block_to_history_node(
305        block: Arc<Block>,
306        network: &Network,
307        sapling_root: &sapling::tree::Root,
308        orchard_root: &orchard::tree::Root,
309    ) -> Self::NodeData {
310        let orchard_tx_count = block.orchard_transactions_count();
311        let node_data_v1 = V1::block_to_history_node(block, network, sapling_root, orchard_root);
312        let orchard_root: [u8; 32] = orchard_root.into();
313        Self::NodeData {
314            v1: node_data_v1,
315            start_orchard_root: orchard_root,
316            end_orchard_root: orchard_root,
317            orchard_tx: orchard_tx_count,
318        }
319    }
320}