Skip to content

Exclusive bounds for thresh: 1 < k < n #242

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
wants to merge 4 commits into from
Closed

Exclusive bounds for thresh: 1 < k < n #242

wants to merge 4 commits into from

Conversation

darosior
Copy link
Contributor

@darosior darosior commented Mar 18, 2021 •
edited
Loading

Currently a draft as i'm unsure how to proceed with the compiler. For k == n, we already translate to and()s, but for k == 1 we stepped by because of the exponential behaviour (see #126).

(Credits to @stepansnigirev for finding the inconsistency)
Fixes #241
Fixes #237
Fixes #126

This was referenced Mar 18, 2021
Open
Open
@darosior
miniscript: be strict on threshold bounds for 'thresh()'
ed91cca 
We were accepting 'thresh()'s with a single sub-policy or a number of
sub-policies equals to the threshold.

This differs with both the C++ implementation and the 'reference' (http://bitcoin.sipa.be/miniscript/)

Reported-by: Stepan Snigirev <snigirev.stepan@gmail.com>
Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
@darosior darosior mentioned this pull request Mar 23, 2021
Closed
@darosior
Copy link
Contributor Author

See #241 (it was actually opened before my PR but i did not see it..)

@darosior
Copy link
Contributor Author

@apoelstra @sanket1729 do you have an opinion on how to proceed to compile thresh(1, a, b, c, ..) after this fix? Should we just bear the compilation time, have a hard limit on the number of subs in this case (iirc that's what the C++ implementation does) ?

@darosior darosior mentioned this pull request Apr 26, 2021
Merged
darosior added 3 commits May 13, 2021 16:29
@darosior
policy/compiler: cleanup and extend the threshold compilation test
59b8a2d 
The logic was quite intricate, this cleans it up as we are going to
reuse it for testing compilation to nested 'or()'s.

In addition, this extends the test to larger multisigs.

Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
@darosior
policy/compiler: compile thresh(1, ..) to nested 'or'
ae88572 
Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
@darosior
policy/compiler: bench thresh(1, ..) compilation
be7d314 
darosior: - is it *that* bad?
cargo bench: - worse.

Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
@darosior
Copy link
Contributor Author

So i went ahead and implemented the Policy compilation part. Added a benchmark for the compilation of nested 'or's too. Wonder if we should add a limit on the number of nested or() possible in a policy (it basically starts taking a very long time at 9 subs and runs forever at 10, so it could be < 10 nested or()s).

@darosior darosior marked this pull request as ready for review May 13, 2021 14:40
sanket1729
sanket1729 reviewed May 19, 2021
View reviewed changes
Copy link
Member

@sanket1729 sanket1729 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@darosior, I should have seen this earlier. Sorry for the delay in response, but I think we decided to allow these scripts for easier way to write miniscripts. It seems natural to write a miniscript with thresh 1 and thresh k = n, so I think we should allow it. This was discussed with Pieter and I was supposed to update the c++ version.

sipa/miniscript#39

@sanket1729
Copy link
Member

Added a benchmark for the compilation of nested 'or's too. Wonder if we should add a limit on the number of nested or() possible in a policy (it basically starts taking a very long time at 9 subs and runs forever at 10, so it could be < 10 nested or()s).

Since we are allowing miniscripts thresh k = 1, we can compile policies with > 6(or some number that is not too long) children into a thresh fragment and use the or fragment for less children

@darosior darosior mentioned this pull request May 20, 2021
Merged
@apoelstra
Copy link
Member

Should we close this PR as we have decided to update the spec to allow these?

@darosior
Copy link
Contributor Author

Yes, i planned to do this as well as maybe opening a PR for the last 3 commits that are not dependent on the spec change. Closing for now :)

@darosior darosior closed this Jun 10, 2021
sipa added a commit to sipa/miniscript that referenced this pull request Jun 15, 2021
@sipa
Merge #55: Inclusive bounds for thresh()'s threshold
1e6edd8 
38b046f index: inclusive bounds for thresh's k (Antoine Poinsot)
51e0cb1 miniscript: allow thresh for k=1 and k=len(subs) (Antoine Poinsot)
e41693e gitignore: ignore the miniscript binary (Antoine Poinsot)

Pull request description:

  As per #39 and discussions on IRC this removes the exclusion of `k = 1` and `k = subs.size()` for `thresh`.

  This is the opposite of rust-bitcoin/rust-miniscript#242 (adapting the Rust implementation to the C++ one) after sanket1729 's feedback.

  Fixes #39

ACKs for top commit:
  sipa:
    utACK 38b046f

Tree-SHA512: 8d76763117c05892ff309b409c70fe928f02b2e8adc54716d0c6363e4993fb1ddc11c858f069694eb7a69ff1f00fe8e2588a3d74021da6cf97a9cc4e36f3a524
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@sanket1729 sanket1729 sanket1729 left review comments

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

thresh(N, n subs) is not optimized to And() if N == 1 Optimize 1-of-N thresholds to or()s thresh checks are different from specs
3 participants
@darosior @sanket1729 @apoelstra