The following structures are difficult to construct challenges for, and therefore I suggest we move them into a contract:
Delayed receipt queue. We might want to iterate on the design of it in the future, especially once we have gas auction. It will be much easier to have this logic encapsulated in the contract, since we wouldn’t need to pollute our code with compiler flags;
Data receipts. There is a large set of cases we would need to go through to prove that certain callback should or shouldn’t have been executed, especially when merged promises are involved;
Contract deletion. We would want to have certain logic around deleting very large contract state, potentially through a special transaction. It is easier to have this logic encapsulated in a contract.
Validator selection and reward mechanism. Though, constructing challenges might not be too hard for this computation, we might have lots of iterations on our validator selection algorithm, and it is better to have them contained in a Wasm file to prevent pollution of our codebase with conditional compilation flags.
Constructing challenges to all these operations would be easy, since the contract will be using the standard key-value API to work with the state, and we already know how to construct challenges to.
Implementation details
Implementation-wise this would be a regular contract that does not live in the state and does not have a state of its own, but it will have access to special host functions that will allow it to manipulate with receipt queue, issue validator rewards, etc.
We can also run this contract with LLVM or Cranelift to achieve close-to-native performance.
Consider a simple scenario of a delayed receipt queue (we are not even talking about priority queue based on the gas price). Suppose some validator executed all delayed receipts, but then at the end executed one extra that did not exist in the queue and we need to construct a challenge for it. We need to include into the state witness:
Path to the node that contains DelayedReceiptIndices structure;
All nodes(+paths) that contained Delayed Receipts that should’ve been executed;
One extra node (+path) to show that there is no more delayed receipts in the queue left.
This is already a pretty non-trivial special-cased state witness. And this does not even count the code for:
Other scenarios related to delayed receipt queue, like: repeated re-execution of a receipt, not executing the right receipt from the queue, terminating execution of delayed receipts too early, etc;
The code that deduces what kind of misbehavior was done so that it can choose the right challenge. (Noticing that state roots do not match is not enough for deciding which challenge to construct);
So for even a simple delayed receipt queue we are going to have a lot of protocol-level code with lots of case and correspondingly a very large surface area for mistakes.
Alternatively, we can have a contract that uses standard host functions like env:: storage_write/storage_read and imports Rust SDK that already implements a queue using these low-level simple operations. This contract would import a queue from Rust SDK to store the data receipts, and it will have a method next_delayed_receipt() that would return to native runtime the next delayed receipt to execute. We already know how to implement challenges for standard key-value storage that contracts use, so we don’t need to think about all corner cases of removing or adding an element into a queue. From the outside of the contract runtime wouldn’t even know what kind of data-structure it is using internally to operate with the delayed receipts.