Decentralized data processing service

[sanity]

Overview

The proposal describes a system for allowing distributed processing on the Freenet network using WebAssembly functions to process input contracts and update the state of other contracts. The system includes mechanisms for validating the accuracy and timeliness of the computed state updates, as well as a reputation system to penalize workers who do not execute jobs correctly.

Jobs

A “job” takes the state from one or more input contracts, processes it using a provided WebAssembly function, and then sets the state of another contract to the result.

Workers

Workers execute jobs. There is also a validation mechanism to ensure workers execute jobs in a timely and accurate manner, as well as a reputation system to punish and exclude workers that don't do their job correctly.

Job Lifecycle

Create a job

Job is created in WebAssembly, implementing this job function:

trait Job {

  /// Execute a job or determine additional input contracts
  fn job(
         /// The parameters that form the job along with the webassembly that implements
         /// this function.
         parameters : [u8],

         /// Any requested dependent contracts, this function requests them by returning
         /// JobOutput::Dependencies() containing the desired dependencies. 
         dependencies : HashMap<ContractInstanceId, Dependency>,
     ) -> JobOutput {
    // ...
  }
}

pub enum JobOutput {
    /// This job requires additional dependencies as specified
    Dependencies(HashMap<ContractInstanceId, DependencyCfg>)

    /// This job produced its output
    Output(Vec<u8>)
}

/// Specify how the contract wishes to receive dependency updates
pub struct DependencyCfg {
    /// Should the update include the initial dependency state we retrieved
    pub initial_state : bool,

    /// How many recent deltas should be included?
    pub recent_deltas : u32,

    /// How many recent states should be included?
    pub recent_states : u32,
}

pub enum Dependency {
    NotFound,
    Found {
        initial_state : Option<State>,
        recent_states : Vec<State>,
        recent_deltas : Vec<Delta>,
    },
}

Notes

• The recent_states and recent_deltas mechanism are designed to allow the job to update state incrementally rather than needing to recompute everything every time a dependency updates

Wrapping by Job Contract

The job WebAssembly is wrapped into a standard job contract as a parameter, the job contract’s purpose is to advertise the job and to collect the job output from workers.

Job Ring

Jobs and workers are assigned positions on the job ring based on a hash of the job’s WebAssembly code or the worker’s public key, respectively.

Priority Ring Tree

To allow peers to find jobs close to them efficiently, we use a system of job discovery contracts arranged in a hierarchy. Each contract is responsible for a segment of the ring, half of the parent contract's segment.

The job ring is broken up into a hierarchy of these contracts, each bisecting the parent’s section of the ring.

Job list

Each discovery contract in the tree contains a list of the top $N$ jobs in its segment of the ring, ranked by:

rank = tokens / (1 + majority - minority)

• tokens - number of antiflood tokens spent on this job in the past 24 hours

• majority - estimated number of workers whose output is the same as the majority's

• minority - estimated number of workers whose output is different to the majorities

Datastructures

mod DiscoveryContract {
    pub struct Parameters {
        /// The depth of this discovery contract in the tree, the root contract has
        /// a depth of 0.
        pub depth: u8,

        /// The index of the segment running counter-clockwise
        /// If depth=0 then there is only one segment so segment_ix=0. The
        /// number of segments = 2^depth.
        pub segment_ix : u32,
    }

    pub struct State {
        pub jobs : Vec<Job>,
    }

    pub struct Job {
        // The location of the job request
        pub location : Location,

        // The request itself
        pub request : JobRequest,

        /// The JobResult ranks together with the job results themselves
        pub results : Vec<(Location, JobResult)>,
    }

    pub struct JobRequest {
        pub code : Wasm,
        pub parameters : [u8],
    }

    pub struct JobResult {
        /// The results, keys are either the output itself or the
        /// hash of the output. The JobCertificates are those
        /// by workers closest to the Job::location.
        pub results : HashMap<ResultOutput, Vec<JobCertificate>>,
    }

    pub enum ResultOutput {
        /// If the output is smaller than a specified threshold, then
        /// embed it directly for efficiency
        Embedded([u8]),

        /// If the output is larger than the specified threshold then
        /// reference the hash of the output which allows the output
        /// itself to be retrieved from a simple content-hash contract
        Referenced(Hash),
    }

    pub struct JobCertificate {
        pub worker_location : Location,
        pub worker_pubkey : PublicKey,
        pub result_signature : Signature,
        pub tokens : Vec<TokenAllocation>,
    }

    pub struct TokenAssignment {
        // See https://github.com/freenet/locutus/issues/246
        // TokenAssignment::assigned_to must be the hash of the
        // job result hash.
    }
}

🚧🚧🚧 To be completed 🚧🚧🚧