Bitcoin Vault Design

Bitcoin is the oldest and most widely traded asset in the cryptocurrency industry. To support native cross-chain swaps between Bitcoin and the rest of the ecosystem, we have designed a unique Vault that allows the Chainflip Validator network to maintain continuous service over a pool of protocol-controlled funds.

Features of the Bitcoin Vault Design

Access funds using Schnorr Signatures as generated by our FROST protocol
Deterministically generate an arbitrary number of Deposit Channel Addresses (Ingress Addresses) that are all controlled by the same key
Ability to send a single transaction that sweeps funds from multiple Deposit Channel Addresses into a central vault
Ability to perform a “key rotation” from one Authority Set to the next, whilst maintaining access to older ingress addresses, even after a key rotation has occurred
Minimise the number of necessary signatures for any transaction

Background on Bitcoin

Bitcoin behaves differently from most other cryptocurrencies. In Bitcoin, there exists no strict notion of an “address” as in other protocols. An address simply tells the sender of a transaction how to prepare that transaction so that the recipient may access the funds. Each transaction produces one or more “outputs” (Also called UTXOs = “Unspent Transaction Outputs”). Each output specifies an amount of Bitcoin that it contains, as well as a “locking script” (Bitcoin calls these locking scripts “ScriptPubKey”). The locking script is a small program, written in Script (opens in a new tab), which defines under what conditions the coins contained in the output may be spent (the conditions of this script “lock” the funds in the output). An address in Bitcoin is a short way to represent such a locking script, i.e. sending funds to a given address will always result in an output with the same locking script.

In order to spend the funds in an output, one must send a transaction that references an output to be spent, as well as another script, called the “unlock script” (Bitcoin calls this the “ScriptSig”). If the unlock script satisfies the conditions set up by the locking script, the funds can be used. Typically, a Bitcoin address contains the Hash of a public key. The corresponding locking script takes as input a public key and a signature and demands that the hash of the provided public key matches the Hash in the address. It also demands that the provided signature signs the details of the output and matches the provided public key. The unlock script simply provides these two inputs (public key and signature).

Accessing BTC Using FROST Protocol Schnorr Signatures

In November 2021, the Bitcoin protocol activated the “Taproot” feature, which consisted of several changes. One of these changes is BIP 340 (opens in a new tab), which introduces support for Schnorr Signatures. By using Taproot addresses as our ingress addresses, we can unlock any output sent to one of our ingress addresses by providing a valid Schnorr Signature. Bitcoin puts some additional constraints on Schnorr signatures, specifically:

The nonce n must be chosen such that $r = n\times G$ has an even y-coordinate $r_y$ . To “fix” a nonce, one can just substitute $n \rightarrow Q - n$ where $Q$ is the known group order of the secp256k1 curve. To fix the corresponding $r$ , one can either recalculate it from the fixed nonce, or just flip the sign of its y-coordinate.

In the context of FROST multisig, the nonce n is never exposed to any party for security reasons, but r can be calculated. To implement this fix for FROST multisig, each participant calculates their share of the signature as in step 5 of the FROST signing protocol but using:

z_i = \begin{cases}\lambda_i\cdot s_i\cdot c + d_i + (e_i\cdot\rho_i) \mod Q, \hspace{2em} \text{if } r_y \text{ even} \\ \lambda_i\cdot s_i\cdot c - d_i - (e_i\cdot\rho_i) \mod Q, \hspace{2em} \text{if } r_y \text{ odd}\end{cases}

The same applies for the private/public key pair: The y-coordinate of the public key must be even. This can be implemented using the same mechanism already used for providing “compatible” keys in our Ethereum implementation.
The signature is just the concatenation of the 32-byte padded, big-endian x-coordinate of $r$ , and the 32-byte padded, big-endian representation of s.

Taproot addresses “look just like” normal bech32 addresses in bitcoin, so any wallet that correctly supports sending to bech32 (should be most wallets) will be able to send to our ingress addresses.

Deterministically Generating an Arbitrary Number of Deposit Channel Addresses All Controlled by the Same Key

Another change introduced by Taproot are “MAST” scripts (”Merkelized Abstract Syntax Tree”). Details are provided in BIP 341 (opens in a new tab) and BIP 342 (opens in a new tab). These changes allow replacing the locking script of an output with a hash value. Now there are two options: Either, the hash value is interpreted as a public key and the funds may be spent by providing a valid signature for this public key, or the hash value is the hash of an (arbitrarily complex) locking script which needs to be satisfied in order to spend the funds. The unlock script trying to spend the funds needs to select one of these options and then either provide the required signature, or the “real” locking script that produces the hash together with the requirements to unlock it. Furthermore, any code branches in the locking script (if-else etc.) will result in a binary tree of code paths, and the code of each possible path is hashed separately, resulting in a “Merkle tree (opens in a new tab)”. Only the root hash of this Merkle tree is used as the hash value in the locking script. The unlock script only needs to provide the code for the path that will be traversed during the unlocking (this results in additional privacy, as well as reduced size of the unlock script). We could now define a locking script that essentially looks like this:

if false {
  let constant = 1337; // Some salt
} else {
  let publicKey = ...; // Our Schnorr pubkey
  check_provided_signature_for(publicKey);
}

This script has two code paths, but the first one will never be executed, because the condition is always false. Inside it, we can specify a different salt for each ingress address. The other code path is always the same and uses our public key to check the provided signature. Because of the salt, the Merkle hash will be different for each salt, resulting in a different ingress address, even though the public key is always the same. In practice, we do not use the Merkle tree feature, because of some additional complications. Instead, we use scripts like this (the salt is chosen as 3 in this example) :

OP_3 OP_DROP 59B2B46FB182A6D4B39FFB7A29D0B67851DDE2433683BE6D46623A7960D2799E OP_CHECKSIG

In general, the script consists of pushing the salt value onto the stack, then dropping it, then pushing our public key onto the stack and then running OP_CHECKSIG. For different salts, this will still generate different addresses.

Sweeping funds from different deposit addresses into the central vault

Because Bitcoin has a different notion of what an “address” is, this feature is provided trivially in Bitcoin. Any transaction can specify multiple UTXOs to be used as “inputs” to that transaction. As long as the locking scripts of all UTXOs are satisfied, the single transaction can now spend the combined funds of all the referenced UTXOs. We prepare a single transaction that uses the UTXOs of all our different ingress addresses and spends them into our vault.

Bitcoin Vault Rotations

Because our Vault is simply another Bitcoin address, a key rotation would just consist of a single transaction of all the funds from the old vault to a new address, which is controlled by a different key.

However, There is no way to change the locking script of an existing UTXO, so funds that are sent to an old ingress address (such as from an open despoit channel created during the previous Epoch) must be unlocked using the corresponding (old) key. If a validator set changes and the mutual key is replaced, the old key will not be accessible going forward. To handle this, we can't just “abandon” any funds sent to older addresses. We could force validator members to keep their old key shares for a certain period of time, or we find a way to “handover” the control of old ingress addresses to the new key. For various reasons, we chose the “handover” option.

As one validator set transitions to the next, most members will probably stick around, so the set of old/new members that need to perform the handover is going to be quite small in practice. Nevertheless, this procedure would also work when completely replacing a validator set entirely.

Chainflip Keyshare Handover Protocol

We developed a modified version of the FROST keygen ceremony, in which both new validators and (some fraction) of old validators take part. This is the keyshaing protocol that we have implemented in our Bitcoin vault and can be applied across many more chains.

Let $V_1$ denote the set of existing validators, and let $V_2$ denote the set of new validators. Note that $V_1$ and $V_2$ are not necessarily disjoint. To simplify notation lets assume $|V_1| = |V_2| = n$ (generalising the protocol for $|V_1| \ne |V_2|$ should be relatively straightforward). The goal of the protocol is for $V_2$ to obtain a new set of shares for the $t/n$ key that $V_1$ collectively hold.

The implementation will be based on the existing keygen/re-sharing implementation with the following modifications:

We will select $t$ validators (denoted $V_S$ ) from $V_1$ that will participate in the ceremony together with $V_2$ . In practice we expect most (if not all) of $V_S$ to also be in $V_2$ , but we make no such assumption in the protocol. The ceremony will thus have $n' =|V_S \cup V_2|$ participants, and we will use $n'$ “votes” (rather than $n$ ) when determining the outcome of the ceremony: e.g. we will require at least ${2\over3}\cdot n'$ reports against a particular party before penalising them.
An additional stage will be added (Stage 0) in which $V_S$ will broadcast public key shares of every party in $V_S$ corresponding to the original key. These are the keys that will be used in Stage 4 to check that $V_S$ have set their secret correctly. Participants not in $V_S$ will assume that the values broadcast by the majority from $V_S$ to be correct
In Stage 1 only participants from $V_S$ will set their secret to their existing shares. Other participants will set their secrets to 0. Note that this is already supported by the current key re-sharing implementation.
Just like in Key-Resharing, in Stage 4 (fast-forwarding past broadcast verification and hash commitments stages) all participants will check coefficient commitments against public key shares (known by $V_S$ or received during Stage 0 by the rest of participants), aborting the ceremony if commitments are incorrect, reporting the misbehaving parties.
In Stage 5 secret shares will only be generated and sent to parties from $V_2$ . Importantly $V_S$ will use a sharing polynomial corresponding to a $t/n$ key (rather than $t'/n'$ ).
From here onward the ceremony will proceed exactly like a regular keygen ceremony with the exception that only complaints (sent in Stage 6) from $V_2$ will be taken into account. At the end of the ceremony we expect $V_2$ to collectively hold $n$ shares (with threshold $t$ ) of the key originally held by $V_1$ .

Minimising the Number of Necessary Signatures for Any Transaction

Bitcoin requires a separate signature (over different data) for every single UTXO spent by a transaction, even if all the UTXOs use the same locking script. This means that we need to do a FROST signing for each ingress payment, even if we ultimately only submit a single transaction (As explained above). Numerous suggestions exist on how this requirement could be changed so that a single signature is sufficient (see BIP 118 (opens in a new tab), this article (opens in a new tab), BIP 131 (opens in a new tab) etc.), but none of these have been implemented in Bitcoin yet. Currently, we would need to sign multiple pieces of data through FROST in order to sweep funds from our ingress addresses. FROST is only “slow” when generating new keys, though. Signing is pretty fast, and we estimate that we can handle 30+ BTC deposit sweeps every minute without impacting the wider protocol.

Governance & Security EVM (Ethereum) Vault Design