The focus of this thesis is twofold: on one hand we study the query complexity of equilibrium computation in games, and on the other hand, we use equilibrium concepts from game theory as a tool to understand miner incentives in Bitcoin. In terms of query complexity, we mostly focus on algorithms that have access to utility queries in large games and best response queries in bimatrix games. For the former, we demonstrate query-efficient completely uncoupled dynamics that achieve non-trivial approximate equilibria. For the latter, we reduce the problem of query-efficient approximate equilibrium computation to a natural geometric learning problem: approximately learning partitions of an 𝑛-dimensional simplex into disjoint convex polytopes via membership queries. Given this reduction we show query-efficient algorithms for the geometric problem, and ultimately provide an algorithm for computing e-well-supported Nash equilibria in 𝑚×𝑛 bimatrix games with a query cost that is polynomial in log(1/e)and max(𝑚,𝑛) provided that min(𝑚,𝑛) is constant.This leads to a polynomial query complexity algorithm for 2-player games,provided that one of the players has a constant number of strategies. As for incentives in Bitcoin, we shed some light into how robust honest mining protocols are to the presence of strategic agents. Our focus is on the strategic aspects of both solo mining and pool mining in Bitcoin. For the former, we take a multiplayer approach and exhibit specific strategy profiles of multiple strategic miners that outperform honest mining, even if said miners would not be incentivised to be dishonest individually. This effectively renders the Bitcoin protocol less secure than previously thought. As for the latter, we propose a new mining pool protocol that is a randomised variant of the already-ubiquitous pay-per-last-N-shares (PPLNS) mining pool scheme in Bitcoin. Our pool protocol, randomised pay-per-last-N-shares (RPPLNS),enjoys the same desirable properties of PPLNS, but with the added benefit of an exponentially reduced state space required to maintain the protocol. More importantly, this reduced state space also allows us to prove robust guarantees against a richer class of strategic pool mining than before.
We utilize optimization methods to determine equilibria of cryptocurrencies. A core group, the wealthy, fears the loss of assets that can be seized by a government. Volatility may be influenced by speculators. The wealthy must divide their assets between the home currency and the cryptocurrency, while the government decides the probability of seizing a fraction the assets of this group. We establish conditions for existence and uniqueness of Nash equilibria. Also examined is the separate timescale problem in which the government policy cannot be reversed, while the wealthy can adjust their allocation in reaction to the government's designation of probability.
Célestin Coquidé, José Lages, Dima L. Shepelyansky
We construct the Google matrices of bitcoin transactions for all year quarters during the period of January 11, 2009 till April 10, 2013. During the last quarters the network size contains about 6 million users (nodes) with about 150 million transactions. From PageRank and CheiRank probabilities, analogous to trade import and export, we determine the dimensionless trade balance of each user and model the contagion propagation on the network assuming that a user goes bankrupt if its balance exceeds a certain dimensionless threshold $\kappa$. We find that the phase transition takes place for $\kappa 0.55$ almost all users remain safe. We find that even on a distance from the critical threshold $\kappa_c$ the top PageRank and CheiRank users, as a house of cards, rapidly drop to the bankruptcy. We attribute this effect to strong interconnections between these top users which we determine with the reduced Google matrix algorithm. This algorithm allows to establish efficiently the direct and indirect interactions between top PageRank users. We argue that this study models the contagion on real financial networks.
Blockchain systems benefit from lessons in prior art such as fault tolerance, distributed systems, peer-to-peer systems, and game theory. In this paper we argue that blockchain algorithms should tolerate both rational (self-interested) users and Byzantine (malicious) ones, rather than assuming all non-Byzantine users are altruistic and follow the protocols blindly. Such algorithms are called BAR-tolerant [1]. To design a BAR-tolerant system, one can follow these three steps: clearly define the utility function for the rational users, prove the algorithm is such that there is no benefit from unilaterally deviating (that is, it's a Byzantine Nash Equilibrium), then prove the algorithm correct assuming the rational actors follow the protocol. We present an example attack by rational users: the gatekeeping attack, where members of a system selfishly decide to prevent newcomers from joining. This attack may affect any stake-based system where the existing members prevent newcomers from making a stake, and essentially form a cartel. We then sketch a BAR-tolerant consensus protocol for blockchain that can defend against this attack. It relies on a strict order to decide who gets to propose a new block (so there's no need to race to solve a crypto puzzle) and it relies on hardware ID tokens to make sure every computer is only represented at most once as a block proposer to mitigate Sybil attacks. It also defends against the gatekeeper attack. The BAR-tolerant approach is naturally also applicable to other blockchain algorithms.
The purpose of this paper is to show how the mechanism of the reward structure for cryptocurrency mining (known as “Proof of Work†) is applicable to alleviation of the free rider problem for voluntary public goods provision. This paper presents the following results. First, if each individual reports preferences honestly, then the Samuelson condition can hold. It is possible to set an appropriate level of mining. Second, if the scheme (mechanism) offered by our manuscript is introduced, public goods can theoretically be provided at a Pareto optimal level under certain conditions because each rational individual reports true preferences to the government.
Optimization methods are used to determine equilibria of investment in cryptocurrencies. The basic assumptions involve existence of a core group (the "wealthy") that fears the loss of substantial assets through government seizure. Speculators constitute another group that tends to introduce volatility and risk for the wealthy. The wealthy must divide their assets between the home currency and the cryptocurrency, while the government decides on the probability of seizing a fraction the assets of this group. Under the assumption that each group exhibits risk aversion through a utility function, we establish the existence and uniqueness of Nash equilibrium. Also examined is the more realistic optimization problem in which the government policy cannot be reversed, while the wealthy can adjust their allocation in reaction to the government's designation of probability. The methodology leads to an understanding the equilibrium market capitalization of cryptocurrencies.
Michele Bottone, Franco Raimondi, Giuseppe Primiero
In the past ten years distributed ledgers such as Bitcoin and smart contracts that can run code autonomously have seen an exponential growth both in terms of research interest and in terms of industrial and financial applications. These find a natural application in the area of Sensor Networks and Cyber-Physical Systems. However, the incentive architecture of blockchains requires massive computational resources for mining, delays in the confirmation of transactions and, more importantly, continuously growing transaction fees, which are ill-suited to systems in which services may be provided by resource-limited devices and confirmation times and transaction costs should be kept minimal, ideally absent. We focus on a new block-less, fee-less paradigm for distributed ledgers suitable for the WSN, IoT and CPS in which transactions are nodes of a directed acyclic graph, that overcomes the limitations of blockchains for these applications, and where e.g. sensors can be at the same time issuers of transactions and validators of previous transactions. In particular, we present and release open-source a simulation environment that can be easily extended and analysed, and confirms the available results on the performance of the network.
Given the parallels between game theory and consensus, it makes sense to intelligently design blockchain or DAG protocols with an incentive-compatible-first mentality. To that end, we propose a new blockchain or DAG protocol enhancement based on delayed rewards. We devise a new method for imposing slashing conditions on miner behavior, using their delayed rewards as stake in a Proof of Work system. Using fraud proofs, we can slash malicious miner behavior and reward long-lived, honest behavior.
Consensus protocols inherently rely on the notion of leader election, in which one or a subset of participants are temporarily elected to authorize and announce the network's latest state. While leader election is a well studied problem, the rise of distributed ledgers (i.e., blockchains) has led to a new perspective on how to perform large-scale leader elections via solving a computationally difficult puzzle (i.e., proof of work). In this paper, we present Caucus, a large-scale leader election protocol with minimal coordination costs that does not require the computational cost of proof-of-work. We evaluate Caucus in terms of its security, using a new model for blockchain-focused leader election, before testing an implementation of Caucus on an Ethereum private network. Our experiments highlight that one variant of Caucus costs only $0.10 per leader election if deployed on Ethereum.
We propose a design for philanthropic or publicly-funded seeding to allow (near) optimal provision of a decentralized, self-organizing ecosystem of public goods. The concept extends ideas from Quadratic Voting to a funding mechanism for endogenous community formation. Individuals make public goods contributions to projects of value to them. The amount received by the project is (proportional to) the square of the sum of the square roots of contributions received. Under the standard model this yields first best public goods provision. Variations can limit the cost, help protect against collusion and aid coordination. We discuss applications to campaign finance, open source software ecosystems, news media finance and urban public projects. More broadly, we offer a resolution to the classic liberal-communitarian debate in political philosophy by providing neutral and non-authoritarian rules that nonetheless support collective organization.
Ilaria Bertazzi, Sylvie Huet, Guillaume Deffuant, Floriana Gargiulo
Bitcoin-otc is a peer to peer (over-the-counter) marketplace for trading with bit- coin crypto-currency. To mitigate the risks of the p2p unsupervised exchanges, the establishment of a reliable reputation systems is needed: for this reason, a web of trust is implemented on the website. The availability of all the historic of the users interaction data makes this dataset a unique playground for studying reputation dynamics through others evaluations. We analyze the structure and the dynamics of this web of trust with a multilayer network approach distin- guishing the rewarding and the punitive behaviors. We show that the rewarding and the punitive behavior have similar emergent topological properties (apart from the clustering coefficient being higher for the rewarding layer) and that the resultant reputation originates from the complex interaction of the more regular behaviors on the layers. We show which are the behaviors that correlate (i.e. the rewarding activity) or not (i.e. the punitive activity) with reputation. We show that the network activity presents bursty behaviors on both the layers and that the inequality reaches a steady value (higher for the rewarding layer) with the network evolution. Finally, we characterize the reputation trajectories and we identify prototypical behaviors associated to three classes of users: trustworthy, untrusted and controversial.
We analyse the Tangle --- a DAG-valued stochastic process where new vertices get attached to the graph at Poissonian times, and the attachment's locations are chosen by means of random walks on that graph. These new vertices, also thought of as "transactions", are issued by many players (which are the nodes of the network), independently. The main application of this model is that it is used as a base for the IOTA cryptocurrency system (www.iota.org). We prove existence of "almost symmetric" Nash equilibria for the system where a part of players tries to optimize their attachment strategies. Then, we also present simulations that show that the "selfish" players will nevertheless cooperate with the network by choosing attachment strategies that are similar to the "recommended" one.
This paper presents a simple game theoretic framework, assuming complete information, to model Bitcoin mining activity. It does so by formalizing the activity as an all-pay contest: a competition where participants contend with each other to win a prize by investing in computational power, and victory is probabilistic. With at least two active miners, the unique pure strategy Nash equilibrium of the game suggests the following interesting insights on the motivation for being a miner: while the optimal amount of energy consumption depends also on the reward for solving the puzzle, as long as the reward is positive the decision to be an active miner depends only on the mining costs. Moreover, the intrinsic structure of the mining activity seems to prevent the formation of a monopoly, because in an equilibrium with two miners, both of them will have positive expected profits for any level of the opponent’s costs. A monopoly could only form if the rate of return on investment were higher outside bitcoin.
Miles Carlsten, Harry Kalodner, S. Matthew Weinberg, Arvind Narayanan
Bitcoin provides two incentives for miners: block rewards and transaction fees. The former accounts for the vast majority of miner revenues at the beginning of the system, but it is expected to transition to the latter as the block rewards dwindle. There has been an implicit belief that whether miners are paid by block rewards or transaction fees does not affect the security of the block chain.
Aggelos Kiayias, Ηλίας Κουτσουπιάς, Maria Kyropoulou, Yiannis Tselekounis
We study the strategic considerations of miners participating in the bitcoin's protocol. We formulate and study the stochastic game that underlies these strategic considerations. The miners collectively build a tree of blocks, and they are paid when they create a node (mine a block) which will end up in the path of the tree that is adopted by all. Since the miners can hide newly mined nodes, they play a game with incomplete information. Here we consider two simplified forms of this game in which the miners have complete information. In the simplest game the miners release every mined block immediately, but are strategic on which blocks to mine. In the second more complicated game, when a block is mined it is announced immediately, but it may not be released so that other miners cannot continue mining from it. A miner not only decides which blocks to mine, but also when to release blocks to other miners. In both games, we show that when the computational power of each miner is relatively small, their best response matches the expected behavior of the bitcoin designer. However, when the computational power of a miner is large, he deviates from the expected behavior, and other Nash equilibria arise.