How do pool operators do their hashing?

Question

For every "getwork" served by the pool, a Merkle root must be calculated for a block. The run time of SHA-256 is proportional to the number of "chunks" of 256 bits, and a typical block will have thousands of these chunks (a block header has just has three, after preprocessing). So the pool operator will need hashing power in the Mhash/sec range, roughly. Am I right so far?

The individual miners need much more hashing power, but in a simpler form: here's a three chunk preprocessed block header; hash it with each of 0000_0000x through FFFF_FFFFx in the nonce field. If hashing engines specialize on that simplicity, to make them cheaper and/or faster, then they don't work so well for the pool operators.

So if I'm a pool operator, or a solo miner, and I need to generate millions of Merkle roots, what are my options? Do the hashing engines (CPU/GPU/FPGA/ASIC) have an API I can use?

Answer 1

A pool will generally create a unique merkle root for each getwork request by a miner. If it accepts difficulty 1 shares, the miner can spend an average of about 4,000 Mega-hashes on that block (and will earn an average of 1 share per getwork).

To create a block header for each miner, the pool operator changes some unique information in the first (generation) transaction of the block, and then rehashes the block to create the merkle root. If done naively, this will take O(N log N) sha256 hashes (where N is the number of transactions in the block being mined). By saving some information from computing the last merkle root, you can recalculate a change in the generation transaction with only O(log N) hashes.

With hundreds of transactions per block the ratio of hashes performed by the pool operator and the miners is over 100 million to 1.

For an even greater savings, pools can accept a getblocktemplate api request instead of a getwork request. This mode allows the miner to generate his own block headers and mine for an average of 10 minutes before needing to be refreshed by the pool.

Answer 2

One compute-intensive part of the server work is creating new merkle roots. As mckoss mentions this becomes a lot faster if you only recalculate the merkle branch that is changed by the new generation transaction instead of recalculating the entire merkle tree.

The other compute-intensive part of the server's job is verifying the proofs of work that are later sent in. In general this means hashing two SHA-256 chunks and verifying the result against the difficulty. But if there are multiple proofs of work with the same merkle root then you could calculate the midstate once, and then just hash one SHA-256 chunk for each proof of work you want to verify. Just like clients do with rollntime.

So every new merkle root is work to generate, and also creates more work later by needing a new midstate to be calculated.

BitMinter makes use of rolling the ntime field on the server as well as in the client. Every time the wall clock ticks forward one second, you update the ntime field of the block data with a new timestamp. Then you can reuse all the merkle roots and midstates you have from the previous second.

This saves a massive amount of work on the server, and it is how BitMinter could run with low load on a single server with 2-3 TH/s of hashpower while some (not well optimized) pools needed a new server for every 300 GH/s of hashpower.

Since then such optimizations have become less important. More clients started supporting rollntime. Servers and clients started using work difficulty above 1, meaning much less work had to be verified on the server. And then there are the new protocols to replace getwork: Stratum and GBT (getblocktemplate). With these protocols the server just generates a template which is very cheap to generate, then the clients do the heavier part of creating work based on the template.

I still think it's a good idea for clients to use the ntime trick to reuse merkle roots and midstates, which allows midstate reuse on the server side as well, although this is no longer a big deal.