Pooled mining is an approach where multiple generating clients contribute to the generation of a block, and then split the block reward according the contributed processing power. Pooled mining effectively reduces the granularity of the block generation reward, spreading it out more smoothly over time.
With increasing generation difficulty, mining with lower-performance devices can take a very long time before block generation, on average. For example, with a mining speed of 1000 Khps, at a difficulty of 14484 (which was in effect at the end of December, 2010), the average time to generate a block is almost 2 years.
To provide a more smooth incentive to lower-performance miners, several pooled miners, using different approaches, have been created. With a mining pool, a lot of different people contribute to generating a block, and the reward is then split among them according to their processing contribution. This way, instead of waiting for years to generate 50btc in a block, a smaller miner may get a fraction of a bitcoin on a more regular basis.
A share is awarded by the mining pool to the clients who present a valid proof of work of the same type as the proof of work that is used for creating blocks, but of lesser complexity, so that it requires less time on average to generate.
Pooled mining approaches
The problem with pooled mining is that steps must be taken to prevent cheating by the clients and the server. Currently there are two different approaches used.
The slush approach
Bitcoin Pooled Mining (BPM), sometimes referred to as "slush's pool", follows a score-based method. Older shares (from beginning of the round) has lower weight than newer shares, which demotivate cheater from switching between pools inside one round.
The puddinpop approach
(As of February, 2011, there are no puddinpop pools running.)
Another approach is the 'metahash' technique, used by puddinpop's remote miner. Clients generate hashes, and also submit 'metahashes', which are hashes of a large chunk of generated hashes. The server checks that the metahashes are correct (in a round-robin fashion, picking up a metahash from a client that hasn't been checked on the longest), thus preventing clients from simply claiming that they have done work without actually doing the work. The withholding of good blocks by the clients is prevented via the server being in possession of the private key, just as in the previous approach. Rewards are distributed based on the number of metahashes submitted by the clients.
The generated blocks contain multiple keys in the generation transaction, giving fractional bitcoin amounts to each key, in proportion to their hashing contribution for that block.
The BitPenny approach
The BitPenny approach is to offer an instant, flat payout for each share that is solved. The payout is offered from the pool's existing balance and can therefore be withdrawn immediately, without waiting for a block to be solved or confirmed. The possibility of cheating by the pool operator and by timing attacks is thus completely eliminated.
This method results in the least possible variance for miners while transferring all risk to the pool operator. The resulting possibility of loss for the server is offset by setting the payout lower than the full expected value.
Luke-Jr's approach ("Eligius")
Luke came up with a third approach borrowing strengths from the earlier two. Like slush's approach, miners submit proofs-of-work to earn shares. Like puddinpop's approach, the pool pays out immediately via block generation. When distributing block rewards, it is divided equally among all shares since the last valid block. Unlike any preexisting pool approach, this means that the shares contributed toward orphaned blocks are recycled into the next block's shares. In order to spare participating miners from transaction fees, rewards are only paid out if a miner has earned at least 1 BTC. If the amount owed is less, it will be added to the earnings of a later block (which may then total over 1 BTC). If a miner does not submit a share for over a week, the pool sends any balance remaining, regardless of its size.
The cooperative mining approach (slush and Luke-Jr) uses a lot less resources on the pool server, since rather than continuously checking metahashes, all that has to be checked is the validity of submitted shares. The number of shares sent can be adjusted by adjusting the artificial difficulty level.
Further, the cooperative mining approach allows the clients to use existing miners without any modification, while the puddinpop approach requires the custom pool miner, which are as of now not as efficient on GPU mining as the existing GPU miners.
Additionally, the puddinpop and Luke-Jr approaches of distributing the earnings by way of including precise sub-cent amounts in the generation transaction for the participants, results in the presence of sub-cent bitcoin amounts in your wallet, which are liable to disappear (as unnecessary fees) later due to a bug in old (before 0.3.21) bitcoin nodes. (E.g., if you have a transaction with 0.052 in your wallet, and you later send .05 to someone, your .002 will disappear.).
Puddinpop and Luke-Jr miners receive coins directly, which eliminates the delay in receiving earnings that is required on slush-based mining servers. However, earnings sent directly to some services like MyBitcoin and MtGox will not be accounted for.