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 our a Bitcoin Vault Design
1.Access funds using Schnorr Signatures as generated by our FROST protocol​
2.Deterministically generate an arbitrary number of Deposit Channel Addresses (Ingress Addresses) that are all controlled by the same key
3.Ability to send a single transaction that sweeps funds from multiple Deposit Channel Addresses into a central vault
4.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
5.Minimise the number of necessary signatures for any transaction
Some Background Information 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, 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, 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:
1.The nonce n must be chosen such that r=n×Gr = n\times Gr=n×G
 has an even y-coordinate ryr_yry​
. To “fix” a nonce, one can just substitute n→Q−nn \rightarrow Q - nn→Q−n
 where QQQ
 is the known group order of the secp256k1 curve. To fix the corresponding rrr
, 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:
zi={λi⋅si⋅c+di+(ei⋅ρi)mod  Q,if ry evenλi⋅si⋅c−di−(ei⋅ρi)mod  Q,if ry oddz_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}zi​={λi​⋅si​⋅c+di​+(ei​⋅ρi​)modQ,if ry​ evenλi​⋅si​⋅c−di​−(ei​⋅ρi​)modQ,if ry​ odd​
2.Same thing 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.
3.The signature is just the concatenation of the 32-byte padded, big-endian x-coordinate of rrr
, 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 and BIP 342. 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”. 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 can 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 where the salt is chosen as 3 in this example and the hex blob is our public key:
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.
Sweeping Inputs from Different Despoit Channels 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 would 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. We can imagine a process for this as follows:
Multi-Stage Keyshare Handover Protocol Example
Preliminaries:
Let A\mathbb{A}A
 be the old validator that leaves the set and B\mathbb{B}B
 be the new validator joining. A\mathbb{A}A
 needs to pass its secret share aaa
 with known public key A=gaA = g^{a}A=ga
  to B\mathbb{B}B
, who has just generated its new secret share bbb
 with known public key B=gbB = g^{b}B=gb
 . Let H\mathcal{H}H
 be a cryptographically secure hash function, K\mathcal{K}K
 a suitable key-derivation function, ℓ\ellℓ
 a unique session identifier for the current key ceremony, ⊕\oplus⊕
 the bitwise XOR operator and ∣∣|| ∣∣
 the concatenation operator.
Step 1:
​A\mathbb{A}A
 calculates a random value ttt
 and publishes
T=gtm=t⊕K(ℓ∣∣Bt)T = gt \\ 
m = t ⊕ K(ℓ||B^t)T=gtm=t⊕K(ℓ∣∣Bt)
Step 2:
​B\mathbb{B}B
 recovers t=m⊕H(ℓ∣∣Tb)t = m \oplus \mathcal{H}(\ell||T^{b})t=m⊕H(ℓ∣∣Tb)
and verifies that gt=Tg^t=Tgt=T
. 
If the verification works, B\mathbb{B}B
 indicates agreement by calculating a random nonce nnn
 and publishing
N=gnz=n−bH(ℓ∣∣N∣∣T)N = g^n \\ z = n-b\mathcal{H}(\ell ||N||T)N=gnz=n−bH(ℓ∣∣N∣∣T)
If the verification fails, B\mathbb{B}B
 complains to the rest of the validators.
Step 3 (B\mathbb{B}B
 agreed in step 2):
​A\mathbb{A}A
 verifies that N=gzBH(ℓ∣∣N∣∣T)N = g^zB^{\mathcal{H}(\ell ||N||T)}N=gzBH(ℓ∣∣N∣∣T)
. If this works, she publishes k=t−ak =t-ak=t−a
 . If it doesn’t work, A\mathbb{A}A
  complains to the rest of the validators, who also try the verification. If they find that it fails B\mathbb{B}B
  is slashed, else A\mathbb{A}A
 is slashed.
Step 3 (B\mathbb{B}B
 complained in step 2):
​A\mathbb{A}A
 publishes ttt
. All other validators use the published ttt
 to calculate mmm
 and TTT
 as above and verify that they match the values published in step 1. If they do, B\mathbb{B}B
 is slashed. If they don’t match, A\mathbb{A}A
 is slashed.
Step 4:
​B\mathbb{B}B
  recovers a=t−ka = t-ka=t−k
  and verifies A=gaA=g^{a}A=ga
. If this doesn’t work, B\mathbb{B}B
 complains and everyone verifies that gk=TA−1g^k=TA^{-1}gk=TA−1
. If this fails, A\mathbb{A}A
 is slashed, otherwise, B\mathbb{B}B
 is slashed.
In this protocol, any validators that remain in the new set can just keep their old shares. Only leaving/joining validators need to perform the handover. If no complaints arise throughout the process, no other validators need to get involved and it can be performed only between the two parties.
In the situation that a validator from the old set disappeared and does not participate in the handover, or misbehaves during the handover or the sizes of the old and new validator set don’t match, we need to transform the key so that it satisfies the threshold signing requirements for the new validator set.

For this it is sufficient to run another FROST key-generation (called Key Re-sharing in code), with the only difference that in Step 1 of Round 1 of the FROST key-generation, the participant PiP_iPi​
 only samples t−1t-1t−1
 random values to define ai1...ai(t−1)a_{i1}...a_{i(t-1)}ai1​...ai(t−1)​
. Then they set ai0=λjxja_{i0} = \lambda_jx_jai0​=λj​xj​
, where xjx_jxj​
 is the secret key share they received from a previous validator set and λj\lambda_jλj​
 is the Lagrange interpolation polynomial for the identifier of the xjx_jxj​
 and a set size α\alphaα
 equal to the number of keys that were successfully transitioned from the old set. If PiP_iPi​
 did not receive a key share, they simply set ai0=0a_{i0} = 0ai0​=0
. This will produce a new set of key shares for an arbitrary validator set with an arbitrary signing threshold, as long as the number of transitioned keys is equal or larger than the threshold of the previous validator set.
Chainflip Single-Phase Keyshare Handover Protocol
The mechanism mentioned above has two phases: (1) to ensure that there is a threshold of holders of the existing key in the new set of validators, and (2) to perform a key re-sharing ceremony entirely within the new validator set to generate N new shares of the existing key. In practice, we can develop this further to cut down the process into just one phase: a modified version of a Re-Sharing 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 V1V_1V1​
 denote the set of existing validators, and let V2V_2V2​
 denote the set of new validators. Note that V1V_1V1​
 and V2V_2V2​
 are not necessarily disjoint. To simplify notation lets assume ∣V1∣=∣V2∣=n|V_1| = |V_2| = n∣V1​∣=∣V2​∣=n
 (generalising the protocol for ∣V1∣≠∣V2∣|V_1| \ne |V_2|∣V1​∣=∣V2​∣
 should be relatively straightforward). The goal of the protocol is for V2V_2V2​
 to obtain a new set of shares for the t/nt/nt/n
 key that V1V_1V1​
 collectively hold.
The implementation will be based on the existing keygen/re-sharing implementation with the following modifications:
 We will select ttt
 validators (denoted VSV_SVS​
) from V1V_1V1​
 that will participate in the ceremony together with V2V_2V2​
. In practice we expect most (if not all) of VSV_SVS​
 to also be in V2V_2V2​
, but we make no such assumption in the protocol. The ceremony will thus have n′=∣VS∪V2∣n' =|V_S \cup V_2|n′=∣VS​∪V2​∣
 participants, and we will use n′n'n′
 “votes” (rather than nnn
) when determining the outcome of the ceremony: e.g. we will require at least 23⋅n′{2\over3}\cdot n'32​⋅n′
 reports against a particular party before penalising them.
An additional stage will be added (Stage 0) in which VSV_SVS​
 will broadcast public key shares of every party in VSV_SVS​
 corresponding to the original key. These are the keys that will be used in Stage 4 to check that VSV_SVS​
 have set their secret correctly. Participants not in VSV_SVS​
 will assume that the values broadcast by the majority from VSV_SVS​
 to be correct (using the same principle as described in Broadcast Verification section ofhttps://www.notion.so/chainflip/FROST-implementation-44643d46165c4893aeb998517430bbae).
In Stage 1 only participants from VSV_SVS​
 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 VSV_SVS​
 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 V2V_2V2​
. Importantly VSV_SVS​
 will use a sharing polynomial corresponding to a t/nt/nt/n
 key (rather than t′/n′t'/n'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 V2V_2V2​
 will be taken into account. At the end of the ceremony we expect V2V_2V2​
 to collectively hold nnn
 shares (with threshold ttt
) of the key originally held by V1V_1V1​
.
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, this article, BIP 131 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.
Some Additional Learning Resources (written for macs for now)
Read the book “Mastering Bitcoin” for some nice details on how Bitcoin works. It’s available for free here.
To play around with Bitcoin without needing a full node, you can run an instance of the regtest network, which is a local test network with your computer as the only node:
On Mac, download a suitable version of the bitcoin-core application from here. Open the file, install by dragging the Bitcoin icon into the application folder. Start a terminal and run
/Applications/Bitcoin-Qt.app/Contents/MacOS/Bitcoin-Qt -regtest
If it doesn’t start, go to “System Settings” → “Privacy & Security”, scroll down. There should be an entry asking about the Bitcoin software. Allow it to be started and retry the above command.
In the Bitcoin software, click on “Bitcoin Core” in the menu bar and select “Preferences”. Click on “Open Configuration File” → “Continue” and add this line to the config file:
regtest=1
Save and close the editor. Now the Bitcoin app will always start in regtest mode, even when started via Spotlight or similar.
Blocks are not mined automatically in regtest, so we need to do this by hand. Create a new wallet and a “receive” address. Copy the address into your clipboard, then press ⌘T to open a terminal. run generatetoaddress 107 YOUR_ADDRESS_GOES_HERE (replace with the address from your clipboard, obviously) in order to mine 107 blocks, with all rewards going to your provided address. This is necessary, because the mining rewards for the first 100 blocks are not spendable in Bitcoin (weird bug), and the wallet will only consider funds available if they have 6 blocks of confirmation. If you later want to send some transactions, you can rerun this command with a lower blockcount (even 1) to mine new blocks and include your submitted transactions.
To try some taproot features, go here and get the source code for btcdeb, the BitcoinDebugger. Follow the instructions for building it. If you use an M1 Apple machine and the build fails, comment out the line that says libbitcoin_a_LIBADD = $(LIBSECP256K1) in Makefile.am (should be line 89), run make clean and retry. Now you can use the “tap” executable to follow this tutorial.
​
Last modified 1mo ago