Paper 2017/241

Forkable Strings are Rare

Alexander Russell and Cristopher Moore and Aggelos Kiayias and Saad Quader

Abstract

A fundamental combinatorial notion related to the dynamics of the Ouroboros proof-of-stake blockchain protocol (https://eprint.iacr.org/2016/889) is that of a forkable string. The original description and analysis of the protocol established that the probability that a string of length $n$ is forkable, when drawn from a binomial distribution with parameter $(1 - \epsilon)/2$, is $\exp(-\Omega(\sqrt{n}))$. In this note we improve this estimate to $\exp(-\Omega(n))$.