vendor/github.com/btcsuite/btcd/txscript/sigcache.go

   1 // Copyright (c) 2015-2016 The btcsuite developers
   2 // Use of this source code is governed by an ISC
   3 // license that can be found in the LICENSE file.
   4
   5 package txscript
   6
   7 import (
   8         "sync"
   9
  10         "github.com/btcsuite/btcd/btcec"
  11         "github.com/btcsuite/btcd/chaincfg/chainhash"
  12 )
  13
  14 // sigCacheEntry represents an entry in the SigCache. Entries within the
  15 // SigCache are keyed according to the sigHash of the signature. In the
  16 // scenario of a cache-hit (according to the sigHash), an additional comparison
  17 // of the signature, and public key will be executed in order to ensure a complete
  18 // match. In the occasion that two sigHashes collide, the newer sigHash will
  19 // simply overwrite the existing entry.
  20 type sigCacheEntry struct {
  21         sig    *btcec.Signature
  22         pubKey *btcec.PublicKey
  23 }
  24
  25 // SigCache implements an ECDSA signature verification cache with a randomized
  26 // entry eviction policy. Only valid signatures will be added to the cache. The
  27 // benefits of SigCache are two fold. Firstly, usage of SigCache mitigates a DoS
  28 // attack wherein an attack causes a victim's client to hang due to worst-case
  29 // behavior triggered while processing attacker crafted invalid transactions. A
  30 // detailed description of the mitigated DoS attack can be found here:
  31 // https://bitslog.wordpress.com/2013/01/23/fixed-bitcoin-vulnerability-explanation-why-the-signature-cache-is-a-dos-protection/.
  32 // Secondly, usage of the SigCache introduces a signature verification
  33 // optimization which speeds up the validation of transactions within a block,
  34 // if they've already been seen and verified within the mempool.
  35 type SigCache struct {
  36         sync.RWMutex
  37         validSigs  map[chainhash.Hash]sigCacheEntry
  38         maxEntries uint
  39 }
  40
  41 // NewSigCache creates and initializes a new instance of SigCache. Its sole
  42 // parameter 'maxEntries' represents the maximum number of entries allowed to
  43 // exist in the SigCache at any particular moment. Random entries are evicted
  44 // to make room for new entries that would cause the number of entries in the
  45 // cache to exceed the max.
  46 func NewSigCache(maxEntries uint) *SigCache {
  47         return &SigCache{
  48                 validSigs:  make(map[chainhash.Hash]sigCacheEntry, maxEntries),
  49                 maxEntries: maxEntries,
  50         }
  51 }
  52
  53 // Exists returns true if an existing entry of 'sig' over 'sigHash' for public
  54 // key 'pubKey' is found within the SigCache. Otherwise, false is returned.
  55 //
  56 // NOTE: This function is safe for concurrent access. Readers won't be blocked
  57 // unless there exists a writer, adding an entry to the SigCache.
  58 func (s *SigCache) Exists(sigHash chainhash.Hash, sig *btcec.Signature, pubKey *btcec.PublicKey) bool {
  59         s.RLock()
  60         entry, ok := s.validSigs[sigHash]
  61         s.RUnlock()
  62
  63         return ok && entry.pubKey.IsEqual(pubKey) && entry.sig.IsEqual(sig)
  64 }
  65
  66 // Add adds an entry for a signature over 'sigHash' under public key 'pubKey'
  67 // to the signature cache. In the event that the SigCache is 'full', an
  68 // existing entry is randomly chosen to be evicted in order to make space for
  69 // the new entry.
  70 //
  71 // NOTE: This function is safe for concurrent access. Writers will block
  72 // simultaneous readers until function execution has concluded.
  73 func (s *SigCache) Add(sigHash chainhash.Hash, sig *btcec.Signature, pubKey *btcec.PublicKey) {
  74         s.Lock()
  75         defer s.Unlock()
  76
  77         if s.maxEntries <= 0 {
  78                 return
  79         }
  80
  81         // If adding this new entry will put us over the max number of allowed
  82         // entries, then evict an entry.
  83         if uint(len(s.validSigs)+1) > s.maxEntries {
  84                 // Remove a random entry from the map. Relying on the random
  85                 // starting point of Go's map iteration. It's worth noting that
  86                 // the random iteration starting point is not 100% guaranteed
  87                 // by the spec, however most Go compilers support it.
  88                 // Ultimately, the iteration order isn't important here because
  89                 // in order to manipulate which items are evicted, an adversary
  90                 // would need to be able to execute preimage attacks on the
  91                 // hashing function in order to start eviction at a specific
  92                 // entry.
  93                 for sigEntry := range s.validSigs {
  94                         delete(s.validSigs, sigEntry)
  95                         break
  96                 }
  97         }
  98         s.validSigs[sigHash] = sigCacheEntry{sig, pubKey}
  99 }