Biblio

Software-defined networks (SDN), through their programmability, significantly increase network resilience by enabling dynamic reconfiguration of network topologies in response to faults and potentially malicious attacks detected in real-time. Another key trend in network softwarization is cloud-native software, which, together with SDN, will be an integral part of the core of future 5G networks. In SDN, the control plane forms the "brain" of the software-defined network and is typically implemented as a set of distributed controller replicas to avoid a single point of failure. Distributed consensus algorithms are used to ensure agreement among the replicas on key data even in the presence of faults. Security is also a critical concern in ensuring that attackers cannot compromise the SDN control plane; byzantine fault tolerance algorithms can provide protection against compromised controller replicas. However, while reliability/availability and security form key attributes of resilience, they are typically modeled separately in SDN, without consideration of the potential impacts of their interaction. In this paper we present an initial framework for a model that unifies reliability, availability, and security considerations in distributed consensus. We examine – via simulation of our model – some impacts of the interaction between accidental faults and malicious attacks on SDN and suggest potential mitigations unique to cloud-native software.

A blockchain is a distributed ledger forming a distributed consensus on a history of transactions, and is the underlying technology for the Bitcoin cryptocurrency. However, its applications are far beyond the financial sector. The transaction verification process for cryptocurrencies is much slower than traditional digital transaction systems. One approach to increase transaction speed and scalability is to identify a solution that offers faster Proof of Work. In this paper, we propose a method for accelerating the process of Proof of Work based on parallel mining rather than solo mining. The goal is to ensure that no more than two or more miners put the same effort into solving a specific block. The proposed method includes a process for selection of a manager, distribution of work and a reward system. This method has been implemented in a test environment that contains all the characteristics needed to perform Proof of Work for Bitcoin and has been tested, using a variety of case scenarios, by varying the difficulty level and number of validators. Preliminary results show improvement in the scalability of Proof of Work up to 34% compared to the current system.

The celebrated Nakamoto consensus protocol [16] ushered in several new consensus applications including cryptocurrencies. A few recent works [7, 17] have analyzed important properties of blockchains, including most significantly, consistency, which is a guarantee that all honest parties output the same sequence of blocks throughout the execution of the protocol. To establish consistency, the prior analysis of Pass, Seeman and Shelat [17] required a careful counting of certain combinatorial events that was difficult to apply to variations of Nakamoto. The work of Garay, Kiayas, and Leonardas [7] provides another method of analyzing the blockchain under the simplifying assumption that the network was synchronous. The contribution of this paper is the development of a simple Markov-chain based method for analyzing consistency properties of blockchain protocols. The method includes a formal way of stating strong concentration bounds as well as easy ways to concretely compute the bounds. We use our new method to answer a number of basic questions about consistency of blockchains: Our new analysis provides a tighter guarantee on the consistency property of Nakamoto's protocol, including for parameter regimes which [17] could not consider; We analyze a family of delaying attacks first presented in [17], and extend them to other protocols; We analyze how long a participant should wait before considering a high-value transaction "confirmed"; We analyze the consistency of CliqueChain, a variation of the Chainweb [14] system; We provide the first rigorous consistency analysis of GHOST [20] and also analyze a folklore "balancing"-attack. In each case, we use our framework to experimentally analyze the consensus bounds for various network delay parameters and adversarial computing percentages. We hope our techniques enable authors of future blockchain proposals to provide a more rigorous analysis of their schemes.

Nakamoto's famous blockchain protocol enables achieving consensus in a so-called permissionless setting—anyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents "sybil attacks" (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. "moderately hard functions") introduced by Dwork and Naor (Crypto'92). Recent work by Garay et al (EuroCrypt'15) and Pass et al (manuscript, 2016) demonstrate that this protocol provably achieves consistency and liveness assuming a) honest players control a majority of the computational power in the network, b) the puzzle-hardness is appropriately set as a function of the maximum network delay and the total computational power of the network, and c) the computational puzzle is modeled as a random oracle. Assuming honest participation, however, is a strong assumption, especially in a setting where honest players are expected to perform a lot of work (to solve the computational puzzles). In Nakamoto's Bitcoin application of the blockchain protocol, players are incentivized to solve these puzzles by receiving rewards for every "block" (of transactions) they contribute to the blockchain. An elegant work by Eyal and Sirer (FinancialCrypt'14), strengthening and formalizing an earlier attack discussed on the Bitcoin forum, demonstrates that a coalition controlling even a minority fraction of the computational power in the network can gain (close to) 2 times its "fair share" of the rewards (and transaction fees) by deviating from the protocol instructions. In contrast, in a fair protocol, one would expect that players controlling a φ fraction of the computational resources to reap a φ fraction of the rewards. We present a new blockchain protocol—the FruitChain protocol—which satisfies the same consistency and liveness properties as Nakamoto's protocol (assuming an honest majority of the computing power), and additionally is δ-approximately fair: with overwhelming probability, any honest set of players controlling a φ fraction of computational power is guaranteed to get at least a fraction (1-δ)φ of the blocks (and thus rewards) in any Ω(κ/δ) length segment of the chain (where κ is the security parameter). Consequently, if this blockchain protocol is used as the ledger underlying a cryptocurrency system, where rewards and transaction fees are evenly distributed among the miners of blocks in a length κ segment of the chain, no coalition controlling less than a majority of the computing power can gain more than a factor (1+3δ) by deviating from the protocol (i.e., honest participation is an n/2-coalition-safe 3δ-Nash equilibrium). Finally, the FruitChain protocol enables decreasing the variance of mining rewards and as such significantly lessens (or even obliterates) the need for mining pools.