Topic: What happens if a Block can't be found? (Read 1562 times)

http://en.wikipedia.org/wiki/Sha256
http://en.wikipedia.org/wiki/Avalanche_effect

No more than 32 zeros as half the bits are flipped to produce the the avalanche effect.

It would be like trying to create a device that the more heat you put into it it, the colder it gets. 

Great analogy. I guess if we ever did run into an issue a hard-fork would be done to fix it.

I do not think it is mathematically possible to get a SHA256 hash result of all zero's because of the way the SHA256 constants are introduced into the algorithm. It raises the question of what the smallest possible result would be? And of course what the largest possible result would be?

Even those 104 bytes give you 832 bits of entropy. And even if we theoretically hit the difficulty which would require hitting the exact hash of 0 (which would basically break BTC anyway and require a computer the size of the Solar System), it still means that we need to put 2^832 values into 2^256 buckets, and one of the buckets needs to be empty. The probability of this is, if my math is correct, ((2^256-1)/(2^256))^(2^832) which is, let's just say, a very small number.

There is, of course, a chance that SHA256 is internally broken and doesn't follow uniform distribution of hash values, but again, finding this out breaks BTC anyway.

Mathematically speaking, using the current bitcoin hash algorithm, there will be a point where the difficulty will be impossible to target because of the avalanche effect built into the sha256 algorithm that fights it. When that time comes, what happens if the difficulty is not achievable and no more blocks can be created? All transactions stop in bitcoin because the two systems (transactions and currency creation) are locked together.

I would say it like this: given what we know about the properties of SHA256 hashing, asking "what happens if a block can't be found" would get the same answer as "what happens if it never rains again": there can be droughts, but it is not going to happen.

Use the binomial expansion: Let x=2^256, then p=[(1-1/x)^x]^(2^576) ~= (1/e)^(2^576). ~= 1/(10^173). So yeah, pretty close!

Can you (or someone else) expand on this a bit? What exactly do you mean by this?

The main point is how even the sha256 hash value distributed. In other words, we need to know the probability that given N >> 2 ^ 256, the probability that sha256(D0) to sha256(DN) always larger than 0 (I think this is the minimal target and represents the largest difficulty, and I doubt we will achieve this difficulty some day).

Then talk about N. If we never change the transactions included, we have 4 bytes in Nonce and 100 bytes in extra nonce. So it is 2 ^ (32 + 800) = 2 ^ (832). If we can just remove/add some transactions (that means the root hash needs to be recomputed), then theoretically the N is much larger and almost 2 ^ (8000000).

If the distribution of sha256 is truly even, that means every nonce will have the same chance to have sha256(d) = 0, that is 1/(2 ^ 256). The probability for hash of 2 ^ (832) nonces all larger than 0 then is (1 -  1 / (2 ^ 256)) ^ (2 ^ 832) =  ?. I don't know how to calculate this yet, but pretty sure it's very very close to 0.

Yeah my mistake- I was just thinking more generally about the phrase "data which can be hashed".  But yeah, obviously if there is a size limit there's a finite amount.

I was thinking the same thing, but didn't say anything because i thought i was missing something.

The number of possible nonces is certainly not infinite. The nonce field in the header is 4 bytes, the extraNonce field in the coinbase can be up to 100 bytes. This makes for a very large, but finite number of possible nonces and therefore a finite number of solutions. Even if you added additional fields that could hold arbitrary value, the maximum block size of 1 MB still restricts the number of possibilities to something finite.

That's not correct.  The number of unique data which can be hashed with sha256 (or any hash) is infinite.  Some nonce will work out.  And if it doesn't, it won't be the leading zeros, it'll just be some random flaw in the algorithm that happens to manifest itself in the leading zero case.

You're thinking as the leading zeros increase, the number of solutions decrease, but that's not true because there's an infinite number of possible nonces which hash to be valid solutions.  Let's say that block difficulty is such that 1% of random nonces will hash to be a block solution.  Even though only 1/100 random nonces will yield a valid solution, there's still an infinite amount of nonces.

Think of drawing tickets out of a (infinitely deep) hat with every number from 1 to infinity written on them (one number per ticket), and a valid ticket is divisible by some prime number, and as the difficulty goes up the prime number that the ticket must be divisible by goes higher.  That's what makes a ticket a winner.  So when the prime number is 1, every ticket is a winner, and when it's 2, half the tickets are winners, etc.  So as the difficulty increases, it's progressively harder and harder to have a drawing be a winner, and yet the number of possible winners is still infinite.

thank you for responding Gavin.

No, not possible, given what we know about the properties of SHA256 hashing.

But you are right it would come down to a probability, a perfect storm. I wonder what is the risk that this will happen before our sun dies? It would be fun if someone manage to calculate it.

Yes but isn't it a finite number of maximum zeros.

So it could be always possible of the number of possible input combinations are even greater.

And the input combinations are the nuance, all bitcoin addresses and all combinations of all possible transactions from all possible bitcoin addresses that can fit within a block.

It is a bit late here so i could have missed something.

edit: And all possible combinations of transaction sizes.

As the number of leading zeroes goes up, the number of possible solutions goes down. As an extreme, look at one digit with all leading zeroes. there are what, 10 possible solutions? since, for any given input there is one unique output. If the parts of the input that are constant for all possible inputs all fall outside those 10, you are screwed. of course if the difficulty was that high, there would most likely be other problems as well.

For any possible input you say, that would be a perfect storm.
Any combination of all made transactions plus any miner bitcoin address plus the nuance. That is a lot of combinations. :-)
Someone can probably calculate if it even theoretically possible. Maybe start with if it is theoretically possible if you assume there are no new transactions, just combinations of all bitcoin addresses and the nuance.

Ok, I may be way off with this, but it seems to me that since each block contains the hash of the previous block, this is a constant that must be in the found block regardless of who finds it. Considering how difficulty rises, some time in the distant future difficulty could be so high that for a given previous block hash there is no solution due to all possible solutions not being able to meet the difficulty.

Yes this is unlikly. But as the number of leading zeroes increases, the number of possible solutions decreases. It is possible to create the perfect storm if you will, where a solution can not be found for any possible inputs. if a block can't be found, the difficulty won't decrease because it is dependant on blocks being found.

Is it anticipated that this won't happen because difficulty will adjust down prior to this occurring? If so, one occurance of really bad luck and that one hash that can't be completed could occur. Is there anything built into the bitcoin algorithim to deal with this potential problem?