Bitcoin Integration

Overview

Bitcoin is a decentralized digital currency based on an open-source P2P protocol. Bitcoin uses the unspent transaction output (UTXO) accounting model, i.e., transactions create outputs which are used as inputs to other transactions that create new transaction outputs. A UTXO is always fully consumed by a transaction.

Bitcoin is a payment network without support for smart contracts. Smart contract support for Bitcoin through the IC would add tremendous value: It would leverage the combined strength of the Bitcoin network as the world’s digital gold reserve and the Internet Computer as a platform for securely and efficiently executing smart contracts. An example class of applications that will become possible with this integration are decentralized finance (DeFi) applications, which can currently be implemented only with wrapped Bitcoin requiring additional trusted entities on blockchains such as Ethereum. Moreover, Bitcoin could be used for paying for any kind of services on the Internet Computer, which opens up a sheer endless number of application scenarios.

The Bitcoin integration feature integrates the Internet Computer with the Bitcoin blockchain with the goal of making powerful smart contract functionality available for Bitcoin through a direct, "trustless," integration of the two blockchains. Trustless in this context means that no additional trust assumptions have to be introduced besides those we already have for the Bitcoin network and the IC. This immediately implies that no additional parties, such as bridges or other types of intermediaries, may be introduced for the solution. In the trustless integration we envision, canisters can directly hold Bitcoin on the Bitcoin blockchain.

This direct integration requires the following:

• Canisters can have Bitcoin addresses (and therefore can receive and hold bitcoin directly on the Bitcoin blockchain)
• Canisters can access the UTXO set of the addresses they control
• Canisters can securely sign Bitcoin transactions
• Canisters can submit Bitcoin transactions to the Bitcoin network

The trustless aspect of the integration requires us to implement a threshold ECDSA protocol that allows a subnet to compute ECDSA signatures based on a secret-shared private key on request of canisters. With this protocol, each canister can "control" an infinite set of derivable ECDSA keys and obtain signatures for them. This allows canisters to be able to receive, hold, and transfer Bitcoin directly on the Bitcoin blockchain in a secure manner. In order to know about incoming transactions a canister receives and the associated UTXOs, it needs to have access to the UTXO sets associated with Bitcoin addresses. This is rather an engineering challenge than one of cryptographic protocols, that can be solved by the IC pulling in Bitcoin blocks directly from the Bitcoin network, validating them accordingly, extracting the transactions and their inputs and output, and maintaining the unspent transaction output (UTXO) set of the Bitcoin network.

Architecture

We next present the architecture for the direct integration with the Bitcoin blockchain on a high level. The integration requires components to be changed or added at every layer of the IC protocol stack.

The Bitcoin canister, a virtual canister implemented at the execution layer as part of the replica, exposes APIs for querying UTXO sets and submitting transactions. The UTXO set for Bitcoin addresses is exposed by the API get_utxos and the balance of Bitcoin addresses through the get_balance method. Sending of Bitcoin transactions is done using the send_transaction method. Those three methods are used by canisters to interact with the Bitcoin blockchain and retrieve its state.

Serving UTXO sets by the Bitcoin canister requires that Bitcoin blocks be pulled into the IC from nodes of the Bitcoin network, that their transaction inputs and outputs be extracted, and that the set of unspent transaction outputs (UTXOs) be maintained by the Bitcoin canister. This requires an architecture that spans all layers of the IC protocol stack and also includes a new component external to the replica.

The Bitcoin canister maintains a representation of a recent set of Bitcoin blocks (e.g., a span of 144 blocks in width), the UTXO set of the Bitcoin network, and a set of outgoing transactions submitted by canisters. The UTXO set and the recent blocks are used for responding to UTXO queries of canisters.

Outside the replica we have the Bitcoin Adapter, a sandboxed OS-level process, that connects to multiple Bitcoin nodes randomly using Bitcoin's peer discovery protocol. The Adapter synchronizes the block headers and blocks of the Bitcoin network. The Adapter maintains a recent view of the Bitcoin network's blocks as well and provides blocks to the IC protocol stack on request.

In every IC round, the active block maker, a core component of the consensus layer, makes a request for a new Bitcoin block to the networking layer. The networking layer retrieves part of the state of the Bitcoin canister that comprises the headers of the recent Bitcoin blocks the Bitcoin canister maintains as well as the outgoing transactions. Both those items are used as parameters in a Bitcoin block request to the Bitcoin Adapter. The Bitcoin Adapter matches the received block hashes with its recent view of the Bitcoin network and, if it holds a block that is a successor to one of the blocks represented through the hashes, returns this block. It furthermore adds the transactions received in the request to a queue for outgoing transactions to be submitted asynchronously to the Bitcoin network. If a block is returned by the Bitcoin Adapter, it is put into the proposed IC block by the block maker.

Let's assume that an IC block containing a Bitcoin block has been proposed in the current IC protocol round. This IC block is gossiped to the subnet nodes as usual and needs to go through the notarization and finalization process. The notarization process is extended for the Bitcoin integration: Each replica performs a deterministic validity check of the Bitcoin block contained in the IC block based on the expected hashwork and its timestamp. It is crucial that the block maker may propose a block only if it is guaranteed that the block will be successfully validated by all honest replicas as otherwise consensus of the subnet may fail.

Once the IC block with the Bitcoin block payload has successfully been validated, finalization proceeds without changes. Once the block is finalized, the Bitcoin payload needs to be extracted in the message routing layer and posted to the according subnet queue to get executed. When the Bitcoin block reaches the execution layer, it gets executed by the BTC canister at the execution layer: The block is validated, its transactions and the transactions' inputs and outputs get extracted and the UTXO set and view of the Bitcoin blockchain updated accordingly.

Creating a Bitcoin transaction requires computing one ECDSA signature per UTXO used as transaction input. Canisters can request ECDSA signatures from a threshold ECDSA API that is implemented as part of dedicated ECDSA signing subnets. One such subnet will be deployed initially, if demand increases, multiple signing subnets may be made available in the future. Figure 1 shows the threshold ECDSA functionality in a simplified manner as part of the Bitcoin-enabled subnet instead of being located on a separate subnet. Using the threshold ECDSA API allows a canister to request an ECDSA signature computed jointly by the replicas of the ECDSA subnet based on a secret-shared private key. Using a generalization of BIP-32 key derivation, each canister has access to an infinite set of Threshold ECDSA keys it controls.

Technical Details

As described in the previous section, canisters interact with the (virtual) Bitcoin canister to make use of the Bitcoin integration API. The Bitcoin canister in turn depends on the Bitcoin adapter, which is the component that interacts with the Bitcoin network.

In this section, technical details about the individual components are provided, starting bottom-up with the Bitcoin adapter.

Bitcoin Adapter The Bitcoin adapter interacts with the Bitcoin network to obtain block headers and blocks, and publish Bitcoin transactions issued by canisters.

Connecting to Bitcoin Nodes

By default, the Bitcoin adapter connects to 8 randomly chosen Bitcoin nodes but the number of connections is configurable. In order to ensure that the Bitcoin adapter of each replica connects to a different random set with high probability, the Bitcoin adapter queries the seed nodes for addresses until it has received at least 1000 addresses and randomly chooses nodes from these addresses until the desired number of connections have been established. Experiments showed that this process results in the Bitcoin adapter of each replica connecting to mostly different addresses. State

The Bitcoin adapter aims to maintain the following state:

• All block headers.
• A cache for blocks, which it expects the Bitcoin canister to request next.
• A cache for outgoing transactions that are advertised but not transmitted to Bitcoin nodes yet.

Initially, the adapter does not have any block headers and the caches are empty.

Bitcoin Adapter in Operation

When the Bitcoin adapter is started, it connects to Bitcoin nodes and starts pulling in block headers from genesis until it has caught up. For each downloaded block header, the Bitcoin adapter performs the following checks: The block header is well-formed, i.e., it can be parsed as a correct block header. The hash work in the block header is sufficient based on the difficulty target.

The caches remain empty until messages from the Bitcoin canister are received. Periodically, the Bitcoin canister sends a list of block header hashes of the recent block headers for which it already has the full blocks (containing all transactions). Details on which block header hashes are sent is described in more detail in the section about the Bitcoin canister.

The Bitcoin adapter checks if it has any block headers on the chain with the most hash work (typically the longest chain) whose hashes are not in the received list, indicating that the Bitcoin canister did not receive the corresponding blocks yet. If the Bitcoin adapter has some of the missing blocks that extend the current chain in the Bitcoin canister in its cache, it will respond with a message containing the next missing blocks including the corresponding block headers up to a total maximum size of 2 MB. This upper bound implies that only one block (and block header) is returned for the recent blocks whose size is typically over 1 MB. The ability to send multiple blocks in one message is useful to ingest older blocks more quickly as they were significantly smaller.

If the Bitcoin adapter does not have the missing blocks in its cache, it immediately returns an empty message in order not to delay consensus. Having an accurate view on the state of the Bitcoin canister, the Bitcoin adapter then downloads the next missing blocks so that it can pack them in a return message in a future request from the Bitcoin canister. Since the Bitcoin adapter does not keep track of transactions, it cannot verify the validity of transactions in received blocks. However, in order to prevent spamming the Bitcoin canister with invalid blocks, it performs a few basic checks:

• The block is well-formed, i.e., it can be parsed as a correct Bitcoin block.
• The Merkle tree root hash corresponds to the hash in the corresponding block header.

Blocks are dropped from the cache as soon as the received set of block header hashes indicates that the Bitcoin canister has received the block.

When the Bitcoin adapter receives outbound transactions, they are placed in the transaction cache and advertised to the Bitcoin network. As soon as the transaction has been transmitted to the connected Bitcoin nodes, the transaction is removed from the cache.

Note that not all validity checks are performed in the developer preview. Moreover, the Bitcoin adapter will return any locally available block that is missing in the Bitcoin canister, not necessarily the block on the chain with most hash work.

Passing through Consensus

Technically, the Bitcoin adapter of a replica is queried for Bitcoin blocks whenever the replica is chosen as the next (IC) block maker. When the Bitcoin adapter’s response contains one or more Bitcoin blocks, Consensus calls a function to check the validity of the Bitcoin blocks before putting them into an IC block. It is important to ensure that the validity checks lead to consistent results across all replicas in a subnet as otherwise the whole IC block might be dropped. The validity checks must therefore be a deterministic function, i.e., factors such as local time and the locally available state of the Bitcoin adapter cannot be considered. The following validity checks are performed:

• The block header is well-formed, i.e., it can be parsed as a correct block header.
• The block is well-formed, i.e., it can be parsed as a correct Bitcoin block.
• The Merkle tree root hash corresponds to the hash in the corresponding block header.

Again, the transactions are not validated at this stage.

Once the IC block has passed through consensus (and message routing), the Bitcoin blocks (and corresponding block headers) are offered to the Bitcoin canister for ingestion. Bitcoin Canister The Bitcoin canister is a virtual canister, similar to the management canister, which means that it appears to other canisters as a regular canister but it is effectively part of the replica itself. The Bitcoin integration AP is offered through the Bitcoin canister to enable other canisters to incorporate Bitcoin functionality. State The Bitcoin canister stores the following state:

• The full UTXO set from genesis up to a certain block height h.
• Blocks including their block headers starting at height h.
• The set of outgoing transactions.

Since the Bitcoin canister does not store the full history of transactions, it must decide when it is safe to drop a block, relying only on the information in the UTXO set that it maintains.

Due to the risk of long-running forks, the Bitcoin canister does not use the confirmation count to determine when to drop a block. Instead, it uses a slightly more complex concept, which we call stability. Simply put, we consider a block stable if there are a certain number of subsequent blocks, reducing the risk that the block will be discarded in the future, and the tip of any other fork is also at least the same number of blocks behind. More formally, if h(b) denotes the number of predecessor blocks of block b since genesis and d(b) denotes the length of the longest successor path starting at block b, stability is defined as follows.

Definition (𝜹-stability): For a parameter 𝜹>0, we say that a block is 𝜹-stable if the following conditions hold:

• d(b) ≥ 𝜹
• ∀ b’ ∈ B, h(b’) = h(b): d(b) - d(b’) ≥ 𝜹

The Bitcoin canister is configured with a stability threshold 𝜹 of 144, i.e., if there are no forks, the Bitcoin canister keeps all blocks around for about one day (at one block every 10 minutes on average). Once a block becomes 𝜹-stable, the transactions are applied to the UTXO set and the block is discarded. Thus, stability is used to define the cut-off block height h mentioned in the description of the state above. All blocks with a stability below the threshold are considered unstable. Bitcoin Canister in Operation When requesting an update from the Bitcoin adapter, the Bitcoin canister sends a message containing the hashes of all unstable blocks to the Bitcoin adapter, which uses the hashes to determine which blocks the Bitcoin canister is missing, if any. When receiving blocks and block headers from the Bitcoin adapter, the following validity checks are performed for each block/block header pair:

• The block header is well-formed, i.e., it can be parsed as a correct block header.
• The hash work in the block header is sufficient based on the difficulty target.
• The block header points to a known predecessor.
• The block is well-formed, i.e., it can be parsed as a correct Bitcoin block.
• The Merkle tree root hash corresponds to the hash in the corresponding block header.
• All transactions are valid, i.e., the signatures are correct and only unspent outputs are consumed.

If the verification is successful, the block is added to the list of unstable blocks. Additionally, if a block becomes 𝜹-stable as a result, the UTXO set is updated based on the transaction in this block and the block is discarded.

The Bitcoin canister exposes the following API: get_utxos: The function returns the unspent transaction outputs (UTXOs) of a given Bitcoin address. get_balance: The function returns the balance of a given Bitcoin address. send_transaction: The function sends the given transaction to the Bitcoin network. Details about the API can be found on this GitHub page. When answering get_utxos and get_balance calls, which have an optional min_confirmations parameter, the Bitcoin canister considers both the UTXO state as well as all transactions in the unstable blocks that have at least the requested minimum number of confirmations. In other words, after extracting the relevant unspent outputs from the UTXO set, the unstable blocks are parsed to find additional unspent outputs. Moreover, if there are transactions that consume any of the collected outputs, the outputs are dropped as they are considered spent.

In order to reduce the risk of inconsistencies due to forks, confirmations are counted conservatively, again using 𝜹-stability. We say that the stability count of a block is the largest 𝜹 so that the block is 𝜹-stable. The process to determine the number of confirmations for transactions is as follows: The largest block height is identified with only a single block at this height. The chain of unstable blocks up to the block identified in the first step is considered, and the number of confirmations for a transaction in a block is defined as the stability count of the block plus 1.

While this rule may seem complicated, it has several nice properties: If there are no forks, the number of confirmations for each transaction is exactly what one would expect: Once a transaction is in a block, it has one confirmation, if there is a subsequent block, it has two confirmations and so forth. However, if there are multiple competing forks with similar heights, the number of confirmations will remain low until one chain prevails, at which point the number of confirmations start to increase. In short, the rule is meant to ensure that a large number of confirmations implies a large probability that the transaction will not be undone even in the presence of competing forks.

When the Bitcoin canister receives an outbound transaction and the transaction passes verification checks, it forwards the transaction to the Bitcoin adapter as described above. The Bitcoin canister caches the transaction and periodically resubmits it if the transaction does not appear in a block. The transaction is dropped once it appears in a block or it expires after 24 hours.

Developer Preview

The developer preview released on February 3, 2022, is an early release of the Bitcoin integration functionality. It is intended to be used by developers to start implementing smart contracts against the API and to give feedback so the API can be improved with community feedback towards the final release. The Developer Preview is available only as part of the local development environment (Canister SDK) and does not integrate with the Bitcoin mainnet or testnet. Instead, it runs a local bitcoin node (bitcoind) in regression testing ("regtest") mode that simulates a real Bitcoin network, while being fully controlled by the developer. This is preferable to a Bitcoin network integration for a local development environment due to being better suitable for testing because of the deterministic behaviour of the local Bitcoin node. The developer preview release makes all Bitcoin-related logic of the feature available through the APIs get_utxos, get_balance, and send_transaction. However, the integration with the IC protocol stack is simplified: It does not use the custom integration with the IC protocol layers, particularly consensus, but adds an Adapter Shim as external component that hooks up the Adapter to the regular iC protocol stack through query calls and ingress messages. Users of the developer preview need to install the release on top of their local Canister SDK environment and launch it. The Bitcoin canister is exposed as a Wasm canister instead of a virtual canister implemented as part of the replica, much like the management canister, as in the final release.