We improve the fundamental security threshold of eventual consensus Proof-of-Stake (PoS) blockchain protocols under the longest-chain rule by showing, for the first time, the positive effect of rounds with concurrent honest leaders. Current securit
y analyses reduce consistency to the dynamics of an abstract, round-based block creation process that is determined by three events associated with a round: (i) event $A$: at least one adversarial leader, (ii) event $S$: a single honest leader, and (iii) event $M$: multiple, but honest, leaders. We present an asymptotically optimal consistency analysis assuming that an honest round is more likely than an adversarial round (i.e., $Pr[S] + Pr[M] > Pr[A]$); this threshold is optimal. This is a first in the literature and can be applied to both the simple synchronous communication as well as communication with bounded delays. In all existing consistency analyses, event $M$ is either penalized or treated neutrally. Specifically, the consistency analyses in Ouroboros Praos (Eurocrypt 2018) and Genesis (CCS 2018) assume that $Pr[S] - Pr[M] > Pr[A]$; the analyses in Sleepy Consensus (Asiacrypt 2017) and Snow White (Fin. Crypto 2019) assume that $Pr[S] > Pr[A]$. Moreover, all existing analyses completely break down when $Pr[S] < Pr[A]$. These thresholds determine the critical trade-off between the honest majority, network delays, and consistency error. Our new results can be directly applied to improve the security guarantees of the existing protocols. We also provide an efficient algorithm to explicitly calculate these error probabilities in the synchronous setting. Furthermore, we complement these results by analyzing the setting where $S$ is rare, even allowing $Pr[S] = 0$, under the added assumption that honest players adopt a consistent chain selection rule.
We establish an uncertainty principle for functions $f: mathbb{Z}/p rightarrow mathbb{F}_q$ with constant support (where $p mid q-1$). In particular, we show that for any constant $S > 0$, functions $f: mathbb{Z}/p rightarrow mathbb{F}_q$ for which $
|text{supp}; {f}| = S$ must satisfy $|text{supp}; hat{f}| = (1 - o(1))p$. The proof relies on an application of Szemeredis theorem; the celebrated improvements by Gowers translate into slightly stronger statements permitting conclusions for functions possessing slowly growing support as a function of $p$.
We are given an integer $d$, a graph $G=(V,E)$, and a uniformly random embedding $f : V rightarrow {0,1}^d$ of the vertices. We are interested in the probability that $G$ can be realized by a scaled Euclidean norm on $mathbb{R}^d$, in the sense that
there exists a non-negative scaling $w in mathbb{R}^d$ and a real threshold $theta > 0$ so that [ (u,v) in E qquad text{if and only if} qquad Vert f(u) - f(v) Vert_w^2 < theta,, ] where $| x |_w^2 = sum_i w_i x_i^2$. These constraints are similar to those found in the Euclidean minimum spanning tree (EMST) realization problem. A crucial difference is that the realization map is (partially) determined by the random variable $f$. In this paper, we consider embeddings $f : V rightarrow { x, y}^d$ for arbitrary $x, y in mathbb{R}$. We prove that arbitrary trees can be realized with high probability when $d = Omega(n log n)$. We prove an analogous result for graphs parametrized by the arboricity: specifically, we show that an arbitrary graph $G$ with arboricity $a$ can be realized with high probability when $d = Omega(n a^2 log n)$. Additionally, if $r$ is the minimum effective resistance of the edges, $G$ can be realized with high probability when $d=Omegaleft((n/r^2)log nright)$. Next, we show that it is necessary to have $d geq binom{n}{2}/6$ to realize random graphs, or $d geq n/2$ to realize random spanning trees of the complete graph. This is true even if we permit an arbitrary embedding $f : V rightarrow { x, y}^d$ for any $x, y in mathbb{R}$ or negative weights. Along the way, we prove a probabilistic analog of Radons theorem for convex sets in ${0,1}^d$. Our tree-realization result can complement existing results on statistical inference for gene expression data which involves realizing a tree, such as [GJP15].
