14 - Extended Key Derivation using 256-bit Unsigned Integers#

  DIP: 0014
  Title: Extended Key Derivation using 256-bit Unsigned Integers
  Author(s): Samuel Westrich
  Special-Thanks: Dashameter, Eric Britten, Thephez
  Comments-Summary: No comments yet.
  Status: Proposed
  Type: Informational
  Created: 2020-11-25
  License: MIT License

Table of Contents#

  1. Abstract

  2. Motivation

  3. Prior Work

  4. Compatibility

  5. The Dashpay Example

  6. Specification: Key derivation

  7. Test Vectors

  8. Copyright

Abstract#

This Document expands the derivation ability set by BIP32 to allow for derivation on paths using 256-bit unsigned integers.

Motivation#

Derivation paths defined in BIP32 are limited to 31-bit children. The original reasoning seems to be mostly from the use case of BIP32. It seems unattainable to use more than 231 (Over 2 billion) addresses in a wallet. However if we need a unique child in a derivation path, this cannot be achieved with 31-bit children. We need unique children in DashPay derivation paths. Unique children can be defined as 2 random indexes that have less than 2128 chance of being the same. As 256-bit derivation paths might be useful for other applications, we believe the solution presented within merits its own document.

Prior work#

Compatibility#

One fundamental aspect of this document is backwards compatibility with BIP32 derivation. If a child key’s index is less than 232-1 then the resultant child key created by the derivation outlined in this document will match the derivation outlined in BIP32.

The Dashpay Example#

Derivation in BIP32 is limited to 31 bits (the 32nd bit is used to mark hardening). If we limited ourselves to 31-bit derivations we would be faced with the following problem: we need the derivation path between user A and user B to be unique and be made in such a way that a user C could never create an attack to have the same address space as given to B from A.

To illustrate the attack let’s assume we used only 31-bit derivation. Since user A and user B’s unique id is public, any form that reduces the entropy of this relationship to 31 bits per child would be attackable. For example, if we used the last 31 bits of the unique id for each user to make the tail of the derivation path then user C could cycle through ~231 Blockchain Identities and eventually find one that would match. This would easily be achievable with an ASIC miner. User C would then receive the same extended public key as user B and therefore be able to know when payments were made from User B to user A. More complicated schemes also suffer the same problem as User C could replicate any known function to create the same 31 bits.

To solve this we allow derivation of paths on 256-bit unsigned integers matching the Identity’s registration hash.

The derivation path for Dashpay relationships is discussed more in depth in the DashPay Implementation Proposal. Here we will focus on the last two 256-bit derivations. The derivation path will look like:

m(userA)/9’/5’/15’/0’/(userA’s unique id)/(userB’s unique id)

Deconstructed that is :

  • 9 hardened / See DIP9

  • 5 hardened / Coin type

  • 15 hardened / Feature

  • 0 hardened / Account

  • userA’s unique id (not hardened)

  • userB’s unique id (not hardened)

Making the last two fields non-hardened allows for an extended public key that covers all address spaces of all our contacts for all our blockchain identities. This can be used for accounting and also to create the friend requests without having to use a private key.

Specification: Key derivation#

We will modify the following to the original specification as described in BIP32.

Conventions#

As standard conversion functions, we assume:

  • ser256(i): serialize a 256-bit unsigned integer i as a 32-byte sequence, most significant byte first.

Extended Keys#

In the original BIP32 specification, each extended key had 231 normal child keys and 231 hardened child keys. We extend that specification to now allow 2256 normal child keys and 2256 hardened child keys. Each of these child keys has an index. In the original specification, a key was hardened if the most significant bit of the index was set. Instead we now use a Boolean h to represent if a child key is hardened. Hence now both normal child keys and hardened keys will use indices 0 through 2256-1.

Child Key Derivation (CKD) Functions#

Given a parent extended key and an index i, it is possible to compute the corresponding child extended key. The algorithm to do so depends on whether the child is a hardened key or not, if the index is less or more than 231, and whether we’re talking about private or public keys.

Private parent key → private child key#

The function CKDpriv256((kpar, cpar), i, h) → (ki, ci) computes a child extended private key from the parent extended private key:

  • Check whether i < 232 (whether we should use compatibility mode) and check if h is true (whether the child is a hardened key).

    • If (i< 232) :

      • If hardened child (h==true): let I = HMAC-SHA512(Key = cpar, Data = 0x00 || ser256(kpar) || ser32(i)). (Note: The 0x00 pads the private key to make it 33 bytes long.)

      • If normal child: let I = HMAC-SHA512(Key = cpar, Data = serP(point(kpar)) || ser32(i)).

    • If (i>=232) :

      • If hardened child (h==true): let I = HMAC-SHA512(Key = cpar, Data = 0x00 || ser256(kpar) || ser256(i)). (Note: The 0x00 pads the private key to make it 33 bytes long.)

      • If normal child: let I = HMAC-SHA512(Key = cpar, Data = serP(point(kpar)) || ser256(i)).

  • Split I into two 32-byte sequences, IL and IR.

  • The returned child key ki is parse256(IL) + kpar (mod n).

  • The returned chain code ci is IR.

  • In case parse256(IL) ≥ n or ki = 0, the resulting key is invalid, and one should proceed with the next value for i. (Note: this has a probability lower than 1 in 2127.)

The HMAC-SHA512 function is specified in RFC 4231.

Public parent key → public child key#

The function CKDpub256((Kpar, cpar), i, h) → (Ki, ci) computes a child extended public key from the parent extended public key. It is only defined for non-hardened child keys.

  • Check if h is true, if it is then return failure.

  • Check whether i < 232 (whether we should use compatibility mode).

    • If it is (compatibility mode): let I = HMAC-SHA512(Key = cpar, Data = serP(Kpar) || ser32(i)).

    • If not (UInt256 mode): let I = HMAC-SHA512(Key = cpar, Data = serp(Kpar) || ser256(i)).

  • Split I into two 32-byte sequences, IL and IR.

  • The returned child key Ki is point(parse256(IL)) + Kpar.

  • The returned chain code ci is IR.

  • In case parse256(IL) ≥ n or Ki is the point at infinity, the resulting key is invalid, and one should proceed with the next value for i.

Serialization Format#

Extended public and private keys are serialized as follows:

If (child number < 232) follow serialization format as described in BIP32 :

  • 4 byte: version bytes (mainnet: 0x0488B21E public, 0x0488ADE4 private; testnet: 0x043587CF public, 0x04358394 private)

  • 1 byte: depth: 0x00 for master nodes, 0x01 for level-1 derived keys, ….

  • 4 bytes: the fingerprint of the parent’s key (0x00000000 if master key)

  • 4 bytes: child number. This is ser32(i) for i in xi = xpar/i, with xi the key being serialized. (0x00000000 if master key)

  • 32 bytes: the chain code

  • 33 bytes: the public key or private key data (serP(K) for public keys, 0x00 || ser256(k) for private keys)

Because of the choice of the version bytes, the Base58 representation will start with xprv or xpub on mainnet, tprv or tpub on testnet.

If (child number >= 232) then serialize the following way :

  • 4 byte: version bytes (mainnet: 0X0EECEFC5 public, 0x0EECF02E private; testnet: 0x0EED270B public, 0x0EED2774 private)

  • 1 byte: depth: 0x00 for master nodes, 0x01 for level-1 derived keys, ….

  • 4 bytes: the fingerprint of the parent’s key (0x00000000 if master key)

  • 1 byte: hardening: 0x00 if not hardened, 0x01 if hardened

  • 32 bytes: child number. This is ser256(i) for i in xi = xpar/i, with xi the key being serialized. (Only zeros if master key)

  • 32 bytes: the chain code

  • 33 bytes: the public key or private key data (serP(K) for public keys, 0x00 || ser256(k) for private keys)

Because of the choice of the version bytes, the Base58 representation will start with dpms (dashpay mainnet secret) or dpmp (dashpay mainnet public) on mainnet, dpts (dashpay testnet secret) or dptp (dashpay testnet public) on testnet or devnets.

Test Vectors#

Test Vector 1#

Mnemonic : birth kingdom trash renew flavor utility donkey gasp regular alert pave layer

Seed Data : b16d3782e714da7c55a397d5f19104cfed7ffa8036ac514509bbb50807f8ac598eeb26f0797bd8cc221a6cbff2168d90a5e9ee025a5bd977977b9eccd97894bb

Key Type : Secp256k1

Derivation (Note : The second derivation is hardened) :

m/
0x775d3854c910b7dee436869c4724bed2fe0784e198b8a39f02bbb49d8ebcfc3b/
0xf537439f36d04a15474ff7423e4b904a14373fafb37a41db74c84f1dbb5c89a6'/
0x4c4592ca670c983fc43397dfd21a6f427fac9b4ac53cb4dcdc6522ec51e81e79/
0

  • Key : 0xe8781fdef72862968cd9a4d2df34edaf9dcc5b17629ec505f0d2d1a8ed6f9f09

  • Ext Pub : tpubDF4tEyAdpXySRui9CvGRTSQU4BgLwGxuLPKEb9WqEE93raF2ffU1PRQ6oJHCgZ7dArzcMj9iKG8s8EFA1DdwgzWAXs61uFuRE1bQi8kAmLy

  • Ext Priv : tprv8iNr6Z8PgAHmYSgMKGbq42kMVAAQmwmzm5iTJdUXoxLf25zG3GeRCvnEdC6HKTHkU59nZkfjvcGk9VW2YHsFQMwsZrQLyNrGx9c37kgb368

Test Vector 2#

Mnemonic : birth kingdom trash renew flavor utility donkey gasp regular alert pave layer

Seed Data : b16d3782e714da7c55a397d5f19104cfed7ffa8036ac514509bbb50807f8ac598eeb26f0797bd8cc221a6cbff2168d90a5e9ee025a5bd977977b9eccd97894bb

Key Type : Secp256k1

Derivation (Note : All derivations except the last are hardened) :

m/9'/5'/15'/0'/
0x555d3854c910b7dee436869c4724bed2fe0784e198b8a39f02bbb49d8ebcfc3a'/
0xa137439f36d04a15474ff7423e4b904a14373fafb37a41db74c84f1dbb5c89b5'/
0

  • Key : 0xfac40790776d171ee1db90899b5eb2df2f7d2aaf35ad56f07ffb8ed2c57f8e60

  • Ext Pub : tpubDLqNye58JQGox9dqWN5xZUgC5XGC6KwWmTSX6qGugrGEa5QffDm3iDfsVtX7qyXuWoQsXA6YCSuckKshyjnwiGGoYWHonAv2X98HTU613UH

  • Ext Priv : tprv8p9LqE2tA2b94gc3ciRNA525WVkFvzkcC9qjpKEcGaTqjb9u2pwTXj41KkZTj3c1a6fJUpyXRfcB4dimsYsLMjQjsTJwi5Ukx6tJ5BpmYpx

Test Vector 3#

Mnemonic : birth kingdom trash renew flavor utility donkey gasp regular alert pave layer

Seed Data : b16d3782e714da7c55a397d5f19104cfed7ffa8036ac514509bbb50807f8ac598eeb26f0797bd8cc221a6cbff2168d90a5e9ee025a5bd977977b9eccd97894bb

Key Type : Secp256k1

Derivation (Note : The derivation is NOT hardened) :

m/
0x775d3854c910b7dee436869c4724bed2fe0784e198b8a39f02bbb49d8ebcfc3b

  • Key : 0xf6a95ae75ea8362d9478932f71b262b3d981918fe030316686a475dea4889938

  • Ext Pub : dptp1C5gGd8NzvAke5WNKyRfpDRyvV2UZ3jjrZVZU77qk9yZemMGSdZpkWp7y6wt3FzvFxAHSW8VMCaC1p6Ny5EqWuRm2sjvZLUUFMMwXhmW6eS69qjX958RYBH5R8bUCGZkCfUyQ8UVWcx9katkrRr

  • Ext Priv : dpts1vgMVEs9mmv1YLwURCeoTn9CFMZ8JMVhyZuxQSKttNSETR3zydMFHMKTTNDQPf6nnupCCtcNnSu3nKZXAJhaguyoJWD4Ju5PE6PSkBqAKWci7HLz37qmFmZZU6GMkLvNLtST2iV8NmqqbX37c45

Test Vector 4#

Mnemonic : birth kingdom trash renew flavor utility donkey gasp regular alert pave layer

Seed Data : b16d3782e714da7c55a397d5f19104cfed7ffa8036ac514509bbb50807f8ac598eeb26f0797bd8cc221a6cbff2168d90a5e9ee025a5bd977977b9eccd97894bb

Key Type : Secp256k1

Derivation (Note : The second derivation is hardened) :

m/
0x775d3854c910b7dee436869c4724bed2fe0784e198b8a39f02bbb49d8ebcfc3b/
0xf537439f36d04a15474ff7423e4b904a14373fafb37a41db74c84f1dbb5c89a6'

  • Key : b898ad92d3a0698bc3117d3777d82676673816ce52f4fc2f1263a2f676825f90

  • Ext Pub : dptp1CLkexeadp6guoi8Fbiwq6CLZm3hT1DJLwHsxWvwYSeAhjenFhcQ9HumZSftfZEr4dyQjFD7gkM5bSn6Aj7F1Jve8KTn4JsMEaj9dFyJkYs4Ga5HSUqeajxGVmzaY1pEioDmvUtZL3J1NCDCmzQ

  • Ext Priv : dpts1vwRsaPMQfqwp59ELpx5UeuYtdaMCJyGTwiGtr8zgf6qWPMWnhPpg8R73hwR1xLibbdKVdh17zfwMxFEMxZzBKUgPwvuosUGDKW4ayZjs3AQB9EGRcVpDoFT8V6nkcc6KzksmZxvmDcd3MqiPEu