Module tx_graph

Module for structures that store and traverse transactions.

TxGraph contains transactions and indexes them so you can easily traverse the graph of those transactions. TxGraph is monotone in that you can always insert a transaction – it does not care whether that transaction is in the current best chain or whether it conflicts with any of the existing transactions or what order you insert the transactions. This means that you can always combine two TxGraphs together, without resulting in inconsistencies. Furthermore, there is currently no way to delete a transaction.

Transactions can be either whole or partial (i.e., transactions for which we only know some outputs, which we usually call “floating outputs”; these are usually inserted using the insert_txout method.).

The graph contains transactions in the form of TxNodes. Each node contains the txid, the transaction (whole or partial), the blocks that it is anchored to (see the Anchor documentation for more details), and the timestamp of the last time we saw the transaction as unconfirmed.

Canonicalization

Conflicting transactions are allowed to coexist within a TxGraph. A process called canonicalization is required to get a conflict-free view of transactions.

• list_canonical_txs lists canonical transactions.
• filter_chain_txouts filters out canonical outputs from a list of outpoints.
• filter_chain_unspents filters out canonical unspent outputs from a list of outpoints.
• balance gets the total sum of unspent outputs filtered from a list of outpoints.
• canonical_iter returns the CanonicalIter which contains all of the canonicalization logic.

All these methods require a chain and chain_tip argument. The chain must be a ChainOracle implementation (such as LocalChain) which identifies which blocks exist under a given chain_tip.

The canonicalization algorithm uses the following associated data to determine which transactions have precedence over others:

• Anchor - This bit of data represents that a transaction is anchored in a given block. If the transaction is anchored in chain of chain_tip, or is an ancestor of a transaction anchored in chain of chain_tip, then the transaction must be canonical.
• last_seen - This is the timestamp of when a transaction is last-seen in the mempool. This value is updated by insert_seen_at and apply_update. Transactions that are seen later have higher priority than those that are seen earlier. last_seen values are transitive. This means that the actual last_seen value of a transaction is the max of all the last_seen values from it’s descendants.
• last_evicted - This is the timestamp of when a transaction last went missing from the mempool. If this value is equal to or higher than the transaction’s last_seen value, then it will not be considered canonical.

Graph traversal

You can use TxAncestors/TxDescendants to traverse ancestors and descendants of a given transaction, respectively.

Applying changes

The ChangeSet reports changes made to a TxGraph; it can be used to either save to persistent storage, or to be applied to another TxGraph.

Methods that change the state of TxGraph will return ChangeSets.

Generics

Anchors are represented as generics within TxGraph<A>. To make use of all functionality of the TxGraph, anchors (A) should implement Anchor.

Anchors are made generic so that different types of data can be stored with how a transaction is anchored to a given block. An example of this is storing a merkle proof of the transaction to the confirmation block - this can be done with a custom Anchor type. The minimal Anchor type would just be a BlockId which just represents the height and hash of the block which the transaction is contained in. Note that a transaction can be contained in multiple conflicting blocks (by nature of the Bitcoin network).

let mut tx_graph: TxGraph = TxGraph::default();

// insert a transaction
let changeset = tx_graph.insert_tx(tx_a);

// We can restore the state of the `tx_graph` by applying all
// the changesets obtained by mutating the original (the order doesn't matter).
let mut restored_tx_graph: TxGraph = TxGraph::default();
restored_tx_graph.apply_changeset(changeset);

assert_eq!(tx_graph, restored_tx_graph);

A TxGraph can also be updated with another TxGraph which merges them together.

let mut graph: TxGraph = TxGraph::default();

let mut update = tx_graph::TxUpdate::default();
update.txs.push(Arc::new(tx_a));
update.txs.push(Arc::new(tx_b));

// apply the update graph
let changeset = graph.apply_update(update.clone());

// if we apply it again, the resulting changeset will be empty
let changeset = graph.apply_update(update);
assert!(changeset.is_empty());

Structs

CanonicalTx

A transaction that is deemed to be part of the canonical history.

ChangeSet

The ChangeSet represents changes to a TxGraph.

TxAncestors

An iterator that traverses ancestors of a given root transaction.

TxDescendants

An iterator that traverses transaction descendants.

TxGraph

A graph of transactions and spends.

TxNode

A transaction node in the TxGraph.

TxUpdate

Data object used to communicate updates about relevant transactions from some chain data source to the core model (usually a bdk_chain::TxGraph).

Enums

CalculateFeeError

Errors returned by TxGraph::calculate_fee.