Source of randomness for selecting relayers

[s1na]

Hey everyone, this is a challenge we were exploring with @Perseverance for one of the possible solutions (read more about the general solution here) for the collision problem. Would love to hear whether you think something like this could work, or a more complex PRNG is required.

Introduction

One of the directions under consideration for the collision problem is to have relayers register on-chain, put a stake, and have the protocol randomly select a relayer every epoch to submit a batch of meta txes to a smart contract. Selecting a relayer on-chain requires a source of randomness that can't be predicted ahead of time or manipulated in a way to increase a relayer's chance of getting selected.

Problem Statement

Given a list of relayers R = [R_1, R_2, ..., R_n], and function isTurnOf(R_i) which returns true if R_i can produce a block during this block (B), we'd like to discuss employing the parent's block hash (P_h) as a source of entropy in isTurnOf, e.g. by checking if R[uint256(P_h) % n] == R_i. Using P_h is usually not a good practice, due to the following reasons:

1. Miners could withhold a block, if the block hash is disadvantageous for them.
2. During B, P_h is known, and therefore, users (and specially miners) can make transactions to influence the decision in isTurnOf.

Discussion

In the case of selecting a relayer:

1. The reward a miner would forego by withholding a block, is probably significantly than the reward of a batch of meta txes (also depends on the number of meta txes in a batch).

2. In the simple isTurnOf mentioned above, if R is mutable, the miner could create the transactions and add them to the beginning of the block to influence the decision (if it's their turn to propose block). This might seem like a very unlikely case to assume such collaboration between a relayer and a miner, but, I think a considerable percent of relayers could also be miners (as miners are running a full node anyway and the marginal cost of running a relayer is low).

Possible Improvements

Two general approaches could help with problem 2.:

• Fix R, for at least one block before B, e.g. if a new relayer calls register, or an existing relayer calls withdraw, they are put on a queue, that is processed the next block.
• Modify isTurnOf to make it unpredictable for everyone but the relayer who should submit batch now. For example, have each relayer commit to a random value (e.g. keccak256(S)) on register, and on every execTransactions, and pass that to isTurnOf(R_i, S). This limits miners to only knowing whether it's their turn this block or not, so it becomes harder for them to influence the decision by front-running. However, because nobody but the relayer knows whose turn it is, it becomes hard to punish relayers for not submitting blocks, if this is required by the protocol.

Extension

The simple protocol outlined above can be further extended in various ways. One particular extension, is to select a shuffled subset of R (D for dynasty) every M=32 blocks, in which, isTurnOf(D_i) == true in block B_i where 0 <= i < M.

[s1na]

@PhABC your input is appreciated.