Cryptology ePrint Archive: Report 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))$.

Category / Keywords: cryptographic protocols/blockchain

Date: received 8 Mar 2017, last revised 20 Mar 2017

Contact author: acr at uconn edu

Available format(s): PDF | BibTeX Citation

Version: 20170320:171043 (All versions of this report)

Short URL: ia.cr/2017/241

Discussion forum: Show discussion | Start new discussion