One of the most important features of blockchain protocols is decentralization, as their main contribution is that they formulate a distributed ledger that will be maintained and extended without the need of a trusted party. Bitcoin has been criticized for its tendency to centralization, as very few pools control the majority of the hashing power. Pass et al. proposed FruitChain [PODC 17] and claimed that this blockchain protocol mitigates the formation of pools by reducing the variance of the rewards in the same way as mining pools, but in a fully decentralized fashion. Many follow up papers consider that the problem of centralization in Proof-of- Work (PoW) blockchain systems can be solved via lower rewards' variance, and that in FruitChain the formation of pools is unnecessary. Contrary to the common perception, in this work, we prove that lower variance of the rewards does not eliminate the tendency of the PoW blockchain protocols to centralization; miners have also other incentives to create large pools, and specifically to share the cost of creating the instance they need to solve the PoW puzzle. We abstract the procedures of FruitChain as oracles and assign to each of them a cost. Then, we provide a formal definition of a pool in a blockchain system, and by utilizing the notion of equilibrium with virtual payoffs (EVP) [AFT 21], we prove that there is a completely centralized EVP, where all the parties form a single pool controlled by one party called the pool leader. The pool leader is responsible for creating the instance used for the PoW procedure. To the best of our knowledge, this is the first work that examines the construction of mining pools in the FruitChain system.

Consider a set of participants invited to execute a protocol Π. The protocol will incur some cost to run while in the end (or at regular intervals), it will populate and update local bookkeeping tables that assign virtual rewards to participants. Each participant aspires to offset the costs of participation by these virtual payoffs that are provided in the course of the protocol and are assumed to be accepted as forms of payment. In this setting, we introduce and study a notion of coalition-safe equilibria. In particular, we consider a strategic coalition of participants that is centrally coordinated and potentially deviates from Π with the objective to increase its utility with respect to the view of at least one of the other participants. The protocol Π is called a coalition-safe equilibrium with virtual payoffs (EVP) if no such protocol deviation exists. We apply our notion to study incentives in blockchain protocols.

We introduce and study reward sharing schemes (RSS) that promote the fair formation of stake pools in collaborative projects that involve a large number of stakeholders such as the maintenance of a proof-of-stake (PoS) blockchain. Our mechanisms are parameterized by a target value for the desired number of pools. We show that by properly incentivizing participants, the desired number of stake pools is a Nash equilibrium arising from rational play. Our equilibria also exhibit an efficiency / security tradeoff via a parameter that calibrates between including pools with the smallest cost and providing protection against Sybil attacks, the setting where a single stakeholder creates a large number of pools in the hopes to dominate the collaborative project. We then describe how RSS can be deployed in the PoS setting, mitigating a number of potential deployment attacks and protocol deviations that include censoring transactions, performing Sybil attacks with the objective to control the majority of stake, lying about the actual cost and others. Finally, we experimentally demonstrate fast convergence to equilibria in dynamic environments where players react to each other's strategic moves over an indefinite period of interactive play. We also show how simple reward sharing schemes that are seemingly more “fair”, perhaps counterin-tuitively, converge to centralized equilibria.