Miniscript integration #24147

darosior · 2022-01-25T10:27:16Z

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 (Miniscript support in Output Descriptors #24148) introduces support for Miniscript in Output Descriptors, allowing for watch-only support of Miniscript Descriptors in the wallet.
The third one (Signing support for Miniscript Descriptors #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 How to fuzz stateful logic? #23105). A minified corpus of Miniscript Scripts is available at miniscript_decode: add initial corpus bitcoin-core/qa-assets#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..

src/script/miniscript.h

darosior · 2022-01-25T13:03:05Z

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) :)

Sjors · 2022-01-25T15:09:00Z

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.

meshcollider · 2022-01-25T21:00:47Z

Strong concept ACK

src/script/miniscript.h

sipa · 2022-01-25T21:01:31Z

src/test/miniscript_tests.cpp

+    g_testdata.reset();
+}
+
+BOOST_AUTO_TEST_CASE(random_tests)


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.

src/script/miniscript.h

DrahtBot · 2022-01-26T00:26:59Z

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.

src/script/script.h

jb55 · 2022-01-27T21:03:53Z

nice. Concept ACK.

dunxen · 2022-01-29T08:18:00Z

Concept ACK

darosior · 2022-01-29T09:37:04Z

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 · 2022-01-29T15:33:56Z

It's mostly 3a2c00d 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.

src/script/miniscript.h

src/script/miniscript.cpp

src/test/miniscript_tests.cpp

achow101 · 2022-01-31T22:59:02Z

src/script/miniscript.h

+    constexpr Type operator&(Type x) const { return Type(m_flags & x.m_flags); }
+
+    //! Check whether the left hand's properties are superset of the right's (= left is a subtype of right).
+    constexpr bool operator<<(Type x) const { return (x.m_flags & ~m_flags) == 0; }


In 3a2c00d "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.

src/script/miniscript.h

fanquake · 2022-03-03T19:16:42Z

@stepansnigirev you might be interested in reviewing this.

sipa · 2022-03-03T19:19:08Z

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).

We'll need it for Miniscript

It is used by Miniscript.

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>

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>

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

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

darosior · 2022-03-17T13:52:36Z

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 sipa/miniscript#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

jb55 · 2022-03-19T15:33:10Z

ACK 2da94a4

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.

laanwj · 2022-04-04T12:25:50Z

src/script/miniscript.cpp

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


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

I'll address than in #24148 .

See sipa/miniscript#112

laanwj · 2022-04-04T13:37:58Z

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

darosior · 2022-04-15T09:01:13Z

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.
#24860

sanket1729

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

src/script/miniscript.cpp

sanket1729 · 2022-04-28T01:47:14Z

src/script/miniscript.h

+
+    /** Return the maximum number of stack elements needed to satisfy this script non-malleably, including
+     * the script push. */
+    uint32_t GetStackSize() const { return ss.sat.value + 1; }


Same comment as above for the opcodes

sanket1729 · 2022-04-28T01:47:16Z

src/script/miniscript.h

 public:
    //! Return the size of the script for this expression (faster than ToScript().size()).
    size_t ScriptSize() const { return scriptlen; }

+    //! Return the maximum number of ops needed to satisfy this script non-malleably.
+    uint32_t GetOps() const { return ops.count + ops.sat.value; }


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?

uint32_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.

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?

True, but i'm not sure it's worth "fixing".

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

sanket1729 · 2022-04-28T08:31:42Z

src/script/miniscript.h

+            case Fragment::SHA256:
+            case Fragment::RIPEMD160:
+            case Fragment::HASH256:
+            case Fragment::HASH160: return {1, {}};


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

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

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?

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.

Sorry, error on my part. You are correct

@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?

@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.

@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).

sanket1729 · 2022-04-28T08:42:00Z

src/script/miniscript.h

+            }
+        }
+        assert(false);
+        return {{}, {}};


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

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

Done in #24860

stickies-v · 2022-05-14T22:39:24Z

src/script/miniscript.h

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


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

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.

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.

ffc79b8 qa: functional test Miniscript watchonly support (Antoine Poinsot) bfb0367 Miniscript support in output descriptors (Antoine Poinsot) 4a08288 qa: better error reporting on descriptor parsing error (Antoine Poinsot) d25d58b miniscript: add a helper to find the first insane sub with no child (Antoine Poinsot) c38c7c5 miniscript: don't check for top level validity at parsing time (Antoine Poinsot) Pull request description: This adds Miniscript support for Output Descriptors without any signing logic (yet). See the OP of #24147 for a description of Miniscript and a rationale of having it in Bitcoin Core. On its own, this PR adds "watchonly" support for Miniscript descriptors in the descriptor wallet. A follow-up adds signing support. A minified corpus of Miniscript Descriptors for the `descriptor_parse` fuzz target is available at bitcoin-core/qa-assets#92. The Miniscript descriptors used in the unit tests here and in #24149 were cross-tested against the Rust implementation at https://github.com/rust-bitcoin/rust-miniscript. This PR contains code and insights from Pieter Wuille. ACKs for top commit: Sjors: re-utACK ffc79b8 achow101: ACK ffc79b8 w0xlt: reACK ffc79b8 Tree-SHA512: 02d919d38bb626d3c557eca3680ce71117739fa161b7a92cfdb6c9c432ed88870b1ed127ba24248574c40c7428217d7e9bdd986fd8cd7c51fae8c776e1271fb9

ffc79b8 qa: functional test Miniscript watchonly support (Antoine Poinsot) bfb0367 Miniscript support in output descriptors (Antoine Poinsot) 4a08288 qa: better error reporting on descriptor parsing error (Antoine Poinsot) d25d58b miniscript: add a helper to find the first insane sub with no child (Antoine Poinsot) c38c7c5 miniscript: don't check for top level validity at parsing time (Antoine Poinsot) Pull request description: This adds Miniscript support for Output Descriptors without any signing logic (yet). See the OP of bitcoin#24147 for a description of Miniscript and a rationale of having it in Bitcoin Core. On its own, this PR adds "watchonly" support for Miniscript descriptors in the descriptor wallet. A follow-up adds signing support. A minified corpus of Miniscript Descriptors for the `descriptor_parse` fuzz target is available at bitcoin-core/qa-assets#92. The Miniscript descriptors used in the unit tests here and in bitcoin#24149 were cross-tested against the Rust implementation at https://github.com/rust-bitcoin/rust-miniscript. This PR contains code and insights from Pieter Wuille. ACKs for top commit: Sjors: re-utACK ffc79b8 achow101: ACK ffc79b8 w0xlt: reACK bitcoin@ffc79b8 Tree-SHA512: 02d919d38bb626d3c557eca3680ce71117739fa161b7a92cfdb6c9c432ed88870b1ed127ba24248574c40c7428217d7e9bdd986fd8cd7c51fae8c776e1271fb9

darosior mentioned this pull request Jan 25, 2022

Miniscript support in Output Descriptors #24148

Merged

darosior force-pushed the updated_miniscript branch from 4c172cb to 52165e4 Compare January 25, 2022 11:12

darosior mentioned this pull request Jan 25, 2022

miniscript_decode: add initial corpus bitcoin-core/qa-assets#85

Merged

darosior force-pushed the updated_miniscript branch from 52165e4 to 74d3f9b Compare January 25, 2022 11:45

darosior mentioned this pull request Jan 25, 2022

Don't use the locale-dependant std::to_string() sipa/miniscript#90

Closed

DrahtBot added Build system Consensus labels Jan 25, 2022

maflcko reviewed Jan 25, 2022

View reviewed changes

src/script/miniscript.h Outdated Show resolved Hide resolved

fanquake mentioned this pull request Jan 25, 2022

Basic Miniscript support in output descriptors #16800

Closed

darosior force-pushed the updated_miniscript branch from 74d3f9b to 86076cb Compare January 25, 2022 13:20

darosior force-pushed the updated_miniscript branch from 86076cb to 2b9f9f9 Compare January 25, 2022 15:14

sipa reviewed Jan 25, 2022

View reviewed changes

This was referenced Jan 26, 2022

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

Merged

Make script interpreter independent from storage type CScript #13062

Closed

laanwj added Descriptors Utils/log/libs and removed Consensus labels Jan 27, 2022

maflcko reviewed Jan 27, 2022

View reviewed changes

src/script/script.h Outdated Show resolved Hide resolved

maflcko removed Build system Utils/log/libs labels Jan 27, 2022

achow101 reviewed Jan 31, 2022

View reviewed changes

willcl-ark reviewed Feb 1, 2022

View reviewed changes

src/script/miniscript.h Outdated Show resolved Hide resolved

fanquake added this to the 24.0 milestone Mar 2, 2022

DrahtBot added the Needs rebase label Mar 4, 2022

darosior and others added 7 commits March 17, 2022 14:09

script: make IsPushdataOp non-static

31ec6ae

We'll need it for Miniscript

script: move CheckMinimalPush from interpreter to script.h

f4e289f

It is used by Miniscript.

script: expose getter for CScriptNum, add a BuildScript helper

4fe2936

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>

Miniscript: conversion from script

2e55e88

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

Miniscript: ops limit and stack size computation

f836999

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

fuzz: add a fuzz target for Miniscript decoding from Script

2da94a4

darosior force-pushed the updated_miniscript branch from cdd630e to 2da94a4 Compare March 17, 2022 13:52

DrahtBot removed the Needs rebase label Mar 17, 2022

laanwj reviewed Apr 4, 2022

View reviewed changes

laanwj merged commit d492dc1 into bitcoin:master Apr 5, 2022

sidhujag pushed a commit to syscoin/syscoin that referenced this pull request Apr 5, 2022

Merge bitcoin#24147: Miniscript integration

652944f

sanket1729 reviewed Apr 28, 2022

View reviewed changes

This was referenced May 6, 2022

Output Script Descriptor (with Miniscript) support BitBoxSwiss/bitbox02-firmware#911

Closed

Output Script Descriptor (with Miniscript) support trezor/trezor-firmware#2258

Open

stickies-v reviewed May 14, 2022

View reviewed changes

notmandatory mentioned this pull request May 18, 2022

The rpc blockchain tests don't work with Bitcoin Core 23.0 bitcoindevkit/bdk#598

Closed

sanket1729 mentioned this pull request May 19, 2022

Debug ms attributes test rust-bitcoin/rust-miniscript#413

Closed

glozow mentioned this pull request Sep 8, 2022

miniscript: avoid wasteful computation, prevent memory blowup when fuzzing #25540

Merged

bitcoin locked and limited conversation to collaborators Aug 23, 2023

Miniscript integration #24147

Miniscript integration #24147

Uh oh!

Conversation

darosior commented Jan 25, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

darosior commented Jan 25, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Sjors commented Jan 25, 2022

Uh oh!

meshcollider commented Jan 25, 2022

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

DrahtBot commented Jan 26, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

Uh oh!

jb55 commented Jan 27, 2022 via email

Uh oh!

dunxen commented Jan 29, 2022

Uh oh!

darosior commented Jan 29, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Sjors commented Jan 29, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

fanquake commented Mar 3, 2022

Uh oh!

sipa commented Mar 3, 2022

Uh oh!

darosior commented Mar 17, 2022

Uh oh!

jb55 commented Mar 19, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

laanwj commented Apr 4, 2022

Uh oh!

darosior commented Apr 15, 2022

Uh oh!

sanket1729 left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

darosior commented Jan 25, 2022 •

edited

Loading

darosior commented Jan 25, 2022 •

edited

Loading

DrahtBot commented Jan 26, 2022 •

edited

Loading

darosior commented Jan 29, 2022 •

edited

Loading

Sjors commented Jan 29, 2022 •

edited

Loading

sanket1729 left a comment •

edited

Loading