BIP-0032 HD Wallet

1. 引言

HD Wallet：Hierarchical deterministic wallet，可用于：与多个不同的系统部分或完全分享，可为每个系统分别分配具有 可spend 或 不可spend 的能力。 HD Wallet中通常包含的是a single “chain” of keypairs。

1.1 相关定义

Bitcoin中采用secp256k1 curve，其field和curve参数遵循 SEC 2: Recommended Elliptic Curve Domain Parameters 中的推荐值。

变量通常具有如下形式之一：

• module n n n的整数（ n n n为curve的order）
• 曲线上的point坐标
• byte sequences

2个coordinate pair 的加法定义为EC group operation。 ∣ ∣ || ∣∣表示byte sequence的拼接。

标准转换函数有：

• p o i n t ( p ) point(p) point(p)：返回的为 p ∗ G p*G p∗G的结果，其中 G G G为曲线的base point， p p p为整数。
• s e r 32 ( i ) ser_{32}(i) ser32​(i)：对32位unsigned整数 i i i 序列化为 4-byte sequence，最高有效byte排在最前面。
• s e r 256 ( p ) ser_{256}(p) ser256​(p)：将整数 p p p序列化为32-byte sequence，最高有效byte排在最前面。
• s e r p ( P ) ser_{p}(P) serp​(P)：将point P = ( x , y ) P=(x,y) P=(x,y) 按 SEC 1: Elliptic Curve Cryptography的压缩格式 序列化为byte sequence： ( 0 x 02  or  0 x 03 ) ∣ ∣ s e r 256 ( x ) (0x02\ \text{or}\ 0x03) || ser_{256}(x) (0x02 or 0x03)∣∣ser256​(x)，即第一个byte为 0 x 02 0x02 0x02还是 0 x 03 0x03 0x03具体取决于 y y y坐标的正负极。
• p a r s e 256 ( p ) parse_{256}(p) parse256​(p)：将32-byte sequence解析为256-bit number，最高有效byte排在最前面。

当根据一个parent key 派生出 多个child keys，为了防止单纯依赖于parent key本身，可为public key和private key额外引入256 bit的entropy，额外引入的256 bit称为chain code，与公私钥一样，也为32 byte。

extended private key表示为：

• ( k , c ) (k,c) (k,c)：其中 k k k为正常的私钥， c c c为chain code。

extended public key表示为：

• ( K , c ) (K,c) (K,c)：其中 K = p o i n t ( k ) K=point(k) K=point(k)为正常的公钥， c c c为chain code。

每个extended key有：

• 2 31 2^{31} 231个normal child keys。其序号为 0 0 0 到 2 31 − 1 2^{31}-1 231−1。通常用 i i i来表示normal child key的序号。
• 2 31 2^{31} 231个hardened child keys。其序号为 2 31 2^{31} 231 到 2 32 − 1 2^{32}-1 232−1。为了简化，通常用 i H i_H iH​数字来表示hardened child key的序号， i H = i + 2 31 i_H=i+2^{31} iH​=i+231。

2. Child key derivation (CDK)函数

已知：

• a parent extended key
• 和 an index i i i。 i ≥ 2 31 i\geq 2^{31} i≥231表示child为hardended key。

可计算出相应的child extended key。

具体的child key派生（CDK）函数有：

• Private parent key → private child key：根据父私钥，派生子私钥。
• Public parent key → public child key：根据父公钥，派生子公钥。
• Private parent key → public child key：根据父私钥，派生子公钥。
• Public parent key → private child key：无法根据父公钥派生子私钥。

HMAC相关知识可参看：密码学中的MAC(message authentication code)

2.1 Private parent key → private child key

C K D p r i v ( ( k p a r , c p a r ) , i ) → ( k i , c i ) CKD_{priv}((k_{par},c_{par}),i)\rightarrow (k_i,c_i) CKDpriv​((kpar​,cpar​),i)→(ki​,ci​)，可根据parent extend private key计算出child extend private key：

• 1）判断 i ≥ 2 31 i\geq 2^{31} i≥231（即child是否为hardened key）：
  • 若是hardened child key，则：令 I = HMAC-SHA512 ( Key = c p a r , Data = 0 x 00 ∣ ∣ s e r 256 ( k p a r ) ∣ ∣ s e r 32 ( i ) ) I=\text{HMAC-SHA512}(\text{Key} = c_{par}, \text{Data} = 0x00 || ser_{256}(k_{par}) || ser_{32}(i)) I=HMAC-SHA512(Key=cpar​,Data=0x00∣∣ser256​(kpar​)∣∣ser32​(i))。注意，此处为父私钥pad了 0 x 00 0x00 0x00，使其长度为33 bytes。
  • 若是normal child key，则：令 I = HMAC-SHA512 ( Key = c p a r , Data = s e r p ( p o i n t ( k p a r ) ) ∣ ∣ s e r 32 ( i ) ) I=\text{HMAC-SHA512}(\text{Key} = c_{par}, \text{Data} = ser_{p}(point(k_{par})) || ser_{32}(i)) I=HMAC-SHA512(Key=cpar​,Data=serp​(point(kpar​))∣∣ser32​(i))。
• 2）将 I I I切分为2个32 byte sequence I L , I R I_L,I_R IL​,IR​。
• 3）返回child key k i = p a r s e 256 ( I L ) + k p a r ( m o d    n ) k_i=parse_{256}(I_L)+k_{par}(\mod n) ki​=parse256​(IL​)+kpar​(modn)。
• 4）返回chain code c i = I R c_i=I_R ci​=IR​。
• 5）若 p a r s e 256 ( I L ) ≥ n parse_{256}(I_L)\geq n parse256​(IL​)≥n 或 k i = 0 k_i=0 ki​=0，则生成的child key无效，需使用 i = i + 1 i=i+1 i=i+1再进行如上过程派生。（注意，这种情况发生的概率低于 1 / 2 127 1/2^{127} 1/2127。）

2.2 Public parent key → public child key

C K D p u b ( ( K p a r , c p a r ) , i ) → ( K i , c i ) CKD_{pub}((K_{par},c_{par}),i)\rightarrow (K_i,c_i) CKDpub​((Kpar​,cpar​),i)→(Ki​,ci​)，可根据parent extend public key计算出child extend public key：

• 1）判断 i ≥ 2 31 i\geq 2^{31} i≥231（即child是否为hardened key）：
  • 若是hardened child key，则：返回失败。
  • 若是normal child key，则：令 I = HMAC-SHA512 ( Key = c p a r , Data = s e r p ( K p a r ) ∣ ∣ s e r 32 ( i ) ) I=\text{HMAC-SHA512}(\text{Key} = c_{par}, \text{Data} = ser_{p}(K_{par}) || ser_{32}(i)) I=HMAC-SHA512(Key=cpar​,Data=serp​(Kpar​)∣∣ser32​(i))。
• 2）将 I I I切分为2个32 byte sequence I L , I R I_L,I_R IL​,IR​。
• 3）返回child key K i = p o i n t ( p a r s e 256 ( I L ) ) + K p a r K_i=point(parse_{256}(I_L))+K_{par} Ki​=point(parse256​(IL​))+Kpar​。
• 4）返回chain code c i = I R c_i=I_R ci​=IR​。
• 5）若 p a r s e 256 ( I L ) ≥ n parse_{256}(I_L)\geq n parse256​(IL​)≥n 或 K i = O K_i=\mathcal{O} Ki​=O，则生成的child key无效，需使用 i = i + 1 i=i+1 i=i+1再进行如上过程派生。

2.3 Private parent key → public child key

N ( ( k , c ) ) → ( K , c ) N((k,c))\rightarrow (K,c) N((k,c))→(K,c)，可根据 extend private key计算出 extend public key：

• 1）返回key K = p o i n t ( k ) K=point(k) K=point(k)。
• 2）返回chain code c = c c=c c=c。

根据parent extend private key 计算出 child extend public key的方式有：

• N ( C K D p r i v ( ( k p a r , c p a r ) , i ) ) N(CKD_{priv}((k_{par},c_{par}),i)) N(CKDpriv​((kpar​,cpar​),i))：总是管用。
• C K D p u b ( ( N ( k p a r , c p a r ) ) , i ) CKD_{pub}((N(k_{par},c_{par})),i) CKDpub​((N(kpar​,cpar​)),i)：仅适于non-hardened child keys。

即，可在不知道父私钥，仅根据父公钥就派生出相应的non-hardened child public key。

2.4 Public parent key → private child key

无法根据 父公钥 派生出 子私钥。

3. Key tree

接下来，将堆叠使用多个CKD函数来构建key tree。

假设该key tree仅有1个root——the master extended key m m m。通过对多个 i i i值进行evaluate C D K p r i v ( m , i ) CDK_{priv}(m,i) CDKpriv​(m,i) 可获得一组 level-1 derived nodes。每个node又可作为extended key，持续应用 C D K p r i v CDK_{priv} CDKpriv​进行派生。

可将 C K D p r i v ( C K D p r i v ( C K D p r i v ( m , 3 H ) , 2 ) , 5 ) CKD_{priv}(CKD_{priv}(CKD_{priv}(m,3_H),2),5) CKDpriv​(CKDpriv​(CKDpriv​(m,3H​),2),5) 简化表示为 m / 3 H / 2 / 5 m/3_H/2/5 m/3H​/2/5，等价的，对于公钥，会将 C K D p u b ( C K D p u b ( C K D p u b ( M , 3 ) , 2 ) , 5 ) CKD_{pub}(CKD_{pub}(CKD_{pub}(M,3),2),5) CKDpub​(CKDpub​(CKDpub​(M,3),2),5) 简化表示为 M / 3 / 2 / 5 M/3/2/5 M/3/2/5。 从而具有如下属性：

• N ( m / a / b / c ) = N ( m / a / b ) / c = N ( m / a ) / b / c = N ( m ) / a / b / c = M / a / b / c N(m/a/b/c) = N(m/a/b)/c = N(m/a)/b/c = N(m)/a/b/c = M/a/b/c N(m/a/b/c)=N(m/a/b)/c=N(m/a)/b/c=N(m)/a/b/c=M/a/b/c
• N ( m / a H / b / c ) = N ( m / a H / b ) / c = N ( m / a H ) / b / c N(m/a_H/b/c) = N(m/a_H/b)/c = N(m/a_H)/b/c N(m/aH​/b/c)=N(m/aH​/b)/c=N(m/aH​)/b/c，此时，无法将 N ( m / a H ) N(m/a_H) N(m/aH​)表示为 N ( m ) / a H N(m)/a_H N(m)/aH​。

key tree中的每个叶子节点都对应为一个实际的key，其内部节点对应为该key派生的一组子key。叶子节点的chain code可忽略，仅与其embedded private key或public key 相关。因为在以上构建过程中，知道某extended private key，可构建出其所有 子private key 和 子public key，知道某extended public key，可构建出其所有 non-hardened子public key。

3.1 Key identifier

不考虑chain code，可将Extended key表示为 H a s h 160 ( s e r p ( K ) ) Hash160(ser_{p}(K)) Hash160(serp​(K))，其中 K K K 为为公钥， H a s h 160 ( ∗ ) = R I P E M D 160 ( S H A 256 ( ∗ ) ) Hash160(*)=RIPEMD160(SHA256(*)) Hash160(∗)=RIPEMD160(SHA256(∗))。这与传统的比特币地址表达方式类似。不建议将该该数据进行进一步base58转换，因为那样的化将无法与正常的比特币地址区分，且wallet software并不需要通过chain key本身来接收payment。

key identifier的前32bit称为key fingerprint。

3.2 序列化格式

Extended public key和private key可按如下方式进行序列化：【共78 byte】

• 4 byte：为version byte。（mainnet: 0x0488B21E public, 0x0488ADE4 private; testnet: 0x043587CF public, 0x04358394 private）
• 1 byte：为depth。 0 x 00 0x00 0x00表示master node， 0 x 01 0x01 0x01表示level-1 derived keys，以此类推。
• 4 byte：为parent key的fingerprint（对于master key，其值为 0 x 00000000 0x00000000 0x00000000）。仅作为快速定位父子节点的方式，实际软件实现时要注意处理collision情况，实际内部可直接使用完整的160-bit identifier。
• 4 byte：为child number。为 s e r 32 ( i ) ser_{32}(i) ser32​(i) for i i i in x i = x p a r / i x_i=x_{par}/i xi​=xpar​/i，其中 x i x_i xi​为the key being serialized。（对于master key，其值为 0 x 00000000 0x00000000 0x00000000）。
• 32 byte：为chain code。
• 33 byte：为public key或private key data（对于公钥为 s e r p ( K ) ser_{p}(K) serp​(K)，对于私钥为 0 x 00 ∣ ∣ s e r 256 ( k ) 0x00||ser_{256}(k) 0x00∣∣ser256​(k)）。

以上78 byte结构也可采用Base58编码为112字符的string，对于主网，其以"xprv"或“xpub”开头；对于测试网，其前缀为"tprv"或“tpub”。

当extended public key进行序列化时，需判断该公钥是否为曲线上的point，若不是，则该extended public key为invalid的。

3.3 Master key generation

可能的extended keypair总数约为 2 512 2^{512} 2512个，最终产生的key仅为 256 256 256-bit long，从而流程了约一半的安全控件。 master通常不是直接生成的，而是源于一个short seed：

• 由§RNG生成一个指定长度的seed byte sequence S S S，该长度通常为128~512bit，推荐为256bit。
• 计算 I = HMAC-SHA512 ( Key = c p a r , Data = S ) I=\text{HMAC-SHA512}(\text{Key} = c_{par}, \text{Data} =S) I=HMAC-SHA512(Key=cpar​,Data=S)。
• 将 I I I切分为2个32 byte sequence I L , I R I_L,I_R IL​,IR​。
• 将 p a r s e 256 ( I L ) parse_{256}(I_L) parse256​(IL​)作为master secret key，将 I R I_R IR​作为master chain code。

若 I L = 0 I_L=0 IL​=0或 I L ≥ n I_L\geq n IL​≥n，则该master key为invalid的。

参考资料

[1] BIP-0032