The Distributed Compute Problem
The setup is a trustless, permissionless, two-sided marketplace for compute, where clients can purchase compute services from compute nodes. Trustless means that by default, the protocol does not assume that any particular node behaves in a trustworthy manner and that each node should be considered as rationally self-interested (note that this excludes intentionally malicious behavior). Permissionless means that any node can join or leave the network at will.
Matches for compute jobs are made off-chain, with the resulting deals and results recorded on-chain. Both clients and compute nodes need to agree to matches before they become deals, and make deposits to the protocol to enable rewards and punishments. Results are verified using verification-via-replication, and clients can check the results of any job after it has been completed, but before it needs to pay. It does so by calling upon a mediation protocol. The mediation protocol is the ultimate source of truth, and the outcome of the mediation protocol determines how payouts to nodes are made.
The issue of preventing fake results in the presence of a Trusted Third Party (TTP) as a mediator is effectively a solved problem (for example, see the section on prior verification-via-replication protocols, though there is much more literature on this topic). Given the assumption that the mediation protocol is the source of truth, we can treat the mediation protocol as a TTP. Since the fake results problem is basically already solved in this case, the cheating problem reduces down to solving the collusion problem within the mediation protocol. (Note, however, that we will address both cheating and collusion; the framework described here exists to conceptually simplify the problem.)
This is a typical scenario of a Byzantine environment, and we can use well-established approaches to Byzantine Fault Tolerance when invoking mediation. However, most BFT algorithms and cryptographic methods rely on assumptions regarding some fraction of honest nodes. The problem is that rational, utility-maximizing agents may still collude, even in a mediation consortium, in order to converge on incorrect results. On the one hand, we could assume that some fraction of nodes are honest, as is often done. On the other hand, can we do better?
The task is to find the mechanisms that incentivizes all nodes to behave honestly.
All agents in the protocol are utility-maximizing. This will be elucidated in a subsequent section. Most of the literature has focused on the case where compute nodes are dishonest. However, the client can also behave dishonestly in some manner that maximizes their utility. For example, if the client has some level of control over the choice of mediator, and dishonest nodes have their collateral slashed, the client could collude with the mediator in order to deem a correct result incorrect and get a cut of the honest compute node's collateral.
"Good" solutions can take a number of forms:
Nodes never have an incentive to be dishonest.
Nodes have an incentive to be dishonest that goes to zero as a function of the parameters of the protocol.
(1) or (2), but under some simplifying assumptions, such as there being some fraction of honest nodes within every mediation protocol.
A good solution would achieve any of these goals. Alternatively, another valuable outcome of this research would be to discover under what assumptions these goals can or cannot be met, or if the goals are even possible to achieve at all.
There are a number of ways that these goals may be achieved. The approach will be to construct a digital twin of the protocol and test a number of different mechanisms in simulation. These mechanisms include variations on mediation protocols, collateralization, staking, taxes and jackpots, and others; see the Mechanisms to Explore section for details.
Investigation of some previous verifiacation-by-replication computing protocols
Before explaining our approach, we give a short overview of three prior approaches to verification-via-replication distributed computing protocols: Truebit, Modicum, and Smart Contract Counter-Collusion. We will outline potential improvements, and how our work builds on top of, and differs from, prior work.
Truebit is a protocol for outsourcing computation from blockchains, built using smart contracts on top of Ethereum. The original potential use cases were trustless mining pools, trustless bridges, scaling transaction throughput, and, scalable “on-chain” storage. Since its goal is to scale on-chain computation, it aims for global consensus: "Since there exist no trusted parties on Ethereum’s network, by symmetry we must allow any party to be hired to solve any computational task, and similarly anyone should be able to challenge a Solver’s outcome of a computational task. The latter requirement ensures that TrueBit operates by unanimous consensus." (emphasis added)
The components of Truebit are Miners, Task Givers, Solvers, Verifiers, and Judges. In order to incentivize checking results, random errors are forced into computations, with jackpots awarded to those who find them. These jackpots are funded by taxes on computations.
The verification game consists of a series of rounds, where in each round, a smaller and smaller subset of the computation is checked. Eventually, only one instruction is used to determine whether a Solver or Verifier is correct: "In fact, only one instruction line is used in a verification game. There will be a part of the program code where there is a discrepancy between the Solver and the Verifier. The instruction of that discrepancy point is used to verify who is right."
The authors claim that Sybil attacks are mitigated by pairwise Sybil-resistance between the parties of Task Givers, Solvers, and Verifiers, with Judges and Referees, whose roles are played by Miners, assumed to function as intended. Likewise, they claim that attacks to get bogus solutions on-chain by scaring off Verifiers are mitigated by the economics of deposits, taxes, and jackpot rewards. Additionally, a cartel of Solvers who absorb losses until they find a task with a forced error, upon which time they will receive the jackpot, will lose money in the long-term, since the expected Solver deposit per task is higher than the expected jackpot per task. Addressing another attack, the authors claim that an attack involving a flood of Challengers who try to take as much of the jackpot reward resulting from a forced error as possible is mitigated by having the total jackpot reward decrease as the number of Challengers increases.
Does not scale to large/complicated/arbitrary computations
No formal theorems or proofs, no simulations, many plausible but unsubstantiated claims, especially regarding collusion
Everything is done on-chain
This model does not work well with two-sided marketplaces, because
It aims for global consensus, where any node is allowed to do the computation, whereas in two-sided marketplaces, clients need to be able to choose which nodes they are paying to do the computation
Clients may have time restrictions on their computations, and cannot wait for cases where their computations were injected with forced errors
No accounting for repeated games
Taxes and jackpots are a valuable tool to create a global game that affects local outcomes
Provides a list of potential client attacks
The original version of Modicum had five key components: Job Creators (JC), Resource Providers (RP), Solvers (market makers), Mediators (agreed-upon third parties for mediation), and Directories (file systems, which we have replaced with IPFS and Docker registries). Job Creators are clients, the ones who have computations that need to be done and are willing to pay. Resource Providers are those with computational resources that they are willing to rent out for the right price. Solvers are market-makers; they match the offers from JCs and RPs. Mediators are third parties trusted by both JCs and RPs to arbitrate disagreements. The Directories are network storage services available to both JCs and RPs.
Job Creators are only allowed to submit deterministic jobs to the protocol. The Mediator exists to check for non-deterministic tasks submitted by the Job Creator (which can be used by the Job Creator as an attack vector to get free results), and fake results returned by the Resource Provider. The method for determining whether a job is deterministic or not is for the Mediator to run a job n times and check to see whether it receives different answers.
Modicum combines two separate ideas: checking the result from a Resource Provider to see if it is correct, and checking a result from a job submitted by a Job Creator to see if the job was deterministic or not. This implies that there is no capability for a client to simply check whether a result is correct or not, without the possibility of its collateral being slashed.
An alternative to trusting the Mediator (to act as a TTP) by having it run a job n times is having a consortium of n Mediators each run the task a single time. However, this adds the complication of achieving consensus in that consortium.
The issue of the Resource Provider and Mediator colluding to return a fake result is not addressed by this protocol. The authors allow for a Job Creator or Resource Provider to remove a Mediator from their list of trusted Mediators if they no longer trust it. However, that still leaves room to cheat at least once, and ideally this should be disincentivized from the outset.
There is also the issue of collateralization. The Modicum protocol, as well as a number of other protocols, assume (approximate) guesses as to the cost of jobs in advance, so that nodes can deposit the correct amount of collateral. However, doing so is fraught with complications; we provide an alternative approach in the Mechanisms to Explore section.
The Mediator is basically a trusted third party
Client cannot simply check a result without being slashed, which is a consequence of the client attack model
No accounting for repeated games
Potential client attack, though one that can be mitigated by technical means
The client has benefit of getting correct results, which needs to be accounted for in simulation
Useful prototype for a two-sided marketplace (the follow-up paper for stream processing applications is also useful)
The authors determine that cryptographic methods for verifiable computation are too expensive for real-world scenarios. For that reason, they rely on verification-via-replication. The scenario is one in which a client simultaneously outsources computation to two clouds, where those two clouds deposit collateral into smart contracts in such a way to create a game between them, where the game incentivizes doing the computation honestly. The central challenge that the authors tackle is the issue of collusion - that is, what if the two clouds collude on an incorrect answer?
In contrast to Modicum, the client is assumed to be honest, and in contrast to Truebit, a trusted third part (TTP) is used to handle disputes.
The authors use a series of three contracts to counter collusion.
The first game is an induced Prisoner's Dilemma - to avoid the two clouds colluding, one cloud can be rewarded the other cloud's deposit (minus payment to the TTP for resolving the dispute) if the former returned the correct result and the latter did not. Thus, each cloud is better off giving the other cloud fake results while computing the correct result itself. This contract is called the Prisoner's contract. It is analogous to the equilibrium in the classic prisoner's dilemma being defection <> computing honest result and giving other node fake result if offered to collude.
However, the clouds can agree to collude via a smart contract as well. They could do this by both depositing another amount into a contract, where the leader of the collusion must add a bribe (less than its cost of computing) to the contract as well (disregarding the bribe, both clouds deposit the same amount of collateral). The deposit is such that the clouds have more of an incentive to follow the collusion strategy than to deviate from it. This contract is called the Colluder's contract.
In order to counteract the Colluder's contract, a Traitor's contract is used to avoid this scenario by incentivizing the clouds to report the Colluder's contract. The basic concept is that the traitor cloud indeed reports the agreed-upon collusion result to the client in order to avoid the punishment in the Colluder's contract, but also honestly computes and returns the result to the client in order to avoid the punishment of the Prisoner's contract. The client must also put down a deposit in the Traitor's contract. Only the first cloud to report the Colluder's contract gets rewarded. The signing and reporting of the contracts must happen in a particular order in order for this process to work.
The authors prove that these games individually and together lead to a sequential equilibrium (which is stronger than a Nash equilibrium), meaning that it is optimal not only in terms of the whole game, but at every information set (basically the set of options each player has at every turn).
A Colluder's contract can be signed on different chains (or even off-chain). In order to mitigate this, the Traitor's contracts would have to become cross-chain (which is a major technical challenge), not to mention the possibility of cryptographically secure contracts (e.g. MPC contracts) where one of the parties alone would not be able to prove the existence of this contract
Relies on trusted third party to resolve disputes
Every task is replicated (that is, two copies of each job are always computed)
Assumes client is honest
Assumes amount of collateral known beforehand
No accounting for repeated games
It is well known that in the repeated Prisoner's dilemma, depending on the assumptions, cooperation becomes the equilibrium
The contracts and the payoffs that they induce offer a valuable toolbox to think about the problem of collusion
The contracts offer, in a restricted setting, an ironclad way (assuming the proofs are correct) of preventing collusion
The following is a list of mechanisms that we are currently considering exploring in order to mitigate attacks. Note that some of these mechanisms clearly would not be able to deter cheating and collusion alone. However, in combination with other mechanisms, they may achieve the goals. In this sense, they should be thought of as modules, optionally composable with each other.
Clients call upon a mediation protocol in order to verify the results of a node. There are several variations of the structure of the mediation protocol; the following parameters can be varied:
The number of nodes in the mediation protocol.
If more than two nodes in the mediation consortium, the consensus threshold that determines which result is the one considered to be correct.
How the nodes are chosen.
For example, we may want as a baseline the same constraint as in Modicum - that only mediators that both the client and the compute node mutually trust can be used for mediation.
Even with this baseline, there is still a question of how to choose the node(s) - it can be random, be determined by an auction, or any other method.
Recursive mediation - that is, if there is no consensus in the consortium, do another mediation.
There is a large space of possibilities regarding how to execute this.
There needs to be a limit to the number of nodes this recursive process can use. For example, the set of potential nodes can be the same as the set of mutually trusted mediators, as described above.
Other methods discussed here, such as taxes and jackpots, as well as staking and prediction markets, can be incorporated into the mediation protocol.
There are a number of different types of collateral that need to be included in the protocol.
The client needs to deposit collateral so that the compute node knows that it can be paid. For computations where the cost is known up front, this is simple. However, it becomes complicated for arbitrary compute; the client might not have put up enough collateral initially, so there may have to be a back-and-forth between client and compute node where the latter halts the computation until the former deposits more collateral or simply cancels the computation and pays for the partially computed result. If the client does not pay, then the compute node can invoke a mediation process.
The compute node needs to deposit several types of collateral.
Collateral in case they timeout.
This is put up as part of the deal agreement - that is, when the deal is posted on-chain.
Collateral in case they cheat.
The way that the compute node will convey the amount of collateral they will deposit to indicate that they will not cheat is via a collateral multiplier. The compute node commits to a multiple of whatever they will charge the client ahead of time as part of the deal agreement. The actual collateral is put up after the result is computed and sent to the client. This simplifies immensely the task of determining how much collateral to deposit for arbitrary computations.
Collateral in case they don't do the computation at the rate they said they would. This is closely related to timeout collateral.
Ideally, this is a way of enforcing deadlines on jobs.
It is not necessary to make this collateral slashing binary - for example, a late result can be still be rewarded.
It is enforceable if, for example, the compute node says that they will do X WASM instructions/time. However, technical limitations may make this unrealistic, and it needs to be tested.
One possible way to overcome collusion is to require super high collateral for some particular nodes against each other that that even discount factors very favorable to collusion would not incentivize collusion, even when accounting for repeated games.
While this is not a part of anti-cheating mechanisms, collateral pooling could lower capital requirements for collateralization. High capital requirements are a second-order concern, but will become a higher priority once robust anti-cheating mechanisms are implemented.
Taking inspiration from the taxes and jackpots scheme used in Truebit, deals can be taxed, with those taxes going to a jackpot that is then used to reward nodes via some distribution protocol determined by the mediation process. For this, we want to be able to take any fraction of the jackpot(s) and distribute it arbitrarily to arbitrary nodes (perhaps even those not involved in the mediation process).
This is a particularly interesting approach because the taxation + jackpots mechanism inherently create a global game that impacts local outcomes. While it may lead to potential collusion attacks, the tool alone is very useful, especially in conjunction with some other the other methods mentioned here. Modeling it in simulation would also provide the opportunity to test some of the hypotheses in the Truebit paper.
This method may also be useful in creating a robust platform where some clients do not care to check their results. That is, if some clients do not check results in general, it may be difficult to assert that the network is secure. Taxes and jackpots may be a way to address this.
Prediction markets have been well-studied in a variety of different fields. More recently, a type of prediction market called a replication market has been explored in the context of replicability in science. With this inspiration, it may be possible that allowing nodes to make bets regarding the replicability of the computations of nodes may be useful in mitigating cheating. For example, nodes with a low prediction for replicability may act as a signal for that node's reputation and encourage it to behave honestly.
It is possible to overlay this mechanism on top of taxes, allowing nodes to choose where their taxes go in the prediction market.
Additionally, since Automated Market Makers are closely related to prediction markets, we can leverage many DeFi tools in this context.
Allow users to stake behind nodes. This is similar to prediction markets, but with slightly different economics. Like with prediction markets, it may be possible to tax users and then allow them to choose which nodes they stake behind. Overall, this approach is similar to delegated Proof-of-Stake.
Can a node announcing that it successfully cheated (and thereby receiving a reward) benefit the robustness of the protocol? How much would this node have to be rewarded?
How often should a client check results? Clearly it is related to the amount of collateral that the other node deposits, how much they value getting true/false results, reputation, and so on. This is a parameter that the client would need to learn to maximize its own utility.
The ledger can maintain a record, for each compute node, of the number of jobs the compute node has completed, the number of times its results were checked, and the number of times those results were replicated successfully. All other nodes (client and compute) could locally run some arbitrary function over these numbers to determine how reputable they find that node.
Results can only be replicated for as long as the inputs are stored somewhere. The client, compute node, or some other entity can pay for storing the inputs/outputs of jobs. The longer they are stored, the more time there is to check the results, which affects things like collateralization, the frequency of checks, etc.
This is related to, but not totally overlapping with, the amount of time that a node might have to wait before getting paid, which is the same time interval that a client has to check a result. However, checking the result after the node gets paid and receives back its collateral may still be possible, with other penalty schemes (or reward schemes, for example, coming from jackpots).
Colluding requires the following knowledge in order to enforce the parameters of the collusion.
The public keys of the nodes participating in collusion.
The results that were posted by those public keys.
The payouts to the public keys.
In order to sign a collusion contract to begin with, the public keys must be known. However, in a mediation protocol with enough nodes, it may be possible to obscure (2) and (3) by
Having nodes submit results to the mediation protocol in an obscured/anonymous way
Have nodes be paid out according to the results of the mediation protocol in an obscured/anonymous way
If these two criteria can be met, then a mediation protocol based on them might be capable of imitating the game-theoretic outcomes seen in the Smart Contract Counter-Collusion paper.
There have been many decades of cryptography and security research focusing on similar problems to these. It may be the case that it is already possible to do this; otherwise, there is a large amount of ongoing research on the topics of privacy-preserving transactions, and much prior work in the flavor of secret-sharing/MPC/Tor/Monero/ZKPs that could enable this.
Our Approach
A core assumption in much of game theory is that agents are utility-maximizing. That is, agents are completely rational actors, and are able to execute exactly the behavior that maximizes their return, however "return" is defined in the given context.
However, we know that in real life, humans are not completely rational, and are not capable of perfect execution of actions. In that light, how can we look at the game-theoretic approaches in the last section?
Either we can try to account for the irrational behavior of humans, or we can try to emulate the behavior of utility-maximizing agents. While there is a large amount of game-theoretic literature dedicated to the former, we opt for the latter for reasons that will become clear below.
While this problem setting - verifiable computation by way of game theory - is different than many game theoretic settings, we can draw inspiration from commonly used concepts like the revelation principle and strategyproofness. Both strategyproofness and the revelation principle are centered around the idea of incentivizing agents to truthfully report their preferences. Most approaches in the literature rely on analytic methods to determine what rational agents will do by analyzing their payoffs as a function of their preferences, the behaviors of other agents, and the mechanism under analysis. Ultimately, we are also aiming to find (a) mechanism(s) that lead(s) to an equilibrium where all agents choose to not cheat and not collude.
Note that the actual environment of a two-sided marketplace for distributed computation is extremely complicated (e.g. the heterogeneity of hardware, types of computation, latencies and bandwidths, etc.). Any theoretical/analytic approach to the problem that is actually correct should also work in simulation, so we opt for a simulation-driven approach.
The way that we can emulate perfectly rational behavior is by training autonomous agents to act on behalf of their human owners in a utility-maximizing manner. At that point, the challenge is to design the global game to drive the probability of cheating to zero - ideally, to make it be equal to zero - which is no small feat in a trustless and permissionless environment. However, the simplifying assumption that we are in fact operating with utility-maximizing agents conceptually simplifies the problem immensely.
The process begins by creating a digital twin of a two-sided marketplace. In this environment, autonomous agents acting on behalf of client and compute nodes will be trained to maximize returns based on data gathered in simulation. For now, we will avoid maximizing returns by optimizing scheduling, though this is a future topic of interest. We will use techniques primarily from the field of multi-agent reinforcement learning in order to train the agents. The precise methods we will use (e.g. modes of training and execution, homogeneous vs. heterogeneous agents, choice of equilibrium, self-play vs. mixed-play, value-based vs. policy-based learning, etc.) will be determined in the course of building the simulation. See the pre-print by Albrecht, Christianos, and Schäfer for our reference text.
At a minimum, the action space for an autonomous agent representing a compute node should be to cheat or not to cheat, and to collude or not collude within a mediation protocol. The observable environment for nodes on the network should include all data stored on the blockchain - that is, the sequence of deals, results, and mediations - as well as the information in the orderbook. While the orderbook will be off-chain, we model in the digital twin the orderbook acting as a centralized, single source of truth that all agents have access to. In the long-term, nodes will have (potentially non-identical) local information regarding other job and resource offers on the network.
Further work may explore agents forming beliefs about the hardware and strategies of other agents, but that is beyond the scope of the current work.
We conclude with two "axioms" upon which we will base our simulations:
Every agent attempts to maximize its utility, including cheating and/or colluding if necessary.
All other components of the game should lead to a "good" solution, as defined in the problem statement.
Verifiable computing is dedicated to ensuring that outsourced computations (that is, computations that are not done locally) are done correctly. In some scenarios, it cannot be assumed that the node to which a job is being outsourced will compute the result honestly, or that it is not faulty. Moreover, verifying the result should have less overhead than computing the result in the first place.
While blockchains provide safety and liveness, the massive replication of computation becomes too costly when that level of security is not needed. There is a difference between global consensus, which is necessary in blockchain environments, and local consensus, which is more suited for two-sided marketplaces. In global consensus, all nodes need to be convinced that every computation was done correctly. In contrast, in local consensus, only a small number of nodes - potentially only one node, the client - needs to be convinced that a computation was done correctly.
Ostensibly, for a two-sided marketplace, this implies that only a client really needs to be convinced that a computation was done correctly. However, these computations are not done in isolation, and the interrelation between a client choosing one node repeatedly versus many different nodes, and the mathematics behind those decisions, as well as the need to create a protocol that any client can come along to with no prior experience and trust that cheating is disincentivized, implies the creation of a global game that, while not requiring global consensus in the traditional sense, emulates it in some manner.
One way to ensure that computations were done correctly is by using cryptographic methods. There are a number of cryptographic approaches for verifiable computation, including
Interactive Proof (IP)
In interactive proofs, verification of a statement is modeled as an interaction between a prover and a verifier. The goal of the prover is to convince the verifier that the statement is true, even when the verifier does not have the computation resources to do the computation itself.
The protocol must satisfy completeness (if the statement is true, an honest verifier will be convinced) and soundness (if the statement is false, the prover cannot convince the verifier except with some negligible probability).
Zero-Knowledge Proof (ZKP)
Zero-knowledge proofs are a type of interactive proof where the verifier learns nothing about private inputs of the computation, other than that the outputs were computed correctly from the all the inputs (some of which may be public/known to the verifier).
A ZKP can be made non-interactive, in which case it is called a Non-Interactive Zero-Knowledge Proof (NIZK). Two common variants of NIZKs are zk-SNARKs (zero-knowledge Succinct Non-interactive Argument of Knowledge) and zk-STARKs (zero-knowledge Scalable Transparent Argument of Knowledge).
Like IPs, ZKPs must also satisfy the requirements of completeness and soundness.
Multi-Party Computation (MPC)
Multi-party computation allows multiple parties to jointly compute a function over their individual inputs without any party revealing its input to other parties. The main objectives of MPC are privacy (parties should learn known about each others' inputs), security (some level of anti-collusion preventing malicious attempts to learn information), functionality (the ability to compute functions over data), and robustness (the protocol should work correctly even in the presence of malicious behavior or faults).
Trusted Execution Environments are secure and isolated enclaves, where code and data inside of the enclave are insulated from the rest of the system, including the operating system, applications, and other enclaves. The goal is to maintain both the confidentiality and the integrity of the code and data.
Verification-via-replication - often described using the adjective "optimistic" in the blockchain world - relies on recomputing the computation to check whether the end result is the same. The benefits of this method are that it is the easiest to understand, and in some sense, the easiest to implement.
In contrast to the other approaches, verification-via-replication often requires reliance on game-theoretic mechanisms such as collateral slashing, reputation, and other methods. This can become a bit complex when trying to counter collusion between the nodes that are computing the results.
One of the downsides of this approach is, of course, the extra effort expended on recomputing computations. However, with proper incentives, the overhead of this can be reduced dramatically. It is also important to keep in mind that the overhead of this approach is much lower than cryptographic methods, which usually have much higher overhead.
We opt for verification-via-replication as a first approach, for the reasons that it is simple to understand, has less overhead than cryptographic approaches, and has an attack surface that can be economically modelled and analyzed.
This has the downside of making private computations difficult. While the inputs and outputs of jobs can be encrypted so that only the client and compute node can see the code and data, this still leaves the client vulnerable to having their information leaked. Future approaches can incorporate SLAs and eventually support for homomorphic encryption to deal with this issue.
These documents provide a background for ongoing Lilypad research.
If you have questions or find something in here interesting, please feel free to raise a discussion in the GitHub or in the Lilypad Discord server!
These documents provide a background for the ongoing research on Lilypad. They are primarily focused on the game theory and cryptoeconomics of the protocol, and include an introduction to verifiable computing, an overview of the specific problems we are tackling, a brief overview of prior work, a description of our approach, and mechanisms that we plan to test in simulation.