We describe and analyze a simple protocol for$n$parties that implements a randomness beacon: a sequence of high entropy values, continuously emitted at regular intervals, with sub-linear communication per value. The algorithm can tolerate a$(1-\epsilon)/2$fraction of the$n$players to be controlled by an adaptive adversary that may deviate arbitrarily from the protocol. The randomness mechanism relies on verifiable random functions (VRF), modeled as random functions, and effectively stretches an initial$\lambda$-bit seed to an arbitrarily long public sequence so that (i) with overwhelming probability in k-the security parameter-each beacon value has high min-entropy conditioned on the full history of the algorithm, and (ii) the total work and communication required per value is$O(k)$cryptographic operations. The protocol can be directly applied to provide a qualitative improvement in the security of several proof-of-stake blockchain algorithms, rendering them safe from “grinding” attacks.

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 security 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 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.

The blockchain data structure maintained via the longest-chain rule—popularized by Bitcoin—is a powerful algorithmic tool for consensus algorithms. Such algorithms achieve consistency for blocks in the chain as a function of their depth from the end of the chain. While the analysis of Bitcoin guarantees consistency with error 2−k for blocks of depth O(k), the state-of-the-art of proof-of-stake (PoS) blockchains suffers from a quadratic dependence on k: these protocols, exemplified by Ouroboros (Crypto 2017), Ouroboros Praos (Eurocrypt 2018) and Sleepy Consensus (Asiacrypt 2017), can only establish that depth Θ(k2) is sufficient. Whether this quadratic gap is an intrinsic limitation of PoS—due to issues such as the nothing-at-stake problem—has been an urgent open question, as deployed PoS blockchains further rely on consistency for protocol correctnes. We give an axiomatic theory of blockchain dynamics that permits rigorous reasoning about the longest-chain rule and achieve, in broad generality, Θ(k) dependence on depth in order to achieve consistency error 2−k In particular, for the first time we show that PoS protocols can match proof-of-work protocols for linear consistency. We analyze the associated stochastic process, give a recursive relation for the critical functionals of this process, and derive tail bounds in both i.i.d. and martingale settings via associated generating functions.

Network motifs are statistically overrepresented sub-structures (sub-graphs) in a network, and have been recognized as 'the simple building blocks of complex networks'. Study of biological network motifs may reveal answers to many important biological questions. The main difficulty in detecting larger network motifs in biological networks lies in the facts that the number of possible sub-graphs increases exponentially with the network or motif size (node counts, in general), and that no known polynomial-time algorithm exists in deciding if two graphs are topologically equivalent. This article discusses the biological significance of network motifs, the motivation behind solving the motif-finding problem, and strategies to solve the various aspects of this problem. A simple classification scheme is designed to analyze the strengths and weaknesses of several existing algorithms. Experimental results derived from a few comparative studies in the literature are discussed, with conclusions that lead to future research directions.