# Blockchain Traceability Process for Hairy Crab Based on Cuckoo Filter
## 2 Filter Technical Analysis  
### Bloom Filter  
In the field of data structure research, bitmap filters are an important technique whose origin dates back to the 1970s [18]. A Bloom filter consists of a Boolean array of length m bits and k independent hash functions, which uniquely identify elements, and fast querying is achieved by mapping elements to random locations in the array through the hash functions [19; 20; 21; 22; 23; 24]. Its core advantage lies in the efficient mapping of elements using multiple hash functions while maintaining a low false positive rate. During insertion, elements are mapped to k positions of a Boolean array by k hash functions, and these positions are set to true. When querying, the existence of the element is determined by detecting the values of these positions. Figure 1 visualises the insertion process of elements x and y with three hash functions as an example, highlighting the efficiency and accuracy of Bloom filters when dealing with large amounts of data.  
Bloom filters are an efficient data structure designed to quickly determine whether an element belongs to a particular set. At its core is a bit array of length m. Element features are mapped to the bit array by k hash functions to achieve constant time complexity queries. On insertion, element features are mapped and set to 1. On query, feature values are mapped, and the bit array is checked; if they are all 1, then they may exist. Otherwise, it is determined that they do not exist. Eigenvalue extraction can be achieved by independent hash functions or by splitting a single hash. By adjusting m and k, the Bloom filter minimises the false positive rate and optimises the spatial efficiency. When designing a Bloom filter for storing n data items, the optimal values of m and k can be calculated by the following  
Figure 1: Bloom filter data structure example.  
mathematical formula to ensure that the false positive rate is minimised while minimising the space occupation.  
\[m=-\frac{n\times\ln p}{\left(\ln 2\right)^{2}} \tag{1}\]  
\[k=\ln 2\times\frac{m}{n} \tag{2}\]  
Bloom filters have significant advantages in terms of storage and query efficiency. Taking the example of storing 10 billion pieces of data (i.e., n = 10\({}^{10}\)), if the false positive rate \(p\) is set to be no more than 3%, according to the theoretical calculation, the value of m/n is about 7.30. The theoretical optimal value for k is about 5.06, but in practice, the smallest integer larger than this value should be chosen, i.e., k should be taken to be 6. Therefore, the number of hash functions should be set to be 6 in practice, and at this time, the value of m/n is about 4.16, resulting in a value of m of approximately 4.16 \(\times\) 10\({}^{10}\) bits. Converted to bytes, this is 5.2 \(\times\) 10\({}^{9}\) bytes, which is equivalent to 4.84 GB, and this amount of storage can be easily stored in the server's memory. In contrast, if the method of recording the hash value of each data item is used, with each hash value occupying 32 bytes, the overhead of storing 10 billion pieces of data would be 3.2 \(\times\) 10\({}^{11}\) bytes, or about 298.02 GB, which is typically beyond the storage capacity of typical server memory.