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.
Cheating by the server, by way of the pool operator fraudulently granting himself extra shares, is also not addressed, requiring the clients to trust the operator.
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 approach BitPenny uses is to offer a flat-payout for each share that is solved. The service is operated for-profit and thus self-insures against variances from the percent of generation proceeds retained.
DeepBit offers both a proportional reward distribution as well as a fixed-rate pay-per-share mode.
The slush approach uses a lot fewer 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 slush 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 approach 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 likely to disappear later due to transaction fees. (E.g., if you have a transaction with 0.052 in your wallet, and you later send .05 to someone, your .002 will disappear. This is because the current schedule of fees requires a fee of .01 if any transaction output is less than .01. The client thus decides, correctly, that it would be cheaper to just throw away the .002 to tx fee, than it would to contribute an extra .01 as a fee, to keep the .002).
Puddinpop miners receive coins directly, which eliminates the delay in receiving earnings that is required on slush's server. However, bitcoind is incapable of detecting generation transactions, so earnings sent directly to MyBitcoin, MtGox, etc. will disappear.
This all seems to point to the slush approach being the better one. Its only downside is that the server software is not open source, while the puddinpop software is.