WIXLIB

Distributed Computing Meets Game TheoryFault Tolerance and Implementation with Cheap Talk#Cornell University, Ithaca, NY, USAJoseph Y. HalpernAbstractTraditionally, work in distributed computing has divided the agents into “good guys” and “bad guys”.The good guys follow the protocol; the bad guys do everything in their power to make sure it doesnot work. By way of contrast, game theory has focused on “rational” agents, who try to maximizetheir utilities. Here I try to combine these viewpoints. Specifically, following the work of Abrahamet al. [2], I consider (k, t)-robust protocols/strategies, which tolerate coalitions of rational players ofsize up to k and up to t malicious players. I focus in particular on the problem that economistshave called implementing a mediator. That is, can the players in the system, just talking amongthemselves (using what economists call “cheap talk”) simulate the effects of the mediator (see, e.g.,[3, 4, 5, 6, 8, 10, 11]). In computer science, this essentially amounts to multiparty computation[7, 9, 12]. Ideas from cryptography and distributed computing allow us to prove results on howmany agents are required to implement a (k, t)-robust mediator just using cheap talk. These resultssubsume (and, in some cases, correct) results from the game theory literature.The results of Abraham et al. [2] were proved for what are called synchronous systems in thedistributed computing community; this is also the case for all the results in the economics literaturecited above. In synchronous systems, communication proceeds in atomic rounds, and all messagessent during round r are received by round r 1. But many systems in the real world are asynchronous.In an asynchronous setting, there are no rounds; messages sent by the players may take arbitrarilylong to get to their recipients. Markets and the internet are best viewed as asynchronous. Blockchainimplementations assume partial synchrony, where there is an upper bound on how long messagestake to arrive. The partial synchronous setting already shows some of the difficulty of moving awayfrom synchrony: An agent i can wait to take its action until it receives a message from j (on whichits action can depend). This cannot happen in a synchronous setting. Abraham, Dolev, Geffner,abnd Halpern [1] extend the results on implementing mediators to the asynchronous setting.2012 ACM Subject Classification Theory of computation Algorithmic game theory and mechanismdesignKeywords and phrases robust equilibrium, implementing mediators, asynchronous systemsDigital Object Identifier 10.4230/OASIcs.Tokenomics.2021.1Category Invited TalkRelated Versions The talk described by this paper is based on two papers: “Distributed computingmeets game theory: robust mechanisms for rational secret sharing and multiparty computation”, byIttai Abraham, Danny Dolev, Rica Gonen, and Joseph Y. Halpern, which appeared in the Proceedingsof the 25th Annual ACM Symposium on Principles of Distributed Computing, pp. 53–62, 2006, and“Implementing mediators with asynchronous cheap talk”, by Ittai Abraham, Danny Dolev, IvanGeffner, Joseph Y. Halpern, which appeared in Proceedings of the 38th Annual ACM Symposium onPrinciples of Distributed Computing, pp. 501–510, 2019.Full Version: https://arxiv.org/abs/1806.01214Funding Halpern’s work was supported in part by NSF grants IIS-1703846 and IIS-0911036, AROgrant W911NF-17-1-0592, MURI (MultiUniversity Research Initiative) under grant W911NF-19-10217, and a grant from Open Philanthropy. Joseph Y. Halpern;licensed under Creative Commons License CC-BY 4.03rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021).Editors: Vincent Gramoli, Hanna Halaburda, and Rafael Pass; Article No. 1; pp. 1:1–1:2OpenAccess Series in InformaticsSchloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

1:2Distributed Computing Meets Game TheoryReferences123456789101112I. Abraham, D. Dolev, I. Geffner, and J. Y. Halpern. Implementing mediators withasynchronous cheap talk. In Proc. 38th ACM Symposium on Principles of DistributedComputing, pages 501–510, 2019.I. Abraham, D. Dolev, R. Gonen, and J. Y. Halpern. Distributed computing meets game theory:robust mechanisms for rational secret sharing and multiparty computation. In Proc. 25thACM Symposium on Principles of Distributed Computing, pages 53–62, 2006.I. Barany. Fair distribution protocols or how the players replace fortune. Mathematics ofOperations Research, 17(2):327–340, 1992.E. Ben-Porath. Cheap talk in games with incomplete information. Journal of EconomicTheory, 108(1):45–71, 2003.F. Forges. Universal mechanisms. Econometrica, 58(6):1341–64, 1990.D. Gerardi. Unmediated communication in games with complete and incomplete information.Journal of Economic Theory, 114:104–131, 2004.O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In Proc. 19th ACMSymposium on Theory of Computing, pages 218–229, 1987.Y. Heller. A minority-proof cheap-talk protocol. Unpublished manuscript, 2005.A. Shamir, R. L. Rivest, and L. Adelman. Mental poker. In D. A. Klarner, editor, TheMathematical Gardner, pages 37–43. Prindle, Weber, and Schmidt, Boston, MA, 1981.A. Urbano and J. E. Vila. Computational complexity and communication: coordination intwo-player games. Econometrica, 70(5):1893–1927, 2002.A. Urbano and J. E. Vila. Computationally restricted unmediated talk under incompleteinformation. Economic Theory, 23(2):283–320, 2004.A. Yao. Protocols for secure computation (extended abstract). In Proc. 23rd IEEESymp. Foundations of Computer Science, pages 160–164, 1982.

General Congestion Attack on HTLC-BasedPayment Channel Networks#Cryptape, Hangzhou, ChinaZhichun Lu#Monash University, Melbourne, AustraliaCSIRO-Data61, Melbourne, AustraliaRunchao Han#Monash University, Melbourne, AustraliaJiangshan YuAbstractPayment Channel Networks (PCNs) have been a promising approach to scale blockchains. However,PCNs have limited liquidity: large-amount or multi-hop payments may fail. The major threat ofPCNs liquidity is payment griefing, where the adversary who acts as the payee keeps withholding thepayment, so that coins involved in the payment cannot be used for routing other payments beforethe payment expires. Payment griefing gives adversaries a chance to launch the congestion attack,where the adversary griefs a large number of payments and paralyses the entire PCN. Understandingcongestion attacks, including their strategies and impact, is crucial for designing PCNs with betterliquidity guarantees. However, existing research has only focused on the specific attacking strategiesand specific aspects of their impact on PCNs.We fill this gap by studying the general congestion attack. Compared to existing attack strategies,in our framework each step serves an orthogonal purpose and is customisable, allowing the adversaryto focus on different aspects of the liquidity. To evaluate the attack’s impact, we propose a genericmethod of quantifying PCNs’ liquidity and effectiveness of the congestion attacks. We evaluate ourgeneral congestion attacks on Bitcoin’s Lightning Network, and show that with direct channels to1.5% richest nodes, and 0.0096 BTC of cost, the adversary can launch a congestion attack thatlocks 47% ( 280 BTC) coins in the network; reduces success rate of payments by 16.0% 60.0%;increases fee of payments by 4.5% 16.0%; increases average attempts of payments by 42.0% 115.3%;and increase the number of bankruptcy nodes (i.e., nodes with insufficient balance for makingnormal-size payments) by 26.6% 109.4%, where the amounts of payments range from 0.001 to 0.019BTC.2012 ACM Subject Classification Security and privacy Distributed systems securityKeywords and phrases Blockchain, PCN, CongestionDigital Object Identifier 10.4230/OASIcs.Tokenomics.2021.2Related Version Full Version: c blockchains suffer from limited throughput. Payment Channel Network (PCN) –introduced by the Lightning Network (LN) [17] – is one of the promising ways to scaleblockchains. Payment channels enable off-chain payments, i.e. payments that do not need tobe recorded on the blockchain. To open a payment channel, two nodes collateralise some coinsin a joint address. They can make a payment by signing a new transaction that updates theirbalances. To close the channel, one of the two nodes commits the transaction recording thelatest balance allocation to the blockchain. If two nodes do not have a direct channel, theycan make payments to each other using multi-hop payments, i.e., payments going throughone or more intermediate channels. In a multi-hop payment, the payer has to find a path Zhichun Lu, Runchao Han, and Jiangshan Yu;licensed under Creative Commons License CC-BY 4.03rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021).Editors: Vincent Gramoli, Hanna Halaburda, and Rafael Pass; Article No. 2; pp. 2:1–2:15OpenAccess Series in InformaticsSchloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

2:2General Congestion Attack on HTLC-Based Payment Channel Networksthat directs him to the payee. The payment is made by updating balances of these channelsin an atomic way. The atomic update can be achieved by Hash Time Locked Contracts(HTLCs): the payment in each hop is locked by a hash value chosen by the payee, and allpayments proceed if the payee reveal a hash value’s preimage before a timeout to redeem thepayment from the payer, otherwise the payment will expire. In a HTLC-based multi-hoppayment, the payee chooses a preimage, and nodes make HTLC payments on all involvedchannels with this preimage’s hash value. Revealing this preimage activates these HTLCpayments simultaneously.A well-known attack on HTLC-based multi-hop payments is payment griefing [19], wherethe adversary makes a payment and withholds the preimage, so that coins involved in thispayment are locked and cannot be used in other payments before the griefing paymentexpires. Thus, payment griefing can reduce the PCN’s liquidity, i.e. the ability of routingpayments. In addition, payment griefing is free, as the payer does not need to pay anythingfor failed payments. Moreover, payment griefing is also unaccountable, as 1) the victimcannot distinguish between a normal failed payment and a griefing payment, and 2) theintermediate nodes can not know the payer and payee’s identity.Griefing opens an important attack vector on HTLC-based PCN’s liquidity, namely thecongestion attack [7, 14]. In a congestion attack, the adversary initiates a large numberof concurrent payments and griefs them. Consequently, some channels hit the limit ofmax concurrent htlcs, i.e., the number of concurrent unsettled payments allowed in thechannel, and therefore cannot route payments before the adversary’s payments expire. Bylaunching a large-scale congestion attack, the entire PCN can be paralysed, i.e., the PCNcannot route further payments.Understanding congestion attacks is important for understanding PCNs’ liquidity andtherefore future PCN design. However, congestion attacks are still a new concept and haven’tbeen well-studied yet. While existing research [7, 14] only considers max concurrent htlcsas an exhaustible resource, it’s unclear whether there exists other resources that can beexhausted to create congestion. In addition, existing congestion attacks apply a ratherstraightforward attack strategy, which will be analysed in detail in §7. Moreover, we alsoobserve that liquidity – the congestion attack’s target – is not well-defined yet. Besidesthe amount of locked balance and the number of locked channels mentioned in Mizrahi etal. [14], some other metrics such as success rate of payments, fee of payments, and number ofattempts for making a payment have direct indications on the PCN’s liquidity. Congestionattacks over these metrics are not explored before.In this paper, we fill this gap by introducing general congestion attack, which generalisesthe existing congestion attack in terms of attack strategies and targeted metrics. We introducea framework for launching congestion attacks, where the adversary generates Sybil nodesconnecting to a carefully chosen set of nodes, establishes channels with them, initiatesnumerous multi-hop payments between its nodes, and griefs these payments simultaneously.Compared to existing studies that put less effort on the order of payments to be griefed [14,22],we provide five strategies for ranking these payments, and each strategy focuses on somespecific aspects of liquidity. To quantify the effectiveness of congestion attacks, we introducea generic method of quantifying PCNs’ liquidity. We evaluate the congestion attack onBitcoin’s LN – the first and most well-known PCN. Our results show that congestion attackscan significantly damage the liquidity of PCNs. In particular, with direct channels to 1.5%richest nodes, the adversary can launch a congestion attack that locks 47% ( 280 BTC)coins in the network; reduces success rate of payments by 16.0% 60.0%; increases fee of

Z. Lu, R. Han, and J. Yu2:3payments by 4.5% 16.0%; increases average attempts of payments by 42.0% 115.3%; andincrease the number of bankruptcy nodes by 26.6% 109.4%, where the amounts of paymentsrange from 0.001 to 0.019 BTC.While being effective, our general congestion attacks are cheap to launch. The only costof general congestion attacks is the fee for establishing channels. Our evaluation shows that,a successful attack on LN requires channel fee of approximately 0.0096 BTC. The adversarydoes not lose its custody (i.e., coins in the channel) during the attack, as payments forgriefing will expire.Section 2 provides the background of PCNs and griefing. Section 3 describes the securitymodel and the congestion attack. Section 4 describes the method of quantifying PCNs’liquidity. Section 5 evaluates congestion attacks on LN. Section 6 discusses the cost ofcongestion and strategy to utilise it for making a profit. Section 7 reviews relevant literature,and provides a quantitative comparison between the general congestion attack and theexisting ones. Section 8 concludes this paper.2Background2.1Payment Channel NetworksLightning Network (LN) [17] introduces the idea of Payment Channel Networks. A paymentchannel allows two parties to pay each other without the need to publish every payment tothe blockchain. Instead, they collateralise their coins into a 2-of-2 multi-signature address.They can make payments by mutually signing new transactions with updated balances. Theycan make payments with each other by mutually signing new transactions with updatedamounts of their collateralised coins. To close the channel, one party commits the lateststate of channel balance to the blockchain, and coins in the channel will be allocated to bothparties accordingly.ABCC sends h to A1e 07A and B sign HAB9e 08B and C sign HBC9e 08C reveals s to B to advance HBCB reveals s to A to advance1e 07HABFigure 1 A multi-hop payment from A to C via an intermediate node B.The system can be further extended to support multi-hop payments. Most multi-hoppayment protocols are based on Hash Time Locked Contracts (HTLCs). HTLC is a contractbetween two parties which guarantees that a payment will be made if the payee shows thepreimage of a hash value before a negotiated block height on the blockchain. If the payeedoes not show the preimage and the timeout expires, the payment is deemed invalid.Figure 1 describes a multi-hop payment where A pays 9e-08 BTC to C via an intermediatenode B in Bitcoin’s LN. First, C chooses a random string s as preimage and sends its hashvalue h H(s) to A, where H(·) is a cryptographic hash function. A then signs a HTLC1e 07contract HABwith B stating “A will pay 1e-07 BTC to B if B can show the value of sTo k e n o m i c s 2 0 2 1

2:4General Congestion Attack on HTLC-Based Payment Channel Networks9e 08within (e.g.) 144 blocks”. B also signs a HTLC contract HBCwith C saying that “B willpay 9e-08 BTC to C if C can show the value of s within (e.g.) 138 blocks”. Then C shows9e 08s to B to redeem 9e-08 BTC in HBCfrom B. Meanwhile, B can redeem 1e-07 BTC in1e 07HAB from A by revealing s to A. B is incentivised to reveal s, as B does not want to losemoney. The timelock of AB is set to be longer than BC, so B always has sufficient time toreveal s to A.By routing this payment, B gets 1e-08 BTC from A. This is known as “fee”, which ispaid by the payer and is used for encouraging nodes to route multi-hop payments. In LN, feeconsists of a fixed base fee and proportional fee that fluctuates according to the congestionlevel of the network. To minimise the cost, payers usually search for a path with the leastfee when making payments.2.2Payment GriefingIf the payee C reveals the preimage on time and the intermediate node B is rational, themulti-hop payment will happen. However, as we mentioned before, there exists an attackcalled payment griefing [11], where the payee withholds the preimage until HTLCs expire.Before HTLC expires, coins involved in all channels of this payment are locked and cannotroute other payments.Payment griefing is a threat to PCNs’ liquidity. If a big portion of coins in a PCN arelocked, the PCN will no longer be able to route payments. Payment griefing is cheap, asthe payment does not really happen and the payer does not pay for the fee to intermediatenodes. Identifying payment griefing can be hard, as nodes cannot distinguish whether thewithholding is due to network delay, on purpose, or by accident. If the PCN’s routing protocolis privacy-preserving, payment griefing can even be launched anonymously. For example,Bitcoin’s LN adopts Sphinx [5], where each intermediate node only has the knowledge ofnodes who directly connect with him.2.3Congestion attack1121 Attacker12Attacker2322233AttackerAttackerFigure 2 Congestion attack.In a congestion attack, the adversary establishes payment channels with existing nodesin the PCN, and make numerous multi-hop payments between its nodes simultaneously.Then, the adversary withholds preimages until these payments expire. Before that, coins

Z. Lu, R. Han, and J. Yu2:5locked in these payments cannot be used in other payments. If the adversary has sufficientcustody, it can lock a great portion of coins in the PCN so that the PCN may be paralysed.Figure 2 shows the intuition of the congestion attack, where the adversary generates Sybilnodes connecting to a carefully chosen set of nodes, establishes channels with them, initiatesnumerous multi-hop payments between its nodes, and griefs these payments simultaneously.To reduce the custody required for an attack, Mizrahi et al. [14] proposed to lock the channel by init

Editors VincentGramoli UniversityofSydney,Australia EPFL,Switzerland vincent.gramoli@sydney.edu.au HannaHalaburda NYUSternSchoolofBusiness,USA hh66@stern.nyu.edu RafaelPass Cornel