Bitcoin Forum
March 31, 2020, 08:11:29 AM *
News: Latest Bitcoin Core release: 0.19.0.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Is there any added benefit to using SHA256d over SHA256 in Bitcoin?  (Read 4087 times)
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1007


Gerald Davis


View Profile
January 17, 2015, 09:53:14 PM
Last edit: January 17, 2015, 10:16:09 PM by DeathAndTaxes
 #1

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
Code:
SHA256d(x) = SHA256(SHA256(x))

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:
  
Quote
First-preimage resistance:  it is computationally infeasible to find any input which hashes to a pre-specified output
Given a "y" such that h(x) = y it is difficult to find any preimage x .

Second-preimage resistance: it is computationally infeasible to find a second input which has the same output as a specified input.
Given x, it is difficult to find a second preimage x' ≠ x such that h(x) = h(x′)

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.
1585642289
Hero Member
*
Offline Offline

Posts: 1585642289

View Profile Personal Message (Offline)

Ignore
1585642289
Reply with quote  #2

1585642289
Report to moderator
1585642289
Hero Member
*
Offline Offline

Posts: 1585642289

View Profile Personal Message (Offline)

Ignore
1585642289
Reply with quote  #2

1585642289
Report to moderator
1585642289
Hero Member
*
Offline Offline

Posts: 1585642289

View Profile Personal Message (Offline)

Ignore
1585642289
Reply with quote  #2

1585642289
Report to moderator
Best ratesfor crypto
EXCHANGE
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1585642289
Hero Member
*
Offline Offline

Posts: 1585642289

View Profile Personal Message (Offline)

Ignore
1585642289
Reply with quote  #2

1585642289
Report to moderator
1585642289
Hero Member
*
Offline Offline

Posts: 1585642289

View Profile Personal Message (Offline)

Ignore
1585642289
Reply with quote  #2

1585642289
Report to moderator
Kazimir
Legendary
*
Offline Offline

Activity: 1176
Merit: 1000



View Profile
January 17, 2015, 10:00:56 PM
 #2

Personally, I would have chosen
Code:
SHA256d = SHA256(SHA256(message)+message)
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.

In theory, there's no difference between theory and practice. In practice, there is.
Insert coin(s): 1KazimirL9MNcnFnoosGrEkmMsbYLxPPob
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2128
Merit: 1009

Newbie


View Profile
January 17, 2015, 10:13:52 PM
 #3

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

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

PS: Maybe double hashing increases resistance to quantum computers from 2256/3 to a higher value?
jonald_fyookball
Legendary
*
Offline Offline

Activity: 1302
Merit: 1002


Core dev leaves me neg feedback #abuse #political


View Profile
January 17, 2015, 11:03:28 PM
 #4

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

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

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

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


Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2128
Merit: 1009

Newbie


View Profile
January 17, 2015, 11:12:26 PM
 #5

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?

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

Activity: 1302
Merit: 1002


Core dev leaves me neg feedback #abuse #political


View Profile
January 17, 2015, 11:18:47 PM
 #6

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?

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

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

DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1007


Gerald Davis


View Profile
January 17, 2015, 11:27:55 PM
 #7

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

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.  
jonald_fyookball
Legendary
*
Offline Offline

Activity: 1302
Merit: 1002


Core dev leaves me neg feedback #abuse #political


View Profile
January 18, 2015, 03:13:30 AM
 #8


Quote
First-preimage resistance:  it is computationally infeasible to find any input which hashes to a pre-specified output
Given a "y" such that h(x) = y it is difficult to find any preimage x .

Second-preimage resistance: it is computationally infeasible to find a second input which has the same output as a specified input.
Given x, it is difficult to find a second preimage x' ≠ x such that h(x) = h(x′)


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

QuestionAuthority
Legendary
*
Offline Offline

Activity: 2128
Merit: 1378


You lead and I'll watch you walk away.


View Profile
January 18, 2015, 03:57:00 AM
 #9

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

DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1007


Gerald Davis


View Profile
January 18, 2015, 04:49:09 AM
 #10

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

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.
Come-from-Beyond
Legendary
*
Offline Offline

Activity: 2128
Merit: 1009

Newbie


View Profile
January 18, 2015, 08:40:43 AM
 #11

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.  

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

Quote
Given a function f as an oracle, the collision problem is to find two distinct indexes i and j such that f(i) = f(j), under the promise that such indexes exist. Since the security of many fundamental cryptographic primitives depends on the hardness of finding collisions, our lower bounds provide evidence for the existence of cryptographic primitives that are immune to quantum cryptanalysis. We prove that any quantum algorithm for finding a collision in an r-to-one function must evaluate the function Ω((n/r)1/3) times, where n is the size of the domain and r|n. This matches an upper bound of Brassard, Høyer, and Tapp. No lower bound better than constant was previously known. Our result also implies a quantum lower bound of Ω(n2/3) queries for the element distinctness problem, which is to determine whether n integers are all distinct. The best previous lower bound was Ω(&sqrt;n) queries.
zebedee
Donator
Hero Member
*
Offline Offline

Activity: 668
Merit: 500



View Profile
January 20, 2015, 06:22:49 AM
 #12

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
Code:
SHA256d(x) = SHA256(SHA256(x))

Effectively all hashing operations are taking twice as long.
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.
stdset
Hero Member
*****
Offline Offline

Activity: 572
Merit: 500



View Profile
January 20, 2015, 08:16:41 AM
 #13

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.
Miners don't know their desirable input.

DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1007


Gerald Davis


View Profile
January 20, 2015, 07:19:26 PM
 #14

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.

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.
grau
Hero Member
*****
Offline Offline

Activity: 836
Merit: 1000


bits of proof


View Profile WWW
January 21, 2015, 08:53:22 AM
 #15

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

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.
jonald_fyookball
Legendary
*
Offline Offline

Activity: 1302
Merit: 1002


Core dev leaves me neg feedback #abuse #political


View Profile
January 24, 2015, 04:37:16 AM
 #16

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

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.

interesting theory but why would such a chip exist?

Sukrim
Legendary
*
Offline Offline

Activity: 2548
Merit: 1002


View Profile
January 24, 2015, 10:36:00 AM
 #17

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.

https://www.coinlend.org <-- automated lending at various exchanges.
https://www.bitfinex.com <-- Trade BTC for other currencies and vice versa.
Mail me at Bitmessage: BM-BbiHiVv5qh858ULsyRDtpRrG9WjXN3xf
jl2012
Legendary
*
Offline Offline

Activity: 1792
Merit: 1010


View Profile
January 24, 2015, 12:27:48 PM
 #18

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

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 but this still can't explain the use of SHA256d in the calculation of Merkle Tree and transaction ID, etc.

Donation address: 374iXxS4BuqFHsEwwxUuH3nvJ69Y7Hqur3 (Bitcoin ONLY)
LRDGENPLYrcTRssGoZrsCT1hngaH3BVkM4 (LTC)
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!