Subnostr

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./..

Komi_Hartman 2y ago

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)./..

Reply to this note

Please Login to reply.

Discussion

Komi_Hartman 2y ago

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'./..

Komi_Hartman 2y ago

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'./..

Komi_Hartman 2y ago

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.

https://core.ac.uk/download/pdf/31227294.pdf