diff --git a/chronik/bitcoinsuite-core/src/tx/tx.rs b/chronik/bitcoinsuite-core/src/tx/tx.rs index ce9028c0e..c1a53e535 100644 --- a/chronik/bitcoinsuite-core/src/tx/tx.rs +++ b/chronik/bitcoinsuite-core/src/tx/tx.rs @@ -1,126 +1,135 @@ // Copyright (c) 2023 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. use crate::{script::Script, tx::TxId}; /// CTransaction, a Bitcoin transaction. /// /// ``` /// # use bitcoinsuite_core::tx::{Tx, TxId, TxMut}; /// let txid = TxId::from([3; 32]); /// let tx = Tx::with_txid( /// txid, /// TxMut { /// version: 1, /// inputs: vec![], /// outputs: vec![], /// locktime: 0, /// }, /// ); /// assert_eq!(tx.txid(), txid); /// assert_eq!(tx.version, 1); /// assert_eq!(tx.inputs, vec![]); /// assert_eq!(tx.outputs, vec![]); /// assert_eq!(tx.locktime, 0); /// ``` /// /// Immutable version of [`TxMut`], so this will fail: /// ```compile_fail /// # use bitcoinsuite_core::tx::Tx; /// let mut tx = Tx::default(); /// tx.version = 1; /// ``` #[derive(Clone, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)] pub struct Tx { txid: TxId, tx: TxMut, } /// Bitcoin transaction. Mutable version of [`Tx`], like CMutableTransaction. /// /// The biggest difference is that it doesn't have a txid() method, which we /// cannot know without hashing the tx every time, which would be expensive to /// compute. #[derive(Clone, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)] pub struct TxMut { /// nVersion of the tx. pub version: i32, /// Tx inputs. pub inputs: Vec, /// Tx outputs. pub outputs: Vec, /// Locktime of the tx. pub locktime: u32, } /// COutPoint, pointing to a coin being spent. #[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)] pub struct OutPoint { /// TxId of the output of the coin. pub txid: TxId, /// Index in the outputs of the tx of the coin. pub out_idx: u32, } +/// Points to an input spending a coin. +#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)] +pub struct SpentBy { + /// TxId of the tx with the input. + pub txid: TxId, + /// Index in the inputs of the tx. + pub input_idx: u32, +} + /// CTxIn, spending an unspent output. #[derive(Clone, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)] pub struct TxInput { /// Points to an output being spent. pub prev_out: OutPoint, /// scriptSig unlocking the output. pub script: Script, /// nSequence. pub sequence: u32, /// Coin being spent by this tx. /// May be [`None`] for coinbase txs or if the spent coin is unknown. pub coin: Option, } /// CTxOut, creating a new output. #[derive(Clone, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)] pub struct TxOutput { /// Value of the output. pub value: i64, /// Script locking the output. pub script: Script, } /// Coin, can be spent by providing a valid unlocking script. #[derive(Clone, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)] pub struct Coin { /// Output, locking the coins. pub output: TxOutput, /// Height of the coin in the chain. pub height: i32, /// Whether the coin is a coinbase. pub is_coinbase: bool, } impl Tx { /// Create a new [`Tx`] with a given [`TxId`] and [`TxMut`]. /// /// It is the responsibility of the caller to ensure the `txid` matches /// `tx`. pub fn with_txid(txid: TxId, tx: TxMut) -> Self { Tx { txid, tx } } /// [`TxId`] of this [`Tx`]. pub fn txid(&self) -> TxId { self.txid } /// Like [`Tx::txid`], but as a reference. pub fn txid_ref(&self) -> &TxId { &self.txid } } impl std::ops::Deref for Tx { type Target = TxMut; fn deref(&self) -> &Self::Target { &self.tx } } diff --git a/chronik/chronik-db/src/mem/mod.rs b/chronik/chronik-db/src/mem/mod.rs index d6be3cb7c..ec9e2ca48 100644 --- a/chronik/chronik-db/src/mem/mod.rs +++ b/chronik/chronik-db/src/mem/mod.rs @@ -1,11 +1,13 @@ // Copyright (c) 2023 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. //! Module containing structs to index the mempool. mod group_history; mod mempool; +mod spent_by; pub use self::group_history::*; pub use self::mempool::*; +pub use self::spent_by::*; diff --git a/chronik/chronik-db/src/mem/spent_by.rs b/chronik/chronik-db/src/mem/spent_by.rs new file mode 100644 index 000000000..d0445ce9e --- /dev/null +++ b/chronik/chronik-db/src/mem/spent_by.rs @@ -0,0 +1,313 @@ +// Copyright (c) 2023 The Bitcoin developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +use std::collections::{btree_map::Entry, BTreeMap, HashMap}; + +use abc_rust_error::Result; +use bitcoinsuite_core::tx::{OutPoint, SpentBy, TxId}; +use thiserror::Error; + +use crate::mem::MempoolTx; + +/// Store which outputs have been spent by which mempool tx. +/// +/// Spent outputs don't necessarily have to be of mempool txs. +#[derive(Clone, Debug, Default, Eq, PartialEq)] +pub struct MempoolSpentBy { + spent_by: HashMap>, +} + +/// Error indicating that something went wrong with [`MempoolSpentBy`]. +#[derive(Debug, Error, PartialEq, Eq)] +pub enum MempoolSpentByError { + /// Tried adding a spent-by entry, but it's already marked as spent by + /// another entry. + #[error( + "Inconsistent mempool: Duplicate spend by entry for {outpoint:?}: \ + {existing:?} already exists, but tried to add {new:?}" + )] + DuplicateSpentByEntry { + /// Which output has been spent + outpoint: OutPoint, + /// Entry already present in the mempool. + existing: SpentBy, + /// Entry we tried to add. + new: SpentBy, + }, + + /// Tried removing a spent-by entry, but it doesn't match what we got from + /// the disconnected block. + #[error( + "Inconsistent mempool: Mismatched spent-by entry for {outpoint:?}: \ + Expected {expected:?} to be present, but got {actual:?}" + )] + MismatchedSpentByEntry { + /// Tried removing a spent-by entry for this output. + outpoint: OutPoint, + /// Entry we expected based on the removed tx. + expected: SpentBy, + /// Entry actually found in the mempool. + actual: SpentBy, + }, + + /// Tried removing a spent-by entry, but it doesn't exist. + #[error( + "Inconsistent mempool: Missing spend by entry for {outpoint:?}: \ + Expected {expected:?} to be present, but none found" + )] + MissingSpentByEntry { + /// Tried removing a spent-by entry for this output. + outpoint: OutPoint, + /// Entry we expected to be present based on the disconnected block. + expected: SpentBy, + }, +} + +use self::MempoolSpentByError::*; + +impl MempoolSpentBy { + /// Mark all the outputs spent by this tx. + /// + /// Fails if a spent output already has been marked as spent. + pub fn insert(&mut self, tx: &MempoolTx) -> Result<()> { + for (input_idx, input) in tx.tx.inputs.iter().enumerate() { + let entries = self.spent_by.entry(input.prev_out.txid).or_default(); + let new_entry = SpentBy { + txid: tx.tx.txid(), + input_idx: input_idx as u32, + }; + match entries.entry(input.prev_out.out_idx) { + Entry::Vacant(entry) => { + entry.insert(new_entry); + } + Entry::Occupied(entry) => { + return Err(DuplicateSpentByEntry { + outpoint: OutPoint { + txid: input.prev_out.txid, + out_idx: input.prev_out.out_idx, + }, + existing: *entry.get(), + new: new_entry, + } + .into()); + } + } + } + Ok(()) + } + + /// Un-mark all the outputs spent by this tx as spent. + /// + /// Only to be used when the tx has been added to the mempool before. + pub fn remove(&mut self, tx: &MempoolTx) -> Result<()> { + for (input_idx, input) in tx.tx.inputs.iter().enumerate() { + let spent_outpoint = OutPoint { + txid: input.prev_out.txid, + out_idx: input.prev_out.out_idx, + }; + let entries = self.spent_by.entry(spent_outpoint.txid).or_default(); + let removed_entry = SpentBy { + txid: tx.tx.txid(), + input_idx: input_idx as u32, + }; + match entries.entry(spent_outpoint.out_idx) { + Entry::Vacant(_) => { + return Err(MissingSpentByEntry { + outpoint: spent_outpoint, + expected: removed_entry, + } + .into()); + } + Entry::Occupied(entry) => { + if *entry.get() != removed_entry { + return Err(MismatchedSpentByEntry { + outpoint: spent_outpoint, + expected: removed_entry, + actual: *entry.get(), + } + .into()); + } + entry.remove(); + } + } + if entries.is_empty() { + self.spent_by.remove(&spent_outpoint.txid).unwrap(); + } + } + Ok(()) + } + + /// Return the outputs of the given tx that have been spent by mempool txs. + pub fn outputs_spent( + &self, + txid: &TxId, + ) -> Option<&BTreeMap> { + self.spent_by.get(txid) + } +} + +#[cfg(test)] +mod tests { + use std::collections::BTreeMap; + + use abc_rust_error::Result; + use bitcoinsuite_core::tx::{OutPoint, SpentBy, TxId}; + + use crate::{ + mem::{MempoolSpentBy, MempoolSpentByError, MempoolTx}, + test::{make_inputs_tx, utxo::make_mempool_tx}, + }; + + #[test] + fn test_mempool_spent_by() -> Result<()> { + macro_rules! spent_by { + ($($out_idx:literal -> (txid_num=$by_txid_num:literal, + out_idx=$by_out_idx:literal)),*) => { + [ + $(( + $out_idx, + SpentBy { + txid: TxId::from([$by_txid_num; 32]), + input_idx: $by_out_idx, + } + )),* + ] + .into_iter() + .collect::>() + }; + } + + let mut mempool = MempoolSpentBy::default(); + + // Add tx spending txid_num=10, out_idx=4 + let tx1 = + make_mempool_tx!(txid_num = 1, inputs = [(10, 4)], num_outputs = 1); + mempool.insert(&tx1)?; + assert_eq!( + mempool.outputs_spent(&TxId::from([10; 32])), + Some(&spent_by!(4 -> (txid_num=1, out_idx=0))), + ); + + // Remove tx -> no entries in MempoolSpentBy anymore + mempool.remove(&tx1)?; + assert_eq!(mempool, MempoolSpentBy::default()); + + // Add tx again + mempool.insert(&tx1)?; + + // Failed insert: Tx conflicts with existing tx + let tx_conflict = make_mempool_tx!( + txid_num = 2, + inputs = [(0, 0), (10, 4)], + num_outputs = 0 + ); + assert_eq!( + mempool + .insert(&tx_conflict) + .unwrap_err() + .downcast::()?, + MempoolSpentByError::DuplicateSpentByEntry { + outpoint: OutPoint { + txid: TxId::from([10; 32]), + out_idx: 4, + }, + existing: SpentBy { + txid: TxId::from([1; 32]), + input_idx: 0, + }, + new: SpentBy { + txid: TxId::from([2; 32]), + input_idx: 1, + }, + }, + ); + + // Failed remove: Output never spent in mempool + let tx_missing = + make_mempool_tx!(txid_num = 3, inputs = [(10, 3)], num_outputs = 0); + assert_eq!( + mempool + .remove(&tx_missing) + .unwrap_err() + .downcast::()?, + MempoolSpentByError::MissingSpentByEntry { + outpoint: OutPoint { + txid: TxId::from([10; 32]), + out_idx: 3, + }, + expected: SpentBy { + txid: TxId::from([3; 32]), + input_idx: 0, + }, + }, + ); + + // Failed remove: Output spent by a different tx + let tx_mismatch: MempoolTx = + make_mempool_tx!(txid_num = 4, inputs = [(10, 4)], num_outputs = 0); + assert_eq!( + mempool + .remove(&tx_mismatch) + .unwrap_err() + .downcast::()?, + MempoolSpentByError::MismatchedSpentByEntry { + outpoint: OutPoint { + txid: TxId::from([10; 32]), + out_idx: 4, + }, + expected: SpentBy { + txid: TxId::from([4; 32]), + input_idx: 0, + }, + actual: SpentBy { + txid: TxId::from([1; 32]), + input_idx: 0, + }, + }, + ); + + // Add more spends to existing entries; also spend mempool tx + let tx2 = make_mempool_tx!( + txid_num = 5, + inputs = [(10, 5), (10, 3), (1, 0)], + num_outputs = 0 + ); + mempool.insert(&tx2)?; + assert_eq!( + mempool.outputs_spent(&TxId::from([10; 32])), + Some(&spent_by!( + 3 -> (txid_num=5, out_idx=1), + 4 -> (txid_num=1, out_idx=0), + 5 -> (txid_num=5, out_idx=0) + )), + ); + assert_eq!( + mempool.outputs_spent(&TxId::from([1; 32])), + Some(&spent_by!(0 -> (txid_num=5, out_idx=2))), + ); + + // "Mine" first tx + mempool.remove(&tx1)?; + assert_eq!( + mempool.outputs_spent(&TxId::from([10; 32])), + Some(&spent_by!( + 3 -> (txid_num=5, out_idx=1), + 5 -> (txid_num=5, out_idx=0) + )), + ); + // The now mined tx is still marked as spent in the mempool + assert_eq!( + mempool.outputs_spent(&TxId::from([1; 32])), + Some(&spent_by!(0 -> (txid_num=5, out_idx=2))), + ); + + // "Mine" dependent tx, now there no entries marked as spent in the + // mempool anymore. + mempool.remove(&tx2)?; + assert_eq!(mempool.outputs_spent(&TxId::from([10; 32])), None); + assert_eq!(mempool.outputs_spent(&TxId::from([1; 32])), None); + + Ok(()) + } +} diff --git a/chronik/chronik-db/src/test/mod.rs b/chronik/chronik-db/src/test/mod.rs index 5f66e73ec..d9622d86d 100644 --- a/chronik/chronik-db/src/test/mod.rs +++ b/chronik/chronik-db/src/test/mod.rs @@ -1,7 +1,8 @@ // Copyright (c) 2023 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. +pub(crate) mod utxo; mod value_group; pub(crate) use self::value_group::*; diff --git a/chronik/chronik-db/src/test/utxo.rs b/chronik/chronik-db/src/test/utxo.rs new file mode 100644 index 000000000..acaf0446f --- /dev/null +++ b/chronik/chronik-db/src/test/utxo.rs @@ -0,0 +1,22 @@ +// Copyright (c) 2023 The Bitcoin developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +macro_rules! make_mempool_tx { + ( + txid_num = $txid_num:literal, + inputs = [$(($input_txid_num:literal, $input_out_idx:literal)),*], + num_outputs = $num_outputs:literal + ) => { + MempoolTx { + tx: make_inputs_tx( + $txid_num, + [$(($input_txid_num, $input_out_idx, -1)),*], + [-1; $num_outputs], + ), + time_first_seen: 0, + } + }; +} + +pub(crate) use make_mempool_tx;