Dropbox Paper

What makes blockchains secure? [4/5]

In the past three parts of this series, we investigated probabilistic threat models for comparing blockchain protocol guarantees and estimating liveness and safety. The last blog post, in particular, illustrated how the choice of probabilistic model can lead a transformation that transfers some guarantees from one blockchain model to another. In light of this, a natural set of questions to ask are:

Can guarantees from an arbitrary single chain protocol be transferred to any other single chain protocol?

The reason for excluding multiple chain protocols is that inter-shard communication and hiding schemes add in enough non-determinism to make it hard to evaluate whether certain properties are actually the same

How do we figure out what guarantees are transferable between seemingly different protocols?

Can we construct a taxonomy of protocols that connects protocols based on their probabilistic properties?

Can we use these transferable features to determine our protocol resistant to ‘small’ perturbations or changes?

These small changes could arise due to an implementation detail when one is writing a client or if there is a sudden change in the demographics within our blockchain system (e.g. if there is a shock and 50% of miners / validators stop mining / validating)

This post will try to answer these questions by generalizing the notion of ideal functionality, which is commonly used in the blockchain literature to prove guarantees on a variety of protocols:

Arbitrum [Off-Chain Labs]

Avalanche [Ava]

Ekiden [Oasis Labs]

GRANDPA [PolkaDot]

Hawk

Ouroboros [Cardano]

Zexe

We aim to show that ideal functionalities, at least as used in the blockchain literature, are equivalent to the mathematical concept of universality. At a high-level, universality is the idea that seemingly unrelated complex systems that are made up of individual units (transactions, people, atoms, DNA, etc.) with different microscopic or local behaviors can actually have the same macroscopic/collective/global behavior. The simplest notion of a universal law that you might have experience with is the Central Limit Theorem (CLT), which states that the sum of independent, identically distributed random variables divided by

\sqrt{n}

converges in distribution to the familiar Bell curve (or Gaussian distribution) [0]:

Convergence of different distributions (normalized via a Z-score:

\tilde{X} = \frac{X-\mu_n}{\sigma_n}

) to a standard normal

Z = \mathcal{N}(0,1)

Fields Medalist Terence Tao has an excellent presentation for non-experts that explain how universality occurs in a plethora of seemingly unrelated natural contexts and how it shows up in unexpected places in mathematics. Our goal is to take these ideas and show how they manifest themselves within the blockchain literature. Once we do this, it will be a lot easier to answer the above questions and figure out how to we might make a statistical taxonomy of consensus protocols.

P.S. While it was hard to avoid using the words and phrases, Virasoro Algebra, hitting time, and martingale, this is the first and last time that they will appear within this post.

In the second blog post of this series, we spoke about environments that show up within the analysis of blockchain protocols. Recall that the idea of an environment is to encode the total state of the blockchain system (over all participants) in an object with random and deterministic components that closely approximate what the underlying protocol is doing. This allows us to analyze the entire blockchain system in the same way that one analyzes random algorithms (e.g. using classical methods from books like Randomized Algorithms by Motwani and Raghavan). Environments help by centralizing the analysis and making the game theoretic aspects of a protocol more transparent. However, environments are often times too difficult to analyze directly. This difficulty stems from subtle correlations and dependencies between steps in a protocol. Before going further, let's look at a few examples:

Bitcoin: The order of arrival of blocks on different forks affects which fork a given miner will choose. To statistically analyze the chain growth, chain quality, and liveness of the chain, we will have to average over all permutations of block arrivals

PoS: If multiple users are to get slashed for signing on an invalid fork (to prevent nothing-at-stake attacks), then the ordering in which they get slashed is ambiguous. To correctly compute the probability that the system will fail (e.g. will have insufficient chain growth, chain quality, or liveness), we will need to compute this probability over all orderings of slashes.

Such ordering complexities make probabilistic analysis untenable — we have dramatically increased the size of our probability space, decreasing the ease and efficiency of computing moments (such as means and variance), tail bounds, and rates of convergence. How do we get around this?

The intuitive answer goes back to Satoshi and his famously incorrect Poisson analysis of fork probabilities in the original Bitcoin paper. The idea is that the probability of ordering being important decays quickly — hopefully, exponentially — in a system parameter and you can compute statistics as if these ordering complexities don't matter. If you need to have more precise control about how ordering affects an observable, you can add in a decaying correction term to account for this. Let’s illustrate this via a simple example example. Suppose that

\lambda

is the block production rate of a Bitcoin system and that

H_i(t)

represents the height of blockchain of the

i

th miner in a Bitcoin system at time

t

, which is a random variable. It can be shown that under synchrony and partial asynchrony,

H_i(t) = H(t) + o\left(\frac{\lambda}{\sqrt{n}}\right)

for a deterministic, linear function

H(t)

(see the analysis here, for instance). Ideal functionalities aim to formalize this intuition in a more rigorous manner than Satoshi. They generically do this in the following manner:

Construct a simpler model, which is usually referred to as ideal functionality, that doesn't have the correlation or complexity that is vexing your analysis. In the cryptography literature, this is referred to as the hybrid method.

Show that the probability that the true model differs from the ideal functionality can be bounded by an error tolerance that is a function of parameters controlled by the protocol designer

An an example, let’s go through how this works for Bitcoin (as represented by Pass, Shelat, and Seeman):

Originally, we define Bitcoin as close to the original spec as possible:

We have a multiplayer game where there are a number of rounds. Each round is demarcated by an evaluation of a hash function (in the random oracle model)

Each user is allow to compute one hash per round but can has an unlimited number of verification queries; this is done to replicate

The oracle determines if a hash is valid (e.g. $H(x)<D_p$ , where $D_p$ is the current difficulty)

We reduce this to an ideal functionality that removes the explicit hashing and simply draws a random fork with the right probability (e.g. $\frac{D_p}{2^{\ell}}$ where $\ell$ is the bit width of the hash):

User-uploaded image: Screen+Shot+2019-02-06+at+1.04.37+PM.png

Taken from Pass, Shelat, Seeman

To use a hybrid argument, we need to show that these two models are ‘close’. The Poisson arrival times of Bitcoin blocks coupled with the random oracle model are used to show that the second model is “close” if the Poisson parameter is large enough (e.g. the block production rate is large enough [1]). All of the aforementioned protocols utilize a statistical reduction of this form to provide protocol security guarantees. This probabilistic transformation from a complex model to a simple one will be our guide as we aim to connect Blockchain analysis to modern probability theory. But first, we will need to take a detour through statistical physics to see an example of a universal model that naturally has blockchain-style ‘voting’ dynamics.

Universal probabilistic laws provide a way to take sequences of random variables and show that their tail bounds and moments are equal. While the first universal law discovered was inspired by gambling and games of chance (the CLT, discovered by Carl Friedrich Gauss and, to some extent, Daniel Bernoulli [2]), the subsequent examples of universal laws came from statistical and high-energy physics. These areas of physics study complex systems — systems of millions of particles and highly coupled particle systems that are recovered from smashing atoms together, respectively — and aim to find laws that hold statistically, regardless of the precise initial conditions of an experiment [3]. Over time, Physicists discovered that for many systems, one finds universal laws at different large parameter scales that correspond to ‘zooming out’ (in some parameter) enough. The following picture is a visual representation of this using the Ising Model, a prototypical model for how iron can be magnetized at low temperatures, but cannot at higher temperatures. The simplest version of the model represents molecules as points on a lattice that either have a +1 or a -1, representing their net spin [4], and each molecule’s probability of being a +1 or -1 is influenced by polling it’s neighbors (treating the lattice as a graph) and deciding whether +1 or -1 is in the majority [5]. This idea that your neighbors’ votes influence your vote is how we will be able to make the connection back to distributed consensus. In the following picture, we see images of the two-dimensional Ising Model at different temperatures (red and blue represent +1 and -1):

The transition from purely random (the upper left box) at high temperatures to much more structured clusters corresponds to going from a purely random microscopic description (e.g. particles moving about randomly) to undergoing to a phase transition and having well-defined clusters (e.g. magnetized, correlated particles). When these clusters are more aligned to one color than the other, then the material is magnetized in the direction of that color. This color alignment is very similar to consensus — when the system can magnetize to a non-zero number $m$ , then the system has reached consensus on that the value is $m + |m|\min(1-m,m+1)$ (e.g. round to $\pm 1$ ). On the other hand, if the system is at a high temperature and cannot magnetize (on average) then we do not reach consensus. In this setting, temperature serves as a parameter that controls a phase transition between when the system is able to reach ‘consensus’ on average (e.g. has non-trivial magnetization) or not. At this point, you might be wondering if phase transition behavior shows up in existing blockchain analysis, since many protocols seem to have a similar behavior (albeit with different parameters than a physical temperature). It turns out it does — take a look at the following theorem statements:

User-uploaded image: pass_seeman_shelat_thm.png

Main theorem from Pass, Shelat, Seeman, Analysis of the Blockchain Protocol in Asynchronous Networks

User-uploaded image: ouroboros_prao_thm4.png

Theorem 4 from Ouroboros Praos, which provides concentration bounds on the stake distribution

User-uploaded image: ekiden_main_thm.png

Ekiden Theorem, reduction to blockchain security