Topic: Is there any added benefit to using SHA256d over SHA256 in Bitcoin? (Read 4290 times)

Good point but this still can't explain the use of SHA256d in the calculation of Merkle Tree and transaction ID, etc.

Crypto co-processors are not unimaginable, also SHA256 was designed by the NSA, so they might have had already at least designs for specialized hardware ready even before they proposed the standard.

interesting theory but why would such a chip exist?

Maybe satoshi wanted to exclude the chance that there is a SHA256 ASIC in some drawer. The probability for the existence of a single chip piping through two SHA256s was less likely, so the "one CPU one vote" was more likely at the bootstrap of the currency.

Good point.  The average txn is ~560 bytes so it involves 9 blocks to complete the SHA256 hash.   The output is then 32 bytes which requires only 1 more block to perform the second hash.  So 10 vs 9 blocks on the average txn.  However this is offset by the fact that each txn will be hashed again in the merkle tree which would require 2 blocks for SHA256 (due to padding and length value the last block in SHA256 can't hold full 64 bytes) or 3 blocks for SHA256d.  So it is more like 11 blocks vs 13 blocks but that is only ~20% more not 100% more.

Miners don't know their desirable input.

Wow, not every day I get to point something out to D&T.  Note that SHA256 takes time roughly proportional to length (modulo 64-byte partitioning) so a double hash would only take a bit longer than a single hash for a long message.

Can't find the link right now, fast googling returned http://dl.acm.org/citation.cfm?id=1008735:

In a collision the attacker supplies both inputs and attempts to find a pair that produce the same hash output.  "Find x and x' such that x' ≠ x and H(x) = H(x)."  I can't think of many areas where true collisions present a credible attack in Bitcoin because most attacks involve "impersonating" an existing txn, block, or address.

Wouldn't this question get more traction if you asked it in the Dev & Nerd section?

So what would be the difference between this so called "second preimage" and a collision?

Grover's algorithm can be used to find preimages of hashing functions but the usefulness is limited though.  Finding a preimage for a hash function of length n takes O(2^n) time using a classical computer and O(2^n/2) time using a quantum computer (of sufficient size). Unlike asymmetric encryption (Shor's algorithm), the potential of quantum computing to break hashing functions (and symmetric encryption) is rather lackluster.

As for n/2 vs n/3 I have never heard of such a distinction before so I can't comment other than to say in big O terms that is pretty much meaningless.  

Why would you say that?  What quantum algorithm would be involved and what attack?

And my guess is that increase of number of SHA256 operations pushes security from lowest (2^256/3) to highest (2^256/2) bound if an attacker possesses a quantum computer.

(oh stop trolling...we all know who D&T is...he's not Satoshi.)

The point of the thread is that if the hash function itself is secure,
does hashing again make it MORE secure?  Why or why not?

The point of this thread is not very clear. If you try to distract attention from yourself... it doesn't work.

PS: Maybe double hashing increases resistance to quantum computers from 2^256/3 to a higher value?

Personally, I would have chosen since this helps against both kinds of SHA256 preimage attacks.

Still, I think SHA256d is better than plain SHA256. Fully breaking the hash will not be reality in the foreseeable future, but partial attacks (lowering brute force resistance) may appear at the horizon in the coming decades. In that case, SHA256 would become somewhat vulnerable whereas SHA256d would not. Also, plain SHA256 (being a common standard and all) is currently a much more likely (and easier) target for hackers/cryptobreakers (including TLAs) than SHA256d.

The extra computation time for SHA256d compared to SHA256 is completely negligible.

Is there any added benefit to using SHA256d over SHA256 in Bitcoin?

For the computing of transaction hashes, block hashes, and merkle trees Bitcoin uses SHA256d

Effectively all hashing operations are taking twice as long.   This isn't as bad as it sounds because ECDSA verification takes up the majority of the CPU cycles when verifying a block but is there any benefit to the work done in double hashing?  Or should we just accept that this was a poor implementation decision by Satoshi?  Simple if always better in cryptography so Satoshi must have had a reason to go with a double hash but I am wondering if that reason was based on flawed understanding of the limited benefits of double hashing.

Over the years I have heard a couple theories but I don't think they hold up to any scrutiny.

1) Double hashing prevents length extension attacks
This is true but length extension attacks are not useful against Bitcoin.  Length extension attacks involve signature spoofing in authentication when the send and receiver are using a shared secret.   There are no share secret communications in the Bitcoin protocol and thus there are no possible length extension attacks.

2) Double hashing provides a fallback if preimage resistance is weakened
This is also true but only for first preimage resistance which involves the input being unknown.  As such there is some merit to this rationale in using HASH160 (or any double hash) to produce the PubKeyHash (or ScriptHash) from the PubKey (or Script).   Any benefit to double hashing is lost if the address is reused as the input becomes known.   It would also only apply if due to cryptanalysis second preimage resistance was degraded but first preimage resistance was not.

This doesn't apply to any use of SHA256d because they are used in instances where the input is known.  For those unclear on first and second preimage resistance:
  

The key difference to the two scenarios is what is known to the attacker.  In the first the attacker only has the hash. A good example would be cracking a password.  In the second the attacker has the original input. A good example would be producing a "counterfeit" txn/block/merkletree/pubkey which results in the same hash as an existing one to spoof the network and steal funds.

In Bitcoin every use of SHA256 relies on second not first preimage resistance to provide security.  The input is already known so the interim hash can be computed.  The second hashing step provides no security because if the attacker finds a second input which produces the same interim hash as the target then they both will obviously produce the same final hash.  It is possible that double hashing may harden a hash against first preimage attack but that doesn't enhance the security of Bitcoin.

3) Double hashing may break a backdoor in SHA256
I believe a backdoor in a public open algorithm like SHA256 to be very unlikely.  It would have to be hidden in plain sight.   Still even if one did exist the use of a double hash could only provide protection in a first preimage scenario.   Similar to the reasons above, in a second preimage scenario the input is known and thus the adversary can separate out the two steps.