Smart Contracts for Trustless Sampling of Correlated Equilibria

1 Introduction

Smart contracts. The concept of smart contracts was first proposed [Szabo, 1997] as protocols that let us formalize and secure relationships across a public network. Their relevance dramatically increased with the arrival of programmable cryptocurrency platforms like Ethereum [Vogelsteller and Buterin, 2014]. Blockchain, the underlying protocol of Bitcoin [Nakamoto, 2009], can go beyond managing digital currency transactions and serve as a consensus mechanism for any well-defined deterministic process. Thus, programmable blockchains such as Ethereum allow arbitrary programs, also called smart contracts, to be written and executed subject to consensus. Smart contracts and blockchains offer a trustless system for automating the execution of an agreement terms without relying on central authorities.

Gas. Gas is the measure of computational work of executing an transaction on Ethereum. It is defined in Ethereum virtual machine (EVM) maintained by all nodes according to the consensus protocol, hence not depending on any specific machine. A transaction issuer is required to pay a gas fee proportional to the transaction's gas usage. Gas usage is the criterion of efficiency in the design of Ethereum programs [Cai et al., 2023; Barakbayeva et al., 2025; Ballweg et al., 2025; Farokhnia and Goharshady, 2023b; Farokhnia and Goharshady, 2023a].

Non-cooperative games and correlated equilibria. Noncooperative games are strategic interactions among rational players who act independently to maximize their payoff without forming coalitions. The concept of equilibrium, a stable state where no player has an incentive to deviate from their chosen strategy, is essential for the analysis of noncooperative games. The first classical form of equilibrium is the Nash equilibrium, in which each player's strategy is optimal given the other players' strategies, i.e. no player has an incentive to deviate from their strategy assuming that other players do not deviate. In Nash equilibria, the players act completely independently in choosing their strategies but they may use randomness. Generalizing Nash equilibria, Aumann proposed the concept of a correlated equilibrium [Aumann, 1974; Aumann, 1987], which can achieve payoffs that Pareto dominate Nash equilibria. In a correlated equilibrium setting, an external signal, also called the correlation device, or a trusted third-party mediator coordinates players' strategies and enables improved outcomes.

Example. Consider two drivers who are reaching an intersection. They each have two options: stopping or crossing. Naturally, each player prefers to cross and thus there is a small negative payoff associated with stopping. However, if both players decide to cross at the same time, there will be a crash and they both get a huge negative payoff. If we rely on Nash equilibria, each player has to choose their strategy independently and with no coordination. It is thus impossible to completely rule out a crash. However, a correlated equilibrium can be obtained by a traffic light, which acts as the external signal/correlation device, and suggests strategies to both players. Each player can only observe the signal's suggestion to themselves, i.e. their own component of the signal, but not the signal shown to the other player. However, they know that the signal components are correlated, e.g. if the light is green for me, then it should be red for the other side. This correlation allows the players to avoid a crash but it is also self-enforcing in the sense that it is in each player's best interest to follow the traffic light.

Game-theoretic analysis and design of Blockchain protocols.There are many works that consider game-theoretic analysis of blockchain protocols and smart contracts, as well as their vulnerabilities and the corresponding attacks [Biais et al., 2021; Azouvi and Hicks, 2021; Xu et al., 2021; Liu et al., 2019; Lewenberg et al., 2015; Laszka et al., 2015; Johnson et al., 2014; Kruminis and Navaie, 2022; Bhudia et al., 2023; Manshaei et al., 2018; Chatterjee et al., 2018a; Chatterjee et al., 2018b]. This is unsurprising, given the strategic nature of the interactions on the blockchain, in which there are often well-defined payoffs for the parties in the form of the underlying cryptocurrency and the players are naturally incentivized to maximize their payoffs. Thus, to avoid attacks and incentive misalignments, designers of blockchain-based protocols and smart contracts must ensure that their protocol disincentivizes undesirable behavior and strictly encourages the players to act honestly, i.e. follow the protocol as was intended by the designer. This brings us into the area of mechanism design [Diamantaras et al., 2009], in which the goal is to design games with desired equilibria that allow us to achieve desired outcomes. Examples of such mechanism design in blockchain-based protocols include BitHalo [Zimbeck et al., 2014; Goharshady, 2021] and game-theoretic approaches for decentralized generation of tamper-proof random numbers [Cai and Goharshady, 2023a; Schindler et al., 2020].

Motivation. Currently, mechanism design for blockchain applications is limited to Nash equilibria. This is the approach taken in the works mentioned above. However, mechanism design literature, when not considering blockchain, often uses the much more expressive and general concept of correlated equilibria [Diamantaras et al., 2009]. The obstacle in adopting correlated equilibria in blockchain-based usecases is their inherent reliance on an external signal. Such an external signal is assumed to be a trusted third-party which samples from the correlated equilibrium and then discloses each player's component of the sample to them while keeping them unaware of the other player's component. While classical cryptographic protocols such as commitment schemes can implement sampling from Nash equilibria, they cannot implement the external signal required in correlated equilibria. In this work, we present two novel approaches to implement the external signal as a smart contract. Our approaches are trustless, do not require any third-parties, provide the desired privacy properties of a correlated equilibrium and are gas-efficient in practice.

Our Contribution. We assume that we have a noncooperative two-player game and a correlated equilibrium σ

of the game and our goal is to provide the external signal as a smart contract so that the players can follow the game's correlated equilibrium. Since our setting is decentralized, using a third-party mediator would not be acceptable. We propose two novel methods for privately sampling strategies from the correlated equilibrium, thereby eliminating the need for reliance on a trusted correlation device and enabling secure execution of the game on blockchain. This will in turn directly allow the protocol designers to apply more general mechanism design techniques, relying on correlated equilibria instead of Nash equilibria. Our solution might be useful in applications beyond blockchains and sampling from any correlated distributions other than correlated equilibria.

Formal Definition of the Problem. Formally, σ is a probability distribution over A1 × A2. Our goal is to sample an outcome (s1, s2) ∈ A1 × A2 according to σ but additionally ensure that player 1 (player 2) can only see s1(s2) while gaining no extra information about s2(s1), beyond what can be deduced from σ.

RNG on the Blockchain. When imperative programs are extended with the ability to access a random source, they form the more expressive class of probabilistic programs [Chatterjee et al., 2019]. In blockchain, the deterministic nature of smart contracts ensures consistent execution from the pointof-view of every node of our decentralized network. Although to ensure consensus in contracts they cannot be nondeterministic, this does not mean that they should also be non-probabilistic. Random number generation, i.e. sampling publicly from a given distribution, is a well-studied problem in the blockchain community [Schindler et al., 2020; Wang and Nixon, 2020; Krasnoselskii et al., 2020; Barakbayeva et al., 2024; Abidha et al., 2024; Fatemi and Goharshady, 2025; Cai and Goharshady, 2023a; Cai and Goharshady, 2023b; Ballweg et al., 2023; Fatemi and Goharshady, 2023b]. In these approaches, several parties contribute to the generation of a single random number, which is then public and subject to consensus. There is also a recent work that targets decentralized generation of secret randomness [Fatemi and Goharshady, 2023a]. In this setting, several players contribute to the generation of a single secret random number r which is then only visible to one participant. However, this participant can later reveal r and prove that it was generated by the protocol with no tampering. Note that our problem does not fit either setting since our RNG is neither public nor private. Instead, each player's component should be visible to only that player.

Secure MPC and Oblivious Transfer. Secure multi-party computation, as introduced in [Yao, 1982], addresses the problem of enabling two or more parties to conduct computations based on their private inputs without disclosing those inputs to one another. Oblivious transfer (OT) protocols are a crucial tool used in secure MPC [Yadav et al., 2022]. OT facilitates a scenario where a sender possesses a set of data elements, and a receiver wishes to obtain a particular element of this dataset. The "oblivious" nature of the protocol ensures that the sender remains unaware of the specific piece of data the receiver selects. At the same time, the latter gains no knowledge of any other data elements.

Zero-knowledge proofs. Zero-knowledge proofs (ZKPs) allow verifying the correctness of a statement without leaking any additional information. ZKPs are widely used in multiparty computation protocols to achieve malicious-security without sacrificing privacy. In another line of research, efforts on efficient verifiable computation led to the development of Succinct Non-interactive ARguments of Knowledge (SNARKs) [Groth, 2016; Ben-Sasson et al., 2018; BenSasson et al., 2019]. Such zk-SNARKs are widely used in blockchain applications to efficiently verify a large number of transactions and are essential to the scalability of decentralized finance [Fernando and Roy, 2023]. In protocol 2, we use zk-SNARKs to reduce the transaction fees of the noncooperative games compared with the protocol 1 when the strategy space is large.

2 Preliminaries

2.1 Game Theory and Correlated Equilibrium

Probability distributions. A probability distribution on a set S = {s1, ..., sn} is a function σ mapping every sj ∈ S to a value between 0 and 1, σ : S → [0, 1]. Moreover, the sum of σ(sj) for every j must be 1. To avoid problems with representations of real numbers, in this work, we assume that all probability distributions of interest have rational values, i.e. σ(sj) is a rational number.

One-shot games. A one-shot non-cooperative game is a game with n players {1, ..., n} where each player i chooses the strategy si simultaneously. Here, the set of possible strategies for player i is denoted as Ai, and the player chooses si from Ai. The set of strategies chosen by the players is s = (s1, ..., sn), and the play of the game using s decides the outcome for each player. To represent the set of all possible strategies the players take, we define A = A1 × · · · ×An. In this work, we focus on two-player games.

Payoffs. For every outcome, there is a specific value that each player is paid. We refer to this as utility or payoff ui, and it is a function ui : A→R. As a result of the game, each player i receives ui(s). Note that each player's payoff depends on all players' chosen strategies. When a distribution σ over A is used to sample strategies for players, the expected payoff of each player i is defined as ui(σ) = Es∼σui(s).

Example for correlated equilibrium. Consider a 2-player game in which both players drive to an intersection and want to cross it. We can construct a payoff matrix. In the matrix, a player crossing the road receives 1, while a player staying and not crossing it gets 0. A car accident happens when both players try to cross the road simultaneously, resulting in a payoff of -100 for both players.

In a correlated equilibrium, a third-party, such as a traffic light, selects the strategies for players 1 and 2 based on a particular distribution on A1 ×A2. The main idea is that every player should follow the recommended strategy, assuming the other player also follows the recommendation. In comparison, in a Nash equilibrium, every player selects a strategy independently from others.

Correlated equilibria. A correlated equilibrium is a probability distribution over a set of strategies s = (s1, . . . , sn) in A1×. . .×An. Every player i receives a pure strategy si ∈ Ai. Consider σ(s) as the probability of choosing strategy set s. Then, the probability distribution corresponding to a correlated equilibrium satisfies the following: for every player i and every swap action δi : Ai → Ai, E(si,s-i)ui(si, s-i) ≥ E(si,s-i)ui(δi(si), s-i). In other words, if a player i gets a strategy si, deviating to any other strategy δi(si) would not increase their expected utility.

2.2 Oblivious Transfer

Oblivious transfer (OT) is a fundamental cryptographic primitive in the area of secure Multi-Party Computation (MPC)[Yadav et al., 2022]. In OT, a sender holds a private list of data x, and a receiver wants to access a particular data entry at index i, i.e. xi. Here, the receiver should not know other data entries xj (j ̸= i) after the transfer, and the sender should not know the index i being accessed. We use OT to achieve data security between participants of the non-cooperative games.

1-out-of-2 OT. The simplest case of OT is 1-out-of-2 OT, where the sender holds only two data entries (x0, x1), such that x0, x1 ∈ {0, 1}l and the receiver has choice bit b ∈ {0, 1}. For example, we present a 1-out-of-2 OT protocol proposed in [Naor and Pinkas, 2001].

Initial Setup. Assume the sender and receiver have access to the following common inputs: security parameter λ, a multiplicative group G, for example a subgroup of Z ∗ p of prime order q with generator g, a random oracle hash function H : {0, 1}∗ → {0, 1}l , and an element c in the group with hidden discrete log, i.e. no one knows logg c.

Round 1. The receiver randomly chooses a number s ∈ {0, 1, . . . , q - 1}. He computes βb = gs and β1-b = c · (gs )-1 , sends β0 to the sender.

Round 2. After receiving β0, the sender randomly chooses a number γ ∈ {0, 1, . . . , q - 1} and computes βγ 1 = cγ /βγ 0 . She encrypts x0 by computing e0 = H(βγ 0 , 0) ⊕ x0, and encrypts x1 by e1 = H(βγ 1 , 1) ⊕ x1, and sends the (e0, e1, gγ ) to the receiver.

Using the values of b and s, the receiver can extract the value xb as H((gγ )s , b) ⊕ eb. The receiver can compute βγ b = (gγ )s but not βγ 1-b = cγ /(gγ )s , bacause he cannot compute cγ from c and gγ assuming hardness of computational Diffie-Hellman (CDH) problem. The sender does not know b because βb and β1-b are both taken randomly from the uniform distribution.

1-out-of-2n OT. The above 1-out-of-2 OT can be naturally extended to 1-out-of-N OT. The receiver generates N public keys PKi (0 ≤ i < N) but only knows the secret key SKb for one of them. The sender encryptes xi using PKi, and the receiver can only decrypt xb using SKb. The communication and computation increase to Θ(N), as well as the size of common inputs. In case the encryption operation in OT is computationally more expensive than other operations such as pseudo-random number generators, [Naor and Pinkas, 1999] propose to achieve 1-out-of-2n OT using n 1out-of-2 OT. The key idea is that only n pairs of keys are required to encrypt/decrypt 2n data entriely differently.

2.3 zk-SNARKs

For a relation R, a Succinct Non-interactive ARgument of Knowledge (SNARK) comprises of 3 algorithms as follows:

• Setup(1λ ,R) → crs. crs is a common reference string.
• Prove(crs, x,w) → π. x is a statement and w is the witness such that R(x, w) holds. It outputs π as proof.
• Verify(crs, x, π) → {0, 1}. On inputs the crs, statement x and proof π, if the proof checks correctly, it outputs 1; otherwise, it outputs 0.

A SNARK is complete, knowledge-sound, and succinct. Completeness means that if R(x,w) holds, an honest prover fails to generate the proof π with probability less than negl(λ). Knowledge soundness means that given a valid proof, there exists an extractor to extract the witness for that statement. Finally, a SNARK is succinct if the proof and verification time are poly-logarithmic in the witness size. This property allows the verifier to check any statement in R faster than checking the statement and witness (if given) directly. If a SNARK is also zero-knowledge, it leaks no information of the witness and is called zk-SNARK. Our second protocol uses the Groth16 SNARK [Groth, 2016].

3 Our First Protocol

In this section, we present our first protocol for sampling from the joint distribution of a correlated equilibrium. We show that the protocol can be implemented on the blockchain as a smart contract and is thus usable for DeFi applications. We call our smart contract SIGNAL and the two players Alice and Bob. Additionally, we assume access to a secret random number generation beacon SRNG, which is also a smart contract as in [Fatemi and Goharshady, 2023a].

Roles. Our contract SIGNAL can support multiple instances of games and equilibria. The roles are the following:

• Alice: player 1 of the game, a blockchain user.
• Bob: player 2 of the game, a blockchain user.
• SIGNAL: a smart contract to facilitate the game. This contract has the role of an external signal.
• SRNG: a smart contract running a secret random beacon service. Alice can generate a private but tamper-proof random number r using SRNG. The oracle is not under Alice's control and no one, including Alice, can tamper with r. Alice can then publish r and publicly verifiable proofs that she has not changed it on the blockchain.

Problem Formulation. Suppose Alice and Bob want to jointly play a game with a correlated equilibrium, which is a distribution σ over strategy profiles A1 ×A2. They want to sample a strategy profile (s1, s2) ∈ A1 ×A2 according to the correlated equilibrium σ. Alice should be able to see s1 but should not gain any information about s2. Conversely, Bob should have access to s2 but gain no information about s1.

Overview of protocol. Our protocol first determines the strategy of Alice by letting Alice query the SRNG for a fresh secret random number r. Then Alice and Bob communicate over the blockchain via SIGNAL to determine the strategy of Bob.

Usage of OT protocol. We use the Naor-Pinkas 1-out-of-N OT protocols in our presentation for its simplicity and efficiency. Nonetheless, it can be replaced by other 1-out-of-N OT protocols.

Participants. Two blockchain users can join the game by calling the join function of SIGNAL to play the roles of Alice and Bob respectively. They both learn the rules of the game and agree with a representation of the correlated equilibrium σ. To prevent Alice and Bob from deviating from the protocol, they should make a deposit as specified by the game. Alice and Bob agree on a source of common input for the oblivious transfer protocols.

3.1 Sampling a strategy for Alice

We first pick an integer N such that ∀(x, y) ∈ A1 × A2, σ(x, y) is a rational number of the form sxy N , where sxy is an integer and

Basically, N is the common denominator of all fractions appearing in our correlated equilibrium σ. Let [N] denote the set {0, 1, . . . ,N - 1}. Then, we can define a function f : [N] →A1×A2 to map each integer n ∈ [N] to a strategy profile (x, y), such that a uniform-distribution over the range [N] maps to the correlated equilibrium σ over strategy profiles. We also define the function f1 : [N] → A1 such that f1(n) = f(n)[1], i.e. f1(n) is the first component of f(n). Then, a uniform distribution over [N] maps to the marginal distribution of σ for Alice under the function f1.

Our protocol starts with Alice querying the secret random beacon oracle SRNG. Alice gets a random number ρ from the oracle and uses r = ρ (mod N) to know her strategy f1(r) = xr.

3.2 Sampling a strategy for Bob

For a fixed choice of xr, Bob's strategy should be drawn from the conditional distribution σxr , assigning to each strategy y the probability

Let Nr be ∑y′ sxry′ . We sample the strategy y of Bob using oblivious transfer between Alice and Bob. Alice knows the distribution σxr for Bob and Bob wants to sample his strategy y from σxr . Alice is not allowed to know the sample y, because otherwise Alice will not follow the correlated equilibrium. Bob is not allowed to know the distribution σxr , because the distribution leaks information about xr, the strategy of Alice. We achieve this using oblivious transfer.

Conditional distribution. The distribution δxr can be represented by a function fr that maps an integer in {0, 1, . . . , Nr -1} to a strategy y in A2. This function can be represented as a list Lr of Nr entries

Alice knows the list Lr and Bob should get a uniformly sampled entry from the list.

Random choice. Alice acts as the sender of OT and Bob is the receiver. From the perspective of Bob, to prevent Alice from knowing the strategy, Bob should use a secret choice number. On the other hand, to make sure Bob samples his strategy randomly, Alice should randomly permute the list Lr to L′r and use L′r in the OT protocol.

Aligning list size. Now Bob chooses a choice number b uniformly from L′r and wants to obtain L′r [b] from Alice using one 1-out-of-Nr OT. However, one more issue remains that Nr leaks information about xr to Bob, when Nr1 ̸= Nr2 for some r1 and r2. Our solution is to compute the least common multiple (LCM) Nm of {N0,N1, . . . ,Nr}. For each r, Alice concatenates Nm/Nr copies of Lr into ˜Lr and then Bob has to choose one element of ˜Lr through OT.

Random Permutation. Alice should also randomly permutes ˜Lr into another array ˜L′r , otherwise Bob might know a lot of information about ˜Lr when Alice has only a few possible strategies. Alice can draw a local random number rp to compute the permutation. As long as rp consists of enough bits (for example 256 bits), Bob can guess ˜L′r [i] for any index i with a negligible probability. Next Alice and Bob run one oblivious transfer with input ˜L′r and v ∈ Sm = {0, 1, . . . , Nm - 1}.

Off-Chain communication. Communication through blockchain transactions (on-chain) can reach consensus among different players due to the consensus layer of blockchain. However, transmitting data using on-chain communication costs significant transaction fees. Alternatively, the players can send large chunks of data off-chain to save the financial cost. Disputes might arise and in such cases they resolve the conflict on chain and punish dishonest behavior.

The main protocol. With a slight abuse of notation, let X be the chosen aligned array X and ˜X denote the permuted array. Let N be the length of ˜X. Assume N = 2n for some integer n, otherwise Alice pads zeros to ˜X. Bob wants to read the v-th element of ˜X, for an integer v ∈ {0, 1 . . . ,N - 1}. The main protocol consists of the following steps:

1. Commit (On-Chain): Alice calls the commit function of SIGNAL to publish the following: (1) cr, a commitment to the secret random number r, (2) c ˜X , a succinct

commitment to the vector ˜X.

1. SendKeys (On-Chain): Bob chooses the n secret keys (s1, . . . , sn) and computes the n pairs of public keys {yj,0, yj,1}nj=1 according to his choice v. Bob calls the smart contract function sendkeys to send n keys: (y1,0, y2,0, . . . , yn,0).
2. SendData (On-Chain and Off-Chain): Upon receiving the public keys from Bob, Alice can choose random numbers (γ1, γ2, . . . , γn) and compute encryptions e = (e0, e1, . . . , eN-1). (1) Alice sends the array e to Bob off-chain. (2) Besides, she sends the n random numbers {γj}nj=1 and a short commitment ce (e.g. a Merkle tree commitment) of e to Bob on-chain by calling the smart contract function senddata.

Disputes arise in two cases: (1) if Alice does not send e to Bob off-chain within a predetermined period, Bob can call the smart contract function resolveSenddata to ask Alice to send e on-chain. Alice and Bob each pay for half of cost of sending e on-chain using their deposit. (2) If Alice sends e that is not consistent with its commitment ce, Bob also calls resolveSenddata and provides a Merkle proof of the inconsistency. Alice is punished if the proof of inconsistency is valid.

Remark. In case N is too large so that Bob cannot afford to pay half of the transaction fee, we allow Bob to call resolveSenddata with a random index i as the argument that asks Alice to send ei on-chain. Bob is strictly incentivized to call this function whenever he has not received the complete e, to avoid getting punished for not proceeding. If he has received e, he is strictly incentivized to not call resolveSenddata function because he shares the transaction fee. On the other hand, if Alice is rational, she will faithfully send the entire e to Bob to avoid paying fees for Bob's challenge.

1. Action: If Bob receives e, he can decrypt his strategy xv. Now that both parties know their own strategies but do not know others, they can take actions in the game, which may be off-chain or on-chain. We assume they know the strategies of each other after taking actions.
2. Reveal (On-Chain): If the protocol terminates now, Bob is not convinced that Alice faithfully sampled her strategy and committed to the correct vector X in the first place. Therefore, after Alice and Bob complete their actions, Alice should publish all the necessary secret in-

• formation to generate r and X. Using a reveal function call, Alice publishes to the smart contract (1) r, the secret random number from SRNG with a publicly verifiable proof πr for its generation, (2) the randomness rp used to generate the permutation. Bob should also reveal v and (s1, . . . , sn) in a reveal function call to show which strategy he received via OT.
• Challenge or Finish (On-Chain): With r and rp, Bob can compute X and ˜X. Using the public keys, Bob can check whether e is computed correctly. If Alice cheated, Bob can call the smart contract function challenge to claim the deposit of Alice. Otherwise, after the challenge period, Alice can call the finish function to claim her deposit.

4 Analysis of Our First Protocol

4.1 Functionality

Functionality. Alice and Bob get an unbiased sample from the correlated equilibrium distribution σ. Alice gets a strategy xr ∈ A1 and Bob gets a strategy yrb ∈ A2. Alice is sure that Bob has made decision on a strategy yrb but knows no more information about yrb than it is drawn from the conditional distribution under σ given that Alice plays strategy xr. Bob's knowledge about Alice is similar. Therefore, they can take their own actions.

4.2 Assumptions

Secret Random Beacon. Our protocol relies on an oracle that produces secret but publicly verifiable random numbers, as in [Fatemi and Goharshady, 2023a]. The secret random beacon directly determines the strategy of Alice. As long as the secret random beacon does not collude with Bob, the strategy of Alice will not be know to Bob. To ensure that Bob cannot corrupt the SRNG, Alice can run the SRNG contract herself.

Rationality Assumption. In our protocol, Alice is disincentivized from violating the protocol (i.e., using arbitrary invalid distribution list ˜L′r ) by losing a deposit afterward when Bob's check fails. Therefore, to use our protocol securely, the users should carefully make sure that the deposit is larger than the incentive of Alice to misbehave. The correctness of our protocol relies on the assumption that Alice is rational. In contrast, Bob is not involved in the sampling of strategy for Alice and cannot manipulate his own strategy due to random permutation by Alice. However, Bob should still reveal his choices of the secret keys (s1, . . . , sn) to show which strategy was sampled via the OT.

4.3 Security

Privacy. Our protocol achieves perfect privacy before finally checking the correctness of Alice's behavior. Firstly, Bob does not know the strategy of Alice, assuming the SRNG is a secret random beacon, which does not collude with Bob. To be exact, from Bob's point-of-view, Alice's strategy xr is sampled from the conditional distribution of σ given yrb. Secondly, Alice does not know the strategy of Bob, based on the security of the Naor-Pinkas 1-out-of-N OT.

4.4 Efficiency

Assuming Rational Players. Firstly, assume that Alice and Bob are rational and follow the protocol honestly.

• On-chain communication. Besides the join function call, 6 functions should be called in each session of the game: commit, sendkeys, senddata, reveal by Alice and by Bob, and finish. The total number of bits is O(n) = O(log(N)), where N is determined by the correlated equilibrium σ and log(N) is roughly proportional to the number of bits to represent σ. In concrete numbers, assuming the oblivious transfer uses the BN254 curve as the group, the total bits of communication include the following: (1) n public keys by Bob, each of 512 bits, (2) n random numbers by Alice, each of 256 bits, (3) n secret keys revealed by Bob, each of 256 bits, (4) cr, c ˜X , ce, r, πr, rp, each of 256 bits (assuming that the oracle proof πr is short).
• Gas Fees. (1) When n is sufficiently small n < 20, each of the 6 transaction consumes the minimum gas 21k. At the gas price of 11gwei per gas unit, 126k gas requires 0.001386 Ether (equivalently $4.3 at the exchange rate of 1 Ether = 3100 USD). (2) When n > 40, the transactions sendkeys, senddata, Bob's reveal together require 2048n gas (0.000022n Ether/$0.0682n), apart from the minimum fees of the other three transactions.
• Total communication. The most costly communication is to send the entire encrypted list to Bob, which requires O(N) bits. Note that off-chain communication is much cheaper than on-chain communication.

Assuming Irrational Players. As argued above, honesty is incentivized in our protocol. However, if a party decides to act irrationally, i.e. not in their own best interest, then the bounds above might change. When Alice is dishonest, she might send a wrong vector ˜X′ = [x0, ..., x0] to force Bob to play strategy x0 chosen by Alice. Bob should resolve the dispute on-chain by computing ˜X on-chain, which incurs Ω(N) transaction fees. Bob might not afford to call the challenge function, which undermines the security against a malicious Alice. Although Alice should pay the transaction fee if the challenge is successful, it requires Alice to put a huge deposit in advance. To address this issue, we will introduce a second protocol in the next section, which uses zk-SNARKs for games with large N. We remark that N is small in all conceivable real-world scenarios. In terms of gas fees, to publish ˜X on-chain, at least 256N bits are sent on-chain. The gas cost is 512N gas (0.0000055n Ether or $0.017N). Note that this is significantly more than the case with rational players since N ≈ 2n .

5 Our Second Protocol

This section presents another protocol for sampling from correlated equilibria, that uses SNARKs to reduce the cost of resolving disputes on-chain.

Setting up the Game. Alice and Bob cannot publish large arrays on-chain. Instead, they publish succinct commitments of these arrays on-chain.

Strategy of Alice. Alice samples her strategy via a random number r from the SRNG. Based on her strategy xr, she chooses one array from the set of aligned arrays that correspond to the conditional distribution of Bob's strategy. Let {Xa}a∈A1 denote the set of aligned arrays, and let X = Xxr denote the selected array. Assume that length of X is |X| = N = 2n . The smart contract has a commitment of {Xa}a∈A1 , as this is part of the description of the game. The rest of the protocol consists of the following steps:

1. Commit (On-Chain): Alice calls the commit function of SIGNAL to publish (1) cr, cX, c ˜X , commitments to the secret random number r, the vector X and ˜X, and (2) a SNARK proof πX showing that X = Xxr , the array X is chosen correctly.
2. SendKeys (On-Chain and Off-Chain): Bob sends y = (y1,0, y2,0, . . . , yn,0) to Alice off-chain, and publishes a commitment cy the smart contract in sendkeys call. Alice and Bob might have a dispute on y since it is transferred off-chain. However, resolving the conflict on-chain only requires O(n) = O(logN) communication, hence the disincentive of cheating is enforced in practice.
3. SendData (On-Chain and Off-Chain): Alice sends γ = (γ1, . . . , γn) and e = (e0, . . . , eN-1) to Bob off-chain. She also publishes the commitments cγ and ce on-chain. Besides, she should also publish on-chain a zk-SNARK proof π for the following relationship (the witness consists of all relevant vectors (X, ˜X, y, γ, e) and secret information r, rp): 1) all commitments are computed correctly, 2) ˜X is a permutation of X, 3) e is the encryption of ˜X under public keys y and random numbers γ. Note that Alice might publish a valid proof on-chain without actually sending e to Bob. However, as explained in the previous section, she is strongly disincentivized to do so, because Bob can call the resolveSenddata function and let Alice share the transaction fee.
4. Check (on-chain): If Bob receives e, he can decrypt his strategy xv. Different from the first protocol, Bob can check the zk-SNARK proof π to verify the validity of e. Bob also checks the zk-SNARK proof πX. If any check fails, Bob calls a requestCheck function to verify the proof π or πX on-chain and confiscates the deposit of Alice. Bob proceeds to take actions only if the SNARK checks pass. This prevents Alice from using a fake X to manipulate Bob's strategy.
5. Action: Same as in the first protocol.
6. Reveal (On-Chain): Same as in the first protocol. After Alice and Bob complete their actions, Alice should call reveal function to publish (1) r, the secret random number from SRNG with a publicly verifiable proof πr for its generation, (2) rp: the randomness for the permutation. Bob calls reveal function to reveal his choice v. Besides he sends the secret keys (s1, . . . , sn) to Alice using off-chain communication.
7. Challenge or Finish (On-Chain): Similar to the first protocol. The only exception is that the challenge only checks r is generated correctly and matches cr, which

does not require expensive transaction fees.

6 Analysis of Our Second Protocol

We implemented SNARK proofs presented in our approach in https://github.com/zhuocai/ Correlated-Equilibrium-Sampling-on-Smart-Contracts.

Efficiency under rationality. If Alice and Bob are rational and therefore honest, the on-chain cost includes 6 transactions: commit, sendkeys, senddata, reveal by Alice and by Bob, finish. The total number of public data on the smart contract consists of the commitments cX, c ˜X , cr, crp , cy, cγ, ce, the SNARK proofs πX and π, and the secret randomness r and rp. In concrete terms, each of the 7 commitments consists of 256 bits. Each Groth16 proof consists of 2 G1 elements and 1 G2 element. Using BN254 curves, each group element consists of 512 bits. Each random number consists of 256 bits. Overall, the on-chain communication is roughly 680 bytes, which requires 11k gas. The overall transaction fees are dominated by the minimum gas of 6 transactions: 126k gas. At the gas price of 11gwei per gas unit, this requires 0.001386 Ether (equivalently $4.3 at the exchange rate of 1 Ether = 3100 USD).

Efficiency under dishonesty. If Alice is dishonest in the sense that X ̸= Xxr , or ˜X is not a permutation of X, or E is not valid encryption of ˜X, the cost to verify it on-chain is bounded by 288k gas, the cost verifying π which has more public inputs compared to πX. The total gas cost increases to 356k gas (0.004554 Ether/$14.12).

Comparison with the Previous Protocol. (1) When both parties are honest, the gas costs of the two protocols are the same because only short messages are sent on-chain. (2) When either is dishonest, the total transaction fee of our first protocol is lower bounded by $(4.3 + 0.017N), while the second protocol takes a constant $14.12. Our second protocol is cheaper in practice when N ≥ 578.

Remark. If we assume both Alice and Bob are rational, then the transaction fee with dishonesty determines the amount of deposit that they should freeze, while the transaction fee under honesty is the actual payment of game players.

7 Conclusion and FutureWork

In this work, we considered the problem of implementing the external signal needed for a correlated equilibrium in a twoplayer non-cooperative game as a smart contract. We provided two novel approaches to achieve this, one based on oblivious transfer and the second using zkSNARKs. Our results enable mechanism designers for blockchain-based protocols to rely on correlated equilibria instead of the much more limited set of Nash equilibria. We implemented our approaches for Ethereum and showed that they are highly gas-efficient and affordable in practice, using merely $12.14 of gas for each sampling of the correlated equilibrium. An important direction of future research is to study noncooperative one-shot games with more than two players.

Acknowledgments

The research was partially supported by the Hong Kong Research Grants Council ECS Project Number 26208122, the HKUST-Kaisa Joint Research Institute Project Grant HKJRI3A-055 and the HKUST Startup Grant R9272. T. Barakbayeva and Z. Cai were supported by the Hong Kong PhD Fellowship Scheme (HKPFS). K. Keypoor was a research intern at HKUST. Authors are ordered alphabetically.