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 “longest 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 “little 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 “lightly 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.