Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

NIP 0006 - Multi-Account Hierarchy for Deterministic Wallets #12

Open
evias opened this Issue Apr 6, 2019 · 15 comments

Comments

Projects
None yet
4 participants
@evias
Copy link

commented Apr 6, 2019

NIP-? - Multi-Account Hierarchy for Deterministic Wallets

    NIP: ?
    Layer: Applications
    Title: Multi-Account Hierarchy for Deterministic Wallets
    Author: Grégory Saive <greg@nem.foundation>
    Status: Draft
    Type: Standards Track
    Created: 2019-04-09
    License: BSD-2 Clause

Table of contents

Abstract

This document describes hierarchical deterministic wallets for NEM.

This document uses Bitcoin's BIP32, BIP39, BIP43 and BIP44 as sources of documentation.

A standard for deterministic wallets creation is needed to improve handling of NEM wallets within client applications.

This standard will set the rules for generating extended keys as defined in BIP32, for generating mnemonic pass phrases as defined in BIP39 and for defining a logical hierarchy for deterministic wallets.

Extracts from the Bitcoin documents will be added in quotes and detailed extensions or updates will be annotated for the NEM platform.

Motivation

Previous versions of NEM clients (wallets) used a user password to encrypt private keys, resulting in the need of creating backups every time when a new private key is generated.

Deterministic wallets do not require frequent backups as they will permit the generation of multiple public keys (addresses) without revealing the spending private key, with the use of elliptic curve mathematics.

This multi-account hierarchy will support several chains of keypairs (multiple trees) as to allow selective sharing of wallet public keys.

Additionally, we will be defining Mnemonic code for generating deterministic keys using the definition in Bitcoin BIP39.

Furthermore, using [Bitcoin BIP44], we will define a scheme to build logical hierarchies for deterministic wallets. This will represent the recommended method to work with NEM CATAPULT wallets and keys.

Non-Hardened Child Key Derivation

It has been discussed that non-hardened child key derivation may not fill any required use-case.

Use case #1: Facilitate Audit Process

The non-hardened child key derivation model can be used to facilitate the process of auditing a hierarchical deterministic wallet. By sharing the non-hardened extended public key at the top of the tree in a HD wallet, one can give an auditor the ability to view all addresses in the wallet without the ability to generate the associated private keys.

Reference: https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#audits-nm

Use case #2: Unsecure money receiver

The non-hardened child key derivation model can be used when using unsecure VPS or webservers to run e-commerce websites. In those scenarios, the e-commerce will be configured to derive public keys (addresses) from a non-hardened extended public key as this will make sure that, even if the webserver is ever compromised, there is no chance of losing funds associated with the public keys.

In cases of compromised money receivers, there will however be a loss in privacy as the extended public key allows for the derivation of a whole tree of child keys making it possible for the attacker to associate public keys to the parent key.

Reference: https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#unsecure-money-receiver-nmih0

Resources:

Following are the proposed implementation for BIP32-ED25519 extended keys. The implementation proposal by the Cardano team was defined in a paper that can be found in the resources as well:

Compatibility

Following table describes compatibility of implementation proposal with regards to hardened key derivation and non-hardened key derivaton.

Resource Language Hardened CKD Non-Hardened CKD
IMPL1 rust YES  YES
IMPL2 JS/TS YES NO
IMPL3 rust YES NO

Conclusion

The described use cases make it potentially useful to implement non-hardened child key derivation scheme.

Due to the complexity of implementation and status of the available resources for the ed25519-compatible non-hardended child key derivation implementation, it may be decided to drop support of non-hardened child key derivation as we are aiming for stable, tested and maintained solutions for this NIP to be a success in cross-client interoperability.

Specification

Following section defines the technical specification of the proposed Multi-Account Hierarchy for Deterministic Wallets.

Conversion functions

From the Bitcoin standard, as standard conversion functions, we assume:

  • point(p): returns the coordinate pair resulting from EC point multiplication (repeated application of the EC group operation) of the ED25519 base point with the integer p.
  • ser32(i): serialize a 32-bit unsigned integer i as a 4-byte sequence, most significant byte first.
  • ser256(p): serializes the integer p as a 32-byte sequence, most significant byte first.
  • serP(P): serializes the coordinate pair P = (x,y) as a byte sequence using SEC1's compressed form: (0x02 or 0x03) || ser256(x), where the header byte depends on the parity of the omitted y coordinate.
  • parse256(p): interprets a 32-byte sequence as a 256-bit number, most significant byte first.

Extended keys

The Bitcoin BIP32 document describes extended keys in detail. With the following extracts:

We represent an extended private key as (k, c), with k the normal private key, and c the chain code. An extended public key is represented as (K, c), with K = point(k) and c the chain code.

Each extended key has 2^31 normal child keys, and 2^31 hardened child keys. Each of these child keys has an index. The normal child keys use indices 0 through 2^31-1. The hardened child keys use indices 2^31 through 2^32-1. To ease notation for hardened key indices, a number iH represents i+2^31.

Multiple child key derivation functions (CKDs) are proposed in BIP32 as well, with the following references :

Key trees

In the source document, a key tree is defined that will make use of the CKDs defined above. The child key derivation functions are cascaded several times to build a tree of keys.

Leaf nodes of that tree each define one key (private or public). A detailed explanation of the created key tree can be found here.

Compatibility

From the Bitcoin BIP32 standard document:

To comply with this standard, a client must at least be able to import an extended public or private key, to give access to its direct descendants as wallet keys. The wallet structure (master/account/chain/subchain) presented in the second part of the specification is advisory only, but is suggested as a minimal structure for easy compatibility - even when no separate accounts or distinction between internal and external chains is made. However, implementations may deviate from it for specific needs; more complex applications may call for a more complex tree structure.

Security implications

Security properties of the Extended Keys proposals can be found here.

From the Bitcoin BIP32 description:

Private and public keys must be kept safe as usual. Leaking a private key means access to coins - leaking a public key can mean loss of privacy.

Somewhat more care must be taken regarding extended keys, as these correspond to an entire (sub)tree of keys.

One weakness that may not be immediately obvious, is that knowledge of a parent extended public key plus any non-hardened private key descending from it is equivalent to knowing the parent extended private key (and thus every private and public key descending from it). This means that extended public keys must be treated more carefully than regular public keys. It is also the reason for the existence of hardened keys, and why they are used for the account level in the tree. This way, a leak of account-specific (or below) private key never risks compromising the master or other accounts.

Wallet structure

The previous sections specified key trees and their nodes as defined by the Bitcoin BIP32 source document. Next we are imposing a wallet structure that leverages this tree of keys.

From the Bitcoin BIP32 standard - The default wallet layout:

The layout defined in this section is a default only, though clients are encouraged to mimic it for compatibility, even if not all features are supported.

An hyper deterministic wallet is organized as several accounts. Accounts are numbered, the default account ("") being number 0. Clients are not required to support more than one account - if not, they only use the default account.

Each account is composed of two keypair chains: an internal and an external one. The external keychain is used to generate new public addresses, while the internal keychain is used for all other operations.

We will detail the logical hierarchy more in detail in the section BIP44: A logical hierarchy for deterministic wallets.

Mnemonic seeds

Mnemonic seeds are sentences with words matching a Wordlists as well as holding a checksum as defined in BIP39's Generating the mnemonic.

Mnemonic seeds are created from the available Wordlists in the BIP39 annex.

Following references will be used during reference implementation:

A logical hierarchy with BIP44

Because we want to comply to the BIP44 standard we will define path levels as recommended in BIP44. This gives us the following path levels:

m / purpose' / coin_type' / account' / change' / address_index'

:warning Note the addition of hardened change and address_index path levels. Because Catapult makes use of ed25519 elliptic curve cryptography, deriving non-hardened extended keys is complicated to implement, while for the derivation of hardened extended keys there is already available implementation proposals.

:warning It is currently being examined whether non-hardened derivation is needed at all or not.

  • Our purpose level will be 44' as we are building a logical hierarchy following the BIP44 standard.
  • Our coin_type is 43' as this corresponds to NEM in SLIP-44 annexed to the source document.
  • The next level corresponds to the index of the account that we want to use, starting at 0 for the first account.
  • The change path level is used to define which keychain must be used. Set to 0', the keychain used is said to be external, while any other change path level will result in using the internal keychain.
  • The address_index path level corresponds to the index of the address that we want to use, starting at 0' for the first address.

The appended apostrophe (') in path levels is used to mark hardened key levels. As defined in Bitcoin BIP32 and in this document's Wallet structure, the BIP32 algorithm permits derivation of two entirely independent keyspaces. Those are usually called the hardened key space and the non-hardened key space.

The proposed implementation for Catapult/NEM may be limited to hardened key levels in order to avoid complexity in the implementation for the first implementation proposal.

For NEM, we can define a base logical hierarchy of m/44'/43'. It is recommended for client implementations to follow this standard in order to achieve better cross-client compatibility.

For client implementations which do not wish to implement the full capabilities of multi-account hierarchy for deterministic wallets, it is recommended to use only the following default address path: m/44'/43'/0'/0'/0'.

Examples

Following table displays example derivation paths with their corresponding hierarchy details. The two first path levels, namely the purpose and the coin_type, are always expected to contain 44' and 43' respectively. The next path levels, the third, represents the account number to be derived, and so on.

account keychain address path
first external first m/44'/43'/0'/0'/0'
first external second m/44'/43'/0'/0'/1'
first external third m/44'/43'/0'/0'/2'
first internal first m/44'/43'/0'/1'/0'
first internal second m/44'/43'/0'/1'/1'
first internal third m/44'/43'/0'/1'/2'
second external first m/44'/43'/1'/0'/0'
second external second m/44'/43'/1'/0'/1'
second external third m/44'/43'/1'/0'/2'
second internal first m/44'/43'/1'/1'/0'
second internal second m/44'/43'/1'/1'/1'
second internal third m/44'/43'/1'/1'/2'

Implementation

An implementation proposal has been started with following specification:

The current implementation is open for suggestions. The library is now BIP32-compatible and allows generating hardened-only ED25519 extended keys.

Ongoing Work

Integration

This package should aim at following integration examples:

import {MnemonicPassPhrase, ExtendedKey} from 'nem2-hd-wallets';

const mnemonic = MnemonicPassPhrase.createRandom();
const extended = ExtendedKey.fromSeed(mnemonic.toEntropy());

// derive XPRV and XPUB extended keys
const xprvKey  = extended.getChildPrivateKey(`m/44'/43'/0'/0'/0'`);
const xpubKey  = extended.getChildPublicKey(`m/44'/43'/0'/0'/0'`);

References

History

Date Version
Apr 6 2019 Initial Draft
Apr 18 2019 Second Draft
Apr 23 2019 Third Draft

evias added a commit to evias/NIP that referenced this issue Apr 6, 2019

evias added a commit to evias/nem2-hd-wallets that referenced this issue Apr 8, 2019

@evias

This comment has been minimized.

Copy link
Author

commented Apr 8, 2019

Status Update:

  • Added BIP39 draft implementation based on bitcoinjs/bip39

Blocking:

  • Define whether it is possible to derive a public child key from a public parent key with ED25519 curve.

Alternative:

  • Use only hardened key derivation at keychain level like Nanowallet.

References:

@jontey

This comment has been minimized.

Copy link

commented Apr 9, 2019

Blocking:

Define whether it is possible to derive a public child key from a public parent key.

Quoted from https://github.com/satoshilabs/slips/blob/master/slip-0010.md (Emphasis added)

For ed25519 curve the private keys are no longer multipliers for the group generator; instead the hash of the private key is the multiplier. For this reason, our scheme for ed25519 does not support public key derivation and uses the produced hashes directly as private keys.

So it seems that because of the hash function applied on the private key it is not possible to retrieve the parent keypair from the child keypair

@gimer

This comment has been minimized.

Copy link
Member

commented Apr 9, 2019

Adding info here so it won't get lost:

Looked at nano impl, it basically uses bip32 almost as is to derive some keys, it then treats output as privkey and derives ed25519 pub key from that. This generally does not make much sense, cause it could (and probably even should) be replaced by PBKDF2.

@evias

This comment has been minimized.

Copy link
Author

commented Apr 9, 2019

@jontey this is mentioned in my referenced links yes.

With the Cardano approach, it gets possible to derive a child public from a parent public. I only referenced the SLIP-10 because its first starting point.

@dgarcia360

This comment has been minimized.

Copy link
Collaborator

commented Apr 10, 2019

@evias consider creating a PR to add it as a draft (NIP 6). Once there is an implementation and becomes used, you can propose the NIP to be reviewed by the committee.

@evias

This comment has been minimized.

Copy link
Author

commented Apr 10, 2019

I was waiting for my first draft implementation because we are still awaiting clarity and confirmation on whether implementation for ED25519-BIP32 from cardano can be aplied.

Will post in a PR asap 👍

evias added a commit to evias/nem2-hd-wallets that referenced this issue Apr 10, 2019

evias added a commit to evias/nem2-hd-wallets that referenced this issue Apr 11, 2019

evias added a commit to evias/nem2-hd-wallets that referenced this issue Apr 11, 2019

evias added a commit to evias/nem2-hd-wallets that referenced this issue Apr 11, 2019

evias added a commit to evias/nem2-hd-wallets that referenced this issue Apr 11, 2019

@evias

This comment has been minimized.

Copy link
Author

commented Apr 11, 2019

Status Update for evias/nem2-hd-wallets library (npm package@0.1.0):

  • ExtendedKeyNode on branch master: Creates BIP32 compliant keys (no ED25519 added).
  • MnemonicPassPhrase on master: Creates BIP39 compliant mnemonic pass phrases.
  • MnemonicPassPhrase added toSeed(password) and toEntropy() for BIP32 compatibility.
  • Added Examples usage in README.me (Only supported features)

Todo:

  • Create ED25519-BIP32 algorithm with Cardano ED25519-BIP32 paper
  • Add Wallet class to use ExtendedKeyNode and MnemonicPassPhrase classes.

evias added a commit to evias/nem2-hd-wallets that referenced this issue Apr 11, 2019

@gimer

This comment has been minimized.

Copy link
Member

commented Apr 15, 2019

Can you add a section describing motivation for BIP32 non-hardened keys in nem?

I see usage in bitcoin, due to the way transactions work there (inputs/outputs - which makes it sensible to have derivable pub keys), but I'm not sure if I see value in case of NEM.

That is important part, cause if we decide it's not really needed, we could skip whole cardano approach, and just go with Argon2 key derivation.

@jontey

This comment has been minimized.

Copy link

commented Apr 16, 2019

I don't see the need for non hardened keys. For our use case, it is more useful to have hardened keys to help us identify groups of accounts that belong to us (assets, wallets, etc...) plus being able to obfuscate the total amount of assets we have (to a certain degree).

evias added a commit to evias/nem2-hd-wallets that referenced this issue Apr 18, 2019

evias added a commit to evias/nem2-hd-wallets that referenced this issue Apr 18, 2019

evias added a commit to evias/NIP that referenced this issue Apr 18, 2019

@evias

This comment has been minimized.

Copy link
Author

commented Apr 18, 2019

Updated the above NIP document. Please review @gimer

@gimer

This comment has been minimized.

Copy link
Member

commented Apr 18, 2019

give an auditor the ability to view all addresses in the wallet without the ability to generate the associated private keys. - I know that use case, I've heard it somewhere already, if you think about it, it's senseless.
Any auditor will simply request ALL your public keys.

(moreover, that is hardly a justification to actually HAVE this feature)

The Unsecure money receiver does not explain, why non-hardened keys have to be used.
btw, i'm not sure i understand correctly the description in referenced BIP32 for that case.

@jontey

This comment has been minimized.

Copy link

commented Apr 19, 2019

Any auditor will simply request ALL your public keys.

This doesn't prove that the list of public keys you provided belongs to you. But if you can show that all the public keys are derived in this way, then you just need to show proof that you own the root public key, and by extension the derived public keys also belongs to you.

evias added a commit to evias/nem2-hd-wallets that referenced this issue Apr 20, 2019

evias added a commit to evias/nem2-hd-wallets that referenced this issue Apr 21, 2019

nemtech/NIP#12 : refactored draft implementation for SLIP-20/BIP32 in…
…tegration with ED25519 - ED25519 SLIP-10 unit tests pass
@gimer

This comment has been minimized.

Copy link
Member

commented Apr 23, 2019

This doesn't prove that the list of public keys you provided belongs to you.

ownership of public keys can be easily shown (by signing some predefined message), but even without this, I fail to see a reason, where you would like to give to auditor MORE public keys than you actually own...

@evias

This comment has been minimized.

Copy link
Author

commented Apr 23, 2019

I updated the implementation proposal to be SLIP-10 compliant. That is a hardened-only implementation.

@gimer

This comment has been minimized.

Copy link
Member

commented Apr 23, 2019

Regarding bip-32/SLIP-10 key deriviation: both are using HMAC, to form PRF out of SHA512.

Since we're using sha3 almost everywhere I would suggest switching to KMAC + sha3 for key deriviation. You can find description of KMAC here: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-185.pdf

evias added a commit to evias/NIP that referenced this issue Apr 23, 2019

@dgarcia360 dgarcia360 changed the title Multi-Account Hierarchy for Deterministic Wallets NIP 0006 - Multi-Account Hierarchy for Deterministic Wallets Apr 23, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.