Fix TapTree hidden branches bug by dr-orlovsky · Pull Request #929 · rust-bitcoin/rust-bitcoin

dr-orlovsky · 2022-04-01T04:50:32Z

Closes #928

shesek · 2022-04-01T04:54:18Z

src/util/psbt/map/output.rs

The comment here was not updated to reflect the change

sanket1729

Did not do a detail review, but left one which we should discuss before we invest more time

sanket1729 · 2022-04-01T05:06:43Z

src/util/psbt/map/output.rs

It is rust convention to return inner as Err when it is consumed. So, the caller at least gets the copy it needs.

I don't remember completely, but I think @Kixunil suggested I do this in his review.

Ah, ok. But it is really confusing when working with an API like that - I was confused myself, as you've seen in the issue

@sanket1729 what about making IncompleteTapTree type to be a wrapper around TaprootBuilder, implemeting std::error::Error?

Reworked that way.

I will let him comment on this.

Invoking @Kixunil: please see above.

FWIW, I like the implemented solution in this PR in case we decide to proceed with this.

Yes, error wrapper containing original data is even more idiomatic Rust. PoisonError is a good example of this.

It could be interesting to do it the way std does - instead of private field have accessor methods, so that the type can be extended. Or add a dummy field to emulate #[non_exhaustive] (and change it to #[non_exhaustive] after MSRV bump). Not sure how likely the change is here (writing this in hurry).

sanket1729

Some MSRV failures. I like this better, left a few comments that should be discussed

sanket1729 · 2022-04-01T15:39:10Z

src/util/taproot.rs

nit:
has_hidden_branches or has_hidden_leaves instead? I am not a big fan of names where humans have to reason about things in order to complete them "has hidden what?", "Oh, must be has_hidden_leaves".

Originally I did it as has_hidden_branches. Than, I had a though, "may be this is leaves?". Than I have found that the only unambiguous guess present in current API is add_hidden, and decided to skip the suffix. No idea how "branch" is different from "node", "part" etc - we have no terminology in place yet in this area.

I'm out of my depth here but if 'parts' is correct in the rustdoc then wouldn't has_hidden_parts be a descriptive name?

"Hidden" can be a script leaf or a tree branch, thus we need some term to describe it. I see only two applicable terms here: hidden_tips and hidden_parts. But then we also have to rename TreeBuilder::add_hidden, and I am not happy with both add_hidden_tip and add_hidden_part. This also brings us to #924 (comment) where TipNode can be used as an enum name for both script leafs and hidden (something).

Had come to conclusion that "hidden something" can always be called a "node". Updated all names accordingly.

sanket1729 · 2022-04-01T15:43:35Z

src/util/taproot.rs

I don't think we should be updating this function here. Instead, we should be using it in psbt TapTree::from_inner() check. Trees can be complete and well-formed even if they contain hidden nodes.

Also thought. But than, is the tree considered "complete" having hidden nodes? May be this method should be named "is_finalizable"?

But than, is the tree considered "complete" having hidden nodes?

I think there are two different things here. Builder is called complete if there is nothing else to add. In that sense using complete makes sense here. I don't mind renaming this to is_finalizable.

TapTree is always complete.

is_finalizable would be ok but this PR uses is_finalized which does not make sense to me

sanket1729 · 2022-04-01T15:44:19Z

src/util/psbt/serialize.rs

nit: Why pub?

Had plans to use it in taproot mod to do more extensive tests

sanket1729 · 2022-04-01T15:47:19Z

src/util/psbt/map/output.rs

I will let him comment on this.

dr-orlovsky · 2022-04-04T15:51:41Z

@sanket1729 addressed all your comments & rebased

sanket1729

c9fa3a9a77c7831ba6cedfaa39bf8a4985af85c7 also does not compile.

I think you can squash or re-order "Prevent TapTree from hidden parts" and "TapTree hidden branches unit test".

sanket1729 · 2022-04-04T19:54:14Z

I like the PR, will ACK after the commits pass tests.

sanket1729 · 2022-04-04T20:48:26Z

If this release is getting delayed anyway, IMO we can do the clean solution with Hidden leaves instead. We don't need to restrict ourselves artificially with trees only containing full leaves.

tcharding · 2022-04-04T21:49:28Z

src/util/taproot.rs

Suggested change

return false;

false

tcharding · 2022-04-04T21:56:40Z

src/util/taproot.rs

I'm out of my depth here but if 'parts' is correct in the rustdoc then wouldn't has_hidden_parts be a descriptive name?

dr-orlovsky · 2022-04-05T12:19:09Z

If this release is getting delayed anyway, IMO we can do the clean solution with Hidden leaves instead. We don't need to restrict ourselves artificially with trees only containing full leaves.

@sanket1729 I did what I think the best solution for now in the latest version of #924 and provided rationale in #924 (comment). Right now we do not have hidden branches to iterate over, so adding that second iterator in this release does not makes a lot of sense. Please let me know if you are ok with this approach.

Also pls let me know do I need to discard your review by fixing single non-compilling commit in the history, or it can go like that. @tcharding I will address your comments iff I will be force-pushing again.

sanket1729 · 2022-04-05T19:47:21Z

@dr-orlovsky , you can force push

sanket1729 · 2022-04-05T20:15:33Z

@dr-orlovsky if you can force push, I will be prompt to review today. I don't want to merge non-compiling commits.

dr-orlovsky · 2022-04-05T20:32:08Z

Force-pushed fully reordering commits, checking each to be compiling & addressing all @sanket1729 and @tcharding comments. Also renamed *_hidden into *_hidden_node, since it is a tree node which is hidden (leaf is also a form of node).

sanket1729

ACK 7771531 .

Reviwed the range diff. Why did you remove the test

 
-    #[test]
-    fn taptree_hidden() {
-        let mut builder = compose_taproot_builder(0x51, &[2, 2, 2]);
-        builder = builder.add_leaf_with_ver(3, Script::from_hex("b9").unwrap(), LeafVersion::from_consensus(0xC2).unwrap()).unwrap();
-        builder = builder.add_hidden(3, sha256::Hash::default()).unwrap();
-        assert!(TapTree::from_inner(builder.clone()).is_err());
-    }
-

dr-orlovsky · 2022-04-05T20:44:10Z

@sanket1729 s**, this happened during re-ordering of the commitments. Added it back - sorry will do it on top.

sanket1729

ACK c036b0d. Reviewed the range diff

tcharding · 2022-04-05T22:30:07Z

Awesome thanks, all looks good to me.

apoelstra · 2022-04-14T16:53:07Z

src/util/psbt/serialize.rs

                .map_err(|_| encode::Error::ParseFailed("Tree not in DFS order"))?;
        }
-        if builder.is_finalized() {
+        if builder.is_finalized() || !builder.has_hidden_nodes() {


In 7771531:

I don't understand the name is_finalized but I'm pretty sure this || is supposed to be a &&.

This is a serious issue.

apoelstra

ACK c036b0d

Let's go ahead and merge this. The || vs && thing we will fix in a followup PR.

I really liked the is_complete naming, but that was changed earlier in b0f3992 Was also suggested by Andrew rust-bitcoin#929 (comment)

I really liked the is_complete naming, but that was changed earlier in b0f3992 Was also suggested by Andrew rust-bitcoin/rust-bitcoin#929 (comment)

dr-orlovsky added code quality Makes code easier to understand and less likely to lead to problems RC fix labels Apr 1, 2022

dr-orlovsky added this to the 0.28.0 milestone Apr 1, 2022

dr-orlovsky requested review from sanket1729 and tcharding April 1, 2022 04:50

shesek reviewed Apr 1, 2022

View reviewed changes

sanket1729 reviewed Apr 1, 2022

View reviewed changes

dr-orlovsky added bug P-high High priority labels Apr 1, 2022

dr-orlovsky changed the title ~~Make TapTree::from_inner return a proper error type~~ Fix TapTree hidden branches bug Apr 1, 2022

dr-orlovsky mentioned this pull request Apr 1, 2022

TapTree roundtrip serialization fails with hidden branches #928

Closed

sanket1729 reviewed Apr 1, 2022

View reviewed changes

sanket1729 previously approved these changes Apr 4, 2022

View reviewed changes

tcharding reviewed Apr 4, 2022

View reviewed changes

dr-orlovsky added 7 commits April 5, 2022 22:16

Track information about hidden leaves in taproot NodeInfo

6add0dd

Rename taproot *_hidden API into *_hidden_nodes

e69701e

TaprootBuilder::has_hidden_nodes method

56adfa4

TapTree serialization roundtrip unit test

e24c6e2

Make TapTree::from_inner return a proper error type

efa800f

Rename TaprootBuilder::is_complete into is_finalized

b0f3992

Prevent TapTree from hidden parts

7771531

dr-orlovsky dismissed sanket1729’s stale review via 7771531 April 5, 2022 20:31

dr-orlovsky requested a review from tcharding April 5, 2022 20:37

dr-orlovsky requested a review from sanket1729 April 5, 2022 20:37

sanket1729 previously approved these changes Apr 5, 2022

View reviewed changes

Unit test for failing TapTree on builder containing hidden nodes.

c036b0d

dr-orlovsky dismissed sanket1729’s stale review via c036b0d April 5, 2022 20:44

dr-orlovsky mentioned this pull request Apr 5, 2022

Release 0.28.0 #944

Merged

sanket1729 approved these changes Apr 5, 2022

View reviewed changes

dr-orlovsky requested a review from Kixunil April 6, 2022 11:53

apoelstra reviewed Apr 14, 2022

View reviewed changes

apoelstra approved these changes Apr 14, 2022

View reviewed changes

apoelstra merged commit 8ca18f7 into rust-bitcoin:master Apr 14, 2022

sanket1729 added a commit to sanket1729/rust-bitcoin that referenced this pull request Jul 29, 2022

Rename is_finalized to is_finalizable

870ad59

I really liked the is_complete naming, but that was changed earlier in b0f3992 Was also suggested by Andrew rust-bitcoin#929 (comment)

Conversation

dr-orlovsky commented Apr 1, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sanket1729 left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

dr-orlovsky Apr 1, 2022 • 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!

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 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!

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!

Choose a reason for hiding this comment

Uh oh!

dr-orlovsky commented Apr 4, 2022

Uh oh!

sanket1729 left a comment

Choose a reason for hiding this comment

Uh oh!

sanket1729 commented Apr 4, 2022

Uh oh!

sanket1729 commented Apr 4, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

dr-orlovsky commented Apr 5, 2022

Uh oh!

sanket1729 commented Apr 5, 2022

Uh oh!

sanket1729 commented Apr 5, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dr-orlovsky commented Apr 5, 2022

Uh oh!

sanket1729 left a comment

Choose a reason for hiding this comment

Uh oh!

dr-orlovsky Apr 1, 2022 •

edited

Loading

sanket1729 commented Apr 5, 2022 •

edited

Loading

sanket1729 left a comment •

edited

Loading