Protocol

[eldenpark]

Protocol

1. 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,
   1. s has a pair of private and public keys that are generated using an asymmetric key encryption scheme
   2. g is an amount of compensation which is to be given to a node that accomplishes work
2. Any bidding node b of N who wants to participate in a selection round makes a transaction to C such that,
   1. 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
   2. b makes a transaction and it needs to arrive within a window w to be examined by C
3. 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,
   1. C creates SN only when |BN| > 1
   2. 1 < |SN| < |BN|
   3. 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
4. Nodes of SN make a transaction to C with r_i within a window w
5. C creates a set of integers VR and computes a random value r using gen(X) such that
   1. 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
   2. C computes r if and only if |VR| / |R| > THRESHOLD
   3. gen(|SN|, VR) is a function that outputs an integer r such that 0 <= r < |SN|
6. C selects a node s of SN whose index is r and appends s in SR.
7. C adds a pair (x,y) into a set of work W, a binary relation such that,
   1. x is an id of node n
   2. y is a unique identifier of work w, which C generates
8. C adds a pair (x,y) into a set of work proof WF, a binary relation such that,
   1. x is a unique identifier of work w
   2. 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.