Merge pull request #2829 from sipa/bip32

BIP 32 derivation + test vectors

9 files changed, 585 insertions, 36 deletions

diff --git a/src/base58.h b/src/base58.h
index 630d6fe9aa..aabae8de88 100644
--- a/src/base58.h
+++ b/src/base58.h
@@ -177,8 +177,8 @@ inline bool DecodeBase58Check(const std::string& str, std::vector<unsigned char>
 class CBase58Data
 {
 protected:
-    // the version byte
-    unsigned char nVersion;
+    // the version byte(s)
+    std::vector<unsigned char> vchVersion;
 
     // the actually encoded data
     typedef std::vector<unsigned char, zero_after_free_allocator<unsigned char> > vector_uchar;
@@ -186,38 +186,38 @@ protected:
 
     CBase58Data()
     {
-        nVersion = 0;
+        vchVersion.clear();
         vchData.clear();
     }
 
-    void SetData(int nVersionIn, const void* pdata, size_t nSize)
+    void SetData(const std::vector<unsigned char> &vchVersionIn, const void* pdata, size_t nSize)
     {
-        nVersion = nVersionIn;
+        vchVersion = vchVersionIn;
         vchData.resize(nSize);
         if (!vchData.empty())
             memcpy(&vchData[0], pdata, nSize);
     }
 
-    void SetData(int nVersionIn, const unsigned char *pbegin, const unsigned char *pend)
+    void SetData(const std::vector<unsigned char> &vchVersionIn, const unsigned char *pbegin, const unsigned char *pend)
     {
-        SetData(nVersionIn, (void*)pbegin, pend - pbegin);
+        SetData(vchVersionIn, (void*)pbegin, pend - pbegin);
     }
 
 public:
-    bool SetString(const char* psz)
+    bool SetString(const char* psz, unsigned int nVersionBytes = 1)
     {
         std::vector<unsigned char> vchTemp;
         DecodeBase58Check(psz, vchTemp);
-        if (vchTemp.empty())
+        if (vchTemp.size() < nVersionBytes)
         {
             vchData.clear();
-            nVersion = 0;
+            vchVersion.clear();
             return false;
         }
-        nVersion = vchTemp[0];
-        vchData.resize(vchTemp.size() - 1);
+        vchVersion.assign(vchTemp.begin(), vchTemp.begin() + nVersionBytes);
+        vchData.resize(vchTemp.size() - nVersionBytes);
         if (!vchData.empty())
-            memcpy(&vchData[0], &vchTemp[1], vchData.size());
+            memcpy(&vchData[0], &vchTemp[nVersionBytes], vchData.size());
         OPENSSL_cleanse(&vchTemp[0], vchData.size());
         return true;
     }
@@ -229,15 +229,15 @@ public:
 
     std::string ToString() const
     {
-        std::vector<unsigned char> vch(1, nVersion);
+        std::vector<unsigned char> vch = vchVersion;
         vch.insert(vch.end(), vchData.begin(), vchData.end());
         return EncodeBase58Check(vch);
     }
 
     int CompareTo(const CBase58Data& b58) const
     {
-        if (nVersion < b58.nVersion) return -1;
-        if (nVersion > b58.nVersion) return  1;
+        if (vchVersion < b58.vchVersion) return -1;
+        if (vchVersion > b58.vchVersion) return  1;
         if (vchData < b58.vchData)   return -1;
         if (vchData > b58.vchData)   return  1;
         return 0;
@@ -289,8 +289,8 @@ public:
     bool IsValid() const
     {
         bool fCorrectSize = vchData.size() == 20;
-        bool fKnownVersion = nVersion == Params().Base58Prefix(CChainParams::PUBKEY_ADDRESS) ||
-                             nVersion == Params().Base58Prefix(CChainParams::SCRIPT_ADDRESS);
+        bool fKnownVersion = vchVersion == Params().Base58Prefix(CChainParams::PUBKEY_ADDRESS) ||
+                             vchVersion == Params().Base58Prefix(CChainParams::SCRIPT_ADDRESS);
         return fCorrectSize && fKnownVersion;
     }
 
@@ -318,16 +318,16 @@ public:
             return CNoDestination();
         uint160 id;
         memcpy(&id, &vchData[0], 20);
-        if (nVersion == Params().Base58Prefix(CChainParams::PUBKEY_ADDRESS))
+        if (vchVersion == Params().Base58Prefix(CChainParams::PUBKEY_ADDRESS))
             return CKeyID(id);
-        else if (nVersion == Params().Base58Prefix(CChainParams::SCRIPT_ADDRESS))
+        else if (vchVersion == Params().Base58Prefix(CChainParams::SCRIPT_ADDRESS))
             return CScriptID(id);
         else
             return CNoDestination();
     }
 
     bool GetKeyID(CKeyID &keyID) const {
-        if (!IsValid() || nVersion != Params().Base58Prefix(CChainParams::PUBKEY_ADDRESS))
+        if (!IsValid() || vchVersion != Params().Base58Prefix(CChainParams::PUBKEY_ADDRESS))
             return false;
         uint160 id;
         memcpy(&id, &vchData[0], 20);
@@ -336,7 +336,7 @@ public:
     }
 
     bool IsScript() const {
-        return IsValid() && nVersion == Params().Base58Prefix(CChainParams::SCRIPT_ADDRESS);
+        return IsValid() && vchVersion == Params().Base58Prefix(CChainParams::SCRIPT_ADDRESS);
     }
 };
 
@@ -366,7 +366,7 @@ public:
     bool IsValid() const
     {
         bool fExpectedFormat = vchData.size() == 32 || (vchData.size() == 33 && vchData[32] == 1);
-        bool fCorrectVersion = nVersion == Params().Base58Prefix(CChainParams::SECRET_KEY);
+        bool fCorrectVersion = vchVersion == Params().Base58Prefix(CChainParams::SECRET_KEY);
         return fExpectedFormat && fCorrectVersion;
     }
 
@@ -390,4 +390,30 @@ public:
     }
 };
 
+
+template<typename K, int Size, CChainParams::Base58Type Type> class CBitcoinExtKeyBase : public CBase58Data
+{
+public:
+    void SetKey(const K &key) {
+        unsigned char vch[Size];
+        key.Encode(vch);
+        SetData(Params().Base58Prefix(Type), vch, vch+Size);
+    }
+
+    K GetKey() {
+        K ret;
+        ret.Decode(&vchData[0], &vchData[Size]);
+        return ret;
+    }
+
+    CBitcoinExtKeyBase(const K &key) {
+        SetKey(key);
+    }
+
+    CBitcoinExtKeyBase() {}
+};
+
+typedef CBitcoinExtKeyBase<CExtKey, 74, CChainParams::EXT_SECRET_KEY> CBitcoinExtKey;
+typedef CBitcoinExtKeyBase<CExtPubKey, 74, CChainParams::EXT_PUBLIC_KEY> CBitcoinExtPubKey;
+
 #endif // BITCOIN_BASE58_H
diff --git a/src/chainparams.cpp b/src/chainparams.cpp
index 6b83624040..0795f09765 100644
--- a/src/chainparams.cpp
+++ b/src/chainparams.cpp
@@ -10,6 +10,10 @@
 #include "protocol.h"
 #include "util.h"
 
+#include <boost/assign/list_of.hpp>
+
+using namespace boost::assign;
+
 //
 // Main network
 //
@@ -141,9 +145,11 @@ public:
         vSeeds.push_back(CDNSSeedData("dashjr.org", "dnsseed.bitcoin.dashjr.org"));
         vSeeds.push_back(CDNSSeedData("xf2.org", "bitseed.xf2.org"));
 
-        base58Prefixes[PUBKEY_ADDRESS] = 0;
-        base58Prefixes[SCRIPT_ADDRESS] = 5;
-        base58Prefixes[SECRET_KEY] = 128;
+        base58Prefixes[PUBKEY_ADDRESS] = list_of(0);
+        base58Prefixes[SCRIPT_ADDRESS] = list_of(5);
+        base58Prefixes[SECRET_KEY] =     list_of(128);
+        base58Prefixes[EXT_PUBLIC_KEY] = list_of(0x04)(0x88)(0xB2)(0x1E);
+        base58Prefixes[EXT_SECRET_KEY] = list_of(0x04)(0x88)(0xAD)(0xE4);
 
         // Convert the pnSeeds array into usable address objects.
         for (unsigned int i = 0; i < ARRAYLEN(pnSeed); i++)
@@ -203,10 +209,11 @@ public:
         vSeeds.push_back(CDNSSeedData("bitcoin.petertodd.org", "testnet-seed.bitcoin.petertodd.org"));
         vSeeds.push_back(CDNSSeedData("bluematt.me", "testnet-seed.bluematt.me"));
 
-        base58Prefixes[PUBKEY_ADDRESS] = 111;
-        base58Prefixes[SCRIPT_ADDRESS] = 196;
-        base58Prefixes[SECRET_KEY] = 239;
-
+        base58Prefixes[PUBKEY_ADDRESS] = list_of(111);
+        base58Prefixes[SCRIPT_ADDRESS] = list_of(196);
+        base58Prefixes[SECRET_KEY]     = list_of(239);
+        base58Prefixes[EXT_PUBLIC_KEY] = list_of(0x04)(0x35)(0x87)(0xCF);
+        base58Prefixes[EXT_SECRET_KEY] = list_of(0x04)(0x35)(0x83)(0x94);
     }
     virtual Network NetworkID() const { return CChainParams::TESTNET; }
 };
@@ -234,10 +241,6 @@ public:
         assert(hashGenesisBlock == uint256("0x0f9188f13cb7b2c71f2a335e3a4fc328bf5beb436012afca590b1a11466e2206"));
 
         vSeeds.clear();  // Regtest mode doesn't have any DNS seeds.
-
-        base58Prefixes[PUBKEY_ADDRESS] = 0;
-        base58Prefixes[SCRIPT_ADDRESS] = 5;
-        base58Prefixes[SECRET_KEY] = 128;
     }
 
     virtual bool RequireRPCPassword() const { return false; }
diff --git a/src/chainparams.h b/src/chainparams.h
index 572712b589..1930e49afb 100644
--- a/src/chainparams.h
+++ b/src/chainparams.h
@@ -45,6 +45,8 @@ public:
         PUBKEY_ADDRESS,
         SCRIPT_ADDRESS,
         SECRET_KEY,
+        EXT_PUBLIC_KEY,
+        EXT_SECRET_KEY,
 
         MAX_BASE58_TYPES
     };
@@ -60,7 +62,7 @@ public:
     const string& DataDir() const { return strDataDir; }
     virtual Network NetworkID() const = 0;
     const vector<CDNSSeedData>& DNSSeeds() const { return vSeeds; }
-    int Base58Prefix(Base58Type type) const { return base58Prefixes[type]; }
+    const std::vector<unsigned char> &Base58Prefix(Base58Type type) const { return base58Prefixes[type]; }
     virtual const vector<CAddress>& FixedSeeds() const = 0;
     int RPCPort() const { return nRPCPort; }
 protected:
@@ -76,7 +78,7 @@ protected:
     int nSubsidyHalvingInterval;
     string strDataDir;
     vector<CDNSSeedData> vSeeds;
-    int base58Prefixes[MAX_BASE58_TYPES];
+    std::vector<unsigned char> base58Prefixes[MAX_BASE58_TYPES];
 };
 
 /**
diff --git a/src/hash.cpp b/src/hash.cpp
index bddd8abf38..7b054bd154 100644
--- a/src/hash.cpp
+++ b/src/hash.cpp
@@ -56,3 +56,44 @@ unsigned int MurmurHash3(unsigned int nHashSeed, const std::vector<unsigned char
 
     return h1;
 }
+
+int HMAC_SHA512_Init(HMAC_SHA512_CTX *pctx, const void *pkey, size_t len)
+{
+    unsigned char key[128];
+    if (len <= 128)
+    {
+        memcpy(key, pkey, len);
+        memset(key + len, 0, 128-len);
+    }
+    else
+    {
+        SHA512_CTX ctxKey;
+        SHA512_Init(&ctxKey);
+        SHA512_Update(&ctxKey, pkey, len);
+        SHA512_Final(key, &ctxKey);
+        memset(key + 64, 0, 64);
+    }
+
+    for (int n=0; n<128; n++)
+        key[n] ^= 0x5c;
+    SHA512_Init(&pctx->ctxOuter);
+    SHA512_Update(&pctx->ctxOuter, key, 128);
+
+    for (int n=0; n<128; n++)
+        key[n] ^= 0x5c ^ 0x36;
+    SHA512_Init(&pctx->ctxInner);
+    return SHA512_Update(&pctx->ctxInner, key, 128);
+}
+
+int HMAC_SHA512_Update(HMAC_SHA512_CTX *pctx, const void *pdata, size_t len)
+{
+    return SHA512_Update(&pctx->ctxInner, pdata, len);
+}
+
+int HMAC_SHA512_Final(unsigned char *pmd, HMAC_SHA512_CTX *pctx)
+{
+    unsigned char buf[64];
+    SHA512_Final(buf, &pctx->ctxInner);
+    SHA512_Update(&pctx->ctxOuter, buf, 64);
+    return SHA512_Final(pmd, &pctx->ctxOuter);
+}
diff --git a/src/hash.h b/src/hash.h
index 536ab71165..880468a2d2 100644
--- a/src/hash.h
+++ b/src/hash.h
@@ -123,4 +123,14 @@ inline uint160 Hash160(const std::vector<unsigned char>& vch)
 
 unsigned int MurmurHash3(unsigned int nHashSeed, const std::vector<unsigned char>& vDataToHash);
 
+typedef struct
+{
+    SHA512_CTX ctxInner;
+    SHA512_CTX ctxOuter;
+} HMAC_SHA512_CTX;
+
+int HMAC_SHA512_Init(HMAC_SHA512_CTX *pctx, const void *pkey, size_t len);
+int HMAC_SHA512_Update(HMAC_SHA512_CTX *pctx, const void *pdata, size_t len);
+int HMAC_SHA512_Final(unsigned char *pmd, HMAC_SHA512_CTX *pctx);
+
 #endif
diff --git a/src/key.cpp b/src/key.cpp
index 1ab4c62ebf..5d7ea93a0f 100644
--- a/src/key.cpp
+++ b/src/key.cpp
@@ -2,6 +2,7 @@
 // Distributed under the MIT/X11 software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
+#include <openssl/bn.h>
 #include <openssl/ecdsa.h>
 #include <openssl/rand.h>
 #include <openssl/obj_mac.h>
@@ -254,6 +255,57 @@ public:
         ECDSA_SIG_free(sig);
         return ret;
     }
+
+    static bool TweakSecret(unsigned char vchSecretOut[32], const unsigned char vchSecretIn[32], const unsigned char vchTweak[32])
+    {
+        bool ret = true;
+        BN_CTX *ctx = BN_CTX_new();
+        BN_CTX_start(ctx);
+        BIGNUM *bnSecret = BN_CTX_get(ctx);
+        BIGNUM *bnTweak = BN_CTX_get(ctx);
+        BIGNUM *bnOrder = BN_CTX_get(ctx);
+        EC_GROUP *group = EC_GROUP_new_by_curve_name(NID_secp256k1);
+        EC_GROUP_get_order(group, bnOrder, ctx); // what a grossly inefficient way to get the (constant) group order...
+        BN_bin2bn(vchTweak, 32, bnTweak);
+        if (BN_cmp(bnTweak, bnOrder) >= 0)
+            ret = false; // extremely unlikely
+        BN_bin2bn(vchSecretIn, 32, bnSecret);
+        BN_add(bnSecret, bnSecret, bnTweak);
+        BN_nnmod(bnSecret, bnSecret, bnOrder, ctx);
+        if (BN_is_zero(bnSecret))
+            ret = false; // ridiculously unlikely
+        int nBits = BN_num_bits(bnSecret);
+        memset(vchSecretOut, 0, 32);
+        BN_bn2bin(bnSecret, &vchSecretOut[32-(nBits+7)/8]);
+        EC_GROUP_free(group);
+        BN_CTX_end(ctx);
+        BN_CTX_free(ctx);
+        return ret;
+    }
+
+    bool TweakPublic(const unsigned char vchTweak[32]) {
+        bool ret = true;
+        BN_CTX *ctx = BN_CTX_new();
+        BN_CTX_start(ctx);
+        BIGNUM *bnTweak = BN_CTX_get(ctx);
+        BIGNUM *bnOrder = BN_CTX_get(ctx);
+        BIGNUM *bnOne = BN_CTX_get(ctx);
+        const EC_GROUP *group = EC_KEY_get0_group(pkey);
+        EC_GROUP_get_order(group, bnOrder, ctx); // what a grossly inefficient way to get the (constant) group order...
+        BN_bin2bn(vchTweak, 32, bnTweak);
+        if (BN_cmp(bnTweak, bnOrder) >= 0)
+            ret = false; // extremely unlikely
+        EC_POINT *point = EC_POINT_dup(EC_KEY_get0_public_key(pkey), group);
+        BN_one(bnOne);
+        EC_POINT_mul(group, point, bnTweak, point, bnOne, ctx);
+        if (EC_POINT_is_at_infinity(group, point))
+            ret = false; // ridiculously unlikely
+        EC_KEY_set_public_key(pkey, point);
+        EC_POINT_free(point);
+        BN_CTX_end(ctx);
+        BN_CTX_free(ctx);
+        return ret;
+    }
 };
 
 }; // end of anonymous namespace
@@ -394,3 +446,131 @@ bool CPubKey::Decompress() {
     key.GetPubKey(*this, false);
     return true;
 }
+
+void static BIP32Hash(const unsigned char chainCode[32], unsigned int nChild, unsigned char header, const unsigned char data[32], unsigned char output[64]) {
+    unsigned char num[4];
+    num[0] = (nChild >> 24) & 0xFF;
+    num[1] = (nChild >> 16) & 0xFF;
+    num[2] = (nChild >>  8) & 0xFF;
+    num[3] = (nChild >>  0) & 0xFF;
+    HMAC_SHA512_CTX ctx;
+    HMAC_SHA512_Init(&ctx, chainCode, 32);
+    HMAC_SHA512_Update(&ctx, &header, 1);
+    HMAC_SHA512_Update(&ctx, data, 32);
+    HMAC_SHA512_Update(&ctx, num, 4);
+    HMAC_SHA512_Final(output, &ctx);
+}
+
+bool CKey::Derive(CKey& keyChild, unsigned char ccChild[32], unsigned int nChild, const unsigned char cc[32]) const {
+    assert(IsValid());
+    assert(IsCompressed());
+    unsigned char out[64];
+    LockObject(out);
+    if ((nChild >> 31) == 0) {
+        CPubKey pubkey = GetPubKey();
+        assert(pubkey.begin() + 33 == pubkey.end());
+        BIP32Hash(cc, nChild, *pubkey.begin(), pubkey.begin()+1, out);
+    } else {
+        assert(begin() + 32 == end());
+        BIP32Hash(cc, nChild, 0, begin(), out);
+    }
+    memcpy(ccChild, out+32, 32);
+    bool ret = CECKey::TweakSecret((unsigned char*)keyChild.begin(), begin(), out);
+    UnlockObject(out);
+    keyChild.fCompressed = true;
+    keyChild.fValid = ret;
+    return ret;
+}
+
+bool CPubKey::Derive(CPubKey& pubkeyChild, unsigned char ccChild[32], unsigned int nChild, const unsigned char cc[32]) const {
+    assert(IsValid());
+    assert((nChild >> 31) == 0);
+    assert(begin() + 33 == end());
+    unsigned char out[64];
+    BIP32Hash(cc, nChild, *begin(), begin()+1, out);
+    memcpy(ccChild, out+32, 32);
+    CECKey key;
+    bool ret = key.SetPubKey(*this);
+    ret &= key.TweakPublic(out);
+    key.GetPubKey(pubkeyChild, true);
+    return ret;
+}
+
+bool CExtKey::Derive(CExtKey &out, unsigned int nChild) const {
+    out.nDepth = nDepth + 1;
+    CKeyID id = key.GetPubKey().GetID();
+    memcpy(&out.vchFingerprint[0], &id, 4);
+    out.nChild = nChild;
+    return key.Derive(out.key, out.vchChainCode, nChild, vchChainCode);
+}
+
+void CExtKey::SetMaster(const unsigned char *seed, unsigned int nSeedLen) {
+    static const char hashkey[] = {'B','i','t','c','o','i','n',' ','s','e','e','d'};
+    HMAC_SHA512_CTX ctx;
+    HMAC_SHA512_Init(&ctx, hashkey, sizeof(hashkey));
+    HMAC_SHA512_Update(&ctx, seed, nSeedLen);
+    unsigned char out[64];
+    LockObject(out);
+    HMAC_SHA512_Final(out, &ctx);
+    key.Set(&out[0], &out[32], true);
+    memcpy(vchChainCode, &out[32], 32);
+    UnlockObject(out);
+    nDepth = 0;
+    nChild = 0;
+    memset(vchFingerprint, 0, sizeof(vchFingerprint));
+}
+
+CExtPubKey CExtKey::Neuter() const {
+    CExtPubKey ret;
+    ret.nDepth = nDepth;
+    memcpy(&ret.vchFingerprint[0], &vchFingerprint[0], 4);
+    ret.nChild = nChild;
+    ret.pubkey = key.GetPubKey();
+    memcpy(&ret.vchChainCode[0], &vchChainCode[0], 32);
+    return ret;
+}
+
+void CExtKey::Encode(unsigned char code[74]) const {
+    code[0] = nDepth;
+    memcpy(code+1, vchFingerprint, 4);
+    code[5] = (nChild >> 24) & 0xFF; code[6] = (nChild >> 16) & 0xFF;
+    code[7] = (nChild >>  8) & 0xFF; code[8] = (nChild >>  0) & 0xFF;
+    memcpy(code+9, vchChainCode, 32);
+    code[41] = 0;
+    assert(key.size() == 32);
+    memcpy(code+42, key.begin(), 32);
+}
+
+void CExtKey::Decode(const unsigned char code[74]) {
+    nDepth = code[0];
+    memcpy(vchFingerprint, code+1, 4);
+    nChild = (code[5] << 24) | (code[6] << 16) | (code[7] << 8) | code[8];
+    memcpy(vchChainCode, code+9, 32);
+    key.Set(code+42, code+74, true);
+}
+
+void CExtPubKey::Encode(unsigned char code[74]) const {
+    code[0] = nDepth;
+    memcpy(code+1, vchFingerprint, 4);
+    code[5] = (nChild >> 24) & 0xFF; code[6] = (nChild >> 16) & 0xFF;
+    code[7] = (nChild >>  8) & 0xFF; code[8] = (nChild >>  0) & 0xFF;
+    memcpy(code+9, vchChainCode, 32);
+    assert(pubkey.size() == 33);
+    memcpy(code+41, pubkey.begin(), 33);
+}
+
+void CExtPubKey::Decode(const unsigned char code[74]) {
+    nDepth = code[0];
+    memcpy(vchFingerprint, code+1, 4);
+    nChild = (code[5] << 24) | (code[6] << 16) | (code[7] << 8) | code[8];
+    memcpy(vchChainCode, code+9, 32);
+    pubkey.Set(code+41, code+74);
+}
+
+bool CExtPubKey::Derive(CExtPubKey &out, unsigned int nChild) const {
+    out.nDepth = nDepth + 1;
+    CKeyID id = pubkey.GetID();
+    memcpy(&out.vchFingerprint[0], &id, 4);
+    out.nChild = nChild;
+    return pubkey.Derive(out.pubkey, out.vchChainCode, nChild, vchChainCode);
+}
diff --git a/src/key.h b/src/key.h
index ce469ad298..75431e944f 100644
--- a/src/key.h
+++ b/src/key.h
@@ -161,6 +161,9 @@ public:
 
     // Turn this public key into an uncompressed public key.
     bool Decompress();
+
+    // Derive BIP32 child pubkey.
+    bool Derive(CPubKey& pubkeyChild, unsigned char ccChild[32], unsigned int nChild, const unsigned char cc[32]) const;
 };
 
 
@@ -201,6 +204,10 @@ public:
         UnlockObject(vch);
     }
 
+    friend bool operator==(const CKey &a, const CKey &b) {
+        return a.fCompressed == b.fCompressed && memcmp(&a.vch[0], &b.vch[0], 32);
+    }
+
     // Initialize using begin and end iterators to byte data.
     template<typename T>
     void Set(const T pbegin, const T pend, bool fCompressedIn) {
@@ -251,6 +258,45 @@ public:
     //                  0x1D = second key with even y, 0x1E = second key with odd y,
     //                  add 0x04 for compressed keys.
     bool SignCompact(const uint256 &hash, std::vector<unsigned char>& vchSig) const;
+
+    // Derive BIP32 child key.
+    bool Derive(CKey& keyChild, unsigned char ccChild[32], unsigned int nChild, const unsigned char cc[32]) const;
+};
+
+struct CExtPubKey {
+    unsigned char nDepth;
+    unsigned char vchFingerprint[4];
+    unsigned int nChild;
+    unsigned char vchChainCode[32];
+    CPubKey pubkey;
+
+    friend bool operator==(const CExtPubKey &a, const CExtPubKey &b) {
+        return a.nDepth == b.nDepth && memcmp(&a.vchFingerprint[0], &b.vchFingerprint[0], 4) == 0 && a.nChild == b.nChild &&
+               memcmp(&a.vchChainCode[0], &b.vchChainCode[0], 32) == 0 && a.pubkey == b.pubkey;
+    }
+
+    void Encode(unsigned char code[74]) const;
+    void Decode(const unsigned char code[74]);
+    bool Derive(CExtPubKey &out, unsigned int nChild) const;
+};
+
+struct CExtKey {
+    unsigned char nDepth;
+    unsigned char vchFingerprint[4];
+    unsigned int nChild;
+    unsigned char vchChainCode[32];
+    CKey key;
+
+    friend bool operator==(const CExtKey &a, const CExtKey &b) {
+        return a.nDepth == b.nDepth && memcmp(&a.vchFingerprint[0], &b.vchFingerprint[0], 4) == 0 && a.nChild == b.nChild &&
+               memcmp(&a.vchChainCode[0], &b.vchChainCode[0], 32) == 0 && a.key == b.key;
+    }
+
+    void Encode(unsigned char code[74]) const;
+    void Decode(const unsigned char code[74]);
+    bool Derive(CExtKey &out, unsigned int nChild) const;
+    CExtPubKey Neuter() const;
+    void SetMaster(const unsigned char *seed, unsigned int nSeedLen);
 };
 
 #endif
diff --git a/src/test/bip32_tests.cpp b/src/test/bip32_tests.cpp
new file mode 100644
index 0000000000..66d2330fbf
--- /dev/null
+++ b/src/test/bip32_tests.cpp
@@ -0,0 +1,116 @@
+#include <boost/test/unit_test.hpp>
+
+#include <string>
+#include <vector>
+
+#include "key.h"
+#include "base58.h"
+#include "uint256.h"
+#include "util.h"
+
+struct TestDerivation {
+    std::string pub;
+    std::string prv;
+    unsigned int nChild;
+};
+
+struct TestVector {
+    std::string strHexMaster;
+    std::vector<TestDerivation> vDerive;
+
+    TestVector(std::string strHexMasterIn) : strHexMaster(strHexMasterIn) {}
+
+    TestVector& operator()(std::string pub, std::string prv, unsigned int nChild) {
+        vDerive.push_back(TestDerivation());
+        TestDerivation &der = vDerive.back();
+        der.pub = pub;
+        der.prv = prv;
+        der.nChild = nChild;
+        return *this;
+    }
+};
+
+TestVector test1 =
+  TestVector("000102030405060708090a0b0c0d0e0f")
+    ("xpub661MyMwAqRbcFtXgS5sYJABqqG9YLmC4Q1Rdap9gSE8NqtwybGhePY2gZ29ESFjqJoCu1Rupje8YtGqsefD265TMg7usUDFdp6W1EGMcet8",
+     "xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKmPGJxWUtg6LnF5kejMRNNU3TGtRBeJgk33yuGBxrMPHi",
+     0x80000000)
+    ("xpub68Gmy5EdvgibQVfPdqkBBCHxA5htiqg55crXYuXoQRKfDBFA1WEjWgP6LHhwBZeNK1VTsfTFUHCdrfp1bgwQ9xv5ski8PX9rL2dZXvgGDnw",
+     "xprv9uHRZZhk6KAJC1avXpDAp4MDc3sQKNxDiPvvkX8Br5ngLNv1TxvUxt4cV1rGL5hj6KCesnDYUhd7oWgT11eZG7XnxHrnYeSvkzY7d2bhkJ7",
+     1)
+    ("xpub6ASuArnXKPbfEwhqN6e3mwBcDTgzisQN1wXN9BJcM47sSikHjJf3UFHKkNAWbWMiGj7Wf5uMash7SyYq527Hqck2AxYysAA7xmALppuCkwQ",
+     "xprv9wTYmMFdV23N2TdNG573QoEsfRrWKQgWeibmLntzniatZvR9BmLnvSxqu53Kw1UmYPxLgboyZQaXwTCg8MSY3H2EU4pWcQDnRnrVA1xe8fs",
+     0x80000002)
+    ("xpub6D4BDPcP2GT577Vvch3R8wDkScZWzQzMMUm3PWbmWvVJrZwQY4VUNgqFJPMM3No2dFDFGTsxxpG5uJh7n7epu4trkrX7x7DogT5Uv6fcLW5",
+     "xprv9z4pot5VBttmtdRTWfWQmoH1taj2axGVzFqSb8C9xaxKymcFzXBDptWmT7FwuEzG3ryjH4ktypQSAewRiNMjANTtpgP4mLTj34bhnZX7UiM",
+     2)
+    ("xpub6FHa3pjLCk84BayeJxFW2SP4XRrFd1JYnxeLeU8EqN3vDfZmbqBqaGJAyiLjTAwm6ZLRQUMv1ZACTj37sR62cfN7fe5JnJ7dh8zL4fiyLHV",
+     "xprvA2JDeKCSNNZky6uBCviVfJSKyQ1mDYahRjijr5idH2WwLsEd4Hsb2Tyh8RfQMuPh7f7RtyzTtdrbdqqsunu5Mm3wDvUAKRHSC34sJ7in334",
+     1000000000)
+    ("xpub6H1LXWLaKsWFhvm6RVpEL9P4KfRZSW7abD2ttkWP3SSQvnyA8FSVqNTEcYFgJS2UaFcxupHiYkro49S8yGasTvXEYBVPamhGW6cFJodrTHy",
+     "xprvA41z7zogVVwxVSgdKUHDy1SKmdb533PjDz7J6N6mV6uS3ze1ai8FHa8kmHScGpWmj4WggLyQjgPie1rFSruoUihUZREPSL39UNdE3BBDu76",
+     0);
+
+TestVector test2 =
+  TestVector("fffcf9f6f3f0edeae7e4e1dedbd8d5d2cfccc9c6c3c0bdbab7b4b1aeaba8a5a29f9c999693908d8a8784817e7b7875726f6c696663605d5a5754514e4b484542")
+    ("xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDMSgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB",
+     "xprv9s21ZrQH143K31xYSDQpPDxsXRTUcvj2iNHm5NUtrGiGG5e2DtALGdso3pGz6ssrdK4PFmM8NSpSBHNqPqm55Qn3LqFtT2emdEXVYsCzC2U",
+     0)
+    ("xpub69H7F5d8KSRgmmdJg2KhpAK8SR3DjMwAdkxj3ZuxV27CprR9LgpeyGmXUbC6wb7ERfvrnKZjXoUmmDznezpbZb7ap6r1D3tgFxHmwMkQTPH",
+     "xprv9vHkqa6EV4sPZHYqZznhT2NPtPCjKuDKGY38FBWLvgaDx45zo9WQRUT3dKYnjwih2yJD9mkrocEZXo1ex8G81dwSM1fwqWpWkeS3v86pgKt",
+     0xFFFFFFFF)
+    ("xpub6ASAVgeehLbnwdqV6UKMHVzgqAG8Gr6riv3Fxxpj8ksbH9ebxaEyBLZ85ySDhKiLDBrQSARLq1uNRts8RuJiHjaDMBU4Zn9h8LZNnBC5y4a",
+     "xprv9wSp6B7kry3Vj9m1zSnLvN3xH8RdsPP1Mh7fAaR7aRLcQMKTR2vidYEeEg2mUCTAwCd6vnxVrcjfy2kRgVsFawNzmjuHc2YmYRmagcEPdU9",
+     1)
+    ("xpub6DF8uhdarytz3FWdA8TvFSvvAh8dP3283MY7p2V4SeE2wyWmG5mg5EwVvmdMVCQcoNJxGoWaU9DCWh89LojfZ537wTfunKau47EL2dhHKon",
+     "xprv9zFnWC6h2cLgpmSA46vutJzBcfJ8yaJGg8cX1e5StJh45BBciYTRXSd25UEPVuesF9yog62tGAQtHjXajPPdbRCHuWS6T8XA2ECKADdw4Ef",
+     0xFFFFFFFE)
+    ("xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL",
+     "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc",
+     2)
+    ("xpub6FnCn6nSzZAw5Tw7cgR9bi15UV96gLZhjDstkXXxvCLsUXBGXPdSnLFbdpq8p9HmGsApME5hQTZ3emM2rnY5agb9rXpVGyy3bdW6EEgAtqt",
+     "xprvA2nrNbFZABcdryreWet9Ea4LvTJcGsqrMzxHx98MMrotbir7yrKCEXw7nadnHM8Dq38EGfSh6dqA9QWTyefMLEcBYJUuekgW4BYPJcr9E7j",
+     0);
+
+void RunTest(const TestVector &test) {
+    std::vector<unsigned char> seed = ParseHex(test.strHexMaster);
+    CExtKey key;
+    CExtPubKey pubkey;
+    key.SetMaster(&seed[0], seed.size());
+    pubkey = key.Neuter();
+    BOOST_FOREACH(const TestDerivation &derive, test.vDerive) {
+        unsigned char data[74];
+        key.Encode(data);
+        pubkey.Encode(data);
+        // Test private key
+        CBitcoinExtKey b58key; b58key.SetKey(key);
+        BOOST_CHECK(b58key.ToString() == derive.prv);
+        // Test public key
+        CBitcoinExtPubKey b58pubkey; b58pubkey.SetKey(pubkey);
+        BOOST_CHECK(b58pubkey.ToString() == derive.pub);
+        // Derive new keys
+        CExtKey keyNew;
+        BOOST_CHECK(key.Derive(keyNew, derive.nChild));
+        CExtPubKey pubkeyNew = keyNew.Neuter();
+        if (!(derive.nChild & 0x80000000)) {
+            // Compare with public derivation
+            CExtPubKey pubkeyNew2;
+            BOOST_CHECK(pubkey.Derive(pubkeyNew2, derive.nChild));
+            BOOST_CHECK(pubkeyNew == pubkeyNew2);
+        }
+        key = keyNew;
+        pubkey = pubkeyNew;
+    }
+}
+
+BOOST_AUTO_TEST_SUITE(bip32_tests)
+
+BOOST_AUTO_TEST_CASE(bip32_test1) {
+    RunTest(test1);
+}
+
+BOOST_AUTO_TEST_CASE(bip32_test2) {
+    RunTest(test2);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/hmac_tests.cpp b/src/test/hmac_tests.cpp
new file mode 100644
index 0000000000..92ca5e6aff
--- /dev/null
+++ b/src/test/hmac_tests.cpp
@@ -0,0 +1,125 @@
+#include <boost/test/unit_test.hpp>
+
+#include "hash.h"
+#include "util.h"
+
+using namespace std;
+
+BOOST_AUTO_TEST_SUITE(hmac_tests)
+
+typedef struct {
+    const char *pszKey;
+    const char *pszData;
+    const char *pszMAC;
+} testvec_t;
+
+// test cases 1, 2, 3, 4, 6 and 7 of RFC 4231
+static const testvec_t vtest[] = {
+    {
+        "0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b"
+        "0b0b0b0b",
+        "4869205468657265",
+        "87aa7cdea5ef619d4ff0b4241a1d6cb0"
+        "2379f4e2ce4ec2787ad0b30545e17cde"
+        "daa833b7d6b8a702038b274eaea3f4e4"
+        "be9d914eeb61f1702e696c203a126854"
+    },
+    {
+        "4a656665",
+        "7768617420646f2079612077616e7420"
+        "666f72206e6f7468696e673f",
+        "164b7a7bfcf819e2e395fbe73b56e0a3"
+        "87bd64222e831fd610270cd7ea250554"
+        "9758bf75c05a994a6d034f65f8f0e6fd"
+        "caeab1a34d4a6b4b636e070a38bce737"
+    },
+    {
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaaaa",
+        "dddddddddddddddddddddddddddddddd"
+        "dddddddddddddddddddddddddddddddd"
+        "dddddddddddddddddddddddddddddddd"
+        "dddd",
+        "fa73b0089d56a284efb0f0756c890be9"
+        "b1b5dbdd8ee81a3655f83e33b2279d39"
+        "bf3e848279a722c806b485a47e67c807"
+        "b946a337bee8942674278859e13292fb"
+    },
+    {
+        "0102030405060708090a0b0c0d0e0f10"
+        "111213141516171819",
+        "cdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcd"
+        "cdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcd"
+        "cdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcd"
+        "cdcd",
+        "b0ba465637458c6990e5a8c5f61d4af7"
+        "e576d97ff94b872de76f8050361ee3db"
+        "a91ca5c11aa25eb4d679275cc5788063"
+        "a5f19741120c4f2de2adebeb10a298dd"
+    },
+    {
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaa",
+        "54657374205573696e67204c61726765"
+        "72205468616e20426c6f636b2d53697a"
+        "65204b6579202d2048617368204b6579"
+        "204669727374",
+        "80b24263c7c1a3ebb71493c1dd7be8b4"
+        "9b46d1f41b4aeec1121b013783f8f352"
+        "6b56d037e05f2598bd0fd2215d6a1e52"
+        "95e64f73f63f0aec8b915a985d786598"
+    },
+    {
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+        "aaaaaa",
+        "54686973206973206120746573742075"
+        "73696e672061206c6172676572207468"
+        "616e20626c6f636b2d73697a65206b65"
+        "7920616e642061206c61726765722074"
+        "68616e20626c6f636b2d73697a652064"
+        "6174612e20546865206b6579206e6565"
+        "647320746f2062652068617368656420"
+        "6265666f7265206265696e6720757365"
+        "642062792074686520484d414320616c"
+        "676f726974686d2e",
+        "e37b6a775dc87dbaa4dfa9f96e5e3ffd"
+        "debd71f8867289865df5a32d20cdc944"
+        "b6022cac3c4982b10d5eeb55c3e4de15"
+        "134676fb6de0446065c97440fa8c6a58"
+    }
+};
+
+BOOST_AUTO_TEST_CASE(hmacsha512_testvectors)
+{
+    for (unsigned int n=0; n<sizeof(vtest)/sizeof(vtest[0]); n++)
+    {
+        vector<unsigned char> vchKey  = ParseHex(vtest[n].pszKey);
+        vector<unsigned char> vchData = ParseHex(vtest[n].pszData);
+        vector<unsigned char> vchMAC  = ParseHex(vtest[n].pszMAC);
+        unsigned char vchTemp[64];
+
+        HMAC_SHA512_CTX ctx;
+        HMAC_SHA512_Init(&ctx, &vchKey[0], vchKey.size());
+        HMAC_SHA512_Update(&ctx, &vchData[0], vchData.size());
+        HMAC_SHA512_Final(&vchTemp[0], &ctx);
+
+        BOOST_CHECK(memcmp(&vchTemp[0], &vchMAC[0], 64) == 0);
+
+    }
+}
+
+BOOST_AUTO_TEST_SUITE_END()