[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 .
We consider a variant of Ouroboros where the random bits necessary for selecting the slot leaders for the next epoch come from a per-epoch random value, plus the random values from a certain prefix of the blocks issued in the current epoch. Because the random values do not depend on the contents of the block, the adversary cannot maliciously choose a block-content that affects the leader selection. He, however, has one of three options:
- Issuing a block and attaching it to the longest available chain
- Not issuing a block
- Issuing a block but linking it to a shorter, possibly malicious chain. If an honest block is bypassed by this maneuver, we say the adversary has skipped an honest player
We are interested in giving an upper bound to the expected number of competing chains that the adversary can possibly present to the leader selection process. This number would limit the choices for even a computationally-unbounded adversary. Not surprisingly, we call this number the grinding power of the adversary.
Continue reading “Characterizing the Adversarial Grinding Power in a Proof-of-Stake Blockchain Protocol”
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.
Continue reading “Forkable Strings are Rare”
In this post, I will discuss my own understanding of the spectral sparsification paper by Daniel Spielman and Nikhil Srivastava (STOC 2008). I will assume the following:
- The reader is a beginner, like me, and have already glanced through the Spielman-Srivastava paper (from now on, the SS paper).
- The reader has, like me, a basic understanding of spectral sparsification and associated concepts of matrix analysis. I will assume that she has read and understood the Section 2 (Preliminaries) of the SS paper.
- The reader holds a copy of the SS paper while reading my post.
First, I will mention the main theorems (actually, I will mention only what they “roughly” say).
Continue reading “Spectral Sparsification by Spielman and Srivastava: How They Connected the Dots”
How likely is it that the absolute value of a random variable will be greater than some specific value, say, ? The Russian mathematician Andrey Andreyevich Markov proved a simple, yet nice, result which enables us to answer the above question.
Markov’s Inequality states that if is a random variable with mean , and is a positive number, then
Continue reading “Markov’s Inequality”