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

Fi3 · 2022-10-13T15:24:51Z

RCasatta · 2022-10-13T15:39:40Z

bitcoin/src/util/hash.rs

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


typo: fcuntion, here and some lines below

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"

RCasatta · 2022-10-13T15:46:29Z

bitcoin/src/util/hash.rs

+
+    #[test]
+    fn test_merkle_root_from_path() {
+        let coinbase_hash = [


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

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?

Kixunil

Unless I'm mistaken this doesn't allow computing merkle root of an arbitrary branch which I'd consider a bug.

Kixunil · 2022-10-13T17:05:42Z

bitcoin/src/util/hash.rs

+pub fn bitcoin_merkle_root_from_path<T, I>(mut hashes: I) -> Option<T>
+where
+    T: Hash + Encodable,
+    <T as Hash>::Engine: io::Write,


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

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

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

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.

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

Kixunil · 2022-10-13T17:11:15Z

bitcoin/src/util/hash.rs

+    };
+
+    let mut encoder = T::engine();
+    let mut root = first;


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

Kixunil · 2022-10-13T17:13:19Z

bitcoin/src/util/hash.rs

+    let mut encoder = T::engine();
+    let mut root = first;
+    root.consensus_encode(&mut encoder).expect("in-memory writers don't error");
+    second.consensus_encode(&mut encoder).expect("in-memory writers don't error");


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

Any way to convert Inner into a byte array?

Just dereference it? Or do you mean something else?

In order to do that I need to restrict Hash to a type with a Inner 8000 =[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.

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.

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.

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).

Kixunil · 2022-10-13T17:15:40Z

bitcoin/src/util/hash.rs

+    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");


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.

OK a bool is enough or you prefer an enum?

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

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.

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.)~~

How do you know what position the leaf is in?

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

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?

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.

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

apoelstra · 2022-10-20T16:23:58Z

Breaking out of the long comment thread: I think we should back up and reduce the scope of this method, since @Fi3 is trying to get stuff working for stratum, which is simpler and less general than "validate arbitrary merkle proofs". In particular stratum proofs are always about the coinbase and therefore we don't need to worry about left vs right children.

I propose instead that we extend BlockHeader with two methods:

stratum_v2_coinbase_proof(&self) -> (Vec<sha256dHash>, Txid)
check_stratum_v2_coinbase_proof(&self, hashes: &[sha256d::Hash], coinbase: &Txid) -> bool

Since this is stratum-specific I could be convinced to merge the coinbase txid into the list of hashes, since I think that is how they serialize the txid.

apoelstra · 2022-10-21T00:46:11Z

Holy shit, we already have a MerkleBlock structure that does everything we want. The only functionality we're actually missing is the stratum2-specific stuff, which can be implemented as a couple of simple functions (as suggested in my above commit, and does not require reasoning about left children and right children).

Sorry @Fi3 for leading you on a wild goose chase!!

Fi3 · 2022-10-21T09:35:41Z

@apoelstra no prob, and thanks for your help. I will only add the 2 suggested functions.

Kixunil · 2022-10-21T09:47:40Z

Heh, OK, but why does upstreaming stratum code make sense here? This library is already super-huge with all kinds of stuff and as I understand it stratum protocol is only used in a few places.

apoelstra · 2022-10-21T14:16:22Z

@Kixunil because this particular function is simple (despite our running in circles :)) and seems generally useful. Though I agree, it seems less useful now that we realize that the same functionality, roughly, is exposed via MerkleBlock.

I agree that we shouldn't bring stratum data structures etc into this library, and if there was a rust-stratum-v2 lib I might propose moving this functionality there. But I'm not aware of such a library, and (a) I don't think implementors of stratum should have to figure this out on their own, (b) this library does provide a couple similar-sounding-but-incorrect methods, so I'd like to reduce that sort of confusion.

Mostly, I have an affinity for this particular feature -- letting miners prove that their coinbase is correct rather than allowing pools to dictate blocks -- because it's very socially positive and possibly critical to the survival of Bitcoin. But I don't have any other good place to put it.

Fi3 · 2022-10-25T13:13:54Z

There is a rust sv2 library and this function is already implemented there. So if you feel that having it also here is redundant maybe we can just close the issue @Kixunil @apoelstra

Kixunil · 2022-10-25T13:41:38Z

@Fi3 do you mean this one? https://github.com/ccdle12/rust-stratum-v2 Last commit 15 months ago... but maybe it's done?

@apoelstra if the algorithm is general-purpose I definitely like having it here. But there's so much more to stratum V2 than just proving the root. I don't think it makes sense to add one function here to make implementations easier. If you strongly care about it you should just make a separate crate. In that crate you can simply wrap the proof using .map(MerkleNode::RChild).

apoelstra · 2022-10-25T16:44:07Z

Ah, okay @Fi3, in this case I do think we should close this. Sorry!

@Kixunil I think that to be as general as possible, we want to support multiple branches at once -- but this is exactly what MerkleBlock does! Maybe we want to refactor it to be generic over the transaction type but I don't thing we should bother until somebody asks for it.

Fi3 · 2022-10-26T09:24:40Z

@Kixunil I mean this one stratum-mining/stratum#305

Add function to calculate merkle root from a merle path

f6f00c5

RCasatta reviewed Oct 13, 2022

View reviewed changes

Kixunil requested changes Oct 13, 2022

View reviewed changes

Fi3 changed the title ~~Add function to calculate merkle root from a merle path~~ Add function to calculate merkle root from a merkle path Oct 13, 2022

tcharding mentioned this pull request Oct 21, 2022

Rename hash module to merkle_root #1334

Merged

Fi3 closed this Oct 27, 2022

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

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

Uh oh!

Conversation

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!

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!

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!

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!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!