A Bloom-Filter-Based Unique Address Checking Approach for DAG-Based Blockchain Systems

Authors:
Publisher website
Google Scholar
Abstract
Winternitz one-time signature (WOTS) is a quantum-resistant signature mechanism that has been widely used in direct acyclic graph (DAG)-based blockchain systems. However, it needs to generate a unique private/public key pair for each transaction, which severely limits blockchain performance by performing a time-consuming unique address checking process when generating transactions. This article proposes a bloom-filter-based approach, called ABACUS, to optimize the unique address checking process in WOTS. In ABACUS, we separate the large address space into multiple small subspaces and apply bloom filters to perform uniqueness checking for all addresses in one subspace. Specifically, we propose a two-level address space mechanism to strike a balance between the checking efficiency and the memory/storage space overhead of the bloom filter design. A bucket-based scalable bloom filter (SBF) design is proposed to match the growth of used addresses with efficient I/O access by storing all sub-bloom-filters together in one bucket. To further reduce disk I/Os, ABACUS incorporates an in-memory write buffer and a read-only cache. To reclaim wasted addresses, we also propose a layered address recycling mechanism by efficiently checking and reusing unused addresses that were identified as used due to false positives of bloom filters. We have implemented a fully functional prototype of ABACUS and integrated it into IOTA, a widely used DAG-based blockchain system. A series of experiments have been conducted on a private IOTA system. Experimental results show that ABACUS can significantly reduce the transaction generation time by up to four orders of magnitude, and achieve up to $3\times $ boost on the system throughput with more than 80% space-saving. We have released the open-source code of ABACUS for public access.
Funding Information
  • Research Grants Council of the Hong Kong Special Administrative Region, China (GRF 14219422)
  • Direct Grant for Research, The Chinese University of Hong Kong (4055151)
  • National Natural Science Foundation of China (62272271)
  • Key Research and Development Program of Shandong Province (2023CXPT002)

This publication has 31 references indexed in Scilit: