The Sha256 Algorithm

[qplayer]

I was wondering why bitcoin uses   Sha256(Sha256()) instead of sha256() . Is it because the hashing algorithm is not considered safe?


If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate? 

y = "abc"
C = 0
y = sha256(y)
y = sha256(y)

do loop until y = sha256("abc")
   {
    y = sha256(y)
    C = C + 1
   }
   
Print c

[jackthebeanstalk]

I don't see how it is not safe, it is not supposed to be cracked for another 30 years.

[DannyHamilton]

I don't see how it is not safe, it is not supposed to be cracked for another 30 years.

There is a schedule for cracking SHA-256?

[DannyHamilton]

- snip -
If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate? 
- snip -

I'm not sure that it can even be said for certain that the loop would ever terminate.  If it did, I don't think you can predict ahead of time just how many iterations it would take.

[zemario]

- snip -
If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate?  
- snip -

I'm not sure that it can even be said for certain that the loop would ever terminate.  If it did, I don't think you can predict ahead of time just how many iterations it would take.

You can absolutely be sure that it would terminate.
That is in fact the definition of hash function. A function which accepts an input from an infinite set and maps it into a FINITE set. Therefore, the time that program would take to finish would be finite. 'Finite' doesn't mean that is ridiculously large, which it is.

If the  computing power is infinite than that program would terminate immediately. But there is no such thing as 'infinite computing power'.
In practice that method is won't get you anywhere. The technology is nowhere near to break that.

[DannyHamilton]

- snip -
If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate?  
- snip -

I'm not sure that it can even be said for certain that the loop would ever terminate.  If it did, I don't think you can predict ahead of time just how many iterations it would take.

You can absolutely be sure that it would terminate.
That is in fact the definition of hash function. A function which accepts an input from an infinite set and maps it into a FINITE set. Therefore, the time that program would take to finish would be finite.
- snip -

A finite set doesn't guarantee any particular pattern of solution.

Here's an extreme example:

Imagine a hash function that maps an infinite set of values to the finite set between 0 and 999.  Imagine that results of the hash function are evenly distributed across the finite set so that any value in the finite set is equally likely to result from the function.  Now imagine that he function results in the following particular results:

• hash('abc') results in a value of 100
• hash(100) results in a value of 200
• hash(200) results in a value of 300
• hash(300) results in a value of 400
• hash(400) results in a value of 200

The loop that the OP suggested would NEVER exit.  It would run infinitely generating the sequence 200, 300, 400, 200, 300, 400, 200, 300, 400, etc.  It would never reach a value where hash(y) = 100.

I stand by my statement, "I'm not sure that it can even be said for certain that the loop would ever terminate.  If it did, I don't think you can predict ahead of time just how many iterations it would take."

SHA-256 isn't predictable enough to know if a pattern of results would emerge.

[erasmas]

- snip -
If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate?  
- snip -

I'm not sure that it can even be said for certain that the loop would ever terminate.  If it did, I don't think you can predict ahead of time just how many iterations it would take.

You can absolutely be sure that it would terminate.
That is in fact the definition of hash function. A function which accepts an input from an infinite set and maps it into a FINITE set. Therefore, the time that program would take to finish would be finite.
- snip -

A finite set doesn't guarantee any particular pattern of solution.

Here's an extreme example:

Imagine a hash function that maps an infinite set of values to the finite set between 0 and 999.  Imagine that results of the hash function are evenly distributed across the finite set so that any value in the finite set is equally likely to result from the function.  Now imagine that he function results in the following particular results:

• hash('abc') results in a value of 100
• hash(100) results in a value of 200
• hash(200) results in a value of 300
• hash(300) results in a value of 400
• hash(400) results in a value of 200

The loop that the OP suggested would NEVER exit.  It would run infinitely generating the sequence 200, 300, 400, 200, 300, 400, 200, 300, 400, etc.  It would never reach a value where hash(y) = 100.

I stand by my statement, "I'm not sure that it can even be said for certain that the loop would ever terminate.  If it did, I don't think you can predict ahead of time just how many iterations it would take."

SHA-256 isn't predictable enough to know if a pattern of results would emerge.

Is the hash space for the SHA256 algorithm cyclic under sha256? I guess I don't know enough about the math involved, and a quick search doesn't turn up anything promising.

Intuition says that it should be, but that not every initial value is a generator. In fact, groups that have this property are very special, so I doubt it.

[ARGpentem]

wait so what happens when it is cracked 

[r3wt]

wait so what happens when it is cracked 

we start using sha 512, Whirlpool-T or my personal favorite, Gost

[zemario]

- snip -
If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate?  
- snip -

I'm not sure that it can even be said for certain that the loop would ever terminate.  If it did, I don't think you can predict ahead of time just how many iterations it would take.

You can absolutely be sure that it would terminate.
That is in fact the definition of hash function. A function which accepts an input from an infinite set and maps it into a FINITE set. Therefore, the time that program would take to finish would be finite.
- snip -

A finite set doesn't guarantee any particular pattern of solution.

Here's an extreme example:

Imagine a hash function that maps an infinite set of values to the finite set between 0 and 999.  Imagine that results of the hash function are evenly distributed across the finite set so that any value in the finite set is equally likely to result from the function.  Now imagine that he function results in the following particular results:

• hash('abc') results in a value of 100
• hash(100) results in a value of 200
• hash(200) results in a value of 300
• hash(300) results in a value of 400
• hash(400) results in a value of 200

The loop that the OP suggested would NEVER exit.  It would run infinitely generating the sequence 200, 300, 400, 200, 300, 400, 200, 300, 400, etc.  It would never reach a value where hash(y) = 100.

I stand by my statement, "I'm not sure that it can even be said for certain that the loop would ever terminate.  If it did, I don't think you can predict ahead of time just how many iterations it would take."

SHA-256 isn't predictable enough to know if a pattern of results would emerge.

You are right, I overlooked the code and assumed it was a trivial brute-forcer.
One thing we know, by hashing the output of an hash we are limiting the the input to a finite set, this, in theory, a brute force would require less iterations.

[qplayer]

- snip -
If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate?  
- snip -

I'm not sure that it can even be said for certain that the loop would ever terminate.  If it did, I don't think you can predict ahead of time just how many iterations it would take.

You can absolutely be sure that it would terminate.
That is in fact the definition of hash function. A function which accepts an input from an infinite set and maps it into a FINITE set. Therefore, the time that program would take to finish would be finite.
- snip -

A finite set doesn't guarantee any particular pattern of solution.

Here's an extreme example:

Imagine a hash function that maps an infinite set of values to the finite set between 0 and 999.  Imagine that results of the hash function are evenly distributed across the finite set so that any value in the finite set is equally likely to result from the function.  Now imagine that he function results in the following particular results:

• hash('abc') results in a value of 100
• hash(100) results in a value of 200
• hash(200) results in a value of 300
• hash(300) results in a value of 400
• hash(400) results in a value of 200

The loop that the OP suggested would NEVER exit.  It would run infinitely generating the sequence 200, 300, 400, 200, 300, 400, 200, 300, 400, etc.  It would never reach a value where hash(y) = 100.

I stand by my statement, "I'm not sure that it can even be said for certain that the loop would ever terminate.  If it did, I don't think you can predict ahead of time just how many iterations it would take."

SHA-256 isn't predictable enough to know if a pattern of results would emerge.

Is the hash space for the SHA256 algorithm cyclic under sha256? I guess I don't know enough about the math involved, and a quick search doesn't turn up anything promising.

Intuition says that it should be, but that not every initial value is a generator. In fact, groups that have this property are very special, so I doubt it.

• hash(100) results in a value of 200
• hash(400) results in a value of 200

This would mean there is a collision i.e   hash(100) = hash(400)

I think either the loop would terminate for some value of  C less than 2^256 or it would not terminate, meaning there was a collison in the sha256

[DannyHamilton]

- snip -
If I ran the below program on a computer with near infinite computing power what value of C would the loop terminate?  
- snip -

I'm not sure that it can even be said for certain that the loop would ever terminate.  If it did, I don't think you can predict ahead of time just how many iterations it would take.

You can absolutely be sure that it would terminate.
That is in fact the definition of hash function. A function which accepts an input from an infinite set and maps it into a FINITE set. Therefore, the time that program would take to finish would be finite.
- snip -

A finite set doesn't guarantee any particular pattern of solution.

Here's an extreme example:
- snip -

Is the hash space for the SHA256 algorithm cyclic under sha256? I guess I don't know enough about the math involved, and a quick search doesn't turn up anything promising.

Intuition says that it should be, but that not every initial value is a generator. In fact, groups that have this property are very special, so I doubt it.

• hash(100) results in a value of 200
• hash(400) results in a value of 200

This would mean there is a collision i.e   hash(100) = hash(400)

Obviously.  Given an infinite source, collisions will have to occur eventually in the solution.  It can't be avoided.

I think either the loop would terminate for some value of  C less than 2^256 or it would not terminate, meaning there was a collison in the sha256

Agreed, either:

• sha256(y) would collide with an earlier iteration of sha256(y) creating a loop that would never terminate
• sha256(y) would collide with sha256("abc") creating a loop that would terminate before C = 2²⁵⁶+1

I suppose it is possible that you could encounter every possible value between 0 and 2²⁵⁶-1.  If that were to happen, then at C = 2²⁵⁶+1 you would either have to collide with an earlier value (since there are no values left that haven't been generated), or with sha256("abc").  I doubt the result set is that perfectly distributed, but I've not seen anything that says it can't be.

[stelmoi]

wait so what happens when it is cracked 

we start using sha 512, Whirlpool-T or my personal favorite, Gost

Maybe someone will start testing these with Whirlpoolcoin and Gostcoin ?   

[sliding scale]

wait so what happens when it is cracked 

we start using sha 512, Whirlpool-T or my personal favorite, Gost

So we just switch over to a new crypto and everything is OK? We don't loose any coins?

[stelmoi]

So we just switch over to a new crypto and everything is OK? We don't loose any coins?

It would be a hard fork, and those are not easy.   But possible if the majority of miners agree.

[kokjo]

So the question is if that sha256 is a bijective map between the set of numbers under 2^256 to itself?

i don't know, but my guess would be that its not.

[AliceWonder]

So the question is if that sha256 is a bijective map between the set of numbers under 2^256 to itself?

i don't know, but my guess would be that its not.

I would guess not, that some valid numbers can not be obtained by hashing valid numbers while others have collissions.
But I don't know.