TestFramework: Add Python Miniscript Support #17975

jachiang commented at 4:52 PM on January 21, 2020: contributor

This PR introduces basic Miniscript support to the TestFramework.

I believe this would be useful for:

Functional tests with more complex script satisfaction(s)
Functional tests for future wallet RPC calls which handle Miniscript
Entry point for developers looking to integrate Miniscript into external wallet projects (ecdsa, SomberNight, dgpv).

Usage:

Miniscript string constructor.

# key, delay in descriptor below must be represented as hex/int.

example_desc = “or_b(or_i(n:thresh_m(k,key,key),0),a:or_i(0,older(delay)))”

miniscript_node = Node.from_desc(example_desc)

Miniscript CScript constructor.

miniscript_node = Node.from_script(cscript)

Miniscript type and properties.

miniscript_node.p.to_string()

(Dis)satisfaction methods, returns list of tuple-lists.

# Canonical (dis)satisfying witnesses
miniscript_node.sat
miniscript_node.dsat

# Non-canonical (dis)satisfying witnesses
miniscript_node.sat_ncan
miniscript_node.dsat_ncan

Each tuple-list encodes a single, unique satisfying witness:

[
	(SatType, Value),
	(SatType, Value),
	(SatType, Value),
	…
]

The SatType, Value tuples encode the following witness information in correct order. Exception: Time/Delay tuples are not witness elements and will always be positioned at the beginning of the list.

SatType	Value
OLDER	Delay int
AFTER	Time int
SIGNATURE	33B Key/20B HASH160 Digest
KEY_AND_HASH160_PREIMAGE	20B HASH160 Digest
SHA256_PREIMAGE	32B SHA256 Digest
HASH256_PREIMAGE	32B HASH256 Digest
RIPEMD160_PREIMAGE	20B RIPEMD160 Digest
HASH160_PREIMAGE	20B HASH160 Digest
DATA	Bytes

Our example miniscript_node.sat above returns the following 2 satisfying witnesses:

[
	[
		(<SatType.DATA: 8>, b'\x01'), 
		(<SatType.DATA: 8>, b''), 
		(<SatType.SIGNATURE: 2>,  key_bytes), 
		(<SatType.SIGNATURE: 2>,  key_bytes), 
		(<SatType.DATA: 8>, b'\x01')
	], 
	[
		(<SatType.OLDER: 0>, 45), 
		(<SatType.DATA: 8>, b''), 
		(<SatType.DATA: 8>, b'')
	]
]

Tests:

I have included tests in feature_miniscript.py to facilitate potential reviews, but would suggest to omit these if the maintainers decide to merge this PR.

jachiang requested review from instagibbs on Jan 21, 2020

jachiang requested review from jnewbery on Jan 21, 2020

jachiang requested review from sipa on Jan 21, 2020

jachiang requested review from achow101 on Jan 21, 2020

jachiang requested review from jonatack on Jan 21, 2020

instagibbs commented at 5:01 PM on January 21, 2020: member

@sanket1729 @apoelstra may be interested too

jnewbery removed review request from jnewbery on Jan 21, 2020

jnewbery requested review from jnewbery on Jan 21, 2020

DrahtBot added the label Tests on Jan 21, 2020

in test/functional/test_framework/miniscript.py:1301 in 5d31fb46b6 outdated

1296 | +            assert child.p.d and child.p.u
1297 | +            child_is_z_count += 1 if child.p.z else 0
1298 | +            child_is_o_count += 1 if child.p.o else 0
1299 | +            child_is_s_count += 1 if child.p.s else 0
1300 | +            child_is_e += child_is_e and child.p.e
1301 | +            child_is_m += child_is_m and child.p.m

dgpv commented at 6:41 PM on January 21, 2020:

should be = rather than += in two lines above, otherwise child_is_e will be converted to int and will always be >= 1

jachiang commented at 7:41 PM on January 21, 2020:

Excellent catch. Thank you for review.

in test/functional/test_framework/miniscript.py:1697 in 5d31fb46b6 outdated

1553 | +
1554 | +    def _thresh_sat(self, child_sat_set, child_dsat_set):
1555 | +        thresh_sat_ls = []
1556 | +        n = len(self.children)
1557 | +        for i in range(2**n):
1558 | +            if bin(i).co

dgpv commented at 6:54 PM on January 21, 2020:

why not child.t.name.startswith('WRAP_') ?

jachiang commented at 7:38 PM on January 21, 2020:

That's much better. Thx.

michaelfolkson commented at 9:41 AM on January 22, 2020: contributor

This looks great. To get the concept ACK I'm wondering what the arguments against are. I think (I may be mistaken) these are broadly long term motivations and sketched out roadmap-like issues.

Does Bitcoin Core need to be able to recognize Miniscript in the future? Are the future upsides sufficiently material to introduce it? Presumably Miniscript could always be translated to Script externally to Core at little cost?
Is this a stepping stone towards greater support for Miniscript (and possibly a policy language too) in Core? What impact does this have on the use and ongoing development of external libraries like the Rust Miniscript library?
I'm not convinced of the rationale "entry point for developers" as a motivation. Does Miniscript support in the test framework provide any material assistance/assurance to external wallet developers?

I'm excited by the potential of Miniscript and look forward to following future work on this.

in test/functional/feature_miniscript.py:2 in 5d31fb46b6 outdated

   0 | @@ -0,0 +1,433 @@
   1 | +#!/usr/bin/env python3
   2 | +# Copyright (c) 2019 James Chiang

emilengler commented at 12:51 PM on January 22, 2020:

Please change this to "The Bitcoin Core developers" or add your name on line 105 in https://github.com/bitcoin/bitcoin/blob/master/contrib/devtools/copyright_header.py

Otherwise it will get overridden by the copyright-headers script

jachiang commented at 1:10 PM on January 22, 2020:

Thank you for the review and tip, will gladly amend copyright header as you suggested!

practicalswift commented at 1:38 PM on January 22, 2020: contributor

@jachiang

Very nice to see another Miniscript implementation! I love Miniscript! :)

You might want to check your Python implementation for the following issues I've reported in the C++ and Rust implementations:

The bugs are somewhat overlapping across implementations.

As you can see six of the seven bugs in the Rust implementation have been resolved, and hopefully the eight bugs in the C++ implementation will be resolved soon :)

Of the eight bugs in the C++ implementation only one bug affects the initial Bitcoin Core Miniscript PR #16800 ("Basic Miniscript support in output descriptors"). That is a heap out-of-bounds read in Node::CalcOps (called indirectly from miniscript::FromScript) which I reported in #16800 (comment) and suggested a solution for in https://github.com/sipa/miniscript/pull/18 ("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)").

michaelfolkson commented at 1:21 PM on January 31, 2020: contributor

Concept ACK. Moving these high level questions to a RFC (#18040) so as not to hold up review of the details of this PR. #17975 (comment)

in test/functional/test_framework/miniscript.py:943 in 5d31fb46b6 outdated

 938 | +        prop_str += "u" if child_y.p.u else ""
 939 | +        prop_str += "n" if child_x.p.n or (child_x.p.z and child_y.p.n) else ""
 940 | +        prop_str += "z" if child_x.p.z and child_y.p.z else ""
 941 | +        prop_str += "o" if (child_x.p.z and child_y.p.o) or \
 942 | +            (child_x.p.o and child_y.p.z) else ""
 943 | +        prop_str += "f" if child_x.p.f or child_y.p.f else ""

sanket1729 commented at 12:07 AM on February 2, 2020:

I think this should be prop_str += "f" if child_x.p.s or child_y.p.f else "" . Since the left child must have a base typeV, it always has malleability property f. The above statement will make all and_v has property f. There is only one possible non-canonical dissat being [sat(X), dissat(Y)] which gives us self.f = sx or fy.

One valid miniscript counter-example: and_v(vc:pk(A),and_v(v:after(10),sha256(H))) where right branch of first and_v is not an f.

jachiang commented at 8:50 AM on February 2, 2020:

This was a mistake in encoding the property rules, thank you.

sanket1729 changes_requested

sanket1729 commented at 12:11 AM on February 2, 2020: contributor

Great work with the PR :) . I just a partial review, will do a more detailed review over the next couple of days.

in test/functional/test_framework/miniscript.py:962 in 5d31fb46b6 outdated

 957 | +        prop_str += "z" if child_x.p.z and child_y.p.z else ""
 958 | +        prop_str += "o" if (child_x.p.z and child_y.p.o) or \
 959 | +            (child_x.p.o and child_y.p.z) else ""
 960 | +        prop_str += "n" if child_x.p.n or (child_x.p.z and child_y.p.n) else ""
 961 | +        prop_str += "d" if child_x.p.d and child_y.p.d else ""
 962 | +        prop_str += "f" if child_x.p.f and child_y.p.f else ""

sanket1729 commented at 3:47 AM on February 2, 2020:

Should be f=fxfy or sxfx or syfy

in test/functional/test_framework/miniscript.py:982 in 5d31fb46b6 outdated

 977 | +        prop_str = ""
 978 | +        prop_str += "B" if child_x.p.B and child_y.p.B else ""
 979 | +        prop_str += "z" if child_x.p.z and child_y.p.z else ""
 980 | +        prop_str += "o" if child_x.p.o and child_y.p.z else ""
 981 | +        prop_str += "u" if child_y.p.u else ""
 982 | +        prop_str += "d" if child_x.p.d else ""

sanket1729 commented at 4:48 AM on February 2, 2020:

Nit: Always d

in test/functional/test_framework/miniscript.py:983 in 5d31fb46b6 outdated

 978 | +        prop_str += "B" if child_x.p.B and child_y.p.B else ""
 979 | +        prop_str += "z" if child_x.p.z and child_y.p.z else ""
 980 | +        prop_str += "o" if child_x.p.o and child_y.p.z else ""
 981 | +        prop_str += "u" if child_y.p.u else ""
 982 | +        prop_str += "d" if child_x.p.d else ""
 983 | +        prop_str += "f" if child_x.p.f and child_y.p.f else ""

sanket1729 commented at 5:00 AM on February 2, 2020:

Nit: Can never be f. Convert to an assertion?

in test/functional/test_framework/miniscript.py:988 in 5d31fb46b6 outdated

 983 | +        prop_str += "f" if child_x.p.f and child_y.p.f else ""
 984 | +        prop_str += "e" if child_x.p.e and \
 985 | +            (child_x.p.s or child_y.p.f) else ""
 986 | +        prop_str += "m" if child_x.p.m and child_y.p.m and \
 987 | +            child_x.p.e else ""
 988 | +        prop_str += "s" if child_x.p.s and child_y.p.s else ""

sanket1729 commented at 5:23 AM on February 2, 2020:

I think this should be or instead of and?

jachiang commented at 8:40 AM on February 2, 2020:

Yes absolutely! Thanks for the correction!

in test/functional/test_framework/miniscript.py:1005 in 5d31fb46b6 outdated

1000 | +        prop_str = "du"
1001 | +        prop_str += "B" if child_x.p.B and child_z.p.W else ""
1002 | +        prop_str += "z" if child_x.p.z and child_z.p.z else ""
1003 | +        prop_str += "o" if (child_x.p.z and child_z.p.o) or \
1004 | +            (child_x.p.o and child_z.p.z) else ""
1005 | +        prop_str += "d" if child_x.p.d and child_z.p.d else ""

sanket1729 commented at 5:26 AM on February 2, 2020:

unnecessary since it's already added at the start of function

in test/functional/test_framework/miniscript.py:1006 in 5d31fb46b6 outdated

1001 | +        prop_str += "B" if child_x.p.B and child_z.p.W else ""
1002 | +        prop_str += "z" if child_x.p.z and child_z.p.z else ""
1003 | +        prop_str += "o" if (child_x.p.z and child_z.p.o) or \
1004 | +            (child_x.p.o and child_z.p.z) else ""
1005 | +        prop_str += "d" if child_x.p.d and child_z.p.d else ""
1006 | +        prop_str += "f" if child_x.p.f or child_z.p.f else ""

sanket1729 commented at 5:28 AM on February 2, 2020:

This should never happen. Maybe replace it with an assertion?

in test/functional/test_framework/miniscript.py:1064 in 5d31fb46b6 outdated

1059 | +        return self
1060 | +
1061 | +    def construct_or_i(self, child_x, child_z):
1062 | +        prop_str = ""
1063 | +        prop_str += "B" if child_x.p.B and child_z.p.B else ""
1064 | +        prop_str += "K" if child_x.p.K and child_z.p.K else ""

sanket1729 commented at 5:46 AM on February 2, 2020:

Missing both V condition

jachiang commented at 8:42 AM on February 2, 2020:

Ah yes, both V are from revised rules.

in test/functional/test_framework/miniscript.py:1094 in 5d31fb46b6 outdated

1089 | +        prop_str += "z" if child_x.p.z and child_y.p.z and child_z.p.z else ""
1090 | +        prop_str += "o" if (child_x.p.z and child_y.p.o and child_z.p.o) or \
1091 | +            (child_x.p.o and child_y.p.z and child_z.p.z) else ""
1092 | +        prop_str += "u" if child_y.p.u and child_z.p.u else ""
1093 | +        prop_str += "d" if child_x.p.d and child_z.p.d else ""
1094 | +        prop_str += "f" if child_y.p.f and (child_x.p.f or child_z.p.f) else ""

sanket1729 commented at 5:52 AM on February 2, 2020:

f = fz and (sx or fy)

jachiang commented at 8:44 AM on February 2, 2020:

Got it, revised rules again :)

in test/functional/test_framework/miniscript.py:1306 in 5d31fb46b6 outdated

1301 | +            child_is_m += child_is_m and child.p.m
1302 | +            if idx == 0:
1303 | +                is_B = child.p.B
1304 | +            else:
1305 | +                is_B = is_B and child.p.W
1306 | +        prop_str = "Wdu" if not is_B else "Bdu"

sanket1729 commented at 6:31 AM on February 2, 2020:

Should be if "Bdu" if is_B, otherwise ""

sanket1729 changes_requested

sanket1729 commented at 6:55 AM on February 2, 2020: contributor

Changes requested according to revised typing rules in http://bitcoin.sipa.be/miniscript/ Reviewed typing rules. I will review the sat/dsat and script parsing in the following week.

laanwj commented at 1:57 PM on February 5, 2020: member

Concept ACK

jachiang force-pushed on Mar 14, 2020

TestFramework: Add Miniscript property class

Property describes basic Miniscript types and properties. Class includes
string (de)serializers and property consistency checks.

af8ed9a0e8

TestFramework: Add Miniscript expression enum 63197b3017

TestFramework: Add Miniscript Node class

Adds basic miniscript expression class for terminal expressions as
well as descriptor string and cscript (de)serializers. Support of
expression properties is added (Node.p.to_string()).

a62393ad15

TestFramework: Add non-terminal Miniscript exprs

Adds non-terminal miniscript expressions, which inherit properties from
its children.

a85d9c9b74

TestFramework: Add SatType class

SatType enum defines types of witness elements which is required to
produce a valid witness to spend a miniscript expression. SatType is
used in a tuple context (SatType, Hint), where the hint data provides
the required information to generate the satisfying witness element.

08ecc87fb9

TestFramework: Add Node.(d)sat and _lift methods

Node.sat/Node.dsat return a list of tuple-lists which allow the user
to generate all possible (dis)satisfying witnesses.

7a59782a2d

TestFramework: Add non-canonical (d)sat methods

There are non-canonical, yet valid, (dis)satisfying witnesses for
certain miniscript expressions. These are added for completeness.

f8a30b4c76

jachiang force-pushed on Mar 14, 2020

jachiang commented at 1:56 PM on March 14, 2020: contributor

Apologies for the delay updating this PR.

f8a30b4c7 includes rebase and changes suggested by reviewers so far.

in test/functional/test_framework/miniscript.py:1065 in f8a30b4c76

1060 | +
1061 | +    def construct_or_i(self, child_x, child_z):
1062 | +        prop_str = ""
1063 | +        prop_str += "B" if child_x.p.B and child_z.p.B else ""
1064 | +        prop_str += "K" if child_x.p.K and child_z.p.K else ""
1065 | +        prop_str += "K" if child_x.p.V and child_z.p.V else ""

JeremyRubin commented at 5:54 PM on July 5, 2020:

Should be type "V" if both "V".

in test/functional/test_framework/miniscript.py:53 in af8ed9a0e8 outdated

  48 | +        # Can only be of a single type.
  49 | +        num_types = 0
  50 | +        for typ in self.types:
  51 | +            if getattr(self, typ):
  52 | +                num_types += 1
  53 | +        assert num_types == 1

darosior commented at 7:57 PM on August 1, 2021:

nit: since we are returning False on invalid by conflicts below, let's just return False here too?

in test/functional/test_framework/miniscript.py:68 in af8ed9a0e8 outdated

  63 | +            (not self.e or self.d) and \
  64 | +            (not self.V or not self.e) and \
  65 | +            (not self.d or not self.f) and \
  66 | +            (not self.V or self.f) and \
  67 | +            (not self.K or self.s) and \
  68 | +            (not self.z or self.m)

darosior commented at 8:24 PM on August 1, 2021:

W conflicts with n, too.

in test/functional/test_framework/miniscript.py:76 in 63197b3017 outdated

  67 | @@ -66,3 +68,36 @@ def is_valid(self):
  68 |              (not self.V or self.f) and \
  69 |              (not self.K or self.s) and \
  70 |              (not self.z or self.m)
  71 | +
  72 | +
  73 | +class NodeType(Enum):
  74 | +    JUST_0 = 0
  75 | +    JUST_1 = 1
  76 | +    PK = 2

darosior commented at 6:55 AM on August 2, 2021:

It was renamed to PK_K

darosior commented at 2:55 PM on August 2, 2021:

(and pk() is now an alias for c:pk_k())

in test/functional/test_framework/miniscript.py:103 in 63197b3017 outdated

  98 | +    OR_C = 24
  99 | +    OR_D = 25
 100 | +    OR_I = 26
 101 | +    ANDOR = 27
 102 | +    THRESH = 28
 103 | +    THRESH_M = 29

darosior commented at 6:55 AM on August 2, 2021:

Now renamed to MULTI

in test/functional/test_framework/miniscript.py:383 in a62393ad15 outdated

 378 | +        return self
 379 | +
 380 | +    def construct_pk(self, pubkey):
 381 | +        assert isinstance(pubkey, ECPubKey) and pubkey.is_valid
 382 | +        self._pk = [pubkey.get_bytes()]
 383 | +        self._construct(NodeType.PK, Property().from_string("Konudems"),

darosior commented at 3:05 PM on August 2, 2021:

pk is x

in test/functional/test_framework/miniscript.py:392 in a62393ad15 outdated

 387 | +        return self
 388 | +
 389 | +    def construct_pk_h(self, pk_hash_digest):
 390 | +        assert isinstance(pk_hash_digest, bytes) and len(pk_hash_digest) == 20
 391 | +        self._pk_h = pk_hash_digest
 392 | +        self._construct(NodeType.PK_H, Property().from_string("Knudems"),

darosior commented at 3:05 PM on August 2, 2021:

pk_h is x too

in test/functional/test_framework/miniscript.py:23 in af8ed9a0e8 outdated

  18 | +    # "u": Unit property
  19 | +    # "e": Expression property
  20 | +    # "f": Forced property
  21 | +    # "s": Safe property
  22 | +    # "m": Nonmalleable property
  23 | +    # "x": Expensive verify

darosior commented at 3:32 PM on August 2, 2021:

The x property isn't part of Miniscript itself and is an implementation detail of the C++ implem so i wonder if it's not clearer here to just use a boolean member to the Node class instead.

darosior commented at 4:18 PM on August 2, 2021:

You don't even actually use it actually (you match against child_script[-1] to check if you need to append VERIFY), so i'd say it's better to not have it at all (and therefore to ignore my comments regarding missing xs in the following commits).

in test/functional/test_framework/miniscript.py:412 in a62393ad15 outdated

 407 | +        return self
 408 | +
 409 | +    def construct_after(self, time):
 410 | +        assert time >= 1 and time < 2**31
 411 | +        self._time = time
 412 | +        self._construct(NodeType.AFTER, Property().from_string("Bzfm"),

darosior commented at 3:32 PM on August 2, 2021:

after and older are x

in test/functional/test_framework/miniscript.py:768 in a85d9c9b74 outdated

 763 | +        prop_str += "z" if child_x.p.z and child_y.p.z else ""
 764 | +        prop_str += "o" if (child_x.p.z and child_y.p.o) or \
 765 | +            (child_x.p.o and child_y.p.z) else ""
 766 | +        prop_str += "f" if child_x.p.s or child_y.p.f else ""
 767 | +        prop_str += "m" if child_x.p.m and child_y.p.m else ""
 768 | +        prop_str += "s" if child_x.p.s or child_y.p.s else ""

darosior commented at 3:36 PM on August 2, 2021:

and_v should inherit x from y too

in test/functional/test_framework/miniscript.py:777 in a85d9c9b74 outdated

 772 | +                        "and_v("+child_x.desc+","+child_y.desc+")"
 773 | +                        )
 774 | +        return self
 775 | +
 776 | +    def construct_and_b(self, child_x, child_y):
 777 | +        prop_str = "u"

darosior commented at 3:36 PM on August 2, 2021:

and_b is x

in test/functional/test_framework/miniscript.py:801 in a85d9c9b74 outdated

 796 | +        return self
 797 | +
 798 | +    def construct_and_n(self, child_x, child_y):
 799 | +        assert (child_x.p.d and child_x.p.u)
 800 | +        assert (child_x.p.f and child_y.p.f) is False
 801 | +        prop_str = "d"

darosior commented at 3:38 PM on August 2, 2021:

and_n (like and_or) is x too

in test/functional/test_framework/miniscript.py:822 in a85d9c9b74 outdated

 817 | +        return self
 818 | +
 819 | +    def construct_or_b(self, child_x, child_z):
 820 | +        assert (child_x.p.d and child_z.p.d)
 821 | +        assert (child_x.p.f or child_z.p.f) is False
 822 | +        prop_str = "du"

darosior commented at 3:38 PM on August 2, 2021:

or_b is x too

in test/functional/test_framework/miniscript.py:841 in a85d9c9b74 outdated

 836 | +                        )
 837 | +        return self
 838 | +
 839 | +    def construct_or_d(self, child_x, child_z):
 840 | +        assert (child_x.p.d and child_x.p.u)
 841 | +        prop_str = ""

darosior commented at 3:38 PM on August 2, 2021:

or_d is x too

in test/functional/test_framework/miniscript.py:863 in a85d9c9b74 outdated

 858 | +                        )
 859 | +        return self
 860 | +
 861 | +    def construct_or_c(self, child_x, child_z):
 862 | +        assert (child_x.p.d and child_x.p.u)
 863 | +        prop_str = ""

darosior commented at 3:38 PM on August 2, 2021:

or_c is x

in test/functional/test_framework/miniscript.py:879 in a85d9c9b74 outdated

 874 | +                        "or_c("+child_x.desc+","+child_z.desc+")"
 875 | +                        )
 876 | +        return self
 877 | +
 878 | +    def construct_or_i(self, child_x, child_z):
 879 | +        prop_str = ""

darosior commented at 3:39 PM on August 2, 2021:

or_i is x

in test/functional/test_framework/miniscript.py:902 in a85d9c9b74 outdated

 897 | +                        )
 898 | +        return self
 899 | +
 900 | +    def construct_andor(self, child_x, child_y, child_z):
 901 | +        assert (child_x.p.d and child_x.p.u)
 902 | +        prop_str = ""

darosior commented at 3:39 PM on August 2, 2021:

and_or is x

in test/functional/test_framework/miniscript.py:927 in a85d9c9b74 outdated

 922 | +                        + child_z.desc+")"
 923 | +                        )
 924 | +        return self
 925 | +
 926 | +    def construct_a(self, child_x):
 927 | +        prop_str = ""

darosior commented at 3:52 PM on August 2, 2021:

a: is x

in test/functional/test_framework/miniscript.py:952 in a85d9c9b74 outdated

 947 | +        prop_str += "d" if child_x.p.d else ""
 948 | +        prop_str += "f" if child_x.p.f else ""
 949 | +        prop_str += "e" if child_x.p.e else ""
 950 | +        prop_str += "m" if child_x.p.m else ""
 951 | +        prop_str += "s" if child_x.p.s else ""
 952 | +        tag = "s" if child_x.t.name.startswith('WRAP_') else "s:"

darosior commented at 3:53 PM on August 2, 2021:

Should inherit x too

in test/functional/test_framework/miniscript.py:976 in a85d9c9b74 outdated

 971 | +                        child_x._script+[OP_CHECKSIG], tag+child_x.desc
 972 | +                        )
 973 | +        return self
 974 | +
 975 | +    def construct_t(self, child_x):
 976 | +        prop_str = "uf"

darosior commented at 3:55 PM on August 2, 2021:

I think t: is x since it's and_v(X, 1) and 1 is x.

in test/functional/test_framework/miniscript.py:1008 in a85d9c9b74 outdated

1003 | +                        )
1004 | +        return self
1005 | +
1006 | +    def construct_v(self, child_x):
1007 | +        assert child_x.p.B
1008 | +        prop_str = "V"

darosior commented at 3:55 PM on August 2, 2021:

d: and v: are x

in test/functional/test_framework/miniscript.py:1032 in a85d9c9b74 outdated

1027 | +                        script, tag+child_x.desc)
1028 | +        return self
1029 | +
1030 | +    def construct_j(self, child_x):
1031 | +        assert (child_x.p.n)
1032 | +        prop_str = "nd"

darosior commented at 3:55 PM on August 2, 2021:

j: is x

in test/functional/test_framework/miniscript.py:1047 in a85d9c9b74 outdated

1042 | +                        [child_x],
1043 | +                        script, tag+child_x.desc)
1044 | +        return self
1045 | +
1046 | +    def construct_n(self, child_x):
1047 | +        prop_str = "u"

darosior commented at 3:56 PM on August 2, 2021:

n is x too

in test/functional/test_framework/miniscript.py:1079 in a85d9c9b74 outdated

1074 | +                        [child_x],
1075 | +                        script, tag+child_x.desc)
1076 | +        return self
1077 | +
1078 | +    def construct_u(self, child_x):
1079 | +        prop_str = "d"

darosior commented at 3:57 PM on August 2, 2021:

l: and u: should be x since or_i() is

in test/functional/test_framework/miniscript.py:45 in af8ed9a0e8 outdated

  40 | +        """Generate string representation of property"""
  41 | +        property_str = ""
  42 | +        for char in self.types+self.props:
  43 | +            if getattr(self, char):
  44 | +                property_str += char
  45 | +        return property_str

darosior commented at 4:25 PM on August 2, 2021:

That's super nit but i find it nicer to have an optional argument to the constructor instead of from_string() and use __repr__ instead of to_string()

in test/functional/test_framework/miniscript.py:142 in a62393ad15 outdated

 137 | +            return Node().construct_just_0()
 138 | +
 139 | +        if tag == '1':
 140 | +            return Node().construct_just_1()
 141 | +
 142 | +        if tag == 'pk':

darosior commented at 4:33 PM on August 2, 2021:

In addition to pk being renamed to pk_k, pk is now an alias for c:pk_k (so we need to keep matching this tag)

in test/functional/test_framework/miniscript.py:175 in a62393ad15 outdated

 170 | +                key_n.append(key_obj)
 171 | +            return Node().construct_thresh_m(k, key_n)
 172 | +
 173 | +        if tag == 'thresh':
 174 | +            k = int(child_exprs.pop(0))
 175 | +            return Node().construct_thresh(

darosior commented at 4:36 PM on August 2, 2021:

This function doesn't exist as of this commit.

in test/functional/test_framework/miniscript.py:1095 in a85d9c9b74 outdated

1090 | +                        script, tag+child_x.desc)
1091 | +        return self
1092 | +
1093 | +    def construct_thresh(self, k, children_n):
1094 | +        n = len(children_n)
1095 | +        assert n > k > 1

darosior commented at 4:37 PM on August 2, 2021:

thresh now supports k == 1 or k == n.

in test/functional/test_framework/miniscript.py:325 in a62393ad15 outdated

 320 | +        idx = expr_list_len - 1
 321 | +        while idx >= 0:
 322 | +
 323 | +            # Match against thresh_m.
 324 | +            # Termainal expression, but k and n values can be Nodes (JUST_0/1)
 325 | +            if expr_list_len-idx >= 5 and \

darosior commented at 7:53 AM on August 3, 2021:

Why 5? It wouldn't match 1 <pk> 1 CMS?

in test/functional/test_framework/miniscript.py:336 in a62393ad15 outdated

 331 | +                    expr_list[idx].t == NodeType.JUST_1
 332 | +                    )):
 333 | +                k = Node._coerce_to_int(expr_list[idx])
 334 | +                # Permissible values for n:
 335 | +                # len(expr)-3 >= n >= 1
 336 | +                for n in range(k, expr_list_len-2):

darosior commented at 8:06 AM on August 3, 2021:

Why k? I think you rather want to iterate from idx to expr_list_len-2 here?

in test/functional/test_framework/miniscript.py:756 in a85d9c9b74 outdated

 751 | @@ -476,6 +752,392 @@ def construct_thresh_m(self, k, keys_n):
 752 |                          )
 753 |          return self
 754 |  
 755 | +
 756 | +    def construct_and_v(self, child_x, child_y):

darosior commented at 2:15 PM on August 3, 2021:

This should check that child_x is V and y is B, K or V

in test/functional/test_framework/miniscript.py:975 in a85d9c9b74 outdated

 970 | +                        [child_x],
 971 | +                        child_x._script+[OP_CHECKSIG], tag+child_x.desc
 972 | +                        )
 973 | +        return self
 974 | +
 975 | +    def construct_t(self, child_x):

darosior commented at 8:28 AM on August 4, 2021:

This needs to check that child_x is V

in test/functional/test_framework/miniscript.py:148 in a62393ad15 outdated

 143 | +            key_b = bytes.fromhex(child_exprs[0])
 144 | +            key_obj = ECPubKey()
 145 | +            key_obj.set(key_b)
 146 | +            return Node().construct_pk(key_obj)
 147 | +
 148 | +        if tag == 'pk_h':

darosior commented at 10:38 AM on August 4, 2021:

Similarly as for pk(), pkh() is now an alias for c:pk_h().

in test/functional/test_framework/miniscript.py:400 in a62393ad15 outdated

 395 | +                        'pk_h('+pk_hash_digest.hex()+')'
 396 | +                        )
 397 | +        return self
 398 | +
 399 | +    def construct_older(self, delay):
 400 | +        assert delay >= 1

darosior commented at 11:11 AM on August 4, 2021:

This should also check the other boundary imo:

assert delay > 0 and delay < 2**31

in test/functional/test_framework/miniscript.py:900 in a85d9c9b74 outdated

 895 | +                        OP_ENDIF],
 896 | +                        "or_i("+child_x.desc+","+child_z.desc+")"
 897 | +                        )
 898 | +        return self
 899 | +
 900 | +    def construct_andor(self, child_x, child_y, child_z):

darosior commented at 11:19 AM on August 4, 2021:

This should check Bdu for x and either B, K or V for both y and z.

        # X is Bdu; Y and Z are both B, K, or V
        assert all([getattr(child_x.p, pt) for pt in "Bdu"])
        for child in child_y, child_z:
            assert any([getattr(child.p, t) for t in "BKV"])

in test/functional/test_framework/miniscript.py:776 in a85d9c9b74 outdated

 771 | +                        child_x._script+child_y._script,
 772 | +                        "and_v("+child_x.desc+","+child_y.desc+")"
 773 | +                        )
 774 | +        return self
 775 | +
 776 | +    def construct_and_b(self, child_x, child_y):

darosior commented at 11:23 AM on August 4, 2021:

x must be B and y must be W..

in test/functional/test_framework/miniscript.py:819 in a85d9c9b74 outdated

 814 | +                            OP_ENDIF],
 815 | +                        "and_n("+child_x.desc+","+child_y.desc+")"
 816 | +                        )
 817 | +        return self
 818 | +
 819 | +    def construct_or_b(self, child_x, child_z):

darosior commented at 11:29 AM on August 4, 2021:

or_b(X,Z) | X is Bd; Z is Wd

in test/functional/test_framework/miniscript.py:839 in a85d9c9b74 outdated

 834 | +                        child_x._script+child_z._script+[OP_BOOLOR],
 835 | +                        "or_b("+child_x.desc+","+child_z.desc+")"
 836 | +                        )
 837 | +        return self
 838 | +
 839 | +    def construct_or_d(self, child_x, child_z):

darosior commented at 11:29 AM on August 4, 2021:

or_d(X,Z) | X is Bdu; Z is B

in test/functional/test_framework/miniscript.py:878 in a85d9c9b74 outdated

 873 | +                        child_x._script+[OP_NOTIF]+child_z._script+[OP_ENDIF],
 874 | +                        "or_c("+child_x.desc+","+child_z.desc+")"
 875 | +                        )
 876 | +        return self
 877 | +
 878 | +    def construct_or_i(self, child_x, child_z):

darosior commented at 11:30 AM on August 4, 2021:

or_i(X,Z) | both are B, K, or V

in test/functional/test_framework/miniscript.py:390 in a62393ad15 outdated

 385 | +                        [pubkey.get_bytes()], 'pk('+self._pk[0].hex()+')'
 386 | +                        )
 387 | +        return self
 388 | +
 389 | +    def construct_pk_h(self, pk_hash_digest):
 390 | +        assert isinstance(pk_hash_digest, bytes) and len(pk_hash_digest) == 20

darosior commented at 3:08 PM on August 4, 2021:

pk_h is defined as taking a key, not a key hash. Different implementors have different opinions on this but we need to at least be able to parse pk_h() nodes with keys.

in test/functional/test_framework/miniscript.py:495 in a62393ad15 outdated

 490 | +    @staticmethod
 491 | +    def _coerce_to_int(expr):
 492 | +        # Coerce expression to int when iterating through CScript expressions
 493 | +        # after terminal expressions have been parsed.
 494 | +        if isinstance(expr, bytes):
 495 | +            op_int = int.from_bytes(expr, byteorder="big")

darosior commented at 11:05 AM on August 5, 2021:

Script Numbers are little endian. Also, you don't check if the sign bit is set. Consider something like so (what i'm using for python-miniscript):

class ScriptNumError(ValueError):
    def __init__(self, message):
        self.message = message


def read_script_number(data):
    """Read a Script number from {data} bytes"""
    size = len(data)
    if size > 4:
        raise ScriptNumError("Too large push")

    if size == 0:
        return 0

    # We always check for minimal encoding
    if (data[size - 1] & 0x7f) == 0:
        if size == 1 or (data[size - 2] & 0x80) == 0:
            raise ScriptNumError("Non minimal encoding")

    res = int.from_bytes(data, byteorder="little")

    # Remove the sign bit if set, and negate the result
    if data[size - 1] & 0x80:
        return -(res & ~(0x80 << (size - 1)))
    return res

in test/functional/test_framework/miniscript.py:1046 in a85d9c9b74 outdated

1041 | +        self._construct(NodeType.WRAP_J, Property().from_string(prop_str),
1042 | +                        [child_x],
1043 | +                        script, tag+child_x.desc)
1044 | +        return self
1045 | +
1046 | +    def construct_n(self, child_x):

darosior commented at 7:30 AM on August 6, 2021:

X must be B

in test/functional/test_framework/miniscript.py:862 in a85d9c9b74 outdated

 857 | +                        "or_d("+child_x.desc+","+child_z.desc+")"
 858 | +                        )
 859 | +        return self
 860 | +
 861 | +    def construct_or_c(self, child_x, child_z):
 862 | +        assert (child_x.p.d and child_x.p.u)

darosior commented at 8:45 AM on August 6, 2021:

X is Bdu; Z is V

in test/functional/test_framework/miniscript.py:991 in a85d9c9b74 outdated

 986 | +                        child_x._script+[1], tag+child_x.desc
 987 | +                        )
 988 | +        return self
 989 | +
 990 | +    def construct_d(self, child_x):
 991 | +        assert (child_x.p.z)

darosior commented at 8:46 AM on August 6, 2021:

X is Vz

in test/functional/test_framework/miniscript.py:1031 in a85d9c9b74 outdated

1026 | +                        [child_x],
1027 | +                        script, tag+child_x.desc)
1028 | +        return self
1029 | +
1030 | +    def construct_j(self, child_x):
1031 | +        assert (child_x.p.n)

darosior commented at 9:01 AM on August 6, 2021:

X is Bn

in test/functional/test_framework/miniscript.py:1063 in a85d9c9b74 outdated

1058 | +        self._construct(NodeType.WRAP_N, Property().from_string(prop_str),
1059 | +                        [child_x],
1060 | +                        child_x._script+[OP_0NOTEQUAL], tag+child_x.desc)
1061 | +        return self
1062 | +
1063 | +    def construct_l(self, child_x):

darosior commented at 9:04 AM on August 6, 2021:

X must be B, K or V

in test/functional/test_framework/miniscript.py:800 in a85d9c9b74 outdated

 795 | +                        )
 796 | +        return self
 797 | +
 798 | +    def construct_and_n(self, child_x, child_y):
 799 | +        assert (child_x.p.d and child_x.p.u)
 800 | +        assert (child_x.p.f and child_y.p.f) is False

darosior commented at 9:16 AM on August 6, 2021:

X is Bdu; Y and Z are both B, K, or V

darosior commented at 2:59 PM on August 6, 2021: member

Concept ACK. Didn't review tests nor satisfaction yet. Will do post rebase.

As mentioned elsewhere, i'm working on a python-miniscript package started from your branch. All my comments about updates and corrections can be found as commits there. I also included more test cases and changed the structure + nits for my Python OCD, of course feel free to take anything from there.

Hopefully Github will keep my comments ordered by commits, but the main points are:

You are missing a lot of child property checks when constructing nodes.
I think you should get rid of the x property
Miniscript has been updated, pk is now pk_k and pk is an alias to c:pk_k, pkh is now an alias to c:pk_h, and thresh_m was renamed to multi. Some new properties were also added for timelocks conflicts, but they are not yet merged in both implementations so i didn't comment on it.

JeremyRubin commented at 3:51 PM on August 6, 2021: contributor

Another option here which might not be too bad in the scheme of things would be to check in a WASM blob that is gitian built of e.g. rust miniscript, and then call it using a wasm runtime https://github.com/wasmerio/wasmer-python

the main benefit being we don't have to check in yet another implementation of miniscript to maintain as miniscript evolves, we can use the rust or c++ one today, and when the C++ becomes merged & available as an RPC we can drop it.

jachiang commented at 1:51 PM on August 7, 2021: contributor

the main benefit being we don't have to check in yet another implementation of miniscript to maintain as miniscript evolves, we can use the rust or c++ one today, and when the C++ becomes merged & available as an RPC we can drop it.

In the absence of a formal, (mechanizable) specification of Miniscript (MS), separate implementations have higher chances of finding bugs or problems than a single, canonical one. I think this should be a goal of the test-framework. Having said that, I believe the biggest challenge here is the lack of a formal specification of MS and by extension, Script itself, without which, the correctness of the MS type-system is impossible to verify. One must assume the MS authors are working on this.

Sjors commented at 7:35 AM on December 8, 2021: member

In the absence of a formal, (mechanizable) specification of Miniscript (MS), separate implementations have higher chances of finding bugs or problems than a single, canonical one. I think this should be a goal of the test-framework.

Agreed. Concept ACK.

michaelfolkson commented at 11:23 AM on May 25, 2022: contributor

I'm assuming this PR could be closed then @darosior? Direct interested parties for Python Miniscript/Miniscript support in test framework to https://github.com/darosior/python-bip380? When that's in a ready state a new PR will be opened in this repo?

darosior commented at 12:54 PM on May 25, 2022: member

@michaelfolkson it's not my PR to close. :sweat_smile:

When that's in a ready state a new PR will be opened in this repo?

I think having multiple implementations of Miniscript is good, but having multiple ones as part of this repo would only have marginal benefits, if at all.

michaelfolkson commented at 1:02 PM on May 25, 2022: contributor

@michaelfolkson it's not my PR to close

Ok up to @jachiang then. Your repo is building on his work and he should be credited when a new PR is opened (which I'm sure you would anyway)

Sjors commented at 1:33 PM on July 16, 2022: member

@michaelfolkson it's not my PR to close. 😅

When that's in a ready state a new PR will be opened in this repo?

I think having multiple implementations of Miniscript is good, but having multiple ones as part of this repo would only have marginal benefits, if at all.

A good set of test vectors is one way to compare implementations. Lacking that, it's nice if we can generate a few thousand miniscripts in Python and compare them with what the C++ code does.

Now that #24148 has landed, it should be more straight forward to rebase this PR and do the comparison by e.g. calling deriveaddresses on various wsh(some_miniscript).

darosior commented at 8:18 PM on July 16, 2022: member

We did have those, but for some reason we dropped them in the C++ test framework. We can probably add those back. Dmitri generated thousands of Miniscripts (for testing timelock mixes initially) we tested rust-miniscript and the C++ implem against.

If you want an up to dare Python implem i have one at https://github.com/darosior/python-bip380. But again i'm not convinced we should maintain it as part of this repo. -------- Original Message -------- On Jul 16, 2022, 3:33 PM, Sjors Provoost wrote:

@.***(https://github.com/michaelfolkson) it's not my PR to close. 😅

When that's in a ready state a new PR will be opened in this repo?

I think having multiple implementations of Miniscript is good, but having multiple ones as part of this repo would only have marginal benefits, if at all.

A good set of test vectors is one way to compare implementations. Lacking that, it's nice if we can generate a few thousand miniscripts in Python and compare them with what the C++ code does.

Now that #24148 has landed, it should be more straight forward to rebase this PR and do the comparison by e.g. calling deriveaddresses on various wsh(some_miniscript).

— Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you were mentioned.Message ID: @.***>

achow101 commented at 6:05 PM on October 12, 2022: member

Closing this as it has not had any activity in a while. If you are interested in continuing work on this, please leave a comment so that it can be reopened.

achow101 closed this on Oct 12, 2022

bitcoin locked this on Oct 12, 2023