The HK key derivation stumbles in rare cases

[Giszmo]

I think it is a bug in bitcore as Mycelium's bitlib, Schildbach's bitcoinJ and blockchain.info agree to disagree with how to derive m/44' from a seed I have.

This is mainnet but the user agreed to share the secret as we got the funds out.
He was using a bitcore script but copay works to show the issue.

Restoring the wallet
"surface poem manual curve size banner truly just object soup inhale craft"
yields one set of addresses on copay and a different one on Mycelium, blockchain.info (tested by pasting the xpub that bitcoinj, bitcore and bitlib agree on) and bitcoinJ (tested with custom code. See below.)

Upon further investigation all libs get from phrase to seed to m xpriv and would agree on m/x but not on m/x'. Thus, starting with .derive("m/44'") things diverge.

I would kindly ask for your cooperation to keep our wallets interoperable. If you feel this is a bug in the other libs, please also let us know.

---

I got the test vectors by running:

> var rootXPriv = new require('bitcore-mnemonic')("surface poem manual curve
 size banner truly just object soup inhale craft").toHDPrivateKey()
 undefined
> rootXPriv
 <HDPrivateKey:
 xprv9s21ZrQH143K35ARDviUNynUYAJvcAvGbfrLpsVStB8dVSYkriwjxAXPxna2uddxogs5jtUJXhqdHMxq5nUXrwW1yqJfxJScPsiC1Hm7q7A>
> rootXPriv.derive("m")
 <HDPrivateKey:
 xprv9s21ZrQH143K35ARDviUNynUYAJvcAvGbfrLpsVStB8dVSYkriwjxAXPxna2uddxogs5jtUJXhqdHMxq5nUXrwW1yqJfxJScPsiC1Hm7q7A>
> rootXPriv.derive("m/44'")
 <HDPrivateKey:
 xprv9vk9bXHrTJxKGrh2C438ANZQ4nY2bmnNWckgU4f53ECxUzS7ctbU8kQa3hr5xEiTYjhFzHFFrxATRS7rzZ9q8yxR7H52CYX8BJcHYifvQkU>
> rootXPriv.derive("m/44'/0'")
 <HDPrivateKey:
 xprv9x1Mgspn3xsS699TmcnEuzvL1sApTmUKGYzehFYnyzY3i2EfBh6mN8b2ZSAfvbRdNJbLYCDLmR9g5b49fAReavuVeeKG2kj9bNL81ZCs5bd>
> rootXPriv.derive("m/44'/0'/0'")
 <HDPrivateKey:
 xprv9yfdoZVLEGmpxJ4qzHW59jhwm6CLWSNmdvXLQRdWNGqDqfAwuKLXapAVQrtHoiDxKdiHpa2TkN4ZDAmeQ9bjBvX4HhdDgmZB7fNmCemMons>
> rootXPriv.derive("m/44'/0'/0'/0")
 <HDPrivateKey:
 xprvA278YSf9xDhX6mGsR6fTUELKKn92Vf2sHQLmmU6JVtd6w11owkhqHJgietZ8dJvPhDGp774RhVtVhAJBTcaE8PTJUJPUCYQBP7jdqa2cm4F>
> rootXPriv.derive("m/44'/0'/0'/0/0")
 <HDPrivateKey:
 xprvA4JXApUprCxaYcUG2fQCC3CjvKHVbYRnTohawmRQyTnmAFWQMdxMbaDR1Asa1ctmMrJ5uDN2KcDjG5XBRGm8dmueRwyUxPvgj87LfNXsku7>
> rootXPriv.derive("m/42'")
 <HDPrivateKey:
 xprv9vk9bXHrTJxKC2AMkAnsHecLtGxoMcK7SnYwxkNQNBDkr5eS7kpKjmyoQw1J1JrYQAXtJxzaTqB3xAEqQJfDUKZF6BnS8r45a96ePjnJGiT>
> rootXPriv.derive("m/42")
 <HDPrivateKey:
 xprv9vk9bXHi7eRM2Z2MduzHC1VLyXUuuT3qfTgjf2BD97JXofRiCyEY666hwzRzMNEU9h5DHTWsFVrYtngQyboNx4maYddAPC9gpo6wiHQVLue>

those pairs of path + xpriv I used as such:

@Test
public void testKunagiIssue62() throws UnreadableWalletException {
     String words = "surface poem manual curve size banner truly just object soup inhale craft";
     TestVector tv = new TestVector(null, words, "839f804eb61243b7400d8dcb3955997d421c02f86aec96070d46a772ab7366a954f812bc983d462aaf3dc33aa7aa5ce79bf86895fa8fc65f8a89faf8f13876f3", "");
     MasterSeed masterSeed = Bip39.generateSeedFromWordList(tv.wordList, tv.passphrase);
     assertEquals("passphrase should match test vector + normalization", masterSeed.getBip39Passphrase(), Normalizer.normalize(tv.passphrase, Normalizer.Form.NFKD));
     assertEquals("seed should match test vector", tv.bip32seed, HexUtils.toHex(masterSeed.getBip32Seed()));
     HdKeyNode rootNode = HdKeyNode.fromSeed(masterSeed.getBip32Seed());


     DeterministicSeed seed = new DeterministicSeed(words, null, "", 0L);
     DeterministicKeyChain keyChain = Wallet.fromSeed(MainNetParams.get(), seed).getActiveKeyChain();
     for (String[] derivKey : new String[][]{
             {"", "xprv9s21ZrQH143K35ARDviUNynUYAJvcAvGbfrLpsVStB8dVSYkriwjxAXPxna2uddxogs5jtUJXhqdHMxq5nUXrwW1yqJfxJScPsiC1Hm7q7A"},
             {"/42", "xprv9vk9bXHi7eRM2Z2MduzHC1VLyXUuuT3qfTgjf2BD97JXofRiCyEY666hwzRzMNEU9h5DHTWsFVrYtngQyboNx4maYddAPC9gpo6wiHQVLue"},

             {"/44H", "xprv9vk9bXHrTJxKGrh2C438ANZQ4nY2bmnNWckgU4f53ECxUzS7ctbU8kQa3hr5xEiTYjhFzHFFrxATRS7rzZ9q8yxR7H52CYX8BJcHYifvQkU"},
             {"/44H/0H", "xprv9x1Mgspn3xsS699TmcnEuzvL1sApTmUKGYzehFYnyzY3i2EfBh6mN8b2ZSAfvbRdNJbLYCDLmR9g5b49fAReavuVeeKG2kj9bNL81ZCs5bd"},
             {"/44H/0H/0H", "xprv9yfdoZVLEGmpxJ4qzHW59jhwm6CLWSNmdvXLQRdWNGqDqfAwuKLXapAVQrtHoiDxKdiHpa2TkN4ZDAmeQ9bjBvX4HhdDgmZB7fNmCemMons"},
             {"/44H/0H/0H/0", "xprvA278YSf9xDhX6mGsR6fTUELKKn92Vf2sHQLmmU6JVtd6w11owkhqHJgietZ8dJvPhDGp774RhVtVhAJBTcaE8PTJUJPUCYQBP7jdqa2cm4F"},
             {"/44H/0H/0H/0/0", "xprvA4JXApUprCxaYcUG2fQCC3CjvKHVbYRnTohawmRQyTnmAFWQMdxMbaDR1Asa1ctmMrJ5uDN2KcDjG5XBRGm8dmueRwyUxPvgj87LfNXsku7"}
     }) {
         String path = derivKey[0];
         String xpriv = derivKey[1];
         DeterministicKey key = keyChain.getKeyByPath(HDUtils.parsePath(path), true);
         String actualXpriv = key.serializePrivB58(MainNetParams.get());
         if(!xpriv.equals(actualXpriv)) {
             System.out.println("BitcoinJ path " + path + ": " + actualXpriv);
         }
         // assertEquals(path, xpriv, actualXpriv); }



     for (String[] derivKey : new String[][]{
             {"m", "xprv9s21ZrQH143K35ARDviUNynUYAJvcAvGbfrLpsVStB8dVSYkriwjxAXPxna2uddxogs5jtUJXhqdHMxq5nUXrwW1yqJfxJScPsiC1Hm7q7A"},
             {"m/42", "xprv9vk9bXHi7eRM2Z2MduzHC1VLyXUuuT3qfTgjf2BD97JXofRiCyEY666hwzRzMNEU9h5DHTWsFVrYtngQyboNx4maYddAPC9gpo6wiHQVLue"},

             {"m/44'", "xprv9vk9bXHrTJxKGrh2C438ANZQ4nY2bmnNWckgU4f53ECxUzS7ctbU8kQa3hr5xEiTYjhFzHFFrxATRS7rzZ9q8yxR7H52CYX8BJcHYifvQkU"},
             {"m/44'/0'", "xprv9x1Mgspn3xsS699TmcnEuzvL1sApTmUKGYzehFYnyzY3i2EfBh6mN8b2ZSAfvbRdNJbLYCDLmR9g5b49fAReavuVeeKG2kj9bNL81ZCs5bd"},
             {"m/44'/0'/0'", "xprv9yfdoZVLEGmpxJ4qzHW59jhwm6CLWSNmdvXLQRdWNGqDqfAwuKLXapAVQrtHoiDxKdiHpa2TkN4ZDAmeQ9bjBvX4HhdDgmZB7fNmCemMons"},
             {"m/44'/0'/0'/0", "xprvA278YSf9xDhX6mGsR6fTUELKKn92Vf2sHQLmmU6JVtd6w11owkhqHJgietZ8dJvPhDGp774RhVtVhAJBTcaE8PTJUJPUCYQBP7jdqa2cm4F"},
             {"m/44'/0'/0'/0/0", "xprvA4JXApUprCxaYcUG2fQCC3CjvKHVbYRnTohawmRQyTnmAFWQMdxMbaDR1Asa1ctmMrJ5uDN2KcDjG5XBRGm8dmueRwyUxPvgj87LfNXsku7"}
     }) {
         String path = derivKey[0];
         String xpriv = derivKey[1];
         String actualXpriv = rootNode.createChildNode(HdKeyPath.valueOf(path)).serialize(productionNetwork);
         if(!xpriv.equals(actualXpriv)) {
             System.out.println("bitlib path " + path + ": " + actualXpriv);
         }
         // assertEquals(path, xpriv, actualXpriv); }


     HdKeyNode childNode = rootNode.createChildNode(HdKeyPath.valueOf("m/44'/0'/0'/0/0"));
     Address address = childNode.getPublicKey().toAddress(productionNetwork);
     assertEquals("1CyEfZAvqfuw58hcwP9YAAjj1BcLLavBmi", address.toString());
 }

So the issue is with calculating the first derivation if hardening is involved.

[gabegattis]

I haven't looked deep into what you are seeing, but it may be related to our hardened derivation bug. See bitpay/bitcore-lib#116

Try using deriveChild() instead of derive() and I bet it will give you the results you expect.

[NicSil]

Here is the code used to get the address:

var Mnemonic = require('bitcore-mnemonic'); // https://bitcore.io/api/mnemonic/

exports.createWallet = function(seed) {
	var seed = new Mnemonic(seed);
	var hdPrivateKey = seed.toHDPrivateKey(); // https://bitcore.io/api/lib/hd-keys
	
	var derived = hdPrivateKey.derive("m/44'/0'/0'/0/0");
	var privateKey = derived.privateKey;
	var address = privateKey.toAddress();
	
	return {
		seed: seed,
		address: address
	};

How to you suggest to fix it?

[Giszmo]

The bug only affected hardened derivations using an extended private key, and did not affect public key derivation. It also did not affect every derivation and would happen 1 in 256 times where the private key for the extended private key had a leading zero (e.g. any private key less than or equal to '0fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff')

> rootXPriv.derive("m").privateKey
<PrivateKey: 270f3f11f2cf40eaa5f069fa9f7fa512ef2d8072a45142060e4dd2468a39c4, network: livenet>
> rootXPriv.derive(44, true).privateKey
<PrivateKey: 24537700cabb8efae7d0e65f06aff7dcb522def39a59176010e9592c11b1a852, network: livenet>
> rootXPriv.derive("m/44'").privateKey
<PrivateKey: 24537700cabb8efae7d0e65f06aff7dcb522def39a59176010e9592c11b1a852, network: livenet>


  270f3f11f2cf40eaa5f069fa9f7fa512ef2d8072a45142060e4dd2468a39c4 <
0fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff <
24537700cabb8efae7d0e65f06aff7dcb522def39a59176010e9592c11b1a852

Yep, looks like same bug.

@NicSil, to fix your script you will have to wait for availability of .deriveChild(), which will be the fixed version of .derive(), which got deprecated but ... will be of literal value for all eternity as people with coins disappeared from their wallets will pop up ever after.

[Giszmo]

I guess it's clear this is a known bug in bitcore-lib that bitpay/bitcore-lib#116 should fix.