How to use wallet compartments for key rotation

I’ve just read a transcript of an excellent Bryan Bishop’s talk “Wallet Security, Key Management & Hardware Security Modules (HSMs)” from Dev++ conference in Tokyo: https://diyhpl.us/wiki/transcripts/scalingbitcoin/tokyo-2018/edgedevplusplus/wallet-security/. He briefly mentions key rotation there, and the costs of doing it:

Key rotation, I haven’t even talked about key rotation, in theory everyone should be rotating their keys quite regularly because you never know when someone has stolen your private key. And key rotation on the bitcoin blockchain side has a cost, it has a fee associated with it, but if you have this multisig quorum stuff going on to access your bitcoin or control it, this is one way of minimizing costs while also improving your security situation.

The point here is that the keys, in theory, should be treated the same way as passwords — you are expected to change your password periodically. You may not know that your private key was leaked, just no one have discovered it yet, or a thief just waits until you make a big transfer to your wallet.

You may want to perform key rotation if one of the keys in multisignature scheme is compromised — your funds are still safe, but the protection is weakened.

For simple one-user wallet performing key rotation is trivial— just create a wallet with new keys and send everything to it. But for services that have a lot of users, with multiple address per user, and a lot of UTXO in their wallets, this transition can be complicated.

I’d like to expand on how key rotation can be performed in such large-scale setups, and how the costs associated with it can be minimized.

In Simplexum, we define a wallet as just a set of addresses. Initially, you create a wallet that have no associated addresses in it. Later, you can add an address, or a sequence¹ of HD-generated addresses to it. You can think of this as defining ‘compartments’ for the wallet:

Here, we have two sequences of BIP44-derived addresses from some 2of3 multisig configuration², and a donation address — all assigned to one wallet.

The relevant part for key rotation are two of the three things that are attached to combined_wallet at its right side, in the picture: receive and change. We call them ‘wallet endpoints’. Only the receive and change endpoints are required, but you can add more: in this example, a donation address have its own named compartment.

You can handle funds in the wallet as a whole: get balance on it and spend from it, but before you can get an address from the wallet, you need to configure the receive endpoint, to specify a compartment from where the address will come from. Same for change: when order-processor creates a transaction for the outgoing payment order from that wallet, it needs to know where to send the change.

How this can be used to facilitate key rotation ?

Let’s say your initial 2of3 config is becoming old, and you think it would be a good idea to change the keys.

You create another configuration — let’s call it 3of5_new, with different keys. You then define BIP44-derived sequences for it, and assign them to the wallet:

assign('seq://3of5_new/bip44/account/0/internal/.wlt',
       'combined_wallet')
assign('seq://3of5_new/bip44/account/0/external/.wlt',
       'combined_wallet')

Next, you redefine ‘receive’ and ‘change’ endpoints for the wallet:

assign(‘wlt://combined_wallet/.dst.receive’,
       ‘seq://3of5_new/bip44/account/0/external’)
assign(‘wlt://combined_wallet/.dst.change’,
       ‘seq://3of5_new/bip44/account/0/internal’)

Two old sequences are still a part of combined_wallet:

All funds from original 2of3 setup remain the wallet, too, but when you get new address from it, the address comes from 3of5_new’s external chain.

When you create outgoing payment order, order-processor will get destination address for change output from 3of5_new’s internal chain.

This way, as your wallet continue its operation, funds will gradually move from old 2of3 setup to new 3of5 setup, via change outputs. You can set ‘eviction score’ for 2of3 sequences, and funds from them will always be used first for outgoing transaction building — which will result in faster, but still gradual, transition.

As the transition happens along with regular payments, you are only paying network fee that you would be paying anyway, to send these payments.

If you need to move the funds right now, you can always create an order to sweep them:

acc0_balance = balance('seq://2of3/bip44/account/0/*')
create('ord://move-obsolete-2of3',
       src='seq://2of3/bip44/account/0/*', # all seqs under this path
       dst='wlt://combined_wallet',
       amount=acc0_balance,
       charge_fee='ben',       # charge fee from recipient
       no_change_output=True)  # we are sending whole balance,
                               # change output is not required

But of course this will create a separate sweeping transaction, and you will be paying current network fee on it.

When you no longer accept funds on the old 2of3 addresses, you can remove these sequences from the wallet, and retire the keys. Or you can leave them attached, with high eviction score. If an occasional payment is sent to these addresses, these coins will be selected for spending first, and the change will be sent to addresses of 3of5_new configuration.

Footnotes:

1. ^ We use the term ‘sequences’, and not ‘chains’, because you can also have a sequence of addresses not derived from xpriv, but created from randomly-generated keys (maybe you have them from legacy setup, and cannot retire them yet, or you want vanity addresses). Randomly-generated addresses do not depend on one shared extended key, so they are not a ‘chain’.
2. ^ The named ‘2of3’ and ‘3of5_new’ configurations are an example of what we call a ‘sequence base’ —it specifies what private keys participate in controlling the funds, how they participate, what address formats will be used, etc. If some of the participating keys are HD keys, then multiple sequences can be created on top of the sequence base, with different HD derivation paths.