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  }