Skip to content

Instantly share code, notes, and snippets.

@karalabe
Last active April 1, 2018 12:14
Show Gist options
  • Save karalabe/0ab4d715a81b74dd257d to your computer and use it in GitHub Desktop.
Save karalabe/0ab4d715a81b74dd257d to your computer and use it in GitHub Desktop.
Geth supported decentralized contract cron

Decentralized cron service in Ethereum

Even though the EVM is more or less a turing-complete machine, one significant limitation is that it's a reactive system: whenever it receives an event, it does its bidding, after which it spins down and goes to sleep until it's woken again. For many smart contracts this is not a problem, as they operate on user input.

However, there's a class of contracts that occasionally (or regularly) need to execute a task some time in the future. A few of these can be ignored (e.g. you won something and you explicitly have to claim it... as you're an end user beneficiary, it makes sense to require you (make you suffer that xtra step)). On the other hand, if we would like to give contracts a bit more self autonomy and life, there should be a way for them to "wake up".

Previous proposals included:

  • ALERT opcode supported by the EVM (requires consensus change, bad to link the outside world with the inside, etc).
  • Poor man's cron: check scheduled tasks upon any transactive operation (very unreliable and hackish).
  • Trusted third party cron service (you depend on an outside service that can disappear or censor certain things).
  • Incentivise people to call your scheduled tasks (issues with gas costs, relaibility, etc).

I propose is a dual component cron architecture: a contract based cron schedule service, which itself incentivises any entity in the network for task execution, and a miner extension that allows the gas and reliability issues to be fully circumvented.

Cron scheduler contract

The scheduler contract is a very simple component meant to conver the task and incentive maintenance part of the system. Users can schedule a task for future (possibly recurring) execution, offering an incentive for each of those invocations. The contract itself would enfoce that only successfully completed tasks can claim the reward.

A crude proof of concept pseudo code contract would be:

contract Cron {
  // Task is a single future scheduled operation
  struct Task{
    address   owner;
    address   target;
    bytes     opdata;
    timestamp uint;
    blocknum  uint;
    incentive uint;
  }
  // schedules is the collection of scheduled operations (mapped by id)
  mapping (uint => Task) schedules;
  
  // next is the autoincrement unique id for the next scheduled task
  uint next;

  // schedule creates a new task for future execution.
  function schedule(contract address, bytes data, uint atTime, uint atBlock) uint {
    // Short circuit if no incentive is given
    if (msg.value == 0) {
      return 0;
    }
    // Schedule the task for execution
    next++;
    schedules[next] = Task(msg.sender, contract, data, atTime, atBlock, msg.value)
    return next
  }
  
  // cancel aborts and refunds a pending schedule.
  function cancel(uint id) {
    // ...
  }
  
  // execute runs a scheduled task and claims the reward to the specified address.
  function execute(uint id, address claimer) {
    // Check schedule conditions 
    task = schedules[id]
    if (task.atTime > 0 && task.atTime > block.timestamp) {
      return
    }
    if (task.atBlock > 0 && task.atBlock > block.number) {
      return
    }
    // Execute the task and claim the reward
    delete(schedules, id)                      // Or however it's done in solidity
    task.target.call(task.opdata, task.owner); // Again, this should be doable, don't know the exact syntax
    claimer.send(task.incentive);
  }
}

The above contract should be enough to get the idea behind what a scheduler should look like and do. A few points the emphasize in it are:

  • The contract enforces that you only get to claim the reward if you successfully ran the function first.
  • The boundary conditions are currently implemented as AND, but could be changes to OR, or maybe support both.
  • The original scheduler of a task is passed on to the target contract, so it can verify validity.
  • The reward doesn't go to the msg.sender or coinbase for a very specific reasion (see next section).

Geth miner extension

The above contract implementes the full incentivised cron scheduler, but it does not (cannot) address the issues of gas usage (how can I be sure the incentive covers the gas + some extra); or the reliability (what guarantees do I have that someone will request my task to run). The solutions are three miner modifications: cron scheduled task monitorization; task execution simulation; and zero cost transaction injection.

By modifying the geth miners to explicitly watch for pending tasks in this cron service, we can ensure that as long as the next block is mined by a geth miner, the cron contract will be honored and pending tasks executed.

By doing a dry-run simulation of the pending task, we can check if the incentive is enough to cover the costs, and also ensure that no malicious code hogs the resources: we divide the incentive with our desired gas cost, and simulate the task using those parameters. If gas runs out, we deny running the task (also ignoring it for all future invocations).

If the incentive turns out to cover the task, the miner injects a zero gas-price transaction into the block, by which it claims the task. As the miner itself is mining the block, it can accept a zero-incentive transaction from itself to claim the reward. Furthermore, as the execute function explicitly requires the claimer to be set, the miner can pass it's coinbase address as the claimer, and execute the transaction from any random throwaway account (balance = 0 works, as the gas price is zero).

Miner benefits and drawbacks

The proposed scheme requires that miners run an extended miner, which searches for- and executes scheduled tasks. However, with the proposed incentive scheme, the execution of a scheduled task boils down to effectively one more transaction that the miner can keep the gas costs for (plus almost always a bit more, as there's no refund from the incentive); so from a miner's perspective, such an extension is only extra income.

The single drawback of the scheme is that scheduled tasks that "run out of gas" (i.e. don't have a big enough incentive to cover the gas price) will potentially waste a miner's resources when figuring out that it's not enough. In the case of a normal transaction, the miner would keep the gas anyway. Here however the miner does not have access to the incentive, unless the code runs successfully.

Summary

I proposed here a cron scheduler made up of a smart contract fully deployable on the Ethereum network as is, and a miner modification that would track and execute these scheduled tasks while being incentivied almost the same way as with any other transaction (successfull runs reward more than the gas, failed one don't reward the gas).

In my opinion this proposed cron scheduler beats all previous proposals as it provides all the benefits of a reliable decentralied cron daemon to client users/contracts, while at the same time incentiviezes miners to execute the scheduled tasks purely out of self interest, both pushing further liquidity into the Ethereum network as well as providing it with a new execution dimnesionality.

As the required changes are not consensus breaking, as long as Geth has a large enough share of the total mining capacity, it should be possible to keep the mechanism alive even if cpp/py/other miners do not implement or choose to support it.

@frozeman
Copy link

frozeman commented Sep 7, 2015

if you add ```js it will make you example code more readable.
Besides that it sounds like a good idea

@karalabe
Copy link
Author

karalabe commented Sep 7, 2015

👍 great idea, done :)

@Gustav-Simonsson
Copy link

Comments from gitter:

  • The current code deletes the task before execution; it should check result of execution call before deleting the task. This however poses an interesting question - should execution of scheduled tasks always succeed, or is there a use case where the execution (CALL) fails but the task is still considered executed? Probably this would not be too useful, at least not to start with.
  • It's important to note that gas simulation can be run by non-mining nodes too; in the current version it reads as if they cannot and thus it needs to be a miner extension.
  • This feature would be very useful for non-mining nodes too. They can run monitoring and gas simulation. Execution of scheduled task by non-miner can still be profitable for the executor depending on the rewards, and allows tasks to be executed while not all miners are running this.
  • The only difference for a mining node is that they would include executing txs first in the block to get priority over other execution attempts, and will also get any Ether paid for gas back (or set it to 0).

Having the feature enabled for non-mining nodes will be important as not all miners will run this, at least not to start with. Even in the long term some miners may not run it for whatever reason; it's miner strategy and so cannot be guaranteed. In such a scenario, if rewards are high enough then non-mining nodes would be incentivised to execute tasks in place of miners.

@Gustav-Simonsson
Copy link

Another idea that came up on gitter: have the task declare gas needed, and check if the executor calls with enough gas. If so, the reward can be given before the call to the actual task execution, moving the risk of OOG to the creator of the task for a given declared gas value.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment