# Polkadot Bridges: Design Considerations for Bridging to PoW Chains

## Introduction

This document outlines what we are looking for in bridges on specific bridge parachains in Polkadot. It will be focused on BTC and ETH (1.x) and so will mostly be considering bridging proof of work chains.

The bridge logic will have two important parts: a *bridge relay*, which understands as much as possible the consensus of the bridged chain, and a *bank* (name change possible for PR reasons), which involves staked actors owning bridged chain tokens on behalf of Polkadot.

The bridge relay needs to be able to carry out consensus verification of the bridged chain and verify transaction inclusion proofs there. On the one hand, the bank can be used by users on the bridged chain to lock tokens as backing for the corresponding asset they want to receive on Polkadot, e.g., PolkaETH or PolkaBTC. On the other hand, users can use the bank to redeem these assets into the bridged chain tokens.

[XClaim](https://eprint.iacr.org/2018/643.pdf), is the only existing design similar to this as far as we know.

The bridge relay aims to put as much of the logic of a light/thin client of a bridged chain on a bridge parachain as is feasible -- think [BTC-Relay](http://btcrelay.org/). However, crypto and storage are much cheaper on a parachain than in an ETH smart contract. We aim to put all block headers and proofs-of-inclusion of certain transactions of the bridged chain in the blocks of the bridge parachain. This is enough to decide whether a transaction is in a chain which is probably final.

**Generally, the idea for the bridge relay is to have a longest-chain bridge chain where conflicts are resolved with a voting/attestation scheme.**

After reviewing necessary actors and entities, we describe the bridge protocol from both the Polkadot side and the bridged chain's side.

Note, that many details are left out from this description. Some of them are suggested in XClaim and we need to specify the rest.

### Definitions, Actors, and Entities
**Bridged currency:** The native currency of a bridged chain, i.e. BTC for Bitcoin and ETH for Ethereum.

**Backed asset:** A token issued by the bridge parachain, and backed by the bridged currency. Namely, **PolkaBTC** will be backed by BTC and **PolkaETH** will be backed by ETH, etc.

**Requester** is the user who wants to pay ETH or BTC to receive PolkaETH or PolkaBTC assets on Polkadot.

**Redeemer** is the user who owns PolkaETH or PolkaBTC on Polkadot and wants to redeem them to get ETH or BTC on the respective chains.

**Backing blockchain** is the bridged chain where the requester submits its token as backing for requesting PolkaETH or PolkaBTC or the bridged chain who pays out to the redeemer once he wants to redeem his assets.

**Issuing blockchain** is the blockchain who issues the backed asset. In our case, this will be Polkadot.

**Bridge relayers** are a set of staked and non-staked parachain actors. Both entities will participate in adding block headers and proofs of inclusion from the backed blockchain onto the bridge relay. We will have the staked group of parachain actors vote on when conflicts occur.

It is possible to use the above actors in a protocol that allows users to swap tokens between the bridge and bridged chains without Polkadot owning tokens equivalent to tokens on the bridged chain. But for some purposes, we would like to have a smart contract own e.g. BTC equivalents. For that to be possible we would want bridge actors to own BTC on behalf of Polkadot. Such a solution has already been deployed by e.g. [PoA networks](https://poa.network), but their solution requires trusting the authorities.

**Custodial actors (for Bank)** are responsible for putting down collateral and keeping token from the backing blockchain sent to them by the user and redeeming it later back to the user. They are staked and are vulnerable to slashing, for which the consensus following protocol will allow us to do with minimal trust.

## Polkadot Side

### The Bridge Relay

The bridge relay aims to interpret/maintain the state of the backing blockchain and make issuing non-interactive.

Full nodes of the backing blockchain can act as relayers (staked or non-staked parachain actors) and submit transactions that are:

- Block headers of the backing blockchain which extend a known header with valid PoW.

- Proofs of transaction inclusion in blocks whose headers are on the chain for transactions that involve a list of watched accounts/addresses.

Staked-relayers can vote that a header in the chain is invalid. If a majority of staked-relayers do so, we consider those blocks invalid, however, we still accept headers that build on invalid blocks. While the majority think a block in the longest chain is invalid, we will halt many operations. This allows security even in the event of a 51% attack, which could force an invalid chain to be longest.

A key part of our security guarantees should be that if the bridged chain is not 51%ed and the parachain is censorship resistant, then a malicious majority of stakers can do only limited harm. For example, they can make the bridge chain halt, however, they cannot do serious harm provided that there is at least one honest staked-relayer. The 51% can lead to double spending but bridge assets cannot be obtained from nothing. Likewise, we want where possible to reduce the damage that a 51% attack or general poor network performance for the backed blockchain can do under the assumption that a majority of staked-relayers are honest.

The relayers also need to detect when a block from the bridged chain that has a header in the bridge relay is available to them. Hence, when a relayer detects unavailability it needs to inform other relayers and if a majority of honest staked-relayers have attested to unavailability we need to wait until it becomes available. This is established when the majority of staked-relayers attest to its availability, otherwise, we cannot move on.

## Backed Blockchain's Side (Ethereum or Bitcoin)

### Bank
On this side, there is a number of staked entities, custodial actors, who operate a multisig with a threshold that holds the ETH or BTC that has been locked by requesters and released to the redeemers. The custodial nodes need to be able to know when txs are final in Polkadot.

On Bitcoin, we need multiple banks.

## Assumptions
The custodial actors for the bank do not need to be trusted. Although the banks do not need to interact with the issuer, they need to be always online for redeeming assets when users ask for it. Moreover, they have locked DOTs at the parachain and need to adjust their collateral according to changes in the exchange rate. Therefore, the custodial actors can (and will) be slashed for being offline.

We assume that there is at least one honest relayer and that they can get any transaction onto the parachain within a reasonable time. This requires that the parachain be censorship resistant and that network delays be reasonable. The bridge actors should not be vulnerable to eclipse attacks.

The staked-relayers need to have a majority of non-compromised actors, though we will still get some guarantees if they do not as long as the bridged chain has 51% honest miners. Relayers are not punished for being offline.

Next, we review how requesting and redeeming works on our bridges.

## Request PolkaETH by paying ETH

Figure 1 (to be updated) shows the necessary steps that need to be carried out for requesting PolkaETH.
The Bank needs to put down collateral at the Polkadot bridge as backing for the requested PolkaETH, step 1).
The user (requester) pays ETH into the Bank multisig contract, step 2). Then the requester posts a transaction on the parachain that includes the amount they sent and their parachain account address signed with their ETH private key.

Either the user or any relayer should post the proof of the ETH transaction inclusion into a block onto the parachain. When the longest chain includes sufficient confirmations, step 4), then PolkaETH should be issued to the user's parachain account, step 5).


*Figure 1: The Request protocol for requesting PolkaETH by paying ETH*

It may be easier to only accept the parachain transaction when the ETH transaction is final so that the PolkaETH can be issued immediately.

## Redeem PolkaETH and get ETH
Figure 2 (to be updated) shows the necessary steps that need to be carried out for redeeming PolkaETH.

The user (redeemer) submits a transaction with their PolkaETH that nominates an ETH address to receive it; in Figure 2 this is step 1).

The parachain should wait until this transaction is final on Polkadot. This either means understanding GRANDPA commit messages or needs a protocol.

Then the multisig owners should send the equivalent ETH to the address, step 4). A proof that this was done would be put on the parachain, step 5). Again this would be a proof of event inclusion as the multisig is a smart contract. Finally, the collateral of the bank is unlocked by the Polkadot bridge.

*Figure 2: The Redeem protocol for redeeming PolkaETH by getting ETH*

To deal with DoS attacks and unresponsiveness in general, multiple banks can be deployed. This isn't much of a problem for Ethereum, but it is for Bitcoin.

There should be a limited time frame where the pre-determined bank (by the issuer) pays the redeemer. If the bank does not carry out the tx until the end of the time frame it should be punished. Once the time frame ends another bank can be commissioned to pay the user. When multiple banks are used, eclipsing attacks can lead to double redeem as follows. Let us assume the system has two banks $b_1$ and $b_2$. The protocol proceeds until step 4) in Figure 2, where $b_1$ has carried out the release of ETH. If bank $b_1$ is eclipsed, the user can claim to the Polkadot bridge that step 4) has not happened and then the Polkadot bridge would carry out another unlock order for another bank $b_2$, and slash bank $b_1$. The user would be paid by both banks. Therefore, banks need to be responsible for being well connected and hard to eclipse.

We also need to figure out the tx fees. Low tx fees might lead to the redeem tx not going through.

---
## Practicality and the numbers for BTC/ETH

### Header data:

Bitcoin has an 80 byte header every 10 minutes. Ethereum has a 508 byte header every 14s (see https://github.com/ethereum/yellowpaper for the header format and https://etherscan.io/chart/blocktime for the times). Therefore following ETH take 250x as much data per minute than BTC. While this is not too much data for a parachain to bridge ETH, we could have one parachain that bridges to all the Bitcoin forks without trouble and this might be harder for ETH.

### Transaction inclusion Merkle proofs:

For Ethereum, sometimes we will need a *proof of event* instead. If the bridge needs to deal with ERC-20 tokens or uses a smart contract for the bank, then we will need to show that a contract emitted a particular event in its execution.

The events emitted during the execution of a transaction appear in the transaction receipt. A Merkle root of these appears an Ethereum header. However, the transaction receipt includes a log of all events emitted in the execution and we would need to give them all. There is a gas cost, so the log cannot be spammed too much, but this still might be too big.

It's possible this can be mitigated by strategic use of gas limits and requiring the multisig contract to be called from non-smart contract accounts for it to send. We still might have problems with especially verbose ERC-20 implementations, but hopefully, this will not be an issue in practice.

### Invalid block proofs:
We might want invalidity vote by staked entities. It would be nice if we could prove that a block is invalid instead. However, this is not so easy for either BTC or ETH.

For BTC, an invalid block proof might need proof that a UTXO was not in the chain, which appears impossible.

For ETH, we have a state root and we need to expand the relevant state for the block as in a light client proof for a block to show that it is invalid. How big is that?

### Multisig wallets

For BTC, m-of-n wallets exist but n is very small, like 3 or 5. There are plans to use threshold signatures, but they would remove accountability. This will likely mean that we need a complex protocol to ensure that money is spread evenly across the authorities.

For ETH, we can handle much bigger multisigs. There may still be a tradeoff between using expensive crypto and getting many signers to send transactions for a single send.

### Collateral and Locked DOTs

When custodial actors want to leave and replaced by someone else it would need to either transfer it's BTC to another bank operator(s) with sufficient collateral or else redeems its BTC with PolkaBTC.

XClaim has a non-interactive atomic swap protocol for this purpose in its appendix.

### Exchange rate
We need to know the current exchange rate to be able to determine how much the bank needs put down collateral at the issuing blockchain. If the rate changes drastically the collateral has to be adjusted.

XClaim deals with fluctuations in exchange rates by suggesting over-collateralization, collateral adjustment, and automatic liquidation. However, this still would only allow a limited fluctuation in the exchange rate. We think we could make the bank to lock some DOTs for this purpose in addition to the countermeasures suggested by XClaim. If the banks are not willing to adjust their missing collateral, the users will automatically get the PolkaETH or PolkaBTC back and the user is paid DOTs to cover the difference.

If a bank operator is slashed, then there will be fewer BTC in banks than PolkaBTC and the bridge has some DOTS to compensate. Anyone should be able to redeem this excess PolkaBTC for DOTs instead of BTC. As long as the exchange rate doesn't move fast to a much worse DOT/BTC rate and stay there, this will suffice. The price here is determined by the excess PolkaBTC and the owned DOTs.

Otherwise, we may have to pay people who want to redeem PolkaBTC for BTC fewer BTC and give them DOTs to compensate. Again both the amount of BTC and DOTs are given are proportional to the amount owned and the fraction of all PolkaBTC redeemed.

## Differences with XClaim
On a high level:
* Voting to deal with 51 % attacks on the bridged chain. The purpose is to be able to deal with invalidity and unavailability.

* Locking DOTs to deal with exchange rate fluctuations.

On a lower level:
* The redeem protocol needs to know when txs are final in Polkadot.

* We will specify the incentive model for the bridge actors.

* XClaim only considers Bitcoin as the bridged chain, we go over practical considerations for Ethereum being the bridged chain such as including proof of events.

---
### Requirements we are interested in:
For a given set of assumptions, we want the bridge design to fulfill the following goals and functionalities.

* Safety: we want to only allow finalized transactions from external chains into our Polkadot bridge. We want the design to be safe against 51 % attacks on either the external side or on our side. We realize making it safe against simultaneous 51 % attacks on both sides seems a hard problem to solve. In the event of a 51% attack on the external chain, we cannot prevent double spending, but we want it to be impossible to create assets from nothing. We also want to be able to detect attacks and respond by delaying finality or by suspending activity completely. Both of these should be possible if 51% of bridge actors on our side are honest.

* Liveness: every user can obtain assets over the Polkadot bridge as long as an equivalent amount of backing has been carried out.

* Consistency: the bridge is only allowing issuing assets on Polkadot if the equivalent value of it is backed on the external chain

* Redeemability: every user that is owning Polkadot assets can redeem them to the cryptocurrency that has backed that asset.

* Auditability: everyone one can audit the correctness of the bridge operation and detect failures

* Scalability: the bridge protocol should be scalable

Note: for the future version we might want to replace the Bank with a (Polkadot) relay on the bridged chain (Ethereum).

## Open Questions:

#### 1) who are relayers and how are they incentivized:
A relayer can be anyone. They don't need to register and can just submit headers and relevant proofs-of-inclusion as transactions.

Staked relayers (which might want a more distinctive name) will need to lock stake. This can be any amount but votes will be weighted by stake.

Relayers should be paid a small amount. And relay transactions should have no fees so this is a net positive for them. Note that the number of relay transactions should be limited. For instance, headers needed to be valid PoW blocks limits how many there are. For proofs of inclusion of transactions to followed accounts, paying into the account and reporting that payment should not lead to a net profit!

Even when a relayer sends erroneous data, a valid parachain block has valid data. It is not possible for a relayer to get erroneous data into the parachain by design. So the parachain logic needs to be able to check headers and inclusion proofs for correctness.

A valid header or a valid proof-of-inclusion for an invalid block should still be included if possible.

Staked relayers voting for things like invalidity, on the other hand, should be accountable. They have locked deposits but there will be no automatic way to punish them. Instead, we may have to rely on governance, probably relay chain governance, to punish them by taking these deposits if governance decides that they misbehaved.

The bridge should wait for Polkadot finality and reverting the parachain beyond that should be really expensive. The relay relies on its censorship resistance and the ability to validate proof-of-work.

#### 2) why did we choose to have the bridge relay and not alternative ways of verifying PoW offline:

We want to store the complete block header because we don't fully trust anyone staking on the parachain. Even if all staked relayers and all bank operators collude, they should not be able to profit by attacking the chain (except for exchange rate crashes, where this is probably unavoidable).

Parachains are relatively hard to censor. Even if a majority of collators are malicious, as long as a majority of relay chain validators are not, they cannot censor an honest collator. So if one honest relayer talks to one honest collator who gets a parachain block in, then there is nothing a majority of parachain actors can do to censor this. This is a bit different to e.g. a Cosmos Zone.

Since we have many parachains, Polkadot will already be more scalable than existing single chain architectures. And parachains, unlike smart contracts can implement different cryptographic primitives than the rest of the system cheaply. The ETH and BTC bridges are important enough to devote an entire parachain to (although we may want to consider bridging to more than one chain on the same parachain if data allows). So in principle, we have enough data capacity on the ETH bridge parachain to not only put the headers in but all the blocks too! It's just that the cost of implementing a full ETH client would be prohibitive so there would be little point.

Trading data cost for minimizing trust for important bridges is worth it at the level of putting all ETH headers in.

#### 3) how does the bridge react to chain organization, 51 % attacks on the external chain, and forks:

If the relay functions correctly, any long reorg will appear in the relayed headers, and the parachain "light client" will see the reorg just as other clients do.

If we see long reorgs that are still short of our threshold, we should increase the number of confirmations we need to act on transactions in the bridged chain. If we see long reorgs, that could be used to attack us, we should stop most bridge activities completely at least temporarily.

If you look at Coinbases response to [the ETC 51% attack](https://blog.coinbase.com/ethereum-classic-etc-is-currently-being-51-attacked-33be13ce32de), you can see why this might help.

For a 51% attack, we should see a long reorg, and I answered above what the response to that should be. This is not enough to stop us being a victim of a double spend in the very first long reorg in a 51% attack; that is more or less impossible. So this is more of a mitigation of possible damage. But in principle, we stop and wait for governance to manually intervene in the face of a permanent 51% attack.

We hope that our requirements for a single honest relayer, who can be anyone, to send transactions to a single honest collator who produces a block occasionally mean that we are no more vulnerable than all the other clients on the network. Then the worst that can happen is a long reorg and double spend.

As long as the header format is not changed, the relay will follow the longest chain. Then it is up to the staked relayers to decide if this chain is invalid.

If the header format does not change and the staked relayers think the longer chain is valid, then the bridge ignores the fork. If the staked relayers think the longest chain is invalid, because they agree that the other fork is correct then the bridge will stop.

If the header format changes, then the relay would follow the fork with the existing header format. But then as long as the staked relayers consider this invalid, the bridge will stop.

If code important to operating the bridge is due to change, such as header and transaction formats, then maybe governance can change our code in advance and effectively decide which fork to follow. If it does not, then the bridge might stop until the code can be changed.

#### 4) how are oracles used in the Polkadot bridge:

Polkadot will have various oracles, possibly both centralized and decentralized, and a bridge would likely use some on different parachains. Whatever scheme we use would need to be analyzed for the difficulty of attacking bridges.

This is a similar problem to the one Maker face with their ETH/DAI oracle for CDPs so their solutions, analysis, and plans will be useful.

Suggestions would be welcome if you can design an oracle that would be good for this.

(When the price used for the collateral is updated? )(What will happen if the oracle is attacked):

The oracle would be periodically polled. We should not be slashing someone in the event of a flash crash anyway - it should be good enough for collateral to have been enough at a recent exchange rate, not just right now, so periodic polling suffices.

If an oracle is DOSable when the prices change in a direction that favors running off with bank contents then we are indeed in trouble. If we had multiple oracles, we could mitigate this.

#### 5) how do we make sure the bank does not fulfill a redeem request and how do we deal with under-collateralization:

We will know if it wasn't included in a block. If the bank operators are operating full nodes, they should be relaying their transactions.

In the case that they cannot post a transaction on the bridged chain, then they could post it on the parachain, in the hope than someone else will relay it to the bridged chain.

The difficult thing to handle here is transaction fees. How do we know if it is reasonable for a transaction to be included or not on the bridged chain based on its fees? Maybe the easiest thing is to have the redeemer specify the fee. In this case, they would also need a way of increasing it and it appearing

If there is no proof of transaction inclusion or transaction in a reasonable time, we will presume the bank is at fault and hand the responsibility of the redemption to another operator. The original operator should not themselves post a transaction after they have timed out and there should be a gap between this happening and someone else being responsible to prevent double payouts.

The operator who timed out should have a small amount of collateral slashed for this misbehavior.

It should have the opportunity to post the transaction to either chain as above. if it cannot then it is timed out and punished slightly as above.

Sustained under-collateralization by a single bank operator for the BTC bridge will lead to them being slashed. A bank operator who has insufficient DOTs to cover its collateral has a choice of
(i) Acquiring PolkaBTC to redeem their own BTC
(ii) transferring their obligation to an overcollateralized bank operator or
(iii) Just accepting the slash and running off with the BTC

(ii) will need some implementation. XClaim has suggestions for it in an appendix of their paper.

#### 6) how would the bank smart contract in Ethereum be carried out:

The easiest solution would be to have multisig with a fixed number of signers and then elect those who lock the most stake.

Periodically, we will redo this election, and need a way of the signers handing the contract to the next set.

Ideally, we would have a way of allowing relay chain validators to opt into being slashed on their entire relay chain stake, including those from nominators, which would allow them to be very well backed signers. Code for this is planned but it may not be ready for the initial deployment of the ETH bridge.

#### 7) how are multiple banks handled?

Do they have to be highly connected to each other for preventing eclipsing of a certain bank?

When we have multiple banks, how does the Polkadot bridge decide which bank should redeem the user? It is not necessarily the bank the user chose to request assets, because we don't keep track of that and because that would make eclipsing attacks easier to carry out. The bank is either selected randomly or the bank with the least amount of collateral is selected.

#### 8) how are we going to incentivize nodes to become custodial actors for the bank?
do they get some sort of compensation for being the bank?

#### 9) how big are the tx inclusion Merkle proofs?

#### 10) for the bank, how are the custodial actors staked in DOT on Ethereum?