Cross-chain transaction processing is pivotal to blockchain interoperability, enabling coordinated state transitions across multiple blockchains to support increasingly complexdecentralized applications(dApps). However, existing atomicity-preserving mechanisms, predominantly based ontwo-phase commit(2PC) protocols, are hindered by sequential coordination, prolonged state locking, and high susceptibility to cascading aborts. These limitations severely degrade throughput and latency under contention, undermining practical deployability. This paper proposes Furion, a novel cross-chain transaction processing mechanism that achieves both atomicity and efficiency. Furion introduces the multi-future exploration, a new execution paradigm that explicitly materializes multiple possible futures of cross-chain states via multi-versioning. By speculatively executing transactions across feasible state evolutions, Furion eliminates blocking on unresolved dependencies and fundamentally avoids cascading aborts. To further unlock concurrency in the finalization phase, Furion employs preemptive voting, which allows local transactions to cast commit or abort votes early when their outcomes are invariant across all state versions. Experimental evaluations demonstrate that Furion significantly outperforms state-of-the-art systems, achieving substantially higher throughput, lower latency, and markedly reduced abort rates under skewed and highly contended workloads.

Asynchronous Byzantine Fault Tolerant (BFT) consensus protocols have garnered significant attention with the rise of blockchain technology. A typical asynchronous protocol is designed by executing sequential instances of the Asynchronous Common Sub-seQuence (ACSQ). The ACSQ protocol consists of two primary components: the Asynchronous Common Subset (ACS) protocol and a block sorting mechanism, with the ACS protocol comprising two stages: broadcast and agreement. However, current protocols encounter three critical issues: high latency arising from the execution of the agreement stage, latency instability due to the integral-sorting mechanism, and reduced throughput caused by block discarding. To address these issues, we propose Falcon, an asynchronous BFT protocol that achieves low latency and enhanced throughput. Falcon introduces a novel broadcast protocol, Graded Broadcast (GBC), which enables a block to be included in the ACS set directly, bypassing the agreement stage and thereby reducing latency. To ensure safety, Falcon incorporates a new binary agreement protocol called Asymmetrical Asynchronous Binary Agreement (AABA), designed to complement GBC. Additionally, Falcon employs a partial-sorting mechanism, allowing continuous rather than simultaneous block committing, enhancing latency stability. Finally, we incorporate an agreement trigger that, before its activation, enables nodes to wait for more blocks to be delivered and committed, thereby boosting throughput. We conduct a series of experiments to evaluate Falcon, demonstrating its superior performance.

Blockchain-based query with its traceability and data provenance has become increasingly popular and widely adopted in numerous applications. Yet existing index-based query approaches are only efficient under static blockchain query workloads where the query attribute or type must be fixed. It turns out to be particularly challenging to construct an efficient index for dynamic workloads due to prohibitively long construction time and excessive storage consumption. In this paper, we present FlexIM, the first efficient and verifiable index management system for blockchain dynamic queries. The key innovation in FlexIM is to uncover the inherent characteristics of blockchain, i.e., data distribution and block access frequency, and then to optimally choose the index by utilizing reinforcement learning technique under varying workloads. In addition, we enhance and facilitate verifiability with low storage overhead by leveraging Root Merkle Tree (RMT) and Bloom Filter Merkle Tree (BMT). Our comprehensive evaluations demonstrate that FlexIM outperforms the state-of-the-art blockchain query mechanism, vChain+, by achieving a 26.5% speedup while consuming 94.2% less storage, on average, over real-world Bitcoin datasets.

Directed Acyclic Graph (DAG)-based blockchain (a.k.a distributed ledger) has become prevalent for supporting highly concurrent applications. Its inherent parallel data structure accelerates block generation significantly, shifting the bottleneck from performance to storage scalability. An intuitive solution is to apply state sharding that divides the entire ledger (i.e., transactions and states) into multiple shards. While each node only stores proportional transactions, it suffers from the challenges of storing and ensuring the processing consistency of cross-shard transactions. In this paper, we propose SharDAG, a new mechanism that leverages adaptive sharding for DAG-based blockchains to achieve high performance and strong consistency. The key idea of SharDAG is to exploit unique characteristics - silent assets - and design a lightweight processing mechanism based on avatar account caching. Furthermore, we design a Byzantine resilient cross-shard verification mechanism with a theoretically optimal number of participating nodes, which guarantees the consistency and security of avatar account aggregation. Our comprehensive evaluations on real-world workloads demonstrate that SharDAG presents up to 3.8 x throughput improvement compared to the state-of-the-art and reduces the storage overhead of cross-shard transactions.

The widespread availability of Internet access and online services has led to the generation of numerous large-scale graphs in various real-world applications, such as online social networks and knowledge graphs. Keyword search stands out as a crucial task in the analysis and mining of these graphs. However, graph data owners tend to outsource storage and computation tasks to the cloud due to limited computing and storage resources. In this case, it is critical to ensure the integrity of the query results, as the cloud may have an incentive to return tampered results to serve its own interests. Currently, blockchain systems can store data efficiently and securely, creating a decentralized, tamper-proof digital platform. This functionality positions blockchain as a crucial complement and enhancement to traditional cloud storage solutions. Mainstream blockchains use a hybrid storage system to improve scalability, storing small meta-data on-chain and outsourcing raw data off-chain. While cryptographic proofs protect data integrity for queries, current schemes only support key-value data. This paper pioneers the study of authenticated keyword searches on graphs in hybrid-storage blockchains. The key challenge is to design an authenticated data structure (ADS) based on the graph data that can efficiently deal with keyword search queries. We propose Merkle Path DAG (MP-DAG), a novel ADS that aggregates the unqualified paths that will not appear in the result trees to efficiently handle authenticated keyword search queries on graphs. Furthermore, to reduce the ADS storage cost, we design an optimization scheme MP-DAG* by combining the similar subgraphs of MP-DAG. Experimental results demonstrate the performance of the proposed ADS and optimization measure.

With the development of permissioned blockchains, transaction processing plays an increasingly crucial role in improving performance. The execution and consensus phases in existing transaction processing methods are based on total order. The consensus phase constructs a total order representing the execution order and submission order of different transactions. Then, in the execution phase, transactions are executed or validated sequentially based on this total order. However, while the total order guarantees consistency across nodes, it also restricts the execution order of any two transactions, even if there is no conflict between them. Additionally, existing methods process transactions based on block snapshots before the consensus phase, but these snapshots are only updated after reaching consensus. The stale data between these phases results in high transaction abort rates due to delays in updated visibility. Therefore, we propose a novel blockchain called Partial Order-Based Ledger (POBL). POBL constructs a partial order of transaction executions in the execution phase and then, in the consensus phase, builds a consistent submission order based on this execution partial order. Notably, POBL allows the visibility of transaction processing results in the execution phase even before committing its block. To ensure the correct execution, the consensus and execution phases need to consider the consistency of data and the dependencies between transactions. Therefore, we use a graph, PGraph, to capture the concurrent partial order in the execution phase. In the consensus phase, we propose a consensus algorithm to conduct the maximal common subgraph, CPGraph, based on the PGraphs of different nodes. We propose to validate blocks and transactions in parallel based on CPGraph, without being restricted by the order between blocks. We perform extensive experiments compared to state-of-the-art architectural systems, and our method significantly outperforms existing work.

Increasingly popular decentralized applications (dApps) with complex application logic incur significant overhead for executing smart contract transactions, which greatly limits public blockchain performance. Pre-executing transactions off the critical path can mitigate substantial I/O and computation costs during execution. However, pre-execution does not yield any state transitions, rendering the system state inconsistent with actual execution. This inconsistency can lead to deviations in pre-execution paths when processing smart contracts with multiple state-related branches, thus diminishing pre-execution effectiveness. In this paper, we develop Seer, a novel public blockchain execution engine that incorporates fine-grained branch prediction to fully exploit pre-execution effectiveness. Seer predicts state-related branches using a two-level prediction approach, reducing inconsistent execution paths more efficiently than executing all possible branches. To enable effective reuse of pre-execution results, Seer employs checkpoint-based fast-path execution, enhancing transaction execution for both successful and unsuccessful predictions. Evaluations with realistic blockchain workloads demonstrate that Seer delivers an average of 27.7× transaction-level speedup and an overall 20.6× speedup in the execution phase over vanilla Ethereum, outperforming existing blockchain execution acceleration solutions.

Directed Acyclic Graph(DAG)-based blockchain represents a paradigm shift from conventional blockchains, which has the potential to drastically improve throughput performance through concurrent storage and executions. In practice, however, existing DAG-based blockchains fail to deliver such promises, often with limited throughput, high conflicts, and security vulnerabilities under dynamic workloads. The root causes are their unawareness of the workload characteristics of different workload sizes and skewed access patterns. In this paper, we propose MorphDAG, the first workload-aware DAG-based blockchain that can significantly enhance throughput without compromising security and achieve elastic scaling under realistic workloads. We derive the theoretically optimal degree of storage concurrency to achieve high throughput while retaining system security as the workload size changes, while enabling fine-grained concurrency adjustment that accommodates aProof-of-Stake(PoS)-based consensus protocol. We develop a dual-mode transaction processing mechanism that effectively resolves the conflicts brought by skewed access. We implement a prototype of MorphDAG and evaluate under real-world workloads. Extensive evaluations demonstrate that MorphDAG improves end-to-end throughput by up to 2.3× and 2.4× over state-of-the-art DAG-based blockchain systems AdaptChain and OHIE, respectively.

In most blockchain-based application scenarios, a complete application logic consists of multiple continuous transactions, in which the initiation of one transaction depends on the confirmation result of the previous one. This mandates that continuous transactions must be processed in the correct order. Unfortunately, existing chain-based blockchains fail to effectively support continuous transaction processing due to considerable latency in confirming continuous transactions. Recent studies shifted from chain-based blockchains toDirected Acyclic Graph(DAG) based blockchains, which reduced transaction confirmation latencies. However, DAG-based blockchains store transactions in an out-of-order manner that leads to unordered transaction processing. To address this challenge, we propose FLUID, a new DAG-based blockchain that supports continuous transaction processing while delivering high performance. The fundamental idea of FLUID is to design a transaction dependency tracking structure to ensure that continuous transactions can be processed in the correct order. FLUID utilizes a conflict resolution mechanism to provide instant confirmation and to support concurrent transaction processing with lower latencies. In addition, FLUID builds a checkpoint-based verification mechanism to achieve deterministic consensus on transaction processing results in the DAG. Extensive experiments demonstrate that our proposed FLUID can improve the throughput over state-of-the-art OHIE by 66% with two orders of magnitude lower latencies.

Graph stream, referred to as an evolving graph with a timing sequence of updated edges through a continuous stream, is an emerging data format widely used in big data applications. Coping with a graph stream is challenging because: 1) fully storing the continuously produced and extremely large-scale datasets is difficult if not impossible; 2) supporting queries relevant to both graph topology and temporal information is nontrivial. Recently, graph stream summarization techniques have attracted much attention in providing approximate storage and query processing for a graph stream. Existing designs largely utilize hash functions to reduce the graph scale and leverage a compressive matrix to represent the graph stream. However, such designs are unable to store the time dimension information of graph streams, and thus fail to support temporal queries. In this paper, we propose Horae, a novel graph stream summarization structure for efficient temporal range query, which presents a time prefix embedded multi-layer summarization structure. Our design is based on the insight that an arbitrary temporal range of length$L$can be decomposed to at most$2\log L$sub-ranges, where all the time points in each sub-range have the same binary code prefix. We further design an efficient Binary Range Decomposition (BRD) algorithm, which achieves a logarithmic scale query processing time. Experimental results show that Horae significantly reduces the latency of various temporal range queries by two to three orders of magnitude compared to the state-of-the-art designs.

In modern big data warehouse systems, we observe a common phenomenon that a column of data values can be derived from one or several other columns by transforming and concatenating these columns. We call this relationship between columns a Soft Concatenation Mapping (SCM). SCMs imply significant redundancy in the schema or data, and therefore can be exploited for data integration or data compression. In this paper, we formalize the problem of SCM detection and prove it is NP-hard. We then propose efficient approximate algorithms to detect all SCMs or an optimal set of SCMs in a table. Our experiments on both real-world and synthetic datasets show promising results.

In this paper, we present TICC, an automatic data compression component that can transparently eliminate data redundancies across columns in column-oriented database systems. We further propose two approaches to integrate inter-column compression into existing database systems. One approach is to use User Defined Functions (UDFs), and the other is native. We implement these two approaches on top of Hive based on the ORC file, a common data format in column stores, and evaluate the performance of TICC using real-world datasets. The experimental results demonstrate that TICC can significantly reduce the storage overhead and process a variety of queries over large-scale data with up to 20% performance improvement over the original Hive.