On Chain Computation

The Computation Marketplace is intended for algorithms which are sufficiently complex that performing them on-chain will be costly. For many algorithms, this also means that computation must be split across multiple steps to fit within the gas limit of the EVM.

Stateless Computations

An executable is stateless if the implementation does not require any additional data beyond the output from the previous step.

A fibonacci computation that was stateless would be implemented such that each step of computation returned the two most recently computed fibonacci numbers. This would allow each step to operate purely on the return value of the previous step.

This design allows for computation of the 3rd fibonacci number to be executed as follows.

  • fib_3rd = fib.step(3, fib.step(2, fib.step(1, “3”)))

Each of these calls could be made using .call() allowing all computation to be done using the on-chain implementation without actually sending any transactions.

Executable contracts that are stateless are superior to stateful implementations in cases where the stateless implementation does not introduce unacceptable complexity. Stateless implementations allow for participants in the computation market to compute the requested computation using the actual on-chain implementation.

The fibonacci example is best done as stateless since the implementation overhead of returning the latest two fibonacci numbers is small.

Statefull Computations

An executable is stateful if the implementation requires additional information beyond the return value of the previous step.

A fibonacci implementation that was stateful might store each computed number in contract storage, only returning the latest computed number. On each step, this function would need to lookup the computed number from two steps ago in order to compute the next number. This reliance on local state is what makes the contract stateful. It also disallows using .call() to compute the final result since each execution of the step function must be done within a transaction in order to update the local state of the contract.

An algorithm like scrypt could theoretically be done as a stateless contract, but each step would have to return a very large lookup table due to the the nature of the scrypt algorithm. This large input and return value would reduce the number of actual computations that could be executed in a single step which would cause a significant increase in the total number of steps necessary to complete the computation.

Authoring an Algorithm

The simplest way to author a new algorithm is to use the abstract solidity contracts provided by the service.

StatelessExecutable and StatefulExecutable

  • contracts/Execution/Execution.sol::StatelessExecutable
  • contracts/Execution/Execution.sol::StatelessExecutable

These abstract contracts can be used to implement stateless or stateful algorithms. They only require implementating the step function from the Execution Contract* api.

FactoryBase

  • contracts/Factory.sol::FactoryBase

This abstract contract can be used to implement the Factory API for an Execution Contract. It requires you implement either a _build function which returns the address of the newly deployed Execution Contract. This function implements a default build function which logs an event with the address of the newly deployed contract which can be overridden if this behavior isn’t wanted.

Example Stateless Fibonacci Contracts

The following example code implements a stateless Execution Contract and Factory for computing fibonacci numbers.

import {StatelessExecutable, ExecutableBase} from "contracts/Execution.sol";
import {FactoryBase} from "contracts/Factory.sol";


contract Fibonacci is StatelessExecutable {
    function Fibonacci(bytes args) StatelessExecutable(args) {
    }

    function step(uint currentStep, bytes _state) public returns (bytes result, bool) {
        /*
         *  Uses a 64-byte return value to serialize the previous two
         *  computed fibonacci numbers.
         */
        uint i;
        bytes memory fib_n;

        if (currentStep == 1 || currentStep == 2) {
            // special case the first two fibonacci numbers
            fib_n = toBytes(1);
        }
        else {
            // otherwise extract the previous two fibonacci numbers from
            // the previous return value to compute the next fibonacci number.
            var n_1 = _state.extractUint(0, 31);
            var n_2 = _state.extractUint(32, 63);
            fib_n = toBytes(n_1 + n_2);
        }

        if (currentStep > toUInt(input)) {
            // If we have computed the desired fibonacci number just return
            // it as a serialized bytes value.
            result = fib_n;
        }
        else if (currentStep == 1) {
            // Special case the first step to initialize the 64-byte return
            // value.
            result = new bytes(64);
            for (i = 0; i < fib_n.length; i++) {
                result[32 + i] = fib_n[i];
            }
        }
        else {
            // Write the latest two computed numbers to the 64-byte return
            // value.
            result = new bytes(64);
            for (i = 0; i < 32; i++) {
                result[i] = _state[i + 32];
                if (i < fib_n.length) {
                    result[32 + i] = fib_n[i];
                }
            }
        }

        return (result, (currentStep > toUInt(input)));
    }

    /*
     *  Functions used to serialize and deserialize unsigned integers to
     *  and from bytes arrays.
     */
    function toUInt(bytes v) constant returns (uint result) {
        // Helper function which converts a bytes value to an unsigned integer.
        for (uint i = 0; i < v.length; i++) {
            result += uint(v[i]) * 2 ** (8 * i);
        }
        return result;
    }

    function extractUint(bytes v, uint startIdx, uint endIdx) constant returns (uint result) {
        // Helper function which extracts an unsigned integer from a slice
        // of a bytes array.
        if (startIdx >= endIdx || endIdx >= v.length) throw;
        for (uint i = startIdx; i < endIdx; i++) {
            result += uint(v[i]) * 2 ** (8 * (i - startIdx));
        }
        return result;
    }
}


contract FibonacciFactory is FactoryBase {
    function FibonacciFactory() FactoryBase("ipfs://test", "solc 9000", "--fake") {

    function _build(bytes args) internal returns (address) {
        var fibonacci = new Fibonacci(args);
        return address(fibonacci);
    }
}

API Requirements

A developer authoring an algorithm for the the computatoin market must conform to the following API requirements.

All algorithms must be implented as a contract with the following API.

It Must take a bytes value for any arguments receives as input.

It Must implement the following functions.

isStateless()

  • isStateless() constant returns (bool)

Returns whether this computation relies on intermediate state. If each step of execution only relies on the output of the previous step then this should return true. Otherwise it should return false.

isFinished()

  • function isFinished() constant returns (bool)

Return true if the computation has finished, or false if computation is in progress.

getOutputHash()

  • function getOutputHash() constant returns (bytes32)

Return the sha3() of the final return value of the computation. Return 0x0 if the function has not completed computation.

requestOutput(bytes4 sig)

  • function requestOutput(bytes4 sig) public returns (bool)

This function should send the bytes return value of the computation to the msg.sender by calling the function indicated by the provided 4-byte signature as follows.

function requestOutput(bytes4 sig) public returns (bool) {
    if (isFinal) {
        return msg.sender.call(sig, output.length, output);
    }
    return false;
}

This allows circumvention of the inability of contracts to receive bytes values from the return values of external function calls.

step(uint currentStep, bytes _state)

  • function step(uint currentStep, bytes _state) public returns (bytes result, bool)

This function should perform one unit of computation that is sufficiently small to fit within the EVM gas limit.

It will be provided the following arguments.

  • uint currentStep - The 1-indexed step number for the current computation. This increases by one each time the contract executes a unit of computation.
  • bytes _state - The return value from the previous step, or the bytes input value that the contract was initialized with if this is the first step.

This function must return a tuple of (bytes, bool) where the bool value indicates whether computation has completed.

execute()

  • function execute() public

A call to this function must advance the computation by a single step. If the computation has already completed, this function should throw an exception.

executeN(uint nTimes)

  • function executeN(uint nTimes) public returns (uint iTimes)

A call to this function should advance the computation up to but not exceeding nTimes. This function must interpret nTimes == 0 as instruction to run as many steps as possible prior to returning. This function must return the number of steps that were completed. This function should throw an exeception if computation has already completed when called. This function must handle the case where execution of nTimes steps would exceed the gas limit and still execute successfuly in these cases.

Factory

This contract is used to deploy instances of the Execution Contract*.

It must implement the following API.

sourceURI()

  • function sourceURI() returns (string)

Returns the URI where the source code for this contract can be found.

compilerVersion()

  • function compilerVersion() returns (string)

Returns information about the compiler and version which should be used to recompile the bytecode of this contract.

compilerFlags()

  • function compilerFlags() returns (string)

Returns any configuration arguments that should be used to recompile the bytecode of this contract.

build(bytes args)

  • function build(bytes args) public returns (address addr)

A call to this function should deploy a new instance of the Execution Contract initialized with the provided bytes args value. This function must return the address of a contract which conforms to the Execution Contract API and which can be used to compute the result of the computation given the provided bytes args input value.

isStateless()

  • isStateless() constant returns (bool)

Returns whether this factory’s Execution Contract is stateless or stateful. If each step of execution only relies on the output of the previous step then this should return true. Otherwise it should return false.

totalGas()

  • function totalGas(bytes args) constant returns(int)

Returns the total gas estimate in wei that would be required to compute the computation for the given input.