bitcoindevkit / bitcoindevkit/bdk_wallet

`extract_policy` enumerates all m-of-n combinations; impractical for large `multi_a`

Open
#555 0 comments 0 reactions 0 assignees View on GitHub
bug
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.