HD Key Derivation and its MPC Version
There are two types of child key derivation (CKD) for HD wallets:
Normal derivation: A method of deriving child public keys from a given parent public key. In such public manner, it enables the definition of addresses for different purposes that can be derived automatically by anyone wishing to make the transaction. It also enables the controlled sharing of addresses in an unlimited way. It is possible to give someone an address and have them use normal derivation many times, in order to achieve separation of accounts and the like.
Hardened derivation: A method of deriving child public keys involving parent private key. All keys derived in this method look like independent keys generated randomly. It enables users to back-up a single master secret and then derive as many keys as needed without requiring any further back-up.
BIP-32 and SLIP-10 are two existing protocol standards in the scope. BIP-32 was originally proposed for Bitcoin with ECDSA/secp256k1 only. Later SLIP-10 defines for EdDSA/ed25519 and keeps itself also compatible with ECDSA curve. SLIP-10 only support hardened derivation for EdDSA. To cope with EdDSA normal derivation, Dimitry proposed another spec named BIP32-Ed25519 by tweaking the “after hash” of private key.
Let’s firstly look the BIP-32 CKD functions without MPC, and take curve secp256k1 for example.
Parameters:
k_par: parent private key
c_par: parent chain code
i: address index in HD path
k_i: child private key
c_i: child chain code
K_par: parent public key
K_i: child public key
n: order of curve
Serialisation:
integer: 32-bit unsigned integer to 4 bytes, most significant byte first
Point: compressed form y_parity_byte || Point.x , where y_parity_byte = (0x02 or 0x03)
CKD Functions
Master key generation
Function: master_key(seed) → (k, c)
seed random between 128 and 512 bits
I = HMAC-SHA512(key=”Bitcoin seed”, data = seed)
I_L, I_R = I
if I_L >= n or I_L == 0:
return None
k, c = I_L, I_R
Parent private key -> child private key
Function: priv_2_priv((k_par, c_par), i) -> (k_i, c_i)
• hardened = i >= 2^31
data = Point(k_par) || i, for normal. Note K_par = Point(k_par) is parent public key
data = 0x00 || k_par || i, for hardened. Note parent private key is required for i, which cuts off public path transition
•I = HMAC-SHA512(key=c_par, data)
•I_L, I_R = I
•k_i = I_L + k_par mod n
•c_i = I_R
if I_L >= n or k_i == 0:
return None # Note that SLIP-10 suggests retry here
return (k_i, c_i)
Parent public key -> child public key (normal only)
Function: pub_to_pub((K_par, c_par), i) -> (K_i, c_i)
•data = K_par || i
•I = HMAC-SHA512(key=c_par, data)
•I_L, I_R = I
•K_i = Point(I_L) + K_par
•c_i = I_R
return (K_i, c_i)
Parent private key -> child public key
Function: priv_to_pub((k_par, c_par), i) -> (K_i, c_i)
k_i, c_i = CKDpriv2priv((k_par, c_par), i)
K_i = Point(k_i)
return (K_i, c_i)
Parent public key -> child private key (Not feasible)
MPC Key Derivation
Problem
In MPC scenario, parties can convert their shares of a public key into shares of a child key in terms of BIP-32 key derivation spec. Note that the key derivation requires all parties to collaborate with each other, but not doable in individual way.
Normal derivation can be straightforwardly supported, since deriving a key without including the underlying private key. But hardened derivation would require hashing of the secret key which makes the protocol design challenging since no single party has access to private key.
Hardened Key Derivation using MPC
Now let’s look how these key derivation functions can be distributed by splitting key into key shares. Shamir Secret Sharing (SSS) scheme can be used for key share and combination. SLIP-39 specified an SSS method that splits master key into key shares. But how the parent key can pass thru CKD functions, specifically HMAC-SHA512, and become child key is not trivial.
Existing works including both
Zengo’s MPC 2-party version of key derivation asks each MPC node to perform CKD functions separately, which deviates from the BIP32 standard and becomes incompatible.
Unbound security: BIP-32 key derivation is firstly carried out on parent (key-share, chain-code) for each MPC signer. Security is enhanced with dual execution with garbled circuits. Then all signers run the MPC DKG protocol to get child key share distributed. The resulted key shares are, however, still not compatible.
BIP-32 process without MPC
priv_to_priv(k_par, c_par) → (k_i, c_i)
BIP-32 process without MPC
k_par = x1 + x2 + x3 (implicitly) thru last MPC DKG
c_par = c_x1 + c_x2 + c_x3, MPC DKG
Party 1: priv_to_priv(x1, c_x1) → (y1, c_y1), BIP CKD
Party 2: priv_to_priv(x2, c_x2) → (y2, c_y2), BIP CKD
Party 3: priv_to_priv(x3, c_x3) → (y3, c_y3), BIP CKD
for child level, is there
k_i ?= y1 + y2 + y3
c_i ?= c_y1 + c_y2 + c_y3
If yes, then we say the MPC version is compatible to BIP-32 standard.
References:
HD Wallet. 前言 | by 徐粲邦 | Medium
https://github.com/meherett/python-hdwallet
https://github.com/ebellocchia/bip_utils
nano whitepaper on key derivation: https://docs.nano.org/protocol-design/signing-hashing-and-key-derivation/
AMIS open source HD TSS library:
https://blog.amis.com/amis-open-sources-hierarchical-threshold-signature-scheme-library-alice-7bfa6265cfb8
https://github.com/getamis/alice