Is there a proof that the hashing will always yield a result? Or proof that there exist unsolvable blocks?
It's my understanding that even if we hit an unsolvable block that eventually the transactions in the block would change, so what's being hashed would change. Of course, that subsequent data could also be unsolvable... etc.
I'm just curious to what we do or do not know about the solvability of blocks.
It depends on what you mean. (Review: https://en.bitcoin.it/wiki/Block_hashing_algorithm)
Is it possible that with today's difficulty target a miner can exhaust the 32-bit nonce space in the block header without "solving" the block? Yes. But then the miner can change bits in the coinbase transaction (including a field unofficially called extraNonce), change a few bits in the version, increment the timestamp and then also like you mentioned, rearrange/add/remove transactions from the body of the block candidate. So depending on how restrictive you want to be with your question, a miner will never really run out of inputs to try.
But what about the output? A block is "solved" when it's hash, interpreted as a 32-byte integer, is less than a target value (also a 32-byte integer). So what we're looking for then is:
SHA256(data) < Target
This means there are many potential solutions for a block at any given time (all the 20-or-so-byte integer values less than the current target value). If it were impossible to find one single solution in this set that would mean that SHA256 is broken and does not have the random, evenly distributed output we think it does.
(At the current difficulty) most blocks are unsolvable, but your question makes me ponder on how you think of a block
hashing will always yield a result?
Hashing always yields a result. Most of the time it is not a result that the protocol is looking for because of the difficulty. In essence you have some data X, you hash it to a number Y, and if Y is less than a globally agreed number difficulty Z then your block is solved; you may announce the block, others verify it and your solution becomes part of the chain. The race is on!
If the difficulty was set to the easiest possible factor, the solution would be found first time every time. The difficulty changes, always striving to make sure a block arrangement is solved (the hash is less than the difficulty), on average, every ten minutes.
we hit an unsolvable block
"We" don't hit blocks - there isn't some global consensus on "this is the next block everyone will work on, go try find a hash for it that is less than X" - each miner is free to build a block however it likes and hash it, in the same way that you and a friend are free to pick different lottery numbers and each try to win.
Getting back to my very first point, the miner builds a block and hashes it. It will either will solve or it won't, and luck of the draw if it just so happens that it packed those transactions however it did, and chose a nonce of whatever it did, and hashed it and got a result that is less than the difficulty then it's a solution. Quick, get it announced and claim the reward.
If one tiny bit was off about the way it randomly chose to assemble the block, it wouldn't solve; there is no solution for that block, packed that way, at the current difficulty.
All the miner will do is keep changing the block, and it does this every time it doesn't find a solve. You can make a small tweak, for example to the nonce, and re-hash. You can run through every nonce - each is as likely to win as any other. You can exhaust all the nonces, change the timestamp, and exhaust all the nonces again. You could mine so fast you can run out of nonces before timestamps so you'll have to change something else about the block in order to make good use of your hashing ability but ultimately a block built like X will hash the same way so if you build it, hash it and it doesn't work out you have to do something to change it so you get a different hash.. i.e. you have make another/different block.
As such, for any given globally agreed difficulty, most blocks are unsolvable and have to be changed - a block of transactions A and timestamp B with nonce C, is a different block to one with transactions A, timestamp B and nonce D - this may differ to how you think of a block.
nonce. In that sense of "block" we have yet to hit an unsolvable one.
A really unsolvable block will hint for a weakness in SHA-256 algorithm. SHA-256 is expected to generate evenly distributed hashes in respect to the hashed text and to any part of it (in Bitcoin block, this includes the content of the block and the nonce value).
The nonce is as big as the hash itself, so in theory using all possible values of the nonce will make a great deal of the possible hash values. Or maybe all of them if there is no collisions and I am not sure if SHA-256 will produce collisions in this case. But even if there are collisions, they (as well as the "holes") will be evenly distributed as well.
On the other hand, the nonce field is big enough so we are not in a position to try exhausting all possible values. That's why we can expect finding an unsovable block not in practice, but as a result of some theoretical effort against SHA-256.
Even if someone finds such a beast, and even if some hasher constructs such a block, the bitcoin won't fail. Other hashers will construct their blocks in different order and not necessarily including the same transactions. Their timestamps will be different as well.
Depending on the existence of now-unknown weaknesses of SHA-256, it is possible that in the future, when a higher difficulty level is reached, the rate of unsolvable blocks becomes significant. This can be either considered a fair game for the miners (at least for a while) or provoke some reform in Bitcoin.
The answers given so far are detailed and correct. A more simplified version of the answer is yes.
Unsolvable blocks can exist and (if I'm not mistaken) have already existed. However there is enough information in the block that can be changed by the miner so that this is not a problem.
