Multi-Account Hierarchy for P2WSH Multi-signature Deterministic Wallets

bip-xxxx.mediawiki

  BIP: x
  Layer: Applications
  Title: Multi-Account Hierarchy for P2WSH Multi-signature Deterministic Wallets
  Author: Braydon Fuller <[email protected]>
  Comments-Summary: No comments yet.
  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-x
  Status: Draft
  Type: Standards Track
  Created: 2019-02-12
  License: PD

Table of Contents Abstract Motivation Specification Purpose Coin type Shared account Change Address index Transaction creation and signing Shared account import Shared account export Address gap limit Examples Compatible wallets Test vectors Reference Copyright

Abstract

This BIP defines a structure for multi-account hierarchical deterministic P2WSH (BIP143) multi-party multi-signature wallets based on the algorithm described in BIP32 and purpose scheme described in BIP43. It is intended to be implemented along-side BIP44.

This BIP is a particular application of BIP43.

Motivation

With the usage of P2WSH (BIP143) transactions it is necessary to have a common derivation scheme for multi-signature wallets.

The structure proposed in this paper is quite comprehensive. It allows the handling of multiple coins, multiple accounts, external and internal chains per account and millions of addresses per chain. It defines standard ways to create, use, import, and store wallets. It allows to handle multiple parties sharing an m-of-n wallet, on the following assumptions:

• n parties share an m-of-n wallet.
• Each party generates their master private keys independently.
• Multisig P2WSH (BIP143) is used for all addresses. Additional proposals can extend this for use with other addresses using a different purpose field.
• BIP32 is used to derive public keys, then create a multisig script, and the corresponding P2WSH address for that script.
• Address generation should not require communication between parties after the initial shared account setup.
• Transaction creation and signing requires communication between parties.
• A single master node (seed) can be used for multiple shared accounts with different parties, as is often the case with hardware.

Specification

We define the following levels in BIP32 path:

m / purpose' / coin_type' / shared_account' / change / address_index

Apostrophe in the path indicates that BIP32 hardened derivation is used.

Each level has special meaning described in the chapters below.

Purpose

Purpose is a constant set to x, following the BIP43 recommendation. It indicates that the subtree of this node is used according to this specification.

m / x' / *

Hardened derivation is used at this level.

Coin type

One master node (seed) can be used for many independent coins such as Bitcoin, Handshake, and others. However, sharing the same space for various coins has some disadvantages.

This level creates a separate subtree for every coin, avoiding reusing addresses across coins and improving privacy issues.

Coin type is a constant, set for each coin. Coin developers may ask for registering unused number for their project.

The list of already allocated coin types is in the chapter "Registered coin types" from BIP44.

Hardened derivation is used at this level.

Shared account

This level splits the key space for independent shared accounts.

Users can use these shared accounts to organize with different groups of cosigners and for different purposes; donations (where all addresses are considered public), for saving, for common expenses etc.

This number is used as child index in BIP32 derivation.

Hardened derivation is used at this level.

To create a new shared account; each party shares their extended shared account public key with the other cosigners. Each party can generate any of the other's derived public keys, but only their own private keys.

Software should facilitate backup of the shared accounts and associated cosigner extended public keys whenever there is a new shared account created. Such backup serialization is described in the "Shared account export" chapter. Software should warn a user if a backup has not been made.

Software needs to restore based on the serialization of all shared accounts and cosigners when importing the seed from an external source. Such an algorithm is described in the "Shared account import" chapter.

Change

Constant 0 is used for external chain and constant 1 for internal chain (also known as change addresses). External chain is used for addresses that are meant to be visible outside of the wallet (e.g. for receiving payments). Internal chain is used for addresses which are not meant to be visible outside of the wallet and is used for return transaction change.

For example, if a cosigner wants to generate a change address, they would use m / x' / coin_type' / shared_account' / 1 / *, and m / x' / coin_type' / shared_account' / 0 / * for a receive address.

Non-hardened derivation is used at this level.

Address index

Addresses are numbered from index 0 in sequentially increasing manner. This number is used as child index in BIP32 derivation.

Non-hardened derivation is used at this level.

When generating an address, each party can independently generate the n needed public keys. They do this by deriving the public key for each cosigner tree, but using the same path. They can then generate the multisig script (by lexicographically sorting the public keys) and the corresponding p2wsh address.

Transaction creation and signing

When creating a transaction, first one of the parties creates a transaction proposal. This is a transaction that spends some output stored in any of the p2wsh multisig addresses. This proposal is sent to the other parties, who decide if they want to sign. If they approve the proposal, they can generate their needed private key for that specific address (using the same path that generated the public key in that address, but deriving the private key instead), and sign it. Once the proposal reaches m signatures, any cosigner can broadcast it to the network, becoming final.

Shared account import

When the master seed is imported from an external source the software should also include the account export data described in the "Shared account export" chapter, and then discover the addresses in the following manner:

For each shared account:

1. store the shared account index mapped to the cosigner extended public keys and the m-of-n
2. derive the external chain node of this account (m / x' / coin_type' / account' / 0) for all cosigners
3. scan addresses of the chain; respect the gap limit described below

Please note that the algorithm works with the transaction history, not account balances, so you can have an account with 0 total coins and the algorithm will still continue with discovery.

Shared account export

The initial exchange of account extended public keys between cosigners should be backed up with each cosigner's master seed for later discovery of each account. Each shared account is adding external entropy to the master seed, and essential to discovery and spending of coins.

The export is serialized as follows:

• 4 bytes: version bytes
• 4 bytes: number of accounts

For each shared account:

• 4 bytes: shared account index
• 2 bytes: m of m-of-n
• 2 bytes: n of m-of-n

For each shared account extended public key (See "Serialization format" in BIP32):

• 1 byte: depth
• 4 bytes: the fingerprint of the parent's key
• 4 bytes: child number
• 32 bytes: the chain code
• 33 bytes: the public key

The version bytes are not included with the extended public keys as they would all be the same.

Address gap limit

Address gap limit is currently set to 20. If the software hits 20 unused addresses (no transactions associated with that address) in a row, it expects there are no used addresses beyond this point and stops searching the address chain. We scan just the external chains, because internal chains receive only coins that come from the associated external chains.

Wallet software should warn when user is trying to exceed the gap limit on an external chain by generating a new address.

Examples

Compatible wallets

Test vectors

Reference

• BIP32 - Hierarchical Deterministic Wallets
• BIP43 - Purpose Field for Deterministic Wallets
• BIP44 - Multi-Account Hierarchy for Deterministic Wallets
• BIP45 - Structure for Deterministic P2SH Multisignature Wallets
• BIP143 - Transaction Signature Verification for Version 0 Witness Program

Copyright

This document is placed in the public domain.

The initial exchange of account extended public keys between cosigners should be backed up with each cosigner's master seed for later discovery of each account

Does this mean M? When I hear master seed, I think of m (master private key directly derived from the mnemonic)

Yeah, the master node that the purpose node is derived. Technically it could be the coin_type node (m / x' / coin_type), as the higher levels wouldn't be necessary in the export. I was also thinking about including the extended private key in the export, so that it would be: <version><extended-privkey><number-of-accounts><account-index><m-of-n><extended-pubkey><extended-pubkey><account-index><m-of-n><extended-pubkey><extended-pubkey>.

The version bytes are not included with the extended public keys as they would all be the same.

For completeness, I would like to see the version bytes included in the extended public key serialization. In the case of most protocols, the coin_type index indicates the intended network, i.e main, testnet, etc. I tend to use the version byte as a validation artifact. If it does not match the coin_type this could be due to an error and may cause future confusion.

Address generation should not require communication between parties after the initial shared account setup.

As currently specified, this BIP allows for mistaken address reuse unless the parties agree on the latest used address index. While the BIP45 cosigner index logic was a bit complex for implementation purposes, it did carry the property of defense against such address reuse within the specification.

Perhaps we should make note of this, and suggest implementation strategies to assuage this problem, e.g. using a centralized wallet server for address generation and providing individual client software, per signer, for key management, hardware wallet support, etc.

For completeness, I would like to see the version bytes included in the extended public key serialization. In the case of most protocols, the coin_type index indicates the intended network, i.e main, testnet, etc. I tend to use the version byte as a validation artifact. If it does not match the coin_type this could be due to an error and may cause future confusion.

Yeah, I was imagining that the first 4 bytes would be those version bytes, or a version that is coupled with the extended public key version bytes. So when deserializing, the pubkeys would be expanded with the correspending version bytes.

As currently specified, this BIP allows for mistaken address reuse unless the parties agree on the latest used address index. While the BIP45 cosigner index logic was a bit complex for implementation purposes, it did carry the property of defense against such address reuse within the specification.

Indeed the BIP45 cosigner index does mitigate accidental address reuse, as accepting new funds to an address would not have a race condition with other wallets. However it does increase the address scanning to the total number of cosigners, which likely has performance concerns.

The issue with address reuse in that case would happen rarely. As the address index can be discovered via the chain, mempool and the communication for managing transaction proposals. Two wallets would need to be asking for payment at the same time within several seconds for it to be an issue, which could be further mitigated by a quick acknowledgement to the other wallets, if unreachable, the wallets are likely not be requesting payments. Even absent such mitigation, multiple payments to the same address needs to be handled.

We can make a note of that in the paper.

I have also considered adding a case for a 1-of-1 account to be handled as a P2PKH address instead of P2WSH, so that there could be 1-of-1 accounts with 2-of-3 accounts of the same wallet. However, this can be better handled with the same master node (seed) via BIP44, and new accounts can be created without breaking the determinism of wallet recovery.

For completeness, I would like to see the version bytes included in the extended public key serialization. In the case of most protocols, the coin_type index indicates the intended network, i.e main, testnet, etc. I tend to use the version byte as a validation artifact. If it does not match the coin_type this could be due to an error and may cause future confusion.

Yeah, I was imagining that the first 4 bytes would be those version bytes, or a version that is coupled with the extended public key version bytes. So when deserializing, the pubkeys would be expanded with the correspending version bytes.

Ah, I see.