Mining logic basics...

[botnet]

Hey all, I'm trying to write an open source C# miner, but am having some trouble with the mining logic.

As I've read, a basic miner does this:

      var blockheader = DoGetWorkRPCCall();
      var target = ExtractTarget(blockheader);

      for(nonce = 0; nonce < 4294967295; nonce++)
      {
         var attempt = ModifyNonce(blockheader, nonce);
         var hash = SHA256(SHA256(attempt));
         if (hash <= target)
            ReportSolution(attempt);
      }


1) Are there really multiple solutions?  Should that instead read:

         if (hash <= target)
         {
            ReportSolution(attempt);
            break;
         }

2) if(hash <= target) - I can't figure out where GPU miners do this.   They all seem to add some magic constant to the uper 32 bits, and then check if that == 0.  Isn't that just an approximation of "< target" ? Won't that result in some incorrect solutions being reported?

3) From http://blog.ezyang.com/2011/06/the-cryptography-of-bitcoin/: the computationally hard problem is essentially a watered-down version of the first-preimage attack on a hash function. Miners are given a set of solution hashes (the hash of all zeros to a target hash), and are required to find a message with particular structure (a chain of blocks plus a nonce) that hashes to one of these hashes.    Is this accurate?  In the above code,  does DoGetWorkRPCCall get a single solution hash?  What exactly does "hash of all zeros to a target hash" mean? 

4) Lastly, is there some simple (commented?  )  non-optimized source code for a complete miner, that serves as a clear example of how this all should be working?

[1714161896]

1714161896

[1714161896]

1714161896

[1714161896]

1714161896

[1714161896]

1714161896

[1714161896]

1714161896

[1714161896]

1714161896

[ius]

1) Are there really multiple solutions?  Should that instead read:

A hash function is designed to be unpredictable (yet deterministic). There may be multiple solutions satisfying the target criteria for a given blockheader (varying the nonce) - you simply cannot tell. Some miners grab a new piece of work after finding a single solution, others check the full 'keyspace' (all 2^32 nonces).

2) if(hash <= target) - I can't figure out where GPU miners do this.   They all seem to add some magic constant to the uper 32 bits, and then check if that == 0.  Isn't that just an approximation of "< target" ? Won't that result in some incorrect solutions being reported?

The full (hash < target) check should be performed by the CPU as well. Poclbm does - found any which doesn't?

3) From http://blog.ezyang.com/2011/06/the-cryptography-of-bitcoin/: the computationally hard problem is essentially a watered-down version of the first-preimage attack on a hash function. Miners are given a set of solution hashes (the hash of all zeros to a target hash), and are required to find a message with particular structure (a chain of blocks plus a nonce) that hashes to one of these hashes.    Is this accurate?  In the above code,  does DoGetWorkRPCCall get a single solution hash?  What exactly does "hash of all zeros to a target hash" mean? 

This is oddly worded. What the author appears to be trying to convey, is that miners are given a target and have to find a 'hash of a hash' (the double SHA256) satisfying the target. The 'chain of blocks' is simply represented as the prevhash field of the block header (see Block hashing algorithm).

4) Lastly, is there some simple (commented?  )  non-optimized source code for a complete miner, that serves as a clear example of how this all should be working?

Check out pyminer

Hope this helps.

[botnet]

You have cleared up so much.  Thank you.

re:  (hash <= target), here's what I see:

phatk kernel:

   Vals[7] += H[7];

   if (Vals[7] == 0)
   {
      uint nonce = W[3];
      output[OUTPUT_SIZE] = output[(nonce >> 2) & OUTPUT_MASK] = nonce;
   }


poclbm kernel:

   H+=0x5be0cd19U;

   if (H == 0)
   {
      output[OUTPUT_SIZE] = output[nonce & OUTPUT_MASK] = nonce;
   }


This is the only check, and it's still unclear to me how this is the equivalent of (hash <= target), considering it's only the top 32 bits and it's an equality check.

[Raistlan]

I believe that those are mining *pool* clients, and mining pools have a lower difficulty than the actual mining difficulty [quite possible that the mining *pool* difficulty is just the top 32 bits are 0].

Mining pools use these lower difficulty targets to show that their miners are doing work and then use this much smaller list of possible solutions to calculate if they also match Bitcoin's target difficulty.

[just_someguy]

4) Lastly, is there some simple (commented?  )  non-optimized source code for a complete miner, that serves as a clear example of how this all should be working?

You can check out the bitcoinj solve function here:
http://code.google.com/p/bitcoinj/source/browse/trunk/src/com/google/bitcoin/core/Block.java#210

[fpgaminer]

This is the only check, and it's still unclear to me how this is the equivalent of (hash <= target), considering it's only the top 32 bits and it's an equality check.

There are two things going on here. The add before the check is simply part of SHA-256. (1)

After that, within the kernel, they are only checking to make sure the hash matches at least a Difficulty 1 target. At difficulty 1 the Target is 0x00000000_FFFFFFFF_..._FFFFFFFF, so hash <= target can be optimized to hash[7] == 0x00000000.

The reason for this, is that you want the kernel doing as little work as possible, and difficulty 1 is easy to check for (computationally). If it finds a hash that matches the difficulty 1 target, it reports it. The rest of the miner code (outside of the kernel) can do another check on the hash to see if it also meets the real target.

Also note that, for pooled mining, the target is artificially lowered to 1 anyway. These are called "shares" and miners are rewarded based on the number of shares they submit. So, in this case, the kernel's results can be directly submitted to the pool. A second target check is only needed for solo mining (2), or the rare mining pools with a difficulty over 1.

(1) Some miners may optimize this even further and combine the addition with the K constant for round 61
(2) Actually, for solo mining, you can submit the hashes anyway without checking, because bitcoind will check the hash itself and reject if it didn't meet the actual target.

[botnet]

but the kernels only report the nonce.  aren't then the hashes re-computed when checking for higher difficulties?

[fpgaminer]

aren't then the hashes re-computed when checking for higher difficulties?

Yes ... is there a problem with that?