Bitcoin Integration

From Internet Computer Wiki
Revision as of 17:52, 23 March 2022 by Thomas.locher (talk | contribs)
Jump to: navigation, search

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 Internet Computer adds tremendous value: It leverages 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. 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 Internet Computer is integrated 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 trust assumptions are required other than trust in the correct functioning of the Bitcoin network and the Internet Computer. In other words, there can be no additional parties, such as bridges or other types of intermediaries, resulting in a much cleaner and more secure integration. In this trustless integration of Bitcoin and the Internet Computer, canisters can directly hold Bitcoin on the Bitcoin blockchain.

This direct integration is based on the following features:

  • Canisters can have Bitcoin addresses (and therefore 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 relies on a threshold ECDSA protocol that enables a subnet to compute ECDSA signatures based on a secret-shared private key on a canister's request. With this protocol, each canister can "control" a vast number of derivable ECDSA keys and obtain signatures for them, making it possible for canisters to receive, hold, and transfer Bitcoin directly on the Bitcoin blockchain in a secure manner. Naturally, a canister must be able to retrieve the UTXOs associated with its Bitcoin addresses. To this end, the Internet Computer pulls in blocks directly from the Bitcoin network. In the following, the underlying architecture of this integration is explored in more detail.

Architecture

In this section, we present the architecture for the direct integration with the Bitcoin blockchain on a high level. The integration changes and adds components at every layer of the Internet Computer (IC) protocol stack.

A high-level overview of the Bitcoin integration architecture.

The Bitcoin component ("BTC System Component" in the figure) is implemented at the execution layer as part of the replica and exposes the Bitcoin integration API via the virtual management canister. The API offers functions to query Bitcoin state (unspent transaction outputs (UTXOs), balances, and current transaction fees) and to submit transactions.

In order to serve up-to-date UTXOs, Bitcoin blocks must be pulled continously into the Internet Computer (IC) from the Bitcoin network and the set of all UTXOs (referred to as the "UTXO set") updated based on the transaction inputs and outputs contained in the blocks. This mechanism requires an architecture that spans all layers of the IC protocol stack and also includes a new component external to the replica.

The Bitcoin component in the execution layer maintains a set of recent Bitcoin blocks, the entire UTXO set, and a set of outgoing transactions submitted by canisters. The UTXO set and the recent blocks are used for responding to UTXO and balance queries of canisters.

The Bitcoin adapter, a sandboxed OS-level process external to the replica, connects to multiple Bitcoin nodes randomly using Bitcoin's peer discovery protocol. The Bitcoin adapter maintains a local copy of the whole block header chain as well as a small cache of blocks that it provides to the replica upon request.

In every IC round, the block maker, a core component of the consensus layer, sends a request from the Bitcoin component to the Bitcoin adapter and gets the response, which is then included in the IC block's payload. More precisely, the Bitcoin component stores the request in the replicated state, where it is picked up by the payload builder in the Consensus layer. The payload builder uses interprocess communication to relay the request to the external Bitcoin adapter, which handles the request and returns the result to the payload builder. The payload builder then incorporates the result in the IC block. A request contains hashes of recent block headers for which the Bitcoin component has the block of transactions as well as the outgoing transactions. The Bitcoin adapter matches the received block hashes with its view of the Bitcoin network and, if it has one or more successors of the blocks that the Bitcoin component has, returns these blocks. Furthermore, it adds the transactions received in the request to a queue for outgoing transactions to be submitted asynchronously to the Bitcoin network.

Every IC block is gossiped to the subnet nodes 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 payload contained in the IC block. It is crucial that the block maker 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, causing the entire IC block to be dropped.

Once the IC block with the Bitcoin payload has been validated successfully, 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 correct subnet queue to get executed. When the Bitcoin payload reaches the execution layer, it gets executed by the Bitcoin component it the execution layer: The payload is validated and the state of the Bitcoin component is updated accordingly.

Creating a Bitcoin transaction requires computing one ECDSA signature per UTXO used as transaction input. Canisters can request ECDSA signatures through a threshold ECDSA API that is implemented as part of dedicated ECDSA signing subnets. One such subnet will be deployed initially and, 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. The threshold ECDSA API makes it possible for a canister to request an ECDSA signature computed jointly by the replicas of the ECDSA subnet based on a secret-shared private key.

Technical Details

As described in the previous section, canisters interact with the Bitcoin component using the Bitcoin integration API exposed through the management canister. The Bitcoin component 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.

Note that some technical details are not implemented in the developer preview, which is discussed in the next section. For example, several validity checks are not performed. These omissions are not crucial for a local testing environment.

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 Bitcoin nodes for addresses until it has received 2000 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 Bitcoin block headers.
  • A cache for Bitcoin blocks, which it expects the Bitcoin component to request next.
  • A cache for outgoing transactions that are advertised but not transmitted to Bitcoin nodes yet.

Initially, the adapter only has the hard-coded genesis block header 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 until it is fully synced. 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 previous block field points to a locally available block header.
  • The hash work in the block header is sufficient based on the difficulty target.
  • The timestamp in the block header is greater than the median of the 11 previous blocks.

The caches remain empty until requests from the Bitcoin component are received. Periodically, the Bitcoin component 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 are provided in the section about the Bitcoin component.

The Bitcoin adapter checks if it has any blocks that the Bitcoin component is missing and responds with a message containing the missing blocks, prioritizing blocks with a lower height. Multiple blocks can be returned in a single message up to a soft cap of 2 MB, ensuring that at least one Bitcoin block can be returned even if its size exceeds 2 MB. This upper bound implies that only one block (and block header) is returned for most of 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 component, the Bitcoin adapter then downloads the next missing blocks so that it can pack them into a return message in a future request from the Bitcoin component. 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 component 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 component 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.

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 as mentioned before. 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 component for ingestion.

Bitcoin Component

The Bitcoin component 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 API is offered through the Bitcoin component to enable other canisters to incorporate Bitcoin functionality.

State

The Bitcoin component 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 component 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 component 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 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): Let B denote the set of locally available blocks.
For a parameter 𝜹>0, we say that a block b is 𝜹-stable if the following conditions hold:
* d(b) ≥ 𝜹
* ∀ b’ ∈ B \ {b}, h(b’) = h(b): d(b) - d(b’) ≥ 𝜹

The Bitcoin component is configured with a stability threshold 𝜹 of 144, i.e., if there are no forks, the Bitcoin component 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 Component in Operation

When requesting an update from the Bitcoin adapter, the Bitcoin component sends a message containing the hashes of all unstable blocks to the Bitcoin adapter, which uses the hashes to determine which blocks the Bitcoin component 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.
  • The timestamp in the block header is greater than the median of the 11 previous blocks.

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.

As mentioned above, the Bitcoin component 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.

The following address formats are supported:

  • Pay to public key hash (P2PKH)
  • Pay to script hash (P2SH)
  • Pay to witness public key hash (P2WPKH)
  • Pay to witness script hash (P2WSH)

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 component 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. The stability count of a block is defined as 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, based on the stability count, implies a large probability that the transaction will not be undone even in the presence of competing forks.

When the Bitcoin component receives an outbound transaction and the transaction passes verification checks, it forwards the transaction to the Bitcoin adapter as described above. The Bitcoin component 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. Moreover, the Bitcoin component is exposed as a Wasm canister. Recall that the Bitcoin integration API is exposed through the management canister on mainnet.