wallet: derive the key pool from a seed, so a phrase could bring it back (#93)

Adds BIP32 derivation behind the wallet key pool, with no user-facing way to create a seed yet. wallet.dat gains hdmaster/hdchaincode/hdnext; the mnemonic is never stored. TopUpKeyPool derives m/n' when a seed exists and falls back to a random key, with a log line, if derivation fails. New -selftest=wallet-hd, wired into make tests on both platforms.

9 files changed, 382 insertions, 4 deletions

diff --git a/src/Makefile b/src/Makefile
index d4b1837..bbdc9e2 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -50,7 +50,7 @@ IMGUI_OBJS = obj/imgui.o obj/imgui_draw.o obj/imgui_tables.o \
 NODE_OBJS = obj/util.o obj/script.o obj/db.o obj/net.o obj/main.o \
             obj/market.o obj/sha.o obj/nostr.o obj/randomx_pow.o \
             obj/btfaddr.o obj/btfchan.o obj/btfrv.o obj/btftunnel.o obj/rpc.o \
-            obj/selftest.o
+            obj/selftest.o obj/bip32.o
 
 GUI_OBJS = obj/gui.o obj/main_gui.o
 
@@ -131,3 +131,4 @@ test_bip32: test_bip32.cpp bip32.cpp bip32.h bip39_english.h
 tests: test_bip32 bitflash-node
         ./test_bip32
         ./bitflash-node -selftest=wallet-keypool
+        ./bitflash-node -selftest=wallet-hd
diff --git a/src/db.cpp b/src/db.cpp
index d482c5a..294920b 100644
--- a/src/db.cpp
+++ b/src/db.cpp
@@ -639,6 +639,18 @@ bool CWalletDB::LoadWallet(vector<unsigned char>& vchDefaultKeyRet)
             {
                 ssValue >> vchDefaultKeyRet;
             }
+            else if (strType == "hdmaster")
+            {
+                ssValue >> vchHDMaster;
+            }
+            else if (strType == "hdchaincode")
+            {
+                ssValue >> vchHDChainCode;
+            }
+            else if (strType == "hdnext")
+            {
+                ssValue >> nHDNext;
+            }
             else if (strType == "pool")
             {
                 int64 nIndex;
diff --git a/src/db.h b/src/db.h
index f51047e..01b8583 100644
--- a/src/db.h
+++ b/src/db.h
@@ -386,6 +386,33 @@ public:
         return Write(string("defaultkey"), vchPubKey);
     }
 
+    // --- Deterministic (BIP32) seed ---------------------------------------
+    //
+    // Stored as the master key and chain code rather than the mnemonic: the
+    // twelve words are the user's to write down, and keeping a copy of them in
+    // the file they are meant to protect defeats the point of having them.
+    //
+    // "hdnext" is the next child index to derive, so the sequence a restore
+    // reproduces is the same one this wallet handed out.
+    bool ReadHDMaster(vector<unsigned char>& vchMasterRet, vector<unsigned char>& vchChainCodeRet)
+    {
+        vchMasterRet.clear();
+        vchChainCodeRet.clear();
+        return Read(string("hdmaster"), vchMasterRet)
+            && Read(string("hdchaincode"), vchChainCodeRet);
+    }
+
+    bool WriteHDMaster(const vector<unsigned char>& vchMaster, const vector<unsigned char>& vchChainCode)
+    {
+        return Write(string("hdmaster"), vchMaster)
+            && Write(string("hdchaincode"), vchChainCode);
+    }
+
+    bool WriteHDNext(unsigned int nNext)
+    {
+        return Write(string("hdnext"), nNext);
+    }
+
     // Keys generated ahead of time and not yet handed out. The private key of
     // each is already stored under its own "key" record by AddKey; a "pool"
     // record only says that this one is still unspoken for.
diff --git a/src/key.h b/src/key.h
index 26e1ae2..6cc2a24 100644
--- a/src/key.h
+++ b/src/key.h
@@ -86,6 +86,40 @@ public:
         return true;
     }
 
+    // Load a raw 32-byte scalar, the form BIP32 derivation produces.
+    //
+    // SetPrivKey above takes DER and cannot be used for this: handing it a
+    // scalar makes d2i_ECPrivateKey fail, and if the caller ignores the return
+    // value -- as one attempt at this did -- the key is left with no material
+    // at all and the address it produces has no private half. Coins paid there
+    // are gone. Hence a separate entry point rather than a looser SetPrivKey.
+    //
+    // The public half is computed here rather than read from anywhere:
+    // pub = G * secret.
+    bool SetSecret(const std::vector<unsigned char>& vchSecret)
+    {
+        if (vchSecret.size() != 32)
+            return false;
+
+        bool fOk = false;
+        BIGNUM* bn = BN_bin2bn(&vchSecret[0], 32, NULL);
+        EC_POINT* pubkey = NULL;
+        if (bn && EC_KEY_set_private_key(pkey, bn))
+        {
+            const EC_GROUP* group = EC_KEY_get0_group(pkey);
+            pubkey = EC_POINT_new(group);
+            if (pubkey &&
+                EC_POINT_mul(group, pubkey, bn, NULL, NULL, NULL) &&
+                EC_KEY_set_public_key(pkey, pubkey))
+                fOk = true;
+        }
+        if (pubkey)
+            EC_POINT_free(pubkey);
+        if (bn)
+            BN_clear_free(bn);   // it held the secret
+        return fOk;
+    }
+
     CPrivKey GetPrivKey() const
     {
         unsigned int nSize = i2d_ECPrivateKey(pkey, NULL);
diff --git a/src/main.cpp b/src/main.cpp
index 82a98d2..e5754e6 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -14,6 +14,7 @@
 #include <atomic>
 #include <mutex>
 #include <thread>
+#include "bip32.h"
 #include "btfaddr.h"
 #include "btftunnel.h"
 #ifndef _WIN32
@@ -178,6 +179,66 @@ vector<unsigned char> GenerateNewKey()
 CCriticalSection cs_keyPool;
 map<int64, vector<unsigned char> > mapKeyPool;
 
+vector<unsigned char> vchHDMaster;
+vector<unsigned char> vchHDChainCode;
+unsigned int nHDNext = 0;
+
+bool DeriveHDKey(unsigned int nIndex, CKey& keyRet, string& strErrorRet)
+{
+    if (!HaveHDSeed())
+    {
+        strErrorRet = "no seed";
+        return false;
+    }
+
+    bitflash::BIP32PrivateNode parent;
+    parent.privateKey = vchHDMaster;
+    parent.chainCode  = vchHDChainCode;
+
+    bitflash::BIP32PrivateNode child;
+    if (!bitflash::BIP32DeriveHardenedChild(parent, nIndex, child, strErrorRet))
+        return false;
+
+    if (!keyRet.SetSecret(child.privateKey))
+    {
+        strErrorRet = "derived scalar is not a usable key";
+        return false;
+    }
+    return true;
+}
+
+bool SetHDSeedFromMnemonic(const string& strMnemonic, string& strErrorRet)
+{
+    string strNormalized;
+    if (!bitflash::BIP39ValidateMnemonic(strMnemonic, strNormalized, strErrorRet))
+        return false;
+
+    vector<unsigned char> vchSeed;
+    if (!bitflash::BIP39MnemonicToSeed(strNormalized, "", vchSeed, strErrorRet))
+        return false;
+
+    bitflash::BIP32PrivateNode master;
+    if (!bitflash::BIP32MasterFromSeed(vchSeed, master, strErrorRet))
+        return false;
+
+    CRITICAL_BLOCK(cs_keyPool)
+    {
+        // Written before the globals change, so a failed write leaves the
+        // wallet on the seed it already had rather than on one that exists
+        // only in memory.
+        if (!CWalletDB().WriteHDMaster(master.privateKey, master.chainCode) ||
+            !CWalletDB().WriteHDNext(0))
+        {
+            strErrorRet = "could not write the seed to wallet.dat";
+            return false;
+        }
+        vchHDMaster    = master.privateKey;
+        vchHDChainCode = master.chainCode;
+        nHDNext        = 0;
+    }
+    return true;
+}
+
 void TopUpKeyPool()
 {
     CRITICAL_BLOCK(cs_keyPool)
@@ -191,7 +252,30 @@ void TopUpKeyPool()
                 nIndex = (--mapKeyPool.end())->first + 1;
 
             CKey key;
-            key.MakeNewKey();
+            if (HaveHDSeed())
+            {
+                // Derived, so a recovery phrase can reproduce this exact key.
+                // A derivation that fails is not a reason to stop filling the
+                // pool -- fall back to a random key, which is what a wallet
+                // without a seed uses anyway. It will not come back from the
+                // phrase, and that is better than a node that cannot mine.
+                string strError;
+                if (DeriveHDKey(nHDNext, key, strError))
+                {
+                    nHDNext++;
+                    CWalletDB().WriteHDNext(nHDNext);
+                }
+                else
+                {
+                    printf("TopUpKeyPool() : derivation at index %u failed (%s), "
+                           "falling back to a random key\n", nHDNext, strError.c_str());
+                    key.MakeNewKey();
+                }
+            }
+            else
+            {
+                key.MakeNewKey();
+            }
             // AddKey writes the private key. Order matters: the key is in
             // wallet.dat before anything can point at it, so a crash between
             // the two writes costs an unused key, never a usable one.
@@ -310,6 +394,32 @@ bool AddToWalletIfMine(const CTransaction& tx, const CBlock* pblock)
     return true;
 }
 
+bool CanScanWalletTransactions(string& strErrorRet)
+{
+    strErrorRet.clear();
+
+    if (pindexGenesisBlock == NULL || pindexBest == NULL || hashBestChain == 0 || nBestHeight < 0)
+    {
+        strErrorRet = "The block index is not loaded, so the wallet scan cannot "
+                      "prove whether imported or restored keys own coins.";
+        return false;
+    }
+
+    if (nBestHeight == 0)
+    {
+        strErrorRet = "The local chain is only at height 0. A wallet scan would "
+                      "inspect only the genesis block and could incorrectly "
+                      "report zero transactions. Start the node and let it sync "
+                      "before scanning. If this happened after copying a data "
+                      "directory, keep wallet.dat safe and rebuild or re-download "
+                      "the block data instead of trusting the copied database/ "
+                      "environment.";
+        return false;
+    }
+
+    return true;
+}
+
 int ScanForWalletTransactions(CBlockIndex* pindexStart)
 {
     // Walk the chain looking for transactions that belong to keys this wallet
diff --git a/src/main.h b/src/main.h
index 8d9b7e6..a04a4e3 100644
--- a/src/main.h
+++ b/src/main.h
@@ -141,6 +141,33 @@ static const int KEYPOOL_SIZE = 100;
 extern CCriticalSection cs_keyPool;
 extern map<int64, vector<unsigned char> > mapKeyPool;
 
+// --- Deterministic wallet (BIP32) -----------------------------------------
+//
+// When a seed is present the key pool is derived from it -- m/0'/n, hardened,
+// n increasing -- instead of being made of random keys. That is what lets a
+// recovery phrase bring a wallet back: the same twelve words reproduce the same
+// keys in the same order.
+//
+// A wallet without a seed keeps working exactly as before. Nothing here
+// migrates an existing wallet on its own: the seed is created only when the
+// user asks for a phrase and confirms they have written it down, because a
+// phrase generated silently is a backup nobody has.
+//
+// Empty until a seed exists.
+extern vector<unsigned char> vchHDMaster;     // 32-byte master private key (IL)
+extern vector<unsigned char> vchHDChainCode;  // 32 bytes (IR)
+extern unsigned int nHDNext;                  // next child index to derive
+inline bool HaveHDSeed() { return vchHDMaster.size() == 32 && vchHDChainCode.size() == 32; }
+
+// Install a seed derived from a mnemonic, replacing any existing one, and reset
+// the derivation counter. Writes to wallet.dat. Returns false and leaves the
+// wallet untouched if the phrase is not valid.
+bool SetHDSeedFromMnemonic(const string& strMnemonic, string& strErrorRet);
+
+// Derive the child at nIndex and return it as a key. Used by the key pool and
+// by restore, which needs to run ahead of the pool.
+bool DeriveHDKey(unsigned int nIndex, CKey& keyRet, string& strErrorRet);
+
 // Fill the pool back up to KEYPOOL_SIZE. Every key it creates is written to
 // wallet.dat before it is offered to anybody.
 void TopUpKeyPool();
@@ -156,6 +183,7 @@ void ReacceptWalletTransactions();
 // a key this wallet holds. Returns how many were added or updated. Needed by
 // anything that puts a key into the wallet after the fact -- an import, a
 // restored backup, and later a recovery phrase.
+bool CanScanWalletTransactions(string& strErrorRet);
 int  ScanForWalletTransactions(CBlockIndex* pindexStart);
 // Returns how many wallet transactions the chain corrected.
 int  RescanSpentFlags();
diff --git a/src/main_gui.cpp b/src/main_gui.cpp
index 2bcdb83..aa9c23d 100644
--- a/src/main_gui.cpp
+++ b/src/main_gui.cpp
@@ -323,6 +323,16 @@ int main(int argc, char* argv[])
             // import having failed.
             if (nAdded > 0)
             {
+                string strScanError;
+                if (!CanScanWalletTransactions(strScanError))
+                {
+                    fprintf(stderr, "Cannot scan for imported coins: %s\n",
+                            strScanError.c_str());
+                    fprintf(stderr, "The key import was written, but the wallet "
+                                    "balance was not proven against the chain.\n");
+                    DBFlush(true);
+                    return 1;
+                }
                 printf("Looking through the chain for coins belonging to the imported key(s)...\n");
                 int nFound = ScanForWalletTransactions(pindexGenesisBlock);
                 printf("Found %d transaction(s). Start the node normally to see the balance.\n", nFound);
@@ -339,6 +349,14 @@ int main(int argc, char* argv[])
     // balance is wrong for this reason.
     if (arg(argc,argv,"/rescan") || arg(argc,argv,"-rescan"))
     {
+        string strScanError;
+        if (!CanScanWalletTransactions(strScanError))
+        {
+            fprintf(stderr, "Cannot rescan wallet transactions: %s\n",
+                    strScanError.c_str());
+            DBFlush(true);
+            return 1;
+        }
         printf("Rescanning the chain for this wallet's transactions...\n");
         int nFound = ScanForWalletTransactions(pindexGenesisBlock);
         printf("Rescan done: %d transaction(s) added or updated.\n", nFound);
diff --git a/src/makefile.mingw b/src/makefile.mingw
index 4f297d9..07ae034 100644
--- a/src/makefile.mingw
+++ b/src/makefile.mingw
@@ -42,7 +42,7 @@ IMGUI_OBJS = obj/imgui.o obj/imgui_draw.o obj/imgui_tables.o \
 NODE_OBJS = obj/util.o obj/script.o obj/db.o obj/net.o obj/main.o \
             obj/market.o obj/sha.o obj/nostr.o obj/randomx_pow.o \
             obj/btfaddr.o obj/btfchan.o obj/btfrv.o obj/btftunnel.o obj/rpc.o \
-            obj/selftest.o
+            obj/selftest.o obj/bip32.o
 
 GUI_OBJS = obj/gui.o obj/main_gui.o obj/bitflash_res.o
 
@@ -103,3 +103,4 @@ test_bip32.exe: test_bip32.cpp bip32.cpp bip32.h bip39_english.h
 tests: test_bip32.exe bitflash.exe
         ./test_bip32.exe
         ./bitflash.exe -selftest=wallet-keypool
+        ./bitflash.exe -selftest=wallet-hd
diff --git a/src/selftest.cpp b/src/selftest.cpp
index abe1d15..6792ae7 100644
--- a/src/selftest.cpp
+++ b/src/selftest.cpp
@@ -314,14 +314,161 @@ static void AttachTerminal()
 #endif
 }
 
+static int RunWalletHDSelfTest()
+{
+    fflush(stdout);
+    printf("wallet-hd self-test\n");
+
+    std::string tmp;
+    std::string cwd;
+    if (!MakeTempDir(tmp))
+    {
+        printf("  FAIL could not create a temporary data directory\n");
+        return 1;
+    }
+    if (!GetCurrentDir(cwd) || !SetCurrentDir(tmp))
+    {
+        printf("  FAIL could not move into the temporary data directory\n");
+        RemoveTree(tmp);
+        return 1;
+    }
+
+    int nFail = 0;
+    strSetDataDir = tmp;
+    printf("  temp datadir: %s\n", tmp.c_str());
+
+    // Test-vector phrases, so nothing here depends on randomness.
+    const std::string strPhraseA =
+        "abandon abandon abandon abandon abandon abandon "
+        "abandon abandon abandon abandon abandon about";
+    const std::string strPhraseB =
+        "legal winner thank year wave sausage worth useful "
+        "legal winner thank yellow";
+
+    try
+    {
+        if (!LoadWallet())
+            throw std::runtime_error("LoadWallet failed");
+
+        std::string strError;
+        nFail += Check(SetHDSeedFromMnemonic(strPhraseA, strError),
+                       "a valid phrase installs a seed") ? 0 : 1;
+        nFail += Check(HaveHDSeed(), "the wallet reports having a seed") ? 0 : 1;
+
+        std::vector<unsigned char> vchBefore = vchHDMaster;
+        nFail += Check(!SetHDSeedFromMnemonic("not a mnemonic at all", strError),
+                       "an invalid phrase is refused") ? 0 : 1;
+        nFail += Check(vchHDMaster == vchBefore,
+                       "a refused phrase leaves the existing seed alone") ? 0 : 1;
+
+        // The property the whole feature exists for: the same words give back
+        // the same keys, in the same order.
+        std::vector<std::string> first;
+        for (unsigned int i = 0; i < 5; i++)
+        {
+            CKey key;
+            if (!DeriveHDKey(i, key, strError))
+                throw std::runtime_error("derivation failed: " + strError);
+            first.push_back(HexStrLocal(key.GetPubKey()));
+        }
+
+        SetHDSeedFromMnemonic(strPhraseA, strError);
+        std::vector<std::string> again;
+        for (unsigned int i = 0; i < 5; i++)
+        {
+            CKey key;
+            if (!DeriveHDKey(i, key, strError))
+                throw std::runtime_error("derivation failed: " + strError);
+            again.push_back(HexStrLocal(key.GetPubKey()));
+        }
+        nFail += Check(first == again,
+                       "the same phrase derives the same keys in the same order") ? 0 : 1;
+
+        SetHDSeedFromMnemonic(strPhraseB, strError);
+        std::vector<std::string> other;
+        for (unsigned int i = 0; i < 5; i++)
+        {
+            CKey key;
+            if (!DeriveHDKey(i, key, strError))
+                throw std::runtime_error("derivation failed: " + strError);
+            other.push_back(HexStrLocal(key.GetPubKey()));
+        }
+        nFail += Check(first != other, "a different phrase derives different keys") ? 0 : 1;
+
+        std::set<std::string> distinct(first.begin(), first.end());
+        nFail += Check(distinct.size() == first.size(),
+                       "consecutive indices give distinct keys") ? 0 : 1;
+
+        // With a seed installed the pool must be derived from it, and the
+        // counter must move exactly once per key.
+        SetHDSeedFromMnemonic(strPhraseA, strError);
+        CRITICAL_BLOCK(cs_keyPool)
+            mapKeyPool.clear();
+        unsigned int nNextBefore = nHDNext;
+        TopUpKeyPool();
+
+        int nPool = 0;
+        CRITICAL_BLOCK(cs_keyPool)
+            nPool = (int)mapKeyPool.size();
+        nFail += Check(nPool == KEYPOOL_SIZE, "the derived pool fills") ? 0 : 1;
+        nFail += Check(nHDNext == nNextBefore + (unsigned int)KEYPOOL_SIZE,
+                       "the derivation counter advances once per pooled key") ? 0 : 1;
+
+        std::set<std::string> derived;
+        for (unsigned int i = nNextBefore; i < nHDNext; i++)
+        {
+            CKey key;
+            if (!DeriveHDKey(i, key, strError))
+                throw std::runtime_error("derivation failed: " + strError);
+            derived.insert(HexStrLocal(key.GetPubKey()));
+        }
+
+        bool fStored = true;
+        bool fFromSeed = true;
+        CRITICAL_BLOCK(cs_keyPool)
+        {
+            for (map<int64, vector<unsigned char> >::const_iterator mi = mapKeyPool.begin();
+                 mi != mapKeyPool.end(); ++mi)
+            {
+                if (!WalletHasPrivateKey(mi->second))
+                    fStored = false;
+                if (!derived.count(HexStrLocal(mi->second)))
+                    fFromSeed = false;
+            }
+        }
+        nFail += Check(fStored, "every derived pooled key is stored in wallet.dat") ? 0 : 1;
+        nFail += Check(fFromSeed, "every pooled key came from the seed, not from chance") ? 0 : 1;
+    }
+    catch (const std::exception& e)
+    {
+        printf("  FAIL exception: %s\n", e.what());
+        nFail++;
+    }
+    catch (...)
+    {
+        printf("  FAIL unknown exception\n");
+        nFail++;
+    }
+
+    DBFlush(true);
+    SetCurrentDir(cwd);
+    RemoveTree(tmp);
+    printf("%s (%d failure%s)\n", nFail == 0 ? "ALL TESTS PASSED" : "TESTS FAILED",
+           nFail, nFail == 1 ? "" : "s");
+    fflush(stdout);
+    return nFail == 0 ? 0 : 1;
+}
+
 int RunSelfTest(const std::string& name)
 {
     AttachTerminal();
 
     if (name == "wallet-keypool")
         return RunWalletKeyPoolSelfTest();
+    if (name == "wallet-hd")
+        return RunWalletHDSelfTest();
 
     printf("Unknown self-test '%s'\n", name.c_str());
-    printf("Known self-tests: wallet-keypool\n");
+    printf("Known self-tests: wallet-keypool, wallet-hd\n");
     return 1;
 }