PaperlayerView exact revision on arXiv

Source-linked AI summary

Betrayal, Distrust, and Rationality: Smart Counter-Collusion Contracts for Verifiable Cloud Computing

Changyu Dong, Yilei Wang, Amjad Aldweesh, Patrick McCorry, Aad van Moorsel

arXiv:1708.01171v4cs.CR

TL;DR

The paper addresses how to provide verifiable outsourced cloud computation without the high cost of existing verification methods. It uses two-cloud replication and smart-contract games to deter rational collusion, proving effectiveness under stated assumptions and reporting low additional contract cost. The main practical boundary is that the model assumes an honest client and leaves repeated interactions and deposit efficiency for future work.

  • Problem

    Existing verifiable-computation techniques impose high overhead, while clients need strong correctness guarantees at a cost comparable to on-premises computation.

  • Method

    The client sends the same task to two clouds and uses Prisoner’s, Colluder’s, and Traitor’s smart contracts to manipulate incentives against collusion.

  • Results

    The contracts make honest, non-colluding behavior the unique sequential equilibrium for rational clouds under the paper’s assumptions, enabling verification by cross-checking results.

  • Takeaways & Limitations

    The approach achieves verifiability with two cloud computations and small additional transaction and cryptographic costs instead of heavy cryptographic protocols.

  • Takeaways & Limitations

    The model assumes an honest client and leaves repeated interactions and the efficiency of the deposit mechanism for future work.

Abstract

from arXiv · show

Cloud computing has become an irreversible trend. Together comes the pressing need for verifiability, to assure the client the correctness of computation outsourced to the cloud. Existing verifiable computation techniques all have a high overhead, thus if being deployed in the clouds, would render cloud computing more expensive than the on-premises counterpart. To achieve verifiability at a reasonable cost, we leverage game theory and propose a smart contract based solution. In a nutshell, a client lets two clouds compute the same task, and uses smart contracts to stimulate tension, betrayal and distrust between the clouds, so that rational clouds will not collude and cheat. In the absence of collusion, verification of correctness can be done easily by crosschecking the results from the two clouds. We provide a formal analysis of the games induced by the contracts, and prove that the contracts will be effective under certain reasonable assumptions. By resorting to game theory and smart contracts, we are able to avoid heavy cryptographic protocols. The client only needs to pay two clouds to compute in the clear, and a small transaction fee to use the smart contracts. We also conducted a feasibility study that involves implementing the contracts in Solidity and running them on the official Ethereum network.

1 INTRODUCTION

The paper seeks low-cost verifiable cloud computing by replicating computation across two clouds and using smart contracts to prevent rational clouds from colluding. It formalizes contract-induced games and reports that verification then requires cross-checking results, with two-cloud computation as the main cost.

  • Existing Approaches: Existing cryptographic approaches impose high overhead, while replication commonly requires at least three clouds and can at least triple client costs.One cited protocol using two replicas still introduces overhead of about 10–20 times the computation being verified.
  • Problem Statement: Verifiable cloud computing must provide strong correctness guarantees without costing more than on-premises computation.The paper targets a replication-based design using no more than two replicas.
  • Approach: The proposed solution outsources the same task to two clouds and cross-checks their results when they do not collude.This uses replication while limiting the client to two cloud computations.
  • Approach: Smart contracts use deposits, rewards, and betrayal incentives to make collusion less favorable and encourage correct computation.Deposits penalize incorrect results, rewards are transferred to honest clouds, and betrayal incentives create distrust between potential colluders.
  • Game-Theoretic Design: The Prisoner’s and Traitor’s contracts are designed so rational clouds honestly compute and avoid collusion under moderate assumptions.The paper formally analyzes the induced games and identifies honest non-collusion as the unique sequential equilibrium for the two clouds.
  • Cost and Feasibility: The main cost is employing two clouds, while contract use adds only a small transaction fee and light cryptographic overhead.The design assumes an offline trusted third party for disputes, whose cost is assigned to the faulty cloud if invoked.

2 PRELIMINARIES

The preliminaries introduce extensive-form games with imperfect information, behavior strategies, beliefs, and sequential equilibrium, then summarize blockchain and smart-contract foundations. These concepts provide the formal language for analyzing the contracts.

  • Games and Strategies: An extensive-form game represents players, actions, decision nodes, terminal outcomes, information, and payoffs in a game tree.Imperfect information allows players not to know all actions previously taken by others.
  • Games and Strategies: Information sets capture uncertainty about the current node, such as a player’s inability to distinguish whether an earlier move was M or R.The example game illustrates this uncertainty through nodes v2 and v3.
  • Games and Strategies: Behavior strategies assign independent action probabilities at each information set, and strategy profiles collect the players’ strategies.The paper treats behavior strategies as equivalent to mixed strategies in its setting.
  • Equilibrium Concepts: A belief system assigns probabilities to nodes within each information set, supporting decisions under imperfect information.Expected payoffs are weighted by both play probabilities and beliefs over possible nodes.
  • Equilibrium Concepts: Sequential equilibrium combines sequential rationality with consistency between strategies and beliefs.Consistency requires beliefs to arise as limits of completely mixed strategy profiles using Bayes’ rule.
  • Cryptocurrencies and Smart Contracts: Cryptocurrency blockchains maintain public ledgers through peer consensus, while Ethereum supports programmable smart contracts written in languages such as Solidity.Contract behavior is determined by executed code and transactions invoke contract functions with arguments.

3 ADVERSARY MODEL AND ASSUMPTIONS

The model considers integrity rather than confidentiality, with an honest client outsourcing deterministic computation to two physically isolated, rational clouds. It assumes smart contracts, cryptocurrency infrastructure, and an offline trusted third party are available to enforce outcomes and resolve disputes.

  • Adversary Model: The paper models each cloud as an individual rational adversary that maximizes payoff rather than acting arbitrarily.Clouds may return wrong results, and the model does not distinguish intentional from unintentional faults.
  • Scope: The analysis addresses computation integrity but not confidentiality and assumes the client is honest.The client seeks the correct result while minimizing cost.
  • Adversary Model: Cheating is assumed to reduce computation cost, and a plausible incorrect answer may be selected at no cost to derive conservative deposit bounds.The paper notes that selecting such an answer would not actually be free in reality.
  • Infrastructure Assumptions: The model assumes secure smart-contract platforms with stable-valued cryptocurrencies accepted by all parties throughout the contract lifetime.Smart contracts are assumed to execute faithfully.
  • Dispute Resolution: An offline trusted third party can recompute tasks and resolve disputes, but rational clouds are assumed never to trigger it.Its existence provides deterrence even when it takes no action.
  • Task Assumptions: Tasks must be deterministic or reducible to deterministic computation, have a low probability of correct-result guessing, and not be time-critical.The design relies on the smart-contract network to enforce the contracts.

4 MONETARY VARIABLES

The contract model defines monetary variables for bribes, computation, dispute resolution, deposits, and related payments. It imposes inequalities that constrain these amounts so the intended incentives can operate.

  • Variables: The monetary variables include the collusion bribe b, computation cost c, and dispute-resolution fee ch.The client sets d in the Prisoner’s contract, while the clouds can set b and t in the Colluder’s contract.
  • Constraints: The contract parameters satisfy d > c + ch, b < c, and t > z + d −b.All monetary variables are non-negative.

5 THE PRISONER’S CONTRACT

The Prisoner’s contract uses deposits, penalties, rewards, and dispute resolution to make honest computation attractive when two clouds independently compute the same task. Under d > c + ch, its unique sequential equilibrium has both clouds send f(x), making the honest result the only reachable outcome.

  • Contract design: The contract pays each cloud w for correct, timely computation and requires each to deposit d before receiving the task.Deposits are refunded when both results match; cheating deposits can be taken after trusted-party verification.
  • Contract design: When results disagree or are incomplete, the client invokes the TTP, which recomputes f(x) and identifies cheating by comparing submitted results.The TTP’s decision determines whether deposits are refunded, forfeited, or transferred as a bonus to the honest cloud.
  • Contract design: Deadlines T1 < T2 < T3 enforce timely actions and prevent funds from remaining permanently locked in the smart contract.The contract specifies refunds or transfers after deadlines when parties fail to proceed.
  • Game and analysis: If d > c + ch, both rational clouds send f(x) with probability 1 in the unique sequential equilibrium.The game therefore always terminates at v4, where both clouds choose the honest computation result.
  • Game and analysis: At C2’s decision points, sending f(x) yields a higher payoff than sending r or taking another action, and C1 consequently also chooses f(x).The equilibrium follows by backward reasoning: C2 never selects the cheating branches, so C1 selects the outcome with payoff w − c rather than −d.

6 THE COLLUDER’S CONTRACT

The Colluder’s contract lets two clouds make collusion credible by combining a bribe with deposits that punish deviation. Under explicit inequalities on d, b, and t, rational clouds initiate collusion, send the agreed false result r, and reach the collusive equilibrium.

  • Game and analysis: The Colluder’s contract changes the Prisoner’s-contract game by making enforceable promises possible between the clouds.Without such promises, the Prisoner’s contract creates a dilemma; with them, collusion becomes the equilibrium outcome under the stated conditions.
  • Contract design: The contract defines a ringleader and follower who agree to send r and deposit t, while the ringleader additionally pays the follower a bribe b.The deposits are held by the smart contract and must be paid before the Prisoner’s-contract deadline.
  • Contract design: Deviation is penalized through deposit transfers: a deviating party loses its deposit, while specified outcomes pay the compliant party more.The contract distinguishes cases where both parties follow, one deviates, or both deviate from collusion.
  • Conditions: The Colluder’s contract is effective only when b < c and t > z + d − b, alongside d > c + ch.The bribe must be below computation cost, while the collusion deposit must make deviation unattractive and compliance preferable.
  • Game and analysis: Under these conditions, the unique sequential equilibrium has the ringleader initiate collusion and both clouds send r.Theorem 6.2 states that the resulting game always terminates at v10 when C1 and C2 are rational.

7 THE TRAITOR’S CONTRACT

The Traitor’s contract addresses collusion by rewarding the first cloud that reports it, rather than by escalating counter-contracts. Under the paper’s conditions, rational clouds avoid initiating collusion, and the analyzed games reach the honest-computation outcome.

  • Contract design: This reporting mechanism avoids an endless counter-contract loop because, after a report, each cloud’s payoff depends on whether it cheated rather than on the other cloud’s behavior.The contract therefore changes the strategic target from deterring deviation to incentivizing disclosure.
  • Contract design: The Traitor’s contract offers the first reporting cloud immunity from the Prisoner’s-contract penalty and compensates its loss in suitable cases.The client signs with only the first reporter, and the trusted third party determines which cloud cheated.
  • Contract procedure: The contract’s deposit and payment rules compensate the reporter and impose outcomes based on whether either cloud cheated and whether the reporter delivered a correct result.The client funds the contract with w + 2 · d − ch, and the reporter may need to deliver r in the Prisoner’s contract and f(x) in the Traitor’s contract.
  • Contract procedure: The reporting cloud must follow a prescribed sequence: wait for the collusion contract, report before signing it, then sign only after the Traitor’s contract is established.It may submit evidence such as the collusion contract address and agreed value r.
  • Sub-game and analysis: In the subgame without an effective Colluder’s contract, rational clouds do not falsely report and instead send the correct result in the Prisoner’s contract.If d > c + ch, Game 3 has a unique sequential equilibrium and always terminates at v13.
  • Full game and analysis: In the full three-contract game, if d > c + ch, b < c, and t > z + d − b, the ringleader does not initiate collusion because the follower can pretend to collude and report.Theorem 7.4 states that Game 4 consequently terminates at v13 in Game 3.

8 IMPLEMENTATION

The implementation addresses blockchain privacy and verifiability with commitments and NIZKs, then evaluates cryptographic overhead and Ethereum execution costs. The contracts require only small cryptographic overhead, while execution costs are low in the reported deployment.

  • Protocol use: The contracts replace plaintext values with commitments and require parties to run cryptographic protocols when submitting computation results.For the Prisoner’s contract, the client commits to hashes of the function and input, while each cloud commits to the hash of its result.
  • Cryptographic primitives: Commitments hide computation inputs and outputs on the blockchain, while NIZKs let peers verify equality or inequality without learning the concealed values.The implementation uses a collision-resistant hash function, Pedersen commitments, and NIZKs derived with the Fiat–Shamir heuristic.
  • Overhead: Each contract requires at most 2 commitments and 2 NIZKs, with local generation and blockchain-side NIZK verification.With 256-bit ECC, commitments are 512 bits, equality NIZKs are 768 bits, and inequality NIZKs are 1536 bits.
  • Financial cost: 3.8 million gas ($0.65) is the reported total cost for the Prisoner’s contract when no dispute occurs.The cost includes the client and two clouds; dispute-related functions are more expensive because they verify NIZKs.
  • Financial cost: Ethereum’s reported contract cost is low, and native ECC support was expected to reduce costs for ECC-heavy functions such as Dispute.The experiment was conducted on the official Ethereum network, and the Init transaction costs the most because blockchain storage is expensive.

9 RELATED WORK

Prior verifiable-computation work uses cryptography or replication, but both approaches create cost or assumption challenges. The paper positions its two-cloud design as a way to retain replication-based verifiability while addressing collusion with contracts.

  • Verifiable computation: Cryptography-based verification can provide high-assurance execution, but proof generation and pre-computation may cost orders of magnitude more than the computation verified.Replication instead runs the task on multiple servers and relies on enough honest servers for consensus-based correctness.
  • Replication: Traditional replication counters collusion by increasing the number of servers, an option unavailable when the system must be limited to two servers.A two-server protocol exists, but it assumes at least one server is honest and therefore excludes the possibility that both collude.
  • Blockchain mechanisms: Related blockchain mechanisms use deposits to penalize parties who withhold results, while other work combines bounties with cryptography-based correctness proofs.These approaches address fairness, timely delivery, or answer submission rather than the paper’s specific counter-collusion game.

10 CONCLUSION AND FUTURE WORK

The paper combines two-cloud replication with smart-contract games that seek to prevent collusion, allowing correctness checking by crosschecking returned results. It reports low additional costs but leaves important assumptions and deployment issues for future work.

  • Conclusion: Smart contracts create games intended to restrain two rational clouds from colluding and cutting corners, so the client can crosscheck their results.The main cost is employing two clouds; the paper states that other costs are small.
  • Future work: The analysis assumes an honest client, while treating client adversaries and repeated interactions as future extensions requiring substantial contract changes.Repeated interactions may make reputation and long-term profitability affect incentives.
  • Future work: The current deposit mechanism can require large cash reserves from clouds serving many clients and simultaneous contracts.The paper suggests pooling contracts or insurance as possible directions for more efficient deposits.
  • Future work: The authors seek standard, verified, composable contract templates and broader counter-collusion contracts for applications such as preventing vote buying.The current contracts are written case-by-case.

A SAVING ON TCO

This appendix describes the configurations used to estimate three-year infrastructure ownership costs and compares small, median, and large deployments. The supplied passages define the compared scales but do not report the table’s numerical values.

  • Cost methodology: The TCO calculation uses Amazon AWS’s calculator with US-east, VMware, Linux, specified VM utilization, SAN storage, and a 1000 Mbit/s data-center network.The calculation was performed on May 3, 2017 using default assumptions and the listed configurations.
  • Compared deployments: The comparison covers small, median, and large infrastructures with 10, 100, and 1000 servers, respectively.The corresponding storage capacities are 10 TB, 100 TB, and 1,000 TB.
  • Compared deployments: Table 3 is a three-year TCO comparison across the defined infrastructure sizes.The supplied table reference identifies the comparison but does not provide its numeric results.

B.1 Analysis of Game 1

Game 1 is analyzed through sequential rationality and consistency. Under the stated payoff conditions, both parties’ equilibrium behavior is uniquely determined and reaches v4 with probability 1.

  • Sequential rationality: C2’s expected payoff is maximized by playing f (x) with probability 1 when d > c + ch.The payoff ordering supports this choice at each relevant node.
  • Sequential rationality: C1’s expected payoff is maximized by choosing f (x), because u1(v4) > u1(v7) = u1(v10).This makes the strategy profile sequentially rational at C1’s information set.
  • Equilibrium result: The equilibrium is sequentially rational because each party’s strategy maximizes expected payoff at every information set.The analysis states that both parties have strictly dominant strategies.
  • Equilibrium result: The unique sequential equilibrium has both parties play f (x) with probability 1, yielding Pr[v4|Ep] = 1.The probability is computed as the product of three probability-1 transitions.

C.1 Analysis of Game 2

Game 2’s backward-induction analysis determines the parties’ optimal actions across the collusion game. The resulting assessment is sequentially rational, consistent, and the only sequential equilibrium.

  • Backward-induction analysis: FLR must choose r with probability 1 at I2,2 because this maximizes its expected payoff regardless of LDR’s strategy.The result follows from the payoff comparisons under the stated parameter conditions.
  • Backward-induction analysis: LDR must choose r with probability 1 at I1,2 because r yields a higher payoff than the alternative actions under the stated condition.The analysis uses t > z + d − b and w > c > b to establish the payoff ordering.
  • Backward-induction analysis: FLR must choose collude with probability 1 at I2,1 because u2(v10) = w + b exceeds u2(Game 1) = w − c.Thus collusion is preferred at this information set in the analyzed game.
  • Backward-induction analysis: LDR must initiate with probability 1 at I1,1 because u1(v10) = w − b exceeds u1(Game 1) = w − c when b < c.The equilibrium path therefore begins with initiation and proceeds through collusion and r choices.
  • Equilibrium characterization: The assessment is sequentially rational because it maximizes each party’s expected payoff at every information set.The stated strategy and belief system are summarized explicitly in the equilibrium assessment.
  • Equilibrium characterization: The assessment is consistent and is the only sequential equilibrium of the game.Consistency is established by a fully mixed sequence converging to the strategy and belief system.

C.2 Analysis of Game 3

Game 3 is analyzed by backward induction over players’ information sets and beliefs. Under the stated payoff conditions, the sequential-equilibrium strategies select specific actions that maximize each player’s expected payoff.

  • Sequential-equilibrium analysis: The analysis computes players’ expected payoffs at each information set using beliefs over possible game-tree nodes.The strategy profile and belief system assign probabilities to actions and information-set nodes before payoffs are maximized.
  • TRA’s choices: When d > c + ch, TRA chooses ψ4 = 1, ψ5 = 0, ψ6 = 0 at information set I2.These probabilities maximize TRA’s expected payoff under the stated payoff comparisons.
  • TRA’s choices: When d > c + ch and ϕ1 > 0, TRA chooses ψ7 = 1, ψ8 = 0, ψ9 = 0 at information set I2,3.If ϕ1 = 0, any probabilities summing to one maximize the expected payoff at that information set.
  • TRA’s choices: When d > c + ch, TRA chooses ψ10 = 1, ψ11 = 0, ψ12 = 0 at information set I2,4.The selected action maximizes the expected payoff at each node in that information set.
  • OTH’s choice: OTH chooses ϕ1 = 1, ϕ2 = 0, ϕ3 = 0 at information set I1 to maximize its expected payoff.The analysis compares the payoffs from the relevant branches, including the case where ϕ1 = 0.
  • Equilibrium outcome: TRA chooses ψ1 = 1, ψ2 = 0, ψ3 = 0 at information set I2,1 because u2(v13) exceeds the alternative payoffs.This is the final backward-induction choice reported for TRA in the analysis.
  • Equilibrium outcome: The game has one sequential equilibrium in which both parties play f (x) with probability 1, giving Pr[v13 | Ec] = 1.The reported path probability is 1 · 1 · 1 · 1 = 1.

F MORE ON THE EXPERIMENT

The experiment deployed and exercised the Solidity contracts on the official Ethereum network. The results identify contract initialization as the dominant transaction cost and show that resetting a contract is much cheaper than deploying a new one.

  • Deployment: The experiment ran the contracts on the official Ethereum network and recorded contract and transaction addresses.The implementation included Prisoner’s, Colluder’s, and Traitor’s contracts.
  • Testing: The contracts were tested through multiple executions with different parameters, with one representative transaction recorded for each function.Variations in gas consumption across executions were described as small.
  • Transaction costs: Initialization costs the most among contract transactions because storing data on the blockchain is expensive.The contracts can be reused for sequences of outsourced computation tasks, although reuse reduces anonymity.
  • Contract reuse: Resetting a Prisoner’s contract costs about 56 thousand gas ($0.01), versus about 2.3 million gas ($0.40) to set up a new contract.The reset function cleans the data and returns the contract to its initial state.
  • Signing messages: Message-signing alone would deter cheating only if the clouds do not collude and public exposure causes unavoidable damage.Under those assumptions, signatures provide evidence that can damage a dishonest cloud’s reputation.
  • Scope: The counter-collusion contracts target cases where collusion remains possible; when clouds prefer not to collude, simpler solutions may suffice.The paper identifies this as a scope boundary for when its contracts are necessary.
Loading 1708.01171v4…