How can we derive all work ever done on the system from the lowest hash ever found?

Question

If not mathematically (I imagine the proof might be quite rigorous), could you please provide an intuitive explanation for why the lowest hash ever found tells approximates the total amount of work ever done on the system? Source: https://youtu.be/zYzEmBlJ77s?t=4720

My thinking: We can figure out the probability of finding a hash that is lower than the hash we found. From there, we can find the "mid-point" of a distribution for how many attempts it would take to find such a hash. So it just gives you a point on a distribution.

Thank you!

Answer 1

Every hash attempt, regardless of who does it, or what difficulty it occurs at, is an independent evaluation of a hash function, resulting in a number uniformly distributed between 0 and 2²⁵⁶ - 1.

Now consider the distribution of the minimum of N independent samples. See this question for a derivation, but the result is that the average of that distribution is approximately 2²⁵⁶ / (N+1).

This gives an intuition about the relation between the smallest observed hash and the number of hashes performed: on average, the minimum will scale approximately proportional to 1 / (N+1) with N performed hashes.

The statistical tool for estimating N from the observation is called likelihood estimation: we have a probability distribution with unknown parameter N, and make one observation from that distribution. That distribution of the minimum of N hashes (if we simplify it a bit by turning the output of hashing into a continuous real function, uniformly distributed over [0, 2²⁵⁶]), has probability density function f_N(x) = N(1-x/2²⁵⁶)^N-1. Given an observation min_hash, the value for N that maximizes f_N(min_hash) (the maximum likelihood estimator) is -1 / log(1 - min_hash/2²⁵⁶). For small values of min_hash, that expression is closely approximated by 2²⁵⁶/x - 1/2.

Answer 2

Proof-of-work as used in Bitcoin relies on finding low hashes, in other words finding hashes that begin with a certain number of zeros. To find a hash whose binary representation starts with 30 zeros, you would need to do, on average, 2^30 attempts. When you find this hash and present it, it is a proof that you have actually done about as much work. And it works both ways, when you perform 2^30 attempts, the lowest hash you will end up with will start with roughly 30 zeros.

Importantly, this works on any scale. The smallest block hash I could find starts with 23 hexadecimal zeros, or 92 binary zeros, which shows that the network has calculated around 2^92 hashes in its existence.

If you want to see it even more intuitively, check out this answer from a different thread that shows how the number of zeros in the lowest ever hash has been rising over time.