1 files changed, 196 insertions, 201 deletions

diff --git a/src/script/sign.cpp b/src/script/sign.cpp
index 6dbfbda029..60a8a2655d 100644
--- a/src/script/sign.cpp
+++ b/src/script/sign.cpp
@@ -33,27 +33,51 @@ bool MutableTransactionSignatureCreator::CreateSig(const SigningProvider& provid
     return true;
 }
 
-static bool Sign1(const SigningProvider& provider, const CKeyID& address, const BaseSignatureCreator& creator, const CScript& scriptCode, std::vector<valtype>& ret, SigVersion sigversion)
+static bool GetCScript(const SigningProvider& provider, const SignatureData& sigdata, const CScriptID& scriptid, CScript& script)
 {
-    std::vector<unsigned char> vchSig;
-    if (!creator.CreateSig(provider, vchSig, address, scriptCode, sigversion))
-        return false;
-    ret.push_back(vchSig);
-    return true;
+    if (provider.GetCScript(scriptid, script)) {
+        return true;
+    }
+    // Look for scripts in SignatureData
+    if (CScriptID(sigdata.redeem_script) == scriptid) {
+        script = sigdata.redeem_script;
+        return true;
+    } else if (CScriptID(sigdata.witness_script) == scriptid) {
+        script = sigdata.witness_script;
+        return true;
+    }
+    return false;
 }
 
-static bool SignN(const SigningProvider& provider, const std::vector<valtype>& multisigdata, const BaseSignatureCreator& creator, const CScript& scriptCode, std::vector<valtype>& ret, SigVersion sigversion)
+static bool GetPubKey(const SigningProvider& provider, const SignatureData& sigdata, const CKeyID& address, CPubKey& pubkey)
 {
-    int nSigned = 0;
-    int nRequired = multisigdata.front()[0];
-    for (unsigned int i = 1; i < multisigdata.size()-1 && nSigned < nRequired; i++)
-    {
-        const valtype& pubkey = multisigdata[i];
-        CKeyID keyID = CPubKey(pubkey).GetID();
-        if (Sign1(provider, keyID, creator, scriptCode, ret, sigversion))
-            ++nSigned;
+    if (provider.GetPubKey(address, pubkey)) {
+        return true;
+    }
+    // Look for pubkey in all partial sigs
+    const auto it = sigdata.signatures.find(address);
+    if (it != sigdata.signatures.end()) {
+        pubkey = it->second.first;
+        return true;
     }
-    return nSigned==nRequired;
+    return false;
+}
+
+static bool CreateSig(const BaseSignatureCreator& creator, SignatureData& sigdata, const SigningProvider& provider, std::vector<unsigned char>& sig_out, const CKeyID& keyid, const CScript& scriptcode, SigVersion sigversion)
+{
+    const auto it = sigdata.signatures.find(keyid);
+    if (it != sigdata.signatures.end()) {
+        sig_out = it->second.second;
+        return true;
+    }
+    if (creator.CreateSig(provider, sig_out, keyid, scriptcode, sigversion)) {
+        CPubKey pubkey;
+        GetPubKey(provider, sigdata, keyid, pubkey);
+        auto i = sigdata.signatures.emplace(keyid, SigPair(pubkey, sig_out));
+        assert(i.second);
+        return true;
+    }
+    return false;
 }
 
 /**
@@ -63,17 +87,17 @@ static bool SignN(const SigningProvider& provider, const std::vector<valtype>& m
  * Returns false if scriptPubKey could not be completely satisfied.
  */
 static bool SignStep(const SigningProvider& provider, const BaseSignatureCreator& creator, const CScript& scriptPubKey,
-                     std::vector<valtype>& ret, txnouttype& whichTypeRet, SigVersion sigversion)
+                     std::vector<valtype>& ret, txnouttype& whichTypeRet, SigVersion sigversion, SignatureData& sigdata)
 {
     CScript scriptRet;
     uint160 h160;
     ret.clear();
+    std::vector<unsigned char> sig;
 
     std::vector<valtype> vSolutions;
     if (!Solver(scriptPubKey, whichTypeRet, vSolutions))
         return false;
 
-    CKeyID keyID;
     switch (whichTypeRet)
     {
     case TX_NONSTANDARD:
@@ -81,37 +105,47 @@ static bool SignStep(const SigningProvider& provider, const BaseSignatureCreator
     case TX_WITNESS_UNKNOWN:
         return false;
     case TX_PUBKEY:
-        keyID = CPubKey(vSolutions[0]).GetID();
-        return Sign1(provider, keyID, creator, scriptPubKey, ret, sigversion);
-    case TX_PUBKEYHASH:
-        keyID = CKeyID(uint160(vSolutions[0]));
-        if (!Sign1(provider, keyID, creator, scriptPubKey, ret, sigversion))
-            return false;
-        else
-        {
-            CPubKey vch;
-            provider.GetPubKey(keyID, vch);
-            ret.push_back(ToByteVector(vch));
-        }
+        if (!CreateSig(creator, sigdata, provider, sig, CPubKey(vSolutions[0]).GetID(), scriptPubKey, sigversion)) return false;
+        ret.push_back(std::move(sig));
+        return true;
+    case TX_PUBKEYHASH: {
+        CKeyID keyID = CKeyID(uint160(vSolutions[0]));
+        if (!CreateSig(creator, sigdata, provider, sig, keyID, scriptPubKey, sigversion)) return false;
+        ret.push_back(std::move(sig));
+        CPubKey pubkey;
+        GetPubKey(provider, sigdata, keyID, pubkey);
+        ret.push_back(ToByteVector(pubkey));
         return true;
+    }
     case TX_SCRIPTHASH:
-        if (provider.GetCScript(uint160(vSolutions[0]), scriptRet)) {
+        if (GetCScript(provider, sigdata, uint160(vSolutions[0]), scriptRet)) {
             ret.push_back(std::vector<unsigned char>(scriptRet.begin(), scriptRet.end()));
             return true;
         }
         return false;
 
-    case TX_MULTISIG:
+    case TX_MULTISIG: {
+        size_t required = vSolutions.front()[0];
         ret.push_back(valtype()); // workaround CHECKMULTISIG bug
-        return (SignN(provider, vSolutions, creator, scriptPubKey, ret, sigversion));
-
+        for (size_t i = 1; i < vSolutions.size() - 1; ++i) {
+            CPubKey pubkey = CPubKey(vSolutions[i]);
+            if (ret.size() < required + 1 && CreateSig(creator, sigdata, provider, sig, pubkey.GetID(), scriptPubKey, sigversion)) {
+                ret.push_back(std::move(sig));
+            }
+        }
+        bool ok = ret.size() == required + 1;
+        for (size_t i = 0; i + ret.size() < required + 1; ++i) {
+            ret.push_back(valtype());
+        }
+        return ok;
+    }
     case TX_WITNESS_V0_KEYHASH:
         ret.push_back(vSolutions[0]);
         return true;
 
     case TX_WITNESS_V0_SCRIPTHASH:
         CRIPEMD160().Write(&vSolutions[0][0], vSolutions[0].size()).Finalize(h160.begin());
-        if (provider.GetCScript(h160, scriptRet)) {
+        if (GetCScript(provider, sigdata, h160, scriptRet)) {
             ret.push_back(std::vector<unsigned char>(scriptRet.begin(), scriptRet.end()));
             return true;
         }
@@ -139,9 +173,11 @@ static CScript PushAll(const std::vector<valtype>& values)
 
 bool ProduceSignature(const SigningProvider& provider, const BaseSignatureCreator& creator, const CScript& fromPubKey, SignatureData& sigdata)
 {
+    if (sigdata.complete) return true;
+
     std::vector<valtype> result;
     txnouttype whichType;
-    bool solved = SignStep(provider, creator, fromPubKey, result, whichType, SigVersion::BASE);
+    bool solved = SignStep(provider, creator, fromPubKey, result, whichType, SigVersion::BASE, sigdata);
     bool P2SH = false;
     CScript subscript;
     sigdata.scriptWitness.stack.clear();
@@ -152,7 +188,8 @@ bool ProduceSignature(const SigningProvider& provider, const BaseSignatureCreato
         // the final scriptSig is the signatures from that
         // and then the serialized subscript:
         subscript = CScript(result[0].begin(), result[0].end());
-        solved = solved && SignStep(provider, creator, subscript, result, whichType, SigVersion::BASE) && whichType != TX_SCRIPTHASH;
+        sigdata.redeem_script = subscript;
+        solved = solved && SignStep(provider, creator, subscript, result, whichType, SigVersion::BASE, sigdata) && whichType != TX_SCRIPTHASH;
         P2SH = true;
     }
 
@@ -161,15 +198,16 @@ bool ProduceSignature(const SigningProvider& provider, const BaseSignatureCreato
         CScript witnessscript;
         witnessscript << OP_DUP << OP_HASH160 << ToByteVector(result[0]) << OP_EQUALVERIFY << OP_CHECKSIG;
         txnouttype subType;
-        solved = solved && SignStep(provider, creator, witnessscript, result, subType, SigVersion::WITNESS_V0);
+        solved = solved && SignStep(provider, creator, witnessscript, result, subType, SigVersion::WITNESS_V0, sigdata);
         sigdata.scriptWitness.stack = result;
         result.clear();
     }
     else if (solved && whichType == TX_WITNESS_V0_SCRIPTHASH)
     {
         CScript witnessscript(result[0].begin(), result[0].end());
+        sigdata.witness_script = witnessscript;
         txnouttype subType;
-        solved = solved && SignStep(provider, creator, witnessscript, result, subType, SigVersion::WITNESS_V0) && subType != TX_SCRIPTHASH && subType != TX_WITNESS_V0_SCRIPTHASH && subType != TX_WITNESS_V0_KEYHASH;
+        solved = solved && SignStep(provider, creator, witnessscript, result, subType, SigVersion::WITNESS_V0, sigdata) && subType != TX_SCRIPTHASH && subType != TX_WITNESS_V0_SCRIPTHASH && subType != TX_WITNESS_V0_KEYHASH;
         result.push_back(std::vector<unsigned char>(witnessscript.begin(), witnessscript.end()));
         sigdata.scriptWitness.stack = result;
         result.clear();
@@ -181,99 +219,29 @@ bool ProduceSignature(const SigningProvider& provider, const BaseSignatureCreato
     sigdata.scriptSig = PushAll(result);
 
     // Test solution
-    return solved && VerifyScript(sigdata.scriptSig, fromPubKey, &sigdata.scriptWitness, STANDARD_SCRIPT_VERIFY_FLAGS, creator.Checker());
-}
-
-SignatureData DataFromTransaction(const CMutableTransaction& tx, unsigned int nIn)
-{
-    SignatureData data;
-    assert(tx.vin.size() > nIn);
-    data.scriptSig = tx.vin[nIn].scriptSig;
-    data.scriptWitness = tx.vin[nIn].scriptWitness;
-    return data;
+    sigdata.complete = solved && VerifyScript(sigdata.scriptSig, fromPubKey, &sigdata.scriptWitness, STANDARD_SCRIPT_VERIFY_FLAGS, creator.Checker());
+    return sigdata.complete;
 }
 
-void UpdateInput(CTxIn& input, const SignatureData& data)
+class SignatureExtractorChecker final : public BaseSignatureChecker
 {
-    input.scriptSig = data.scriptSig;
-    input.scriptWitness = data.scriptWitness;
-}
+private:
+    SignatureData& sigdata;
+    BaseSignatureChecker& checker;
 
-bool SignSignature(const SigningProvider &provider, const CScript& fromPubKey, CMutableTransaction& txTo, unsigned int nIn, const CAmount& amount, int nHashType)
-{
-    assert(nIn < txTo.vin.size());
-
-    MutableTransactionSignatureCreator creator(&txTo, nIn, amount, nHashType);
-
-    SignatureData sigdata;
-    bool ret = ProduceSignature(provider, creator, fromPubKey, sigdata);
-    UpdateInput(txTo.vin.at(nIn), sigdata);
-    return ret;
-}
-
-bool SignSignature(const SigningProvider &provider, const CTransaction& txFrom, CMutableTransaction& txTo, unsigned int nIn, int nHashType)
-{
-    assert(nIn < txTo.vin.size());
-    CTxIn& txin = txTo.vin[nIn];
-    assert(txin.prevout.n < txFrom.vout.size());
-    const CTxOut& txout = txFrom.vout[txin.prevout.n];
-
-    return SignSignature(provider, txout.scriptPubKey, txTo, nIn, txout.nValue, nHashType);
-}
+public:
+    SignatureExtractorChecker(SignatureData& sigdata, BaseSignatureChecker& checker) : sigdata(sigdata), checker(checker) {}
+    bool CheckSig(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override;
+};
 
-static std::vector<valtype> CombineMultisig(const CScript& scriptPubKey, const BaseSignatureChecker& checker,
-                               const std::vector<valtype>& vSolutions,
-                               const std::vector<valtype>& sigs1, const std::vector<valtype>& sigs2, SigVersion sigversion)
+bool SignatureExtractorChecker::CheckSig(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const
 {
-    // Combine all the signatures we've got:
-    std::set<valtype> allsigs;
-    for (const valtype& v : sigs1)
-    {
-        if (!v.empty())
-            allsigs.insert(v);
-    }
-    for (const valtype& v : sigs2)
-    {
-        if (!v.empty())
-            allsigs.insert(v);
-    }
-
-    // Build a map of pubkey -> signature by matching sigs to pubkeys:
-    assert(vSolutions.size() > 1);
-    unsigned int nSigsRequired = vSolutions.front()[0];
-    unsigned int nPubKeys = vSolutions.size()-2;
-    std::map<valtype, valtype> sigs;
-    for (const valtype& sig : allsigs)
-    {
-        for (unsigned int i = 0; i < nPubKeys; i++)
-        {
-            const valtype& pubkey = vSolutions[i+1];
-            if (sigs.count(pubkey))
-                continue; // Already got a sig for this pubkey
-
-            if (checker.CheckSig(sig, pubkey, scriptPubKey, sigversion))
-            {
-                sigs[pubkey] = sig;
-                break;
-            }
-        }
-    }
-    // Now build a merged CScript:
-    unsigned int nSigsHave = 0;
-    std::vector<valtype> result; result.push_back(valtype()); // pop-one-too-many workaround
-    for (unsigned int i = 0; i < nPubKeys && nSigsHave < nSigsRequired; i++)
-    {
-        if (sigs.count(vSolutions[i+1]))
-        {
-            result.push_back(sigs[vSolutions[i+1]]);
-            ++nSigsHave;
-        }
+    if (checker.CheckSig(scriptSig, vchPubKey, scriptCode, sigversion)) {
+        CPubKey pubkey(vchPubKey);
+        sigdata.signatures.emplace(pubkey.GetID(), SigPair(pubkey, scriptSig));
+        return true;
     }
-    // Fill any missing with OP_0:
-    for (unsigned int i = nSigsHave; i < nSigsRequired; i++)
-        result.push_back(valtype());
-
-    return result;
+    return false;
 }
 
 namespace
@@ -298,89 +266,115 @@ struct Stacks
 };
 }
 
-static Stacks CombineSignatures(const CScript& scriptPubKey, const BaseSignatureChecker& checker,
-                                 const txnouttype txType, const std::vector<valtype>& vSolutions,
-                                 Stacks sigs1, Stacks sigs2, SigVersion sigversion)
+// Extracts signatures and scripts from incomplete scriptSigs. Please do not extend this, use PSBT instead
+SignatureData DataFromTransaction(const CMutableTransaction& tx, unsigned int nIn, const CTxOut& txout)
 {
-    switch (txType)
-    {
-    case TX_NONSTANDARD:
-    case TX_NULL_DATA:
-    case TX_WITNESS_UNKNOWN:
-        // Don't know anything about this, assume bigger one is correct:
-        if (sigs1.script.size() >= sigs2.script.size())
-            return sigs1;
-        return sigs2;
-    case TX_PUBKEY:
-    case TX_PUBKEYHASH:
-        // Signatures are bigger than placeholders or empty scripts:
-        if (sigs1.script.empty() || sigs1.script[0].empty())
-            return sigs2;
-        return sigs1;
-    case TX_WITNESS_V0_KEYHASH:
-        // Signatures are bigger than placeholders or empty scripts:
-        if (sigs1.witness.empty() || sigs1.witness[0].empty())
-            return sigs2;
-        return sigs1;
-    case TX_SCRIPTHASH:
-        if (sigs1.script.empty() || sigs1.script.back().empty())
-            return sigs2;
-        else if (sigs2.script.empty() || sigs2.script.back().empty())
-            return sigs1;
-        else
-        {
-            // Recur to combine:
-            valtype spk = sigs1.script.back();
-            CScript pubKey2(spk.begin(), spk.end());
-
-            txnouttype txType2;
-            std::vector<std::vector<unsigned char> > vSolutions2;
-            Solver(pubKey2, txType2, vSolutions2);
-            sigs1.script.pop_back();
-            sigs2.script.pop_back();
-            Stacks result = CombineSignatures(pubKey2, checker, txType2, vSolutions2, sigs1, sigs2, sigversion);
-            result.script.push_back(spk);
-            return result;
-        }
-    case TX_MULTISIG:
-        return Stacks(CombineMultisig(scriptPubKey, checker, vSolutions, sigs1.script, sigs2.script, sigversion));
-    case TX_WITNESS_V0_SCRIPTHASH:
-        if (sigs1.witness.empty() || sigs1.witness.back().empty())
-            return sigs2;
-        else if (sigs2.witness.empty() || sigs2.witness.back().empty())
-            return sigs1;
-        else
-        {
-            // Recur to combine:
-            CScript pubKey2(sigs1.witness.back().begin(), sigs1.witness.back().end());
-            txnouttype txType2;
-            std::vector<valtype> vSolutions2;
-            Solver(pubKey2, txType2, vSolutions2);
-            sigs1.witness.pop_back();
-            sigs1.script = sigs1.witness;
-            sigs1.witness.clear();
-            sigs2.witness.pop_back();
-            sigs2.script = sigs2.witness;
-            sigs2.witness.clear();
-            Stacks result = CombineSignatures(pubKey2, checker, txType2, vSolutions2, sigs1, sigs2, SigVersion::WITNESS_V0);
-            result.witness = result.script;
-            result.script.clear();
-            result.witness.push_back(valtype(pubKey2.begin(), pubKey2.end()));
-            return result;
+    SignatureData data;
+    assert(tx.vin.size() > nIn);
+    data.scriptSig = tx.vin[nIn].scriptSig;
+    data.scriptWitness = tx.vin[nIn].scriptWitness;
+    Stacks stack(data);
+
+    // Get signatures
+    MutableTransactionSignatureChecker tx_checker(&tx, nIn, txout.nValue);
+    SignatureExtractorChecker extractor_checker(data, tx_checker);
+    if (VerifyScript(data.scriptSig, txout.scriptPubKey, &data.scriptWitness, STANDARD_SCRIPT_VERIFY_FLAGS, extractor_checker)) {
+        data.complete = true;
+        return data;
+    }
+
+    // Get scripts
+    txnouttype script_type;
+    std::vector<std::vector<unsigned char>> solutions;
+    Solver(txout.scriptPubKey, script_type, solutions);
+    SigVersion sigversion = SigVersion::BASE;
+    CScript next_script = txout.scriptPubKey;
+
+    if (script_type == TX_SCRIPTHASH && !stack.script.empty() && !stack.script.back().empty()) {
+        // Get the redeemScript
+        CScript redeem_script(stack.script.back().begin(), stack.script.back().end());
+        data.redeem_script = redeem_script;
+        next_script = std::move(redeem_script);
+
+        // Get redeemScript type
+        Solver(next_script, script_type, solutions);
+        stack.script.pop_back();
+    }
+    if (script_type == TX_WITNESS_V0_SCRIPTHASH && !stack.witness.empty() && !stack.witness.back().empty()) {
+        // Get the witnessScript
+        CScript witness_script(stack.witness.back().begin(), stack.witness.back().end());
+        data.witness_script = witness_script;
+        next_script = std::move(witness_script);
+
+        // Get witnessScript type
+        Solver(next_script, script_type, solutions);
+        stack.witness.pop_back();
+        stack.script = std::move(stack.witness);
+        stack.witness.clear();
+        sigversion = SigVersion::WITNESS_V0;
+    }
+    if (script_type == TX_MULTISIG && !stack.script.empty()) {
+        // Build a map of pubkey -> signature by matching sigs to pubkeys:
+        assert(solutions.size() > 1);
+        unsigned int num_pubkeys = solutions.size()-2;
+        unsigned int last_success_key = 0;
+        for (const valtype& sig : stack.script) {
+            for (unsigned int i = last_success_key; i < num_pubkeys; ++i) {
+                const valtype& pubkey = solutions[i+1];
+                // We either have a signature for this pubkey, or we have found a signature and it is valid
+                if (data.signatures.count(CPubKey(pubkey).GetID()) || extractor_checker.CheckSig(sig, pubkey, next_script, sigversion)) {
+                    last_success_key = i + 1;
+                    break;
+                }
+            }
         }
-    default:
-        return Stacks();
     }
+
+    return data;
+}
+
+void UpdateInput(CTxIn& input, const SignatureData& data)
+{
+    input.scriptSig = data.scriptSig;
+    input.scriptWitness = data.scriptWitness;
+}
+
+void SignatureData::MergeSignatureData(SignatureData sigdata)
+{
+    if (complete) return;
+    if (sigdata.complete) {
+        *this = std::move(sigdata);
+        return;
+    }
+    if (redeem_script.empty() && !sigdata.redeem_script.empty()) {
+        redeem_script = sigdata.redeem_script;
+    }
+    if (witness_script.empty() && !sigdata.witness_script.empty()) {
+        witness_script = sigdata.witness_script;
+    }
+    signatures.insert(std::make_move_iterator(sigdata.signatures.begin()), std::make_move_iterator(sigdata.signatures.end()));
+}
+
+bool SignSignature(const SigningProvider &provider, const CScript& fromPubKey, CMutableTransaction& txTo, unsigned int nIn, const CAmount& amount, int nHashType)
+{
+    assert(nIn < txTo.vin.size());
+
+    MutableTransactionSignatureCreator creator(&txTo, nIn, amount, nHashType);
+
+    SignatureData sigdata;
+    bool ret = ProduceSignature(provider, creator, fromPubKey, sigdata);
+    UpdateInput(txTo.vin.at(nIn), sigdata);
+    return ret;
 }
 
-SignatureData CombineSignatures(const CScript& scriptPubKey, const BaseSignatureChecker& checker,
-                          const SignatureData& scriptSig1, const SignatureData& scriptSig2)
+bool SignSignature(const SigningProvider &provider, const CTransaction& txFrom, CMutableTransaction& txTo, unsigned int nIn, int nHashType)
 {
-    txnouttype txType;
-    std::vector<std::vector<unsigned char> > vSolutions;
-    Solver(scriptPubKey, txType, vSolutions);
+    assert(nIn < txTo.vin.size());
+    CTxIn& txin = txTo.vin[nIn];
+    assert(txin.prevout.n < txFrom.vout.size());
+    const CTxOut& txout = txFrom.vout[txin.prevout.n];
 
-    return CombineSignatures(scriptPubKey, checker, txType, vSolutions, Stacks(scriptSig1), Stacks(scriptSig2), SigVersion::BASE).Output();
+    return SignSignature(provider, txout.scriptPubKey, txTo, nIn, txout.nValue, nHashType);
 }
 
 namespace {
@@ -416,6 +410,7 @@ public:
 }
 
 const BaseSignatureCreator& DUMMY_SIGNATURE_CREATOR = DummySignatureCreator();
+const SigningProvider& DUMMY_SIGNING_PROVIDER = SigningProvider();
 
 bool IsSolvable(const SigningProvider& provider, const CScript& script)
 {