Updated Miniscript with timelock and heightlock information #41

sanket1729 · 2020-10-30T13:23:58Z

Added functionality for checking combination of timelocks and height locks.
Currently, I am focusing on trying to work on Miniscript without the compiler, but if required I can update the compiler to fail if given a policy that could contain such a combination.

After going through all the remaining issues in the repo, I will adapt the PR to bitcoin core.
Leaving some review comments for places I was not sure about the C++ idiomatic way to do things.

bitcoin/script/miniscript.h

dgpv · 2020-12-21T08:45:56Z

I've generated 1772 miniscripts with timelock conflicts, hopefully will be useful to test this code. The archive with .dot files is at https://github.com/dgpv/miniscript-alloy-spec-generated-samples/blob/master/8f1e80d95c49d49563b97fb97fd3ed38b55b4672_timelock_conflicts.zip, the code to convert from .dot file to the miniscript string representation is at https://github.com/dgpv/miniscript-alloy-spec/blob/master/tools/parse_miniscript_dot.py

bitcoin/script/miniscript.cpp

bitcoin/script/miniscript.h

main.cpp

bitcoin/script/miniscript.h

compiler.cpp

sanket1729 · 2021-07-23T17:40:05Z

bitcoin/script/miniscript.cpp

+                    // Thresh contains a combination of timelocks if it has threshold > 1 and
+                    // it contains two different children that have different types of timelocks
+                    // Note how if any of the children don't have "k", the parent also does not have "k"
+                    "k"_mst.If(((acc_tl & t) << "k"_mst) && ((k <= 1) ||


This might be a bit tricky to review. Let me know if there is some better expression for this.

sanket1729 · 2021-07-23T18:29:57Z

@dgpv, I looked at the tests but it looks like there is something off about the timelock conflict detection algorithm.

The current suggested algorithm only makes sure that the canonical satisfaction paths don't have any conflicts. So, in the miniscript or_i(after(1), after(500000001)) would not be any conflict because the user should not take both paths together.

On the other hand, and_b(after(1),a:after(500000001)) would be a conflict since there is a satisfaction path that requires both types of timelocks.

sipa · 2021-07-23T18:39:20Z

@sanket1729 Thinking a bit more about this height/timelock conflict... is it actually a property of a miniscript, or of the policy? In other words: are there policies that can be compiled to both non-conflicting and conflicting forms?

sanket1729 · 2021-07-23T18:52:34Z

@sipa This is a property of the policy. There are no policies that can be compiled to both non-conflicting and conflicting forms.

Our transcript from last year.

To summarize, we decided the following w.r.t to timelock conflicts.

- The Miniscripts that contain a possible spend of timelock and height locks are still well-typed valid miniscripts.
- For the policy compiler, we refuse to accept policies that can contain such a spend path
- We don't do any semantic analysis on such Miniscripts because that can result in incorrect results.

There is also safety/hassig s property which only depends on the policy. Our rationale for making it a miniscript property is it should be easy for software to detect such things without relying on the policy part.

sipa · 2021-07-23T19:31:55Z

@sanket1729 Ok, thanks, that makes sense.

sanket1729 · 2021-07-24T14:21:14Z

I've generated 1772 miniscripts with timelock conflicts, hopefully will be useful to test this code. The archive with .dot files is at https://github.com/dgpv/miniscript-alloy-spec-generated-samples/blob/master/8f1e80d95c49d49563b97fb97fd3ed38b55b4672_timelock_conflicts.zip, the code to convert from .dot file to the miniscript string representation is at https://github.com/dgpv/miniscript-alloy-spec/blob/master/tools/parse_miniscript_dot.py

Thanks a lot. I have updated the rust-miniscript and c++ codebase to use those vectors. As mentioned earlier (#41 (comment)), not all of them are conflicts. But the c++ and rust-miniscript versions agree on those vectors.

Because tests in the current master are based on an old version of miniscript, I have added tests in #58 which first updates the tests to the latest miniscript spec, and then adds new tests.

dgpv · 2021-07-25T14:49:37Z

@sanket1729 The conditions I've chosen to generate those cases were apparently too simplistic, and now I even forgot the conditions I used to generate these, so just filtering this data is the easier path :-). You already filtered out the 'not really conflicts' cases, so all is fine I suppose.

darosior

ACK 7bba0e9

sipa

Feel like adding this to the website interface (js wrapper) too?

sipa · 2021-09-22T18:09:29Z

bitcoin/script/miniscript.h

@@ -750,7 +750,10 @@ struct Node {

 public:
    //! Return the size of the script for this expression (faster than ToString().size()).


Unrelated: this should be ToScript().size().

sipa · 2021-09-22T18:10:35Z

bitcoin/script/miniscript.h

@@ -780,7 +783,7 @@ struct Node {
    bool NeedsSignature() const { return GetType() << "s"_mst; }

    //! Do all sanity checks.
-    bool IsSafeTopLevel() const { return GetType() << "Bms"_mst && CheckOpsLimit() && CheckStackSize(); }
+    bool IsSafeTopLevel() const { return GetType() << "Bms"_mst && CheckOpsLimit() && CheckStackSize() && CheckTimeLocksMix(); }


Now that timelock-safeness is just the "k" property, this could be simplified to just changing the required type to be "Bmsk"_mst. If CheckTimeLocksMix is independently interesting, it doesn't matter much.

sipa · 2021-09-22T18:13:17Z

compiler.cpp

    }

    void Add(const CostPair& pair, Node node) {
        auto new_typ = node->GetType();
        double cost = Cost(pair, node);
-        if (!node->CheckOpsLimit()) return;
-        if (node->GetStackSize() > MAX_STANDARD_P2WSH_STACK_ITEMS) return;
+        if (!node->IsSafeTopLevel()) return;


I don't think this is right; it will reject all non-B expressions.

We could have both a IsSafe and IsSafeTopLevel and call the former here?

bool IsSafe() const { return CheckOpsLimit() && CheckStackSize() && CheckTimeLocksMix() && CheckScriptSize(); } bool IsSafeTopLevel() const { return GetType() << "Bms"_mst && IsSafe(); }

I think "ms" should be required for IsSafe, not just IsSafeTopLevel.

sanket1729 · 2021-09-23T16:13:37Z

Feel like adding this to the website interface (js wrapper) too?

Yes, I will add another commit to this PR

The top level miniscript is considered safe if the the miniscript represents the underlying semantics obtained after lifting. In case, there is atleast one possible satisfaction path that could require height-based and time-based satisfactions, we consider that as unsafe and the miniscript properties are no longer guaranteed

sanket1729 · 2021-09-28T21:11:08Z

Rebased and removed all the resource limitations checks for MAX_WITNESS_SCRIPT_SIZE from this PR. Those are being dealt with separate PRs by Darosior.

sipa · 2021-09-28T21:13:50Z

index.html

+The <samp>nSequence</samp> field in a transaction input, or the <samp>nLockTime</samp> field in transaction can be specified either as a time or height but not both.
+Therefore it is not possible to spend scripts that require satisfaction of both, height based timelock and time based timelock of the same type.
+<ul>
+<li><b>"k"</b> No timelock mixing. This expression does not contain a mix of heightlock and timelock of the same type. If the miniscript does not have the "k" property, the miniscript template will not match the user expectation of the corresponding spending policy.</li>


Mention the other types here too, or alternatively, drop them from Props() below?

Dropped from Props() as other properties are just implementation detail to obtain k

nit: shouldn't this be part of the above list with the other properties? ("z", "o", "n", "d", "u")

This can later be detected at policy language itself before running the compiler. But nevertheless this check is still good to have

sanket1729 · 2021-09-28T23:11:42Z

I have a few tests that I can push, but currently those would conflict with #76. I can push those once we resolve my comment in #73

darosior

ACK 1838d3e

Verified especially that the ComputeType diff didn't change since my last review (and therefore i didn't re-check it).

darosior · 2021-09-29T08:30:36Z

index.html

+The <samp>nSequence</samp> field in a transaction input, or the <samp>nLockTime</samp> field in transaction can be specified either as a time or height but not both.
+Therefore it is not possible to spend scripts that require satisfaction of both, height based timelock and time based timelock of the same type.
+<ul>
+<li><b>"k"</b> No timelock mixing. This expression does not contain a mix of heightlock and timelock of the same type. If the miniscript does not have the "k" property, the miniscript template will not match the user expectation of the corresponding spending policy.</li>


nit: shouldn't this be part of the above list with the other properties? ("z", "o", "n", "d", "u")

darosior · 2021-09-29T09:02:10Z

FWIW i have a rebased #75 on top of this so sounds better to go with this PR first (as it's more complex to both review and rebase): https://github.com/darosior/miniscript/tree/rebased_is_sane

sipa · 2021-09-29T15:07:09Z

ACK 1838d3e

253172e compiler: use IsSane in place of ad hoc sanity checks (Antoine Poinsot) e27282e miniscript: only check "s" at top level for IsSane, rename IsSafe -> IsSane (Antoine Poinsot) fa2fa68 miniscript: IsSafe() implies IsValid(), separate IsSafe() and IsSafeTopLevel() (Antoine Poinsot) Pull request description: Based on #72 this separates `IsSafe` and `IsSafeTopLevel` as suggested in #41 (comment) . ACKs for top commit: sipa: ACK 253172e Tree-SHA512: 5f1bbff0e9092e13f1df6a9166dc8738e694cb6b78b07bc50ec0968ecc07a74e8f73405ba4932753c70cb58a3ff9c62de1b7fe8468f4a4c6295541de557c4457

…5b7bf9d0a777578a(July 18th) 2dba8d6 Add new timelock tests (sanket1729) 5adf006 Update to bitcoin master (July 18th 2021) e8f85e0e86e92e583b8984455b7bf9d0a777578a (sanket1729) Pull request description: This builds on top #41. The PR consists also has a second commit that adds tests for timelock mix detection. ACKs for top commit: sipa: ACK 2dba8d6 Tree-SHA512: 9ee1b36d9e5ff30b6a4b0145b196e972169d2b92c0968a4115ccd839bfb791a378f678c824ec9452f846a19e3ae584d4d712f963743bd5ae14a213c28717b5b3

sanket1729 commented Oct 30, 2020

View reviewed changes

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

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

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

sipa reviewed Oct 30, 2020

View reviewed changes

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

sanket1729 force-pushed the timelocks branch 2 times, most recently from 9506668 to 6d81c0a Compare May 17, 2021 06:57

sanket1729 force-pushed the timelocks branch 4 times, most recently from 3ced688 to 5451373 Compare July 22, 2021 21:55

sanket1729 mentioned this pull request Jul 22, 2021

Update miniscript to bitcoin core e8f85e0e86e92e583b8984455b7bf9d0a777578a(July 18th) #58

Merged

sanket1729 force-pushed the timelocks branch 2 times, most recently from 685dba8 to b723e14 Compare July 23, 2021 13:36

darosior reviewed Jul 23, 2021

View reviewed changes

bitcoin/script/miniscript.cpp Outdated Show resolved Hide resolved

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

main.cpp Outdated Show resolved Hide resolved

sanket1729 force-pushed the timelocks branch 3 times, most recently from da5c1f6 to afc46a6 Compare July 23, 2021 16:15

sipa reviewed Jul 23, 2021

View reviewed changes

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

darosior reviewed Jul 23, 2021

View reviewed changes

compiler.cpp Outdated Show resolved Hide resolved

sanket1729 force-pushed the timelocks branch 3 times, most recently from 0cf4ad1 to 8cab80a Compare July 23, 2021 17:43

sanket1729 commented Jul 23, 2021

View reviewed changes

sanket1729 force-pushed the timelocks branch from 8cab80a to 7bba0e9 Compare July 24, 2021 14:10

darosior approved these changes Aug 1, 2021

View reviewed changes

sipa reviewed Sep 22, 2021

View reviewed changes

darosior mentioned this pull request Sep 27, 2021

Miniscript safety #75

Merged

sanket1729 force-pushed the timelocks branch from 7bba0e9 to 8ed9e72 Compare September 28, 2021 20:21

sanket1729 added 2 commits September 28, 2021 13:55

Added TimeLockInfo to miniscript

3058301

sanket1729 force-pushed the timelocks branch from 8ed9e72 to f179cc3 Compare September 28, 2021 21:03

sipa reviewed Sep 28, 2021

View reviewed changes

sanket1729 added 3 commits September 28, 2021 14:21

Update website with timelock info

7061a77

Do not compile policies that contain a timelock mix

9ef1d2c

This can later be detected at policy language itself before running the compiler. But nevertheless this check is still good to have

fix typo in ScriptSize doccomment

1838d3e

sanket1729 force-pushed the timelocks branch 2 times, most recently from 45c38a4 to 1838d3e Compare September 28, 2021 23:08

darosior reviewed Sep 29, 2021

View reviewed changes

sipa merged commit d37485f into sipa:master Sep 29, 2021

sanket1729 mentioned this pull request Jan 9, 2023

conflict_tests_from_alloy in miniscript/ms_tests.rs does not actually test for timelock mixing rust-bitcoin/rust-miniscript#514

Open

		@@ -750,7 +750,10 @@ struct Node {

		public:
		//! Return the size of the script for this expression (faster than ToString().size()).

Updated Miniscript with timelock and heightlock information #41

Updated Miniscript with timelock and heightlock information #41

Uh oh!

Conversation

sanket1729 commented Oct 30, 2020

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

dgpv commented Dec 21, 2020

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sanket1729 commented Jul 23, 2021

Uh oh!

sipa commented Jul 23, 2021

Uh oh!

sanket1729 commented Jul 23, 2021

Uh oh!

sipa commented Jul 23, 2021

Uh oh!

sanket1729 commented Jul 24, 2021

Uh oh!

dgpv commented Jul 25, 2021

Uh oh!

darosior left a comment

Choose a reason for hiding this comment

Uh oh!

sipa left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sanket1729 commented Sep 23, 2021

Uh oh!

sanket1729 commented Sep 28, 2021

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sanket1729 commented Sep 28, 2021

Uh oh!

darosior left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

darosior commented Sep 29, 2021

Uh oh!

sipa commented Sep 29, 2021

Uh oh!

Uh oh!