The query optimizer is a fundamental component of database management systems that determines the most efficient execution strategy for a given query by evaluating alternative query plans. Among its tasks, join optimization plays a central role, as the order of joins in multi-table queries can significantly affect execution performance. However, due to the inherent complexity of join optimization, logical bugs are inevitable and often difficult to detect. While existing fuzzing tools have shown notable success in uncovering crash- and performance-related errors, effectively identifying logical bugs -- cases in which the system produces incorrect query results -- remains largely unresolved. In this paper, we propose a metamorphic testing approach to detect DBMS bugs related to INNER JOIN optimization through the lens of set theory. For each testing case, equivalent queries are generated based on a basic set operation -- intersection -- and three semantics-preserving transformation rules, i.e., symmetric join transformation, asymmetric difference transformation, and symmetric difference transformation, are introduced. These rules rewrite a simple NATURAL/INNER JOIN query into a more complex, yet semantically equivalent, form. We implement this design in JoinEquiv, which serves as a testing oracle to systematically uncover logical inconsistencies in DBMS query processing by comparing the results of original and transformed queries. Using JoinEquiv, we uncovered 29 previously unknown issues in mainstream DBMSs (MySQL, TiDB, DuckDB, and Percona), and 27 of them were officially confirmed. JoinEquiv reveals deep logical flaws in DBMS optimizers and executors, underscoring its value in enhancing DBMS robustness.

This paper investigates the feasibility of achieving zero-knowledge verifiability for graph databases, enabling database owners to cryptographically prove the query execution correctness without disclosing the underlying data. Although similar capabilities have been explored for relational databases, their implementation for graph databases presents unique challenges. This is mainly attributed to the relatively large complexity of queries in graph databases. When translating graph queries into arithmetic circuits, the circuit scale can be too large to be practically evaluated. To address this issue, we propose to break down graph queries into more fine-grained, primitive operators, enabling a step-by-step evaluation through smaller-scale circuits. Accordingly, the verification with ZKP circuits of complex graph queries can be decomposed into a series of composable cryptographic primitives, each designed to verify a fundamental structural property such as path ordering or edge directionality. Especially, having noticed that the graph expansion (i.e., traversing from nodes to their neighbors along edges) operation serves as the backbone of graph query evaluation, we design the expansion centric operator decomposition. In addition to constructing circuits for the expansion primitives, we also design specialized ZKP circuits for the various attributes that augment this traversal. The circuits are meticulously designed to take advantage of PLONKish arithmetization. By integrating these optimized circuits, we implement ZKGraph, a system that provides verifiable query processing while preserving data privacy. Performance evaluation indicates that ZKGraph significantly outperforms naive in circuit implementations of graph operators, achieving substantial improvements in both runtime and memory consumption.

Zero-knowledge proof (ZKP) is a cryptographic protocol that allows a prover to convince verifiers that a computation is correctly executed without disclosing the prover’s secret. ZKP has been deployed in various privacy-preserving applications. However, the proof generation is notably inefficient on general-purpose processors. Multi-scalar multiplication (MSM) and polynomial computation (POLY), including number theoretic transform (NTT), are two of the most computation-intensive parts in proof generation. Recently, separate accelerators for MSM and POLY (mostly NTT) have been proposed. Unfortunately, separate accelerators may have poor resource utilization since MSM and POLY cannot be performed concurrently. To address this challenge, we propose Exa, a unified hardware architecture for MSM and POLY. It enables MSM and POLY to share computational resources and memory resources through decoupling dataflow control, computation, and memory. We design a novel unified functional unit (FU) array that can support both POLY operation and point addition (PADD) for MSM. In addition, we propose a 3-D NTT implementation and an adaptive MSM implementation on the FU array using a domain-specific instruction set architecture (ISA). Exa is scalable and can be efficiently orchestrated by our proposed runtime system. Compared with the separate accelerators for MSM and NTT, Exa occupies 47% less chip area. Compared to state-of-the-art accelerator PipeZK, Exa achieves up to$20.68 \times $and$4.58 \times $improvement for NTT and MSM, respectively, while occupying a chip area that is$2.6 \times $smaller. For end-to-end applications, Exa can achieve a speedup of$6.5 \times $on average than software implementation.

Federated Learning (FL) realizes distributed machine learning training via sharing model updates rather than raw data, thus ensuring data privacy. However, an attacker may infer the client's local original data from the model parameter so that original data leakage can be caused. While Differential Privacy (DP) is designed to address data leakage issues in FL, injecting noises during training reduces model accuracy. To minimize the negative impact caused by noises on model accuracy while considering privacy protections, in this article we propose an adaptive FL model, entitledRDP-basedAdaptiveFederatedLearning inShuffle model (RAFLS). To ensure the dataset privacy of clients, we inject adaptive noises into the client's local model by leveraging the adaptive layer-wise adaptive sensitivity of the local model. Our approach shuffles all local model parameters in order to address privacy explosion concerns caused by high-dimensional aggregation and multiple iterations. We further propose a fine-grained model weight aggregation scheme to aggregate all local models and obtain a global model. Our experiment evaluations demonstrate the proposed RAFLS has a better performance than the state-of-the-art methods in reducing noise's impact on model accuracy while protecting data, i.e., showing that the accuracy of RAFLS increases by 1.54% than that of the baseline scheme when$\epsilon = 2.0$and FashionMNIST under IID setting.

We present Rhombus, a new secure matrix-vector multiplication (MVM) protocol in the semi-honest two-party setting, which is able to be seamlessly integrated into existing privacy-preserving machine learning (PPML) frameworks and serve as the basis of secure computation in linear layers. Rhombus adopts RLWE-based homomorphic encryption (HE) with coefficient encoding, which allows messages to be chosen from not only a field Fp but also a ring Z2l, where the latter supports faster computation in non-linear layers. To achieve better efficiency, we develop an input-output packing technique that reduces the communication cost incurred by HE with coefficient encoding by about 21×, and propose a split-point picking technique that reduces the number of rotations to that sublinear in the matrix dimension. Compared to the recent protocol HELiKs by Balla and Koushanfar (CCS'23), our implementation demonstrates that Rhombus improves the whole performance of an MVM protocol by a factor of 7.4x ~ 8x, and improves the end-to-end performance of secure two-party inference of ResNet50 by a factor of 4.6x ~ 18x.

With the demand of cryptocurrencies, threshold ECDSA recently regained popularity. So far, several methods have been proposed to construct threshold ECDSA, including the usage of OT and homomorphic encryptions (HE). Due to the mismatch between the plaintext space and the signature space, HE-based threshold ECDSA always requires zero-knowledge range proofs, such as Paillier and Joye-Libert (JL) encryptions. However, the overhead of range proofs constitutes a major portion of the total cost.

Multi-scalar multiplication (MSM) is the most computation-intensive part in proof generation of Zero-knowledge proof (ZKP). In this paper, we propose MSMAC, an FPGA accelerator for large-scale MSM. MSMAC adopts a specially designed Instruction Set Architecture (ISA) for MSM and optimizes pipelined Point Addition Unit (PAU) with hybrid Karatsuba multiplier. Moreover, a runtime system is proposed to split MSM tasks with the optimal sub-task size and orchestrate execution of Processing Elements (PEs). Experimental results show that MSMAC achieves up to 328X and 1.96X speedups compared to the state-of-the-art implementation on CPU (one core) and GPU, respectively, outperforming the state-of-the-art ASIC accelerator by 1.79X. On 4 FPGAs, MSMAC performs 1,261X faster than a single CPU core.

The rise of decentralized finance (DeFi), Web 3.0, and other blockchain-based applications has led to an increased demand for on-chain data analysis across multiple blockchains. Conducting advanced queries, such as data aggregation and correlation analysis, is essential for gaining valuable insights in this context. However, multi-chain queries pose several challenges for the querying system, including compatibility with existing blockchains, supporting diverse query types, and ensuring the integrity of query results. To tackle these challenges, we propose a novel paradigm called verifiable virtual filesystem (V2FS). V2FS extends the POSIX I/O interface, shifting the focus from verifying computation to verifying data. This innovative approach empowers query clients to leverage an off-the-shelf database engine to evaluate queries using verifiable data retrieved from an indexing service provider (ISP). Our solution ensures strong integrity guarantees and can be smoothly integrated with existing database engines to support various query types. To achieve blockchain compatibility, we utilize the DCert framework to certify blocks from different blockchains, making our system applicable to various blockchain systems. Furthermore, we propose cache-based algorithms and a bloom filter-integrated algorithm to optimize query performance and minimize network communication costs. Security analysis and empirical study validate the effectiveness and efficiency of the proposed system.

Permissioned blockchains are being widely applied to solve the trust problem in enterprise collaboration. However, most of these systems suffer from low throughput and flexibility lacking issues. In this paper, we present a blockchain system SChain with scalable concurrent execution based on a flexible architecture. SChain separates the functionality of a complete "node" into three sub-functions and assigns them to different peers within every organization. Then each organization can scale each sub-function flexibly with no need for negotiation between organizations. Based on this architecture, SChain explores scalable concurrent execution from two levels. First, SChain takes the advantage of multiple peers to execute transactions collectively, while promising they make the same results as one peer does serially. Second, SChain enables concurrent transaction execution across blocks to utilize the resources of peers fully, breaking up the block-by-block process manner, based on a pipelined workflow. The extensive evaluation results demonstrate that SChain significantly outperforms the serial execution and other competing systems-level approaches.

Byzantine fault tolerant (BFT) consensus protocols are becoming an appealing solution to blockchains. As most blockchain systems are deployed on Wide Area Networks (WANs), with each node acting on behalf of its entity, partially synchronous BFT protocols that rely on network synchrony to elect a single leader can be ill-suited. In contrast, asynchronous protocols have no such timing assumptions. Existing asynchronous protocols confront challenges in terms of both flexibility and performance.

The emergence of digital asset applications, driven by Web 3.0 and powered by blockchain technology, has led to a growing demand for blockchain-specific graph analytics to unearth the insights. However, current blockchain data analytics systems are unable to perform efficient ad-hoc graph analytics over both live and past time windows due to their inefficient data synchronization and slow graph snapshots retrieval capability. To address these issues, we propose ChainDash, a blockchain data analytics system that dedicates a highly-parallelized data synchronization component and a retrieval-optimized temporal graph store. By leveraging these techniques, ChainDash supports efficient ad-hoc graph analytics of smart contract activities over arbitrary time windows. In the demonstration, we showcase the interactive visualization interfaces of ChainDash, where attendees will execute customized queries for ad-hoc graph analytics of blockchain data.

Elliptic Curve Cryptography (ECC), one of the most widely used asymmetric cryptographic algorithms, has been deployed in Transport Layer Security (TLS) protocol, blockchain, secure multiparty computation, and so on. As one of the most secure ECC curves, Curve25519 is employed by some secure protocols, such as TLS 1.3 and Diffie-Hellman Private Set Intersection (DH-PSI) protocol. High-performance implementation of ECC is required, especially for the DH-PSI protocol used in privacy-preserving platform. Point multiplication, the chief cryptographic primitive in ECC, is computationally expensive. To improve the performance of DH-PSI protocol, we propose Topgun, a novel and high-performance hardware architecture for point multiplication over Curve25519. The proposed architecture features a pipelined Finite-field Arithmetic Unit and a simple and highly efficient instruction set architecture. Compared to the best existing work on Xilinx Zynq 7000 series FPGA, our implementation with one Processing Element can achieve 3.14× speedup on the same device. To the best of our knowledge, our implementation appears to be the fastest among the state-of-the-art works. We also have implemented our architecture consisting of 4 Compute Groups, each with 16 PEs, on an Intel Agilex AGF027 FPGA. The measured performance of 4.48 Mops/s is achieved at the cost of 86 Watts power, which is the record-setting performance for point multiplication over Curve25519 on FPGAs.

Blockchain performance cannot meet the requirement nowadays. One of the crucial ways to improve performance is sharding. However, most blockchain sharding research focuses on the public blockchain. As for consortium blockchain, previous studies cannot support high cross-shard efficiency, multiple-shard contract calling, strict transaction atomicity, and shard availability, which are essential requirements but also challenges in consortium blockchain systems. Facing these challenges, we propose Meepo, a systematic study on sharded consortium blockchain. Meepo enhances cross-shard efficiency via the cross-epoch and cross-call. Moreover, a partial cross-call merging strategy is designed to handle the multi-state dependency in contract calls, achieving flexible multiple-shard contract calling. Meepo employs a replay-epoch to ensure strict transaction atomicity, and it also uses a backup algorithm called shadow shard based recovery to improve the shard robustness. On a test-bed of 128 AliCloud servers, setting 32 shards and 4 consortium members, Meepo-OpenEtheruem can achieve more than 140,000 cross-shard TPS under the workload of 100,000,000 asset transactions. It also shows more than 50,000 TPS under the transactions of real-world shopping behaviors.

Blockchain has attracted lots of attention in recent years. However, the performance of blockchain cannot meet the requirement of massive Internet of Things (IoT) devices. One of the important bottlenecks of blockchain is the limited computing resources on a single server while executing transactions. To address this issue, we propose Aeolus blockchain to achieve the distributed execution of blockchain transactions. There are two key challenges to achieving this for IoT blockchain: transaction structure and state consistency. Facing these challenges, we first propose a distributed blockchain transaction structure, which imports extra parameters to divide the transaction execution into different stages to enable distributed execution. Second, we propose distributed state update sharding, which equips each blockchain peer with its own master and shard servers. In this way, each blockchain peer can be considered as a cluster that distributes the transaction to shorten the processing time and reach the consensus finally. We implement Aeolus on Go-Ethereum to evaluate its feasibility, on a testbed including 132 cloud servers. Our system runs stably for more than 8 h under the workload of 190 000 000 real-world user transactions. Experimental results show the efficiency that Aeolus can achieve more than 100 000 transactions/s of blockchain transactions, which is 15.6 times the throughput of the original blockchain.

Blockchain performance cannot meet the requirement nowadays. One of the crucial ways to improve performance is sharding. However, most blockchain sharding research focuses on public blockchain. As for consortium blockchain, previous studies cannot support high cross-shard efficiency, cross-contract flexibility, shard availability, and strict transaction atomicity, which are the essential requirements but also the challenges in consortium blockchain systems. Facing these challenges, we propose Meepo, a systematic study on sharded consortium blockchain. Meepo enhances cross-shard efficiency via the cross-epoch and cross-call. Moreover, a partial cross-call merging strategy is designed to handle the multi-state dependency in contract calls, achieving cross-contract flexibility. Meepo employs a replay-epoch to ensure strict transaction atomicity, and it also uses a backup algorithm called shadow shard based recovery to improve the shard robustness. We implement Meepo on the AliCloud, using 32 shards in maximum, achieving more than 120,000 cross-shard TPS under the workload of 100,000,000 asset transactions.

We demonstrate SChain, a consortium blockchain that scales transaction processing to support large-scale enterprise applications. The unique advantage of SChain stems from the exploitation of both intra- and inter-block concurrency. The intra-block concurrency not only takes advantage of the multi-core processor on a single peer but also leverages the capacity of multiple peers. The interblock concurrency enables simultaneous processing across multiple blocks to increase the utilization of various peers. In our demonstration, we use real-time dashboards containing visualization based on the output of SChain to give the attendees interactive explorations of how SChain achieves intra- and inter-block concurrency.

Confidentiality is an indispensable requirement in financial applications of blockchain technology, and supporting it along with high performance and friendly programmability is technically challenging. In this paper, we present a system design called CONFIDE to support on-chain confidentiality by leveraging Trust Execution Environment (TEE). CONFIDE's secure data transmission protocol and data encryption protocol, together with a highly efficient virtual machine run in TEE, guarantee the confidentiality in the life cycle of a transaction from end to end. CONFIDE proposes a secure data model along with an application-driven secure protocol to guarantee data confidentiality and integrity. Its smart contract language extension offers users the flexibility to define complex confidentiality models. CONFIDE is implemented as a plugin module to Antfin Blockchain's proprietary platform, and can be plugged into other blockchain platforms as well with its universal interface design. Nowadays, CONFIDE is supporting millions of commercial transactions daily on consortium blockchain running financial applications including supply chain finance, ABS, commodity provenance, and cold-chain logistics.

Blockchain has been adopted in many applications to construct trust among multiple participants, such as supply chain management, digital assets transfer, philanthropy, etc. Blockchain platforms are often used as decentralized databases. However, existing blockchain platforms are far less convenient to use than traditional databases. They are lack of the capability of modelling complex tasks conveniently and efficiently, especially when both on-chain and off-chain data are involved at the same time. In this paper, we propose and implement a novel blockchain database, called SEBDB, which leverages the existing databases' functionality which are optimized for decades. Comparing to existing works, SEBDB is the first platform which considers both useability and scalability. Specifically, first, weaddrelationaldata semantics into blockchain platform, where each transaction is a tuple with multiple attributes in a pre-defined table. Second, we use SQL-like language as the general interface, instead of code-level APIs, to support convenient application development, in which intrinsic operations are re-defined and re-implemented to suit for blockchain platform. Third, as RDBMS has achieved great success in the past decades, our system, though not relying on RDBMS, treats it as an important component. Finally, we define a mini-benchmark to evaluate the performance of the blockchain database. Extensive experiments demonstrate the effectiveness and efficiency of our proposed system.

With the advance of the semantic Web, varying RDF data were increasingly generated, published, queried, and reused via the Web. For example, the DBpedia, a community effort to extract structured data from Wikipedia articles, broke 100 million RDF triples in its latest release. Initiated by Tim Berners-Lee,likewise, the Linking Open Data (LOD) project has published and interlinked many open licence datasets which consisted of over 2 billion RDF triples so far. In this context, fast query response over such large scaled data would be one of the challenges to existing RDF data stores. In this paper, we propose a novel triple indexing scheme to help RDF query engine fast locate the instances within a small scope. By considering the RDF data as a graph, we would partition the graph into multiple subgraph pieces and store them individually, over which a signature tree would be built up to index the URIs. When a query arrives, the signature tree index is used to fast locate the partitions that might include the matches of the query by its constant URIs. Our experiments indicate that the indexing scheme dramatically reduces the query processing time in most cases because many partitions would be early filtered out and the expensive exact matching is only performed over a quite small scope against the original dataset.

Digital videos are increasingly adopted in various multimedia applications where they are usually broadcasted or transmitted as video streams. Continuously monitoring copies on the fast and long streaming videos is gaining attention due to its importance in content and rights management. The problem of video copies detection on video streams is complicated by two issues. First, original videos may be edited, with their frames being reordered, to avoid detection. Second, there are many concurrent video streams and for each stream, there could be many continuous video copy monitoring queries. Efficient data stream algorithms are therefore essential for processing a large number of continuous queries on video streams. In this paper, we first define video sequence similarity that is robust with respect to changes of videos, and a hash-based video sketch for efficient computation of sequence similarity. We then present a novel bit vector signature of the sketch to achieve two optimization objectives: CPU cost and memory requirement. Finally, in order to handle multiple continuous queries simultaneously, we design an index structure for the query sequences. We implemented the system and use real videos for the experimental study. Experimental results confirm the efficiency and effectiveness of our proposed techniques.

Network traffic monitoring have been gaining attentions due to its importance in telecom industry. However, the monitoring systems deployed in telecom operators are usually too slow because of their disk-based processing approach. To address this problem, an online network traffic monitoring system, named SMART, is designed and developed. The system converts different formats of raw Netflow data (Netflow IPv5, IPv7 and IPv9) to user-defined control flows through combination and filtering. It can compute top-k frequent flows with sliding window, detects burst on arbitrary attributes, and presents results visually to users. The system could be used to replace the traditional offline monitoring system used in Shanghai Telecom. In its daily operation, it is shown that the processing speed achieves 30,000 flows per second. The basis of advanced streaming algorithms and design of robust system architecture enable SMART to achieve good performance.

Efficiently querying RDF [1] data is being an important factor in applying Semantic Web technologies to real-world applications. In this context, many efforts have been made to store and query RDF data in relational database using particular schemas. In this paper, we propose a new scheme to store, index, and query RDF data in triple stores. Graph feature of RDF data is taken into considerations which might help reduce the join costs on the vertical database structure. We would partition RDF triples into overlapped groups, store them in a triple table with one more column of group identity, and build up a signature tree to index them. Based on this infrastructure, a complex RDF query is decomposed into multiple pieces of sub-queries which could be easily filtered into some RDF groups using signature tree index, and finally is evaluated with a composed and optimized SQL with specific constraints. We compare the performance of our method with prior art on typical queries over a large scaled LUBM and UOBM benchmark data (more than 10 million triples)in [3]. For some extreme cases, they can promote3to4ordersofmagnitude.

Efficiently processing continuous k-nearest neighbor queries on data streams is important in many application domains, e. g. for network intrusion detection. Usually not all valid data objects from the stream can be kept in main memory. Therefore, most existing solutions are approximative. In this paper, we propose an efficient method for exact k-NN monitoring. Our method is based on three ideas, (1) selecting exactly those objects from the stream which are able to become the nearest neighbor of one or more continuous queries and storing them in a skyline data structure, (2) delaying to process those objects which are not immediately nearest neighbors of any query, and (3) indexing the queries rather than the streaming objects. In an extensive experimental evaluation we demonstrate that our method is applicable on high throughput data streams requiring only very limited storage.

Clustering data streams has been attracting a lot of research efforts recently. However, this problem has not received enough consideration when the data streams are generated in a distributed fashion, whereas such a scenario is very common in real life applications. There exist constraining factors in clustering the data streams in the distributed environment: the data records generated are noisy or incomplete due to the unreliable distributed system; the system needs to on-line process a huge volume of data; the communication is potentially a bottleneck of the system. All these factors pose great challenge for clustering the distributed data streams. In this paper, we proposed an EM-based (Expectation Maximization) framework to effectively cluster the distributed data streams, with the above fundamental challenges in mind. In the presence of noisy or incomplete data records, our algorithms learn the distribution of underlying data streams by maximizing the likelihood of the data clusters. A test-and-cluster strategy is proposed to reduce the average processing cost, which is especially effective for online clustering over large data streams. Our extensive experimental studies show that the proposed algorithms can achieve a high accuracy with less communication cost, memory consumption and CPU time.

No abstract available.

The filtering of XML data is the basis of many complex applications. Lots of algorithms have been proposed to solve this problem. One important challenge is that the number of path queries is huge. It is necessary to take an efficient data structure representing path queries. Another challenge is that these path queries usually vary with time. The maintenance of path queries determines the flexibility and capacity of a filtering system. In this paper, we introduce a novel approximate method for XML data filtering, which uses Bloom filters representing path queries. In this method, millions of path queries can be stored efficiently At the same time, it is easy to deal with the change of these path queries. To improve the filtering performance, we introduce a new data structure, Prefix Filters, to decrease the number of candidate paths. Experiments show that our Bloom filter-based method takes less time to build routing table than automaton-based method. And our method has a good performance with acceptable false positive when filtering XML packets of relatively small depth with millions of path queries.