Abstract:

The current derivation method of Hierarchical Deterministic wallets has a weakness in which any individual private key may be combined with any ancestor extended public key (as long as there are no hardened keys in between) to generate the associated extended private key.

This proposal will set out to eliminate this weakness by:

1. Using 1 leak protection of keys
1. Using convention to prevent multiple keys being derived from the same parent.

Motivation:

There is a lot of considerations for security in use cases that would benefit from an extended public key on a server to generate public keys. Currently there are even certain business models that are impossible to use BIP32 due to the weakness.

One example is the service of Reality Keys. The site must generate a yes and no address for every bet that takes place, and reveal the private key to the winning address as a smart contract + oracle based betting service. As they are purposely giving out private keys, they can not use BIP32 via an online Extended public key, as one private key would reveal all private keys for all bets.

Another example are organizations that would want to use HD wallets to give departmentalized extended private keys without having a risk of colluding with a third party auditor with the Extended Public Key that is ancestor to the colluder's key.

In short, the motivation of this proposal is to allow the great feature of Extended Public Keys to be used without worry of the destruction of the whole tree later down the line.

Master generation:

(Note: All HMAC-SHA512 are split into left 32 bytes and right 32 bytes)

a, c1 = HMAC-SHA512(seed)
b, c2 = HMAC-SHA512(concat(a, c1, seed))
chaincode = c1 xor c2

xprv contents: chaincode, a, b

(Deriving index 3)
i3, c1 = HMAC-SHA512(concat(3,chaincode,A))
j3, c2 = HMAC-SHA512(concat(3,chaincode,B))
New chaincode = c1 xor c2
 
a3 = i3 * a
b3 = j3 * b

k3 = a3 + b3

k3 = the derived private key

(  Calculation cost: 2ptmult + 2HMAC + 1xor + 2mult + 3mod + 1add) (for ->pubkey add 1ptmult)
(     Current BIP32: 1ptmult + 1HMAC + 1mod + 1add)
(Extra calculations: 1ptmult + 1HMAC + 1xor + 2mult + 2mod)

xpub contents: chaincode, A, B

(Deriving index 3)
i3, c1 = HMAC-SHA512(concat(3,chaincode,A))
j3, c2 = HMAC-SHA512(concat(3,chaincode,B))
New chaincode = c1 xor c2

A3 = i3 * A
B3 = j3 * B
 
K3 = A3 + B3

K3 = the derived public key

(  Calculation cost: 2ptmult + 2HMAC + 1xor + 1ptadd)
(     Current BIP32: 1ptmult + 1HMAC + 1ptadd)
(Extra calculations: 1ptmult + 1HMAC + 1xor)

Conventions:

All generated keys must end in key code index for last layer (abbreviated as "k")
All nodes generated must have two consecutive last layers as node code index (abbreviated as a single "n"). Nodes MUST end paths with n.
All intermediate layers must not use key or node codes as index
Any path not ending in k or n will be assumed to be a key, and automatically place a k as the extra last layer.
A key can not be the first layer, nor may it immediately follow a node layer. ("k" may not directly follow "m" or "n")

Examples

(Using m/i'/c/k setup from BIP32) m/0/1/0/k == First Account's First Change Key m/0/0/3/k == First Account's Fourth Receiving Key m/4/0/7 == Fifth Account's Eighth Receiving Key (same as m/4/0/7/k)

m/0/n == First Account's Node (Extended Key) m/0/n/2/0/4/k == First Account's Node's Third Account's 5th Receiving Key (Notice how "m" may derive over "n" to generate lower layers)

Note on Depth: Path : m/0/ n /2/0/4/k Depth : 0.1.(2.3).4.5.6.7 "n" represents both the third and fourth depths. The Extended key will contain the depth of 0x03 (The deepest depth of the 2 layers) ("k" will never be represented as an xprv or xpub, but is there for illustrative purposes)

(Notice: 5 byte index instead of 4) key code index = (0x00 || 0xffffffff) node code index = (0x01 || 0xffffffff)

Weakness (but stronger than BIP32):

An attacker could theoretically derive the parent extended private key if he had 2 things:

The xpub extended public key
Any 2 private keys that are child to the xpub

Equations: Known: k0, k1, A, B, chaincode (2 derived keys and the A and B pubkeys + chaincode from their parent xpub)

... i0 = HMAC-SHA512(0,chaincode,A) ... i1 = HMAC-SHA512(1,chaincode,A) ... j0 = HMAC-SHA512(0,chaincode,B) ... j1 = HMAC-SHA512(1,chaincode,B)

now we have: k0, k1, i0, i1, j0, j1, A, B, chaincode

since Bn = jn*B, we can replace it as such: (G is the generator point)

k0G = i0aG + j0bG k1G = i1aG + j1bG

Cross out the generator points to get:

k0 = i0a + j0b k1 = i1a + j1b

Bring a to one side on both to subtract equations:

a = (k0 - j0b)/i0 a = (k1 - j1b)/i1

Bring b to one side:

0 = (k0 - j0b)/i0 - (k1 - j1b)/i1 0 = i1k0 - i1j0b - i0k1 + i0j1b i0k1 - i1k0 = b(i0j1 - i1j0)

b = (i0k1 - i1k0)/(i0j1 - i1j0) mod n

Now we know b, plug in and solve for a:

a = (k0 - j0*b)/i0

Knowing only 1 child privkey you can not solve for parent privkey:

This is because knowing only k0 = i0a + j0b, there are 2 unknowns (a,b) and only 1 equation.

Since convention will require wallets to generate keys alone on their lowest layer (using the key code index) it is impossible for an attacker to retrieve 2 keys from the same parent.

However, a malicious implementation of the method could purposefully generate multiple keys from the same parent in order to break the wallet in the future... but by this point, there are other more conventional attacks they could carry out.

Also, requiring nodes (sub-xpub/xprvs) that are shared to others (ie. departments of a company) to derive two layers of depth using index values that are not allowed for normal key derivation, we further protect the possibility of multiple department heads colluding, as they could not possibly be under the same parent.

benjiqq/NewHDWallet.md