Add (sorted)multi_a descriptor for k-of-n multisig inside tr

sipa commented at 7:20 pm on January 11, 2022: member

This adds a new multi_a(k,key_1,key_2,...,key_n) (and corresponding sortedmulti_a) descriptor for k-of-n policies inside tr(). Semantically it is very similar to the existing multi() descriptor, but with the following changes:

The corresponding script is <key1> OP_CHECKSIG <key2> OP_CHECKSIGADD <key3> OP_CHECKSIGADD ... <key_n> OP_CHECKSIGADD <k> OP_NUMEQUAL, rather than the traditional OP_CHECKMULTISIG-based script, making it usable inside the tr() descriptor.
The keys can optionally be specified in x-only notation.
Both the number of keys and the threshold can be as high as 999; this is the limit due to the consensus stacksize=1000 limit

I expect that this functionality will later be replaced with a miniscript-based implementation, but I don’t think it’s necessary to wait for that.

Limitations:

The wallet code will for not estimate witness size incorrectly for script path spends, which may result in a (dramatic) fee underpayment with large multi_a scripts.
The multi_a script construction is (slightly) suboptimal for n-of-n (where a <key1> OP_CHECKSIGVERIFY ... <key_n-1> OP_CHECKSIGVERIFY <key_n> OP_CHECKSIG would be better). Such a construction is not included here.

sipa requested review from darosior on Jan 11, 2022

sipa requested review from achow101 on Jan 11, 2022

sipa force-pushed on Jan 11, 2022

DrahtBot added the label Descriptors on Jan 11, 2022

sipa force-pushed on Jan 11, 2022

sipa renamed this:
~~Add multi_a descriptor for k-of-n multisig inside tr~~
Add (sorted)multi_a descriptor for k-of-n multisig inside tr
on Jan 11, 2022

sipa force-pushed on Jan 11, 2022

in src/script/descriptor.cpp:31 in 9966b84894 outdated

22@@ -23,6 +23,13 @@
23 
24 namespace {
25 
26+/** Current maximum number of accepted public keys in a multi_a descriptor.
27+ *  The theoretical limit of what fits in 100000 vbytes is around 11418,
28+ *  but limit to a significantly smaller number to avoid running into
29+ *  transaction size limits when multiple of these occur in a transaction,
30+ *  and to keep descriptor strings of reasonable length. */
31+static constexpr unsigned int MAX_PUBKEYS_PER_MULTI_A = 512;

sanket1729 commented at 0:07 am on January 12, 2022:

In 9966b84894801879cda1d2639ab3da7f29be55e7:

We are actually limited by starting witness stack size. So the number of keys should be <= 1000 (excluding control block and script itself). 512 seems like a good choice. But the above comment can be updated

sipa commented at 4:13 am on January 12, 2022:

Oh, good point. That’s possibly a reason to set the limit to 999 instead (so that the first pubkey pushed doesn’t push it past 1000).

in src/script/standard.cpp:163 in 9966b84894 outdated

160+        keyspans.emplace_back(&*it, 32);
161+        it += 32;
162+        if (*it != (keyspans.size() == 1 ? OP_CHECKSIG : OP_CHECKSIGADD)) return {};
163+        ++it;
164+    }
165+    if (keyspans.size() == 0 || keyspans.size() > (MAX_BLOCK_WEIGHT / 34)) return {};

sanket1729 commented at 0:24 am on January 12, 2022:

In 9966b84: should this be keyspans.size() > MAX_PUBKEYS_PER_MULTI_A?

sipa commented at 4:17 am on January 12, 2022:

With your comment above, probably.

But my thinking here was that the matching code shouldn’t be as strict as the descriptors (in that signing should work if you happen to have a script that happens to exceed those policy-informed limits).

But if we set the limit to just 999, which appears to be the consensus limit, that’s something the matcher should also use.

sipa commented at 4:31 pm on January 12, 2022:

Fixed.

in src/script/standard.cpp:173 in 9966b84894 outdated

171+    if (it == script.end()) return {};
172+    if (*it != OP_NUMEQUAL) return {};
173+    ++it;
174+    if (it != script.end()) return {};
175+    int threshold;
176+    if (!GetMultisigKeyCount(opcode, data, threshold, (int)keyspans.size())) return {};

sanket1729 commented at 0:35 am on January 12, 2022:

In 9966b84:

nit: It is slightly confusing that the function named GetMultisigKeyCount is being used to decode the threshold and check that threshold is within limits. Can’t think of a clear better name

sipa commented at 4:30 pm on January 12, 2022:

I’ve renamed/refactored this function in a new initial commit.

in src/script/standard.cpp:174 in 9966b84894 outdated

172+    if (*it != OP_NUMEQUAL) return {};
173+    ++it;
174+    if (it != script.end()) return {};
175+    int threshold;
176+    if (!GetMultisigKeyCount(opcode, data, threshold, (int)keyspans.size())) return {};
177+    if ((size_t)threshold > keyspans.size()) return {};

sanket1729 commented at 0:38 am on January 12, 2022:

In 9966b84: This line is redundant because the above GetMultiSigKeyCount would check that threshold is less than keyspans.size()

sipa commented at 4:30 pm on January 12, 2022:

Fixed.

sanket1729 commented at 1:04 am on January 12, 2022: contributor

Left a few comments, did not review the tests.

DrahtBot commented at 3:17 am on January 12, 2022: contributor

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#24149 (Signing support for Miniscript Descriptors by darosior)
#24148 (Miniscript support in Output Descriptors by darosior)
#24147 (Miniscript integration by darosior)
#23578 (Add external signer taproot support by Sjors)
#23502 (wallet: Avoid underpaying transaction fees when signing taproot spends by achow101)
#22838 (descriptors: Be able to specify change and receiving in a single descriptor string by achow101)
#22558 (psbt: Taproot fields for PSBT 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.

sipa force-pushed on Jan 12, 2022

luke-jr commented at 8:02 am on January 12, 2022: member

It seems like the distinction between the normal and _a variants is likely to cause confusion. Can we not support multi being smart enough to pick the right script? Is there a reason not to do that? How bad of a situation can exist if someone uses the wrong one?

Merge/generalize IsValidMultisigKeyCount/GetMultisigKeyCount 25e95f9ff8

Add (sorted)multi_a descriptor and script derivation 79728c4a3d

Add multi_a descriptor inference 3eed6fca57

Add signing support for (sorted)multi_a scripts c17c6aa08d

Add tests for (sorted)multi_a derivation/signing eb0667ea96

Simplify wallet_taproot.py functional test b5f33ac1f8

Add (sorted)multi_a descriptors to doc/descriptors.md 4828d53ecc

sipa force-pushed on Jan 12, 2022

sipa commented at 4:35 pm on January 12, 2022: member

@luke-jr I like to keep the invariant that every “function” in descriptors (and later, miniscript) refer to the same opcode construction.

The reason is that while for this example it’s unambiguous (multi only in toplevel/sh/wsh, multi_a only in tr), that’s not going to be the case for all (or in the case of miniscript, even most) functions. So there will inevitably be constructions with variants which cannot be derived from the context, and given that it seems more consistent to keep the contextual smartness out of this.

luke-jr commented at 6:06 pm on January 12, 2022: member

How about erroring if they’re used in the wrong context?

sipa commented at 6:08 pm on January 12, 2022: member

@luke-jr They do (even before this PR).

Sjors commented at 6:35 pm on January 12, 2022: member

The multi_a script construction is (slightly) suboptimal for n-of-n (where…

Isn’t it also suboptimal for m-of-n where the permutations are sufficiently tractable to go in separate leaves? There may even be a privacy benefit to never revealing N. Neither is an objection to this descriptor though.

sanket1729 approved

sanket1729 commented at 10:59 pm on January 13, 2022: contributor

code review ACK 4828d53eccd52a67631c64cef0ba7df90dff138d

in src/script/standard.cpp:147 in 79728c4a3d outdated

138@@ -139,6 +139,40 @@ static bool MatchMultisig(const CScript& script, int& required_sigs, std::vector
139     return (it + 1 == script.end());
140 }
141 
142+std::optional<std::pair<int, std::vector<Span<const unsigned char>>>> MatchMultiA(const CScript& script)
143+{
144+    std::vector<Span<const unsigned char>> keyspans;
145+
146+    // Redundant, but very fast and selective test.
147+    if (script.size() == 0 || script[0] != 32 || script.back() != OP_NUMEQUAL) return {};

darosior commented at 9:21 am on January 18, 2022:

0if (script.size() > MAX_PUBKEYS_PER_MULTI_A * 34 + 3 + 1) return {};

Would also be a fast test bounding the potential number of iterations below.

in src/script/standard.cpp:168 in 79728c4a3d outdated

163+    std::vector<unsigned char> data;
164+    if (!script.GetOp(it, opcode, data)) return {};
165+    if (it == script.end()) return {};
166+    if (*it != OP_NUMEQUAL) return {};
167+    ++it;
168+    if (it != script.end()) return {};

darosior commented at 9:31 am on January 18, 2022:

nit: any reason to not combine these two lines?

in src/script/descriptor.cpp:1297 in 3eed6fca57 outdated

1292+    auto match = MatchMultiA(script);
1293+    if (!match) return {};
1294+    std::vector<std::unique_ptr<PubkeyProvider>> keys;
1295+    keys.reserve(match->second.size());
1296+    for (const auto keyspan : match->second) {
1297+        if (keyspan.size() != 32) return {};

darosior commented at 10:14 am on January 18, 2022:

This cannot happen?

in test/functional/test_framework/script.py:30 in eb0667ea96 outdated

26@@ -27,6 +27,7 @@
27 from .ripemd160 import ripemd160
28 
29 MAX_SCRIPT_ELEMENT_SIZE = 520
30+MAX_PUBKEYS_PER_MULTI_A = 512

darosior commented at 10:19 am on January 18, 2022:

This should be 999.

darosior commented at 10:37 am on January 18, 2022:

Oh, actually it’s part of the next commit

darosior approved

darosior commented at 10:42 am on January 18, 2022: member

Code review ACK 4828d53eccd52a67631c64cef0ba7df90dff138d

michaelfolkson commented at 12:27 pm on January 31, 2022: contributor

Concept ACK, Approach ACK

I’ll attempt to summarize some additional context that was discussed in Friday’s Core wallet meeting that may be helpful for other reviewers too. (It was helpful for me. Apologies if I get any of this wrong and it needs a correction)

It seems like the distinction between the normal and _a variants is likely to cause confusion.

If you consider descriptors and Miniscript as one thing under a single name (which one day hopefully they will be, we already consider Miniscript as an extension to descriptors) then Miniscript already has suffixes such as and_b. The idea would be that the user would specify a Policy of multi (Policy doesn’t have suffixes) and then the Policy to Miniscript compiler would determine whether it should be multi_a, multi_b etc depending on what the most efficient Miniscript is. This will most likely to be done outside of Core as the compiler isn’t expected to be part of Core.

Can we not support multi being smart enough to pick the right script?

Each descriptor and each Miniscript is one-to-one with a specific script. I think multi at the Policy level will be able to pick the most efficient script using the Policy to Miniscript compiler. Still a lot of work to do though as Miniscript doesn’t currently support Taproot.

Isn’t it also suboptimal for m-of-n where the permutations are sufficiently tractable to go in separate leaves? There may even be a privacy benefit to never revealing N. Neither is an objection to this descriptor though.

As Sjors says there will be likely be many alternative Miniscripts that a Taproot multi Policy could compile down to. A 2-of-3 could be a single script path (a single Tapleaf) or it could be three 2-of-2s (one key path using MuSig2 and two script paths ) and that is before we have threshold key aggregation schemes (FROST etc) that could allow us to put the 2-of-3 directly in the key path.

achow101 commented at 6:54 pm on February 15, 2022: member

ACK 4828d53eccd52a67631c64cef0ba7df90dff138d

gruve-p commented at 3:05 pm on February 21, 2022: contributor

ACK https://github.com/bitcoin/bitcoin/pull/24043/commits/4828d53eccd52a67631c64cef0ba7df90dff138d

maflcko added this to the milestone 24.0 on Feb 21, 2022

achow101 merged this on Mar 4, 2022

achow101 closed this on Mar 4, 2022

michaelfolkson commented at 2:52 pm on March 4, 2022: contributor

@achow101: FYI there’s some unresolved comments from @darosior above.

darosior commented at 3:13 pm on March 4, 2022: member

No worries, they are nits that’s why i acked. :)

——– Original Message ——– On Mar 4, 2022, 14:53, Michael Folkson wrote:

@.(https://github.com/achow101): FYI there’s some unresolved comments from @.(https://github.com/darosior) above.

— Reply to this email directly, view it on GitHub, or unsubscribe. Triage notifications on the go with GitHub Mobile for iOS or Android. You are receiving this because you were mentioned.Message ID: @.***>

achow101 commented at 3:14 pm on March 4, 2022: member

nits are non-blocking

sidhujag referenced this in commit 7c3585c2aa on Mar 5, 2022

ajtowns commented at 4:41 am on March 7, 2022: contributor

The tr(H,multi_a(1,XPUB,XPRV)) test seems to be occasionally failing CI? https://cirrus-ci.com/task/4848707953754112 (through PSBT) https://cirrus-ci.com/task/6303111479296000 (address derivation) [EDIT: I’ve managed to reproduce this failure once on the master branch locally, but so far it hasn’t repeated since I’ve added debug output]

ajtowns commented at 10:34 am on March 7, 2022: contributor

I think the problem might be if different calls to do_test result in the same key being selected via keys = self.rand_keys(nkeys * 4) as in a previous invocation, then self.addr_gen will increment the derivation path from whatever was last used and choose /4 for addr_g, while addr_r will reuse the /0 path, and they’ll get different results causing an assertion failure.

achow101 commented at 10:53 am on March 7, 2022: member

I think the problem might be if different calls to do_test result in the same key being selected via keys = self.rand_keys(nkeys * 4) as in a previous invocation, then self.addr_gen will increment the derivation path from whatever was last used and choose /4 for addr_g, while addr_r will reuse the /0 path, and they’ll get different results causing an assertion failure.

I’m seeing it fail with other indexes too. I think it’s actually that multi_a and sortedmulti_a with the same keys will sometimes produce the same addresses for a given index. When the descriptor is imported, it finds that one of the previous addresses was used so it starts at an index other than 0, which is why we get the assertion failure.

achow101 commented at 11:01 am on March 7, 2022: member

#24490 should fix the test failure

ajtowns commented at 11:07 am on March 7, 2022: contributor

Makes sense!

in doc/descriptors.md:36 in 4828d53ecc

32@@ -33,6 +33,7 @@ Output descriptors currently support:
33 - Pay-to-taproot outputs (P2TR), through the `tr` function.
34 - Multisig scripts, through the `multi` function.
35 - Multisig scripts where the public keys are sorted lexicographically, through the `sortedmulti` function.
36+- Multisig scripts inside taproot script trees, through the `multi_a` (and `sortedmulti_a`) function.

kouloumos commented at 4:41 pm on October 29, 2022:

Should this also be included in the 24.0 release notes?

Something like

tr() descriptors now support multisig scripts through the multi_a (and sortedmulti_a) function.

fanquake referenced this in commit bc67215b29 on Nov 25, 2022

sidhujag referenced this in commit 5935c81a28 on Nov 25, 2022

delta1 referenced this in commit 45f83fd396 on Oct 13, 2023

bitcoin locked this on Oct 29, 2023

Add (sorted)multi_a descriptor for k-of-n multisig inside tr #24043

Conflicts