Feature Request: Data/Computation Bounties

[Stebalien]

Actors could post "bounties" to some bounty actor requesting some operation/lookup on a CID.

There are many ways to "fulfill" bounties but they generally fall into one of two main categories.

1. Verifiable results.
2. Verifiable computation.
3. Trusted Validators.

Verifiable Computation

Executing a "bounty" would always produce a corresponding "proof" of correct execution.

Halting problem note: careful gas accounting needs to be done to ensure the "always" part. That is, a proof of correctness may need to prove that the operation doesn't halt within some number of operations.

Data re-hydration

In data re-hydration:

1. The requested operation would be executed with access to the necessary state.
2. All touched data (accessed IPLD blocks) would be bundled up into a CAR file.
3. The CAR file would be sent to the bounty actor to re-execute the operation on-chain with access to the blocks in the CAR file.

The upside is that this method is very simple and efficient to compute (for the storage provider). The downside is that a potentially large amount message may need to be sent to the chain.

This variant is likely most useful for operations that need to perform storage-access efficient lookups on very large datasets.

Succinct Cryptographic Verifiable Computation

For example, the bounty could be executed under LURK and the resulting SNARK could then be validated by the chain. However, for this to work, the IPLD dag would likely need to be structured in such a way that computing a SNARK over it is efficient (e.g., hashed with Poseidon, not SHA).

1. Pro: User-friendly.
2. Pro: Storage providers can always prove that they executed the message, even if execution fails.
3. Pro: Efficient on-chain validation.
4. Pro: Small messages.
5. Con: Expensive off-chain computation.

Notes: To ensure that the computation halts, the code would need to be instrumented with gas accounting logic before compiling it into a verifiable computation.

Verifiable Results

Alternatively, bounties could "return" some arbitrary proof. This is a strict super-set of verifiable computation and is significantly more flexible. For example, an actor could:

1. Return a custom, efficient merkle-proof (potentially more compact than a simple trace of accessed IPLD objects).
2. Operate over data encrypted with authenticated homomorphic encryption.

Unfortunately, it may not be possible to prove that some execution failed. That is, storage providers may execute an expensive bounty, then fail to claim it because the proof fails to validate (a DoS vector). Solutions include:

1. Optimistic verifiable results, falling back on verifiable computation to prove that an actor failed to produce a valid proof. When combined with a large deposit, this would remove the DoS vector.
2. Reputation and bounded execution.

Trusted Validators

In the trusted validators model:

1. The party fulfilling the bounty (likely the storage provider) would execute the bounty and perform the data re-hydration described above.
2. A set of validators would then fetch the re-hydrated data, validate the execution, and certify the results on-chain.

The primary downsides are:

1. The need for some set of trusted validators. A mitigating factor is that the client/provider can agree on the set of validators up-front.
2. The storage provider may need to send a significant amount of data to the valdiator.