Merge branch 'optimize'

6 files changed, 544 insertions, 286 deletions

diff --git a/src/key.cpp b/src/key.cpp
index dab1eed2eb..4172d6be5e 100644
--- a/src/key.cpp
+++ b/src/key.cpp
@@ -2,8 +2,15 @@
 // Distributed under the MIT/X11 software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
-#include <openssl/ec.h>
+#include <map>
+
+#include <boost/tuple/tuple.hpp>
 #include <openssl/ecdsa.h>
+#include <openssl/obj_mac.h>
+
+#include "key.h"
+#include "sync.h"
+#include "util.h"
 
 // Generate a private key from just the secret parameter
 int EC_KEY_regenerate_key(EC_KEY *eckey, BIGNUM *priv_key)
@@ -115,3 +122,326 @@ err:
     if (Q != NULL) EC_POINT_free(Q);
     return ret;
 }
+
+void CKey::SetCompressedPubKey()
+{
+    EC_KEY_set_conv_form(pkey, POINT_CONVERSION_COMPRESSED);
+    fCompressedPubKey = true;
+}
+
+void CKey::Reset()
+{
+    fCompressedPubKey = false;
+    pkey = EC_KEY_new_by_curve_name(NID_secp256k1);
+    if (pkey == NULL)
+        throw key_error("CKey::CKey() : EC_KEY_new_by_curve_name failed");
+    fSet = false;
+}
+
+CKey::CKey()
+{
+    Reset();
+}
+
+CKey::CKey(const CKey& b)
+{
+    pkey = EC_KEY_dup(b.pkey);
+    if (pkey == NULL)
+        throw key_error("CKey::CKey(const CKey&) : EC_KEY_dup failed");
+    fSet = b.fSet;
+}
+
+CKey& CKey::operator=(const CKey& b)
+{
+    if (!EC_KEY_copy(pkey, b.pkey))
+        throw key_error("CKey::operator=(const CKey&) : EC_KEY_copy failed");
+    fSet = b.fSet;
+    return (*this);
+}
+
+CKey::~CKey()
+{
+    EC_KEY_free(pkey);
+}
+
+bool CKey::IsNull() const
+{
+    return !fSet;
+}
+
+bool CKey::IsCompressed() const
+{
+    return fCompressedPubKey;
+}
+
+void CKey::MakeNewKey(bool fCompressed)
+{
+    if (!EC_KEY_generate_key(pkey))
+        throw key_error("CKey::MakeNewKey() : EC_KEY_generate_key failed");
+    if (fCompressed)
+        SetCompressedPubKey();
+    fSet = true;
+}
+
+bool CKey::SetPrivKey(const CPrivKey& vchPrivKey)
+{
+    const unsigned char* pbegin = &vchPrivKey[0];
+    if (!d2i_ECPrivateKey(&pkey, &pbegin, vchPrivKey.size()))
+        return false;
+    fSet = true;
+    return true;
+}
+
+bool CKey::SetSecret(const CSecret& vchSecret, bool fCompressed)
+{
+    EC_KEY_free(pkey);
+    pkey = EC_KEY_new_by_curve_name(NID_secp256k1);
+    if (pkey == NULL)
+        throw key_error("CKey::SetSecret() : EC_KEY_new_by_curve_name failed");
+    if (vchSecret.size() != 32)
+        throw key_error("CKey::SetSecret() : secret must be 32 bytes");
+    BIGNUM *bn = BN_bin2bn(&vchSecret[0],32,BN_new());
+    if (bn == NULL)
+        throw key_error("CKey::SetSecret() : BN_bin2bn failed");
+    if (!EC_KEY_regenerate_key(pkey,bn))
+    {
+        BN_clear_free(bn);
+        throw key_error("CKey::SetSecret() : EC_KEY_regenerate_key failed");
+    }
+    BN_clear_free(bn);
+    fSet = true;
+    if (fCompressed || fCompressedPubKey)
+        SetCompressedPubKey();
+    return true;
+}
+
+CSecret CKey::GetSecret(bool &fCompressed) const
+{
+    CSecret vchRet;
+    vchRet.resize(32);
+    const BIGNUM *bn = EC_KEY_get0_private_key(pkey);
+    int nBytes = BN_num_bytes(bn);
+    if (bn == NULL)
+        throw key_error("CKey::GetSecret() : EC_KEY_get0_private_key failed");
+    int n=BN_bn2bin(bn,&vchRet[32 - nBytes]);
+    if (n != nBytes)
+        throw key_error("CKey::GetSecret(): BN_bn2bin failed");
+    fCompressed = fCompressedPubKey;
+    return vchRet;
+}
+
+CPrivKey CKey::GetPrivKey() const
+{
+    int nSize = i2d_ECPrivateKey(pkey, NULL);
+    if (!nSize)
+        throw key_error("CKey::GetPrivKey() : i2d_ECPrivateKey failed");
+    CPrivKey vchPrivKey(nSize, 0);
+    unsigned char* pbegin = &vchPrivKey[0];
+    if (i2d_ECPrivateKey(pkey, &pbegin) != nSize)
+        throw key_error("CKey::GetPrivKey() : i2d_ECPrivateKey returned unexpected size");
+    return vchPrivKey;
+}
+
+bool CKey::SetPubKey(const std::vector<unsigned char>& vchPubKey)
+{
+    const unsigned char* pbegin = &vchPubKey[0];
+    if (!o2i_ECPublicKey(&pkey, &pbegin, vchPubKey.size()))
+        return false;
+    fSet = true;
+    if (vchPubKey.size() == 33)
+        SetCompressedPubKey();
+    return true;
+}
+
+std::vector<unsigned char> CKey::GetPubKey() const
+{
+    int nSize = i2o_ECPublicKey(pkey, NULL);
+    if (!nSize)
+        throw key_error("CKey::GetPubKey() : i2o_ECPublicKey failed");
+    std::vector<unsigned char> vchPubKey(nSize, 0);
+    unsigned char* pbegin = &vchPubKey[0];
+    if (i2o_ECPublicKey(pkey, &pbegin) != nSize)
+        throw key_error("CKey::GetPubKey() : i2o_ECPublicKey returned unexpected size");
+    return vchPubKey;
+}
+
+bool CKey::Sign(uint256 hash, std::vector<unsigned char>& vchSig)
+{
+    unsigned int nSize = ECDSA_size(pkey);
+    vchSig.resize(nSize); // Make sure it is big enough
+    if (!ECDSA_sign(0, (unsigned char*)&hash, sizeof(hash), &vchSig[0], &nSize, pkey))
+    {
+        vchSig.clear();
+        return false;
+    }
+    vchSig.resize(nSize); // Shrink to fit actual size
+    return true;
+}
+
+// create a compact signature (65 bytes), which allows reconstructing the used public key
+// The format is one header byte, followed by two times 32 bytes for the serialized r and s values.
+// The header byte: 0x1B = first key with even y, 0x1C = first key with odd y,
+//                  0x1D = second key with even y, 0x1E = second key with odd y
+bool CKey::SignCompact(uint256 hash, std::vector<unsigned char>& vchSig)
+{
+    bool fOk = false;
+    ECDSA_SIG *sig = ECDSA_do_sign((unsigned char*)&hash, sizeof(hash), pkey);
+    if (sig==NULL)
+        return false;
+    vchSig.clear();
+    vchSig.resize(65,0);
+    int nBitsR = BN_num_bits(sig->r);
+    int nBitsS = BN_num_bits(sig->s);
+    if (nBitsR <= 256 && nBitsS <= 256)
+    {
+        int nRecId = -1;
+        for (int i=0; i<4; i++)
+        {
+            CKey keyRec;
+            keyRec.fSet = true;
+            if (fCompressedPubKey)
+                keyRec.SetCompressedPubKey();
+            if (ECDSA_SIG_recover_key_GFp(keyRec.pkey, sig, (unsigned char*)&hash, sizeof(hash), i, 1) == 1)
+                if (keyRec.GetPubKey() == this->GetPubKey())
+                {
+                    nRecId = i;
+                    break;
+                }
+        }
+
+        if (nRecId == -1)
+            throw key_error("CKey::SignCompact() : unable to construct recoverable key");
+
+        vchSig[0] = nRecId+27+(fCompressedPubKey ? 4 : 0);
+        BN_bn2bin(sig->r,&vchSig[33-(nBitsR+7)/8]);
+        BN_bn2bin(sig->s,&vchSig[65-(nBitsS+7)/8]);
+        fOk = true;
+    }
+    ECDSA_SIG_free(sig);
+    return fOk;
+}
+
+// reconstruct public key from a compact signature
+// This is only slightly more CPU intensive than just verifying it.
+// If this function succeeds, the recovered public key is guaranteed to be valid
+// (the signature is a valid signature of the given data for that key)
+bool CKey::SetCompactSignature(uint256 hash, const std::vector<unsigned char>& vchSig)
+{
+    if (vchSig.size() != 65)
+        return false;
+    int nV = vchSig[0];
+    if (nV<27 || nV>=35)
+        return false;
+    ECDSA_SIG *sig = ECDSA_SIG_new();
+    BN_bin2bn(&vchSig[1],32,sig->r);
+    BN_bin2bn(&vchSig[33],32,sig->s);
+
+    EC_KEY_free(pkey);
+    pkey = EC_KEY_new_by_curve_name(NID_secp256k1);
+    if (nV >= 31)
+    {
+        SetCompressedPubKey();
+        nV -= 4;
+    }
+    if (ECDSA_SIG_recover_key_GFp(pkey, sig, (unsigned char*)&hash, sizeof(hash), nV - 27, 0) == 1)
+    {
+        fSet = true;
+        ECDSA_SIG_free(sig);
+        return true;
+    }
+    return false;
+}
+
+// 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)
+
+// sigdata_type is (signature hash, signature, public key):
+typedef boost::tuple<uint256, std::vector<unsigned char>, std::vector<unsigned char> > sigdata_type;
+static std::set< sigdata_type> setValidSigCache;
+static CCriticalSection cs_sigcache;
+
+static bool
+GetValidSigCache(uint256 hash, const std::vector<unsigned char>& vchSig, const std::vector<unsigned char>& pubKey)
+{
+    LOCK(cs_sigcache);
+
+    sigdata_type k(hash, vchSig, pubKey);
+    std::set<sigdata_type>::iterator mi = setValidSigCache.find(k);
+    if (mi != setValidSigCache.end())
+        return true;
+    return false;
+}
+
+static void
+SetValidSigCache(uint256 hash, const std::vector<unsigned char>& vchSig, const std::vector<unsigned char>& 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 (setValidSigCache.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<unsigned char> unused;
+        std::set<sigdata_type>::iterator it =
+            setValidSigCache.lower_bound(sigdata_type(randomHash, unused, unused));
+        if (it == setValidSigCache.end())
+            it = setValidSigCache.begin();
+        setValidSigCache.erase(*it);
+    }
+
+    sigdata_type k(hash, vchSig, pubKey);
+    setValidSigCache.insert(k);
+}
+
+
+bool CKey::Verify(uint256 hash, const std::vector<unsigned char>& vchSig)
+{
+    if (GetValidSigCache(hash, vchSig, GetPubKey()))
+        return true;
+
+    // -1 = error, 0 = bad sig, 1 = good
+    if (ECDSA_verify(0, (unsigned char*)&hash, sizeof(hash), &vchSig[0], vchSig.size(), pkey) != 1)
+        return false;
+
+    // good sig
+    SetValidSigCache(hash, vchSig, GetPubKey());
+    return true;
+}
+
+bool CKey::VerifyCompact(uint256 hash, const std::vector<unsigned char>& vchSig)
+{
+    if (GetValidSigCache(hash, vchSig, GetPubKey()))
+        return true;
+
+    CKey key;
+    if (!key.SetCompactSignature(hash, vchSig))
+        return false;
+    if (GetPubKey() != key.GetPubKey())
+        return false;
+
+    SetValidSigCache(hash, vchSig, GetPubKey());
+    return true;
+}
+
+bool CKey::IsValid()
+{
+    if (!fSet)
+        return false;
+
+    bool fCompr;
+    CSecret secret = GetSecret(fCompr);
+    CKey key2;
+    key2.SetSecret(secret, fCompr);
+    return GetPubKey() == key2.GetPubKey();
+}
diff --git a/src/key.h b/src/key.h
index f687f334ce..bd58c84375 100644
--- a/src/key.h
+++ b/src/key.h
@@ -8,13 +8,11 @@
 #include <stdexcept>
 #include <vector>
 
-#include <openssl/ec.h>
-#include <openssl/ecdsa.h>
-#include <openssl/obj_mac.h>
-
 #include "allocators.h"
 #include "uint256.h"
 
+#include <openssl/ec.h> // for EC_KEY definition
+
 // secp160k1
 // const unsigned int PRIVATE_KEY_SIZE = 192;
 // const unsigned int PUBLIC_KEY_SIZE  = 41;
@@ -38,9 +36,6 @@
 // see www.keylength.com
 // script supports up to 75 for single byte push
 
-int extern EC_KEY_regenerate_key(EC_KEY *eckey, BIGNUM *priv_key);
-int extern ECDSA_SIG_recover_key_GFp(EC_KEY *eckey, ECDSA_SIG *ecsig, const unsigned char *msg, int msglen, int recid, int check);
-
 class key_error : public std::runtime_error
 {
 public:
@@ -62,267 +57,50 @@ protected:
     bool fSet;
     bool fCompressedPubKey;
 
-    void SetCompressedPubKey()
-    {
-        EC_KEY_set_conv_form(pkey, POINT_CONVERSION_COMPRESSED);
-        fCompressedPubKey = true;
-    }
+    void SetCompressedPubKey();
 
 public:
 
-    void Reset()
-    {
-        fCompressedPubKey = false;
-        pkey = EC_KEY_new_by_curve_name(NID_secp256k1);
-        if (pkey == NULL)
-            throw key_error("CKey::CKey() : EC_KEY_new_by_curve_name failed");
-        fSet = false;
-    }
-
-    CKey()
-    {
-        Reset();
-    }
-
-    CKey(const CKey& b)
-    {
-        pkey = EC_KEY_dup(b.pkey);
-        if (pkey == NULL)
-            throw key_error("CKey::CKey(const CKey&) : EC_KEY_dup failed");
-        fSet = b.fSet;
-    }
-
-    CKey& operator=(const CKey& b)
-    {
-        if (!EC_KEY_copy(pkey, b.pkey))
-            throw key_error("CKey::operator=(const CKey&) : EC_KEY_copy failed");
-        fSet = b.fSet;
-        return (*this);
-    }
-
-    ~CKey()
-    {
-        EC_KEY_free(pkey);
-    }
-
-    bool IsNull() const
-    {
-        return !fSet;
-    }
+    void Reset();
 
-    bool IsCompressed() const
-    {
-        return fCompressedPubKey;
-    }
+    CKey();
+    CKey(const CKey& b);
 
-    void MakeNewKey(bool fCompressed)
-    {
-        if (!EC_KEY_generate_key(pkey))
-            throw key_error("CKey::MakeNewKey() : EC_KEY_generate_key failed");
-        if (fCompressed)
-            SetCompressedPubKey();
-        fSet = true;
-    }
+    CKey& operator=(const CKey& b);
 
-    bool SetPrivKey(const CPrivKey& vchPrivKey)
-    {
-        const unsigned char* pbegin = &vchPrivKey[0];
-        if (!d2i_ECPrivateKey(&pkey, &pbegin, vchPrivKey.size()))
-            return false;
-        fSet = true;
-        return true;
-    }
+    ~CKey();
 
-    bool SetSecret(const CSecret& vchSecret, bool fCompressed = false)
-    {
-        EC_KEY_free(pkey);
-        pkey = EC_KEY_new_by_curve_name(NID_secp256k1);
-        if (pkey == NULL)
-            throw key_error("CKey::SetSecret() : EC_KEY_new_by_curve_name failed");
-        if (vchSecret.size() != 32)
-            throw key_error("CKey::SetSecret() : secret must be 32 bytes");
-        BIGNUM *bn = BN_bin2bn(&vchSecret[0],32,BN_new());
-        if (bn == NULL)
-            throw key_error("CKey::SetSecret() : BN_bin2bn failed");
-        if (!EC_KEY_regenerate_key(pkey,bn))
-        {
-            BN_clear_free(bn);
-            throw key_error("CKey::SetSecret() : EC_KEY_regenerate_key failed");
-        }
-        BN_clear_free(bn);
-        fSet = true;
-        if (fCompressed || fCompressedPubKey)
-            SetCompressedPubKey();
-        return true;
-    }
+    bool IsNull() const;
+    bool IsCompressed() const;
 
-    CSecret GetSecret(bool &fCompressed) const
-    {
-        CSecret vchRet;
-        vchRet.resize(32);
-        const BIGNUM *bn = EC_KEY_get0_private_key(pkey);
-        int nBytes = BN_num_bytes(bn);
-        if (bn == NULL)
-            throw key_error("CKey::GetSecret() : EC_KEY_get0_private_key failed");
-        int n=BN_bn2bin(bn,&vchRet[32 - nBytes]);
-        if (n != nBytes) 
-            throw key_error("CKey::GetSecret(): BN_bn2bin failed");
-        fCompressed = fCompressedPubKey;
-        return vchRet;
-    }
+    void MakeNewKey(bool fCompressed);
+    bool SetPrivKey(const CPrivKey& vchPrivKey);
+    bool SetSecret(const CSecret& vchSecret, bool fCompressed = false);
+    CSecret GetSecret(bool &fCompressed) const;
+    CPrivKey GetPrivKey() const;
+    bool SetPubKey(const std::vector<unsigned char>& vchPubKey);
+    std::vector<unsigned char> GetPubKey() const;
 
-    CPrivKey GetPrivKey() const
-    {
-        int nSize = i2d_ECPrivateKey(pkey, NULL);
-        if (!nSize)
-            throw key_error("CKey::GetPrivKey() : i2d_ECPrivateKey failed");
-        CPrivKey vchPrivKey(nSize, 0);
-        unsigned char* pbegin = &vchPrivKey[0];
-        if (i2d_ECPrivateKey(pkey, &pbegin) != nSize)
-            throw key_error("CKey::GetPrivKey() : i2d_ECPrivateKey returned unexpected size");
-        return vchPrivKey;
-    }
-
-    bool SetPubKey(const std::vector<unsigned char>& vchPubKey)
-    {
-        const unsigned char* pbegin = &vchPubKey[0];
-        if (!o2i_ECPublicKey(&pkey, &pbegin, vchPubKey.size()))
-            return false;
-        fSet = true;
-        if (vchPubKey.size() == 33)
-            SetCompressedPubKey();
-        return true;
-    }
-
-    std::vector<unsigned char> GetPubKey() const
-    {
-        int nSize = i2o_ECPublicKey(pkey, NULL);
-        if (!nSize)
-            throw key_error("CKey::GetPubKey() : i2o_ECPublicKey failed");
-        std::vector<unsigned char> vchPubKey(nSize, 0);
-        unsigned char* pbegin = &vchPubKey[0];
-        if (i2o_ECPublicKey(pkey, &pbegin) != nSize)
-            throw key_error("CKey::GetPubKey() : i2o_ECPublicKey returned unexpected size");
-        return vchPubKey;
-    }
-
-    bool Sign(uint256 hash, std::vector<unsigned char>& vchSig)
-    {
-        unsigned int nSize = ECDSA_size(pkey);
-        vchSig.resize(nSize); // Make sure it is big enough
-        if (!ECDSA_sign(0, (unsigned char*)&hash, sizeof(hash), &vchSig[0], &nSize, pkey))
-        {
-            vchSig.clear();
-            return false;
-        }
-        vchSig.resize(nSize); // Shrink to fit actual size
-        return true;
-    }
+    bool Sign(uint256 hash, std::vector<unsigned char>& vchSig);
 
     // create a compact signature (65 bytes), which allows reconstructing the used public key
     // The format is one header byte, followed by two times 32 bytes for the serialized r and s values.
     // The header byte: 0x1B = first key with even y, 0x1C = first key with odd y,
     //                  0x1D = second key with even y, 0x1E = second key with odd y
-    bool SignCompact(uint256 hash, std::vector<unsigned char>& vchSig)
-    {
-        bool fOk = false;
-        ECDSA_SIG *sig = ECDSA_do_sign((unsigned char*)&hash, sizeof(hash), pkey);
-        if (sig==NULL)
-            return false;
-        vchSig.clear();
-        vchSig.resize(65,0);
-        int nBitsR = BN_num_bits(sig->r);
-        int nBitsS = BN_num_bits(sig->s);
-        if (nBitsR <= 256 && nBitsS <= 256)
-        {
-            int nRecId = -1;
-            for (int i=0; i<4; i++)
-            {
-                CKey keyRec;
-                keyRec.fSet = true;
-                if (fCompressedPubKey)
-                    keyRec.SetCompressedPubKey();
-                if (ECDSA_SIG_recover_key_GFp(keyRec.pkey, sig, (unsigned char*)&hash, sizeof(hash), i, 1) == 1)
-                    if (keyRec.GetPubKey() == this->GetPubKey())
-                    {
-                        nRecId = i;
-                        break;
-                    }
-            }
-
-            if (nRecId == -1)
-                throw key_error("CKey::SignCompact() : unable to construct recoverable key");
-
-            vchSig[0] = nRecId+27+(fCompressedPubKey ? 4 : 0);
-            BN_bn2bin(sig->r,&vchSig[33-(nBitsR+7)/8]);
-            BN_bn2bin(sig->s,&vchSig[65-(nBitsS+7)/8]);
-            fOk = true;
-        }
-        ECDSA_SIG_free(sig);
-        return fOk;
-    }
+    bool SignCompact(uint256 hash, std::vector<unsigned char>& vchSig);
 
     // reconstruct public key from a compact signature
     // This is only slightly more CPU intensive than just verifying it.
     // If this function succeeds, the recovered public key is guaranteed to be valid
     // (the signature is a valid signature of the given data for that key)
-    bool SetCompactSignature(uint256 hash, const std::vector<unsigned char>& vchSig)
-    {
-        if (vchSig.size() != 65)
-            return false;
-        int nV = vchSig[0];
-        if (nV<27 || nV>=35)
-            return false;
-        ECDSA_SIG *sig = ECDSA_SIG_new();
-        BN_bin2bn(&vchSig[1],32,sig->r);
-        BN_bin2bn(&vchSig[33],32,sig->s);
-
-        EC_KEY_free(pkey);
-        pkey = EC_KEY_new_by_curve_name(NID_secp256k1);
-        if (nV >= 31)
-        {
-            SetCompressedPubKey();
-            nV -= 4;
-        }
-        if (ECDSA_SIG_recover_key_GFp(pkey, sig, (unsigned char*)&hash, sizeof(hash), nV - 27, 0) == 1)
-        {
-            fSet = true;
-            ECDSA_SIG_free(sig);
-            return true;
-        }
-        return false;
-    }
+    bool SetCompactSignature(uint256 hash, const std::vector<unsigned char>& vchSig);
 
-    bool Verify(uint256 hash, const std::vector<unsigned char>& vchSig)
-    {
-        // -1 = error, 0 = bad sig, 1 = good
-        if (ECDSA_verify(0, (unsigned char*)&hash, sizeof(hash), &vchSig[0], vchSig.size(), pkey) != 1)
-            return false;
-        return true;
-    }
+    bool Verify(uint256 hash, const std::vector<unsigned char>& vchSig);
 
     // Verify a compact signature
-    bool VerifyCompact(uint256 hash, const std::vector<unsigned char>& vchSig)
-    {
-        CKey key;
-        if (!key.SetCompactSignature(hash, vchSig))
-            return false;
-        if (GetPubKey() != key.GetPubKey())
-            return false;
-        return true;
-    }
-
-    bool IsValid()
-    {
-        if (!fSet)
-            return false;
+    bool VerifyCompact(uint256 hash, const std::vector<unsigned char>& vchSig);
 
-        bool fCompr;
-        CSecret secret = GetSecret(fCompr);
-        CKey key2;
-        key2.SetSecret(secret, fCompr);
-        return GetPubKey() == key2.GetPubKey();
-    }
+    bool IsValid();
 };
 
 #endif
diff --git a/src/main.cpp b/src/main.cpp
index 9b38d9efba..8900115efe 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -44,7 +44,7 @@ map<uint256, CBlock*> mapOrphanBlocks;
 multimap<uint256, CBlock*> mapOrphanBlocksByPrev;
 
 map<uint256, CDataStream*> mapOrphanTransactions;
-multimap<uint256, CDataStream*> mapOrphanTransactionsByPrev;
+map<uint256, map<uint256, CDataStream*> > mapOrphanTransactionsByPrev;
 
 // Constant stuff for coinbase transactions we create:
 CScript COINBASE_FLAGS;
@@ -161,17 +161,37 @@ void static ResendWalletTransactions()
 // mapOrphanTransactions
 //
 
-void AddOrphanTx(const CDataStream& vMsg)
+bool AddOrphanTx(const CDataStream& vMsg)
 {
     CTransaction tx;
     CDataStream(vMsg) >> tx;
     uint256 hash = tx.GetHash();
     if (mapOrphanTransactions.count(hash))
-        return;
+        return false;
+
+    CDataStream* pvMsg = new CDataStream(vMsg);
 
-    CDataStream* pvMsg = mapOrphanTransactions[hash] = new CDataStream(vMsg);
+    // Ignore big transactions, to avoid a
+    // send-big-orphans memory exhaustion attack. If a peer has a legitimate
+    // large transaction with a missing parent then we assume
+    // it will rebroadcast it later, after the parent transaction(s)
+    // have been mined or received.
+    // 10,000 orphans, each of which is at most 5,000 bytes big is
+    // at most 500 megabytes of orphans:
+    if (pvMsg->size() > 5000)
+    {
+        delete pvMsg;
+        printf("ignoring large orphan tx (size: %u, hash: %s)\n", pvMsg->size(), hash.ToString().substr(0,10).c_str());
+        return false;
+    }
+
+    mapOrphanTransactions[hash] = pvMsg;
     BOOST_FOREACH(const CTxIn& txin, tx.vin)
-        mapOrphanTransactionsByPrev.insert(make_pair(txin.prevout.hash, pvMsg));
+        mapOrphanTransactionsByPrev[txin.prevout.hash].insert(make_pair(hash, pvMsg));
+
+    printf("stored orphan tx %s (mapsz %u)\n", hash.ToString().substr(0,10).c_str(),
+        mapOrphanTransactions.size());
+    return true;
 }
 
 void static EraseOrphanTx(uint256 hash)
@@ -183,14 +203,9 @@ void static EraseOrphanTx(uint256 hash)
     CDataStream(*pvMsg) >> tx;
     BOOST_FOREACH(const CTxIn& txin, tx.vin)
     {
-        for (multimap<uint256, CDataStream*>::iterator mi = mapOrphanTransactionsByPrev.lower_bound(txin.prevout.hash);
-             mi != mapOrphanTransactionsByPrev.upper_bound(txin.prevout.hash);)
-        {
-            if ((*mi).second == pvMsg)
-                mapOrphanTransactionsByPrev.erase(mi++);
-            else
-                mi++;
-        }
+        mapOrphanTransactionsByPrev[txin.prevout.hash].erase(hash);
+        if (mapOrphanTransactionsByPrev[txin.prevout.hash].empty())
+            mapOrphanTransactionsByPrev.erase(txin.prevout.hash);
     }
     delete pvMsg;
     mapOrphanTransactions.erase(hash);
@@ -202,9 +217,7 @@ unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans)
     while (mapOrphanTransactions.size() > nMaxOrphans)
     {
         // Evict a random orphan:
-        std::vector<unsigned char> randbytes(32);
-        RAND_bytes(&randbytes[0], 32);
-        uint256 randomhash(randbytes);
+        uint256 randomhash = GetRandHash();
         map<uint256, CDataStream*>::iterator it = mapOrphanTransactions.lower_bound(randomhash);
         if (it == mapOrphanTransactions.end())
             it = mapOrphanTransactions.begin();
@@ -1155,17 +1168,28 @@ bool CTransaction::ConnectInputs(MapPrevTx inputs,
                     if (pindex->nBlockPos == txindex.pos.nBlockPos && pindex->nFile == txindex.pos.nFile)
                         return error("ConnectInputs() : tried to spend coinbase at depth %d", pindexBlock->nHeight - pindex->nHeight);
 
+            // Check for negative or overflow input values
+            nValueIn += txPrev.vout[prevout.n].nValue;
+            if (!MoneyRange(txPrev.vout[prevout.n].nValue) || !MoneyRange(nValueIn))
+                return DoS(100, error("ConnectInputs() : txin values out of range"));
+
+        }
+        // The first loop above does all the inexpensive checks.
+        // Only if ALL inputs pass do we perform expensive ECDSA signature checks.
+        // Helps prevent CPU exhaustion attacks.
+        for (unsigned int i = 0; i < vin.size(); i++)
+        {
+            COutPoint prevout = vin[i].prevout;
+            assert(inputs.count(prevout.hash) > 0);
+            CTxIndex& txindex = inputs[prevout.hash].first;
+            CTransaction& txPrev = inputs[prevout.hash].second;
+
             // Check for conflicts (double-spend)
             // This doesn't trigger the DoS code on purpose; if it did, it would make it easier
             // for an attacker to attempt to split the network.
             if (!txindex.vSpent[prevout.n].IsNull())
                 return fMiner ? false : error("ConnectInputs() : %s prev tx already used at %s", GetHash().ToString().substr(0,10).c_str(), txindex.vSpent[prevout.n].ToString().c_str());
 
-            // Check for negative or overflow input values
-            nValueIn += txPrev.vout[prevout.n].nValue;
-            if (!MoneyRange(txPrev.vout[prevout.n].nValue) || !MoneyRange(nValueIn))
-                return DoS(100, error("ConnectInputs() : txin values out of range"));
-
             // Skip ECDSA signature verification when connecting blocks (fBlock=true)
             // before the last blockchain checkpoint. This is safe because block merkle hashes are
             // still computed and checked, and any change will be caught at the next checkpoint.
@@ -2460,7 +2484,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv)
                     // at a time so the setAddrKnowns of the chosen nodes prevent repeats
                     static uint256 hashSalt;
                     if (hashSalt == 0)
-                        RAND_bytes((unsigned char*)&hashSalt, sizeof(hashSalt));
+                        hashSalt = GetRandHash();
                     int64 hashAddr = addr.GetHash();
                     uint256 hashRand = hashSalt ^ (hashAddr<<32) ^ ((GetTime()+hashAddr)/(24*60*60));
                     hashRand = Hash(BEGIN(hashRand), END(hashRand));
@@ -2676,6 +2700,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv)
     else if (strCommand == "tx")
     {
         vector<uint256> vWorkQueue;
+        vector<uint256> vEraseQueue;
         CDataStream vMsg(vRecv);
         CTxDB txdb("r");
         CTransaction tx;
@@ -2691,32 +2716,41 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv)
             RelayMessage(inv, vMsg);
             mapAlreadyAskedFor.erase(inv);
             vWorkQueue.push_back(inv.hash);
+            vEraseQueue.push_back(inv.hash);
 
             // Recursively process any orphan transactions that depended on this one
             for (unsigned int i = 0; i < vWorkQueue.size(); i++)
             {
                 uint256 hashPrev = vWorkQueue[i];
-                for (multimap<uint256, CDataStream*>::iterator mi = mapOrphanTransactionsByPrev.lower_bound(hashPrev);
-                     mi != mapOrphanTransactionsByPrev.upper_bound(hashPrev);
+                for (map<uint256, CDataStream*>::iterator mi = mapOrphanTransactionsByPrev[hashPrev].begin();
+                     mi != mapOrphanTransactionsByPrev[hashPrev].end();
                      ++mi)
                 {
                     const CDataStream& vMsg = *((*mi).second);
                     CTransaction tx;
                     CDataStream(vMsg) >> tx;
                     CInv inv(MSG_TX, tx.GetHash());
+                    bool fMissingInputs2 = false;
 
-                    if (tx.AcceptToMemoryPool(txdb, true))
+                    if (tx.AcceptToMemoryPool(txdb, true, &fMissingInputs2))
                     {
                         printf("   accepted orphan tx %s\n", inv.hash.ToString().substr(0,10).c_str());
                         SyncWithWallets(tx, NULL, true);
                         RelayMessage(inv, vMsg);
                         mapAlreadyAskedFor.erase(inv);
                         vWorkQueue.push_back(inv.hash);
+                        vEraseQueue.push_back(inv.hash);
+                    }
+                    else if (!fMissingInputs2)
+                    {
+                        // invalid orphan
+                        vEraseQueue.push_back(inv.hash);
+                        printf("   removed invalid orphan tx %s\n", inv.hash.ToString().substr(0,10).c_str());
                     }
                 }
             }
 
-            BOOST_FOREACH(uint256 hash, vWorkQueue)
+            BOOST_FOREACH(uint256 hash, vEraseQueue)
                 EraseOrphanTx(hash);
         }
         else if (fMissingInputs)
@@ -3072,7 +3106,7 @@ bool SendMessages(CNode* pto, bool fSendTrickle)
                     // 1/4 of tx invs blast to all immediately
                     static uint256 hashSalt;
                     if (hashSalt == 0)
-                        RAND_bytes((unsigned char*)&hashSalt, sizeof(hashSalt));
+                        hashSalt = GetRandHash();
                     uint256 hashRand = inv.hash ^ hashSalt;
                     hashRand = Hash(BEGIN(hashRand), END(hashRand));
                     bool fTrickleWait = ((hashRand & 3) != 0);
diff --git a/src/test/DoS_tests.cpp b/src/test/DoS_tests.cpp
index 04e2a95d70..7defd23f80 100644
--- a/src/test/DoS_tests.cpp
+++ b/src/test/DoS_tests.cpp
@@ -1,7 +1,10 @@
 //
 // Unit tests for denial-of-service detection/prevention code
 //
+#include <algorithm>
+
 #include <boost/assign/list_of.hpp> // for 'map_list_of()'
+#include <boost/date_time/posix_time/posix_time_types.hpp>
 #include <boost/test/unit_test.hpp>
 #include <boost/foreach.hpp>
 
@@ -13,10 +16,10 @@
 #include <stdint.h>
 
 // Tests this internal-to-main.cpp method:
-extern void AddOrphanTx(const CDataStream& vMsg);
+extern bool AddOrphanTx(const CDataStream& vMsg);
 extern unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans);
 extern std::map<uint256, CDataStream*> mapOrphanTransactions;
-extern std::multimap<uint256, CDataStream*> mapOrphanTransactionsByPrev;
+extern std::map<uint256, std::map<uint256, CDataStream*> > mapOrphanTransactionsByPrev;
 
 CService ip(uint32_t i)
 {
@@ -57,7 +60,7 @@ BOOST_AUTO_TEST_CASE(DoS_banscore)
     BOOST_CHECK(!CNode::IsBanned(addr1));
     dummyNode1.Misbehaving(1);
     BOOST_CHECK(CNode::IsBanned(addr1));
-    mapArgs["-banscore"] = "100";
+    mapArgs.erase("-banscore");
 }
 
 BOOST_AUTO_TEST_CASE(DoS_bantime)
@@ -129,18 +132,10 @@ BOOST_AUTO_TEST_CASE(DoS_checknbits)
     
 }
 
-static uint256 RandomHash()
-{
-    std::vector<unsigned char> randbytes(32);
-    RAND_bytes(&randbytes[0], 32);
-    uint256 randomhash(randbytes);
-    return randomhash;
-}
-
 CTransaction RandomOrphan()
 {
     std::map<uint256, CDataStream*>::iterator it;
-    it = mapOrphanTransactions.lower_bound(RandomHash());
+    it = mapOrphanTransactions.lower_bound(GetRandHash());
     if (it == mapOrphanTransactions.end())
         it = mapOrphanTransactions.begin();
     const CDataStream* pvMsg = it->second;
@@ -162,7 +157,7 @@ BOOST_AUTO_TEST_CASE(DoS_mapOrphans)
         CTransaction tx;
         tx.vin.resize(1);
         tx.vin[0].prevout.n = 0;
-        tx.vin[0].prevout.hash = RandomHash();
+        tx.vin[0].prevout.hash = GetRandHash();
         tx.vin[0].scriptSig << OP_1;
         tx.vout.resize(1);
         tx.vout[0].nValue = 1*CENT;
@@ -192,6 +187,32 @@ BOOST_AUTO_TEST_CASE(DoS_mapOrphans)
         AddOrphanTx(ds);
     }
 
+    // This really-big orphan should be ignored:
+    for (int i = 0; i < 10; i++)
+    {
+        CTransaction txPrev = RandomOrphan();
+
+        CTransaction tx;
+        tx.vout.resize(1);
+        tx.vout[0].nValue = 1*CENT;
+        tx.vout[0].scriptPubKey.SetBitcoinAddress(key.GetPubKey());
+        tx.vin.resize(500);
+        for (int j = 0; j < tx.vin.size(); j++)
+        {
+            tx.vin[j].prevout.n = j;
+            tx.vin[j].prevout.hash = txPrev.GetHash();
+        }
+        SignSignature(keystore, txPrev, tx, 0);
+        // Re-use same signature for other inputs
+        // (they don't have to be valid for this test)
+        for (int j = 1; j < tx.vin.size(); j++)
+            tx.vin[j].scriptSig = tx.vin[0].scriptSig;
+
+        CDataStream ds(SER_DISK, CLIENT_VERSION);
+        ds << tx;
+        BOOST_CHECK(!AddOrphanTx(ds));
+    }
+
     // Test LimitOrphanTxSize() function:
     LimitOrphanTxSize(40);
     BOOST_CHECK(mapOrphanTransactions.size() <= 40);
@@ -202,4 +223,92 @@ BOOST_AUTO_TEST_CASE(DoS_mapOrphans)
     BOOST_CHECK(mapOrphanTransactionsByPrev.empty());
 }
 
+BOOST_AUTO_TEST_CASE(DoS_checkSig)
+{
+    // Test signature caching code (see key.cpp Verify() methods)
+
+    CKey key;
+    key.MakeNewKey(true);
+    CBasicKeyStore keystore;
+    keystore.AddKey(key);
+
+    // 100 orphan transactions:
+    static const int NPREV=100;
+    CTransaction orphans[NPREV];
+    for (int i = 0; i < NPREV; i++)
+    {
+        CTransaction& tx = orphans[i];
+        tx.vin.resize(1);
+        tx.vin[0].prevout.n = 0;
+        tx.vin[0].prevout.hash = GetRandHash();
+        tx.vin[0].scriptSig << OP_1;
+        tx.vout.resize(1);
+        tx.vout[0].nValue = 1*CENT;
+        tx.vout[0].scriptPubKey.SetBitcoinAddress(key.GetPubKey());
+
+        CDataStream ds(SER_DISK, CLIENT_VERSION);
+        ds << tx;
+        AddOrphanTx(ds);
+    }
+
+    // Create a transaction that depends on orphans:
+    CTransaction tx;
+    tx.vout.resize(1);
+    tx.vout[0].nValue = 1*CENT;
+    tx.vout[0].scriptPubKey.SetBitcoinAddress(key.GetPubKey());
+    tx.vin.resize(NPREV);
+    for (int j = 0; j < tx.vin.size(); j++)
+    {
+        tx.vin[j].prevout.n = 0;
+        tx.vin[j].prevout.hash = orphans[j].GetHash();
+    }
+    // Creating signatures primes the cache:
+    boost::posix_time::ptime mst1 = boost::posix_time::microsec_clock::local_time();
+    for (int j = 0; j < tx.vin.size(); j++)
+        BOOST_CHECK(SignSignature(keystore, orphans[j], tx, j));
+    boost::posix_time::ptime mst2 = boost::posix_time::microsec_clock::local_time();
+    boost::posix_time::time_duration msdiff = mst2 - mst1;
+    long nOneValidate = msdiff.total_milliseconds();
+    if (fDebug) printf("DoS_Checksig sign: %ld\n", nOneValidate);
+
+    // ... now validating repeatedly should be quick:
+    // 2.8GHz machine, -g build: Sign takes ~760ms,
+    // uncached Verify takes ~250ms, cached Verify takes ~50ms
+    // (for 100 single-signature inputs)
+    mst1 = boost::posix_time::microsec_clock::local_time();
+    for (int i = 0; i < 5; i++)
+        for (int j = 0; j < tx.vin.size(); j++)
+            BOOST_CHECK(VerifySignature(orphans[j], tx, j, true, SIGHASH_ALL));
+    mst2 = boost::posix_time::microsec_clock::local_time();
+    msdiff = mst2 - mst1;
+    long nManyValidate = msdiff.total_milliseconds();
+    if (fDebug) printf("DoS_Checksig five: %ld\n", nManyValidate);
+
+    BOOST_CHECK_MESSAGE(nManyValidate < nOneValidate, "Signature cache timing failed");
+
+    // Empty a signature, validation should fail:
+    CScript save = tx.vin[0].scriptSig;
+    tx.vin[0].scriptSig = CScript();
+    BOOST_CHECK(!VerifySignature(orphans[0], tx, 0, true, SIGHASH_ALL));
+    tx.vin[0].scriptSig = save;
+
+    // Swap signatures, validation should fail:
+    std::swap(tx.vin[0].scriptSig, tx.vin[1].scriptSig);
+    BOOST_CHECK(!VerifySignature(orphans[0], tx, 0, true, SIGHASH_ALL));
+    BOOST_CHECK(!VerifySignature(orphans[1], tx, 1, true, SIGHASH_ALL));
+    std::swap(tx.vin[0].scriptSig, tx.vin[1].scriptSig);
+
+    // Exercise -maxsigcachesize code:
+    mapArgs["-maxsigcachesize"] = "10";
+    // Generate a new, different signature for vin[0] to trigger cache clear:
+    CScript oldSig = tx.vin[0].scriptSig;
+    BOOST_CHECK(SignSignature(keystore, orphans[0], tx, 0));
+    BOOST_CHECK(tx.vin[0].scriptSig != oldSig);
+    for (int j = 0; j < tx.vin.size(); j++)
+        BOOST_CHECK(VerifySignature(orphans[j], tx, j, true, SIGHASH_ALL));
+    mapArgs.erase("-maxsigcachesize");
+
+    LimitOrphanTxSize(0);
+}
+
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/util.cpp b/src/util.cpp
index 9e7a8c0348..08e3625b3d 100644
--- a/src/util.cpp
+++ b/src/util.cpp
@@ -176,6 +176,12 @@ int GetRandInt(int nMax)
     return GetRand(nMax);
 }
 
+uint256 GetRandHash()
+{
+    uint256 hash;
+    RAND_bytes((unsigned char*)&hash, sizeof(hash));
+    return hash;
+}
 
 
 
diff --git a/src/util.h b/src/util.h
index 47065d8426..5b58147ce6 100644
--- a/src/util.h
+++ b/src/util.h
@@ -164,6 +164,7 @@ boost::filesystem::path GetSpecialFolderPath(int nFolder, bool fCreate = true);
 void ShrinkDebugFile();
 int GetRandInt(int nMax);
 uint64 GetRand(uint64 nMax);
+uint256 GetRandHash();
 int64 GetTime();
 void SetMockTime(int64 nMockTimeIn);
 int64 GetAdjustedTime();