Wednesday, September 30th, 2020

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 robustnessThe 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.

[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.

[2] Andrychowicz, Marcin, Stefan Dziembowski, Daniel Malinowski, and Lukasz Mazurek. 2014. “Secure Multiparty Computations on Bitcoin.” In 2014 IEEE Symposium on Security and Privacy, SP 2014, Berkeley, CA, USA, May 18-21, 2014, 443–58. IEEE Computer Society.

[3] Badertscher, Christian, Juan A. Garay, Ueli Maurer, Daniel Tschudi, and Vassilis Zikas. 2018. “But Why Does It Work? A Rational Protocol Design Treatment of Bitcoin.” In Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part II, edited by Jesper Buus Nielsen and Vincent Rijmen, 10821:34–65. Lecture Notes in Computer Science. Springer.

[4] Badertscher, Christian, Ueli Maurer, Daniel Tschudi, and Vassilis Zikas. 2017. “Bitcoin as a Transaction Ledger: A Composable Treatment.” In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part I, edited by Jonathan Katz and Hovav Shacham, 10401:324–56. Lecture Notes in Computer Science. Springer.

[5] Benigno, Pierpaolo, Linda Schilling, and Harald Uhlig. 2019. “Cryptocurrencies, Currency Competition and the Impossible Trinity.”

[6] Bentov, Iddo, and Ranjit Kumaresan. 2014. “How to Use Bitcoin to Design Fair Protocols.” In Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part II, edited by Juan A. Garay and Rosario Gennaro, 8617:421–39. Lecture Notes in Computer Science. Springer.

[7] Ciampi, Michele, Yun Lu, and Vassilis Zikas. 2020. “Collusion-Preserving Computation Without a Mediator.” IACR Cryptol. ePrint Arch. 2020: 497.

[8] Cleve, Richard. 1986. “Limits on the Security of Coin Flips When Half the Processors Are Faulty (Extended Abstract).” In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, CA, USA, edited by Juris Hartmanis, 364–69. ACM.

[9] Eyal, Ittay, and Emin Gün Sirer. 2014. “Majority Is Not Enough: Bitcoin Mining Is Vulnerable.” In Financial Cryptography and Data Security - 18th International Conference, FC 2014, Christ Church, Barbados, March 3-7, 2014, Revised Selected Papers, edited by Nicolas Christin and Reihaneh Safavi-Naini, 8437:436–54. Lecture Notes in Computer Science. Springer.

 [10] Garay, Juan A., Jonathan Katz, Ueli Maurer, Björn Tackmann, and Vassilis Zikas. 2013. “Rational Protocol Design: Cryptography Against Incentive-Driven Adversaries.” In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, October 26-29, 2013, Berkeley, CA, USA, 648–57. IEEE Computer Society.

[11] Garay, Juan A., Jonathan Katz, Björn Tackmann, and Vassilis Zikas. 2015. “How Fair Is Your Protocol?: A Utility-Based Approach to Protocol Optimality.” In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21-23, 2015, edited by Chryssis Georgiou and Paul G. Spirakis, 281–90. ACM.

[12] Garay, Juan A., Aggelos Kiayias, and Nikos Leonardos. 2015. “The Bitcoin Backbone Protocol: Analysis and Applications.” In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part II, edited by Elisabeth Oswald and Marc Fischlin, 9057:281–310. Lecture Notes in Computer Science. Springer.

[13] Garay, Juan A., Björn Tackmann, and Vassilis Zikas. 2015. “Fair Distributed Computation of Reactive Functions.” In Distributed Computing - 29th International Symposium, DISC 2015, Tokyo, Japan, October 7-9, 2015, Proceedings, edited by Yoram Moses, 9363:497–512. Lecture Notes in Computer Science. Springer.

[14] Gradwohl, Ronen, Noam Livne, and Alon Rosen. 2010. “Sequential Rationality in Cryptographic Protocols.” In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, 623–32. IEEE Computer Society.

[15] Huberman, Gur, Jacob Leshno, and Ciamac C. Moallemi. 2019. “An Economic Analysis of the Bitcoin Payment System.” Columbia Business School Research Paper No. 17-92.

[16] Kiayias, Aggelos, Hong-Sheng Zhou, and Vassilis Zikas. 2016. “Fair and Robust Multi-Party Computation Using a Global Transaction Ledger.” In Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II, edited by Marc Fischlin and Jean-Sébastien Coron, 9666:705–34. Lecture Notes in Computer Science. Springer.

[17] Pass, Rafael, Lior Seeman, and Abhi Shelat. 2017. “Analysis of the Blockchain Protocol in Asynchronous Networks.” In Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part II, edited by Jean-Sébastien Coron and Jesper Buus Nielsen, 10211:643–73. Lecture Notes in Computer Science.

[18] Prat, Julien, and Benjamin Walter. 2018. “An Equilibrium Model of the Market for Bitcoin Mining.” CESifo Working Paper Series No. 6865.