Labor: a proposal for a decentralized oracle

In a previous post I described what I believe to be main obstacles to a game-theoretically sound decentralized oracle. Here I propose a design for one. If you want to skip my slow introduction to the mechanism and just see the proposal, scroll down to the “In the nutshell” section.

Before I dove into the world of DApps this summer, it always puzzled me why no one has implemented a robust decentralized oracle using schelling point games. It’s not until you sit down and try to work out the details that the fundamental challanges become apparent. First, one has to account for potentially wealthy adversaries trying to alter oracle’s output, and somehow guard against them without ratcheting up the fees. Then, another important problem is to avoid hard-coding rewards and instead allow free-market mechanics to shape appropriate prices for tasks. Both of these objectives are crucial to most applications, yet satisfying both at the same time is challenging if not impossible.

The oracle mechanism I present, Labor, was designed with the goal of approximating both adversary-resilience and free-market mechanics. It also employs a frugal scheme for dynamically matching workers and tasks that might be useful in other decentralized applications. More precisely, here’ s the spec for a decentralized oracle I have in mind:

• cheap adversary-resilience: subverting a given task requires significantly more capital than task’s reward
• free market: agents get some say in which tasks to process, task givers are incentivized to set competitive rewards, as mispriced tasks end up being thrown out
• Working for the oracle yields predictable revenue. Workers are unlikely to participate in complex games with unpredictable payoffs.
• No incentives to perform sybil attacks/pool with others, unless the agent’s or pool’s capital is comparable to the total market cap of the oracle
• creator of the task has control over cost/security trade-off. Some tasks have higher underlying stakes, and it make sense to spend more money on ensuring their integrity
• all free parameters are transparent trade-offs between efficiency, security and usability.

The proposal I have in mind is somewhat complex, although practically it can be implemented rather frugally (both in terms of gas costs and solidity code volume). I think a good way to present it is to start with something simple and introduce modifications together with their rationale until we arrive at a design that has a fighting chance in satisfying the spec I outlined above.

Naive random matching

This mechanism mimics the recent proposal by Julia Koch and Christian Reitwießner

1) Workers stake eth signaling their willingness to perform a task
2) A task-giver submits a question and reward deposit.
3) n workers are matched randomly to the task (with match probabilities weighted in proportion to stakes)
4) elected workers submit their concealed votes
5) once all votes are in, or a certain time has expired, task enters reveal stage
6) workers reveal their votes, task’s result is set to the most popular vote value, everyone who has voted for the winning value splits the reward

What happens when an elected worker fails to submit a vote? One question is whether to punish them (TrueBit rather harshly suggests to burn the entire stake of the participant), but let’s put this issue off for now. The second question is whether we should proceed and tally up the votes with the remaining players, or first recruit a new vote by replacing the slacker with another worker?

• If we just fire the slacker and proceed to tally up the votes, task-giver ends up not being in control of how many votes the challenge gets (and thus its security); worker’s revenue becomes unpredictable as well.
• If we match a new worker to the task in place of the slacker, the oracle might become slow if workers often reject tasks (And some level of rejection is to be expected even under adequate rewards, due to idiosyncratic preferences and qualifications of participants). In addition, some control over the number of re-matches is required for security.

Gradual stochastic matching

The process of matching the workers to a task, waiting for a timeout, and then re-matching the spots of workers who didn’t submit the votes is somewhat awkward and potentially slow. Instead, I propose to match workers to tasks in a stochastic process that doesn’t require time-outs to recruit new workers. Although slightly more convoluted conceptually, this scheme is arguably easier to implement than the alternative, and it also provides the dexterity needed for features described in the sections below.

On any block, a given worker can check if they are matched to a given task (e.g. by hashing their address, challenge ID and block’s hash together and comparing it to the target value, choice of which controls the probability of success). For now, let’s set the probability of a match to p=vs/S, where s is worker’s stake and S is the total stake of all workers; v is a constant setting the average speed of vote accumulation (I discuss the trade-offs involved in setting all the free parameters later on).

Because the match probability formula is linear, splitting sybil-attacks or pulling do not yield significant benefit unless the capital of defectors is comparable to the total stake in the oracle.

If the worker discovers they are matched to some task (which they can do without running any contract functions), they report the match to the oracle, thus claiming their right to submit a vote to this task. They can submit a concealed vote at any point before the task accumulates needed number of votes. Workers are still incentivized to work fast: if they procrastinate on a task, workers who are matched to it later might submit the votes, beating procrastinator to the reward.

After n concealed votes are submitted to the task, it enters the reveal period and resolves in the same way as before. We can impose a tight deadline for revealing votes and punish failing to reveal harshly, as workers can automate this step and have no legitimate reasons to skip it .

Task expiration

Imagine different workers keep getting matched to some task, but no one submits a vote (e.g. because the reward is not worth the work). This going on indefinitely is bad for a couple of reasons: security and externalities to other tasks. Let’s first address the security issue.

If some task keeps getting matched to workers, but no one submits a vote (e.g. because it’s not worth the reward), it becomes an easy target to adversaries. A modestly-budgeted adversary can wait long enough to fill all the voting seats with their accounts.

To prevent this attack, a task is given an expiration date (set by task-giver) — if T matches have been reported on some task and there are still not enough votes submitted, the task is cancelled, and the reward is returned to the creator. This policy makes estimating security of a given task rather simple:

Suppose a task needs 10 votes, and expiration period is T=30 matches. The task is considered to successfully resolve if some value gets at least 8/10 votes. Then adversary with 10% of stake has probability <13% of successfully subverting the task. (to get this upper bound, consider number of votes won by adversary a binomial variable in the adversary-optimal scenario of exactly 2 outsiders submitting a vote to the task)

Taxing worker participation.

Currently we are not penalizing workers who get matched to a task but do not submit a vote. This gives workers total freedom in choosing which tasks to not process, but it comes at the cost of efficiency and security. A worker in this scheme is incentivized to stake as much eth as possible to get matched to numerous tasks and process only the most profitable ones. When adopted by all, this strategy leads to a market where workers are in a constant stake arms race and tasks take forever to get processed.

The fundamental reason why these problems arise is that workers are allowed to impose externality on the rest of the system without having to pay for it: if I get matched but do not submit a vote, I indirectly prevent someone else from submitting a vote, as well as waste some of the time the task has to recruit votes.

To avoid all this, we tax the workers in a revenue-neutral way. When a worker is matched to a task, some fraction of task’s reward size is substracted from their stake. The tax goes towards task’s reward, so effectively the workers only pay the tax only when they choose not to process the task.

Supply/demand balancing

Here’s another problem with our protocol. Suppose there are 20 workers lavishly verifying a steady stream of several prediction market tasks per day. The World Cup comes along and Augur dumps 1000 tasks into the system on tournament’s last day. Workers can’t possibly process all tasks in time, so most of them end up expiring.

One solution to such supply/demand mismatches is to set v, matching speed, to be very small. This solution however has the obvious disadvantage of leading to a very slow oracle. The fundamental problem here is that system’s throughput (number of processed tasks per day) is constrained by workers, but is effectively set by task-givers. I propose to fix this by modifying the match probability to

p(s) = vs/max(N*C,S),

where C,v are constants, and N is the number of tasks. This effectively caps the maximum number of tasks a given worker with a given stake can take up per unit of time. When there are few tasks and many workers, this formula is equivalent to the old one, p(s)=vs/S, and it takes just as long for tasks to accumulate votes. When the number of tasks is large, p=vs/NC, and the expected number of tasks a given worker gets is determined by their stake but not the total number of active tasks.

This creates a natural relationship between supply/demand ratio and the average time it takes to resolve a task. One could also modify this formula to weigh different tasks differently in order to allow task-givers to express how urgent their task is, but I forgo of this feature to keep things simple.

Taxing task participation

Similarly to workers, tasks can impose an externality on the system. When there are many tasks and few workers, the task, by virtue of being there, decreases the number of matched workers for the other tasks. In the supply-dominant regime, there might still be an externality due to workers spending their attention looking at the task, although this depends on the application.

If the task givers aren’t paying this externality, bad things can happen. For example, one can bring the oracle to a halt by posting hundreds of fake 0-reward tasks, completely depriving the real tasks of workers.

We can again fix this with revenue-neutral taxation. When a task expires, a portion of its reward is distributed between the workers who were matched to the task, and the rest is returned to the task giver. How much should we tax? It makes sense to charge proportionally to tasks expiration time, as the externality it imposes is linear in time. Taxing more results in a riskier game for the task givers, as well as imposes a higher minimum reward for a task, but it also increases the disincentive to submit under-rewarded tasks.

In a nutshell

Oracle’s workflow:

0) workers who wish to participate stake eth

1) task givers submit tasks with chosen reward, required number of votes, and expiration time

2) Stochastic matching: a worker can check if they are matched to a task on a given block by hashing their address, task id and block hash and comparing it to a target, which is set by their stake.

3) If the match is successful, a worker reports the match to the mechanism — this allows the worker to submit a concealed vote to the task later on(they can submit the concealed vote as long as the task is recruiting votes)

4) once a task accumulates the needed number of concealed votes, it enters reveal stage

5) after all votes are revealed, task’s value is decided and the reward is distributed according to some rule (e.g. majority rule + splitting reward between majority voters)

Task timeouts:

To prevent sybil attacks we allow matches to take place only for a certain amount of time T_task, after which the task is cancelled. In that case some of task’s reward is distributed between all workers who claimed a match to the task.

Matching probability:

A worker is matched with a task on a given block with probability

p(s) = vs/max(NC,S)

, where s is worker’s stake,
S is the total stake in the system,
v , C are constants,
N is the number of tasks that are recruiting votes,

Worker Taxation:

To account for externalities to others, workers are taxed for being in the worker pool proportionally to their stake. This is done in a revenue-neutral way (redistributing the taxes back to workers through rewards).

Every time a worker claims a match to a given task, a fraction of reward is subtracted from their stake. This amount is transferred towards task’s reward.

To disincentivize tax-evasion by not reporting successful matches , we allow tax-collection arbitrage. If someone notices that some worker was matched to a task but failed to report it, they can report this worker to the contract, getting a reward for doing so (subtracted from mischievous worker’s wallet) and forcing the tax collection.

Setting parameters

Market creator sets:

v — probability price — the higher it is, the more stake it takes to take up a given workload. Setting it higher leads to a safer oracle, as the amount of stake needed to start subverting tasks is higher, but setting it too high may prevent workers from participating at full capacity due to insufficient budget or low ROI.

alpha_worker — worker tax rate, fraction of reward subtracted from stake upon successful match. Low tax rates allows workers to grab more tasks than they can process, thus giving them more freedom in picking which ones to perform, and this leads to better price discovery for rewards. But it also increases the time needed to process a task and as a result makes it easier to subvert. To estimate the trade-off, notice that a worker can stay profitable while processing at least 1 task out of 1/alpha, and in this regime tasks get at most nv/alpha matches before resolving.

alpha_task — task tax rate, the amount distributed between matched workers in the event of task’s cancellation, at the expense of task’s reward. It makes sense to tax proportionally to T_task to account for task’s externality. High tax rate disincentivizes mispricing tasks and thus increases price discovery, but it also makes task-givers pay more for cancelled tasks, as well as make the minimum price for submitting a task high. To get a lowerbound for this tradeoff, notice that if a fair reward for a task is r, and a risk-neutral task-giver has value 2r for getting an answer, they would keep submitting the task to the system as long as, on average, at least 1 in 1/alpha_task fairly priced task gets processed.

T_reveal — time to reveal a concealed vote — should be set to several blocks so that network congestion doesn’t prevent a worker from revealing the vote, but there is no point in setting it higher, as this step can be automated and there are no legitimate reasons for a worker to delay the process.

T_task — task expiration date. After this many agents claim being matched to a task, it is canceled. It should equal to at least n_votes. Increasing it makes it more likely that the task would get processed, but it also leads to a decrease in security and increase in the tax paid by a task in the event of cancellation.

Bottom line

I have described a mechanism that stochastically matches workers to task, and does so in a way that guards against adversaries while allowing participants on both sides the freedom to express their preferences: task givers get to choose how to trade-off task security with its cost, and workers get some freedom in picking which tasks to process, as well as set their peak processing capacity. All parties are held accountable for the externality they impose on the system via taxation, and because of this the market is unlikely to end up in an inefficient regime of large processing times or high task rejection rates.

This mechanism is by no means uniquely good, and there are probably better design choices that I haven’t thought of. However, whatever those choices are they would have to get around the incentive problems I have described here and in the previous post; I am convinced these problems and trade-offs are bound to arise independently of oracle’s design.

There are a few issues that I haven’t addressed at all here, such as vulnerability to the bribes or the trade-off between oracle specialization and security. I might do this in the following posts, as this one is already plenty long.