HdWalletNotes.hs

{-# LANGUAGE GADTs              #-}
{-# LANGUAGE StandaloneDeriving #-}

{-# OPTIONS_GHC -Wall -fno-warn-incomplete-patterns #-}

module HdWalletNotes where

{-------------------------------------------------------------------------------
  This module is a simple Haskell model of BIP-32, with a focus on why and
  how hardening works. We start with some types for which we need no further
  assumptions:
-------------------------------------------------------------------------------}

data Bytes
data PubKey
data PrivKey
data Index

{-------------------------------------------------------------------------------
  To study the computations, we define them using a simple embedded value
  language. This language is mostly entirely standard, but we have three
  domain-specific operators:

  * (Keyed) hashing
  * Deriving a public key from a private key
  * Checking whether an index is "hardened"

  Note that for a real implementation, the check whether or not an index is
  hardened is simply a check whether the index is greater than some threshold
  value.
-------------------------------------------------------------------------------}

type VarName = String

data Value a where
  Var  :: String -> Value a
  Err  :: String -> Value a
  If   :: Value Bool -> Value a -> Value a -> Value a
  Pair :: Value a -> Value b -> Value (a, b)
  Fst  :: Value (a, b) -> Value a
  Snd  :: Value (a, b) -> Value b
  Add  :: Value a -> Value a -> Value a
  Sub  :: Value a -> Value a -> Value a

  -- | Keyed-hash
  --
  -- Given a cryptographic key, hash any value. The resulting bytes are split
  -- into two, with the first half interpreted as a private key and the second
  -- half left uninterpreted (will be used as a 'ChainCode').
  HMAC :: Value Bytes -> Value a -> Value (PrivKey, Bytes)

  -- | The public key corresponding to a private key
  --
  -- NOTE: Has the property that
  --
  -- Point (Add x y) == Add (Point x) (Point y)
  Point :: Value PrivKey -> Value PubKey

  -- | Check if an index is hardened
  Hardened :: Value Index -> Value Bool

deriving instance Show (Value a)

{-------------------------------------------------------------------------------
  An extended (private/public) key is the (private/public) key along with a
  "chaincode", effectively just some additional (secret) value.
-------------------------------------------------------------------------------}

type ChainCode  = Bytes
type ExtPrivKey = (PrivKey, ChainCode)
type ExtPubKey  = (PubKey, ChainCode)

{-------------------------------------------------------------------------------
  Child key derivation

  We can now define how child key derivation works. It's actually surprisingly
  simple.
-------------------------------------------------------------------------------}

-- | Private parent key → private child key
--
-- The only difference between the hardened derivation of the non-hardened
-- one is whether we use the private key or the public key of the parent.
ckdPriv :: Value Index -> Value ExtPrivKey -> Value ExtPrivKey
ckdPriv i (Pair kPar cPar) =
    If (Hardened i)
      ( let l = HMAC cPar $ Pair kPar i
        in Pair (kPar `Add` Fst l) (Snd l)
      )
      ( let l = HMAC cPar $ Pair (Point kPar) i
        in Pair (kPar `Add` Fst l) (Snd l)
      )

-- | Public parent key → public child key
--
-- Since for hardened derivation we need the private key of the parent, this
-- function only applies to non-hardened derivation.
ckdPub :: Value Index -> Value ExtPubKey -> Value ExtPubKey
ckdPub i (Pair pkPar cPar) =
    If (Hardened i)
      ( Err "ckdPub: hardened key" )
      ( let l = HMAC cPar $ Pair pkPar i
        in Pair (pkPar `Add` Point (Fst l)) (Snd l)
      )

-- | Compute the extended public key corresponding to an extended private key
neuter :: Value ExtPrivKey -> Value ExtPubKey
neuter (Pair k c) = Pair (Point k) c
neuter (If b x y) = If b (neuter x) (neuter y)

-- | Private parent key → public child key
--
-- First version (works always)
ckdPrivPub1 :: Value Index -> Value ExtPrivKey -> Value ExtPubKey
ckdPrivPub1 i = neuter . ckdPriv i

-- | Private parent key → public child key
--
-- Second version (works only for non-hardened child keys)
ckdPrivPub2 :: Value Index -> Value ExtPrivKey -> Value ExtPubKey
ckdPrivPub2 i = ckdPub i . neuter

-- | The spec mentions that these two derivations are equivalent
--
-- If you study the two terms that this spits out, it becomes clear that this
-- is a consequence of the law
--
-- > Point (Add i j) == Add (Point i) (Point j)
equivalent_ckdPrivPub12 :: (Value ExtPubKey, Value ExtPubKey)
equivalent_ckdPrivPub12 = (ckdPrivPub1 i ekPar, ckdPrivPub2 i ekPar)
  where
    ekPar = Pair (Var "kPar") (Var "cPar")
    i     = Var "i"

{-------------------------------------------------------------------------------
  "Parent key derivation" (the reverse of "child key derivation")
-------------------------------------------------------------------------------}

-- | Derive parent private key from parent master key and derived private key
--
-- This is an "attack", albeit one that is well-known. It shows that we must
-- be very careful with HD wallets. For details, see "Using hardened keys",
-- below.
--
-- NOTE: Since there are only 2^32 indices, not knowing the index doesn't
-- actually provide more security: just trying all of them is feasible.
--
-- NOTE: Mastering Bitcoin says that "Worse, the child private key together with
-- a parent chain code can be used to deduce the parent private key.". I don't
-- know if this is correct. I think we need the parent public key also.
pkdPriv :: Value ExtPubKey   -- ^ Parent extended public key
        -> Value PrivKey     -- ^ Derived private key
        -> Value Index       -- ^ Index
        -> Value ExtPrivKey  -- ^ Uhoh: the parent extended private key
pkdPriv (Pair pkPar cPar) ki i =
    let l = HMAC cPar $ Pair pkPar i
    in Pair (ki `Sub` Fst l) cPar

-- | To show that pkdPriv is inverse, study the term from this function.
--
-- Using the rule
--
-- > x `Add` y `Sub` y == x
--
-- it is clear that this term is equal to the original private key.
--
-- Note that 'pkdPriv' uses the computation for non-hardened keys, and hence
-- we end up this equality only for non-hardened keys. Moreover, for hardened
-- keys 'pkdPriv' would need to know the /private/ parent key.
inverse_pkdPriv :: Value ExtPrivKey
inverse_pkdPriv = pkdPriv (neuter ekPar) (Fst (ckdPriv i ekPar)) i
  where
    ekPar = Pair (Var "kPar") (Var "cPar")
    i     = Var "i"

{-------------------------------------------------------------------------------
  Full HD wallets
-------------------------------------------------------------------------------}

-- | For a full HD wallet, we just repeat this derivation procedure
--
-- Note that hardening can be applied at any given step.
derivePriv :: [Value Index] -> Value ExtPrivKey -> Value ExtPrivKey
derivePriv = foldr (flip (.)) id . map ckdPriv

-- | Like 'derivePriv', but for public keys.
--
-- This will fail if any of the indices are hardened.
derivePub :: [Value Index] -> Value ExtPubKey -> Value ExtPubKey
derivePub = foldr (flip (.)) id . map ckdPub

{-------------------------------------------------------------------------------
  USING HARDENED KEYS

  From an extended private parent key we can derive the @i@th extended private
  child key (A), and similarly from the extended public parent we can derive the
  @i@th extended public key (B).

  >         +=======+  /  +--------+
  >         {       }  /  (        )
  >  /----->{ ekPar }  /  ( epkPar )------\
  >  |      {       }  /  (        )      |
  >  |      +=======+  /  (========)      |
  >  |          |             |           |
  >  |          | (A)         | (B)       | (C)
  >  |          v             v           |
  >  |      +=======+  /  +--------+      |
  >  |      {       }  /  (        )      |
  >  |      {  eki  }  /  (  epki  )      |
  >  |      {       }  /  (        )      |
  >  |      +=======+  /  (========)      |
  >  |          |                         |
  >  |          |                         |
  >  \----------/-------------------------/

  The problem is derivation (C): from the extended public parent key and the
  private derived key (we don't even need the extended private derived key),
  we can derive the parent private key. Thus, we cannot give read-only access
  to the whole wallet and read-write access to part of the wallet.

  The solution is to use hardering, which makes derivation (C) impossible.
  A derivation of a hardened derived key requires the /private/ key of the
  parent. This solves the problem in the following way. We setup keys as
  follows:

  >          +=======+  /  +--------+
  >          {       }  /  (        )
  >          { ekPar }  /  ( epkPar )
  >          {       }  /  (        )
  >          +=======+  /  (========)
  >                     H
  >                     H (R)
  >                     v
  >          +=======+  /  +--------+
  >          {       }  /  (        )
  >   /----->{  eki  }  /  (  epki  )------\
  >   |      {       }  /  (        )      |
  >   |      +=======+  /  (========)      |
  >   |          |             |           |
  >   |          | (A)         | (B)       | (C)
  >   |          v             v           |
  >   |      +=======+  /  +--------+      |
  >   |      {       }  /  (        )      |
  >   |      { eki,j }  /  ( epki,j )      |
  >   |      {       }  /  (        )      |
  >   |      +=======+  /  (========)      |
  >   |          |                         |
  >   |          |                         |
  >   \----------/-------------------------/

  We first derive (R) a hardened key eki ("account") from the master key
  ("root"). Note that it is not possible to public account key from the public
  master key. We then derive a non-hardened key eki,j ("address") from the
  account.  This is a regular derivation, so we /can/ derive (B) the public
  address key from the public account key, and moreover given the public account
  key and a private address key we /can/ derive the private account key (C).
  In other words, we cannot give read-write access to a single address and
  read-only access to the entire account. However, we /can/ give read-only
  access to the entire wallet but read-write access to only one account.

  Note that hardering does /not/ mean we cannot derive further keys from it,
  nor does it provide any protection for itself or any of the keys derived from
  a hardened key. Rather, it provides protection for its /parent/: in the
  diagram above, the hardened derivation (R) provides a protection that no matter
  what we do below the that derivation, we cannot go /up/ past R.

  NOTE: Mastering Bitcoin writes "In simple terms, if you want to use the
  convenience of an extended public key to derive branches of public keys,
  without exposing yourself to the risk of a leaked chain code, you should
  derive it from a hardened parent, rather than a normal parent.". This is
  confusing, because hardering affects the /children/, not the parents. I hope
  the above clarifies it a bit better.
-------------------------------------------------------------------------------}

{-------------------------------------------------------------------------------
  References

  * https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki , especially
    https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#user-content-Security
  * https://bitcoinmagazine.com/articles/deterministic-wallets-advantages-flaw-1385450276/
  * https://www.linkedin.com/pulse/working-bitcoin-hd-wallets-key-derivation-andr%C3%A1s-sevcsik/
  * https://www.linkedin.com/pulse/working-bitcoin-hd-wallets-ii-deriving-public-keys-andr%C3%A1s-sevcsik/
  * https://bitcoin.org/en/developer-guide#hardened-keys
  * https://www.safaribooksonline.com/library/view/mastering-bitcoin/9781491902639/ch04.html ,
    section "Hardened child key derivation" as well as above and below
  * Tangental: https://eprint.iacr.org/2014/998.pdf but makes the remark that
    'This vulnerability was known to the author of the BIP32 standard [13].
     Indeed, BIP32 compensates for this vulnerability by allowing for “hardened”
     child private keys that can be compromised without also compromising the
     master private key. Unfortunately, those hardened keys lack the master
     public key property: their public keys cannot be generated from the master
     public key.'
-------------------------------------------------------------------------------}