The Security Tradeoffs of Validating Bridges

Building a secure bridge is one of the most difficult tasks in the crypto ecosystem. I started designing Bitcoin bridges back in 2012. My first proposal was P2PTradeX . P2PTradeX introduced the idea that one chain should validate blocks from a foreign chain as a condition to release locked funds. It was a precursor of Blockstream’s sidechains and one of the first proposed atomic swap methods . Later, in 2016, I designed the Rootstock bridge : the oldest bridge that is still alive and kicking. With the invaluable feedback from Coinspect , the Rootstock bridge evolved into the Powpeg, the first federated, HSM-based Proof-of-work secured bridge to be in production, and still the only of its kind. While I was auditing bridges, I found the 64-byte type confusion vulnerability in Bitcoin’s Merkle Tree that affected several bridge projects such as tBTC . In 2020, I designed the Hawkclient , a validating bridge between Rootstock and Ethereum. I recently invented the jumplist , a data structure that allows the creation of simple proofs of cumulative work, a critical tool for validating bridges. Now, I’m working with Fairgate Labs and Rootstock Labs on yet another bridge design: the new BitVMX -based bridge we will propose for Rootstock . All bridges, since 2012 until today, have to deal with the same core problem: how to validate the consensus of a foreign chain in a resource efficient and economically sustainable way. Having this mechanism, one can build a lock proof (Bitcoin to sidechain) or burn proof (sidechain to Bitcoin) which comprises an anchored chain fork containing a certain event followed by a number of confirmation blocks.

While there have been new developments in Bitcoin bridge designs, such as schemes relying on BitVM2 or BitVMX , the core problem remains the same. If a chain must decide to release funds based on a transaction occurring in a foreign chain, then we better ensure that the transaction is final. Since bridges can control billions of dollars in value, the incentive for an attacker to lie about the finality of a foreign transaction is huge. This is not the same as a double-spend attack, like the classical 51%-attack where block producers reorganize the chain to double their holdings, but rather a direct theft of funds. Which consensus protocol has such a strong settlement finality guarantee that can withstand a billion dollar bounty to revert blocks? AFAIK, no permissionless consensus protocol. And that’s why bridge systems need to wait for many confirmation blocks to enable withdrawals, and they need solid crypto-economic arguments against someone forking the chain to double-spend.

Every blockchain has a rule to determine the “longest chain” when presented with two competing chain forks: in Nakamoto consensus, it is the one with the highest cumulative work, while in most PoS-based consensus protocols, it is the one with more attestations. Ideally, we want bridge withdrawals to be controlled by an autonomous system that can select the honest chain when presented with competing forks, yet we also want it to be an open system that anyone can communicate with to contribute to the honest chain, because an isolated node is prone to double-spend attacks. These kinds of bridges are called validating bridges . The straightforward but inefficient solution to this problem would be to execute a full node into a smart contract. Let’s call this solution the Node-In-A-Contract (NIAC) . The NIAC should fully validate every foreign block submitted and connect it to a Directed Acyclic Graph (DAG) built with the previously stored blocks. It must also evaluate the foreign chain consensus rules to determine the canonical fork. Of course, in practice this approach does not work for most foreign L1s because of resource limitations of L1s. Fully validating a single foreign chain like Ethereum for a node like Bitcoin would mean increasing by an order of magnitude the resources consumed by the Bitcoin node (there are some rare exceptions like Mina , where a NIAC could synchronize with it in constant time). Weaker versions of a NIAC are often called light clients or light relays. The first light relay was BTCRelay , launched in 2014 and deployed in Ethereum in 2016.

There is a second problem: transaction censorship. The security of the NIAC relies on anyone being able to submit a block to update the NIAC. How can we prevent miners from censoring those submissions? Since no known blockchain has an anti-censorship mechanism (i.e. a mechanism to reserve future block space), the only solution is to wait for enough blocks so that many distinct block producers have the opportunity to include transactions from the (uncensorable) memory pool.

Note that a bridge is much more than a NIAC or a light relay: it defines the properties of lock and burn proofs, controls a wallet, and supports a myriad of procedures to track foreign transactions, peg-in, peg-out, recycle UTXOs, stake/unstake handling, penalize offenders, distribute rewards, add/remove members, collect fees, burn coins, reimburse, etc.

To summarize: the main problem of decentralized bridges is being unable to efficiently validate a foreign chain in a smart contract, and the secondary problem, how to avoid censorship of updates to that contract. All known solutions to the main problem negatively affect the security of the bridge. I present now a simple taxonomy with 4 bridge properties, each one representing a security-efficiency trade-off. Most bridges make compromises in these 4 properties:

1. Consensus Validation: Full or Partial (SPV)
2. Interactivity: none (a single proof), single-chance (single proof and single counter-proof, sometimes called fraud proofs) or extensible (any number of proofs and counter-proofs that can extend previous proofs).
3. Anchor: anchored (or stateful) with proof rooted in a genesis block, or unanchored (or stateless) in a standalone fork without reference to the canonical chain. There are many variants of anchoring: peg-in (i.e. every time an anchor is needed for peg-in, a recent anchor block is picked), updatable anchoring (all anchor links are updated periodically to newer blocks), majority-hashrate-anchoring (the anchor is to whatever chain had the most hashrate at certain time), and more.
4. Finality: Dynamic (number of confirmations chosen at peg-in time depending on the value locked) or fixed (a constant number of blocks needed)

Some orthogonal properties we’re less interested in are:

5. Collateralization: fully collateralized (at all times), fully collateralized during peg-out only, penalization-only, or none
6. Openness: permissionless (generally onchain smart contract) or permissioned (generally offchain, by a functionary or HSM). If it is permissioned, then it’s important the number of independent parties that participate in the voting process.

Let’s first analyze the less interesting properties: Collateralization and Openness. At first glance it may look like a fully collateralized bridge is more secure, and the user shouldn’t care much about how it validates a foreign chain because there is a party taking the risks associated with the security of the transaction settlement, and this party is willing to bet his collateral on trusting the system. This is not the case, because if the NIAC in the bridge cannot correctly assess transaction finality of the payment to the end-user, an attacker posing as an end-user would be able to double-spend and steal funds from the peg. The problem of foreign chain validation does not go away in a collateralized bridge.

But, anyway, I’m not interested in collateralized bridges. The reason is not because they are more or less secure, but because they require a second money-like stable token to be staked as collateral, which in theory works great but in practice what we get is an illiquid collateral token and a short term incentive system designed to pump its price.

A not ideal but still more capital efficient bridge would require collateral only during peg-out, and generally for short periods. Most (but not all) BitVM and BitVM2 bridges will be of this kind because Bitcoin lacks the capability to create script constraints to where the bitcoins should be sent to in the future, so the bitcoins need to be advanced by an operator to an address that is known only at peg-out time. The next, more efficient variant is a bridge requiring collateral only as bonds for penalization. These bridges require collateral to be locked at all times, but the collateral represents a small percentage of the funds in custody (i.e. 1%), and it’s only slashed on misbehavior of a participant. It prevents protocol disruption, such as DoS attacks.

While some BitVM bridges will need collateral only for peg-outs, all BitVM-based bridges will additionally need collateral for penalization. Since there is a high cost to defend a dispute, creating a spurious dispute must be penalized. The best case would be a bridge that doesn’t require any collateral. Federated bridges using multisigs are often of this kind because bad signatures can be simply ignored.

Most existent bridges are closed systems, where you need permission to participate in the committee that controls the bridge. But in this article we focus on open bridges, so we’ll not delve further into this category.

The Four Security-Efficiency Trade-offs

The properties we must focus on are: Consensus Validation, Interactivity, Anchor and Finality. Perfection would be to have an open, fully validating, interactive, stateful, and dynamic bridge without collateral. The reality is always different.

For example, let’s take a look at the Rootstock Powpeg bridge again. Since Rootstock can run complex smart contracts and Bitcoin SPV validation is inexpensive, the Rootstock side of the Powpeg is a partially validating (SPV), interactive, stateful, fixed finality bridge. It’s partially validating because it follows the hashrate and doesn’t validate every transaction in a block. It’s stateful because the bridge tracks all blocks and their connections from genesis to the latest Bitcoin block. It’s interactive because anyone can submit block headers and extend the best chain, and the parties “compete” to grow the best chain. The Powpeg requires a fixed number of confirmations per peg-in (100 Bitcoin blocks in all cases), which at this time is high enough to discourage malicious reorgs.

Another example is the Threshold bridge ( tBTC v2.0), which has been cloned by the BOB rollup. This bridge makes trade-offs in all of the security properties by using partial validation, no interactivity, a pseudo-anchor, and fixed number of block confirmations (currently 6 blocks, but curiously, the bridge contract accepts only 2 blocks if the second has a five-fold difficulty target). The pseudo-anchor protects only from Bitcoin’s rising difficulty, but not against pre-mining. Since the redemption key associated with each peg-out is predictable, a miner could slowly build a selfish fork for a fake redemption that will be requested in the future. The pre-mining limit is restricted by the changing epoch difficulty (every 2016 blocks) which the chain in the redeem proof must comply with. A centralized watchtower seems to be used to veto malicious redemptions. The protection against rising difficulty requires the NIAC tracking the current Bitcoin difficulty analyzing a small number of block headers around the epoch boundaries (2016 blocks). The block headers are provided by an oracle. It is surprising that a 500 BTC redeem ( request , success ) can be successfully executed requiring only 6 confirmations. All past redeems are nicely listed here .

Bridges that support both interactivity and are anchored often need to prove the correctness of the blocks in the lock/burn proofs in a succinct way because of the variable length of the given chains. More so for foreign blockchains with high block rates.

The Problem of Non-interactive Protocols

Let’s assume there is a non-interactive bridge protocol where redeems have predictable ids (as in tBTC). A miner can start mining the fork to create a fake peg-in/peg-out proof in advance, then even a minority miner will sooner or later reach the requested fork cumulative difficulty (or chain length). In Bitcoin, a miner with only 10% of the Bitcoin hashrate would take 10 times more to create the fork (on average), but he will eventually manage to carry out the attack. If the fork is kept private, the miner of those blocks will not be compensated with authentic Bitcoin block rewards, and the attack becomes as expensive as the sum of all rewards that could have been collected by using the hashrate invested in the fork honestly. But a private fork can be used to hold fake peg-out requests for many bridge UTXOs simultaneously, especially in a SPV system that cannot see all the transactions in a block. The attacker can re-use the same confirmation blocks in the proofs to confirm many withdrawals.

Therefore, the cost of selfish mining is amortized. If such a bridge is securing 1B USD in value, and the average Bitcoin block reward is 200k USD, it means that the chain that confirms a withdrawal must contain at least 5000 blocks to provide the right incentives for honest behavior. This implies that withdrawals will take more than one month even if there is no BitVM/BitVM2 dispute. The number of required confirmations could be worse, as this estimation assumes there are no other bridges that can be simultaneously attacked nor that over time successive halvings and reward reductions may force the need for more confirmation blocks.

The Special case of Bitcoin

Bitcoin is a special case because it doesn’t have stateful smart-contracts nor chain introspection opcodes. We will dig deeper into this case. We first focus on the case of a bridge designed only for Bitcoin rollups. In an Ethereum rollup, there is no need to verify a chain of blocks in a burn proof because the stateful smart contracts can track the state of L2 burns and pair them with L1 withdrawals. Bitcoin can’t do that. The recently published BitVM Bridge uses a clever trick to anchor the burn proof to a point with proven high hashrate. The paper claims this anchor point can only be produced by the majority of Bitcoin miners, so the anchor point must belong to the canonical blockchain. We’ll analyze this claim in detail in a follow-up article.

In principle, having a recent anchor point enables the use of a non-recursive SNARK proving system such as Groth16. Without a recent anchor point, the variable and continuously increasing number of blocks in a burn proof would force the use of a recursive argument, such as Nova.

If the bridge is for a Bitcoin sidechain, then the anchor point could be either the sidechain genesis block, or the sidechain block chosen when the peg-in was made. In both cases, the burn proof length will be variable. There are some other solutions to keep the burn proof fixed length:

• Accept variable-difficulty superblocks . A skiplist-like data structure would need to be part of the sidechain block format and consensus.
• Periodically emit committee signed messages with updates on the last anchor, and require these messages in proofs and counter-proofs.
• Periodically recycle the peg-in UTXO and re-anchor them to recent blocks.

How BitVMX makes Better Bridges

BitVMX was designed to be a dual-input protocol, where both the operator (prover) and the challenger (verifier) can provide inputs to a program to be verified. If the prover provides a burn proof with a chain of blocks with certain cumulative work that is lower than the work present in the canonical chain, the challenger can always provide his own proof that outcompetes the operator’s, proving fraud. The proofs and counter-proofs can be both verified directly or through two SNARKs, since BitVMX can run arbitrary programs. The use of fraud proofs matches the design in the original sidechains whitepaper from 2014. With BitVMX it’s possible to build an open, partially validating, interactive, stateful, and dynamic bridge without collateral.

Summary

Building validating bridges is difficult. Bridges need a Node-in-a-contract (NIAC) to follow the consensus of a foreign chain. But creating an efficient generic Node-in-a-contract is not possible, so validating bridges make security/efficiency trade-offs on some of the 4 core security properties: Consensus Validation, Interactivity, Anchor and Finality. Full consensus is the first to be dropped toward light clients. However, making all these trade-offs is not a prerequisite for Bitcoin bridges. BitVMX-based bridges can use BitVMX dual-input capability to be interactive and support fraud proofs. Both proof and fraud-proof can be verified by the same program execution. Bridges can make use of BitVMX almost unbounded execution capability to verify argument schemes supporting recursion, and therefore enable verification of arbitrary long chains with distant anchor points and dynamic number of confirmation blocks. At Farigate Labs, together with Rootstock Labs, we’re designing a new Bridge for Rootstock that moves most of the complexity to the sidechain side, resulting in a bridge that is capital efficient and makes use of the Rootstock Node-In-A-Contract feature to provide strong security guarantees. Stay tuned for important announcements regarding this development.