text: // Copyright (c) 2009-2010 Satoshi Nakamoto
  // Copyright (c) 2009-2014 The Bitcoin developers
  // Copyright (c) 2016-2017 The PIVX developers
  // Copyright (c) 2017-2018 The HUZU developers
  // Copyright (c) 2018-2019 The ZIJA developers
  // Copyright (c) 2019 The CGEN developers
  // Distributed under the MIT software license, see the accompanying
  // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  
  #include "script/sign.h"
  
  #include "primitives/transaction.h"
  #include "key.h"
  #include "keystore.h"
  #include "script/standard.h"
  #include "uint256.h"
  #include "util.h"
  
  #include <boost/foreach.hpp>
  
  using namespace std;
  
  typedef vector<unsigned char> valtype;
  
  bool Sign1(const CKeyID& address, const CKeyStore& keystore, uint256 hash, int nHashType, CScript& scriptSigRet)
  {
      CKey key;
      if (!keystore.GetKey(address, key))
          return false;
  
      vector<unsigned char> vchSig;
      if (!key.Sign(hash, vchSig))
          return false;
      vchSig.push_back((unsigned char)nHashType);
      scriptSigRet << vchSig;
  
      return true;
  }
  
  bool SignN(const vector<valtype>& multisigdata, const CKeyStore& keystore, uint256 hash, int nHashType, CScript& scriptSigRet)
  {
      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(keyID, keystore, hash, nHashType, scriptSigRet))
              ++nSigned;
      }
      return nSigned==nRequired;
  }
  
  /**
   * Sign scriptPubKey with private keys stored in keystore, given transaction hash and hash type.
   * Signatures are returned in scriptSigRet (or returns false if scriptPubKey can't be signed),
   * unless whichTypeRet is TX_SCRIPTHASH, in which case scriptSigRet is the redemption script.
   * Returns false if scriptPubKey could not be completely satisfied.
   */
  bool Solver(const CKeyStore& keystore, const CScript& scriptPubKey, uint256 hash, int nHashType,
                    CScript& scriptSigRet, txnouttype& whichTypeRet)
  {
      scriptSigRet.clear();
  
      vector<valtype> vSolutions;
      if (!Solver(scriptPubKey, whichTypeRet, vSolutions))
      {
          LogPrintf("*** solver solver failed \n");
          return false;
      }
  
      CKeyID keyID;
      switch (whichTypeRet)
      {
      case TX_NONSTANDARD:
      case TX_NULL_DATA:
      {
          LogPrintf("*** null data \n");
          return false;
      }
      case TX_ZEROCOINMINT:
          return false;
      case TX_PUBKEY:
          keyID = CPubKey(vSolutions[0]).GetID();
          if(!Sign1(keyID, keystore, hash, nHashType, scriptSigRet))
          {
              LogPrintf("*** Sign1 failed \n");
              return false;
          }
          return true;
      case TX_PUBKEYHASH:
          keyID = CKeyID(uint160(vSolutions[0]));
          if (!Sign1(keyID, keystore, hash, nHashType, scriptSigRet))
          {
              LogPrintf("*** solver failed to sign \n");
              return false;
          }
          else
          {
              CPubKey vch;
              keystore.GetPubKey(keyID, vch);
              scriptSigRet << ToByteVector(vch);
          }
          return true;
      case TX_SCRIPTHASH:
          return keystore.GetCScript(uint160(vSolutions[0]), scriptSigRet);
  
      case TX_MULTISIG:
          scriptSigRet << OP_0; // workaround CHECKMULTISIG bug
          return (SignN(vSolutions, keystore, hash, nHashType, scriptSigRet));
      }
      LogPrintf("*** solver no case met \n");
      return false;
  }
  
  bool SignSignature(const CKeyStore &keystore, const CScript& fromPubKey, CMutableTransaction& txTo, unsigned int nIn, int nHashType)
  {
      assert(nIn < txTo.vin.size());
      CTxIn& txin = txTo.vin[nIn];
  
      // Leave out the signature from the hash, since a signature can't sign itself.
      // The checksig op will also drop the signatures from its hash.
      uint256 hash = SignatureHash(fromPubKey, txTo, nIn, nHashType);
  
      txnouttype whichType;
      if (!Solver(keystore, fromPubKey, hash, nHashType, txin.scriptSig, whichType))
          return false;
  
      if (whichType == TX_SCRIPTHASH)
      {
          // Solver returns the subscript that need to be evaluated;
          // the final scriptSig is the signatures from that
          // and then the serialized subscript:
          CScript subscript = txin.scriptSig;
  
          // Recompute txn hash using subscript in place of scriptPubKey:
          uint256 hash2 = SignatureHash(subscript, txTo, nIn, nHashType);
  
          txnouttype subType;
          bool fSolved =
              Solver(keystore, subscript, hash2, nHashType, txin.scriptSig, subType) && subType != TX_SCRIPTHASH;
          // Append serialized subscript whether or not it is completely signed:
          txin.scriptSig << static_cast<valtype>(subscript);
          if (!fSolved) return false;
      }
  
      // Test solution
      return VerifyScript(txin.scriptSig, fromPubKey, STANDARD_SCRIPT_VERIFY_FLAGS, MutableTransactionSignatureChecker(&txTo, nIn));
  }
  
  bool SignSignature(const CKeyStore &keystore, 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(keystore, txout.scriptPubKey, txTo, nIn, nHashType);
  }
  
  static CScript PushAll(const vector<valtype>& values)
  {
      CScript result;
      BOOST_FOREACH(const valtype& v, values)
          result << v;
      return result;
  }
  
  static CScript CombineMultisig(const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn,
                                 const vector<valtype>& vSolutions,
                                 const vector<valtype>& sigs1, const vector<valtype>& sigs2)
  {
      // Combine all the signatures we've got:
      set<valtype> allsigs;
      BOOST_FOREACH(const valtype& v, sigs1)
      {
          if (!v.empty())
              allsigs.insert(v);
      }
      BOOST_FOREACH(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;
      map<valtype, valtype> sigs;
      BOOST_FOREACH(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 (TransactionSignatureChecker(&txTo, nIn).CheckSig(sig, pubkey, scriptPubKey))
              {
                  sigs[pubkey] = sig;
                  break;
              }
          }
      }
      // Now build a merged CScript:
      unsigned int nSigsHave = 0;
      CScript result; result << OP_0; // pop-one-too-many workaround
      for (unsigned int i = 0; i < nPubKeys && nSigsHave < nSigsRequired; i++)
      {
          if (sigs.count(vSolutions[i+1]))
          {
              result << sigs[vSolutions[i+1]];
              ++nSigsHave;
          }
      }
      // Fill any missing with OP_0:
      for (unsigned int i = nSigsHave; i < nSigsRequired; i++)
          result << OP_0;
  
      return result;
  }
  
  static CScript CombineSignatures(const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn,
                                   const txnouttype txType, const vector<valtype>& vSolutions,
                                   vector<valtype>& sigs1, vector<valtype>& sigs2)
  {
      switch (txType)
      {
      case TX_NONSTANDARD:
      case TX_NULL_DATA:
      case TX_ZEROCOINMINT:
          // Don't know anything about this, assume bigger one is correct:
          if (sigs1.size() >= sigs2.size())
              return PushAll(sigs1);
          return PushAll(sigs2);
      case TX_PUBKEY:
      case TX_PUBKEYHASH:
          // Signatures are bigger than placeholders or empty scripts:
          if (sigs1.empty() || sigs1[0].empty())
              return PushAll(sigs2);
          return PushAll(sigs1);
      case TX_SCRIPTHASH:
          if (sigs1.empty() || sigs1.back().empty())
              return PushAll(sigs2);
          else if (sigs2.empty() || sigs2.back().empty())
              return PushAll(sigs1);
          else
          {
              // Recur to combine:
              valtype spk = sigs1.back();
              CScript pubKey2(spk.begin(), spk.end());
  
              txnouttype txType2;
              vector<vector<unsigned char> > vSolutions2;
              Solver(pubKey2, txType2, vSolutions2);
              sigs1.pop_back();
              sigs2.pop_back();
              CScript result = CombineSignatures(pubKey2, txTo, nIn, txType2, vSolutions2, sigs1, sigs2);
              result << spk;
              return result;
          }
      case TX_MULTISIG:
          return CombineMultisig(scriptPubKey, txTo, nIn, vSolutions, sigs1, sigs2);
      }
  
      return CScript();
  }
  
  CScript CombineSignatures(const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn,
                            const CScript& scriptSig1, const CScript& scriptSig2)
  {
      txnouttype txType;
      vector<vector<unsigned char> > vSolutions;
      Solver(scriptPubKey, txType, vSolutions);
  
      vector<valtype> stack1;
      EvalScript(stack1, scriptSig1, SCRIPT_VERIFY_STRICTENC, BaseSignatureChecker());
      vector<valtype> stack2;
      EvalScript(stack2, scriptSig2, SCRIPT_VERIFY_STRICTENC, BaseSignatureChecker());
  
      return CombineSignatures(scriptPubKey, txTo, nIn, txType, vSolutions, stack1, stack2);
  }
  