0
$\begingroup$

Imagine a large array (Megabytes) that is virtually empty, i.e. contains 0 in almost all locations. But also imagine there's 1000 pseudo random locations that contain a pseudo random byte. There is no correlation between bytes nor locations. So on average, there is a random byte > 1000 bytes apart. Then the entire array is hashed with a Merkle–Damgård type hash.

Is there a way to speed up the overall hashing time by knowing that the likely values ahead are 0? Certainly most of the time, the next input block will be all 0. Many times over. Can this statistical predictability be leveraged for speed?

Improve this question
$\endgroup$
2
  • $\begingroup$ Is "Merkle–Damgård" a hard requirement? Because if instead we use an adequate hash tree, then serious savings are possible (including when keeping a compression function like that of SHA-256 or SHA-512). $\endgroup$
    – fgrieu ♦
    Aug 11 at 14:50
  • $\begingroup$ @fgrieu I was considering SHA-256 actually... $\endgroup$
    – Paul Uszak
    Aug 11 at 16:07

1 Answer 1

Reset to default
1
$\begingroup$

Can this statistical predictability be leveraged for speed?

Well, both SHA-256 and SHA-512 apply 'message scheduling' to expand the 64/128 [1] byte message block to a 256/640 byte sequence (or 64/80 word sequence); this message scheduling isn't that expensive, but it isn't free. If you were to check the next block and see all the bytes are 0, you could either use a fixed 256/640 byte sequence (what the block of all 0's would expand to), or use an alternative hash compression implementation which skips stirring in the words from the message scheduling (because I believe that, in both cases, the message scheduling expands an all-0 message block into an all-0's word sequence).

I suspect that testing the bytes, and doing a conditional jump based on that would, on average, be measurably faster (assuming that most of the message blocks do consist of 'all 0s')

[1]: By 64/128, I mean "64 bytes in the case of SHA-256 and 128 bytes in the case of SHA-512"

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, statistically most of the message blocks do consist of 'all 0s'. $\endgroup$
    – Paul Uszak
    Aug 13 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.