# Blockchain Traceability Process for Hairy Crab Based on Cuckoo Filter
## 2 Filter Technical Analysis
### Cuckoo Filter  
A cuckoo hash table is a highly optimised hash table structure whose main advantage is its ability to efficiently handle the insertion and query process of a single element [25; 26; 27; 28; 29]. In a cuckoo hash table, for any given element x, its mapping to the hash table follows a specific mapping rule that ensures an even distribution of elements. However, a so-called storage conflict occurs when an element is mapped to a bucket that is already full. At this point, a strategy must be adopted to redistribute the conflicting elements to ensure the stability and efficiency of the system. As shown in Figure 2a, when the expected positions of element x in all sub-hash tables are occupied, a mechanism called 'kick-out' is triggered. This mechanism first removes the conflicting element a from its current sub-hash table and tries to reinsert it into the next sub-hash table. If successive sub-hash tables are full, the process is repeated until a suitable storage location is found. If no available storage location is found after successive attempts, this indicates that the storage capacity of the hash table has reached its design limit. In this case, the system must be expanded to accommodate the growing demand for element storage in order to maintain the performance and scalability of the hash table.  
A cuckoo filter is an approximate membership test data structure based on cuckoo hashing [30; 31; 32; 33; 34; 35]. Unlike the traditional cuckoo hash table, the cuckoo filter improves on the  
Figure 2: Cuckoo hash tables and cuckoo filters.  
storage strategy by saving space by not storing the complete elements but only keeping the fingerprint information of the elements. The architecture of this design enables a substantial reduction in the necessary storage space for cuckoo filters while concurrently sustaining a high level of query performance. However, the reliance on fingerprint data for element identification within the cuckoo filter does introduce a potential for misclassification. Specifically, there exists a risk that elements not actually present in the filter might be erroneously recognised as existing members. Despite this possibility, the rate of such errors is controllable and is confined within established theoretical limits.  
As shown in Figure 2c, the cuckoo filter structure relies on a hash table consisting of b buckets. Each bucket contains c cells dedicated to storing the fingerprint information of an element. When an element x is inserted, it is mapped to two different buckets using two hash functions. Each bucket holds at most c elements. To locate the buckets and obtain the fingerprint information, the cuckoo filter uses two hash functions: h\({}_{1}\)(x) and the fingerprint hash function f(x). Specifically, if the fingerprint of an element x is f(x), its corresponding two bucket positions index\({}_{1}\) and index\({}_{2}\) are calculated by the following formula:  
\[index_{1}=h_{1}(x) \tag{3}\]  
\[index_{2}=h_{1}(x)\oplus f(x) \tag{4}\]  
By knowing the position of one bucket and its fingerprint, the position of another bucket can be deduced using the operation of different-or (XOR). This approach simplifies the computation process. Figure 2c demonstrates its insertion mechanism, similar to the cuckoo hash table, which involves a reinsertion process to improve storage efficiency. By optimising this process, the storage space can be maximised. This design not only improves the performance of the filter but also ensures that a low probability of misclassification is maintained with limited resources. The method finds a good balance between space efficiency and operational complexity and is suitable for a variety of application scenarios. In addition, for the case of fingerprint length e, the misjudgement rate p can be calculated by the formula \(p=\frac{c}{2^{c-1}}\).