Bitcoin Forum
March 28, 2024, 08:55:05 AM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 3 4 5 »  All
  Print  
Author Topic: For fun: the lowest block hash yet  (Read 21185 times)
etotheipi (OP)
Legendary
*
expert
Offline Offline

Activity: 1428
Merit: 1093


Core Armory Developer


View Profile WWW
July 17, 2011, 02:53:26 PM
Last edit: November 23, 2011, 03:35:22 PM by etotheipi
Merited by ABCbits (1)
 #1

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?

Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
1711616105
Hero Member
*
Offline Offline

Posts: 1711616105

View Profile Personal Message (Offline)

Ignore
1711616105
Reply with quote  #2

1711616105
Report to moderator
No Gods or Kings. Only Bitcoin
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
hashcoin
Full Member
***
Offline Offline

Activity: 372
Merit: 101


View Profile
July 17, 2011, 03:55:35 PM
Last edit: July 17, 2011, 04:09:59 PM by hashcoin
Merited by ABCbits (1)
 #2

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:
Code:
>>> 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 (OP)
Legendary
*
expert
Offline Offline

Activity: 1428
Merit: 1093


Core Armory Developer


View Profile WWW
July 17, 2011, 06:05:05 PM
Last edit: July 17, 2011, 08:54:40 PM by etotheipi
 #3

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.





Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
Noitev
Hero Member
*****
Offline Offline

Activity: 812
Merit: 505


The Last NXT Founder


View Profile
August 23, 2013, 11:13:44 AM
 #4

Has anyone beaten this yet considering the 2 year gap and insane difficulty increase (and  consequently, hashrate) since this thread started?
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8343



View Profile WWW
September 05, 2013, 11:47:01 AM
Merited by ABCbits (2)
 #5


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
Noitev
Hero Member
*****
Offline Offline

Activity: 812
Merit: 505


The Last NXT Founder


View Profile
September 06, 2013, 04:21:23 PM
 #6

ty! Smiley
David Rabahy
Hero Member
*****
Offline Offline

Activity: 709
Merit: 501



View Profile
September 06, 2013, 04:32:23 PM
 #7

Which hash has the most trailing 0s?  Is a hash of *all* 0s possible?
David Rabahy
Hero Member
*****
Offline Offline

Activity: 709
Merit: 501



View Profile
September 06, 2013, 04:33:25 PM
 #8

Can a hash *ever* repeat?
eb3full
VIP
Full Member
*
Offline Offline

Activity: 198
Merit: 101


View Profile
September 06, 2013, 09:40:43 PM
Merited by ABCbits (1)
 #9

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.

"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
*
expert
Offline Offline

Activity: 4158
Merit: 8343



View Profile WWW
September 06, 2013, 09:55:29 PM
Merited by ABCbits (2)
 #10

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 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.
kjj
Legendary
*
Offline Offline

Activity: 1302
Merit: 1024



View Profile
September 07, 2013, 05:03:24 AM
 #11

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 2384 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 2256 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 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.

Indeed.  The output space of sha256 is currently unknown.  We suspect (hope) that it is close to [0-2256], 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 (OP)
Legendary
*
expert
Offline Offline

Activity: 1428
Merit: 1093


Core Armory Developer


View Profile WWW
September 07, 2013, 05:16:16 AM
Merited by ABCbits (1)
 #12

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. 

Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
w00dy
Member
**
Offline Offline

Activity: 96
Merit: 10


View Profile
September 08, 2013, 08:59:44 AM
 #13

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. 

well... whatever some1 says... they CAN happen. Just because the chance is VERY-low*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
Hero Member
*****
Offline Offline

Activity: 924
Merit: 1001

Unlimited Free Crypto


View Profile
September 08, 2013, 09:31:01 AM
Merited by ABCbits (1)
 #14

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. 

well... whatever some1 says... they CAN happen. Just because the chance is VERY-low*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
Hero Member
*****
Offline Offline

Activity: 836
Merit: 1021


bits of proof


View Profile WWW
September 09, 2013, 05:48:32 AM
 #15

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
Hero Member
*****
Offline Offline

Activity: 560
Merit: 517



View Profile WWW
September 09, 2013, 07:52:22 AM
 #16

Quote
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 one-way functions.

(1) "In computer science, a one-way 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:One-way function

David Rabahy
Hero Member
*****
Offline Offline

Activity: 709
Merit: 501



View Profile
September 09, 2013, 01:58:25 PM
 #17

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/49
00000000f067c09041ff0fcee3d91aeb7fbcc5654d3f766af2b4377aaee68d00

but it takes a long time until another trailing double 0 comes along;

http://blockexplorer.com/b/665
000000008b3292ededf3a3a675c44bb2a2ac378878fad1c10cef4219f2d95100

One wonders when a trailing triple 0 appears.
David Rabahy
Hero Member
*****
Offline Offline

Activity: 709
Merit: 501



View Profile
September 09, 2013, 02:02:36 PM
 #18

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
Hero Member
*****
Offline Offline

Activity: 836
Merit: 1021


bits of proof


View Profile WWW
September 09, 2013, 02:18:18 PM
 #19

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
Hero Member
*****
Offline Offline

Activity: 709
Merit: 501



View Profile
September 09, 2013, 03:26:32 PM
 #20

The nonce is only 32 bits; could there come a day with the difficulty is high enough that no nonce works?
Pages: [1] 2 3 4 5 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!