How does a miner perform hashing?

Question

I'm trying to walk my way through the process by which a miner hashes.

Let's say the getwork request returns a data field of:

0000000244de6ceba49e1c8d438c0d8c584eefd9c8590545bfdfbf380000025c00000000fb3a091de1b4bbe5dc7acfe6bdacbc3fc3bb09bf1030adef8e2854db1b6ac42f5075c0051a057e08456c6f69000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000

As far as I understand, the first step is to calculate the midstate. To do this, we first take the first half of the data string:

0000000244de6ceba49e1c8d438c0d8c584eefd9c8590545bfdfbf380000025c00000000fb3a091de1b4bbe5dc7acfe6bdacbc3fc3bb09bf1030adef8e2854db

We then reverse the endianness of each 32-bit unsigned int (represented as 8 hex digits in the string), yielding:

02000000eb6cde448d1c9ea48c0d8c43d9ef4e58450559c838bfdfbf5c020000000000001d093afbe5bbb4e1e6cf7adc3fbcacbdbf09bbc3efad3010db54288e

Next we transform this into sixteen 32-bit unsigned ints:

33554432, 3949780548, 2367463076, 2349698115, 3656339032, 1157978568, 952098751, 1543634944, 0, 487144187, 3854284001, 3872357084, 1069329597, 3205086147, 4021104656, 3679725710

We then input this int array into SHA-256's internal function, with the second input being the eight 32-bit numbers given on page 13 of the SHA-256 specs.

The output of this preliminary hash yields the following eight 32-bit ints as our midstate:

3045448562, 361056177, 1940413978, 3803584651, 1661283772, 3478943551, 2906109005, 300125848

From this point on, I'm not sure how correct the steps are. Corrections are greatly appreciated!

Next, we look at the second half of the input string:

1b6ac42f5075c0051a057e08456c6f69000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000

Once again, we reverse the endianness, as everything is an 8-character hex string representing 32-bit unsigned ints:

2fc46a1b05c07550087e051a696f6c45800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000280

Now, we break this up into sixteen 32-bit ints: 801401371, 96499024, 142476570, 1768909893, 2147483648, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 640

The fifth number (21474836481) should be the nonce, according to this description.

(Why isn't this nonce zero?)

Now, starting at the given nonce, we use the SHA-256 function to hash the sixteen 32-bit ints from the second half of the data, using the midstate as the other eight int inputs. This yields: 3993002029, 2278477219, 3977673643, 191934125, 2075691039, 4115259165, 601235791, 2598049038

Now, what do I use as inputs for the second hash function in the "double-hash"? Or did calculating the midstate count as the first hash computation?

And when the nonce overflows, should I submit another getwork request or wait until I've checked the nonces in the range of [0, original_nonce_value)? (Assuming my analysis that the given nonce is 21474836481 is correct?)

Lastly, if our target value from the getwork request is:

ffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000

We need to switch the endianness of this value, yielding:

00000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffff

And then we convert this to eight 32-bit unsigned ints, yielding: 0, 4294967295, 4294967295, 4294967295, 4294967295, 4294967295, 4294967295, 4294967295

And I believe after the second SHA-256 hash we should have eight 32-bit unsigned ints. Lastly, we should compare these eight output ints against our eight target ints (from left to right in the array, so comparing output[0] against the target's 0, then output[1] against 4294967295, etc.) and if our output is less than the target, we convert our eight int values to hex strings, switch the endianness, concatenate them in the same order (output[0]'s hex string is the first set of eight characters), and submit it back to the pool server in a getwork completion POST.

How much of this is correct, and where am I misinterpreting the protocol?

All help is appreciated; thanks so much!

Answer 1

This question is a complicated one, but I'll see what I can do to answer it. Also, I won't try tackling the issue of endianness, as in the case of Bitcoin it gives me a headache...

First, lets see what we have in a block header given to us by getwork. Lets take the Genesis Block for an example.

01000000 - version
0000000000000000000000000000000000000000000000000000000000000000 - prev block
3BA3EDFD7A7B12B27AC72C3E67768F617FC81BC3888A51323A9FB8AA4B1E5E4A - merkle root
29AB5F49 - timestamp
FFFF001D - bits
00000000 - nonce (it will be set to 1DAC2B7C later)
00 - number of transactions (always 0, this is the block header)
0000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000 - padding

In order to calculate the midstate, we split the header into two parts that are accepted by SHA algorithm (64 bytes each):

0100000000000000000000000000000000000000000000000000000000000000000000003BA3EDFD7A7B12B27AC72C3E67768F617FC81BC3888A51323A9FB8AA
4B1E5E4A29AB5F49FFFF001D00000000000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000

We load the first part into the SHA algorithm. We take save this state for later use (midstate) (sorry for lack of examples, but I don't have my hashing algorithms on hand). Then we load the second part into the SHA algorithm. We read the output, this is the first hash. We take that output, plug it back to a new input, and get its result. That is the second hash. Assuming we got the correct nonce (in our case - 1DAC2B7C), our result should look something like this:

000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f

and compare it to our target:

00000000ffff0000000000000000000000000000000000000000000000000000

Taken as a number, which is bigger? The target. This means that we have the correct nonce, and we can submit our full header as the result. Profit!

From what I understand, you tried to break up the resulting numbers too much, instead of operating on really big numbers like Bitcoin appears to be doing. Then again, endianness is also a big problem with the protocol and what not...

I hope this answers your problem.