Miniscript integration

darosior commented at 10:27 am on January 25, 2022: member

Miniscript is a language for writing (a subset of) Bitcoin Scripts in a structured way.

Miniscript permits:

To safely extend the Output Descriptor language to many more scripting features thanks to the typing system (composition).
Static analysis of spending conditions, maximum spending cost of each branch, security properties, third-party malleability.
General satisfaction of any correctly typed (“valid” [0]) Miniscript. The satisfaction itself is also analyzable.
To extend the possibilities of external signers, because of all of the above and since it carries enough metadata.

Miniscript guarantees:

That for any statically-analyzed as “safe” [0] Script, a witness can be constructed in the bounds of the consensus and standardness rules (standardness complete).
That unless the conditions of the Miniscript are met, no witness can be created for the Script (consensus sound).
Third-party malleability protection for the satisfaction of a sane Miniscript, which is too complex to summarize here.

For more details around Miniscript (including the specifications), please refer to the website.

Miniscript was designed by Pieter Wuille, Andrew Poelstra and Sanket Kanjalkar. This PR is an updated and rebased version of #16800. See the commit history of the Miniscript repository for details about the changes made since September 2019 (TL;DR: bugfixes, introduction of timelock conflicts in the type system, pk() and pkh() aliases, thresh_m renamed to multi, all recursive algorithms were made non-recursive).

This PR is also the first in a series of 3:

The first one (here) integrates the backbone of Miniscript.
The second one (#24148) introduces support for Miniscript in Output Descriptors, allowing for watch-only support of Miniscript Descriptors in the wallet.
The third one (#24149) implements signing for these Miniscript Descriptors, using Miniscript’s satisfaction algorithm.

Note to reviewers:

Miniscript is currently defined only for P2WSH. No Taproot yet.
Miniscript is different from the policy language (a high-level logical representation of a spending policy). A policy->Miniscript compiler is not included here.
The fuzz target included here is more interestingly extended in the 3rd PR to check a script’s satisfaction against VerifyScript. I think it could be further improved by having custom mutators as we now have for multisig (see #23105). A minified corpus of Miniscript Scripts is available at https://github.com/bitcoin-core/qa-assets/pull/85.

[0] We call “valid” any correctly-typed Miniscript. And “safe” any sane Miniscript, ie one whose satisfaction isn’t malleable, which requires a key for any spending path, etc..

darosior force-pushed on Jan 25, 2022

DrahtBot added the label Build system on Jan 25, 2022

DrahtBot added the label Consensus on Jan 25, 2022

in src/script/miniscript.h:504 in 74d3f9b58e outdated

499+        };
500+        // The upward function computes for a node, given whether its parent is a wrapper,
501+        // and the string representations of its child nodes, the string representation of the node.
502+        auto upfn = [&ctx](bool wrapped, const Node& node, Span<std::string> subs) -> std::optional<std::string> {
503+            std::string ret = wrapped ? ":" : "";
504+            std::stringstream k_sstr;

MarcoFalke commented at 12:28 pm on January 25, 2022:

Would it compile if you remove this and use ::ToString(node.k) instead?

darosior commented at 1:03 pm on January 25, 2022:

:man_facepalming: Yes. Done.

darosior commented at 1:03 pm on January 25, 2022: member

Arg, the unit test (miniscript_tests) gets OOM killed in the CI when ASAN is enabled. EDIT: reproduced locally (the RAM usage is crazy, went up to 13G before i killed it although the test without ASAN uses only a few hundreds MB). Decreasing the number of iterations for the random tests to 100 for now (caps the mem usage to 2G on my machine under ASAN). I’ll look into making GenNode generate valid nodes more often, which i think is the main culprit here…

Note: this was later fixed by having a miniscript_random fuzz target (in #24149) instead of trying to generate random nodes in the unit tests.

Aside: this shouldn’t be labeled as “Consensus” (neither should #24148 be) :)

darosior force-pushed on Jan 25, 2022

Sjors commented at 3:09 pm on January 25, 2022: member

Concept ACK. I wonder if it makes sense to start out with a small subset of miniscript, so reviewers can focus on the implementation rather than on completeness.

darosior force-pushed on Jan 25, 2022

in src/script/miniscript.h:150 in 3a2c00d9bc outdated

145+    constexpr Type If(bool x) const { return Type(x ? m_flags : 0); }
146+};
147+
148+//! Literal operator to construct Type objects.
149+inline constexpr Type operator"" _mst(const char* c, size_t l) {
150+    return l == 0 ? Type(0) : operator"" _mst(c + 1, l - 1) | Type(

sipa commented at 8:54 pm on January 25, 2022:

This is my code, but it was written when the codebase was still C++11. In C++17 this can be written more idiomatically without recursion. Can be done afterwards, but it may help review.

in src/script/miniscript.h:320 in 3a2c00d9bc outdated

315+        while (stack.size()) {
316+            const Node& node = stack.back().node;
317+            if (stack.back().expanded < node.subs.size()) {
318+                /* We encounter a tree node with at least one unexpanded child.
319+                 * Expand it. By the time we hit this node again, the result of
320+                 * that child (and all earlier children) will be on the stack. */

sipa commented at 8:56 pm on January 25, 2022:

Self-nit: this should be “will be at the end of result”, not on the stack.

in src/script/miniscript.h:361 in 3a2c00d9bc outdated

356+
357+    //! Compute the type for this miniscript.
358+    Type CalcType() const {
359+        using namespace internal;
360+
361+        // THRESH has a variable number of subexpression

sipa commented at 8:57 pm on January 25, 2022:

Self-nit: subexpressions.

meshcollider commented at 9:00 pm on January 25, 2022: contributor

Strong concept ACK

in src/test/miniscript_tests.cpp:382 in 3a2c00d9bc outdated

377+
378+
379+    g_testdata.reset();
380+}
381+
382+BOOST_AUTO_TEST_CASE(random_tests)

sipa commented at 9:01 pm on January 25, 2022:

This test, along with all the RandomNode logic, is probably much more useful if converted to a fuzz test (which doesn’t need to construct a realistic/useful probability model, but can just choose based on inputs). Let me know if you want any help with that.

in src/script/miniscript.h:750 in 9d4cddd829 outdated

550@@ -549,10 +551,10 @@ struct Node {
551     Type GetType() const { return typ; }
552 
553     //! Check whether this node is valid at all.
554-    bool IsValid() const { return !(GetType() == ""_mst); }
555+    bool IsValid() const { return !(GetType() == ""_mst) && ScriptSize() <= MAX_STANDARD_P2WSH_SCRIPT_SIZE; }

sipa commented at 9:02 pm on January 25, 2022:

In commit “Miniscript: conversion from script”

I think this change (as well as the one to IsValidTopLevel below) is in the wrong commit.

DrahtBot commented at 0:26 am on January 26, 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:

#13062 (Make script interpreter independent from storage type CScript by sipa)

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.

laanwj added the label Descriptors on Jan 27, 2022

laanwj removed the label Consensus on Jan 27, 2022

laanwj added the label Utils/log/libs on Jan 27, 2022

in src/script/script.h:439 in e4711c23cb outdated

434+        reserve(size() + b.size());
435+        insert(end(), b.begin(), b.end());
436+        return *this;
437+    }
438+
439+    friend CScript operator+(const CScript& a, const CScript& b)

MarcoFalke commented at 5:43 pm on January 27, 2022:

I don’t really like this revert. Does this also enable CScript{} + CScriptBase{}? If yes, that sounds bad, because you likely don’t want to append data without pushing it.

Even if it doesn’t, is there any downside in having a named function for this? The existing Cat might even work for this?

darosior commented at 4:33 pm on January 30, 2022:

Indeed, just using Cat does work.

 0diff --git a/src/script/miniscript.h b/src/script/miniscript.h
 1index c67a3c4ea0..88fa4730cd 100644
 2--- a/src/script/miniscript.h
 3+++ b/src/script/miniscript.h
 4@@ -446,7 +446,7 @@ public:
 5                 case NodeType::RIPEMD160: return CScript() << OP_SIZE << 32 << OP_EQUALVERIFY << OP_RIPEMD160 << node.data << (verify ? OP_EQUALVERIFY : OP_EQUAL);
 6                 case NodeType::HASH256: return CScript() << OP_SIZE << 32 << OP_EQUALVERIFY << OP_HASH256 << node.data << (verify ? OP_EQUALVERIFY : OP_EQUAL);
 7                 case NodeType::HASH160: return CScript() << OP_SIZE << 32 << OP_EQUALVERIFY << OP_HASH160 << node.data << (verify ? OP_EQUALVERIFY : OP_EQUAL);
 8-                case NodeType::WRAP_A: return (CScript() << OP_TOALTSTACK) + std::move(subs[0]) + (CScript() << OP_FROMALTSTACK);
 9+                case NodeType::WRAP_A: return Cat(Cat((CScript() << OP_TOALTSTACK), std::move(subs[0])), (CScript() << OP_FROMALTSTACK));
10                 case NodeType::WRAP_S: return (CScript() << OP_SWAP) + std::move(subs[0]);
11                 case NodeType::WRAP_C: return std::move(subs[0]) + CScript() << (verify ? OP_CHECKSIGVERIFY : OP_CHECKSIG);
12                 case NodeType::WRAP_D: return (CScript() << OP_DUP << OP_IF) + std::move(subs[0]) + (CScript() << OP_ENDIF);

I’ll look into adding a Cat() which takes variadic arguments, instead of nesting them and creating more vectors than needed.

Update: current plan is to have a BuildScript() instead.

MarcoFalke removed the label Build system on Jan 27, 2022

MarcoFalke removed the label Utils/log/libs on Jan 27, 2022

jb55 commented at 9:03 pm on January 27, 2022: contributor

nice. Concept ACK.

dunxen commented at 8:18 am on January 29, 2022: contributor

Concept ACK

darosior commented at 9:37 am on January 29, 2022: member

Concept ACK. I wonder if it makes sense to start out with a small subset of miniscript, so reviewers can focus on the implementation rather than on completeness.

I have tried to split this work into as many PR as reasonable, to reduce the size of this first chunk as much as possible. Note that 21% (you can’t make this up) of the diff here is tests, and even more so in the following PRs. I’m afraid that further splitting this doesn’t make sense. For smaller chunks to review, commits here should be focused, atomic and independently reviewable.

Further, i’m currently simplifying a few things following Pieter’s comments above. I’m happy to help review as much as i can, and if not for the first reviewers, comments like “it took time for me to grasp this was doing X, [adding a comment here / rewriting it this way] would be helpful to following reviewers” are very welcome!

Sjors commented at 3:33 pm on January 29, 2022: member

It’s mostly 3a2c00d9bc3c7a34fb8727d76e9c3a691395b67c that introduces a rather large body of stuff. Conceptually c:pk_k(key) is the easiest thing to understand, the equivalent of a pk() descriptor. So one commit could introduce NodeType with just PK_K and WRAP_C, Type with just B and K implemented. That should make that commit about 90% smaller, while still introducing the main moving parts of a parser, constraint checking, etc.

This doesn’t necessarily require more PR’s, though it might: only a limited subset of the descriptor language is necessary to get the functionality currently in descriptors. So then you could go straight to #24148 and #24149, to finish the job of blending miniscript with descriptors, while using parallel PR’s to expand the miniscript language.

in src/script/miniscript.h:366 in 3a2c00d9bc outdated

361+        // THRESH has a variable number of subexpression
362+        std::vector<Type> sub_types;
363+        if (nodetype == NodeType::THRESH) {
364+            for (const auto& sub : subs) sub_types.push_back(sub->GetType());
365+        }
366+        // All other nodes than THRESH can be computed just from the types of the 0-3 subexpexpressions.

achow101 commented at 9:28 pm on January 31, 2022:

In 3a2c00d9bc3c7a34fb8727d76e9c3a691395b67c “Miniscript: type system, script creation, text notation, tests”

nit: spelling subexpressions

in src/script/miniscript.h:417 in 3a2c00d9bc outdated

412+                case NodeType::AND_B: return std::move(subs[0]) + std::move(subs[1]) + (CScript() << OP_BOOLAND);
413+                case NodeType::OR_B: return std::move(subs[0]) + std::move(subs[1]) + (CScript() << OP_BOOLOR);
414+                case NodeType::OR_D: return std::move(subs[0]) + (CScript() << OP_IFDUP << OP_NOTIF) + std::move(subs[1]) + (CScript() << OP_ENDIF);
415+                case NodeType::OR_C: return std::move(subs[0]) + (CScript() << OP_NOTIF) + std::move(subs[1]) + (CScript() << OP_ENDIF);
416+                case NodeType::OR_I: return (CScript() << OP_IF) + std::move(subs[0]) + (CScript() << OP_ELSE) + std::move(subs[1]) + (CScript() << OP_ENDIF);
417+                case NodeType::ANDOR: return std::move(subs[0]) + (CScript() << OP_NOTIF) + std::move(subs[2]) + (CScript() << OP_ELSE) + std::move(subs[1]) + (CScript() << OP_ENDIF);

achow101 commented at 9:41 pm on January 31, 2022:

In 3a2c00d9bc3c7a34fb8727d76e9c3a691395b67c “Miniscript: type system, script creation, text notation, tests”

I think the pattern (CScript() << OP_BLAH) can be simplified to CScript(OP_BLAH).

darosior commented at 8:24 am on February 1, 2022:

Yes, but it is going to go along with #24147 (review) in favour of a BuildScript(OP, sub, sub, OP, OP, sub, ...).

in src/script/miniscript.h:549 in 3a2c00d9bc outdated

484+                    if (node.subs[0]->nodetype == NodeType::JUST_0) return "l" + std::move(subs[1]);
485+                    if (node.subs[1]->nodetype == NodeType::JUST_0) return "u" + std::move(subs[0]);
486+                    break;
487+                default: break;
488+            }
489+            switch (node.nodetype) {

achow101 commented at 9:55 pm on January 31, 2022:

In 3a2c00d9bc3c7a34fb8727d76e9c3a691395b67c “Miniscript: type system, script creation, text notation, tests”

I don’t understand why a new switch-case block starts here. Couldn’t this just be part of the previous one?

darosior commented at 8:36 am on February 1, 2022:

Note the duplicated case between the two switches. Some nodes’ text representation can be abbreviated using a wrapper, and you want to try that first. Besides that, i guess it’s a matter of style between trying all wrappers first and merging them between the respective node types that are currently duplicated.

in src/script/miniscript.h:182 in 3a2c00d9bc outdated

177+//! Construct a miniscript node as a shared_ptr.
178+template<typename Key, typename... Args>
179+NodeRef<Key> MakeNodeRef(Args&&... args) { return std::make_shared<const Node<Key>>(std::forward<Args>(args)...); }
180+
181+//! The different node types in miniscript.
182+enum class NodeType {

achow101 commented at 9:57 pm on January 31, 2022:

In 3a2c00d9bc3c7a34fb8727d76e9c3a691395b67c “Miniscript: type system, script creation, text notation, tests”

It would be nice if NodeType and Type were named with more distinct names so that it is less confusing about what “type” is being referred to.

darosior commented at 3:37 pm on February 5, 2022:

I’m renaming NodeType to Fragment.

in src/script/miniscript.h:957 in 3a2c00d9bc outdated

731+                Key key;
732+                int key_size = FindNextChar(in, ')');
733+                if (key_size < 1) return {};
734+                if (!ctx.FromString(in.begin(), in.begin() + key_size, key)) return {};
735+                constructed.push_back(MakeNodeRef<Key>(NodeType::WRAP_C, Vector(MakeNodeRef<Key>(NodeType::PK_K, Vector(std::move(key))))));
736+                in = in.subspan(key_size + 1);

achow101 commented at 10:07 pm on January 31, 2022:

In 3a2c00d9bc3c7a34fb8727d76e9c3a691395b67c “Miniscript: type system, script creation, text notation, tests”

Can the key parsing stuff be refactored into its own function instead of copy and pasted for the next 3 expressions?

in src/script/miniscript.h:981 in 3a2c00d9bc outdated

761+                std::string val = std::string(in.begin(), in.begin() + hash_size);
762+                if (!IsHex(val)) return {};
763+                auto hash = ParseHex(val);
764+                if (hash.size() != 32) return {};
765+                constructed.push_back(MakeNodeRef<Key>(NodeType::SHA256, std::move(hash)));
766+                in = in.subspan(hash_size + 1);

achow101 commented at 10:08 pm on January 31, 2022:

In 3a2c00d9bc3c7a34fb8727d76e9c3a691395b67c “Miniscript: type system, script creation, text notation, tests”

Can the hex data parsing stuff be refactored into a function instead of copy and pasted for the next 3 expressions?

in src/script/miniscript.cpp:278 in 3a2c00d9bc outdated

273+        case NodeType::OR_D: return subsize + 3;
274+        case NodeType::OR_C: return subsize + 2;
275+        case NodeType::OR_I: return subsize + 3;
276+        case NodeType::ANDOR: return subsize + 3;
277+        case NodeType::THRESH: return subsize + n_subs + 1;
278+        case NodeType::MULTI: return subsize + 3 + (n_keys > 16) + (k > 16) + 34 * n_keys;

achow101 commented at 10:46 pm on January 31, 2022:

In 3a2c00d9bc3c7a34fb8727d76e9c3a691395b67c “Miniscript: type system, script creation, text notation, tests”

Several of these sizes are the same, so this could be deduplicated to be a bit easier to read.

darosior commented at 3:54 pm on February 5, 2022:

Also removing the subsize where it was not necessary (it must always be 0 for “leaf” fragments). I think it’s much less confusing now.

in src/test/miniscript_tests.cpp:72 in 3a2c00d9bc outdated

65+//! Global TestData object
66+std::unique_ptr<const TestData> g_testdata;
67+
68+/** A class encapsulating conversion routing for CPubKey. */
69+struct KeyConverter {
70+    typedef CPubKey Key;

achow101 commented at 10:49 pm on January 31, 2022:

In 3a2c00d9bc3c7a34fb8727d76e9c3a691395b67c “Miniscript: type system, script creation, text notation, tests”

This appears to be unused.

darosior commented at 8:38 am on February 1, 2022:

It is? See the CONVERTER global.

EDIT: ok i missed you were talking about the Key type. The Miniscript context expects it to be defined.

achow101 commented at 4:00 pm on February 1, 2022:

Oh, I grepped for Key and did not see it, but removing this does indeed cause a compilation failure.

in src/script/miniscript.h:138 in 3a2c00d9bc outdated

131+
132+    //! Compute the type with the intersection of properties.
133+    constexpr Type operator&(Type x) const { return Type(m_flags & x.m_flags); }
134+
135+    //! Check whether the left hand's properties are superset of the right's (= left is a subtype of right).
136+    constexpr bool operator<<(Type x) const { return (x.m_flags & ~m_flags) == 0; }

achow101 commented at 10:59 pm on January 31, 2022:

In 3a2c00d9bc3c7a34fb8727d76e9c3a691395b67c “Miniscript: type system, script creation, text notation, tests”

<< confused me for a while as I am used to it meaning bit shift when used in a flags like context, rather than a containment operator.

in src/script/miniscript.h:110 in 2b9f9f9121 outdated

105+ * This helps users detect if miniscript does not match the semantic behaviour the
106+ * user expects.
107+ * - "g" Whether the branch contains a relative time timelock
108+ * - "h" Whether the branch contains a relative height timelock
109+ * - "i" Whether the branch contains a absolute time timelock
110+ * - "j" Whether the branch contains a absolute time heightlock

willcl-ark commented at 8:06 am on February 1, 2022:

If you touch this perhaps worth changing to * - "j" Whether the branch contains a absolute height timelock

flack commented at 12:58 pm on February 1, 2022:

mini-nit: It should be “an absolute […]” in both lines

in src/script/miniscript.h:47 in 3a2c00d9bc outdated

40+ *   - Takes its inputs from the top of the stack.
41+ *   - When satisfactied, pushes nothing.
42+ *   - Cannot be dissatisfied.
43+ *   - This is obtained by adding an OP_VERIFY to a B, modifying the last opcode
44+ *     of a B to its -VERIFY version (only for OP_CHECKSIG, OP_CHECKSIGVERIFY
45+ *     and OP_EQUAL), or using IFs where both branches are also Vs.

sanket1729 commented at 9:53 pm on February 2, 2022:

In 3a2c00d9bc3c7a34fb8727d76e9c3a691395b67c: These are not exhaustive ways to compute a V type. This can be computed by or_c, and_v too.

nit: Perhaps replace

0+ This is obtained
1- This can be obtained

sanket1729 commented at 10:02 pm on February 2, 2022:

Perhaps this was written before the miniscript spec was updated. The comments here can be updated to reflect the website that has an updated explanation.

darosior commented at 5:17 pm on March 14, 2022:

I’ve updated the comment to be more general but not exhaustive:

 0diff --git a/src/script/miniscript.h b/src/script/miniscript.h
 1index 88270e54d7..070dcc9d14 100644
 2--- a/src/script/miniscript.h
 3+++ b/src/script/miniscript.h
 4@@ -42,9 +42,9 @@ namespace miniscript {
 5  *   - Takes its inputs from the top of the stack.
 6  *   - When satisfactied, pushes nothing.
 7  *   - Cannot be dissatisfied.
 8- *   - This is obtained by adding an OP_VERIFY to a B, modifying the last opcode
 9+ *   - This can be obtained by adding an OP_VERIFY to a B, modifying the last opcode
10  *     of a B to its -VERIFY version (only for OP_CHECKSIG, OP_CHECKSIGVERIFY
11- *     and OP_EQUAL), or using IFs where both branches are also Vs.
12+ *     and OP_EQUAL), or by combining a V fragment under some conditions.
13  *   - For example vc:pk_k(key) = <key> OP_CHECKSIGVERIFY
14  * - "K" Key:
15  *   - Takes its inputs from the top of the stack.

Resolving for now, feel free to continue if you think i should do more and i’ll unresolve.

in src/script/miniscript.h:92 in 3a2c00d9bc outdated

85+ * - "f" Forced:
86+ *   - Dissatisfactions (if any) for this expression always involve at least one signature.
87+ *   - Is always true for type 'V'.
88+ * - "s" Safe:
89+ *   - Satisfactions for this expression always involve at least one signature.
90+ * - "m" Nonmalleable:

sanket1729 commented at 10:33 pm on February 2, 2022:

Note to reviewers: that the website no longer explicitly lists m as a type property. It is implicitly captured in the “Guaranteeing non-malleability” table.

in src/script/miniscript.cpp:82 in 3a2c00d9bc outdated

76+    }
77+
78+    // Below is the per-nodetype logic for computing the expression types.
79+    // It heavily relies on Type's << operator (where "X << a_mst" means
80+    // "X has all properties listed in a").
81+    switch (nodetype) {

sanket1729 commented at 10:45 pm on February 2, 2022:

nit (Feel free to ignore, this may be some work for no benefit): Here and all other places, I think it might be useful to have the same ordering of fragments here as listed on the website for ease for review.

darosior commented at 5:33 pm on March 14, 2022:

+1 for consistency :). But was there a rationale for the website’s order? I find it not very intuitive, and i’d rather “fix” it there first before modifying switches here. For instance what about:

All leaf fragments (from 0 to multi)
2-args “combiner” fragments
3-args “combiner” fragments
n-args “combiner” fragments (thresh)
wrappers

Also, note that most other places where we switch on the fragment type have grouped cases and groups aren’t necessarily in the same order as the website (or mine from above). So ordering in switch cases would be more of a “best effort” in most places.

Sjors commented at 6:28 pm on February 3, 2022: member

Rather than somehow rebuilding from scratch, I tried the opposite approach…

I peeled back the fragments in 3a2c00d9bc3c7a34fb8727d76e9c3a691395b67c like an onion, deleting a bunch of related fragments and committing that. The order is somewhat random, but I started with the ones that are not needed for descriptors. I then reverted all these commits, and squashed the original ones. The end result is a series of commits that builds all of Miniscript piecemeal: https://github.com/Sjors/bitcoin/commits/2022/02/miniscript

If you want to use it, you should be able to rebase the rest of this PR on top of it.

The types and properties are now introduced in the commit for the first fragment that needs them. Because I peeled back in somewhat random order, this may not be the most optimal way to introduce them. But at least they’re not all introduced at once. That said, the bulk of properties is still introduced in the first commit, because c:pk_h() uses the kitchensink.

Only commits df93206ff5cea371594da2d7f140325c1573f8ef, 547a8d6e7de1cf1afb472564d68da2683e9aa8e7 and e1984c4a5d433531e5d66df832514b642af43997 are needed for our current descriptor capability.

The other commits implement the rest of miniscript could be moved to another PR. They can be reviewed in parallel with your followup PR’s that integrate miniscript with descriptors.

I put older() and after() immediately after that in 6f87083fd6b01f3f7a5228a05702c0177dfe1c75, since time/height locks are probably the most useful wallet feature to introduce next (and the wallet RPC already has some timelock related functionality). That said, it’s probably fine to introduce all the new miniscript functionality in one go.

While peeling back fragments I was pretty reckless with the tests: I just deleted any test that contained the fragment. This leads to low coverage for the initial commits, which can probably be improved with some new tests.

Update 2022-02-06: I simplified the first commit even further by delaying the introduction of all properties. None of them are needed until after/older and the and/or fragments. The makes the first commit far easier to understand imo.

darosior force-pushed on Feb 6, 2022

in src/script/miniscript.h:1156 in f09f339d48 outdated

1151+                constructed.push_back(MakeNodeRef<Key>(Fragment::RIPEMD160, in[1].second));
1152+                in += 7;
1153+            } else if (last - in >= 7 && in[0].first == OP_EQUAL && in[1].second.size() == 32 && in[2].first == OP_HASH256 && in[3].first == OP_VERIFY && in[4].first == OP_EQUAL && ParseScriptNumber(in[5], k) && k == 32 && in[6].first == OP_SIZE) {
1154+                constructed.push_back(MakeNodeRef<Key>(Fragment::HASH256, in[1].second));
1155+                in += 7;
1156+            } else if (last - in >= 7 && in[0].first == OP_EQUAL && in[1].second.size() == 20 && in[2].first == OP_HASH160 && in[3].first == OP_VERIFY && in[4].first == OP_EQUAL && ParseScriptNumber(in[5], k) && k == 32 && in[6].first == OP_SIZE) {

achow101 commented at 8:34 pm on February 7, 2022:

In f09f339d483824a40b7aacc7c1449a206d4f79f4 “Miniscript: conversion from script”

These if statements are almost the same, ISTM this could be de-duplicated so that there is only one really long line to read.

darosior commented at 9:35 am on February 11, 2022:

If i do that i need to get rid of all the else ifs and replace them with if { ...; break;}. I can do that but it’s more a matter of taste than a net benefit.

EDIT: done.

in src/script/miniscript.h:257 in 85cf12e202 outdated

252+    }
253+};
254+
255+struct Ops {
256+    //! Non-push opcodes.
257+    uint32_t stat;

achow101 commented at 8:36 pm on February 7, 2022:

In 85cf12e20201eee4ed23902e1da151f63663cfab “Miniscript: ops limit and stack size computation”

This is named very similarly to sat on the next line. It is confusing and potentially disastrous if a typo is made.

0    uint32_t ops;

darosior commented at 3:34 pm on February 10, 2022:

Naming a field of Ops “ops” is a bit weird, went with count instead.

in src/script/miniscript.h:629 in 85cf12e202 outdated

624+            case Fragment::WRAP_D: return {3 + subs[0]->ops.stat, subs[0]->ops.sat, 0};
625+            case Fragment::WRAP_V: return {subs[0]->ops.stat + (subs[0]->GetType() << "x"_mst), subs[0]->ops.sat, {}};
626+            case Fragment::WRAP_J: return {4 + subs[0]->ops.stat, subs[0]->ops.sat, 0};
627+            case Fragment::WRAP_N: return {1 + subs[0]->ops.stat, subs[0]->ops.sat, subs[0]->ops.dsat};
628+            case Fragment::JUST_1: return {0, 0, {}};
629+            case Fragment::JUST_0: return {0, {}, 0};

achow101 commented at 9:04 pm on February 7, 2022:

In 85cf12e20201eee4ed23902e1da151f63663cfab “Miniscript: ops limit and stack size computation”

A lot of these are the same, so this could be de-duplicated in the same way that the size calculation was.

darosior commented at 5:32 pm on February 10, 2022:

Not so many are the same so it wasn’t a huge readability gain. So i re-ordered it to hopefully make it easier on the eyes.

I also broke down the super long lines into “count, sat, dsat”. I think that helps. Same for the stack size computation below.

in src/script/miniscript.h:674 in 85cf12e202 outdated

669+            case Fragment::WRAP_D: return {1 + subs[0]->ss.sat, 1};
670+            case Fragment::WRAP_V: return {subs[0]->ss.sat, {}};
671+            case Fragment::WRAP_J: return {subs[0]->ss.sat, 1};
672+            case Fragment::WRAP_N: return subs[0]->ss;
673+            case Fragment::JUST_1: return {0, {}};
674+            case Fragment::JUST_0: return {{}, 0};

achow101 commented at 9:04 pm on February 7, 2022:

In 85cf12e20201eee4ed23902e1da151f63663cfab “Miniscript: ops limit and stack size computation”

A lot of these are the same, so this can be de-duplicated in the same way that the size calculation was.

in src/script/miniscript.h:607 in 85cf12e202 outdated

599@@ -555,10 +600,110 @@ struct Node {
600         return res.has_value();
601     }
602 
603+    internal::Ops CalcOps() const {
604+        switch (nodetype) {
605+            case Fragment::PK_K: return {0, 0, 0};
606+            case Fragment::PK_H: return {3, 0, 0};
607+            case Fragment::OLDER: return {1, 0, {}};

achow101 commented at 9:06 pm on February 7, 2022:

In 85cf12e20201eee4ed23902e1da151f63663cfab “Miniscript: ops limit and stack size computation”

What is the distinction between {} and 0? How com some fragments use 0, and others use {}?

It seems like {} is being used for fragments that have no dis/satisfaction. However it is used for the hashing fragments and those have a dissatisfaction.

sipa commented at 9:20 pm on February 7, 2022:

While hashes do have dissatisfactions, they are always malleable. The ops counting algorithm only works for non-malleable signing, which will never use these.

(Just mentioning this to explain it to you; if it’s not clear from the code that this is the case it should be documented of course)

in src/script/miniscript.h:741 in 85cf12e202 outdated

697+
698+    //! Check the ops limit of this script against the consensus limit.
699+    bool CheckOpsLimit() const { return GetOps() <= MAX_OPS_PER_SCRIPT; }
700+
701+    //! Return the maximum number of stack elements needed to satisfy this script non-malleably.
702+    uint32_t GetStackSize() const { return ss.sat.value + 1; }

achow101 commented at 9:07 pm on February 7, 2022:

In 85cf12e20201eee4ed23902e1da151f63663cfab “Miniscript: ops limit and stack size computation”

It was not immediately obvious to me that this includes the script itself as a stack item, perhaps mention that in the docstring?

bitcoin deleted a comment on Feb 10, 2022

darosior commented at 11:44 am on February 11, 2022: member

Addressed Andrew’s comments, i also reworked the fuzz target. As a consequence i added a couple missing checks in the function decoding from Script. We are currently working on different approaches to write one or more fuzz targets generating random fragments in place of the random unit tests, which was removed in the previous push. They could be included here or in #24149 since it’s tightly related to testing the satisfaction logic.

Regarding Sjors’ point about splitting commits further i’d like to have other reviewers’ opinion. I’m personally still not sure that it makes sense but heh i’m not the one reviewing the PR :). So if others think that would be useful, i could break down the first commit into tiny ones..

darosior force-pushed on Feb 11, 2022

achow101 commented at 7:22 pm on February 14, 2022: member

ACK 4b74cc97d3543efe6c2f126da5e807da72cc782c

in src/script/miniscript.h:671 in f38df6abfb outdated

665+                    for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back(Choose(sats[j] + sub->ops.dsat, sats[j - 1] + sub->ops.sat));
666+                    next_sats.push_back(sats[sats.size() - 1] + sub->ops.sat);
667+                    sats = std::move(next_sats);
668+                }
669+                assert(k <= sats.size());
670+                return {count, sats[k], sats[0]};

achow101 commented at 9:49 pm on February 14, 2022:

in f38df6abfb40120899c7324b7e690d1b585bc26b “Miniscript: ops limit and stack size computation”

I’m having a bit of a hard time figuring out how this arrives at the right answer. Could you provide a brief explanation of how this loop works to count the opcodes (and stack size, and the input stack, in other places)?

darosior commented at 10:34 am on February 21, 2022:

The algorithm used here is the same as the one used for the satisfaction of a thresh fragment in #24149. The intent is to compute the maximum satisfaction and dissatisfaction cost (in various resources) for a given fragment.

For a thresh with n sub-fragments and a threshold of k the algorithm will end up with a vector of n elements, acting as a mapping from k -> cost. With the special case of k == 0 considered the dissatisfaction of the thresh fragment (the only non-malleable dissatisfaction of this fragment). Note a thresh with a k of 0 is invalid.

The algorithm works by adding for each sub the cost of its dissatisfaction to the first entry of the vector, and the cost of its satisfaction to the last entry. The entries from 1 to n - 1 are then updated with the bigger of:

the existing cost (at k) plus the dissatisfaction cost of the current sub, that is we have enough subs satisfied and we dissatisfy the current sub
the previous cost (k - 1) plus the satisfaction cost of the current sub, that is we are missing one sub to get to the threshold and we satisfy the current sub

darosior force-pushed on Feb 21, 2022

darosior commented at 2:27 pm on February 21, 2022: member

Pushed some cleanups by @sipa (https://github.com/sipa/miniscript/pull/101).

in src/script/miniscript.h:705 in 65c79db368 outdated

700+                return {sat, dsat};
701+            }
702+            case Fragment::OR_C: return {Choose(subs[0]->ss.sat, subs[0]->ss.dsat + subs[1]->ss.sat), {}};
703+            case Fragment::OR_D: return {Choose(subs[0]->ss.sat, subs[0]->ss.dsat + subs[1]->ss.sat), subs[0]->ss.dsat + subs[1]->ss.dsat};
704+            case Fragment::OR_I: return {Choose(subs[0]->ss.sat + 1, subs[1]->ss.sat + 1), Choose(subs[0]->ss.dsat + 1, subs[1]->ss.dsat + 1)};
705+            case Fragment::MULTI: return {(uint32_t)keys.size() + 1, (uint32_t)keys.size() + 1};

sanket1729 commented at 9:14 am on March 1, 2022:

In 65c79db36818acc193e21c4b5bb6bf7dbf8ff764:

This should be a number of signatures instead of keys.

darosior commented at 1:53 pm on March 17, 2022:

Done, and added a unit test reproducing this.

sanket1729 commented at 9:14 am on March 1, 2022: contributor

Did a partial review. Will review the remaining PR shortly.

fanquake added this to the milestone 24.0 on Mar 2, 2022

fanquake commented at 7:16 pm on March 3, 2022: member

@stepansnigirev you might be interested in reviewing this.

sipa commented at 7:19 pm on March 3, 2022: member

We’ll address all comments that have been left here soon, but just FYI, there are a bunch of improvements still ongoing in the miniscript repo itself (https://github.com/sipa/miniscript/, most of which will eventually be moved here after this PR and the followups).

DrahtBot added the label Needs rebase on Mar 4, 2022

script: make IsPushdataOp non-static

We'll need it for Miniscript

31ec6ae92a

script: move CheckMinimalPush from interpreter to script.h

It is used by Miniscript.

f4e289f384

script: expose getter for CScriptNum, add a BuildScript helper

Some prep work for Miniscript. BuildScript is an efficient way to build
Scripts in a generic manner (by concatenating OPs, data, and other
Scripts).

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

4fe29368c0

Miniscript: type system, script creation, text notation, tests

More information about Miniscript can be found at https://bitcoin.sipa.be/miniscript/ (the
website source is hosted at https://github.com/sipa/miniscript/).
This commit defines all fragments, their composition, parsing from
string representation and conversion to Script.

Co-Authored-By: Antoine Poinsot <darosior@protonmail.com>
Co-Authored-By: Sanket Kanjalkar <sanket1729@gmail.com>
Co-Authored-By: Samuel Dobson <dobsonsa68@gmail.com>

1ddaa66eae

Miniscript: conversion from script

Co-Authored-By: Antoine Poinsot <darosior@protonmail.com>
Co-Authored-By: Samuel Dobson <dobsonsa68@gmail.com>

2e55e88f86

Miniscript: ops limit and stack size computation

Co-Authored-By: Antoine Poinsot <darosior@protonmail.com>

f8369996e7

fuzz: add a fuzz target for Miniscript decoding from Script 2da94a4c6f

darosior commented at 1:52 pm on March 17, 2022: member

Rebased. This is now ready for review.

There are still refactorings to the fuzz targets that have not landed in the Miniscript repo yet, i’ll either add them here eventually or we’ll open them as followup PRs. See https://github.com/sipa/miniscript/issues/98 for details.

Changes since last push:

Fixed the CHECKMULTISIG stack size calculation bug (thanks Sanket!)
Choose was renamed to operator|
The modifications to script.h were split from the type system commit to make it only introduce miniscript.h
Some leftovers (from previous iterations of concatenating Scripts) were removed from vector.h

darosior force-pushed on Mar 17, 2022

DrahtBot removed the label Needs rebase on Mar 17, 2022

jb55 commented at 3:33 pm on March 19, 2022: contributor

ACK 2da94a4c6f55f7a3621f4a6f70902c52f735c868

I’ve been running the miniscript_decode fuzzer for awhile and it looks good. looking forward to testing the smarter fuzzers after this is merged.

in src/script/miniscript.cpp:20 in 2da94a4c6f

15+
16+Type SanitizeType(Type e) {
17+    int num_types = (e << "K"_mst) + (e << "V"_mst) + (e << "B"_mst) + (e << "W"_mst);
18+    if (num_types == 0) return ""_mst; // No valid type, don't care about the rest
19+    assert(num_types == 1); // K, V, B, W all conflict with each other
20+    bool ok = // Work around a GCC 4.8 bug that breaks user-defined literals in macro calls.

laanwj commented at 12:25 pm on April 4, 2022:

FYI: we require gcc 8.1 according to doc/dependencies.md. There’s no need to work around gcc 4.8 bugs.

darosior commented at 2:00 pm on April 5, 2022:

I’ll address than in #24148 .

sipa commented at 2:45 pm on April 5, 2022:

See https://github.com/sipa/miniscript/pull/112

laanwj commented at 1:37 pm on April 4, 2022: member

Light code review ACK 2da94a4c6f55f7a3621f4a6f70902c52f735c868 (mostly reviewed the changes to the existing code and build system)

laanwj merged this on Apr 5, 2022

laanwj closed this on Apr 5, 2022

sidhujag referenced this in commit 652944f6c1 on Apr 5, 2022

darosior commented at 9:01 am on April 15, 2022: member

Reviewers, before the integration into output descriptors, i’ve made a follow-up PR with the final updates and cleanups we made in the Miniscript repo. https://github.com/bitcoin/bitcoin/pull/24860

in src/script/miniscript.cpp:263 in 1ddaa66eae outdated

258+        case Fragment::AFTER: return 1 + BuildScript(k).size();
259+        case Fragment::HASH256:
260+        case Fragment::SHA256: return 4 + 2 + 33;
261+        case Fragment::HASH160:
262+        case Fragment::RIPEMD160: return 4 + 2 + 21;
263+        case Fragment::MULTI: return 3 + (n_keys > 16) + (k > 16) + 34 * n_keys;

sanket1729 commented at 0:44 am on April 23, 2022:

nit: I think this can be improved as 1 + BuildScript(n_keys).size() + BuildScript(k).size()

The current formulation is correct but internally relies on the reasoning that k and n cannot be greater than 20.

darosior commented at 1:25 pm on May 16, 2022:

Done in #24860, thanks

in src/script/miniscript.h:741 in f8369996e7 outdated

736+    //! Check the ops limit of this script against the consensus limit.
737+    bool CheckOpsLimit() const { return GetOps() <= MAX_OPS_PER_SCRIPT; }
738+
739+    /** Return the maximum number of stack elements needed to satisfy this script non-malleably, including
740+     * the script push. */
741+    uint32_t GetStackSize() const { return ss.sat.value + 1; }

sanket1729 commented at 1:47 am on April 28, 2022:

Same comment as above for the opcodes

in src/script/miniscript.h:734 in f8369996e7 outdated

729 public:
730     //! Return the size of the script for this expression (faster than ToScript().size()).
731     size_t ScriptSize() const { return scriptlen; }
732 
733+    //! Return the maximum number of ops needed to satisfy this script non-malleably.
734+    uint32_t GetOps() const { return ops.count + ops.sat.value; }

sanket1729 commented at 1:47 am on April 28, 2022:

What should we do when there is a script that cannot be satisfied? For example, thresh(1,0,a:0,a:pk(A)) is a valid miniscript that can never be satisfied. Should GetOps return 0 or some constant?

Maybe something like?

0uint32_t GetOps() const { return op.sat.valid ? ops.count + ops.sat.value : 0; }

This is really a nit, as I don’t see any useful miniscripts being constructed this way, but still good to check the validity of the variable before accessing it’s value.

darosior commented at 1:19 pm on May 16, 2022:

True, but i’m not sure it’s worth “fixing”. In this case returning 0 would be as wrong as any other value. We could probably make the return value std::optional but that sounds a bit overkill?

sanket1729 commented at 6:21 pm on May 16, 2022:

True, but i’m not sure it’s worth “fixing”.

Agreed. I don’t think it is worth fixing. Just wanted to highlight this.

in src/script/miniscript.h:689 in f8369996e7 outdated

684+            case Fragment::PK_K: return {1, 1};
685+            case Fragment::PK_H: return {2, 2};
686+            case Fragment::SHA256:
687+            case Fragment::RIPEMD160:
688+            case Fragment::HASH256:
689+            case Fragment::HASH160: return {1, {}};

sanket1729 commented at 8:31 am on April 28, 2022:

This should be {1, 0}. All hash types can be dis-satisfied with a random 32-byte pre-image.

darosior commented at 8:50 am on April 30, 2022:

But it’s malleable, so we don’t want to account for it.

sanket1729 commented at 9:22 pm on April 30, 2022:

Why be different while calculating stack size and opcodes? In calculating executed op code count, we count the correct opcodes when this expression is dissatisfied. But we don’t do so while considering stack size?

sipa commented at 2:48 pm on May 1, 2022:

The hashing fragments return {4, 0, {}} in CalcOps, and {1, {}} in CalcStackSize? In both cases, no value ({}) is returned for the dissatisfaction case, because the non-malleable signing algorithm will never use the dissatisfaction path.

sanket1729 commented at 6:20 pm on May 16, 2022:

Sorry, error on my part. You are correct

sanket1729 commented at 8:52 pm on May 19, 2022:

@sipa @darosior Revisiting this: I am considering should malleability rules even come into play over here? Any witness malleability cannot change the max opcode count. Though, it can potentially change the witness stack element count.

An example test-case in rust-miniscript broke of this,

c:and_v(or_c(sha256(H),v:multi(1,A)),pk_k(B))

Outputs maxops=8 because it does not count the malleable solution we dissatisfy sha256. Just trying to stay consistent with the definition of OpsCount with rust-miniscript.

If we are ignoring malleable solutions in Ops/StackElems, how about we change GetOps/GetStackSize to output Error/Option/-1 when it operates on the malleable script?

sipa commented at 10:25 pm on May 19, 2022:

@sanket1729 That’s probably reasonable, but I’m not sure it’s needed.

Really what these functions (as currently written) answer is: “what is the maximum stacksize/opcode needed for non-malleable satisfactions”. If you have a script with branches that cannot be satisfied non-malleable, you probably don’t care about the numbers of just the non-malleable ones, but you also probably don’t care about these functions in general. Their purpose is really only contributing to determining IsSane(TopLevel), and in case of not IsNonMalleable(), IsSane() will already be false.

sanket1729 commented at 11:08 pm on May 19, 2022:

@sipa Agreed. It might not be needed. I was translating the test vector from this PR to rust-miniscript when I noted the difference between the implementations.

c:and_v(or_c(sha256(H),v:multi(1,A)),pk_k(B)) with MaxOps() = 8 but rust-miniscript outputs 9.

I was also using them for cross-testing outputs with rust-miniscript to check why the value mismatches here. I agree that from an end-user perspective this is not really needed.

It might not be worth it to change the tests for future miniscript implementations(if any).

in src/script/miniscript.h:726 in f8369996e7 outdated

721+                assert(k <= sats.size());
722+                return {sats[k], sats[0]};
723+            }
724+        }
725+        assert(false);
726+        return {{}, {}};

sanket1729 commented at 8:42 am on April 28, 2022:

What’s the purpose of return after an assert? Is this normal in c++? Same comment for the above function

darosior commented at 8:49 am on April 30, 2022:

Yeah it’s not necessary, Marco mentioned it to me elsewhere. I can remove it in #24860

darosior commented at 1:25 pm on May 16, 2022:

Done in https://github.com/bitcoin/bitcoin/pull/24860

sanket1729 commented at 8:49 am on April 28, 2022: contributor

Finally completed the review. Sorry for the delay. Did a line-by-line comparison of all miniscript code with rust-miniscript. Did not review tests/fuzzer.

Found a couple of issues that can be addressed in followups. ACK for the rest of it

in src/script/miniscript.h:137 in 2da94a4c6f

132+    constexpr Type operator|(Type x) const { return Type(m_flags | x.m_flags); }
133+
134+    //! Compute the type with the intersection of properties.
135+    constexpr Type operator&(Type x) const { return Type(m_flags & x.m_flags); }
136+
137+    //! Check whether the left hand's properties are superset of the right's (= left is a subtype of right).

stickies-v commented at 10:39 pm on May 14, 2022:

Isn’t it the other way around, where if true then the right hand’s properties are a superset of the left’s?

stickies-v commented at 10:45 pm on May 14, 2022:

Sorry of course right after posting I see that the order of m_flags and x.m_flags is switched up for this operator compared to the other operators, which makes the docstring correct so please disregard my previous comment. The inconsistent order is maybe a bit confusing but no problem.

sipa commented at 10:46 pm on May 14, 2022:

No, the comment is correct I believe.

(x.m_flags & ~m_flags) is zero when every flag set in x.m_flags is also set in m_flags. In other words, where this’s flags (=left hand) are a superset of x’s flags.

achow101 referenced this in commit 85b601e043 on Jul 14, 2022

sidhujag referenced this in commit 2a8811a52a on Jul 18, 2022

bitcoin locked this on Aug 23, 2023

Miniscript integration #24147

Conflicts