###### tags: `Issue`,`Solving multiple tasks`
# Issue: On the parallel task solution

**Investigating the question: should Solvers be allowed to solve different tasks to propose a valid block or not.**

Possible approaches:
1. Prevent Solvers to solve an arbitrary task but force them to solve a specific one, for example the first one from a task queue (FIFO order, priority queue), or a randomly selected one through a hash function.
2. Allow Solvers to arbitrarily select the task they prefer to solve in order to propose a valid block.
3. The task is pseudorandomly assigned to a specific Solvers, which is not allowed to freely select the task.
* The PRF must be deterministic and verifiable
* The PRF must use public information
* The PRF must be secure, i.e. there should be no efficient way for the Solver be able to change the task it has been assigned to solve

## Analysis of case 1
Advantages:
- More efficient task validation since the metadata necessary for validation can be prefetched.

Disadvantages:
- Less efficient task solution: more energy consumption per task

## Analysis of case 2
Disadvantage:
- Opens to possible attacks due to the lack of control over the complexity of the task proposed by the Suppleir

## Analysis of case 3

Advantages:
- More efficient to produce solutions because of higher degree of parallelization
- Less energy is consumed per single task
- Might improve fairness because

Disadvantages:
- Increases the complexity due to the PRF
- Prevents the contribution about fine-grained adjustable complexity paid by the Supplier
- The validation is less efficient because all the validator have to retrieve the validation metadata (or otherwise store it beforehand). In case of ML task the size can be several GB

### On the usage of Algorand's Verifiable Random Function (VRF) as PRF

[Algorand](https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf) uses VRF to select specific users in a private and non-interactive way. In algorand, users selected by the VRF join committees and propose blocks.

:::success
**Idea**: To use Algorand's VRF to assign one of the Task in the Task pool to a specific Solver
:::

In Algorand the **inputs** to the VRF are:
- Private key of the user
- A public seed
- A role
- Expected number of users selected for a role, $\tau$
- weights associated to one user and the sum of all the weights

VRF **outputs**:
- a hash
- a proof $\pi$
- $j$ number of times the user is selected (since the process is random and a single user might be selected multiple times)


The Sortition algorithm in hybrid chain doesn't need roles nor $\tau$.

The VerifySort function is modified accordingly.

### Additional considerations and notes
:::info
In Algorand, every user that owns a token could in principle be selected as committee member, proportionally to the amound of tokens owned.

We cannot apply the same construction directly to hybrid chain because not every token owner might want to be a Solver. See the disadvantages box for a different approach.

A note to keep in mind: w,W in algorand weights the users. In our approach we would like to weight the tasks. Therefore we would like to use the weights differently than in algorand.
:::

:::success
Advantages:
1. **Efficiency**. Using the Sortition algorithm, we can associate a Solver to a Task in a non-interactive and verifiable way. In such way, Solvers can work on different tasks concurrently and improve the efficiency of the system.
:::

:::danger
Disadvantages:
1. **The pool of Solvers (their public/private keys) must be known before Sortition. Additionally, it should be known long before the seed for the Sortition algorithm is selected** (for security reasons). We can do that in a permissionless blockchain introducing a new type of transaction "Enroll new Solver". The transaction might lock a deposit so that when a Solver is not interested in solving anymore can claim it back.
2. **Delayed beginning of problem solution search**. Fetching problem metadata can be done only after the execution of the Sortition algorithm, which introduces delay and possible unfairness about metadata sizes. Prefetching is still possible as an optimization is the number of Tasks is limited.
3. **Validation delay**. Validation may require fetching metadata. Since metadata is different for every task and cannot be optimized through prefetching, the validation is delayed, affecting the consensus delay. Definitely it applied to ML tasks, not sure about OV.
:::

[Algorang documentation](https://developer.algorand.org/docs/algorand_consensus/#verifiable-random-function)