Proposal: BIP32 (Hierarchical Deterministic Wallet) Support about stellar-protocol

[zulucrypto]

@bartekn - I've been looking into how BIP39 (mnemonic codes) would fit in with this and I think it may impact the path derivation.

From what I can tell from the Ledger's docs, each "app" running on it only gets access to a BIP32 path that it has to request. This means for maximum compatibility we have to go with how they're deriving the master key.

If they're doing it like other BIP39 generators (I've tested a javascript one, a PHP one, and looked at Trezor's implementation) then the algorithm looks something like this:

uint8_t hash[64]; // stores the final 64 bytes of the sha512 hash
HMAC_SHA512_CTX ctx;

sha512_init(&ctx, 'Bitcoin seed'); // this value is hardcoded
sha512_update(&ctx, seed); // "seed" is the raw bytes generated from the mnemonic
sha512_Final(&ctx, hash);

I think this will impact your Go PR since you'll need to include the hardcoded "Bitcoin seed" string as part of the data you're hashing to arrive at the same master key as the Ledger and Trezor.

Mnemonic test

mnemonic string, tested with https://iancoleman.io/bip39/ :

athlete sample issue bulk horn hundred two bike element scheme humble drink shy buzz advance blouse now present episode canoe pupil laugh lemon net

Using the above, I get a bip32 root key of xprv9s21ZrQH143K3gibDDyyvSrtBe54pQAWwEn6Eo55wAWdwvwWVS1arrvfxaeteBV7gytLt8QDe7FwR9MQmhDrfSoguuTUnBJb8zgV5RXXbKg

Deriving m/44'/148'/0' (had to modify the source code since the link above doesn't have an option for 148') then gets me a key of xprv9yKvAL8uvo8GbXpfU6tZjianzBgG34fd25WBg7vZFRncA9Sg48cDZkz9pF2491heYd57qbQBEMAXKHp1jVmEv6HRxvCEGuAoLvjCMzoYU2F

Decoding this key and passing the raw 32 bytes to StellarSdk.Keypair.fromRawEd25519Seed(rawBytes) gives me this keypair:

GCXY2T6AKYEA43GPXBXYFM53Y4TEPWBIQKMZPECJRO6UXFDRRE3SRDE2
SAHOYQ5U6NT35KC2KVXDOPX4IQLNK56KP4GGXMDSTJQSSIR6WXMWCNWL

@lenondupe Can you confirm that the Ledger works this way and what keypair is generated given the above mnemonic?

[bartekn]

I spent some time exploring BIP-[32, 39, 44] while working on stellar/go#81 and tyler-smith/go-bip32#7.

First of all, you call your proposal BIP32 but it's actually a mirror of BIP-44 (95% the same). Correct me if I'm wrong but I see no point of copying the full doc here. The key to BIP-44 is to use the same protocol for each coin so wallet developers don't have to search for per-coin specification. For example, BIP-44 is also not 100% applicable for Ethereum because of it's nature and all of the Ethereum wallets I've used just used main key (which is m/44'/60'/0'/0). For example, in Ledger Ethereum app you simply use one account for all your operations. I think we should do the same for Stellar.

I see your point when it comes to using primary_asset segment in the derivation path but given that in Stellar each account needs to have a minimum balance of, currently, 20 XLM plus 10 XLM per each subentry I don't think users will want to use this feature, they are more likely to have all their assets in a single account.

When it comes to BIP-32 for Stellar the main problem is we're using different elliptic curve: curve25519 instead of secp256k1 used in Bitcoin and Ethereum. During my research some time ago I found two papers dealing with this problem:

• 1st from chain.com which turns out to be insecure (https://chain.com/docs/1.1/protocol/specifications/chainkd)
• 2nd from University of Luxemburg that proves that chain.com's solution is vulnerable to timing attack and other problems. They proposed their own solution: https://cardanolaunch.com/assets/Ed25519_BIP.pdf

I couldn't find anything better so at this point I think there is no reliable method for deterministic key derivation for curve25519. Maybe @lenondupe has more information? But because of this, you can't use the full magic of BIP-32 and BIP-39, in other words: you can generate mnemonic code and derive private keys for master private key but you can't do the same for master public key. Actually I created a proof-of-concept recently: stellar/go#78 but obviously master public key -> child public key derivation doesn't work because of above.

Maybe @stanford-scs will have some time in a near future to research it (of course if my findings are correct).

I think it's a good idea to have this discussion now and try to come to a consensus. Indeed, it encouraged me to take a closer look at how to properly use the bip32 paths following bip44.

A couple of things.

While your scheme reuses the bip44 purpose field (44') it does not actually follow the bip44 scheme. Bip43 states: "We encourage different schemes to apply for assigning a separate BIP number and use the same number for purpose field, so addresses won't be generated from overlapping BIP32 spaces." So I think if we want to invent our own scheme we need our own bip too.

Summerizing your proposal, compared to bip44 it inserts a field for the network between the purpose field and the coin type field and removes the change and index fields. Instead of:
m / purpose' / coin type' / account' / change / address_index
we would have
/ purpose' / network' / coin type' / account'

Two observations about removing the change and address_index fields. I can't determine whether bip44 regards these fields as optional or not. However that may be, they indeed do not apply to Stellar and it would be better to not have to deal with them at all. Moreover the problem with the Ledger Nano S is that (quoting one of the Ledger devs) 'the way public key is derived from private one in EDDSA does not allow not hardened derivation of the ecdsa key'. You will notice that at both the change and address_index level public derivation is used (non-hardened). So it seems it is not even possible right now to follow bip44 exactly in this regard. In that case, better just ignore these fields.

About the network field, we need to think about how useful this would be as coin type is already a unique identifier. The one use I can think of is that it allows a Stellar-specific app to lock on the Stellar path 44'/148' while allowing derivation for all Stellar-based assets that wish to register their own coin type without requiring a new release. I'll explain. For instance, Ledger requires you to specify one or more bip32 paths when you load an app onto the device. The app is then 'locked' for that path, meaning attempts to derive from a different path are rejected. Note that this is not a full path, but a path prefix. So for the Ledger app I use 44'/148'.

But here appears another difference between Stellar and the type of network the authors of bip44 had in mind. On most other networks accounts are free so there is less incentive to use the same Ethereum address for all your Ethereum-based assets than is the case with Stellar. I'm wondering if we couldn't just assume people will want to use the same address for all their stellar-based assets. Probably the vast majority of people on the Ethereum network use the same address for all their Ethereum-based coins. And I see the Ethereum Ledger app simply locks on the ether and ether classic coin types and so assumes the same.

So the question remains is, do we want to / need to apply for a bip to register our own scheme or do we re-use / abuse / re-interpret bip44 for our own purpose, meaning:

1. don't use change and address_index fields
2. use coin type 148 for all Stellar-based assets

[zulucrypto]

While your scheme reuses the bip44 purpose field (44') it does not actually follow the bip44 scheme. Bip43 states: "We encourage different schemes to apply for assigning a separate BIP number and use the same number for purpose field, so addresses won't be generated from overlapping BIP32 spaces." So I think if we want to invent our own scheme we need our own bip too.

This is a good point, I arrived at my address based on the Trezor specification but after reading BIP43 I think you're right and something besides 44 should have been used for their purpose field.

I did a bit of research on this and found a thread where some Ethereum developers were trying to standardize on a HD wallet path. I haven't read the entire thread, but the consensus looked like it was to start all paths with m/44'/60'/ (60` being the Ether coin code).

See: ethereum/EIPs#84

It looks like we'd be following convention if we stuck with m/44'/148'/, but I see your point about BIP43 and I'm not opposed to registering a purpose for Stellar since it's fairly different from other currencies.

You will notice that at both the change and address_index level public derivation is used (non-hardened). So it seems it is not even possible right now to follow bip44 exactly in this regard. In that case, better just ignore these fields.

I'm in favor of maximum compatibility, so no issue here using a non-hardened account.

I'm wondering if we couldn't just assume people will want to use the same address for all their stellar-based assets.

I was a little torn on this since it seems like having multiple Stellar accounts is probably overcomplicating things, but from a privacy perspective it might be nice to separate your ICOs from each other or from your main wallet.

I don't have a strong objection to simplifying the path and having it just become m / 44' / 148' / account'

So the question remains is, do we want to / need to apply for a bip to register our own scheme or do we re-use / abuse / re-interpret bip44 for our own purpose, meaning

After reading the Ethereum thread above, I'm leaning towards "reinterpreting" BIP44 and sticking with m/44'/148'/ since that seems to be existing convention and a lot easier than registering a new purpose code.

Thanks for the link. It looks more like that discussion ended in the agreement to come up with a separate scheme to me though.

I was a little torn on this since it seems like having multiple Stellar accounts is probably overcomplicating things, but from a privacy perspective it might be nice to separate your ICOs from each other or from your main wallet.

Someone on that thread commented aptly that even for Ethereum separate accounts for different coins poses a problem since to use it you need native currency in your account to pay network fees. So, indeed, it's not only the activation of the account that plays a role.

It seems entirely unnecessary to reserve a dedicated field in order to allow users to have separate accounts for different coins. Users have 2^32 different accounts at their disposal by using the account field as they see fit. They can use 44'/148'/0' for their lumens, 44'/148'/1' for their mobi, etc. if they want. Reserving a separate field for coin type would suggest each coin necessarily be on a separate branch, which we seem to agree is not the case at all.

I love being pragmatic with these kinds of things. It is true that this proposal is not entirely compliant with BIP44 while using the BIP44 purpose. But as modern linguists agree, usage trumps formal definition and in practice we've seen 44' to mean rather something like 'here be crypto currency' instead of the technically exact definition outlined in the BIP44 proposal. For instance, Ethereum wallets have been using 44'/60'/account'/index, leaving out the change field. It's not like wallet developers that want to support different coins would benefit if we'd follow the specification exactly. Networks are so different they need custom handling anyway.

I agree with you that to take the path Ethereum developers are taking now of registering their own purpose seems cumbersome and a long winded process. We need a formal document that defines a standard for Stellar so that Stellar wallets can be interoperable in practice. We don't need advise or approval from bitcoin devs or wider crypto-currency community to achieve that. If there is a good argument why we should take that route I would like hear it. It hasn't occurred to me yet.

[zulucrypto]

It looks more like that discussion ended in the agreement to come up with a separate scheme to me though.

Good catch, I missed that.

I agree with the rest of the points you made and think we should go with m/44'/148'/ account' as the path and get rid of the primary_asset field.

Unless anyone else has comments, I'll update the specification and work on adding in some of the test vectors from https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#Test_Vectors so we can verify both our implementations are generating the expected addresses.

[zulucrypto]

First of all, you call your proposal BIP32 but it's actually a mirror of BIP-44 (95% the same). Correct me if I'm wrong but I see no point of copying the full doc here.

You are correct, most of the BIP44 background was included for context and for people unfamiliar with HD wallets.

I see your point when it comes to using primary_asset segment in the derivation path but given that in Stellar each account needs to have a minimum balance of, currently, 20 XLM plus 10 XLM per each subentry I don't think users will want to use this feature, they are more likely to have all their assets in a single account.

I've also come around to this way of thinking .

I couldn't find anything better so at this point I think there is no reliable method for deterministic key derivation for curve25519.

Thanks a lot for this reference, are you aware of any implementations of the key generation scheme in the University of Luxemburg paper?

The main motivation for submitting this proposal was so that the two hardware wallet projects (mine and @lenondupe 's) ensure they generate the same key from the same input. A user should be able to recover their account on a Trezor if they started with a Ledger Nano and vice-versa.

These devices are heavily focused on Bitcoin, so maybe we're taking the wrong approach by trying to force their existing functionality into Stellar. I think what matters from the user's perspective is that if they take the mnemonic they used on their Nano and use it on a Trezor they should get the same Stellar account out.

@bartekn - Do you think it would be a better idea to try to come up with a BIP-39 style way of converting a passphrase to a Stellar private seed and not worry about hierarchical addresses since they're not important to Stellar?

I think that might actually simplify the Trezor implementation and think it sounds like a good idea since no one has come up with a use case for multiple accounts (and several against).

Hi @bartekn

I get the feeling you have not read all the comments following the proposal yet. Some of the points you raise have already been discussed. For more fruitful discussion please take note of some of these previous points.

Correct me if I'm wrong, I'm a novice on this topic, but I think the security concerns you mention involve the public key derivation only. This is possibly the reason Ledger currently disallows public key derivation when using curve25519 like I mentioned earlier.

As it happens, BIP-44 stipulates the usage of public key derivation only for the change and address_index fields, and as previously mentioned these do not seem applicable to Stellar. Hence my proposal to use m / 44' / 148' / x' for deriving Stellar keys and discarding the remaining two fields.

I agree with @zulucrypto that formalising a convention on this topic would be very helpful indeed. If you follow the link @zulucrypto posted to the discussion the Ethereum community was having you will notice a lot of frustration with the mess created by different wallets using slightly different path schemes to derive their keys.

@zulucrypto

Do you think it would be a better idea to try to come up with a BIP-39 style way of converting a passphrase to a Stellar private seed and not worry about hierarchical addresses since they're not important to Stellar?

I wouldn't know how to derive key pair on the Ledger without using a BIP32 path. It seems so integrated in their whole philosophy and OS that I doubt they would even accept an app that tries to do it differently. See for instance this doc on Ledger key derivation.

I think that might actually simplify the Trezor implementation and think it sounds like a good idea since no one has come up with a use case for multiple accounts (and several against).

Well, I for one would certainly like to have multiple accounts at my disposal when using my Ledger, and I suspect a lot more people find that an indispensable requirement.

From my point of view using BIP32 with a subset of BIP44 (m / 44' / 148' / x') is simply the most pragmatic way to go about this. It is the only BIP32 path is formally reserved for Stellar in a proposal that is recognised by the larger crypto community. This gives you two advantages: 1) People will be dealing with a familiar pattern instead of coming across yet another way of doing things. 2) No threat of BIP32 path clashes with other usages.

[bartekn]

Thanks a lot for this reference, are you aware of any implementations of the key generation scheme in the University of Luxemburg paper?

Unfortunately no.

@bartekn - Do you think it would be a better idea to try to come up with a BIP-39 style way of converting a passphrase to a Stellar private seed and not worry about hierarchical addresses since they're not important to Stellar?

I think this will work if you are going to generate a single seed (m/ 44'/148'/0'/0) from the master private key and then use it to derive public key. BIP-32 hd keys would be great to have but these aren't that important in Stellar (IMHO). I wouldn't try to adapt BIP-39 to Stellar. We should use the same method.

I get the feeling you have not read all the comments following the proposal yet.

Actually you are right, sorry. Will check them now.

Correct me if I'm wrong, I'm a novice on this topic, but I think the security concerns you mention involve the public key derivation only. This is possibly the reason Ledger currently disallows public key derivation when using curve25519 like I mentioned earlier.

Yes, you are correct. I just wanted to share what I've learnt so far and what are the limitations.

As it happens, BIP-44 stipulates the usage of public key derivation only for the change and address_index fields, and as previously mentioned these do not seem applicable to Stellar. Hence my proposal to use m / 44' / 148' / x' for deriving Stellar keys and discarding the remaining two fields.

I think we should still follow BIP-44, check my motivation below.

---

What do you think about this (we can write SEP including all of these):

• We strictly follow BIP-39 when it comes to mnemonic code. This generates master private key.
• We strictly follow BIP-44:
  • We generate the main private key using m/ 44'/148'/0'/0/0 path as in BIP-32. To generate a public key you need to curve25519 private -> public key derivation (or simply one of our SDKs). This should be enough for most of the users.
  • If your app supports it, you can generate more private keys using m/ 44'/148'/x'/0/y paths.
  • This way we will be able to achieve all the use cases described in BIP-32 doc when master public key -> child public works for curve25519.
• We should make it clear that master public key -> child public key derivation does not work.

I think this could be a good start and we can always update the doc if there are new developments connected to "BIP-32 for curve25519".

We strictly follow BIP-44:
We generate the main private key using m/ 44'/148'/0'/0/0 path as in BIP-32. To generate a public key you need to curve25519 private -> public key derivation (or simply one of our SDKs). This should be enough for most of the users.

So this currently won't work on Ledger. I probably used the incorrect terminology earlier to convey this. I can't derive a private key using a path that contains non-hardened components. It is currently impossible for me to follow BIP44 exactly if I want the private keys to remain on the device. The best thing I can do is either 44'/148'/0'/0'/0' which do contain change and adress_index but use private derivation for the latter two fields, violating the spec, or forget about the two latter fields altogether, again not conforming to the spec.

[bartekn]

OK, @lenondupe I agree with you. We should use m/44'/148'/x' and m/44'/148'/0' as a main key in Stellar.

Great! It's a good starting point. I think this proposal still enables us to improve upon later without compatibility issues once public-to-public derivation becomes possible and allows support for the more advanced use cases you mentioned.

[zulucrypto]

@bartekn @lenondupe - Thanks a lot for your input, it sounds like we've decided a few things.

Copying from bartekn's comment with some minor changes to reflect later comments:

• generate the main private key using m/ 44'/148'/0' path as in BIP-32. To generate a public key you need to curve25519 private -> public key derivation (or simply one of our SDKs). This should be enough for most of the users.
• If your app supports it, you can generate more private keys using m/ 44'/148'/x' paths (where x is not 0).

We strictly follow BIP-39 when it comes to mnemonic code. This generates master private key.

I like this idea too, any thoughts on whether mnemonic to private key be a separate standard or would you like me to add it to this one? I am slightly leaning towards making it a separate standard since it's a separate BIP and not strictly necessary for how we're using BIP44.

Can you confirm that the Ledger works this way and what keypair is generated given the above mnemonic?

Sorry, I only have one Ledger device and use it to keep my funds so don't want to mess with it.

I think this will impact your Go PR since you'll need to include the hardcoded "Bitcoin seed" string as part of the data you're hashing to arrive at the same master key as the Ledger and Trezor.

The master key derivation from the BIP39 binary seed as described in SLIP-0010 involves a different seed modifier for ed25519 ('ed25519 seed') than is used for secp256k1 ('Bitcoin seed'). According to this thread on reddit Ledger is following SLIP-0010 on this so should be good.

[bartekn]

@zulucrypto the process will be slightly different in terms of key derivation (I finished working on this yesterday: stellar/go#150). Mnemonic -> seed will be exactly the same as in BIP-0039.

[bartekn]

Let's continue the discussion here: #63