Optimizing asset exchanges on blockchain-driven platforms poses a novel and challenging graph query optimization problem. In this model, assets represent vertices and exchanges form edges, recasting the graph query task as a routing problem over a large-scale, dynamic graph. However, the existing solutions fail to solve the problem efficiently due to the non-linear nature of the edge weights defined by a concave swap function. To address the challenge, we propose PRIME, a two-stage iterative graph algorithm designed for the Token Graph Routing Problem (TGRP). The first stage employs a pruned graph search to efficiently identify a set of high-potential routing paths. The second stage formulates the allocation task as a strongly convex optimization problem, which we solve using our novel Adaptive Sign Gradient Method (ASGM) with a linear convergence rate. Extensive experiments on real-world Ethereum data confirm PRIME's advantages over industry baselines. PRIME consistently outperforms the widely-used Uniswap routing algorithm, achieving up to 8.42 basis points (bps) better execution prices on large trades while reducing computation up to 96.7%. The practicality of PRIME is further validated by its deployment in hedge fund production environments, demonstrating its viability as a scalable graph query processing solution for high-frequency decentralized markets.

Ethereum, as a representative of Web3, adopts a novel framework called Proposer Builder Separation (PBS) to prevent the centralization of block profits in the hands of institutional Ethereum stakers. Introducing builders to generate blocks based on public transactions, PBS aims to ensure that block profits are distributed among all stakers. Through the auction among builders, only one will win the block in each slot. Ideally, the equilibrium strategy of builders under public information would lead them to bid all block profits. However, builders are now capable of extracting profits from private order flows. In this paper, we explore the effect of PBS with private order flows. Specifically, we propose the asymmetry auction model of MEV-Boost auction. Moreover, we conduct empirical study on Ethereum blocks from January 2023 to May 2024. Our analysis indicates that private order flows contribute to 54.59% of the block value, indicating that different builders will build blocks with different valuations. Interestingly, we find that builders with more private order flows (i.e., higher block valuations) are more likely to win the block, while retain larger proportion of profits. In return, such builders will further attract more private order flows, resulting in a monopolistic market gradually. Our findings reveal that PBS in current stage is unable to balance the profit distribution, which just transits the centralization of block profits from institutional stakers to the monopolistic builder.

Interactive graph search (IGS) has emerged as a powerful paradigm for information retrieval across diverse applications. The goal of IGS is to identify the most appropriate (i.e., deepest) node within a hierarchy for an unknown object, typically leveraging human intelligence such as crowdsourcing as the oracle. Existing IGS algorithms usually rely on reachability queries, such as "is the target node reachable from node x ?", and assume that correct answers are always available. However, in practice, answering such queries is challenging due to the requirement for domain-specific knowledge, resulting in frequent errors in the oracle's responses. As a consequence, the reachability-query-based approaches would perform poorly. In this paper, we propose a practical solution to the IGS problem, leveraging the power of large language models (LLMs) to tackle the issue of reachability queries. Specifically, we formally analyze the inherent properties of real-world hierarchies with the notion of ambiguous nodes and overlapping nodes to debunk the difficulty of reachability queries. In addition, we develop a practical oracle based on LLMs that can answer reachability queries on (near) leaf nodes accurately. Building on the LLM oracle, we propose a similarity-based upward search algorithm, namely SuS, to address the IGS problem. We further enhance SuS with layer-wise search and fast initialization techniques. We evaluate SuS on two real-world datasets against four baseline methods, and the experimental results clearly demonstrate the superiority of our solution.

Interactive graph search (IGS) uses human intelligence to locate the target node in hierarchy, which can be applied for image classification, product categorization and searching a database. Specifically, IGS aims to categorize an object from a given category hierarchy via several rounds of interactive queries. In each round of query, the search algorithm picks a category and receives a boolean answer on whether the object is under the chosen category. The main efficiency goal asks for the minimum number of queries to identify the correct hierarchical category for the object. In this paper, we study the average-case interactive graph search (AIGS) problem that aims to minimize the expected number of queries when the objects follow a probability distribution. We propose a greedy search policy that splits the candidate categories as evenly as possible with respect to the probability weights, which offers an approximation guarantee of$O(\log n)$for AIGS given the category hierarchy is a directed acyclic graph (DAG), where$n$is the total number of categories. Meanwhile, if the input hierarchy is a tree, we show that a constant approximation factor of$(1+\sqrt{5})/2$can be achieved. Furthermore, we present efficient implementations of the greedy policy, namely GreedyTree and GreedyDAG, that can quickly categorize the object in practice. Extensive experiments in real-world scenarios are carried out to demonstrate the superiority of our proposed methods.

The interactive graph search (IGS) problem aims to locate an initially unknown target node leveraging human intelligence. In IGS, we can gradually find the target node by sequentially asking humans some reachability queries like "is the target node reachable from a given node x?". However, human workers may make mistakes when answering these queries. Motivated by this concern, in this paper, we study a noisy version of the IGS problem. Our objective in this problem is to minimize the query complexity while ensuring accuracy. We propose a method to select the query node such that we can push the search process as much as possible and an online method to infer which node is the target after collecting a new answer. By rigorous theoretical analysis, we show that the query complexity of our approach is near-optimal up to a constant factor. The extensive experiments on two real datasets also demonstrate the superiorities of our approach.

Proof-of-Work (PoW) is the most widely adopted incentive model in current blockchain systems, which unfortunately is energy inefficient. Proof-of-Stake (PoS) is then proposed to tackle the energy issue. The rich-get-richer concern of PoS has been heavily debated in the blockchain community. The debate is centered around the argument that whether rich miners possessing more stakes will obtain higher staking rewards and further increase their potential income in the future. In this paper, we define two types of fairness, i.e., expectational fairness and robust fairness, that are useful for answering this question. In particular, expectational fairness illustrates that the expected income of a miner is proportional to her initial investment, indicating that the expected return on investment is a constant. To better capture the uncertainty of mining outcomes, robust fairness is proposed to characterize whether the return on investment concentrates to a constant with high probability as time evolves. Our analysis shows that the classical PoW mechanism can always preserve both types of fairness as long as the mining game runs for a sufficiently long time. Furthermore, we observe that current PoS blockchains implement various incentive models and discuss three representatives, namely ML-PoS, SL-PoS and C-PoS. We find that (i) ML-PoS (e.g., Qtum and Blackcoin) preserves expectational fairness but may not achieve robust fairness, (ii) SL-PoS (e.g., NXT) does not protect any type of fairness, and (iii) C-PoS (e.g., Ethereum 2.0) outperforms ML-PoS in terms of robust fairness while still maintaining expectational fairness. Finally, massive experiments on real blockchain systems and extensive numerical simulations are performed to validate our analysis.