Difference between revisions of "Bitcoin Integration"

From Internet Computer Wiki
Jump to: navigation, search
Line 29: Line 29:
 
The Bitcoin canister maintains a set of recent Bitcoin blocks and the entire UTXO set, which are used together to respond to UTXO and balance queries of canisters.
 
The Bitcoin canister maintains a set of recent Bitcoin blocks and the entire UTXO set, which are used together to respond to UTXO and balance queries of canisters.
  
The ''Bitcoin adapter'', a sandboxed OS-level process external to the replica, connects to multiple Bitcoin nodes chosen 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.
+
The ''Bitcoin adapter'', an OS-level process external to the replica, connects to multiple Bitcoin nodes chosen 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 canister to the Bitcoin adapter and gets the response, which is then included in the IC block's payload. More precisely, the Bitcoin canister 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.
+
In every IC round, the block maker, a core component of the consensus layer, sends a request from the Bitcoin canister to the Bitcoin adapter and gets the response, which is then included in the IC block's payload. More precisely, the Bitcoin canister makes a call to access internal replica APIs to store 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 canister has the block of transactions as well as the outgoing transactions. The Bitcoin adapter compares the received block hashes against its view of the Bitcoin network: if its cache contains one or more successors of the blocks that the Bitcoin canister has, it 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.
 
A request contains hashes of recent block headers for which the Bitcoin canister has the block of transactions as well as the outgoing transactions. The Bitcoin adapter compares the received block hashes against its view of the Bitcoin network: if its cache contains one or more successors of the blocks that the Bitcoin canister has, it 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 may not be reached, causing the entire IC block to be dropped.
 
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 may not be reached, 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 for execution. When the Bitcoin payload reaches the execution layer, it gets executed by the Bitcoin canister: The payload is validated and the state of the Bitcoin canister is updated accordingly.
+
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 for execution. When the Bitcoin payload reaches the execution layer, it gets sent to the Bitcoin canister where the payload is validated and the state of the Bitcoin canister is updated accordingly.
  
 
Creating a Bitcoin transaction requires computing one ECDSA signature per UTXO used as transaction input. Canisters can request ECDSA signatures through the threshold ECDSA API that is implemented as part of dedicated chain-key signing subnets. There is one such subnet deployed 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.
 
Creating a Bitcoin transaction requires computing one ECDSA signature per UTXO used as transaction input. Canisters can request ECDSA signatures through the threshold ECDSA API that is implemented as part of dedicated chain-key signing subnets. There is one such subnet deployed 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.
Line 96: Line 96:
 
* The balances of all addresses in the UTXO set.
 
* The balances of all addresses in the UTXO set.
 
* Blocks including their block headers starting from block height h+1.
 
* Blocks including their block headers starting from block height h+1.
* The full history of all received block headers.
+
* The full history of block headers of ''stable blocks'' (the notion of stability is defined below).
  
 
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.
 
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.
Line 164: Line 164:
 
[[File:Stability example.png|thumb|center|upright=3|A chain with a fork is shown, including both the stability counts (inside the blocks) and confirmation counts (inside the circles).]]
 
[[File:Stability example.png|thumb|center|upright=3|A chain with a fork is shown, including both the stability counts (inside the blocks) and confirmation counts (inside the circles).]]
  
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.
+
When the Bitcoin canister receives an outbound transaction and the transaction passes a basic verification that the transaction can be decoded, it forwards the transaction to the Bitcoin adapter as described above.
 
There is no guarantee that the transaction will ever be included in a block. It is up to the issuer of the transaction to maximize the chances to get the transaction into a block by making sure that the transaction is valid and including an appropriate miner fee.
 
There is no guarantee that the transaction will ever be included in a block. It is up to the issuer of the transaction to maximize the chances to get the transaction into a block by making sure that the transaction is valid and including an appropriate miner fee.
  

Revision as of 12:20, 9 December 2022

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 fully consumed when used as inputs for other transactions that create new transaction outputs.

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 is decentralized finance (DeFi) built around Bitcoin, which can currently be implemented only with wrapped Bitcoin requiring additional trusted entities. Moreover, Bitcoin can be used to pay 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 to make powerful smart contract functionality available for Bitcoin through a direct, bridgeless, integration of the two blockchains. "Direct" 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 are no additional parties required, such as bridges or other types of intermediaries, resulting in a much cleaner and more secure integration.

This direct integration has the following main features:

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

The direct, bridgeless, integration relies on a novel threshold ECDSA protocol that enables a subnet to compute ECDSA signatures based on a secret-shared private key upon 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 main component is the Bitcoin canister, which runs on a system subnet and exposes the Bitcoin integration endpoints through the virtual management canister interface. The API offers functions to query Bitcoin state (UTXOs, balances, and current transaction fees) and to submit transactions.

In order to serve up-to-date information about the Bitcoin state, Bitcoin blocks must be pulled continuously into the Internet Computer 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.

The Bitcoin canister maintains a set of recent Bitcoin blocks and the entire UTXO set, which are used together to respond to UTXO and balance queries of canisters.

The Bitcoin adapter, an OS-level process external to the replica, connects to multiple Bitcoin nodes chosen 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 canister to the Bitcoin adapter and gets the response, which is then included in the IC block's payload. More precisely, the Bitcoin canister makes a call to access internal replica APIs to store 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 canister has the block of transactions as well as the outgoing transactions. The Bitcoin adapter compares the received block hashes against its view of the Bitcoin network: if its cache contains one or more successors of the blocks that the Bitcoin canister has, it 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 may not be reached, 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 for execution. When the Bitcoin payload reaches the execution layer, it gets sent to the Bitcoin canister where the payload is validated and the state of the Bitcoin canister is updated accordingly.

Creating a Bitcoin transaction requires computing one ECDSA signature per UTXO used as transaction input. Canisters can request ECDSA signatures through the threshold ECDSA API that is implemented as part of dedicated chain-key signing subnets. There is one such subnet deployed 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 canister to retrieve information about the Bitcoin state and send transactions. 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 5 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 5 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 maintains the following state:

  • All Bitcoin block headers.
  • A cache for Bitcoin 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 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 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 are provided in the section about the Bitcoin canister.

The Bitcoin adapter checks if it has any blocks that the Bitcoin canister 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 advantageous mainly for the Bitcoin testnet where blocks are usually significantly smaller.

If the Bitcoin adapter does not have the missing blocks in its cache, it immediately returns an empty message to prevent an unnecessary delay in the Consensus layer. Having an accurate view on the state of the Bitcoin canister, the Bitcoin adapter then downloads the next missing blocks so that it can put them into 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 blocks.

When the Bitcoin adapter receives outbound transactions, they are placed in the transaction cache and advertised to the Bitcoin network. The transactions are transmitted to the connected Bitcoin peers upon request and removed from the cache after 10 minutes. There is no guarantee that the transactions are ever requested by connected peers.

Bitcoin Canister

As mentioned above, the Bitcoin canister is the main component as it provides access to the Bitcoin integration API.

State

For a certain block height h, defined below, the Bitcoin canister stores the following state:

  • The full UTXO set from genesis up to block height h.
  • The balances of all addresses in the UTXO set.
  • Blocks including their block headers starting from block height h+1.
  • The full history of block headers of stable blocks (the notion of stability is defined below).

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.

Fork Resolution

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, a block is considered stable if there is 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 the tip of the chain containing the block.

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’) ≥ 𝜹

Since Bitcoin uses the weight of forks to determine the "correct" chain, the Bitcoin canister uses a generalization of 𝜹-stability, dubbed weighted 𝜹-stability, to evaluate forks. The difference to 𝜹-stability defined above is that weighted 𝜹-stability uses a weight-based depth function dw(b):

For any block b, let p be the most recent block up to and including block b itself that is the only block at its height. The depth dw(b) is the sum of the weights of all successors and block b itself, divided by the weight of block p.

Note that if all blocks have the same weight, we have that d(b) = dw(b) for every block b.

The Bitcoin canister is configured with a weighted 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 "weighted 144-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: h is the largest height with a weighted 144-stable block.

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 timestamp in the block header is greater than the median of the 11 previous blocks.
  • The timestamp in the block header is at most two hours in the future with respect to IC time.
  • 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.

It is important to note that the validity of transactions is not verified in the Bitcoin canister. The Bitcoin canister relies on the proof of work that goes into the blocks and the verification of the blocks in the Bitcoin network. For a newly discovered block, a regular Bitcoin (full) node therefore provides a higher level of security than the Bitcoin canister, which implies that it is advisable to set the number of confirmations to a reasonably large value to gain confidence in the correctness of the information provided by the Bitcoin canister.

If the verification is successful, the block is added to the list of unstable blocks. Additionally, if a block becomes (weighted 144-)stable as a result, the UTXO set is updated based on the transaction in this block and the block is discarded, keeping only the corresponding block header.

The (virtual) management canister exposes the following Bitcoin integration API:

  • bitcoin_get_utxos: The function returns the unspent transaction outputs (UTXOs) of a given Bitcoin address.
  • bitcoin_get_balance: The function returns the balance of a given Bitcoin address.
  • bitcoin_send_transaction: The function sends the given transaction to the Bitcoin network.
  • bitcoin_get_current_fee_percentiles: The function returns the percentiles of the fees, in satoshi per virtual byte, for the last 10,000 transactions.

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 Bitcoin integration API can be found in the Internet Computer specification.

In order to reduce the risk of inconsistencies due to forks, confirmations are counted conservatively, using 𝜹-stability (and not weighted 𝜹 stability). The stability count of a block is defined as the largest 𝜹 so that the block is 𝜹-stable. The number of confirmations for a transaction in a block is defined as the stability count of the block plus 1 (adding 1 because a transaction already has 1 confirmation once it appears in a block). There is one special case: If there are (at least) two longest forks, the stability count at the tip of these forks is 0. In fact, all blocks between the block where the diversion occurred and the tips have a stability count of 0 as well. If UTXOs with a single confirmation are to be returned, it is unclear which fork to consider. In this case, no blocks with a stability count of 0 are considered in the response.

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 for blocks on the competing forks until one fork prevails, at which point the number of confirmations starts 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.

The following figure shows an example of a chain with a fork. The numbers inside the blocks are the stability counts and the numbers in the circles in the lower-right corner of the blocks indicate the number of confirmations for transactions in the corresponding block for all blocks on the longest chain.

A chain with a fork is shown, including both the stability counts (inside the blocks) and confirmation counts (inside the circles).

When the Bitcoin canister receives an outbound transaction and the transaction passes a basic verification that the transaction can be decoded, it forwards the transaction to the Bitcoin adapter as described above. There is no guarantee that the transaction will ever be included in a block. It is up to the issuer of the transaction to maximize the chances to get the transaction into a block by making sure that the transaction is valid and including an appropriate miner fee.

Bitcoin Testnet Release

In summer 2022, the Bitcoin testnet integration was released on the IC. The Testnet Integration is intended to allow engineers to interact with the Bitcoin API on the IC, but only with Bitcoin Testnet and a threshold ECDSA test key. The goal is to allow engineers to build and test their Bitcoin-integrated dApps using a beta running on the IC. This is the next step after the previously-launched developer preview that facilitates dApp development through the community. It is strongly advised that engineers do not associate any value with the threshold ECDSA test key as it may be deleted at some point in time and it is running only on regular-size subnet.

Bitcoin Mainnet Release

The Bitcoin integration was released on the IC in the beginning of December 2022, making all Bitcoin integration features available for Bitcoin mainnet.

See Also