Authors: Rongjian Lan, Ganesha Upadhyaya, Stephen Tse, Mahdi Zamani (Visa Research)

A unifying vision of the distributed ledger technology is to connect multiple distributed systems together. While the disruption of financial infrastructure is still early, now is the time to bring many protocols together to scale their innovations for broader adoption. Cross-chain bridges provide broader access of users and assets to decentralized finance. In particular, lending Bitcoin for high-yield financial instruments on Ethereum has surpassed US $1B on-chain management. Cross-chain transactions are more than asset transfers via atomic swaps with hash time locked contracts.

A relay bridge implements a bi-directional relay of block headers between two blockchains. In such a bridge, block headers of blockchain A are constantly being submitted to a smart contract in blockchain B, which implements a light client logic to verify the validity of the headers. And analogously headers from blockchain B are submitted to a smart contract in blockchain A.

A simple example is the BTC relay which implements a uni-directional relay from Bitcoin to Ethereum. There, the Ethereum smart contract computes the difficulty of the submitted Bitcoin headers. A proof for the validity of each header amounts to checking it resides on the longest chain of submitted headers.

Light clients [1–3] can be used to perform cross-chain transactions efficiently. Such transactions can happen when exchanging cryptocurrencies [4, 5], transferring assets to sidechains [2, 6, 7], or sharding blockchains [8, 9]. Such clients enable a user to generate short cryptographic inclusion proofs about past events recorded on a blockchain. In a proof-of-work (PoW) blockchain such as

Bitcoin [10] and Ethereum [11], this can be done by providing the sequence of all block headers to prove to any verifier that the event is recorded on the honest chain that is the longest, or more precisely, the most computationally-difficult chain.

An important characteristic of many light client proofs is portability, i.e., they can be forwarded to other nodes on other blockchain networks to convince them that a certain event was recorded on the source blockchain. While light clients for PoW chains have been proposed starting with Bitcoin’s SPV client [10] and later in PoPoW [2, 12] and FlyClient [3], no light client has been proposed for proof-of-stake chain that rely on Byzantine fault tolerance (BFT) for consensus. Designing a light client for such chains is challenging. While aggregate signatures contain a sufficient number of attestations, we do not know if those attestations actually come from validators that actually have stake. The only way to know this is if we know the balance (i.e., state) of every validator which is what a full node does.

[This work was done when the author Mahdi Zamani was affiliated with Yale University.]

We propose a gas-efficient, cross-chain bridge protocol to transfer assets from a BFT blockchain to another blockchain (e.g., Ethereum) which supports basic smart contract execution. To achieve this, our paper makes the following contributions:

On PoW-to-BFT Transfers. Our bridge protocol further allows a client to transfer assets from a PoW chain (such as Bitcoin or Ethereum) to a BFT chain using FlyClient [3] logarithmic-size proofs. This, however, requires certain chain commitments (in the form of Merkle roots) already being included in every block header, which unfortunately, is not possible until a soft fork on Bitcoin and Ethereum includes these commitments in all future block headers. Until then, our bridge protocol adopts the SPV approach of Rainbow bridge [13], where the relay node periodically sends all recent Bitcoin/Ethereum block headers to the smart contract on the BFT chain. While this incurs a significantly higher storage and computation overhead on the contract, we expect the significantly lower gas cost of most BFT chain (such as Harmony [14] and NEAR [13]) could justify such overhead until chain commitments become available on Bitcoin and Ethereum.

System Model. Consider a blockchain protocol A, where a group of validators agree on a chain via a BFT blockchain protocol such as [15–17], where validators participate in a BFT consensus protocol to agree on each block of transactions. In a permissionless setting, such a protocol typically proceeds in epochs, where in each epoch, one or more BFT executions are followed by a reconfiguration step to randomly select a new group of validators to drive the next epoch. To obtain voting power in the BFT protocol, the reconfiguration protocol may establish identities through any Sybil-resistance mechanism such as PoW (as in [8, 15, 18]) or proof-of-stake (PoS) (as in [14, 16, 19]).

Let B denote another blockchain network that grows a valid chain based on any consensus mech-anism (e.g., Nakamoto [10] or BFT) and provides basic smart contract support to execute arbitrary programs. We say a block B of transactions added to B’s chain is final when B is permanently recorded on the chain. For example, in Bitcoin and Ethereum, this means that a sufficient number of blocks are appended to the chain after B, formalized as the most difficult chain principle by Garay et al. [20, 21].

Our bridge system consists of (1) a client C who can submit cross-chain transactions to A and B, (2) a relay R which periodically submits information about A’s chain to B, and (3) a full node FA that maintains an up-to-date copy of A’s chain at any time and responds to queries from C and R about the chain.

Threat Model. We consider a probabilistic polynomial-time Byzantine adversary who wishes to prevent our protocol from reaching its goals by corrupting a subset of nodes involved. The corrupt nodes may not only collude with each other but can also deviate from the protocol in any arbitrary manner, e.g., by sending invalid or inconsistent messages, by remaining silent, etc. We allow the adversary to control both C and R to prevent our protocol from achieving its goals.

We assume that, at any time, both chains maintain standard blockchain immutability and no double spending properties. In PoW chains, for example, this requires that, at any time, less than 1 2 of the computational mining power (aka, hash rate) be controlled by the adversary. To ensure security against selfish mining [22], one may alternatively assume less than 1 4 adversarial computational power. Alternatively, a PoS chain may require less than 1 3 of the total stake associated with validators in the network be controlled by the adversary.

Problem Definition. Client C wants to perform a cross-chain transaction XA!B to transfer an amount of x tokens from A to B. The transaction consists of two on-chain transactions Tburn and Tunlock to be recorded on A and B respectively. A cross-chain bridge protocol is secure if and only if it guarantees the following atomicity property:

To verify that a blockchain is valid without participating in the mining process, a client may choose to download blocks from a miner or a full node that holds a copy of the entire chain. Currently, downloading and verifying all blocks in Bitcoin or Ethereum requires a node to download more than 200 GB of data, taking hours to synchronize the node’s local blockchain [23]. Such a requirement causes long delays for regular clients and makes it nearly impossible for storage-limited clients to quickly verify transactions.

The original Bitcoin design [10] describes a faster synchronization mechanism, known as simplified payment verification, that allows efficient verification of transactions on the blockchain. In Bitcoin [10] and Ethereum [11], block headers contain enough information to ensure that (1) the PoW is valid, (2) the block includes a certain transaction, and (3) the block is at a certain position on the correct chain. The transaction validation process utilizes a Merkle tree commitment to all transactions in a block which is stored in each block header. A light client does not verify all transactions in the entire chain and essentially relies on the assumption that the chain with the most proof-of-work contains only valid transactions and follows the rules of the system.

Kiayias et al. [2, 12] propose an interactive proof mechanism, known as proofs of proof-of-work (PoPoW) that allows a prover to convince a verifier with high probability in logarithmic time and communication that a chain contains a sufficient amount of work. The PoPoW protocol suffers from multiple drawbacks described by Bünz et al. [3] who propose a new solution, known as FlyClient, that overcomes the limitations of PoPoW.

FlyClient uses a probabilistic sampling technique to randomly sample a logarithmic number of block headers (in the chain length) from a PoW-based blockchain with variable block diffi-culty. FlyClient uses an efficiently-updatable commitment mechanism, known as Merkle mountain range (MMR) [24], that allows provers to commit to an entire blockchain with a small (constant-size) commitment while offering logarithmic block inclusion proofs with position binding guarantees.

Rainbow Bridge [13]. NEAR’s Rainbow bridge uses light clients to transfer ERC-20 tokens from Ethereum to NEAR’s PoS blockchain and vice versa. For each chain, the Rainbow protocol deploys a smart contract that implements a light client and relay nodes that regularly sends block headers to the light client. Namely, Ethereum relays (aka, ETH-2-NEAR relays) sends every single Ethereum header to the NEAR contract, while the NEAR relays (aka, NEAR-2-ETH relays) sends one header every 4 hours to the Ethereum contract. As a result, both contracts can independently verify the inclusion of any event on the other chain.

While the Rainbow bridge allows trustless cross-chain transfers, it has multiple performance and security drawbacks. First, the relays need to constantly forward Ethereum and NEAR headers to the smart contracts and this comes at a large gas cost on both chains. Second, to avoid an ever-growing state of the NEAR contract, the bridge limits the number of synced headers to only seven days. If the contract also limits the verification to only the seven-day log, then this significantly lowers the security of the light client as a malicious Ethereum relay can now create a fake chain of only seven days worth of headers appended to a valid prefix and present it to the NEAR contract. If the contract also incorporates previous seven-day logs from old blocks on the NEAR blockchain, then the large gas cost overhead would again come into play. Third, Rainbow’s Ethereum contract does not verify all validator signatures on every NEAR header submitted to the contract.

XCLAIM [25]. XCLAIM is a framework for trustless, cross-chain exchanges, where a smart contract on each chain governs the exchanges between the two chains (e.g., Bitcoin and Ethereum) and punishes malicious parties by seizing their collateral in favor of honest parties. The XCLAIM model consists of three main entities: A client who wishes to move funds from Bitcoin to Ethereum, a vault that locks the Bitcoin funds received from the client, and an Ethereum relay contract known as BTCRelay [26] which stores Bitcoin block headers to allow verification of SPV proofs.

The protocol starts with the vault locking up sufficient collateral on the Ethereum smart contract. The client then sends her Bitcoins to the vault and submits a proof to the contract showing that the transaction has been recorded on the Bitcoin blockchain. The chain relay verifies this proof and confirms to the contract that the lock has been executed correctly. Finally, the contract releases Ethereum tokens to Alice.

tBTC [27]. tBTC is a multi-wallet, multi-signer protocol that provides a BTC-backed bearer asset on Ethereum. tBTC attempts to remove single points of failure by geographically distributing signers and aiming for a multi-wallet scheme. The signers use a multi-party threshold ECDSA protocol to collectively create a signing group wallet which is created by randomly selecting a set of signers from the eligible pool of signers. tBTC relies on collateral to prevent signers from deviating the protocol as in the following cases: (1) To liquidate deposits in case they are in danger of undercollateralization; (2) To punish a signing group if it signs an unauthorized piece of data is once distributed key generation is complete; (3) To punish a signing group that fails to produce a signature for the system when requested; and (4) To ensure a depositor is refunded if the signing group fails to form. As a result, tBTC requires a complicated mechanism for detecting and dealing with undercollateralized signers.

Waterloo [28]. Kyber’s Waterloo is a cross-chain bridge between Ethereum and EOS [29]. An Ethereum smart contract serves as a light client that only verifies EOS block headers. The consensus protocol of EOS is based on the delegated PoS mechanism [30], where EOS token holders continuously vote (i.e., delegate) for their favorite block producers. Instead of relaying all EOS block headers, the Waterloo relay only relays the changes in the set of EOS block producers.

We build our solution for transferring assets from a BFT blockchain to a PoW blockchain in the context of the Harmony blockchain [14] as our BFT protocol and Ethereum as our PoW blockchain. Harmony is a sharded PoS blockchain protocol inspired by research results including but not limited to RapidChain [8] and OmniLedger [9]. The protocol execution is divided into predetermined time intervals (e.g., 24 hours), known as epochs. In each epoch, the network is partitioned into a set of shards each of which maintains a separate blockchain in parallel to other shards.

The validators of shards are randomly sampled using a distributed random generation (DRG) protocol executed at the end of every epoch by a special shard known as the beacon shard, which itself gets re-elected in every epoch. The beacon shard is also where the configuration of the network (i.e., validator identities and shard assignments) are stores. Moreover, the beacon shard is where token holders deposit their stakes to become validators in the consensus protocol.

Each epoch consists of multiple executions of a BFT consensus protocol in each shard, where a block of transactions is generated and appended to the shard’s chain after every execution. The set of validators and shards is fixed throughout each epoch but may change between epochs based on a shard reconfiguration protocol executed by the beacon shard at the end of each epoch. The last block of the beacon chain in every epoch is called an epoch block which stores the identities (i.e., public keys) of all shard members for the next epoch. Each identity consists of the node’s ECDSA address, its BLS public key, and its stake in the consensus, represented as a decimal number between 0 and 1.

For every BFT consensus execution, a leader is selected based on the randomness generated by the DRG at the end of the previous epoch.1 In every run of the consensus protocol, the leader runs the aggregate BLS signature protocol of Boneh et al. [33, 34] to collect the validators’ votes in a constant-sized, threshold aggregate signature and then broadcast it to the shard. The aggregate signature is included in the block header for later block verification. After the new block is committed to the shard chain (i.e., the chain maintained by the shard), the shard validators send the block header to the beacon shard who verifies the header contents (i.e., the previous hash and the aggregate signature) and broadcast it to all shards to facilitate future cross-shard verification.

Consider a client C who wants to perform a cross-chain transaction XA!B to transfer an amount x of her coins from blockchain A (i.e., the Harmony blockchain) to blockchain B (e.g., the Ethereum blockchain). Our bridge protocol consists of a smart contract S deployed on blockchain B as well as a relay node R who periodically syncs S with epoch block headers from A. As shown in Figure 2, our protocol consists of two parts: (1) Relay/contract sync, and (2) Cross-chain transaction. In the following sections, we describe each part in detail.

At the end of each epoch (i.e., every 24 hours), R sends to the contract the most recent epoch block header Bi which is maintained by the beacon shard. This block contains sufficient information to allow the contract to later verify the inclusion of any transaction on A. In our bridge protocol, the contract verifies the inclusion of a burn transaction, denoted by Tburn, submitted by the client. T burn essentially transfers x coins on A to a null address, i.e., deletes the coins permanently. We refer to an inclusion proof for a burn transaction as a proof of burn (PoB).

Cross-Chain Bridge Protocol (Horizon)

For ease of presentation and without loss of generality, we consider only one shard (i.e., the beacon shard) and describe our protocol for the case when Tburn is recorded on the beacon chain.2

Proofs of Burn (PoB). An inclusion proof for Tburn should convince the verifier (i.e., the con-tract) that (1) The transaction is included in a block with header Bk , and (2) The block correspond-ing to Bk is included on A’s chain. The former can be proved using a transaction Merkle proof and verified using the Merkle root stored in Bk . The latter, however, requires a new chain commitment added to the epoch block Bi . Inspired by FlyClient [3], we use a Merkle tree variant, known as a Merkle Mountain Range (MMR) [24], over all block headers added to the blockchain between two epoch blocks. This allows S to verify the inclusion of Bk within the epoch using the root of the MMR stored at Bi .

Checkpoint Blocks. The confirmation latency of a cross-chain transaction depends mainly on the rate at which R submits epoch block headers to S. Since one epoch block is created every 24 hours, then a cross-chain transaction would take about 12 hours to be confirmed in expectation. To reduce the confirmation latency, we propose to create periodic checkpoint blocks in the middle of epochs on A. A block is called a checkpoint block if its header contains an MMR root calculated over all block headers added to the chain since the previous checkpoint block. Therefore, epoch blocks are considered checkpoint blocks.

Every checkpoint block header Bi includes the following fields the first four of which are included in all blocks:

Checkpoint Verification. At every checkpoint block header Bi, the relay sends a sync transaction Tsync to S as defined in Figure 2. Upon receiving Tsync from R, contract S verifies that the checkpoint information is valid, otherwise it replaces R with another relay and aborts. Namely, S does the replacement and aborts if any of the following conditions are true:

Otherwise, S stores Bi in the contract’s state for future cross-chain verification requests.

This part of the protocol is initiated by the client C submitting Tburn to blockchain A. Once the transaction is confirmed on A, C sends a request to a full node F who always maintains a full, up-to-date copy of A’s chain. Upon receiving the request, F finds the block Bk that includes Tburn. Then, it generates two Merkle proofs ΠB and ΠT that together form the PoB, denoted by Πburn. The former is generated using the checkpoint Merkle root cmri stored at the first checkpoint block after Bk , denoted by Bi . The latter is generated using the transaction Merkle root Bk :tmr. Finally, F sends Πburn, i, and Bk to C who creates an unlock transaction Tunlock and submits it to blockchain B. Since the full node is not trusted, this transaction may fail, in which case the client replaces F with another full node and repeats the process.

PoB Verification and Asset Unlocking. Upon receiving Tunlock, contract S fetches Bi from its state (checkpoint block height i is specified by C in Tunlock) and verifies the validity of the burn transaction against the unlock transaction through the checks listed in Figure 2. If all checks are successful, then the contracts unlocks x tokens on B (maintained on S’s state) and delivers them to C’s address on B.

The single-relay bridge model exposes cross-chain transactions to denial-of-service scenarios which could make the bridge protocol completely non-functional. One may alternatively choose to employ a group of relay nodes which redundantly submit the same checkpoint information to the smart contract. Unfortunately, this significantly increases the gas cost of relaying information to the contract as it needs to compare/store an amount of information that grows linearly with the redundancy factor (i.e., the number of relays).

Instead of multiple relay nodes actively submitting checkpoint information to the contract at the same time, we propose to have only one node relay the information at any time and have the other n 1 relays read and verify the contract’s state after every regular relay event. If the first relay fails to send proper checkpoint information, the second relay would take its role and so forth.

In some scenarios, one may prefer to implement a bridge protocol without a relay. For example, if the number of cross-chain transactions is small, it might not justify the overhead (i.e., the gas cost) of constantly sending checkpoint information to the smart contract. That’s because the number of checkpoint blocks grows linearly with the chain length.

On the other hand, due to the block gas limit, the client cannot include the list of checkpoint blocks for the entire chain in its unlock transaction Tunlock. While the client can split the transaction data into multiple transactions/blocks to avoid the gas limit issue, this strategy likely still results in an unreasonable gas cost for a single cross-chain transactions. Moreover, splitting a transaction across multiple blocks requires waiting for multiple block intervals, and thus significantly increasing the latency of the overall transaction.

To allow relay-free cross-chain transactions, we propose to add another layer of chain commitments to every checkpoint block in the form of an MMR constructed over all checkpoint blocks. This allows the prover (i.e., the client) to prove to the verifier (i.e., the contract) that a checkpoint block is included in a missing chain of checkpoint blocks. The client proof now consists of the following information:

https://fc22.ifca.ai/program.html

https://tselab.stanford.edu/research/blockchains-decentralized-systems/