sipa / miniscript Goto Github PK

View Code? Open in Web Editor NEW

156.0 21.0 47.0 605 KB

Miniscript site and implementation

Makefile 0.29% C 1.98% C++ 87.93% HTML 9.78% CSS 0.02%

miniscript's Introduction

Go to the Miniscript website.

This repository contains a C++ implementation of Miniscript and a number of related things:

The core Miniscript module (cpp, h) together with a number of dependencies based on the Bitcoin Core source code.
A policy to Miniscript compiler (cpp, h).
Javascript wrappers for the website (cpp).
The project website (.html).

miniscript's People

Contributors

Stargazers

Watchers

Forkers

jakinyele sanket1729 microhexhq pox honsa sticker592 cryptorurik nayuta-ueno afk11 ko-matsu tzawislak kallewoof jimmysong lukechilds gwillen harrigan shesek thelyo vergecurrency dgpv nirvananimbusa matwwje darosior meshcollider jwobith jenward12003 22388o bigspider kindly12 richard875 rnshah9 fanquake landabaso timechain-academy benma bitcoinerlab instagibbs 5l1v3r1 satshub adewaleijalana brunoerg f1r3hydr4nt scgbckbone bitcoincore-dev kingcrypto38 gopherj

miniscript's Issues

miniscript::Node::operator== is recursive

Should we:

try to turn it into a non-recursive algorithm
try to remove it
leave it

Taproot support?

Will miniscript be adapted for taproot?
I guess a few things should change for taproot, as now we need the tap scripts, and not using OP_CHECKMULTISIG.

bug: `pk()()` is considered a valid policy

pk()() is considered a valid policy because it identifies )( as the name.

Found via: bitcoinfuzz

Calling FromScript with a script with 2000 consecutive OP_CHECKSIGVERIFY opcodes causes execution to halt due to running out of stack space

Calling FromScript with a script with 2000 consecutive OP_CHECKSIGVERIFY opcodes causes execution to halt due to running out of stack space.

The root cause is the unbounded recursion in Decode, DecodeMulti, DecodeSingle and DecodeWrapped.

The site currently says: "Fragments that do not change the semantics of their subexpressions are called wrappers." and a bit below it says "t:, l:, and u: wrappers are syntactic sugar for other Miniscripts".

The wrappers with their opcodes are listed under "X (identities)" in the translations table.

Other than the c: and v: wrappers, their purpose is rather mysterious to me.

FromString accepts ":" without a wrapper character before it

sorted_thresh_m fragment needed (bip67)?

It would be practical if miniscript could be used to represent multisig scripts currently used in practice. sorted_thresh_m(k,key_1,...,key_n) would behave like thresh_m(k,key_1,...,key_n), but would sort the keys according to bip67 when producing the redeem script.

edit: to elaborate, the mental hang-up I am having is that if you plugged in xpubs in the textual representation, thresh_m(k, xpub_1, xpub_2), it is not obvious if one is allowed sort the derived subkeys before creating the redeem script. It would be an additional rule and it is not clear to me at what level to encode this so the miniscript-with-xpubs combination stays portable between wallets.

Compiler outputs suboptimal miniscript for `or(pk(k1),pk(k2))`

The second policy example at https://bitcoin.sipa.be/miniscript/

"One of two keys (equally likely)" - or(pk(key_1),pk(key_2))) - compiles to or_b(pk(key_1),s:pk(key_2)).

Should it not compile to multi(1,key_1,key_2) instead, which has the same witness size but a smaller script size (71 WU vs 72 WU)?

Support `after()` timelocks with values up to 2^32

Opened for discussion. Previous discussions: #97, https://gnusha.org/miniscript/2022-02-07.log.

Allow k = 1 and k = n for thresh.

Allowing k = 1 and k = n increases the expressiveness of current language.

Things to make sure in a PR addressing this issue:
Recheck all the typing rules for thresh fragment without the 1<k<n constraint.

Should `a:` forward `z`? Better yet, we could accept a `Bz` where a `W` is currently required

Could be something we want to do eventually.

12:09 < darosior> Why doesn't the 'a:' wrapper "forward" the 'z' property? Sure TOALTSTACK <X> FROMALTSTACK does technically consume the top stack element, but it puts it back and as long as X is 'z' it should appear to the following OPs as if it didn't consume anything.
12:11 < darosior> I was thinking about this in the context of https://github.com/sipa/miniscript/pull/105#issuecomment-1074459067, but unfortunately it would only enable '0' to be 'Wzdu' which is not very interesting. Still, i wonder if the 'a:' wrapper should for some reason never be 'z'?
12:11 <@sipa> There are other properties missing around W and z. Every Bz could be automatically treated as a W directly too.
12:11 <@sipa> But I think those aren't all that useful in practice.
12:16 < darosior> I'll open an issue regarding 'z' and 'W' <-> 'Bz', if you don't mind. Probably not worth addressing now but there could be use case we missed
12:17 <@sipa> Counting Bz as W or Wz would be even better than passing through z through a.
12:17 < darosior> Oh, right
12:17 <@sipa> It might need a "wrapper" that involves no opcode, like and_v, to convert Bz to Wz
12:18 <@sipa> Alternatively, we could just permit and_b or_b and thresh to accept Bz args
12:18 <@sipa> In addition to W args.

Link to the discussion logs

Multiple "e" modifier differences between spec and impl. for choice-related fragments

or_b: spec claims it is always e, implementation does e=e_x*e_z

or_d: spec claims e=e_z, implementation does e=e_x*e_z

andor: spec claims e=e_z and (s_x or f_y), implementation does e=e_x*e_z*(s_x+f_y)

thresh: spec claims e=all are s, implementation does e=all e and all s

(note that implementation uses 'x, y' instead for arguments of or_* fragments while the spec uses x, z. I used the spec convention in the examples above)

It seems likely that the specification is out of sync and the implementation is correct. But I cannot say this with certainty, because this will take significant time to analyze for me. Most likely the authors of the spec and implementation had already done this analysis, so I ask for clarification. If the spec is just out of sync, I will submit PR to fix the spec, and adjust my formal spec accordingly.

Implementation error for malleability type inference for `or_d`

The e type property for or_d is computed as e=e_x*e_y

miniscript/bitcoin/script/miniscript.cpp

Line 175 in 484386a

(x & y & "zes"_mst) | // z=z_x*z_y, e=e_x*e_y, s=s_x*s_y

The website's type table however states that e=e_z (which in the code would be e=e_y):

miniscript/index.html

Line 624 in 484386a

    
           <tr><td><code>or_d(<em>X</em>,<em>Z</em>)</code></td><td>e<sub>X</sub> and (s<sub>X</sub> or s<sub>Z</sub>)</td><td>s=s<sub>X</sub>s<sub>Z</sub>; f=f<sub>Z</sub>; e=e<sub>Z</sub></td></tr>

The rust-miniscript library also implements it as e=e_y:

https://github.com/rust-bitcoin/rust-miniscript/blob/a0648b3a4d63abbe53f621308614f97f04a04096/src/miniscript/types/malleability.rs#L241

Too long hex strings (correct length + 1) are accepted as valid arguments to hash160/ripemd160/hash256/sha256 in policies

Too long hex strings (correct length + 1) are accepted as valid arguments to hash160/ripemd160/hash256/sha256 in policies.

For hash160 and ripemd160:

40 char hex is valid as expected:

$./miniscript <<< "hash160(1234567890123456789012345678901234567890)"
      0 scriptlen=27 maxops=4 type=B safe=no nonmal=yes dissat=yes input=1n output=1 miniscript=hash160(1234567890123456789012345678901234567890)

41 char hex is unexpectedly valid:

$ ./miniscript <<< "hash160(12345678901234567890123456789012345678901)"
      0 scriptlen=27 maxops=4 type=B safe=no nonmal=yes dissat=yes input=1n output=1 miniscript=hash160(12345678901234567890123456789012345678901)

42 char hex is invalid as expected:

$ ./miniscript <<< "hash160(123456789012345678901234567890123456789012)"
Failed to parse as policy or miniscript 'hash160(123456789012345678901234567890123456789012)'

For hash256 and sha256:

64 char hex is valid as expected:

$ ./miniscript <<< "hash256(1234567890123456789012345678901234567890123456789012345678901234)"
      0 scriptlen=39 maxops=4 type=B safe=no nonmal=yes dissat=yes input=1n output=1 miniscript=hash256(1234567890123456789012345678901234567890123456789012345678901234)

65 char hex is unexpectedly valid:

$ ./miniscript <<< "hash256(12345678901234567890123456789012345678901234567890123456789012345)"

66 char hex is invalid as expected:

$ ./miniscript <<< "hash256(123456789012345678901234567890123456789012345678901234567890123456)"

hash160/ripemd160: concrete hash missing in output script

At https://bitcoin.sipa.be/miniscript/, if I enter this miniscript:

sha256(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa)

I receive the expected script structure:

OP_SIZE <20> OP_EQUALVERIFY OP_SHA256
<aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa> OP_EQUAL

For hash160/ripemd160 however, the hash is missing in the script. For example:

hash160(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa) results in:

OP_SIZE <20> OP_EQUALVERIFY OP_HASH160  OP_EQUAL

(<a....> is missing before OP_EQUAL).

using hash160(H) correctly outputs:

OP_SIZE <20> OP_EQUALVERIFY OP_HASH160 <h> OP_EQUAL

"or(sha256(H),sha256(H))" not equivalent to "sha256(H)" in threshold construction?

$ ./miniscript <<< "thresh(2,sha256(H),sha256(H),sha256(H))"
      0 scriptlen=121 maxops=15 type=(invalid) safe=no nonmal=no dissat=unknown input=- output=nonzero miniscript=thresh(2,sha256(H),sha256(H),sha256(H))
$ ./miniscript <<< "thresh(2,sha256(H),sha256(H),or(sha256(H),sha256(H)))"
Cannot compile arg=2 as B
Failed to parse as policy or miniscript 'thresh(2,sha256(H),sha256(H),or(sha256(H),sha256(H)))'

Note the "Cannot compile arg=2 as B" output written to stderr:

$ git grep -B3 "Cannot compile arg=%i as B"
compiler.cpp-            for (size_t i = 0; i < strat->sub.size(); ++i) {
compiler.cpp-                const Compilation& comp = GetCompilation(strat->sub[i], pqs.first[i], pqs.second[i], cache);
compiler.cpp-                auto res_B = comp.Query("Bemdu"_mstf);
compiler.cpp:                if (res_B.size() == 0) {fprintf(stderr, "Cannot compile arg=%i as B\n", (int)i); return; }

Is this expected behaviour? :-)

stability guarantees or versioned releases

I am not yet familiar with miniscript, so please correct me if my assumptions are wrong.

In order to be able to add miniscript support to a wallet, it seems like a requirement that the miniscript->Script compiler is stable over time, i.e. the same miniscript should always (in the future) compile to the same Script. If this wasn't the case, a wallet receiving miniscripts from the user would also need to store/backup the compiled Script so the user can spend the utxos again in the future.

An alternative (but less desirable) option is that the compiler has official versioned releases using semantic versioning, and keep the Script output stable per major version. Then a wallet could store the compiler version alongside the miniscript, to be able to derive the right Script again in the future. In this case, the miniscript itself might benefit from a version prefix, to make compatibility between different wallets easier.

It would be great to document the current status and the promises this project can make in the README.

Mistake in malleability type table for `thresh`

The malleability type properties for thresh on the website state:

s=at most k-1 are non-s; e=all are s

for e it should say e=all are e and all are s. The code implements it like this too:

miniscript/bitcoin/script/miniscript.cpp

Line 241 in 484386a

"e"_mst.If(all_e && num_s == n_subs) | // e=all e and all s

Fuzz targets

We agreed upon having:

A fuzz target for FromScript(). ~~That's #78.~~ That's #106.
A fuzz target for random node generation that's "dumb" (does not help the fuzzer to generate valid nodes). That's #100.
A fuzz target for random node generation that's "smart" (does help the fuzzer to generate valid nodes). That's #105
A fuzz target for FromString(). That's #106

Calling node->ToString on a node constructed from 2000 consecutive OP_FALSE opcodes causes execution to halt due to running out of stack space

Calling node->ToString on a node constructed from 2000 consecutive OP_FALSE opcodes causes execution to halt due to running out of stack space.

The root cause is the unbounded recursion in MakeString.

"0" and "1" accepted as valid policies

~~It seems like 0 and 1 are accepted as valid policies by the C++ implementation:~~

$ ./miniscript <<< "0"
      0 scriptlen=1 maxops=0 type=B safe=yes nonmal=yes dissat=unique input=0 output=1 miniscript=0
$ ./miniscript <<< "1"
      0 scriptlen=1 maxops=0 type=B safe=no nonmal=yes dissat=no input=0 output=1 miniscript=1

~~Is this intentional?~~

~~It seems like 0 and 1 are not valid in other contexts in a Miniscript policy:~~

$ ./miniscript <<< "and(pk(H),1)"
Failed to parse as policy or miniscript 'and(pk(H),1)'

~~Is there any use case for 0 and 1 as part of policy language or could they be dropped from the policy vocabulary?~~

Analyzing Scripts

While browsing the code i found this :-

miniscript/bitcoin/script/miniscript.h

Line 1226 in 02682a3

    
           inline NodeRef<typename Ctx::Key> FromScript(const CScript& script, const Ctx& ctx) {

Can this be used to analyze existing scripts? To maybe produce a more efficient version ?

Modernize codebase: optional instead of out-args

The codebase in several places uses constructions like functions that return a bool to communicate success/failure, and then actually put their output in a by-ref argument, e.g.:

template<typename Ctx> bool ToString(const Ctx& ctx, std::string& ret) const

With the code now using C++17, I think those should be retrofitted to use std::optional instead:

template<typename Ctx> std::optional<std::string> ToString(const Ctx& ctx) const

(and many other examples)

Sematics of "andor" differs from expected by the reader (no mention that it is satisfaction-dependent)

miniscript/index.html

Lines 251 to 255 in 027b422

    
           <tr> 
        
             <td>(<em>X</em> and <em>Y</em>) or <em>Z</em></td> 
        
             <td><code>andor(<em>X</em>,<em>Y</em>,<em>Z</em>)</code></td> 
        
             <td><samp><em>[X]</em> NOTIF <em>[Z]</em> ELSE <em>[Y]</em> ENDIF</samp></td> 
        
           </tr>

For andor(X,Y,Z) the semantics is listed as (X and Y) or Z, while the code [X] NOTIF [Z] ELSE [Y] ENDIF when applied to the truth table for the three variables does not correspond to the truth table that results from (X and Y) or Z expression.

This can be shown with the following script (using python-bitcoinlib):

from bitcoin.core import *
from bitcoin.core.script import *
from bitcoin.core.scripteval import *

print(f'X Y Z | E A')
print(f'-----------')
for X in (0, 1):
    for Y in (0, 1):
        for Z in (0, 1):
            script = CScript([X, OP_NOTIF, Z, OP_ELSE, Y, OP_ENDIF])
            stack=[]
            EvalScript(stack, script, CTransaction(), 0)

            expected = (X and Y) or Z
            actual = int(bool(stack[0]))

            print(f'{X} {Y} {Z} | {expected} {actual}')

the output:

X Y Z | E A
-----------
0 0 0 | 0 0
0 0 1 | 1 1
0 1 0 | 0 0
0 1 1 | 1 1
1 0 0 | 0 0
1 0 1 | 1 0
1 1 0 | 1 1
1 1 1 | 1 1

We can see that for X=1 Y=0 Z=1 the result of (X and Y) or Z does not correspond to the result of evaluating the script.

Either the logical expression in the 'Semantics' column has to be (X or Z) and ((not X) or Y), or the script in the Bitcoin script column has to be changed to have the semantics of (X and Y) or Z

Why after(n) and older(n) are limited to 231-1 while opcodes allow up to 239-1 ?

To quote the comment from Bitcoin's interpreter.cpp:

//This limitation is implemented by CScriptNum's default 4-byte limit.
              
// If we kept to that limit we'd have a year 2038 problem,
// even though the nLockTime field in transactions
// themselves is uint32 which only becomes meaningless
// after the year 2106.

I can imagine that someone might want to create a spend policy to restrict spending in the next 18+ years (example: give coins to newborn that they can spend only when they are an adult), and this would take the value beyond year 2038

Witness malleability only avoided under standardness rules: reference for the reasoning ?

I remember watching a talk about miniscript, and the witness malleability issue was discussed (Unfortunately I don't have the link to this talk).

IIRC, It was said that because preventing witness malleability under consensus rules is very hard, and at the same time only miners can malleate the witnesses in a way that breaks the standardness rules. And the miners are the entities that can directly influence the transaction ordering anyway. Thus it was said that it is sufficient to only consider the avoidance of witness malleability for miniscript under standartness rules.

Is there any document with that reasoning spelled out, that I can reference from my own texts, to not re-state the reasoning about the decision?

Missing "make check"

Missing make check.

make check would simply run the test suite (miniscript_tests.cpp) :-)

thresh_m() in the spec, multi() in the code - should be in sync ?

The spec uses thresh_m(k,key1,...,keyn) to denote CHECKMULTISIG-based check, but the miniscript binary only allows multi(k,...).

Is there a reason to keep thresh_m in the spec, and not change it to multi ?

Heap out-of-bounds read in Node::CalcOps when processing script OP_0 OP_2 OP_EQUAL

I'm afraid a carefully constructed script is able to trigger a heap out-of-bounds read in Node::CalcOps.

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

Node::CalcOps appears to be reachable via RPC calls listunspent, scantxoutset and getaddressinfo.

Code:

miniscript/bitcoin/script/miniscript.h

Lines 499 to 510 in 99fa147

    
           case NodeType::THRESH: { 
        
               uint32_t stat = 0; 
        
               auto sats = Vector(internal::MaxInt<uint32_t>(0)); 
        
               for (const auto& sub : subs) { 
        
                   stat += sub->ops.stat + 1; 
        
                   auto next_sats = Vector(sats[0] + sub->ops.dsat); 
        
                   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)); 
        
                   next_sats.push_back(sats[sats.size() - 1] + sub->ops.sat); 
        
                   sats = std::move(next_sats); 
        
               } 
        
               return {stat, sats[k], sats[0]}; 
        
           }

Note that k is not necessarily within bounds.

Call graph:

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

Policies with too high nesting depth are not rejected: It is possible to create small inputs that cause extreme memory usage (in practice: OOM kill or std::bad_alloc)

Policies with too high nesting depth are not rejected: It is possible to create small inputs that cause extreme memory usage (in reality: OOM) and long running time.

The ./threshold.py 9 example below is 252 bytes and causes a memory consumption of 18.5 GB RAM and a running time of more than ten minutes.

The ./threshold.py 10 example below is 280 bytes will hit OOM on most systems before having a chance to finish.

The following script can be used to construct pathological inputs based on nested thresh:

#!/usr/bin/env python3

import sys


def main():
    if len(sys.argv) != 2:
        print("Usage: {} <number-of-nested-thresholds>".format(sys.argv[0]))
        sys.exit(0)

    N_DEPTH = int(sys.argv[1])
    assert N_DEPTH >= 1

    N_PK = 3
    assert N_PK >= 1

    s = None
    for _ in range(N_DEPTH):
        s = "thresh(1," + ",".join(N_PK * ["pk(H)"]) + ("," + s if s else "") + ")"
    print(s)


if __name__ == "__main__":
    main()

Example runs with varying levels of nesting:

$ ./threshold.py 1 > input
$ wc -c input
28 input
$ cat input
thresh(1,pk(H),pk(H),pk(H))
$ \time ./miniscript < input
X    179.0000000000   105 thresh_m(1,H,H,H) thresh(1,pk(H),pk(H),pk(H))
0.00user 0.00system 0:00.00elapsed 66%CPU (0avgtext+0avgdata 3644maxresident)k
0inputs+0outputs (0major+142minor)pagefaults 0swaps

$ ./threshold.py 2 > input
$ wc -c input
56 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))
$ \time ./miniscript < input
X    263.1250000000   170 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H)))))) thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))
0.01user 0.00system 0:00.01elapsed 83%CPU (0avgtext+0avgdata 3940maxresident)k
0inputs+0outputs (0major+210minor)pagefaults 0swaps

$ ./threshold.py 3 > input
$ wc -c input
84 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H))))
$ \time ./miniscript < input
X    344.3645833333   251 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H))))))))) thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H))))
0.05user 0.00system 0:00.05elapsed 94%CPU (0avgtext+0avgdata 5404maxresident)k
0inputs+0outputs (0major+573minor)pagefaults 0swaps

$ ./threshold.py 4 > input
$ wc -c input
112 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))))
$ \time ./miniscript < input
X    425.4244791667   332 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H)))))))))))) thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))))
0.31user 0.00system 0:00.32elapsed 98%CPU (0avgtext+0avgdata 12712maxresident)k
0inputs+0outputs (0major+2413minor)pagefaults 0swaps

$ ./threshold.py 5 > input
$ wc -c input
140 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H))))))
$ \time ./miniscript < input
X    506.4394531250   413 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H))))))))))))))) thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk
(H),thresh(1,pk(H),pk(H),pk(H))))))
1.38user 0.01system 0:01.41elapsed 99%CPU (0avgtext+0avgdata 47732maxresident)k
0inputs+0outputs (0major+11148minor)pagefaults 0swaps

$ ./threshold.py 6 > input
$ wc -c input
168 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))))))
$ \time ./miniscript < input
X    587.4431966146   494 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H)))))))))))))))))) thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1
,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))))))
7.07user 0.10system 0:07.25elapsed 98%CPU (0avgtext+0avgdata 208636maxresident)k
0inputs+0outputs (0major+51370minor)pagefaults 0swaps

$ ./threshold.py 7 > input
$ wc -c input
196 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H))))))))
$ \time ./miniscript < input
X    668.4441324870   575 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H))))))))))))))))))))) thresh(1,pk(H),pk(H)
,pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H))))))))
33.60user 0.61system 0:34.51elapsed 99%CPU (0avgtext+0avgdata 935792maxresident)k
0inputs+0outputs (0major+233170minor)pagefaults 0swaps

$ ./threshold.py 8 > input
$ wc -c input
224 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))))))))
$ \time ./miniscript < input
X    749.4443664551   656 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H)))
))))))))))))))))))))) thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))))))))
152.81user 3.02system 2:37.25elapsed 99%CPU (0avgtext+0avgdata 4178928maxresident)k
0inputs+0outputs (0major+1043945minor)pagefaults 0swaps

$ ./threshold.py 9 > input
$ wc -c input
252 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H))))))))))
$ \time ./miniscript < input
X    830.4444249471   737 c:or_i(pk(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h(H),or_i(pk_h
(H),or_i(pk_h(H),or_i(pk_h(H),pk_h(H))))))))))))))))))))))))))) thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H))))))))))
703.78user 11.88system 12:02.40elapsed 99%CPU (0avgtext+0avgdata 18487544maxresident)k
0inputs+0outputs (0major+4621129minor)pagefaults 0swaps

$ ./threshold.py 10 > input
$ wc -c input
280 input
$ cat input
thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H),thresh(1,pk(H),pk(H),pk(H)))))))))))
$ \time ./miniscript < input
… will most likely call in the OOM killer or throw std::bad_alloc before finishing …
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
Command terminated by signal 6

FromString accepts multiple wrappers separated by ":"

For example "t:v:c:pk(A)" is valid; only "tvc:pk(A)" should be acceptable.

emscripten miniscript.js errors with fix

OS: Macos

So I was trying to build the miniscript.js using emscripten which didn't work initially and gave an error of TypeError: Module.asm.S is undefined. I landed on this issue which fixed my problem, basically you just need to alter the Makefile to:

miniscript.js: $(HEADERS) $(SOURCES) js_bindings.cpp
    em++ -O3 -g0 -Wall -std=c++11 -fno-rtti -flto -Ibitcoin $(SOURCES) js_bindings.cpp -s WASM=1 -s FILESYSTEM=0 -s ENVIRONMENT=web -s DISABLE_EXCEPTION_CATCHING=0 -s EXPORTED_FUNCTIONS='["_miniscript_compile","_miniscript_analyze","_malloc","_free"]' -s EXTRA_EXPORTED_RUNTIME_METHODS='["cwrap","UTF8ToString"]' -o miniscript.js -s WASM=0 --memory-init-file 0

Note the -s WASM=0 --memory-init-file 0 at the end.

I don't fully understand what this does so I didn't feel comfortable putting it into a pull request but thought it should be reported on but I would gladly turn this into a pull request if you sign off on it so let me know what you think.

Policy with nested or() emits unexpected pk_h.

Perhaps there's a reason that I'm not seeing, but the behavior of or(a,b) differs in an unexpected way from or(a,or(b,c)):

Unnested: both are pk()'s.

or(
   pk(key1),
   pk(key2)
)
->
or_b(
   c:pk(key1),
   sc:pk(key2)
)

Nested: the 2 latter are now pk_h():

or(
   pk(key1),
   or(
      pk(key2),
      pk(key3)))
->
or_d(
   c:pk(key1),
   c:or_i(
      pk_h(key2),
      pk_h(key3)))

Hex string with non-hex data appended to it accepted as valid hex argument to hash160/ripemd160/hash256/sha256

Hex string with non-hex data appended to it accepted as valid hex argument to hash160/ripemd160/hash256/sha256.

Accepted since 40 chars of hex:

$ ./miniscript <<< "hash160(ffffffffffffffffffffffffffffffffffffffff)"
      0 scriptlen=27 maxops=4 type=B safe=no nonmal=yes dissat=yes input=1n output=1 miniscript=hash160(ffffffffffffffffffffffffffffffffffffffff)

Not accepted since 48 chars of hex (we want 40 chars of hex):

$ ./miniscript <<< "hash160(ffffffffffffffffffffffffffffffffffffffffcafebabe)"
Failed to parse as policy or miniscript 'hash160(ffffffffffffffffffffffffffffffffffffffffcafebabe)'

Unexpectedly accepted despite being 48 chars (note the non-hex "z" as the 41:th char):

$ ./miniscript <<< "hash160(ffffffffffffffffffffffffffffffffffffffffzafebabe)"
      0 scriptlen=27 maxops=4 type=B safe=no nonmal=yes dissat=yes input=1n output=1 miniscript=hash160(ffffffffffffffffffffffffffffffffffffffffzafebabe)

Total C++ noob question, but how to compile?

I tried c++ main.cpp -o and make, but it crashes on the include statements.

Assertion failure in ComputeType when processing script OP_0 OP_0 OP_EQUAL

The following assertion failure in ComputeType is hit when passing the script OP_0 OP_0 OP_EQUAL (00 00 87) to miniscript::FromScript.

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

d-wrapper: o=z_X property condition redundant (should be just o) ?

for d: wrapper, in the "correctness requirements" table, the "Requires" column specifies X is Vz so the argument must have z type modifier. In the properties column, it lists o=z_X; n; u; d (o=z<sub>X</sub>), which I read as it has o property if the argument X has the z property. But as it is already specified in "Requires" that z property is mandatory, conditional for o in the "properties" column is unnecessary, and it seems that it should just be o; n; u; d

Link for Rust Implementation

Should this link here:
https://github.com/sipa/miniscript/blob/master/index.html#L114

Be pointing to:
https://github.com/apoelstra/rust-miniscript

Or this:
https://github.com/rust-bitcoin/rust-miniscript

The latter seems more appropriate, since the former is fork and hasn't been updated in ~2 years.

Happy to make a PR. Please advise.

	<tr>
	<td>(<em>X</em> and <em>Y</em>) or <em>Z</em></td>
	<td><code>andor(<em>X</em>,<em>Y</em>,<em>Z</em>)</code></td>
	<td><samp><em>[X]</em> NOTIF <em>[Z]</em> ELSE <em>[Y]</em> ENDIF</samp></td>
	</tr>

	case NodeType::THRESH: {
	uint32_t stat = 0;
	auto sats = Vector(internal::MaxInt<uint32_t>(0));
	for (const auto& sub : subs) {
	stat += sub->ops.stat + 1;
	auto next_sats = Vector(sats[0] + sub->ops.dsat);
	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));
	next_sats.push_back(sats[sats.size() - 1] + sub->ops.sat);
	sats = std::move(next_sats);
	}
	return {stat, sats[k], sats[0]};
	}