zebra_state/service/check/nullifier.rs
1//! Checks for nullifier uniqueness.
2
3use std::{collections::HashMap, sync::Arc};
4
5use tracing::trace;
6use zebra_chain::transaction::Transaction;
7
8use crate::{
9 error::DuplicateNullifierError,
10 service::{
11 finalized_state::ZebraDb,
12 non_finalized_state::{Chain, SpendingTransactionId},
13 },
14 SemanticallyVerifiedBlock, ValidateContextError,
15};
16
17// Tidy up some doc links
18#[allow(unused_imports)]
19use crate::service;
20
21/// Reject double-spends of nullifers:
22/// - one from this [`SemanticallyVerifiedBlock`], and the other already committed to the
23/// [`FinalizedState`](service::FinalizedState).
24///
25/// (Duplicate non-finalized nullifiers are rejected during the chain update,
26/// see [`add_to_non_finalized_chain_unique`] for details.)
27///
28/// # Consensus
29///
30/// > A nullifier MUST NOT repeat either within a transaction,
31/// > or across transactions in a valid blockchain.
32/// > Sprout and Sapling and Orchard nullifiers are considered disjoint,
33/// > even if they have the same bit pattern.
34///
35/// <https://zips.z.cash/protocol/protocol.pdf#nullifierset>
36#[tracing::instrument(skip(semantically_verified, finalized_state))]
37pub(crate) fn no_duplicates_in_finalized_chain(
38 semantically_verified: &SemanticallyVerifiedBlock,
39 finalized_state: &ZebraDb,
40) -> Result<(), ValidateContextError> {
41 for nullifier in semantically_verified.block.sprout_nullifiers() {
42 if finalized_state.contains_sprout_nullifier(nullifier) {
43 Err(nullifier.duplicate_nullifier_error(true))?;
44 }
45 }
46
47 for nullifier in semantically_verified.block.sapling_nullifiers() {
48 if finalized_state.contains_sapling_nullifier(nullifier) {
49 Err(nullifier.duplicate_nullifier_error(true))?;
50 }
51 }
52
53 for nullifier in semantically_verified.block.orchard_nullifiers() {
54 if finalized_state.contains_orchard_nullifier(nullifier) {
55 Err(nullifier.duplicate_nullifier_error(true))?;
56 }
57 }
58
59 Ok(())
60}
61
62/// Accepts an iterator of revealed nullifiers, a predicate fn for checking if a nullifier is in
63/// in the finalized chain, and a predicate fn for checking if the nullifier is in the non-finalized chain
64///
65/// Returns `Err(DuplicateNullifierError)` if any of the `revealed_nullifiers` are found in the
66/// non-finalized or finalized chains.
67///
68/// Returns `Ok(())` if all the `revealed_nullifiers` have not been seen in either chain.
69fn find_duplicate_nullifier<'a, NullifierT, FinalizedStateContainsFn, NonFinalizedStateContainsFn>(
70 revealed_nullifiers: impl IntoIterator<Item = &'a NullifierT>,
71 finalized_chain_contains: FinalizedStateContainsFn,
72 non_finalized_chain_contains: Option<NonFinalizedStateContainsFn>,
73) -> Result<(), ValidateContextError>
74where
75 NullifierT: DuplicateNullifierError + 'a,
76 FinalizedStateContainsFn: Fn(&'a NullifierT) -> bool,
77 NonFinalizedStateContainsFn: Fn(&'a NullifierT) -> bool,
78{
79 for nullifier in revealed_nullifiers {
80 if let Some(true) = non_finalized_chain_contains.as_ref().map(|f| f(nullifier)) {
81 Err(nullifier.duplicate_nullifier_error(false))?
82 } else if finalized_chain_contains(nullifier) {
83 Err(nullifier.duplicate_nullifier_error(true))?
84 }
85 }
86
87 Ok(())
88}
89
90/// Reject double-spends of nullifiers:
91/// - one from this [`Transaction`], and the other already committed to the
92/// provided non-finalized [`Chain`] or [`ZebraDb`].
93///
94/// # Consensus
95///
96/// > A nullifier MUST NOT repeat either within a transaction,
97/// > or across transactions in a valid blockchain.
98/// > Sprout and Sapling and Orchard nullifiers are considered disjoint,
99/// > even if they have the same bit pattern.
100///
101/// <https://zips.z.cash/protocol/protocol.pdf#nullifierset>
102#[tracing::instrument(skip_all)]
103pub(crate) fn tx_no_duplicates_in_chain(
104 finalized_chain: &ZebraDb,
105 non_finalized_chain: Option<&Arc<Chain>>,
106 transaction: &Arc<Transaction>,
107) -> Result<(), ValidateContextError> {
108 find_duplicate_nullifier(
109 transaction.sprout_nullifiers(),
110 |nullifier| finalized_chain.contains_sprout_nullifier(nullifier),
111 non_finalized_chain
112 .map(|chain| |nullifier| chain.sprout_nullifiers.contains_key(nullifier)),
113 )?;
114
115 find_duplicate_nullifier(
116 transaction.sapling_nullifiers(),
117 |nullifier| finalized_chain.contains_sapling_nullifier(nullifier),
118 non_finalized_chain
119 .map(|chain| |nullifier| chain.sapling_nullifiers.contains_key(nullifier)),
120 )?;
121
122 find_duplicate_nullifier(
123 transaction.orchard_nullifiers(),
124 |nullifier| finalized_chain.contains_orchard_nullifier(nullifier),
125 non_finalized_chain
126 .map(|chain| |nullifier| chain.orchard_nullifiers.contains_key(nullifier)),
127 )?;
128
129 Ok(())
130}
131
132/// Reject double-spends of nullifers:
133/// - both within the same `JoinSplit` (sprout only),
134/// - from different `JoinSplit`s, [`sapling::Spend`][2]s or
135/// [`orchard::Action`][3]s in this [`Transaction`][1]'s shielded data, or
136/// - one from this shielded data, and another from:
137/// - a previous transaction in this [`Block`][4], or
138/// - a previous block in this non-finalized [`Chain`][5].
139///
140/// (Duplicate finalized nullifiers are rejected during service contextual validation,
141/// see [`no_duplicates_in_finalized_chain`] for details.)
142///
143/// # Consensus
144///
145/// > A nullifier MUST NOT repeat either within a transaction,
146/// > or across transactions in a valid blockchain.
147/// > Sprout and Sapling and Orchard nullifiers are considered disjoint,
148/// > even if they have the same bit pattern.
149///
150/// <https://zips.z.cash/protocol/protocol.pdf#nullifierset>
151///
152/// We comply with the "disjoint" rule by storing the nullifiers for each
153/// pool in separate sets (also with different types), so that even if
154/// different pools have nullifiers with same bit pattern, they won't be
155/// considered the same when determining uniqueness. This is enforced by the
156/// callers of this function.
157///
158/// [1]: zebra_chain::transaction::Transaction
159/// [2]: zebra_chain::sapling::Spend
160/// [3]: zebra_chain::orchard::Action
161/// [4]: zebra_chain::block::Block
162/// [5]: service::non_finalized_state::Chain
163#[tracing::instrument(skip(chain_nullifiers, shielded_data_nullifiers))]
164pub(crate) fn add_to_non_finalized_chain_unique<'block, NullifierT>(
165 chain_nullifiers: &mut HashMap<NullifierT, SpendingTransactionId>,
166 shielded_data_nullifiers: impl IntoIterator<Item = &'block NullifierT>,
167 revealing_tx_id: SpendingTransactionId,
168) -> Result<(), ValidateContextError>
169where
170 NullifierT: DuplicateNullifierError + Copy + std::fmt::Debug + Eq + std::hash::Hash + 'block,
171{
172 for nullifier in shielded_data_nullifiers.into_iter() {
173 trace!(?nullifier, "adding nullifier");
174
175 // reject the nullifier if it is already present in this non-finalized chain
176 if chain_nullifiers
177 .insert(*nullifier, revealing_tx_id)
178 .is_some()
179 {
180 Err(nullifier.duplicate_nullifier_error(false))?;
181 }
182 }
183
184 Ok(())
185}
186
187/// Remove nullifiers that were previously added to this non-finalized
188/// [`Chain`][1] by this shielded data.
189///
190/// "A note can change from being unspent to spent as a node’s view
191/// of the best valid block chain is extended by new transactions.
192///
193/// Also, block chain reorganizations can cause a node to switch
194/// to a different best valid block chain that does not contain
195/// the transaction in which a note was output"
196///
197/// <https://zips.z.cash/protocol/nu5.pdf#decryptivk>
198///
199/// Note: reorganizations can also change the best chain to one
200/// where a note was unspent, rather than spent.
201///
202/// # Panics
203///
204/// Panics if any nullifier is missing from the chain when we try to remove it.
205///
206/// Blocks with duplicate nullifiers are rejected by
207/// [`add_to_non_finalized_chain_unique`], so this shielded data should be the
208/// only shielded data that added this nullifier to this [`Chain`][1].
209///
210/// [1]: service::non_finalized_state::Chain
211#[tracing::instrument(skip(chain_nullifiers, shielded_data_nullifiers))]
212pub(crate) fn remove_from_non_finalized_chain<'block, NullifierT>(
213 chain_nullifiers: &mut HashMap<NullifierT, SpendingTransactionId>,
214 shielded_data_nullifiers: impl IntoIterator<Item = &'block NullifierT>,
215) where
216 NullifierT: std::fmt::Debug + Eq + std::hash::Hash + 'block,
217{
218 for nullifier in shielded_data_nullifiers.into_iter() {
219 trace!(?nullifier, "removing nullifier");
220
221 assert!(
222 chain_nullifiers.remove(nullifier).is_some(),
223 "nullifier must be present if block was added to chain"
224 );
225 }
226}