6192744084

Committed 15 Sep 2023 01:24AM UTC coverage: 78.917% (+0.2%) from 78.702%

Build # 6192744084

Build Type

push

github

Committed by

evanlinjin

Commit Message

Merge bitcoindevkit/bdk#1084: Enhance bdk chain structures

<a class=hub.com/bitcoindevkit/bdk/commit/1ff806c67f4da9ba58b7c7689fde0fe41a34a6f5">1ff806c67<a href="https://github.com/bitcoindevkit/bdk/commit/c20a4da9fc902a062eb217b39e37a32d9e64a148"> fix(chain)!: rm weird `From` impl (志宇)
<a class="double-link" href="https://github.com/bitcoindevkit/bdk/commit/d43ae0231fa4670b98780cad84466c14ae087292">d43ae0231</a><a href="https://github.com/bitcoindevkit/bdk/commit/c20a4da9fc902a062eb217b39e37a32d9e64a148"> refactor: improve docs, cleanup unnecessary types and improve code (Vladimir Fomene)
</a><a class="double-link" href="https://github.com/bitcoindevkit/bdk/commit/41042069809e3eeb4a8cc8a5a8db1af2c57c4a11">410420698</a><a href="https://github.com/bitcoindevkit/bdk/commit/c20a4da9fc902a062eb217b39e37a32d9e64a148"> feat: impl Append for lots of tuples (LLFourn)
</a><a class="double-link" href="https://github.com/bitcoindevkit/bdk/commit/c56728ff1315e0deaf256af07fd1ff5e18fced8a">c56728ff1</a><a href="https://github.com/bitcoindevkit/bdk/commit/c20a4da9fc902a062eb217b39e37a32d9e64a148"> refactor: Remove `scan` and `scan_txout` from SpkTxoutIndex and KeychainTxoutIndex (Vladimir Fomene)
</a><a class="double-link" href="https://github.com/bitcoindevkit/bdk/commit/32c40ac939bc514ac7f1d3f1d7cd1080011e20ba">32c40ac93</a><a href="https://github.com/bitcoindevkit/bdk/commit/c20a4da9fc902a062eb217b39e37a32d9e64a148"> feat(electrum)!: change signature of `ElectrumExt` (志宇)
</a><a class="double-link" href="https://github.com/bitcoindevkit/bdk/commit/a28748c33976312b9e6671636ab7e305323efb03">a28748c33</a><a href="https://github.com/bitcoindevkit/bdk/commit/c20a4da9fc902a062eb217b39e37a32d9e64a148"> refactor: Implement Default for WalletUpdate (Vladimir Fomene)
</a><a class="double-link" href="https://github.com/bitcoindevkit/bdk/commit/f42f8b8ff19c2e67888b476487e4e5c9edb0d0ff">f42f8b8ff</a><a href="https://github.com/bitcoindevkit/bdk/commit/c20a4da9fc902a062eb217b39e37a32d9e64a148"> refactor: Allow for no chain update (Vladimir Fomene)
68572bfd2 refactor: move WalletChangeset to wallet module (Vladimir Fomene)
2392e50fd refactor: Move WalletUpdate to wallet module (Vladimir Fomene)
7c12dc994 refactor: Remove ForEachTxout trait (Vladimir Fomene)
6bcbb9323 refactor: Edit ElectrumExt not to use WalletUpdate (Vladimir Fomene)

Pull request description:

  ### Description

  Fixes #1061

  ### Changelog notice

  - Move WalletUpdate to the wallet module
  - Remove ForEachTxout trait completely
  - Refactor ElectrumExt to not use WalletUpdate.

  ### Checklists

  #### All Submissions:

  * [x] I've signed all my commits
  * [x] I followed the [contribution guidelines](https://github.com/bitcoindevkit/bdk/blob/master/CONTRIBUTING.md)
  * [x] I ran `cargo fmt` and `cargo clippy` before committing

ACKs for top commit:
  evanlinjin:
    ACK 1ff806c67f4da9ba58b7c7689fde0fe41a34a6f5

Tree-SHA512: 05349713a6adf2f93007816c4d305ed65a2

Run Details

115 of 115 new or added lines in 5 files covered. (100.0%)

8033 of 10179 relevant lines covered (78.92%)

5214.03 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/crates/electrum/src/electrum_ext.rs

use bdk_chain::{
    bitcoin::{OutPoint, ScriptBuf, Transaction, Txid},
    local_chain::{self, CheckPoint},
    tx_graph::{self, TxGraph},
    Anchor, BlockId, ConfirmationHeightAnchor, ConfirmationTimeAnchor,
};
use electrum_client::{Client, ElectrumApi, Error, HeaderNotification};
use std::{
    collections::{BTreeMap, BTreeSet, HashMap, HashSet},
    fmt::Debug,
    str::FromStr,
};

/// We assume that a block of this depth and deeper cannot be reorged.
const ASSUME_FINAL_DEPTH: u32 = 8;

/// Represents updates fetched from an Electrum server, but excludes full transactions.
///
/// To provide a complete update to [`TxGraph`], you'll need to call [`Self::missing_full_txs`] to
/// determine the full transactions missing from [`TxGraph`]. Then call [`Self::into_tx_graph`] to
/// fetch the full transactions from Electrum and finalize the update.
#[derive(Debug, Default, Clone)]
pub struct RelevantTxids(HashMap<Txid, BTreeSet<ConfirmationHeightAnchor>>);

impl RelevantTxids {
    /// Determine the full transactions that are missing from `graph`.
    ///
    /// Refer to [`RelevantTxids`] for more details.
    pub fn missing_full_txs<A: Anchor>(&self, graph: &TxGraph<A>) -> Vec<Txid> {
        self.0
            .keys()
            .filter(move |&&txid| graph.as_ref().get_tx(txid).is_none())
            .cloned()
            .collect()
    }

    /// Finalizes the [`TxGraph`] update by fetching `missing` txids from the `client`.
    ///
    /// Refer to [`RelevantTxids`] for more details.
    pub fn into_tx_graph(
        self,
        client: &Client,
        seen_at: Option<u64>,
        missing: Vec<Txid>,
    ) -> Result<TxGraph<ConfirmationHeightAnchor>, Error> {
        let new_txs = client.batch_transaction_get(&missing)?;
        let mut graph = TxGraph::<ConfirmationHeightAnchor>::new(new_txs);
        for (txid, anchors) in self.0 {
            if let Some(seen_at) = seen_at {
                let _ = graph.insert_seen_at(txid, seen_at);
            }
            for anchor in anchors {
                let _ = graph.insert_anchor(txid, anchor);
            }
        }
        Ok(graph)
    }

    /// Finalizes [`RelevantTxids`] with `new_txs` and anchors of type
    /// [`ConfirmationTimeAnchor`].
    ///
    /// **Note:** The confirmation time might not be precisely correct if there has been a reorg.
    /// Electrum's API intends that we use the merkle proof API, we should change `bdk_electrum` to
    /// use it.
    pub fn into_confirmation_time_tx_graph(
        self,
        client: &Client,
        seen_at: Option<u64>,
        missing: Vec<Txid>,
    ) -> Result<TxGraph<ConfirmationTimeAnchor>, Error> {
        let graph = self.into_tx_graph(client, seen_at, missing)?;

        let relevant_heights = {
            let mut visited_heights = HashSet::new();
            graph
                .all_anchors()
                .iter()
                .map(|(a, _)| a.confirmation_height_upper_bound())
                .filter(move |&h| visited_heights.insert(h))
                .collect::<Vec<_>>()
        };

        let height_to_time = relevant_heights
            .clone()
            .into_iter()
            .zip(
                client
                    .batch_block_header(relevant_heights)?
                    .into_iter()
                    .map(|bh| bh.time as u64),
            )
            .collect::<HashMap<u32, u64>>();

        let graph_changeset = {
            let old_changeset = TxGraph::default().apply_update(graph);
            tx_graph::ChangeSet {
                txs: old_changeset.txs,
                txouts: old_changeset.txouts,
                last_seen: old_changeset.last_seen,
                anchors: old_changeset
                    .anchors
                    .into_iter()
                    .map(|(height_anchor, txid)| {
                        let confirmation_height = height_anchor.confirmation_height;
                        let confirmation_time = height_to_time[&confirmation_height];
                        let time_anchor = ConfirmationTimeAnchor {
                            anchor_block: height_anchor.anchor_block,
                            confirmation_height,
                            confirmation_time,
                        };
                        (time_anchor, txid)
                    })
                    .collect(),
            }
        };

        let mut new_graph = TxGraph::default();
        new_graph.apply_changeset(graph_changeset);
        Ok(new_graph)
    }
}

/// Combination of chain and transactions updates from electrum
///
/// We have to update the chain and the txids at the same time since we anchor the txids to
/// the same chain tip that we check before and after we gather the txids.
#[derive(Debug)]
pub struct ElectrumUpdate {
    /// Chain update
    pub chain_update: local_chain::Update,
    /// Transaction updates from electrum
    pub relevant_txids: RelevantTxids,
}

/// Trait to extend [`Client`] functionality.
pub trait ElectrumExt {
    /// Scan the blockchain (via electrum) for the data specified and returns updates for
    /// [`bdk_chain`] data structures.
    ///
    /// - `prev_tip`: the most recent blockchain tip present locally
    /// - `keychain_spks`: keychains that we want to scan transactions for
    /// - `txids`: transactions for which we want updated [`Anchor`]s
    /// - `outpoints`: transactions associated with these outpoints (residing, spending) that we
    ///     want to included in the update
    ///
    /// The scan for each keychain stops after a gap of `stop_gap` script pubkeys with no associated
    /// transactions. `batch_size` specifies the max number of script pubkeys to request for in a
    /// single batch request.
    fn scan<K: Ord + Clone>(
        &self,
        prev_tip: Option<CheckPoint>,
        keychain_spks: BTreeMap<K, impl IntoIterator<Item = (u32, ScriptBuf)>>,
        txids: impl IntoIterator<Item = Txid>,
        outpoints: impl IntoIterator<Item = OutPoint>,
        stop_gap: usize,
        batch_size: usize,
    ) -> Result<(ElectrumUpdate, BTreeMap<K, u32>), Error>;

    /// Convenience method to call [`scan`] without requiring a keychain.
    ///
    /// [`scan`]: ElectrumExt::scan
    fn scan_without_keychain(
        &self,
        prev_tip: Option<CheckPoint>,
        misc_spks: impl IntoIterator<Item = ScriptBuf>,
        txids: impl IntoIterator<Item = Txid>,
        outpoints: impl IntoIterator<Item = OutPoint>,
        batch_size: usize,
    ) -> Result<ElectrumUpdate, Error> {
        let spk_iter = misc_spks
            .into_iter()
            .enumerate()
            .map(|(i, spk)| (i as u32, spk));

        let (electrum_update, _) = self.scan(
            prev_tip,
            [((), spk_iter)].into(),
            txids,
            outpoints,
            usize::MAX,
            batch_size,
        )?;

        Ok(electrum_update)
    }
}

impl ElectrumExt for Client {
    fn scan<K: Ord + Clone>(
        &self,
        prev_tip: Option<CheckPoint>,
        keychain_spks: BTreeMap<K, impl IntoIterator<Item = (u32, ScriptBuf)>>,
        txids: impl IntoIterator<Item = Txid>,
        outpoints: impl IntoIterator<Item = OutPoint>,
        stop_gap: usize,
        batch_size: usize,
    ) -> Result<(ElectrumUpdate, BTreeMap<K, u32>), Error> {
        let mut request_spks = keychain_spks
            .into_iter()
            .map(|(k, s)| (k, s.into_iter()))
            .collect::<BTreeMap<K, _>>();
        let mut scanned_spks = BTreeMap::<(K, u32), (ScriptBuf, bool)>::new();

        let txids = txids.into_iter().collect::<Vec<_>>();
        let outpoints = outpoints.into_iter().collect::<Vec<_>>();

        let (electrum_update, keychain_update) = loop {
            let (tip, _) = construct_update_tip(self, prev_tip.clone())?;
            let mut relevant_txids = RelevantTxids::default();
            let cps = tip
                .iter()
                .take(10)
                .map(|cp| (cp.height(), cp))
                .collect::<BTreeMap<u32, CheckPoint>>();

            if !request_spks.is_empty() {
                if !scanned_spks.is_empty() {
                    scanned_spks.append(&mut populate_with_spks(
                        self,
                        &cps,
                        &mut relevant_txids,
                        &mut scanned_spks
                            .iter()
                            .map(|(i, (spk, _))| (i.clone(), spk.clone())),
                        stop_gap,
                        batch_size,
                    )?);
                }
                for (keychain, keychain_spks) in &mut request_spks {
                    scanned_spks.extend(
                        populate_with_spks(
                            self,
                            &cps,
                            &mut relevant_txids,
                            keychain_spks,
                            stop_gap,
                            batch_size,
                        )?
                        .into_iter()
                        .map(|(spk_i, spk)| ((keychain.clone(), spk_i), spk)),
                    );
                }
            }

            populate_with_txids(self, &cps, &mut relevant_txids, &mut txids.iter().cloned())?;

            let _txs = populate_with_outpoints(
                self,
                &cps,
                &mut relevant_txids,
                &mut outpoints.iter().cloned(),
            )?;

            // check for reorgs during scan process
            let server_blockhash = self.block_header(tip.height() as usize)?.block_hash();
            if tip.hash() != server_blockhash {
                continue; // reorg
            }

            let chain_update = local_chain::Update {
                tip,
                introduce_older_blocks: true,
            };

            let keychain_update = request_spks
                .into_keys()
                .filter_map(|k| {
                    scanned_spks
                        .range((k.clone(), u32::MIN)..=(k.clone(), u32::MAX))
                        .rev()
                        .find(|(_, (_, active))| *active)
                        .map(|((_, i), _)| (k, *i))
                })
                .collect::<BTreeMap<_, _>>();

            break (
                ElectrumUpdate {
                    chain_update,
                    relevant_txids,
                },
                keychain_update,
            );
        };

        Ok((electrum_update, keychain_update))
    }
}

/// Return a [`CheckPoint`] of the latest tip, that connects with `prev_tip`.
fn construct_update_tip(
    client: &Client,
    prev_tip: Option<CheckPoint>,
) -> Result<(CheckPoint, Option<u32>), Error> {
    let HeaderNotification { height, .. } = client.block_headers_subscribe()?;
    let new_tip_height = height as u32;

    // If electrum returns a tip height that is lower than our previous tip, then checkpoints do
    // not need updating. We just return the previous tip and use that as the point of agreement.
    if let Some(prev_tip) = prev_tip.as_ref() {
        if new_tip_height < prev_tip.height() {
            return Ok((prev_tip.clone(), Some(prev_tip.height())));
        }
    }

    // Atomically fetch the latest `ASSUME_FINAL_DEPTH` count of blocks from Electrum. We use this
    // to construct our checkpoint update.
    let mut new_blocks = {
        let start_height = new_tip_height.saturating_sub(ASSUME_FINAL_DEPTH);
        let hashes = client
            .block_headers(start_height as _, ASSUME_FINAL_DEPTH as _)?
            .headers
            .into_iter()
            .map(|h| h.block_hash());
        (start_height..).zip(hashes).collect::<BTreeMap<u32, _>>()
    };

    // Find the "point of agreement" (if any).
    let agreement_cp = {
        let mut agreement_cp = Option::<CheckPoint>::None;
        for cp in prev_tip.iter().flat_map(CheckPoint::iter) {
            let cp_block = cp.block_id();
            let hash = match new_blocks.get(&cp_block.height) {
                Some(&hash) => hash,
                None => {
                    assert!(
                        new_tip_height >= cp_block.height,
                        "already checked that electrum's tip cannot be smaller"
                    );
                    let hash = client.block_header(cp_block.height as _)?.block_hash();
                    new_blocks.insert(cp_block.height, hash);
                    hash
                }
            };
            if hash == cp_block.hash {
                agreement_cp = Some(cp);
                break;
            }
        }
        agreement_cp
    };

    let agreement_height = agreement_cp.as_ref().map(CheckPoint::height);

    let new_tip = new_blocks
        .into_iter()
        // Prune `new_blocks` to only include blocks that are actually new.
        .filter(|(height, _)| Some(*height) > agreement_height)
        .map(|(height, hash)| BlockId { height, hash })
        .fold(agreement_cp, |prev_cp, block| {
            Some(match prev_cp {
                Some(cp) => cp.push(block).expect("must extend checkpoint"),
                None => CheckPoint::new(block),
            })
        })
        .expect("must have at least one checkpoint");

    Ok((new_tip, agreement_height))
}

/// A [tx status] comprises of a concatenation of `tx_hash:height:`s. We transform a single one of
/// these concatenations into a [`ConfirmationHeightAnchor`] if possible.
///
/// We use the lowest possible checkpoint as the anchor block (from `cps`). If an anchor block
/// cannot be found, or the transaction is unconfirmed, [`None`] is returned.
///
/// [tx status](https://electrumx-spesmilo.readthedocs.io/en/latest/protocol-basics.html#status)
fn determine_tx_anchor(
    cps: &BTreeMap<u32, CheckPoint>,
    raw_height: i32,
    txid: Txid,
) -> Option<ConfirmationHeightAnchor> {
    // The electrum API has a weird quirk where an unconfirmed transaction is presented with a
    // height of 0. To avoid invalid representation in our data structures, we manually set
    // transactions residing in the genesis block to have height 0, then interpret a height of 0 as
    // unconfirmed for all other transactions.
    if txid
        == Txid::from_str("4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b")
            .expect("must deserialize genesis coinbase txid")
    {
        let anchor_block = cps.values().next()?.block_id();
        return Some(ConfirmationHeightAnchor {
            anchor_block,
            confirmation_height: 0,
        });
    }
    match raw_height {
        h if h <= 0 => {
            debug_assert!(h == 0 || h == -1, "unexpected height ({}) from electrum", h);
            None
        }
        h => {
            let h = h as u32;
            let anchor_block = cps.range(h..).next().map(|(_, cp)| cp.block_id())?;
            if h > anchor_block.height {
                None
            } else {
                Some(ConfirmationHeightAnchor {
                    anchor_block,
                    confirmation_height: h,
                })
            }
        }
    }
}

fn populate_with_outpoints(
    client: &Client,
    cps: &BTreeMap<u32, CheckPoint>,
    relevant_txids: &mut RelevantTxids,
    outpoints: &mut impl Iterator<Item = OutPoint>,
) -> Result<HashMap<Txid, Transaction>, Error> {
    let mut full_txs = HashMap::new();
    for outpoint in outpoints {
        let txid = outpoint.txid;
        let tx = client.transaction_get(&txid)?;
        debug_assert_eq!(tx.txid(), txid);
        let txout = match tx.output.get(outpoint.vout as usize) {
            Some(txout) => txout,
            None => continue,
        };
        // attempt to find the following transactions (alongside their chain positions), and
        // add to our sparsechain `update`:
        let mut has_residing = false; // tx in which the outpoint resides
        let mut has_spending = false; // tx that spends the outpoint
        for res in client.script_get_history(&txout.script_pubkey)? {
            if has_residing && has_spending {
                break;
            }

            if res.tx_hash == txid {
                if has_residing {
                    continue;
                }
                has_residing = true;
                full_txs.insert(res.tx_hash, tx.clone());
            } else {
                if has_spending {
                    continue;
                }
                let res_tx = match full_txs.get(&res.tx_hash) {
                    Some(tx) => tx,
                    None => {
                        let res_tx = client.transaction_get(&res.tx_hash)?;
                        full_txs.insert(res.tx_hash, res_tx);
                        full_txs.get(&res.tx_hash).expect("just inserted")
                    }
                };
                has_spending = res_tx
                    .input
                    .iter()
                    .any(|txin| txin.previous_output == outpoint);
                if !has_spending {
                    continue;
                }
            };

            let anchor = determine_tx_anchor(cps, res.height, res.tx_hash);
            let tx_entry = relevant_txids.0.entry(res.tx_hash).or_default();
            if let Some(anchor) = anchor {
                tx_entry.insert(anchor);
            }
        }
    }
    Ok(full_txs)
}

fn populate_with_txids(
    client: &Client,
    cps: &BTreeMap<u32, CheckPoint>,
    relevant_txids: &mut RelevantTxids,
    txids: &mut impl Iterator<Item = Txid>,
) -> Result<(), Error> {
    for txid in txids {
        let tx = match client.transaction_get(&txid) {
            Ok(tx) => tx,
            Err(electrum_client::Error::Protocol(_)) => continue,
            Err(other_err) => return Err(other_err),
        };

        let spk = tx
            .output
            .get(0)
            .map(|txo| &txo.script_pubkey)
            .expect("tx must have an output");

        let anchor = match client
            .script_get_history(spk)?
            .into_iter()
            .find(|r| r.tx_hash == txid)
        {
            Some(r) => determine_tx_anchor(cps, r.height, txid),
            None => continue,
        };

        let tx_entry = relevant_txids.0.entry(txid).or_default();
        if let Some(anchor) = anchor {
            tx_entry.insert(anchor);
        }
    }
    Ok(())
}

fn populate_with_spks<I: Ord + Clone>(
    client: &Client,
    cps: &BTreeMap<u32, CheckPoint>,
    relevant_txids: &mut RelevantTxids,
    spks: &mut impl Iterator<Item = (I, ScriptBuf)>,
    stop_gap: usize,
    batch_size: usize,
) -> Result<BTreeMap<I, (ScriptBuf, bool)>, Error> {
    let mut unused_spk_count = 0_usize;
    let mut scanned_spks = BTreeMap::new();

    loop {
        let spks = (0..batch_size)
            .map_while(|_| spks.next())
            .collect::<Vec<_>>();
        if spks.is_empty() {
            return Ok(scanned_spks);
        }

        let spk_histories =
            client.batch_script_get_history(spks.iter().map(|(_, s)| s.as_script()))?;

        for ((spk_index, spk), spk_history) in spks.into_iter().zip(spk_histories) {
            if spk_history.is_empty() {
                scanned_spks.insert(spk_index, (spk, false));
                unused_spk_count += 1;
                if unused_spk_count > stop_gap {
                    return Ok(scanned_spks);
                }
                continue;
            } else {
                scanned_spks.insert(spk_index, (spk, true));
                unused_spk_count = 0;
            }

            for tx in spk_history {
                let tx_entry = relevant_txids.0.entry(tx.tx_hash).or_default();
                if let Some(anchor) = determine_tx_anchor(cps, tx.height, tx.tx_hash) {
                    tx_entry.insert(anchor);
                }
            }
        }
    }
}

1	use bdk_chain::{
2	bitcoin::{OutPoint, ScriptBuf, Transaction, Txid},
3	local_chain::{self, CheckPoint},
4	tx_graph::{self, TxGraph},
5	Anchor, BlockId, ConfirmationHeightAnchor, ConfirmationTimeAnchor,
6	};
7	use electrum_client::{Client, ElectrumApi, Error, HeaderNotification};
8	use std::{
9	collections::{BTreeMap, BTreeSet, HashMap, HashSet},
10	fmt::Debug,
11	str::FromStr,
12	};
13
14	/// We assume that a block of this depth and deeper cannot be reorged.
15	const ASSUME_FINAL_DEPTH: u32 = 8;
16
17	/// Represents updates fetched from an Electrum server, but excludes full transactions.
18	///
19	/// To provide a complete update to [`TxGraph`], you'll need to call [`Self::missing_full_txs`] to
20	/// determine the full transactions missing from [`TxGraph`]. Then call [`Self::into_tx_graph`] to
21	/// fetch the full transactions from Electrum and finalize the update.
22	#[derive(Debug, Default, Clone)]	×
23	pub struct RelevantTxids(HashMap<Txid, BTreeSet<ConfirmationHeightAnchor>>);
24
25	impl RelevantTxids {
26	/// Determine the full transactions that are missing from `graph`.
27	///
28	/// Refer to [`RelevantTxids`] for more details.
29	pub fn missing_full_txs<A: Anchor>(&self, graph: &TxGraph<A>) -> Vec<Txid> {	×
30	self.0	×
31	.keys()	×
32	.filter(move \|&&txid\| graph.as_ref().get_tx(txid).is_none())	×
33	.cloned()	×
34	.collect()	×
35	}	×
36
37	/// Finalizes the [`TxGraph`] update by fetching `missing` txids from the `client`.
38	///
39	/// Refer to [`RelevantTxids`] for more details.
40	pub fn into_tx_graph(	×
41	self,	×
42	client: &Client,	×
43	seen_at: Option<u64>,	×
44	missing: Vec<Txid>,	×
45	) -> Result<TxGraph<ConfirmationHeightAnchor>, Error> {	×
46	let new_txs = client.batch_transaction_get(&missing)?;	×
47	let mut graph = TxGraph::<ConfirmationHeightAnchor>::new(new_txs);	×
48	for (txid, anchors) in self.0 {	×
49	if let Some(seen_at) = seen_at {	×
50	let _ = graph.insert_seen_at(txid, seen_at);	×
51	}	×
52	for anchor in anchors {	×
53	let _ = graph.insert_anchor(txid, anchor);	×
54	}	×
55	}
56	Ok(graph)	×
57	}	×
58
59	/// Finalizes [`RelevantTxids`] with `new_txs` and anchors of type
60	/// [`ConfirmationTimeAnchor`].
61	///
62	/// Note: The confirmation time might not be precisely correct if there has been a reorg.
63	/// Electrum's API intends that we use the merkle proof API, we should change `bdk_electrum` to
64	/// use it.
65	pub fn into_confirmation_time_tx_graph(	×
66	self,	×
67	client: &Client,	×
68	seen_at: Option<u64>,	×
69	missing: Vec<Txid>,	×
70	) -> Result<TxGraph<ConfirmationTimeAnchor>, Error> {	×
71	let graph = self.into_tx_graph(client, seen_at, missing)?;	×
72
73	let relevant_heights = {	×
74	let mut visited_heights = HashSet::new();	×
75	graph	×
76	.all_anchors()	×
77	.iter()	×
78	.map(\|(a, _)\| a.confirmation_height_upper_bound())	×
79	.filter(move \|&h\| visited_heights.insert(h))	×
80	.collect::<Vec<_>>()	×
81	};
82
83	let height_to_time = relevant_heights	×
84	.clone()	×
85	.into_iter()	×
86	.zip(	×
87	client	×
88	.batch_block_header(relevant_heights)?	×
89	.into_iter()	×
90	.map(\|bh\| bh.time as u64),	×
91	)	×
92	.collect::<HashMap<u32, u64>>();	×
93		×
94	let graph_changeset = {	×
95	let old_changeset = TxGraph::default().apply_update(graph);	×
96	tx_graph::ChangeSet {	×
97	txs: old_changeset.txs,	×
98	txouts: old_changeset.txouts,	×
99	last_seen: old_changeset.last_seen,	×
100	anchors: old_changeset	×
101	.anchors	×
102	.into_iter()	×
103	.map(\|(height_anchor, txid)\| {	×
104	let confirmation_height = height_anchor.confirmation_height;	×
105	let confirmation_time = height_to_time[&confirmation_height];	×
106	let time_anchor = ConfirmationTimeAnchor {	×
107	anchor_block: height_anchor.anchor_block,	×
108	confirmation_height,	×
109	confirmation_time,	×
110	};	×
111	(time_anchor, txid)	×
112	})	×
113	.collect(),	×
114	}	×
115	};	×
116		×
117	let mut new_graph = TxGraph::default();	×
118	new_graph.apply_changeset(graph_changeset);	×
119	Ok(new_graph)	×
120	}	×
121	}
122
123	/// Combination of chain and transactions updates from electrum
124	///
125	/// We have to update the chain and the txids at the same time since we anchor the txids to
126	/// the same chain tip that we check before and after we gather the txids.
127	#[derive(Debug)]	×
128	pub struct ElectrumUpdate {
129	/// Chain update
130	pub chain_update: local_chain::Update,
131	/// Transaction updates from electrum
132	pub relevant_txids: RelevantTxids,
133	}
134
135	/// Trait to extend [`Client`] functionality.
136	pub trait ElectrumExt {
137	/// Scan the blockchain (via electrum) for the data specified and returns updates for
138	/// [`bdk_chain`] data structures.
139	///
140	/// - `prev_tip`: the most recent blockchain tip present locally
141	/// - `keychain_spks`: keychains that we want to scan transactions for
142	/// - `txids`: transactions for which we want updated [`Anchor`]s
143	/// - `outpoints`: transactions associated with these outpoints (residing, spending) that we
144	/// want to included in the update
145	///
146	/// The scan for each keychain stops after a gap of `stop_gap` script pubkeys with no associated
147	/// transactions. `batch_size` specifies the max number of script pubkeys to request for in a
148	/// single batch request.
149	fn scan<K: Ord + Clone>(
150	&self,
151	prev_tip: Option<CheckPoint>,
152	keychain_spks: BTreeMap<K, impl IntoIterator<Item = (u32, ScriptBuf)>>,
153	txids: impl IntoIterator<Item = Txid>,
154	outpoints: impl IntoIterator<Item = OutPoint>,
155	stop_gap: usize,
156	batch_size: usize,
157	) -> Result<(ElectrumUpdate, BTreeMap<K, u32>), Error>;
158
159	/// Convenience method to call [`scan`] without requiring a keychain.
160	///
161	/// [`scan`]: ElectrumExt::scan
162	fn scan_without_keychain(	×
163	&self,	×
164	prev_tip: Option<CheckPoint>,	×
165	misc_spks: impl IntoIterator<Item = ScriptBuf>,	×
166	txids: impl IntoIterator<Item = Txid>,	×
167	outpoints: impl IntoIterator<Item = OutPoint>,	×
168	batch_size: usize,	×
169	) -> Result<ElectrumUpdate, Error> {	×
170	let spk_iter = misc_spks	×
171	.into_iter()	×
172	.enumerate()	×
173	.map(\|(i, spk)\| (i as u32, spk));	×
174
175	let (electrum_update, _) = self.scan(	×
176	prev_tip,	×
177	[((), spk_iter)].into(),	×
178	txids,	×
179	outpoints,	×
180	usize::MAX,	×
181	batch_size,	×
182	)?;	×
183
184	Ok(electrum_update)	×
185	}	×
186	}
187
188	impl ElectrumExt for Client {
189	fn scan<K: Ord + Clone>(	×
190	&self,	×
191	prev_tip: Option<CheckPoint>,	×
192	keychain_spks: BTreeMap<K, impl IntoIterator<Item = (u32, ScriptBuf)>>,	×
193	txids: impl IntoIterator<Item = Txid>,	×
194	outpoints: impl IntoIterator<Item = OutPoint>,	×
195	stop_gap: usize,	×
196	batch_size: usize,	×
197	) -> Result<(ElectrumUpdate, BTreeMap<K, u32>), Error> {	×
198	let mut request_spks = keychain_spks	×
199	.into_iter()	×
200	.map(\|(k, s)\| (k, s.into_iter()))	×
201	.collect::<BTreeMap<K, _>>();	×
202	let mut scanned_spks = BTreeMap::<(K, u32), (ScriptBuf, bool)>::new();	×
203		×
204	let txids = txids.into_iter().collect::<Vec<_>>();	×
205	let outpoints = outpoints.into_iter().collect::<Vec<_>>();	×
206
207	let (electrum_update, keychain_update) = loop {	×
208	let (tip, _) = construct_update_tip(self, prev_tip.clone())?;	×
209	let mut relevant_txids = RelevantTxids::default();	×
210	let cps = tip	×
211	.iter()	×
212	.take(10)	×
213	.map(\|cp\| (cp.height(), cp))	×
214	.collect::<BTreeMap<u32, CheckPoint>>();	×
215		×
216	if !request_spks.is_empty() {	×
217	if !scanned_spks.is_empty() {	×
218	scanned_spks.append(&mut populate_with_spks(	×
219	self,	×
220	&cps,	×
221	&mut relevant_txids,	×
222	&mut scanned_spks	×
223	.iter()	×
224	.map(\|(i, (spk, _))\| (i.clone(), spk.clone())),	×
225	stop_gap,	×
226	batch_size,	×
227	)?);	×
228	}	×
229	for (keychain, keychain_spks) in &mut request_spks {	×
230	scanned_spks.extend(
231	populate_with_spks(	×
232	self,	×
233	&cps,	×
234	&mut relevant_txids,	×
235	keychain_spks,	×
236	stop_gap,	×
237	batch_size,	×
238	)?	×
239	.into_iter()	×
240	.map(\|(spk_i, spk)\| ((keychain.clone(), spk_i), spk)),	×
241	);
242	}
243	}	×
244
245	populate_with_txids(self, &cps, &mut relevant_txids, &mut txids.iter().cloned())?;	×
246
247	let _txs = populate_with_outpoints(	×
248	self,	×
249	&cps,	×
250	&mut relevant_txids,	×
251	&mut outpoints.iter().cloned(),	×
252	)?;	×
253
254	// check for reorgs during scan process
255	let server_blockhash = self.block_header(tip.height() as usize)?.block_hash();	×
256	if tip.hash() != server_blockhash {	×
257	continue; // reorg	×
258	}	×
259		×
260	let chain_update = local_chain::Update {	×
261	tip,	×
262	introduce_older_blocks: true,	×
263	};	×
264		×
265	let keychain_update = request_spks	×
266	.into_keys()	×
267	.filter_map(\|k\| {	×
268	scanned_spks	×
269	.range((k.clone(), u32::MIN)..=(k.clone(), u32::MAX))	×
270	.rev()	×
271	.find(\|(_, (_, active))\| *active)	×
272	.map(\|((_, i), _)\| (k, *i))	×
273	})	×
274	.collect::<BTreeMap<_, _>>();	×
275		×
276	break (	×
277	ElectrumUpdate {	×
278	chain_update,	×
279	relevant_txids,	×
280	},	×
281	keychain_update,	×
282	);	×
283	};	×
284		×
285	Ok((electrum_update, keychain_update))	×
286	}	×
287	}
288
289	/// Return a [`CheckPoint`] of the latest tip, that connects with `prev_tip`.
290	fn construct_update_tip(	×
291	client: &Client,	×
292	prev_tip: Option<CheckPoint>,	×
293	) -> Result<(CheckPoint, Option<u32>), Error> {	×
294	let HeaderNotification { height, .. } = client.block_headers_subscribe()?;	×
295	let new_tip_height = height as u32;	×
296
297	// If electrum returns a tip height that is lower than our previous tip, then checkpoints do
298	// not need updating. We just return the previous tip and use that as the point of agreement.
299	if let Some(prev_tip) = prev_tip.as_ref() {	×
300	if new_tip_height < prev_tip.height() {	×
301	return Ok((prev_tip.clone(), Some(prev_tip.height())));	×
302	}	×
303	}	×
304
305	// Atomically fetch the latest `ASSUME_FINAL_DEPTH` count of blocks from Electrum. We use this
306	// to construct our checkpoint update.
307	let mut new_blocks = {	×
308	let start_height = new_tip_height.saturating_sub(ASSUME_FINAL_DEPTH);	×
309	let hashes = client	×
310	.block_headers(start_height as _, ASSUME_FINAL_DEPTH as _)?	×
311	.headers
312	.into_iter()	×
313	.map(\|h\| h.block_hash());	×
314	(start_height..).zip(hashes).collect::<BTreeMap<u32, _>>()	×
315	};
316
317	// Find the "point of agreement" (if any).
318	let agreement_cp = {	×
319	let mut agreement_cp = Option::<CheckPoint>::None;	×
320	for cp in prev_tip.iter().flat_map(CheckPoint::iter) {	×
321	let cp_block = cp.block_id();	×
322	let hash = match new_blocks.get(&cp_block.height) {	×
323	Some(&hash) => hash,	×
324	None => {
325	assert!(	×
326	new_tip_height >= cp_block.height,	×
327	"already checked that electrum's tip cannot be smaller"	×
328	);
329	let hash = client.block_header(cp_block.height as _)?.block_hash();	×
330	new_blocks.insert(cp_block.height, hash);	×
331	hash	×
332	}
333	};
334	if hash == cp_block.hash {	×
335	agreement_cp = Some(cp);	×
336	break;	×
337	}	×
338	}
339	agreement_cp	×
340	};	×
341		×
342	let agreement_height = agreement_cp.as_ref().map(CheckPoint::height);	×
343		×
344	let new_tip = new_blocks	×
345	.into_iter()	×
346	// Prune `new_blocks` to only include blocks that are actually new.	×
347	.filter(\|(height, _)\| Some(*height) > agreement_height)	×
348	.map(\|(height, hash)\| BlockId { height, hash })	×
349	.fold(agreement_cp, \|prev_cp, block\| {	×
350	Some(match prev_cp {	×
351	Some(cp) => cp.push(block).expect("must extend checkpoint"),	×
352	None => CheckPoint::new(block),	×
353	})
354	})	×
355	.expect("must have at least one checkpoint");	×
356		×
357	Ok((new_tip, agreement_height))	×
358	}	×
359
360	/// A [tx status] comprises of a concatenation of `tx_hash:height:`s. We transform a single one of
361	/// these concatenations into a [`ConfirmationHeightAnchor`] if possible.
362	///
363	/// We use the lowest possible checkpoint as the anchor block (from `cps`). If an anchor block
364	/// cannot be found, or the transaction is unconfirmed, [`None`] is returned.
365	///
366	/// [tx status](https://electrumx-spesmilo.readthedocs.io/en/latest/protocol-basics.html#status)
367	fn determine_tx_anchor(	×
368	cps: &BTreeMap<u32, CheckPoint>,	×
369	raw_height: i32,	×
370	txid: Txid,	×
371	) -> Option<ConfirmationHeightAnchor> {	×
372	// The electrum API has a weird quirk where an unconfirmed transaction is presented with a	×
373	// height of 0. To avoid invalid representation in our data structures, we manually set	×
374	// transactions residing in the genesis block to have height 0, then interpret a height of 0 as	×
375	// unconfirmed for all other transactions.	×
376	if txid	×
377	== Txid::from_str("4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b")	×
378	.expect("must deserialize genesis coinbase txid")	×
379	{
380	let anchor_block = cps.values().next()?.block_id();	×
381	return Some(ConfirmationHeightAnchor {	×
382	anchor_block,	×
383	confirmation_height: 0,	×
384	});	×
385	}	×
386	match raw_height {	×
387	h if h <= 0 => {	×
388	debug_assert!(h == 0 \|\| h == -1, "unexpected height ({}) from electrum", h);	×
389	None	×
390	}
391	h => {	×
392	let h = h as u32;	×
393	let anchor_block = cps.range(h..).next().map(\|(_, cp)\| cp.block_id())?;	×
394	if h > anchor_block.height {	×
395	None	×
396	} else {
397	Some(ConfirmationHeightAnchor {	×
398	anchor_block,	×
399	confirmation_height: h,	×
400	})	×
401	}
402	}
403	}
404	}	×
405
406	fn populate_with_outpoints(	×
407	client: &Client,	×
408	cps: &BTreeMap<u32, CheckPoint>,	×
409	relevant_txids: &mut RelevantTxids,	×
410	outpoints: &mut impl Iterator<Item = OutPoint>,	×
411	) -> Result<HashMap<Txid, Transaction>, Error> {	×
412	let mut full_txs = HashMap::new();	×
413	for outpoint in outpoints {	×
414	let txid = outpoint.txid;	×
415	let tx = client.transaction_get(&txid)?;	×
416	debug_assert_eq!(tx.txid(), txid);	×
417	let txout = match tx.output.get(outpoint.vout as usize) {	×
418	Some(txout) => txout,	×
419	None => continue,	×
420	};
421	// attempt to find the following transactions (alongside their chain positions), and
422	// add to our sparsechain `update`:
423	let mut has_residing = false; // tx in which the outpoint resides	×
424	let mut has_spending = false; // tx that spends the outpoint	×
425	for res in client.script_get_history(&txout.script_pubkey)? {	×
426	if has_residing && has_spending {	×
427	break;	×
428	}	×
429		×
430	if res.tx_hash == txid {	×
431	if has_residing {	×
432	continue;	×
433	}	×
434	has_residing = true;	×
435	full_txs.insert(res.tx_hash, tx.clone());	×
436	} else {
437	if has_spending {	×
438	continue;	×
439	}	×
440	let res_tx = match full_txs.get(&res.tx_hash) {	×
441	Some(tx) => tx,	×
442	None => {
443	let res_tx = client.transaction_get(&res.tx_hash)?;	×
444	full_txs.insert(res.tx_hash, res_tx);	×
445	full_txs.get(&res.tx_hash).expect("just inserted")	×
446	}
447	};
448	has_spending = res_tx	×
449	.input	×
450	.iter()	×
451	.any(\|txin\| txin.previous_output == outpoint);	×
452	if !has_spending {	×
453	continue;	×
454	}	×
455	};
456
457	let anchor = determine_tx_anchor(cps, res.height, res.tx_hash);	×
458	let tx_entry = relevant_txids.0.entry(res.tx_hash).or_default();	×
459	if let Some(anchor) = anchor {	×
460	tx_entry.insert(anchor);	×
461	}	×
462	}
463	}
464	Ok(full_txs)	×
465	}	×
466
467	fn populate_with_txids(	×
468	client: &Client,	×
469	cps: &BTreeMap<u32, CheckPoint>,	×
470	relevant_txids: &mut RelevantTxids,	×
471	txids: &mut impl Iterator<Item = Txid>,	×
472	) -> Result<(), Error> {	×
473	for txid in txids {	×
474	let tx = match client.transaction_get(&txid) {	×
475	Ok(tx) => tx,	×
476	Err(electrum_client::Error::Protocol(_)) => continue,	×
477	Err(other_err) => return Err(other_err),	×
478	};
479
480	let spk = tx	×
481	.output	×
482	.get(0)	×
483	.map(\|txo\| &txo.script_pubkey)	×
484	.expect("tx must have an output");	×
485
486	let anchor = match client	×
487	.script_get_history(spk)?	×
488	.into_iter()	×
489	.find(\|r\| r.tx_hash == txid)	×
490	{
491	Some(r) => determine_tx_anchor(cps, r.height, txid),	×
492	None => continue,	×
493	};
494
495	let tx_entry = relevant_txids.0.entry(txid).or_default();	×
496	if let Some(anchor) = anchor {	×
497	tx_entry.insert(anchor);	×
498	}	×
499	}
500	Ok(())	×
501	}	×
502
503	fn populate_with_spks<I: Ord + Clone>(	×
504	client: &Client,	×
505	cps: &BTreeMap<u32, CheckPoint>,	×
506	relevant_txids: &mut RelevantTxids,	×
507	spks: &mut impl Iterator<Item = (I, ScriptBuf)>,	×
508	stop_gap: usize,	×
509	batch_size: usize,	×
510	) -> Result<BTreeMap<I, (ScriptBuf, bool)>, Error> {	×
511	let mut unused_spk_count = 0_usize;	×
512	let mut scanned_spks = BTreeMap::new();	×
513
514	loop {	×
515	let spks = (0..batch_size)	×
516	.map_while(\|_\| spks.next())	×
517	.collect::<Vec<_>>();	×
518	if spks.is_empty() {	×
519	return Ok(scanned_spks);	×
520	}	×
521
522	let spk_histories =	×
523	client.batch_script_get_history(spks.iter().map(\|(_, s)\| s.as_script()))?;	×
524
525	for ((spk_index, spk), spk_history) in spks.into_iter().zip(spk_histories) {	×
526	if spk_history.is_empty() {	×
527	scanned_spks.insert(spk_index, (spk, false));	×
528	unused_spk_count += 1;	×
529	if unused_spk_count > stop_gap {	×
530	return Ok(scanned_spks);	×
531	}	×
532	continue;	×
533	} else {	×
534	scanned_spks.insert(spk_index, (spk, true));	×
535	unused_spk_count = 0;	×
536	}	×
537
538	for tx in spk_history {	×
539	let tx_entry = relevant_txids.0.entry(tx.tx_hash).or_default();	×
540	if let Some(anchor) = determine_tx_anchor(cps, tx.height, tx.tx_hash) {	×
541	tx_entry.insert(anchor);	×
542	}	×
543	}
544	}
545	}
546	}	×

bitcoindevkit / bdk / 6192744084

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous