If you have been involved in Bitcoin for any significant length of time, you have probably at least heard of the idea of “proof of work”. The basic concept behind proof of work is simple: one party (usually called the prover) presents the result of a computation which is known to be hard to compute, but easy to verify, and by verifying the solution anyone else can be sure that the prover performed a certain amount of computational work to generate the result. The first modern application, presented as “Hashcash” by Adam Back in 1996, uses a SHA256-based proof of work as an anti-spam measure – by requiring all emails to come with a strong proof-of-work attached, the system makes it uneconomical for spammers to send mass emails while still allowing individuals to send messages to each other when they need to. A similar system is used today for the same purpose in Bitmessage, and the algorithm has also been repurposed to serve as the core of Bitcoin’s security in the form of “mining”.
How does SHA256 Proof of Work Work?
SHA256 is what cryptographers call a “one-way function” – a function for which it is easy to calculate an output given an input, but it is impossible to do the reverse without trying every possible input until one works by random chance. The canonical representation of a SHA256 output is as a series of 64 hexadecimal digits – letters and numbers taken from the set 0123456789abcdef.
For example, here are the first digits of a few hashes:
SHA256("hello") = 2cf24dba...SHA256("Hello") = 185f8db3...SHA256("Hello.") = 2d8bd7d9...The output of SHA256 is designed to be highly chaotic; even the smallest change in the input completely scrambles the output, and this is part of what makes SHA256 a one-way function.
Finding an input whose SHA256 starts with ‘0’ on average takes 16 attempts, ’00’ takes 256 attempts, and so forth. The way Hashcash, and Bitcoin mining, work, is by requiring provers (ie. mail senders or miners) to find a “nonce” such that SHA256(message+nonce)starts with a large number of zeroes, and then send the valid nonce along with the message as the proof of work. For example, the hash of block 254291 is:000000000000003cf55c8d254fc97d2850547e5b787a936bc729497d76443a89
On average, it would take 72057 trillion attempts to find a nonce that, when hashed together with a block, returns a value starting with this many zeroes (technically, 282394 trillion since the POW requirement is a bit more complex than “starts with this many zeroes”, but the general principle is the same). The reason this artificial difficulty exists is to prevent attackers from overpowering the Bitcoin network and introducing alternative blockchains that reverse previous transactions and block new transactions; any attacker trying to flood the Bitcoin network with their own fake blocks would need to make 282394 trillion SHA256 computations to produce each one.
However, there is a problem: proof of work is highly wasteful. Six hundred trillion SHA256 computations are being performed by the Bitcoin network every second, and ultimately these computations have no practical or scientific value; their only purpose is to solve proof of work problems that are deliberately made to be hard so that malicious attackers cannot easily pretend to be millions of nodes and overpower the network. Of course, this waste is not inherently evil; given no alternatives, the wastefulness of proof of work may well be a small price to pay for the reward of a decentralized and semi-anonymous global currency network that allows anyone to instantly send money to anyone else in the world for virtually no fee. And in 2009 proof of work was indeed the only option. Four years later, however, we have developed a number of alternatives.
Sunny King’s Primecoin is perhaps the most moderate, and yet at the same time potentially the most promising, solution. Rather than doing away with proof of work entirely, Primecoin seeks to make its proof of work useful. Rather than using SHA256 computations, Primecoin requires miners to look for long “Cunningham chains” of prime numbers – chains of values n-1, 2n-1, 4n-1, etc. up to some length such that all of the values in the chain are prime (for the sake of accuracy, n+1, 2n+1, 4n+1 can also be a valid Cunningham chain, and Primecoin also accepts “bi-twin chains” of the form n-1, n+1, 2n-1, 2n+1 where all terms are prime).
It is not immediately obvious how these chains are useful – Primecoin advocates have pointed to a few theoretical applications, but these all require only chains of length 3 which are trivial to produce. However, the stronger argument is that in modern Bitcoin mining the majority of the production cost of mining hardware is actually researching methods of mining more efficiently (ASICs, optimized circuits, etc) and not building or running the devices themselves, and in a Primecoin world this research would go towards finding more efficient ways of doing arithmetic and number theory computation instead – things which have applications far beyond just mining cryptocurrencies.
The reason why Primecoin-like “useful POWs” are the most promising is that, if the computations are useful enough, the currency’s “waste factor” can actually drop below zero, making the currency a public good. For example, suppose that there is a computation which, somehow, has a 1 in 1020chance of getting researchers significantly further along the way to curing cancer. Right now, no individual or organization has much of an incentive to attempt it: if they get lucky and succeed, they could either release the secret and earn little personal benefit beyond some short-lived media recognition or they could try to sell it to a few researchers under a non-disclosure agreement, which would rob everyone not under the non-disclosure agreement of the benefits of the discovery and likely not earn too much money in any case. If this magic computation was integrated into a currency, however, the block reward would incentivize many people to perform the computation, and the results of the computations would be visible on the blockchain for everyone to see. The societal reward would be more than worth the electricity cost. However, so far we know of no magical cancer-curing computation; the closest is Folding@home, but it lacks mathematical verificability – a dishonest miner can easily cheat by making fake computations that are indistinguishable from real results to any proof of work checker but have no value to society. As far as mathematically verifiable useful POWs go, Primecoin is the best we have, and whether its societal benefit fully outweighs its production and electricity cost is hard to tell; many people doubt it. But even then, what Primecoin accomplished is very praiseworthy; even partially recovering the costs of mining as a public good is better than nothing.
Proof of Stake
However, there is one SHA256 alternative that is already here, and that essentially does away with the computational waste of proof of work entirely: proof of stake. Rather than requiring the prover to perform a certain amount of computational work, a proof of stake system requires the prover to show ownership of a certain amount of money. The reason why Satoshi could not have done this himself is simple: before 2009, there was no kind of digital property which could securely interact with cryptographic protocols. Paypal and online credit card payments have been around for over ten years, but those systems are centralized, so creating a proof of stake system around them would allow Paypal and credit card providers themselves to cheat it by generating fake transactions. IP addresses and domain names are partially decentralized, but there is no way to construct a proof of ownership of either that could be verified in the future. Indeed, the first digital property that could possibly work with an online proof of stake system is Bitcoin (and cryptocurrency in general) itself.
There have been several proposals on how proof of stake can be implemented; the only one that is currently working in practice, however, is PPCoin, once again created by Sunny King. PPCoin’s proof of stake algorithm works as follows. When creating a proof-of-stake block, a miner needs to construct a “coinstake” transaction, sending some money in their possession to themselves as well as a preset reward (like an interest rate, similar to Bitcoin’s 25 BTC block reward). A SHA256 hash is calculated based only on the transaction input, some additional fixed data, and the current time (as an integer representing the number of seconds since Jan 1, 1970). This hash is then checked against a proof of work requirement, much like Bitcoin, except the difficulty is inversely proportional to the “coin age” of the transaction input. Coin age is defined as the size of the transaction input, in PPcoins, multiplied by the time that the input has existed. Because the hash is based only on the time and static data, there is no way to make hashes quickly by doing more work; every second, each PPCoin transaction output has a certain chance of producing a valid work proportional to its age and how many PPCoins it contains, and that is that. Essentially, every PPCoin can act as a “simulated mining rig”, albeit with the interesting property that its mining power goes up linearly over time but resets to zero every time it finds a valid block.
It is not clear if using coin age as PPCoin does rather than just output size is strictly necessary; the original intent of doing so was to prevent miners from re-using their coins multiple times, but PPCoin’s current design does not actually allow miners to consciously try to generate a block with a specific transaction output. Rather, the system does the equivalent of picking a PPCoin at random every second and maybe giving its owner the right to create a block. Even without including age as a weighting factor in the randomness, this is roughly equivalent to a Bitcoin mining setup but without the waste. However, there is one more sophisticated argument in coin age’s favor: because your chance of success goes up the longer you fail to create a block, miners can expect to create blocks more regularly, reducing the incentive to dampen the risk by creating the equivalent of centralized mining pools.
Beyond Cryptocurrency
But what makes proof of stake truly interesting is the fact that it can be applied to much more than just currency. So far, anti-spam systems have fallen into three categories: proof of work, captchas and identity systems. Proof of work, used in systems like Hashcash and Bitmessage, we have already discussed extensively above. Captchas are used very widely on the internet; the idea is to present a problem that a human can easily solve but a computer can’t, thereby distinguishing the two (CAPTCHA stands for “Completely Automated Public Turing test to tell Computers and Humans Apart”). In practice, this usually involves presenting a messy image containing letters and numbers, and requiring the solver to type in what the letters and numbers are. Recent providers have implemented a “public good” component into the system by making part of the captcha a word from a printed book, using the power of the crowd to digitize old printed literature. Unfortunately, captchas are not that effective; recent machine-learning efforts have achieved success rates of 30-96 – similar to that of humans themselves. Identity systems come in two forms. First, there are systems that require users to register with their physical identity; this is how democracies have so far avoided being overrun by anonymous trolls. Second, there are systems that require some fee to get into, and moderators can close accounts without refund if they are found to be trying to abuse the system. These systems work, but at the cost of privacy.
Proof of stake can be used to provide a fourth category of anti-spam measure. Imagine that, instead of filling in a captcha to create a forum account, a user can consume coin age by sending a Bitcoin or PPCoin transaction to themselves instead. To make sure each proof of stake computation is done by the user, and not simply randomly pulled from the blockchain, the system might require the user to also send a signed message with the same address, or perhaps send their money back to themselves in a specific way (eg. one of the outputs must contain exactly 0.000XXXXX BTC, with the value randomly set each time). Note that here coin age is crucial; we want users to be able to create proofs of stake on demand, so something must be consumed to prevent reuse. In a way, a form of proof of stake already exists in the form of SMS verification, requiring users to send text messages to prove ownership of a phone to create a Google account – although this is hardly pure proof of stake, as phone numbers are also heavily tied with physical identity and the process of buying a phone is itself a kind of captcha. Thus, SMS verification has some of the advantages and some of the disadvantages of all three systems.
But proof of stake’s real advantage is in decentralized systems like Bitmessage. Currently, Bitmessage uses proof of work because it has no other choice; there is no “decentralized captcha” solution out there, and there has been little research into figuring out how to make one. However, proof of work is wasteful, and makes Bitmessage a somewhat cumbersome and power-consuming system to use – for emails, it’s fine, but for instant messaging forget about it. But if Bitmessage could be integrated into Bitcoin (or Primecoin or PPCoin) and use it as proof of stake, much of the difficulty and waste could be alleviated.
Does proof of stake have a future? Many signs suggest that it certainly does. PPCoin founder Sunny King argues that Bitcoin’s security will become too weak over time as its block reward continues to drop; indeed, this is one of his primary motivations for creating PPCoin and Primecoin. Since then, PPCoin has come to be the fifth largest cryptocurrency on the market, and an increasing number of new cryptocurrencies are copying its proof-of-stake design. Currently, PPCoin is not fully proof-of-stake; because it is a small cryptocurrency with a highly centralized community, the risk of some kind of takeover is higher than with Bitcoin, so a centralized checkpointing system does exist, allowing developers to create “checkpoints” that are guaranteed to remain part of the transaction history forever regardless of what any attacker does. Eventually, the intent is to both move toward making the checkpointing system more decentralized and reducing its power and PPCoins come to be owned by a larger group of people. An alternative approach might be to integrate proof of stake as a decentralized checkpointing system into Bitcoin itself; for example, one protocol might allow any coalition of people with at least 1 million BTC-years to consume their outputs to generate a checkpoint that the community would agree is a valid block, at the cost of sending their coins to themselves and consuming coin age.
In 2009, cryptocurrency emerged as the culmination of a number of unrelated cryptographic primitives: hash functions, Merkle trees, proof of work and public key cryptography all play key roles in Bitcoin’s construction. Now, however, Bitcoin and cryptocurrencies are here to stay, and this presents another exciting possibility for the future of cryptography: we can now design protocols that build off of cryptocurrency itself – of which proof of stake is the perfect example. Proof of stake can be used to secure a cryptocurrency, it can be used in decentralized anti-spam systems, and probably in dozens of other protocols that we haven’t even thought of yet – just like no one had thought of anything like Bitcoin until Wei Dai’s b-money in 1998. The possibilities are endless.