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}