Why do hashes begin with 0000000...?

Meni Rosenfeld

donator

Activity: 2058

Merit: 1054

Quote from: TangibleCryptography on October 16, 2012, 06:48:21 AM

There isn't anything special or harder about an all zero hash.

If you ask me, "will you bet your life on the fact that no SHA-256 hash will be found by 2020 with a value of 00000000000000000000000000000000000000000000000000000000000000000, without SHA-256 being broken?", I'll say "sure", because this has a probability of about 1 in 10^50, and will thus not happen.

If you ask me the same about b0867d52439eedac556187087c69bbe6fdb3c47f266780775931068f18fae223, I will refuse. Why? Because I don't know how you came up with b0867d52439eedac556187087c69bbe6fdb3c47f266780775931068f18fae223. Maybe you generated it truly randomly (and then the answer is the same). But maybe you came up with it by calculating some SHA-256 hash, and then I will lose even before the bet began.

What makes me so confident in the 00000000000000000000000000000000000000000000000000000000000000000 case, and not in the b0867d52439eedac556187087c69bbe6fdb3c47f266780775931068f18fae223 case, is that 0 has a much lower Kolmogorov complexity (and the describing program has no reference to anything remotely relevant to SHA-256).

TangibleCryptography

sr. member

Activity: 476

Merit: 250

Tangible Cryptography LLC

Quote from: Come-from-Beyond on October 16, 2012, 06:54:36 AM

I see. Btw, is there any proof that output of SHA256 is distributed uniformly? I suspect that some outputs r met more often than others.

No hashing algorithm is perfectly distributed. That goal isn't even realistic or attempted. The theoretical "perfect" hashing function would be a Random Oracle. All practical implementations fall short of this ideal. SHA256 has been studied extensively to ensure its distribution is (for lack of a better term) "randomly distributed enough" to make using any imperfections in distribution an ineffective attack vector.

Here is a paper on forcing a collision attack (a method of exploiting non-random distribution) on a round reduced version of SHA256.
http://eprint.iacr.org/2008/131.pdf

By round reduced it means that this "attack" is only theoretical at best because it involves a shortened version of the SHA256 algorithm. In theory similar attacks could eventually be found on longer versions and possibly someday even the full length version.

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

I see. Btw, is there any proof that output of SHA256 is distributed uniformly? I suspect that some outputs r met more often than others.

TangibleCryptography

sr. member

Activity: 476

Merit: 250

Tangible Cryptography LLC

Quote from: Come-from-Beyond on October 16, 2012, 06:32:34 AM

Quote from: TangibleCryptography on October 16, 2012, 06:15:04 AM

It could mean that however it could simply be pure luck. A solution for a block (any block) today could be found that produces an all zero hash.

Doubtful. Who will calc 2²⁵⁵ hashes in average to find such a solution?

Well that is the thing about probability. While on AVERAGE (over an infinite number of universes) it will take 2^255 attempts to find that hash the same thing can be said of any individual hash.

The odds of finding this exact hash:
000000000000006472e36fb3dc1f77b846feabe001b2b86fc78fe8110cd6ce4f (solution for the most recent block #203545)
is also one in 2^256 and if you were looking for this specific hash using random inputs it would take on average 2^255 attempts.

There isn't anything special or harder about an all zero hash. Difficulty simply reduces the set of valid hashes relative to the set of all possible hashes and thus controls how many attempts on average will be necessary to find a valid one.

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: TangibleCryptography on October 16, 2012, 06:15:04 AM

It could mean that however it could simply be pure luck. A solution for a block (any block) today could be found that produces an all zero hash.

Doubtful. Who will calc 2²⁵⁵ hashes in average to find such a solution?

TangibleCryptography

sr. member

Activity: 476

Merit: 250

Tangible Cryptography LLC

Quote from: Meni Rosenfeld on October 16, 2012, 05:03:41 AM

Quote from: Come-from-Beyond on October 16, 2012, 03:52:44 AM

Quote from: waspoza on October 16, 2012, 03:37:15 AM

Quote from: herzmeister on October 16, 2012, 02:42:26 AM

You will know that we have reached the economic, technological and cosmological singularity once we've reached the 00000000000000000000000000000000000000000000000000000000000000000 hash.

And when that happens, division by zero will became possible and universe will cease to exist. Wink

To find "00000000000000000000000000000000000000000000000000000000000000000" hash is not harder than to find "458264a810936934867095f02578963498570298345702946587165c845698074" one.

"00000000000000000000000000000000000000000000000000000000000000000" has a lower Kolmogorov complexity, making finding it a more impressive achievement than "458264a810936934867095f02578963498570298345702946587165c845698074".

Of course, all it would mean is that SHA-256 has been sufficiently broken.

It could mean that however it could simply be pure luck. A solution for a block (any block) today could be found that produces an all zero hash.

Meni Rosenfeld

donator

Activity: 2058

Merit: 1054

Quote from: Come-from-Beyond on October 16, 2012, 03:52:44 AM

Quote from: waspoza on October 16, 2012, 03:37:15 AM

Quote from: herzmeister on October 16, 2012, 02:42:26 AM

You will know that we have reached the economic, technological and cosmological singularity once we've reached the 00000000000000000000000000000000000000000000000000000000000000000 hash.

And when that happens, division by zero will became possible and universe will cease to exist. Wink

To find "00000000000000000000000000000000000000000000000000000000000000000" hash is not harder than to find "458264a810936934867095f02578963498570298345702946587165c845698074" one.

"00000000000000000000000000000000000000000000000000000000000000000" has a lower Kolmogorov complexity, making finding it a more impressive achievement than "458264a810936934867095f02578963498570298345702946587165c845698074".

Of course, all it would mean is that SHA-256 has been sufficiently broken.

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: waspoza on October 16, 2012, 03:37:15 AM

Quote from: herzmeister on October 16, 2012, 02:42:26 AM

You will know that we have reached the economic, technological and cosmological singularity once we've reached the 00000000000000000000000000000000000000000000000000000000000000000 hash.

And when that happens, division by zero will became possible and universe will cease to exist. Wink

To find "00000000000000000000000000000000000000000000000000000000000000000" hash is not harder than to find "458264a810936934867095f02578963498570298345702946587165c845698074" one.

waspoza

hero member

Activity: 602

Merit: 508

Firstbits: 1waspoza

Quote from: herzmeister on October 16, 2012, 02:42:26 AM

You will know that we have reached the economic, technological and cosmological singularity once we've reached the 00000000000000000000000000000000000000000000000000000000000000000 hash.

And when that happens, division by zero will became possible and universe will cease to exist. Wink

herzmeister

legendary

Activity: 1764

Merit: 1007

You will know that we have reached the economic, technological and cosmological singularity once we've reached the 00000000000000000000000000000000000000000000000000000000000000000 hash.

CIYAM

legendary

Activity: 1890

Merit: 1086

Ian Knowles - CIYAM Lead Developer

The SHA256 "solution" hash for a block requires x number of zeros at the start as the way of controlling the "difficulty" to find such a hash by continually trying to hash the block header with a different "nonce" until such a solution is found.

This is the "proof of work" that is fundamental to the Bitcoin block chain method to prevent double spends.

Fjordbit

hero member

Activity: 588

Merit: 500

firstbits.com/1kznfw

Quote from: 🏰 TradeFortress 🏰 on October 16, 2012, 02:02:53 AM

For example, this page: http://blockchain.info/blocks/BTC%20Guild

Is there any reason for the hash being like that?

Yes, this is how the difficulty works. For a miner to successfully record the blocks, they have to have the transactions and block header all work out to have a hash less than a certain number. So the beginning will always have a bunch of zeros because the hash has to work out less than a certain target.

See the article on difficulty for more details.

🏰 TradeFortress 🏰

vip

Activity: 1316

Merit: 1043

👻

For example, this page: http://blockchain.info/blocks/BTC%20Guild

Is there any reason for the hash being like that?

Topic: Why do hashes begin with 0000000...? (Read 1567 times)