zebra_state/service/check/
utxo.rs

1//! Consensus rule checks for the finalized state.
2
3use std::collections::HashMap;
4
5use zebra_chain::{
6    amount,
7    transparent::{self, utxos_from_ordered_utxos, CoinbaseSpendRestriction::*},
8};
9
10use crate::{
11    constants::MIN_TRANSPARENT_COINBASE_MATURITY,
12    service::{finalized_state::ZebraDb, non_finalized_state::SpendingTransactionId},
13    SemanticallyVerifiedBlock,
14    ValidateContextError::{
15        self, DuplicateTransparentSpend, EarlyTransparentSpend, ImmatureTransparentCoinbaseSpend,
16        MissingTransparentOutput, UnshieldedTransparentCoinbaseSpend,
17    },
18};
19
20/// Lookup all the [`transparent::Utxo`]s spent by a [`SemanticallyVerifiedBlock`].
21/// If any of the spends are invalid, return an error.
22/// Otherwise, return the looked up UTXOs.
23///
24/// Checks for the following kinds of invalid spends:
25///
26/// Double-spends:
27/// - duplicate spends that are both in this block,
28/// - spends of an output that was spent by a previous block,
29///
30/// Missing spends:
31/// - spends of an output that hasn't been created yet,
32///   (in linear chain and transaction order),
33/// - spends of UTXOs that were never created in this chain,
34///
35/// Invalid spends:
36/// - spends of an immature transparent coinbase output,
37/// - unshielded spends of a transparent coinbase output.
38pub fn transparent_spend(
39    semantically_verified: &SemanticallyVerifiedBlock,
40    non_finalized_chain_unspent_utxos: &HashMap<transparent::OutPoint, transparent::OrderedUtxo>,
41    non_finalized_chain_spent_utxos: &HashMap<transparent::OutPoint, SpendingTransactionId>,
42    finalized_state: &ZebraDb,
43) -> Result<HashMap<transparent::OutPoint, transparent::OrderedUtxo>, ValidateContextError> {
44    let mut block_spends = HashMap::new();
45
46    for (spend_tx_index_in_block, transaction) in
47        semantically_verified.block.transactions.iter().enumerate()
48    {
49        // Coinbase inputs represent new coins,
50        // so there are no UTXOs to mark as spent.
51        let spends = transaction
52            .inputs()
53            .iter()
54            .filter_map(transparent::Input::outpoint);
55
56        for spend in spends {
57            let utxo = transparent_spend_chain_order(
58                spend,
59                spend_tx_index_in_block,
60                &semantically_verified.new_outputs,
61                non_finalized_chain_unspent_utxos,
62                non_finalized_chain_spent_utxos,
63                finalized_state,
64            )?;
65
66            // The state service returns UTXOs from pending blocks,
67            // which can be rejected by later contextual checks.
68            // This is a particular issue for v5 transactions,
69            // because their authorizing data is only bound to the block data
70            // during contextual validation (#2336).
71            //
72            // We don't want to use UTXOs from invalid pending blocks,
73            // so we check transparent coinbase maturity and shielding
74            // using known valid UTXOs during non-finalized chain validation.
75            let spend_restriction = transaction.coinbase_spend_restriction(
76                &finalized_state.network(),
77                semantically_verified.height,
78            );
79            transparent_coinbase_spend(spend, spend_restriction, utxo.as_ref())?;
80
81            // We don't delete the UTXOs until the block is committed,
82            // so we  need to check for duplicate spends within the same block.
83            //
84            // See `transparent_spend_chain_order` for the relevant consensus rule.
85            if block_spends.insert(spend, utxo).is_some() {
86                return Err(DuplicateTransparentSpend {
87                    outpoint: spend,
88                    location: "the same block",
89                });
90            }
91        }
92    }
93
94    remaining_transaction_value(semantically_verified, &block_spends)?;
95
96    Ok(block_spends)
97}
98
99/// Check that transparent spends occur in chain order.
100///
101/// Because we are in the non-finalized state, we need to check spends within the same block,
102/// spent non-finalized UTXOs, and unspent non-finalized and finalized UTXOs.
103///
104/// "Any input within this block can spend an output which also appears in this block
105/// (assuming the spend is otherwise valid).
106/// However, the TXID corresponding to the output must be placed at some point
107/// before the TXID corresponding to the input.
108/// This ensures that any program parsing block chain transactions linearly
109/// will encounter each output before it is used as an input."
110///
111/// <https://developer.bitcoin.org/reference/block_chain.html#merkle-trees>
112///
113/// "each output of a particular transaction
114/// can only be used as an input once in the block chain.
115/// Any subsequent reference is a forbidden double spend-
116/// an attempt to spend the same satoshis twice."
117///
118/// <https://developer.bitcoin.org/devguide/block_chain.html#introduction>
119///
120/// # Consensus
121///
122/// > Every non-null prevout MUST point to a unique UTXO in either a preceding block,
123/// > or a previous transaction in the same block.
124///
125/// <https://zips.z.cash/protocol/protocol.pdf#txnconsensus>
126fn transparent_spend_chain_order(
127    spend: transparent::OutPoint,
128    spend_tx_index_in_block: usize,
129    block_new_outputs: &HashMap<transparent::OutPoint, transparent::OrderedUtxo>,
130    non_finalized_chain_unspent_utxos: &HashMap<transparent::OutPoint, transparent::OrderedUtxo>,
131    non_finalized_chain_spent_utxos: &HashMap<transparent::OutPoint, SpendingTransactionId>,
132    finalized_state: &ZebraDb,
133) -> Result<transparent::OrderedUtxo, ValidateContextError> {
134    if let Some(output) = block_new_outputs.get(&spend) {
135        // reject the spend if it uses an output from this block,
136        // but the output was not created by an earlier transaction
137        //
138        // we know the spend is invalid, because transaction IDs are unique
139        //
140        // (transaction IDs also commit to transaction inputs,
141        // so it should be cryptographically impossible for a transaction
142        // to spend its own outputs)
143        if output.tx_index_in_block >= spend_tx_index_in_block {
144            return Err(EarlyTransparentSpend { outpoint: spend });
145        } else {
146            // a unique spend of a previous transaction's output is ok
147            return Ok(output.clone());
148        }
149    }
150
151    if non_finalized_chain_spent_utxos.contains_key(&spend) {
152        // reject the spend if its UTXO is already spent in the
153        // non-finalized parent chain
154        return Err(DuplicateTransparentSpend {
155            outpoint: spend,
156            location: "the non-finalized chain",
157        });
158    }
159
160    non_finalized_chain_unspent_utxos
161        .get(&spend)
162        .cloned()
163        .or_else(|| finalized_state.utxo(&spend))
164        // we don't keep spent UTXOs in the finalized state,
165        // so all we can say is that it's missing from both
166        // the finalized and non-finalized chains
167        // (it might have been spent in the finalized state,
168        // or it might never have existed in this chain)
169        .ok_or(MissingTransparentOutput {
170            outpoint: spend,
171            location: "the non-finalized and finalized chain",
172        })
173}
174
175/// Check that `utxo` is spendable, based on the coinbase `spend_restriction`.
176///
177/// # Consensus
178///
179/// > A transaction with one or more transparent inputs from coinbase transactions
180/// > MUST have no transparent outputs (i.e. tx_out_count MUST be 0).
181/// > Inputs from coinbase transactions include Founders’ Reward outputs and
182/// > funding stream outputs.
183///
184/// > A transaction MUST NOT spend a transparent output of a coinbase transaction
185/// > from a block less than 100 blocks prior to the spend.
186/// > Note that transparent outputs of coinbase transactions include
187/// > Founders’ Reward outputs and transparent funding stream outputs.
188///
189/// <https://zips.z.cash/protocol/protocol.pdf#txnconsensus>
190pub fn transparent_coinbase_spend(
191    outpoint: transparent::OutPoint,
192    spend_restriction: transparent::CoinbaseSpendRestriction,
193    utxo: &transparent::Utxo,
194) -> Result<(), ValidateContextError> {
195    if !utxo.from_coinbase {
196        return Ok(());
197    }
198
199    match spend_restriction {
200        CheckCoinbaseMaturity { spend_height } => {
201            let min_spend_height = utxo.height + MIN_TRANSPARENT_COINBASE_MATURITY.into();
202            let min_spend_height =
203                min_spend_height.expect("valid UTXOs have coinbase heights far below Height::MAX");
204            if spend_height >= min_spend_height {
205                Ok(())
206            } else {
207                Err(ImmatureTransparentCoinbaseSpend {
208                    outpoint,
209                    spend_height,
210                    min_spend_height,
211                    created_height: utxo.height,
212                })
213            }
214        }
215        DisallowCoinbaseSpend => Err(UnshieldedTransparentCoinbaseSpend { outpoint }),
216    }
217}
218
219/// Reject negative remaining transaction value.
220///
221/// "As in Bitcoin, the remaining value in the transparent transaction value pool
222/// of a non-coinbase transaction is available to miners as a fee.
223///
224/// The remaining value in the transparent transaction value pool of a
225/// coinbase transaction is destroyed.
226///
227/// Consensus rule: The remaining value in the transparent transaction value pool
228/// MUST be nonnegative."
229///
230/// <https://zips.z.cash/protocol/protocol.pdf#transactions>
231pub fn remaining_transaction_value(
232    semantically_verified: &SemanticallyVerifiedBlock,
233    utxos: &HashMap<transparent::OutPoint, transparent::OrderedUtxo>,
234) -> Result<(), ValidateContextError> {
235    for (tx_index_in_block, transaction) in
236        semantically_verified.block.transactions.iter().enumerate()
237    {
238        if transaction.is_coinbase() {
239            continue;
240        }
241
242        // Check the remaining transparent value pool for this transaction
243        let value_balance = transaction.value_balance(&utxos_from_ordered_utxos(utxos.clone()));
244        match value_balance {
245            Ok(vb) => match vb.remaining_transaction_value() {
246                Ok(_) => Ok(()),
247                Err(amount_error @ amount::Error::Constraint { .. })
248                    if amount_error.invalid_value() < 0 =>
249                {
250                    Err(ValidateContextError::NegativeRemainingTransactionValue {
251                        amount_error,
252                        height: semantically_verified.height,
253                        tx_index_in_block,
254                        transaction_hash: semantically_verified.transaction_hashes
255                            [tx_index_in_block],
256                    })
257                }
258                Err(amount_error) => {
259                    Err(ValidateContextError::CalculateRemainingTransactionValue {
260                        amount_error,
261                        height: semantically_verified.height,
262                        tx_index_in_block,
263                        transaction_hash: semantically_verified.transaction_hashes
264                            [tx_index_in_block],
265                    })
266                }
267            },
268            Err(value_balance_error) => {
269                Err(ValidateContextError::CalculateTransactionValueBalances {
270                    value_balance_error,
271                    height: semantically_verified.height,
272                    tx_index_in_block,
273                    transaction_hash: semantically_verified.transaction_hashes[tx_index_in_block],
274                })
275            }
276        }?
277    }
278
279    Ok(())
280}