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}