In the mining process, everytime a block has to be confirmed, a certain hash with an incremental nonce is generated: If the nonce is a 32 bit number it can assume a value between 0 and 2^32 - 1. It gives about max 4.000.000.000 attempts on the same block to find the right hash. But if the target begins with 13 zeroes why isn't 2^32 too little to find the correct hash?
1 Answer
First of all, when 1 second has passed, the miner can just increment the timestamp in the header. This already gives us 4 Ghash/s rather than 4 GHash/block.
When this is not enough, and the nonce range is exhausted before a second has passed, the miner builds a new proposed block with a hash to search through. Specifically, the very first transaction in the block (the coinbase, which also receives the subsidy and fees) has a 100-byte area that essentially contains arbitrary data. So miners use this area as an 'extra nonce'.