Let C be a contract, N be a set of all K nodes in the network, and a solicitor s be a node in N who wants to delegate work to other nodes. s makes a transaction to C with a pledge g and a public key b such that,
s has a pair of private and public keys that are generated using an asymmetric key encryption scheme
g is an amount of compensation which is to be given to a node that accomplishes work
Any bidding node b of N who wants to participate in a selection round makes a transaction to C such that,
b makes a transaction with a sha of a random number r_i, where sha(x) is a function that outputs cryptographic hash of x
b makes a transaction and it needs to arrive within a window w to be examined by C
Given a sequence of nodes BN who made a bid within a window w, and a sequence of nodes SR who have recently worked, C creates SN, a subset of BN such that the following conditions hold,
C creates SN only when |BN| > 1
1 < |SN| < |BN|
A node n whose transaction comes early generally has a higher chance to be selected, with exceptions that if n is in SR it gets repositioned to the end of BN. If more than a single such node exists in BN, they are repositioned and ordered such that the least recently worked node n comes first
Nodes of SN make a transaction to C with r_i within a window w
C creates a set of integers VR and computes a random value r using gen(X) such that
Valid random numbers VR is a subset of a sequence R whose elements are all r_is transmitted such that an element of VR is unique
C computes r if and only if |VR| / |R| > THRESHOLD
gen(|SN|, VR) is a function that outputs an integer r such that 0 <= r < |SN|
C selects a node s of SN whose index is r and appends s in SR.
C adds a pair (x,y) into a set of work W, a binary relation such that,
x is an id of node n
y is a unique identifier of work w, which C generates
C adds a pair (x,y) into a set of work proof WF, a binary relation such that,
x is a unique identifier of work w
y is a public key b which s provided
Comparison with DRAND
DRAND requires a private network, which requires the secondary network for randomness beacon
Our approach relies on a smart contract
Communication overhead may be the same
The only downside of our approach is the transaction cost
Next steps
(First Step) Review of DRAND and a deeper comparison to identify its pros and cons
We might be able to leverage some of the features in our protocol
(Second Step) Implementation of our idea
First, write down the design specification and the steps
Full Picture
There would be a set of task givers, T
T_i would submit a task/job to a smart contract. Let us a software package SP which consists of input I and code C.
Smart contract/blockchain can not store heavy software code and data, therefore, we should store the software package (code, input) to a decentralized storage such as IPFS. At the time of submission, only the pointer to IPFS storage is given to the smart contract
There are S nodes, that are ready to solve/run the task
How to select a subset of nodes (it could be one or more) for the execution? - this is where your protocol will start the work
Node selection protocol is expected to select one or more nodes for the computation/execution
Software package distribution: Assuming that your protocol selects S_a for the computation, how does the smart contract inform the location/IPFS pointer to the compute node, so that it can go and download the software package to start the execution?
Software execution engine (VeriPy): How do we introduce the special version of Python for the execution?
After the execution, the node would be uploading a new software package including the software, input, output, and the execution profile (stack trace).
Everything would be uploaded to IPFS and only the pointer is relayed to the smart contract notifying the completion of the task
Now, the smart contract will have to start the verification process to check the correctness
Your node selection protocol would select one or more nodes to perform verification
Software package distribution (this time with output as well as the execution profile): Assuming that your protocol selects S_a for the computation, how does the smart contract inform the location/IPFS pointer to the compute node, so that it can go and download the software package to start the execution?
After completing the verification, the verifiers notify the smart contract that the results are correct based on their analysis of stack profile, etc. - this can be a proof.
We have successfully executed the task giver’s T_i software using public resources
The smart contract can emit an event notifying the completion of execution along with the pointer to the software package. At this stage, the T_i can download a software package SP_completed, which would have input I, code C, output O, and execution profile EP.
Protocol
Comparison with DRAND
Next steps
Full Picture