/ hdkey.go
hdkey.go
1 package extkeys 2 3 import ( 4 "bytes" 5 "crypto/ecdsa" 6 "encoding/binary" 7 "encoding/hex" 8 "errors" 9 "fmt" 10 "math/big" 11 12 "github.com/btcsuite/btcd/btcec/v2" 13 "github.com/btcsuite/btcd/btcutil" 14 "github.com/btcsuite/btcd/btcutil/base58" 15 "github.com/btcsuite/btcd/chaincfg" 16 "github.com/btcsuite/btcd/chaincfg/chainhash" 17 "github.com/ethereum/go-ethereum/crypto/secp256k1" 18 ) 19 20 // Implementation of the following BIPs: 21 // - BIP32 (https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki) 22 // - BIP39 (https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki) 23 // - BIP44 (https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki) 24 // 25 // Referencing 26 // https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki 27 // https://bitcoin.org/en/developer-guide#hardened-keys 28 29 // Reference Implementations 30 // https://github.com/btcsuite/btcd/tree/master/btcutil/hdkeychain 31 // https://github.com/WeMeetAgain/go-hdwallet 32 33 // https://github.com/ConsenSys/eth-lightwallet/blob/master/lib/keystore.js 34 // https://github.com/bitpay/bitcore-lib/tree/master/lib 35 36 // MUST CREATE HARDENED CHILDREN OF THE MASTER PRIVATE KEY (M) TO PREVENT 37 // A COMPROMISED CHILD KEY FROM COMPROMISING THE MASTER KEY. 38 // AS THERE ARE NO NORMAL CHILDREN FOR THE MASTER KEYS, 39 // THE MASTER PUBLIC KEY IS NOT USED IN HD WALLETS. 40 // ALL OTHER KEYS CAN HAVE NORMAL CHILDREN, 41 // SO THE CORRESPONDING EXTENDED PUBLIC KEYS MAY BE USED INSTEAD. 42 43 // TODO make sure we're doing this ^^^^ !!!!!! 44 45 type KeyPurpose int 46 47 const ( 48 KeyPurposeWallet KeyPurpose = iota + 1 49 KeyPurposeChat 50 ) 51 52 const ( 53 // HardenedKeyStart defines a starting point for hardened key. 54 // Each extended key has 2^31 normal child keys and 2^31 hardened child keys. 55 // Thus the range for normal child keys is [0, 2^31 - 1] and the range for hardened child keys is [2^31, 2^32 - 1]. 56 HardenedKeyStart = 0x80000000 // 2^31 57 58 // MinSeedBytes is the minimum number of bytes allowed for a seed to a master node. 59 MinSeedBytes = 16 // 128 bits 60 61 // MaxSeedBytes is the maximum number of bytes allowed for a seed to a master node. 62 MaxSeedBytes = 64 // 512 bits 63 64 // serializedKeyLen is the length of a serialized public or private 65 // extended key. It consists of 4 bytes version, 1 byte depth, 4 bytes 66 // fingerprint, 4 bytes child number, 32 bytes chain code, and 33 bytes 67 // public/private key data. 68 serializedKeyLen = 4 + 1 + 4 + 4 + 32 + 33 // 78 bytes 69 70 // CoinTypeBTC is BTC coin type 71 CoinTypeBTC = 0 // 0x80000000 72 73 // CoinTypeTestNet is test net coin type 74 CoinTypeTestNet = 1 // 0x80000001 75 76 // CoinTypeETH is ETH coin type 77 CoinTypeETH = 60 // 0x8000003c 78 79 // EmptyExtendedKeyString marker string for zero extended key 80 EmptyExtendedKeyString = "Zeroed extended key" 81 82 // MaxDepth is the maximum depth of an extended key. 83 // Extended keys with depth MaxDepth cannot derive child keys. 84 MaxDepth = 255 85 ) 86 87 // errors 88 var ( 89 ErrInvalidKey = errors.New("key is invalid") 90 ErrInvalidKeyPurpose = errors.New("key purpose is invalid") 91 ErrInvalidSeed = errors.New("seed is invalid") 92 ErrInvalidSeedLen = fmt.Errorf("the recommended size of seed is %d-%d bits", MinSeedBytes, MaxSeedBytes) 93 ErrDerivingHardenedFromPublic = errors.New("cannot derive a hardened key from public key") 94 ErrBadChecksum = errors.New("bad extended key checksum") 95 ErrInvalidKeyLen = errors.New("serialized extended key length is invalid") 96 ErrDerivingChild = errors.New("error deriving child key") 97 ErrInvalidMasterKey = errors.New("invalid master key supplied") 98 ErrMaxDepthExceeded = errors.New("max depth exceeded") 99 ) 100 101 var ( 102 // PrivateKeyVersion is version for private key 103 PrivateKeyVersion, _ = hex.DecodeString("0488ADE4") 104 105 // PublicKeyVersion is version for public key 106 PublicKeyVersion, _ = hex.DecodeString("0488B21E") 107 108 // EthBIP44ParentPath is BIP44 keys parent's derivation path 109 EthBIP44ParentPath = []uint32{ 110 HardenedKeyStart + 44, // purpose 111 HardenedKeyStart + CoinTypeETH, // cointype set to ETH 112 HardenedKeyStart + 0, // account 113 0, // 0 - public, 1 - private 114 } 115 116 // EIP1581KeyTypeChat is used as chat key_type in the derivation of EIP1581 keys 117 EIP1581KeyTypeChat uint32 = 0x00 118 119 // EthEIP1581ChatParentPath is EIP-1581 chat keys parent's derivation path 120 EthEIP1581ChatParentPath = []uint32{ 121 HardenedKeyStart + 43, // purpose 122 HardenedKeyStart + CoinTypeETH, // cointype set to ETH 123 HardenedKeyStart + 1581, // EIP-1581 subpurpose 124 HardenedKeyStart + EIP1581KeyTypeChat, // key_type (chat) 125 } 126 ) 127 128 // ExtendedKey represents BIP44-compliant HD key 129 type ExtendedKey struct { 130 Version []byte // 4 bytes, mainnet: 0x0488B21E public, 0x0488ADE4 private; testnet: 0x043587CF public, 0x04358394 private 131 Depth uint8 // 1 byte, depth: 0x00 for master nodes, 0x01 for level-1 derived keys, .... 132 FingerPrint []byte // 4 bytes, fingerprint of the parent's key (0x00000000 if master key) 133 ChildNumber uint32 // 4 bytes, This is ser32(i) for i in xi = xpar/i, with xi the key being serialized. (0x00000000 if master key) 134 KeyData []byte // 33 bytes, the public key or private key data (serP(K) for public keys, 0x00 || ser256(k) for private keys) 135 ChainCode []byte // 32 bytes, the chain code 136 IsPrivate bool // (non-serialized) if false, this chain will only contain a public key and can only create a public key chain. 137 CachedPubKeyData []byte // (non-serialized) used for memoization of public key (calculated from a private key) 138 } 139 140 // nolint: gas 141 const masterSecret = "Bitcoin seed" 142 143 // NewMaster creates new master node, root of HD chain/tree. 144 // Both master and child nodes are of ExtendedKey type, and all the children derive from the root node. 145 func NewMaster(seed []byte) (*ExtendedKey, error) { 146 // Ensure seed is within expected limits 147 lseed := len(seed) 148 if lseed < MinSeedBytes || lseed > MaxSeedBytes { 149 return nil, ErrInvalidSeedLen 150 } 151 152 secretKey, chainCode, err := splitHMAC(seed, []byte(masterSecret)) 153 if err != nil { 154 return nil, err 155 } 156 157 master := &ExtendedKey{ 158 Version: PrivateKeyVersion, 159 Depth: 0, 160 FingerPrint: []byte{0x00, 0x00, 0x00, 0x00}, 161 ChildNumber: 0, 162 KeyData: secretKey, 163 ChainCode: chainCode, 164 IsPrivate: true, 165 } 166 167 return master, nil 168 } 169 170 // Child derives extended key at a given index i. 171 // If parent is private, then derived key is also private. If parent is public, then derived is public. 172 // 173 // If i >= HardenedKeyStart, then hardened key is generated. 174 // You can only generate hardened keys from private parent keys. 175 // If you try generating hardened key form public parent key, ErrDerivingHardenedFromPublic is returned. 176 // 177 // There are four CKD (child key derivation) scenarios: 178 // 1) Private extended key -> Hardened child private extended key 179 // 2) Private extended key -> Non-hardened child private extended key 180 // 3) Public extended key -> Non-hardened child public extended key 181 // 4) Public extended key -> Hardened child public extended key (INVALID!) 182 func (k *ExtendedKey) Child(i uint32) (*ExtendedKey, error) { 183 if k.Depth == MaxDepth { 184 return nil, ErrMaxDepthExceeded 185 } 186 187 // A hardened child may not be created from a public extended key (Case #4). 188 isChildHardened := i >= HardenedKeyStart 189 if !k.IsPrivate && isChildHardened { 190 return nil, ErrDerivingHardenedFromPublic 191 } 192 193 keyLen := 33 194 seed := make([]byte, keyLen+4) 195 if isChildHardened { 196 // Case #1: 0x00 || ser256(parentKey) || ser32(i) 197 copy(seed[1:], k.KeyData) // 0x00 || ser256(parentKey) 198 } else { 199 // Case #2 and #3: serP(parentPubKey) || ser32(i) 200 copy(seed, k.pubKeyBytes()) 201 } 202 binary.BigEndian.PutUint32(seed[keyLen:], i) 203 204 secretKey, chainCode, err := splitHMAC(seed, k.ChainCode) 205 if err != nil { 206 return nil, err 207 } 208 209 child := &ExtendedKey{ 210 ChainCode: chainCode, 211 Depth: k.Depth + 1, 212 ChildNumber: i, 213 IsPrivate: k.IsPrivate, 214 // The fingerprint for the derived child is the first 4 bytes of parent's 215 FingerPrint: btcutil.Hash160(k.pubKeyBytes())[:4], 216 } 217 218 if k.IsPrivate { 219 // Case #1 or #2: childKey = parse256(IL) + parentKey 220 parentKeyBigInt := new(big.Int).SetBytes(k.KeyData) 221 keyBigInt := new(big.Int).SetBytes(secretKey) 222 keyBigInt.Add(keyBigInt, parentKeyBigInt) 223 keyBigInt.Mod(keyBigInt, secp256k1.S256().N) 224 225 // Make sure that child.KeyData is 32 bytes of data even if the value is represented with less bytes. 226 // When we derive a child of this key, we call splitHMAC that does a sha512 of a seed that is: 227 // - 1 byte with 0x00 228 // - 32 bytes for the key data 229 // - 4 bytes for the child key index 230 // If we don't padd the KeyData, it will be shifted to left in that 32 bytes space 231 // generating a different seed and different child key. 232 // This part fixes a bug we had previously and described at: 233 // https://medium.com/@alexberegszaszi/why-do-my-bip32-wallets-disagree-6f3254cc5846#.86inuifuq 234 keyData := keyBigInt.Bytes() 235 if len(keyData) < 32 { 236 extra := make([]byte, 32-len(keyData)) 237 keyData = append(extra, keyData...) 238 } 239 240 child.KeyData = keyData 241 child.Version = PrivateKeyVersion 242 } else { 243 // Case #3: childKey = serP(point(parse256(IL)) + parentKey) 244 245 // Calculate the corresponding intermediate public key for intermediate private key. 246 // Use btcec for all operations to maintain curve consistency 247 keyx, keyy := secp256k1.S256().ScalarBaseMult(secretKey) 248 if keyx.Sign() == 0 || keyy.Sign() == 0 { 249 return nil, ErrInvalidKey 250 } 251 252 // Convert big.Int coordinates to btcec.FieldVal 253 var keyXField, keyYField btcec.FieldVal 254 keyXField.SetByteSlice(keyx.Bytes()) 255 keyYField.SetByteSlice(keyy.Bytes()) 256 257 // Convert the serialized compressed parent public key into X and Y coordinates 258 // so it can be added to the intermediate public key. 259 // For compressed public keys, the format is: 0x02/0x03 + 32-byte X coordinate 260 // We need to decompress to get Y coordinate 261 if len(k.KeyData) != 33 { 262 return nil, ErrInvalidKey 263 } 264 265 // Extract X coordinate from compressed public key 266 xBytes := k.KeyData[1:33] 267 var xField btcec.FieldVal 268 xField.SetByteSlice(xBytes) 269 270 // Decompress Y coordinate 271 var yField btcec.FieldVal 272 wantOddY := k.KeyData[0] == 0x03 273 if !btcec.DecompressY(&xField, wantOddY, &yField) { 274 return nil, ErrInvalidKey 275 } 276 277 // Convert FieldVal to big.Int for secp256k1 operations 278 xInt := new(big.Int).SetBytes(xField.Bytes()[:]) 279 yInt := new(big.Int).SetBytes(yField.Bytes()[:]) 280 281 // childKey = serP(point(parse256(IL)) + parentKey) 282 // Use secp256k1 for all operations to maintain curve consistency 283 childX, childY := secp256k1.S256().Add(keyx, keyy, xInt, yInt) 284 285 // Serialize the coordinates directly to compressed format without creating btcec.PublicKey 286 // This avoids the curve mismatch issue 287 child.KeyData = secp256k1.CompressPubkey(childX, childY) 288 child.Version = PublicKeyVersion 289 } 290 return child, nil 291 } 292 293 // ChildForPurpose derives the child key at index i using a derivation path based on the purpose. 294 func (k *ExtendedKey) ChildForPurpose(p KeyPurpose, i uint32) (*ExtendedKey, error) { 295 switch p { 296 case KeyPurposeWallet: 297 return k.EthBIP44Child(i) 298 case KeyPurposeChat: 299 return k.EthEIP1581ChatChild(i) 300 default: 301 return nil, ErrInvalidKeyPurpose 302 } 303 } 304 305 // BIP44Child returns Status CKD#i (where i is child index). 306 // BIP44 format is used: m / purpose' / coin_type' / account' / change / address_index 307 // BIP44Child is depracated in favour of EthBIP44Child 308 // Param coinType is deprecated; we override it to always use CoinTypeETH. 309 func (k *ExtendedKey) BIP44Child(coinType, i uint32) (*ExtendedKey, error) { 310 return k.EthBIP44Child(i) 311 } 312 313 // BIP44Child returns Status CKD#i (where i is child index). 314 // BIP44 format is used: m / purpose' / coin_type' / account' / change / address_index 315 func (k *ExtendedKey) EthBIP44Child(i uint32) (*ExtendedKey, error) { 316 if !k.IsPrivate { 317 return nil, ErrInvalidMasterKey 318 } 319 320 if k.Depth != 0 { 321 return nil, ErrInvalidMasterKey 322 } 323 324 // m/44'/60'/0'/0/index 325 extKey, err := k.Derive(append(EthBIP44ParentPath, i)) 326 if err != nil { 327 return nil, err 328 } 329 330 return extKey, nil 331 } 332 333 // EthEIP1581ChatChild returns the whisper key #i (where i is child index). 334 // EthEIP1581ChatChild format is used is the one defined in the EIP-1581: 335 // m / 43' / coin_type' / 1581' / key_type / index 336 func (k *ExtendedKey) EthEIP1581ChatChild(i uint32) (*ExtendedKey, error) { 337 if !k.IsPrivate { 338 return nil, ErrInvalidMasterKey 339 } 340 341 if k.Depth != 0 { 342 return nil, ErrInvalidMasterKey 343 } 344 345 // m/43'/60'/1581'/0/index 346 extKey, err := k.Derive(append(EthEIP1581ChatParentPath, i)) 347 if err != nil { 348 return nil, err 349 } 350 351 return extKey, nil 352 } 353 354 // Derive returns a derived child key at a given path 355 func (k *ExtendedKey) Derive(path []uint32) (*ExtendedKey, error) { 356 var err error 357 extKey := k 358 for _, i := range path { 359 extKey, err = extKey.Child(i) 360 if err != nil { 361 return nil, ErrDerivingChild 362 } 363 } 364 365 return extKey, nil 366 } 367 368 // Neuter returns a new extended public key from a give extended private key. 369 // If the input extended key is already public, it will be returned unaltered. 370 func (k *ExtendedKey) Neuter() (*ExtendedKey, error) { 371 // Already an extended public key. 372 if !k.IsPrivate { 373 return k, nil 374 } 375 376 // Get the associated public extended key version bytes. 377 version, err := chaincfg.HDPrivateKeyToPublicKeyID(k.Version) 378 if err != nil { 379 return nil, err 380 } 381 382 // Convert it to an extended public key. The key for the new extended 383 // key will simply be the pubkey of the current extended private key. 384 return &ExtendedKey{ 385 Version: version, 386 KeyData: k.pubKeyBytes(), 387 ChainCode: k.ChainCode, 388 FingerPrint: k.FingerPrint, 389 Depth: k.Depth, 390 ChildNumber: k.ChildNumber, 391 IsPrivate: false, 392 }, nil 393 } 394 395 // IsZeroed returns true if key is nil or empty 396 func (k *ExtendedKey) IsZeroed() bool { 397 return k == nil || len(k.KeyData) == 0 398 } 399 400 // String returns the extended key as a human-readable base58-encoded string. 401 func (k *ExtendedKey) String() string { 402 if k.IsZeroed() { 403 return EmptyExtendedKeyString 404 } 405 406 var childNumBytes [4]byte 407 binary.BigEndian.PutUint32(childNumBytes[:], k.ChildNumber) 408 409 // The serialized format is: 410 // version (4) || depth (1) || parent fingerprint (4)) || 411 // child num (4) || chain code (32) || key data (33) || checksum (4) 412 serializedBytes := make([]byte, 0, serializedKeyLen+4) 413 serializedBytes = append(serializedBytes, k.Version...) 414 serializedBytes = append(serializedBytes, k.Depth) 415 serializedBytes = append(serializedBytes, k.FingerPrint...) 416 serializedBytes = append(serializedBytes, childNumBytes[:]...) 417 serializedBytes = append(serializedBytes, k.ChainCode...) 418 if k.IsPrivate { 419 serializedBytes = append(serializedBytes, 0x00) 420 serializedBytes = paddedAppend(32, serializedBytes, k.KeyData) 421 } else { 422 serializedBytes = append(serializedBytes, k.pubKeyBytes()...) 423 } 424 425 checkSum := chainhash.DoubleHashB(serializedBytes)[:4] 426 serializedBytes = append(serializedBytes, checkSum...) 427 return base58.Encode(serializedBytes) 428 } 429 430 // pubKeyBytes returns bytes for the serialized compressed public key associated 431 // with this extended key in an efficient manner including memoization as 432 // necessary. 433 // 434 // When the extended key is already a public key, the key is simply returned as 435 // is since it's already in the correct form. However, when the extended key is 436 // a private key, the public key will be calculated and memoized so future 437 // accesses can simply return the cached result. 438 func (k *ExtendedKey) pubKeyBytes() []byte { 439 // Just return the key if it's already an extended public key. 440 if !k.IsPrivate { 441 return k.KeyData 442 } 443 444 pkx, pky := secp256k1.S256().ScalarBaseMult(k.KeyData) 445 // Use secp256k1.CompressPubkey directly to avoid curve mismatch 446 return secp256k1.CompressPubkey(pkx, pky) 447 } 448 449 // ToECDSA returns the key data as ecdsa.PrivateKey 450 func (k *ExtendedKey) ToECDSA() *ecdsa.PrivateKey { 451 // Use standard crypto/ecdsa to avoid curve mismatch 452 privKey := new(ecdsa.PrivateKey) 453 privKey.PublicKey.Curve = secp256k1.S256() 454 privKey.D = new(big.Int).SetBytes(k.KeyData) 455 privKey.PublicKey.X, privKey.PublicKey.Y = secp256k1.S256().ScalarBaseMult(k.KeyData) 456 return privKey 457 } 458 459 // NewKeyFromString returns a new extended key instance from a base58-encoded 460 // extended key. 461 func NewKeyFromString(key string) (*ExtendedKey, error) { 462 if key == EmptyExtendedKeyString || len(key) == 0 { 463 return &ExtendedKey{}, nil 464 } 465 466 // The base58-decoded extended key must consist of a serialized payload 467 // plus an additional 4 bytes for the checksum. 468 decoded := base58.Decode(key) 469 if len(decoded) != serializedKeyLen+4 { 470 return nil, ErrInvalidKeyLen 471 } 472 473 // The serialized format is: 474 // version (4) || depth (1) || parent fingerprint (4)) || 475 // child num (4) || chain code (32) || key data (33) || checksum (4) 476 477 // Split the payload and checksum up and ensure the checksum matches. 478 payload := decoded[:len(decoded)-4] 479 checkSum := decoded[len(decoded)-4:] 480 expectedCheckSum := chainhash.DoubleHashB(payload)[:4] 481 if !bytes.Equal(checkSum, expectedCheckSum) { 482 return nil, ErrBadChecksum 483 } 484 485 // Deserialize each of the payload fields. 486 version := payload[:4] 487 depth := payload[4:5][0] 488 fingerPrint := payload[5:9] 489 childNumber := binary.BigEndian.Uint32(payload[9:13]) 490 chainCode := payload[13:45] 491 keyData := payload[45:78] 492 493 // The key data is a private key if it starts with 0x00. Serialized 494 // compressed pubkeys either start with 0x02 or 0x03. 495 isPrivate := keyData[0] == 0x00 496 if isPrivate { 497 // Ensure the private key is valid. It must be within the range 498 // of the order of the secp256k1 curve and not be 0. 499 keyData = keyData[1:] 500 keyNum := new(big.Int).SetBytes(keyData) 501 if keyNum.Cmp(secp256k1.S256().N) >= 0 || keyNum.Sign() == 0 { 502 return nil, ErrInvalidSeed 503 } 504 } else { 505 // Ensure the public key parses correctly and is actually on the 506 // secp256k1 curve. 507 // Use secp256k1.DecompressPubkey to validate the public key 508 x, y := secp256k1.DecompressPubkey(keyData) 509 if x == nil || y == nil { 510 return nil, ErrInvalidKey 511 } 512 } 513 514 return &ExtendedKey{ 515 Version: version, 516 KeyData: keyData, 517 ChainCode: chainCode, 518 FingerPrint: fingerPrint, 519 Depth: depth, 520 ChildNumber: childNumber, 521 IsPrivate: isPrivate, 522 }, nil 523 }