Merge #11403: SegWit wallet support

b224a47a1 Add address_types test (Pieter Wuille)
7ee54fd7c Support downgrading after recovered keypool witness keys (Pieter Wuille)
940a21932 SegWit wallet support (Pieter Wuille)
f37c64e47 Implicitly know about P2WPKH redeemscripts (Pieter Wuille)
57273f2b3 [test] Serialize CTransaction with witness by default (Pieter Wuille)
cf2c0b6f5 Support P2WPKH and P2SH-P2WPKH in dumpprivkey (Pieter Wuille)
37c03d3e0 Support P2WPKH addresses in create/addmultisig (Pieter Wuille)
3eaa003c8 Extend validateaddress information for P2SH-embedded witness (Pieter Wuille)
30a27dc5b Expose method to find key for a single-key destination (Pieter Wuille)
985c79552 Improve witness destination types and use them more (Pieter Wuille)
cbe197470 [refactor] GetAccount{PubKey,Address} -> GetAccountDestination (Pieter Wuille)
0c8ea6380 Abstract out IsSolvable from Witnessifier (Pieter Wuille)

Pull request description:

  This implements a minimum viable implementation of SegWit wallet support, based on top of #11389, and includes part of the functionality from #11089.

  Two new configuration options are added:
  * `-addresstype`, with options `legacy`, `p2sh`, and `bech32`. It controls what kind of addresses are produced by `getnewaddress`, `getaccountaddress`, and `createmultisigaddress`.
  * `-changetype`, with the same options, and by default equal to `-addresstype`, that controls what kind of change is used.

  All wallet private and public keys can be used for any type of address. Support for address types dependent on different derivation paths will need a major overhaul of how our internal detection of outputs work. I expect that that will happen for a next major version.

  The above also applies to imported keys, as having a distinction there but not for normal operations is a disaster for testing, and probably for comprehension of users. This has some ugly effects, like needing to associate the provided label to `importprivkey` with each style address for the corresponding key.

  To deal with witness outputs requiring a corresponding redeemscript in wallet, three approaches are used:
  * All SegWit addresses created through `getnewaddress` or multisig RPCs explicitly get their redeemscripts added to the wallet file. This means that downgrading after creating a witness address will work, as long as the wallet file is up to date.
  * All SegWit keys in the wallet get an _implicit_ redeemscript added, without it being written to the file. This means recovery of an old backup will work, as long as you use new software.
  * All keypool keys that are seen used in transactions explicitly get their redeemscripts added to the wallet files. This means that downgrading after recovering from a backup that includes a witness address will work.

  These approaches correspond to solutions 3a, 1a, and 5a respectively from https://gist.github.com/sipa/125cfa1615946d0c3f3eec2ad7f250a2. As argued there, there is no full solution for dealing with the case where you both downgrade and restore a backup, so that's also not implemented.

  `dumpwallet`, `importwallet`, `importmulti`, `signmessage` and `verifymessage` don't work with SegWit addresses yet. They're remaining TODOs, for this PR or a follow-up. Because of that, several tests unexpectedly run with `-addresstype=legacy` for now.

Tree-SHA512: d425dbe517c0422061ab8dacdc3a6ae47da071450932ed992c79559d922dff7b2574a31a8c94feccd3761c1dffb6422c50055e6dca8e3cf94a169bc95e39e959

4 files changed, 48 insertions, 10 deletions

diff --git a/src/script/sign.cpp b/src/script/sign.cpp
index f1ec5e2d13..838e502a0a 100644
--- a/src/script/sign.cpp
+++ b/src/script/sign.cpp
@@ -422,3 +422,22 @@ bool DummySignatureCreator::CreateSig(std::vector<unsigned char>& vchSig, const
     vchSig[6 + 33 + 32] = SIGHASH_ALL;
     return true;
 }
+
+bool IsSolvable(const CKeyStore& store, const CScript& script)
+{
+    // This check is to make sure that the script we created can actually be solved for and signed by us
+    // if we were to have the private keys. This is just to make sure that the script is valid and that,
+    // if found in a transaction, we would still accept and relay that transaction. In particular,
+    // it will reject witness outputs that require signing with an uncompressed public key.
+    DummySignatureCreator creator(&store);
+    SignatureData sigs;
+    // Make sure that STANDARD_SCRIPT_VERIFY_FLAGS includes SCRIPT_VERIFY_WITNESS_PUBKEYTYPE, the most
+    // important property this function is designed to test for.
+    static_assert(STANDARD_SCRIPT_VERIFY_FLAGS & SCRIPT_VERIFY_WITNESS_PUBKEYTYPE, "IsSolvable requires standard script flags to include WITNESS_PUBKEYTYPE");
+    if (ProduceSignature(creator, script, sigs)) {
+        // VerifyScript check is just defensive, and should never fail.
+        assert(VerifyScript(sigs.scriptSig, script, &sigs.scriptWitness, STANDARD_SCRIPT_VERIFY_FLAGS, creator.Checker()));
+        return true;
+    }
+    return false;
+}
diff --git a/src/script/sign.h b/src/script/sign.h
index 0fe97a80e8..97c0014cd0 100644
--- a/src/script/sign.h
+++ b/src/script/sign.h
@@ -81,4 +81,10 @@ SignatureData CombineSignatures(const CScript& scriptPubKey, const BaseSignature
 SignatureData DataFromTransaction(const CMutableTransaction& tx, unsigned int nIn);
 void UpdateTransaction(CMutableTransaction& tx, unsigned int nIn, const SignatureData& data);
 
+/* Check whether we know how to sign for an output like this, assuming we
+ * have all private keys. While this function does not need private keys, the passed
+ * keystore is used to look up public keys and redeemscripts by hash.
+ * Solvability is unrelated to whether we consider this output to be ours. */
+bool IsSolvable(const CKeyStore& store, const CScript& script);
+
 #endif // BITCOIN_SCRIPT_SIGN_H
diff --git a/src/script/standard.cpp b/src/script/standard.cpp
index 43961d0572..cfb3c58588 100644
--- a/src/script/standard.cpp
+++ b/src/script/standard.cpp
@@ -348,19 +348,14 @@ CScript GetScriptForWitness(const CScript& redeemscript)
     std::vector<std::vector<unsigned char> > vSolutions;
     if (Solver(redeemscript, typ, vSolutions)) {
         if (typ == TX_PUBKEY) {
-            unsigned char h160[20];
-            CHash160().Write(&vSolutions[0][0], vSolutions[0].size()).Finalize(h160);
-            ret << OP_0 << std::vector<unsigned char>(&h160[0], &h160[20]);
-            return ret;
+            return GetScriptForDestination(WitnessV0KeyHash(Hash160(vSolutions[0].begin(), vSolutions[0].end())));
         } else if (typ == TX_PUBKEYHASH) {
-           ret << OP_0 << vSolutions[0];
-           return ret;
+            return GetScriptForDestination(WitnessV0KeyHash(vSolutions[0]));
         }
     }
     uint256 hash;
     CSHA256().Write(&redeemscript[0], redeemscript.size()).Finalize(hash.begin());
-    ret << OP_0 << ToByteVector(hash);
-    return ret;
+    return GetScriptForDestination(WitnessV0ScriptHash(hash));
 }
 
 bool IsValidDestination(const CTxDestination& dest) {
diff --git a/src/script/standard.h b/src/script/standard.h
index 5925f2a512..3b2838a5bb 100644
--- a/src/script/standard.h
+++ b/src/script/standard.h
@@ -73,8 +73,19 @@ public:
     friend bool operator<(const CNoDestination &a, const CNoDestination &b) { return true; }
 };
 
-struct WitnessV0ScriptHash : public uint256 {};
-struct WitnessV0KeyHash : public uint160 {};
+struct WitnessV0ScriptHash : public uint256
+{
+    WitnessV0ScriptHash() : uint256() {}
+    explicit WitnessV0ScriptHash(const uint256& hash) : uint256(hash) {}
+    using uint256::uint256;
+};
+
+struct WitnessV0KeyHash : public uint160
+{
+    WitnessV0KeyHash() : uint160() {}
+    explicit WitnessV0KeyHash(const uint160& hash) : uint160(hash) {}
+    using uint160::uint160;
+};
 
 //! CTxDestination subtype to encode any future Witness version
 struct WitnessUnknown
@@ -144,6 +155,10 @@ bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
  * addressRet is populated with a single value and nRequiredRet is set to 1.
  * Returns true if successful. Currently does not extract address from
  * pay-to-witness scripts.
+ *
+ * Note: this function confuses destinations (a subset of CScripts that are
+ * encodable as an address) with key identifiers (of keys involved in a
+ * CScript), and its use should be phased out.
  */
 bool ExtractDestinations(const CScript& scriptPubKey, txnouttype& typeRet, std::vector<CTxDestination>& addressRet, int& nRequiredRet);
 
@@ -164,6 +179,9 @@ CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys);
  * Generate a pay-to-witness script for the given redeem script. If the redeem
  * script is P2PK or P2PKH, this returns a P2WPKH script, otherwise it returns a
  * P2WSH script.
+ *
+ * TODO: replace calls to GetScriptForWitness with GetScriptForDestination using
+ * the various witness-specific CTxDestination subtypes.
  */
 CScript GetScriptForWitness(const CScript& redeemscript);