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.

Graphs serve as an essential data structure to model complex relationships in a variety of applications, such as social networks, web graphs, and chemical informatics. Due to the high cost of maintaining large-scale graph data and executing graph queries, data owners often outsource their graph data to a third-party service provider for graph processing. In this scenario, it is crucial to ensure the integrity of query results, as the provider may have the incentive to return only partial or tampered results to save computing resources or serve their own interests. Blockchain, as a promising solution for secure data storage and retrieval, opens up new opportunities for data management in such scenarios. To scale the blockchain, many works have been conducted using off-chain storage while ensuring the integrity of query results for key-value data in hybrid-storage blockchain architectures. To our knowledge, there is no work to enable the blockchain to support subgraph matching queries. In this paper, we present a novel approach to support authenticated subgraph matching queries for large graphs kept off-chain. We first design the authenticated data structure as MELTree and keep the digests of the roots on-chain. We propose the verification object (VO) construction algorithm AMatching for queries to ensure the completeness and soundness of the results. To further reduce the cost, we propose AMatching* based on a bidirectional search including forward search and reverse search. Moreover, we further optimize the on-chain storage cost by proposing MVPTree, which organizes the structures for vertices and only needs to keep one root digest on-chain for verification. Experimental results show that the proposed algorithms and the optimizations improve the performance significantly.

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.