# Securing IoT: Mitigating Sybil Flood Attacks with Bloom Filters and Hash Chains
## 2 Background
### Bloom Filters  
Bloom filters offer a space-efficient data structure that enables efficient query responses, making them ideal for scenarios where fast lookups are crucial [13]. This efficiency comes with a trade-off, however, in the possibility of false positives (FP), where a query element might be incorrectly identified as a member of the set. However, unlike false negatives (FN), which Bloom filters are guaranteed to avoid, false positives indicate a potential membership that needs further verification. FNs occur when a query element is erroneously reported as absent even though it is present in the dataset. This characteristic makes Bloom filters particularly valuable in scenarios where a certain level of FPs is tolerable or where secondary verification mechanisms can be employed to eliminate FPs post-filtering [14]. Due to their rapid query times and space-efficient nature, Bloom filters have found widespread application in various domains. These data structures are particularly advantageous for tasks such as weak password detection, unique username identification, and suspicious URL caching within social media platforms. Their ability to conserve storage space makes them well suited for applications where managing large datasets is crucial. Figure 2 visually depicts the operation of a simple Bloom filter. Initially, all bits within the filter array are set to zero, representing an empty set. During the insertion stage, elements are added to the Bloom filter. Each element is inserted as follows:  
* Hashing: The element undergoes hashing using multiple hash functions, typically denoted as \(K\). This process maps the element to a set of (\(K\)) hash values. * Modulo Operation: Each hash value is then subjected to a modulo operation with the size \(M\) of the Bloom filter array. This ensures that the resulting index falls within the valid range of the array (0 to \(M-1\)). * Bit Setting: The corresponding bit positions in the Bloom filter array, determined by the modulo operation results, are set to one. Consider the example of Entry 1 in Figure 2. The entry is hashed using two different hash functions. These hash values undergo a modulo operation by 12. Consequently, positions 4 and 8 within the Bloom filter array are set to 1. During a search operation, the queried element undergoes hashing with the same functions used for insertion, generating multiple hash values. These values are subjected to a modulo operation to obtain valid indices within the filter array. A bitwise AND operation is then performed between the corresponding bit positions in the array and a bit vector of ones. If the resulting vector is equal to the search vector (as exemplified by Search 2 in Figure 2), it indicates a potential match. However, due to the probabilistic nature of Bloom filters, there is a chance of a false positive (the element might not actually be present; see the example of Search 3 in Figure 2). Conversely, any unset bit reveals the element's definitive absence (guaranteed true negative), as demonstrated by Search 1 in Figure 2.  
The design and application of Bloom filters necessitates careful consideration of the False Positive Rate (FPR), as false positives can lead to unnecessary resource consumption, increased latency, and potentially compromised network security if not managed effectively [15]. To minimize the inherent tradeoff between query speed and accuracy, key parameters require thoughtful configuration. These parameters include:  
* The size of the Bloom filter (\(N\)). * The number of entries stored in the filter (\(M\)). * The number of different hash functions employed (\(K\)). The probability of encountering a false positive during a search operation can be calculated using the following formula:  
\[FPR=\left(1-\left(1-\frac{1}{M}\right)^{KN}\right)^{K}. \tag{1}\]  
The Formula (1) calculates the FPR by considering the interplay between the following key parameters:  
* Array size (\(N\)): A larger array size reduces the probability of collisions during hash function application.