technical

The History of Casper — Chapter 1

Posted?by?Vlad Zamfir?on?December 6th, 2016.

Vitalik suggested last week that I share my basic research and design philosophy in a blog post, I agreed but complained that it was still changing. My friend Jon West told me that everyone would really appreciate it if I told everyone about my Casper research, I mostly agreed. Then someone on reddit told me to focus on Ethereum.

So here’s the Casper tech story, given as a chronological history of the evolution of the key technology, ideas and language that are involved in “Casper research”. Many of our favorite blockchain personalities are part of the story. This is my attempt to recount everything in an accessible, sequential way so that you can see where we are now (and where we’re going) with our research efforts (so don’t argue until the end of the story!). I’m going to try to release a chapter per day until it’s complete.

Also note that this is my personal point of view, understanding what little I could manage through the process of working on proof-of-stake. Vitalik and Greg Meredith’s accounts will vary, for example, as they each have their own view of Casper research.

Preface: How I started doing research at Ethereum

March 2013-April 2014

I immediately got hooked on the Blockchain technology story when Bitcoin first (really) caught my attention in March of 2013. This was during the “Cyprus crisis” run-up in the price of Bitcoin. I learned about cryptographic hashes, digital signatures and public key cryptography. I also learned about Bitcoin mining, and the incentives that miners have to protect the network. I was interested in computer science and security for the first time in my life. It was great.

Set against a narrative of dystopian libertarian economics, it was underground developers (like Amir Taaki) versus central bankers in an epic global battle to save the world from the fractional reserve banking system. The blockchain revolution was better than fiction.

I consumed content on reddit, listened to Lets Talk Bitcoin and a lot of Peter Todd content. I lost money on BTC-e (once because I took advice from the trollbox). I argued with my friends Ethan Buchman and Zach Ramsay about technology. We learned about MasterCoin and the possibility of building systems of top of Bitcoin, taking advantage of its Proof-of-Work network effect. When I first heard about proof-of-stake (PoS) in the 2013 alt-coin scene (thanks PPCoin!), I thought it sounded like heretical voodoo magic. Replacing miners with coins seemed like an inherently strange thing to try to do. I ended up deciding that the long-range attack problem was fatal, and any solutions were going to involve developer checkpoints of one form or another (an opinion I learned from Peter Todd). Being a Bitcoiner in 2013 was one of the most intellectually stimulating experiences of my life.

In Janurary or Feburary 2014, I read about Ethereum for the first time. I watched Vitalik’s youtube videos, and I met him in person at the Toronto Decentral Bitcoin Meetups. He obviously knew way more of the tech story than I did, so I became hooked in, this time on Ethereum. Ethereum was the promise of decentralization made accessible to me, someone without much background. It was general purpose smart contracts that could do anything, disrupt any centralized system. It could be and do so many things that it wasn’t always clear to me what role ethereum would actually play in the blockchain ecosystem. The blockchain tech story (as I see it) took an exciting turn with Ethereum, and I got to be closer to the action ??

Having been invited by Russel Verbeeten at one of these meetups, Ethan and I went to the hackathon prior to the 2014 Bitcoin Expo in Toronto. (Vitalik taught me how to use Merkle trees at this event.) I was thinking about properly incentivizing and decentralizing the peer review system for a couple of weeks, having recently had a paper rejected from an academic journal. Ethan and I tried putting this kind of system together at the hackathon. Ethan did most of the hard work using pyethereum, while I very slowly put together the first GUI I ever made. We came in second place at the hackathon (after Amir’s “Dark Market”, which became Open Bazaar). We got to meet the whole Ethereum team at the Expo, and we got ourselves invited to the public Skype channels! Charles Hoskinson offered us jobs: It was then, in April 2014, that we started volunteering for Ethereum. We even got @ethereum.org email addresses.

So I got into the blockchain space because I got hooked on the Bitcoin tech story, and then on the Ethereum tech story. I then got hooked on the proof-of-stake tech story, which I now know to be very compelling. I’m going to share it, being as faithful as possible to the timeline and manner in which the parts of picture have been coming together, in an effort to help bring everyone?up to speed on our efforts. It may take a few chapters, but story time ain’t over ’til it’s over.

Chapter 1: Slasher + Security Deposits: The move from naive proof-of-stake to modern proof-of-stake.

May 2014 – September 12, 2014

When Vitalik first expressed interest in PoS to me in May 2014, first over Skype and then at a Bitcoin conference in Vienna, I was skeptical. Then he told me about?slasher, which I think he had come up in January 2014. Slasher was the idea that you could lose your block reward if you sign blocks at the same height on two forks.

This gave Vitalik the ability to directly tackle (and arguably solve) the nothing-at-stake problem. (For the uninitiated, the “nothing-at-stake” problem refers to the fact that the PoS miners best strategy is to mine on all forks, because signatures are very cheap to produce). It also opened up our imaginations to a new space of interactive protocols for disincentivizing bad behaviour.

Still, I did not feel very satisfied with proof-of-stake at this time (despite Vitalik telling me a couple of times that he thinks “proof-of-stake is the future”) because I was really in love with proof-of-work. So during the summer I mostly worked on proof-of-work problems (ASIC-hard PoW, security sharing between PoW Chains via “Proofs-of-Proof-of-Work”, neither to completion). But I did suggest the use of security deposits to a couple of contract developers on a couple of different occasions. This planted the seed for insights made on the fateful post-Ethereum-meetup night of September 11th 2014 (kudos to Stephan Tual for organizing + getting me to that event!).

Ethan Buchman and I stayed up late talking about proof-of-stake at the “hacker” instead of the “party” section of Amir Taaki’s squat in London. I connected the dots and internalized the power of security deposits for proof-of-stake. This was the night that I became convinced that PoS would work, and that making it work would be a huge amount of fun. It was also the first time I experienced the surprising size of the PoS design space, through long arguments about attacks and possible protocol responses.

Since the early morning of September 12th, 2014 I have firmly advocated (to everyone who would listen) that blockchains move to PoS because it would be more secure. Amir Taaki was unimpressed by my enthusiasm for proof-of-stake. At least Ethan and I were having the best time.

The use of security deposits always significantly leveraged slasher’s effectiveness. Instead of forgoing some profit X, a provably faulty node would lose a security deposit (imagined to be on the order of size X/r) on which the block reward X was to be paid as interest (at rate r).

You place a deposit to play, and if you play nice you make a small return on your deposit, but if you play mean you lose your deposit. It feels economically ideal, and it’s so programmable.

Adding deposits to slasher meant that the nothing at stake problem was officially solved.

At least, I had made up my mind that it was solved to the point where we could no longer understand why anyone would want to build a proof-of-stake system without security deposits, for fear of nothing-at-stake problems.

Also on?September 12th, 2014 I met Pink Penguin for the first time, due to an introduction from Stephan Tual. I breathlessly recounted my PoS insights made the night before. And after I respectfully declined a job from from Eris Industries (now Monax) that week, Pink Penguin began sponsoring this?research! (Thanks <3!!)

At this point in the story I was unaware of the other, multiple independent discoveries of the use of security deposits in proof-of-stake systems made by Jae Kwon, Dominic Williams, and Nick Williamson.

Stay tuned… the next chapter is about the central role that ideas from game theory played in setting the design goals that led to Casper!

The History of Casper?—?Chapter?2

Reposted from the Ethereum blog.

This chapter describes the game theory and economic security modelling we were doing in the Fall of 2014. It recounts how the “bribing attacker model” led our research directly to a radical solution to the long range attack problem.

Chapter 2: The Bribing Attacker, Economic Security, and the Long Range Attack?Problem

Vitalik and I had each been reasoning about incentives as part of our research before we ever met, so the proposition that “getting the incentives right” was crucial in proof-of-stake was never a matter of debate.?We were never willing to take “half of the coins are honest” as a security assumption.?(It’s in bold because it’s important.) We knew that we needed some kind of “incentive compatibility” between bonded node incentives and protocol security guarantees.

It was always our view that the protocol could be viewed as a game that could easily result in “bad outcomes” if the protocol’s incentives encouraged that behaviour. We regarded this as a potential security problem. Security deposits gave us a clear way to punish bad behaviour; slashing conditions, which are basically programs that decide whether to destroy the deposit.

We had long observed that Bitcoin was more secure when the price of bitcoin was higher, and less secure when it was lower. We also now knew that security deposits provided slasher with more economic efficiency than slasher only on rewards.?It was clear to us that economic security existed and we made it a high priority.

The Bribing?Attacker

I’m not sure how much background Vitalik had in game theory (though it was clear he had more than I did). My own game theory knowledge at the start of the story was even more minimal than it is at the end. But I knew how to recognize and calculate Nash Equilibriums. If you haven’t learned about Nash Equilibriums yet, this next paragraph is for you.

A Nash Equilibrium is a strategy profile (the players’ strategy choices) with a corresponding payoff (giving $ETH or taking $ETH away) where no players individually have an incentive to deviate.?“Incentive to deviate” means “they get more $ETH if they somehow change what they’re doing”. If you remember that, and every time you hear “Nash Equilbrium” you thought “no points for individual strategy changes”, you’ll have it.

Some time in late summer of 2014, I first ran into “the bribing attacker model” when I made an offhand response to an economic security question Vitalik asked me on a Skype call (“I can just bribe them to do it”). I don’t know where I got the idea. Vitalik then asked me again about this maybe a week or two later, putting me on the spot to develop it further.

By bribing game participants you can modify a game’s payoffs, and through this operation change its Nash Equilibriums.?Here’s how this might look:

Image upload broken, so.. look here:?http://i.imgur.com/owE9V4c.png

The bribe attack changes the Nash Equilibrium of the Prisoner’s Dilemma game from (Up, Left) to (Down,Right). The bribing attacker in this example has a cost of 6 if (Down, Right) is played.

The bribing attacker was our first useful model of economic security.

Before the bribing attack, we usually thought about economic attacks as hostile takeovers by foreign, extra-protocol purchasers of tokens or mining power. A pile of external capital would have to come into the system to attack the blockchain. With the bribe attack, the question became “what is the price of bribing the currently existing nodes to get the desired outcome?”.

We hoped that the bribing attacks of our yet-to-be-defined proof-of-stake protocol would have to spend a lot of money to compensate for lost deposits.

Debate about “reasonableness” aside, this was our first step in learning to reason about economic security. It was fun and simple to use a bribing attacker. You just see how much you have to pay the players to do what the attacker wants. And we were already confident that we would be able to make sure that an attacker has to pay security-deposit-sized bribes to revert the chain in an attempted double-spend. We knew we could recognize “double-signing”. So we were pretty sure that this would give proof-of-stake a quantifiable economic security advantage over a proof-of-work protocol facing a bribing attacker.

The Bribing Economics of the Long Range?Attack

Vitalik and I applied the bribing attacker to our proof-of-stake research.?We found that PoS protocols without security deposits could be trivially defeated with small bribes. You simply pay coin holders to move their coins to new addresses and give you the key to their now empty addresses.?(I’m not sure who originally thought of this idea.) Our insistence on using the briber model easily ruled out all of the proof-of-stake protocols we knew about. I liked that. (At the time we had not yet heard of Jae Kwon’s Tendermint, of Dominic William’s now-defunct Pebble, or of Nick Williamson’s Credits.)

This bribe attack also posed a challenge to security-deposit based proof-of-stake: The moment after a security deposit was returned to its original owner, the bribing adversary could buy the keys to their bonded stakeholder address at minimal cost.

This attack is identical to the long range attack.?It is acquiring old keys to take control of the blockchain. It meant that the attacker can create “false histories” at will. But only if they start at a height from which all deposits are expired.

Before working on setting the incentives for our proof-of-stake protocol, therefore, we needed to address the long-range attack problem.?If we didn’t address the long range attack problem, then it would be impossible for clients to reliably learn who really had the security deposits.

We did know that developer checkpoints could be used to deal with the long-range attack problem. We thought this was clearly way too centralized.

In the weeks following my conversion to proof-of-stake, while I was staying at Stephan Tual’s house outside of London, I discovered that there was a natural rule for client reasoning about security deposits.?Signed commitments are only meaningful if the sender?currently?has a deposit.?That is to say, after the deposit is withdrawn, the signatures from these nodes are no longer meaningful. Why would I trust you after you withdraw your deposit?

The bribing attack model demanded it.?It would cost the bribing attacker almost nothing to break the commitments after the deposit is withdrawn.

This meant that a client would hold a list of bonded nodes, and stop blocks at the door if they were not signed by one of these nodes.?Ignoring consensus messages from nodes who don’t?currently?have security deposits solves/circumvents the long-range attack problem.?Instead of authenticating the current state based on the history starting from the genesis block, we authenticate it based on a list of who currently has deposits.

This is radically different from proof-of-work.

In PoW, a block is valid if it is chained to the genesis block, and if the block hash meets the difficulty requirement for its chain. In this security deposit-based model, a block is valid if it was created by a stakeholder with a currently existing deposit. This meant that you would need to have current information in order to authenticate the blockchain. This subjectivity has caused a lot of people a lot of concern, but it is necessary for security-deposit based proof-of-stake to be secure against the bribing attacker.

This realization made it very clear to me that the proof-of-work security model and the proof-of-stake security model are fundamentally not compatible. I therefore abandoned any serious use of “hybrid” PoW/PoS solutions. Trying to authenticate a proof-of-stake blockchain from genesis now seemed very obviously wrong.

Beyond changing the authentication model, however, we did need to provide a way to manage these lists of security deposits.?We had to use signatures from bonded nodes to manage changes to the list of bonded nodes, and we had to do it after the bonded nodes come to consensus on these changes.?Otherwise, clients would have different lists of bonded validators, and they would therefore be unable to agree on the state of Ethereum.

Bond time needed to be made long, so that clients have time to learn about the new, incoming set of bonded stakeholders.?As long as clients were online enough, they could keep up to date. I thought we would use twitter to share the bonded node list, or at least a hash, so that new and hibernating clients could get synchronized after their user enters a hash into the UI.

If you have the wrong validator list you can get?man-in-the-middled.?But it’s really not that bad. The argument was (and still is!) that?you only need to be able to trust an external source for this information once. After that once, you will be able to update your list yourself?—?at least, if you are able to be online regularly enough to avoid the “l(fā)ong range” of withdrawn deposits.

I know that it might take some getting used to. But we can only rely on fresh security deposits. Vitalik was a bit uncomfortable with this argument at first, trying to hold onto the ability to authenticate from genesis, but eventually was convinced by the necessity of this kind of subjectivity in proof of stake protocols. Vitalik independently came up with his?weak subjectivity scoring rule, which seemed to me like a perfectly reasonable alternative to my idea at the time, which was basically “have all the deposits sign every Nth block to update the bonded node list”.

With the nails in the nothing-at-stake and long-range attack coffins completely hammered in, we were ready to start choosing our slashing conditions.

The next chapter will document what we learned from our first struggles to define a consensus protocol by specifying slashing conditions. I’ll also tell you about what we learned from talking with fine people from our space about our research. The game theory and economic modelling story presented here will continue developing in Chapter 4.

The History of Casper?—?Chapter?3

This chapter describes our proof-of-stake research during the period starting after the discovery of the solution to the long-range attack problem and ending when we first became aware of the existence and relevance of traditional, pre-blockchain consensus research.

This “wild west” period is characterized by wide experimentation, exploration, and ignorance. Much of this chapter is therefore a collection of relatively disorganized protocol ideas. The period’s end is marked by my getting kicked out of a Financial Cryptography mailing list, and by my consequently learning about (and immediately becoming a fan of) Jae Kwon’s Tendermint.

Proof-of-stake consensus at “Ground?Zero”

September 20th 2014?—?December?2014.

We were initially been quite confident that we would soon “solve proof-of-stake”, having discovered solutions to the “fundamental” nothing-at-stake and the long-range attack problems. However, we quickly found that (almost) all of the key technical questions were still unanswered.

We didn’t know how blocks would be created. We didn’t know what the incentive mechanism would be exactly, only that it was clear that you would lose your deposit for “double-signing”, whatever that meant. We didn’t have a clear expression of the relationship between our protocol ideas and our often-implicit timing assumptions (e.g. synchronized clocks and predictable network latency). We relied on the idea that clients would eventually choose the same chain because they have the same fork-choice rule (to provide ‘consensus’) without fully realizing that this mechanism relies on strong synchrony assumptions.

Deposit rotation and Consensus Finality

From our solution to the long-range attack problem, we knew that we needed a way for the blockchain’s clients to agree on changes to the set of security deposits “with finality”, which is to say that the agreement is irreversible.

Forking of changes to the set of bonded stakeholders could mean that clients may permanently lose consensus: A client who goes offline at time T and is scheduled to return at time T + 1 needs to have the guarantee that the deposits that they saw placed at time T for time T + 1 were not since “unplaced” by forking in the blockchain.?See this illustration for clarification.Clients with incorrect information about the list of deposits may be easily attacked, as non-consensus security deposits have a price of 0.

From the start, then, we knew that we must have “finalized consensus” for proof-of-stake to work.

I had the idea of using the security deposits themselves to checkpoint the blockchain, replacing developer checkpoints with proof-of-stake checkpoints. The hashes of these checkpoints could be used by clients to authenticate changes to the list of deposits. These checkpoints would happen every X blocks, and the “checkpointing” of the block at height N*X would begin at height (N+1)*X (giving them time to agree, via the shared tail of their “l(fā)ongest chains”) and a super-majority of the bonded stake’s would be required, so that the existence of two valid checkpoints at a height would certainly result in the triggering of slashing conditions. (Vitalik generally prefers more continuous, lower overhead mechanisms, and independently came up with the?“weak subjectivity”?scoring rule to provide finality in a more gradual way.)

Sampling for “block makers” and “validation signatures”

It was initially pretty clear to us that we needed to have a system for sampling bonded stakeholders to produce blocks (with probability proportional to their security deposit), in an effort to produce a growing blockchain. It also became clear that we could easily reinforce the security of the blockchain by additionally sampling a set of bonded stakeholders to produce “validation signatures” on blocks, when they are created. Because stakeholders with deposits don’t need to do proof-of-work, they are able to contribute meaningful economic commitments immediately after seeing a new block.

I only spent a bit of effort reasoning about entropy generation for this sampling process at this time, because sampling is a defense against an attacker with a pre-defined proportion of bonded stake under their control, rather than against a bribing adversary (who would be able to bribe nodes after they are sampled). Our economic security, therefore, would have to come from slashing conditions resulting from the violation of economic commitments, rather than from sampling alone.

Slashing conditions:

So we began juggling slashing conditions. It was very easy to slash deposits when a bonded node creates or signs two blocks at the same height, and this was regarded as “clearly bad behaviour”.

How about two blocks on distinct forks at two different heights? This was tricky. We were sure that we needed to disincentivize forking, and forking could be caused by bonded stakeholder participation on any (other) fork. But we still had to allow bonded nodes the flexibility to make validation signatures on the fork that has the highest score?in their particular view, without being penalized. It’s perfectly honest to sign off on a block on fork 1 and then on a block on fork 2,?if fork 2 had a higher score than fork 1, at the time that the signature on fork 2 was created. This is exactly analogous to how it is perfectly honest for a PoW miner to mine a block on an attacker’s fork after it becomes longer than the “victim fork”. At the time we did not have the tools available to make signing on two forks at different heights a slashable offense without also penalizing bonded stakeholders for signing the highest scoring chain.

I explored slashing rules that hold bonded stakeholders to account to a commitment of form “I will never sign on blocks that are not an extension of this [given] blockchain”. I thought this rule could be very effective at preventing the chain from forking, if all bonded nodes could make that commitment about the same fork. If they couldn’t, however, then they would either no longer be able to participate or lose they would lose their deposits. This seemed very severe, so I knew that we had to be sure that bonded stakeholders are able to make this commitment on the same fork, for this slashing rule to work.

Considering this slashing rule was my first introduction to traditional consensus research, even though at the time I was not aware of its relevance or existence. Vitalik always wanted to keep the slashing rules simple, and (unless I’m mistaken) did not become a fan of cross-height slashing conditions until a few months later, when we later came to terms with “consensus state finality” via Casper’s “betting cycle”. In any case, I was unable to convince myself that bonded stakeholders would be able to make these commitments on the same fork (unless they were making the commitments on a very old block, such as in the checkpointing example given earlier in this chapter). Consensus is surprisingly hard.

Censorship of Byzantine proofs

Vitalik and I became concerned about the censorship of evidence of Byzantine behaviour, as such censorship could undermine the economic security of the security-deposit-based approach, as these proofs were necessary for triggering slashing conditions.

Note that, while we weren’t (or, at least I wasn’t) very aware of the actual content of traditional consensus research, we did use the term “Byzantine behaviour”, and (at least I) did regard the blockchain has having “solved the Byzantine generals problem”. I had picked this up from Andreas Antonopoulos during my days as a Bitcoiner.

I asserted that clients would be able to recognize censorship of Byzantine proofs by 1) observing the Byzantine proofs or provably Byzantine behaviour and 2) attempting to post these proofs to the chain. This process was to be used by an interactive client protocol, by which clients could regard the censoring blockchain to be invalid, or at least as having a lower score than non-censoring forks of the blockchain. I was not aware of the synchronicity assumptions that I was making, at this time.

The beginning of the end of the “wild west” of proof-of-stake

During November 2014, Peter Todd and Vinay Gupta each independently forced me to face the fact that I was making strong synchronicity assumptions (Peter Todd especially targeted my assumption that network messages like blocks and validation signatures would arrive to all clients in a reasonable amount of time, while Vinay focused on my assumption that clients would have synchronized clocks). They made me realize that I could not outsource the provision of synchronicity to the “networking stack”, but had to do my best to minimize the reliance that my proof-of-stake protocol(s) had on these assumptions. This marked the beginning of my interest in synchronicity assumptions. Yay!

I started defining a protocol that “ping ponged” messages accross the network to effectively create a heartbeat, rather than using clocks and timing assumptions regarding the arrival of messages. In my PoS protocol at the time, p% of the security deposits were sampled to give validation signatures on every block, and q% of these deposit-weighted signatures needed to be included by the next block in the chain, for that next block to be valid.

I struggled trying to skip offline block makers without making synchronicity assumptions and failed. No matter what I tried (without timing assumptions), it seemed possible for bonded stakeholders to disagree about whether or not to skip a block maker.

Economics and game theory versus computer science:

The Financial Cryptography mailing list contention.

I don’t precisely remember how I got invited, but somehow I became subscribed to a financial cryptography (and blockchains) mailing list, in November or December of 2014.

The mailing list was managed by our friends Emin Gün Sirer and Byron Gibson, who were making an effort to get academics involved in blockchain research.

Discussion about the relevance of economics to consensus was already on the way when I arrived. I remember that there were, broadly speaking, two factions of belief about the relevance of economics to blockchain-based consensus.

Vitalik, Jae Kwon, and I were more-or-less adamant that economic analysis was central to the research. We talked about security in terms of money spent by an adversary, be it lost deposits or electricity and capital costs in a PoW attack.

Nick Szabo (the clear leader of the opposing faction) argued that economic analysis was little better than “speculating about brain states” and instead insisted that fault tolerance and consensus protocol research (blockchain-based or not) was a pure computer science problem. Szabo argued that there were “big games” and “small games” in life, and that in-protocol incentives (small games) do not end up influencing the larger game very much, which has much larger incentives and payoffs.

Vitalik and I had the same response to this criticism; that even though it was true that “big games” would override the incentives of “l(fā)ittle games”, it was important for the in-protocol incentives to pull as much as possible in the direction of incentivizing that protocol guarantees are respected.

Dominic Williams held a sensible “middle ground” position, that it important to do the computer science and?then?to?subsequently?add incentive compatibility. After Szabo shared it, Dominic also became a bigfan of the “small games/big games” argument, repeating it to me many times throughout the years?:). Dominic’s view was more popular than my own; that the economics was fundamental to blockchain research, but that the traditional consensus research, on the other hand, was not.

I got kicked out of the mailing list when I “l(fā)ightly trolled” Nick Szabo by suggesting that one could not possibly ever be qualified to talk about blockchains without doing economic analysis, regardless of how much “computer science” one employed.

The reason cited for my “getting the boot” was my ignorance of traditional consensus protocol literature. And I was completely ignorant. I just strongly intuited that it could not be?that?relevant because it was not designed to be economic from ground zero.

This episode was the first time I became very aware of traditional consensus research. It planted the seeds of the general interest in (economic and non-economic) consensus protocols that I would eventually come to have. I wasn’t motivated to read the literature right away, by any means. It’s quite difficult literature. But my somewhat-willful ignorance made me feel a bit guilty about not reading the literature.

I want to quickly take this opportunity to thank Gün Sirer for his active and thoughtful engagement on this mailing list. I had never heard anyone speak about distributed systems and game theory with such a high level of precision and correctness. I think it helped me out!

My Introduction to Tendermint

This experience of arguing about economics and consensus on the mailing list is how I initially became acquainted with Jae Kwon and Tendermint.?Tendermint?is a security-deposit based proof-of-stake system that is based on?a traditional consensus protocol.

Upon reading the Tendermint whitepaper, and having a quick Skype call with Jae himself, I became comfortable making the claim that Tendermint was “the simplest secure proof-of-stake protocol”. Where I understood “secure” here means “secure against a bribing attacker who is attempting to fork the blockchain”.

Tendermint had (and still has!) the property that every block was finalized before it was added (“commited”) to the blockchain.?It guaranteed that at least 1/3 of the security deposits would be slashed in the event of any forks whatsoever, no matter how short the fork. This was much stronger of an anti-forking security property than I was able to find. It also meant that a lot of our security-deposit rotation problems could be easily handled. It was beautifully simple, especially compared to the proof-of-stake protocols I was working on at the time.

Tendermint was also the first consistency-favouring consensus protocol that I ever studied. Indeed, learning about Tendermint served as my introduction to traditional consensus protocols in general, and was therefore a formative experience, for my understanding of consensus protocols.

It was from Jae Kwon that Vitalik and I adopted the language of referring to bonded stakeholders as “bonded validators”, or “validators” for short.

Chapter 4 will cover a very important shift in our thinking about game theory and economics in the blockchain space. This change in perspective represents the most important part of Casper’s design philosophy.

The History of Casper?—?Chapter?4

This chapter describes the events that led to a fundamental change in our economic modeling assumptions. These changes represent the foundation of the methodologies that underlie the analysis and architecture that we are working hard to develop at the Ethereum research team (at least for the Casper and Sharding efforts). The design philosophy presented in this chapter (imho) strongly differentiates the work we’re doing at Ethereum from the work being done by every?other project in the space.

Meet The Oligopoly

In December of 2014, Matthew Wampler-Doty (MWD) joined the Ethereum research team. In one of our first Skype calls, MWD and I got into an argument about economic modelling in an early sharding protocol. I wanted to exclusively consider the budget that a bribing adversary would have to spend to cause the failure of a protocol guarantee in a particular shard, when thinking about the security of that guarantee. MWD insisted that we assume that the distribution of deposit sizes in a shard was sampled from?a Pareto distribution. We talked past each other, because the distribution of deposits does not necessarily affect the amount of deposits lost due to an attack. He accused me of making “strange linearity assumptions”, which is something I couldn’t understand through the bribing adversary model. This was my first hint that the concentration of wealth might be relevant to economic analysis of public blockchains.

In January 2015, Matthew Wampler-Doty, Jae Kwon, Ethan Buchman, Zackary Hess, Pink Penguin and I spent some time together in San Francisco. Our time together was kicked off by Cryptoeconomicon 1. Jae Kwon, Dominic Williams, Zack Hess, and I did?a panel on proof-of-stake. I gave a presentation about?cryptoeconomics as economic applied to achieving information security goals. MWD gave a talk where he showed that the problem of maximizing Ethereum miner revenue by choosing which transactions to include in blocks is (at least as hard as)?the knapsack problem.

“Tendermint is two dudes!” Matthew Wampler-Doty excitedly told me, one evening. He explained that a cartel of Tendermint validators with more than 2/3 of the security deposits would form, because it does not require participation from the remaining validators to create finalized blocks (these “non-cartel validators” have less than 1/3 of security deposits). These less than 1/3 of nodes would be censored and eventually removed from the validator set. A new cartel with more than 2/3 of the (now smaller) set of security deposits would then form, and this process would continue until only [at most] 2 validators remain.

This argument struck a major cord. It fundamentally changed the way that I think about economic modelling and game theory in the public blockchain space. It was the first concrete move from efficient/competitive economic models to oligopolistic models. It changed the unit of analysis from individual validators to cartels of validators. It represented a shift from “ordinary” (independent choice) game theory to?social choice/cooperative game theory.

This was a big change from the bribing adversary model. Instead of assuming that every node is willing and able to accept bribes, I instead assumed that profit-maximizing cartels would form, and that validators who are not in a cartel are not coordinating their strategy choices. I could then look at economic security in terms of how much money a cartel of a given size would lose when they undermine a protocol guarantee.

Our research team now had another usable model of economic security.

Unlike the bribing adversary, however, this model is?exceptionally?realistic. Cryptocurrency is incredibly concentrated. So is mining power. Oligopolistic competition is the norm in many “real-life” markets. Coordination between a small number of relatively wealthy validators is much easier than coordination between a large number of relatively poor validators. Cartels formation is completely expected, in our context.

So this is how I became committed to the design philosophy that motivates Casper, to this day:

Blockchain architecture is mechanism design for oligopolistic markets.

(When done correctly, at least…)

Thanks Matthew, your contributions have made a very significant and lasting impact on all of my work?—?you’re my hero!

A call to?action

Taking a break from history for a moment, I’m going to take a moment to review blockchain projects in the space, identifying profit maximizing cartels that directly benefit from undermining protocol guarantees.

Cartels of 51% of the miners of?any?proof-of-work blockchain have a direct incentive to censor the non-cartel miners. This almost doubles their revenue from block rewards (after difficulty adjustment). This problem exists in Bitcoin, Ethereum, Dogecoin, and ZCash (to give the imo most notable examples).

Cartels of 51% of staked coins of any naive proof-of-stake protocol have precisely the same ability to directly benefit from censoring non-cartel members. NXT, PPC, and NEM?—?I’m thinking about you (among others).

Cartels of 67% of bonded coins of any consistency-favouring “traditional” consensus protocol have a similar direct incentive to censor non-cartel members, while 34% of bonded coins in these protocols have the ability to censor transactions by vetoing blocks (by preventing consensus/finality). Cosmos (Tendermint) and Polkadot?—?I’m looking directly at you.

Every single project in this space, as far as I can tell, has serious problems under cartel analysis. It is not a norm to use cooperative game theory, or even to use much game theory at all. Most of the projects in our space rely on an assumption that there are not more than some number of faulty nodes (or some percentage of faulty stake).?Fault count assumptions are not appropriate for public blockchains, because public blockchains exist in an oligopolistic setting, where a very small number of miners or coin holders (or reputation holders, in more exotic architectures) control a vast majority of the weight in the consensus.

I want to call on all analysts and architects in the blockchain space to adopt oligopolistic market models and coordinated choice game theory as mainstays of their practice. They are absolutely realistic. If you don’t assume that there is a concentration of power, and that players coordinate their strategies, then you will be doing your clients a serious disservice. You’re leaving your clients to fend for themselves against the cartels.

I know it sounds hard to provide protocol guarantees in the context of these models, but?this is our context.?Difficulty of getting your software from where it is now to a place where cartels do not stand to benefit from screwing your clients is not an excuse for being negligent of your clients interests.

Over the remaining chapters of this history of Casper, I will document our progress defining Casper; a consensus protocol fit for an oligopolistic world.

The History of Casper?—?Chapter?5

In this chapter I recount the story of Casper’s birth as an application of the principles of Aviv Zohar and Jonatan Sompolinsky’s?GHOST?to proof-of-stake.

I called it “the friendly ghost” because of incentives designed to guarantee censorship resistance against the oligopolists: incentives that force the cartel to be friendly to non-cartel validators.

Censorship Resistance in the Cartel?Model

February 2015?—?friendly incentives

Having seen the oligopoly, I set out to find a way to create a proof-of-stake protocol that was robust under cartel analysis. It had to be the case, in this protocol, that the cartel was not incentivized to censor validators who are not in the cartel.

I realized by doing the cartel analysis of proof-of-work consensus, that a cartel of 51% was incentivized to censor the miners who are not in the cartel. They would immediately be rewarded with more fees and eventually also would get more block rewards (after difficulty re-adjustment).

I already knew that the strength of proof-of-stake over proof-of-work is that the protocol had access to the anti-Sybil assets (deposits), whereas proof-of-work blockchains could not directly handle mining power.

So I realized that it would be impossible for a proof-of-work protocol to detect that censorship had occurred, since proof-of-work was external to the protocol. This led to the observation that would (and will) forever characterize Casper research, as far as I’m concerned:

The cartel cannot censor the absence of censored validators.

[edit: clarification: this is to say that the cartel cannot hide the fact that the censored validators are missing]

So I saw that it is possible to create a protocol where the cartel was not incentivized to censor validators. And it was elegantly simple.?The cartel had to be punished whenever validators appeared to be missing.?It has to be punished severely enough and for long enough so that it is not in its interest to censor non-cartel members.

I was excited; this definitively showed that proof-of-stake was fundamentally more censorship resistant than proof-of-work, reaffirming my intuition that security deposits are king.

It was possible to see how this could be implemented: if a validator failed to get their blocks into the chain, all of the validators who did have their blocks in the chain would be penalized. It also became clear that?the cost of censorship resistance in the cartel model is that a validator could deliberately go offline in order to make online validators lose money.

It was therefore also necessary to penalize validators who go offline, because it could not be clear to the protocol whether they were being censored, or whether they were offline of their own accord.

I immediately suggested to Jae Kwon and Ethan Buchman that Tendermint should adopt this rule. They both rejected the idea because they thought it was unacceptable to penalize all of the validators when some validators go offline. Jae also argued that censorship would not be a problem because it would be noticed by the community, who would promptly rebel against the cartel and stop using the blockchain.

I reluctantly agreed that this was probably true, but did not feel that it justified not doing everything possible in-protocol to guarantee that the cartel wouldn’t censor non-cartel members.

A definition of decentralization

February or March 2015

Sometime early March (or was it February?), Matthew Wampler-Doty came up with an interesting definition of decentralization:

A protocol is decentralized only if it can fully recover from the permanent removal of all but one of its nodes.

This definition was inspired by biology, by the way that mycelium is able to recover from a single cell. The idea was very interesting because it led to the observation that Tendermint was?less decentralized?than traditional blockchain protocols like proof-of-work, or proof-of-stake as seen in PPC or NXT.

Tendermint can’t recover without a hard fork if the network doesn’t have more than 2/3 of validators-weighted-by-stake available to sign blocks. On the other hand, Bitcoin, PPC, and NXT would be able to recover if even a single miner or staker remained online (although it would take a very long for them to produce any blocks).

The Birth of The Friendly?Ghost

March 2015?—?GHOST meets proof-of-stake

Vitalik and Gavin Wood were set to visit me in London, mid March, and I was meant to be able to show them a specification for a proof-of-stake protocol, and I was nowhere near ready.

I desperately did my first dive into the traditional Byzantine fault tolerant consensus literature. And I hardly learned anything at all. What did become clear to me, however, was that the literature was almost entirely focused on consensus protocols that only ever make “safe decisions” (which roughly means “only creates finalized blocks on which all protocol-following nodes will eventually reach consensus”). These consensus protocols, like Tendermint, never had any forking.

I learned that?traditional byzantine fault tolerant consensus protocols require a “Byzantine quorum” to be available in order for the protocol to make decisions, and therefore would not be able to meet Matthew Wampler-Doty’s definition of decentralization.?A Byzantine quorum, by the way, is a set of nodes so large that it must contain a majority of correct nodes (this definition is parametric in a fault count; we will hear more about this in later chapters).

I therefore decided that I needed a consensus protocol that favoured availability, rather than only ever making safe decisions (favouring consistency). I needed a protocol that produced blocks optimistically, so that even one validator acting alone could produce a blockchain.

Achieving finality would still be possible (whenever it is also possible for a traditional protocol) by having a Byzantine quorum (if available) decide on blocks?after?they are produced.

With Vitalik and Gavin practically on my doorstep, I made the following decision in a bit of a confused and desperate state:?I would adapt GHOST for proof-of-stake.?I already knew and loved GHOST, because it informs part of the Ethereum proof-of-work specification.

I resolved that validators would produce a?DAG?of blocks and “validation signatures”?(signatures on blocks, which would attest to their validity and to their consensus weight).?There would be a function that would take any such DAG and returned a “canonical” ordering of transactions. A record of all of the consensus activity would be recorded in the DAG and would be used for incentivization.

And of course, if any validators failed to get their blocks into the canonical order?often enough, everyone would be penalized.

This description, although not actually a working, fully specified protocol, was general enough that I was confident that I could make it work.

It was?the shape of a protocol?that had these properties:

One validator would be able to produce the blockchain if necessary.

The DAG captured all of the information one could possibly find useful for the protocol’s incentive mechanisms.

Cartel censorship would be penalized.

I explained to Vitalik and Gavin the work that I had done. Neither were too impressed (since they had expected a full protocol spec), but both could see that I had done enough work to earn my paycheck (so I was happy!).

Casper was born as simply “the friendly ghost”, an adaptation of GHOST to proof-of-stake, complete with incentives that would make a cartel “friendly” to non-cartel validators.

How “the friendly ghost” became “Casper: The Friendly?Ghost”

A couple of people told me to name this “friendly ghost” “Casper” (unfortunately I can’t remember who with any certainty) before John Dilley convinced me to call the protocol “Casper” at a party at Jeremy Gardner’s “Crypto Castle”, in San Francisco.

At this party I trolled Andrew Poelstra with the idea that security-deposits solved the nothing-at-stake and long-range problems. (Don’t worry, concerned reader, we made up and had a nice time chatting in a friendly way, some time later.)

Coming up next, in the history of?Casper…

The following chapter will describe my struggle to define this “canonical ordering” function of the Casper DAGs. It includes the discovery of “by-block consensus” (an event that occurred before this party where Casper got its namesake). Finally, the chapter will end in Berlin in July of 2015, when Vitalik and I finally figured out how to make Casper converge with finality.