Building a decentralised p2p meta-tx relayer network [MVP] Codename: Harbour ## We solved this problem: https://medium.com/tabookey/1-800-ethereum-gas-stations-network-for-toll-free-transactions-4bbfc03a0a56
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:
Miners could withhold a block, if the block hash is disadvantageous for them.
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:
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).
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
commented
6 years ago
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 functionisTurnOf(R_i)which returns true ifR_ican 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 inisTurnOf, e.g. by checking ifR[uint256(P_h) % n] == R_i. UsingP_his usually not a good practice, due to the following reasons:B,P_his known, and therefore, users (and specially miners) can make transactions to influence the decision inisTurnOf.Discussion
In the case of selecting a relayer:
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).
In the simple
isTurnOfmentioned above, ifRis 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.:
R, for at least one block beforeB, e.g. if a new relayer callsregister, or an existing relayer callswithdraw, they are put on a queue, that is processed the next block.isTurnOfto 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)) onregister, and on everyexecTransactions, and pass that toisTurnOf(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(Dfor dynasty) everyM=32blocks, in which,isTurnOf(D_i) == truein blockB_iwhere0 <= i < M.