Reducing bridge fees: short and long term options

[svyatonik]

Bridge fees will be quite high in initial deployment. Omitting parts, that are not relevant to the bridge itself (transfer_assets transaction cost, HRMP, potential increased fee factors, ...), the fee consists of:

---

For Polkadot -> Kusama message is 1.93 DOTs:

1. cost of XCM execution at Polkadot BH: 0.01 DOT (which has been decreased significantly from 0.48 DOT in [xcm] Fix SovereignPaidRemoteExporter and DepositAsset handling polkadot-sdk#3157). Link
2. cost of message delivery transaction at Kusama BH: 0.06 KSM, converted to 0.3 DOT. Link
3. const of message confirmation transaction at Polkadot BH: 1.62 DOT. Link

---

For Kusama -> Polkadot message is 0.39 KSMs:

1. cost of XCM execution at Kusama BH: almost zero (0.0004 KSM). Link
2. cost of message delivery transaction at Polkadot BH: 1.7 DOT, converted to 0.34 KSM. Link
3. cost of message confirmation transaction at Kusama BH: 0.05 KSM. Link

---

Those costs are at least 33% above the computed value. We have overestimations in other places as well - e.g. the authorities set on Kusama and Polkadot is set to 1_256 to account for potential future changes. So we can easily decrease the fee by ~40%, but it could lead to situation when message senders pay fee that doesn't cover costs, paid by the relayer and since relayer compensations (and rewards) are paid by the Asset Hub "treasuries" (sovereign accounts), we could end up with those treasuries going bankrupt. So we prefer to keep those overestimations.

The major portion of bridge transaction (message delivery and confirmation) fees is the cost of GRANDPA finality proof submissions. E.g. for Kusama -> Polkadot message delivery transaction, the cost of GRANDPA finality proof submission is almost 93% of the total transaction fee. And then, only 10% of this cost is the execution fee - the other 90% comes fom the GRANDPA justification size (which is assumed to have signatures of 2 * 1_256 / 3 + 1 validators).

This issue describes some options we have to decrease the cost of this GRANDPA finality proof submission and hence, the cost that the message sender pays for the message.

Possible Short Term Solutions

Only Relay Mandatory Headers

The bridge requires some relay chain headers to be relayed. Those are called mandatory headers and they are headers that change the GRANDPA authorities sets. Such header is emitted every 4 hours at Polkadot and every 1 hour at Kusama. Since the system relies on those headers, their submission is free:

parity-bridges-common/modules/grandpa/src/lib.rs

Lines 304 to 312 in 06f2520

	// mandatory header is a header that changes authorities set. The pallet can't go
	// further without importing this header. So every bridge MUST import mandatory headers.
	//
	// We don't want to charge extra costs for mandatory operations. So relayer is not
	// paying fee for mandatory headers import transactions.
	//
	// If size/weight of the call is exceeds our estimated limits, the relayer still needs
	// to pay for the transaction.
	let pays_fee = if may_refund_call_fee { Pays::No } else { Pays::Yes };

.

The idea is to run a relay that only submits mandatory relay chain + associated parachain headers. Then we can deliver all messages, "scheduled" at this parachain header. The obvious drawback of that approach is that the message delay may be larger than 4 hours for Polkadot -> Kusama message. And since there are message confirmation transactions, going in opposite direction and required to deliver next batch of messages, we won't be able to deliver more than 4_096 headers in 5 hours (4 hours to submit finalized Polkadot header to Kusama and then deliver 4_096 messages + 1 hour to finalize messages delivery at Kusama side and send confirmation transaction back to the Polkadot, allowing next bunch of messages to be delivered).

The positive side of that change is that now we can remove cost of GRANDPA finality submission (and if we'll also allow submitting associated parachain header for free, then parachain finality submission) from the bridge message fee. For example, it'll reduce bridge fee for Polkadot -> Kusama message from 1.93 DOTs to 0.01 DOT.

Relay Non-Mandatory Headers for Free

The idea is to add more free header submissions. Let's say we allow submitting new header of the bridged chain (relay + parachain) for free every N blocks. Or we allow submitting every Nth block of the bridged chain for free. Then, if systems are operating normally, we'll be able to decrease the message delivery delays, while keeping the bridge fee low (see previous section).

We should be able to introduce that change, because it helps bridge to progress and keep low fees at the same time. So it is the common good deed and is in interest of common good (aka system) parachains.

Long Term Solutions

BEEFY + BLS Signatures

Tracked in the #2439. Apart from using (presumably) lighter signature verification code, will drastically decrease the size of justification.

Running Finality Relays on Collators

Tracked in the #2586. The idea is to have collators include recently finalized header of the bridged chain into the runtime storage via inherent, similarly to how timestamp is included these days. This has some caveats - e.g. we'll probably require fishermens or some other kind of ensuring that the collators system is able (and incentivized to) behave properly, so it needs more investigation. There's also idea by @bkontur to check if this can be implemented by offchain workers.

---

So the most sensible solution is to implement that "Relay Non-Mandatory Headers for Free" soon and then work on long-term solutions. Some details on proposed implementation:

1. for simplicity, let's avoid referencing time (slots) and keep referencing blocks by their number (height);
2. allowing free import of single bridged chain header at every Nth block of this chain (e.g. we allow free import of Polkadot header once in every 16 Kusama BH blocks) isn't a good idea, because someone may choose to submit some old header instead of the most recent one. So let's allow free import of every Nth block of the bridged chain (e.g. every 16th Polkadot header may be imported for free at Kusama BH);
3. in case if there were no relayer working for a while, upon startup it may (being dumb or malicious) start submitting (for free) every Nth header of the bridged chain, which may result in growing our fee factor. To alleviate that, we must set some sane limit on number of free headers that may be submitted at every block (we already have something like that for mandatory headers);
4. since we are interested in seeing latest blocks submissions (we don't actually need every Nth block if we missed N*100 blocks - we only need latest block, which should satisfy all our needs), we may tweak priority of header-submit transactions to bump priority of last-header-submission transactions comparing to submissions of some ancient headers;
5. it makes sense to have free transactions for both relay chain header and associated parachain (bridged BH) headers. They're both equally important for the bridge;
6. we'll need to deploy two relayer instances (instead of one as we do now). One will submit relay and parachain headers - we don't have such mode now, to be implemented. The other one will submit message-related transactions. Both need to be registered to get priority bumps

[acatangiu]

Above is inline with what we discussed offline and I fully support points 1->6 for short-term solution.
I wanted to also add a couple of points:

• "free" submission has dedicated extrinsic/call
• we still have "paid" extrinsic for submitting finality proofs with no restrictions (other than proofs being valid) - this paid version can be used by anyone willing to "pay the premium" for relaying message(s) with low latency

---

Adding here some more ideas for longer time horizon enhancements:

1. Instead of static every Nth target block is free, we could say e.g. 5% of blockspace/blockweight is free to use for finality proofs -> if 1 proof is 30% of a block -> every 6th (or newer/higher) target block finality is free
2. instead of free, we could do very cheap dynamic tx fees, with exponential curve increasing cost as block space is utilized
   1. for this to work we need XCM dynamic fees discovery mechanism Estimate Fees for XCM polkadot-sdk#690 (comment)
   2. better mechanisms to claim trapped assets for partially executed XCM programs (for failures in BH execution for example)
3. we should also use a custom tx_fee_payment pallet where we can also do QoS and split block-space allowance and dynamic price per-bridge

[Polkadot-Forum]

This issue has been mentioned on Polkadot Forum. There might be relevant details there:

https://forum.polkadot.network/t/polkadot-kusama-bridge/2971/26

[svyatonik]

Suggested short-term scheme has been implemented and deployed at Rococo <> Westend. Should be deployed soon on Polkadot <> Kusama. Long-term solutions still need to be considered