StakeManager

In Autonomy, executors execute Requests in exchange for a fee. If anyone could execute any Request at any time, then the Nash equilibrium would be that, for a given Request that paid a $1 fee, executors are willing to spend up to $1 collectively in order to compete for that profit. That means that, overall, nobody is making any money, and results in a very fragile ecosystem of executors that cannot be relied upon and is dominated by very few actors who could censor Requests. For example, if an executor could send more transactions that attempt to execute a given Request, that resulted in a 25% chance of success for a $1 profit, they'd be willing to spend up to $0.25 out their own pocket to maximize their chance of success. If 4 people in total do that, everyone spends $1 in total, and makes $1 in total. These kind of mempool games were infamously described as the dark forest.

In order to solve this problem, Autonomy implements a lightweight Proof of Stake algorithm in the StakeManager contract that stakes the platform token, AUTO. Instead of 'winning' the ability to mine a block, stakers instead receive the exclusive right to execute Requests on the network for an epoch (100 blocks on Ethereum). The more stake that a user stakes, the higher chance they have of 'winning' this right. This essentially gives them to right to perform work and receive the fees without competition for the epoch. This economic incentive essentially guarantees that a Request will be executed. It is similar to Proof of Work and Proof of Stake in the sense that the incentive for the staker is to execute as many Requests as possible while they can in order to maximize profit, in the same way that PoW/PoS miners want to include as many transactions in their block as possible in order to maximize their profit. It is true that an executor could censor a Request, but the next executor will have an incentive to execute all Requests, and aslong as there is atleast 1 purely economically incentivized executor, every Request will eventually be executed. The same is true for PoW/PoS - miners can censor some transactions from being in their block, but eventually another miner will include that transaction. Therefore, if the ability for an entity to censor a Request is of concern to someone, then they shouldn't use a blockchain in the first place, because even if executors couldn't censor Requests, the transaction to execute that Request could still be censored by a miner, and therefore, Autonomy doesn't increase the ability for that to happen.

Staking

Problematic Approach

In order to stake, stakers can call stake in the StakeManager. In Autonomy, you cannot stake any arbitrary amount of AUTO - this is basically down to gas and block gas limit constraints. For example if stakers could stake any amount and 3 stakers staked 3, 69, and 420 AUTO tokens each, resulting in [3, 69, 420], the algorithm for selecting a 'winner', given a random number, would need to have knowledge of up to every element in this array. Iterating over an arbitrarily large array is prohibitively expensive, and could 'brick' the contract if the array gets so large that iterating it takes more than the block gas limit. For example, if a random number was obtained, and converted to a fraction of its maximum possible value, such as 0.415, then the algorithm would need to convert that to a proportion of the total. Assuming the total stake was cached (in this case, 492), this number would be 492 * 0.415 = 204. The algorithm would need to iterate through the array, calculating the cumulative total and checking whether that cumulative total is more than 204 as it goes.

Pragmatic Solution

In order to solve this gas problem, Autonomy uses constant sized stakes - STAN_STAKE - which is 10,000 AUTO. This means that the array of stakes is an array of staker's addresses, each element representing a single time they staked SNAN_STAKE amount of AUTO. Someone that stakes 20,000 AUTO tokens would therefore have 2 entries in this array, rather than having an array or mapping where each staker only has a single entry as in the 'Problematic Approach' case. For example, the stake array would look like [addrA, addrB, addrB, addrC] if addrA staked 10k, addrB staked 20k, and addrC staked 10k. This allows the fraction (0.415) to be multiplied by the length of the array and instantly obtain and index of the winner: 0.415 * 4 = 1 = addrB (in Solidity, all decimals are dropped, as everything is an integer). Stakers are forced to stake in increments of STAN_STAKE, but the tradeoff is that selecting a 'winner' is constant time and very low gas, which is important since this happens every epoch.

Epochs

The epoch as a number is basically defined as the starting block number of an epoch. For Ethereum, since the number of blocks in each epoch (EPOCH_LENGTH) is 100, the epoch for block 420 is 400. The epoch for block 39487969 is 39487900. This means that epochs increase in increments of EPOCH_LENGTH rather than in increments of 1.

Randomness is obtained using the blockhash of the block just before the start of the epoch. For example, for epoch 400, the blockhash used is from block 399, and for epoch 39487900, the blockhash used is from block 39487899. This is done so that the randomness used for a given epoch cannot be manipulated from within that epoch. It is true that blockhashes can be manipulated by miners, but this is expensive to do in PoW, and does not affect the security of Autonomy, since the only benefit to manipulating the randomness is to be able to be selected as the executor more often than otherwise and therefore be able to receive fees from a larger number of Requests. Once Ethereum moves to PoS itself, this mechanism will be changed to a randomness source more secure.

It's a bit annoying that epochs go up in increments of 100 instead of 1, but the reason for this is because of how randomness is obtained. Since the blockhash for block epoch - 1 is the source of the randomness, an epoch that increments by 1 would be 4 for block 420. Solidity is constrained to only be able to lookup information about the previous 256 blocks. Therefore from block 420, it is impossible to look up information about block 3 from within the smart contract. This necessitates the source of randomness to be within the last 256 blocks, so that's why the epoch number needs to be within 256 of the current block number.

Caching The Current Executor

Once the current executor is selected, their address is stored in StakeManager, along with the current epoch , partly because of gas savings from using it as a cache, but mainly so that it cannot be changed within the epoch. For example if someone updated the executor for the first time in the epoch at block 420, and someone came and staked some AUTO at block 421, then the result of selecting the executor might change because the array and its length has changed. Certainty of who is executing at what time, without that being able to be manipulated, is necessary. For that reason, every time someone stakes or unstakes, the executor for that epoch is selected (if they haven't been selected for the epoch already) before any changes are made to the stake array. This guarantees that nobody can unfairly manipulate who is selected as the executor, essentially making the executor for that epoch deterministic from the start of that epoch.

The way that execution of Requests actually interacts with the StakeManager is by all executions calling isUpdatedExec before doing anything else. If the executor is already set for this epoch, this checks whether the current executor is the set executor - if not, revert. If the executor for this epoch hasn't been set, then set it, and check whether the current executor is the new set executor - revert if not.