1 // Package hd is BIP32 private derivation, and the account paths a swap wallet uses.
2 //
3 // It derives from a seed and never from a public key: the wallet holds its own keys, so it
4 // has no reason to derive a child it cannot spend, and private derivation is the smaller
5 // surface. A future watch-only export needs public derivation and is not in this cut.
6 package hd
7 8 import (
9 "crypto/hmac"
10 "crypto/sha256"
11 "crypto/sha512"
12 "encoding/binary"
13 "fmt"
14 "strconv"
15 "strings"
16 17 "git.smesh.lol/nostrino/pkg/crypto/decred/secp256k1"
18 "golang.org/x/crypto/ripemd160"
19 )
20 21 // Hardened is the index offset that marks a hardened child, as BIP32 defines it.
22 const Hardened uint32 = 0x80000000
23 24 // Key is one node of a BIP32 tree: a private scalar and the chain code that derives the
25 // next level.
26 type Key struct {
27 // Private is the 32-byte scalar.
28 Private [32]byte
29 // ChainCode is the 32-byte chain code, which is what makes a child unique to its
30 // parent even when two parents share a key.
31 ChainCode [32]byte
32 // Depth is 0 at the master key.
33 Depth byte
34 // ParentFingerprint is the first four bytes of the parent's hash160.
35 ParentFingerprint [4]byte
36 // Child is the index this key was derived at, zero at the master key.
37 Child uint32
38 // Path is every index from the master key down to this one. It is carried rather than
39 // looked up, because a key that cannot say where it came from cannot be written down
40 // and found again, and a wallet's addresses are exactly that.
41 Path []uint32
42 }
43 44 // NewMaster derives the master key from a BIP39 seed.
45 //
46 // The seed is 16 to 64 bytes per BIP32; a BIP39 seed is 64.
47 func NewMaster(seed []byte) (*Key, error) {
48 if len(seed) < 16 || len(seed) > 64 {
49 return nil, fmt.Errorf("a BIP32 seed is 16 to 64 bytes, not %d", len(seed))
50 }
51 52 mac := hmac.New(sha512.New, []byte("Bitcoin seed"))
53 mac.Write(seed)
54 55 sum := mac.Sum(nil)
56 57 key, err := keyFromParts(sum[:32], sum[32:], 0, [4]byte{}, 0, nil)
58 59 if err != nil {
60 return nil, fmt.Errorf("this seed has no master key: %w", err)
61 }
62 63 return key, nil
64 }
65 66 // keyFromParts validates a private scalar and assembles a key.
67 func keyFromParts(
68 private, chainCode []byte, depth byte, parent [4]byte, child uint32, path []uint32,
69 ) (*Key, error) {
70 if len(private) != 32 || len(chainCode) != 32 {
71 return nil, fmt.Errorf("a key is a 32-byte scalar and a 32-byte chain code")
72 }
73 74 var scalar secp256k1.ModNScalar
75 76 if overflow := scalar.SetByteSlice(private); overflow {
77 return nil, fmt.Errorf("the scalar is not below the curve order")
78 }
79 80 if scalar.IsZero() {
81 return nil, fmt.Errorf("the scalar is zero")
82 }
83 84 out := &Key{Depth: depth, ParentFingerprint: parent, Child: child}
85 86 if len(path) > 0 {
87 out.Path = append([]uint32(nil), path...)
88 }
89 90 copy(out.ChainCode[:], chainCode)
91 92 scalar.PutBytesUnchecked(out.Private[:])
93 94 // The scalar is stored as the value the curve uses, so a caller that reads Private
95 // gets the canonical 32 bytes whatever the input's leading zeroes were.
96 return out, nil
97 }
98 99 // Valid reports whether a key is usable.
100 func (k *Key) Valid() bool { return k != nil }
101 102 // Public returns the 33-byte compressed public key.
103 func (k *Key) Public() []byte {
104 private := secp256k1.PrivKeyFromBytes(k.Private[:])
105 106 return private.PubKey().SerializeCompressed()
107 }
108 109 // ChildKey derives one child key.
110 //
111 // A hardened index (at least 2^31) is derived from the private key; a normal index from the
112 // parent's public key. Both are the same arithmetic on the parent's scalar, which is why
113 // this package never needs point addition.
114 func (k *Key) ChildKey(index uint32) (*Key, error) {
115 mac := hmac.New(sha512.New, k.ChainCode[:])
116 117 if index >= Hardened {
118 mac.Write([]byte{0})
119 mac.Write(k.Private[:])
120 } else {
121 mac.Write(k.Public())
122 }
123 124 var encoded [4]byte
125 126 binary.BigEndian.PutUint32(encoded[:], index)
127 128 mac.Write(encoded[:])
129 130 sum := mac.Sum(nil)
131 132 var offset secp256k1.ModNScalar
133 134 if overflow := offset.SetByteSlice(sum[:32]); overflow {
135 // Roughly one seed in 2^127. BIP32 says to derive the next index; a caller with a
136 // fixed path cannot, so it is an error and the wallet's index loop can skip it.
137 return nil, fmt.Errorf("child %d is unrepresentable at this path", index)
138 }
139 140 var parent secp256k1.ModNScalar
141 142 parent.SetByteSlice(k.Private[:])
143 144 var child secp256k1.ModNScalar
145 146 child.Add2(&offset, &parent)
147 148 if child.IsZero() {
149 return nil, fmt.Errorf("child %d derives the zero key", index)
150 }
151 152 var private [32]byte
153 154 child.PutBytesUnchecked(private[:])
155 156 next := &Key{
157 Private: private,
158 Depth: k.Depth + 1,
159 ParentFingerprint: k.Fingerprint(),
160 Child: index,
161 Path: append(append([]uint32(nil), k.Path...), index),
162 }
163 164 copy(next.ChainCode[:], sum[32:])
165 166 return next, nil
167 }
168 169 // Fingerprint is the first four bytes of the key's hash160, which identifies it as a
170 // parent in a serialised extended key.
171 func (k *Key) Fingerprint() [4]byte {
172 hash := hash160(k.Public())
173 174 var out [4]byte
175 176 copy(out[:], hash[:4])
177 178 return out
179 }
180 181 // hash160 is sha256 then ripemd160, the identifier a P2WPKH address carries.
182 func hash160(data []byte) [20]byte {
183 first := sha256.Sum256(data)
184 185 hasher := ripemd160.New()
186 hasher.Write(first[:])
187 188 var out [20]byte
189 190 copy(out[:], hasher.Sum(nil))
191 192 return out
193 }
194 195 // Path is a derivation path such as m/84'/0'/0'/0/0.
196 type Path []uint32
197 198 // String renders a path in the usual notation.
199 func (p Path) String() string {
200 var out strings.Builder
201 202 out.WriteString("m")
203 204 for _, index := range p {
205 out.WriteString("/")
206 out.WriteString(strconv.FormatUint(uint64(index&^Hardened), 10))
207 208 if index >= Hardened {
209 out.WriteString("'")
210 }
211 }
212 213 return out.String()
214 }
215 216 // ParsePath reads a derivation path.
217 //
218 // Both the apostrophe and an "h" are accepted for a hardened index, because a person who
219 // copies a path from another wallet has no way to know which one this client wants.
220 func ParsePath(text string) (Path, error) {
221 trimmed := strings.TrimSpace(text)
222 223 if trimmed == "" {
224 return nil, fmt.Errorf("a derivation path is required")
225 }
226 227 parts := strings.Split(trimmed, "/")
228 229 if parts[0] != "m" && parts[0] != "M" {
230 return nil, fmt.Errorf("a derivation path starts with m: %q", text)
231 }
232 233 path := make(Path, 0, len(parts)-1)
234 235 for _, part := range parts[1:] {
236 if part == "" {
237 return nil, fmt.Errorf("the derivation path has an empty level: %q", text)
238 }
239 240 hardened := false
241 242 switch {
243 case strings.HasSuffix(part, "'"):
244 hardened = true
245 part = strings.TrimSuffix(part, "'")
246 case strings.HasSuffix(part, "h"), strings.HasSuffix(part, "H"):
247 hardened = true
248 part = part[:len(part)-1]
249 }
250 251 index, err := strconv.ParseUint(part, 10, 32)
252 253 if err != nil {
254 return nil, fmt.Errorf("the derivation level %q is not a number: %q", part, text)
255 }
256 257 if index >= uint64(Hardened) {
258 return nil, fmt.Errorf("the derivation level %q is out of range", part)
259 }
260 261 value := uint32(index)
262 263 if hardened {
264 value |= Hardened
265 }
266 267 path = append(path, value)
268 }
269 270 return path, nil
271 }
272 273 // Derive walks a path from this key.
274 func (k *Key) Derive(path Path) (*Key, error) {
275 current := k
276 277 for _, index := range path {
278 next, err := current.ChildKey(index)
279 280 if err != nil {
281 return nil, fmt.Errorf("%s at %s: %w", path, current.ChildPath(), err)
282 }
283 284 current = next
285 }
286 287 return current, nil
288 }
289 290 // ChildPath renders the path this key was derived at, for an error message or a record.
291 func (k *Key) ChildPath() string { return Path(k.Path).String() }
292