etotheipi
Legendary
Offline
Activity: 1428
Merit: 1000
Core Armory Developer


July 17, 2011, 02:53:26 PM 

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/00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1dIf 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?








Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.

hashcoin


July 17, 2011, 03:55:35 PM 

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: >>> pinv = (2**256)/0x00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1dL >>> pinv 154566286767518877857L >>> pinv/2**32 35987768035L
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.




etotheipi
Legendary
Offline
Activity: 1428
Merit: 1000
Core Armory Developer


July 17, 2011, 06:05:05 PM 

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 logbase2 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. Threeminute blocks happen all the time.




Noitev


August 23, 2013, 11:13:44 AM 

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




gmaxwell
Moderator
Legendary
Offline
Activity: 2436
Merit: 1182


September 05, 2013, 11:47:01 AM 

SetBestChain: new best=000000000000000004ae693a1a8e740a33dd996c27ccc64217ed647e0b90d910 height=244583 log2_work=70.572612 tx=20254333 date=20130703 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

Bitcoin will not be compromised



Noitev


September 06, 2013, 04:21:23 PM 

ty!




David Rabahy


September 06, 2013, 04:32:23 PM 

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




David Rabahy


September 06, 2013, 04:33:25 PM 

Can a hash *ever* repeat?




eb3full
VIP
Full Member
Offline
Activity: 198
Merit: 100


September 06, 2013, 09:40:43 PM 

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_functionHowever, neither of those situations are even remotely likely given what we understand about hash functions, in particular SHA2.

"With four parameters I can fit an elephant, and with five I can make him wiggle his trunk." John von Neumann buy me beer: 1HG9cBBYME4HUVhfAqQvW9Vqwh3PLioHcU



gmaxwell
Moderator
Legendary
Offline
Activity: 2436
Merit: 1182


September 06, 2013, 09:55:29 PM 

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).
I don't actually know that we know if there is a hash with all zeros. The state space of the SHA2256 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.

Bitcoin will not be compromised



kjj
Legendary
Offline
Activity: 1302
Merit: 1000


September 07, 2013, 05:03:24 AM 

Can a hash *ever* repeat?
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 ^{384} possible block headers per block ID, with 384 being 640256. 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^{256} is still impossibly huge.I don't actually know that we know if there is a hash with all zeros. The state space of the SHA2256 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.
Indeed. The output space of sha256 is currently unknown. We suspect (hope) that it is close to [02 ^{256}], 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.

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8 I routinely ignore posters with paid advertising in their sigs. You should too.



etotheipi
Legendary
Offline
Activity: 1428
Merit: 1000
Core Armory Developer


September 07, 2013, 05:16:16 AM 

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 lowerbound of energy to find such a collision is many billion times more energy than the sun contains.




w00dy
Member
Offline
Activity: 96
Merit: 10


September 08, 2013, 08:59:44 AM 

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 lowerbound of energy to find such a collision is many billion times more energy than the sun contains.
well... whatever some1 says... they CAN happen. Just because the chance is VERYlow*10^whateverhere does not mean it's impossible. Math don't care about Atoms in the Universe or a human lifetime. End of story.




lophie


September 08, 2013, 09:31:01 AM 

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 lowerbound of energy to find such a collision is many billion times more energy than the sun contains.
well... whatever some1 says... they CAN happen. Just because the chance is VERYlow*10^whateverhere does not mean it's impossible. Math don't care about Atoms in the Universe or a human lifetime. End of story. Not the end of story by far and here where people start losing grasp of the link between math, natural sciences and their real life implications. What to be considered impossible to occur in nature is well defined even though it is within the boundaries of mathematical calculations. Start from here please http://en.wikipedia.org/wiki/Fermi_paradox, The journey has just started ^_^.

Will take me a while to climb up again, But where is a will, there is a way...



grau


September 09, 2013, 05:48:32 AM 

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.
Not doubting this, just curious what the actual math is convincing you that SHA256 is solid. Do you have a pointer?




fpgaminer


September 09, 2013, 07:52:22 AM 

Not doubting this, just curious what the actual math is convincing you that SHA256 is solid. Do you have a pointer? On a related note, if a solid ^{(1)} hash function actually did exist, it would have some groundbreaking implications: Theoretical implications of oneway functions. (1) "In computer science, a oneway function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems." ~ Wikipedia:Oneway function




David Rabahy


September 09, 2013, 01:58:25 PM 

The very first occurrence of a trailing 0 is; http://blockexplorer.com/b/42 with a hash of 00000000ac21f2862aaab177fd3c5c8b395de842f84d88c9cf3420b2d393e550 but then very soon after that we have a trailing double 0; http://blockexplorer.com/b/4900000000f067c09041ff0fcee3d91aeb7fbcc5654d3f766af2b4377aaee68d00 but it takes a long time until another trailing double 0 comes along; http://blockexplorer.com/b/665000000008b3292ededf3a3a675c44bb2a2ac378878fad1c10cef4219f2d95100 One wonders when a trailing triple 0 appears.




David Rabahy


September 09, 2013, 02:02:36 PM 

I fully realize trailing 0's are no more interesting than any other arbitrary sequence but Satoshi started it with his leading 0's. Why not leading 1's? Why not a leading sequence of 3.1415926535...? No, the cat is out of the bag.




grau


September 09, 2013, 02:18:18 PM 

I fully realize trailing 0's are no more interesting than any other arbitrary sequence but Satoshi started it with his leading 0's. Why not leading 1's? Why not a leading sequence of 3.1415926535...? No, the cat is out of the bag.
Mining blocks is not about constructing a block hash with leading zeros, but a hash numerically less than a target number. Leading zeros in the hash are just the consequence of that target being less and less with increasing difficulty. Difficulty is the ratio of initial/current target.




David Rabahy


September 09, 2013, 03:26:32 PM 

The nonce is only 32 bits; could there come a day with the difficulty is high enough that no nonce works?




