RECENT CHANGES: * (16 Apr 2013) Added private derivation for i >= 0x80000000 (less risk of parent private key leakage) * (30 Apr 2013) Switched from multiplication by I_L to addition of I_L (faster, easier implementation) * (25 May 2013) Added test vectors
BIP: 32 Title: Hierarchical Deterministic Wallets Author: Pieter Wuille Status: Accepted Type: Informational Created: 11-02-2012==Abstract== This document describes hierarchical determinstic wallets (or "HD Wallets"): wallets which can be shared partially or entirely with different systems, each with or without the ability to spend coins. The specification is intended to set a standard for deterministic wallets that can be interchanged between different clients. Although the wallets described here have many features, not all are required by supporting clients. The specification consists of two parts. In a first part, a system for deriving a tree of keypairs from a single seed is presented. The second part demonstrates how to build a wallet structure on top of such a tree. ==Motivation== The Bitcoin reference client uses randomly generated keys. In order to avoid the necessity for a backup after every transaction, (by default) 100 keys are cached in a pool of reserve keys. Still, these wallets are not intended to be shared and used on several systems simultaneously. They support hiding their private keys by using the wallet encrypt feature and not sharing the password, but such "neutered" wallets lose the power to generate public keys as well. Deterministic wallets do not require such frequent backups, and elliptic curve mathematics permit schemes where one can calculate the public keys without revealing the private keys. This permits for example a webshop business to let its webserver generate fresh addresses (public key hashes) for each order or for each customer, without giving the webserver access to the corresponding private keys (which are required for spending the received funds). However, deterministic wallets typically consist of a single "chain" of keypairs. The fact that there is only one chain means that sharing a wallet happens on an all-or-nothing basis. However, in some cases one only wants some (public) keys to be shared and recoverable. In the example of a webshop, the webserver does not need access to all public keys of the merchant's wallet; only to those addresses which are used to receive customer's payments, and not for example the change addresses that are generated when the merchant spends money. Hierarchical deterministic wallets allow such selective sharing by supporting multiple keypair chains, derived from a single root. ==Specification: Key derivation== ===Conventions=== In the rest of this text we will assume the public key cryptography used in Bitcoin, namely elliptic curve cryptography using the field and curve parameters defined by secp256k1 (http://www.secg.org/index.php?action=secg,docs_secg). Variables below are either: * integers modulo the order of the curve (referred to as n), serialized as 32 bytes, most significant byte first. * coordinates of points on the curve, serialized as specified in SEC1 in compressed form: [0x02 or 0x03] + 32 byte x coordinate), where the header byte depends on the parity of the omitted y coordinate. * byte sequences We shall denote the compressed form of point P by χ(P), which for secp256k1 will always be 33 bytes long. Addition (+) of two coordinates is defined as application of the EC group operation. Multiplication (*) of an integer and a coordinate is defined as repeated application of the EC group operation. The generator element of the curve is called G. The public key K corresponding to the private key k is calculated as k*G. We do not distinguish between numbers or coordinates and their serialization as byte sequences. ===Extended keys=== In what follows, we will define a function that derives a number of child keys from a parent key. In order to prevent these from depending solely on the key itself, we extend both private and public keys first with an extra 256 bits of entropy. This extension, called the chain code, is identical for corresponding private and public keys, and consists of 32 bytes. We represent an extended private key as (k, c), with k the normal private key, and c the chain code. An extended public key is represented as (K, c), with K = k*G and c the chain code. ===Child key derivation functions=== We allow for two different types of derivation: private and public. * Private derivation: knowledge of the private key kpar and cpar is required to compute both ki and Ki. * Public derivation: knowledge of the public key Kpar and cpar suffices to compute Ki (but not ki). We define the private and public child key derivation functions: * CKD((kpar, cpar), i) → (ki, ci), defined for both private and public derivation. * CKD'((Kpar, cpar), i) → (Ki, ci), defined only for public derivation. We use the most significant bit of i to specify which type of derivation to use. i is encoded as a 32 bit unsigned integer, most significant byte first; '||' represents concatenation. ====Private child key derivation==== To define CKD((kpar, cpar), i) → (ki, ci): * Check whether the highest bit (0x80000000) of i is set: ** If 1, private derivation is used: let I = HMAC-SHA512(Key = cpar, Data = 0x00 || kpar || i) [Note: The 0x00 pads the private key to make it 33 bytes long.] ** If 0, public derivation is used: let I = HMAC-SHA512(Key = cpar, Data = χ(kpar*G) || i) * Split I = IL || IR into two 32-byte sequences, IL and IR. * ki = IL + kpar (mod n). * ci = IR. In case IL ≥ n or ki = 0, the resulting key is invalid, and one should proceed with the next value for i. [Note: this has probability lower than 1 in 2127.] ====Public child key derivation==== To define CKD'((Kpar, cpar), i) → (Ki, ci): * Check whether the highest bit (0x80000000) of i is set: ** If 1, return error ** If 0, let I = HMAC-SHA512(Key = cpar, Data = χ(Kpar) || i) * Split I = IL || IR into two 32-byte sequences, IL and IR. * Ki = (IL + kpar)*G = IL*G + Kpar * ci = IR. In case IL ≥ n or Ki is the point at infinity, the resulting key is invalid, and one should proceed with the next value for i. Note that the extended public key corresponding to the evaluation of CKD(kext, i) with public derivation (so with i < 0x80000000) is identical to the evaluation of CKD'(Kext, i), with Kext the extended public key corresponding to kext. Symbolically, CKD((k, c), i)*G = CKD'((k*G, c), i). This implies that CKD' can be used to derive all public keys corresponding to the private keys that CKD would find. It cannot be used to retrieve the private keys, however. The HMAC-SHA512 function is specified in [http://tools.ietf.org/html/rfc4231 RFC 4231]. ===The key tree=== The next step is cascading several CKD constructions to build a tree. We start with one root, the master extended key m. By evaluating CKD(m,i) for several values of i, we get a number of first-degree derivative nodes. As each of these is again an extended key, CKD can be applied to those as well. To shorten notation, we will write CKD(CKD(CKD(m,0x8000003),0x2),0x5) as m/3'/2/5 now. Each leaf node in the tree corresponds to an actual keypair, while the internal nodes correspond to the collection of keypairs that descends from them. The chain codes of the leaf nodes are ignored, and only their embedded private or public key is used. Because of this construction, knowing an extended private key allows reconstruction of all descendant private keys and public keys, and knowing an extended public keys allows reconstruction of all descendant public keys derived using public derivation. ===Key identifiers=== Extended keys can be identified by the Hash160 (RIPEMD160 after SHA256) of the serialized public key, ignoring the chain code. This corresponds exactly to the data used in traditional Bitcoin addresses. It is not advised to represent this data in base58 format though, as it may be interpreted as an address that way (and wallet software is not required to accept payment to the chain key itself). The first 32 bits of the identifier are called the fingerprint. ===Serialization format=== Extended public and private keys are serialized as follows: * 4 byte: version bytes (mainnet: 0x0488B21E public, 0x0488ADE4 private; testnet: 0x043587CF public, 0x04358394 private) * 1 byte: depth: 0x00 for master nodes, 0x01 for level-1 descendants, .... * 4 bytes: the fingerprint of the parent's key (0x00000000 if master key) * 4 bytes: child number. This is the number i in xi = xpar/i, with xi the key being serialized. This is encoded in MSB order. (0x00000000 if master key) * 32 bytes: the chain code * 33 bytes: the public key or private key data (0x02 + X or 0x03 + X for public keys, 0x00 + k for private keys) This 78 byte structure can be encoded like other Bitcoin data in Base58, by first adding 32 checksum bits (derived from the double SHA-256 checksum), and then converting to the Base58 representation. This results in a Base58-encoded string of up to 112 characters. Because of the choice of the version bytes, the Base58 representation will start with "xprv" or "xpub" on mainnet, "tprv" or "tpub" on testnet. Note that the fingerprint of the parent only serves as a fast way to detect parent and child nodes in software, and software must be willing to deal with collisions. Internally, the full 160-bit identifier could be used. When importing a serialized extended public key, implementations must verify whether the X coordinate in the public key data corresponds to a point on the curve. If not, the extended public key is invalid. ===Master key generation=== The total number of possible extended keypairs is almost 2^512, but the produced keys are only 256 bits long, and offer about half of that in terms of security. Therefore, master keys are not generated directly, but instead from a potentially short seed value. * Generate a seed S of a chosen length (at least 128 bits, but 256 is advised) from a (P)RNG. * Calculate I = HMAC-SHA512(key="Bitcoin seed", msg=S) * Split I into two 32-byte sequences, IL and IR. * Use IL as master secret key, and IR as master chain code. In case IL is 0 or >=n, the master key is invalid.