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().cloned().collect();
92        let sapling_note_commitments: Vec<_> = block.sapling_note_commitments().cloned().collect();
93        let orchard_note_commitments: Vec<_> = block.orchard_note_commitments().cloned().collect();
94        let ironwood_note_commitments: Vec<_> =
95            block.ironwood_note_commitments().cloned().collect();
96
97        let mut sprout_result = None;
98        let mut sapling_result = None;
99        let mut orchard_result = None;
100        let mut ironwood_result = None;
101
102        rayon::in_place_scope_fifo(|scope| {
103            if !sprout_note_commitments.is_empty() {
104                scope.spawn_fifo(|_scope| {
105                    sprout_result = Some(Self::update_sprout_note_commitment_tree(
106                        sprout,
107                        sprout_note_commitments,
108                    ));
109                });
110            }
111
112            if !sapling_note_commitments.is_empty() {
113                scope.spawn_fifo(|_scope| {
114                    sapling_result = Some(Self::update_sapling_note_commitment_tree(
115                        sapling,
116                        sapling_note_commitments,
117                    ));
118                });
119            }
120
121            if !orchard_note_commitments.is_empty() {
122                scope.spawn_fifo(|_scope| {
123                    orchard_result = Some(Self::update_orchard_note_commitment_tree(
124                        orchard,
125                        orchard_note_commitments,
126                    ));
127                });
128            }
129
130            if !ironwood_note_commitments.is_empty() {
131                scope.spawn_fifo(|_scope| {
132                    ironwood_result = Some(Self::update_ironwood_note_commitment_tree(
133                        ironwood,
134                        ironwood_note_commitments,
135                    ));
136                });
137            }
138        });
139
140        if let Some(sprout_result) = sprout_result {
141            self.sprout = sprout_result?;
142        }
143
144        if let Some(sapling_result) = sapling_result {
145            let (sapling, subtree_root) = sapling_result?;
146            self.sapling = sapling;
147            self.sapling_subtree =
148                subtree_root.map(|(idx, node)| NoteCommitmentSubtree::new(idx, height, node));
149        };
150
151        if let Some(orchard_result) = orchard_result {
152            let (orchard, subtree_root) = orchard_result?;
153            self.orchard = orchard;
154            self.orchard_subtree =
155                subtree_root.map(|(idx, node)| NoteCommitmentSubtree::new(idx, height, node));
156        };
157
158        if let Some(ironwood_result) = ironwood_result {
159            let (ironwood, subtree_root) = ironwood_result?;
160            self.ironwood = ironwood;
161            self.ironwood_subtree =
162                subtree_root.map(|(idx, node)| NoteCommitmentSubtree::new(idx, height, node));
163        };
164
165        Ok(())
166    }
167
168    /// Update the sprout note commitment tree.
169    /// This method modifies the tree inside the `Arc`, if the `Arc` only has one reference.
170    fn update_sprout_note_commitment_tree(
171        mut sprout: Arc<sprout::tree::NoteCommitmentTree>,
172        sprout_note_commitments: Vec<sprout::NoteCommitment>,
173    ) -> Result<Arc<sprout::tree::NoteCommitmentTree>, NoteCommitmentTreeError> {
174        let sprout_nct = Arc::make_mut(&mut sprout);
175
176        for sprout_note_commitment in sprout_note_commitments {
177            sprout_nct.append(sprout_note_commitment)?;
178        }
179
180        // Re-calculate and cache the tree root.
181        let _ = sprout_nct.root();
182
183        Ok(sprout)
184    }
185
186    /// Update the sapling note commitment tree.
187    /// This method modifies the tree inside the `Arc`, if the `Arc` only has one reference.
188    #[allow(clippy::unwrap_in_result)]
189    pub fn update_sapling_note_commitment_tree(
190        mut sapling: Arc<sapling::tree::NoteCommitmentTree>,
191        sapling_note_commitments: Vec<sapling::tree::NoteCommitmentUpdate>,
192    ) -> Result<
193        (
194            Arc<sapling::tree::NoteCommitmentTree>,
195            Option<(NoteCommitmentSubtreeIndex, sapling_crypto::Node)>,
196        ),
197        NoteCommitmentTreeError,
198    > {
199        let sapling_nct = Arc::make_mut(&mut sapling);
200
201        // It is impossible for blocks to contain more than one level 16 sapling root:
202        // > [NU5 onward] nSpendsSapling, nOutputsSapling, and nActionsOrchard MUST all be less than 2^16.
203        // <https://zips.z.cash/protocol/protocol.pdf#txnconsensus>
204        //
205        // Before NU5, this limit holds due to the minimum size of Sapling outputs (948 bytes)
206        // and the maximum size of a block:
207        // > The size of a block MUST be less than or equal to 2000000 bytes.
208        // <https://zips.z.cash/protocol/protocol.pdf#blockheader>
209        // <https://zips.z.cash/protocol/protocol.pdf#txnencoding>
210        let mut subtree_root = None;
211
212        for sapling_note_commitment in sapling_note_commitments {
213            sapling_nct.append(sapling_note_commitment)?;
214
215            // Subtrees end heights come from the blocks they are completed in,
216            // so we check for new subtrees after appending the note.
217            // (If we check before, subtrees at the end of blocks have the wrong heights.)
218            if let Some(index_and_node) = sapling_nct.completed_subtree_index_and_root() {
219                subtree_root = Some(index_and_node);
220            }
221        }
222
223        // Re-calculate and cache the tree root.
224        let _ = sapling_nct.root();
225
226        Ok((sapling, subtree_root))
227    }
228
229    /// Update the orchard note commitment tree.
230    /// This method modifies the tree inside the `Arc`, if the `Arc` only has one reference.
231    #[allow(clippy::unwrap_in_result)]
232    pub fn update_orchard_note_commitment_tree(
233        mut orchard: Arc<orchard::tree::NoteCommitmentTree>,
234        orchard_note_commitments: Vec<orchard::tree::NoteCommitmentUpdate>,
235    ) -> Result<
236        (
237            Arc<orchard::tree::NoteCommitmentTree>,
238            Option<(NoteCommitmentSubtreeIndex, orchard::tree::Node)>,
239        ),
240        NoteCommitmentTreeError,
241    > {
242        let orchard_nct = Arc::make_mut(&mut orchard);
243
244        // It is impossible for blocks to contain more than one level 16 orchard root:
245        // > [NU5 onward] nSpendsSapling, nOutputsSapling, and nActionsOrchard MUST all be less than 2^16.
246        // <https://zips.z.cash/protocol/protocol.pdf#txnconsensus>
247        let mut subtree_root = None;
248
249        for orchard_note_commitment in orchard_note_commitments {
250            orchard_nct.append(orchard_note_commitment)?;
251
252            // Subtrees end heights come from the blocks they are completed in,
253            // so we check for new subtrees after appending the note.
254            // (If we check before, subtrees at the end of blocks have the wrong heights.)
255            if let Some(index_and_node) = orchard_nct.completed_subtree_index_and_root() {
256                subtree_root = Some(index_and_node);
257            }
258        }
259
260        // Re-calculate and cache the tree root.
261        let _ = orchard_nct.root();
262
263        Ok((orchard, subtree_root))
264    }
265
266    /// Update the ironwood note commitment tree.
267    /// This method modifies the tree inside the `Arc`, if the `Arc` only has one reference.
268    ///
269    /// Ironwood reuses the Orchard note commitment tree type but commits into a separate tree, so
270    /// this delegates to [`Self::update_orchard_note_commitment_tree`] and only re-tags the error
271    /// variant as [`NoteCommitmentTreeError::Ironwood`].
272    #[allow(clippy::unwrap_in_result)]
273    pub fn update_ironwood_note_commitment_tree(
274        ironwood: Arc<orchard::tree::NoteCommitmentTree>,
275        ironwood_note_commitments: Vec<orchard::tree::NoteCommitmentUpdate>,
276    ) -> Result<
277        (
278            Arc<orchard::tree::NoteCommitmentTree>,
279            Option<(NoteCommitmentSubtreeIndex, orchard::tree::Node)>,
280        ),
281        NoteCommitmentTreeError,
282    > {
283        Self::update_orchard_note_commitment_tree(ironwood, ironwood_note_commitments).map_err(
284            |err| match err {
285                NoteCommitmentTreeError::Orchard(inner) => NoteCommitmentTreeError::Ironwood(inner),
286                other => other,
287            },
288        )
289    }
290}
zebra_chain/parallel/tree.rs

zebra_chain/parallel/
tree.rs
