bdk_chain/
spk_iter.rs

1use crate::{
2    bitcoin::{secp256k1::Secp256k1, ScriptBuf},
3    miniscript::{Descriptor, DescriptorPublicKey},
4    Indexed,
5};
6use core::{borrow::Borrow, ops::Bound, ops::RangeBounds};
7
8/// Maximum [BIP32](https://bips.xyz/32) derivation index.
9pub const BIP32_MAX_INDEX: u32 = (1 << 31) - 1;
10
11/// An iterator for derived script pubkeys.
12///
13/// [`SpkIterator`] is an implementation of the [`Iterator`] trait which possesses its own `next()`
14/// and `nth()` functions, both of which circumvent the unnecessary intermediate derivations
15/// required when using their default implementations.
16///
17/// ## Examples
18///
19/// ```
20/// use bdk_chain::SpkIterator;
21/// # use miniscript::{Descriptor, DescriptorPublicKey};
22/// # use bitcoin::{secp256k1::Secp256k1};
23/// # use std::str::FromStr;
24/// # let secp = bitcoin::secp256k1::Secp256k1::signing_only();
25/// # let (descriptor, _) = Descriptor::<DescriptorPublicKey>::parse_descriptor(&secp, "wpkh([73c5da0a/86'/0'/0']xprv9xgqHN7yz9MwCkxsBPN5qetuNdQSUttZNKw1dcYTV4mkaAFiBVGQziHs3NRSWMkCzvgjEe3n9xV8oYywvM8at9yRqyaZVz6TYYhX98VjsUk/1/0)").unwrap();
26/// # let external_spk_0 = descriptor.at_derivation_index(0).unwrap().script_pubkey();
27/// # let external_spk_3 = descriptor.at_derivation_index(3).unwrap().script_pubkey();
28/// # let external_spk_4 = descriptor.at_derivation_index(4).unwrap().script_pubkey();
29///
30/// // Creates a new script pubkey iterator starting at 0 from a descriptor.
31/// let mut spk_iter = SpkIterator::new(&descriptor);
32/// assert_eq!(spk_iter.next(), Some((0, external_spk_0)));
33/// assert_eq!(spk_iter.next(), None);
34/// ```
35#[derive(Clone)]
36pub struct SpkIterator<D> {
37    next_index: u32,
38    end: u32,
39    descriptor: D,
40    secp: Secp256k1<bitcoin::secp256k1::VerifyOnly>,
41}
42
43impl<D> SpkIterator<D>
44where
45    D: Borrow<Descriptor<DescriptorPublicKey>>,
46{
47    /// Create a new script pubkey iterator from `descriptor`.
48    ///
49    /// This iterates from derivation index 0 and stops at index 0x7FFFFFFF (as specified in
50    /// BIP-32). Non-wildcard descriptors will only return one script pubkey at derivation index 0.
51    ///
52    /// Use [`new_with_range`](SpkIterator::new_with_range) to create an iterator with a specified
53    /// derivation index range.
54    pub fn new(descriptor: D) -> Self {
55        SpkIterator::new_with_range(descriptor, 0..=BIP32_MAX_INDEX)
56    }
57
58    /// Create a new script pubkey iterator from `descriptor` and a given `range`.
59    ///
60    /// Non-wildcard descriptors will only emit a single script pubkey (at derivation index 0).
61    /// Wildcard descriptors have an end-bound of 0x7FFFFFFF (inclusive).
62    ///
63    /// Refer to [`new`](SpkIterator::new) for more.
64    pub fn new_with_range<R>(descriptor: D, range: R) -> Self
65    where
66        R: RangeBounds<u32>,
67    {
68        let start = match range.start_bound() {
69            Bound::Included(start) => *start,
70            Bound::Excluded(start) => *start + 1,
71            Bound::Unbounded => u32::MIN,
72        };
73
74        let mut end = match range.end_bound() {
75            Bound::Included(end) => *end + 1,
76            Bound::Excluded(end) => *end,
77            Bound::Unbounded => u32::MAX,
78        };
79
80        // Because `end` is exclusive, we want the maximum value to be BIP32_MAX_INDEX + 1.
81        end = end.min(BIP32_MAX_INDEX + 1);
82
83        Self {
84            next_index: start,
85            end,
86            descriptor,
87            secp: Secp256k1::verification_only(),
88        }
89    }
90
91    /// Get a reference to the internal descriptor.
92    pub fn descriptor(&self) -> &D {
93        &self.descriptor
94    }
95}
96
97impl<D> Iterator for SpkIterator<D>
98where
99    D: Borrow<Descriptor<DescriptorPublicKey>>,
100{
101    type Item = Indexed<ScriptBuf>;
102
103    fn next(&mut self) -> Option<Self::Item> {
104        // For non-wildcard descriptors, we expect the first element to be Some((0, spk)), then None
105        // after. For wildcard descriptors, we expect it to keep iterating until exhausted.
106        if self.next_index >= self.end {
107            return None;
108        }
109
110        // If the descriptor is non-wildcard, only index 0 will return an spk.
111        if !self.descriptor.borrow().has_wildcard() && self.next_index != 0 {
112            return None;
113        }
114
115        let script = self
116            .descriptor
117            .borrow()
118            .derived_descriptor(&self.secp, self.next_index)
119            .expect("the descriptor cannot need hardened derivation")
120            .script_pubkey();
121        let output = (self.next_index, script);
122
123        self.next_index += 1;
124
125        Some(output)
126    }
127
128    fn nth(&mut self, n: usize) -> Option<Self::Item> {
129        self.next_index = self
130            .next_index
131            .saturating_add(u32::try_from(n).unwrap_or(u32::MAX));
132        self.next()
133    }
134}
135
136#[cfg(test)]
137#[cfg_attr(coverage_nightly, coverage(off))]
138mod test {
139    use crate::{
140        bitcoin::secp256k1::Secp256k1,
141        indexer::keychain_txout::KeychainTxOutIndex,
142        miniscript::{Descriptor, DescriptorPublicKey},
143        spk_iter::{SpkIterator, BIP32_MAX_INDEX},
144    };
145
146    #[derive(Clone, Debug, PartialEq, Eq, Ord, PartialOrd)]
147    enum TestKeychain {
148        External,
149        Internal,
150    }
151
152    fn init_txout_index() -> (
153        KeychainTxOutIndex<TestKeychain>,
154        Descriptor<DescriptorPublicKey>,
155        Descriptor<DescriptorPublicKey>,
156    ) {
157        let mut txout_index = KeychainTxOutIndex::<TestKeychain>::new(0, true);
158
159        let secp = Secp256k1::signing_only();
160        let (external_descriptor,_) = Descriptor::<DescriptorPublicKey>::parse_descriptor(&secp, "tr([73c5da0a/86'/0'/0']xprv9xgqHN7yz9MwCkxsBPN5qetuNdQSUttZNKw1dcYTV4mkaAFiBVGQziHs3NRSWMkCzvgjEe3n9xV8oYywvM8at9yRqyaZVz6TYYhX98VjsUk/0/*)").unwrap();
161        let (internal_descriptor,_) = Descriptor::<DescriptorPublicKey>::parse_descriptor(&secp, "tr([73c5da0a/86'/0'/0']xprv9xgqHN7yz9MwCkxsBPN5qetuNdQSUttZNKw1dcYTV4mkaAFiBVGQziHs3NRSWMkCzvgjEe3n9xV8oYywvM8at9yRqyaZVz6TYYhX98VjsUk/1/*)").unwrap();
162
163        txout_index
164            .insert_descriptor(TestKeychain::External, external_descriptor.clone())
165            .unwrap();
166        txout_index
167            .insert_descriptor(TestKeychain::Internal, internal_descriptor.clone())
168            .unwrap();
169
170        (txout_index, external_descriptor, internal_descriptor)
171    }
172
173    #[test]
174    #[allow(clippy::iter_nth_zero)]
175    #[rustfmt::skip]
176    fn test_spkiterator_wildcard() {
177        let (_, external_desc, _) = init_txout_index();
178        let external_spk_0 = external_desc.at_derivation_index(0).unwrap().script_pubkey();
179        let external_spk_16 = external_desc.at_derivation_index(16).unwrap().script_pubkey();
180        let external_spk_20 = external_desc.at_derivation_index(20).unwrap().script_pubkey();
181        let external_spk_21 = external_desc.at_derivation_index(21).unwrap().script_pubkey();
182        let external_spk_max = external_desc.at_derivation_index(BIP32_MAX_INDEX).unwrap().script_pubkey();
183
184        let mut external_spk = SpkIterator::new(&external_desc);
185        let max_index = BIP32_MAX_INDEX - 22;
186
187        assert_eq!(external_spk.next(), Some((0, external_spk_0)));
188        assert_eq!(external_spk.nth(15), Some((16, external_spk_16)));
189        assert_eq!(external_spk.nth(3), Some((20, external_spk_20.clone())));
190        assert_eq!(external_spk.next(), Some((21, external_spk_21)));
191        assert_eq!(
192            external_spk.nth(max_index as usize),
193            Some((BIP32_MAX_INDEX, external_spk_max))
194        );
195        assert_eq!(external_spk.nth(0), None);
196
197        let mut external_spk = SpkIterator::new_with_range(&external_desc, 0..21);
198        assert_eq!(external_spk.nth(20), Some((20, external_spk_20)));
199        assert_eq!(external_spk.next(), None);
200
201        let mut external_spk = SpkIterator::new_with_range(&external_desc, 0..21);
202        assert_eq!(external_spk.nth(21), None);
203    }
204
205    #[test]
206    #[allow(clippy::iter_nth_zero)]
207    fn test_spkiterator_non_wildcard() {
208        let secp = bitcoin::secp256k1::Secp256k1::signing_only();
209        let (no_wildcard_descriptor, _) = Descriptor::<DescriptorPublicKey>::parse_descriptor(&secp, "wpkh([73c5da0a/86'/0'/0']xprv9xgqHN7yz9MwCkxsBPN5qetuNdQSUttZNKw1dcYTV4mkaAFiBVGQziHs3NRSWMkCzvgjEe3n9xV8oYywvM8at9yRqyaZVz6TYYhX98VjsUk/1/0)").unwrap();
210        let external_spk_0 = no_wildcard_descriptor
211            .at_derivation_index(0)
212            .unwrap()
213            .script_pubkey();
214
215        let mut external_spk = SpkIterator::new(&no_wildcard_descriptor);
216
217        assert_eq!(external_spk.next(), Some((0, external_spk_0.clone())));
218        assert_eq!(external_spk.next(), None);
219
220        let mut external_spk = SpkIterator::new(&no_wildcard_descriptor);
221
222        assert_eq!(external_spk.nth(0), Some((0, external_spk_0.clone())));
223        assert_eq!(external_spk.nth(0), None);
224
225        let mut external_spk = SpkIterator::new_with_range(&no_wildcard_descriptor, 0..0);
226
227        assert_eq!(external_spk.next(), None);
228
229        let mut external_spk = SpkIterator::new_with_range(&no_wildcard_descriptor, 0..1);
230
231        assert_eq!(external_spk.nth(0), Some((0, external_spk_0.clone())));
232        assert_eq!(external_spk.next(), None);
233
234        // We test that using new_with_range with range_len > 1 gives back an iterator with
235        // range_len = 1
236        let mut external_spk = SpkIterator::new_with_range(&no_wildcard_descriptor, 0..10);
237
238        assert_eq!(external_spk.nth(0), Some((0, external_spk_0)));
239        assert_eq!(external_spk.nth(0), None);
240
241        // non index-0 should NOT return an spk
242        assert_eq!(
243            SpkIterator::new_with_range(&no_wildcard_descriptor, 1..1).next(),
244            None
245        );
246        assert_eq!(
247            SpkIterator::new_with_range(&no_wildcard_descriptor, 1..=1).next(),
248            None
249        );
250        assert_eq!(
251            SpkIterator::new_with_range(&no_wildcard_descriptor, 1..2).next(),
252            None
253        );
254        assert_eq!(
255            SpkIterator::new_with_range(&no_wildcard_descriptor, 1..=2).next(),
256            None
257        );
258        assert_eq!(
259            SpkIterator::new_with_range(&no_wildcard_descriptor, 10..11).next(),
260            None
261        );
262        assert_eq!(
263            SpkIterator::new_with_range(&no_wildcard_descriptor, 10..=10).next(),
264            None
265        );
266    }
267}
268
269#[test]
270fn spk_iterator_is_send_and_static() {
271    fn is_send_and_static<A: Send + 'static>() {}
272    is_send_and_static::<SpkIterator<Descriptor<DescriptorPublicKey>>>()
273}
bdk_chain/spk_iter.rs

bdk_chain/
spk_iter.rs
