Basic Miniscript support in output descriptors #16800

pull sipa wants to merge 7 commits into bitcoin:master from sipa:201908_miniscript changing 11 files +1942 −103
  1. sipa commented at 2:58 am on September 4, 2019: member

    This pull request introduces support for miniscript in Bitcoin Core.

    The bulk of the code is in the 3 commits that add the miniscript module, including conversion from/to CScript, converting to and parsing from its engineer-readable string notation, property analysis and ops limit/stack size limit that are necessary to assess the security of arbitrary scripts.

    A number of tests are included, including tests against known scripts, and against randomly generated scripts.

    The final commit integrates the miniscript module into descriptors. This is only rudimentary, as it is not yet integrated in the signing code. I’m including it here to give something accessible to play with, but if desirable I can move that to a later PR as well.

  2. DrahtBot added the label Build system on Sep 4, 2019
  3. DrahtBot added the label Consensus on Sep 4, 2019
  4. DrahtBot added the label Tests on Sep 4, 2019
  5. DrahtBot added the label Utils/log/libs on Sep 4, 2019
  6. sipa force-pushed on Sep 4, 2019
  7. sipa force-pushed on Sep 4, 2019
  8. sipa force-pushed on Sep 4, 2019
  9. DrahtBot commented at 4:11 am on September 4, 2019: member

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

    Conflicts

    Reviewers, this pull request conflicts with the following ones:

    • #17056 (descriptors: Introduce sortedmulti descriptor by achow101)
    • #16889 (Add some general std::vector utility functions by sipa)
    • #16887 (Abstract out some of the descriptor Span-parsing helpers by sipa)
    • #16807 (Let validateaddress locate error in Bech32 address by meshcollider)
    • #16710 (build: Enable -Wsuggest-override if available by hebasto)
    • #16440 (BIP-322: Generic signed message format by kallewoof)
    • #15590 (Descriptor: add GetAddressType() and IsSegWit() by Sjors)
    • #13751 (Utils and libraries: Drops the boost/algorithm/string/split.hpp dependency by l2a5b1)

    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.

  10. practicalswift commented at 8:23 am on September 4, 2019: contributor

    Concept ACK

    Thanks for the great work on miniscript and the C++ implementation!

    This version seems to deviate somewhat to the version in the upstream repo which makes it unclear to me which of the issues I found during my review that have been addressed:

    Could you clarify? :-)

  11. fanquake removed the label Tests on Sep 4, 2019
  12. fanquake added the label Needs Conceptual Review on Sep 4, 2019
  13. fanquake removed the label Build system on Sep 4, 2019
  14. in src/script/miniscript.h:165 in 892acd4877 outdated 
    160+NodeRef<Key> MakeNodeRef(Args&&... args) { return std::make_shared<const Node<Key>>(std::forward<Args>(args)...); }
161+
162+//! The different node types in miniscript.
163+enum class NodeType {
164+    FALSE,     //!< OP_0
165+    TRUE,      //!< OP_1
    MarcoFalke commented at 11:32 am on September 4, 2019:

    Looks like these already are macros on mac from /home/travis/build/bitcoin/bitcoin/depends/SDKs/MacOSX10.11.sdk/usr/include/mach/boolean.h?

    And also in windows: https://travis-ci.org/bitcoin/bitcoin/jobs/580527642#L3384

    sipa commented at 6:13 pm on September 4, 2019:
    Fixed by renaming to JUST_0 and JUST_1.
  15. in src/test/miniscript_tests.cpp:115 in 892acd4877 outdated 
    110+        return true;
111+    }
112+};
113+
114+//! Singleton instance of KeyConverter.
115+const KeyConverter CONVERTER;
    MarcoFalke commented at 11:35 am on September 4, 2019: 
    0test/miniscript_tests.cpp:115:20: error: default initialization of an object of const type 'const (anonymous namespace)::KeyConverter' without a user-provided default constructor

    https://travis-ci.org/bitcoin/bitcoin/jobs/580527646#L3225

    sipa commented at 6:13 pm on September 4, 2019:
    Fixed pedantry by using const KeyConverter CONVERTER{}; instead.
  16. in src/script/miniscript.h:599 in 892acd4877 outdated 
    594+    for (int i = 0; i < expr.size(); ++i) {
595+        if (expr[i] == ':') {
596+            auto in2 = expr.subspan(i + 1);
597+            auto sub = Parse<Key>(in2, ctx);
598+            if (!sub || in2.size()) return {};
599+            for (size_t j = i; j-- > 0; ) {
    MarcoFalke commented at 11:38 am on September 4, 2019: 
    0Running tests: miniscript_tests from test/miniscript_tests.cpp
1Running 2 test cases...
2Test cases order is shuffled using seed: 1580527639
3Entering test module "Bitcoin Core Test Suite"
4test/miniscript_tests.cpp(282): Entering test suite "miniscript_tests"
5test/miniscript_tests.cpp(322): Entering test case "random_tests"
6script/miniscript.h:599:33: runtime error: unsigned integer overflow: 0 - 1 cannot be represented in type 'size_t' (aka 'unsigned long')
    sipa commented at 6:13 pm on September 4, 2019:
    Thanks for investigating; fixed.
  17. sipa force-pushed on Sep 4, 2019
  18. sipa force-pushed on Sep 4, 2019
  19. sipa commented at 6:18 pm on September 4, 2019: member

    @practicalswift Thanks for reminding me, I had forgotten about those (and wasn’t really looking at the miniscript repo while working on this PR). Specifically:

    • The overflow/underflow issue and the OOM issue don’t apply here, as they’re in the compiler code which I’m not PR’ing here.
    • The unhandled exception I’ve fixed independently because stoul and friends are locale dependent (both here and upstream).
    • The stack depth we need to fix still, I’ve commented on the issue.

    Also, this PR should be perfectly in sync with the upstream repo, so if you want to PR fixes, they can go there preferably, and I’ll incorporate them here.

  20. sipa force-pushed on Sep 4, 2019
  21. sipa force-pushed on Sep 4, 2019
  22. sipa force-pushed on Sep 4, 2019
  23. sipa force-pushed on Sep 4, 2019
  24. sipa force-pushed on Sep 4, 2019
  25. in src/script/miniscript.h:508 in 046a0b9cc2 outdated 
    503+                    if (sub->ss.sat.valid) diffs.push_back((int32_t)sub->ss.sat.value - (int32_t)sub->ss.dsat.value);
504+                }
505+                if (diffs.size() < k) return {{}, dsat};
506+                std::sort(diffs.begin(), diffs.end());
507+                for (size_t i = diffs.size() - k; i < diffs.size(); ++i) sat_sum += diffs[i];
508+                return {sat_sum + dsat, dsat};
    MarcoFalke commented at 11:41 pm on September 4, 2019:

    Looks like this is still failing on https://bitcoinbuilds.org/index.php?job=e1623137-779c-47dd-8a8a-ebaee60766ec

    0Entering test module "Bitcoin Core Test Suite"
1test/miniscript_tests.cpp(282): Entering test suite "miniscript_tests"
2test/miniscript_tests.cpp(284): Entering test case "fixed_tests"
3test/miniscript_tests.cpp(284): Leaving test case "fixed_tests"; testing time: 35249us
4test/miniscript_tests.cpp(322): Entering test case "random_tests"
5script/miniscript.h:508:33: runtime error: unsigned integer overflow: 4294967295 + 11 cannot be represented in type 'unsigned int'
6    [#0](/bitcoin-bitcoin/0/) 0x561901402481 in miniscript::Node<CPubKey>::CalcStackSize() const /home/ubuntu/src/src/./script/miniscript.h:508:33
    sipa commented at 5:12 pm on September 6, 2019:
    Fixed by switching to a different algorithm.
  26. sipa force-pushed on Sep 5, 2019
  27. Abstract out some of the descriptor Span-parsing helpers fc4691899d
  28. Add some general std::vector utility functions 
    Added are:

* Vector(arg1,arg2,arg3,...) constructs a vector with the specified
  arguments as elements. The vector's type is derived from the
  arguments. If some of the arguments are rvalue references, they
  will be moved into place rather than copied (which can't be achieved
  using list initialization).

* Cat(vector1,vector2) returns a concatenation of the two vectors,
  efficiently moving elements when relevant.

Vector generalizes (and replaces) the Singleton function in
src/descriptor.cpp, and Cat replaces the Cat function in bech32.cpp
    663d5e7908
  29. sipa force-pushed on Sep 5, 2019
  30. Miniscript: type system, script creation, text notation, tests f9fb48eba1
  31. Miniscript: conversion from script 36cd6f903e
  32. Miniscript: ops limit and stack size computation 5c86ef5d19
  33. Abstract out DescriptorImpl::KeyToString d316203de6
  34. Basic Miniscript support in output descriptors 037e55adc0
  35. sipa force-pushed on Sep 5, 2019
  36. practicalswift commented at 12:46 pm on September 12, 2019: contributor

    I’m afraid a carefully constructed script is able to trigger a heap out-of-bounds read in Node::CalcOps (called indirectly from miniscript::FromScript).

    Node::CalcOps appears to be reachable via RPC calls listunspent, scantxoutset and getaddressinfo (see call graph below).

    Code:

    https://github.com/bitcoin/bitcoin/blob/037e55adc005e9d8253d3d35e7a30b2e8521389c/src/script/miniscript.h#L451-L462

    Note that k is not necessarily within bounds.

    Call graph:

    • listunspent/scantxoutset/getaddressinfo → InferDescriptor → InferScript → miniscript::FromScript → DecodeMulti → DecodeSingle → MakeNodeRef → Node ctor → Node::CalcOps

    (Also posted to the original repo as https://github.com/sipa/miniscript/issues/12)

  37. practicalswift commented at 3:09 pm on September 12, 2019: contributor
    The smallest Bitcoin script I’ve been able to construct that triggers this heap out-of-bounds read is OP_0 OP_2 OP_EQUAL (00 52 87).
  38. practicalswift commented at 3:22 pm on September 12, 2019: contributor

    Found another somewhat related issue: an assertion failure in ComputeType is hit when processing the script OP_0 OP_0 OP_EQUAL (00 00 87).

    0bitcoin/script/miniscript.cpp:54: 
1    miniscript::Type miniscript::internal::ComputeType(…):
2    Assertion `k > 1 && k < n_subs' failed.

    It is AFAICT reachable via the same code paths as the Node::CalcOps discussed above.

    (Also posted to the original repo as https://github.com/sipa/miniscript/issues/13).

  39. promag commented at 10:36 pm on September 15, 2019: member

    Concept ACK.

    You could submit the refactors as separate pulls one by one. For instance, one for fc4691899d128cd4d8a8b60503803fc53d43eb9f which I think is acceptable on its own.

  40. laanwj added the label Feature on Sep 30, 2019
  41. DrahtBot commented at 7:13 pm on October 8, 2019: member
  42. DrahtBot added the label Needs rebase on Oct 8, 2019
  43. MarcoFalke referenced this in commit befdef8aee on Oct 10, 2019
  44. sidhujag referenced this in commit a7e4761106 on Oct 11, 2019
  45. MarcoFalke referenced this in commit 0ff7cd7d0c on Oct 18, 2019
  46. sidhujag referenced this in commit e432a0902d on Oct 18, 2019
  47. practicalswift commented at 11:09 pm on October 27, 2019: contributor
    @sipa Would you mind cherry-picking in the miniscript::FromScript(...) fuzzer from #17129 in to this PR? That would allow for closing #17129 which is entirely dependent on the merge of this one anyway :)
  48. practicalswift commented at 6:55 pm on November 12, 2019: contributor
    @fanquake Could you add “Waiting for author”? :)
  49. MarcoFalke commented at 6:59 pm on November 12, 2019: member
    “Needs rebase” implies “Waiting for author”
  50. achow101 commented at 7:09 pm on February 7, 2020: member

    I’ve noticed that there are some Miniscript functions that may conflict in naming or functionality with existing output descriptors that may cause issues.

    • multi() and thresh_m() are functionally the same. So the easy thing to do would be to just make multi() an alias for thresh_m()
    • sortedmulti() currently has no Miniscript counterpart. But I think that is easily solved by having a sorted_thresh_m() which is semantically the same.
    • pkh() and pk_h() are very similar, both in naming and function. pkh() is the same as c:pk_h() so I think we can just call pkh() an alias for c:pk_h(). Since pkh() and pk_h() are named differently, the only other issue is that they may confuse people.
    • pk() in descriptors directly conflicts with pk() in Miniscript. pk() in descriptors is c:pk() in Miniscript. Because they are named exactly the same but have (slightly) different meanings, this can cause some issues.
      • One solution is to change the meaning of pk() depending on its location. If found at the top level or as the direct child of a sh() or wsh(), it would mean the current meaning today (to preserve compatibility). If found elsewhere, it would have the Miniscript meaning. But this solution is confusing as pk() has multiple meanings and it could be easy to mess up.
      • Alternatively we could deprecate and remove the usage of pk() and replace it with c:pk(). We could add c:pk() now (for 0.20) and have it mean the same thing as pk() now. Then once Miniscript is merged, remove pk()’s descriptor definition and just use the Miniscript definition. We could add warnings in some places as well to let people know that their usage of pk() is deprecated. The good thing about this is that pk() probably isn’t currently being used so this probably won’t effect a lot of people.

    We will still need to preserve the current naming of functions as people may already be using them and changing these would break compatibility. At least most of these are straightforward aliases.

  51. sipa deleted a comment on Feb 7, 2020
  52. Sjors commented at 3:29 pm on February 10, 2020: member

    Concept ACK, after many hours of @apoelstra explaining Miniscript and its relation to Output Descriptors :-)

    I like @achow101’s suggestion:

    • Alternatively we could deprecate and remove the usage of pk() and replace it with c:pk(). We could add c:pk() now (for 0.20) and have it mean the same thing as pk() now.

    Would be great to get a rebase of this before 0.20 splits off, so we can deprecate other Output Descriptor stuff early on, if needed.

  53. sipa commented at 8:00 pm on February 12, 2020: member

    After a number of discussions, I think this highlights the possibility to decrease the gap between Miniscript and non-Miniscript descriptors.

    My suggestion is making the following changes to Miniscript:

    • Rename thresh_m to multi.
    • Rename pk to pk_k.
    • Add an alias pk(A)=c:pk_k(A) (just like and_n(A,B)=andor(A,B,0) for example).
    • Add an alias pkh(A)=c:pk_h(A).

    That means that for users, there doesn’t need to be a distinction between Miniscript or not, as pk(A) and wsh(pk(A)) would look uniform. Meanwhile, implementations could choose what to deal with at what layer (e.g. top-level pkh could be dealt with as a special case, or through a sufficiently generic Miniscript library).

    I prefer this approach as at this stage I’m more comfortable with making some small changes to Miniscript, than to change descriptors in general.

  54. practicalswift commented at 7:16 am on February 13, 2020: contributor
    @sipa I would like to continue my robustness testing of this PR. Could you please rebase on master and perhaps also pull in my fix for the heap out-of-bounds read present in the current version of this PR: “Avoid heap out-of-bounds read in Node::CalcOps (test case: OP_0 OP_2 OP_EQUAL) and assertion failure in ComputeType (test case: OP_0 OP_0 OP_EQUAL)”? :)
  55. darosior commented at 12:37 pm on July 24, 2020: member
    Concept ACK
  56. michaelfolkson commented at 5:28 pm on July 30, 2021: contributor

    Scratching the surface on what would be needed to revitalize this PR. Obviously there is a mega rebase to do as it has been sitting here for a while but there have also been some changes since to the C++ implementation of Miniscript. Presumably it would make sense to work on the Core rebase first and then the Miniscript updates?

    edit:

    This version seems to deviate somewhat to the version in the upstream repo which makes it unclear to me which of the issues I found during my review that have been addressed:

    Plus this. Not just Miniscript updates since this PR was opened but deviations before the updates.

  57. meshcollider commented at 4:27 am on August 22, 2021: contributor
    (Just for the information of those wondering what’s happening here, there are currently a few things being finished up in the miniscript repository before this PR is rebased, but it is a current WIP so expect something soon-ish!)
  58. DrahtBot commented at 12:29 pm on December 22, 2021: member
    • Is it still relevant? ➡️ Please solve the conflicts to make it ready for review and to ensure the CI passes.
    • Is it no longer relevant? ➡️ Please close.
    • Did the author lose interest or time to work on this? ➡️ Please close it and mark it ‘Up for grabs’ with the label, so that it can be picked up in the future.
  59. Sjors commented at 1:49 pm on December 28, 2021: member
    It would be nice to have an up to date version here to compare with ElementsProject/libwally-core#310
  60. darosior commented at 2:12 pm on December 28, 2021: member

    The most up-to-date WIP is available here https://github.com/darosior/bitcoin/pull/2 but for the purpose of reviewing other implementations i’d recommend checking against the C++ implem at sipa/miniscript or the Rust one at rust-bitcoin/rust-miniscript. ——– Original Message ——– On Dec 28, 2021, 14:49, Sjors Provoost wrote:

    It would be nice to have an up to date version here to compare with ElementsProject/libwally-core#310

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

  61. fanquake commented at 12:52 pm on January 25, 2022: member
    @sipa did you want to close this now that #24147 is open?
  62. sipa commented at 3:43 pm on January 25, 2022: member
    Superseded by #24147.
  63. sipa closed this on Jan 25, 2022
  64. laanwj referenced this in commit d492dc1cda on Apr 5, 2022
  65. DrahtBot locked this on Jan 25, 2023


sipa DrahtBot practicalswift MarcoFalke promag achow101 Sjors darosior michaelfolkson meshcollider fanquake

Labels
Feature Consensus Utils/log/libs Needs rebase Needs Conceptual Review

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-12-21 15:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me