qplayer (OP)
Newbie
Offline
Activity: 5
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 25, 2013, 11:09:32 AM |
|
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
Newbie
Offline
Activity: 52
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 25, 2013, 11:23:17 AM |
|
I don't see how it is not safe, it is not supposed to be cracked for another 30 years.
|
|
|
|
DannyHamilton
Legendary
Offline
Activity: 3472
Merit: 4794
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 25, 2013, 04:07:11 PM |
|
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? ![Huh](https://bitcointalk.org/Smileys/default/huh.gif)
|
|
|
|
DannyHamilton
Legendary
Offline
Activity: 3472
Merit: 4794
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 25, 2013, 04:10:36 PM |
|
- 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
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 25, 2013, 04:24:47 PM |
|
- 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
Legendary
Offline
Activity: 3472
Merit: 4794
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 25, 2013, 04:36:25 PM |
|
- 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
Newbie
Offline
Activity: 1
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 25, 2013, 05:00:43 PM |
|
- 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
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 25, 2013, 05:32:46 PM |
|
wait so what happens when it is cracked ![Huh](https://bitcointalk.org/Smileys/default/huh.gif)
|
A freedom fighter. Stop all your bull shit !
|
|
|
r3wt
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 25, 2013, 05:34:53 PM |
|
wait so what happens when it is cracked ![Huh](https://bitcointalk.org/Smileys/default/huh.gif) we start using sha 512, Whirlpool-T or my personal favorite, Gost
|
My negative trust rating is reflective of a personal vendetta by someone on default trust.
|
|
|
zemario
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 25, 2013, 07:50:52 PM |
|
- 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 (OP)
Newbie
Offline
Activity: 5
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 25, 2013, 08:42:13 PM |
|
- 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
Legendary
Offline
Activity: 3472
Merit: 4794
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 25, 2013, 11:58:16 PM |
|
- 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 = 2256+1
I suppose it is possible that you could encounter every possible value between 0 and 2 256-1. If that were to happen, then at C = 2 256+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
Newbie
Offline
Activity: 14
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 26, 2013, 06:55:20 PM |
|
wait so what happens when it is cracked ![Huh](https://bitcointalk.org/Smileys/default/huh.gif) we start using sha 512, Whirlpool-T or my personal favorite, Gost Maybe someone will start testing these with Whirlpoolcoin and Gostcoin ? ![Roll Eyes](https://bitcointalk.org/Smileys/default/rolleyes.gif)
|
|
|
|
sliding scale
Newbie
Offline
Activity: 14
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 26, 2013, 06:58:28 PM |
|
wait so what happens when it is cracked ![Huh](https://bitcointalk.org/Smileys/default/huh.gif) 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
Newbie
Offline
Activity: 14
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 26, 2013, 07:00:32 PM |
|
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
Legendary
Offline
Activity: 1050
Merit: 1000
You are WRONG!
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 26, 2013, 07:04:07 PM |
|
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.
|
"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
|
|
|
AliceWonder
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 26, 2013, 07:07:22 PM |
|
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.
|
|
|
|
|