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.
Muhammad Saqlain, Vladimir Šimić, Dragan Pamucar
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.
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.
Matteo Loporchio, Anna Bernasconi, Damiano Di Francesco Maesa, Laura Ricci
In many blockchain networks, light nodes (e.g. mobile clients) with few computational resources must rely on more powerful full nodes to retrieve transactions from the chain. However, in this untrusted environment a malicious full node could deliver altered or incomplete information, requiring query authentication techniques to ensure the integrity of the results. To this aim, we study an authentication mechanism for spatial information (i.e. data representing the location, size, and shape of objects in a geographical coordinate system). We assume that light nodes issue range queries to obtain data from a single block. To enable authentication, we propose to construct a Merkle R-tree for each block and embed its root into the corresponding header, so that full nodes can exploit it to fetch information and construct a proof of integrity for lightweight clients. We also develop a new algorithm based on sorting and partitioning for constructing Merkle R-trees from a set of spatial transactions and employ space-filling curves to preserve the locality of elements. We examine its theoretical complexity, evaluate it experimentally on a real data set and compare it against other popular construction strategies. Results show that, as queries become more selective, trees generated with our solution improve query performance and reduce verification times with respect to other approaches. Moreover, we observe that the overhead induced by the tree construction is negligible if compared to the average inter-block time of popular blockchain protocols such as Bitcoin and Ethereum.
We study the growth of a time-ordered rooted tree by probabilistic attachment of new vertices to leaves. We construct a likelihood function of the leaves based on the connectivity of the tree. We take such connectivity to be induced by the merging of directed ordered paths from leaves to the root. Combining the likelihood with an assigned prior distribution leads to a posterior leaf distribution from which we sample attachment points for new vertices. We present computational examples of such Bayesian tree growth. Although the discussion is generic, the initial motivation for the paper is the concept of a distributed ledger, which may be regarded as a time-ordered random tree that grows by probabilistic leaf attachment.
Web-based public participatory GIS (PPGIS) has been used by governmental organizations to facilitate people's contribution to decision-making processes. However, these applications do not provide an open and transparent environment for public participation. This study suggests that PPGISs should be developed as decentralized applications (DApp) based on Ethereum blockchain technology to have a fully open, transparent, and accountable environment for public participation. In a blockchain-based PPGIS, the collected data are securely saved on the blockchain. The validity of the data, replicated on the nodes of the peer-to-peer blockchain network, is ensured through a consensus process without any central control. The data is tamper-free and immutable. Additionally, the data is openly accessible to institutions and citizens. A prototype PPGIS was developed as a DApp through which users can participate in the site selection of urban facilities. Using the application, they compare and rank different criteria. The system solves an analytic hierarchy process to calculate the weights of the criteria. A suitability map is generated afterward and published to be used by both citizens and decision-makers. The feasibility of the application, along with the issues that need to be considered while using blockchain technology for urban planning and development, are thoroughly discussed.
Abstract Partial orders and directed acyclic graphs are commonly recurring data structures that arise naturally in numerous domains and applications and are used to represent ordered relations between entities in the domains. Examples are task dependencies in a project plan, transaction order in distributed ledgers and execution sequences of tasks in computer programs, just to mention a few. We study the problem of order preserving hierarchical clustering of this kind of ordered data. That is, if we have $$a<b$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>a</mml:mi><mml:mo><</mml:mo><mml:mi>b</mml:mi></mml:mrow></mml:math> in the original data and denote their respective clusters by [ a ] and [ b ], then we shall have $$[a]<[b]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>[</mml:mo><mml:mi>a</mml:mi><mml:mo>]</mml:mo><mml:mo><</mml:mo><mml:mo>[</mml:mo><mml:mi>b</mml:mi><mml:mo>]</mml:mo></mml:mrow></mml:math> in the produced clustering. The clustering is similarity based and uses standard linkage functions, such as single- and complete linkage, and is an extension of classical hierarchical clustering. To achieve this, we develop a novel theory that extends classical hierarchical clustering to strictly partially ordered sets. We define the output from running classical hierarchical clustering on strictly ordered data to be partial dendrograms ; sub-trees of classical dendrograms with several connected components. We then construct an embedding of partial dendrograms over a set into the family of ultrametrics over the same set. An optimal hierarchical clustering is defined as the partial dendrogram corresponding to the ultrametric closest to the original dissimilarity measure, measured in the p -norm. Thus, the method is a combination of classical hierarchical clustering and ultrametric fitting. A reference implementation is employed for experiments on both synthetic random data and real world data from a database of machine parts. When compared to existing methods, the experiments show that our method excels both in cluster quality and order preservation.
Mohammed Almukaynizi, Vivin Paliath, Malay Shah, Malav Shah · 5 authors
With the recent prevalence of darkweb/deepweb (D2web) sites specializing in the trade of exploit kits and malware, malicious actors have easy-access to a wide-range of tools that can empower their offensive capability. In this study, we apply concepts from causal reasoning, itemset mining, and logic programming on historical cryptocurrency-related cyber incidents with intelligence collected from over 400 D2web hacker forums. Our goal was to find indicators of cyber threats targeting cryptocurrency traders and exchange platforms from hacker activity. Our approach found interesting activities that, when observed together in the D2web, subsequent cryptocurrency-related incidents are at least twice as likely to occur than they would if no activity was observed. We also present an algorithmic extension to a previously-introduced algorithm called APT-Extract that allows to model new semantic structures that are specific to our application.
We consider natural ways to extend the notion of Zero-Knowledge (ZK) Proofs beyond decision problems. Specifically, we consider search problems, and define zero-knowledge proofs in this context as interactive protocols in which the prover can establish the correctness of a solution to a given instance without the verifier learning anything beyond the intended solution, even if it deviates from the protocol. The goal of this work is to initiate a study of Search Zero-Knowledge (search-ZK), the class of search problems for which such systems exist. This class trivially contains search problems where the validity of a solution can be efficiently verified (using a single message proof containing only the solution). A slightly less obvious, but still straightforward, way to obtain zero-knowledge proofs for search problems is to let the prover send a solution and prove in zero-knowledge that the instance-solution pair is valid. However, there may be other ways to obtain such zero-knowledge proofs, and they may be more advantageous. In fact, we prove that there are search problems for which the aforementioned approach fails, but still search zero-knowledge protocols exist. On the other hand, we show sufficient conditions for search problems under which some form of zero-knowledge can be obtained using the straightforward way.
Abstract We present an efficient method for answering one-dimensional range and closest-point queries in a verifiable and privacy-preserving manner. We consider a model where a data owner outsources a dataset of key-value pairs to a server, who answers range and closest-point queries issued by a client and provides proofs of the answers. The client verifies the correctness of the answers while learning nothing about the dataset besides the answers to the current and previous queries. Our work yields for the first time a zero-knowledge privacy assurance to authenticated range and closest-point queries. Previous work leaked the size of the dataset and used an inefficient proof protocol. Our construction is based on hierarchical identity-based encryption. We prove its security and analyze its efficiency both theoretically and with experiments on synthetic and real data (Enron email and Boston taxi datasets).
Many backtracking algorithms exhibit heavy-tailed distributions, in which their running time is often much longer than their median. We analyze the behavior of two natural variants of the Davis-Putnam-Logemann-Loveland (DPLL) algorithm for Graph 3-Coloring on sparse random graphs G(n,p=c/n). Let P_c(b) be the probability that DPLL backtracks b times. First, we calculate analytically the probability P_c(0) that these algorithms find a 3-coloring with no backtracking at all, and show that it goes to zero faster than any analytic function as c \to c^* = 3.847... Then we show that even in the ``easy'' phase 1 < c < c^* where P_c(0) > 0, including just above the emergence of the giant component, the expected number of backtracks is exponentially large with positive probability. To our knowledge this is the first rigorous proof that the running time of a natural backtracking algorithm has a heavy tail for graph coloring. Moreover, our results show that these algorithms take exponential time, not just below the 3-colorability threshold, but just above the degree c=1 at which the giant component first appears. In addition, we give experimental evidence and heuristic arguments that this tail takes the form P_c(b) ~ b^{-1} up to an exponential cutoff.