Go, midstate SHA-256 hash

Question

Having 128 bytes of data, for example:

00000001c570c4764aadb3f09895619f549000b8b51a789e7f58ea750000709700000000103ca064f8c76c390683f8203043e91466a7fcc40e6ebc428fbcc2d89b574a864db8345b1b00b5ac00000000000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000

And wanting to perform SHA-256 hash on it, one would have to separate it into two 64 bytes of data and hash them individually before hashing the results together. If one was to often change some bits in the second half of the data, one could simplify the calculations and hash the first half of the data only once. How would one do that in Google Go? I tried calling

func SingleSHA(b []byte)([]byte){
    var h hash.Hash = sha256.New()
    h.Write(b)
    return h.Sum()
}

But instead of the proper answer

e772fc6964e7b06d8f855a6166353e48b2562de4ad037abc889294cea8ed1070

I got

12E84A43CBC7689AE9916A30E1AA0F3CA12146CBF886B60103AEC21A5CFAA268

When discussing the matter on Bitcoin forum, someone mentioned that there could be some problems with getting that midstate hash.

How do I calculate a midstate SHA-256 hash in Google Go?

Answer 1

Bitcoin-related byte operations are a bit tricky, as they tend to switch endianness at a whim. First of, we take the initial []byte array representing

00000001c570c4764aadb3f09895619f549000b8b51a789e7f58ea750000709700000000103ca064f8c76c390683f8203043e91466a7fcc40e6ebc428fbcc2d89b574a864db8345b1b00b5ac00000000000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000

Then, we separate out the first half of the array, obtaining:

00000001c570c4764aadb3f09895619f549000b8b51a789e7f58ea750000709700000000103ca06 4f8c76c390683f8203043e91466a7fcc40e6ebc428fbcc2d8

After that, we need to swap some bytes around. We reverse the order of bytes in every slice of 4 bytes, thusly obtaining:

0100000076C470C5F0B3AD4A9F619598B80090549E781AB575EA587F977000000000000064A03C10396CC7F820F8830614E94330C4FCA76642BC6E0ED8C2BC8F

And that is the array we will be using for calculating the midstate. Now, we need to alter the file hash.go, adding to type Hash interface:

Midstate() []byte

And change the file sha256.go, adding this function:

func (d *digest) Midstate() []byte {
    var answer []byte
    for i:=0;i<len(d.h);i++{
        answer=append(answer[:], Uint322Hex(d.h[i])...)
    }
    return answer
}

Where Uint322Hex converts an uint32 variable into a []byte variable. Having all that, we can call:

var h BitSHA.Hash = BitSHA.New()
h.Write(Str2Hex("0100000076C470C5F0B3AD4A9F619598B80090549E781AB575EA587F977000000000000064A03C10396CC7F820F8830614E94330C4FCA76642BC6E0ED8C2BC8F"))
log.Printf("%X", h.Midstate())

Where Str2Hex turns a string into []byte. The result is:

69FC72E76DB0E764615A858F483E3566E42D56B2BC7A03ADCE9492887010EDA8

Remembering the proper answer:

e772fc6964e7b06d8f855a6166353e48b2562de4ad037abc889294cea8ed1070

We can compare them:

69FC72E7 6DB0E764 615A858F 483E3566 E42D56B2 BC7A03AD CE949288 7010EDA8
e772fc69 64e7b06d 8f855a61 66353e48 b2562de4 ad037abc 889294ce a8ed1070

So we can see that we just need to swap the bytes around a bit in each slice of 4 bytes and we will have the proper "midstate" used by Bitcoin pools and miners (until it will no longer be needed due to being deprecated).

Answer 2

The Go code you have is the right way to compute sha256 of a stream of bytes.

Most likely the answer is that what you want to do is not sha256. Specifically:

one would have to separate it into two 64 bits of data and hash them individually before hashing the results together. If one was to often change some bits in the second half of the data, one could simplify the calculations and hash the first half of the data only once.

is not a valid way to calculate sha256 (read http://doc.golang.org/src/pkg/crypto/sha256/sha256.go to e.g. see that sha256 does its work on blocks of data, which must be padded etc.).

The algorithm you described calculates something, but not sha256.

Since you know the expected value you presumably have some reference implementation of your algorithm in another language so just do a line-by-line port to Go.

Finally, it's a dubious optimization in any case. 128 bits is 16 bytes. Hashing cost is usually proportional to the size of data. At 16 bytes, the cost is so small that the additional work of trying to be clever by splitting data in 8 byte parts will likely cost more than what you saved.

Answer 3

In sha256.go, at the start of function Sum() the implementation is making a copy of the SHA256 state. The underlying datatype of SHA256 (struct digest) is private to the sha256 package.

I would suggest to make your own private copy of the sha256.go file (it is a small file). Then add a Copy() function to save the current state of the digest:

func (d *digest) Copy() hash.Hash {
    d_copy := *d
    return &d_copy
}

Then simply call the Copy() function to save a midstate SHA256 hash.

Answer 4

I ran two Go benchmarks on your 128 bytes of data, using an Intel i5 2.70 GHz CPU. First, 1,000 times, I wrote all 128 bytes to the SHA256 hash and read the sum, which took a total of about 9,285,000 nanoseconds. Second, I wrote the first 64 bytes to the SHA256 hash once and then, 1,000 times, I wrote the second 64 bytes to a copy of the SHA256 hash and read the sum, which took a total of about 6,492,371 nanoseconds. The second benchmark, which assumed the first 64 bytes are invariant, ran in 30% less time than the first benchmark.

Using the first method, you could calculate about 9,305,331,179 SHA256 128-byte sums per day before buying a faster CPU. Using the second method, you could calculate 13,307,927,103 SHA256 128-byte sums per day, assuming the first 64 bytes are invariant 1,000 times in a row, before buying a faster CPU. How many SHA256 128-byte sums per day do you need to calculate? For how many SHA256 128-byte sums per day are the first 64 bytes are invariant?

What benchmarks did you run and what were the results?