longest, although other approaches have been suggested. 25

As a result, there is always some uncertainty whether a transaction on the blockchain is permanent, although the probability that a block, once on the blockchain, will be replaced decreases exponentially with the number of blocks that follow it. 9, 20 If Bob uses Alice’s cryptocoupons to buy a car from Carol, Carol would be prudent to wait until Bob’s transaction is fairly deep in the blockchain to minimize the chances that it will be displaced by a fork.

Although Po W is currently the basis for the most popular cryptocurrencies, it is not the only game in town. There are multiple proposals where cryptocurrency ownership assumes the role of costly signaling, such as Ethereum’s Casper2 or Algorand. 10 Cachin and Vukolic3 give a comprehensive survey of blockchain consensus protocols.

Discussion. The distinction between private (or permissioned) blockchain systems, where parties have reliable identities, and only vetted parties can participate, and public (or permissionless) blockchain systems, where parties cannot be reliably identified, and anyone can participate, is critical for making sense of the blockchain landscape.

Private blockchains are better suited for business applications, particularly in regulated industries, like finance, subject to know-your customer and anti-money-laundering regulations. Private blockchains also tend to be better at governance. For example, the lack of any orderly procedure for updating the ledger protocol in response to changing circumstances has caused feuding factions to split both Ethereum6 and Bitcoin12 into distinct, incompatible currencies. Most prior work on distributed algorithms has focused on systems where participants have reliable identities.

Public blockchains are appealing for applications such as Bitcoin, which seek to ensure nobody can control who can participate, and participants may not be eager to have their identities known. Although PoW was invented by Dwork and Naor7 as a way to control spam, Nakamoto’s application of Po W to large-scale consensus was a genuine innovation, one that launched the entire blockchain field.

work. Every miner, and everyone else who cares, keeps a local copy of the ledger, kept more-or-less up-to-date over the gossip network.

Alice is still worried that crooked miners could cheat her customers. Most miners are probably honest, content to collect their fees, but there is still a threat that even a small number of dishonest miners might collude with one another to cheat Alice’s investors. Alice’s first idea is to have miners, identified by their IP addresses, vote via the Byzantine fault-tolerant consensus algorithm4 used in the frozen yogurt example.

Alice quickly realizes this is a bad idea. Alice has a nemesis, Sybil, who is skilled in the art of manufacturing fake IP addresses. Sybil could easily overwhelm any voting scheme simply by flooding the protocol with “ sock-puppet” miners who appear to be independent, but are actually under Sybil’s control.

We noted earlier that the frozen yo-
gurt supply chain blockchain was not
vulnerable to this kind of “Sybil attack”
because parties had reliable identities:
only Alice, Bob, and Carol were allowed
to participate, and even though they
did not trust one another, each one
knew they would be held accountable
if caught cheating. By contrast, Alice’s
Restaurant’s cryptocoupon miners do
not have reliable identities, since IP ad-
dresses are easily forged, and a victim
would have no recourse if Sybil were to
steal his coupons.

Essentially the same problem arises when organizing a street gang: how to ensure someone who wants to join the gang is not a plainclothes police officer, newspaper reporter, or just a freeloader? One approach is what sociologists call costly signaling: 29 the candidate is required to do something expensive and difficult to fake, like robbing a store, or getting a gang symbol tattoo.

In the public blockchain world, the most common form of costly signaling is called proof of work (Po W). In Po W, consensus is reached by holding a self-administered lottery among the miners to decide which transaction is appended next to the ledger. Here is the clever part: buying a lottery ticket is a form of costly signaling because, well, it is costly: expensive in terms of time wasted and electricity bills. Sybil’s talent for impersonation is useless to her if each of her sock puppet miners must buy an expensive, long shot lottery ticket.

Specifically, in the Po W lottery, miners compete to solve a puzzle, where solving the puzzle is difficult, but proving one has solved the puzzle is easy (see sidebar “Proof of Work Puzzles”). Simplifying things for a moment, the first miner to solve the puzzle wins the consensus, and gets to choose the next block to append to the ledger. If that block is valid, that miner also receives a reward (another coupon), but the other miners receive nothing, and must start over on a new puzzle.

As hinted, the previous paragraph was an oversimplification. In fact, PoW consensus is not really consensus. If two miners both solve the puzzle at about the same time, they could append blocks to the blockchain in parallel, so that neither block precedes the other in the chain. When this happens, the blockchain is said to fork. Which block should subsequent miners build on? The usual answer is to build on the block whose chain is

Figure 1. Pseudocode for DAO-like contract.

function withdraw(unit amount){ client = msg.sender: if (balance[ client ] >=amount}{ if (client . call . sendMoney(amount)){ balance[ client ] ¬–=amount;

}}}

Figure 2. Pseudocode for DAO-like exploit.

function sendMoney(unit amount){ victim = msg.sender; balance += amount; victim.withdraw(amount)

}

A cryptographic hash function H(∙) has the property that for any value v, it is easy to compute H(v), but it is infeasible to discover a v ′ ≠ v such that H(v ′) = H(v).

Cryptographic Hash Function