X-Git-Url: https://git.novaco.in/?a=blobdiff_plain;f=src%2Fscript.cpp;h=34c02cfe01007475890f00d99a5e90f1cee6c0f4;hb=21c897e170c14da4754fb699d701b9980f092959;hp=660023ef48a8033dfad2f3ab7ad552f674006f39;hpb=1d8c7a9557d596d4c7edee801a724db7a908bce5;p=novacoin.git diff --git a/src/script.cpp b/src/script.cpp index 660023e..34c02cf 100644 --- a/src/script.cpp +++ b/src/script.cpp @@ -1,8 +1,9 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2012 The Bitcoin developers // Distributed under the MIT/X11 software license, see the accompanying -// file license.txt or http://www.opensource.org/licenses/mit-license.php. +// file COPYING or http://www.opensource.org/licenses/mit-license.php. #include +#include using namespace std; using namespace boost; @@ -12,12 +13,11 @@ using namespace boost; #include "bignum.h" #include "key.h" #include "main.h" +#include "sync.h" +#include "util.h" bool CheckSig(vector vchSig, vector vchPubKey, CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType); - - -typedef vector valtype; static const valtype vchFalse(0); static const valtype vchZero(0); static const valtype vchTrue(1, 1); @@ -51,12 +51,29 @@ bool CastToBool(const valtype& vch) return false; } +// +// WARNING: This does not work as expected for signed integers; the sign-bit +// is left in place as the integer is zero-extended. The correct behavior +// would be to move the most significant bit of the last byte during the +// resize process. MakeSameSize() is currently only used by the disabled +// opcodes OP_AND, OP_OR, and OP_XOR. +// void MakeSameSize(valtype& vch1, valtype& vch2) { // Lengthen the shorter one if (vch1.size() < vch2.size()) + // PATCH: + // +unsigned char msb = vch1[vch1.size()-1]; + // +vch1[vch1.size()-1] &= 0x7f; + // vch1.resize(vch2.size(), 0); + // +vch1[vch1.size()-1] = msb; vch1.resize(vch2.size(), 0); if (vch2.size() < vch1.size()) + // PATCH: + // +unsigned char msb = vch2[vch2.size()-1]; + // +vch2[vch2.size()-1] &= 0x7f; + // vch2.resize(vch1.size(), 0); + // +vch2[vch2.size()-1] = msb; vch2.resize(vch1.size(), 0); } @@ -660,6 +677,11 @@ bool EvalScript(vector >& stack, const CScript& script, co } break; + // + // WARNING: These disabled opcodes exhibit unexpected behavior + // when used on signed integers due to a bug in MakeSameSize() + // [see definition of MakeSameSize() above]. + // case OP_AND: case OP_OR: case OP_XOR: @@ -669,7 +691,7 @@ bool EvalScript(vector >& stack, const CScript& script, co return false; valtype& vch1 = stacktop(-2); valtype& vch2 = stacktop(-1); - MakeSameSize(vch1, vch2); + MakeSameSize(vch1, vch2); // <-- NOT SAFE FOR SIGNED VALUES if (opcode == OP_AND) { for (unsigned int i = 0; i < vch1.size(); i++) @@ -939,8 +961,8 @@ bool EvalScript(vector >& stack, const CScript& script, co { // ([sig ...] num_of_signatures [pubkey ...] num_of_pubkeys -- bool) - unsigned int i = 1; - if (stack.size() < i) + int i = 1; + if ((int)stack.size() < i) return false; int nKeysCount = CastToBigNum(stacktop(-i)).getint(); @@ -951,7 +973,7 @@ bool EvalScript(vector >& stack, const CScript& script, co return false; int ikey = ++i; i += nKeysCount; - if (stack.size() < i) + if ((int)stack.size() < i) return false; int nSigsCount = CastToBigNum(stacktop(-i)).getint(); @@ -959,7 +981,7 @@ bool EvalScript(vector >& stack, const CScript& script, co return false; int isig = ++i; i += nSigsCount; - if (stack.size() < i) + if ((int)stack.size() < i) return false; // Subset of script starting at the most recent codeseparator @@ -1067,7 +1089,7 @@ uint256 SignatureHash(CScript scriptCode, const CTransaction& txTo, unsigned int } else if ((nHashType & 0x1f) == SIGHASH_SINGLE) { - // Only lockin the txout payee at same index as txin + // Only lock-in the txout payee at same index as txin unsigned int nOut = nIn; if (nOut >= txTmp.vout.size()) { @@ -1099,12 +1121,66 @@ uint256 SignatureHash(CScript scriptCode, const CTransaction& txTo, unsigned int } +// Valid signature cache, to avoid doing expensive ECDSA signature checking +// twice for every transaction (once when accepted into memory pool, and +// again when accepted into the block chain) + +class CSignatureCache +{ +private: + // sigdata_type is (signature hash, signature, public key): + typedef boost::tuple, std::vector > sigdata_type; + std::set< sigdata_type> setValid; + CCriticalSection cs_sigcache; + +public: + bool + Get(uint256 hash, const std::vector& vchSig, const std::vector& pubKey) + { + LOCK(cs_sigcache); + + sigdata_type k(hash, vchSig, pubKey); + std::set::iterator mi = setValid.find(k); + if (mi != setValid.end()) + return true; + return false; + } + + void Set(uint256 hash, const std::vector& vchSig, const std::vector& pubKey) + { + // DoS prevention: limit cache size to less than 10MB + // (~200 bytes per cache entry times 50,000 entries) + // Since there are a maximum of 20,000 signature operations per block + // 50,000 is a reasonable default. + int64 nMaxCacheSize = GetArg("-maxsigcachesize", 50000); + if (nMaxCacheSize <= 0) return; + + LOCK(cs_sigcache); + + while (static_cast(setValid.size()) > nMaxCacheSize) + { + // Evict a random entry. Random because that helps + // foil would-be DoS attackers who might try to pre-generate + // and re-use a set of valid signatures just-slightly-greater + // than our cache size. + uint256 randomHash = GetRandHash(); + std::vector unused; + std::set::iterator it = + setValid.lower_bound(sigdata_type(randomHash, unused, unused)); + if (it == setValid.end()) + it = setValid.begin(); + setValid.erase(*it); + } + + sigdata_type k(hash, vchSig, pubKey); + setValid.insert(k); + } +}; + bool CheckSig(vector vchSig, vector vchPubKey, CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType) { - CKey key; - if (!key.SetPubKey(vchPubKey)) - return false; + static CSignatureCache signatureCache; // Hash type is one byte tacked on to the end of the signature if (vchSig.empty()) @@ -1115,7 +1191,20 @@ bool CheckSig(vector vchSig, vector vchPubKey, CSc return false; vchSig.pop_back(); - return key.Verify(SignatureHash(scriptCode, txTo, nIn, nHashType), vchSig); + uint256 sighash = SignatureHash(scriptCode, txTo, nIn, nHashType); + + if (signatureCache.Get(sighash, vchSig, vchPubKey)) + return true; + + CKey key; + if (!key.SetPubKey(vchPubKey)) + return false; + + if (!key.Verify(sighash, vchSig)) + return false; + + signatureCache.Set(sighash, vchSig, vchPubKey); + return true; } @@ -1168,7 +1257,7 @@ bool Solver(const CScript& scriptPubKey, txnouttype& typeRet, vector& multisigdata, const CKeyStore& keystore, uint2 { int nSigned = 0; int nRequired = multisigdata.front()[0]; - for (vector::const_iterator it = multisigdata.begin()+1; it != multisigdata.begin()+multisigdata.size()-1; it++) + for (unsigned int i = 1; i < multisigdata.size()-1 && nSigned < nRequired; i++) { - const valtype& pubkey = *it; - CBitcoinAddress address; - address.SetPubKey(pubkey); - if (Sign1(address, keystore, hash, nHashType, scriptSigRet)) - { + const valtype& pubkey = multisigdata[i]; + CKeyID keyID = CPubKey(pubkey).GetID(); + if (Sign1(keyID, keystore, hash, nHashType, scriptSigRet)) ++nSigned; - if (nSigned == nRequired) break; - } } return nSigned==nRequired; } @@ -1278,7 +1363,7 @@ bool SignN(const vector& multisigdata, const CKeyStore& keystore, uint2 // 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 satisified. +// 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) @@ -1289,22 +1374,22 @@ bool Solver(const CKeyStore& keystore, const CScript& scriptPubKey, uint256 hash if (!Solver(scriptPubKey, whichTypeRet, vSolutions)) return false; - CBitcoinAddress address; + CKeyID keyID; switch (whichTypeRet) { case TX_NONSTANDARD: return false; case TX_PUBKEY: - address.SetPubKey(vSolutions[0]); - return Sign1(address, keystore, hash, nHashType, scriptSigRet); + keyID = CPubKey(vSolutions[0]).GetID(); + return Sign1(keyID, keystore, hash, nHashType, scriptSigRet); case TX_PUBKEYHASH: - address.SetHash160(uint160(vSolutions[0])); - if (!Sign1(address, keystore, hash, nHashType, scriptSigRet)) + keyID = CKeyID(uint160(vSolutions[0])); + if (!Sign1(keyID, keystore, hash, nHashType, scriptSigRet)) return false; else { - valtype vch; - keystore.GetPubKey(address, vch); + CPubKey vch; + keystore.GetPubKey(keyID, vch); scriptSigRet << vch; } return true; @@ -1365,14 +1450,30 @@ unsigned int HaveKeys(const vector& pubkeys, const CKeyStore& keystore) unsigned int nResult = 0; BOOST_FOREACH(const valtype& pubkey, pubkeys) { - CBitcoinAddress address; - address.SetPubKey(pubkey); - if (keystore.HaveKey(address)) + CKeyID keyID = CPubKey(pubkey).GetID(); + if (keystore.HaveKey(keyID)) ++nResult; } return nResult; } + +class CKeyStoreIsMineVisitor : public boost::static_visitor +{ +private: + const CKeyStore *keystore; +public: + CKeyStoreIsMineVisitor(const CKeyStore *keystoreIn) : keystore(keystoreIn) { } + bool operator()(const CNoDestination &dest) const { return false; } + bool operator()(const CKeyID &keyID) const { return keystore->HaveKey(keyID); } + bool operator()(const CScriptID &scriptID) const { return keystore->HaveCScript(scriptID); } +}; + +bool IsMine(const CKeyStore &keystore, const CTxDestination &dest) +{ + return boost::apply_visitor(CKeyStoreIsMineVisitor(&keystore), dest); +} + bool IsMine(const CKeyStore &keystore, const CScript& scriptPubKey) { vector vSolutions; @@ -1380,21 +1481,21 @@ bool IsMine(const CKeyStore &keystore, const CScript& scriptPubKey) if (!Solver(scriptPubKey, whichType, vSolutions)) return false; - CBitcoinAddress address; + CKeyID keyID; switch (whichType) { case TX_NONSTANDARD: return false; case TX_PUBKEY: - address.SetPubKey(vSolutions[0]); - return keystore.HaveKey(address); + keyID = CPubKey(vSolutions[0]).GetID(); + return keystore.HaveKey(keyID); case TX_PUBKEYHASH: - address.SetHash160(uint160(vSolutions[0])); - return keystore.HaveKey(address); + keyID = CKeyID(uint160(vSolutions[0])); + return keystore.HaveKey(keyID); case TX_SCRIPTHASH: { CScript subscript; - if (!keystore.GetCScript(uint160(vSolutions[0]), subscript)) + if (!keystore.GetCScript(CScriptID(uint160(vSolutions[0])), subscript)) return false; return IsMine(keystore, subscript); } @@ -1412,7 +1513,7 @@ bool IsMine(const CKeyStore &keystore, const CScript& scriptPubKey) return false; } -bool ExtractAddress(const CScript& scriptPubKey, CBitcoinAddress& addressRet) +bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet) { vector vSolutions; txnouttype whichType; @@ -1421,24 +1522,61 @@ bool ExtractAddress(const CScript& scriptPubKey, CBitcoinAddress& addressRet) if (whichType == TX_PUBKEY) { - addressRet.SetPubKey(vSolutions[0]); + addressRet = CPubKey(vSolutions[0]).GetID(); return true; } else if (whichType == TX_PUBKEYHASH) { - addressRet.SetHash160(uint160(vSolutions[0])); + addressRet = CKeyID(uint160(vSolutions[0])); return true; } else if (whichType == TX_SCRIPTHASH) { - addressRet.SetScriptHash160(uint160(vSolutions[0])); + addressRet = CScriptID(uint160(vSolutions[0])); return true; } // Multisig txns have more than one address... return false; } -bool ExtractAddresses(const CScript& scriptPubKey, txnouttype& typeRet, vector& addressRet, int& nRequiredRet) +class CAffectedKeysVisitor : public boost::static_visitor { +private: + const CKeyStore &keystore; + std::vector &vKeys; + +public: + CAffectedKeysVisitor(const CKeyStore &keystoreIn, std::vector &vKeysIn) : keystore(keystoreIn), vKeys(vKeysIn) {} + + void Process(const CScript &script) { + txnouttype type; + std::vector vDest; + int nRequired; + if (ExtractDestinations(script, type, vDest, nRequired)) { + BOOST_FOREACH(const CTxDestination &dest, vDest) + boost::apply_visitor(*this, dest); + } + } + + void operator()(const CKeyID &keyId) { + if (keystore.HaveKey(keyId)) + vKeys.push_back(keyId); + } + + void operator()(const CScriptID &scriptId) { + CScript script; + if (keystore.GetCScript(scriptId, script)) + Process(script); + } + + void operator()(const CNoDestination &none) {} +}; + + +void ExtractAffectedKeys(const CKeyStore &keystore, const CScript& scriptPubKey, std::vector &vKeys) { + CAffectedKeysVisitor(keystore, vKeys).Process(scriptPubKey); +} + +bool ExtractDestinations(const CScript& scriptPubKey, txnouttype& typeRet, vector& addressRet, int& nRequiredRet) { addressRet.clear(); typeRet = TX_NONSTANDARD; @@ -1451,21 +1589,16 @@ bool ExtractAddresses(const CScript& scriptPubKey, txnouttype& typeRet, vector(subscript); // Append serialized subscript + 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(subscript); + if (!fSolved) return false; } // Test solution - if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, true, 0)) - return false; - - return true; + return VerifyScript(txin.scriptSig, fromPubKey, txTo, nIn, true, 0); } +bool SignSignature(const CKeyStore &keystore, const CTransaction& txFrom, CTransaction& txTo, unsigned int nIn, int nHashType) +{ + assert(nIn < txTo.vin.size()); + CTxIn& txin = txTo.vin[nIn]; + assert(txin.prevout.n < txFrom.vout.size()); + assert(txin.prevout.hash == txFrom.GetHash()); + const CTxOut& txout = txFrom.vout[txin.prevout.n]; + + return SignSignature(keystore, txout.scriptPubKey, txTo, nIn, nHashType); +} bool VerifySignature(const CTransaction& txFrom, const CTransaction& txTo, unsigned int nIn, bool fValidatePayToScriptHash, int nHashType) { @@ -1560,10 +1699,129 @@ bool VerifySignature(const CTransaction& txFrom, const CTransaction& txTo, unsig if (txin.prevout.hash != txFrom.GetHash()) return false; - if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, fValidatePayToScriptHash, nHashType)) - return false; + return VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, fValidatePayToScriptHash, nHashType); +} - return true; +static CScript PushAll(const vector& values) +{ + CScript result; + BOOST_FOREACH(const valtype& v, values) + result << v; + return result; +} + +static CScript CombineMultisig(CScript scriptPubKey, const CTransaction& txTo, unsigned int nIn, + const vector& vSolutions, + vector& sigs1, vector& sigs2) +{ + // Combine all the signatures we've got: + set 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 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 (CheckSig(sig, pubkey, scriptPubKey, txTo, nIn, 0)) + { + 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(CScript scriptPubKey, const CTransaction& txTo, unsigned int nIn, + const txnouttype txType, const vector& vSolutions, + vector& sigs1, vector& sigs2) +{ + switch (txType) + { + case TX_NONSTANDARD: + // 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 > 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(CScript scriptPubKey, const CTransaction& txTo, unsigned int nIn, + const CScript& scriptSig1, const CScript& scriptSig2) +{ + txnouttype txType; + vector > vSolutions; + Solver(scriptPubKey, txType, vSolutions); + + vector stack1; + EvalScript(stack1, scriptSig1, CTransaction(), 0, 0); + vector stack2; + EvalScript(stack2, scriptSig2, CTransaction(), 0, 0); + + return CombineSignatures(scriptPubKey, txTo, nIn, txType, vSolutions, stack1, stack2); } unsigned int CScript::GetSigOpCount(bool fAccurate) const @@ -1609,7 +1867,7 @@ unsigned int CScript::GetSigOpCount(const CScript& scriptSig) const return 0; } - /// ... and return it's opcount: + /// ... and return its opcount: CScript subscript(data.begin(), data.end()); return subscript.GetSigOpCount(true); } @@ -1623,13 +1881,34 @@ bool CScript::IsPayToScriptHash() const this->at(22) == OP_EQUAL); } -void CScript::SetBitcoinAddress(const CBitcoinAddress& address) +class CScriptVisitor : public boost::static_visitor { - this->clear(); - if (address.IsScript()) - *this << OP_HASH160 << address.GetHash160() << OP_EQUAL; - else - *this << OP_DUP << OP_HASH160 << address.GetHash160() << OP_EQUALVERIFY << OP_CHECKSIG; +private: + CScript *script; +public: + CScriptVisitor(CScript *scriptin) { script = scriptin; } + + bool operator()(const CNoDestination &dest) const { + script->clear(); + return false; + } + + bool operator()(const CKeyID &keyID) const { + script->clear(); + *script << OP_DUP << OP_HASH160 << keyID << OP_EQUALVERIFY << OP_CHECKSIG; + return true; + } + + bool operator()(const CScriptID &scriptID) const { + script->clear(); + *script << OP_HASH160 << scriptID << OP_EQUAL; + return true; + } +}; + +void CScript::SetDestination(const CTxDestination& dest) +{ + boost::apply_visitor(CScriptVisitor(this), dest); } void CScript::SetMultisig(int nRequired, const std::vector& keys) @@ -1641,11 +1920,3 @@ void CScript::SetMultisig(int nRequired, const std::vector& keys) *this << key.GetPubKey(); *this << EncodeOP_N(keys.size()) << OP_CHECKMULTISIG; } - -void CScript::SetPayToScriptHash(const CScript& subscript) -{ - assert(!subscript.empty()); - uint160 subscriptHash = Hash160(subscript); - this->clear(); - *this << OP_HASH160 << subscriptHash << OP_EQUAL; -}