# Blockchain Proof-of-Work Is a Decentralized Clock

If you find WORDS helpful, Bitcoin donations are unnecessary but appreciated. Our goal is to spread and preserve Bitcoin writings for future generations. Read more. |
Make a Donation |

# Blockchain Proof-of-Work Is a Decentralized Clock

### By Grisha Trubetskoy

### Posted January 23, 2018

This is an explanation of the key function on Proof-of-Work in the Bitcoin blockchain. It focuses on the one feature of Proof-of-Work that is essential and shows that other features often talked about such as security are secondary side-effects, useful, but not essential. This explanation rests on illustrating a few interesting properties of how Proof-of-Work is used in the blockchain that are not immediately obvious and sometimes are rather counter-intuitive, for example how participants collectively solve a problem withoutÂ *ever communicating*. Having understood each of these properties, one should conclude that Proof-of-Work is primarily a mechanism which accomplishes a distributed and decentralized system of timing, i.e. a clock. Note that this write up isnâ€™t about Proof-of-WorkÂ *per se*, it explains how the blockchain takes advantage of it. If you do not know anything about Proof-of-Work, thenÂ thisÂ link might be a good start.

## The Decentralized Ledger Time Ordering Problem

Before describing the solution, let us focus on the problem. Much of the literature around Proof-of-Work is so confusing because it attempts to explain the solution without first identifying the problem. Any ledger absolutely needs order. One cannot spend money that has not been received, nor can one spend money that is already spent. Blockchain transactions (or blocks containing them) must be ordered, unambiguously, and without the need for a trusted third party. Even if the blockchain was not a ledger but just data like a log of some sort, for every node to have an identical copy of the blockchain, order is required. A blockchain in a different order is a different blockchain. But if transactions are generated by anonymous participants all over the world, and no central party is responsible for organizing the list, how can it be done? For example transactions (or blocks) could include timestamps, but how could these timestamps be trusted? Time is but aÂ human concept, and any source of it, such as an atomic clock, is a â€śtrusted third partyâ€ť. Which, on top of everything, isÂ slightly wrongÂ most of time due to network delays as well as theÂ effects of Relativity. EvenÂ time dilationÂ between someone in an airplane vs the ground, though minute, is sufficient to make ordering impossible. Paradoxically, relying on a timestamp to determine event order is not possible in a decentralized geographically dispersed system. The â€śtimeâ€ť we are interested in is not the year, month, day, etc. that we are used to. What we need is a mechanism by which we can verify that one event took place before another or perhaps concurrently. First though, for the notions of before and after to be applicable, aÂ *point in time*Â needs to be established. Establishing a point in time may seem theoretically impossible at first because there is no technology accurate enough to measure aÂ Planck. But as youâ€™ll see, Bitcoin works around this by creating its own notion of time where precise points in time are in fact possible. This problem is well described inÂ Leslie Lamportâ€™sÂ 1978 paperÂ â€śTime, Clocks, and the Ordering of Events in a Distributed Systemâ€ťÂ which doesnâ€™t actually provide a comprehensive solution other than â€śproperly synchronized physical clocksâ€ť. In 1982 Lamport also described theÂ â€śByzantine Generals Problemâ€ť, and Satoshi in one of his first emailsÂ explains, how Proof-of-Work is a solution, though theÂ Bitcoin paperÂ states â€śTo implement a distributedÂ *timestamp server*Â on a peer-to-peer basis, we will need to use a proof-of-work systemâ€ť, suggesting that it primarily solves the issue of timestamping.

## Timing is the Root Problem

It must be stressed that theÂ *impossibility of associating events with points in time*Â in distributed systems was the unsolved problem that precluded a decentralized ledger from ever being possible until Satoshi Nakamoto invented a solution. There are many other technical details that play into the blockchain, but timing is fundamental and paramount. Without timing there is no blockchain.

## Proof-of-Work Recap

Very briefly, the Bitcoin Proof-of-Work is a value whoseÂ SHA-2Â hash conforms to a certain requirement which makes such a value difficult to find. The difficulty is established by requiring that the hash is less than a specific number, the smaller the number, the more rare the input value and the higher the difficulty of finding it. It is called â€śProof Of Workâ€ť because it is known that a value with such a hash is extremely rare, which means that finding such a value requires a lot of trial and error, i.e. â€śworkâ€ť. Work in turn impliesÂ *time*. By varying the requirement, we can vary the difficulty and thus the probability of such a hash being found. The Bitcoin Difficulty adjusts dynamically so that a proper hash is found on average once every ten minutes.

## Nothing Happens Between Blocks

The state of the chain is reflected by its blocks, and each new block produces a new state. The blockchain state moves forward one block at a time, and the average 10 minutes of a block is the smallest measure of blockchain time.

## SHA is Memoryless and Progress-Free

The Secure Hash Algorithm is what is known in statistics and probability asÂ *memoryless*. This is a property that is particularly counter-intuitive for us humans. The best example of memoryless-ness is a coin toss. If a coin comes up heads 10 times in a row, does it mean that the next toss is more likely to be tails? Our intuition says yes, but in reality each toss has a 50/50 chance of either outcome regardless of what happened immediately prior. Memorylessness is required for the problem to beÂ *progress-free*. Progress-free means that as miners try to solve blocks iterating overÂ nonces, each attempt is a stand-alone event and the probability of finding a solution is constant at each attempt, regardless of how much work has been done in the past. In other words at each attempt the participant is not getting any â€ścloserâ€ť to a solution or is making no progress. And a miner whoâ€™s been looking for a solution for a year isnâ€™t more likely to solve a block at the next attempt than a miner who started a second ago. The probability of finding the solution given a specific difficulty in a given period of time is therefore determinedÂ *solely by the speed at which all participants can iterate through the hashes*. Not the prior history, not the data, just the hashrate. The hashrate in turn is a function of the number of participants and the speed of the equipment used to calculate the hash. (NB: Though strictly speaking SHA is not progress-free because there is a finite number of hashes, the range of a 256-bit integer is so vast that it is practically progress-free.)

## The SHA Input is Irrelevant

In the Bitcoin blockchain the input is a block header. But if we just fed it random values, the probability of finding a conforming hash wouldÂ *still be the same*. Regardless of whether the input is a valid block header or bytes from /dev/random, it is going to take 10 minutes on average to find a solution. Of course if you find a conforming hash but your input wasnâ€™t a valid block, such a solution cannot be added to the blockchain, but it is still Proof-of-Work (albeit useless).

## The Difficulty is Intergalactic

Curiously, the difficulty isÂ *universal*, meaning it spans the entire universe. We could have miners on Mars helping out, they do not need to know, or communicate with the Earth miners, the problem would still be solved every 10 minutes. (Ok, theyâ€™ll need to somehow tell the Earth people that they solved it if they do, or else weâ€™ll never know about it.) Remarkably, the distant participants are communicating without actually communicating, because they are collectively solving the same statistical problem and yet theyâ€™re not even aware of each otherâ€™s existence. This â€śuniversal propertyâ€ť while at first seemingly magical is actually easy to explain. I used the term â€śuniversalâ€ť because it describes it well in one word, but really it means â€śknown by every participantâ€ť. The input to SHA-256 can be thought of as an integer between 0 and 2256Â (because the output is 32 bytes, i.e. also between 0 and 2256, anything larger guarantees a collision, i.e. becomes redundant). Even though it is extremely large (exponentially largerÂ than the number of atoms in the perceivable universe), it is a set of numbers that is known by every participant and the participants can only pick from this set. If the input set is universally known, the function (SHA-256) is universally known, as well as the difficulty requirement is universally known, then the probability of finding a solution is also indeed â€śuniversalâ€ť.

## Trying a SHA Makes You a Participant

If the stated problem is to find a conforming hash, all you have to do is to try it once, and bingo, youâ€™ve affected the global hash rate, and for that one attempt you were a participant helping others solve the problem. You did not need to tell others that you did it (unless you actually found a solution), others didnâ€™t need to know about it, but your attemptÂ *did*Â affect the outcome. For the whole universe, no less. If the above still seems suspicious, a good analogy might be the problem of finding large prime numbers. Finding the largest prime number is hard and once one is found, it becomes â€śdiscoveredâ€ť or â€śknownâ€ť. There is an infinite number of prime numbers, but only one instance of each number in the universe. Therefore whoever attempts to find the largest prime is working on the same problem, not a separate instance of it. You do not need to tell anyone you decided to look for the largest prime, you only need to announce when you find one. If no one ever looks for the largest prime, then it is never going to be found. Thus, participation (i.e. an attempt to find one), even if itâ€™s in total secrecy, still affects the outcome, as long as the final discovery (if found at all) is publicized. Taking advantage of this mind-boggling probabilistic phenomenon whereby any participation affects the outcome even if in complete secrecy and without success,Â *is*Â what makes Satoshiâ€™s invention so remarkably brilliant. It is noteworthy that since SHA is progress-free, each attempt could be thought of as a participant joining the effort and immediately leaving. Thus miners join and leave, quintillions of times per second.

## The Participation is Revealed in Statistics

The magical secret participation property also works in reverse. The global hashrate listed on many sites is known not because every miner registered at some â€śminers registration officeâ€ť where they report their hash rate periodically. No such thing exists. The hash rate is known because for a solution of a specific difficulty to be found in 10 minutes, on average this many attempts (~1021Â as of this writing) had to have been made by someone somewhere. We do not know who these participants are, they never announced that they are working, those who did not find a solution (which is practically all of them) never told anyone they were working, their location could have been anywhere in the universe, and yet we know with absolute certainty that they exist. Simply because the problem continues to be solved.

## Work is a Clock

And there is the crux of it: The difficulty in finding a conforming hash acts asÂ *a clock*. A universal clock, if you will, because there is only one such clock in the universe, and thus there is nothing to sync and anyone can â€ślookâ€ť at it. It doesnâ€™t matter that this clock is imprecise. What matters is that it is the same clock for everyone and that the state of the chain can be tied unambiguously to the ticks of this clock. This clock is operated by the multi-exahash rate of an unknown number of collective participants spread across the planet, completely independent of one another.

## Last Piece of the Puzzle

The solution must be the hash of a block (the block header, to be precise). As we mentioned, the input doesnâ€™t matter, but if it is an actual block, then whenever a solution is found, it happened at the tick of our Proof-of-Work clock. Not before, not after, butÂ *exactly at*. We know this unambiguosly because the block was part of that mechanism. To put it another way, if blocks werenâ€™t the input to the SHA256 function, weâ€™d still have a distributed clock, but we couldnâ€™t tie blocks to the ticks of this clock. Using blocks as input addresses this issue. Noteworthy, our Proof-of-Work clock only provides us with ticks. There is no way tell order from the ticks, this is what the hash chain is for.

## What About the Distributed Consensus?

Consensus means agreement. What all participants have no choice but to agree on is thatÂ *the clock has ticked*. Also that everyone knows the tick and the data attached to it. And this, in fact, does solve the Byzantine Generals Problem, as Satoshi explained in an email referenced earlier. There is a separate consensus in a rare but common case of two consecutive ticks being associated with conflicting blocks. The conflict is resolved by what block will be associated with the next tick, rendering one of the disputed blocks â€śorphanâ€ť. How the chain will continue is a matter of chance, and so this too could probably be indirectly attributed to the Proof-of-Work clock.

## And that is it

This is what Proof-of-Work does for the blockchain. It is not a â€ślotteryâ€ť where miners win the right to solve a block, nor is it some peculiar conversion of real energy into a valuable concept, those are all red herrings. For example the lottery and the minerâ€™s reward aspect is what encourages miners to participate, but it isnâ€™t what makes the blockchain possible. Blocks hashes form a chain, but again, that has nothing to do with Proof-of-Work, it cryptographically reinforces recording of the block ordering. The hash chain also makes the previous ticks â€śmore certainâ€ť, â€śless deniableâ€ť or simply more secure. Proof-of-Work is also the mechanism by which blocks become effectively immutable, and thatâ€™s a nice side-effect which makes Segregated Witness possible, but it could just as well be done by preserving the signatures (witness), so this too is secondary.

## Conclusion

The Bitcoin blockchain Proof-of-Work is simply a distributed, decentralized clock. If you understand this explanation, then you should have a much better grasp of how Proof-of-Work compares toÂ Proof-of-Stake, and it should be apparent that the two are not comparable: Proof-Of-Stake is about (randomly distributed) authority, while Proof-of-Work is a clock. In the context of the blockchain, Proof-of-Work is probably a misnomer. The term is a legacy from theÂ HashcashÂ project, where it indeed served to prove work. In the blockchain it is primarily about verifiably taking time. When one sees a hash that satisfies the difficulty, one knows it must have taken time. The method by which the delay is accomplished is â€śworkâ€ť, but the hash is primarily interesting because it is a proof ofÂ *time*. The fact that Proof-of-Work is all about time rather than work also suggests that there may be other similar statistical challenges that are time-consuming but require less energy. It may also mean that the Bitcoin hashrate is excessive and that the Bitcoin clock we described above could operate as reliably on a fraction of the hashrate, but it is the incentive structure that drives up the energy consumption. Figuring out a way to pace ticks with less work is a trillion dollar problem, if you find one, please do let me know! P.S. Special thanks toÂ Sasha TrubetskoyÂ ofÂ UChicago StatisticsÂ for the review and suggestions for the above text.