• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

bitcoindevkit / bdk / 5582722505

pending completion
5582722505

Pull #1002

github

web-flow
Merge 98a52d0cb into 81c761339
Pull Request #1002: Implement linked-list `LocalChain` and add rpc-chain module/example

945 of 945 new or added lines in 10 files covered. (100.0%)

8019 of 10332 relevant lines covered (77.61%)

5036.23 hits per line

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

0.0
/crates/electrum/src/electrum_ext.rs
1
use bdk_chain::{
2
    bitcoin::{hashes::hex::FromHex, OutPoint, Script, Transaction, Txid},
3
    keychain::LocalUpdate,
4
    local_chain::CheckPoint,
5
    tx_graph::{self, TxGraph},
6
    Anchor, BlockId, ConfirmationHeightAnchor, ConfirmationTimeAnchor,
7
};
8
use electrum_client::{Client, ElectrumApi, Error, HeaderNotification};
9
use std::{
10
    collections::{BTreeMap, BTreeSet, HashMap, HashSet},
11
    fmt::Debug,
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 an update 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::finalize`] to fetch
21
/// the full transactions from Electrum and finalize the update.
22
#[derive(Debug, Clone)]
×
23
pub struct ElectrumUpdate<K, A> {
24
    /// Map of [`Txid`]s to associated [`Anchor`]s.
25
    pub graph_update: HashMap<Txid, BTreeSet<A>>,
26
    /// The latest chain tip, as seen by the Electrum server.
27
    pub chain_update: CheckPoint,
28
    /// Last-used index update for [`KeychainTxOutIndex`](bdk_chain::keychain::KeychainTxOutIndex).
29
    pub keychain_update: BTreeMap<K, u32>,
30
}
31

32
impl<K, A: Anchor> ElectrumUpdate<K, A> {
33
    fn new(cp: CheckPoint) -> Self {
×
34
        Self {
×
35
            graph_update: HashMap::new(),
×
36
            chain_update: cp,
×
37
            keychain_update: BTreeMap::new(),
×
38
        }
×
39
    }
×
40

41
    /// Determine the full transactions that are missing from `graph`.
42
    ///
43
    /// Refer to [`ElectrumUpdate`].
44
    pub fn missing_full_txs<A2>(&self, graph: &TxGraph<A2>) -> Vec<Txid> {
×
45
        self.graph_update
×
46
            .keys()
×
47
            .filter(move |&&txid| graph.as_ref().get_tx(txid).is_none())
×
48
            .cloned()
×
49
            .collect()
×
50
    }
×
51

52
    /// Finalizes update with `missing` txids to fetch from `client`.
53
    ///
54
    /// Refer to [`ElectrumUpdate`].
55
    pub fn finalize(
×
56
        self,
×
57
        client: &Client,
×
58
        seen_at: Option<u64>,
×
59
        missing: Vec<Txid>,
×
60
    ) -> Result<LocalUpdate<K, A>, Error> {
×
61
        let new_txs = client.batch_transaction_get(&missing)?;
×
62
        let mut graph_update = TxGraph::<A>::new(new_txs);
×
63
        for (txid, anchors) in self.graph_update {
×
64
            if let Some(seen_at) = seen_at {
×
65
                let _ = graph_update.insert_seen_at(txid, seen_at);
×
66
            }
×
67
            for anchor in anchors {
×
68
                let _ = graph_update.insert_anchor(txid, anchor);
×
69
            }
×
70
        }
71
        Ok(LocalUpdate {
×
72
            keychain: self.keychain_update,
×
73
            graph: graph_update,
×
74
            tip: self.chain_update,
×
75
            introduce_older_blocks: true,
×
76
        })
×
77
    }
×
78
}
79

80
impl<K> ElectrumUpdate<K, ConfirmationHeightAnchor> {
81
    /// Finalizes the [`ElectrumUpdate`] with `new_txs` and anchors of type
82
    /// [`ConfirmationTimeAnchor`].
83
    ///
84
    /// **Note:** The confirmation time might not be precisely correct if there has been a reorg.
85
    /// Electrum's API intends that we use the merkle proof API, we should change `bdk_electrum` to
86
    /// use it.
87
    pub fn finalize_as_confirmation_time(
×
88
        self,
×
89
        client: &Client,
×
90
        seen_at: Option<u64>,
×
91
        missing: Vec<Txid>,
×
92
    ) -> Result<LocalUpdate<K, ConfirmationTimeAnchor>, Error> {
×
93
        let update = self.finalize(client, seen_at, missing)?;
×
94
        // client.batch_transaction_get(txid)
95

96
        let relevant_heights = {
×
97
            let mut visited_heights = HashSet::new();
×
98
            update
×
99
                .graph
×
100
                .all_anchors()
×
101
                .iter()
×
102
                .map(|(a, _)| a.confirmation_height_upper_bound())
×
103
                .filter(move |&h| visited_heights.insert(h))
×
104
                .collect::<Vec<_>>()
×
105
        };
106

107
        let height_to_time = relevant_heights
×
108
            .clone()
×
109
            .into_iter()
×
110
            .zip(
×
111
                client
×
112
                    .batch_block_header(relevant_heights)?
×
113
                    .into_iter()
×
114
                    .map(|bh| bh.time as u64),
×
115
            )
×
116
            .collect::<HashMap<u32, u64>>();
×
117

×
118
        let graph_additions = {
×
119
            let old_additions = TxGraph::default().determine_additions(&update.graph);
×
120
            tx_graph::Additions {
×
121
                txs: old_additions.txs,
×
122
                txouts: old_additions.txouts,
×
123
                last_seen: old_additions.last_seen,
×
124
                anchors: old_additions
×
125
                    .anchors
×
126
                    .into_iter()
×
127
                    .map(|(height_anchor, txid)| {
×
128
                        let confirmation_height = height_anchor.confirmation_height;
×
129
                        let confirmation_time = height_to_time[&confirmation_height];
×
130
                        let time_anchor = ConfirmationTimeAnchor {
×
131
                            anchor_block: height_anchor.anchor_block,
×
132
                            confirmation_height,
×
133
                            confirmation_time,
×
134
                        };
×
135
                        (time_anchor, txid)
×
136
                    })
×
137
                    .collect(),
×
138
            }
×
139
        };
×
140

×
141
        Ok(LocalUpdate {
×
142
            keychain: update.keychain,
×
143
            graph: {
×
144
                let mut graph = TxGraph::default();
×
145
                graph.apply_additions(graph_additions);
×
146
                graph
×
147
            },
×
148
            tip: update.tip,
×
149
            introduce_older_blocks: true,
×
150
        })
×
151
    }
×
152
}
153

154
/// Trait to extend [`Client`] functionality.
155
pub trait ElectrumExt<A> {
156
    /// Scan the blockchain (via electrum) for the data specified and returns a [`ElectrumUpdate`].
157
    ///
158
    /// - `prev_tip`: the most recent blockchain tip present locally
159
    /// - `keychain_spks`: keychains that we want to scan transactions for
160
    /// - `txids`: transactions for which we want updated [`Anchor`]s
161
    /// - `outpoints`: transactions associated with these outpoints (residing, spending) that we
162
    ///     want to included in the update
163
    ///
164
    /// The scan for each keychain stops after a gap of `stop_gap` script pubkeys with no associated
165
    /// transactions. `batch_size` specifies the max number of script pubkeys to request for in a
166
    /// single batch request.
167
    fn scan<K: Ord + Clone>(
168
        &self,
169
        prev_tip: Option<CheckPoint>,
170
        keychain_spks: BTreeMap<K, impl IntoIterator<Item = (u32, Script)>>,
171
        txids: impl IntoIterator<Item = Txid>,
172
        outpoints: impl IntoIterator<Item = OutPoint>,
173
        stop_gap: usize,
174
        batch_size: usize,
175
    ) -> Result<ElectrumUpdate<K, A>, Error>;
176

177
    /// Convenience method to call [`scan`] without requiring a keychain.
178
    ///
179
    /// [`scan`]: ElectrumExt::scan
180
    fn scan_without_keychain(
×
181
        &self,
×
182
        prev_tip: Option<CheckPoint>,
×
183
        misc_spks: impl IntoIterator<Item = Script>,
×
184
        txids: impl IntoIterator<Item = Txid>,
×
185
        outpoints: impl IntoIterator<Item = OutPoint>,
×
186
        batch_size: usize,
×
187
    ) -> Result<ElectrumUpdate<(), A>, Error> {
×
188
        let spk_iter = misc_spks
×
189
            .into_iter()
×
190
            .enumerate()
×
191
            .map(|(i, spk)| (i as u32, spk));
×
192

×
193
        self.scan(
×
194
            prev_tip,
×
195
            [((), spk_iter)].into(),
×
196
            txids,
×
197
            outpoints,
×
198
            usize::MAX,
×
199
            batch_size,
×
200
        )
×
201
    }
×
202
}
203

204
impl ElectrumExt<ConfirmationHeightAnchor> for Client {
205
    fn scan<K: Ord + Clone>(
×
206
        &self,
×
207
        prev_tip: Option<CheckPoint>,
×
208
        keychain_spks: BTreeMap<K, impl IntoIterator<Item = (u32, Script)>>,
×
209
        txids: impl IntoIterator<Item = Txid>,
×
210
        outpoints: impl IntoIterator<Item = OutPoint>,
×
211
        stop_gap: usize,
×
212
        batch_size: usize,
×
213
    ) -> Result<ElectrumUpdate<K, ConfirmationHeightAnchor>, Error> {
×
214
        let mut request_spks = keychain_spks
×
215
            .into_iter()
×
216
            .map(|(k, s)| (k, s.into_iter()))
×
217
            .collect::<BTreeMap<K, _>>();
×
218
        let mut scanned_spks = BTreeMap::<(K, u32), (Script, bool)>::new();
×
219

×
220
        let txids = txids.into_iter().collect::<Vec<_>>();
×
221
        let outpoints = outpoints.into_iter().collect::<Vec<_>>();
×
222

223
        let update = loop {
×
224
            let (tip, _) = construct_update_tip(self, prev_tip.clone())?;
×
225
            let mut update = ElectrumUpdate::<K, ConfirmationHeightAnchor>::new(tip.clone());
×
226
            let cps = update
×
227
                .chain_update
×
228
                .iter()
×
229
                .take(10)
×
230
                .map(|cp| (cp.height(), cp))
×
231
                .collect::<BTreeMap<u32, CheckPoint>>();
×
232

×
233
            if !request_spks.is_empty() {
×
234
                if !scanned_spks.is_empty() {
×
235
                    scanned_spks.append(&mut populate_with_spks(
×
236
                        self,
×
237
                        &cps,
×
238
                        &mut update,
×
239
                        &mut scanned_spks
×
240
                            .iter()
×
241
                            .map(|(i, (spk, _))| (i.clone(), spk.clone())),
×
242
                        stop_gap,
×
243
                        batch_size,
×
244
                    )?);
×
245
                }
×
246
                for (keychain, keychain_spks) in &mut request_spks {
×
247
                    scanned_spks.extend(
248
                        populate_with_spks(
×
249
                            self,
×
250
                            &cps,
×
251
                            &mut update,
×
252
                            keychain_spks,
×
253
                            stop_gap,
×
254
                            batch_size,
×
255
                        )?
×
256
                        .into_iter()
×
257
                        .map(|(spk_i, spk)| ((keychain.clone(), spk_i), spk)),
×
258
                    );
259
                }
260
            }
×
261

262
            populate_with_txids(self, &cps, &mut update, &mut txids.iter().cloned())?;
×
263

264
            let _txs =
×
265
                populate_with_outpoints(self, &cps, &mut update, &mut outpoints.iter().cloned())?;
×
266

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

×
273
            update.keychain_update = request_spks
×
274
                .into_keys()
×
275
                .filter_map(|k| {
×
276
                    scanned_spks
×
277
                        .range((k.clone(), u32::MIN)..=(k.clone(), u32::MAX))
×
278
                        .rev()
×
279
                        .find(|(_, (_, active))| *active)
×
280
                        .map(|((_, i), _)| (k, *i))
×
281
                })
×
282
                .collect::<BTreeMap<_, _>>();
×
283
            break update;
×
284
        };
×
285

×
286
        Ok(update)
×
287
    }
×
288
}
289

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

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

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

318
    // Find the "point of agreement" (if any).
319
    let agreement_cp = {
×
320
        let mut agreement_cp = Option::<CheckPoint>::None;
×
321
        for cp in prev_tip.iter().flat_map(CheckPoint::iter) {
×
322
            let cp_block = cp.block_id();
×
323
            let hash = match new_blocks.get(&cp_block.height) {
×
324
                Some(&hash) => hash,
×
325
                None => {
326
                    assert!(
×
327
                        new_tip_height >= cp_block.height,
×
328
                        "already checked that electrum's tip cannot be smaller"
×
329
                    );
330
                    let hash = client.block_header(cp_block.height as _)?.block_hash();
×
331
                    new_blocks.insert(cp_block.height, hash);
×
332
                    hash
×
333
                }
334
            };
335
            if hash == cp_block.hash {
×
336
                agreement_cp = Some(cp);
×
337
                break;
×
338
            }
×
339
        }
340
        agreement_cp
×
341
    };
×
342

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

×
345
    let new_tip = new_blocks
×
346
        .into_iter()
×
347
        // Prune `new_blocks` to only include blocks that are actually new.
×
348
        .filter(|(height, _)| Some(*height) > agreement_height)
×
349
        .map(|(height, hash)| BlockId { height, hash })
×
350
        .fold(agreement_cp, |prev_cp, block| {
×
351
            Some(match prev_cp {
×
352
                Some(cp) => cp.push(block).expect("must extend checkpoint"),
×
353
                None => CheckPoint::new(block),
×
354
            })
355
        })
×
356
        .expect("must have at least one checkpoint");
×
357

×
358
    Ok((new_tip, agreement_height))
×
359
}
×
360

361
/// A [tx status] comprises of a concatenation of `tx_hash:height:`s. We transform a single one of
362
/// these concatenations into a [`ConfirmationHeightAnchor`] if possible.
363
///
364
/// We use the lowest possible checkpoint as the anchor block (from `cps`). If an anchor block
365
/// cannot be found, or the transaction is unconfirmed, [`None`] is returned.
366
///
367
/// [tx status](https://electrumx-spesmilo.readthedocs.io/en/latest/protocol-basics.html#status)
368
fn determine_tx_anchor(
×
369
    cps: &BTreeMap<u32, CheckPoint>,
×
370
    raw_height: i32,
×
371
    txid: Txid,
×
372
) -> Option<ConfirmationHeightAnchor> {
×
373
    // The electrum API has a weird quirk where an unconfirmed transaction is presented with a
×
374
    // height of 0. To avoid invalid representation in our data structures, we manually set
×
375
    // transactions residing in the genesis block to have height 0, then interpret a height of 0 as
×
376
    // unconfirmed for all other transactions.
×
377
    if txid
×
378
        == Txid::from_hex("4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b")
×
379
            .expect("must deserialize genesis coinbase txid")
×
380
    {
381
        let anchor_block = cps.values().next()?.block_id();
×
382
        return Some(ConfirmationHeightAnchor {
×
383
            anchor_block,
×
384
            confirmation_height: 0,
×
385
        });
×
386
    }
×
387
    match raw_height {
×
388
        h if h <= 0 => {
×
389
            debug_assert!(h == 0 || h == -1, "unexpected height ({}) from electrum", h);
×
390
            None
×
391
        }
392
        h => {
×
393
            let h = h as u32;
×
394
            let anchor_block = cps.range(h..).next().map(|(_, cp)| cp.block_id())?;
×
395
            if h > anchor_block.height {
×
396
                None
×
397
            } else {
398
                Some(ConfirmationHeightAnchor {
×
399
                    anchor_block,
×
400
                    confirmation_height: h,
×
401
                })
×
402
            }
403
        }
404
    }
405
}
×
406

407
fn populate_with_outpoints<K>(
×
408
    client: &Client,
×
409
    cps: &BTreeMap<u32, CheckPoint>,
×
410
    update: &mut ElectrumUpdate<K, ConfirmationHeightAnchor>,
×
411
    outpoints: &mut impl Iterator<Item = OutPoint>,
×
412
) -> Result<HashMap<Txid, Transaction>, Error> {
×
413
    let mut full_txs = HashMap::new();
×
414
    for outpoint in outpoints {
×
415
        let txid = outpoint.txid;
×
416
        let tx = client.transaction_get(&txid)?;
×
417
        debug_assert_eq!(tx.txid(), txid);
×
418
        let txout = match tx.output.get(outpoint.vout as usize) {
×
419
            Some(txout) => txout,
×
420
            None => continue,
×
421
        };
422
        // attempt to find the following transactions (alongside their chain positions), and
423
        // add to our sparsechain `update`:
424
        let mut has_residing = false; // tx in which the outpoint resides
×
425
        let mut has_spending = false; // tx that spends the outpoint
×
426
        for res in client.script_get_history(&txout.script_pubkey)? {
×
427
            if has_residing && has_spending {
×
428
                break;
×
429
            }
×
430

×
431
            if res.tx_hash == txid {
×
432
                if has_residing {
×
433
                    continue;
×
434
                }
×
435
                has_residing = true;
×
436
                full_txs.insert(res.tx_hash, tx.clone());
×
437
            } else {
438
                if has_spending {
×
439
                    continue;
×
440
                }
×
441
                let res_tx = match full_txs.get(&res.tx_hash) {
×
442
                    Some(tx) => tx,
×
443
                    None => {
444
                        let res_tx = client.transaction_get(&res.tx_hash)?;
×
445
                        full_txs.insert(res.tx_hash, res_tx);
×
446
                        full_txs.get(&res.tx_hash).expect("just inserted")
×
447
                    }
448
                };
449
                has_spending = res_tx
×
450
                    .input
×
451
                    .iter()
×
452
                    .any(|txin| txin.previous_output == outpoint);
×
453
                if !has_spending {
×
454
                    continue;
×
455
                }
×
456
            };
457

458
            let anchor = determine_tx_anchor(cps, res.height, res.tx_hash);
×
459

×
460
            let tx_entry = update.graph_update.entry(res.tx_hash).or_default();
×
461
            if let Some(anchor) = anchor {
×
462
                tx_entry.insert(anchor);
×
463
            }
×
464
        }
465
    }
466
    Ok(full_txs)
×
467
}
×
468

469
fn populate_with_txids<K>(
×
470
    client: &Client,
×
471
    cps: &BTreeMap<u32, CheckPoint>,
×
472
    update: &mut ElectrumUpdate<K, ConfirmationHeightAnchor>,
×
473
    txids: &mut impl Iterator<Item = Txid>,
×
474
) -> Result<(), Error> {
×
475
    for txid in txids {
×
476
        let tx = match client.transaction_get(&txid) {
×
477
            Ok(tx) => tx,
×
478
            Err(electrum_client::Error::Protocol(_)) => continue,
×
479
            Err(other_err) => return Err(other_err),
×
480
        };
481

482
        let spk = tx
×
483
            .output
×
484
            .get(0)
×
485
            .map(|txo| &txo.script_pubkey)
×
486
            .expect("tx must have an output");
×
487

488
        let anchor = match client
×
489
            .script_get_history(spk)?
×
490
            .into_iter()
×
491
            .find(|r| r.tx_hash == txid)
×
492
        {
493
            Some(r) => determine_tx_anchor(cps, r.height, txid),
×
494
            None => continue,
×
495
        };
496

497
        let tx_entry = update.graph_update.entry(txid).or_default();
×
498
        if let Some(anchor) = anchor {
×
499
            tx_entry.insert(anchor);
×
500
        }
×
501
    }
502
    Ok(())
×
503
}
×
504

505
fn populate_with_spks<K, I: Ord + Clone>(
×
506
    client: &Client,
×
507
    cps: &BTreeMap<u32, CheckPoint>,
×
508
    update: &mut ElectrumUpdate<K, ConfirmationHeightAnchor>,
×
509
    spks: &mut impl Iterator<Item = (I, Script)>,
×
510
    stop_gap: usize,
×
511
    batch_size: usize,
×
512
) -> Result<BTreeMap<I, (Script, bool)>, Error> {
×
513
    let mut unused_spk_count = 0_usize;
×
514
    let mut scanned_spks = BTreeMap::new();
×
515

516
    loop {
×
517
        let spks = (0..batch_size)
×
518
            .map_while(|_| spks.next())
×
519
            .collect::<Vec<_>>();
×
520
        if spks.is_empty() {
×
521
            return Ok(scanned_spks);
×
522
        }
×
523

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

526
        for ((spk_index, spk), spk_history) in spks.into_iter().zip(spk_histories) {
×
527
            if spk_history.is_empty() {
×
528
                scanned_spks.insert(spk_index, (spk, false));
×
529
                unused_spk_count += 1;
×
530
                if unused_spk_count > stop_gap {
×
531
                    return Ok(scanned_spks);
×
532
                }
×
533
                continue;
×
534
            } else {
×
535
                scanned_spks.insert(spk_index, (spk, true));
×
536
                unused_spk_count = 0;
×
537
            }
×
538

539
            for tx in spk_history {
×
540
                let tx_entry = update.graph_update.entry(tx.tx_hash).or_default();
×
541
                if let Some(anchor) = determine_tx_anchor(cps, tx.height, tx.tx_hash) {
×
542
                    tx_entry.insert(anchor);
×
543
                }
×
544
            }
545
        }
546
    }
547
}
×
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2025 Coveralls, Inc