Welcome to the resource topic for 2016/916
Title:
FruitChains: A Fair Blockchain
Authors: Rafael Pass, Elaine Shi
Abstract: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 blocks'' (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 transation fees) by deviating from the protocol instructions. In contrast, in a fair protocol, one would expect that players controlling a \phi fraction of the computational resources to reap a \phi fraction of the rewards. In this work, 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 \delta-approximately fair: with overwhelming probability, any honest set of players controlling a \phi fraction of computational power is guaranteed to get at least a fraction (1 - \delta) \phi of the blocks (and thus rewards) in any Omega( \kappa/\delta ) length segment of the chain (where \kappa is the security parameter). As a consequence, 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 kappa segment of the chain, no coalition controlling less than a majority of the computing power can gain more than a factor (1 + 3\delta) by deviating from the protocol (i.e., honest participation is an n/2-coalition-safe 3\delta-Nash equilibrium). Finally, the fruit chain protocol enables decreasing the variance of mining rewards and as such significantly lessens (or even obliterates) the need for mining pools.
ePrint: https://eprint.iacr.org/2016/916
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .