Skip to content

Latest commit

 

History

History
97 lines (70 loc) · 5.38 KB

bip32.md

File metadata and controls

97 lines (70 loc) · 5.38 KB
Raw

BIP32 Key Derivation

BIP32 defines a procedure for deriving ec-keypairs from parent keys.

Extended Key

Given an elliptic-curve group $(\mathbb{E}_{(\mathbb{Z_q})}, \circ, O, G, p)$, an extended key is a keypair with following properties:

  • the extended private key is a pair $(a,c) \in \mathbb{Z^2_q}$ where
    • a is the regular private key
    • c is the chain code
  • the extended public key is the pair $(A, c) \in \mathbb{E} \times \mathbb{Z_q}$, where
    • $A = aG$ is the regular public key, and
    • c the chain code.

Each extended key has :

  • $2^{31}$ neutered child keys, and
  • $2^{31}$ hardened child keys.

Each of these child keys has an index:

  • the neutered child keys use indices $[0, \dots, 2^{31}-1]$,
  • the hardened child keys use indices $[2^{31}, \dots, 2^{32}-1]$

To ease notation for hardened key indices, we use the representation $i_H = i+2^{31}$

The definition of bit and byte strings as used here is found in strings expressions.

Hardened Derivation

A hardened derivation is only permitted for $i_{child} \ge 2^{31}$. It uses the parent private key bytes to produce the new random number. The key derivation function $HM_{<(b):512>} \equiv \text{HMAC-SHA512}$ produces a $512$ bit string using the following function:

$$z_{h<(b):512>} = HM_{<(b):512>}(c_{parent<(be:o):32>} || \text{0x00}{<(o):1>} || a{parent<(be:o):32:} || i_{child<(be:o):4>})$$

Where

  • $c_{parent&lt;(be:o):32&gt;}$ is the $32$ octets big endian representation of the parent chain code,
  • $\text{0x00}_{&lt;(o):1&gt;}$ is a one octet padding used to achieve the same input length like neutered key derivation on public keys,
  • $a_{parent&lt;(be:o):32&gt;}$ is the $32$ octet big endian representation of the parent private key, and
  • $i_{child&lt;(be:o):4&gt;}$ is the $4$ octets big endian representation of the child index. Recall $i_{child} \ge 2^{31}$ for hardened derivation.

The resulting bit string $z_{h&lt;(b):512&gt;}$ is divided into two, $z_{hL}$ and $z_{hR}$ such that:

  • $n_{priv:i&lt;(be:o):32&gt;} = z_{hL} = z_{h&lt;(b):512:[:255]&gt;}$ is the child's random number from the parent private key. $z_{h&lt;(b):512:[:255]&gt;}$ selects the first $256$ bits of the string. Those are reorganized into a $32$-octets string in big endian byte order and read as a $32$ bytes integer.
  • $a_{child:i} \equiv n_{priv:i} + a_{parent} \pmod q$, this random number is added to the parent private key to form the child's private key,
  • $c_{child:i&lt;(be:o):32&gt;} = z_{hR} = z_{h&lt;(b):512:[256:]&gt;}$ is the child's chain code
  • $A_{child:i} = a_{child:i}G$, is the child's public key.

Output Validation

In case :

  • $n_{priv:i} \ge q$ or
  • $a_{child:i} \equiv n_{priv:i} + a_{parent} \pmod q \equiv 0$

the resulting key is invalid, and one should proceed with the next value for $i_{child}$. (Note: this has probability lower than $1 \text{ in } 2^{127}$)

Neutered Derivation

A neutered derivation is only permitted for $i_{child} \lt 2^{31}$. It uses the parent public key bytes to produce the new random number. The key derivation function $HM_{&lt;(b):512&gt;}$ produces a $512$ bits string using the following function:

$$z_{n<(b):512>} = HM_{<(b):512>}(c_{parent<(be:o):32>} || A_{parent<(ec:o):33>} || i_{child<(be:o):4>})$$

Where

  • $c_{parent&lt;(be:o):32&gt;}$ is the $32$ octets big endian representation of the parent chain code,
  • $A_{parent&lt;(ec:o):33&gt;}$ is the $33$ octets compressed representation of the parent public key point. This is also known as elliptic curve point encoding (ec), and
  • $i_{child&lt;(be:o):4&gt;}$ is the $4$ octets big endian representation of the child index. Recall $i_{child} \lt 2^{31}$ for neutered derivation.

The resulting bit string $z_{n&lt;(b):512&gt;}$ is split into two, $z_{nL}$ and $z_{nR}$ such that:

  • $n_{pub:i&lt;(be:o):32&gt;} = z_{nL} = z_{n&lt;(b):512:[:255]&gt;}$ is the child's random number from the parent public key. $z_{n&lt;(b):512:[:255]&gt;}$ selects the first $256$ bits of the string. Those are reorganized into a $32$-octet string in big endian byte order and read as a $32$ byte integer.
  • $A_{child:i} = n_{pub:i}G \circ A_{parent}$, is the child's public key. This is a simple point addition as the same random number is added to the parent private key to form the child's private key.
  • $c_{child:i&lt;(be:o):32&gt;} = z_{nR} = z_{n&lt;(b):512:[256:]&gt;}$ is the child's chain code

When this computation is performed by the holder of the parent private key, the child private key can also be computed with

  • $a_{child:i} = n_{pub:i} + a_{parent}$.

This procedure works because:

$$ \begin{aligned} A_{child:i} &= n_{pub:i}G \circ a_{parent}G \\ A_{child:i} &= (n_{pub:i} + a_{parent})G \\ A_{child:i} &= a_{child:i}G \end{aligned} $$

Recall the curve arithmetic allows $(a + b)G \equiv aG \circ bG$

Output Validation

In case :

  • $n_{pub:i} \ge q$ or
  • $A_{child:i} = O$ (Identity element)

the resulting key is invalid, and one should proceed with the next value for $i_{child}$. (Note: this has probability lower than $1 \text{ in } 2^{127}$)

Security Properties

For security properties of BIP32 keys, visit the original proposal at BIP32.

For a more formal analysis of the security of BIP32 keys, visit: The Exact Security of BIP32 Wallets.

Next

Proceed with Threshold signature scheme (TSS) on ECDSA.