Add a `Threshold` type by tcharding · Pull Request #605 · rust-bitcoin/rust-miniscript

tcharding · 2023-09-28T21:39:23Z

Draft because I think we should use the new Threshold type in sematic::Policy as well before we consider this for merge, last weeks effort at that got me into a mess.

Creates the new type crate::threshold::Threshold that is an (k, n)-threshold and enforces the invariants

k != 0
n != 0
k < n

Use it in policy::concrete::Policy.

tcharding · 2023-09-29T00:55:53Z

Still got a bug, will try again later.

tcharding · 2023-10-03T03:51:13Z

src/policy/concrete.rs

+        if let Ok(thresh) = Threshold::new(k, policies) {
+            ret.push((prob / policy_thresh.n() as f64, Arc::new(Policy::Thresh(thresh))));
+        }


This looks like a change in logic but if you check the single callsite for generate_combination you can see that this will not result in a logic change.

The original code effectively used new_unchecked. If this really always results in a valid threshold (not immediately obvious from the code but I assume we would've noticed if this were wrong :)) I think we should use an expect() rather than an if let Ok(..) without any other branch.

Can do, I might re-visit the call site too and see if there is any way to make it obvious that we can't hit the expect.

apoelstra · 2023-10-03T16:00:13Z

In b86fbcc:

ACK reducing Threshold to Thresh. No other variant of Policy has an abbreviated name and I don't buy the explanation that Terminal (whose variant names match Miniscript string serializations) but I do buy the argument that the variant names should match the string serialization of policy. Which does use thresh.

Then as far as the new Threshold type, I think I'm in favor of this. As written this seems good: we encapsulate some code and enforce that k <= n. Though the proliferance of new_unchecked kinda sucks. One way we could avoid it is by having a constructor that takes k and n - k and internally doing the addition.

You have a comment somewhere about casting the u32 k to a usize. This is fine; it's done all over the codebase because we have lengths that are script-encoded as 32-bit integers. And we depend unconditionally on rust-bitcoin which will refuse to compile on 16-bit architectures. But this suggests the question of "are there absolute maximum values for n and k?". I think the answer is dependent on the script context. So I wonder whether we want the Threshold type to be parameterized by Ctx, or if we want to add a is_valid method which is parameterized by Ctx (more likely; I think we are moving in that direction for all our other uses of Ctx). Or what.

I'm also unsure if we want to use this same type for multisigs, where we have a 20-key limit in pre-Taproot outputs. This would be easier if Rust had type-level integers..which I think it does now but not in our MSRV?

tcharding · 2023-10-03T21:50:08Z

Thanks for the review man.

In b86fbcc:

ACK reducing Threshold to Thresh. No other variant of Policy has an abbreviated name and I don't buy the explanation that Terminal (whose variant names match Miniscript string serializations) but I do buy the argument that the variant names should match the string serialization of policy. Which does use thresh.

Fair, I can agree with that reasoning.

Then as far as the new Threshold type, I think I'm in favor of this. As written this seems good: we encapsulate some code and enforce that k <= n. Though the proliferance of new_unchecked kinda sucks. One way we could avoid it is by having a constructor that takes k and n - k and internally doing the addition.

I'm not quite following the constructor idea since presumably we'd have to do checks on the k and n-k args also. One observation, the new_unchecked is used in two places:

In unit tests
In translating pubkeys (translate_pk and translate_unsatisfiable_pk)

For (2), AFAICT a translation always uses the same n and k so is always valid. Perhaps there is a better way to express this in the function name. For (1) perhaps it would be better to gate a function on #cfg([test]) (same name of different)?

You have a comment somewhere about casting the u32 k to a usize. This is fine; it's done all over the codebase because we have lengths that are script-encoded as 32-bit integers. And we depend unconditionally on rust-bitcoin which will refuse to compile on 16-bit architectures.

Ah of course, I went looking for the same target_pointer_width attribute here, didn't think of the dependency thing.

But this suggests the question of "are there absolute maximum values for n and k?". I think the answer is dependent on the script context. So I wonder whether we want the Threshold type to be parameterized by Ctx, or if we want to add a is_valid method which is parameterized by Ctx (more likely; I think we are moving in that direction for all our other uses of Ctx). Or what.

I'm also unsure if we want to use this same type for multisigs, where we have a 20-key limit in pre-Taproot outputs. This would be easier if Rust had type-level integers..which I think it does now but not in our MSRV?

Perhaps both of these things suggest that the Threshold type needs to maintain more invariants? Not sure if that would require shoe-horning a bunch of unrelated things in there though. I can have a play with a few ideas, like you suggest.

apoelstra · 2023-10-04T13:29:39Z

I'm not quite following the constructor idea since presumably we'd have to do checks on the k and n-k args

My thinking was that the current code only requires that both values are nonnegative, which is guaranteed by the usize type. But yes, if we add more invariants then we would still need a new_unchecked. I didn't realize that the majority of uses were just unit tests, which is fine though.

For (2), AFAICT a translation always uses the same n and k so is always valid

Then we should implement a map function or something similar on Threshold which would handle the conversion without needing to deconstruct and reconstruct the threshold object.

tcharding · 2023-10-04T23:02:35Z

Then we should implement a map function or something similar on Threshold which would handle the conversion without needing to deconstruct and reconstruct the threshold object.

Nice!

tcharding · 2023-10-05T03:47:39Z

Not worth looking at again yet, I've made a mess. Will come back.

The `Policy` variant names should mirror the serialization of themselves, all do except for `Policy::Threshold`. Shorten the variant to `Thresh`.

We have various enums in the codebase that include a `Thresh` variant, we have to explicitly check that invariants are maintained all over the place because these enums are public (eg, `policy::Concrete`). Add a `Threshold<T>` type that abstracts over a threshold and maintains the following invariants: - v.len() > 0 - k > 0 - k <= v.len()

Use the `Threshold` type in `policy::concrete::Policy::Thresh` to help maintain invariants on n and k.

tcharding · 2023-10-09T04:36:24Z

This is cleaned up, leaving as draft until I manage to use Threshold in semantic::Policy::Thresh. Feel free to review or ignore for now. Thanks

tcharding · 2024-03-19T19:59:41Z

Replaced by #660

apoelstra · 2024-03-19T20:14:07Z

Heh, oops, I actually forgot about this PR.

But FWIW with my approach (which heavily uses map and related methods) I basically never needed to do new_unchecked, and in fact I have no such method. I think there is one situation where I had to deconstruct and reconstruct a threshold and then I needed to do unwrap.

I also avoided thinking much about casting the threshold value around.

tcharding · 2024-03-19T20:54:28Z

Yeah the map stuff is great.

tcharding marked this pull request as draft September 28, 2023 21:51

tcharding force-pushed the 09-29-threshold-type branch from 58b6a91 to 46d79a0 Compare September 29, 2023 00:55

tcharding force-pushed the 09-29-threshold-type branch from 46d79a0 to cd170ac Compare October 3, 2023 03:40

tcharding commented Oct 3, 2023

View reviewed changes

tcharding force-pushed the 09-29-threshold-type branch from cd170ac to b86fbcc Compare October 3, 2023 03:53

tcharding force-pushed the 09-29-threshold-type branch 3 times, most recently from 274b736 to c5f7903 Compare October 5, 2023 01:47

tcharding force-pushed the 09-29-threshold-type branch from c5f7903 to d81faa3 Compare October 9, 2023 04:04

tcharding added 2 commits October 9, 2023 15:11

Shorten Threshold variant to Thresh

68d9994

The `Policy` variant names should mirror the serialization of themselves, all do except for `Policy::Threshold`. Shorten the variant to `Thresh`.

tcharding force-pushed the 09-29-threshold-type branch from d81faa3 to 4d2d430 Compare October 9, 2023 04:21

Use Threshold type in concrete::Policy::Thresh

6468604

Use the `Threshold` type in `policy::concrete::Policy::Thresh` to help maintain invariants on n and k.

tcharding force-pushed the 09-29-threshold-type branch from 4d2d430 to 6468604 Compare October 9, 2023 04:33

tcharding closed this Mar 19, 2024

tcharding mentioned this pull request Mar 19, 2024

Introduce Threshold type and use it in SortedMulti as a preview #660

Merged

Conversation

tcharding commented Sep 28, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tcharding commented Sep 29, 2023

Uh oh!

tcharding Oct 3, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

apoelstra Oct 3, 2023

Choose a reason for hiding this comment

Uh oh!

tcharding Oct 3, 2023

Choose a reason for hiding this comment

Uh oh!

apoelstra commented Oct 3, 2023

Uh oh!

tcharding commented Oct 3, 2023

Uh oh!

apoelstra commented Oct 4, 2023

Uh oh!

tcharding commented Oct 4, 2023

Uh oh!

tcharding commented Oct 5, 2023

Uh oh!

tcharding commented Oct 9, 2023

Uh oh!

tcharding commented Mar 19, 2024

Uh oh!

apoelstra commented Mar 19, 2024

Uh oh!

tcharding commented Mar 19, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

tcharding commented Sep 28, 2023 •

edited

Loading

tcharding Oct 3, 2023 •

edited

Loading