MiniTapscript: port Miniscript to Tapscript

darosior commented at 12:24 pm on March 14, 2023: member

Miniscript was targeting P2WSH, and as such can currently only be used in wsh() descriptors. This pull request introduces support for Tapscript in Miniscript and makes Miniscript available inside tr() descriptors. It adds support for both watching and signing TapMiniscript descriptors.

The main changes to Miniscript for Tapscript are the following:

A new multi_a fragment is introduced with the same semantics as multi. Like in other descriptors multi and multi_a can exclusively be used in respectively P2WSH and Tapscript.
The d: fragment has the u property under Tapscript, since the MINIMALIF rule is now consensus. See also #24906.
Keys are now serialized as 32 bytes. (Note this affects the key hashes.)
The resource consumption checks and calculation changed. Some limits were lifted in Tapscript, and signatures are now 64 bytes long.

The largest amount of complexity probably lies in the last item. Scripts under Taproot can now run into the maximum stack size while executing a fragment. For instance if you’ve got a stack size of 999 due to the initial witness plus some execution that happened before and try to execute a hash256 it would DUP (increasing the stack size 1000), HASH160 and then push the hash on the stack making the script fail. To make sure this does not happen on any of the spending paths of a sane Miniscript, we introduce a tracking of the maximum stack size during execution of a fragment. See the commits messages for details. Those commits were separated from the resource consumption change, and the fuzz target was tweaked to sometimes pad the witness so the script runs on the brink of the stack size limit to make sure the stack size was not underestimated.

Existing Miniscript unit, functional and fuzz tests are extended with Tapscript logic and test cases. Care was taken for seed stability in the fuzz targets where we cared more about them.

The design of Miniscript for Tapscript is the result of discussions between various people over the past year(s). To the extent of my knowledge at least Pieter Wuille, Sanket Kanjalkar, Andrew Poelstra and Andrew Chow contributed thoughts and ideas.

DrahtBot commented at 12:24 pm on March 14, 2023: contributor

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

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	sipa, achow101
Concept ACK	michaelfolkson, josibake
Stale ACK	scgbckbone, bigspider

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:

#28602 (descriptors: Disallow hybrid and uncompressed keys when inferring by achow101)
#28583 (refactor: [tidy] modernize-use-emplace by maflcko)
#28528 (test: Use test framework utils in functional tests by osagie98)
#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.

michaelfolkson commented at 12:40 pm on March 14, 2023: contributor

Concept ACK, an important piece in opening up Taproot scripting.

The design of Miniscript for Tapscript is the result of discussions between various people over the past year(s).

Your PR description is great but perhaps you can link to a few of those discussions for extra background reading for those that are interested? e.g. https://gist.github.com/sipa/06c5c844df155d4e5044c2c8cac9c05e

Also just checking if this PR should be in Draft or not? Are there ongoing open discussions on anything important or is this ready for extensive review?

darosior force-pushed on Mar 14, 2023

darosior commented at 2:31 pm on March 14, 2023: member

Yeah, thanks for the suggestion. Reviewers may be interested in https://github.com/sipa/miniscript/pull/134 as well.

Also just checking if this PR should be in Draft or not? Are there ongoing open discussions on anything important or is this ready for extensive review?

It is ready for (extensive or not) review. Otherwise i’d have opened it as a draft. But please tell me clearly if you disagree.

darosior commented at 2:58 pm on March 14, 2023: member

As it stands in this PR it would be possible to import a tr() descriptor unspendable by standardness: in addition to the script itself, we also need to check if the whole witness (including the control block, which is outside Miniscript..) isn’t larger than the maximum standard transaction size.

EDIT: Actually since we are still bounded by the MAX_STACK_SIZE of 1000 and no element is larger than 65 bytes, i think we can do something more elegant than having to compute the maximum witness size of a script. Just have the following conservative bound: refuse any script whose size is larger than MAX_STANDARD_TX_WEIGHT - (1 + 65) * MAX_STACK_SIZE - TAPROOT_CONTROL_MAX_SIZE (i.e. 329871 bytes). This is still plenty, and should there ever be a usecase for a larger script we can always relax this check by having an accurate max witness size calculation.

in src/script/miniscript.h:2142 in 33f28a8d47 outdated

2135@@ -1901,7 +2136,38 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
2136                 if (!k || *k < 1 || *k > *n) return {};
2137                 in += 3 + *n;
2138                 std::reverse(keys.begin(), keys.end());
2139-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::MULTI, std::move(keys), *k));
2140+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx, Fragment::MULTI, std::move(keys), *k));
2141+                break;
2142+            }
2143+            // Tapscript's multi

bigspider commented at 8:57 am on March 15, 2023:

Perhaps multi_a for consistency, since multi is a valid fragment elsewhere? Or Tapscript multisig if you want to explicitly not refer to the fragment.

in src/script/miniscript.h:1487 in 62d31e6c7b outdated

1187@@ -1188,23 +1188,28 @@ struct Node {
1188     //! Return the number of ops in the script (not counting the dynamic ones that depend on execution).
1189     uint32_t GetStaticOps() const { return ops.count; }
1190 
1191-    //! Check the ops limit of this script against the consensus limit.
1192-    bool CheckOpsLimit() const { return GetOps() <= MAX_OPS_PER_SCRIPT; }
1193+    //! Check the ops limit of this script against the consensus limit. This limit is only present for P2WSH.
1194+    template <typename Ctx> bool CheckOpsLimit(const Ctx& ctx) const {
1195+        return ctx.MsContext() == MiniscriptContext::TAPSCRIPT || GetOps() <= MAX_OPS_PER_SCRIPT;
1196+    }

bigspider commented at 2:42 pm on March 15, 2023:

It might be worth explicitly enumerating both the known contexts, and have a defensive final assert(false);. Similarly for other places where the context is accessed).

darosior commented at 2:55 pm on March 15, 2023:

I could have a IsTapscript(ctx) helper that does that next to the MiniscriptContext enum. It could then be used in all those places to not have to duplicate the verbose switch () ... assert(false).

darosior commented at 3:33 pm on March 16, 2023:

Alright, finally applied the change to the many occurrences in each commit. It should also be more readable now.

in src/script/miniscript.h:1334 in 33f28a8d47 outdated

1336-    bool CheckStackSize() const { return GetStackSize() - 1 <= MAX_STANDARD_P2WSH_STACK_ITEMS; }
1337+    //! Check the maximum stack size for this script against the limits.
1338+    template <typename Ctx> bool CheckStackSize(const Ctx& ctx) const {
1339+        if (ctx.MsContext() == MiniscriptContext::P2WSH && GetStackSize() > MAX_STANDARD_P2WSH_STACK_ITEMS) {
1340+            return false;
1341+        }

bigspider commented at 3:08 pm on March 15, 2023:

Why not this?

0        if (ctx.MsContext() == MiniscriptContext::P2WSH) {
1            return GetStackSize() <= MAX_STANDARD_P2WSH_STACK_ITEMS;
2        }

Otherwise, it seems to add the other condition for the P2WSH context as well.

darosior commented at 11:57 am on March 16, 2023:

Yeah, it didn’t matter since the computation is trivial and the bounds more loose for Tapscript anyways. But your suggestion is clearer indeed, taken, thanks.

in src/test/descriptor_tests.cpp:540 in 33f28a8d47 outdated

536@@ -536,10 +537,10 @@ BOOST_AUTO_TEST_CASE(descriptor_test)
537 
538     // Invalid checksum
539     CheckUnparsable("wsh(and_v(vc:andor(pk(L4gM1FBdyHNpkzsFh9ipnofLhpZRp2mwobpeULy1a6dBTvw8Ywtd),pk_k(Kx9HCDjGiwFcgVNhTrS5z5NeZdD6veeam61eDxLDCkGWujvL4Gnn),and_v(v:older(1),pk_k(L4o2kDvXXDRH2VS9uBnouScLduWt4dZnM25se7kvEjJeQ285en2A))),after(10)))#abcdef12", "wsh(and_v(vc:andor(pk(03cdabb7f2dce7bfbd8a0b9570c6fd1e712e5d64045e9d6b517b3d5072251dc204),pk_k(032707170c71d8f75e4ca4e3fce870b9409dcaf12b051d3bcadff74747fa7619c0),and_v(v:older(1),pk_k(02aa27e5eb2c185e87cd1dbc3e0efc9cb1175235e0259df1713424941c3cb40402))),after(10)))#abcdef12", "Provided checksum 'abcdef12' does not match computed checksum 'tyzp6a7p'");
540-    // Only p2wsh context is valid
541-    CheckUnparsable("sh(and_v(vc:andor(pk(L4gM1FBdyHNpkzsFh9ipnofLhpZRp2mwobpeULy1a6dBTvw8Ywtd),pk_k(Kx9HCDjGiwFcgVNhTrS5z5NeZdD6veeam61eDxLDCkGWujvL4Gnn),and_v(v:older(1),pk_k(L4o2kDvXXDRH2VS9uBnouScLduWt4dZnM25se7kvEjJeQ285en2A))),after(10)))", "sh(and_v(vc:andor(pk(03cdabb7f2dce7bfbd8a0b9570c6fd1e712e5d64045e9d6b517b3d5072251dc204),pk_k(032707170c71d8f75e4ca4e3fce870b9409dcaf12b051d3bcadff74747fa7619c0),and_v(v:older(1),pk_k(02aa27e5eb2c185e87cd1dbc3e0efc9cb1175235e0259df1713424941c3cb40402))),after(10)))", "Miniscript expressions can only be used in wsh");
542+    // Only p2wsh or tr context are valid

bigspider commented at 3:14 pm on March 15, 2023:

Typo: “contexts”

darosior commented at 11:58 am on March 16, 2023:

Meh. Done.

in src/test/fuzz/miniscript.cpp:1151 in 33f28a8d47 outdated

1147@@ -1017,7 +1148,7 @@ void TestNode(const NodeRef& node, FuzzedDataProvider& provider)
1148             assert(it != TEST_DATA.dummy_sigs.end());
1149             return it->second.second;
1150         }
1151-        case Fragment::MULTI: {
1152+        case Fragment::MULTI: case Fragment::MULTI_A: {

bigspider commented at 3:20 pm on March 15, 2023:

Nit: missing a newline

darosior commented at 12:01 pm on March 16, 2023:

Hmm i thought i was following the style used elsewhere, but i must have dreamed it. Done.

in src/script/miniscript.h:331 in 157c4a047b outdated

315@@ -316,11 +316,22 @@ struct MaxInt {
316         return a.value + b.value;
317     }
318 
319+    friend MaxInt<I> operator-(const MaxInt<I>& a, const I& b) {
320+        if (!a.valid) return {};
321+        return a.value - b;

bigspider commented at 3:25 pm on March 15, 2023:

I suppose it never happens, but worth checking that a.value >= b? Especially since it could be used with unsigned types.

darosior commented at 12:06 pm on March 16, 2023:

Hmm that’s a good point re unsigned type, but it needs to be able to return negative values. So i guess it’s up to the caller to make sure they don’t call this with b > a if a is unsigned, as with regular substractions?

darosior force-pushed on Mar 16, 2023

darosior commented at 5:04 pm on March 16, 2023: member

In the last push i’ve:

Added a commit to avoid a stack overflow during the destruction of a too large Node, due to recursive calls in shared_ptr’s destructor. (The reason the CI was failing under MSVC.)
Lowered the maximum size of a TapMiniscript to make sure a spending witness would never hit the maximum standard transaction size limit. (It’s still pretty high.)
Addressed all comments from @bigspider.

This PR is now ready for another round of review.

darosior force-pushed on Mar 17, 2023

darosior commented at 10:31 am on March 17, 2023: member

Pushed to try to wake the CI up. Looks like it worked!

Sjors commented at 12:40 pm on March 17, 2023: member

Very cool. I also noticed bitcoin.sipa.be/miniscript has been updated.

Has there been any thought into how MuSig2 (and threshold friends) would fit into this in the future? I guess that’s only a problem for the compiler, since for the purpose of script it doesn’t matter if e.g. public key C is an aggregate of A + B. But it does change the meaning of something like tr(C,multi_a(2,A,B)) (i.e. regular tapscript multisig fallback if MuSig2 coordination fails - maybe not a good example, since this already works).

michaelfolkson commented at 12:45 pm on March 17, 2023: contributor

Has there been any thought into how MuSig2 (and threshold friends) would fit into this in the future?

Discussed in sipa’s gist. Can comment on that gist @Sjors

Ayaan7211 approved

josibake commented at 3:30 pm on March 27, 2023: member

Concept ACK

DrahtBot added the label Needs rebase on Apr 5, 2023

in src/script/descriptor.cpp:1527 in ef0eb7f87d outdated

1523@@ -1502,7 +1524,7 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const
1524     }
1525     // Process miniscript expressions.
1526     {
1527-        KeyParser parser(&out, nullptr);
1528+        KeyParser parser(/*out = */&out, /* in = */nullptr, /* ctx = */miniscript::MiniscriptContext::P2WSH);

josibake commented at 10:04 am on April 7, 2023:

0        KeyParser parser(/*out =*/&out, /*in=*/nullptr, /*ctx=*/miniscript::MiniscriptContext::P2WSH);

darosior commented at 8:48 am on May 3, 2023:

What’s the rationale for changing this? Do whitespaces prevent the analysis? Happy to do this (and the other similar comments) but i’d rather not go through the hassle of applying it on every single of the 21 commits and solve the rebase conflicts if it’s just a style nit. Let me know!

sipa commented at 10:28 pm on July 8, 2023:

clang-tidy --checks=bugprone-argument-comment catches if the names in such comments mismatch the formal parameter names of the called function, but (I just tested) it works both with and without the spaces.

in src/script/descriptor.cpp:1695 in ef0eb7f87d outdated

1691@@ -1670,7 +1692,7 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo
1692     }
1693 
1694     if (ctx == ParseScriptContext::P2WSH) {
1695-        KeyParser parser(nullptr, &provider);
1696+        KeyParser parser(/* out = */nullptr, /* in = */&provider, /* ctx = */miniscript::MiniscriptContext::P2WSH);

josibake commented at 10:05 am on April 7, 2023:

0        KeyParser parser(/*out=*/nullptr, /*in=*/&provider, /*ctx=*/miniscript::MiniscriptContext::P2WSH);

in src/script/miniscript.cpp:21 in 1360b541ae outdated

16+{
17+    switch (ms_ctx) {
18+        case MiniscriptContext::P2WSH: return false;
19+        case MiniscriptContext::TAPSCRIPT: return true;
20+    }
21+    assert(false);

josibake commented at 10:17 am on April 7, 2023:

iirc, assert crashes the node. wouldn’t it be better to use the Assume macro?

darosior commented at 8:53 am on May 3, 2023:

This specific case is the very common match-all-variants-and-assert pattern so i think it’s good like that. It’s also documented this way in our style guidelines: https://github.com/bitcoin/bitcoin/blob/master/doc/developer-notes.md#c-data-structures.

in src/script/miniscript.h:611 in 1360b541ae outdated

607@@ -605,6 +608,7 @@ struct Node {
608                 case Fragment::OR_I: return BuildScript(OP_IF, subs[0], OP_ELSE, subs[1], OP_ENDIF);
609                 case Fragment::ANDOR: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[2], OP_ELSE, subs[1], OP_ENDIF);
610                 case Fragment::MULTI: {
611+                    assert(!IsTapscript(ctx.MsContext()));

josibake commented at 10:17 am on April 7, 2023:

same comment as above re: assert

darosior commented at 9:00 am on May 3, 2023:

For this and the other assertions of the context: if we get in such an inconsistent state as having a multi_a in a wsh() descriptor or a multi in a tr() descriptor, it’s probably better to crash than to return inconsistent (and potentially harmful, like an unspendable address) data to the user. Though it could raise an exception instead of crashing the node. I’ll see if i can use CHECK_NONFATAL instead.

EDIT: used CHECK_NONFATAL instead here and for MULTI_A too.

in src/script/miniscript.h:711 in 1360b541ae outdated

707@@ -704,6 +708,7 @@ struct Node {
708                     if (node.subs[2]->fragment == Fragment::JUST_0) return std::move(ret) + "and_n(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
709                     return std::move(ret) + "andor(" + std::move(subs[0]) + "," + std::move(subs[1]) + "," + std::move(subs[2]) + ")";
710                 case Fragment::MULTI: {
711+                    assert(!IsTapscript(ctx.MsContext()));

josibake commented at 10:18 am on April 7, 2023:

same comment as above re: assert

in src/script/miniscript.h:1542 in 1360b541ae outdated

1538@@ -1534,6 +1539,7 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
1539                 in = in.subspan(arg_size + 1);
1540                 script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
1541             } else if (Const("multi(", in)) {
1542+                if (IsTapscript(ctx.MsContext())) return {};

josibake commented at 10:20 am on April 7, 2023:

probably out of scope for this PR, but it would be nice to have the parser tell you why it wasn’t able to parse the script, rather than just return empty

darosior commented at 9:24 am on May 3, 2023:

Yes generally it would be nice to have better error reporting for descriptors. And i think there are lower hanging fruits when it comes to unclear descriptor errors that confuse users, for instance https://bitcoin.stackexchange.com/q/118022/101498.

But yeah definitely not going to bring that into this PR. :)

in src/script/miniscript.cpp:12 in 1360b541ae outdated

10@@ -11,6 +11,16 @@
11 #include <assert.h>
12

josibake commented at 10:23 am on April 7, 2023:

not a big deal, but I think it’s more correct to say “CHECKMULTISIG is disabled in Tapscript” in the commit message

darosior commented at 9:25 am on May 3, 2023:

Done.

in src/script/miniscript.h:1963 in c0ba8ebbf6 outdated

1636-                }
1637-                if (keys.size() < 1 || keys.size() > 20) return {};
1638-                if (k < 1 || k > (int64_t)keys.size()) return {};
1639-                script_size += 2 + (keys.size() > 16) + (k > 16) + 34 * keys.size();
1640-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::MULTI, std::move(keys), k));
1641+                if (!parse_multi_exp(in, /* is_multi_a = */false)) return {};

josibake commented at 10:27 am on April 7, 2023:

0                if (!parse_multi_exp(in, /*is_multi_a=*/false)) return {};

in src/script/miniscript.h:1965 in c0ba8ebbf6 outdated

1638-                if (k < 1 || k > (int64_t)keys.size()) return {};
1639-                script_size += 2 + (keys.size() > 16) + (k > 16) + 34 * keys.size();
1640-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::MULTI, std::move(keys), k));
1641+                if (!parse_multi_exp(in, /* is_multi_a = */false)) return {};
1642+            } else if (Const("multi_a(", in)) {
1643+                if (!parse_multi_exp(in, /* is_multi_a = */true)) return {};

josibake commented at 10:28 am on April 7, 2023:

0                if (!parse_multi_exp(in, /*is_multi_a=*/true)) return {};

in src/script/miniscript.h:984 in efdd154359 outdated

1008+                    for (size_t j = 1; j < sats_size.size(); ++j) {
1009+                        // Which is larger, k-1 satisfaction and satifying this sub, or k satisfaction and dissatisfying
1010+                        // this one?
1011+                        next_sats_size.push_back((sats_size[j] + subs[i]->ss.dsat.size) | (sats_size[j - 1] + subs[i]->ss.sat.size));
1012+                        // Same for size of the stack after satisfying k of the past i fragments.
1013+                        next_sats_diff.push_back((sats_diff[j] + subs[i]->ss.dsat.diff) | (sats_diff[j - 1] + subs[i]->ss.sat.diff) + add_diff);

josibake commented at 10:36 am on April 7, 2023:

“warning: suggest parentheses around arithmetic in operand of ‘|’ [-Wparentheses]”

0                        next_sats_diff.push_back((sats_diff[j] + subs[i]->ss.dsat.diff) | ((sats_diff[j - 1] + subs[i]->ss.sat.diff) + add_diff));

darosior commented at 10:05 am on May 3, 2023:

Thanks, good suggestion that i add those for clarity because your suggestion is incorrect: add_diff should always be added. The current (and intended) semantic is:

 0diff --git a/src/script/miniscript.h b/src/script/miniscript.h
 1index 011c7ac6d6..35797153da 100644
 2--- a/src/script/miniscript.h
 3+++ b/src/script/miniscript.h
 4@@ -1002,7 +1002,7 @@ private:
 5                         // this one?
 6                         next_sats_size.push_back((sats_size[j] + subs[i]->ss.dsat.size) | (sats_size[j - 1] + subs[i]->ss.sat.size));
 7                         // Same for size of the stack after satisfying k of the past i fragments.
 8-                        next_sats_diff.push_back((sats_diff[j] + sub_diff.dsat) | (sats_diff[j - 1] + sub_diff.sat) + add_diff);
 9+                        next_sats_diff.push_back(((sats_diff[j] + sub_diff.dsat) | (sats_diff[j - 1] + sub_diff.sat)) + add_diff);
10                         // Update the maximum stack size for satisfying k subs with the largest of the maximum cost of
11                         // satisfying k-1 subs (implying we satisfy this one), the cost of dissatisfying this sub
12                         // after the satisfaction of j subs beforehand, and the cost of satisfying this sub after the

Did you get this warning with GCC?

in src/script/miniscript.h:2262 in 6e3b37b80c outdated

2100-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(*key))));
2101+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx, Fragment::PK_K, Vector(std::move(*key))));
2102                 break;
2103             }
2104             if (last - in >= 5 && in[0].first == OP_VERIFY && in[1].first == OP_EQUAL && in[3].first == OP_HASH160 && in[4].first == OP_DUP && in[2].second.size() == 20) {
2105                 auto key = ctx.FromPKHBytes(in[2].second.begin(), in[2].second.end());

josibake commented at 10:49 am on April 7, 2023:

“warning: ‘void* __builtin_memcpy(void*, const void*, long unsigned int)’ writing 33 bytes into a region of size 32 overflows the destination [-Wstringop-overflow=]”

getting this warning but it doesn’t make sense to me why, because it should be calling the right function based on ctx? there is a definition for FromPKBytes in src/script/descriptor.cpp and another one in src/script/sign.cpp and the warning is coming from the src/sign.cpp one.

darosior commented at 10:21 am on May 3, 2023:

I’m trying to reproduce the warning. What version of which compiler do you use? And what flags have you enabled?

darosior commented at 6:02 pm on May 16, 2023:

Reproduced and fixed!

josibake commented at 10:54 am on April 7, 2023: member

Left some style nits, nothing important. Might want to run clang-tidy, as it ended up reformatting a lot of the new code. Also got a few warnings, not quite sure about the FromPKBytes warning

Still trying to wrap my head around the logic; I’ll follow up with a (hopefully) more helpful review

in src/script/miniscript.cpp:18 in 1360b541ae outdated

10@@ -11,6 +11,16 @@
11 #include <assert.h>
12 
13 namespace miniscript {
14+
15+bool IsTapscript(MiniscriptContext ms_ctx)
16+{
17+    switch (ms_ctx) {
18+        case MiniscriptContext::P2WSH: return false;

michaelfolkson commented at 8:21 am on April 23, 2023:

Is there a reason why the only two options are P2WSH and P2TR? Should there be a case statement for P2SH (sh) too?

darosior commented at 8:42 am on May 3, 2023:

Because the current codebase only support P2WSH, there is no support for legacy P2SH.

darosior commented at 3:33 pm on April 27, 2023: member

Reviewers, i’ve seen the comments i’m going to address them soon and rebase this.

I have discussed this with @sipa in person today. A couple notes from my recollection:

I introduce the diff (net difference in stack size before and after executing a fragment) and exec (maximum stack size reached during execution) here to account for the maximum stack size at all time. Pieter noticed we may be able to express the size in function of the diff. Or vice versa.
We tried to assert this property in the fuzz test.
We noticed or_i is the only fragment with two possible canonical dissatisfactions. If both dissatisfactions are available (only if both fragments are d) we choose the one with the largest stack size. But it seems unnecessary, the satisfier would always choose the smallest one. But the satisfier chooses in function of the actual witness size (not stack size) so it could be checking the dissatisfaction with the largest stack size.

We’ll see if we can introduce some of this to the existing code and rebase this on top.

in src/test/fuzz/miniscript.cpp:860 in 02a5fa633f outdated

855@@ -811,11 +856,15 @@ NodeRef GenNode(F ConsumeNode, Type root_type, bool strict_valid = false) {
856             // Fragment/children have not been decided yet. Decide them.
857             auto node_info = ConsumeNode(type_needed);
858             if (!node_info) return {};
859+            if ((!miniscript::IsTapscript(SCRIPT_CTX) && node_info->fragment == Fragment::MULTI_A)

darosior commented at 4:32 pm on April 28, 2023:

Note to self: i should relax the ops and script size limits below under Tapscript context.

darosior force-pushed on May 16, 2023

darosior commented at 6:25 pm on May 16, 2023: member

Rebased and updated.

I addressed @josibake’s comments. (thanks for the review!)
I fixed the multi_a satisfaction to use an algorithm similar to multi’s.
Modified the maximum script size to account for some breathing room for the spending transaction size.
Made the execution size accounting easier by not tracking the size of the stack after execution of a fragment, instead assuming the maximum amount of stack elements the fragment can consume were consumed. The number of items pushed is an invariant on the type (1 for B K and W, 0 for V). See the code comments for more details.

DrahtBot removed the label Needs rebase on May 16, 2023

benma referenced this in commit 6052b0856d on May 25, 2023

benma referenced this in commit d214d14a24 on May 25, 2023

benma referenced this in commit 19fa823d94 on May 25, 2023

scgbckbone commented at 5:07 pm on June 19, 2023: none

I have tried to run this branch and have 1Q: What is the reason to populate both PSBT_IN_BIP32_DERIVATION and PSBT_IN_TAP_BIP32_DERIVATION. Imo PSBT_IN_BIP32_DERIVATION should be empty/not included for taproot spends.

darosior force-pushed on Jun 20, 2023

darosior commented at 11:01 am on June 20, 2023: member

Thanks @scgbckbone, good catch.

When populating SignatureData from a PSBT input, i (ab)used the misc_pubkeys member to find pubkey hash preimages also when signing for Tapscript. As a consequence, Tapscript public keys would be serialized back into the PSBT input as PSBT_IN_BIP32_DERIVATION.

This is unnecessary. Instead i pushed a modification that simply adds a new field to SignatureData so we have a separate mapping for Tapscript keys in the signing logic that is not serialized back into the PSBT input.

 0diff --git a/src/psbt.cpp b/src/psbt.cpp
 1index a06f89cb3d..7d50402324 100644
 2--- a/src/psbt.cpp
 3+++ b/src/psbt.cpp
 4@@ -131,7 +131,7 @@ void PSBTInput::FillSignatureData(SignatureData& sigdata) const
 5     }
 6     for (const auto& [pubkey, leaf_origin] : m_tap_bip32_paths) {
 7         sigdata.taproot_misc_pubkeys.emplace(pubkey, leaf_origin);
 8-        sigdata.misc_pubkeys.emplace(Hash160(pubkey), std::make_pair(pubkey.GetCPubKey(), leaf_origin.second));
 9+        sigdata.tap_pubkeys.emplace(Hash160(pubkey), pubkey);
10     }
11     for (const auto& [hash, preimage] : ripemd160_preimages) {
12         sigdata.ripemd160_preimages.emplace(std::vector<unsigned char>(hash.begin(), hash.end()), preimage);
13@@ -246,7 +246,7 @@ void PSBTOutput::FillSignatureData(SignatureData& sigdata) const
14     }
15     for (const auto& [pubkey, leaf_origin] : m_tap_bip32_paths) {
16         sigdata.taproot_misc_pubkeys.emplace(pubkey, leaf_origin);
17-        sigdata.misc_pubkeys.emplace(Hash160(pubkey), std::make_pair(pubkey.GetCPubKey(), leaf_origin.second));
18+        sigdata.tap_pubkeys.emplace(Hash160(pubkey), pubkey);
19     }
20 }
21 
22diff --git a/src/script/sign.cpp b/src/script/sign.cpp
23index 515a296d60..b4af979f85 100644
24--- a/src/script/sign.cpp
25+++ b/src/script/sign.cpp
26@@ -113,12 +113,17 @@ static bool GetPubKey(const SigningProvider& provider, const SignatureData& sigd
27         pubkey = it->second.first;
28         return true;
29     }
30-    // Look for pubkey in pubkey list
31+    // Look for pubkey in pubkey lists
32     const auto& pk_it = sigdata.misc_pubkeys.find(address);
33     if (pk_it != sigdata.misc_pubkeys.end()) {
34         pubkey = pk_it->second.first;
35         return true;
36     }
37+    const auto& tap_pk_it = sigdata.tap_pubkeys.find(address);
38+    if (tap_pk_it != sigdata.tap_pubkeys.end()) {
39+        pubkey = tap_pk_it->second.GetCPubKey();
40+        return true;
41+    }
42     // Query the underlying provider
43     return provider.GetPubKey(address, pubkey);
44 }
45diff --git a/src/script/sign.h b/src/script/sign.h
46index f46bc55992..1cd82a7764 100644
47--- a/src/script/sign.h
48+++ b/src/script/sign.h
49@@ -79,6 +79,7 @@ struct SignatureData {
50     std::vector<unsigned char> taproot_key_path_sig; /// Schnorr signature for key path spending
51     std::map<std::pair<XOnlyPubKey, uint256>, std::vector<unsigned char>> taproot_script_sigs; ///< (Partial) schnorr signatures, indexed by XOnlyPubKey and leaf_hash.
52     std::map<XOnlyPubKey, std::pair<std::set<uint256>, KeyOriginInfo>> taproot_misc_pubkeys; ///< Miscellaneous Taproot pubkeys involved in this input along with their leaf script hashes and key origin data. Also includes the Taproot internal key (may have no leaf script hashes).
53+    std::map<CKeyID, XOnlyPubKey> tap_pubkeys; ///< Misc Taproot pubkeys involved in this input, by hash. (Equivalent of misc_pubkeys but for Taproot.)
54     std::vector<CKeyID> missing_pubkeys; ///< KeyIDs of pubkeys which could not be found
55     std::vector<CKeyID> missing_sigs; ///< KeyIDs of pubkeys for signatures which could not be found
56     uint160 missing_redeem_script; ///< ScriptID of the missing redeemScript (if any)

Also took the opportunity to rebase on master.

DrahtBot added the label Needs rebase on Jul 4, 2023

in src/script/miniscript.h:667 in 6e450bd77f outdated

608@@ -605,6 +609,7 @@ struct Node {
609                 case Fragment::OR_I: return BuildScript(OP_IF, subs[0], OP_ELSE, subs[1], OP_ENDIF);
610                 case Fragment::ANDOR: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[2], OP_ELSE, subs[1], OP_ENDIF);
611                 case Fragment::MULTI: {
612+                    CHECK_NONFATAL(!IsTapscript(ctx.MsContext()));

sipa commented at 10:56 pm on July 8, 2023:

Is it possible to instead (or in addition) add an assertion in ComputeType that multi() is not used in TAPSCRIPT context?

darosior commented at 12:29 pm on September 29, 2023:

Done as a separate commit.

darosior force-pushed on Jul 20, 2023

DrahtBot removed the label Needs rebase on Jul 20, 2023

darosior commented at 3:28 pm on July 20, 2023: member

Rebased (and corrected a comment in the fuzz test witness padding commit).

darosior force-pushed on Jul 21, 2023

darosior commented at 9:48 pm on July 21, 2023: member

Added a missing check in the fuzz target since GetExecStackSize() now returns an optional.

achow101 referenced this in commit cbf385058b on Jul 27, 2023

sidhujag referenced this in commit b11d694c10 on Aug 9, 2023

DrahtBot added the label CI failed on Aug 28, 2023

maflcko commented at 6:55 am on August 29, 2023: member

Needs rebase if still relevant

darosior force-pushed on Aug 30, 2023

DrahtBot removed the label CI failed on Aug 30, 2023

darosior commented at 3:30 pm on August 30, 2023: member

Rebased. Thanks Marco for the ping.

michaelfolkson commented at 9:13 am on August 31, 2023: contributor

Scratched around a bit more on this but will go deeper. Built fine and tests passed on MacOS Ventura.

There are more multisig related tests not touched by this PR that seem to need a Tapscript/multi_a equivalent added (e.g. wallet_multisig_descriptor_psbt.py). The multi_a descriptor leaks into a lot of the multisig code, tests and documentation. It might be best to leave that for other PRs (and possibly other authors) but some sort of issue/plan for what needs to be done post this PR would be nice.
sipa’s site that I personally use as the go-to resource (or spec) on Miniscript has some documentation on Tapscript but the Miniscript analyzer doesn’t take Tapscript Miniscripts (or at least it doesn’t analyze multi_a descriptors). That is a handy tool for reviewers, testers, implementers.

edit: I forgot support for the multi_a descriptor i.e. tr(KEY, multi_a) has already been merged in #24043, this PR is adding support for the multi_a Miniscript fragment,e.g. a Miniscript that contains a multi_a within it e.g. tr(KEY, Miniscript that includes a multi_a) or tr(KEY,{S1, Miniscript that includes a multi_a}) Also, sortedmulti_a is only a descriptor and not a Miniscript fragment and so not included in this PR.

DrahtBot added the label Needs rebase on Sep 6, 2023

darosior force-pushed on Sep 7, 2023

darosior commented at 10:36 am on September 7, 2023: member

Rebased post #26567. This allows to get rid of one commit here that is now part of master :tada:. Also fixed a bug in commit 8288091031b481d59cc2b5894fa790a70654496a (“miniscript: don’t anticipate signature presence in CalcStackSize()”) where i overlooked how the patch applied to more than one case: within the switch statement. @michaelfolkson thanks for having a look here. Regarding the multi_a tests: half of this PR is already tests, exercising the code introduced here under a large number of different scenarii. I’ll leave it to others to try to find blind posts in the pre-existing tests for Tapscript multisigs compared to former multisigs. Regarding Pieter’s website, i plan to PR MiniTapscript support to sipa/miniscript once it’s merged here. So i don’t expect it to be available on the website before then. It should be trivial to achieve the same using the Miniscript unit tests here though.

darosior force-pushed on Sep 7, 2023

DrahtBot added the label CI failed on Sep 7, 2023

DrahtBot removed the label Needs rebase on Sep 7, 2023

DrahtBot removed the label CI failed on Sep 8, 2023

scgbckbone commented at 12:28 pm on September 19, 2023: none

tested ACK + tested with COLDCARD integration tests https://github.com/Coldcard/firmware/blob/edge/testing/test_miniscript.py

bigspider commented at 12:59 pm on September 20, 2023: none

tACK

This is also tested in the integration tests for Ledger’s implementation (open PR: https://github.com/LedgerHQ/app-bitcoin-new/pull/155). Note that there are some syntactic differences as Ledger’s implementation is based on Wallet Policies rather than bare descriptors.

e2e tests signing with both bitcoin-core and the Ledger app are still quite minimal − but no issues found so far: could sign with core for both a purely miniscript taptree, and a mix of miniscript and non-miniscript leaves.

Also implemented unit tests for miniscript sanity checks (tests taken from this PR).

bigspider commented at 1:01 pm on September 20, 2023: none

If anyone is interested in testing things end-2-end with a Ledger device, the “Bitcoin Test” app with taproot-miniscript is available as version 2.2.0-alpha, after enabling “Experimental features” ⟹ “Developer tools” in Ledger Live’s settings.

(As it’s not yet integrated with HWI, testing the app will require using either the python, JS, or Rust client libraries for the Ledger bitcoin app)

in src/script/miniscript.cpp:26 in 434bdbe030 outdated

21@@ -22,6 +22,21 @@ bool IsTapscript(MiniscriptContext ms_ctx)
22 
23 namespace internal {
24 
25+//! 200vbytes for the spending transaction data other than the witness
26+constexpr uint32_t TX_BODY_LEEWAY_WEIGHT{800};

sipa commented at 2:22 pm on September 20, 2023:

I don’t care particularly strongly about what this limit is set to, because practically guaranteeing spendability is hard. However, if the goal is guaranteeing just “can this script be spent with at all”, then I think the overhead should be exactly that of a 1-input 1-output 1-tapscript transaction.

darosior commented at 3:41 pm on September 21, 2023:

Figured it’d be harder to review to have a precise calculation, but happy to change that.

darosior commented at 12:29 pm on September 29, 2023:

Done. (See #27255 (comment) for details.)

in src/pubkey.cpp:207 in d46788c1a3 outdated

203@@ -204,6 +204,13 @@ std::vector<CKeyID> XOnlyPubKey::GetKeyIDs() const
204     return out;
205 }
206 
207+CPubKey XOnlyPubKey::GetCPubKey() const

sipa commented at 2:24 pm on September 20, 2023:

Can we give this a more explicit name like GetEvenCorrespondingCPubKey or so?

in src/test/fuzz/miniscript.cpp:860 in a9b2e8f07e outdated

856@@ -809,11 +857,15 @@ NodeRef GenNode(F ConsumeNode, Type root_type, bool strict_valid = false) {
857             // Fragment/children have not been decided yet. Decide them.
858             auto node_info = ConsumeNode(type_needed);
859             if (!node_info) return {};
860+            if ((!miniscript::IsTapscript(SCRIPT_CTX) && node_info->fragment == Fragment::MULTI_A)

sipa commented at 2:35 pm on September 20, 2023:

Having this check is fine, but it shouldn’t be hit for the smart target (we can intelligently decide there where to construct MULTI vs MULTI_A based on the context under which we’re fuzzing).

darosior commented at 12:51 pm on September 21, 2023:

Had a quick look into this. I could adapt SmartInfo to hold two tables or something similar. But that’d greatly increase the size of the diff for what i feel would not be greatly beneficial? The fuzzer would adapt pretty soon to not generate MULTIs under Tapscript and the other way around?

Happy to do it, just want to ponder it against the review burden.

darosior commented at 12:37 pm on September 29, 2023:

I have removed this check and made the miniscript_smart target always generate a valid recipe.

The SmartInfo struct now holds two tables, one for each context. It’s not ideal since there is a lot of overlap between the two sets of valid recipes, but i don’t think it’s worth optimizing the one-time initialization cost and small additional memory footprint at this stage. Let me know if you disagree.

sipa commented at 2:40 pm on September 20, 2023: member

Concept ACK, just a few comments from cursory code review so far.

darosior force-pushed on Sep 26, 2023

darosior commented at 3:46 pm on September 26, 2023: member

I’ve reworked this a bit to hopefully make it easier to review (and also nicer). Here is a list of the changes i’ve made:

Addressed @sipa’s comments:
- Added a couple assertions in ComputeType for context-specific fragments.
- Made the “minimum viable transaction” size calculation explicit instead of a magic “800 WU” value. This introduced some constant values, which i’ve tried to document extensively.
- The GetCPubKey method introduced to CPubKey was renamed to GetEvenCorrespondingCPubKey to make its name explicit. I’ve removed the now-redundant doc-comment.
- In the fuzz targets, ConsumeNodeSmart now always returns only valid recipes for each context. ConsumeNodeStable was also modified to return early on a fragment invalid for a context. The check to ignore those in the caller GenNode was removed to assert we always return a recipe from ConsumeNodeSmart and that it’s valid (it would make the fuzzer crash otherwise).
Changed the API to only ask for a MiniscriptContext (either Tapscript or P2WSH) instead of a whole (Ctx template) context object wherever we only needed the script context. This makes the API nicer as we often know the script context when calling for instance IsValid() on a node, without necessarily having a parsing/satisfying context at hand. For instance, this helped not overusing globals in the fuzzer. (Not that i’m trying to optimize for the tests, but i think it was an indication that the API could be improved.)
In the fuzz targets, the MiniscriptContext is now directly passed to GenNode, TestNode, etc.. instead of relying on it being set indirectly through the global parsing/satisfying contexts.
All the introduction of Tapscript in the fuzzing targets was moved to the appropriate commit. Previously part of it was in the commit introducing the multi_a fragment, which made the changes to the fuzzer a bit harder to follow.
To make sure the change in the max script size calculation mentioned above didn’t introduce a bug, i’ve added a functional test that sanity checks we can spend a maximum-sized TapMiniscript (last commit).
Found an occurrence we had missed in #27117. Added a commit for this (the first one).
In addition to compiling and passing the unit tests, all commits now pass the miniscript_smart fuzzer (on my own corpus which contains Tapscript seeds).

darosior force-pushed on Sep 26, 2023

DrahtBot added the label CI failed on Sep 26, 2023

DrahtBot removed the label CI failed on Sep 26, 2023

in src/script/miniscript.h:354 in 80606412f0 outdated

348@@ -344,13 +349,32 @@ struct Ops {
349     Ops(uint32_t in_count, MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : count(in_count), sat(in_sat), dsat(in_dsat) {};
350 };
351 
352+struct SatInfo {
353+    //! Maximum witness size to (dis)satisfy;
354+    MaxInt<uint32_t> size;

achow101 commented at 10:07 pm on September 26, 2023:

In 80606412f087eef74dedea008dc84a5efb715a49 “miniscript: check maximum stack size during execution”

Is this size as in bytes or size as in number of items on the stack?

darosior commented at 9:32 am on September 27, 2023:

This is the size of the witness stack (since we want to check the stack size during execution). I’ll update the comment to make it more explicit.

darosior commented at 7:53 am on September 29, 2023:

Added a comment to clarify.

in src/script/miniscript.h:915 in 80606412f0 outdated

897             case Fragment::OLDER:
898-            case Fragment::AFTER: return {0, {}};
899-            case Fragment::PK_K: return {0, 0};
900-            case Fragment::PK_H: return {1, 1};
901+            case Fragment::AFTER: return {{0, 1}, {}};
902+            case Fragment::PK_K: return {{0, 1}, {0, 1}};

achow101 commented at 10:11 pm on September 26, 2023:

In 80606412f087eef74dedea008dc84a5efb715a49 “miniscript: check maximum stack size during execution”

I’m slightly confused by these return values. There will always be something on the stack for both satisfy and dissatisfy, and the fragment itself will push a key, so shouldn’t this be {1, 2}?

darosior commented at 9:37 am on September 27, 2023:

We don’t account for what’s already on the stack. We account for how many elements are added by this fragment (both during and after execution).

The check then consists in adding the maximum number of elements added to the stack and the maximum size of the initial witness stack: https://github.com/bitcoin/bitcoin/commit/80606412f087eef74dedea008dc84a5efb715a49#diff-a55760aaec4bce216663f5ebf65823516347356a8320d30459427149f7bbc2c5R1422-R1424.

Note this is (slightly) conservative, it’s possible the spending path adding the largest number of elements to the stack is not the same as the one requiring the largest initial witness stack.

in src/script/descriptor.cpp:1187 in ffdca88818 outdated

1197     {
1198-        for (const auto& key : keys) provider.pubkeys.emplace(key.GetID(), key);
1199-        return Vector(m_node->ToScript(ScriptMaker(keys, miniscript::MiniscriptContext::P2WSH)));
1200+        for (const auto& key : keys) {
1201+            if (miniscript::IsTapscript(script_ctx)) {
1202+                provider.pubkeys.emplace(Hash160(XOnlyPubKey{key}), key);

achow101 commented at 10:21 pm on September 26, 2023:

In ffdca88818f77fda06c6331df5b4bb408ab1833b “descriptor: parse Miniscript expressions within Taproot descriptors”

I don’t think this is correct. In most places, we don’t lookup xonly pubkeys by their hash. We look them up by getting the hashes of both the even and odd versions of the pubkey. So this would result in pubkeys that cannot be found.

It may be necessary to add this to deal with pkh()s, but I think we also need to add the hashes of the even and odd too.

darosior commented at 9:59 am on September 27, 2023:

Happy to also emplace the hashes of the even and odd serializations, but if i remember correctly it seemed unnecessary to me at the time to hash the public key thrice. What’s a usecase for this?

Also, since an x-only serialization is always available but it’s not the case for an even or odd serialization should we always look up Taproot key by x-only serialization hash instead of having 3 different identifiers?

sipa commented at 1:00 am on October 6, 2023:

@darosior @achow101 Did this get resolved?

darosior commented at 10:37 am on October 6, 2023:

I didn’t get any response to my questions from Andrew but figured he thought my approach was fine since he then ACK’d the PR.

achow101 commented at 11:06 pm on October 6, 2023:

I convinced myself that this is fine. IIRC, these pubkeys are actually never used anywhere relevant (I think the only actual usage is in importing a descriptor to a legacy wallet). In signing, the keys will always be in the SigningProvider anyways since they have to be provided externally to the descriptor. Since there’s no way for a private key of any format to produce an XOnlyPubKey, this case is already being handled elsewhere in signing logic.

in src/script/descriptor.cpp:1552 in ffdca88818 outdated

1555@@ -1546,8 +1556,8 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const
1556         }
1557         ++key_exp_index;
1558         return std::make_unique<PKHDescriptor>(std::move(pubkey));
1559-    } else if (Func("pkh", expr)) {
1560-        error = "Can only have pkh at top level, in sh(), or in wsh()";
1561+    } else if (ctx != ParseScriptContext::P2TR && Func("pkh", expr)) {
1562+        error = "Can only have pkh at top level, in sh(), wsh(), or in tr()";

achow101 commented at 10:26 pm on September 26, 2023:

In ffdca88818f77fda06c6331df5b4bb408ab1833b “descriptor: parse Miniscript expressions within Taproot descriptors”

This doesn’t actually allow pkh() to be parsed by the descriptor parsing code, but I assume that’s because the point is to let the miniscript parser deal with it. In that case, a comment here would be helpful.

darosior commented at 7:53 am on September 29, 2023:

Added a comment to this effect.

darosior force-pushed on Sep 29, 2023

darosior commented at 12:16 pm on September 29, 2023: member

I’ve now made the script context a member of the Node structure. The recent change to directly pass the MiniscriptContext instead of the whole Ctx when appropriate already went halfway down this road. This makes more sense (why should you have to pass the script context to IsValid() if you already passed it when constructing the Node?) and reduces the diff a little bit.

h/t @achow101 for the suggestion.

achow101 commented at 5:47 pm on September 29, 2023: member

ACK f45cb489029abfb0f82ebced167d9b5833960f22

achow101 requested review from sipa on Sep 29, 2023

fanquake added this to the milestone 26.0 on Sep 29, 2023

fanquake requested review from bigspider on Sep 30, 2023

fanquake commented at 10:25 am on September 30, 2023: member

@scgbckbone want to take another look here?

DrahtBot removed review request from bigspider on Sep 30, 2023

darosior requested review from bigspider on Oct 2, 2023

scgbckbone commented at 3:41 pm on October 2, 2023: none

ACK https://github.com/bitcoin/bitcoin/pull/27255/commits/f45cb489029abfb0f82ebced167d9b5833960f22

DrahtBot removed review request from bigspider on Oct 2, 2023

bigspider commented at 7:49 am on October 3, 2023: none

ACK f45cb489029abfb0f82ebced167d9b5833960f22

darosior commented at 8:03 am on October 3, 2023: member

Thanks everyone for your reviews! Just as this is piling up ACKs i’d like to explicit that i believe this needs a review from @sipa before it can be merged.

in src/script/miniscript.h:2097 in 4ce118b1de outdated

2092+                if (last - in < 2 + *num * 2) return {};
2093+                std::vector<Key> keys;
2094+                keys.reserve(*num);
2095+                // Walk through the expected (pubkey, CHECKSIG[ADD]) pairs.
2096+                for (int k = 2;; k += 2) {
2097+                    if (last - in < k + 1) return {};

sipa commented at 5:22 pm on October 4, 2023:

In commit “miniscript: introduce a multi_a fragment”

Shouldn’t this be last - in < k + 2? If last - in = k + 1, then in[k + 1] is the same as *last.

darosior commented at 10:22 am on October 5, 2023:

Yes, and we don’t want to dereference last since it’s past the last element? (It’s the vector end(), maybe it’s confusing to name it “last”.)

sipa commented at 12:41 pm on October 5, 2023:

Yes, and you’re accessing in[k + 1] below, so if last - in = k + 1, then this if (last - in < k + 1) return {}; won’t execute, and you’ll be dereferencing the vector end below.

darosior commented at 1:41 pm on October 5, 2023:

My bad, i had this backward. Fixed and added a couple test cases that would run into this.

in src/script/miniscript.cpp:34 in 475a2a3988 outdated

29+// nValue + script len + OP_0 + pushdata 32.
30+constexpr uint32_t P2WSH_TXOUT_BYTES{8 + 1 + 1 + 33};
31+//! Data other than the witness in a transaction. Overhead + vin count + one vin + vout count + one vout + segwit marker
32+constexpr uint32_t TX_BODY_LEEWAY_WEIGHT{(TX_OVERHEAD + 1 + TXIN_BYTES_NO_WITNESS + 1 + P2WSH_TXOUT_BYTES) * WITNESS_SCALE_FACTOR + 2};
33+//! Maximum possible stack size to spend a Taproot output (excluding the script itself). +2 for witness stack size.
34+constexpr uint32_t MAX_TAPSCRIPT_SAT_SIZE{2 + (1 + MAX_TAPMINISCRIPT_STACK_ELEM_SIZE) * MAX_STACK_SIZE + TAPROOT_CONTROL_MAX_SIZE};

sipa commented at 8:43 pm on October 4, 2023:

In commit “miniscript: adapt resources checks depending on context”

If there are 253 witness stack elements or more, 3 bytes are needed for it (and below, 1 byte suffices). Did you mean to use 3 or 1 instead of 2?

darosior commented at 12:00 pm on October 5, 2023:

Oh, right, i meant 3. I overlooked CompactSize needs 3 bytes for values >= 253. Fixed now, thanks.

in src/script/miniscript.h:1277 in 475a2a3988 outdated

1273@@ -1268,7 +1274,8 @@ struct Node {
1274     uint32_t GetStaticOps() const { return ops.count; }
1275 
1276     //! Check the ops limit of this script against the consensus limit.
1277-    bool CheckOpsLimit() const {
1278+    bool CheckOpsLimit(const MiniscriptContext script_ctx) const {

sipa commented at 8:46 pm on October 4, 2023:

Could this function (and many other below) not use m_script_ctx to decide script context instead of needing to take an argument?

darosior commented at 12:00 pm on October 5, 2023:

I had somehow dropped half the of the changes i advertized in #27255 (comment). Sorry about that, this is now fixed.

in src/pubkey.cpp:207 in 69da583e58 outdated

203@@ -204,6 +204,13 @@ std::vector<CKeyID> XOnlyPubKey::GetKeyIDs() const
204     return out;
205 }
206 
207+CPubKey XOnlyPubKey::GetEvenCorrespondingCPubKey() const

sipa commented at 8:48 pm on October 4, 2023:

In commit: “pubkey: introduce a GetCPubKey helper”

Nit: update commit title to reflect new function name.

darosior commented at 12:00 pm on October 5, 2023:

Done.

sipa commented at 8:51 pm on October 4, 2023: member

Reviewed up to 69da583e58131c0be757c71eb388554772b576a1

darosior force-pushed on Oct 5, 2023

DrahtBot added the label Needs rebase on Oct 5, 2023

DrahtBot commented at 4:52 pm on October 5, 2023: contributor

🐙 This pull request conflicts with the target branch and needs rebase.

in src/script/miniscript.h:980 in 8b6c8ac42c outdated

975+                        std::vector<unsigned char> sig;
976+                        Availability avail = ctx.Sign(node.keys[node.keys.size() - 1 - i], sig);
977+                        // Compute signature stack for just this key.
978+                        auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail);
979+                        // Compute the next sats vector: next_sats[0] is a copy of sats[0] (no signatures). All further
980+                        // next_sats[j] are equal to either the existing sats[j], or sats[j-1] plus a signature for the

sipa commented at 8:34 pm on October 5, 2023:

In commit “miniscript: introduce a multi_a fragment”

I believe this comment needs to be adapted for multi_a: next_sats[j] is either equal to sats[j] plus ZERO, or to sats[j-1] plus a signature for the i’th key.

in src/script/miniscript.h:1202 in 8b6c8ac42c outdated

985+                        next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat));
986+                        // Switch over.
987+                        sats = std::move(next_sats);
988+                    }
989+                    assert(node.k <= sats.size());
990+                    return {std::move(nsat), std::move(sats[node.k])};

sipa commented at 8:35 pm on October 5, 2023:

In commit “miniscript: introduce a multi_a fragment”:

I’m idly wondering why we need nsat (here, and in multi and thresh), can’t we use sats[0] instead?

(no need to address this, I’m just a bit confused by the existing code which IIRC I wrote myself)

darosior commented at 8:54 am on October 6, 2023:

For my code you are right, i don’t need nsat, i can juste reuse sats[0]. I made the change, it’s straightforward and i think cleaner that way.

For multi however we can’t do this since sats[0] doesn’t have ZEROs, since CHECKMULTISIG does not need a ZERO as signatures for keys that are unused in case of satisfaction (it will just try the next public key for the same signature in case of failure). I haven’t looked into thresh, but i suppose we could (i mostly reused thresh’s algorithm for multi_a).

sipa commented at 5:09 pm on October 7, 2023:

You’re right, the same approach doesn’t work for multi, because dissatisfying a multi(k, ...) is not the same as satisfying a multi(0, ...) (they consume different numbers of elements).

in src/script/miniscript.h:2089 in 8b6c8ac42c outdated

2082@@ -2016,6 +2083,35 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
2083                 constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI, std::move(keys), *k));
2084                 break;
2085             }
2086+            // Tapscript's equivalent of multi
2087+            if (last - in >= 4 && in[0].first == OP_NUMEQUAL) {
2088+                if (!IsTapscript(ctx.MsContext())) return {};
2089+                const auto num = ParseScriptNumber(in[1]);

sipa commented at 8:44 pm on October 5, 2023:

In commit “miniscript: introduce a multi_a fragment”

It took me a while to realize that num is actually the threshold here, and not the number of keys (especially with a k variable below, but which is a position and not key count or threshold either). Some comments would help, or alternatively renaming num -> k, and k -> pos or so.

darosior commented at 9:05 am on October 6, 2023:

Did both, let’s try to make this code as clear as possible to future readers (which may well be ourselves).

in src/script/miniscript.cpp:44 in a6314b6172 outdated

39+        // Leaf scripts under Tapscript are not explicitly limited in size. They are only implicitly bounded
40+        // by the maximum standard size of a spending transaction. Let the maximum script size conservatively
41+        // be small enough such as even a maximum sized witness and a reasonably sized spending transaction can
42+        // spend an output paying to this script without running into the maximum standard tx size limit.
43+        // +4 to account for the maximum compactsize encoding for the script push.
44+        return MAX_STANDARD_TX_WEIGHT - TX_BODY_LEEWAY_WEIGHT - MAX_TAPSCRIPT_SAT_SIZE - 4;

sipa commented at 8:52 pm on October 5, 2023:

In commit “miniscript: adapt resources checks depending on context”

The compactsize encoding for the script push can be 5 bytes if it’s more than 65535, I think?

darosior commented at 9:27 am on October 6, 2023:

Errr. Again an off-by-one (like #27255 (review)). I was previously hesitant to pull in more changes but i’ve now made GetSizeOfCompactSize constexpr and used it here to self-document the calculation and make sure the values are correct.

darosior commented at 9:52 am on October 6, 2023:

I also added a missing compactsize for the control block in the MAX_TAPSCRIPT_SAT_SIZE calculation.

in src/test/miniscript_tests.cpp:51 in 388ee976a6 outdated

46@@ -44,8 +47,11 @@ struct TestData {
47 
48     TestData()
49     {
50-        // All our signatures sign (and are required to sign) this constant message.
51-        auto const MESSAGE_HASH = uint256S("f5cd94e18b6fe77dd7aca9e35c2b0c9cbd86356c80a71065");
52+        // All our signatures sign (and are required to sign) this empty message.
53+        auto const MESSAGE_HASH{uint256S("")};

sipa commented at 9:00 pm on October 5, 2023:

In commit “qa: Tapscript-Miniscript unit tests”

Any specific reason to replace this (arbitrary) message hash with 0? Not that it should matter for this test, but my gut feeling says it’s better not to use message hash 0 in ECDSA.

darosior commented at 10:01 am on October 6, 2023:

No, no reason. I confused myself by somehow thinking i changed hash 0 for this arbitrary hash in this PR and quickly removed it in my last push to minimize the diff, it was not the case… Dropped this change now.

EDIT: found the origin of my confusion. In the fuzz test i indeed do this change, i just mixed up the two. I’ll just leave it as is now.

in src/test/fuzz/miniscript.cpp:1139 in 0d9495104b outdated

1133@@ -1029,16 +1134,14 @@ void TestNode(const NodeRef& node, FuzzedDataProvider& provider)
1134     // satisfaction will also match the expected policy.
1135     bool satisfiable = node->IsSatisfiable([](const Node& node) -> bool {
1136         switch (node.fragment) {
1137-        case Fragment::MULTI_A:
1138-            // TODO: Tapscript support.
1139-            assert(false);
1140         case Fragment::PK_K:
1141         case Fragment::PK_H: {
1142             auto it = TEST_DATA.dummy_sigs.find(node.keys[0]);

sipa commented at 9:46 pm on October 5, 2023:

In commit “fuzz: adapt Miniscript targets to Tapscript”

(Here and below) Shouldn’t this use TEST_DATA.schnorr_sigs instead of TEST_DATA.dummy_sigs in tapscript context?

darosior commented at 10:26 am on October 6, 2023:

Good catch. Fixed.

in src/script/miniscript.h:877 in 660da86564 outdated

871@@ -848,52 +872,164 @@ struct Node {
872         assert(false);
873     }
874 
875+    //! Get the net difference in the number of stack items after executing this fragment.
876+    internal::NetDiff CalcNetDiff() const {
877+        // B, K, and W fragments always push (or leave) exactly one element on the stack. V framgents never do.

sipa commented at 9:58 pm on October 5, 2023:

In commit “miniscript: check maximum stack size during execution”

Nit: typo “framgents”

in src/script/miniscript.h:893 in 660da86564 outdated

871@@ -848,52 +872,164 @@ struct Node {
872         assert(false);
873     }
874 
875+    //! Get the net difference in the number of stack items after executing this fragment.
876+    internal::NetDiff CalcNetDiff() const {
877+        // B, K, and W fragments always push (or leave) exactly one element on the stack. V framgents never do.
878+        const auto added_items{((typ & "V"_mst) == "V"_mst) ? 0 : 1};
879+        // Get the maximum stack size necessary to (dis)satisfy this fragment as a negative number, if it exists.
880+        // NOTE: it is fine to use the maximum stack size here, since we add the execution stack size value to the

sipa commented at 0:44 am on October 6, 2023:

In commit “miniscript: check maximum stack size during execution”

I believe an alternative approach is possible with similar complexity as what’s being done in this commit, which does not suffer from the inaccuracy caused by distinct paths which cause maximal initial stack size and maximal execution growth. I just want to get the idea out here, I don’t consider this a requirement for this PR (as you know, I was fine with a much more approximate approach too).

The idea is to reason backwards. We know that every satisfaction of the overall script ends with a single stack item (a 1). From that endpoint, it seems possible to me to reason backwards through all possible execution paths and compute their maximal stack size at every point. Taking the maximum of that should give the desired limit.

To implement this, I think you need almost exactly what this commit is already doing, just reasoning in reverse: e.g. taking the maximum of the execution maximum of the second part and the execution maximum of the first plus the net effect of a second part.

darosior commented at 4:55 pm on October 6, 2023:

For anyone following along, i discussed this with @sipa on ##miniscript on Libera. I think he’s currently trying to implement it.

I was previously contemplating the idea of including it in this PR, but given the tight deadline (if we are aiming to get it into 26 at all, maybe some disagree) i would suggest we do this in a follow-up. This should only relax the limit anyways. (So even if we release this conservative estimate for 26, and change for the accurate calculation for 27, there should be no Miniscript descriptor that could ever be accepted by 26 but refused by 27.)

sipa commented at 7:14 pm on October 6, 2023:

It seems to work, and I think it’s a bit simpler too: https://github.com/sipa/bitcoin/commits/202310_wip_miniscript_stack

Fuzz tests pass, and execution limits are 1 lower in two of the unit tests. I hand-verified one of them, and I believe the computation is correct.

darosior commented at 10:34 am on October 7, 2023:

Reviewed, cherry-picked and squashed your commit into the execution stack size tracking one from this PR. Thanks.

in src/script/miniscript.h:1433 in 14d0c1d270 outdated

1428         if (const auto ops = GetOps()) return *ops <= MAX_OPS_PER_SCRIPT;
1429         return true;
1430     }
1431 
1432     /** Return the maximum number of stack elements needed to satisfy this script non-malleably.
1433      * This does not account for the P2WSH script push. */

sipa commented at 0:55 am on October 6, 2023:

Nit: this comment is slightly outdated now that P2TR is also supported.

darosior commented at 10:32 am on October 6, 2023:

Dropped this part of the comment in a new commit.

darosior force-pushed on Oct 6, 2023

darosior force-pushed on Oct 7, 2023

in src/script/miniscript.h:451 in 59ee9a2a3c outdated

368+    constexpr friend SatInfo operator|(const SatInfo& a, const SatInfo& b) noexcept
369+    {
370+        if (!a.valid) return b;
371+        if (!b.valid) return a;
372+        return {a.netdiff > b.netdiff ? a.netdiff : b.netdiff, a.exec > b.exec ? a.exec : b.exec};
373+    }

darosior commented at 12:36 pm on October 7, 2023:

nit: clearer as

 0diff --git a/src/script/miniscript.h b/src/script/miniscript.h
 1index 1f596376d3..a3618362da 100644
 2--- a/src/script/miniscript.h
 3+++ b/src/script/miniscript.h
 4@@ -361,7 +361,7 @@ struct SatInfo {
 5     constexpr friend SatInfo operator+(const SatInfo& a, const SatInfo& b) noexcept
 6     {
 7         if (!a.valid || !b.valid) return {};
 8-        return {a.netdiff + b.netdiff, b.exec > b.netdiff + a.exec ? b.exec : b.netdiff + a.exec};
 9+        return {a.netdiff + b.netdiff, std::max(b.exec, b.netdiff + a.exec)};
10     }
11 
12     /** Branching. */
13@@ -369,7 +369,7 @@ struct SatInfo {
14     {
15         if (!a.valid) return b;
16         if (!b.valid) return a;
17-        return {a.netdiff > b.netdiff ? a.netdiff : b.netdiff, a.exec > b.exec ? a.exec : b.exec};
18+        return {std::max(a.netdiff, b.netdiff), std::max(a.exec, b.exec)};
19     }
20 };

(I’ll do only if i have to retouch)

sipa commented at 12:42 pm on October 7, 2023:

I didn’t do that because I wasn’t sure if std::max was constexpr, and I missed the note on cppreference that it indeed is since c++14.

So feel free to make that change if you retouch.

darosior commented at 5:38 pm on October 7, 2023:

This was included in the latest push.

in src/script/miniscript.cpp:44 in f3ad6144d2 outdated

39+    if (IsTapscript(ms_ctx)) {
40+        // Leaf scripts under Tapscript are not explicitly limited in size. They are only implicitly bounded
41+        // by the maximum standard size of a spending transaction. Let the maximum script size conservatively
42+        // be small enough such as even a maximum sized witness and a reasonably sized spending transaction can
43+        // spend an output paying to this script without running into the maximum standard tx size limit.
44+        const auto max_size{MAX_STANDARD_TX_WEIGHT - TX_BODY_LEEWAY_WEIGHT - MAX_TAPSCRIPT_SAT_SIZE};

sipa commented at 5:19 pm on October 7, 2023:

In commit “miniscript: adapt resources checks depending on context”

Nit: constexpr ?

in src/script/miniscript.cpp:42 in f3ad6144d2 outdated

37+uint32_t MaxScriptSize(MiniscriptContext ms_ctx)
38+{
39+    if (IsTapscript(ms_ctx)) {
40+        // Leaf scripts under Tapscript are not explicitly limited in size. They are only implicitly bounded
41+        // by the maximum standard size of a spending transaction. Let the maximum script size conservatively
42+        // be small enough such as even a maximum sized witness and a reasonably sized spending transaction can

sipa commented at 5:20 pm on October 7, 2023:

In commit “miniscript: adapt resources checks depending on context”

Nit typo: “such as” -> “such that”

in src/script/miniscript.cpp:37 in f3ad6144d2 outdated

32+//! Data other than the witness in a transaction. Overhead + vin count + one vin + vout count + one vout + segwit marker
33+constexpr uint32_t TX_BODY_LEEWAY_WEIGHT{(TX_OVERHEAD + GetSizeOfCompactSize(TXIN_BYTES_NO_WITNESS) + TXIN_BYTES_NO_WITNESS + GetSizeOfCompactSize(P2WSH_TXOUT_BYTES) + P2WSH_TXOUT_BYTES) * WITNESS_SCALE_FACTOR + 2};
34+//! Maximum possible stack size to spend a Taproot output (excluding the script itself).
35+constexpr uint32_t MAX_TAPSCRIPT_SAT_SIZE{GetSizeOfCompactSize(MAX_STACK_SIZE) + (GetSizeOfCompactSize(MAX_TAPMINISCRIPT_STACK_ELEM_SIZE) + MAX_TAPMINISCRIPT_STACK_ELEM_SIZE) * MAX_STACK_SIZE + GetSizeOfCompactSize(TAPROOT_CONTROL_MAX_SIZE) + TAPROOT_CONTROL_MAX_SIZE};
36+
37+uint32_t MaxScriptSize(MiniscriptContext ms_ctx)

sipa commented at 5:20 pm on October 7, 2023:

In commit “miniscript: adapt resources checks depending on context”

Nit: I think this function can be constexpr too.

darosior commented at 0:17 am on October 8, 2023:

Done and made IsTapscript constexpr too while i was at it.

in src/script/miniscript.cpp:33 in f3ad6144d2 outdated

28+//! prevout + nSequence + scriptSig
29+constexpr uint32_t TXIN_BYTES_NO_WITNESS{36 + 4 + 1};
30+//! nValue + script len + OP_0 + pushdata 32.
31+constexpr uint32_t P2WSH_TXOUT_BYTES{8 + 1 + 1 + 33};
32+//! Data other than the witness in a transaction. Overhead + vin count + one vin + vout count + one vout + segwit marker
33+constexpr uint32_t TX_BODY_LEEWAY_WEIGHT{(TX_OVERHEAD + GetSizeOfCompactSize(TXIN_BYTES_NO_WITNESS) + TXIN_BYTES_NO_WITNESS + GetSizeOfCompactSize(P2WSH_TXOUT_BYTES) + P2WSH_TXOUT_BYTES) * WITNESS_SCALE_FACTOR + 2};

sipa commented at 5:24 pm on October 7, 2023:

In commit “miniscript: adapt resources checks depending on context”

The GetSizeOfCompactSize(TXIN_BYTES_NO_WITNESS) and GetSizeOfCompactSize(P2WSH_TXOUT_BYTES) are confusing here; there is no actual push/bytevector anywhere in the serialization with the non-witness txin bytes as contents. You do need to account for the number of inputs and outputs, but GetSizeOfCompactSize(1) would be more appropriate for those.

darosior commented at 11:35 pm on October 7, 2023:

Err.. Right.

darosior force-pushed on Oct 7, 2023

darosior commented at 5:38 pm on October 7, 2023: member

Pushed a bunch of cleanups and documentation improvements from @sipa to the execution stack size tracking code. Also we now only add 1 in GetExecStackSize / GetStackSize for non-V expressions.

in src/script/miniscript.h:2395 in f3ad6144d2 outdated

2391@@ -2379,7 +2392,7 @@ template<typename Ctx>
2392 inline NodeRef<typename Ctx::Key> FromScript(const CScript& script, const Ctx& ctx) {
2393     using namespace internal;
2394     // A too large Script is necessarily invalid, don't bother parsing it.
2395-    if (script.size() > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
2396+    if (script.size() > internal::MaxScriptSize(ctx.MsContext())) return {};

sipa commented at 6:03 pm on October 7, 2023:

In commit “miniscript: adapt resources checks depending on context”

Nit: internal:: is unnecessary given using namespace internal; above.

in src/test/fuzz/miniscript.cpp:97 in edc3e54770 outdated

91@@ -70,6 +92,19 @@ struct TestData {
92             if (i & 1) hash160_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32);
93         }
94     }
95+
96+    //! Get the (Schnorr or ECDSA, depending on context) signature for this pubkey.
97+    std::pair<std::vector<unsigned char>, bool>* GetSig(const MsCtx script_ctx, const Key& key) {

sipa commented at 6:29 pm on October 7, 2023:

In commit “fuzz: adapt Miniscript targets to Tapscript”

Nit: make function const, and make it return a const pointer to pair?

in src/test/fuzz/miniscript.cpp:1076 in 6baff32e78 outdated

1071@@ -1071,10 +1072,25 @@ void TestNode(const MsCtx script_ctx, const NodeRef& node, FuzzedDataProvider& p
1072         // maximal.
1073         // Do not pad more than what would cause MAX_STANDARD_P2WSH_SCRIPT_SIZE to be reached, however,
1074         // as that also invalidates scripts.
1075-        int add = std::min<int>(
1076-            MAX_OPS_PER_SCRIPT - *node_ops,
1077-            MAX_STANDARD_P2WSH_SCRIPT_SIZE - node->ScriptSize());
1078-        for (int i = 0; i < add; ++i) script.push_back(OP_NOP);
1079+        const auto node_ops{node->GetOps()};
1080+        if (!IsTapscript(script_ctx) && provider.ConsumeBool() && node_ops && *node_ops < MAX_OPS_PER_SCRIPT

sipa commented at 7:06 pm on October 7, 2023:

In commit “fuzz: miniscript: higher sensitivity for max stack size limit under Tapscript”

The way this is structured, with two nested conditionals that each have provider.ConsumeBool() call will break stability of seeds for miniscript_stable, which is a goal I believe.

Instead I’d structure it as:

0if (provider.ConsumeBool()) {
1    if (!IsTapscript(script_ctx) && node_ops && *node_ops < MAX_OPS_PER_SCRIPT && node->ScriptSize() < MAX_STANDARD_P2WSH_SCRIPT_SIZE) {
2        // P2WSH OP_NOP padding
3    }
4    if (IsTapscript(script_ctx) && node_exec_ss && *node_exec_ss < MAX_STACK_SIZE) {
5        // P2TR OP_NIP padding
6    }
7}

(to make it clearer that this retains stability, it’s probably best not to introduce the !IsTapscript(script_ctx) && in the conditional in an earlier commit, but instead pull the const bool pad{provider.ConsumeBool()} out first there.

darosior commented at 0:14 am on October 8, 2023:

Right, good catch! I left the ConsumeBool() in the P2WSH branch.

I think simply removing the leftover call to ConsumeBool() is all is needed to keep seed stability however. I’m not sure about re-structuring it and moving the !IsTapscript() in this commit. For reasoning about seed stability i just think of IsTapscript() as always false, and i find the diff before and after this PR makes it pretty clear we do consume exactly the same bytes as before under P2WSH context:

 0-    const auto node_ops{node->GetOps()};
 1-    if (provider.ConsumeBool() && node_ops && *node_ops < MAX_OPS_PER_SCRIPT && node->ScriptSize() < MAX_STANDARD_P2WSH_SCRIPT_SIZE) {
 2-        // Optionally pad the script with OP_NOPs to max op the ops limit of the constructed script.
 3+    // Optionally pad the script or the witness in order to increase the sensitivity of the tests of
 4+    // the resources limits logic.
 5+    CScriptWitness witness_mal, witness_nonmal;
 6+    if (provider.ConsumeBool()) {
 7+        // Under P2WSH, optionally pad the script with OP_NOPs to max op the ops limit of the constructed script.
 8         // This makes the script obviously not actually miniscript-compatible anymore, but the
 9         // signatures constructed in this test don't commit to the script anyway, so the same
10         // miniscript satisfier will work. This increases the sensitivity of the test to the ops
11@@ -954,31 +1072,54 @@ void TestNode(const NodeRef& node, FuzzedDataProvider& provider)
12         // maximal.
13         // Do not pad more than what would cause MAX_STANDARD_P2WSH_SCRIPT_SIZE to be reached, however,
14         // as that also invalidates scripts.
15-        int add = std::min<int>(
16-            MAX_OPS_PER_SCRIPT - *node_ops,
17-            MAX_STANDARD_P2WSH_SCRIPT_SIZE - node->ScriptSize());
18-        for (int i = 0; i < add; ++i) script.push_back(OP_NOP);
19+        const auto node_ops{node->GetOps()};
20+        if (!IsTapscript(script_ctx) && node_ops && *node_ops < MAX_OPS_PER_SCRIPT
21+            && node->ScriptSize() < MAX_STANDARD_P2WSH_SCRIPT_SIZE) {
22+            int add = std::min<int>(
23+                MAX_OPS_PER_SCRIPT - *node_ops,
24+                MAX_STANDARD_P2WSH_SCRIPT_SIZE - node->ScriptSize());
25+            for (int i = 0; i < add; ++i) script.push_back(OP_NOP);
26+        }
27+
28+        // Under Tapscript, optionally pad the stack up to the limit minus the calculated maximum execution stack
29+        // size to assert a Miniscript would never add more elements to the stack during execution than anticipated.
30+        const auto node_exec_ss{node->GetExecStackSize()};
31+        if (miniscript::IsTapscript(script_ctx) && node_exec_ss && *node_exec_ss < MAX_STACK_SIZE) {
32+            unsigned add{(unsigned)MAX_STACK_SIZE - *node_exec_ss};
33+            witness_mal.stack.resize(add);
34+            witness_nonmal.stack.resize(add);
35+            script.reserve(add);
36+            for (unsigned i = 0; i < add; ++i) script.push_back(OP_NIP);
37+        }
38     }

in src/script/sign.cpp:287 in 5f8d2d5880 outdated

315+    }
316+};
317+
318+/** Miniscript satisfier specific to Tapscript context. */
319+struct TapSatisfier: Satisfier<XOnlyPubKey> {
320+    uint256& m_leaf_hash;

sipa commented at 7:43 pm on October 7, 2023:

In commit “script/sign: Miniscript support in Tapscript”

Does this need to be a mutable reference? If at all possible, I’d make it a const uint256 m_leaf_hash.

darosior commented at 0:16 am on October 8, 2023:

The reference didn’t need to be mutable. Fixed.

darosior force-pushed on Oct 8, 2023

miniscript: add a missing dup key check bypass in Parse()

This was calling the wrong constructor.

a3793f2d1a

miniscript: don't anticipate signature presence in CalcStackSize()

It's true that for any public key there'll be a signature check in a
valid Miniscript. The code would previously, when computing the size of
a satisfaction, account for the signature when it sees a public key
push. Instead, account for it when it is required (ie when encountering
the `c:` wrapper). This has two benefits:
- Allows to accurately compute the net effect of a fragment on the stack
  size. This is necessary to track the size of the stack during the
  execution of a Script.
- It also just makes more sense, making the code more accessible to
  future contributors.

bba9340a94

miniscript: introduce a MsContext() helper to contexts

We are going to introduce Tapscript support in Miniscript, for which
some of Miniscript rules and properties change (new or modified
fragments, different typing rules, different resources consumption, ..).

c3738d0344

miniscript: store the script context within the Node structure

Some checks will be different depending on the script context (for
instance the maximum script size).

91b4db8590

miniscript: restrict multi() usage to P2WSH context

CHECKMULTISIG is disabled for Tapscript. Instead, we'll introduce
a multi_a() fragment with the same semantic as multi().

9164c2eca1

miniscript: introduce a multi_a fragment

It is the equivalent of multi() but for Tapscript, using CHECKSIGADD
instead of CHECKMULTISIG.

It shares the same properties as multi() but for 'n', since a threshold
multi_a() may have an empty vector as the top element of its
satisfaction. It could also have the 'o' property when it only has a
single key, but in this case a 'pk()' is always preferable anyways.

687a0b0fa5

miniscript: make 'd:' have the 'u' property under Tapscript context

In Tapscript MINIMALIF is a consensus rule, so we can rely on the fact
that the `DUP IF [X] ENDIF` will always put an exact 1 on the stack upon
satisfaction.

e5aaa3d77a

miniscript: sanity asserts context in ComputeType 892436c7d5

serialize: make GetSizeOfCompactSize constexpr 9cb4c68b89

miniscript: adapt resources checks depending on context

Under Tapscript, there is:
- No limit on the number of OPs
- No limit on the script size, it's implicitly limited by the maximum
  (standard) transaction size.
- No standardness limit on the number of stack items, it's limited by
  the consensus MAX_STACK_SIZE. This requires tracking the maximum stack
  size at all times during script execution, which will be tackled in
  its own commit.

In order to avoid any Miniscript that would not be spendable by a
standard transaction because of the size of the witness, we limit the
script size under Tapscript to the maximum standard transaction size
minus the maximum possible witness and Taproot control block sizes. Note
this is a conservative limit but it still allows for scripts more than a
hundred times larger than under P2WSH.

f4f978d38e

miniscript: account for keys as being 32 bytes under Taproot context ce8845f5dd

pubkey: introduce a GetEvenCorrespondingCPubKey helper

We'll need to get a compressed key out of an x-only one in other places.
Avoid duplicating the code.

fcb6f13f44

qa: Tapscript-Miniscript unit tests

Adapt the test data and the parsing context to support x-only keys.
Adapt the Test() helper to test existing cases under both Tapscript and
P2WSH context, asserting what needs to be valid or not in each.
Finally, add more cases that exercise the logic that was added in the
previous commits (multi_a, different resource checks and keys
serialization under Tapscript, different properties for 'd:' fragment,
..).

84623722ef

fuzz: adapt Miniscript targets to Tapscript

We introduce another global that dictates the script context under which
to operate when running the target.

For miniscript_script, just consume another byte to set the context.
This should only affect existing seeds to the extent they contain a
CHECKMULTISIG. However it would not invalidate them entirely as they may
contain a NUMEQUAL or a CHECKSIGADD, and this still exercises a bit of
the parser.

For miniscript_string, reduce the string size by one byte and use the
last byte to determine the context. This is the change that i think
would invalidate the lowest number of existing seeds.

For miniscript_stable, we don't want to invalidate any seed. Instead of
creating a new miniscript_stable_tapscript, simply run the target once
for P2WSH and once for Tapscript (with the same seed).

For miniscript_smart, consume one byte before generating a pseudo-random
node to set the context. We have less regard for seed stability for this
target anyways.

574523dbe0

miniscript: check maximum stack size during execution

Under Tapscript, due to the lifting of some standardness and consensus
limits, scripts can now run into the maximum stack size during
execution. Any Miniscript that may hit the limit on any of its spending
paths must be marked as unsafe.

Co-Authored-By: Pieter Wuille <pieter@wuille.net>

770ba5b519

qa: test Miniscript max stack size tracking 6f529cbaaf

fuzz: miniscript: higher sensitivity for max stack size limit under Tapscript

In order to exacerbate a mistake in the stack size tracking logic,
sometimes pad the witness to make the script execute at the brink of the
stack size limit. This way if the stack size is underestimated for a
script it would immediately fail `VerifyScript`.

5e76f3f0dd

descriptor: Tapscript-specific Miniscript key serialization / parsing

64-hex-characters public keys are valid in Miniscript key expressions
within a Tapscript context.

Keys under a Tapscript context always serialize as 32-bytes x-only
public keys (and that's what get hashed by OP_HASH160 on the stack too).

8ff9489422

descriptor: parse Miniscript expressions within Taproot descriptors 8571b89a7f

qa: functional test Miniscript inside Taproot descriptors bd4b11ee06

MOVEONLY: script/sign: move Satisfier declaration above Tapscript signing

We'll need the Miniscript satisfier for Tapscript too.

febe2abc0e

script/sign: Miniscript support in Tapscript

We make the Satisfier a base in which to store the common methods
between the Tapscript and P2WSH satisfier, and from which they both
inherit.

A field is added to SignatureData to be able to satisfy pkh() under
Tapscript context (to get the pubkey hash preimage) without wallet data.
For instance in `finalizepsbt` RPC. See also the next commits for a
functional test that exercises this.

4f473ea515

qa: list descriptors in Miniscript signing functional tests

This makes it more generalistic than just having the miniscripts since
we are going to have Taproot descriptors with (multiple) miniscripts in
them too.

5dc341dfe6

qa: Tapscript Miniscript signing functional tests b917c715ac

miniscript: have a custom Node destructor

To avoid recursive calls in shared_ptr's destructor that could lead to a
stack overflow.

117927bd5f

qa: bound testing for TapMiniscript

Make sure we can spend a maximum-sized Miniscript under Tapscript
context.

128bc104ef

miniscript: remove P2WSH-specific part of GetStackSize doc comment ec0fc14a22

darosior force-pushed on Oct 8, 2023

DrahtBot added the label CI failed on Oct 8, 2023

DrahtBot removed the label CI failed on Oct 8, 2023

sipa commented at 2:00 pm on October 8, 2023: member

ACK ec0fc14a22f38b487929ec21145945966f301eb5

I have reviewed the code carefully, and contributed a new stack size limit checking implementation, while testing with fuzzing and the other included tests. I have not tested the feature manually. Also note that some of the code is mine, so my review does not cover that.

Unsure what @DrahtBot is smoking when claiming this needs rebase. It looks perfectly based to me.

DrahtBot requested review from michaelfolkson on Oct 8, 2023

DrahtBot requested review from achow101 on Oct 8, 2023

DrahtBot requested review from scgbckbone on Oct 8, 2023

DrahtBot requested review from bigspider on Oct 8, 2023

DrahtBot requested review from josibake on Oct 8, 2023

achow101 commented at 4:01 pm on October 8, 2023: member

ACK ec0fc14a22f38b487929ec21145945966f301eb5

DrahtBot removed review request from michaelfolkson on Oct 8, 2023

DrahtBot removed review request from achow101 on Oct 8, 2023

DrahtBot removed review request from scgbckbone on Oct 8, 2023

DrahtBot removed review request from bigspider on Oct 8, 2023

DrahtBot requested review from scgbckbone on Oct 8, 2023

DrahtBot requested review from michaelfolkson on Oct 8, 2023

DrahtBot requested review from bigspider on Oct 8, 2023

achow101 merged this on Oct 8, 2023

achow101 closed this on Oct 8, 2023

darosior deleted the branch on Oct 8, 2023

maflcko removed the label Needs rebase on Oct 8, 2023

Frank-GER referenced this in commit c28256cd90 on Oct 13, 2023

murchandamus commented at 6:02 pm on October 26, 2023: contributor

I looked over the release notes draft for 26.0 today. I think this was not mentioned. Should this have release notes?

sipa commented at 6:07 pm on October 26, 2023: member

@murchandamus Yes!

MiniTapscript: port Miniscript to Tapscript #27255

Code Coverage

Reviews

Conflicts