WARNING: Current proposal does not protect against colluding of a single ancestor public node and a single descendant private node. This is still a WIP.
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:
- Using 1 leak protection of keys
- Using convention to prevent multiple keys being derived from the same parent.
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.
(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
Deriving from Private Node (Extended Private Key): (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 x3 = i3 * a y3 = j3 * b p3 = x3 + y3 a3 = x3 + p3 b3 = y3 + p3 k3 = a3 + b3 k3 = the derived private key
Cost Increases deriving from Private Node
- Proposed Calculation cost: 2 EC Multiplication + 2 HMAC-SHA512 + 1 XOR + 2 BIGINT Multiplication + 6 BIGINT MOD + 4 BIGINT Addition
- For Parent privkey to Child pubkey add 1 EC Multiplication)
- Current BIP32 cost: 1 EC Multiplication + 1 HMAC-SHA512 + 1 BIGINT MOD + 1 BIGINT Addition
- Extra calculations: 1 EC Multiplication + 1 HMAC-SHA512 + 1 XOR + 2 BIGINT Multiplication + 5 BIGINT MOD + 3 BIGINT Addition
Deriving from Public Node (Extended Public Key): (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 X3 = i3 * A Y3 = j3 * B P3 = X3 + Y3 A3 = X3 + P3 B3 = Y3 + P3 K3 = A3 + B3 K3 = the derived public key
Cost Increases deriving from Public Node
- Proposed Calculation cost: 2 EC Multiplication + 2 HMAC-SHA512 + 1 XOR + 4 EC Addition
- Current BIP32 cost: 1 EC Multiplication + 1 HMAC-SHA512 + 1 EC Addition
- Extra calculations: 1 EC Multiplication + 1 HMAC-SHA512 + 1 XOR + 3 EC Addition
- 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")
Key and Node index values
(Notice: 5 byte index instead of 4)
key code index = (0x00 || 0xffffffff) node code index = (0x01 || 0xffffffff)
New Master/Node format (xprv/xpub)
- Only difference from BIP32 is adding 33 bytes after public/private key bytes to accommodate for both a/A and b/B.
- Private node will have 1
0x00padding byte for each key (a and b) to preserve the byte length of the node.
- Magic numbers will change to
0xc88efabafor private ("xprv") and
0xc88fb5c4for public ("xpub") masters/nodes.
- Nodes' child numbers shall contain the index of the last non-node layer. So the node
m/2/nwill be index
- Parent fingerprint will be the first 4 bytes of the pubkey hash of the parent's compressed "key" (Which is the point obtained from the EC addition of the two pubkeys within the parent)
m/i'/c/k setup from BIP32)
|Key Paths||Key Explanation|
||First Account's First Change Key|
||First Account's Fourth Receiving Key|
||Fifth Account's Eighth Receiving Key (same as
|Key Paths||Key Explanation|
||First Account's Node (Extended Key)|
||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/... Depth : 0.1.(2.3).4.5....
- "n" represents both the third and fourth depths.
- The Extended key will contain the depth of 0x03 (The deepest depth of the 2 layers)
Considerations for derivation standards
One consideration that must be made is that any derived key path can only have as many Public nodes that can derive it as the number of "n" node layers above it + 1 (for the master node "m")
Example: A key such as the following BIP44 key would need to be altered to follow the functionality sought out in BIP44
|BIP44 path||New HD path|
|The logic behind this conversion is asking the question "which layer would need a node in the future?" to which the only one would be the "Account" layer. However, This may be made obsolete by the fact that releasing M (Master Public Node) would not compromise any private keys, but would be useful for use cases such as "I will give you one of the Account Public Nodes of my chain and you can make payments to those addresses incrementally." where you don't want to give the other party access to your whole wallet's public keys.|
"Two Leaked Keys" Weakness
(Stronger than BIP32, which is completely broken with one leaked key)
An attacker could theoretically derive the parent Private Node (extended private key) if he had 2 things:
- The associated Public Node (extended public key)
- Any 2 private keys that are child to the Public Node
(Note: This attack does not work with a grandparent Public Node and 2 grandchildren private keys)
k0, k1, A, B, chaincode
(2 derived keys and the A and B pubkeys + chaincode from their parent Public Node)
... i0 = HMAC-SHA512(0,chaincode,A) ... i1 = HMAC-SHA512(1,chaincode,A) ... j0 = HMAC-SHA512(0,chaincode,B) ... j1 = HMAC-SHA512(1,chaincode,B)
And now we have:
k0, k1, i0, i1, j0, j1, A, B, chaincode
Bn = 2*jn*B + in*A, we can replace it as such:
(G is the generator point) k0*G = 3*i0*a*G + 3*j0*b*G k1*G = 3*i1*a*G + 3*j1*b*G
- Cross out the generator points to get:
k0 = 3*i0*a + 3*j0*b k1 = 3*i1*a + 3*j1*b
- Bring a to one side on both to subtract equations:
a = (k0 - 3*j0*b)/(3*i0) a = (k1 - 3*j1*b)/(3*i1)
- Bring b to one side:
0 = (k0 - 3*j0*b)/(3*i0) - (k1 - 3*j1*b)/(3*i1) 0 = 3*i1*k0 - 3*i1*j0*b - 3*i0*k1 + 3*i0*j1*b 3*i0*k1 - 3*i1*k0 = b(3*i0*j1 - 3*i1*j0) b = (3*i0*k1 - 3*i1*k0)/(3*i0*j1 - 3*i1*j0) mod n
- Now we know b, plug in and solve for a:
a = (k0 - 3*j0*b)/(3*i0)
Knowing only 1 child privkey you can not solve for parent privkey
This is because knowing only
k0 = i0*a + j0*b, 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 (descendant 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.
I have yet to make a UI for it, but I have modified bip32.js from my website to accommodate these new rules. Here is the diff. https://github.com/dabura667/NewBIP32js/compare/oldbip32...newbip32