A Batch Private Information Retrieval (batch-PIR) scheme allows a client to retrieve multiple data items from a database without revealing them to the storage server(s). Most existing approaches for batch - Pirare based on batch codes, in particular, probabilistic batch codes (PBC) (Angel et al. S&P'18), which incur large storage overheads. In this work, we show that zero storage overhead is achievable for tree-shaped databases. In particular, we develop TreePIR, a novel approach tailored made for private retrieval of the set of nodes along an arbitrary root-to-leaf path in a Merkle tree with no storage redundancy. This type of tree has been widely implemented in many real-world systems such as Amazon DynamoDB, Google's Certificate Transparency, and blockchains. Tree nodes along a root-to-leaf path forms the well-known Merkle proof. TreePIR, which employs a novel tree coloring, outperforms PBC, a fundamental component in state-of-the-art batch-PIR schemes (Angel et al. S&P'18, Mughees-Ren S&P'23, Liu et al. S&P'24), in all metrics, achieving 3 ×lower total storage and 1.5-3 ×lower computation and communication costs. Most notably, TreePIR has 8-160× lower setup time and its polylog-complexity indexing algorithm is 19–160 ×faster than PBC for trees of 210_224leaves.

Chained HotStuff is a state-of-the-art Byzantine fault-tolerant protocol for building decentralized systems like blockchains. Although chained HotStuff has been widely adopted in many systems, its performance (e.g., throughput and latency) under attacks is still under-explored. In this paper, we develop a multi-metric evaluation framework to quantitatively analyze the performance of chained HotStuff with respect to its chain growth rate, chain quality, and latency. We propose several new attack strategies and evaluate their effects on the performance of chained HotStuff. Our analysis shows that the chain growth rate (resp, chain quality) of chained HotStuff under our attacks can drop to$4/9$(resp,$12/17$) of that without attacks when one-third of nodes are Byzantine. In addition, we use our framework to evaluate a variant of chained HotStuff, DiemBFT and find that some engineering optimizations render it more vulnerable to some attacks than the original chained HotStuff. Finally, we provide two countermeasures, i.e., broadcasting QCs and the longest chain rule, to thwart these attacks. Our analysis shows that the proposed countermeasures can significantly reduce the latency (almost half of that in chained HotStuff) and make it impossible for an attacker to lower the chain quality by simple attacks.

Sidechains allow transaction dissemination and execution outside the blockchain main network (i.e., the mainchain), enabling a scalable, efficient, and secure financial infrastructure for the Internet of Things (IoT) without trusting any central authority. Existing sidechains either have online requirements or rely on intensive computation on a central operator, which does not meet the needs of IoT for dynamic changes and high performance. This article proposes an alternative sidechain construction, called Cumulus, which meets the needs of IoT by leveraging the classic Byzantine fault-tolerant (BFT) consensus protocols, such as PBFT, that have commonly been applied in permissioned blockchains. Cumulus builds BFT-based sidechains atop public blockchains (e.g., Ethereum) using smart contracts and ensures the bidirectional safety of users’ assets. Cumulus sidechains periodically interact with the mainchain and submit checkpoints through representatives selected in an efficient and decentralized manner. The experiments show that Cumulus sidechains outperform rollup-based sidechains, and state-of-the-art sidechain constructions, achieving two and three orders of magnitude improvement in throughput and latency while retaining comparable operational cost.

he HotStuff protocol is a recent breakthrough in Byzantine Fault Tolerant (BFT) consensus that enjoys both responsiveness and linear view change by creatively adding a round to classic two-round BFT protocols like PBFT. Despite its great advantages, HotStuff has a few limitations. First, the additional round of communication during normal cases results in higher latency. Second, HotStuff is vulnerable to certain performance attacks, which can significantly deteriorate its throughput and latency. To address these limitations, we propose a new two-round BFT protocol called Fast-HotStuff, which enjoys responsiveness and efficient view change that is comparable to the linear view-change in terms of performance. Our Fast-HotStuff has lower latency and is more robust against the performance attacks that HotStuff is susceptible to.

The collaborative edge and cloud computing system has emerged as a promising solution to fulfill the unprecedented high requirements of 5G application scenarios. Due to vendor variations, it is often difficult to manage hardware facilities in such a collaborative system. Moreover, the amount of data generated and tasks requested by end devices are increasing exponentially, which introduces storage and computation bottlenecks. To address these issues, a novel systematic framework called software-defined edge and cloud computing (SD-ECC) is designed to manage the underlying physical resources of edge and cloud layers via software. SD-ECC is combined with an erasure-coded storage system, for which a task scheduling problem is formulated by considering data access and task processing steps. Then, a joint data access and task processing (JDATP) algorithm is proposed to minimize the task response time including data access latency and task processing latency. A practical SD-ECC platform is developed on OpenStack, OpenDaylight, and Kubernetes to conduct experiments with real-world datasets. The experimental results demonstrate that our proposed JDATP algorithm can reduce 20.87% of the task response time and increase 14.16% of the remaining storage space on average by comparing it with alternative schemes.

HotStuff is a state-of-the-art Byzantine fault-tolerant consensus protocol. It can be pipelined to build large-scale blockchains. One of its variants called LibraBFT is adopted in Facebook's Libra blockchain. Although it is well known that pipelined HotStuff is secure against up to 1/3 of Byzantine nodes, its performance in terms of throughput and delay is still under-explored. In this paper, we develop a multi-metric evaluation framework to quantitatively analyze pipelined HotStuff's performance with respect to its chain growth rate, chain quality, and latency. We then propose several attack strategies and evaluate their effects on the performance of pipelined HotStuff. Our analysis shows that the chain growth rate (resp, chain quality) of pipelined HotStuff under our attacks can drop to as low as 4/9 (resp, 12/17) of that without attacks when 1/3 nodes are Byzantine. As another application, we use our framework to evaluate certain engineering optimizations adopted by LibraBFT. We find that these optimizations make the system more vulnerable to our attacks than the original pipelined HotStuff. Finally, we provide two countermeasures to thwart these attacks. We hope that our studies can shed light on the rigorous understanding of the state-of-the-art pipelined HotStuff protocol as well as its variants.

Sidechains enable off-chain scaling by sending transactions in a private network rather than broadcasting them in the public blockchain (i.e., the mainchain) network. To this end, classic Byzantine fault-tolerant (BFT) consensus protocols such as PBFT seem an excellent fit to fuel sidechains for their permissioned settings and inherent robustness. However, designing a secure and efficient BFT-based sidechain protocol remains an open challenge.This paper presents Cumulus, a novel BFT-based sidechain framework for blockchains to achieve off-chain scaling without compromising any security and efficiency properties of both sides’ consensus protocols. Cumulus encompasses a novel cryptographic sortition algorithm called Proof-of-Wait to fairly select sidechain nodes to communicate with the mainchain in an efficient and decentralized manner. To further reduce the operational cost, Cumulus provides an optimistic checkpointing approach in which the mainchain will not verify checkpoints unless disputes happen. Meanwhile, end-users enjoy a two-step withdrawal protocol, ensuring that they can safely collect assets back to the mainchain without relying on the BFT committee. Our experiments show that Cumulus sidechains outperform ZK-Rollup, another promising sidechain construction, achieving one and two orders of magnitude improvement in throughput and latency while retaining comparable operational cost.