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