Relayer network governance and anti-collision approach

[Perseverance]

Introduction

The goal of this issue is to be a facilitator of the conversation over securing the relayer network. It will outline an approach proposed by me and @s1na and hopefully we can improve it.

Problem statement

An attacker can drain the capital ETH of the relayers in the relayers network by submitting one transaction to be relayed to multiple relayers.

An example of such attack would be, malicious attacker sending one and the same request for relayed execution of a transaction to multiple relayers. Normally all relayers will check the execution of this transaction and decide that this transaction will legitimately go through successfully.
However, only one of the relayers will successfully execute this relayed transaction, due to the nature of the blockchain and anti replay attack mechanisms, the other relayers will lose ETH due to the reverting of the already executed transaction.

Discussion

General overview

By nature, this problem is a synchronisation problem. In general, if all the relayers in the network are synchronised, they will be able to tell who is processing which transaction. Such synchronisation, in real time would be exponentially harder with each new relayer.
Approaching this problem from another angle we've reached the conclusion that this problem can be solved through ordering.

Ordering

Another way to solve the problem is to remove the chaos of every relayer executing transactions all the time. Instead we can allow for one relayer to relay transactions per block(The proposed mechanism of finding the relayer allowed to relay will be found in the following Proposed Solution section). This requires some additional capabilities of the relayers in addition to the plain relaying:

Gossiping received transactions

In order for the network to work as fast as possible, the relayers would need to gossip each other the relayed transactions they receive from the dapps. This will allow for the relayer of the next transactions to include these transactions in the next block ensuring high responsiveness.

Maintaining list of transactions to be executed

All relayers will need to be able to maintain list of transactions to include in the next block. In addition the relayers would need to watch for submitted relayed transactions, in order to guard against resubmitting transactions.

Proposed solution

The proposed solution is based on pseudo-random round robin way of choosing the next relayer. Randomness of the round robin will be ensured by the block-hash of the previous block. Although this can still be manipulated, it becomes very impractical for a miner to collude with relayer as the economical incentive of producing a block would generally much higher than the economical incentive of relaying transactions. Read more here #13.

In addition a staking smart contract needs to be created. This smart contract will have several important functions. Firstly, it will allow for relayers to register as such, via placing a stake. Secondly, this contract is going to be the verifier of which relayer is the current eligible relayer. The identity smart contracts would need to additionally poll this contract verifying the current msg.sender against the eligible relayer.

Possible improvements

There is a need to figure out a way to punish dishonest relayers that are withholding transactions (not gossiping) until it's their time to submit into a block.

[jamesray1]

The proposed solution is based on pseudo-random round robin way of choosing the next relayer.

A round robin is too insecure IMO. See e.g. https://vitalik.ca/files/randomness.html for more info.

[jamesray1]

Randomness of the round robin will be ensured by the block-hash of the previous block. Although this can still be manipulated, it becomes very impractical for a miner to collude with relayer as the economical incentive of producing a block would generally much higher than the economical incentive of relaying transactions.

You are assuming that the miner and relayer are separate entities, but when they aren't, "Euston, we have a problem". A similar problem occurred with https://ethresear.ch/t/exploring-the-proposer-collator-split/1632. Thus, a similar situation can be expected to occur where actors acting only as relayers cannot compete with miner-relayers (who will manipulate the randomness), and so miners relay all blocks, which they do anyway (but just get an extra reward for it).

OTOH, if you use the RANDAO beacon chain with a verifiable delay function as a source of randomness, that should be much more resistant to manipulation. FMI see https://ethresear.ch/t/verifiable-delay-functions-and-randao-manipulability/3777.

[Perseverance]

@jamesray1 That is incredible. I will definitely educate myself more on the matter. The RANDAO chain is only a concept for the time being, right?

[jamesray1]

There is a need to figure out a way to punish dishonest relayers that are withholding transactions (not gossiping) until it's their time to submit into a block.

Good idea, you could have a time limit that is higher than the expected latency (say, even in a high latency location like a remote mountain to allow for decentralization), and by extension, the maximum time taken to propagate a message between two nodes that are furthest apart in the network (using gossipsub you can make sure that the degree of the network is within a certain window and is stabilized towards a target degree, and if it is submitted beyond this time (maybe plus a safety factor), slash the relayer's deposit.

[jamesray1]

That is incredible. I will definitely educate myself more on the matter. The RANDAO chain is only a concept for the time being, right?

It is more than a concept but not on the main net yet.

https://github.com/ethereum/eth2.0-specs/blob/master/specs/beacon-chain.md

https://github.com/ethereum/wiki/wiki/Sharding-introduction-R&D-compendium#implementations

[s1na]

@jamesray1 Is RANDAO necessary? Can't we make the randomness unbiasable by using the output of a VDF over, say the hash of N blocks ago, to determine the current proposer?

Side note: we're also starting a gitter channel for the collision problem, if you'd like to join.

[jamesray1]

@jamesray1 Is RANDAO necessary? Can't we make the randomness unbiasable by using the output of a VDF over, say the hash of N blocks ago, to determine the current proposer?

Creating a gitter channel for the problem seems like overkill, IMO, but I have joined the room. I'm not sure how secure using a VDF with a round robin that can be manipulated is, but I think the additional complexity with implementing RANDAO is worth it, and I don't think it should be that hard to implement.

[jamesray1]

Additionally you still have the disadvantages of round robins as listed in https://vitalik.ca/files/randomness.html:

• No denial of service resistance: because validators can be predicted ahead of time, attackers may be able to target denial-of-service attacks against each validator during the timeslot during which they are supposed to create a block.
• Extreme ease of planning "selfish mining" strategies: an attacker can clearly see any contiguous ranges during which they, by random chance, have more validators than all honest actors, and can use this information to consistently force other validator's blocks to get kicked off the main chain as they can create a longer chain.
• Ease of planning medium-length forks: an attacker can capture a large contiguous sequence of K < N validator slots, and thereby force the previous K-1 blocks to be reverted. This means that no practical notion of "de-facto finality" can be achieved in less than N / 2 blocks, and in a public chain N can be quite large; no "six confirmations" for you.

I don't think using a round robin solves any of those issues.