Help; Would Merkel tree solves problem of Collision encountered with SHA256

odolvlobo

legendary

Activity: 4522

Merit: 3426

Quote from: NdaMk on May 14, 2022, 12:18:19 PM

1. Would Merkle tree solves the problem of Collision sometimes encountered with SHA256?
2. How secure is this more than the normal linear hash and what's the difference?

I assume that you are proposing to use a merkle tree root as the hash for a message instead of a simply computing the hash of the message directly.

That will have no effect on the probability of a collision because both are single SHA-256 hashes in the end. The only way to reduce the probability of a collision is to increase the size of the hash (assuming that there are no flaws in the hash algorithm).

o_e_l_e_o

legendary

Activity: 2268

Merit: 18775

Quote from: PrimeNumber7 on May 15, 2022, 08:45:52 AM

There is an infinite number of data that can potentially be hashed

There isn't, although practical speaking the limit is irrelevant. As I stated above, there are 2^(2⁶⁴)-1 possible inputs in to SHA256.

If you look at page 18 of the Secure Hash Standard document from NIST:

Quote from: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf#page=18

Then append the 64-bit block that is equal to the number l expressed using a binary representation.

This means that for any input in to SHA256, you must first express the length of that input as a 64 bit number and append that 64 bit number to the input. This places an upper limit on the length of any input of 2⁶⁴-1 bits, meaning 2^(2⁶⁴)-1 possible inputs.

For reference, a length of 2⁶⁴-1 bits is equivalent to 2 million terabytes.

PrimeNumber7

copper member

Activity: 1666

Merit: 1901

Amazon Prime Member #7

Quote from: NdaMk on May 15, 2022, 04:04:30 AM

My question isn't about making Collision but can collision (process whereby hashing of two or more different keys gives the same hashing value or result) be totally eradicated with this method of Merkle tree

It is impossible to entirely eradicate the potential for a collusion when using a hashing algorithm. Otherwise, you would just be dealing with raw data.

Given the limited number of blocks, and the algorithm currently being used, the chances of a collusion is effectively zero under the status quo.

Quote from: BlackHatCoiner on May 14, 2022, 12:28:14 PM

Quote from: NdaMk on May 14, 2022, 12:18:19 PM

1. Would Merkle tree solves the problem of Collision sometimes encountered with SHA256?

What do you mean? There's never been a collision with SHA-256.

There are 2²⁵⁶ possible outcomes when hashing a piece of data using SHA-256. There is an infinite number of data that can potentially be hashed, therefore, there is an infinite number of data points that will produce collisions when hashing each of the data points using SHA-256.

With that being said, actually finding any of those collisions is a different story, and it is unlikely that someone will ever encounter a SHA-256 collusion without breaking SHA-256.

o_e_l_e_o

legendary

Activity: 2268

Merit: 18775

Quote from: NotATether on May 14, 2022, 10:54:11 PM

As you can see, it actualy uses SHA256 (I believe Bitcoin's merkle trees hash with SHA512 which is no more secure than SHA256) inside, so it is not a substitute for a direct SHA256 hash.

Bitcoin uses double SHA256, not SHA512, for its Merkle trees. So combining transaction A and B to the next node up would be SHA256(SHA256(A+B)).

Quote from: NdaMk on May 15, 2022, 04:04:30 AM

can collision (process whereby hashing of two or more different keys gives the same hashing value or result) be totally eradicated with this method of Merkle tree

No, it can't. Given that there are 2^(2⁶⁴)-1 possible inputs to SHA256, but "only" 2²⁵⁶ possible outputs, there is always the chance that two completely unrelated inputs will give the same output.

NdaMk

full member

Activity: 303

Merit: 137

Defend Bitcoin and its PoW: bitcoincleanup.com

Quote from: garlonicon on May 14, 2022, 11:57:46 PM

Quote

Would Merkle tree solves the problem of Collision sometimes encountered with SHA256?

No. You can make a collision, so that the left branch and the right branch is the same, and their concatenation after hashing is also the same. Then, you can put some node in an endless merkle branch downloading loop. You only need one collision for that: "SHA-256d(hash||hash)==hash". Also, you should probably be careful about endianness, but yes, it is possible to create a merkle branch, that looks like this:

Code:

     hash
    /    \
hash      hash

My question isn't about making Collision but can collision (process whereby hashing of two or more different keys gives the same hashing value or result) be totally eradicated with this method of Merkle tree

garlonicon

copper member

Activity: 821

Merit: 1992

Quote

Would Merkle tree solves the problem of Collision sometimes encountered with SHA256?

No. You can make a collision, so that the left branch and the right branch is the same, and their concatenation after hashing is also the same. Then, you can put some node in an endless merkle branch downloading loop. You only need one collision for that: "SHA-256d(hash||hash)==hash". Also, you should probably be careful about endianness, but yes, it is possible to create a merkle branch, that looks like this:

Code:

     hash
    /    \
hash      hash

Quote

How secure is this more than the normal linear hash and what's the difference?

We have double SHA-256 and not single SHA-256, because of length extension attacks.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

A Merkle tree is when you repeatedly has together two values, using something like sha256 to get a single "branch" value.

As you can see, it actualy uses SHA256 (I believe Bitcoin's merkle trees hash with SHA512 which is no more secure than SHA256) inside, so it is not a substitute for a direct SHA256 hash.

o_e_l_e_o

legendary

Activity: 2268

Merit: 18775

Quote from: NdaMk on May 14, 2022, 01:28:03 PM

Collision of data ( senerio where by same result is generated when hashing) sometimes happens in hashing with SHA256 although proportional almost impossible.

I wouldn't say "sometimes" - it has never knowingly happened.

Quote from: NdaMk on May 14, 2022, 01:28:03 PM

So my question is can Merkle tree solve it entirely

Bitcoin's Merkle tree is just a large branching series of SHA256 hashes. If you think SHA256 is broken (it isn't), then simply repeating it over and over doesn't make it secure.

NdaMk

full member

Activity: 303

Merit: 137

Defend Bitcoin and its PoW: bitcoincleanup.com

Quote from: BlackHatCoiner on May 14, 2022, 12:28:14 PM

Quote from: NdaMk on May 14, 2022, 12:18:19 PM

1. Would Merkle tree solves the problem of Collision sometimes encountered with SHA256?

What do you mean? There's never been a collision with SHA-256.

Collision of data ( senerio where by same result is generated when hashing) sometimes happens in hashing with SHA256 although proportional almost impossible. So my question is can Merkle tree solve it entirely

BlackHatCoiner

legendary

Activity: 1512

Merit: 7340

Farewell, Leo

Quote from: NdaMk on May 14, 2022, 12:18:19 PM

1. Would Merkle tree solves the problem of Collision sometimes encountered with SHA256?

What do you mean? There's never been a collision with SHA-256.

Quote from: NdaMk on May 14, 2022, 12:18:19 PM

2. How secure is this more than the normal linear hash and what's the difference?

How secure is what? The hash function? The process where we construct hash trees has to do with the efficiency of verification.

NdaMk

full member

Activity: 303

Merit: 137

Defend Bitcoin and its PoW: bitcoincleanup.com

Transactions in a block are compressed and verified as one in a Bitcoin by Merkle tree. The tree is created by repeatedly hashing of nodes to form a single one. This kind of tree is produced upside down ( not like the natural tree). The technique is similar to the process of hashing twice the SHA256. The tree can be constructed from multiple transactions but still has same top root of 32-bytes data. The Merkle tree efficiency increases proportionally with the increase in scale. SPV nodes are verified by Merkle paths without having to download the full Bitcoin blocks. Merkle paths connect transactions to the block Merkle root.

1. Would Merkle tree solves the problem of Collision sometimes encountered with SHA256?

2. How secure is this more than the normal linear hash and what's the difference?

Topic: Help; Would Merkel tree solves problem of Collision encountered with SHA256 (Read 213 times)