Transaction flow networks are crucial in detecting illicit activities such as wash trading, credit card fraud, cashback arbitrage fraud, and money laundering. Our collaborator, Grab, a leader in digital payments in Southeast Asia, faces increasingly sophisticated fraud patterns in its transaction flow networks. In industry settings such as Grab's fraud detection pipeline, identifying fraudulent activities heavily relies on detecting dense flows within transaction networks. Motivated by this practical foundation, we propose theS-T densest flow(STDF) query. Given a transaction flow networkG, a source setS, a sink setT, and a size thresholdk, the query outputs subsets$S^{\prime}\subseteq S$and$T^{\prime}\subseteq T$such that the maximum flow from$S^{\prime}$to$T^{\prime}$is densest, with$\vert S^{\prime}\cup T^{\prime}\vert\geq k$. Recognizing the NP-hardness of the STDF query, we develop an efficient divide-and-conquer algorithm,$\mathsf{Conan}$. Driven by industry needs for scalable and efficient solutions, we introduce an approximate flow-peeling algorithm to optimize the performance of$\mathsf{Conan}$, enhancing its efficiency in processing large transaction networks. Our approach has been integrated into Grab's fraud detection scenario, resulting in significant improvements in identifying fraudulent activities. Experiments show that$\mathsf{Conan}$, outperforms baseline methods by up to three orders of magnitude in runtime and more effectively identifies the densest flows. We showcase$\mathsf{Conan}$'s applications in fraud detection on transaction flow networks from our industry partner, Grab, and on non-fungible tokens (NFTs).
Sungmin Lee, Kichang Lee, Gyeongmin Han, JeongGil Ko
Many location-based services rely on a point-in-polygon test ( PiP ), checking whether a point or a trajectory lies inside a geographic zone. Since geometric operations are expensive in zero-knowledge proofs, privately performing the PiP test is challenging. In this paper, we answer the research questions of how different ways of encoding zones affect accuracy and proof cost by exploiting grid-based lookup tables under a fixed STARK execution model. Beyond a Boolean grid-based baseline that marks cells as in- or outside, we explore a distance-aware encoding approach that stores how far each cell is from a zone boundary and uses interpolation to reason within a cell. % Our experiments on real-world data demonstrate that the proposed distance-aware approach achieves higher accuracy on coarse grids with only a moderate verification overhead, making zone encoding the key lever for efficient zero-knowledge spatial checks. Our experiments on real-world data demonstrate that the proposed distance-aware approach achieves higher accuracy on coarse grids (max. % 60%p 60%p accuracy gain) with only a moderate verification overhead (approximately 1.4×), making zone encoding the key lever for efficient zero-knowledge spatial checks.
The evolution of blockchain technology, from its origins as a decentralized ledger for cryptocurrencies to its broader applications in areas like decentralized finance (DeFi), has significantly transformed financial ecosystems while introducing new challenges such as Maximum Extractable Value (MEV). This paper explores MEV on the Polygon blockchain, with a particular focus on Atomic Arbitrage (AA) transactions. We establish criteria for identifying AA transactions and analyze key factors such as searcher behavior, bidding dynamics, and token usage. Utilizing a dataset spanning 22 months and covering 23 million blocks, we examine MEV dynamics with a focus on Spam-based and Auction-based backrunning strategies. Our findings reveal that while Spam-based transactions are more prevalent, Auction-based transactions demonstrate greater profitability. Through detailed examples and analysis, we investigate the interactions between network architecture, transaction sequencing, and MEV extraction, offering comprehensive insights into the evolution and challenges of MEV in decentralized ecosystems. These results emphasize the need for robust transaction ordering mechanisms and highlight the implications of emerging MEV strategies for blockchain networks.
Haotian Wu, Yuzhe Tang, Zhaoyan Shen, Jun Tao · 6 authors
Blockchain has become a popular paradigm for secure and immutable data storage. Despite its numerous applications across various fields, concerns regarding the user privacy and result integrity during data queries persist. Additionally, the need for rich query functionalities to harness the full potential of blockchain data remains an area ripe for exploration. In order to address these challenges, our paper first utilizes a framework based on the Trusted Execution Environment (TEE) and oblivious RAM technique to achieve both privacy and data integrity. To enhance the query efficiency over the entire blockchain, we then devise a two-level learned indexing methodology named TELEX within the TEE for both integer and string keys. We also propose different query processing algorithms for versatile query types, including exact queries, aggregate queries, Boolean queries, and range queries. By implementing the prototype and conducting extensive evaluation, we demonstrate the feasibility and remarkable improvement in efficiency compared to existing solutions.
The environmental impact of Bitcoin mining in Kazakhstan, which is currently the third-largest market in the world by hash rate, is coming under further scrutiny. Data on the production of renewable energy and related carbon footprints are essential for evaluating the situation. To create a thorough picture of how Bitcoin mining and environmental responsibility connect in Kazakhstan, this paper allows for the analysis and prediction of the interactions between carbon emissions, renewable energy use, and Bitcoin mining. Using a q-rung orthopair fuzzy hypersoft set (q-ROFHS)-based multi-criteria decision-making technique can improve research on the environmental effects of Bitcoin mining, the integration of renewable energy sources, and the corresponding carbon footprints. The analytic hierarchy process is used to identify the best pollution reduction strategies while taking feasibility and cost-effectiveness into account. The proposed approach will assist the business in achieving its environmental objectives, lessen its negative effects on the environment, and promote a greener future. This study guarantees a more precise and dependable evaluation of pollution control tactics, considering not only the effects on the environment but also practicality and affordability. The outcomes highlight the developed approach's effectiveness and stability in managing complicated information within the parameters of q-ROFHS.
Behkish Nassirzadeh, Albert Heinle, Stefanos Leonardos, Anwar Hasan · 5 authors
Blockchain integration in industries like online advertising is hindered by its connectivity limitations to off-chain data. These industries heavily rely on precise counting systems for collecting and analyzing off-chain data. This requires mechanisms, often called oracles, to feed off-chain data into smart contracts. However, current oracle solutions are ill-suited for counting systems since the oracles do not know when to expect the data, posing a significant challenge. To address this, we present CountChain, a decentralized oracle network for counting systems. In CountChain, data is received by all oracle nodes, and any node can submit a proposition request. Each proposition contains enough data to evaluate the occurrence of an event. Only randomly selected nodes participate in a game to evaluate the truthfulness of each proposition by providing proof and some stake. Finally, the propositions with the outcome of True increment the counter in a smart contract. Thus, instead of a contract calling oracles for data, in CountChain, the oracles call a smart contract when the data is available. Furthermore, we present a formal analysis and experimental evaluation of the system's parameters on over half a million data points to obtain optimal system parameters. In such conditions, our game-theoretical analysis demonstrates that a Nash equilibrium exists wherein all rational parties participate with honesty.
Elvira Albert, María García de la Banda, Alejandro Hernández-Cerezo, Alexey Ignatiev · 6 authors
Given a loop-free sequence of instructions, superoptimization techniques use a constraint solver to search for an equivalent sequence that is optimal for a desired objective. The complexity of the search grows exponentially with the length of the solution being constructed and the problem becomes intractable for large sequences of instructions. This paper presents a new approach to superoptimizing stack-bytecode via three novel components: (1) a greedy algorithm to refine the bound on the length of the optimal solution; (2) a new representation of the optimization problem as a set of weighted soft clauses in MaxSAT; (3) a series of domain-specific dominance and redundant constraints to reduce the search space for optimal solutions. We have developed a tool, named S uper S tack , which can be used to find optimal code translations of modern stack-based bytecode, namely WebAssembly or Ethereum bytecode. Experimental evaluation on more than 500,000 sequences shows the proposed greedy, constraint-based and SAT combination is able to greatly increase optimization gains achieved by existing superoptimizers and reduce to at least a fourth the optimization time.
Tracking and tracing of assets using decentralized systems demand optimized data formats to balance storage costs and retrieval performance. This paper proposes a cost-effective sensor data format tailored for decentralized storage of geographic point locations on XNO, a distributed ledger technology. The proposed format optimizes storage by encoding location data in a compact yet retrievable manner, leveraging spatial indexing techniques to facilitate efficient and transparent querying. This solution presents a promising approach for scalable and affordable asset tracking and tracing using the highly available and transparent decentralized environments, with potential applications across various industries.
Mohammed Alghazwi, Dewi Davies-Batista, Dimka Karastoyanova, Fatih Türkmen
Aggregate statistics play an important role in extracting meaningful insights from distributed data while preserving privacy. A growing number of application domains, such as healthcare, utilize these statistics in advancing research and improving patient care. In this work, we explore the challenge of input validation and public verifiability within privacy-preserving aggregation protocols. We address the scenario in which a party receives data from multiple sources and must verify the validity of the input and correctness of the computations over this data to third parties, such as auditors, while ensuring input data privacy. To achieve this, we propose the "VPAS" protocol, which satisfies these requirements. Our protocol utilizes homomorphic encryption for data privacy, and employs Zero-Knowledge Proofs (ZKP) and a blockchain system for input validation and public verifiability. We constructed VPAS by extending existing verifiable encryption schemes into secure protocols that enable N clients to encrypt, aggregate, and subsequently release the final result to a collector in a verifiable manner. We implemented and experimentally evaluated VPAS with regard to encryption costs, proof generation, and verification. The findings indicate that the overhead associated with verifiability in our protocol is 10x lower than that incurred by simply using conventional zkSNARKs. This enhanced efficiency makes it feasible to apply input validation with public verifiability across a wider range of applications or use cases that can tolerate moderate computational overhead associated with proof generation.
The widespread availability of tools to collect and share spatial data enables us to produce a large amount of geographic information on a daily basis. This enormous production of spatial data requires scalable data management systems. Geospatial architectures have changed from clusters to cloud architectures and more parallel and distributed processing platforms to be able to tackle these challenges. Peer-to-peer (P2P) systems as a backbone of distributed systems have been established in several application areas such as web3, blockchains, and crypto-currencies. Unlike centralized systems, data storage in P2P networks is distributed across network nodes, providing scalability and no single point of failure. However, managing and processing queries on these networks has always been challenging. In this work, we propose a spatio-temporal indexing data structure, DSTree. DSTree does not require additional Distributed Hash Trees (DHTs) to perform multi-dimensional range queries. Inserting a piece of new geographic information updates only a portion of the tree structure and does not impact the entire graph of the data. For example, for time-series data, such as storing sensor data, the DSTree performs around 40% faster in spatio-temporal queries for small and medium datasets. Despite the advantages of our proposed framework, challenges such as 20% slower insertion speed or semantic query capabilities remain. We conclude that more significant research effort from GIScience and related fields in developing decentralized applications is needed. The need for the standardization of different geographic information when sharing data on the IPFS network is one of the requirements.
A system of zero-knowledge proofs on graph signatures has been proposed, where a graph can be signed, and the owner of the graph signature can prove a graph relation such as the connectivity and isolation of any two vertexes on the graph without disclosing all information about the graph. The correctness of the graph information is guaranteed by the signature. One of the applications is a virtualized infrastructure, where an infrastructure provider manages a distributed system, and each tenant is allocated a specific portion of this infrastructure for use. Tenants need to check with the provider that their resources are properly connected (connectivity) and that their resources are properly separated from the resources of other tenants (isolation). On the other hand, the provider cannot simply disclose the entire infrastructure topology to each tenant. Using the zero-knowledge proof system on graph signatures, both requirements can be addressed. Previously, an efficient zero-knowledge proof system on graph signatures using a bilinear-map accumulator has been proposed, where the verification time and the size of the proof data do not depend on the number of graph vertexes and edges. However, this system has two problems. First, since the proof does not include labels, it is not possible to prove the connectivity considering network bandwidth and cost. Second, since it assumes undirected graphs, it cannot handle applications on directed graphs such as network flows. In this paper, we extend the previous system and propose a zero-knowledge proof system of the connectivity for directed graphs where each edge has labels. We implemented our system on a PC using a pairing library and evaluate it by measuring the processing times. Compared to the conference version of this paper, we show the formal definitions and the security proofs of our proposed system, and add implementation-based evaluations reflecting the application to the virtualized infrastructure.
NFTs (Non-Fungible Tokens) are a type of digital asset based on blockchain technology that has become an attractive investment tool for many investors. This paper proposes a model based on knowledge graphs and LSTM (Long Short-Term Memory) networks to provide investors with a ranking prediction of future NFT returns, assisting traders in making more accurate investment decisions in the NFT market. To verify the usability and accuracy of the model, we collected data from 345 different types of NFTs on the OpenSea platform and conducted experimental validation, comparing our method with other benchmark methods to demonstrate the accuracy of our proposed method in practical scenarios.
Today’s organizations utilize a plethora of heterogeneous and autonomous DBMSes, many of those being spread across different geo-locations. It is therefore crucial to have effective and efficient cross-database query processing capabilities. We present XDB, an efficient middleware system that runs cross-database analytics over existing DBMSes. In contrast to traditional query processing systems, XDB does not rely on any mediating execution engine to perform cross-database operations (e.g., joining data from two DBMSes). It delegates an entire query execution including cross-database operations to underlying DBMSes. At its core, it comprises an optimizer and a delegation engine: the optimizer rewrites cross-database queries into a delegation plan, which captures the semantics as well as the mechanics of a fully decentralized query execution; the delegation engine then deploys the plan to the underlying DBMSes via their declarative interfaces. Our experimental study based on the TPC-H benchmark data shows that XDB outperforms state-of-the-art systems (Garlic and Presto) by up to 6× in terms of runtime and up to 3 orders of magnitude in terms of data transfer.
Hao Xu, Bin Xiao, Xiulong Liu, Li Wang · 8 authors
Owing to the attractive properties of decentralization, unforgeability, transparency, and traceability, blockchain is increasingly being used in various scenarios such as supply chain and public services, where massive Spatial-Temporal-Keywords (STK) transactions need to be packaged. However, due to the multi-dimensionality and randomness of STK transactions, existing solutions fail to enable queries in a verifiable and efficient way for blockchains storing multidimensional transactions. To this end, this article takes the first step to propose an authenticated and efficient query approach in hybrid blockchain systems consisting of on-chain and off-chain parts. We first design a data structure named MRK-Tree in the block body, which organizes STK transactions for efficient nodes pruning of both kNN and range queries. Then we propose an improved block header, which improves the efficient pruning of blocks on the basis of ensuring the authentication of query results. Also, we design a cross-block searching algorithm named Efficient Block Pruning (EBP) and intra-block searching algorithms named Authenticated kNN/Range Query (AKQ/ARQ) to accelerate authenticated queries for multiple MRK-Trees in the hybrid blockchain systems. Authentication mechanisms are proposed to ensure the soundness and completeness of query results. Rigorous security analysis validates the practicability of the proposed approach. We build a blockchain prototype to comprehensively evaluate the performance of proposed query schemes. Extensive evaluation results with real datasets reveal that our approach can ensure authenticated queries, meanwhile improving the time efficiency by up to 36.45x and space efficiency by up to 4 orders of magnitude compared with the well-known benchmark query schemes.
Blockchain Technology Applications and Security
Data Management and Algorithms
Advanced Steganography and Watermarking Techniques
The cryptocurrency, often known as virtual or digital currency, is one of the most significant breakthroughs brought about by digitalization. It has been mentioned recently, an innovative system for stockholders in particular. Cryptocurrencies of all kinds, including Bitcoin, Shib, Dogecoin, and Tether are decentralized. Categorization complicates decision-making (DM) as well as the transfer of uncertainty and digital currency validation. The multi-attribute group decision-making (MAGDM) method is defined in this article using the Frank weighted averaging and Frank weighted geometric aggregation operators (AOs). This research examines the uniqueness of the q-rung orthopair fuzzy hypersoft set (qROFHSS) that is responsive to volatilities, vagueness, doubt, and inaccurate data. Additionally, certain essential qROFHSS topics are covered in this study. The framework presented here is the greatest alternative for understanding electronic money. This research supports the difficulty of situations involving making choices that must take into account a variety of qualities and sub-attributes to select the best choice. We see that Bitcoin has a variety of applications and that cryptocurrencies have an excellent chance to emerge as a prominent benefit lesson in financial choice-making.
Partial orders and directed acyclic graphs are common data structures that arise naturally in numerous applications, and that define order between data points. Examples are orders of tasks in a project plan, transaction orders in distributed ledgers and execution sequences in computer programs, to mention a few.\nOn the other hand, hierarchical clustering is one of the oldest and most used methods for unsupervised classification and exploratory data analysis. In spite of this, few methods are rigged to take into account the information encoded in the order relation when performing hierarchical clustering of partially ordered data.\nIn his research, Daniel R. Bakkelund has developed new mathematical theory and algorithms to include this information in methods for hierarchical clustering, resulting in the concept of "order preserving hierarchical clustering".\nThe efficacy of theories are demonstrated through experiments on real world data, and show that the in comparison with existing methods, the new methods excel both in cluster quality and order preservation.
High-Definition (HD) map service requires more frequent update and much larger data volume than traditional map services, so that it is very difficult to handle HD map update by existing offline data collection such as survey fleets, and centralized cloud-based map services. To solve this problem, vehicle crowd-sourcing and edge computing infrastructure are proposed to timely capture the change of the physical world and distributedly process the huge amount of raw data close to the vehicles. In such a decentralized environment, Distributed Ledger Technology (DLT), such as blockchain, is very promising to meet some of the important requirements of data integrity and traceability of map update, but it is challenging to meet the requirement of frequent map update and scale to a large-scale system. In this work, we propose a salable HD map update management system by leveraging multiple blockchain networks in parallel and dynamically assign the generated map update to the corresponding blockchains according to the location and update frequency requirements. To verify the proposed system, we prototyped it based on the Hyperledger Fabric, an open-source implementation of consortium blockchain, and tested it in the lab environment.