Task Sampling

Each round (~20 minutes), a random sample of tasks are chosen to be test. Spark checkers can only complete certain tasks from the sample.

Each round of the Spark protocol is approximately 20 minutes. At the start of each round, the Spark tasking service randomly selects a set of records from all Eligible Deals. We refer to each of these records as a Retrieval Task and, specifically, it is the combination of an Eligible Deal and a Round Id. We will also refer to the set of Retrieval Tasks in the round as the Round Retrieval Task List.

It is important for the security of the protocol that the Retrieval Tasks in each round are chosen at random. This is to prevent Spark checkers from being able to choose their own tasks that may benefit them, such as if an SP wanted to run lots of tasks against itself. We don’t yet use Drand for randomness for choosing the Round Retrieval Task List but we would like to introduce that to improve the end-to-end verifiability (Github).

During each round, the Spark Checkers are able to download the current Round Retrieval Task List. You can see the current Round Retrieval Task List here: http://api.filspark.com/rounds/current.

Which of the tasks in the Round Retrieval Task List should each Checker perform?

A simple approach for testing all tasks in the Round Retrieval Task List would be to ask all Spark Checkers (i.e., currently people who are running Filecoin Station) to check whether or not they can complete each Retrieval Task in the round, by attempting to retrieve the CID from the Storage Provider. However, there are many thousands of Spark Checkers and it would be wasteful to ask them all to test every task in each round. This would also create a lot of unnecessary load on the SPs.

At the other end of spectrum, the protocol could ask only one Spark Checker to complete each Retrieval Task in the Round Retrieval Task List. This is also not advisable as we cannot trust individual Spark Checkers to act honestly, nor can we trust their internet connection to be 100% reliable even if they do act honestly. If we trusted the results of individual checkers then you can imagine an adversary, who wants only a certain SP to prosper, to report positive results for that SP, and negative results for all other SPs. We need multiple checkers to perform each Retrieval Task so that the results can be compared.

The current approach lies between these two ends of the spectrum. By asking a subset of Spark Checkers to perform each of the Retrieval Tasks in the round, we can test far more deals in each round, avoid unnecessarily load-testing an SP for one CID, while having enough Checkers perform the same test to build confidence in the result. Specifically, our confidence here is based on assumptions about what percentage of the network of checkers in acting honestly.

How does the protocol orchestrate the Spark Checkers to perform different tasks from each other at random such that each Task is completed by at least $m$ checkers?

As previously mentioned, the checkers start each round by downloading the Round Retrieval Task List. For each task that’s in the List, the checker calculates the task’s “key” by SHA256-hashing the task and the current dRand randomness, fetched from the dRand network API. Leveraging the wonderful properties of cryptographic hash functions, these hash values will be randomly & uniformly distributed in the entire space of $2^{256}$ values. Also, by including the randomness in the input alongside the Eligible Deal details, we will get a different hash digest for a given Eligible Deal in each round. We can define the taskKey as

taskKey = SHA256(payloadCid || miner_id || drand)

Each Spark Checker node can also calculate the SHA256 hash of its Station Id. This is fixed across rounds as it doesn’t depend on any round-specific inputs. (In the future, the protocol may add the drand value into the hash input of the nodeKey too.)

nodeKey = SHA256(station_id)

The checker can then find its $k$ “closest” tasks, using XOR as the distance metric. These $k$ tasks are the Retrieval Tasks the Spark Checker node is eligible to complete. Any other tasks submitted by the checker are not evaluated or rewarded.

dist = taskKey XOR nodeKey

Note that, at the start of each round, the protocol doesn’t know which Spark Checkers will participate as there are no uptime requirements on these checkers. This means the Spark protocol can’t centrally form groups of checkers and assign them a subset of the Round Retrieval Task List. The above approach doesn’t make any assumptions about which checkers are online, but instead relies on the fact that the nodeKeys will be evenly distributed around the SHA256 hash ring.

Following the above approach, for each Retrieval Task, there are a set of Checkers who find this task among their $k$ closest and they will attempt the task in the round. We refer to the set of checkers who attempt a Retrieval Task as the “Committee” for that task. Since we are hashing over a random value for each task when we create its taskKey, this approach mitigates against one party controlling an entire committee and dominating the honest majority consensus decision later in the protocol.

How many tasks should each checker do per round? What value is given to $k$?

The choice of $k$ is determined by Spark protocol logic that aims to keep the overall number of Spark measurements completed by the total network per round fixed. This is important because we don’t want the number of requests that Storage Providers need to deal with go up as the number of Spark Checkers in the network increases.

In each round, the Round Retrieval Task List data object specifies $k$ in a field called maxTasksPerNode. At the start of each round, the spark-api service looks at the number of measurements reported by the network in the previous round, compares it against the desired value, and adjusts both maxTaskPerNode $k$ and the length of the Round Retrieval Task List for the new round.

The choices in each round for $k$ and the length of the Round Retrieval Task List also determine the size of the committee for each Retrieval Task. This is how we ensure each task is completed by at least $m$ checkers; the committee for each task is designed to include between 40 and 100 checkers to make sure there are enough Measurements to add mitigations against malicious actors, but not too many that we load test the Storage Providers.

The Spark Checkers that are members of each committee will go on to make the same retrieval checks in the round. Each committee member then publishes their results to the Spark API, which then calculates the honest majority consensus about the result of the Retrieval Task.

Only the $k$ tasks that have been assigned to a checker in each round are treated as valid and included in the Spark RSR calculation, all others are ignored. This also means Spark checkers only get rewarded for their specified tasks each round.

On this page

• Task Sampling
• Which of the tasks in the Round Retrieval Task List should each Checker perform?
• How does the protocol orchestrate the Spark Checkers to perform different tasks from each other at random such that each Task is completed by at least ⁍ checkers?
• How many tasks should each checker do per round? What value is given to ⁍?