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