Module bdk_chain::tx_graph

source ·
Expand description

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.

Conflicting transactions are allowed to coexist within a TxGraph. This is useful for identifying and traversing conflicts and descendants of a given transaction. Some TxGraph methods only consider transactions that are “canonical” (i.e., in the best chain or in mempool). We decide which transactions are canonical based on the transaction’s anchors and the last_seen (as unconfirmed) timestamp; see the try_get_chain_position documentation for more details.

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.

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

§Applying changes

Methods that change the state of TxGraph will return ChangeSets. ChangeSets can be applied back to a TxGraph or be used to inform persistent storage of the changes to TxGraph.


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();

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 update = TxGraph::new(vec![tx_a, 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);