About Address Derivation

Overview

This document gives a semi-technical overview of multi-account hierarchy for deterministic wallets, their tradeoffs and limitations.

👍

Current Implementation

Our current default path structure is the following: m / 1852' / 7091' / 0' / 0 / x

If you are interested in understanding more about what the various levels mean, please check out our detailed description here

Hierarchical Deterministic Wallets

Motivation

In Topl, hierarchical deterministic (abbrev. HD) wallets are similar to those described in BIP-0032.

Deterministic wallets and elliptic curve mathematics permit schemes where one can
calculate a wallet public keys without revealing its private keys. This permits for
example a webshop business to let its webserver generate fresh addresses
(public key hashes) for each order or for each customer, without giving the
webserver access to the corresponding private keys (which are required for spending the received funds).

However, deterministic wallets typically consist of a single "chain" of
keypairs. The fact that there is only one chain means that sharing a wallet
happens on an all-or-nothing basis. However, in some cases one only wants some
(public) keys to be shared and recoverable. In the example of a webshop, the
webserver does not need access to all public keys of the merchant's wallet;
only to those addresses which are used to receive customer's payments, and not
for example the change addresses that are generated when the merchant spends
money. Hierarchical deterministic wallets allow such selective sharing by
supporting multiple keypair chains, derived from a single root.

Notation

Conceptually, HD derivation can be seen as a tree with many branches, where keys
live at each node and leaf such that an entire sub-tree can be recovered from
only a parent key (and seemingly, the whole tree can be recovered from the root
master key).

For deriving new keys from parent keys, we use the same approach as defined in
BIP32-Ed25519: Hierarchical Deterministic Keys over a Non-linear
Keyspace
.

We note CKDpriv the derivation of a private child key from a parent private key such that:

CKDprv((kP, cP), i) → (ki, ci)

We note CKDpub the derivation of a public child key from a parent public key such that:

i <  231: CKDpub((AP, cP), i) → (Ai, ci)

📘

Note

This is only possible for so-called "soft" derivation indexes, smaller than 231.

We note N the public key corresponding to a private key such that:

N(k, c) → (A, c) 

To shorten notation, we will borrow the same notation as described in BIP-0032
and write CKDpriv(CKDpriv(CKDpriv(m,3H),2),5) as m/3H/2/5. Equivalently for
public keys, we write CKDpub(CKDpub(CKDpub(M,3),2),5) as M/3/2/5.

Path Levels

Topl hd wallet implementations defines the following path levels:

m / purposeH / coin_typeH / accountH / account_type / address_index
  • purpose is set to 1852
  • coin_type is set to 7091
  • account is set for now to 0
  • account_type is either:
    • 0 to indicate an address on the external chain, that is, an address
      that is meant to be public and communicated to other users.
    • 1 to indicate an address on the internal chain, that is, an address
      that is meant for change, generated by a wallet software.
  • address_index is:
    • Anything between 0 and 231 otherwise

Paths with a tilde ' refer to BIP-0032 hardened derivation path (meaning that
the private key is required to derive children). This leads to a couple of
interesting properties:

  1. New addresses (change or not) can be generated from an account's public key alone.
  2. The derivation of addresses can be done sequentially / deterministically.
  3. If an account private key is compromised, it doesn't compromise other accounts.

This allows for external key-stores and off-loading of key derivation to some
external source such that a wallet could be tracking a set of accounts without
the need for knowing private keys as described in the leading examples at the beginning of this documentation

Master Key Generation

Overview

The master key generation is the mean by which one turns an initial entropy into
a secure cryptographic key. Child keys can be derived from a master key to produce
an HD structure as outlined above. Child key derivation is explored in next sections.

The generation is a function from an initial
seed to an extended private key (abbrev. XPrv) composed of:

  • 64 bytes: an extended Ed25519 secret key composed of:
    • 32 bytes: Ed25519 curve scalar from which few bits have been tweaked (see below)
    • 32 bytes: Ed25519 binary blob used as IV for signing
  • 32 bytes: chain code for allowing secure child key derivation

Additional resources:

Topl master key generation style supports setting an extra password as an arbitrary
byte array of any size. This password acts as a second factor applied to cryptographic key
retrieval. When the seed comes from an encoded recovery phrase, the password can therefore
be used to add extra protection in case the recovery phrase were to be exposed.

Pseudo-code

generateMasterKey(seed, password) {
    data := PBKDF2
        ( kdf=HMAC-SHA512
        , iter=4096
        , salt=seed
        , password=password
        , outputLen=96
        );

    return tweakBits(data);
}

tweakBits(data) {
    // on the ed25519 scalar leftmost 32 bytes:
    // * clear the lowest 3 bits
    // * clear the highest bit
    // * clear the 3rd highest bit
    // * set the highest 2nd bit
    data[0]  &= 0b1111_1000;
    data[31] &= 0b0001_1111;
    data[31] |= 0b0100_0000;
}

Differences between Topl HD Sequential and BIP-44

In BIP-44, new derivation paths are obtained by computing points on an elliptic
curve where curve parameters are defined by secp256k1. Topl's implementation
relies on ed25519 for it provides better properties in terms of security and
performances.

Also, we use purpose = 1852' to clearly distinguish these formats from the original BIP-44 specification.

❗️

Note

Due to the differences between Topl's HD Sequential derivators and the BIP-44 proposal, the Topl HD Sequential derivators are NOT compatible with BIP-44

Because Topl HD Sequential public keys are generated in sequence, there's
no need to maintain a derivation path in the address attributes (incidentally,
this also makes addresses more private). Instead, wallet developers can generate pools of
addresses up to a certain limit (called address gap) for known accounts and
look for those addresses during block application.

Although the idea behind the Topl HD Sequential protocol is to be able to have the wallet
working in a mode where the wallet doesn't know about the private keys, we still
do want to preserve compatibility with the existing address scheme (which can't
work without knowing private keys).

This leaves us with two primary operational modes for a wallet application:

  • Compatibility Mode with private key: In this mode, addresses are derived
    using a private key. There is no HD Sequential derivator involved in the process, rather the address is generated from the private key directly.

  • Deterministic Mode with private key: In
    this mode, the wallet maintain the key hierarchy itself, and leverages a modified BIP-44 strategy
    for application view of the blockchain and account restoration.