When you are selling a pizza and accepting Bitcoin, usually you wait “for a while” before you “confirm the transaction” and deliver the pizza. You are cautious because a fraudulent user may double spend—use the same bill to pay two different vendors.
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.
In this note, we are going to state the PCP theorem and its relation to the hardness of approximating some NP-hard problem.
PCP Theorem: the Interactive Proof View
Intuitively, a PCP (Probabilistically Checkable Proof) system is an interactive proof system where the verifier is given random bits and he is allowed to look into the proof in many locations. If the string is indeed in the language, then there exists a proof so that the verifier always accepts. However, if is not in the language, no prover can convince this verier with probability more than . The proof has to be short i.e., of size at most . This class of language is designated as PCP[r(n), q(n)].
Theorem A (PCP theorem). Every NP language has a highly efficient PCP verifier. In particular,
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.
Imagine that a particle is walking in a two-dimensional space, starting at the origin . At every time-step (or “epoch”) it takes a vertical step. At every step, the particle either moves up by , or down by . This walk is “unbiased” in the sense that the up/down steps are equiprobable.
In this post, we will discuss some natural questions about this “unbiased” or “simple” random walk. For example, how long will it take for the particle to return to zero? What is the probability that it will ever reach +1? When will it touch for the first time? Contents of this post are a summary of the Chapter “Random Walks” from the awesome “Introduction to Probability” (Volume I) by William Feller. Also, this is an excellent reference.
Edit: the Biased Case. The biased walk follows
The lazy walk follows
In the exposition, we’ll first state the unbiased case and when appropriate, follow it up with the biased case.