Theoretical minimum # of logic operations to perform double iterated SHA256?

[Geremia]

It seems obvious that reversible computing is the future for Bitcoin mining ASICs, and could be the first major commercial application of the technology.

From the Reddit page you linked: "No. Hashing by definition is irreversible and results in loss of information and therefore increased entropy."

[1714256939]

1714256939

[1714256939]

1714256939

[1714256939]

1714256939

[Peter R]

It seems obvious that reversible computing is the future for Bitcoin mining ASICs, and could be the first major commercial application of the technology.

From the Reddit page you linked: "No. Hashing by definition is irreversible and results in loss of information and therefore increased entropy."

It's irreversible because the normal circuit for SHA256d discards information (and thus requires an energy input to move in the forward direction).  For example, we hash the 640 bit blockheader to get a 256 bit digest; there's no way to work backwards with only 256 bits to reconstruct the 640 bit input (the output contains less information than the input). But I don't see why there wouldn't be another circuit that performs the hash function in a reversible way, by tracking all the information that is normally discarded.  This circuit would output the hash value PLUS enough of other information that one could work backwards to reconstruct the inputs.

[solex]

It seems obvious that reversible computing is the future for Bitcoin mining ASICs, and could be the first major commercial application of the technology.

From the Reddit page you linked: "No. Hashing by definition is irreversible and results in loss of information and therefore increased entropy."

It's irreversible because the normal circuit for SHA256d discards information (and thus requires an energy input to move in the forward direction).  For example, we hash the 640 bit blockheader to get a 256 bit digest; there's no way to work backwards with only 256 bits to reconstruct the 640 bit input (the output contains less information than the input). But I don't see why there wouldn't be another circuit that performs the hash function in a reversible way, by tracking all the information that is normally discarded.  This circuit would output the hash value PLUS enough of other information that one could work backwards to reconstruct the inputs.

Yes, that's what I was thinking. The final hash is irreversible, but not if the results of each step are known. The efficiency is gained by recycling logic gate inputs as they occur. Certainly a challenging design problem though.

[Cryddit]

As I understand it, (and I could be wrong here) what is actually absolutely required to spend energy for, is the output.  IOW, you could at least in theory design a system that answers the one-bit question, "is there a nonce meeting the difficulty target within <some range of nonces>" by actually spending the energy to write exactly one bit.  Everything else can be reversible, so the greater the amount of computation you can do without any external effects required the more of it can be done "free" (albeit at ridiculously high complexity) but no matter what, you have to write the output. 

[DeathAndTaxes]

Indeed. It seems obvious that reversible computing is the future for Bitcoin mining ASICs, and could be the first major commercial application of the technology. I have been looking forward to seeing informed comment on it.

Maybe in 50-80 years.  Nobody has successfully implemented a 32 bit adder using reversible computing.  If you think quantum computing is in its infancy well reversible computing hasn't even been born yet.  Despite the theory being published in 1973 to date there has been pretty much no practical demonstration of implementing the most trivial of reversible circuits.

Part of the problem is that the circuit must be very insulated from the outside environment in order to remain reversible.  To date this means a lot of very expensive near zero superconductors but even esoteric problems like a stray cosmic ray striking your circuit can leak to large scale leakage.  To say the future of mining obviously involves reversible computing is sort of like suggesting Honda should stop researching hybrids and start researching hyperdrives because obviously on a long enough timeline some form of faster than light travel is an obvious requirement for a spacefaring civilization. There is a lot of potential improvement in classical computing.  We something like a million times less efficient than the thermodynamic limit.  

Also as Peter points out there is still an energy time tradeoff.  If I gave you today a reversible miner which ran on near zero energy but had a hardware cost $10,000 of per GH would you be interested?   If the technology is more expensive on an amortized per hash total lifecycle cost than classical computing well it doesn't really matter how little energy it uses.

[DeathAndTaxes]

As I understand it, (and I could be wrong here) what is actually absolutely required to spend energy for, is the output.  IOW, you could at least in theory design a system that answers the one-bit question, "is there a nonce meeting the difficulty target within <some range of nonces>" by actually spending the energy to write exactly one bit.  Everything else can be reversible, so the greater the amount of computation you can do without any external effects required the more of it can be done "free" (albeit at ridiculously high complexity) but no matter what, you have to write the output.  

In theory yes but even proponents of reversible computing don't believe leakage will be that low.  There is the energy cost required to perfectly isolate the circuit from the outside environment so even if your raw circuit was perfectly reversible the total system energy cost will be much higher.

Also theory is just theory.  In theory it is possible for someone to make a miner with 5,000,000 G/J (instead of 1 G/J) using plain boring classical computing.  Granted you aren't going to do it with 20nm silicon but in theory it can be done.  Now 5,000,0000 PH/s well we know that is not possible without a massive reduction in the "work" needed to complete a single hash.  "In theory" is a nice way of saying nobody has proved it impossible.

[2112]

Cryddit gave an estimation on the number of standard gate building blocks required for a Bitcoin ASIC (adders, logic gates)
However, adders require more space than OR gates, so generally the number of gates will be dominated by the number of adders. Also adders can be implemented in several ways,  with different delay/space trade-offs, so even if there could be a theoretical minimum number of gates, practically all implementations would use much more to reduce the delay.

More interesting, you can:

- Compute SHA^2 approximately, and get a better practically good SHA^2 ASIC for mining.
See https://bitslog.wordpress.com/2015/02/17/faster-sha-256-asics-using-carry-reduced-adders.

- Compute SHA^2 asynchronously (e.g. using asynchronous adders)

Last, it has not been proven that performing a complete SHA^2 evaluation is required on average to check that a changing header has a SHA^2 hash that is below the target value. In fact, several widely known optimizations have disprove it.

It is hard to guess what was the original intention of the question: mathematical/algebraic minimum or some sort of minimum for a defined implementation technology.

The typical goal for a implementation using silicon CMOS process would be timing closure, i.e. minimizing the time to compute the result. This is the reason why everyone is using carry-look-ahead adders that add 32 bits in parallel in a single clock cycle.

The other approach would be to use serial adders that add 32 bits in 32 clock cycles. Such an adder is just a pair of XOR gates. The problem with this approach is that the resultant clock rate is too high for the practical silicon-based semiconductor manufacturing processes. But if somebody considers e.g. GaAs manufacturing then the very deeply pipelined serial implementation is a viable alternative.

[Geremia]

It is hard to guess what was the original intention of the question: mathematical/algebraic minimum or some sort of minimum for a defined implementation technology.

either

The typical goal for a implementation using silicon CMOS process would be timing closure, i.e. minimizing the time to compute the result. This is the reason why everyone is using carry-look-ahead adders that add 32 bits in parallel in a single clock cycle.

The other approach would be to use serial adders that add 32 bits in 32 clock cycles. Such an adder is just a pair of XOR gates. The problem with this approach is that the resultant clock rate is too high for the practical silicon-based semiconductor manufacturing processes. But if somebody considers e.g. GaAs manufacturing then the very deeply pipelined serial implementation is a viable alternative.

interesting
thanks

[Geremia]

that's a great diagram

These blog posts were very helpful for me:
http://www.righto.com/2014/09/mining-bitcoin-with-pencil-and-paper.html
http://www.righto.com/2014/02/bitcoin-mining-hard-way-algorithms.html

Very impressive that he shows SHA-256 with pen and pencil!

[smolen]

SHA256D is an interesting choice, actually; usually you don't see it except in a context where someone is worried about an extension attack - which doesn't really apply to the way Bitcoin uses it.

Bitcoin mining would be vulnerable to "constant elimination attack" were plain SHA256 used instead of double one.

EDIT:
Geremia, take a look at Bitfury trick
This line saves some memory at the expense of extra computation:

Code:

ds <= er - cr;