By Sergio Demian Lerner, RSK Chief Innovation Scientist

Bridging blockchains in a fully decentralized and trustless manner is one of the holy grails of blockchain research. At IOV Labs we created the first solid federated bridge in 2016 that has been powering the 1:1 peg between RSK and Bitcoin for 3 years. Now, we are working on a fully decentralized bridge between RSK and Ethereum. This post presents the technical details of this new bridge and the underlying decentralized protocol that powers it.

Introduction

To understand how to move tokens between blockchains, let’s first review some commonly used terms and their history. The term two-way peg (also 1:1 peg) refers to a system that attempts to make two tokens that live in two separate blockchains economically equivalent. When the demand on one side increases, the two-way peg must allow tokens to flow in from the other side, so that the price equivalence is maintained. In 2013, before such system was even designed, a future was envisioned where Bitcoin could have several satellite sidechains connected to the main chain with two-way pegs. A sidechain was conceived as a separate blockchain whose native asset is foreign and therefore transaction fees are paid in this foreign asset. Having no internal coin issuance, blocks do not pay a subsidy to the sidechain miners. However, lacking a proven two-way peg design, the term sidechain was vague. In 2014, a stateless UTXO-based solution was attempted by Blockstream. The design was implemented in the original Elements sidechain codebase, but this approach was later abandoned due to inherent security and censorship problems, and Elements switched to a Federated peg and became the Liquid sidechain. Therefore, the term sidechain does not determine the actual communication system that performs the asset transfer that maintains the 1:1 peg. With the advent of multi-token blockchains, an interoperability system to manage a two-way peg became a token bridge. A token bridge can connect two arbitrary blockchains, where neither is a sidechain of the other. There are some important cryptoeconomic differences between a token bridge that connects independent blockchains and one powering a sidechain regarding the availability of an independent coin to that can be used as collateral and burned on misbehaviour, but we won’t dig into that distinction in this article. 

The first production-ready token bridge was deployed embedded in the RSK sidechain launched in 2017. The RSK bridge is hybrid: the Bitcoin to RSK direction is fully stateful SPV-based, meaning that it achieves the desired properties of decentralization and censorship resistance, while the RSK to Bitcoin direction is federated. As Bitcoin cannot verify RSK consensus, a decentralized and censorship resistant solution for the the transfer of bitcoins from RSK to Bitcoin cannot be implemented: a full-duplex implementation is impossible. However, the current RSK-Bitcoin peg, shown in the following diagram, constitutes one of the best possible solutions.

The RSK Hybrid Federated-SPV Two Way Peg

The RSK-Bitcoin bridge was never hacked and has a record 100% uptime. The RSK-Bitcoin bridge uses autonomous Hardware Security Modules (HSM) to protect the private keys of a large multi-sig. The HSMs evolved over time, and the new generation of RSK HSMs synchronize with the best chain by verifying the chain proof-of-work. The result is that not even the majority of federation functionaries can cheat or censor peg transactions. However, a federated bridge has downsides: it still relies on a small set of entities that need to keep the HSMs alive and well connected to the network, and still relies on the honesty of the companies that manufacture the HSMs not to introduce covert channels, biased random number generators or backdoors. In a new world of decentralized protocols, federated bridges should only exist until better decentralized systems are built to replace them. A truly secure decentralized bridge between two blockchain must rely on each blockchain verifying the consensus of the other in a succinct way. 

Building a Token Bridge with SPV Light-clients 

An SPV client is a lightweight system that accepts succinct proofs of cumulative proof of work in order to find out which is the honest best chain from many possible candidates,  with high cryptoeconomic security. SPV light-clients are ideal for building a smart-contract based bridge between two proof-of-work based blockchains. But standard SPV clients have many limitations, particularly for blockchains with high block rates. RSK produces a high rate of blocks (about one every 30 seconds), which means that full cross-chain header-only verification becomes expensive, both in terms of space and verification time. Ethereum is worse in this regard, due to a higher block rate and much heavier proof-of-work verification. The following diagram depicts a hypothetical decentralized bridge based on cross-chain header-only consensus verification. Each blockchain maintains a representation of the other blockchain’s best chain in SPV mode.

A hypothetical stateful SPV Bridge

Back in 2015, it was generally known how to create short SPV proofs based on a block header challenge-response interactive game. These games can be turned non-interactive using the Fiat-Shamir transformation (something lately called Non-Interactive Proofs of Proof of Work or NiPoPoWs). The idea is that the prover commits to a blockchain and the challenger asks the prover for a number of block headers, which the prover must reveal, together with information that shows that the revealed block belongs to  the same connected blockchain. However, it was not known how to produce proofs for a variable-difficulty blockchain until 2017. In 2017, the FlyClient protocol came out and finally solved this problem. FlyClient is able to adjust the block index selection function to match the changes in difficulty. Also, FlyClient can be tuned for different proof sizes, providing different cheating probability bounds depending on the client’s security needs.

 

The FlyClient Non-Interactive Protocol (simplified)

However, applying FlyClient to existing blockchains seemed impossible without consensus changes, because FlyClient requires periodic commitments to all previous block hashes in block headers. The commitments are organized in a tree (called augmented MMR), and the cumulative proof-of-work and timestamps are stored on every intermediate node of the MMR tree. 

In 2019 we started our research on how to connect RSK and Ethereum. We explored ways to enable FlyClient in Ethereum without any change to its consensus and we discovered a method that extends FlyClient to achieve this and still uses succinct proofs. This discovery turned into what we called the HawkClient, which belongs to a new category of protocols we call Cryptoeconomic Interactive Proof of Proof of Work (CIPoPoW). The HawkClient protocol works for all EVM-based smart-contract platforms, such as RSK, Ethereum, and Ethereum-Classic. Of course, if a blockchain does implement the MMR tree commitment natively, then the protocol is highly simplified. 

Presenting HawkClient

In simple words, HawkClient is an interactive decentralized smart-contract system for maintaining a smart-contract in one “host” blockchain synchronized to a foreign “remote” blockchain, allowing the transfer of information having explicit monetary value. Two HawkClient systems implemented in a mirrored fashion between two blockchains provide the basis for a decentralized token bridge, allowing the transfer of tokens from one blockchain to the other.

A token Bridge based on two HawkClient systems in mirror

We can transfer arbitrary tokens because token transfers are bounded in value, as tokens have known market valuations with transfers provide explicit token amounts. This eliminates the need for cryptographic-level security and enables the bridge to work under a cryptoeconomic model of security, reducing the sizes of the proofs. In this cryptoeconomic model, transfers are batched and they are secured by a security bond. 

A simplified HawkClient system is based on four roles, the provers, a verifier, an Approximate Merkle Mountain Range (AMMR) Updater or AMMR-Updater (more on this role later), and the users. One prover commits to the best chain of the remote blockchain and submits the commitment to the verifier. Afterwards, the verifier emits a challenge, and the prover creates a HawkClient proof containing a selected subset of headers from the best chain and also containing linkage proofs. The subset of block headers to be retrieved is selected by sampling over the cumulative difficulty space, based on a pseudo-random number generator whose seed is derived from the challenge. In case of a token bridge, the whole process would repeat approximately once a day. 

The verifier is a smart-contract implemented in the host blockchain that verifies HawkClient proofs, and uses the proofs to extend and maintain a representation of the remote blockchain. The verifier is similar to a blockchain SPV node, but running in consensus. This is essentially what RSK and the btcrelay do. The verifier will allow other provers to challenge the proof or present alternate proofs during a challenge period, and afterwards it will accept the proof with the highest cumulative proof of work. However, departing from the btcrelay model, the verifier performs a challenge-response protocol with the prover by itself, and therefore typical transaction censorship attacks are deterred. The users interact with both the host and remote blockchains, and that interaction generates events in the remote blockchain that are recorded in receipts. Those events are later informed to the host blockchain by the prover. Smart contracts on the host blockchain can listen to the informed events and interact with them. 

The RSK-Ethereum Bridge

The RSK-ETH bridge connects RSK with Ethereum and it enables the transfer of any ERC-20 token between the two blockchain. It is being actively developed by IOV Labs. The bridge is based on HawkClients. Additionally, the bridge was designed with a unique set of features. For example, it allows the prover to choose the monetary amount of the security bond she is willing to commit, in exchange for an authorization to provide a proof of a specific size, while assuring that cheating is always a losing strategy. For example, the prover can offer to respond to more queries performed by the verifier, reducing the security bond, but increasing the proof size. If transaction fees are high, the prover can increase the security bond to reduce proof size and transaction fees. As the bond is slashed if cheating is detected, cheating is never a rational strategy and cryptoeconomic security is guaranteed. Also, HawkClient forces commitments to be onchain, and challenges to be derived from following block hashes, so the attacker cannot try millions of different commitments offline. Under the assumption that the attacker controls less than 50% of the hash rate of any of the blockchains involved, the attacker would only be able to make a single commitment. In other words, because the system is interactive, the attacker cannot easily brute-force the commitment offline to obtain a favorable challenge. As an example, if we set a bound on the cheating probability to be 1 in a million, we establish a huge disincentive for any attempt to cheat. This cheating probability that usually turns into low cryptographic security, results in an extremely high cryptoeconomic security. Last, the bridge uses a special simplified token-market that serves as an oracle to discover an upper bound on the current token prices, related to the native coin. This market has long delays (in the order of weeks) for both buying and selling, and we don’t expect this market to be used for any real trade unless a party tries to cheat in token prices. Having this oracling system, we can perform the security bonds in native currency instead of tokens, and we can enable multiple provers without requiring each prover to deposit each possible token.

A HawkClient system for communicating information from Ethereum to RSK

Another interesting feature of the RSK-Eth bridge is that anyone can become a prover as long as it is willing to commit to the security bond. Also, we’ve developed a very efficient method to verify ETHash proofs of work without the need for a special opcode. We’ll talk more about this in a following blog post.

Key Features of a HawkClient Proof

The following sections describe the main characteristics of HawkClient proofs, and especially how they interact to enable the creation of  a decentralized bridge.  

Interactive Proofs

HawkClient proofs are interactive. The protocol involves at least one prover. Each prover also has the role of challenging other provers’ potential fake proofs. A prover commits to a proof, and a special smart-contract, that we call HawkClient verifier, chooses a challenge seed from which a set of queries are derived. The prover must then respond to these queries, and responses are then sent back to the verifier smart-contract, which validates them.  After this initial phase, the remaining users can challenge the prover to provide more certainty or they can become provers themselves and submit a proof of a blockchain with more cumulative difficulty to invalidate the previous one.

Cryptoeconomic Proofs

HawkClient proofs are cryptoeconomic, which means that there exists a certain non-negligible probability for the attacker to succeed in cheating. To deter an attack, the protocol forces provers to pre-deposit coins as “security bonds” such that the expected payoff for the attacker when cheating is lower than the expected payoff when behaving honestly. The bridge provides a subsystem that serves as an autonomous oracle to establish the token prices.

The monetary amount the bridge can transfer per day is limited because proof-of-work based blockchains are at risk of double-spend attacks. To fool the bridge an attacker can incur in a cost equivalent of renting 51% of the remote blockchain hashrate for 24 hours. Therefore, assuming there is enough mining hardware that is currently available for rent, the amount of money that the bridge can transfer per time period is bounded. The following table shows the approximate costs in electricity of 51% attacks sustained for 24 hours in different blockchains as of January 2020.

Blockchain	Cost (USD)
Bitcoin	12M
Ethereum	1.1M
RSK	6M

Since cryptocurrency prices vary frequently, the bridge must be parametrized with a sufficient large security margin. For example, the value the RSK-ETH bridge can transfer per day from Ethereum to RSK would be limited to 600K USD, and in the opposite direction, to 3M USD. 

While this is only a simplification of the risk model, all attacks identified have a cost that grows linearly with the cumulative difficulty of the HawkClient proof (which relates to the difficulty of the remote blockchain) and the difficulty of the verifier’s blockchain. 

Gradual Proofs

There are two extremes in smart-contract protocols that need to verify external inputs. On one side, there are “lazy” or “optimistic” protocols whose security entirely depends on the availability and censorship resistance of the on-chain layer. In optimistic protocols, a prover asserts a statement, and the smart contract layer waits for a challenge to the assertion, by means of a fraud-proof. They operate under the “assert-challenge” design pattern. If the statement is unchallenged for a certain fixed period, then the statement is assumed to be true. It’s considered lazy because the smart contract does not perform any verification itself. This model was adopted by TrueBit and lately by Arbitrum. On the other extreme, some “strong” protocols verify every external assertion, and there is no need for challenges, in some cases they use strong Proofs of Computation Integrity, such as zk-SNARKs. Lazy protocols have the downside that they incentivize transaction censorship and miner collusion. Lazy protocols could be proven cryptoeconomically safe if we could estimate the cost of a transaction censorship attack. But this is a daunting task, as censorship is cheap to perform but difficult to prove, and generally impossible to attribute to a specific miner. Miners put their reputation at stake, but that is difficult to value for an external observer. 

The only drawback of strong protocols is that they are expensive in terms of execution resources (gas), and this cost must be somehow shared between the users of the protocol. A middle ground between them are gradual protocols.  Gradual protocols start with an assertion, after which the verifying contract performs some form of probabilistic checking to get an initial degree of certainty. Afterwards other users can either challenge the proof, ask the verifier to request higher certainty, provide another competing proof or wait for a proof to be accepted. When a first proof is challenged by second competing proof, the first prover has the opportunity to prove more cumulative proof-of-work to win the race to become the best chain. Additional proofs can follow, until one of the provers gives up, having no more cumulative proof of work to show. The last unchallenged proof will be chosen as the best chain.

Optimistic, Strong and Gradual for FlyClient

For any protocol there are also other opaque costs such as the composability of the attack: what if the attacker decides to use a single proof to cheat several unrelated systems? Proving security would require knowing every possible system that can be profited from. 

Persistent Sporadic MMR commitments

If the remote blockchain does not support FlyClient natively, HawkClient can look up the MMR commitments in the storage of a fixed smart-contract called AMMR Updater. This contract uses the BLOCKHASH opcode to collect past block hashes and build an up-to-date tree. AMMR stands for Approximate Merkle Mountain Range. This tree contains the bounds to the real cumulative difficulty and time values. The AMMR commitments need not be updated on every block. We assume they are updated every N blocks on average with external calls to the AMMR Updater contract. Once every N blocks on average, the block time will be exact (block time can be accessed using the BLOCKTIME opcode), but block times of intermediate blocks are unknown to the contract. An Ethereum contract does not know the exact cumulative difficulty, there is no such opcode. Therefore when the AMMR Updater contract is called, it must compute  a bound on the cumulative difficulty. The protocol assures that the cumulative difficulty will always be within a percentual error window. The existence of an error bound is justified because the block difficulty cannot vary much between AMMR updates. Let’s consider the Ethereum, where the block difficulty can change by factor of +-1/2048 between blocks. Accepting AMMR updates at a maximum distance of 256 blocks implies the block difficulty can rise or decrease up to 6.65% (in the maximum/minimum point, around block 128). However it must reach the real block difficulty in the last block, because the AAMR Updater checks this using the DIFFICULTY opcode. Therefore the AMMR Updater can compute bounds to the cumulative difficulty in the current block. In the worst case, if no update occurred in the previous 256 blocks, and the block difficulty didn’t change from the last update, this bound represent a rise or decrease up to 3.2% of the real blockchain cumulative difficulty. Therefore, even if the real difficulty is hidden to the smart-contract, it can follow the real difficulty very closely. Also, to change the difficulty 3.2% without being detected, 256 blocks needs to be mined by the attacker, or the attacker must manage to avoid receiving queries for 256 block headers.

Because the AMMR tree does not store exact cumulative difficulty values, when presenting proofs containing many AMMR Updates, the cumulative difficulty bounds on consecutive blocks will overlap. This means that if the attacker is challenged with a query to a block indexing by a specific cumulative difficulty x, she could use this ambiguity to choose one between several adjacent blocks whose difficulty bounds include x. Therefore the attacker could mine just one block for every non-overlapping interval, reducing the amount of work she needs. To prevent this attack, the prover must also commit to a second Merkle tree, the Exact Merkle Mountain Tree (EMMR), containing the exact cumulative difficulties and times for every block. This tree is augmented with cumulative difficulties and cumulative times at every intermediate node. The original function and verifications that were performed on AMMR nodes are now split between these two trees. For every query, the prover must show the AMMR branch and the EMMR branch. The EMMR branch is used to locate the block number with a specific cumulative commitment, and then the AMMR tree is traversed looking for this block number. While doing so, all the cumulative difficulty and cumulative time difficulty bounds are cross-checked. The following diagram depicts a hypothetical blockchain starting with cumulative difficulty 0, and where the difficulty of each block is steady 10. By consensus the difficulty can increase or decrease 10% at every block. After 8 blocks, the real cumulative difficulty (80) has diverged from the minimum and maximum cumulative difficulties that could have been achieved without knowing the actual difficulty of each intermediated block. Only the difficulty of the last block is known. Each green box shows the minimum and maximum cumulative difficulty. During the check of the proof, the EMMR tree is used to locate blocks, and then the branch in the AMMR tree is looked up by block number. At every step, it is checked that the exact range is contained by the bounded range.

The Exact and Approximate Merkle Mountain Range Trees

All systems that interact with HawkClient must know the address of the AMMR Updater contract. Anyone can verify the code deployed by inspecting the transaction that creates the AMMR Updater Contract. However, there is a subtle attack. The creators of the AMMR Updater can create a similar contract with the same address in another blockchain that shares the block header structure and proof of work, and that has previously forked. In this blockchain, the contract could be deployed with a different VM bytecode. To prevent this attack, the MMR Updater contract must be deployed with CREATE2 and use the CHAINID opcode (EIP-1344) to verify that it is running on the target platform during construction, and abort construction if it isn’t. This opcode is available on Ethereum’s since Istanbul hard fork.  

Summary

At IOV Labs we’re working on a decentralized bridge that can connect the main proof-of-work blockchains. The core of this bridge is the HawkClient protocol, which is an extension to FlyClient. There are several differences between FlyClient and HawkClient. In HawkClient, 

• Proofs are interactive
• The security of the proofs is cryptoeconomic not cryptographic
• The system requires security bonds. If being used for a two-way bridge, it may require security bonds both in native currency and in tokens
• Proofs are gradual
• AMMR commitments are sporadic but persistent, without the need to change the consensus of the blockchain
• Prover also commits to a second EMMR tree containing exact cumulative difficulties. This tree needs not be produced in consensus.. 
• Proofs involve one or more provers and a smart-contract verifier. Both the provers and the smart-contract can become challengers.
• Best-chain is monotonically increasing and immutable
• Best-chain growth is delayed (latency from proven tip to best chain tip)

Two HawkClient systems implemented in a mirrored fashion between two blockchains  form the basis of the RSK-ETH bridge. The bridge is currently under development and soon we’ll announce the date of its deployment on RSK testnet, at the same time we will be releasing the source code to the community, providing all the information on how to use it from wallets and smart contracts. We’re very excited to be working on the first genuinely decentralized cryptoeconomic bridge, and the RSK-ETH bridge will be the first step in the building of a communication backbone for all blockchains, making all EVM-compatible blockchain tokens available for DeFi on Bitcoin applications, over RSK.