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?
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.