Repository: bitcoinjs/bitcoinjs-lib
Pull request #538 (2016-02-06 01:08:04)

Adding path derivation
Now this might be a bit controversial, but I found something like that to be really useful.

What will be controversial, I think:

* the usage of strings as indexes 
   * yes, it's not ideal, but adding an apostrophe is a way to easily say "this is hardened" and this notation is common, and you cannot do that otherwise
* the usage of descriptions as paths in the tests
   * again, not ideal, but I didn't want to repeat the description as path again if it's already there

dcousens: ping @jprichardson,  merge here,  finalize API,  then extract to `BIP32`?
dcousens: IMHO,  I think  `node.derivePath('m/0'/1/0')` would be a better API,  aka a `String` argument.

I don't think there is much value in adding an `Array` based path API.  You can trivially do that using `derive` and `forEach` already.
dcousens: We also intend to break out `BIP32` to its own module,  probably encompassing `HDNode` standalone with other utilities for making life easier when dealing with them.

See https://github.com/bitcoinjs/bitcoinjs-lib/issues/508#issuecomment-176188789
runn1ng: ad array based API:

My original thinking for using Array was "What if someone puts there an array that is *not* a path, or that is wrongly formatted? Do I have to trim spaces around the slashes? Does it have to start with 'm/' or not? What if the node is not a master and is a sub-node, the 'm/' doesn't make sense", and that by using Array I just go around all these problems.

Then I also thought about the function accepting both array and string, but that would be really ugly.
jprichardson: > ping @jprichardson, merge here, then extract to BIP32?

@dcousens Yep, I don't see any harm in adding it at the moment. Agreed on not needing the array API. 
runn1ng: how exactly would you do the string-based API? Should it start with 'm/', or should it be "relative"? So for example,` master.derivePath("0'/1/0'/1") `(which would equal to `master.derivePath("0'/1").derivePath("0'/1")`)
dcousens: I think `0'/1/0` is a suitable enough API.
We could easily regex,  optionally skipping any prefixes until the first number is reached?
runn1ng: By "we", you mean the code in the library, or the user of the API?
dcousens: We, the developers of this library.
My suggestion was that we could make the `m/` optional,  but,  ambiguous API's suck,  so,  not sure.
runn1ng: >ambiguous API's suck

Exactly. But then, I don't know how to make it unambiguous and non-sucky.

And I don't also want to totally abandon it either. 😓
dcousens: @runn1ng I think if an `m/` is present,  we check that there is no parent (aka, this is a `master` node).
If it isn't present,  proceed on with derivation.

Thoughts?
runn1ng: Sorry for the delay. OK, that sounds reasonable
runn1ng: Done :)

Patch:
diff --git a/src/hdnode.js b/src/hdnode.js
index 62cac56e..784acf5d 100644
--- a/src/hdnode.js
+++ b/src/hdnode.js
@@ -291,6 +291,30 @@ HDNode.prototype.isNeutered = function () {
   return !(this.keyPair.d)
 }
 
+HDNode.prototype.derivePath = function (path) {
+  typeforce(types.Bip32Path, path)
+
+  var splitPath = path.split('/')
+  if (splitPath[0] === 'm') {
+    if (this.parentFingerprint) {
+      throw new Error('Not a master node')
+    }
+
+    splitPath = splitPath.slice(1)
+  }
+
+  return splitPath.reduce(function (prevHd, indexStr) {
+    var index
+    if (indexStr.slice(-1) === "'") {
+      index = parseInt(indexStr.slice(0, -1), 10)
+      return prevHd.deriveHardened(index)
+    } else {
+      index = parseInt(indexStr, 10)
+      return prevHd.derive(index)
+    }
+  }, this)
+}
+
 HDNode.prototype.toString = HDNode.prototype.toBase58
 
 module.exports = HDNode
diff --git a/src/types.js b/src/types.js
index 7ddf8c85..69ab787d 100644
--- a/src/types.js
+++ b/src/types.js
@@ -26,6 +26,11 @@ function UInt53 (value) {
     Math.floor(value) === value
 }
 
+function Bip32Path (value) {
+  return typeforce.String(value) &&
+    value.match(/^(m\/)?(\d+'?\/)*\d+'?$/)
+}
+
 // external dependent types
 var BigInt = typeforce.quacksLike('BigInteger')
 var ECPoint = typeforce.quacksLike('Point')
@@ -57,7 +62,8 @@ var types = {
   UInt8: UInt8,
   UInt31: UInt31,
   UInt32: UInt32,
-  UInt53: UInt53
+  UInt53: UInt53,
+  Bip32Path: Bip32Path
 }
 
 for (var typeName in typeforce) {


Test patch:
diff --git a/test/fixtures/hdnode.json b/test/fixtures/hdnode.json
index 93530d2d..21ca41d9 100644
--- a/test/fixtures/hdnode.json
+++ b/test/fixtures/hdnode.json
@@ -109,7 +109,7 @@
           "address": "19EuDJdgfRkwCmRzbzVBHZWQG9QNWhftbZ"
         },
         {
-          "description": "m/0/2147483647",
+          "description": "m/0/2147483647'",
           "m": 2147483647,
           "hardened": true,
           "wif": "L1m5VpbXmMp57P3knskwhoMTLdhAAaXiHvnGLMribbfwzVRpz2Sr",
@@ -134,7 +134,7 @@
           "address": "1BxrAr2pHpeBheusmd6fHDP2tSLAUa3qsW"
         },
         {
-          "description": "m/0/2147483647'/1/2147483646",
+          "description": "m/0/2147483647'/1/2147483646'",
           "m": 2147483646,
           "hardened": true,
           "wif": "L5KhaMvPYRW1ZoFmRjUtxxPypQ94m6BcDrPhqArhggdaTbbAFJEF",
@@ -232,6 +232,27 @@
         "exception": "Point is not on the curve",
         "hex": "0488b21e000000000000000000873dff81c02f525623fd1fe5167eac3a55a049de3d314bb42ee227ffed37d508020045400697100007000037899988826500030092003000016366806305909050"
       }
+    ],
+    "deriveHardened": [
+      2147483648,
+      null,
+      "foo",
+      -1
+    ],
+    "derive": [
+      4294967296,
+      null,
+      "foo",
+      -1
+    ],
+    "derivePath": [
+      2,
+      [2, 3, 4],
+      "/",
+      "m/m/123",
+      "a/0/1/2",
+      "m/0/  1  /2",
+      "m/0/1.5/2"
     ]
   }
 }
diff --git a/test/hdnode.js b/test/hdnode.js
index 4e9f1cf6..c5a55fbe 100644
--- a/test/hdnode.js
+++ b/test/hdnode.js
@@ -272,6 +272,7 @@ describe('HDNode', function () {
     fixtures.valid.forEach(function (f) {
       var network = NETWORKS[f.network]
       var hd = HDNode.fromSeedHex(f.master.seed, network)
+      var master = hd
 
       // FIXME: test data is only testing Private -> private for now
       f.children.forEach(function (c, i) {
@@ -285,6 +286,42 @@ describe('HDNode', function () {
           verifyVector(hd, c, i + 1)
         })
       })
+
+      // testing deriving path from master
+      f.children.forEach(function (c) {
+        it(c.description + ' from ' + f.master.fingerprint + ' by path', function () {
+          var path = c.description
+          var child = master.derivePath(path)
+
+          var pathSplit = path.split('/').slice(1)
+          var pathNotM = pathSplit.join('/')
+          var childNotM = master.derivePath(pathNotM)
+
+          verifyVector(child, c, pathSplit.length)
+          verifyVector(childNotM, c, pathSplit.length)
+        })
+      })
+
+      // testing deriving path from children
+      f.children.forEach(function (c, i) {
+        var cn = master.derivePath(c.description)
+
+        f.children.slice(i + 1).forEach(function (cc) {
+          it(cc.description + ' from ' + c.fingerprint + ' by path', function () {
+            var path = cc.description
+
+            var pathSplit = path.split('/').slice(i + 2)
+            var pathEnd = pathSplit.join('/')
+            var pathEndM = 'm/' + pathEnd
+            var child = cn.derivePath(pathEnd)
+            verifyVector(child, cc, pathSplit.length + i + 1)
+
+            assert.throws(function () {
+              cn.derivePath(pathEndM)
+            }, /Not a master node/)
+          })
+        })
+      })
     })
 
     it('works for Private -> public (neutered)', function () {
@@ -328,46 +365,27 @@ describe('HDNode', function () {
       }, /Could not derive hardened child key/)
     })
 
-    it('throws on negative indexes', function () {
-      var f = fixtures.valid[0]
-      var master = HDNode.fromBase58(f.master.base58, NETWORKS_LIST)
-
-      assert.throws(function () {
-        master.deriveHardened(-1)
-      }, /Expected UInt31/)
-      assert.throws(function () {
-        master.derive(-1)
-      }, /Expected UInt32/)
-    })
-
-    it('throws on high indexes', function () {
+    it('throws on wrong types', function () {
       var f = fixtures.valid[0]
       var master = HDNode.fromBase58(f.master.base58, NETWORKS_LIST)
 
-      assert.throws(function () {
-        master.deriveHardened(0x80000000)
-      }, /Expected UInt31/)
-      assert.throws(function () {
-        master.derive(0x100000000)
-      }, /Expected UInt32/)
-    })
+      fixtures.invalid.derive.forEach(function (fx) {
+        assert.throws(function () {
+          master.derive(fx)
+        }, /Expected UInt32/)
+      })
 
-    it('throws on non-numbers', function () {
-      var f = fixtures.valid[0]
-      var master = HDNode.fromBase58(f.master.base58, NETWORKS_LIST)
+      fixtures.invalid.deriveHardened.forEach(function (fx) {
+        assert.throws(function () {
+          master.deriveHardened(fx)
+        }, /Expected UInt31/)
+      })
 
-      assert.throws(function () {
-        master.deriveHardened()
-      }, /Expected UInt31/)
-      assert.throws(function () {
-        master.derive()
-      }, /Expected UInt32/)
-      assert.throws(function () {
-        master.deriveHardened('foo')
-      }, /Expected UInt31/)
-      assert.throws(function () {
-        master.derive('foo')
-      }, /Expected UInt32/)
+      fixtures.invalid.derivePath.forEach(function (fx) {
+        assert.throws(function () {
+          master.derivePath(fx)
+        }, /Expected Bip32Path/)
+      })
     })
   })
 })