#Bitcoin & the 'sublinear complexity of hashing'! 🧵
#Bitcoin’s hash function is a random oracle & the security of a random oracle scheme is 'sub-linear' in the number of invocations. The proof-of-work scheme in Bitcoin, on the other hand, is a 'one-way' function, producing a single fixed value output for a given input. The security of proof-of-work is therefore 'linear' in the number of invocations as we increase 'hashing complexity'./..
In the relationship between the complexity of hashing & the security of proof-of-work systems, there’s a direct relationship as hashing complexity increases there’s a corresponding decrease in the security of proof-of-work systems as we increase the difficulty of finding a 'nonce' that produces the desired hash. So the relationship between hashing complexity & the security of proof-of-work systems is actually 'sub-linear', not linear./..
Bitcoin’s proof-of-work:
Bitcoin’s proof-of-work system is based on a one-way function that’s very similar to the one-way function that hashes are based on. The one-way function in Bitcoin is defined in the Bitcoin protocol as:
The hash function H(x) = H(H(x))
The base is a 'cryptographic hash function' such as 'SHA-256', the same hash function is used for the proof-of-work hash. The key difference is that the hash function in Bitcoin is a random oracle, meaning that it’s a 'function that takes as input a number (the nonce) & returns a fixed value' (the hash of the nonce), while a hash function in Bitcoin is a one-way function that takes as input a string & returns a string. The hash function in Bitcoin’s proof-of-work is defined as:
'The base is the hash function that hashes to a single value' (256 bits in Bitcoin)./..
How secure is a 'one-way function' ?
The relationship between the security of a one-way function & the number of invocations of the function is a subject of research that isn’t fully understood, but some good ideas have been put forward in the literature. A one-way function requires some number 'm' of invocations to compute & the security of a function, as measured by the amount of time it takes to compute 'n' invocations, is given by the following expression:
Security = 2m^(2(n-m)^(2-1))
This relationship is a direct result of the 'birthday paradox'./..
The 'birthday paradox' shows that if you have a large number of people (m) & a finite number of people (n) then the probability that nobody in the large number of people has the same birthday as another person in the large number of people is:
Prob(nobody in large group has same birthday as another one) = 1 - (1-2/m)^n
Thus, the security of a one-way function is roughly inversely proportional to the number of invocations of the function (a function that requires m invocations to compute has a security of roughly 2^m).
If we look at the security of Bitcoin’s proof-of-work one-way function, we get the following:
Security = 2^256
In other words, the security of proof-of-work is roughly a 'constant'. A proof-of-work is considered secure if it takes '256 attempts to find a nonce that computes the desired hash'./..
How hashing complexity affects the security of proof-of-work ?
A hashing function is a one-way function if & only if the hash function is 'collision resistant'.
The birthday paradox is a result of the collision resistance of a one-way function. It’s not difficult to find a collision, i.e. two inputs that compute the same value, but the birthday paradox shows that as the number of invocations, m, increases the probability that you get a collision approaches zero.
