Proof-of-Work (PoW)
Last updated
Last updated
Before we get going, do me a solid and forget anything you ever heard about PoW. Most of it is wrong anyway. Before protesting, answer this one question: what are the security properties of the PoW protocol? If you think you know the answer then you already lost. It was a trick question. PoW is not a consensus protocol at all. So please, just clear your mind and let us take this from the top.
The 1973 novel Sybil by Americal journalist Flora Rheta Schreiber documents the story of the pseudonymous Syb Dorsett, and her experience being treated for dissociative identity disorder. Sybil was a remarkable case: coherently displayed sixteen independent personalities oblivious of each other.
Quite tactlessly, this inspired the term Sybil attack, describing a single attacker taking on many identities to interfere with online protocols (such as creating millions of accounts to sway a Twitter poll).
The term Sybil resistance describes any means to counter the possibility of a Sybil attack, either by making them impossible, or, more commonly, by making them extremely expensive.
The most common form of Sybil resistance is simply maintaining an access list of allowed participants and tracking their participation. For example, consider a presidential election. If we allow ourselves to simplify the process a bit, there is one ballot per voter, that can be used once for voting. This is implemented by an authority that issues these ballots and assures they are not reused.
This kind of System is called permissioned, and it is easy to realize that a permissioned system can never be decentralized. After all, there is a central authority that is in charge of granting permission, decide when it is abused, and sanction the abuser.
But we want to build decentralzied systems, so we must come up with better forms of Sybil resistance.
One thing to keep in mind is that BFT was designed to be distributed, but not necessarily decentralized. In particular, the BFT process happens after the list of participants has been determined, whereas Sybilness is used to form the list of participants.
BFTs precede the ambitions of a cryptographic decentralized economy. They were originally motivated by the need to distribute large computations to a cluster of many computers in a way that would remain robust even if some of the computers were faulty. In such architectures, there is an authority that has an access list of computers that participate in the computation and is responsible for piecing together the solution.
To advance from distribution to decentralization, we need a new paradigm. A way to allow users to attempt as many identities as they want, but somehow make it difficult to produce these identities. A system that inherently limits the ability of creating new identities without keeping any list of known or allowed identities.
The next natural thought is that perhaps we should make it so that creating an identity requires some effort? This thought naturally leads to the consideration of an interesting recent (at that time) work with completely different motivations.
In 1992, Cynthia Dwork (pronounced Dvork) and Moni Naor published a paper called , where they introduced a new idea that would later evolve into what we know as proof-of-work: requiring that each identity provides a proof that requires some effort to produce. Dwork and Naor's motivation was combatting junk mail. They figured that if they could require each e-mail to produce proof that requires say one-tenth of a cent of electricity, then it should not bother the average user too much. However, a spammer trying to send a hundred million e-mails will find themselves $100k short. But of course junk mail is just an application, the core idea was that by imposing processing requirements, we could mitigate spam, whether of voter identities or advertisements for enhancement performing pills. Thus proof-of-work was born.
Proof-of-work is a fascinating form of Sybilness, but it took a while before it caught the eye of the emerging movement of cypherpunks seeking to create a decentralized economy, and even when it did, it took about 16 years since Dwork and Naor's paper and until the pseudonymous Satoshi figured out how it could be used for a brave new form of consensus, a permissionless one.
Since then, many other forms of Sybil resistance emerged, most famously proof-of-stake. But the crypto landscape is not short of all sorts of mechanisms for proof-of-X. Some of them rely on physical resources, like proof-of-time-and-space that relies on provably sacrificing storage space for a given amount of time. Others, like proof-of-stake, proof-of-coverage, proof-of-reputation, and the rest rely on some intrinsic value such as coin holding, accrued reputation, and so on.
I surely don't know what went through Satoshi's pseudonymous mind at the time, but if I had to guess what was his eureka! moment, I would guess that it was the realization that PoW can use to prove the passage of time.
Satoshi, and the cypherpunks that preceded him, imagined a global ledger that anyone can append to. The problem is, of course, that two different messages could be appended at the same time, causing inconsistencies and disagreements. (Don't fret if you are not clear on that, we will dive deep into how Bitcoin works in a moment.)
Satoshi's thought was presumably along the lines of "what if we can somehow force the message to be so far apart that this could never happen? Too bad there is no way to enforce such a policy... or is there?" The key realization here is that by requiring enough work, we can guarantee that enough time passed...
...to an extent. There are several issues with this idea:
Second, it actually cannot guarantee even that. To use PoW as an accurate timer, one must know exactly how many hashes are computed per unit of time, a quantity that constantly changes and is impossible to measure. PoW chains are forced to handle this by using a difficulty adjustment algorithm: a way to approximate the changes in global hashrates through changes in block creation rates. These algorithms are hard to implement (in part, because we can't really know when a block was created since it is impossible to authenticate timestamps), and can enable new attack vectors.
Third, this kind of consensus doesn't fit nicely into the theoretical framework that existed at the time. Until Bitcoin, consensus algorithms were expected to provide deterministic finality, some line in the sand after which it is guaranteed that a transaction will not revert. Bitcoin can "only" provide probabilistic finality, the guarantee that the probability a transaction reverts becomes negligible very fast. This sounds a bit scary to muggles, but a cryptographer knows that essentially all modern cryptography relies on "up to a negligible security." (I mean, it doesn't matter how strong your password is, there is always some chance a hacker would guess it through sheer luck.)
For me, that third observation is a source of great joy. It initiated a brand new theory of probabilistic consensus that is still in its formative stage. It caused decade-old models to be revised and refined and made the theory much more interdisciplinary. I would say that the main reason I found myself in the field, to begin with, is that I love probability theory. If consensus was to remain deterministic and boring, this book might have never been written. Accordingly, the rest of the chapters in Part 1 are dedicated to guiding the reader through this brave, new world. But before that, we finish the current chapter, and our discussion of PoW vs. BFT.
First, it cannot actually guarantee how much time it took to create the block. The guarantee is quite weaker: that the average time between blocks is some predefined interval. In fact, that the block creation process is very noisy, which is likely what caused Satoshi to choose such a long block delay.