zebra_chain/parallel/
tree.rs

1//! Parallel note commitment tree update methods.
2
3use std::sync::Arc;
4
5use thiserror::Error;
6
7use crate::{
8    block::Block,
9    orchard, sapling, sprout,
10    subtree::{NoteCommitmentSubtree, NoteCommitmentSubtreeIndex},
11};
12
13/// An argument wrapper struct for note commitment trees.
14///
15/// The default instance represents the trees and subtrees that correspond to the genesis block.
16#[derive(Clone, Debug, Default, Eq, PartialEq)]
17pub struct NoteCommitmentTrees {
18    /// The sprout note commitment tree.
19    pub sprout: Arc<sprout::tree::NoteCommitmentTree>,
20
21    /// The sapling note commitment tree.
22    pub sapling: Arc<sapling::tree::NoteCommitmentTree>,
23
24    /// The sapling note commitment subtree.
25    pub sapling_subtree: Option<NoteCommitmentSubtree<sapling_crypto::Node>>,
26
27    /// The orchard note commitment tree.
28    pub orchard: Arc<orchard::tree::NoteCommitmentTree>,
29
30    /// The orchard note commitment subtree.
31    pub orchard_subtree: Option<NoteCommitmentSubtree<orchard::tree::Node>>,
32
33    /// The ironwood note commitment tree (NU6.3).
34    ///
35    /// Ironwood reuses the Orchard note commitment tree type (same Pallas/Sinsemilla MerkleCRH),
36    /// but commits Ironwood-pool notes into a separate tree. Stays empty until NU6.3.
37    pub ironwood: Arc<orchard::tree::NoteCommitmentTree>,
38
39    /// The ironwood note commitment subtree (NU6.3).
40    pub ironwood_subtree: Option<NoteCommitmentSubtree<orchard::tree::Node>>,
41}
42
43/// Note commitment tree errors.
44#[derive(Error, Copy, Clone, Debug, Eq, PartialEq, Hash)]
45pub enum NoteCommitmentTreeError {
46    /// A sprout tree error
47    #[error("sprout error: {0}")]
48    Sprout(#[from] sprout::tree::NoteCommitmentTreeError),
49
50    /// A sapling tree error
51    #[error("sapling error: {0}")]
52    Sapling(#[from] sapling::tree::NoteCommitmentTreeError),
53
54    /// A orchard tree error
55    #[error("orchard error: {0}")]
56    Orchard(#[from] orchard::tree::NoteCommitmentTreeError),
57
58    /// An ironwood tree error
59    ///
60    /// Ironwood reuses the Orchard tree type, so this wraps the same error type as
61    /// [`Self::Orchard`]; the distinct variant keeps the pool that failed identifiable.
62    #[error("ironwood error: {0}")]
63    Ironwood(#[source] orchard::tree::NoteCommitmentTreeError),
64}
65
66impl NoteCommitmentTrees {
67    /// Updates the note commitment trees using the transactions in `block`,
68    /// then re-calculates the cached tree roots, using parallel `rayon` threads.
69    ///
70    /// If any of the tree updates cause an error,
71    /// it will be returned at the end of the parallel batches.
72    #[allow(clippy::unwrap_in_result)]
73    pub fn update_trees_parallel(
74        &mut self,
75        block: &Arc<Block>,
76    ) -> Result<(), NoteCommitmentTreeError> {
77        let block = block.clone();
78        let height = block
79            .coinbase_height()
80            .expect("height was already validated");
81
82        // Prepare arguments for parallel threads
83        let NoteCommitmentTrees {
84            sprout,
85            sapling,
86            orchard,
87            ironwood,
88            ..
89        } = self.clone();
90
91        let sprout_note_commitments: Vec<_> = block.sprout_note_commitments().collect();
92        let sapling_note_commitments: Vec<_> = block.sapling_note_commitments().collect();
93        let orchard_note_commitments: Vec<_> = block.orchard_note_commitments().collect();
94        let ironwood_note_commitments: Vec<_> = block.ironwood_note_commitments().collect();
95
96        let mut sprout_result = None;
97        let mut sapling_result = None;
98        let mut orchard_result = None;
99        let mut ironwood_result = None;
100
101        rayon::in_place_scope_fifo(|scope| {
102            if !sprout_note_commitments.is_empty() {
103                scope.spawn_fifo(|_scope| {
104                    sprout_result = Some(Self::update_sprout_note_commitment_tree(
105                        sprout,
106                        sprout_note_commitments,
107                    ));
108                });
109            }
110
111            if !sapling_note_commitments.is_empty() {
112                scope.spawn_fifo(|_scope| {
113                    sapling_result = Some(Self::update_sapling_note_commitment_tree(
114                        sapling,
115                        sapling_note_commitments,
116                    ));
117                });
118            }
119
120            if !orchard_note_commitments.is_empty() {
121                scope.spawn_fifo(|_scope| {
122                    orchard_result = Some(Self::update_orchard_note_commitment_tree(
123                        orchard,
124                        orchard_note_commitments,
125                    ));
126                });
127            }
128
129            if !ironwood_note_commitments.is_empty() {
130                scope.spawn_fifo(|_scope| {
131                    ironwood_result = Some(Self::update_ironwood_note_commitment_tree(
132                        ironwood,
133                        ironwood_note_commitments,
134                    ));
135                });
136            }
137        });
138
139        if let Some(sprout_result) = sprout_result {
140            self.sprout = sprout_result?;
141        }
142
143        if let Some(sapling_result) = sapling_result {
144            let (sapling, subtree_root) = sapling_result?;
145            self.sapling = sapling;
146            self.sapling_subtree =
147                subtree_root.map(|(idx, node)| NoteCommitmentSubtree::new(idx, height, node));
148        };
149
150        if let Some(orchard_result) = orchard_result {
151            let (orchard, subtree_root) = orchard_result?;
152            self.orchard = orchard;
153            self.orchard_subtree =
154                subtree_root.map(|(idx, node)| NoteCommitmentSubtree::new(idx, height, node));
155        };
156
157        if let Some(ironwood_result) = ironwood_result {
158            let (ironwood, subtree_root) = ironwood_result?;
159            self.ironwood = ironwood;
160            self.ironwood_subtree =
161                subtree_root.map(|(idx, node)| NoteCommitmentSubtree::new(idx, height, node));
162        };
163
164        Ok(())
165    }
166
167    /// Update the sprout note commitment tree.
168    /// This method modifies the tree inside the `Arc`, if the `Arc` only has one reference.
169    fn update_sprout_note_commitment_tree(
170        mut sprout: Arc<sprout::tree::NoteCommitmentTree>,
171        sprout_note_commitments: Vec<sprout::NoteCommitment>,
172    ) -> Result<Arc<sprout::tree::NoteCommitmentTree>, NoteCommitmentTreeError> {
173        let sprout_nct = Arc::make_mut(&mut sprout);
174
175        for sprout_note_commitment in sprout_note_commitments {
176            sprout_nct.append(sprout_note_commitment)?;
177        }
178
179        // Re-calculate and cache the tree root.
180        let _ = sprout_nct.root();
181
182        Ok(sprout)
183    }
184
185    /// Update the sapling note commitment tree.
186    /// This method modifies the tree inside the `Arc`, if the `Arc` only has one reference.
187    #[allow(clippy::unwrap_in_result)]
188    pub fn update_sapling_note_commitment_tree(
189        mut sapling: Arc<sapling::tree::NoteCommitmentTree>,
190        sapling_note_commitments: Vec<sapling::tree::NoteCommitmentUpdate>,
191    ) -> Result<
192        (
193            Arc<sapling::tree::NoteCommitmentTree>,
194            Option<(NoteCommitmentSubtreeIndex, sapling_crypto::Node)>,
195        ),
196        NoteCommitmentTreeError,
197    > {
198        let sapling_nct = Arc::make_mut(&mut sapling);
199
200        // It is impossible for blocks to contain more than one level 16 sapling root:
201        // > [NU5 onward] nSpendsSapling, nOutputsSapling, and nActionsOrchard MUST all be less than 2^16.
202        // <https://zips.z.cash/protocol/protocol.pdf#txnconsensus>
203        //
204        // Before NU5, this limit holds due to the minimum size of Sapling outputs (948 bytes)
205        // and the maximum size of a block:
206        // > The size of a block MUST be less than or equal to 2000000 bytes.
207        // <https://zips.z.cash/protocol/protocol.pdf#blockheader>
208        // <https://zips.z.cash/protocol/protocol.pdf#txnencoding>
209        let mut subtree_root = None;
210
211        for sapling_note_commitment in sapling_note_commitments {
212            sapling_nct.append(sapling_note_commitment)?;
213
214            // Subtrees end heights come from the blocks they are completed in,
215            // so we check for new subtrees after appending the note.
216            // (If we check before, subtrees at the end of blocks have the wrong heights.)
217            if let Some(index_and_node) = sapling_nct.completed_subtree_index_and_root() {
218                subtree_root = Some(index_and_node);
219            }
220        }
221
222        // Re-calculate and cache the tree root.
223        let _ = sapling_nct.root();
224
225        Ok((sapling, subtree_root))
226    }
227
228    /// Update the orchard note commitment tree.
229    /// This method modifies the tree inside the `Arc`, if the `Arc` only has one reference.
230    #[allow(clippy::unwrap_in_result)]
231    pub fn update_orchard_note_commitment_tree(
232        mut orchard: Arc<orchard::tree::NoteCommitmentTree>,
233        orchard_note_commitments: Vec<orchard::tree::NoteCommitmentUpdate>,
234    ) -> Result<
235        (
236            Arc<orchard::tree::NoteCommitmentTree>,
237            Option<(NoteCommitmentSubtreeIndex, orchard::tree::Node)>,
238        ),
239        NoteCommitmentTreeError,
240    > {
241        let orchard_nct = Arc::make_mut(&mut orchard);
242
243        // It is impossible for blocks to contain more than one level 16 orchard root:
244        // > [NU5 onward] nSpendsSapling, nOutputsSapling, and nActionsOrchard MUST all be less than 2^16.
245        // <https://zips.z.cash/protocol/protocol.pdf#txnconsensus>
246        let mut subtree_root = None;
247
248        for orchard_note_commitment in orchard_note_commitments {
249            orchard_nct.append(orchard_note_commitment)?;
250
251            // Subtrees end heights come from the blocks they are completed in,
252            // so we check for new subtrees after appending the note.
253            // (If we check before, subtrees at the end of blocks have the wrong heights.)
254            if let Some(index_and_node) = orchard_nct.completed_subtree_index_and_root() {
255                subtree_root = Some(index_and_node);
256            }
257        }
258
259        // Re-calculate and cache the tree root.
260        let _ = orchard_nct.root();
261
262        Ok((orchard, subtree_root))
263    }
264
265    /// Update the ironwood note commitment tree.
266    /// This method modifies the tree inside the `Arc`, if the `Arc` only has one reference.
267    ///
268    /// Ironwood reuses the Orchard note commitment tree type but commits into a separate tree, so
269    /// this delegates to [`Self::update_orchard_note_commitment_tree`] and only re-tags the error
270    /// variant as [`NoteCommitmentTreeError::Ironwood`].
271    #[allow(clippy::unwrap_in_result)]
272    pub fn update_ironwood_note_commitment_tree(
273        ironwood: Arc<orchard::tree::NoteCommitmentTree>,
274        ironwood_note_commitments: Vec<orchard::tree::NoteCommitmentUpdate>,
275    ) -> Result<
276        (
277            Arc<orchard::tree::NoteCommitmentTree>,
278            Option<(NoteCommitmentSubtreeIndex, orchard::tree::Node)>,
279        ),
280        NoteCommitmentTreeError,
281    > {
282        Self::update_orchard_note_commitment_tree(ironwood, ironwood_note_commitments).map_err(
283            |err| match err {
284                NoteCommitmentTreeError::Orchard(inner) => NoteCommitmentTreeError::Ironwood(inner),
285                other => other,
286            },
287        )
288    }
289}
zebra_chain/parallel/tree.rs

zebra_chain/parallel/
tree.rs
