Approaches on Keeper Selection
Last updated
Last updated
An important step in the process of automated task execution is to select one of the many candidates on transaction execution. The exact algorithm depends on the system architecture and desired outcome.
For example, one could simply pick an executor by random.
PowerAgent v2 utilizes the so-called Gas Wars (or Gas Auction) mechanism: every candidate offers the gas price it is willing to pay for the transaction, and the winner (with the highest gas price, hence the highest priority transaction) is chosen to execute the transaction. The executor then receives the compensation for the gas spent, derived from the average block gas price. This method can be seen as a reverse (Dutch) auction on the pure keeperâs profit, as the compensation is fixed and offering higher gas price reduces the total income of the keeper.
With V2.1 update and introduction of new algorithms of task distribution, a new approach to keeper selection is needed. In this research, we examine the aspects of keeper selection and give a brief overview of the algorithms used.
Suppose we want to choose an arbitrary known number of keepers. This problem can be reduced to selection of only one keeper, as we can simply exclude the selected keeper from the set and repeat the process of selection. So, we will cover only the problem of selecting a single keeper from a known set of many.
Selection of a keeper is equal to constructing a total order on the keeper set, and the question posed is about the rule for constructing it. In simple terms, we have to find (mathematically) a way to order (rank) the keepers, so that every keeper has a unique position in this ranking. This ranking can be deterministic or stochastic, with the latter entailing usage of chain-generated pseudorandom numbers. The mechanism by which such generation is carried out will be covered in the next sections.
Deterministic rules must necessarily rely on some property of the keepers amenable to construction of a total order. Such properties could be:
Gas provided by a keeper (used in Gas Auction);
Stake;
Task execution count and history;
Reliability (defined as the ratio of successfully executed tasks to the number of times the keeper was picked, or in any other formulation);
Any function and combination of the above.
All these rules have the undesirable property of being predictable and therefore vulnerable to manipulation by malicious actors. In addition, it is hard to define a total order on a subset of keepers who have identical properties with the exception of their enumeration without producing outcomes likely to be perceived as unfair.
Stochastic rules can be constructed from deterministic rules by multiplication with a probabilistic weighting term or composition with random processes. In addition, an entirely stochastic total order involving no keeper data can be constructed (e.g. uniformly random choice). Hereafter a number of approaches are outlined in simple language. It is understood that the set of viable keepers consists of those keepers whose stakes are no less than a task-specific number.
Gas auction keeper selection works by constructing a total order based on the amount of gas a keeper proposes to spend on the transaction that executes a given task. It has the desirable property of ensuring automatic selection by virtue of the miners behaving (approximately) rationally. However, this rule means reversion of all transactions not included in the block and can incur great losses to the unsuccessful keepers.
The gas auction can be improved by using the Flashbots pool instead of the regular mempool. Though it does create a point of centralization, it also diminishes the potential loss of gas on transaction reversion because reversions are costless in that pool.
In addition, it is desirable that the gas bids are opaque to the keepers, which diminishes the effect of producing vigorous betting. It is interesting that the empirical observations attest to the effective total order being induced by a combination of the gas bid and the ping to the Flashbots server, which produces the undesirable effect of shrinking the effective pool of potential keepers over any finite time horizon. Furthermore, the privacy afforded by Flashbots makes it impossible to employ punishment of those keepers who behaved maliciously or failed the task.
Here the total order is constructed by producing a random number drawn from a uniform distribution, allotting the greatest rank to the keeper corresponding to the number drawn, and allocating smaller ranks to other keepers in a largely arbitrary fashion so that the order is total.
Or, in other words, we index every keeper from 1 to N (number of all keepers) and query a random number in this range. The obtained number is the index of the keeper chosen.
This approach has the benefit of being simple to implement, especially when the chain possesses a native random number generator but fails to properly provide incentives to big stakers, this means every keeper is selected with an equal probability regardless of the keeper's stake size, and deterrence of malicious actors alike (though the latter goal may be achieved by setting great minimal stakes, it may be inconvenient for the task owner).
Here, as before, the total order is constructed by drawing a number according to some probability distribution, but now this distribution is not uniform, instead being induced by some deterministic function of the keeper properties. This approach is of great interest, and we have judged it fit for implementation.
