Instantaneous Decentralized Poker Iddo Bentov Ranjit Kumaresan Andrew Miller CornellUniversity MicrosoftResearch UIUC 7 Abstract 1 Wepresentefficientprotocolsforamortized securemultipartycomputationwithpenaltiesandsecure 0 cashdistribution,ofwhichpokerisaprimeexample. Ourprotocolshaveaninitialphasewheretheparties 2 interactwithacryptocurrencynetwork,thatthenenablesthemtointeractonlyamongthemselvesover b thecourseofplayingmanypokergamesinwhichmoneychangeshands. e The high efficiency of our protocols is achieved by harnessing the power of stateful contracts. Com- F pared to the limited expressive power of Bitcoin scripts, stateful contracts enable richer forms of inter- 1 actionbetweenstandardsecurecomputationandacryptocurrency. 1 We formalize the stateful contract model and the security notions that our protocols accomplish, and provide proofs in the simulation paradigm. Moreover, we provide a reference implementation in ] Ethereum/Solidityforthestatefulcontractsthatourprotocolsarebasedon. R We also adopt our off-chain cash distribution protocols to the special case of stateful duplex micro- C paymentchannels,whichareofindependentinterest. IncomparisontoBitcoinbasedpaymentchannels, . ourduplexchannelimplementationismoreefficientandhasadditionalfeatures. s c [ 1 Introduction 3 v As demonstrated by Cleve [12], fair multiparty computation without an honest majority is impossible in 6 the standard model of communication. Hence, there have been numerous attempts to circumvent this 2 7 theoretical impossibility result, in particular by relying on techniques such as gradual release (cf. [43] 6 for a survey) and optimistic fair exchange [4]. With the introduction of Bitcoin [40], the academic study 0 of decentralized cryptocurrencies gave rise to a line of research that seeks to impose fairness in secure 1. multipartycomputation(MPC)bymeansofmonetarypenalties[6]. Inthismodel, theparticipatingparties 0 make security deposits, and the deposits of parties who deviate from the protocol are used to compensate 7 the honest parties. 1 Still, interacting with a Proof-of-Work based decentralized network entails long waiting times due to the : v needtobesecureagainstreversaloftheledgerhistory. ArecentworkbyKumaresanandBentov[30]showed i a Bitcoin based amortization scheme in which the parties run an initial setup phase requiring interaction X with the cryptocurrency network, but thereafter they engage in many fair secure computation executions, r communicating only among themselves for as long as all parties are honest. a 1.1 Our Contributions Asymptotic gains in amortized protocols. We present new protocols that rely on stateful contracts instead of Bitcoin transactions, and thereby improve upon the previous results in several ways. First, the setup phase of [30] requires the n parties to execute O(n2) PoW-based rounds of interaction with the cryptocurrency network, while our stateful protocols require O(1) rounds. The protocols of [30] for secure MPCwithpenaltiesalsorequireasecuritydepositofO(n2)coinsperparty,whileourprotocolsrequireO(n) coins per party. We use UC-style definitions [10] to formalize the security notions that are achieved by our amortized protocols, and provide proofs using the simulation paradigm. 1 Amortized SCD. Unlike the protocols in [30], our protocols support secure cash distribution with penal- ties (SCD), rather than only fair secure MPC with penalties. The distinction between SCD and fair MPC with penalties is that in SCD the inputs and outputs of the parties are comprised of both money and data, while fair MPC with penalties has only data for inputs and outputs (but uses money to compensate honest parties who did not learn the output). Real poker. AcanonicalexampleofSCDisamentalpokergame,wheretheoutcomeofthecomputation isnotintrinsicallyuseful,butratherdetermineshowmoneyshouldchangehands. Thismeansthatfollowing an on-chain setup phase, the parties can play any number of instantaneous poker games, for as long as no partyhasrunoutofmoney. Hence,whilethereisalargebodyofworkonefficientmentalpokerschemes,to the best of our knowledge we are the first to provide a practical poker protocol with actual money transfers from the losers to the winners. Moreover, we accompany our poker protocol with an implementation for the Ethereum cryptocurrency. Highly efficient payment channels. As a special case, our off-chain cash distribution protocols can also be used for stateful duplex payment channels. This use case does not require secure computation and yet it is particularly important. The reason for this is that micropayment channels can reduce the amount of transaction data that the decentralized cryptocurrency network maintains, and thus the long- term scalability pressures that a cryptocurrency faces can be relieved by well-functioning off-chain payment channels (see, e.g., [17] for further discussion). We compare our stateful duplex channel to Bitcoin based off-chain payment channels, and show that that the stateful approach yields better efficiency and extra features. Sincemicropaymentchannelsareofindependentinterest,weprovideaself-containedprotocoland implementation of our stateful duplex off-chain channel. 1.2 Related Works The first secure computation protocols that utilize Bitcoin to guarantee fairness are by Andrychowicz et al.[3,2]andbyBentovandKumaresan[6]. Bitcoinbasedprotocolsforreactivecashdistributionandpoker were given by Kumaresan, Moran, and Bentov [31]. The technique for amortized secure computation with penalties in the Bitcoin model was introduced by Kumaresan and Bentov [30]. Our protocols subsume and improve on these, providing both the amortization benefit of [30] with the cash distribution functionality of [31], and furthermore reduce the on-chain costs and the necessary amount of collateral. Several other works analyze fair (non-amortized) protocols in other cryptocurrency models, in particular the analysis of Kiayias, Zhou, and Zikas [28] and Kosba et al. [29]. The cash distribution contract we present (see Section 2.3) is closely related to an ongoing proposal in thecryptocurrencycommunityfor“statechannels”(cf. Coleman[13]),whereinagroupofpartiesagreeona sequenceof“off-chain”statetransitions,andresorttoanon-chainreconciliationprocessonlyinthecasethat the off-chain communications break down. To our knowledge, no security definition has yet been provided for such applications. Furthermore, our application is much more expressive, since we can implement state transitions that depend on parties’ private information, while still guaranteeing fairness. The original mental poker protocol by Shamir, Rivest, and Adelman [46] relies on commutative encryp- tion. However,theirprotocolwasonlyfortwopartiesandwasfoundtohavesecurityvulnerabilities[33,14]. Following that, many different protocols for mental poker were proposed. For example, Cr´epeau presented secure poker protocols that are based on probabilistic encryption [15] and zero-knowledge proofs [16], but his constructions are rather inefficient. In 2003, a breakthrough by Barnett and Smart [48] gave a far more efficient poker protocol that utilizes homomorphic encryption. Castell`a-Roca et al. [11] presented a poker protocol that is similar to [48], but has a more efficient shuffle procedure. The poker protocol that we integrate into our SCD implementation is by Wei and Wang [27], with a full version by Wei [26]. This protocol replaces the homomorphic encryption component of [11] with a faster proof of knowledge scheme, and provides a security proof using the simulation paradigm. 2 2 Overview In Bitcoin, the full nodes maintain a data structure that is known as the “unspent transaction outputs set” (UTXO set), which represents the current state of the ledger. Each unspent output in the UTXO set incorporates a circuit (a.k.a. script or predicate), such that any party who can provide an input (a.k.a. witness) that satisfies the circuit can spend the coins amount of this output into a new unspent output. Therefore, if there is only one party who knows the witness for the circuit, then this party is in effect the holder of the coins. Standard Bitcoin transactions use a signature as the witness. The signature is applied on data that also references the new unspent output, thereby binding the transaction to the specific receiver of the coins and thus prevents a man-in-the-middle attack by the nodes in the decentralized Bitcoin network. However, Bitcoin allows the use of more complex circuits as well. Such circuits allow us to support quite elaborate protocols in which money changes hands, as opposed to to using Bitcoin only for simple money transfers between parties. Specifically,protocolsforfairsecurecomputationandfairlotterycanbeimplementedwithablackboxuse ofan ? functionality[6,31,32]. Essentially, ? specifiesthata“sender”P lockshercoinsinaccordance FCR FCR 1 with some circuit φ, such that a “receiver” P can gain possession of these coins if she supplies a witness 2 w that satisfies φ(w)=1 before some predefined timeout, otherwise P can reclaim her coins. As shown in 1 [6, 30], the ? functionality can be realized in Bitcoin, as long as the circuit φ can be expressed in the FCR Bitcoin scripting language. In the aforementioned secure computation and lottery protocols [6, 31, 32], the particular circuit that is needed verifies a signature (just as in standard transactions) and a decommitment according to some arbitrary hardcoded value. Such a circuit can be realized by using a hash function for thecommitmentscheme(BitcoinsupportsSHA1,SHA256,RIPEMD160). Sincesignatureverificationisanorder of magnitude more complex than hash invocation, the complexity of an ? transaction is only marginally FCR higher than that of standard Bitcoin transactions. Thus, the ? model can be regarded as a restricted version of the Bitcoin model, which is expressive FCR enough for realizing multiparty functionalities that are impossible in the standard model. One may ask whether it is possible to design better protocols in a model that is more expressive than the Bitcoin model. In this work we will answer the question in the affirmative. ApossibleextensiontotheBitcointransactionstructureiscovenants[38,41],whereeachunspentoutput specifies not only the conditions on who can spend the coins (i.e., the circuit φ), but also conditions on who is allowed to receive the coins. Indeed, as shown in [38], covenants can be used to implement certain tasks that the current Bitcoin specifications do not support (e.g., vaults that protect against coin theft). Generalizing further, each unspent output can maintain a state. That is, an unspent output will be comprised of a circuit φ and state variables, and parties can update the state variables by carrying out transactions that satisfy φ in accord with the current values of the state variables. Additionally, parties can deposit coins into the unspent output, and a party can withdraw some partial amount of the held coins by satisfyingφwithrespecttothestatevariables. ThisapproachisusedinEthereum[52,9],whereanunspent output is referred to as a “contract”. With a slight abuse of terminology, the transaction format of the Bitcoin model can thus be described as “stateless”. By this we mean that the coins of an unspent Bitcoin output are controlled by a hardcoded predicatethatrepresentstheircurrentstate,andanyonewhocansupplyawitnessthatsatisfiesthispredicate is able to spend these coins into an arbitrary new state. Let us mention that the Bitcoin transaction format can still enable “smart contracts”, in the sense of having coins that can be spent only if some other transaction took place (i.e., without relying on a third party). The technique for achieving this would generally involve multiple signed transactions that are prepared in advance and kept offline. Then, depending on the activity that occurs on the blockchain, some of the prepared transaction will become usable. However, in certain instances the amount of offline transactions may grow exponentially, as in the case of zero-collateral lotteries [37]. The protocols that we present in this work will be in a model that has stateful contracts. As described, this refers to unspent outputs that are controlled according to state variables. It should be emphasized that 3 our protocols do not rely on a Turing-complete scripting language, as all the loops in the contracts that we design (in particular our poker contract) have a fixed number of iterations. To justify our modeling choice, let us review the advantages of stateful contracts over stateless transac- tions. As a warmup, we begin by examining simple protocols for 2-party fair exchange. 2.1 Fair Exchange with Penalties between Two Parties Suppose that P ,P execute an unfair secure computation that generates secret shares of the output x = 1 2 x x and commitments T =h(x ),T =h(x ), and delivers (x ,T ,T ) to party P . Consider the naive 1 2 1 1 2 2 i 1 2 i ⊕ protocol for fair exchange of the shares x ,x via ? transactions: 1 2 FCR P T2 P (1) 1 2 −−−−−−−q−,τ−−−−−→ P T1 P (2) 2 1 −−−−−−−q−,τ−−−−−→ An arrow denotes an ? transaction that lets P collect q coins from P before time τ, by revealing FCR i 3−i a decommitment y such that h(y)=T . i The above protocol is susceptible to an “abort” attack by a malicious P that waits for P to make 2 1 the deposit transaction (i.e., Step 1), after which P simply does not execute Step 2 to make a deposit 2 transaction. Instead, P claims the first transaction, and obtains q coins while P obtains x . Now, P 2 1 2 2 simplyabortstheprotocol. Ineffect,thismeansthatanhonestP paidq coinstolearnP ’sshare. Fairness 1 2 withpenaltiesrequiresthatanhonestpartyneverlosesanymoney,hencethisnaiveapproachdoesnotwork (cf. [6] for precise details). The above vulnerability can be remedied via the following protocol: P1 T1∧T2 P2 (1) −−−−−−−−q−,τ−2−−−−−−→ P T1 P (2) 2 1 −−−−−−−q,−τ1−−−−−→ For this improved protocol to be secure, two sequential PoW-based waiting periods are necessary. Oth- erwise, a corrupt P may be able to reverse transaction (2) after P claims it, so that P would reveal her 2 1 1 share and not be compensated. Bycontrast,considerthe2-partyfairexchangeprotocolthatisbasedonastatefulcontract,asillustrated in Figure 1. Here, both parties should deposit q coins each, concurrently. If the 2q coins were not deposited into the contract before the timeout is reached, then an honest party who deposited into the contract can claim her coins back. In the case that the 2q coins were deposited, it triggers to contract to switch to a new state, where each party P can claim her deposit by revealing the hardcoded decommitment T . In contrast i i to the ? protocol, the stateful contracts requires only one PoW-based waiting period before the honest FCR parties may reveal their shares. q q?+q P switch from x : h(x )=h 1 state=deposit 1 1 1 to state=claim q q?+q P upon receiving x : h(x )=h 2 the 2q coins 2 2 2 Figure 1: Stateful contract for fair secure 2-party computation with penalties. While the quantitative difference between stateful and stateless contracts in the above discussion may appeartobeunimpressive,thedistinctionbecomesmorepronouncedinthecaseofmultipartyfairexchange 4 (a.k.a. fair reconstruction [6]), and even more so in amortized protocols. Let us demonstrate the amortized multiparty case in the next section. 2.2 Amortized Multiparty Fair SFE with Penalties We illustrate in Figure 2 the stateful contract for n parties who wish to engage in amortized fair secure function evaluation (SFE) with penalties. The lifespan of this contract can be thought of as having three phases: (cid:136) Deposit Phase: Allpartiesshoulddepositq(n 1)coinseach. Ifnq(n 1)coinsweredepositedbefore − − theinitialtimeoutisreached,thenthecontrastswitchesintoan“active”state. Otherwise,eachhonest party who deposited will claim her q(n 1) coins back. − (cid:136) Execution Phase: While the state is “active”, the n parties will not interact with the contract at all. Instead, they will engage in multiple executions of SFE. In the ith execution, the secure computation preparessecretshares x n oftheoutput,aswellascommitments h =h(x ) n ,anddelivers { i,j}j=1 { i,j i,j }j=1 (x ;h ,h ,...,h )topartyP . Eachpartywillthenusehersecretkey(forwhichthecorrespond- i,j i,1 i,2 i,n j ingpublickeyishardcodedinthecontract)tocreateasignatures forthetuple(h ,h ,...,h ), i,j i,1 i,2 i,n andsendthesignatures totheotherparties. Uponreceivingallthesignatures s n ,eachhonest i,j { i,j}j=1 party P will send her secret share x in the clear to the other parties. j i,j (cid:136) Claim Phase: In the case that a corrupt party P did not reveal her share x during the execution c i,c phase, each honest party P will send m = (x ;s ,s ,...,s ) to the contract, and thereby j i,j i,j i,1 i,2 i,n transition the contract into a “payout” state. The message m also registers that P deserves to i,j j receive a compensation of q coins, in addition to her initial q(n 1) coins deposit. Until a timeout, − any party P can avoid being penalized by sending m =(x ;s ,s ,...,s ) with i i to the ‘ i0,‘ i0,‘ i0,1 i0,2 i0,n 0 ≥ contract. In case i > i, this would invalidate the q coins compensation that was requested via m , 0 i,j and instead register that P is owed q coins in compensation. ‘ q(n-1) q?+q(n-1) P1 x1, signatureP 1 ,P 2 ,. .. , P n(i,(h(x1) ␣ ␣ ␣. ..)) q(n-1) q?+q(n-1) P2 x2, signatureP 1 ,P 2 ,. .. , P n(i,(␣h(x2) ␣ ␣ ...)) waiting q(n-1) q?+q(n-1) P3 x3, signatureP 1 ,P 2 ,. .. , P n(i,(␣ ␣h(x3) ␣ ...)) period q(n-1) q?+q(n-1) Pn xn, signatureP 1 ,P 2 ,. .. ,P n(i,(␣ ␣ ␣ . ..h(xn))) Figure 2: Stateful contract for amortized multiparty fair SFE with penalties. Ascanbeobserved,thenpartiescanengageinanunlimitedamountofoff-chainSFEexecutions(where the executions can compute different functions), and no interaction with the blockchain will take place as long as all parties are honest. When a corrupt party P deviates from this protocol, each honest party will c receive q coins compensation, that is taken from P ’s initial security deposits of q(n 1) coins. The actual c − protocol handles more technical issues, cf. Section 4. By contrast, achieving the same guarantees in the ? model is known to possible only via an intricate FCR “see-saw” construction, that requires O(n2) PoW-based rounds and a collateral of O(qn2) coins from each party [30]. Moreover, the stateless nature of Bitcoin transaction entail a global timeout after which the entire see-saw construction expires. Setting the global timeout to a high value enables many off-chain SFE executions,butalsoimpliesthataDoSattackbyacorruptparty(whowouldabortbeforesigninganysecret 5 shares of the output of the first execution) will cause each honest party to wait for a long time before being able to regain possession of her O(qn2) coins deposit. Due to the time value of money, this is obviously undesirable. The stateful approach does not require a global timeout that is measured in absolute terms. Instead,thecontractremainsoperationalforaslongasallthepartieswishtoengageintheoff-chainprotocol, and transitioning the contract into the “payout” state will trigger an event whose expiration is relative to the time at which the transition occurred. We provide an Ethereum implementation of this contract in Figure 18. Can stateful contracts provide even more benefits? As the next section shows, the answer is “yes”. 2.3 Stateful Off-Chain Cash Distribution Protocols Suppose that the parties P ,P wish to play a multiple-round lottery game, such that either of them is 1 2 allowed to quit after each round. Thus, P enters the lottery with m coins, P enters with w coins, and in 1 2 the first round P picks a random secret x and commits to com(x ), P picks x and commits to com(x ), 1 1 1 2 2 2 and then they decommit x ,x so that the least significant bit of x x decides whether P ’s balance is 1 2 1 2 1 ⊕ incremented to m+1 and P ’s balance is decremented to w 1, or P ’s balance is decremented to m 1 2 1 − − and P ’s balance is incremented to w+1. If both of them wish to continue, then they will proceed to the 2 next round and repeat this protocol. Obviously, the parties must not be allowed to quit in the middle of a round without repercussions. That is, if P reveals her decommitment x and P aborts, then P should be compensated. Moreover, as in 1 1 2 1 Section 2.2, it is better that the parties play each round without any on-chain interaction. Therefore, in each round i, P and P will sign the current balance m ,w together with the round index 1 2 i i i and the commitments com(x ),com(x ). After the parties exchange these signed messages, they can i,1 i,2 safelysendtheirdecommitmentsx ,x intheclear. Thelogicofthestatefulcontractallowseachpartyto i,1 i,2 send her decommitment along with the signed message, and thus finalize the game according to the current balances. If the other party does not reveal her decommitment during a waiting period, then the contract increments the balance of the honest party. If both parties reveal, then the contract computes x x to 1 2 ⊕ decidewhowonthelastround,sothatthebalanceofthewinnerisincrementedandthebalanceoftheloser is decremented. During the waiting period, an honest party can send a signed message with an index i >i 0 and thereby invalidate the message that a corrupt party sent to the contract. It should also be noted that an honest party should not continue to play after the balance of the other partyreaches0,sincethecontractcannotrewardthewinnermoremoneythanwhatwasoriginallydeposited. We illustrate the contract in Figure 3, and provide an Ethereum implementation in Figures 18 and 20. The multiparty version of our lotery code is available to run at [1]. m m' 1 P1 x1, signatureP 1 ,P 2 (m',w',h(x1),i) waiting ± w period w' 1 P2 x2, signatureP 1 ,P 2 (m',w',h(x2),i) ± Figure 3: Off-chain 2-party lottery. Such a 2-party lottery is a very simple example of a secure cash distribution with penalties (SCD) func- tionality [31]. Another special case of SCD is a multiparty poker game in which money (i.e., coins of the cryptocurrencysystemthatthepartieshold)istransferredfromloserstowinners. InSection3andonwards we formulate the ideal functionalities and protocol for fair MPC and SCD, and in Section 7 we provide an efficient off-chain poker protocol with implementation. As noted in Section 1, SCD can also be realized in the ? model via a non-amortized (i.e., on-chain) FCR protocol, though the construction requires a setup phase with O(n2) PoW-based rounds. To the best of our knowledge, there is no amortized SCD realization in the ? model. FCR 6 2.4 Stateful Duplex Off-Chain Micropayment Channels By removing the commit/decommit logic, the 2-party contract of Section 2.3 would function as a duplex off-chain payment channel. Suppose that Alice may wish to buy some items that Bob sells, and vice versa. Hence, Alice will put m coins into the contract, and Bob will put w coins into the contract. After these two initial transactions are confirmed via PoW, Alice and Bob will be able to perform bi-directional off-chain payments between them. That is, if Bob wishes to buy an item that costs d coins from Alice, then he will create the signature S =Sign (m+d,w d,1)andsendS toAlice. SinceAlicecancreateS =Sign (m+d,w d,1) b,1 skB − b,1 a,1 skA − onherown,sheeffectivelyreceivedapaymentofdcoinsfromBob. Lateron,Alicemaywishtobuyanitem from Bob that costs d coins, hence she will create the signature S = Sign (m+d d,w d+d,2) 0 a,2 skA − 0 − 0 and send it to Bob. IfAliceismaliciousandtriestofinalizethepaymentsbysendingS ,S tothecontract,thenBobwill a,1 b,1 be able to invalidate Alice’s message by sending S ,S = Sign (m+d d,w d+d,2) during the a,2 b,2 skB − 0 − 0 waiting period of the contract. Since 2>1, i.e., the message (m+d d,w d+d,2) has a higher index 0 0 − − than that of the message (m+d,w d,1), the rules of the contract will allow Bob to withdraw w d+d 0 − − coins, as it should be. Letusnotethattheduplexchannelcannotendupinadeadlock. Let(m,w,i)bethelastsignedmessage that was sent off-chain. Suppose that Alice now signs and sends (m 1,w+1,i+1) with the intention of − buying an item that costs 1 coin from Bob, and at the same time Bob signs and sends (m+1,w 1,i+1) − with the intention of buying an item that costs 1 coin from Alice. In this case, both Alice and Bob will refuse to send the item in exchange for the payment. Instead, one of them (for example Alice) will send a signed message(m 1,w+1,i+2)that specifiesthe higherindex i+2, and thenBob cansecurely send his − item to Alice. As in Section 2.2, a duplex payment channel that is based on a stateful contract does not have global timeout: thecontractremainsoperationalaslongasAliceandBobwishtokeepsendingoff-chainpayments between them, and transitioning the contract into the waiting period will trigger an event whose timeout is relative. This stands in contrast to the original Bitcoin-based stateless payment channel (cf. [39, 49, 24, 50, 35]), that relies on the CHECKLOCKTIMEVERIFY script instruction (or on refund transactions) and therefore has an absolute timeout. Setting the absolute timeout to a high value enables off-chain payments over an extendedperiodoftime,butalsoenablesDoSbyacorruptpartywhowouldabortsothatthelockedmoney of the honest party will be rendered useless during this extended time period. Our stateful contract also allows a party who is running out of funds to deposit more coins into the contract via an on-chain transaction. As the alternative is to terminate the channel and starting a new one, this approach is more efficient and requires less fees. Furthermore, our stateful approach allows the parties toinvokeon-chainincrementalwithdrawals,i.e.,tomovesomeoftheirdepositedamountoutofthecontract while retaining the rest of the amount for future off-chain payments. The straightforward Bitcoin-based payment channel [49, 24, 50] is uni-directional (e.g., monotonically increasing balance from Alice to Bob). Poon and Dryja [44] developed an improved payment channel with duplex functionality, that operates by generating ephemeral private keys. Independently, Decker and Wat- tenhofer[19]developedanalternativetechniqueforduplexchannels,wherethedirectionofpaymentscanbe reversed (up to a bounded number of times) by having both parties sign a new “recovery” transaction with an earlier timelock value. The Poon-Dryja duplex channel supports a relative timeout (following a Bitcoin protocolfork[8]),whiletheDecker-Wattenhoferchannelrequiresanabsolutetimeout. BoththePoon-Dryja and Decker-Wattenhofer constructions are significantly more complex than our duplex channel (due to the statelessnatureofBitcointransactions),andneitherofthemsupportsincrementaldeposits/withdrawals. It should be noted that the Poon-Dryja and Decker-Wattenhofer channels also support “hashlock contracts,” which effectively allow multiple channels to be chained, forming a payment network. This feature can easily be incorporated into our setting as well, but we omit it in the interest of simplicity (as it beyond the scope of our work). Overall, the stateful contract enables a duplex off-chain channel where each (micro-)payment requires transmission of only one simple signature from the payer to the payee, which is the bare minimum that any 7 off-chain transaction entails. See Figure 4 for an illustration of the stateful duplex off-chain channel. m m' A signature (m',w',i) waiting A,B w period w' B signature (m',w',i) A,B Figure 4: Duplex Off-chain Payment Channel. AsthecomparisontoSection2.3alludesto,thestatefulcontactforoff-chainpaymentsisaspecialcaseof ourSmartAmortizecontract(giveninFigures18and20)foroff-chainsecurecashdistribution. However,since off-chainmicropaymentchannelsareofparticularinterest,weprovidetheself-containedimplementationofa duplexoff-chainchannelthatsupportsincrementaldepositsandwithdrawals(seeSection6.1andFigure21). Let us note that the universal payment channels proposal of Tremback and Hess [51] is similar to the duplex payment contract that we implement. See also Peterson [42] for an implementation of a slightly different duplex channel design. In contrast to our duplex channel, [51] and [42] do not support incremental deposits and withdrawals. 3 Preliminaries We say that a function µ() is negligible in λ if for every polynomial p() and all sufficiently large λ’s it holds · · that µ(λ) < 1/p(λ). A probability ensemble X = X(t,λ) is an infinite sequence of random variables indexe|d by|a and λ ∈ N. Two distributio{n ensem}bctl∈e{s0,X1}∗=,n∈{NX(t,λ)}λ∈N and Y = {Y(t,λ)}λ∈N are said to be computationally indistinguishable, denoted X Y if for every non-uniform polynomial-time ≡ algorithm D there exists a negligible function µ() such that for every t 0,1 , ∗ · ∈{ } Pr[D(X(t,λ))=1] Pr[D(Y(t,λ))=1] µ(λ). | − |≤ All parties are assumed to run in time polynomial in the security parameter λ. We prove security in the “securecomputationwithcoins”(SCC)modelproposedin[6]. Notethatthemaindifferencefromstandard definitions of secure computation [22] is that now the view of contains the distribution of coins. Let Z ideal (λ,z) denote the output of environment initialized with input z after interacting in the ideal f, , SZ Z processwithidealprocessadversary and(standardorspecial)idealfunctionality onsecurityparameter f S G λ. Recall that our protocols will be run in a hybrid model where parties will have access to a (standard or special) ideal functionality . We denote the output of after interacting in an execution of π in such a g model with by hybridg G (λ,z), where z denotes ’sZinput. We are now ready to define what it means for a protocoAl to SCC realπiz,Ae,aZfunctionality. Z Definition 1. Let n N. Let π be a probabilistic polynomial-time n-party protocol and let f be a proba- ∈ G bilistic polynomial-time n-party (standard or special) ideal functionality. We say that π SCC realizes with f G abortinthe -hybridmodel(where isastandardoraspecialidealfunctionality)ifforeverynon-uniform g g G G probabilistic polynomial-time adversary attacking π there exists a non-uniform probabilistic polynomial- A timeadversary fortheidealmodelsuchthatforeverynon-uniformprobabilisticpolynomial-timeadversary S , Z ideal (λ,z) c hybridg (λ,z) . { f,S,Z }λ∈N,z∈{0,1}∗ ≡{ π,A,Z }λ∈N,z∈{0,1}∗ Definition 2. Let π be a protocol and f be a multiparty functionality. We say that π securely computes f with penalties if π SCC-realizes the functionality ? according to Definition 1. Ff 8 Notation: sessionidentifiersid,partiesP ,...,P ,adversary thatcorrupts P ,safety deposit d,penalty 1 n s s C S { } ∈ amount q. SetH =[n] C andh= H . \ | | Depositphase:Initializeflg= . Waittogetmessage(setup,sid,ssid,j,coins(d))fromP forallj H. Wait j ⊥ ∈ togetmessage(setup,sid,ssid,coins(hq))from . S Executionphase:Setflg=0. Forid=1,2, ,sequentiallydo: ··· (cid:136) Ifamessage(exit,sid)isreceivedfromP ,thensend(exit,sid,j)toallparties,andgototheclaimphase. j (cid:136) Wait to receive a message (input,sid,ssid id,j,y(id),g(id)) from P for all j H. Then send (function,sid, k j j ∈ ssid id,g(id))toallparties. k (cid:136) Wait to receive a message (input,sid,ssid id, y(id) ,g(id)) from . If no such message was received, then s s C k { } ∈ S gototheclaimphase. (cid:136) Computez(id) g(id)(y(id),...,y(id))andsend(output,sid,ssid id,z(id))to . ← 1 n k S (cid:136) If returns(continue,sid,ssid id),send(output,sid,ssid id,z(id))toeachP . j S k k (cid:136) Elseif returns(abort,sid,ssid),updateflg=1,andgototheclaimphase. S Claimphase: (cid:136) Ifflg=0or ,send(return,sid,ssid,coins(d))toP forj H. Ifflg=0,send(return,sid,ssid,coins(hq))to j ⊥ ∈ . S (cid:136) Else if flg = 1, send (penalty,sid,ssid,coins(d+q+q )) to P for all i H where q = 0 unless sent a i i i ∈ S message(extra,sid,ssid, (i,q ) ,coins( q )). { i }i∈H i∈H i P Figure 5: Special ideal functionality for multiple sequential SFE with penalties. FM∗SFE Throughout this paper, we deal only with static adversaries and impose no restrictions on the number of parties that can be corrupted. Our schemes also make use of a digital signature scheme which we denote as (SigKeyGen,SigSign,SigVerify). Please see [6, 31, 32, 30] for additional details on the model including the necessary modifications to UC. Please also see [28] which extensively treats these modifications, proposes alternative models, and uses protocol compilers different from GMW. 3.1 Ideal Functionalities Secure computation with penalties—multiple executions. We now present the functionality FM∗SFE which we wish to realize. Recall that secure computation with penalties guarantees the following. An honest party never has to pay any penalty. If a party aborts after learning the output and does not deliver output to honest parties, then every honest party is compensated. SeeFigure5foraformaldescription. Notethat directlyrealizesmultipleinvocationsofnon-reactive FM∗SFE securecomputationwithpenalties. Inthefirstphasereferredtoasthedepositphase,thefunctionality FM∗SFE accepts safety deposits coins(d) from each honest party and penalty deposit coins(hq) from the adversary. Note that the penalty deposit suffices to compensate each honest party in the event of an abort. Once the deposits are made, parties enter the next phase referred to as the execution phase where parties can engage in unbounded number of secure function evaluations. In each execution, parties submit inputs and wait to receive outputs. As usual, the ideal adversary gets to learn the output first and then decide whether to S deliver the output to all parties. If decides to abort, then no further executions are carried out, parties S enter the claim phase, and honest parties get coins(d+q), i.e., their safety deposit plus the penalty amount. Now if never aborts during a local execution, then the safety deposits are returned back to the honest S parties, and gets back its penalty deposit. Note that we explicitly allow an exit command that enables S partiestoexitthecontractimmediately. Priorworks[31,30]requiredpartiestowaitforapre-specifiedtime out parameter before parties can reclaim their deposits. Supporting cash distribution via . See Figure 6 for a formal definition for . The definition for FM∗SCD FM∗SCD 9 Notation: sessionidentifiersid,partiesP ,...,P ,adversary thatcorrupts P ,safety deposit d,penalty 1 n s s C S { } ∈ amount q,setH =[n] C. \ Depositphase:Initializeflg= . ⊥ (cid:136) Waittoreceiveamessage(setup,sid,ssid,j,coins(d))fromP forallj H. j ∈ (cid:136) Waittoreceiveamessage(setup,sid,ssid,coins(hq))from whereh= H . S | | Executionphase:Initializeflg=0andb 0. Forid=1,2,...,sequentiallydo: ← (cid:136) Ifamessage(exit,sid,ssid)isreceivedfromP ,thensend(exit,sid,ssid,j)toallparties,andgototheclaim j phase. (cid:136) If a message (addmoney,sid,ssid id,b ,coins(b )) is received from some P , and a message j j j k (addmoney,sid,ssid id,b ) was received from every P with k = j, then send (addmoney,sid,ssid id,b ) k j k 6 k j toallparties. Updateb b+( ,0,b ,0, ). j ← ··· ··· (cid:136) Initialize state = . Wait to receive message (function,sid,ssid id,g(id)) from P for all j H. Then send j (function,sid,ssid⊥id,g(id))toallparties. k ∈ k (cid:136) Parseg(id)= g(id) . Fork=1,...,ρ,sequentiallydo: { k }k∈[ρ] – Waittoreceivemessage(input,sid,ssidkidkk,j,yj0)fromPj forallj∈H. – Waittoreceiveamessage(input,sid,ssidkidkk,{ys0}s∈C)fromS. Ifnosuchmessagewasreceived,update flg=1andgototheclaimphase. – Compute(z,b0,state)←gk(id)(y10,...,yn0;state,b). – Sendmessage(output,sid,ssid id k,z,b0)to . k k S – If sends(continue,sid,ssid id k),send(out,sid,ssid id k,z,b0)toallPi. S k k k k – If returns(abort,sid,ssid id k),setflg=1,andgototheclaimphase. S k k – Updateb b0. ← Claimphase: (cid:136) If flg = 0 or , send (return,sid,ssid,coins(d + b )) to all P for r H. If flg = 0, send r r ⊥ ∈ (return,sid,ssid,coins(hq+ b ))to . (cid:136) Else if flg=1, send (penalty,ssid∈,Cssisd,coinSs(d+q+b +q )) to P for all i H where q =0 unless sent a P i i i ∈ i S message(extra,sid,ssid, q ,coins( q )). Send(remaining,sid,ssid,coins( b ))to . { i}i∈H i∈H i s∈C s S P P Figure 6: Special ideal functionality for multiple sequential MPC with penalties. FM∗SCD 10