Blockchain sharding is a promising approach to enhancing scalability by partitioning the network into smaller, parallel shards. However, existing sharding blockchains that rely on Byzantine fault tolerance protocols require large shard sizes to meet strict security thresholds, limiting scalability, while relaxing security parameters can lead to liveness and safety violations. In this work, we present Camael, a secure sharding blockchain that achieves corrupted-shard tolerance through effective detection and processing mechanisms for both liveness and safety violations. Specifically, fake liveness violations forged by malicious nodes are accurately detected via a two-phase reporting and confirmation mechanism, while concealed safety violations are efficiently identified using a lightweight snapshot mechanism. Furthermore, a state determination process ensures overall system consistency. Malicious nodes are precisely identified through a conviction mechanism, which enables the replacement of the targeted nodes and the reconfiguration of the shards. Notably, Camael ensures security while preserving a global fault tolerance of 1/3 and tolerating corrupted shards, with each shard accommodating up to 2/3 malicious nodes. Extensive experiments conducted on 2000 AWS EC2 nodes across 4 regions demonstrate that Camael improves throughput by 3.56 times compared to the baseline (Kronos, NDSS'25), achieving a throughput of 109.3 ktx/sec, while the violation processing requires only 1.64 sec.

Recent progresses in asynchronous Byzantine fault-tolerant (BFT) consensus, e.g.$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$(CCS' 22) and$\mathsf {Tusk}$(EuroSys' 22), show promising performance through decoupling transaction dissemination and block agreement. However, when executed with a larger number$n$of nodes, like several hundreds, they would suffer from significant degradation in performance. Their dominating scalability bottleneck is the huge authenticator complexity: each node has to multicast$\mathcal {O}(n)$quorum certificates (QCs) and subsequently verify them for each block. This paper systematically investigates and resolves the above scalability issue. We first propose a signature-free asynchronous BFT consensus$\mathsf {FIN}\textrm {-}\mathsf {NG}$that adapts a recent signature-free asynchronous common subset protocol FIN (CCS' 23) into the state-of-the-art framework of concurrent broadcast and agreement. The liveness of$\mathsf {FIN}\textrm {-}\mathsf {NG}$relies on our non-trivial redesign of FIN's multi-valued validated Byzantine agreement towards achieving optimal quality.$\mathsf {FIN}\textrm {-}\mathsf {NG}$greatly improves the performance of FIN and already outperforms$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$in most deployment settings. To further overcome the scalability limit of$\mathsf {FIN}\textrm {-}\mathsf {NG}$due to$\mathcal {O}(n^{3})$messages, we propose$\mathsf {JUMBO}$, a scalable instantiation of$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$, with only$\mathcal {O}(n^{2})$complexities for both authenticators and messages. We use various aggregation and dispersal techniques for QCs to significantly reduce the authenticator complexity of original$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$implementations by up to$\mathcal {O}(n^{2})$orders. Finally, we implement our designs in Golang and experimentally demonstrated their enhanced scalability with hundreds of Amazon's AWS instances.$\mathsf {JUMBO}$and FIN-NG significantly outperform the state-of-the-art in (nearly) all deployment settings. Especially, when$n\ge$196,$\mathsf {JUMBO}$can attain a throughput that is more than 4× that of FIN and$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$.

In Web 3.0’s pursuit of a decentralized and user-autonomous network, traditional access control methods, such as central servers and weak decentralized algorithms, are insufficient regarding security, fault tolerance ability, and scalability. To solve this, we first design a decentralized multi-committee attribute-based encryption, X-ABE, to address the weak decentralization and low fault tolerance in Multi-Authority Attribute-Based Encryption (MA-ABE). X-ABE replaces MA-ABE’s fragile attribute authorities with robust attribute committees, each composed of multiple nodes. By developing dual-wrapped shares techniques, we address the increased dimensionality challenge of secret sharing while maintaining only 1 distributed key generation instance. Also, a formal security definition and proof under the partial adaptive model are given using dual system encryption. Second, X-LOCK, an X-ABE based decentralized access control utilizing consensus plus sharding, is proposed for Web 3.0, to achieve full decentralization, consistency, fault tolerance, user autonomy, and scalability. Third, X-ABE-R is proposed for attribute revocation and is demonstrated in X-LOCK-R with sharding blockchain as an immutable revocation ledger. Fourth, a formal definition and comparative analysis of X-ABE’s fault tolerance abilities are demonstrated, covering aspects of liveness and safety, along with the complexity analysis. Fifth, practical evaluations are conducted, demonstrating that while improving fault tolerance, the overhead remains acceptable.

Passwordless user authentication schemes with FIDO as the standard have been widely deployed in web applications. Users use hardware tokens to store their identity credentials (i.e., signing keys) and implement strong authentication through a challenge-response mechanism, avoiding the security risks associated with traditional password-based authentication. Distributed Web services can greatly alleviate the system reliability problem caused by single points of failure, and thus have received increasing attention and research. In distributed systems, resources are distributed across multiple servers, and users must interact with them (or a subset of them in thresholding) to obtain network services. User authentication among the distributed (threshold) systems also poses a challenge: how to ensure security and ease of use at the same time? In particular, users need to authenticate to multiple servers when accessing distributed services, and in the case of using FIDO authentication, users need to authenticate to each server using challenge-response authentication, which will greatly reduce the user experience. In this work, we propose the concept namedThreshold Passwordless Authentication(ThPlA) to address this issue. ThPlA allows users to authenticate to at-of-nthresholding system. ThPlA is designed to be compatible with existing FIDO tokens and requires no extra hardware modifications; the user only needs to interact with the hardware token once during an authentication session; and on the service side, the servers do not need to communicate with each other. ThPlA is based on the component namedNon-interactive Threshold Nonce Generation(NI-ThNG), which extends the two-party challenge-response mechanism tot-of-nsettings. We provide a formal definition of ThPlA and NI-ThNG and give practical constructions. We also provide a performance evaluation of ThPlA and NI-ThNG, respectively. Our experimental results show that the schemes are efficient and practical for real-world applications, even in large-scale distributed systems.

Recent progress of randomized fully asynchronous BFT consensus not only presents appealing performance but also ensures superior robustness against an asynchronous adversary that can arbitrarily delay network communication. But these results are mostly discussed in a static setting with fixed nodes. The root reason for the limit is the heavy dependence on a pre-configured threshold cryptosystem, which is critical to practically generate common randomness for overcoming FLP impossibility, but also fixes a designated set of participants. Even worse, most existing asynchronous BFT protocols rely on another strong assumption that messages sent among honest nodes must eventually be delivered, which could be plausible in the static setting (as all nodes can stay online forever to deliver messages) but becomes elusive in a dynamic blockchain, because a departing node might stop transmitting messages and subsequently cause inevitable message omissions as well as potential security violations To accommodate the enticing asynchronous BFT consensus into real-world blockchains where participating nodes are joining and leaving, we introduce Turritopsis, a novel dynamic asynchronous BFT framework that can (i) efficiently re-configure threshold cryptosystem to accommodate the change of consensus nodes and (ii) tolerate admissible message omissions caused by leaving participants. We first propose a dedicatedly optimized asynchronous distributed key refresh protocol that can quickly reset key materials of discrete logarithm threshold cryptosystem (e.g. BLS threshold signature), from which common randomness can be derived to ensure both safety and liveness despite the rotation of participating nodes. We then extend asynchronous BFT to tolerate a combination oftByzantine nodes andlhonest leaving nodes, where 3t+ 2lis smaller than the total numbernof currently participating nodes. This allows us to tolerate up tolleaving nodes that might behave like crashes due to their departures, while simultaneously preserving maximal resilience against ꜖(n– 2l)/3˩ malicious corruptions. We instantiated Turritopsis and implemented it in Python 3. Extensive experiments were conducted, spanning a network of up ton= 60 AWS EC2 nodes across 15 cities, revealing that Turritopsis exhibits performance closely comparable to its fixed-committee counterpart in both latency and throughput.

Due to the promising scalability property, sharding technology has gained widespread attention. It improves the transaction throughput of blockchain systems but also introduces cross-shard transactions. Current two-phase commit (2PC) protocols process different cross-shard transactions sequentially, resulting in significant system overhead and low throughput. Besides, current sharding blockchains rely on Byzantine fault tolerance (BFT) as a black box, lacking specific designs to efficiently handle cross-shard proposals. Moreover, cross-shard communication complexity is high, and transaction processing parallelism is low. In this paper, we first propose P-2PC, a general framework to process cross-shard transactions of different phases in a pipelined way, suitable for most sharding blockchains. Further, we design Cherubim with improved quadruple 2PC, 4P-2PC. By combining P-2PC with an intra-shard pipelined BFT, 4P-2PC achieves both intra-shard and cross-shard pipelined processing. Combined with a newly designed batch processing method, each shard processes 4 transaction batches simultaneously through 1 round of calculation and communication, compared to 4 rounds in previous work. In particular, Cherubim seamlessly integrates a multi-signature algorithm supporting further aggregation, reducing communication complexity. Furthermore, we evaluate our work through theoretical analysis and implementation, proving that Cherubim has a communication complexity linear to the node number. We also propose horizontal and vertical consensus parallelism degrees to evaluate the parallelism ability. Compared to the state-of-the-art solutions, the evaluation demonstrates that Cherubim achieves a transaction throughput improvement of at least 2.28×.

Blockchain technologies have drawn a lot of attentions, and its immutability is paramount to applications requiring persistent records. However, tremendous real-world incidents have exposed the harm of strict immutability, such as the illicit data stored on Bitcoin and the loss of millions of dollars in vulnerable smart contracts. Moreover, “Right to be Forgotten” has been imposed in new General Data Protection Regulation (GDPR) of European Union, which is incompatible with blockchain's immutability. Therefore, it is imperative to design efficient redactable blockchain in a controlled way. In this paper, we present a generic design of redactable blockchain protocols in the permissionless setting, applied to both proof-of-stake and proof-of-work blockchains. Our protocol can (1) maintain the same adversary bound requirement as the underlying blockchain, (2) support various network environments, (3) offer public verifiability for any redaction, and (4) achieve instant redaction, even only within one slot in the best case, which is desirable for redacting harmful data. Furthermore, we define the first ideal protocol of redactable blockchain and conduct security analysis following the language of universal composition. Finally, we develop a proof-of-concept implementation showing that the overhead remains minimal for both online and re-spawning nodes, which demonstrates the high efficiency of our design.

Peer-to-peer (P2P) content delivery is up-and-coming to provide benefits comprising cost-saving and scalable peak-demand handling compared with centralized content delivery networks (CDNs), and also complementary to the popular decentralized storage networks such as Filecoin. However, reliable P2P delivery demands proper enforcement of delivery fairness, i.e., the deliverers should be rewarded in line with their in-time delivery. Unfortunately, most existing studies on delivery fairness are on the basis of non-cooperative game-theoretic assumptions that are arguably unrealistic in the ad-hoc P2P setting. We propose an expressive yet still minimalist security requirement for desired fair P2P content delivery, and give two efficient blockchain-enabled and monetary-incentivized solutions${\mathsf {FairDownload}}$and${\mathsf {FairStream}}$for P2P downloading and P2P streaming scenarios, respectively. Our designs not only ensure delivery fairness where deliverers are paid (nearly) proportional to their in-time delivery, but also guarantee exchange fairness where content consumers and content providers are also fairly treated. The fairness of each party can be assured even when other two parties collude to arbitrarily misbehave. Our protocols provide a general design of fetching content chunk from any specific position so the delivery can be resumed in the presence of unexpected interruption. Further, our systems are efficient in the sense of achieving asymptotically optimal on-chain costs and optimal delivery communication. We implement the prototype and deploy on the Ethereum Ropsten network. Extensive experiments in both LAN and WAN settings are conducted to evaluate the on-chain costs as well as the efficiency of downloading and streaming. Experimental results show the practicality and efficiency of our protocols.

An urgent demand of deploying BFT consensus (e.g., atomic broadcast) over the Internet is raised for implementing (permissioned) blockchain services. The deterministic synchronous protocols can be simple and fast in good network conditions, but are subject to denial-of-service (or even safety vulnerability) when synchrony assumption fails. Asynchronous protocols, on the contrary, are robust against the adversarial network, but are substantially more complicated and slower for the inherent use of randomness.

Despite recent progresses of practical asynchronous Byzantine-fault tolerant (BFT) consensus, the state-of-the-art designs still suffer from suboptimal performance. Particularly, to obtain maximum throughput, most existing protocols \rev with guaranteed linear amortized communication complexity require each participating node to broadcast a huge batch of transactions, which dramatically sacrifices latency. Worse still, the ƒ slowest nodes' broadcasts might never be agreed to output and thus can be censored (where ƒ is the number of faults). Implementable mitigation to the threat either uses computationally costly threshold encryption or incurs communication blow-up by letting the honest nodes to broadcast redundant transactions, thus causing further efficiency issues.

Efficient asynchronous Byzantine agreement (BA) protocols were mostly studied with private setups, e.g., pre-setup threshold cryptosystem. Challenges remain to reduce the large communication in the absence of such setups. Recently, Abraham et al. (PODC’21) presented the first asynchronous validated BA (VBA) with expected $\mathcal{O}$(n3) messages and $\mathcal{O}$ (1) rounds, relying on only public key infrastructure (PKI) setup, but the design still costs $\mathcal{O}$ (λn3logn) bits. Here n is the number of parties, and λ is a cryptographic security parameter.In this paper, we reduce the communication of private-setup free asynchronous BA to expected $\mathcal{O}$(λn3) bits. At the core of our design, we give a systematic treatment of common randomness protocols in the asynchronous network, and proceed as:•We give an efficient reasonably fair common coin protocol in the asynchronous setting with only PKI setup. It costs only $\mathcal{O}$ (λn3) bit and $\mathcal{O}$(1) rounds, and ensures that with at least 1/3 probability, all honest parties can output a common bit that is as if randomly flipped. This directly renders more efficient private-setup free asynchronous binary agreement (ABA) with expected $\mathcal{O}$(λn3) bits and $\mathcal{O}$(1) rounds.•Then, we lift our common coin to attain perfect agreement by using a single ABA. This gives us a reasonably fair random leader election protocol with expected $\mathcal{O}$(λn3) communication and expected constant rounds. It is pluggable in all existing VBA protocols (e.g., Cachin et al., CRYPTO’01; Abraham et al., PODC’19; Lu et al., PODC’20) to remove the needed private setup or distributed key generation (DKG). As such, the communication of private-setup free VBA is reduced to expected $\mathcal{O}$(λn3) bits while preserving fast termination in expected $\mathcal{O}$(1) rounds. Moreover, our result paves a generic path to private-setup free asynchronous BA protocols, as it is not restricted to merely improve Abraham et al.’s specific VBA protocol (PODC’21).Our results and techniques could be found useful and interesting for a broad array of applications such as asynchronous DKG and DKG-free asynchronous random beacon that is friendly for dynamic participation and reconfiguration.

Though the retailer gift card has been an ultra-practical marketing tactic to attract customers to spend more, it, on the contrary, also places a great number of customers in troublesome situations due to its current limitations. First, dealing with unwanted gift cards is often time-consuming, costly, or even risky due to the frequent occurrences of gift card resale frauds. Worse still, the issuance and redemption of gift cards happen inside the retailer as in a “black-box,” indicating that a compromised retailer can cheat customers (or even third-party auditors) to deny the issuances of some unredeemed gift cards. This paper proposes a practical middle-layer solution based on blockchain to address the fundamental issues of the existing gift card system, with incurring minimal changes to the current infrastructure.

With the rapid popularity of blockchain, decentralized human intelligence tasks (HITs) are proposed to crowdsource human knowledge without relying on vulnerable third-party platforms. However, the inherent limits of blockchain cause decentralized HITs to face a few "new" challenges. For example, the confidentiality of solicited data turns out to be the sine qua non, though it was an arguably dispensable property in the centralized setting. To ensure the "new" requirement of data privacy, existing decentralized HITs use generic zero-knowledge proof frameworks (e.g., SNARK), but scarcely perform well in practice, due to the inherently expensive cost of generality.We present a practical decentralized protocol for HITs, which also achieves the fairness between requesters and workers. At the core of our contributions, we avoid the powerful yet highlycostly generic zk-proof tools and propose a special-purpose scheme to prove the quality of encrypted data. By various nontrivial statement reformations, proving the quality of encrypted data is reduced to efficient verifiable decryption, thus making decentralized HITs practical. Along the way, we rigorously define the ideal functionality of decentralized HITs and then prove the security due to the ideal/real paradigm.We further instantiate our protocol to implement a system called Dragoon1, an instance of which is deployed atop Ethereum to facilitate an image annotation task used by ImageNet. Our evaluations demonstrate its practicality: the on-chain handling cost of Dragoon is even less than the handling fee of Amazon's Mechanical Turk for the same ImageNet HIT.

Multi-valued validated asynchronous Byzantine agreement (MVBA), proposed in the elegant work of Cachin et al. (CRYPTO '01), is fundamental for critical fault-tolerant services such as atomic broadcast in the asynchronous network. It was left as an open problem to asymptotically reduce the O(ℓn2 + λn2 + n3) communication (where n is the number of parties, ℓ is the input length, and λ is the security parameter). Recently, Abraham et al. (PODC '19) removed the n3 term to partially answer the question when input is small. However, in other typical cases, e.g., building atomic broadcast through MVBA, the input length ℓ ≥ λn, and thus the communication is dominated by the ℓn2 term and the problem raised by Cachin et al. remains open.

We design and implement the first private and anonymous decentralized crowdsourcing system ZebraLancer, and overcome two fundamental challenges of decentralizing crowdsourcing, i.e. data leakage and identity breach. First, our outsource-then-prove methodology resolves the tension between blockchain transparency and data confidentiality, which is critical in crowdsourcing use-case. ZebraLancer ensures: (i) a requester will not pay more than what data deserve, according to a policy announced when her task is published via the blockchain; (ii) each worker indeed gets a payment based on the policy, if he submits data to the blockchain; (iii) the above properties are realized not only without a central arbiter, but also without leaking the data to the open blockchain. Furthermore, the transparency of blockchain allows one to infer private information about workers and requesters through their participation history. On the other hand, allowing anonymity will enable a malicious worker to submit multiple times to reap rewards. ZebraLancer overcomes this problem by allowing anonymous requests/submissions without sacrificing the accountability. The idea behind is a subtle linkability: if a worker submits twice to a task, anyone can link the submissions, or else he stays anonymous and unlinkable across tasks. To realize this delicate linkability, we put forward a novel cryptographic concept, i.e. the common-prefix-linkable anonymous authentication. We remark the new anonymous authentication scheme might be of independent interest. Finally, we implement our protocol for a common image annotation task and deploy it in a test net of Ethereum. The experiment results show the applicability of our protocol with the existing real-world blockchain.