The Defrauded Fraud Proof of A Bitcoin Bridge
Hanging out in the Immunefi discord leads me to new wonderlands! Last month I was notified of a new bounty program from Interlay, who claimed the maximal bounty payout could be $1M. Although the mainnet of its BTC bridge was not launched, they promised a minimum reward of $100k for critical bug reports.
This journey took me out of the safety of the moonlight and into the uncertain darkness of collateralization. I dug into new concepts to bring familiarity to unfamiliar code. I quickly found a trivial bug, but I suspected that there was more. After some comprehensive research, I discovered a novel, exciting flaw. Both bugs have been confirmed as critical, leading to the decision to deactivate the vulnerable module.
To understand the hack, you, like I had to do, will have to start with the basics. So sit back, read on, and let's learn about collateral!
the interBTC Bridge and Over-collateralization
The interBTC runtime allows the creation of interBTC, a fungible token that represents Bitcoin in the Polkadot ecosystem. Each interBTC is backed by Bitcoin 1:1 and allows redeeming of the equivalent amount of Bitcoins by relying on a collateralized third-party.
Over-collateralization is a popular technique in DeFi protocols, enabling the minting of a synthesized asset from another base asset. Most Collateralized Debt Position (CDP) protocols are designed for minting stable coins from valuable but volatile assets. The most successful case of over-collateralization is the MakerDAO protocol, which allows users to create debt in DAI by depositing ETH.
In the interBTC protocol, however, one is allowed to synthesize a mapping of a high value token (BTC) from its native tokens, like INTR and KINT. This feature is more like Synthetix, which allows minting any mapped assets by locking its native token SNX. The security of risky collateral usually means higher collateralization rate and lower capital efficiency. For SNX, the Collateralization Ratio (C-Ratio) is 400%. For interBTC, on their Kintsugi canary network, C-Ratio of KINT is 500%, C-Ratio of KSM (the native token of Kusama) is 150%.
As pointed out by the interlay team, they use mainly the KSM/DOT assets (the ceiling of INTR/KINT is very low due to missing liquidity). They primarily target exogenously priced collateral assets rather than endogenous ones - more like Maker, but they allow a small portion of our native asset.
The security properties are usually maintained by price oracles and arbitrageurs, but this may not work during market crashes. Luckily, the over-collateralization of interBTC is just the last line of defenses, the system has guaranteed Bitcoin reserves as long as all the vaults are honest.
But how can we trust decentralized vaults that are controlled by anonymous entities? Now I will try to explain the innovation of interBTC’s fraud proof and slashing mechanisms.
Onchain SPV and Fraud Proof
InterBTC is designed specifically for BTC, so it has to deal with the complexity of bitcoin transactions. It is clearly impossible to maintain all the transactions on chain, so the protocol works like a light wallet. Accordingly, the BTC-relay module of the protocol implements the Simplified Payment Verification (SPV). Instead of tracking all the unspent notes (utxo), only the minimal information of every bitcoin block header is stored on the chain. The relayers are in charge of the synchronization of block headers, providing the root of trust. The validation algorithm only needs to verify a given transaction
has a valid merkle proof for its txid
the merkle root is found in the stored block headers
the corresponding block is mature enough
Thus the system is able to check the validity of any interactions between users and vaults (specifically, transfers of a specific amount of BTC). Where would the users deposit to? To addresses prepared by the vaults in the registry module. The vaults have to respond to reasonable requests from the user, and if no valid proof is supplied in a limited time, the locked collateral for that request will be slashed. All the required information is provided to the system, so it can confirm the honest behaviors with confidence.
What about malicious behaviors without corresponding user requests? The off-chain relayers monitor and check that vaults do not move BTC, unless expressly requested during Redeem, Replace or Refund. If a malicious vault moves BTC without authorization by the bridge, or reuses the authorization by committing the same OP_RETURN transaction, all of its collateral will be slashed. These two behaviors are reported by report_vault_theft and report_vault_double_payment extrinsics respectively.
Therein lie the bugs...
Bug 1: Double Payment Force Liquidation
report_vault_double_payment is exposed as an extrinsic call method. It takes two raw txs and verifies that they share the same input and reference the same user requests.
The two txs are compared to ensure they are different. However, the check of Vec<u8> is incomplete.
BytesParser ignores trailing bytes of the raw transaction, so different raw_txs.0 and raw_txs.1 can be parsed into same Transaction, bypassing all the following checks in report_vault_double_payment.
All the vaults with at least one processed user request (Redeem, Replace or Refund), are vulnerable to this force liquidation. The attacker would steal 5% of the vault's collateral, leaving the whole system broken: all the collateral would be transferred to the liquidation account and all vaults would be banned.
The bug is pretty simple. In the POC, a fake tx is crafted by simply appending an extra byte to the original tx. My patch and testcase were later adopted in their commit. Full Report
Bug 2: P2SH Address Forgery
The bitcoin address itself is a pretty interesting topic. There are many variants of address: P2PK, P2PKH, P2MS, P2SH, P2WSH, P2WPKH… It’s super confusing! Why?
As you may (should!) already know, there is no such concept as an account in Bitcoin: all the balances are maintained by utxos. Every utxo has a ScriptPubkey, which can only be unlocked by the corresponding ScriptSig. The different types of common ScriptPubkey are encoded in addresses of various forms. Notice that they are actually tiny scripts that support limited operations in the special stack-based virtual machine inside Bitcoin.
The interBTC system currently supports 4 types of addresses: P2PKH, P2SH, P2WPKHv0 and P2WSHv0. The vaults can freely register any type of address. One of these types is particularly interesting, P2SH – Pay To Script Hash. This feature has a subtle quirk: any ScriptPubkey can be encoded in a vault address with just its hash, and the actual ScriptPubKey will only be provided by the corresponding ScriptSig (and verified against the stored hash). Subsequently, the rest of the ScriptSig (which is not checked against any hashes), just like the key to a lock, can be forged arbitrarily to match the mutable ScriptPubkey!
The malleability of ScriptSig is not a nightmare until it is used in a SPV system. Due to the reduced amount of information stored in SPV, there is no way to lookup the matching ScriptPubkey of a ScriptSig (unlike a full node, which can look it up in the chain). So the system has to extract the ScriptPubkey/address from the ScriptSig. The extraction of the address must be accurate, otherwise
Attack 1: If the correct address is not recovered from the ScriptSig, the use of the uxto will not be considered as the action of the vault, thus the misbehavior will never be confirmed by
report_vault_theft.Attack 2: If the extracted address is misinterpreted as an address of another vault, the benign vault will be slashed by
report_vault_theft.
Unfortunately, the address extraction algorithm is neither sound nor complete. For example, it only accepts a subset of valid addresses and detects the P2SH address by checking if the first opcode is OP_0. If the ScriptSig violates the hardcoded templates of P2SH and P2PKH, the correct address will not be recognized, leading to Attack 1. If the ScriptSig is carefully crafted by the attacker, any P2PKH or P2SH addresses can be counterfeited. That is Attack 2. It's worth noting that Attack 1 can be a side-effect of Attack 2.
In the POC, I use a P2SH address corresponding to a special redeem script and construct a transaction by spending from that P2SH address. The redeem script consumes 3 elements from stack: [fake sig, fake pubkey, real sig]. It has two OP_NIP opcodes that drop the first two elements of the input stack. The remaining real sig is verified with the hardcoded real pubkey. Because the first two elements, sig and pubkey, are pushed into stack just like other common P2PKH scriptsig, the extracted address from this scriptsig will be just like a normal P2PKH address from the fake pubkey (the fake sig is unused), thus leading to Attack 2. The transaction has been confirmed in the testnet. Full Report.
Patching the design failure is tricky: introducing stricter validations means more chances of missing actual thefts. The interlay team handled the issue quickly and decided to deactivate the vulnerable theft reporting functions. However, my exploration didn’t stop here.
Bonus: Segwit Address Confusion
The P2SH address is not the only type of address with a customized script. P2WSH, the segwit version of P2SH, works in a similar fashion, but the script is revealed inside of the witnesses instead of the ScriptSig. P2WPKH is another specially handled address type, validating the user public key embedded in witnesses. For both cases, there is a deterministic algorithm to infer the correct address from the witnesses. I failed to break the segwit style addresses at first, but eventually I found a weakness!
The extraction algorithm only cares about the last element of the witnesses, because it is either the public key for P2WPKH, or the ScriptPubkey for P2WSH.
So, how can an SPV system determine the exact type of the original address in the unified algorithm? Heuristics again! If the witness of P2WSH address looks like a valid public key:
length in 33 bytes
first byte is ‘\x03’ or ‘\x04’
then it is considered a valid P2WPKH address.
Some knowledge of the opcodes is required for building this tricky script. The confirmed transaction is on the testnet.
Downgraded Security?
In the postmortem of the interlay team, they have decided to remove the theft reporting functions. As we have discussed in the first section, the removal of fraud proof downgrades the security: it degenerates interBTC into a basic over-collateralization system, just like Synthetix. Will it be a problem? In theory, its economic security is unaffected.
There is no guarantee that a vault still holds BTC, but the value at risk for the vault is still the same. So if a vault does not send BTC at the time of redemption it is still the same decision process: keep BTC or lose collateral at the time when the user redeems.
However, the security achieved through sophisticated economic designs does not always work. While searching for more instances of failed fraud proof, I came across an unexpected protocol, ONEBTC, the “Trustless Bitcoin on Harmony”. They listed interlay/BTC-Bridge and interlay/BTC-Bridge-Spec in their references! Their code looks like an old version of interlay BTC bridge, with some random customizations (comment out some functions deliberately).
In OneBTC.sol, they have implemented reportVaultTheft and reportVaultDoublePayment! But these functions are restricted by requiring relay.isApprovedStakedRelayer(msg.sender), and they don’t really parse the transactions – they just slash anybody unconditionally!
I have not verified if they had ever used the fraud proof functions, but even if that happened, it would not be in a trustless style as they claimed (and users expected). It turned out that the “optimistic” and semi-trustless bridge worked pretty well, the decentralized nature of vaults were immune to the compromised private key! The ONEBTC bridge was the only survivor of the epic nine figure hack.😓
Funds SAFU? Maybe not... The fluctuation of its collateral, Harmony (ONE), caused a huge risk of under-collateration. The emergency (still ongoing!) freeze of the bridge reinforced the crisis. The users might not be able to cash out, but the vault operators can leave this dangerous game freely, because the raw Bitcoin is unstoppable!
Closing Thoughts
Given the potential for deceit that we find again and again in not just crypto, but almost every inter-human transaction, did we truly expect it to hold secure? Humans have been forging coins, cash, and checks for centuries. Is it really unexpected that, given the chance, we would forge scripts?
What keeps the darkness at bay? I hope that, in a small part, I've helped keep it at bay with this report. Perhaps there was a potential future with a headline of an interBTC hack that now won't happen. Perhaps not. But what there is, is you. I am but one hacker, just months into my crypto journey. You can come walk it with me: what took me months can take you weeks, and you, too, can keep crypto safe.