I gave a talk in our seminar about the proof-of-work vs. the proof-of-stake blockchain paradigm. Although I don’t have an audio/video recording, here is a Google Slides rendering of my original Powerpoint slides. Some of the animations are out of place/order, but in general, it feels okay.
I intended this talk to be accessible in nature, so I intentionally skipped many details and strived not to flaunt any equation in it.
Advertised Summary: Bitcoin is a blockchain protocol where finalized transactions need a “proof of work”. Such protocols have been criticized for a high demand for computing power i.e., electricity. There is another family of protocols which deals with a “proof of stake”. In these protocols, the ability to make a transaction depends on your “stake” in the system instead of your computing power. In both cases, it is notoriously difficult to mathematically prove that these protocols are secure. Only a handful of provably secure protocols exist today. In this talk, I will tell a lighthearted story about the basics of the proof-of-work vs. proof-of-stake protocols. No equations but a lot of movie references.
Please enjoy, and please let me know your questions and comments.
A blockchain protocol is essentially a distributed consensus protocol. A Proof-of-Work protocol such as Bitcoin requires a user to show a proof — such as making a large number of computations — before he can add a block to an existing chain. Proof-of-Stake protocols, on the other hand, would not require “burning electricity” since the ability to “mine” a coin would depend only on the user’s current stake at the system.
The growing computing power of the bitcoin miners is already consuming a significant amount of electricity. One can easily see the necessity of a provably secure and efficient cryptocurrency without the heavy energy requirement. However, it is easier said than done. So far, I am aware of only three Proof-of-Stake protocols which give provable security guarantees. These are Ouroboros, led by Aggelos Kiayias, Alex Russell, and others; Snow White, led by Rafael Pass and Elaine Shi; Ouroboros Praosfrom the Ouroboros team; and Algorand, led by Silvio Micali. There is also an open-source initiative to implement Ourorboros, named Cardano.
In this post, I am going to present the main theorems of Ouroboros.
[Contents of this post are based on an ongoing discussion with Alex Russell and Aggelos Kiayias. It contains potentially unpublished material.]
In a proof-of-stake blockchain protocol such as Ouroboros, at most half of the users are dishonest. While an honest user always extends the longest available blockchain, the dishonest users try to fool him into extending a manipulated blockchain. Here, the user who is allowed to issue a block at any time-slot is called the “slot leader.” As it happens, a number of future slot leaders are computed in advance using the random values present in the blocks. Although counterintuitive, such a scheme ensures that if the adversary does not control more than half the users now, it is very unlikely that he cannot control more than half the slot leaders. The time-slots are divided into “epochs” of length .
In a blockchain protocol such as Bitcoin, the users see the world as a sequence of states. A simple yet functional view of this world, for the purpose of analysis, is a Boolean string of zeros and ones, where each bit is independently biased towards favoring the “bad guys.”
A bad guy is activated when for some . He may try to present the good guys with a conflicting view of the world, such as presenting multiple candidate blockchains of equal length. This view is called a “fork”. A string that allows the bad guy to fork (with nonnegligible probability) is called a “forkable string”. Naturally, we would like to show that forkable strings are rare: that the manipulative power of the bad guys over the good guys is negligible.
Claim (, Bound 2). Suppose is a Boolean string, with every bit independently set to with probability for some . The probability that is forkable is at most .
In this post, we present a commentary on the proof that forkable strings are rare. I like the proof because it uses simple facts about random walks, generating functions, and stochastic domination to bound an apparently difficult random process.