MultiBit HD soft wallets are incompatible with other BIP32 m/0' wallets (BIP39 mnemonic conversion is incorrect)

[gurnec]

Summary: Using the same mnemonic sentence in a MultiBit HD soft wallet and other BIP32-m/0'-compliant wallets (plus account change index 0) produces different keys and addresses.

Steps to reproduce

1. Create a new HD soft wallet or restore one using a mnemonic sentence. For the sake of this example, restore a wallet using this mnemonic sentence: skin join dog sponsor camera puppy ritual diagram arrow poverty boy elbow
2. Obtain the first receive address.
   expected result in this example: 12QxtuyEM8KBG3ngNRe2CZE28hFw3b1KMJ
   actual result from MultiBit HD: 1LQ8XnNKqC7Vu7atH5k4X8qVCc9ug2q7WE

The expected result was generated by https://dcpos.github.io/bip39/ using the derivation path m/0'/0, however any BIP32-compliant wallet using the same path should produce the same expected result.

Definitions, just so we're on the same page:

• entropy bits - an array of bits as generated by a CSPRNG or a true entropy source; typically 128 - 256 bits long.
• mnemonic sentence - the result of encoding entropy bits plus a checksum into a BIP39 list of words; typically 12 - 24 words long.
• seed bits - the result of running a mnemonic sentence through PBKDF2; always exactly 512 bits long.

How to reproduce the keys and addresses currently produced by MultiBit HD

1. Take the mnemonic sentence (from above) and derive the seed bits. The result is the following 64 bytes: 34, 178, 134, 7, 239, 86, 118, 164, 174, 211, 216, 40, 102, 130, 237, 105, 108, 108, 164, 254, 91, 192, 184, 131, 226, 248, 39, 113, 38, 184, 73, 12, 18, 201, 145, 253, 252, 1, 255, 241, 231, 146, 213, 247, 70, 230, 184, 60, 68, 207, 57, 201, 121, 94, 67, 222, 133, 144, 59, 243, 115, 146, 86, 82
2. Take the seed bits, and interpret them as though they were 512 entropy bits.
3. Take these 512 entropy bits, and derive a new mnemonic sentence as per BIP39. The result is this 48 word long mnemonic: trim snack gorilla discover coast hat member pig build snake mention balance acoustic neutral asthma swift oven choice human orange smart intact soup wild nice public assume lady wing snake critic enrich say session useful base echo nut emotion fantasy trumpet dog deer basket expand hand surface coach
4. Take this new mnemonic sentence, and derive keys and addresses according to BIP32 and a m/0'/0 path (for example at the website mentioned above). The result will be what MultiBit HD is currently producing (1LQ8XnNKqC7Vu7atH5k4X8qVCc9ug2q7WE will be the first address).

The issue is here: https://github.com/bitcoin-solutions/multibit-hd/blob/88bf9ec6863ec0bc33fc1796a80736b038f004b9/mbhd-core/src/main/java/org/multibit/hd/core/managers/WalletManager.java#L318

The DeterministicSeed constructor selected by overload resolution is the first one below; it takes as its first argument a byte array of entropy bits, but it is being passed a byte array of seed bits instead. Perhaps the second constructor below is the one that was intended, however AFAICT you can't construct a DeterministicSeed unless you either provide it with a mnemonic sentence, or let it generate its own mnemonic sentence (which may complicate the fix)....

DeterministicSeed(byte[] entropy, String passphrase, long creationTimeSeconds)
DeterministicSeed(byte[] seed, List<String> mnemonic, long creationTimeSeconds)

( edited for clarity: ) The simplest solution (passing it the mnemonic sentence in addition to the seed bits) probably wouldn't break existing wallets, but it would break the ability to restore existing wallets using only the mnemonic sentence, so I'm not sure what the best path forward is....

[gary-rowe]

Thanks for the feedback and detailed information. We went through compatibility testing a while back which I'll just reference here in case it's relevant to the upcoming investigation: #362.

[jim618]

Hi Gurnec,
Thanks for your bug report on BIP32 compatibility. Gary and I have discussed this this morning and I'm taking it on.
Once we have identified what the problem (assuming there is one) is I suggest we take a similar philosophy as to what the Android bitcoin wallets did with the RNG bug. i.e.

1. Fix it for newly created MBHD wallets and 'Restore wallet from seed and timestamp'
2. On every start up of MBHD check if the wallet has any 'non BIP32' keys/addresses in. If so, create an alert saying something like 'Empty your wallet - check this blog article for why - link to blog'.
3. In the transaction details wizard, mark any non BIP32 addresses with red text 'Do not use this address - link to blog'. That way people will be encouraged to use new BIP32 compliant addresses by creating a new request.
4. The non-BIP32 keys/addresses will have to stay in their wallets (forever) as they could have been given to someone who pays to them in the future. They will get backed up into the rolling backups and cloud backups. If ALL those backups fail then the user can download MBHD 0.0.7beta again and restore from their wallet words to regain access to their bitcoin. We keep all the old releases in our releases directory on multibit.org.

Plus we will write the usual blog article explaining it.

We should bite the bullet now whilst MBHD is in beta and make the HD key trees match BIP32 exactly. It's a big win that people can easily transfer/ clone their BIP32 wallets between different implementations.

Regards,

Jim

[gary-rowe]

Agreed on all points, Jim. The reason this slipped through compatibility testing was that I didn't formally check against a BIP32 seed, only a BIP32 xpub.

Better that it happens in the Beta phase than having it reach the larger audience.

[jim618]

I just recreated a MBHD soft wallet using the 'skin' seed in the OP.
The first key created is:
addr:1LQ8XnNKqC7Vu7atH5k4X8qVCc9ug2q7WE hash160:d4ca3e4c09dd0d5aa0089dae4a8589904652403a (M/0H/0/0)

Thus the path is what we'd expect but the address isn't (corroborating the OP).

[gurnec]

If I got things right, there might be a slightly easier way to go about a fix.

It's not that the addresses aren't BIP32 and along the right path, its just that the mnemonic sentence used to create them isn't what's expected. Maybe you could convert a Beta7 wallet into two Beta8 wallets, one with the "correct" short mnemonic, and the other with the old (long) mnemonic.

The nice thing about this is you won't have to worry about maintaining any special-case code (except the conversion process itself) or storing non-BIP32 loose keys. It also preserves some ability to move the old wallet elsewhere (assuming support for unusually long mnemonics).

From a user's perspective, I'm not so sure this would be an improvement... I just thought I'd throw out the idea.

(Also, sorry for being the bearer of bad news, I know you don't need more work on your plates...)

-Chris

[jim618]

Hi Chris,
That's an idea.
Better to find out now when we still are at the 'hundreds' of users rather than later.

The flexibility of HD wallets is great but it does make things more complicated.
We are expecting people to start producing compatibility tables with:
"If my bitcoin is in the HD wallet X then I can/ cannot see it in HD wallet Y".

[gary-rowe]

It's one to ponder. Jim's (originally Andreas') approach is the full belt-and-braces and may be useful if there is any other incompatibility issue uncovered in the future. Hopefully we won't, but there is always a possibility in the complex world of Bitcoin.

And, seriously, thank you for raising this @gurnec. We'd much rather know about problems and get them fixed early than to discover something like this further down the line. If this has fired you up to really dig into the code and uncover anything else then please go right ahead (that goes for anyone else reading this too).

We want MultiBit HD to be as solid as it possibly be and we need code reviews and testing to get there.

[jim618]

I've just pushed some unit tests (in WalletManagerTest) which capture this issue.
The tests are:
testCreateSkinSeedPhraseWalletInABadWay
This is what we are doing at the moment, where we are (incorrectly) passing in a seed byte array as an entropy byte array. Generates the wallets we have currently which are NOT BIP32 compliant.

testCreateSkinSeedPhraseWalletInAGoodWay
Wallet creation where the entropy byte array is passed in correctly. Creates wallets which (as far as this test tests) are BIP32 compliant.

I have used the 'skin' seed so you can directly compare the addresses generated to those given in the OP.

[jim618]

Pushed changes so that the 'wallet type' combo box in the restore wizard now respects the Lab setting to show/ hide restore of Beta 7 wallets.
These are all UI/ config changes.

To do:

1. Do a different restore according to wallet type in:RestoreWalletReportPanelView#createWalletFromSeedPhraseAndTimestamp
2. Make the create new wallet wizard create BIP32 compliant wallets (with correct WalletType).

[jim618]

I've pushed changes so that there is now a new wallet type MBHD_SOFT_WALLET_BIP32 where the address derivation is BIP32 compliant.
The old 'Beta7' wallet type is still supported.

Due to the postive selection of wallet types in the wallet list in the Credentials screen Beta7 code won't see the new wallets which is a Good Thing.

Users can use their previously created wallets without any change (they are HD wallets, just not BIP32 compliant). The wallet capabilities states this.

To restore a Beta7 wallet from the wallet words the user needs to:

1. Go to Tools | Labs and enable the 'Enable restore of Beta7 wallets'
2. Do a restore and when it asks 'What created these wallet words ?' choose the 'MBHD Beta7' option.
   Users don't see this wallet type unless they enable it in Labs - it would just be confusing.

I have done restores with both BIP32 wallets and Beta7 wallets successfully.
I have checked a Lighthouse wallet can be restored from wallet words ok.

I've still got some FEST tests to do (raised as an issue) and I'll write the blog article.

Awaiting review and closing

[gary-rowe]

Verified working with my Lighthouse account and a Beta7 wallet. Labs configuration worked fine.

Closing.

[gurnec]

You made really fast (& thorough) work of this issue, thanks!!

Just a small note - I probably should have called this a BIP39 compatibility issue more than a BIP32 issue. As gary-rowe already mentioned, things work fine when tested against an xpub/xprv, it's just the mnemonic-sentence-to-xprv step that was different, which is more in the BIP39 domain IMO.

Regardless, the solution from a UI point of view looks great to me.
Thanks again! -Chris

[gary-rowe]

Regarding BIP39, I agree - I'll edit the title to reflect the update.

If you encounter any further problems with MBHD don't hesitate to let us know.

[mackuba]

I tried loading my Hive Web wallet into Multibit HD today, it synced but it's showing 0 BTC and no transactions, is that the same problem as discussed here?

[jim618]

Unfortunately if https://dcpos.github.io/bip39/ is correct it is the Hive wallet structure that is not BIP32.
Have a look at that site at the path derivation for BIP32 (m/0h) and for Hive wallet (m/0h/0).
I think Hive have put in an extra level.

We would need confirmation of this.

[mackuba]

I thought that BIP32 doesn't specify what is the only right way to organize the addresses in subtrees, but only defines how the subtrees work at all, and it's up to the wallet developers (and additional BIPs like BIP44) to define which subtrees should be used for what?

I don't actually know what path Hive Web uses since I didn't work on it, @weilu could you comment on this? I know that the Hive passphrase is compatible with at least Breadwallet, I don't know about other BIP32 wallets (who else uses BIP32?).

[jim618]

You are correct - BIP32 is very flexible.
We will no doubt end up with a big cross compatiblity matrix:
"If your wallet was created in Wallet X, you can/cannot restore in Wallet Y'.

For reference the MultiBit HD first receiving address is:
m/0h/0/0

Lighthouse uses the same path derivation structure AFAIK

[jim618]

Sorry - rereading your post - that would mean that Hive is BIP32 compliant, just using a different path derivation than MultiBit HD.

[gurnec]

@jim618 @jsuder FYI the terminology on the https://dcpos.github.io/bip39/ page can be a bit confusing... when it refers to Hive's path being m/0'/0, it is excluding the final private key index. I'm fairly confident that Hive is using the same path as MultiBit HD Beta8, although I haven't directly tested it yet.

Regarding a compatibility matrix, it's something I've been thinking of recently too; more specifically a table which lists each wallet's BIP32 properties, such as path, account support, lookahead/gap_limit, ability to export/import xpubs (watching-only) & xprvs (and are they account-level or master-level), etc.... if I decide to take a stab at it, I'll open a thread on bitcointalk in the Alt clients forum.

edited to add: BIP39 support, since they don't all use BIP39

[jim618]

That would be great if Hive and MBHD are compatible - I'll probably have a stab at testing that.

[weilu]

Hive web's technical specs are documented here: https://github.com/hivewallet/hive-js/wiki/Technical-Specs. m/0'/0 is the external account, the receiving addresses are derived from that account sequentially, i.e. m/0'/0/0, m/0'/0/1, m/0'/0/2...

[jim618]

@weilu It all looks like it will work ! :-)

[gary-rowe]

I've just created a Hive web wallet for testing and verified that the same wallet words can be used in MultiBit HD as a BIP32 wallet. After sync completed the balance was identical.

@weilu Hive is compatible with MultiBit HD

[mackuba]

Hmm, I've tried on the latest beta from the site (0.0.7) and it still didn't work. Am I doing something wrong? (I did: Restore wallet -> entered 12 words -> What wallet: Multibit HD (BIP 32) -> no backup -> no timestamp -> entered password + conf -> full sync.)

[gary-rowe]

The Beta 7 installer (available from the download site) doesn't have the BIP32 fix - that's due in the Beta 8 milestone. The best way to stay up to date is to run the code from an IDE.

[mackuba]

Oh, ok. What did you change exactly in beta8 that adds this compatibility?

[gary-rowe]

Here's an upcoming blog article that we wrote to assist users: https://raw.githubusercontent.com/bitcoin-solutions/multibit-website/release-4.0.0/src/main/resources/views/html/en/blog/2015-03-10-bip32-wallet-compatibility.html

Sorry for the raw format, it's not released onto the beta site but it should answer most questions.

The quick summary is that we treated the seed bytes as entropy into the bitcoinj API in error. Changing our use of the API corrected the problem but left us with "Beta 7" wallets requiring eternal support.

[gurnec]

@jsuder It's a bit easier to read here, if you prefer: https://rawgit.com/bitcoin-solutions/multibit-website/release-4.0.0/src/main/resources/views/html/en/blog/2015-03-10-bip32-wallet-compatibility.html