1 package hdkeychain
2 3 // References:
4 // [BIP32]: BIP0032 - Hierarchical Deterministic Wallets https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
5 import (
6 "bytes"
7 "crypto/hmac"
8 "crypto/rand"
9 "crypto/sha512"
10 "encoding/binary"
11 "errors"
12 "fmt"
13 "github.com/p9c/p9/pkg/btcaddr"
14 "math/big"
15 16 "github.com/p9c/p9/pkg/base58"
17 "github.com/p9c/p9/pkg/chaincfg"
18 "github.com/p9c/p9/pkg/chainhash"
19 ec "github.com/p9c/p9/pkg/ecc"
20 )
21 22 const (
23 // RecommendedSeedLen is the recommended length in bytes for a seed to a master node.
24 RecommendedSeedLen = 32 // 256 bits
25 // HardenedKeyStart is the index at which a hardened key starts. Each extended key has 2^31 normal child keys and
26 // 2^31 hardned child keys. Thus the range for normal child keys is [0, 2^31 - 1] and the range for hardened child
27 // keys is [2^31, 2^32 - 1].
28 HardenedKeyStart = 0x80000000 // 2^31
29 // MinSeedBytes is the minimum number of bytes allowed for a seed to a master node.
30 MinSeedBytes = 16 // 128 bits
31 // MaxSeedBytes is the maximum number of bytes allowed for a seed to a master node.
32 MaxSeedBytes = 64 // 512 bits
33 // serializedKeyLen is the length of a serialized public or private extended key. It consists of 4 bytes version, 1
34 // byte depth, 4 bytes fingerprint, 4 bytes child number, 32 bytes chain code, and 33 bytes public/private key data.
35 serializedKeyLen = 4 + 1 + 4 + 4 + 32 + 33 // 78 bytes
36 // maxUint8 is the max positive integer which can be serialized in a uint8
37 maxUint8 = 1<<8 - 1
38 )
39 40 var (
41 // ErrDeriveHardFromPublic describes an error in which the caller attempted to derive a hardened extended key from a
42 // public key.
43 ErrDeriveHardFromPublic = errors.New(
44 "cannot derive a hardened key " +
45 "from a public key",
46 )
47 // ErrDeriveBeyondMaxDepth describes an error in which the caller has attempted to derive more than 255 keys from a
48 // root key.
49 ErrDeriveBeyondMaxDepth = errors.New(
50 "cannot derive a key with more than " +
51 "255 indices in its path",
52 )
53 // ErrNotPrivExtKey describes an error in which the caller attempted to extract a private key from a public extended
54 // key.
55 ErrNotPrivExtKey = errors.New(
56 "unable to create private keys from a " +
57 "public extended key",
58 )
59 // ErrInvalidChild describes an error in which the child at a specific index is invalid due to the derived key
60 // falling outside of the valid range for secp256k1 private keys. This error indicates the caller should simply
61 // ignore the invalid child extended key at this index and increment to the next index.
62 ErrInvalidChild = errors.New("the extended key at this index is invalid")
63 // ErrUnusableSeed describes an error in which the provided seed is not usable due to the derived key falling
64 // outside of the valid range for secp256k1 private keys. This error indicates the caller must choose another seed.
65 ErrUnusableSeed = errors.New("unusable seed")
66 // ErrInvalidSeedLen describes an error in which the provided seed or seed length is not in the allowed range.
67 ErrInvalidSeedLen = fmt.Errorf(
68 "seed length must be between %d and %d "+
69 "bits", MinSeedBytes*8, MaxSeedBytes*8,
70 )
71 // ErrBadChecksum describes an error in which the checksum encoded with a serialized extended key does not match the
72 // calculated value.
73 ErrBadChecksum = errors.New("bad extended key checksum")
74 // ErrInvalidKeyLen describes an error in which the provided serialized key is not the expected length.
75 ErrInvalidKeyLen = errors.New(
76 "the provided serialized extended key " +
77 "length is invalid",
78 )
79 // masterKey is the master key used along with a random seed used to generate the master node in the hierarchical
80 // tree.
81 masterKey = []byte("Parallelcoin seed")
82 )
83 84 // ExtendedKey houses all the information needed to support a hierarchical deterministic extended key. See the package
85 // overview documentation for more details on how to use extended keys.
86 type ExtendedKey struct {
87 key []byte // This will be the pubkey for extended pub keys
88 pubKey []byte // This will only be set for extended priv keys
89 chainCode []byte
90 depth uint8
91 parentFP []byte
92 childNum uint32
93 version []byte
94 isPrivate bool
95 }
96 97 // NewExtendedKey returns a new instance of an extended key with the given fields. No error checking is performed here
98 // as it's only intended to be a convenience method used to create a populated struct.
99 //
100 // This function should only by used by applications that need to create custom ExtendedKeys. All other applications
101 // should just use NewMaster, Child, or Neuter.
102 func NewExtendedKey(
103 version, key, chainCode, parentFP []byte, depth uint8,
104 childNum uint32, isPrivate bool,
105 ) *ExtendedKey {
106 // NOTE: The pubKey field is intentionally left nil so it is only computed and memoized as required.
107 return &ExtendedKey{
108 key: key,
109 chainCode: chainCode,
110 depth: depth,
111 parentFP: parentFP,
112 childNum: childNum,
113 version: version,
114 isPrivate: isPrivate,
115 }
116 }
117 118 // pubKeyBytes returns bytes for the serialized compressed public key associated with this extended key in an efficient
119 // manner including memoization as necessary.
120 //
121 // When the extended key is already a public key, the key is simply returned as is since it's already in the correct
122 // form. However, when the extended key is a private key, the public key will be calculated and memoized so future
123 // accesses can simply return the cached result.
124 func (k *ExtendedKey) pubKeyBytes() []byte {
125 // Just return the key if it's already an extended public key.
126 if !k.isPrivate {
127 return k.key
128 }
129 // This is a private extended key, so calculate and memoize the public key if needed.
130 if len(k.pubKey) == 0 {
131 pkx, pky := ec.S256().ScalarBaseMult(k.key)
132 pubKey := ec.PublicKey{Curve: ec.S256(), X: pkx, Y: pky}
133 k.pubKey = pubKey.SerializeCompressed()
134 }
135 return k.pubKey
136 }
137 138 // IsPrivate returns whether or not the extended key is a private extended key. A private extended key can be used to
139 // derive both hardened and non-hardened child private and public extended keys. A public extended key can only be used
140 // to derive non-hardened child public extended keys.
141 func (k *ExtendedKey) IsPrivate() bool {
142 return k.isPrivate
143 }
144 145 // Depth returns the current derivation level with respect to the root. The root key has depth zero, and the field has a
146 // maximum of 255 due to how depth is serialized.
147 func (k *ExtendedKey) Depth() uint8 {
148 return k.depth
149 }
150 151 // ParentFingerprint returns a fingerprint of the parent extended key from which this one was derived.
152 func (k *ExtendedKey) ParentFingerprint() uint32 {
153 return binary.BigEndian.Uint32(k.parentFP)
154 }
155 156 // Child returns a derived child extended key at the given index. When this extended key is a private extended key (as
157 // determined by the IsPrivate function), a private extended key will be derived. Otherwise, the derived extended key
158 // will be also be a public extended key.
159 //
160 // When the index is greater to or equal than the HardenedKeyStart constant, the derived extended key will be a hardened
161 // extended key. It is only possible to derive a hardended extended key from a private extended key. Consequently, this
162 // function will return ErrDeriveHardFromPublic if a hardened child extended key is requested from a public extended
163 // key.
164 //
165 // A hardened extended key is useful since, as previously mentioned, it requires a parent private extended key to
166 // derive. In other words, normal child extended public keys can be derived from a parent public extended key (no
167 // knowledge of the parent private key) whereas hardened extended keys may not be. NOTE: There is an extremely small
168 // chance (< 1 in 2^127) the specific child index does not derive to a usable child. The ErrInvalidChild error will be
169 // returned if this should occur, and the caller is expected to ignore the invalid child and simply increment to the
170 // next index.
171 func (k *ExtendedKey) Child(i uint32) (*ExtendedKey, error) {
172 // Prevent derivation of children beyond the max allowed depth.
173 if k.depth == maxUint8 {
174 return nil, ErrDeriveBeyondMaxDepth
175 }
176 // There are four scenarios that could happen here:
177 //
178 // 1) Private extended key -> Hardened child private extended key
179 //
180 // 2) Private extended key -> Non-hardened child private extended key
181 //
182 // 3) Public extended key -> Non-hardened child public extended key
183 //
184 // 4) Public extended key -> Hardened child public extended key (INVALID!)
185 //
186 // Case #4 is invalid, so error out early.
187 //
188 // A hardened child extended key may not be created from a public extended key.
189 isChildHardened := i >= HardenedKeyStart
190 if !k.isPrivate && isChildHardened {
191 return nil, ErrDeriveHardFromPublic
192 }
193 // The data used to derive the child key depends on whether or not the child is hardened per [BIP32].
194 //
195 // For hardened children:
196 //
197 // 0x00 || ser256(parentKey) || ser32(i)
198 //
199 // For normal children:
200 //
201 // serP(parentPubKey) || ser32(i)
202 keyLen := 33
203 data := make([]byte, keyLen+4)
204 if isChildHardened {
205 // Case #1.
206 //
207 // When the child is a hardened child, the key is known to be a private key due to the above early return. Pad it with a leading zero as required by [BIP32] for deriving the child.(data[1:], k.key)
208 } else {
209 // Case #2 or #3.
210 //
211 // This is either a public or private extended key, but in either case, the data which is used to derive the child key starts with the secp256k1 compressed public key bytes.
212 copy(data, k.pubKeyBytes())
213 }
214 binary.BigEndian.PutUint32(data[keyLen:], i)
215 // Take the HMAC-SHA512 of the current key's chain code and the derived data:
216 //
217 // I = HMAC-SHA512(Key = chainCode, Data = data)
218 hmac512 := hmac.New(sha512.New, k.chainCode)
219 _, e := hmac512.Write(data)
220 if e != nil {
221 E.Ln(e)
222 }
223 ilr := hmac512.Sum(nil)
224 // Split "I" into two 32-byte sequences Il and Ir where:
225 //
226 // Il = intermediate key used to derive the child
227 //
228 // Ir = child chain code
229 il := ilr[:len(ilr)/2]
230 childChainCode := ilr[len(ilr)/2:]
231 // Both derived public or private keys rely on treating the left 32-byte sequence calculated above (Il) as a 256-bit
232 // integer that must be within the valid range for a secp256k1 private key. There is a small chance (< 1 in 2^127)
233 // this condition will not hold, and in that case, a child extended key can't be created for this index and the
234 // caller should simply increment to the next index.
235 ilNum := new(big.Int).SetBytes(il)
236 if ilNum.Cmp(ec.S256().N) >= 0 || ilNum.Sign() == 0 {
237 return nil, ErrInvalidChild
238 }
239 // The algorithm used to derive the child key depends on whether or not a private or public child is being derived.
240 //
241 // For private children:
242 //
243 // childKey = parse256(Il) + parentKey
244 //
245 // For public children:
246 //
247 // childKey = serP(point(parse256(Il)) + parentKey)
248 var isPrivate bool
249 var childKey []byte
250 if k.isPrivate {
251 // Case #1 or #2.
252 //
253 // Add the parent private key to the intermediate private key to derive the final child key.
254 //
255 // childKey = parse256(Il) + parenKey
256 keyNum := new(big.Int).SetBytes(k.key)
257 ilNum.Add(ilNum, keyNum)
258 ilNum.Mod(ilNum, ec.S256().N)
259 childKey = ilNum.Bytes()
260 isPrivate = true
261 } else {
262 // Case #3.
263 //
264 // Calculate the corresponding intermediate public key for intermediate private key.
265 ilx, ily := ec.S256().ScalarBaseMult(il)
266 if ilx.Sign() == 0 || ily.Sign() == 0 {
267 return nil, ErrInvalidChild
268 }
269 // Convert the serialized compressed parent public key into X and Y coordinates so it can be added to the
270 // intermediate public key.
271 pubKey, e := ec.ParsePubKey(k.key, ec.S256())
272 if e != nil {
273 E.Ln(e)
274 return nil, e
275 }
276 // Add the intermediate public key to the parent public key to derive the final child key. childKey =
277 // serP(point(parse256(Il)) + parentKey)
278 childX, childY := ec.S256().Add(ilx, ily, pubKey.X, pubKey.Y)
279 pk := ec.PublicKey{Curve: ec.S256(), X: childX, Y: childY}
280 childKey = pk.SerializeCompressed()
281 }
282 // The fingerprint of the parent for the derived child is the first 4 bytes of the RIPEMD160(SHA256(parentPubKey)).
283 parentFP := btcaddr.Hash160(k.pubKeyBytes())[:4]
284 return NewExtendedKey(
285 k.version, childKey, childChainCode, parentFP,
286 k.depth+1, i, isPrivate,
287 ), nil
288 }
289 290 // Neuter returns a new extended public key from this extended private key. The same extended key will be returned
291 // unaltered if it is already an extended public key.
292 //
293 // As the name implies, an extended public key does not have access to the private key, so it is not capable of signing
294 // transactions or deriving child extended private keys. However, it is capable of deriving further child extended
295 // public keys.
296 func (k *ExtendedKey) Neuter() (*ExtendedKey, error) {
297 // Already an extended public key.
298 if !k.isPrivate {
299 return k, nil
300 }
301 // Get the associated public extended key version bytes.
302 version, e := chaincfg.HDPrivateKeyToPublicKeyID(k.version)
303 if e != nil {
304 E.Ln(e)
305 return nil, e
306 }
307 // Convert it to an extended public key. The key for the new extended key will simply be the pubkey of the current
308 // extended private key.
309 //
310 // This is the function N((k,c)) -> (K, c) from [BIP32].
311 return NewExtendedKey(
312 version, k.pubKeyBytes(), k.chainCode, k.parentFP,
313 k.depth, k.childNum, false,
314 ), nil
315 }
316 317 // ECPubKey converts the extended key to a ec public key and returns it.
318 func (k *ExtendedKey) ECPubKey() (*ec.PublicKey, error) {
319 return ec.ParsePubKey(k.pubKeyBytes(), ec.S256())
320 }
321 322 // ECPrivKey converts the extended key to a ec private key and returns it. As you might imagine this is only possible if
323 // the extended key is a private extended key (as determined by the IsPrivate function). The ErrNotPrivExtKey error will
324 // be returned if this function is called on a public extended key.
325 func (k *ExtendedKey) ECPrivKey() (*ec.PrivateKey, error) {
326 if !k.isPrivate {
327 return nil, ErrNotPrivExtKey
328 }
329 privKey, _ := ec.PrivKeyFromBytes(ec.S256(), k.key)
330 return privKey, nil
331 }
332 333 // Address converts the extended key to a standard bitcoin pay-to-pubkey-hash address for the passed network.
334 func (k *ExtendedKey) Address(net *chaincfg.Params) (*btcaddr.PubKeyHash, error) {
335 pkHash := btcaddr.Hash160(k.pubKeyBytes())
336 return btcaddr.NewPubKeyHash(pkHash, net)
337 }
338 339 // paddedAppend appends the src byte slice to dst, returning the new slice. If the length of the source is smaller than
340 // the passed size, leading zero bytes are appended to the dst slice before appending src.
341 func paddedAppend(size uint, dst, src []byte) []byte {
342 for i := 0; i < int(size)-len(src); i++ {
343 dst = append(dst, 0)
344 }
345 return append(dst, src...)
346 }
347 348 // String returns the extended key as a human-readable base58-encoded string.
349 func (k *ExtendedKey) String() string {
350 if len(k.key) == 0 {
351 return "zeroed extended key"
352 }
353 var childNumBytes [4]byte
354 binary.BigEndian.PutUint32(childNumBytes[:], k.childNum)
355 // The serialized format is:
356 //
357 // version (4) || depth (1) || parent fingerprint (4)) || child num (4) || chain code (32) || key data (33) ||
358 // checksum (4)
359 serializedBytes := make([]byte, 0, serializedKeyLen+4)
360 serializedBytes = append(serializedBytes, k.version...)
361 serializedBytes = append(serializedBytes, k.depth)
362 serializedBytes = append(serializedBytes, k.parentFP...)
363 serializedBytes = append(serializedBytes, childNumBytes[:]...)
364 serializedBytes = append(serializedBytes, k.chainCode...)
365 if k.isPrivate {
366 serializedBytes = append(serializedBytes, 0x00)
367 serializedBytes = paddedAppend(32, serializedBytes, k.key)
368 } else {
369 serializedBytes = append(serializedBytes, k.pubKeyBytes()...)
370 }
371 checkSum := chainhash.DoubleHashB(serializedBytes)[:4]
372 serializedBytes = append(serializedBytes, checkSum...)
373 return base58.Encode(serializedBytes)
374 }
375 376 // IsForNet returns whether or not the extended key is associated with the passed bitcoin network.
377 func (k *ExtendedKey) IsForNet(net *chaincfg.Params) bool {
378 return bytes.Equal(k.version, net.HDPrivateKeyID[:]) ||
379 bytes.Equal(k.version, net.HDPublicKeyID[:])
380 }
381 382 // SetNet associates the extended key, and any child keys yet to be derived from it, with the passed network.
383 func (k *ExtendedKey) SetNet(net *chaincfg.Params) {
384 if k.isPrivate {
385 k.version = net.HDPrivateKeyID[:]
386 } else {
387 k.version = net.HDPublicKeyID[:]
388 }
389 }
390 391 // zero sets all bytes in the passed slice to zero. This is used to explicitly clear private key material from memory.
392 func zero(b []byte) {
393 lenb := len(b)
394 for i := 0; i < lenb; i++ {
395 b[i] = 0
396 }
397 }
398 399 // Zero manually clears all fields and bytes in the extended key. This can be used to explicitly clear key material from
400 // memory for enhanced security against memory scraping. This function only clears this particular key and not any
401 // children that have already been derived.
402 func (k *ExtendedKey) Zero() {
403 zero(k.key)
404 zero(k.pubKey)
405 zero(k.chainCode)
406 zero(k.parentFP)
407 k.version = nil
408 k.key = nil
409 k.depth = 0
410 k.childNum = 0
411 k.isPrivate = false
412 }
413 414 // NewMaster creates a new master node for use in creating a hierarchical deterministic key chain. The seed must be
415 // between 128 and 512 bits and should be generated by a cryptographically secure random generation source.
416 //
417 // NOTE: There is an extremely small chance (< 1 in 2^127) the provided seed will derive to an unusable secret key. The
418 // ErrUnusable error will be returned if this should occur, so the caller must check for it and generate a new seed
419 // accordingly.
420 func NewMaster(seed []byte, net *chaincfg.Params) (*ExtendedKey, error) {
421 // Per [BIP32], the seed must be in range [MinSeedBytes, MaxSeedBytes].
422 if len(seed) < MinSeedBytes || len(seed) > MaxSeedBytes {
423 return nil, ErrInvalidSeedLen
424 }
425 // First take the HMAC-SHA512 of the master key and the seed data:
426 //
427 // I = HMAC-SHA512(Key = "Parallelcoin seed", Data = S)
428 hmac512 := hmac.New(sha512.New, masterKey)
429 _, e := hmac512.Write(seed)
430 if e != nil {
431 E.Ln(e)
432 }
433 lr := hmac512.Sum(nil)
434 // Split "I" into two 32-byte sequences Il and Ir where:
435 //
436 // Il = master secret key
437 //
438 // Ir = master chain code
439 secretKey := lr[:len(lr)/2]
440 chainCode := lr[len(lr)/2:]
441 // Ensure the key in usable.
442 secretKeyNum := new(big.Int).SetBytes(secretKey)
443 if secretKeyNum.Cmp(ec.S256().N) >= 0 || secretKeyNum.Sign() == 0 {
444 return nil, ErrUnusableSeed
445 }
446 parentFP := []byte{0x00, 0x00, 0x00, 0x00}
447 return NewExtendedKey(
448 net.HDPrivateKeyID[:], secretKey, chainCode,
449 parentFP, 0, 0, true,
450 ), nil
451 }
452 453 // NewKeyFromString returns a new extended key instance from a base58-encoded extended key.
454 func NewKeyFromString(key string) (*ExtendedKey, error) {
455 // The base58-decoded extended key must consist of a serialized payload plus an additional 4 bytes for the checksum.
456 decoded := base58.Decode(key)
457 if len(decoded) != serializedKeyLen+4 {
458 return nil, ErrInvalidKeyLen
459 }
460 // The serialized format is:
461 //
462 // version (4) || depth (1) || parent fingerprint (4)) || child num (4) || chain code (32) || key data (33) ||
463 // checksum (4)
464 //
465 // Split the payload and checksum up and ensure the checksum matches.
466 payload := decoded[:len(decoded)-4]
467 checkSum := decoded[len(decoded)-4:]
468 expectedCheckSum := chainhash.DoubleHashB(payload)[:4]
469 if !bytes.Equal(checkSum, expectedCheckSum) {
470 return nil, ErrBadChecksum
471 }
472 // Deserialize each of the payload fields.
473 version := payload[:4]
474 depth := payload[4:5][0]
475 parentFP := payload[5:9]
476 childNum := binary.BigEndian.Uint32(payload[9:13])
477 chainCode := payload[13:45]
478 keyData := payload[45:78]
479 // The key data is a private key if it starts with 0x00. Serialized compressed pubkeys either start with 0x02 or
480 // 0x03.
481 isPrivate := keyData[0] == 0x00
482 if isPrivate {
483 // Ensure the private key is valid. It must be within the range of the order of the secp256k1 curve and not be
484 // 0.
485 keyData = keyData[1:]
486 keyNum := new(big.Int).SetBytes(keyData)
487 if keyNum.Cmp(ec.S256().N) >= 0 || keyNum.Sign() == 0 {
488 return nil, ErrUnusableSeed
489 }
490 } else {
491 // Ensure the public key parses correctly and is actually on the secp256k1 curve.
492 _, e := ec.ParsePubKey(keyData, ec.S256())
493 if e != nil {
494 E.Ln(e)
495 return nil, e
496 }
497 }
498 return NewExtendedKey(
499 version, keyData, chainCode, parentFP, depth,
500 childNum, isPrivate,
501 ), nil
502 }
503 504 // GenerateSeed returns a cryptographically secure random seed that can be used as the input for the NewMaster function
505 // to generate a new master node. The length is in bytes and it must be between 16 and 64 (128 to 512 bits). The
506 // recommended length is 32 (256 bits) as defined by the RecommendedSeedLen constant.
507 func GenerateSeed(length uint8) ([]byte, error) {
508 // Per [BIP32], the seed must be in range [MinSeedBytes, MaxSeedBytes].
509 if length < MinSeedBytes || length > MaxSeedBytes {
510 return nil, ErrInvalidSeedLen
511 }
512 buf := make([]byte, length)
513 _, e := rand.Read(buf)
514 if e != nil {
515 E.Ln(e)
516 return nil, e
517 }
518 return buf, nil
519 }
520