Theoretical minimum # of logic operations to perform double iterated SHA256? - page 2.

btchris

hero member

Activity: 672

Merit: 504

a.k.a. gurnec on GitHub

Quote from: Cryddit on April 18, 2015, 11:04:13 PM

SHA256 is sixty-four rounds comprising

384 32-bit additions (6 per round)
320 32-bit ORs (5 per round)
448 32-bit XORs (7 per round)

And a bunch of bit shifts, but bit shifts are free on an ASIC.

Are you sure of those numbers? For example in a naive implementation, I'm counting 48*3 + 64*7 + 8 = 600 additions for a single SHA-256 block. There could be better ways of doing SHA-256 that don't naively follow the standard though... I wouldn't know....

Meni Rosenfeld

donator

Activity: 2058

Merit: 1054

You should read up on https://en.wikipedia.org/wiki/Reversible_computing. You can in theory construct your logic gates in a way that will not erase information, and make arbitrarily long computations with a bounded energy expenditure. The notion that the Landauer's principle places a lower limit on the energy cost of computation is a myth.

InceptionCoin

member

Activity: 108

Merit: 10

Quote from: Geremia on April 19, 2015, 01:05:43 AM

Quote from: Cryddit on April 19, 2015, 12:35:36 AM

But on an ASIC, Bit shifts are not logic operations. Not even gates. They're just circuit traces that go at an angle instead of directly straight into the next array of gates.

I'm sorry, but I'm not too familiar with circuit design. What do you mean by "circuit traces"?

I will try to explain it simplier than shorena:
imagine you have number 10 in 8bit integer, it means
0 0 0 0 1 0 1 0
Now, you need to shift right it, to get
0 0 0 0 0 1 0 1
In the cpu register you will put number from first bit to second bit, from second to third etc, but in asic you can connect(actualy you shouldn't but nevermind) registers like here:

Code:

_ _ _ _ _ _ _ _
\ \ \ \ \ \ \
— — — — — — — —

And you get shifted number without replacing bits.

shorena

copper member

Activity: 1498

Merit: 1528

No I dont escrow anymore.

Quote from: Geremia on April 19, 2015, 01:05:43 AM

Quote from: Cryddit on April 19, 2015, 12:35:36 AM

But on an ASIC, Bit shifts are not logic operations. Not even gates. They're just circuit traces that go at an angle instead of directly straight into the next array of gates.

I'm sorry, but I'm not too familiar with circuit design. What do you mean by "circuit traces"?

Think of it like you would solder this with huge boxes[2] that contain your logic operations. Each of theses boxes has one or more inputs and outputs. E.g. an AND[1] would have 2 inputs and 1 output. You can consider the circuit traces as the cables you would use to connect the different boxes with eachother. A shift would be a cable that is not going straight, but a little to the left (or right) to use a different input. Leftmost (or rightmost) cable would cross all other cable to use the rightmost (or leftmost) input.

[1] sometimes pictures are better than just words: -> http://www.homofaciens.de/bilder/technik/logic-gates_008.gif

[2] http://www.jaurich-online.de/ebay/ojau/oj1359.jpg

Geremia

sr. member

Activity: 507

Merit: 253

The reason I ask is because I'd like to place a lower limit on the thermal expenditure of ASICs, using Landauer's principle.

So, for SHA256D, I gather there cannot be fewer than 73,728 bits (=32*(768+640+896)) written or erased per hash.
(assuming each addition, XOR, and OR operation involves no more than 32 bits written or erased)

So,

73,728 k T ln(2) = 2.29×10¯¹⁶ Joules,

assuming Boltzmann's constant k = 1.380 6504(24)×10¯²³ J K¯¹ and the circuit is at 324 K (which is the average of my ASIC).

If I'm hashing at 1.1 Thash/s, for example, I get that the power dissipated/required should be:

0.251 milliWatts

So, even the most efficient ASICs like the S5 are many orders of magnitude away from being as efficient as they could be. (Computers nowadays dissipate/require on the order of at least 500× the Landauer limit per elementary logic operation.)

Geremia

sr. member

Activity: 507

Merit: 253

Quote from: Cryddit on April 19, 2015, 12:35:36 AM

But on an ASIC, Bit shifts are not logic operations. Not even gates. They're just circuit traces that go at an angle instead of directly straight into the next array of gates.

I'm sorry, but I'm not too familiar with circuit design. What do you mean by "circuit traces"?

Cryddit

legendary

Activity: 924

Merit: 1132

Quote from: Geremia on April 19, 2015, 12:28:47 AM

Quote from: Cryddit on April 18, 2015, 11:04:13 PM

And a bunch of bit shifts

How many, exactly?

Quote from: Cryddit on April 18, 2015, 11:04:13 PM

but bit shifts are free on an ASIC.

What do you mean they "are free on an ASIC"?

512 32-bit shifts for SHA256, 1024 for SHA256D. 8 per round.

But on an ASIC, Bit shifts are not logic operations. Not even gates. They're just circuit traces that go at an angle instead of directly straight into the next array of gates.

And yes, SHA256D is SHA256D(oubled).

Geremia

sr. member

Activity: 507

Merit: 253

Quote from: Cryddit on April 18, 2015, 11:04:13 PM

And a bunch of bit shifts

How many, exactly?

Quote from: Cryddit on April 18, 2015, 11:04:13 PM

but bit shifts are free on an ASIC.

What do you mean they "are free on an ASIC"?

Geremia

sr. member

Activity: 507

Merit: 253

Quote from: Cryddit on April 18, 2015, 11:04:13 PM

SHA256D, which is what Bitcoin uses

SHA256D = double iterated SHA256?

Cryddit

legendary

Activity: 924

Merit: 1132

SHA256 is sixty-four rounds comprising

384 32-bit additions (6 per round)
320 32-bit ORs (5 per round)
448 32-bit XORs (7 per round)

And a bunch of bit shifts, but bit shifts are free on an ASIC.

SHA256D, which is what Bitcoin uses, is 128 rounds, comprising

768 additions,
640 ORs
896 XORs

And a bunch of bit shifts but bit shifts are free on an ASIC.

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.

Geremia

sr. member

Activity: 507

Merit: 253

What is the theoretical minimum number of logical operations an ASIC needs to perform to compute double iterated SHA256, i.e., sha(sha(•))?

(cf. the Bitcoin StackExchange question)

Topic: Theoretical minimum # of logic operations to perform double iterated SHA256? - page 2. (Read 3933 times)