[V2 Bridges] Coordinated relayers protocol for cheaper relaying

[svyatonik]

related: #316 (comment) , #377, #439, #954, #978

So now if there are multiple concurrent relayers (we're mostly talking about message relayers) running, one/some would lose their funds because of overlapping transactions. I'm opening this issue to track all related discussions/questions and not to lose any information about that.

Specifically - I'm now working on non-altuistic relayers and if we'll be considering sessions+elections as suggested here, then we shall not treat not delivering message M as misbehavior if delivering message is non-profitable (e.g. because of conversion rate change). This would require some non-profitability proof (exchange rate) or some other strategy.

I'm also thinking of single-tx sessions - when relayers are announcing their intention (backed by their funds) to submit single delivery transaction. And either best offer wins (e.g. offer that promises to deliver most messages in the shortest number of blocks), or, if there are several equivalent intentions, only one is picked.

[tomusdrw]

A random thought that I had just now might be to have some round robin mechanism which in general makes delivering messages slightly more expensive for everyone except for the relayer with a "winning ticket".
This can be based on relayers public address and could decay over with time - i.e. there is more winning tickets over time.

With this in place it's always possible to deliver messages (albeit more costly), but there is a bit of "election" mechanism built-in, where with multiple relayers some of them are initially more priviledged to deliver messages.

[svyatonik]

So there are two problems imo - what to do when someone except "winning ticket" owner deliver messages? And how to choose "winning ticket" owner?

With first problem, there's one major decision needs to be made - whether we allow competition here or not. IIUC what you're suggesting allows relayers to deliver messages even without owning "winning ticket". And the only thing that stops them is lowered reward, right? But don't you think that relayers will still compete (by submitting delivery transactions with larger fees) and will only stop when the delivery tx cost will be larger than the reward? And imo it is better to avoid that - delivery transactions are not cheap.

So regarding first problem, my suggestion is to only reward "winning ticket" owner, ignoring relayer who has actually submitted delivery transaction. So if current "winner" is relayer1 and it is relayer2 who has actually delivered messages, we will still reward relayer1. This moves competition from heavy delivery transactions to somewhere else (to be clear - to the procedure where we're selecting this "winning ticket" owner - see below).

The second problem (winner selection) has many solutions imo - "proper" elections and slots, round-robin, delivery promise, ... With elections and round-robin there's a sub-problem - since messages are born at chain1 and selected relayers are submitting delivery transactions to chain2, there's no direct way to know (at chain2) if the relayer has failed to deliver any messages in his slot, or if there were no messages at all. This would require additional proof to be delivered from chain1 to chain2 (proof-of-no-messages or proof-of-relayer-misbehavior), and this transaction must be paid by someone. I'd prefer to avoid this.

For initial version, I'm suggesting a separate module with three entrypoints:

1. signed bond(relayer-aka-origin, amount) call - locks amount on relayer account;
2. signed unbond(relayer-aka-origin, amount) call - should fail if relayer has pending promises;
3. most probably unsigned (to avoid extra costs) delivery_promise(relayer, instance, lane, in_blocks, (messages_count, messages_size, messages_dispatch_weight)). The verification should be cheap - we'll just need to compute cost of delivery transaction and check if relayer has enough bonded funds.

So normal relayer would call bond once, then will submit unsigned (free) delivery_promise() transaction every time it sees undelivered messages. Initial 'promise' may be beaten by the other relayer in, say, next 4 blocks. The winning 'promise' is the promise with largest messages_count, tie is broken by lowest in_blocks, and if it is still tie, then then earliest promise wins. If relayer doesn't keep a promise, his funds are burnt. If messages are delivered without active promise, then the reward is burnt.

Later we may plug some reputation/round-robin/election mechanism to this pallet. But imo it is good and simple enough for the beginning.

I'll leave this comment here for couple of days (before actively working on that) for @tomusdrw + @HCastano review.

[tomusdrw]

But don't you think that relayers will still compete (by submitting delivery transactions with larger fees) and will only stop when the delivery tx cost will be larger than the reward? And imo it is better to avoid that - delivery transactions are not cheap.

Yes, and I actually think that the ones with winning ticket should initially be only ones for which delivering the transaction would be profitable. Basically the goal is to create some kind of ordering over all possible accounts. I would prefer not to have the relayers register, but at the same time never cause a situation where the bridge cannot make any progress (even at high costs).

And how to choose "winning ticket" owner?

What comes to my mind is something that works similarly to this (note this is just from the top of my head and might require a lot of analysis to get security & incentives right).

1. At block N (for instance last submission) we store on-chain randomness R (since randomness does not chain that often instead we might store X = hash(R) ⨁ parent_block_hash for instance (⨁ = XOR)).
2. Now when we receive submission at block M we set Y = 33 - count_ones(X ⨁ hash(sender_address))
3. Based on some data we compute the decay factor as D = M - N (For simplicity let's assume for now this is just this simple subtraction)
4. Then we compute the actual fee as FEE + c * FEE * max(0, Y - D).

So the idea is that if you are lucky, you will pay just the regular FEE right from the start, but others would need to overpay. Over time there will be more and more "winning tickets" that get to pay the same amount of fee as you do. Obviously this doesn't have to be linear even and we need to carefully choose constants (or even have them dynamic based on number of unique relayers), but it's here just to get the point.

Obviously the relayer can generate as many accounts they want to get "winning tickets" more frequently, but:

1. You need to keep this accounts above ED or make a transfer to these accounts before submitting a solution (you could maybe do it in one transaction by creating a proxy account and using batch?), and that obviously increases the costs a bit.
2. By having everyone sybil attacking the system we risk more collisions (we can also adapt parameters based on number of collisions maybe) so it is a slight incentive for the relayers to keep this reasonable.

Overall I'd really like to avoid adding any more pallets to our bridge system and also avoid bonding the relayers. But yeah, if we can't come up with anything better, then maybe there is no choice here.

Also pinging @AlistairStewart, maybe you have some time to chime in.

[svyatonik]

We'll probably start with signed extensions for our pallets (see #1352 for example), so I'll move this to future milestone

[acatangiu]

this is done now

[svyatonik]

this is done now

I have to disagree :) What we have now is just a guarantee that relayers won't lose their tokens if they're honest. This issue is about relayers coordination - i.e. some protocol that allows relayers set to coordinate their actions, get some reward (that's what we miss now) and potentially make bridge operations cheaper.

I don't think we have other issue for that.

[svyatonik]

Possible idea: [V2 Bridges] Alternative model for relayer rewards - Open Market paritytech/parity-bridges-common#2424

[acatangiu]

Slava is right, this issue is actually discussing how to build a smarter relayers protocol that would coordinate them to get fair but also efficient/cheap relaying

[svyatonik]

Some thoughts: https://gist.github.com/svyatonik/398bfd306541b693fe5afe37dc68f908. I'll start implementing something like that. Will need to do some refactorings before

[svyatonik]

Some thoughts: https://gist.github.com/svyatonik/398bfd306541b693fe5afe37dc68f908. I'll start implementing something like that. Will need to do some refactorings before

One important thing that I've missed in proposed design is that we may need to implement both stages simultaneously before v2. Otherwise if there are many opened lanes, we may face the issue when batch transactions ([submit_finality_proof, submit_parachain_heads, receive_messages_proof]) fail because GRANDPA and/or parachain finality has been already updated by another relayer, serving another lane. This could limit the bridge throughput to serving one lane per BH block, which is fine for v1, but not fine for v2.

Ideally (imo), we'll move finality relay to collator. Other options is to allow 1 free bridged finality submission for every N blocks (N may even be 1 here) + do not use refund mechanism for batch transactions.

UPD: extracted to separate issue #2586