Research Vignette: Cryptography and Game Theory for Blockchains

by Vassilis Zikas (University of Edinburgh)

Blockchains and decentralized ledgers are creating a new reality for modern society. A major scientific impact of this new reality is that it creates an interdisciplinary arena where traditionally independent research areas, such as cryptography and game theory/economics, need to work together to address the relevant questions. The Simons Institute's Fall 2019 program on Proofs, Consensus, and Decentralizing Society fostered much-needed cross-disciplinary collaboration by bringing together researchers from these disciplines.

An interdisciplinary research arena

The study of the interplay of cryptography and game theory/economics within the blockchain consists of several subareas. Here we discuss three such areas, with a focus on Bitcoin, as one of the most widely studied and adopted to date blockchains and cryptocurrencies. We stress that the relevant literature is huge and that discussing it all here is beyond the scope of this research vignette.

1. Cryptographic security and economic robustness. The works of Garay et al. [12] and Pass et al. [17] initiated the rigorous cryptographic study of the Bitcoin blockchain protocol and proved that under common assumptions about the underlying hash function and assuming the majority of the hashing power in the system is invested in executing the Bitcoin protocol (rather than attacking it), the protocol achieves a number of basic properties, such as common prefix (corresponding to the traditional notion of safety), chain growth (corresponding to liveness), and chain quality (ensuring that honest parties get to contribute blocks at an acceptable frequency). Follow-up work by Badertscher et al. [4] defined the functionality offered by the Bitcoin ledger and proved the protocol’s security under the above honest-majority assumption in a composable framework. This enables using the ledger functionality directly — without worrying about implementation details — within higher-level protocols. These initial works have ignited a number of follow-ups aiming at relaxing the underlying assumptions and/or tuning the protocol abstraction to better capture reality.

   Parallel to the cryptographic security of blockchain protocols, their economic robustness — i.e., their resilience to incentive-driven attacks/misbehavior — has been extensively investigated. A classical example here is the work of Eyal and Sirer [9], which abstracted the protocol execution as a simple mining game and demonstrated that by withholding mined blocks and strategically releasing them, attackers with favorable network conditions might be incentivized to deviate from the Bitcoin protocol, even when they control only a minority of the hashing power. Note that such deviations cannot affect the worst-case security guarantees established in the cryptographic security proofs, but they can push them to their limits. For instance, although a selfish miner cannot break common prefix and chain quality, they can temporarily create the longest-allowed forks and/or minimize the number of blocks contributed by honest miners to the worst-case value allowed by chain quality.

2. Economics on blockchains. Independently of the questions about their economic robustness, blockchains and their associated cryptocurrencies have created a new scientific playground for economists and game theorists to develop and test new theories and confirm old ones. Indicatively, Huberman et al. [15] investigated how an ideal abstraction of Bitcoin yields a new market design paradigm where market forces do not control the functionality of the underlying payment system. They showed how analyzing this paradigm can explain behavioral aspects of Bitcoin and pointed to interesting modifications that can affect the efficiency of the protocol itself. Similarly, Benigno et al. [5] demonstrated how under common economics assumptions, equipping a two-country economy with a global cryptocurrency can create market forces driving the nominal interest rates to be equal in the two countries and yielding a rate relation between the two national currencies; and Prat and Walter [18] proposed a model using the Bitcoin-U.S. dollar exchange rate to forecast the computing power of the Bitcoin network.

3. Blockchain-induced incentives on cryptographic protocols. A third type of blockchain-related problem where cryptography and game theory meet is the design of more efficient and resilient cryptographic protocols using incentives induced by blockchains and cryptocurrencies. The classical example here is fair multiparty computation (in short, fair MPC). In MPC, n parties wish to run a protocol to jointly compute a function on their private data. Fairness in this context requires that if a worst-case adversary — controlling and coordinating the (malicious) parties attacking the protocol — learns (any information on) the output, then the honest parties should also learn it. Cleve’s well-known impossibility result [8] mandates that if the adversary controls a majority of parties, then fairness is impossible. Intuitively, the reason is that as the protocol has to tolerate any adversarial coalition, the actual corrupted parties might be the ones to first jointly learn such information; once they do, they can stop playing, thereby preventing other parties from also learning it. In [2, 6], it was shown that using the Bitcoin blockchain as an automated escrow mechanism, one can enforce a version of fairness based on collaterals where either nobody learns any information or if someone does and prevents others from also learning it, then he loses his collateral to them. Assuming the adversary values his collateral higher than breaking fairness, this mechanism induces a fair evaluation. These results were subsequently extended to ensure robustness [16], i.e., ensure that the protocol will not fail and either it will fairly conclude or the adversary will lose his collateral.

A joint collaborative framework

The above three layers of blockchain-inspired cross-disciplinary problems have mostly been studied independently by the two communities. The result is that they might include assumptions about the abstraction offered by the other discipline that might be too strong to realize. For example, the study of economics on blockchains typically abstracts the underlying blockchain as an ideal trusted ledger whose basic security properties do not depend on the economic mechanisms built on top of them. It is not hard to see that studying economics on top of such an idealized setting can become problematic when the relevant theories are applied in reality, with the actual blockchain protocol. Indeed, these theories and associated mechanisms can affect and/or give new insights on the incentives of parties maintaining the blockchain itself, which in turn can affect the economic robustness of the underlying blockchain and thereby the trustworthiness of the foundational ideal-blockchain assumption.

The above state of affairs calls for a unified treatment and associated framework that can address these interdependencies between the different layers.

A candidate for a first level of abstraction toward such a unification is the rational protocol design (RPD) framework of Garay et al. [10]. Rather than using the traditional approach of capturing a distributed protocol as a sequential game among the participants, RPD takes a cryptography-inspired approach to address the incentives of a malicious attacker to create party collusions and use them to attack the protocol, and the incentives of honest parties to stick to their protocol in the threat of such attacks. In fact, as demonstrated in [11, 13], the framework is suitable for capturing and analyzing fairness guarantees similar to those implied by the above collateral-based fairness mechanisms.

Most relevant to blockchains, our recent work [3] demonstrated how the RPD framework can be tuned to address the needs of the economic-robustness analysis of Bitcoin. We proved that when the Bitcoin-protocol version from [12, 17, 4] (i.e., the Bitcoin “backbone” with fixed hash-puzzle difficulty) is considered in isolation (where the miners’ utility depends only on their costs and rewards in the protocol), then assuming a sufficiently high Bitcoin-to-hashing-cost ratio, running the protocol strictly dominates attacking it even for a majority-controlling attacker. This indicates, among other things, that the deviations resulting from selfish-mining are in part the result of the difficulty readjustment mechanism. A number of different extensions of this result and applications of the RPD framework were discussed during the Simons Institute program. This includes investigating the forces that tame the attacker even in light of difficulty readjustment, capturing and formally analyzing more recent incentive-driven attacks, and addressing the effect of mining pools on Bitcoin’s security.

A major advantage of RPD when applied to analyze blockchains is its composability guarantees. On the one hand, stability (or strategy-proofness) statements in RPD can be done assuming access to ideally behaving (cryptographic) primitives, such as ideal commitments, signatures, etc. A universal composition theorem provided by the framework ensures then that these idealized statements are preserved even when those primitives are replaced by their cryptographic implementations. Such replacement is known not to be problematic in traditional game-theoretic cryptography models [14]. Revising further game-theoretic notions of stability that allow for such replacement is an active research direction that was discussed during the Simons Institute program.

On the other hand, a stability statement in the RPD model specifies the ideal system and proves that it is implemented under an attacker incentivized by the assumed utilities. For example, [3] shows that under the incentives created by a high-enough ratio of Bitcoin reward to hashing cost, the fixed-difficulty version of the Bitcoin protocol realizes the same transaction ledger as in [4] but without the honest majority of hashing power assumption. The advantage of such a statement is that the economic analysis of a blockchain-based system (whether a market design or a cryptographic protocol) can now use the ledger from [4] as an ideal abstraction of Bitcoin’s ledger, provided the mechanism built on top of it does not affect the underlying realization statement. Using this principle, in [7] we devised a mechanism for leveraging blockchains to remove the mediator from a mediated game and replace it with a weaker assumption of local cryptographically secure hardware, thereby circumventing a powerful impossibility result from [1].

The research described here demonstrates the potential of the RPD framework to serve as common ground for the unified study of blockchains by the cryptography and game theory communities. Without further ramifications, however, the simple two-party game structure of the framework might restrict its expressivity. The study of alternative frameworks and their connection with RPD is an important research direction. The Simons Institute program on Proofs, Consensus, and Decentralizing Society brought together researchers from both these areas and has been a greenhouse for exchanging ideas toward such a unified theory.

References
[1] Alwen, Joël, Jonathan Katz, Ueli Maurer, and Vassilis Zikas. 2012. “Collusion-Preserving Computation.” In Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, edited by Reihaneh Safavi-Naini and Ran Canetti, 7417:124–43. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-642-32009-5_9.