Meta-tx propagation in a decentralized relay network (collision problem)

[s1na]

Hey everyone,

Note: I didn't know any other place to put this to discussion. If it doesn't belong in this repository please let me know and I'll delete it. The goal is to discuss some of the proposed solutions, put forth new ideas, etc.

Challenge

When a user publishes a meta transaction to a decentralized relay network, there'll be a competition among the relayers to submit the transaction first, and thus get the reward. As only the first submitter gets a reward, everyone else's transaction reverts and they lose gas, and this inefficiency would cause the relayers to demand a higher price.

Possible solutions

Stake by users and relayers

• User publishes intent for a meta transaction to a pubsub channel
• Relayers would respond that they're interested in submitting this tx to network
• User acknowledges the request of one relayer, who in turn submits the tx and is rewarded
• To prevent relayers from showing interest, but not submitting the tx, they put a stake, that would be slashed in case of misbehaviour (not submitting within a time frame).
• To prevent users from acknowledging the request of multiple relayers, the user is also required to put a stake.

Considerations
There are however some edge cases to consider in this approach. For example, how to require a newly registered user to put a stake, and doesn't that affect UX? Can the user grief relayers by responding late so the relayers don't have enough time to submit the tx? Can user be caught when doing this? Generally, it seems to me somewhat difficult to distinguish between malicious act and network delays.

PoW

• User publishes meta transaction to a pubsub channel.
• Relayers try to solve a PoW challenge, and the first one who solves the challenge gets to submit the transaction. This acts as a kind of rate-control mechanism.

Considerations
This approach would probably need a dynamic PoW difficulty. Cost of energy needs to be factored in, which results in relayers asking a higher price. Requires on-chain validation of the proof, which means it requires modifications to the existing identity proxies.

Simplified PoS

Relayers register as such on-chain, and a psuedo-random number generator selects a relayer or a committee of relayers to submit transactions in a timeframe. I'm still doing research on this.

[austintgriffith]

This is a perfect place to put this and the first thing everyone talks about when I get on the phone and start talking meta transactions!

The current solution in my head is the first thing you listed. A node announces they are going to submit and they have some stake on the line that can be slashed if they fail.

At first I wanted to look through the pending transaction pool but that isn't always going to be complete and it would require a lot of work/resources from the relayer.

Which leads to my point against PoW... It would be great to run these relayers on very cheap hardware. So far the only requirement is basically an internet connection. If we start to put the need for hash crunching on these devices, costs could shoot up and our pool of miners would be smaller. Maybe that's still the solution and I'm all about finding the best answer.

I would love to hear how others are solving this or are planning on solving this!

[austintgriffith]

And to directly contradict myself, what if we went with a PoW + batched meta transactions model?

Relayers package up a bunch of meta transactions into a "block" and mine for a leading zeros nonce. Once they have it, they submit it as a single transaction to a relayer contract that verifies, splits, and relays meta transactions.

[s1na]

@austintgriffith Will give it some more thought, but so far I like the PoW + blocks of meta transactions!

One of the direct benefits of having a relayer contract, is that it wouldn't be necessary to modify identity proxies to verify PoW anymore.

Regarding the refund, were you thinking it should stay as it is now? Relayer is refunded by the EIP-1077 contract at the end of executeSigned?

Alternatively, the relayer contract could also deposits which would be used to refund the relayer. However this introduces the complexity that the deposit needs to be topped-up every once in a while. Another edge case would be, what happens if one transaction within the block doesn't have enough deposit to refund relayer?

[austintgriffith]

I think the answer to this is like many in the metatx space right now; it depends on the app. Let's try to come up with and a flexible standard that can effectively handle different use-cases. I think I will start a new issue for flexible rewards and we can use this thread to create a narrative behind relay collision prevention. Dynamic Gas Rewards: #4

[pet3r-pan]

We designed ours with staking and slashing in mind. Currently exploring the ability to stake various amounts so that Tx distribution is based off on how much is staked/risked.

[pet3r-pan]

I would also like to rename this issue to "Meta-tx propagation", sybil isn't the right descriptor. It is not about spam attack but rather about how to select which service nodes gets which tx, what is determinate of it and how frequently.

Was thinking that different service nodes could potentially have their own means of queing and meta-tx prioritisation as opposed to having the logic exist on the network layer. Since SNs stake, they must send out a message 'claiming' the meta-tx to be sent, this message is received by other participants and the meta-tx is flag to not be executed. This however brings up the issue of consensus for the claims themselves.

+1 to batched POW txs

[radek1st]

Another aproach I was thinking about is to create some algorithm for allocation of the relayers to users. Simplest idea:

• All known relayers register with a service (public list of all relayers)
• User ask the service for a relayer which gets picked by the algo
• User submits the tx to provided relayer

Challenges:

• Make it trustless
• Tweak the algo for low fee relayers

[lightclient]

I feel like staking and slashing may be overkill and could disincentivize people to create relayers. Please correct me if I am wrong, but if multiple relayers attempt to issue the same transaction only 1 will be mined on-chain and the others will fail due to the nonce being out of sync. In this case, miners already lose the gas fees for issuing the transaction. I think an approach similar @radek1st's suggestion would be more economical.

[s1na]

This thread has some ideas for the same problem, but a different context. To quote:

I believe most of these concerns are addressed by having an operator or close set of operators and a deposit/withdraw queue.

One option would be to require relayers to reserve the chain for a period of 2 blocks (possibly <30000 gas cost) before they can submit a block.

I include them here, so we can consider them in the discussion.

[s1na]

@radek1st I think an approach like the one you suggested definitely works around some of the challenges quite elegantly. As you mentioned, making it trustless is a challenge however. Here are a few thoughts about difficulties we might face when designing such a system:

• Relayers can register many accounts to increase their chance of getting picked. To prevent this, some stake could be required.
• Assuming unique relayers list, it's really difficult to securely pick one randomly. On the bright side, this is being heavily investigated for casper.

We can also combine this with batched txes:

Randomly pick a relayer who submits all the txes that have been published to the relay network, but not submitted on-chain recently, in a batch (block). The reward system might get more complex as a consequence of this however.

[lightclient]

Assuming unique relayers list, it's really difficult to securely pick one randomly. On the bright side, this is being heavily investigated for casper.

I had a DNS-like setup more in mind. Using a root contract with a list of available relayers (or relayer pools?), the client could come up with a random relayer to process their transaction. Clients are incentivized to choose whichever relayer can process their transaction cheapest / quickest, and choosing randomly would probably find the best relayer on average.

[pet3r-pan]

• Previous chat logs about this issue https://hackmd.io/kJISew3BS3KqFAhLjT7yow

[PhABC]

@kosecki123 @lsaether ^

[lsaether]

I've thought about a fews ways which have different assumptions on how the meta-tx data gets passed to relayer services.

1. Decentralized / permissionless / near total data availability. Anyone can become a relayer and everyone has access to the data (delivered for example by Ethereum state or event logs). This is essentially what the TimeNode network on the Ethereum Alarm Clock looks like now. The major problem is transaction collisions which if you're not familiar with the term just means more than one relayer attempting to execute the tx during the same block and all but the first one to get mined will be reverted. We've patched this in EAC by doing a check in the transaction pool for other transactions of the same data. This is an imperfect solution because network latency will always cause a lag in the transaction pool data and therefore leak transaction collisions. A true solution would be running consensus among relayers, which either imply trust (traditional consensus models / PoA) or basically require a sidechain (PoW / PoS). I could be wrong about this though.

2. Decentralized / permissionless / selective data availability. Relayers would run their own services. These services can be closed services, or services running their own consensus internally (akin to relayer pools). Users would pass their signed messages "selectively" to a relayer. The main problem here is the lack of data redundancy, so if the selected relayer fails to publish the meta-tx, the transaction won't go through. This is a problem most notably for time sensitive transactions that need to go through during a specific window of time. Another attack regarding this model: User can send their meta-tx to many relayers. If the relayers don't communicate with each other, they will each attempt the publish of the meta-tx. We hit transaction collision.

Thanks @PhABC :) Saw the tag go up live-- was literally typing this up when you posted.

[PhABC]

Few thoughts ;

1. PoW is probably OK, but might increase the cost for everyone, i.e. rewards will need to be high enough to compensate for mining cost and mining cost need to be high enough to effectively prevent collisions.
2. There are a few main problems that need to be addressed :
   2.1. Execution collision : Two relayers or more trying to fill a tx at the same time
   2.2. Execution reliability : If I schedule a tx for a certain date, I should have some level of confidence that the tx will be executed in time.
   2.3. Long term storage : If I schedule a tx that should be executed in a few months, I should have some level of confidence that the transaction will not be forgotten. I.e. if the relayer set is replaced completely, my tx should still be available (echoing Logan's point on data availability).
   2.4. Efficiency : The lower the cost to operate, the smaller the rewards can be and the less clogged the network will be.

2.1, 2.2 and2.3 are fundamental issues that need to be solved imo, while 2.4 should be kept in mind. However, all can be improved overtime.

[pet3r-pan]

Relevant https://ethresear.ch/t/incentivizing-a-robust-p2p-network-relay-layer/1438

[jamesray1]

Relayers register as such on-chain, and a psuedo-random number generator selects a relayer or a committee of relayers to submit transactions in a timeframe.

Yes I saw this link in https://medium.com/@pet3rpan/harbour-mvp-update-1-35ddbbb9e288 and came here to propose the same idea. Mind you, it doesn't need to be an RNG, but any publicly verififiable random function, such as RANDAO as used in Eth2 shasper beacon chain (which you could use as the source of randomness).

Also, https://pokt.network are designing a blockchain that will be used to incentivize relays, and is intended to be compatible with other blockchains.

[s1na]

@jamesray1 thanks for the comment. I will take a look at pokt.
I was also thinking about RANDAO for the source of randomness, but then I wondered if something simpler, like parent's block hash could also be utilized. I'd appreciate your comment on this, if you can see any attack vectors for example.

[jamesray1]

Things to think about include manipulability of the randomness e.g. by withholding a block in order to increase the likelihood of winning a block in future, and gradually being able to win more blocks, make more profit and gain more power over the network. Also collusion of proposers. Ah I see that you have considered that in #13, but it looks like you haven't got a convincing solution, at best they need further consideration, but I think it would be simpler to use the beacon chain as the randomness source (while scrutinising it yourself to understand how it's more secure and could be made more secure e.g. to reduce the chance of a safety failure by increasing the number of validators in a committee. https://github.com/ethereum/eth2.0-specs/blob/master/specs/beacon-chain.md https://github.com/ethereum/eth2.0-specs/blob/master/specs/beacon-chain.md CTRL+F 111. Also look up on ethresear.ch: - Verifiable random delay function - RANDAO manipulability analysis

[s1na]

@jamesray1 Yeah exactly, I'm also wondering if forgoing the block reward makes sense for miners, given that the reward they'd get from meta txes are probably much lower.
Can you please elaborate on collusion of proposers?

[jamesray1]

What if the block reward reduces to near zero as is planned/proposed with a max supply cap? I don't think you understand. By foregoing the block reward they can manipulate the entropy in their favour to make it more likely that they will be selected in future, and they can increase their profits and power incrementally and potentially take over the whole network, bit by bit.

https://ethresear.ch/t/verifiable-delay-functions-and-randao-manipulability/3777

A proposer could form a cartel whereby they may collude with the next proposer, and so on, in order to increase their chances of being drawn. FMI see https://ethresear.ch/t/rng-exploitability-analysis-assuming-pure-randao-based-main-chain/1825/2 and https://ethresear.ch/search?q=collusion%20randao.