SHA256 doesn't match

help
1

I have used this library to generate a Merkle tree for me.
It uses default SHA256 algorithm to hash a block and then combines the hash of the leaves, which it hashes again to form a root(node) of the Merkle tree.

I find out the hash of the leaves by the following:

use merkle_tree::{MerkleTree};
use rustc_serialize::hex::ToHex;

fn main() {
    let block = "foo";
    let merkle_tree: MerkleTree = MerkleTree::build(&[block, block]);
    let leaves = merkle_tree.leaves();
    let leaves_to_hex = [29, 32, 57, 250, 121, 113, 244, 191, 1, 161, 194, 12, 178,
        163, 254, 122, 244, 104, 101, 202, 156, 217, 184, 64, 194, 6, 61, 248, 254, 196, 255, 117].to_hex();

    println!("{:?}", leaves);
    // Outputs [29, 32, 57, 250, 121, 113, 244, 191, 1, 161, 194, 12, 178,
    //         163, 254, 122, 244, 104, 101, 202, 156, 217, 184, 64, 194, 6, 61, 248, 254, 196, 255, 117]

    println!("{:?}", leaves_to_hex);

    // Outputs 1d2039fa7971f4bf01a1c20cb2a3fe7af46865ca9cd9b840c2063df8fec4ff75
}

It basically returns as_bytes array on which I use to_hex to obtain the hash.

When I match this hash with an SHA256 online, it doesn't match. What's not correct?

My Cargo.toml :

[dependencies]
merkle_tree = {git = "https://github.com/melekes/merkle-tree-rs"}
sha2 = "0.10.6"
rustc-serialize = "0.3"
hex-literal = "0.3.4"

Not all dependencies maybe used in this very snippet of code, they are from the project where they are used somewhere.

2

Your understanding of the whole process, most likely. I suspect that you expected that you can calculate SHA256 from two (or more) pieces and then calculate SHA256 from these and then compare to SHA256 of the whole then it should match.

Of course, in reality, if they would match then it would emergency time with the need to immediately replace SHA256 ASAP everywhere. The inability to do what you are trying to do, is, more-or-less, fundamental requirement for the crypto-hash.

To get the same result you need to repeat the whole thing: calculate SHA256 as many times as merkle tree does and combine them in a way merkle tree combines them.

Merkle tree is not a way to quickly calculate SHA256! It's a quick way to calculate different hash (albeit based on SHA256).

3

Hey @VorfeedCanal , appreciate you taking time to reply.

I didn't expect the node's hash to match.

I just wanted a leaf's hash to match as a leaf is just a hash of a data block, right?

What, I'm trying to establish is:

  • Whether a leaf node has the hash of a data block, or,

  • There is some other way with which it's calculated

If you create the smallest Merkle tree with 1 leaf and 1 node, you should be able to create it with simple hashing functions, ain't it?

4

Sure, but for that you need to know how SHA256 is used in that Merkle tree. If you would look on the implementation you'll see that each leaf is prepended with 0x00 (== LEAF) mark and then every non-leaf is prepended with 0x01 (== INTERIOR) mark.

And it uses Hasher interface which returns u64, not enough to fit full SHA256. Thus I suspect it combines not SHA256 sums but reduced SHA256 sums and you need to know how SHA256 is converted to u64.

You need to do an audit of that crate before you would know enough to replicate algorithm, I'm afraid.

5

Does it then again inflate the reduced set, as the hash I received after applying to_hex has the same length as an SHA256 has?

6

Also, I'm talking about the Merkle tree implementation mentioned here: merkle-tree-rs/lib.rs at master · melekes/merkle-tree-rs · GitHub
,not the one you have assumed.

7

The same thing applies: hash_leaf computes the SHA256 of a signature value followed by the data block. You'll need to duplicate that computation if you want to get the same output.

8

Hmm, I see. Would look to duplicate it. Thanks.

9

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.