bitcoindevkit / bitcoindevkit/bdk_wallet
`extract_policy` enumerates all m-of-n combinations; impractical for large `multi_a`
- Dominant language
- Rust
- Stars
- 59
- Forks
- 105
- Avg merge
- 10d 9h
- Merged PRs (30d)
- 1
Description
**Describe the bug**
`Satisfaction::finalize` in `src/descriptor/policy.rs` eagerly materializes every `m`-of-`n` combination of the available items (`combinations(items, *m)` returning `Vec>`, then further expanded via `mix` for items with multiple conditions) in order to turn a `Partial` satisfaction into `PartialComplete`. The work is `O(C(n, m))` in time and memory.
For legacy/segwit `multi` this is bounded by the 20-key limit, but `multi_a` allows up to 999 keys, so `extract_policy` on a taproot descriptor with a large `multi_a` can take minutes or effectively never finish. `finalize` runs on both the `contribution` (keys available in `SignersContainer`) and the `satisfaction` (signatures present in the PSBT) side whenever `items.len() >= m`, so it can be triggered either by the wallet's own key set or by a PSBT with enough signature entries.
This issue was found by AI.
**To Reproduce**
`tr(K0/0/*, multi_a(k, K1/0/*, ..., Kn/0/*))` with all keys in the `SignersContainer`, then `extract_policy(&signers, BuildSatisfaction::None, &secp)`. Measured on master (`6fc68462`), release build:
| descriptor | combinations | time |
|---|---|---|
| `multi_a(8, 16 keys)` | 12,870 | 26 ms |
| `multi_a(10, 20 keys)` | 184,756 | 362 ms |
| `multi_a(12, 24 keys)` | 2,704,156 | 6.3 s |
`multi_a(15, 30 keys)` would be ~155M combinations; larger thresholds are impractical.
**Expected behavior**
`extract_policy` should complete in reasonable time for any valid descriptor. Whether that means computing conditions lazily, bounding the enumeration, or representing `PartialComplete` differently is up to the maintainers.
**Build environment**
- BDK tag/commit: `6fc68462` (master)
**Which backend(s) are relevant (if any)?**
- [x] None / not backend-related (e.g. `bdk_chain`, `bdk_core`)
**Is this blocking production use?**
- [x] No
Contributor guide
Research direction
Start in src/descriptor/policy.rs at Satisfaction::finalize and trace how extract_policy invokes it for contribution and satisfaction items. Reproduce the provided large multi_a cases, then determine an approach that avoids impractical exhaustive enumeration; done means extract_policy completes in reasonable time for any valid descriptor.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- cryptography
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100