One way functions

[XinXan]

Im not sure if this is the right section, lately i have been reading about a lot of technical details about bitcoins and i found something about one-way functions, theoretically possible but not proven yet, i was just wondering what would be a good candidate for such thing and how do they work exactly? I mean if i have something simple as x + 1 = 3 then its quite easy to calculate, and supposedly one way functions are hard or impossible to calculate backwards if i understood correctly. Would that mean a computer has to calculate backwards from knowing the number 3?? or how does that work

[ObscureBean]

Ok I don't know anything about one way functions but if the name is anything to go by, here are some thoughts based on simple logic. Anything that follows a method can have its steps traced back. Everything follows one method or another. It is not possible for a function to be truly one way when bound by/to the observer's reality. A one way function can coexist with an observer only while the observer is completely unaware of it. In other words while a true one way function can exist, an observer can never have proof of its existence 

[XinXan]

Im trying to figure out how it works exactly, of course it would be ''impossible'' to know how, for example a number ''3'' is obtained because there is no way to know what method was used but im pretty sure thats not how it works.

[medUSA]

I googled a nice explanation about one way functions for you and I ended up enjoying the read 
This is fairly easy to understand. Remember to read Part2 (and Rainbow Tables link), Part3, and Part4:

http://blog.jgc.org/2013/04/a-non-mathematical-explanation-of-one.html

[XinXan]

I googled a nice explanation about one way functions for you and I ended up enjoying the read 
This is fairly easy to understand. Remember to read Part2 (and Rainbow Tables link), Part3, and Part4:

http://blog.jgc.org/2013/04/a-non-mathematical-explanation-of-one.html

I saw that one but im looking for a mathematical explanation actually and its use with bitcoins, the sha 256 and that kind of stuff but thanks for your help

[shorena]

I googled a nice explanation about one way functions for you and I ended up enjoying the read  
This is fairly easy to understand. Remember to read Part2 (and Rainbow Tables link), Part3, and Part4:

http://blog.jgc.org/2013/04/a-non-mathematical-explanation-of-one.html

I saw that one but im looking for a mathematical explanation actually and its use with bitcoins, the sha 256 and that kind of stuff but thanks for your help

Not sure what you are exactly looking for but the simplest "one way" function I can think of is f(x) = x², which gives you the value you put in mutiplied by itself. Now the question is which number did I put in when you only know the result. E.g.:

I say a result of f(x) = x² is 4. What was the x? You cant know the answer, because there are two (in |R) possible answers -2 and 2. If it was a game you could guess and would win 50% of the time.

Its a "one way" function because you cant bijective (math. for one-to-one) reverse the calculation, its only a function in one direction, but not in the other direction, its not a function if you reverse the operation. A function is defined such that for each input there is only a single possible output. Two different inputs may return the same output, thats fine, but there may never be more than one possible result for any given input. If you want to reverse f(x) = x² you get f_R(x) = sqrt(x) which gives you the root of the number you put in, but it will return two results the negative and the positive root, thus its usually only defined on |R_>0 if its used as a function and only returns positive numbers.

SHA256 is very similar to this, its a function as any given input gives the exact same hash value. But since it is mapping all possible (and thus infinte) values to a small (in mathmatical terms) subspace of 2²⁵⁶ possible results, there must be a collision. There must be infinity values that result in the same SHA256 hash. They are just not humanly possible to find. In this sense SHA256 is a one way function similar to x² only that you have no way to try all combinations for a given result. If this was a game, you, your family and everyone on earth could guess all day every day until the sun burned out and I still would win.

This is the basis for bitcoin mining. As the hash must be below a certain value and miners cant just reverse SHA256 that value and get a valid block. They have to try many different combinations to find a value that fits.

[XinXan]

I googled a nice explanation about one way functions for you and I ended up enjoying the read  
This is fairly easy to understand. Remember to read Part2 (and Rainbow Tables link), Part3, and Part4:

http://blog.jgc.org/2013/04/a-non-mathematical-explanation-of-one.html

I saw that one but im looking for a mathematical explanation actually and its use with bitcoins, the sha 256 and that kind of stuff but thanks for your help

Not sure what you are exactly looking for but the simplest "one way" function I can think of is f(x) = x², which gives you the value you put in mutiplied by itself. Now the question is which number did I put in when you only know the result. E.g.:

I say a result of f(x) = x² is 4. What was the x? You cant know the answer, because there are two (in |R) possible answers -2 and 2. If it was a game you could guess and would win 50% of the time.

Its a "one way" function because you cant bijective (math. for one-to-one) reverse the calculation, its only a function in one direction, but not in the other direction, its not a function if you reverse the operation. A function is defined such that for each input there is only a single possible output. Two different inputs may return the same output, thats fine, but there may never be more than one possible result for any given input. If you want to reverse f(x) = x² you get f_R(x) = sqrt(x) which gives you the root of the number you put in, but it will return two results the negative and the positive root, thus its usually only defined on |R_>0 if its used as a function and only returns positive numbers.

SHA256 is very similar to this, its a function as any given input gives the exact same hash value. But since it is mapping all possible (and thus infinte) values to a small (in mathmatical terms) subspace of 2²⁵⁶ possible results, there must be a collision. There must be infinity values that result in the same SHA256 hash. They are just not humanly possible to find. In this sense SHA256 is a one way function similar to x² only that you have no way to try all combinations for a given result. If this was a game, you, your family and everyone on earth could guess all day every day until the sun burned out and I still would win.

This is the basis for bitcoin mining. As the hash must be below a certain value and miners cant just reverse SHA256 that value and get a valid block. They have to try many different combinations to find a value that fits.

Well thats a good example but its not a one way function afterall, because although you cant know for sure what was the x, you have the possibilities, in this case only 2, i guess with harder problems this number increases and if from 2 possibilities we jump to millions then its pretty much impossible to know all of them not taking in count how hard it would be to go in reverse, of course in your example is not hard. The thing is that someone could one day actually break the sha 256 and i know that it could be replaced with something more secure ar the time but what would happen if something like that happens, the attacker would have total control over any wallets?

[shorena]

-snip-
Well thats a good example but its not a one way function afterall, because although you cant know for sure what was the x, you have the possibilities, in this case only 2, i guess with harder problems this number increases and if from 2 possibilities we jump to millions then its pretty much impossible to know all of them not taking in count how hard it would be to go in reverse, of course in your example is not hard.

Its easier to understand with an easy example. The definition of one way function is just that, its only a function in one direction and there is no reverse function. There might be an algorithm to reverse the operation and it might not be important to get the exact same input either. One might not care whether one gets -2 or 2 as long as its a possible input. Similar with bitcoin mining. Any input that results in the needed hash value is good for the miners, it means they just found a valid block and thus get the blockreward.

The thing is that someone could one day actually break the sha 256 and i know that it could be replaced with something more secure ar the time but what would happen if something like that happens, the attacker would have total control over any wallets?

SHA256 is mostly important for mining and its done twice in order to add a layer of difficulty even if SHA256 should be vulnerable. Its more likely that there are shortcuts found over time than that its just broken (as in: can be reversed) one day. While broken SHA256 would certainly be a big problem for bitcoin it would also be a big problem for many other applications.

In terms of private keys an attacker would need to break not only SHA256, but also elliptic curves and RIPEMD160. The private key can only be calculated from the public key if ECDSA[1] is broken, which again would be a huge problem for many other applications besides bitcoin. But even if ECDSA was broken, you can only get the public key from a bitcoin address if you also break SHA256 and RIPEMD160 as both are needed to reverse the calculations of an address[2]. Keep in mind thought that the public key is known to the blockchain if you spend "from"[3] the address in question. This is why using a new address every time adds a (tiny little) bit of security. SHA256 is also considered to be quantum secure while ECDSA is not.

[1] https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_Algorithm
[2] https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses
[3] bitcoins are not actually spend from addresses, but rather refer to another transaction.