# Can “Approximate Hashing” work in a Proof-of-Work context?

Here is a draft of an article claimed to soon appear in a peer-reviewed conference: Matthew Vilim, Uenry Duwe, Rakesh Kumar, Approximate Bitcoin Mining.

It is proposed to simplifying a SHA-256 engine (used in a Proof-of-Work context) in some way, at the expense of quite always having a correct result; and concluded that the ASIC area saved allows to implement significantly more (or/and faster or/and more power efficient) SHA-256 engines on the same area, with the potential of increasing the expected work demonstrated (translating to profit obtained by bitcoin mining gear using the design by 30% overall).

Increasing work demonstrated implies that the rate of correct SHA-256 produced increases at least as much (in a bitcoin context: twice as much, since an incorrect SHA-256 in the two chained SHA-256 characterizing a valid bitcoin will make it rejected with overwhelming certainty, yielding no profit; and odds that a SHA-256 input yields an incorrect result will be largely independent of whether it is involved with a valid bitcoin).

However, I find it hard to believe that the rate of correct SHA-256 obtained does not fall down steeply when we remove any sizable portion of whatever part of a competent ASIC design computing SHA-256 for Proof-of-Work (including the carry-look-ahead logic that is considered as the target of the area reduction).

Any well-informed opinion+explanation?

• Is there any specific reason why you didn't post this at bitcoin.stackexchange.com ? – Maarten Bodewes Feb 14 '16 at 18:02
• @MaartenBodewes: I'm interested in the validity of the principle independent of the bitcoin or crypto-currency context; say, in a general hashing as Proof-of-Work context. I'll edit to make that clearer. – fgrieu Feb 14 '16 at 18:09
• Isn't it basically just a question of whether their hardware assumptions and calculations are correct? – otus Feb 14 '16 at 20:05
• @fgrieu the error rate of SHA-256 is mentioned in the paper. Note that BitCoins obviously do not rely on previous incorrect results (if it was it would not be "embarrassingly parallel"). So you just have the error rate in the double hash calculation. – Maarten Bodewes Feb 14 '16 at 20:05
• @otus: Yes my question largely boils down to that.; except that I'm willing to consider different sources of estimation than in the article, or different uses of SHA-256 for PoW. – fgrieu Feb 14 '16 at 20:57

In the paper the following remark is probably most important:

For example, observing the frequency-error characteristics of Figure 4, the hashing cores corresponding to both approximate adders, $\operatorname{GDA}_{(1,4)}$ and $\operatorname{KSA}_{16}$, have negligible error rates at nominal frequency. Also, their nominal operating frequencies are higher than their non-approximate counterparts, $\operatorname{CLA}$ and $\operatorname{KSA}_{32}$ respectively.

It is further also said that $\operatorname{KSA}_8$ doesn't work because the error rate is so high that the SHA-256 hash is (almost) 100% certain to be wrong.

So it is clear that the double SHA-256 hash still has a large success rate, to be precise the error rate of the "core hash function" is $7.27 × 10^{−3}$ for $\operatorname{GDA}_{(1,4)}$ and $8.79 × 10^{−2}$ for $\operatorname{KSA}_{16}$. Apparently that is small enough an error rate to be good enough compared to the (estimated / calculated) increased speed and reduced die size. This is not that strange, you should just be able to multiply the success rate of the double hash $(1-\varepsilon)^2$ with the speed increase.

Note that incorrect positive results results are not much of an issue within BitCoin; if you find a hash you can very easily verify the result (a correct hash is currently found every 10 minutes, and an approximate hasher is unlikely to change that frequency).

Obviously there is also the problem with missed, correct hashes. This means that - apart from the higher speed mining - there there is also a small amount of blocks missed that should contain a bitcoin. This should however not matter much; it's not known in advance if a block contains a coin and the amount of blocks missed will be minimal.

• I now agree with everything you state (see my updated answer: I think I understood why the authors get a lower error rate than I did initially). – fgrieu Feb 15 '16 at 6:12

I do appreciate the validity and originality of the observation that even if some SHA-256 engine makes some errors because the adders it uses are not quite always yielding the correct result, it might still be usable for Proof-of-Work applications such as bitcoin mining, if the error rate remains low enough; and that this conceivably could be beneficial, by allowing to cram more SHA-256 engines for the same silicon area or cost, and/or run the thing faster, and/or make it draw less power.

However, when I compare a solution using approximate adders to a comparable one not using these, based on the article's own numbers, I'm far from matching the draft article's abstract:

Our results show that approximation has the potential to increase mining profits by $30\%$.

By the numbers in table 2, the delay⋅area product of the SHA-256 implementation using the KSA16 adder is only $1-82744/90769\approx8.8\%$ below that of the next best solution with an adder making no error, KSA32. When we compare against that baseline, which is the Right Thing to do, no usable solution proposed gains more from a delay⋅area standpoint (KSA8 is acknowledged to almost never gives a correct SHA-256 result).

Update: Also, when we take into account the fact that the whole circuit using KSA16 draws more power to run at higher speed than its counterpart using KSA32 (as acknowledged in table 2), its operational benefits taking into account power cost must be somewhat lower than estimated on the sole basis of delay⋅area.

And then, this potential saving has the drawback that some of the hashes are wrong, thus (in most PoW context including bitcoin), anything involving these is worthless.

It is said (above equation 4) [obvious correction mine]

The sensitivity derives from three CPA modulo 32-bit additions each iteration, so there will be $64\cdot3=192$ additions in a single round of SHA-256".

An apparent problem is that there are more than $192$ additions of two 32-bit operands in a single SHA-256. Looking at the "Algorithm 2" pseudocode, I count $48\cdot3$ at line 7; $64\cdot4$ at line 10; $64$ at line 11; $64$ at line 13; $64$ at line 15; $8$ at lines 17 to 20; for a total of $600$ additions of two 32-bit operands per SHA-256.

Performing all the 32-bit additions in SHA-256 by adder KSA16 (the only one giving savings per the above analysis) with stated error rate of $4.6\times10^{-5}$ (taken from table 1) thus makes $1-(1-4.6\times10^{-5})^{600}\approx2.7\%$ of the SHA-256 computations invalid; thus in a bitcoin context $5.4\%$ of the findings valueless. Thus the overall potential benefit would be down from about $8.8\%$ to about $6.1\%$ for SHA-256, or $3.4\%$ for bitcoin mining.

Update: on second thought, the authors are right counting towards the error rate only 3 adders out of 10 of those involved in the round loop, if they optimize only these few adders in the timing-critical path, which would make a lot of sense. This change of a limited portion of the adders will reap low size benefit, but still allow faster speed for the whole circuit. That qualitatively matches the numbers for delay and area in Tables 1 and 2, where we see that most of the benefit of using KSA16 compared to KSA32 is that it allows a faster clock cycle (at the expense of power drawn).

My conclusion is that the article investigates various designs of adders for ASICs performing SHA-256 in PoW systems like bitcoin; rightly observes that it is possible to significantly improve an existing design, by virtue of speeding it up in its timing-critical path, through replacement of some of its basic Ripple Carry Adders with more appropriate ones (larger but faster) still giving exact results; reports some marginal extra improvement (mostly due to further speedup) with another implementation using approximate adders; but do not give any strong argument beyond this anecdotal evidence towards the claim that approximate adders can give sizable overall benefit in hash-based PoW systems.

• Eh, did you just use this platform to attack the outcome of a scientific paper? Or did you really just find this out after asking the question? – Maarten Bodewes Feb 14 '16 at 23:20
• @Maarten Bodewes: I hit the thing reading Slashdot, wondered if that was believable, could not debunk the claim in half an hour, and asked the question with no precise argument against the claim. I have no connection (to my knowledge) or business/academic interest with that scientific paper, its authors, their institution, the subject, or bitcoin mining; the closest thing is that I had training on logic design decades ago, and vaguely remember Ripple Carry Adders versus Carry Lookhead Adders. – fgrieu Feb 15 '16 at 5:39
• The latter then, thought it was a bit curious. It would be interesting to know what the authors think of this. According to their own paper they didn't test their findings in the field, so if they made any miscalculations then those will be reflected in the conclusions. – Maarten Bodewes Feb 15 '16 at 8:58