descriptors: Add a KEY expression representing a list of individual keys

achow101 commented at 8:09 pm on December 2, 2022: member

There are some cases where several individual keys are being used in the same descriptor functions. It can be inefficient to treat them all as separate descriptors. This PR adds a new syntax where multiple keys are provided in an array. This list of keys is a ranged KEY expression (like xpubs) with position in the range being explicitly provided. As the list of descriptors is a range, only non-ranged key expressions are allowed. This is to avoid issues with expanding nested ranges. xpubs can be used as key expressions so long as they do not specify a *.

The descriptors will be of the form func({KEY, KEY, KEY,...}).

DrahtBot commented at 8:09 pm on December 2, 2022: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Concept ACK	apoelstra, Sjors

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#22838 (descriptors: Be able to specify change and receiving in a single descriptor string by achow101)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

DrahtBot added the label Descriptors on Dec 2, 2022

achow101 force-pushed on Dec 2, 2022

darosior commented at 1:37 pm on December 3, 2022: member

So when expanding the descriptor containing func({A1,A2,A3},{B1,B2,B3}) at index 0, 1 and 2 you’d get func(A1,B1), func(A2,B2) and func(A3,B3). This can be expressed more concisely with a ranged xpub: func(A/*,B/*) will give you a similar behaviour when expanded at index 0, 1 and 2. The only differences in behaviour being:

This new syntax may be used with non-xpub keys
This new syntax would fail to be expanded at any index >2

I assume that 2) is never desirable for descriptors, the limitation can always be enforced by the application (“never expand at an index superior to 2”). What is a common situation where you wouldn’t be able to swap a “raw” key for an xpub?

apoelstra commented at 3:20 pm on December 3, 2022: contributor

concept ACK from me. I understand that the use is primarily in expressing pre-descriptor wallet patterns in descriptors.

This concept feels like it could be used (or is related to) multipath descriptors, like if it were possible to use multiple wildcards, one for “set indexing” and the other for “range indexing”.

achow101 commented at 4:35 pm on December 3, 2022: member

This concept feels like it could be used (or is related to) multipath descriptors, like if it were possible to use multiple wildcards, one for “set indexing” and the other for “range indexing”.

It does, but they’re slightly different. I had a discussion with @sipa about that and we concluded that it wasn’t useful at least for the purpose that this PR targets.

Multipath descriptors expands into multiple descriptors. In #22838, this is implemented as Parse returning multiple Descriptor objects. However in this PR, {KEY,KEY,KEY...} is interpreted as a single ranged PubkeyProvider like we do for xpubs. Doing it this way allows us to get the intended performance benefit for migrated non-HD wallets as interpreting it like multipath descriptors would just result in the same issue of having thousands of descriptors.

apoelstra commented at 5:20 pm on December 4, 2022: contributor

That makes sense. We may want to revisit, from a conceptual point of view (vs the concrete needs of the Core wallet), later on.

bigspider commented at 2:52 pm on December 5, 2022: none

This seems a rather ad-hoc extension that doesn’t match the usage of descriptors outside of bitcoin-core. Therefore, it might imho be detrimental to the adoption of descriptors, as it adds complexity to every other implementation, even if they don’t benefit of the additional feature.

Perhaps core could consider having some “extensions” to descriptors for these special use cases, while keeping the standardized descriptor language as lean as possible?

sipa commented at 2:57 pm on December 5, 2022: member

@bigspider I think that’s how we’ve been thinking about descriptors in the first place, a base language, with a set of extensions. There is no requirement that everyone implements all of them, as long as supported keywords have the same meaning across implementations. For example, new software might not care about pre-segwit pk/pkh/sh; that would mean implementing BIP380 (base language) and BIP382 (wpkh/wsh), but not BIP381 (pk/pkh/sh). But if they don’t implement those, they can’t give a different meaning to the same keywords.

Things like BIP384 (combo) and BIP385 (addr/raw) are probably already fairly Bitcoin Core specific.

luke-jr commented at 8:58 am on December 7, 2022: member

Would this scale well to migrating large pre-HD wallets?

achow101 commented at 4:38 pm on December 7, 2022: member

Would this scale well to migrating large pre-HD wallets?

I believe it will. It’s the intended use of this syntax.

achow101 force-pushed on Dec 12, 2022

in src/script/descriptor.cpp:309 in 8f4ee670b3 outdated

304+{
305+    std::vector<std::unique_ptr<PubkeyProvider>> m_pubkeys;
306+
307+public:
308+    ListPubkeyProvider(uint32_t exp_index, std::vector<std::unique_ptr<PubkeyProvider>> pubkeys) : PubkeyProvider(exp_index), m_pubkeys(std::move(pubkeys)) {}
309+    bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override

Sjors commented at 5:42 pm on December 13, 2022:

8f4ee670b34d984a7d20d2e44d1d80bb8f683a25: could make this a uint or check that it’s positive (though at(pos) would catch a negative value too).

achow101 commented at 9:19 pm on December 13, 2022:

Added a commit that does that.

in src/script/descriptor.cpp:336 in 8f4ee670b3 outdated

318+    {
319+        return std::accumulate(
320+            m_pubkeys.begin(), m_pubkeys.end(),
321+            0,
322+            [](const size_t acc, const std::unique_ptr<PubkeyProvider>& pubkey) {
323+                return std::max(acc, pubkey->GetSize());

Sjors commented at 5:58 pm on December 13, 2022:

8f4ee670b34d984a7d20d2e44d1d80bb8f683a25: Is this going to cause problems if compressed and uncompressed keys end up in a single descriptor? Maybe we should enforce keeping those separate (including when migrating from legacy)?

achow101 commented at 9:05 pm on December 13, 2022:

If there are mixed compressed and uncompressed keys in the list, then this will always use the uncompressed size, which may result in overestimating the size. I think this will only be used by miniscript though.

in src/test/descriptor_tests.cpp:464 in 70189d9eee outdated

457@@ -450,6 +458,11 @@ BOOST_AUTO_TEST_CASE(descriptor_test)
458     CheckUnparsable("sh(sh(pk(L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1)))", "sh(sh(pk(03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd)))", "Can only have sh() at top level"); // Cannot embed P2SH inside P2SH
459     CheckUnparsable("wsh(wsh(pk(L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1)))", "wsh(wsh(pk(03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd)))", "Can only have wsh() at top level or inside sh()"); // Cannot embed P2WSH inside P2WSH
460 
461+    // Using list of keys expression
462+    Check("pkh({L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1,KzoAz5CanayRKex3fSLQ2BwJpN7U52gZvxMyk78nDMHuqrUxuSJy,KwGNz6YCCQtYvFzMtrC6D3tKTKdBBboMrLTsjr2NYVBwapCkn7Mr})", "pkh({03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd,03669b8afcec803a0d323e9a17f3ea8e68e8abe5a278020a929adbec52421adbd0,0260b2003c386519fc9eadf2b5cf124dd8eea4c4e68d5e154050a9346ea98ce600})", "pkh({03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd,03669b8afcec803a0d323e9a17f3ea8e68e8abe5a278020a929adbec52421adbd0,0260b2003c386519fc9eadf2b5cf124dd8eea4c4e68d5e154050a9346ea98ce600})", RANGE | DERIVE_HARDENED | SIGNABLE, {{"76a9149a1c78a507689f6f54b847ad1cef1e614ee23f1e88ac"}, {"76a914a48e80ddd68b1a9ac7b3bdf028b00a1dbf5e450388ac"}}, OutputType::LEGACY, {{}, {}});

Sjors commented at 8:49 pm on December 13, 2022:

70189d9eee477c823ced260b746ef95e4093a4fa Why are RANGE | DERIVE_HARDENED set?

achow101 commented at 9:06 pm on December 13, 2022:

RANGE to do the range tests, DERIVE_HARDENED to avoid the xpub cache checks.

Sjors commented at 8:49 pm on December 13, 2022: member

Concept ACK, mostly happy with the code.

achow101 force-pushed on Jan 7, 2023

DrahtBot added the label Needs rebase on Feb 16, 2023

achow101 force-pushed on Feb 16, 2023

DrahtBot removed the label Needs rebase on Feb 16, 2023

achow101 requested review from sipa on Apr 25, 2023

achow101 requested review from josibake on Apr 25, 2023

DrahtBot added the label Needs rebase on May 8, 2023

achow101 force-pushed on May 8, 2023

DrahtBot removed the label Needs rebase on May 8, 2023

DrahtBot added the label CI failed on Jul 4, 2023

maflcko commented at 5:36 pm on July 4, 2023: member

Needs rebase if still relevant

maflcko commented at 8:48 am on July 21, 2023: member

Maybe mark as draft for as long as CI is red?

descriptors: Add ListPubkeyProvider for lists of single keys

ListPubkeyProvider is a ranged PubkeyProvider that returns individual
public keys that it was constructed with.

ec94996d99

descriptors: Add key expression for list of public keys

A new KEY expression is introduced which takes a list of non-ranged
public keys. This expression itself is ranged and can provide the key at
a particular index. It can take any KEY as long as it is not ranged.

29c53f908a

tests: Test descriptors with list of keys ee4c4bc588

descriptors: Change pos to uint32_t 1488496613

achow101 force-pushed on Jul 21, 2023

DrahtBot removed the label CI failed on Jul 21, 2023

achow101 closed this on Sep 20, 2023

bitcoin locked this on Sep 19, 2024

descriptors: Add a KEY expression representing a list of individual keys #26626

Reviews

Conflicts