8000 Add function to calculate merkle root from a merkle path by Fi3 · Pull Request #1321 · rust-bitcoin/rust-bitcoin · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Add function to calculate merkle root from a merkle path #1321

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

Closed
wants to merge 1 commit into from
Closed

Add function to calculate merkle root from a merkle path #1321

Changes from all commits
Commits
Show all changes
1 commit
Select commit
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
120 changes: 115 additions & 5 deletions bitcoin/src/util/hash.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -14,8 +14,8 @@ use crate::prelude::*;
use crate::io;
use core::cmp::min;

use crate::hashes::Hash;
use crate::consensus::encode::Encodable;
use crate::hashes::Hash;

/// Calculates 8000 the merkle root of a list of *hashes*, inline (in place) in `hashes`.
///
Expand All @@ -28,7 +28,7 @@ use crate::consensus::encode::Encodable;
pub fn bitcoin_merkle_root_inline<T>(hashes: &mut [T]) -> Option<T>
where
T: Hash + Encodable,
<T as Hash>::Engine: io::Write,
<T as Hash>::Engine: io::Write,
{
match hashes.len() {
0 => None,
Expand All @@ -39,6 +39,44 @@ where

/// Calculates the merkle root of an iterator of *hashes*.
///
/// This fcuntion calculate the root from a merkle path when we need to derive the root from the
Copy link
Collaborator

Choose a reason for hiding this comment

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

typo: fcuntion, here and some lines below

Copy link
Collaborator

Choose a reason for hiding this comment

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

Also "calculates" is missing "s" at the end. There should be a comma or dot and a new sentence before "when". Also the commit message has a typo - "merle"

10000

/// txs list [bitcoin_merkle_root] should be used.
///
/// # Returns
/// - `None` if `hashes` is empty. The merkle root of an empty tree of hashes is undefined.
/// - `Some(hash)` if `hashes` contains one element. A single hash is by definition the merkle root.
/// - `Some(merkle_root)` if length of `hashes` is greater than one.
pub fn bitcoin_merkle_root_from_path<T, I>(mut hashes: I) -> Option<T>
where
T: Hash + Encodable,
<T as Hash>::Engine: io::Write,
Copy link
Collaborator

Choose a reason for hiding this comment

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

Is there any use of non-sha256 function? If not I'd just hard-code SHA256.

Copy link
Author

Choose a reason for hiding this comment

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

Do we need arbitrary function or do we want just sha256?

Copy link
Collaborator

Choose a reason for hiding this comment

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

Both transaction merkle tree and taproot use SHA256. We don't have other merkle trees in bitcoin.

Copy link
Member

Choose a reason for hiding this comment

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

Taproot tree uses a single tagged sha256. Transaction merkle tree uses double-sha256. So these are actually different hashes. I'm not sure about the segwit witness merkle tree.

Copy link
Collaborator

Choose a reason for hiding this comment

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

Ah, good point. OK, let's have them generic.

I: Iterator<Item = T>,
{
let first = hashes.next()?;
let second = match hashes.next() {
Some(second) => second,
None => return Some(first),
};

10000 let mut encoder = T::engine();
let mut root = first;
Copy link
Collaborator

Choose a reason for hiding this comment

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

It'd be nicer to write let mut root = T::from_engine(encoder); below and remove this line.

Copy link
Author

Choose a reason for hiding this comment

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

👍

root.consensus_encode(&mut encoder).expect("in-memory writers don't error");
second.consensus_encode(&mut encoder).expect("in-memory writers don't error");
Copy link
Collaborator

Choose a reason for hiding this comment

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

You can avoid unwraps by writing encoder.input(root.as_inner());

Copy link
Author

Choose a reason for hiding this comment

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

👍

Copy link
Author

Choose a reason for hiding this comment

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

Any way to convert Inner into a byte array?

Copy link
Collaborator

Choose a reason for hiding this comment

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

Just dereference it? Or do you mean something else?

Copy link
Author

Choose a reason for hiding this comment

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

In order to do that I need to restrict Hash to a type with a Inner=[u8;32] This limit the generality of this function, not seem to be an issue to me. Btw I see that the others function in the file do not do it so I want to double check it with you.

Copy link
Collaborator

Choose a reason for hiding this comment

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

Ah, I see now. If we want to restrict it to SHA256 at least temporarily we can do that. Or we could add as_slice() method to Hash trait. I'd normally suggest Inner: AsRef<[u8]> but that's not available for SHA512 in our MSRV.

Copy link
Member
@apoelstra apoelstra Oct 19, 2022 •
edited
Loading

Choose a reason for hiding this comment

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

This sounds like a reason for us to at least put back Index<range::All> on all our hash functions, even if we don't put back all the indexing traits. It's frustrating that there's no way to generically get bytestrings from them.

Copy link
Collaborator

Choose a reason for hiding this comment

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

Index feels like a hack TBH. If we're breaking APIs by removing indexing we may as well move the relevant parts to a proper method(s).

root = T::from_engine(encoder);
for hash in hashes {
let mut encoder = T::engine();
root.consensus_encode(&mut encoder).expect("in-memory writers don't error");
hash.consensus_encode(&mut encoder).expect("in-memory writers don't error");
Copy link
Collaborator

Choose a reason for hiding this comment

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

If I'm not mistaken this can only compute the merkle root for leftmost branch of the tree because root always goes first. I'd expect here to be some condition selecting the order of hashing.

Copy link
9E12 Author

Choose a reason for hiding this comment

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

OK a bool is enough or you prefer an enum?

Copy link
Collaborator

Choose a reason for hiding this comment

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

Definitely an enum here but naming such that it'll be obvious to the readers is hard.

Copy link
Member

Choose a reason for hiding this comment

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

I suggest using

enum MerkleNode<H: Hash> {
    LChild(H),
    RChild(H),
}

and taking an array of these. I'm not sure how leftness/rightness is normally encoded (in stratum every node is implicitly a left child since we only ever prove the coinbase tx which is always first) but we should maybe impl Encodable/Decodable and/or serde Deserialize/Serialize as appropriate.

Copy link
Collaborator
@Kixunil Kixunil Oct 14, 2022 •
edited
Loading

Choose a reason for hiding this comment

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

I like that naming! I was thinking more along enum MerkleNode { LChild, RChild } and (MerkleNode, H) which simplifies the enum but I don't strongly oppose your suggestion. I'm still not convince about hash being anything else than sha256. (Note that we should be always able to make it more generic without breaking backcompat.)

Copy link
Member

Choose a reason for hiding this comment

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

How do you know what position the leaf is in?

Copy link
Author

Choose a reason for hiding this comment

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

you are right I need to know at least in which position the leaf is

Copy link
Author

Choose a reason for hiding this comment

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

btw still not sure if we want to specify the position of all the elements into the iterator.
I could pass an iterator that is the path without and is composed by simple hashes and contains the leaf so it is likely something that as a user I do not need to change (changing the Inner types or removing the leaf)
Then I pass the leaf that need to specify the position.

Does it make sense from an usability point of view?

Copy link
Member

Choose a reason for hiding this comment

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

Sorry, I have been conflating two things:

From a usability point of view we would like to be able to create and validate the CMerkleBlock structure that is output from Core's gettxoutproof RPC. This is actually an interesting structure which is able to prove more than one TXID at a time. I think this is what @Kixunil and I really would like.

Separately, we want to be able to validate a stratum v2 merkle proof, which is just a single list of hashes (all of which are right-parents because the proof is always about a coinbase tx). I think this is what you're trying specifically to achieve.

What may make sense is to have two completely separate APIs -- one which is called check_stratum_v2_coinbase_merkle_proof or something similarly crazy, and one based around the txoutproof format. Alternately, we could have a TxOutProof structure and add a constructor that takes a stratum v2 proof and synthetically constructs a gettxoutproof object from that.

Copy link
Collaborator

Choose a reason for hiding this comment

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

Why do we need a separate API? Just use map(MerkleNode::Right) on the existing iterator for stratum.

root = T::from_engine(encoder);
}
Some(root)
}

/// Calculates the merkle root of an iterator of *hashes*.
///
/// This fcuntion calculate the root from the list of all the txs in the block when we need to
/// derive the root from the merkle path [bitcoin_merkle_root_from_path] should be used.
///
/// # Returns
/// - `None` if `hashes` is empty. The merkle root of an empty tree of hashes is undefined.
/// - `Some(hash)` if `hashes` contains one element. A single hash is by definition the merkle root.
Expand All @@ -47,7 +85,7 @@ pub fn bitcoin_merkle_root<T, I>(mut hashes: I) -> Option<T>
where
T: Hash + Encodable,
<T as Hash>::Engine: io::Write,
I: Iterator<Item=T>,
I: Iterator<Item = T>,
{
let first = hashes.next()?;
let second = match hashes.next() {
Expand Down Expand Up @@ -81,7 +119,7 @@ where
<T as Hash>::Engine: io::Write,
{
if hashes.len() == 1 {
return hashes[0]
return hashes[0];
}

for idx in 0..((hashes.len() + 1) / 2) {
Expand All @@ -102,8 +140,9 @@ mod tests {
use crate::consensus::encode::deserialize;
use crate::hashes::sha256d;

use crate::blockdata::block::Block;
use super::*;
use crate::blockdata::block::Block;
use crate::hashes::Hash;

#[test]
fn both_merkle_root_functions_return_the_same_result() {
Expand All @@ -123,4 +162,75 @@ mod tests {
let from_array = bitcoin_merkle_root_inline(&mut hashes_array);
assert_eq!(from_iter, from_array);
}

#[test]
fn test_merkle_root_from_path() {
let coinbase_hash = [
Copy link
Collaborator

Choose a reason for hiding this comment

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

could you add a comment with reference to the tx/block if they are available on mainnet or testnet?

Copy link
Author

Choose a reason for hiding this comment

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

they are not, what I could do is to add a function to calculate path from ids and check that

let path = path_from_ids(real_block.ids, index);
let expected = bitcoin_merkle_root(real_block.merkle_root);
let root = bitcoin_merkle_root_from_path(path);
assert_eq!(expected,root)

What about that?

10_u8, 66, 217, 241, 152, 86, 5, 234, 225, 85, 251, 215, 105, 1, 21, 126, 222, 69, 40,
157, 23, 177, 157, 106, 234, 164, 243, 206, 23, 241, 250, 166,
];

let a = [
122, 97, 64, 124, 164, 158, 164, 14, 87, 119, 226, 169, 34, 196, 251, 51, 31, 131, 109,
250, 13, 54, 94, 6, 177, 27, 156, 154, 101, 30, 123, 159,
];
let b = [
180, 113, 121, 253, 215, 85, 129, 38, 108, 2, 86, 66, 46, 12, 131, 139, 130, 87, 29,
92, 59, 164, 247, 114, 251, 140, 129, 88, 127, 196, 125, 116,
];
let c = [
171, 77, 225, 148, 80, 32, 41, 157, 246, 77, 161, 49, 87, 139, 214, 236, 149, 164, 192,
128, 195, 9, 5, 168, 131, 27, 250, 9, 60, 179, 206, 94,
];
let d = [
6, 187, 202, 75, 155, 220, 255, 166, 199, 35, 182, 220, 20, 96, 123, 41, 109, 40, 186,
142, 13, 139, 230, 164, 116, 177, 217, 23, 16, 123, 135, 202,
];
let e = [
9FB7 109, 45, 171, 89, 223, 39, 132, 14, 150, 128, 241, 113, 136, 227, 105, 123, 224, 48,
66, 240, 189, 186, 222, 49, 173, 143, 80, 90, 110, 219, 192, 235,
];
let f = [
196, 7, 21, 180, 228, 161, 182, 132, 28, 153, 242, 12, 210, 127, 157, 86, 62, 123, 181,
33, 84, 3, 105, 129, 148, 162, 5, 152, 64, 7, 196, 156,
];
let g = [
22, 16, 18, 180, 109, 237, 68, 167, 197, 10, 195, 134, 11, 119, 219, 184, 49, 140, 239,
45, 27, 210, 212, 120, 186, 60, 155, 105, 106, 219, 218, 32,
];
let h = [
83, 228, 21, 241, 42, 240, 8, 254, 109, 156, 59, 171, 167, 46, 183, 60, 27, 63, 241,
211, 235, 179, 147, 99, 46, 3, 22, 166, 159, 169, 183, 159,
];
let i = [
230, 81, 3, 190, 66, 73, 200, 55, 94, 135, 209, 50, 92, 193, 114, 202, 141, 170, 124,
142, 206, 29, 88, 9, 22, 110, 203, 145, 238, 66, 166, 35,
];
let l = [
43, 106, 86, 239, 237, 74, 208, 202, 247, 133, 88, 42, 15, 77, 163, 186, 85, 26, 89,
151, 5, 19, 30, 122, 108, 220, 215, 104, 152, 226, 113, 55,
];
let m = [
148, 76, 200, 221, 206, 54, 56, 45, 252, 60, 123, 202, 195, 73, 144, 65, 168, 184, 59,
130, 145, 229, 250, 44, 213, 70, 175, 128, 34, 31, 102, 80,
];
let n = [
203, 112, 102, 31, 49, 147, 24, 25, 245, 61, 179, 146, 205, 127, 126, 100, 78, 204,
228, 146, 209, 154, 89, 194, 209, 81, 57, 167, 88, 251, 44, 76,
];
let path: Vec<crate::hashes::sha256d::Hash> =
vec![coinbase_hash, a, b, c, d, e, f, g, h, i, l, m, n]
.iter()
.map(|h| crate::hashes::Hash::from_slice(&h[..]).unwrap())
.collect();
let expected_root: crate::hashes::sha256d::Hash = crate::hashes::Hash::from_slice(
&[
73_u8, 100, 41, 247, 106, 44, 1, 242, 3, 64, 100, 1, 98, 155, 40, 91, 170, 255,
170, 29, 193, 255, 244, 71, 236, 29, 134, 218, 94, 45, 78, 77,
][..],
)
.unwrap();
let root = bitcoin_merkle_root_from_path(path.into_iter()).unwrap();
assert_eq!(expected_root, root)
}
}
0