Decentralized Knowledge Graph (DKG) platforms allow the sharing of knowledge with multiple owners. While data owners can share their data with others by encrypting their data before sharing it, this naïve approach prevents data encrypted by different owners from being queried together, as it compromises query verifiability, an essential DKG platform feature. We propose Pistis, the first DKG platform capable of preserving ownership while also enabling verifiable SPARQL queries. Two novel techniques facilitate this: owner-managed end-to-end encryption and collaborative query verification. In Pistis, data owners thus encrypt their data individually and collaborate to construct an authenticated data structure (ADS) with a global key by means of secret sharing and secure multi-party computation. Then, by indexing KG data as ciphertext over the ADS, Pistis offers a cryptographic scheme called VO-SPARQL that facilitates verifiable queries on encrypted KG data with multiple owners. Pistis provides succinct proofs for two-stage SPARQL queries, including subgraph queries based on the ADS and aggregation on encrypted intermediate results based on a key-aggregate cryptographic primitive. A theoretical analysis and an empirical study provide detailed insight into the performance of Pistis while offering provable security.

Prediction queries have revolutionized data search by integrating machine learning models and traditional data processing operations for advanced analytics. However, existing prediction query frameworks for outsourced databases face a critical security vulnerability: data flows are processed in plaintext on semi-honest servers, making them susceptible to data breaches. The main challenge in achieving secure prediction queries is that machine learning inference and data processing operations are distinct functionalities, while most current cryptographic frameworks support only a single type of operation on specific encrypted data. To bridge this crucial gap, we propose$\mathsf {SecPQ}$, the first framework tailored for secure prediction queries. Our approach unifies decision tree pipelines and data processing operations, such as selection, projection, and equality-joining, through equality matching on encrypted outsourced data. This enables the design of secure prediction queries with decision tree pipelines operating on encrypted data. We provide formal security definitions and proofs for$\mathsf {SecPQ}$. To further optimize the efficiency of secure prediction queries, we leverage order-preserving encryption to construct$\mathsf {SecPQ}_{{{ope}}}$, which offers improved query efficiency at the expense of weaker security properties compared with$\mathsf {SecPQ}$. Extensive experimental evaluations on billions of records demonstrate the feasibility and effectiveness of both$\mathsf {SecPQ}$and$\mathsf {SecPQ}_{{{ope}}}$.

Federated Knowledge Graph Embedding (FKGE) is an emerging collaborative learning technique for deriving expressive representations (i.e., embeddings) from client-maintained distributed knowledge graphs (KGs). However, poisoning attacks in FKGE, which lead to biased decisions by downstream applications, remain unexplored. This paper is the first work to systematize the risks of FKGE poisoning attacks, from which we develop a novel framework for poisoning attacks that force the victim client to predict specific false facts. Unlike centralized KGEs, FKGE maintains KGs locally, making direct injection of poisoned data challenging. Instead, attackers must create poisoned data without access to the victim's KG and inject it indirectly through FKGE aggregation. Specifically, to create poisoned data, the attacker first infers the targeted relations in the victim's local KG via a new KG component inference attack. Then, to accurately mislead the victim's embeddings via aggregation, the attacker locally trains a shadow model using the poisoned data and uses an optimized dynamic poisoning scheme to adjust the model and generate progressive poisoned updates. Our experimental results demonstrate the attack's effectiveness, achieving a remarkable success rate on various KGE models (e.g., 100% on TransE with WN18RR) while keeping the original task's performance nearly unchanged.

Sharding scales throughput by splitting blockchain nodes into parallel groups. However, different shards’ independent and random scheduling for cross-shard transactions results in numerous conflicts and aborts, since cross-shard transactions from different shards may access the same account. A deterministic ordering can eliminate conflicts by determining a global order for transactions before processing, as proved in the database field. Unfortunately, due to the intertwining of the Byzantine environment and information isolation among shards, there is no trusted party able to predetermine such an order for cross-shard transactions. To tackle this challenge, this paper proposes Prophet, a conflict-free sharding blockchain based on Byzantine-tolerant deterministic ordering. It first depends on untrusted self-organizing coalitions of nodes from different shards to pre-execute cross-shard transactions for prerequisite information about ordering. It then determines a trusted global order based on stateless ordering and post-verification for pre-executed results, through shard cooperation. Following the order, the shards thus orderly execute and commit transactions without conflicts. Prophet orchestrates the pre-execution, ordering, and execution processes in the sharding consensus for minimal overhead. We rigorously prove the determinism and serializability of transactions under the Byzantine and sharded environment. An evaluation of our prototype shows that Prophet improves the throughput by 3.11× and achieves nearly no aborts on 1 million Ethereum transactions compared with state-of-the-art sharding.

Blockchain databases have attracted widespread attention but suffer from poor scalability due to underlying non-scalable blockchains. While blockchain sharding is necessary for a scalable blockchain database, it poses a new challenge named on-chain cross-shard database services. Each cross-shard database service (e.g., cross-shard queries or inter-shard load balancing) involves massive cross-shard data exchanges, while the existing cross-shard mechanisms need to process each cross-shard data exchange via the consensus of all nodes in the related shards (i.e., on-chain) to resist a Byzantine environment of blockchain, which eliminates sharding benefits. To tackle the challenge, this paper presents GriDB, the first scalable blockchain database, by designing a novel off-chain cross-shard mechanism for efficient cross-shard database services. Borrowing the idea of off-chain payments, GriDB delegates massive cross-shard data exchange to a few nodes, each of which is randomly picked from a different shard. Considering the Byzantine environment, the untrusted delegates cooperate to generate succinct proof for cross-shard data exchanges, while the consensus is only responsible for the low-cost proof verification. However, different from payments, the database services' verification has more requirements (e.g., completeness, correctness, freshness, and availability); thus, we introduce several new authenticated data structures (ADS). Particularly, we utilize consensus to extend the threat model and reduce the complexity of traditional accumulator-based ADS for verifiable cross-shard queries with a rich set of relational operators. Moreover, we study the necessity of inter-shard load balancing for a scalable blockchain database and design an off-chain and live approach for both efficiency and availability during balancing. An evaluation of our prototype shows the performance of GriDB in terms of scalability in workloads with queries and updates.

The ability to decentralize knowledge graphs (KG) is important to exploit the full potential of the Semantic Web and realize the Web 3.0 vision. However, decentralization also renders KGs more prone to attacks with adverse effects on data integrity and query verifiability. While existing studies focus on ensuring data integrity, how to ensure query verifiability - thus guarding against incorrect, incomplete, or outdated query results - remains unsolved. We propose VeriDKG, the first SPARQL query engine for decentralized knowledge graphs (DKG) that offers both data integrity and query verifiability guarantees. The core of VeriDKG is the RGB-Trie, a new blockchain-maintained authenticated data structure (ADS) facilitating correctness proofs for SPARQL query results. VeriDKG enables verifiability of subqueries by gathering global index information on subgraphs using the RGB-Trie, which is implemented as a new variant of the Merkle prefix tree with an RGB color model. To enable verifiability of the final query result, the RGB-Trie is integrated with a cryptographic accumulator to support verifiable aggregation operations. A rigorous analysis of query verifiability in VeriDKG is presented, along with evidence from an extensive experimental study demonstrating its state-of-the-art query performance on the largeRDFbench benchmark.

Blockchain has been regarded as a trusted carrier for distributed data storage. With large volumes of valuable data stored on blockchain, data query has become a major requirement. However, the existing blockchains do not provide efficient query functionality because of their deep-rooted chain structure. Blockchain database is a new direction that constructs index on top of blockchain to provide rich query functionalities. The existing works are either insecure because the query process separates from the blockchain consensus, or inscalable because all the data needs to be stored in the block. In this paper, we propose a novel semantic blockchain database called MSTDB. We design a hybrid on/off chain blockchain storage architecture in which the majority of blockchain storage is offloaded to the off-chain storage and a novel index structure named Merkle Semantic Trie (MST) is designed to be a secure and semantic bridge between on- and off-chain. Based on MST, MSTDB provides a variety of semantic query functions including multi-keyword query, range query, Top-K query, and cross-chain query. To improve the performance further, we design some index compression and query preprocessing techniques for MSTDB. Extensive experiments demonstrate the effectiveness and efficiency of our blockchain database.

Cross-heterogeneous blockchain interactions have been attracting much attention due to their application in depository blockchains mutual access and cross-blockchain identity authentication. Trusted access across heterogeneous chains is gradually becoming a hot challenge. In order to ensure cross-blockchain trusted access, the majority of the current works focus on on-chain notaries and the relay chain model. However, these methods have the following drawbacks: 1) notaries on the chain are more vulnerable to attacks due to their high degree of centralization, which causes off-chain users to lose their trust and thus exacerbates the off-chain trust crisis; 2) although the relay model involves multiple parties in maintenance and supervision and enjoys a more robust trust, the paticipatant nodes are relatively fixed, which impose a terrible dilemma that invalid nodes cannot participate in consensus formation in a timely manner, thus progressively disrupting the connectivity of the relay across heterogeneous chains and eventually reducing the rate of trusted mutual access. In this article, we propose a novel general framework for cross-heterogeneous blockchain communication based on a periodical committee rotation mechanism to support information exchange of diverse transactions across multiple heterogeneous blockchain systems. Connecting heterogeneous blockchains through committees has a more robust trust than the notary method. In order to eliminate the impact of downtime nodes in a timely manner, we periodically reorganize the committee and give priority to replacing downed nodes to ensure the reliability of the system. In addition, a message-oriented verification mechanism is designed to improve the rate of trusted intervisit across heterogeneous chains. We have built a prototype of the scheme and conducted simulation experiments on the current mainstream blockchain for message exchange across heterogeneous chains. The results show that our solution has a good performance both in inter-chain access rate and system stability.

As a decentralized trusted database, the blockchain is finding applications in a growing number of fields such as finance, supply chain and medicine traceability, where large volumes of valuable data are stored on the blockchain. Currently, the mainstream blockchains employ a hybrid data storage architecture combining on-chain and off-chain storage. Real-time distributed search of mass data stored in this hybrid system is now a major need. However, previous fast retrieval schemes for the blockchain system are aimed only at on-chain data without considering their relevance to off-chain data, and thus fail to meet the requirement. In this paper, we propose an efficient blockchain data query scheme by introducing a novel Merkle Semantic Trie-based indexing technique without modifying the underlying database. A consensus on-chain index structure is constructed using the extracted semantic information of the off-chain data to create a mapping between the on-chain and off-chain data, thus enabling real-time data query both on and off the chain. Our scheme also provides multiple complex analytical query primitives to support semantic query, range query, and even fuzzy query. Experiments on three open data sets show that the proposed scheme has good query performance with shorter query latency for four different search types and offers better retrieval performance and verification efficiency than those available.