Topic: For fun: the lowest block hash yet - page 5. (Read 21200 times)

People like to take the idea "hash collisions are theoretically possible!" and pretend like they could actually happen and that something in life should accommodate that possibility.  If you have a solid hash function (which SHA256 is) and you come across a collision, then either:

(1) SHA256 is broken
(2) You hashed two things that were identical

End of story.  There's about as many different SHA256 hash values as there are atoms in the universe.  From the perspective of a human, a proper hash function that outputs more than 128 bits do not have collisions.  They won't even happen in the future due to increasing computational speed -- Bruce Schneier showed that the thermodynamic lower-bound of energy to find such a collision is many billion times more energy than the sun contains. 

This question is oddly difficult in bitcoin.  In bitcoin, the hashes are used as identifiers.

As pointed out by others already, cryptographic hashing systems are essentially lossy compression.  For a given sha256 output, there is at least one input that creates it, and possibly an infinite number.  A block header is 80 bytes long, and a sha256 output is 256 bits long.  If we assume an even distribution for both the bits of a header (known to be false) and for sha256 (see previous posts, and my addition below), we can expect about 2³⁸⁴ possible block headers per block ID, with 384 being 640-256.

It gets messy in reality.  Large portions of the block header are not evenly distributed, and several of those portions are moving targets.  Someone could probably work up reasonable estimates for the actual bits of freedom for a given block header candidate, and from that estimate how many such candidates we can expect per output.  I find it interesting enough, but it is late, and I'm tired, so I won't bother.

With that pointless aside out of the way, back to identifiers.  We use the block header hashes as identifiers for the block.  The network enforces uniqueness of these identifiers in an odd way.  Say you are hashing along, and you find a nonce that satisfies a header for the next block, but by a strange twist of fate, that hash just happens to be equal to a freakishly low hash previously found*, perhaps one listed in this thread.  Your node announces this to peers by sending them a message with the new block's identifier.  They all ignore you, because they already "have" that block and so there is no point asking you for the rest of it.  I'm actually not sure how your node would even handle it.  I'd have to check the code to see if it would overwrite the old block, or drop the new one.  Odds are good that we'll never find out the hard way.

With transactions, it is even worse.  The same mechanism exists, but nodes do not (by default) keep full track of all transactions, just unspent ones.  It is possible** to create a new transaction that happens to have the same hash as an old transaction.  Again, I'm not sure how it would end up without reading the code.

* I'm not sure if this would qualify for impossibly good luck, or impossibly bad luck.  Certainly one of these extremes though

**  Not really.  The birthday attack on 2²⁵⁶ is still impossibly huge.



Indeed.  The output space of sha256 is currently unknown.  We suspect (hope) that it is close to [0-2²⁵⁶], but we don't exactly know that.  Cryptographic hashes look a hell of a lot like random numbers, by design.  One of the standard tests is to generate pairs of hashes from pairs of inputs that differ by a single flipped bit.  We expect that about half of the output bits will change between pairs, on average, and we expect a fairly flat distribution of flip counts for each bit position, again, on average.  The sha family passes these tests, and from this, we gain confidence (but not certainty) about the distribution of outputs.

I don't actually know that we know if there is a hash with all zeros.  The state space of the SHA2-256 compression function is 'only' 768 bits and it's not at all constructed like a permutation on the input. There is clearly internal cancellation, so  AFAICT some outputs may be unreachable but we don't know which ones are.

To answer both your questions David, yes a hash can repeat and yes a hash with all zeroes exists (an infinite number of strings can produce it, in fact).

http://en.wikipedia.org/wiki/Cryptographic_hash_function

However, neither of those situations are even remotely likely given what we understand about hash functions, in particular SHA-2.

Can a hash *ever* repeat?

Which hash has the most trailing 0s?  Is a hash of *all* 0s possible?

ty!

SetBestChain: new best=000000000000000004ae693a1a8e740a33dd996c27ccc64217ed647e0b90d910  height=244583  log2_work=70.572612  tx=20254333  date=2013-07-03 14:50:02 progress=0.645633

Effective "difficulty": 234,873,483,844  or about 69.77 bits, thats somewhat behind relative to the cumulative work at that point (and our current amount: log2_work=71.682609)

Block 125552 is now the 20th best, fwiw. The current top 20 are:


000000000000000004ae693a1a8e740a33dd996c27ccc64217ed647e0b90d910
000000000000000006582fa9652895fda92c757ae6beee9dfbc3932125b5ab8e
00000000000000000ae2dba9951e28a3e6308ac7e9e8536104c503aa772c848f
00000000000000000c5da159125977d610e97afaad2b52c5641cf5d107cbb4c8
00000000000000000ce84e315900096f772ddce728fe74eb01cb2f5ca9b8a608
00000000000000000eab32386b8854581ca95f672ec9ccd96d2201c493f2c644
00000000000000001115d0f81474bbb9ebb9a45e04597f2df39e0eba903b679f
0000000000000000139008bfda982356c5065c9035d6c7d588069d3e1b35746a
000000000000000013b542b70897dcb248a0379e7a2cf9763f5fb3e90759072a
000000000000000014d28626334cb5bcd8aad5b3a313239b7d669b232dfe7021
000000000000000017f9c4f0af122d4a8cd9607acfecaffa7445ba3fc4523297
0000000000000000193f0908548ed5a36237a0a6f9fa480d79d107d31eb329d2
000000000000000019e6cf209f3509db56f45ad6f1f85287c1202f634911e87b
00000000000000001a956b37c9e81414c43086acd14ec1c0e32fd3ff995efc6b
00000000000000001b0490e228c3f66442fc0b4ac740a3223a90ce71e2cf9026
00000000000000001b81cb08052cff1f1468d3e9bdb42fb7487cea6a9d62f233
00000000000000001bfaa06e0d8c9aa94ce50ecf685d153e81f65e56546cf0bb
00000000000000001c0ac3a94007add81dee24ab9ab4d7dc87636a6c9260483d
00000000000000001ceb24157a3316477b4529b0c4d9be7636aedb05f8981003
00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d

Has anyone beaten this yet considering the 2 year gap and insane difficulty increase (and  consequently, hashrate) since this thread started?

That's high, but it's not ludicrous given the amount of hashing that has been done in the last year.  At the current global hashrate, it seems it would take 150 days (on average) to find another hash just as good.  The blockchain has been in generation for over a year, but with much lower rates for most of that time.

Well okay, let's be more precise:  I summed up all the difficulties up to block 136,496.  The total value is 10,939,043,020.8.  Take the log-base-2 and add 32 for the difficulty=1 size:  you get 65.35.  So the network has executed on somewhere around 2^65.35 hashes to produce the 136,496 blocks with their associated difficulties.  This isn't terribly far from the block in question, requiring on average 2^67.07 hashes.   It is only 3.3 times higher (1.72 bits) higher than the total difficulty sum.  

This is well within the scope of the exponential distribution of block generation.  This is like having enough computational power on the network for the difficulty to be at 35 billion, and then the network solving a block at that difficulty in 3 minutes.  Three-minute blocks happen all the time.

Quite cool!

Here's an easy way to do the math:  think of putting a "0." before the target hash value, and now you have a number between 0 and 1 written in hex.  (E.g., 0.A in hex is 0xA/0x10).

Call this number p.  But now observe p is precisely the probability you beat that target.  So it would take on average, 1/p hashes to beat.

So to get the # of hashes, just get 1/p.  To get the difficulty, divide that by 2^32 since difficulty 1 = 2^32 hashes (equivalently, difficulty 1 = dot shifted over 8 places to right).

If you have a python interpreter handy, you can see:


If you want to go another step, you could compute the probability this happened by now in a parallel bitcoin world.  If you have your script handy, just compute the SUM of all difficulties, over all blocks.  That * 2^32 is roughly how many hashes have been done since bitcoin was born.

Since I finally figured out how to read the block chain, I decided it would be fun to find the lowest hash produced, yet.  The hash for a block doesn't have to be AT that difficulty, it just has to beat it, and I figured there's gotta be some blocks with major overkill in terms target hash, just by luck.  Well here it is, block 125,552:

http://blockexplorer.com/block/00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d

If I did the difficulty calculation correctly (no guarantees), I believe this block would've been valid even at difficulty 35,987,768,035  (current difficulty is 1,564,057).  Can someone verify that?