Given the current hashing powers, what do pools actually do in practice? Given the current hashing powers, what do pools actually do in practice to find a block?

Ok, so here is my thinking, please correct me if I'm wrong anywhere:


Here's the format of the block header, the thing which is actually hashed:



  version(4b) + prevBlockHash(32b) + merkleHash(32b) + ctimestamp(4b) +
  ctarget(4b) + nonce(4b);



So, canonically, what miners do is going through all the possible values of the last NONCE(4 bytes).
If we treat that as unsigned int, the range would be 0-4294967295.
Right now you can buy a 2Ghs miner for &lt; $100.
Given that you have something that can hash 2GHs(very cheap solution, I'm not even talking about THs systems that pools reportedly have), you could bruteforce through the range of 0:4294967295 in less than 3 seconds.


So, the question is, what keeps mining in that ~10min period?

My suspicion is that its not that much of a problem to find a nonce anymore, its more a problem to find the proper block that will actually have a nonce.

If that is true: 

a) what do miners do in practice, play around with the timestamp, or generate some transactions to change the merkle root?

b) is there any mathematical proof that such a block will ever be found? I mean, bitcoin not getting stuck, because of some unfortunate block having such a bad coincidence of bits that will endup blocking the result from getting enough zeros in the end to fit the target(I'm asking about mathematical proof that it is impossible).
For a given combination of

version(4b) + prevBlockHash(32b) + merkleHash(32b) + ctimestamp(4b) + ctarget(4b),

There is no guarantee that there will be a valid nonce. There usually isn't - the probability that there will be is 1 divided by the difficulty, which is currently 9 billion. So miners try different combinations, try the nonce range for each, until they find a valid solution.

a) The most general method is to change extraneous data in the generation transaction to change the Merkle root. Currently, to reduce communication overhead between the pool and miners, a method such as GBT is used, where the miner gets a block template and can fill in the generation transaction himself.

b) No; hashing, like much of the core cryptographic primitives, is kind of a "dark art" - there's little in the way of proof that it all works. Let's say you fix just the prevBlockHash, there is no proof that you can fill in the other details to obtain a valid hash. However, if hash functions behave more or less the way we think they do, it is extremely unlikely there will be no solution.