Blockchain Papers

Craig Calcaterra, Wulf A. Kaal

No abstract is available for this record.

Alexander Braun, Niklas Häusle, Stephan Karpischek

No abstract is available for this record.

Hanna Hałaburda, Zhiguo He, Jiasun Li

No abstract is available for this record.

Avigail Gurin-Schleifer, Ouri Poupko, Ehud Shapiro, Nimrod Talmon

We envision a self-sovereign, grassroots, digital community that grows in a bottom up, decentralized manner, and aim to integrate for it the following previously-proposed building blocks: a mechanism that accepts members into the community while keeping a bounded number of sybils; digital social contracts that define the possible interactions of a community bounded by such a contract; a design for a fault-tolerant distributed ledger implementation of digital social contracts; and a digital social contract for the egalitarian and just minting of digital currency, which also offers a form of universal basic income. We augment these building blocks with a mechanism that allows the community to maintain sovereignty over the economy, by making it sybil-resilient. To do so, we assume that the community has the means for exposing sybils and we extend the basic egalitarian currency digital social contract with means to balance the economy so that money minted by sybils is eventually retrieved and burned. This leads---asymptotically---to distributive justice among the genuine agents, with the amount of money minted being equal to the number of genuine agents, multiplied by the time each agent was a member of the community. We then argue that this approach constitutes a mechanism that deters the creation of sybils and incentivizes sybil hunting.

Yotam Sali, Aviv Zohar

Off-chain transaction channels represent one of the leading techniques to scale the transaction throughput in cryptocurrencies such as Bitcoin. They allow multiple agents to route payments through one another. So far, the topology and construction of payment networks has not been explored much. Participants are expected to minimize costs that are due to the allocation of liquidity as well as blockchain record fees. In this paper we study the optimization of maintenance costs of such networks. We present for the first time, a closed model for symmetric off-chain channels, and provide efficient algorithms for constructing minimal cost spanning-tree networks under this model. We prove that for any network demands, a simple hub topology provides a 2-approximation to the minimal maintenance cost showing that spanning trees in general are efficient. We also show an unbounded price of anarchy in a greedy game between the transactors, when each player wishes to minimize his costs by changing the network's structure. Finally, we simulate and compare the costs of payment networks with scale free demand topologies.

Olívia Terence Saa

\n In the first part of this work, we present, model and analyze a randomized automated peering model, that can be implemented to any distributed system. We conclude that the scheme has some desirable properties (specifically, a reasonable message overhead, a reasonable distribution of the numbers of peers of a node, and a negligible probability of an attack by a malicious actor to be successful). In the second part, we present an article published in the volume 136 of the journal Computers & Industrial Engineering, in October of 2019 (DOI 10.1016=j.cie.2019.07.025). In the paper, we analyze the Nash Equilibria of a graph attachment game, defined to represent the different strategies that malicious actors can use to take certain advantages in a DAG-based (i.e., based on Directed Acyclic Graphs) distributed ledger system. We prove the existence of almost symmetric Nash equilibria for the system where a part of players tries to optimize their attachment strategies and another part follows a default one. We also present simulations that show that the selfish players will not choose strategies that are considerably different that the recommended one.\n

Floriana Gargiulo, Ilaria Bertazzi, Sylvie Huet

Bitcoin-otc is a peer to peer (over-the-counter) marketplace for trading with bitcoin 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 distinguishing 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 that the systems' reputation inequality reaches a high steady value with the network evolution. We characterize the reputation trajectories identifying prototypical behaviors associated to three classes of users: trustworthy, untrusted and controversial. Controversial users are the only ones presenting up and down reputation trends. We focus on these cases for understanding which are the possible factors driving reputation falls and which dynamical patterns characterize these cascades: some users have real oscillating behaviors, other abuse of the trust system doing a few good transactions to gain reputation for cheating the users afterwards, other naturally and slowly die out after a long series of positive exchanges (like disappearing from the system) and finally, some users are hardly beaten by organized trolling attacks.

Moran Cerf, Sandra Matz, Aviram Berg

Human decision making is often prone to biases and irrationality. Group decisions add dynamic interactions that further complicate the choice process and frequently result in outcomes that are suboptimal for both the individual and the collective. We show that an implementation of a Blockchain protocol improves individuals’ decision strategies and increases the alignment between desires and outcomes. The Blockchain protocol affords (1) a distributed decision, (2) the ability to iterate repeatedly over a choice, (3) the use of feedback and corrective inputs, and (4) the quantification of intrinsic choice attributes (i.e., greed, desire for fairness, etc.). We test our protocol’s performance in the context of the Public Goods Game. The game, a generalized version of the Prisoner’s Dilemma, allows players to maximize their own gain or act in ways that benefit the collective. Empirical evidence shows that participants’ cooperation in the game typically decreases once a single player favors their own interest at the expense of others’. In our Blockchain implementation, “smart contracts” are used to safeguard individuals against losses and, consequently, encourage contributions to the public good. Across different tested simulations, the Blockchain protocol increases both the overall trust among the participants and their profits. Agents decision strategies remain flexible while they act as each other’s source of accountability (which can be seen as formalized distributed “Ulysses contract”). To highlight the contribution of our protocol to society at large we incorporated an entity that represents the public good. This benevolent independent beneficiary of the contributions of all participants (e.g. a charity organization or a tax system) maximized its payoffs when the Blockchain protocol was implemented. We provide a formalized implementation of the Blockchain protocol and discuss potential applications that could benefit society by more accurately capturing individuals’ preferences. For example, the protocol could help maximize profits in groups, facilitate democratic election that better reflect the public opinion, or enable group decision in circumstances where a balance between anonymity, diverse opinions, personal preferences and loss-aversion play a role.

Nida Khan, Tabrez Ahmad, Anass Patel, Radu State

Blockchain governance is a subject of ongoing research and an interdisciplinary view of blockchain governance is vital to aid in further research for establishing a formal governance framework for this nascent technology. In this paper, the position of blockchain governance within the hierarchy of Institutional governance is discussed. Blockchain governance is analyzed from the perspective of IT governance using Nash equilibrium to predict the outcome of different governance decisions. A payoff matrix for blockchain governance is created and simulation of different strategy profiles is accomplished for computation of all Nash equilibria. The paper elaborates upon payoff matrices for different kinds of blockchain governance, which are used in the proposition of novel mathematical formulae usable to predict the best governance strategy that minimizes the occurrence of a hard fork as well as predicts the behavior of the majority during protocol updates. The paper also includes validation of the proposed formulae using real Ethereum data.

Chris Berg, Sinclair Davidson, Jason Potts

Blockchain technology is the distributed, decentralised ledger technology underlying Bitcoin and other cryptocurrencies. We apply Oliver Williamson’s transactions cost analysis to the blockchain consensus mechanism. Blockchains reduce the costs of opportunism but are not ‘trustless’. We show that blockchains are trust machines. Blockchains are platforms for three-sided bargaining that convert energy-intensive computation into economically-valuable trust.

Eitan Altman, Daniel Sadoc Menasché, Alexandre Reiffers-Masson, Mandar Datar · 7 authors

We model the competition over mining resources and over several cryptocurrencies as a non-cooperative game. Leveraging results about congestion games, we establish conditions for the existence of pure Nash equilibria and provide efficient algorithms for finding such equilibria. We account for multiple system models, varying according to the way that mining resources are allocated and shared and according to the granularity at which mining puzzle complexity is adjusted. When constraints on resources are included, the resulting game is a constrained resource allocation game for which we characterize a normalized Nash equilibrium. Under the proposed models, we provide structural properties of the corresponding types of equilibrium, e.g., establishing conditions under which at most two mining infrastructures will be active or under which no miners will have incentives to mine a given cryptocurrency.

Zongxi Li, A. Max Reppen, Ronnie Sircar

We propose a mean field game model to study the question of how centralization of reward and computational power occur in Bitcoin-like cryptocurrencies. Miners compete against each other for mining rewards by increasing their computational power. This leads to a novel mean field game of jump intensity control, which we solve explicitly for miners maximizing exponential utility and handle numerically in the case of miners with power utilities. We show that the heterogeneity of their initial wealth distribution leads to greater imbalance of the reward distribution, and increased wealth heterogeneity over time, or a “rich get richer” effect. This concentration phenomenon is aggravated by a higher Bitcoin mining reward and reduced by competition. Additionally, an advantaged miner with cost advantages such as access to cheaper electricity, contributes a significant amount of computational power in equilibrium, unaffected by competition from less efficient miners. Hence, cost efficiency can also result in the type of centralization seen among miners of cryptocurrencies. This paper was accepted by Kay Giesecke, finance. Funding: A. M. Reppen is partly supported by the Swiss National Science Foundation [Grant SNF 181815]. Supplemental Material: The data files are available at https://doi.org/10.1287/mnsc.2023.4798 .

Colleen Alkalay-Houlihan, Nisarg Shah

Bitcoin, a cryptocurrency built on the blockchain data structure, has generated significant academic and commercial interest. Contrary to prior expectations, recent research has shown that participants of the protocol (the so-called “miners”) are not always incentivized to follow the protocol. We study the game induced by one such attack – the pool block withholding attack – in which mining pools (groups of miners) attack other mining pools. We focus on the case of two pools attacking each other, with potentially other mining power in the system.We show that this game always admits a pure Nash equilibrium, and its pure price of anarchy, which intuitively measures how much computational power can be wasted due to attacks in an equilibrium, is at most 3. We conjecture, and prove in special cases, that it is in fact at most 2. Our simulations provide compelling evidence for this conjecture, and show that players can quickly converge to the equilibrium by following best response strategies.

Vitalik Buterin, Zoë Hitzig, E. Glen Weyl

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. Citizens make contributions to public goods of value to them. The amount received by the public good is (proportional to) the square of the sum of the square roots of contributions received. Under the “standard model,” this mechanism yields first best public goods provision. Variations can limit the cost, help protect against collusion, and aid coordination. We discuss applications to campaign finance and highlight directions for future analysis and experimentation. This paper was accepted by Joshua Gans, business strategy.

Yevhen Zolotavkin, Julián García, Joseph K. Liu

Pool mining is a common way to reduce income variance for miners in Proof of Work Cryptocurrencies. A vast majority of mining does happen in pools, where a popular scheme to distribute rewards is Pay per last N Shares (PPLNS). In PPLNS and related schemes, miners are frequently making decisions whose rewards are not immediate and will only manifest in the future. This implies that models of inter-temporal utility are relevant when considering the incentives of miners. We show that when including these features of human behaviour in models of rational pool miners, the conditions that lead to decentralisation are hampered because larger pools may be more attractive to miners. We present a new game theoretical model of PPLNS where rational miners have time preferences. In this setup, the incentives of miners to work for a pool depend on the initial distribution of power between mining pools, as well as the specific details of how time is discounted. Agents jumping to larger pools face a trade-off between reducing the expected payoff from their shares in their current pool, or getting faster rewards in the future by joining a larger pool. We consider a case where pools of different mining power have the same size of reward window N. According to our study, in equilibrium larger pools have a tendency to accumulate a disproportionate share of the network power at the expense of smaller pools. This outcome is prevalent over a large range of realistic model parameters. Our model shows that PPLNS may be harmful to the decentralised governance of cryptocurrencies. A way to ameliorate these negative effects, is to encourage pools to have diverse window sizes, or use different reward mechanisms. Doing this in a decentralised fashion is an open challenge.

Marmolejo Cossio, Francisco Javier

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.

Carey Caginalp, Gunduz Caginalp

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.

Jean‐Philippe Martin, Eunjin, Jung

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.

János Flesch, Arkadi Predtetchinski, William D. Sudderth

No abstract is available for this record.

Carey Caginalp, Gunduz Caginalp

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.

Drew Stone

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.

Sarah Azouvi, Patrick McCorry, Sarah Meiklejohn

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.

Vitalik Buterin, Zoë Hitzig, E. Glen Weyl

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.