8000 Remove redundant code computing tap hashes by dr-orlovsky · Pull Request #926 · rust-bitcoin/rust-bitcoin · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Remove redundant code computing tap hashes #926

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

Merged
merged 2 commits into from
Apr 1, 2022
Merged

Remove redundant code computing tap hashes #926

Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
1b28375
Abstract tap branch hash computing into a dedicated method
dr-orlovsky Mar 31, 2022
f3ebfd6
Remove repeated tap branch hash computing logic
dr-orlovsky Mar 31, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
39 changes: 21 additions & 18 deletions src/util/taproot.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -131,6 +131,21 @@ impl TapLeafHash {
}
}

impl TapBranchHash {
/// Computes branch hash given two hashes of the nodes underneath it.
pub fn from_node_hashes(a: sha256::Hash, b: sha256::Hash) -> TapBranchHash {
Copy link
Collaborator Author

Choose a reason for hiding this comment

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

Referring to the previous discussion on whether this function should be public: https://github.com/rust-bitcoin/rust-bitcoin/pull/922/files#r838943645

I am using this function downstream in OP_RETURN taproot commitment code.

Copy link
Member

Choose a reason for hiding this comment

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

Yeah, I like having it be public. It seems like a generally useful thing to do.

Copy link
Member

Choose a reason for hiding this comment

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

Should this parameter be TapBranchHash instead?

Copy link
Member

Choose a reason for hiding this comment

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

I see that for leaves it is TapLeafHash and for nodes, it is TapBranchHash. Maybe not worth having it here

Copy link
Collaborator Author

Choose a reason for hiding this comment

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

There are three hash types involved in taproot trees: TapBranchHash, TapLeafHash and sha256::Hash for hidden branches/leaves or for parameters generic over branch/leaves. To solve the abiguity we have the following options

  1. Add type alias pub type TapNodeHash = sha256::Hash and use it in API
  2. Use impl Into<TapNodeHash> in arguments which are generic over specific hash type
  3. Do From<TapBranch|LeafHash> for TapNodeHash convertors.

But even if we decide to do so, this should be a scope of separate (quite large) PR.

Copy link
Member

Choose a reason for hiding this comment

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

Sorry to be nit-picky here. I would like this to be left and right instead of a and b.

let mut eng = TapBranchHash::engine();
if a < b {
eng.input(&a);
eng.input(&b);
} else {
eng.input(&b);
eng.input(&a);
};
TapBranchHash::from_engine(eng)
}
Copy link
Member

Choose a reason for hiding this comment

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

Perhaps:

        let (min, max) = if a < b { (a, b) } else { (b, a) };

        let mut eng = TapBranchHash::engine();

        eng.input(&min);
        eng.input(&max);

        TapBranchHash::from_engine(eng)
    }

Copy link
Member

Choose a reason for hiding this comment

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

I like this, but I won't hold up the PR for it.

}

/// Maximum depth of a taproot tree script spend path.
// https://github.com/bitcoin/bitcoin/blob/e826b22da252e0599c61d21c98ff89f366b3120f/src/script/interpreter.h#L229
pub const TAPROOT_CONTROL_MAX_NODE_COUNT: usize = 128;
Expand Down Expand Up @@ -561,16 +576,9 @@ impl NodeInfo {
b_leaf.merkle_branch.push(a.hash)?; // add hashing partner
all_leaves.push(b_leaf);
}
let mut eng = TapBranchHash::engine();
if a.hash < b.hash {
eng.input(&a.hash);
eng.input(&b.hash);
} else {
eng.input(&b.hash);
eng.input(&a.hash);
};
let hash = TapBranchHash::from_node_hashes(a.hash, b.hash);
Ok(Self {
hash: sha256::Hash::from_engine(eng),
hash: sha256::Hash::from_inner(hash.into_inner()),
Copy link
Member

Choose a reason for hiding this comment

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

Is this a 'normal' thing to do, convert between the various sha256 hash types? Should be be providing conversion functions over in bitcoin_hashes?

Copy link
Member

Choose a reason for hiding this comment

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

We should probably provide a conveience method for "wrapped hashes" to their generic form (and vice-versa), yeah.

Sometimes hash conversions reflect perversions in Bitcoin, and these should appear perversely in our code :) but I don't think this is one of them.

In any case, for purposes of this PR the explicit conversion is fine.

leaves: all_leaves,
})
}
Expand Down Expand Up @@ -775,16 +783,11 @@ impl ControlBlock {
let mut curr_hash = TapBranchHash::from_inner(leaf_hash.into_inner());
// Verify the proof
for elem in self.merkle_branch.as_inner() {
let mut eng = TapBranchHash::engine();
if curr_hash.as_inner() < elem.as_inner() {
eng.input(&curr_hash);
eng.input(elem);
} else {
eng.input(elem);
eng.input(&curr_hash);
}
// Recalculate the curr hash as parent hash
curr_hash = TapBranchHash::from_engine(eng);
curr_hash = TapBranchHash::from_node_hashes(
sha256::Hash::from_inner(curr_hash.into_inner()),
*elem
);
}
// compute the taptweak
let tweak = TapTweakHash::from_key_and_tweak(self.internal_key, Some(curr_hash));
Expand Down
0