The proof-of-stake (PoS) protocols aim to reduce the unnecessary computing power waste seen in Bitcoin. Various practical and provably secure designs have been proposed, like Ouroboros Praos (Eurocrypt 2018) and Snow White (FC 2019). However, the essential security property of unpredictability in these protocols remains insufficiently explored. This paper delves into this property in the cryptographic setting to achieve the "best possible" unpredictability for PoS protocols.We first present an impossibility result for all PoS protocols under the single-extension design framework, where each honest player extends one chain per round. The state-of-the-art permissionless PoS protocols (e.g., Praos, Snow White, and more), are all under this single-extension framework. Our impossibility result states that, if a single-extension PoS protocol achieves the best possible unpredictability, then this protocol cannot be proven secure unless more than 73% of stake is honest.To overcome this impossibility, we introduce a new design framework called multi-extension PoS, allowing each honest player to extend multiple chains using greedy strategy in a round. This strategy allows us to construct a class of PoS protocols that achieve the best possible unpredictability. Additionally, we design a new tiebreak rule for the multi-extension protocol to choose the best chain that can be extended faster, ensuring that the adversary cannot slow-down the chain growth of honest players. It is noteworthy that these protocols can be proven secure, assuming a much smaller fraction (e.g., 57%) of stake to be honest.For a comprehensive security analysis in the cryptographic setting, we develop several new techniques. Analyzing chain growth becomes highly non-trivial as players can extend multiple chains. We introduce a new analysis framework using the Markov chain to assess the chain growth of a multi-extension protocol. To prove the common prefix property, we introduce a concept called "virtual chains" and present a reduction from the regular version of the common prefix to "common prefix w.r.t. virtual chains."

Byzantine Fault-Tolerant (BFT) consensus protocols are increasingly utilized in blockchain environments. In such protocols, the leader node holds the authority to dictate the transaction order, potentially impacting the fairness of decentralized finance (DeFi) applications. For instance, attackers can exploit this to manipulate transaction order and conduct front-running attacks. The concept of order-fairness, which recently emerged, has become a critical property for preventing a single node from unilaterally determining transaction order. Protocols designed to uphold order-fairness often rely on the sequence in which transactions appear across the network, a factor that can be influenced by the network’s topology. However, this approach has inherent limitations, such as challenges in avoiding Condorcet cycles (Kelkar et al., Crypto 2020).To address these challenges, we propose a novel definition of fairness that requires concealing transaction content before ordering. Additionally, we extend the definitions of liveness and safety of consensus protocols to cover the transaction decryption process, guaranteeing the successful decryption of transactions. Based on the existing BFT protocol and utilizing threshold encryption algorithms, we designed a framework called EquiBFT which can incorporate fairness to BFT protocols. We have proven that the EquiBFT satisfies fairness while ensuring the liveness and safety. We implemented this framework based on HotStuff (Yin et al., PODC 2019) and validated its feasibility in a real-world network environment.

The management of cryptographic keys within cloud services is crucial for ensuring data security but raises significant privacy and trust issues. This paper addresses the vulnerabilities of conventional key management systems (KMS), where cloud service providers might access and control user keys without consent, as well as intercept and misappropriate users’ secret data. To address these concerns, we propose a KMS protocol that leverages trusted hardware to minimize the level of trust required in cloud service providers. Our protocol ensures that the customer master key remains confined within a secure enclave, inaccessible to the service provider, and incorporates a bidirectional authentication mechanism to protect against impersonation by malicious providers. Within the universally composable framework, we design and analyze our protocol and rigorously prove its security. As a result, our designed KMS can be used in composition with any system, and its security can be guaranteed under any conditions. We also develop a prototype KMS based on Intel Trust Domain Extensions and evaluate its performance, emphasizing the system’s viability in real-world applications. The source code for our prototype is publicly available.

The proof-of-stake (PoS) protocols aim to reduce the unnecessary computing power waste seen in Bitcoin. Various practical and provably secure designs have been proposed, like Ouroboros Praos (Eurocrypt 2018) and Snow White (FC 2019). However, the essential security property of unpredictability in these protocols remains insufficiently explored. This paper delves into this property in the cryptographic setting to achieve the "best possible" unpredictability for PoS. We first present an impossibility result for all PoS protocols under the single-extension design framework, where each honest player extends one chain per round. The state-of-the-art permissionless PoS protocols (e.g., Praos, Snow White, and more), are all under this single-extension framework. Our impossibility result states that, if a single-extension PoS protocol achieves the best possible unpredictability, then this protocol cannot be proven secure unless more than 73% of stake is honest. To overcome this impossibility, we introduce a new design framework called multi-extension PoS, allowing each honest player to extend multiple chains using a greedy strategy in a round. This strategy allows us to construct a class of PoS protocols that achieve the best possible unpredictability. It is noteworthy that these protocols can be proven secure, assuming a much smaller fraction (e.g., 57%) of stake to be honest.

Asynchronous Byzantine Fault-Tolerant (BFT) consensus protocols maintain strong consistency across nodes (i.e., ensure safety) and terminate probabilistically (i.e., ensure liveness) despite unbounded network delay. In contrast to protocols under partial synchrony, asynchronous counterparts pay no extra timing assumptions for electing a special role, and thus is more robust to network issues. To formally study this feature, we propose a new classification method for consensus and accordingly categorize relevant work: timing-balanced protocols are those that do not introduce strictly stronger timing-related assumptions for liveness, compared to ones required by safety.

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.

Key-value (KV) stores play an important role in today’s online service systems, but concerns about server-side attacks hinder users from uploading their workloads. The proposal of the hardware trusted execution environment (TEE) like Intel SGX provides an alternative for trusted computing on untrusted hosts. TEE can be used to construct privacy preserving scheme for KV stores. The current research on secure persistent KV store is limited to the shielded execution framework which involves a large trusted computing base and high overhead.In this paper, we propose Pldb, a secure persistent KV store that is based on Log-Structured Merge (LSM) tree. In order to ensure security, TEE’s access to persistent storage data needs to pass through the encryption/decryption interface. This is the main overhead of secure KV data storage based on TEE design. We designed a hybrid KV storage structure, which encrypts the value data and stores it directly on the disk, thereby reducing the encryption/decryption interface calls through the TEE. With a carefully designed architecture leveraging Intel SGX, Pldb provides security properties including confidentiality, integrity, authentication, and data freshness to prevent rollback attacks. We extend LevelDB to implement a fully functional prototype system. Experiments show that our system can achieve reasonable overhead under different types of workloads.

Cryptocurrencies have recently gained huge popularity. It is desirable to come up with effective approaches to constructing better blockchain protocols. In this paper, inspired by the 2-hop design by Duong et al (ePrint 2016/716), we put forth a generic paradigm for blockchain design, called n-hop blockchain. It includes one main chain, which is supported by (n -- 1) supporting chains; hence, the main chain can achieve better security performance. In our paradigm, we show that our n-hop design can be easily extended to (n + 1)-hop design. To demonstrate the power of our paradigm, we showcase two instantiations: 2-hop blockchain variant, a combination of proof-of-stake and proof-of-work, and 3-hop blockchain variant, which is extended from 2-hop blockchain variant by adding Byzantine fault tolerance blockchain in 3rd hop.

Yang and Shieh proposed two password authentication schemes based on smart cards. The best merit of their schemes is that the remote server can verify a login user without any prior knowledge except a login request message. Unfortunately, some security weaknesses had been found and kinds of attacks were presented later. Although some improvements were proposed to fix those weaknesses, part of these improvements need the remote server to maintain verification tables and the other improvements were proved insecure either. In this paper, we will propose two improved schemes that can withstand all existed attacks while keeping the best merit of the original schemes. The remote server in our improved schemes is still able to verify a login user only by a request message.