Add trait bound to Merkle tree method; fix typing by apoelstra · Pull Request #2864 · rust-bitcoin/rust-bitcoin

apoelstra · 2024-06-13T14:43:29Z

Alternate to #2853. Takes patch 1 from that PR.

coveralls · 2024-06-13T14:51:48Z

Pull Request Test Coverage Report for Build 9501833057

Details

34 of 34 (100.0%) changed or added relevant lines in 3 files are covered.
No unchanged relevant lines lost coverage.
Overall coverage increased (+0.007%) to 83.293%

Totals
Change from base Build 9500447857:	0.007%
Covered Lines:	19523
Relevant Lines:	23439

💛 - Coveralls

tcharding

Thanks for putting this up, I would have never got here because I was stuck on the inline conundrum. I particular like the combine function.

tcharding · 2024-06-13T22:07:44Z

bitcoin/src/merkle_tree/mod.rs

This moves the problem I described (that I thought needed unsafe to solve) onto the user.

Said another way, what is the point of providing this function now, presumably the caller has a vector of Txids and needs to convert them to MerkleNode implementors?

We could take the pub away if it worries you. It is only used within the library as a helper function to implement calculate_root, and it exists to theoretically allow people to implement calculate_root without any allocations.

I doubt it has ever been actually used by anybody else in the history of this library.

BTW the algorithm implemented here is super memory-wasteful and bizarrely combines recursion with an explicit Vec, giving us the worst of both worlds (and spread across 3 functions for some reason). I'll do a followup PR that fixes this since I'm looking at it.

Nah, I'll just do it here. If I'm breaking the API I should go all the way. Added two commits.

coveralls · 2024-06-14T16:04:03Z

Pull Request Test Coverage Report for Build 9518993748

Warning: This coverage report may be inaccurate.

This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.

For more information on this, see Tracking coverage changes with pull request builds.
To avoid this issue with future PRs, see these Recommended CI Configurations.
For a quick fix, rebase this PR at GitHub. Your next report should be accurate.

Details

43 of 43 (100.0%) changed or added relevant lines in 3 files are covered.
No unchanged relevant lines lost coverage.
Overall coverage decreased (-0.005%) to 83.281%

Totals
Change from base Build 9500447857:	-0.005%
Covered Lines:	19497
Relevant Lines:	23411

💛 - Coveralls

tcharding · 2024-06-14T21:19:03Z

Looks good, its non-trivial to review for me though. Perhaps we should have some regression tests before we make the change? Currently only one unit test.

apoelstra · 2024-06-15T00:00:29Z

@tcharding there are like a dozen regression tests in merkle_tree/block.rs, and the "one unit test" is also a regression test.

Try changing the tree algorithm and see how much breaks.

coveralls · 2024-06-15T13:15:39Z

Pull Request Test Coverage Report for Build 9528363460

Details

42 of 42 (100.0%) changed or added relevant lines in 3 files are covered.
No unchanged relevant lines lost coverage.
Overall coverage decreased (-0.006%) to 83.13%

Totals
Change from base Build 9528230836:	-0.006%
Covered Lines:	19519
Relevant Lines:	23480

💛 - Coveralls

coveralls · 2024-06-15T13:17:18Z

Pull Request Test Coverage Report for Build 9528371517

Details

42 of 42 (100.0%) changed or added relevant lines in 3 files are covered.
No unchanged relevant lines lost coverage.
Overall coverage decreased (-0.006%) to 83.13%

Totals
Change from base Build 9528230836:	-0.006%
Covered Lines:	19519
Relevant Lines:	23480

💛 - Coveralls

coveralls · 2024-06-16T15:02:29Z

Pull Request Test Coverage Report for Build 9536877191

Details

42 of 42 (100.0%) changed or added relevant lines in 3 files are covered.
No unchanged relevant lines lost coverage.
Overall coverage decreased (-0.006%) to 83.137%

Totals
Change from base Build 9536654741:	-0.006%
Covered Lines:	19519
Relevant Lines:	23478

💛 - Coveralls

coveralls · 2024-06-16T15:14:33Z

Pull Request Test Coverage Report for Build 9536960269

Details

45 of 45 (100.0%) changed or added relevant lines in 3 files are covered.
No unchanged relevant lines lost coverage.
Overall coverage decreased (-0.01%) to 83.133%

Totals
Change from base Build 9536654741:	-0.01%
Covered Lines:	19513
Relevant Lines:	23472

💛 - Coveralls

tcharding · 2024-06-16T23:43:47Z

My bad, I appreciate you have also probably written this algorithm a dozen times before. I was sick in bed reviewing and had zero confidence in my ability to fully grok the change. I didn't look in block.rs at the time either :(

ACK 66ca2c20519b726e3c5931d6b99eedc3aec60106

tcharding · 2024-06-17T02:29:52Z

bitcoin/src/merkle_tree/mod.rs

Coming back for a post ack review :)

Perhaps:

/// Converts a hash to a leaf node of the tree. fn from_leaf(leaf: Self::Leaf) -> Self; /// Combines two nodes to get a single node. /// /// The final node of the tree is the Merkle root. fn combine(&self, other: &Self) -> Self;

tcharding · 2024-06-17T02:31:00Z

bitcoin/src/merkle_tree/mod.rs

Suggested change

/// Returns `None` iff the iterator was empty.

/// # Returns

///

/// Returns `None` iff the iterator was empty.

Kixunil

ACK 66ca2c20519b726e3c5931d6b99eedc3aec60106

Nice changes overall!

Kixunil · 2024-06-17T09:02:58Z

bitcoin/src/merkle_tree/mod.rs

I find n /= 2 more readable

Kixunil · 2024-06-17T09:03:49Z

bitcoin/src/merkle_tree/mod.rs

n + 2 == 1 is more readable, the compiler knows how to optimize it.

Kixunil · 2024-06-17T09:18:15Z

One more thing: this does not address Taproot. I don't remember what the differences are. Can we unify them?

apoelstra · 2024-06-17T15:02:21Z

I don't remember what the differences are. Can we unify them?

Unfortunately not. The differences in Taproot are:

The use of a tagged hash rather than sha256 (probably not too hard to handle)
Combining hashes in lexicographic order to make an "unordered tree" (can be handled by the new MerkleNode::combine trait function).
Hashing leaves properly rather than just pretending like they're nodes (can be handled by MerkleNode::from_leaf)
Allowing arbitrarily-shaped binary trees rather than just balaced trees.
Treating single branches as leaves rather than doing this dumb doubling-up trick to simulate a balanced tree.

It's the last two points where we have a meaningfully different tree algorithm and I don't think it makes sense to unify them.

Kixunil · 2024-06-17T18:12:14Z

It's the last two points where we have a meaningfully different tree algorithm and I don't think it makes sense to unify them.

I believe you're right then. Might be worth mention in the code.

Currently we are defining the two merkle tree hash types in the `block` module, a better home for them is the `merkle_tree` module. This is an API breaking change because the types were public in the `block` module, however the change should/could be unnoticeable to users if they use the crate level re-export - which is maintained.

These are pretty noisy but it's just a move.

…lculation

These changes are nontrivial. They * Drop the `From` impls from (w)txids to (w)TxMerkleRoots * Introduce a new trait and bound calculate_root on it... * ...in such a way that its return value cannot be inferred without further hints (though in practice this doesn't matter because usually the return value is immediately assigned to something with a known type such as a BlockHeader field)

Drop recursion, reduce memory usage to be logarithmic in size of tree rather than linear, and put it all in one function rather than three. Also make the method an trait method on MerkleNode which makes it a easier on type inference, by writing e.g. TxMerkleNode::calculate_root.

apoelstra · 2024-06-18T16:12:10Z

Rebased and expanded comment.

coveralls · 2024-06-18T16:15:00Z

Pull Request Test Coverage Report for Build 9568518880

Details

46 of 46 (100.0%) changed or added relevant lines in 3 files are covered.
No unchanged relevant lines lost coverage.
Overall coverage decreased (-0.01%) to 83.119%

Totals
Change from base Build 9551233748:	-0.01%
Covered Lines:	19548
Relevant Lines:	23518

💛 - Coveralls

Kixunil

ACK 90b6d67

tcharding

ACK 90b6d67

github-actions bot added the C-bitcoin PRs modifying the bitcoin crate label Jun 13, 2024

apoelstra mentioned this pull request Jun 13, 2024

Return specific hash type when calculating merkle tree #2853

Closed

apoelstra force-pushed the 2024-06--merkle-tree branch from 60dce23 to 4dec788 Compare June 13, 2024 14:48

tcharding reviewed Jun 13, 2024

View reviewed changes

apoelstra mentioned this pull request Jun 15, 2024

hashes: Epic re-write #2770

Closed

apoelstra force-pushed the 2024-06--merkle-tree branch 2 times, most recently from 7384679 to 1835605 Compare June 15, 2024 13:14

apoelstra force-pushed the 2024-06--merkle-tree branch from 1835605 to 4cf9752 Compare June 16, 2024 15:00

tcharding previously approved these changes Jun 16, 2024

View reviewed changes

tcharding reviewed Jun 17, 2024

View reviewed changes

Kixunil previously approved these changes Jun 17, 2024

View reviewed changes

apoelstra added 7 commits June 17, 2024 19:10

api changes after moving the hashes

0435390

These are pretty noisy but it's just a move.

merkle_tree: introduce MerkleNode trait to better-type merkle tree ca…

8d5cb01

…lculation

api changes for "rewrite merkle root calculation"

48ad5e4

merkle_tree: remove some now-redundant code from block.rs

90b6d67

apoelstra dismissed stale reviews from Kixunil and tcharding via 90b6d67 June 18, 2024 16:12

apoelstra force-pushed the 2024-06--merkle-tree branch from 66ca2c2 to 90b6d67 Compare June 18, 2024 16:12

Kixunil approved these changes Jun 18, 2024

View reviewed changes

tcharding approved these changes Jun 19, 2024

View reviewed changes

apoelstra merged commit d063cc1 into rust-bitcoin:master Jun 19, 2024

apoelstra deleted the 2024-06--merkle-tree branch June 19, 2024 14:52

-    /// Returns `None` iff the iterator was empty.
+    /// # Returns
+    ///
+    /// Returns `None` iff the iterator was empty.

Conversation

apoelstra commented Jun 13, 2024

Uh oh!

coveralls commented Jun 13, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Test Coverage Report for Build 9501833057

Details

💛 - Coveralls

Uh oh!

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

coveralls commented Jun 14, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Test Coverage Report for Build 9518993748

Warning: This coverage report may be inaccurate.

Details

💛 - Coveralls

Uh oh!

tcharding commented Jun 14, 2024

Uh oh!

apoelstra commented Jun 15, 2024

Uh oh!

coveralls commented Jun 15, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Test Coverage Report for Build 9528363460

Details

💛 - Coveralls

Uh oh!

coveralls commented Jun 15, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Test Coverage Report for Build 9528371517

Details

💛 - Coveralls

Uh oh!

coveralls commented Jun 16, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Test Coverage Report for Build 9536877191

Details

💛 - Coveralls

Uh oh!

coveralls commented Jun 16, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Test Coverage Report for Build 9536960269

Details

💛 - Coveralls

Uh oh!

tcharding commented Jun 16, 2024

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

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

Kixunil commented Jun 17, 2024

Uh oh!

apoelstra commented Jun 17, 2024

Uh oh!

Kixunil commented Jun 17, 2024

Uh oh!

apoelstra commented Jun 18, 2024

Uh oh!

coveralls commented Jun 18, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Test Coverage Report for Build 9568518880

Details

coveralls commented Jun 13, 2024 •

edited

Loading

coveralls commented Jun 14, 2024 •

edited

Loading

coveralls commented Jun 15, 2024 •

edited

Loading

coveralls commented Jun 15, 2024 •

edited

Loading

coveralls commented Jun 16, 2024 •

edited

Loading

coveralls commented Jun 16, 2024 •

edited

Loading

coveralls commented Jun 18, 2024 •

edited

Loading