Oh University of Washington Seattle
Stanford University
Stanford University
University of Washington Seattle
Copyright By PowCoder代写 加微信 powcoder
Princeton University
Proof-of-Stake Longest Chain Protocols: Security vs Predictability
The Nakamoto longest chain protocol is remarkably simple and has been proven to provide security against any adversary with less than 50% of the total hashing power. Proof-of-stake (PoS) proto- cols are an energy efficient alternative; however existing protocols adopting Nakamoto’s longest chain design achieve provable se- curity only by allowing long-term predictability, subjecting the system to serious bribery attacks. In this paper, we prove that a natural longest chain PoS protocol with similar predictability as Nakamoto’s PoW protocol can achieve security against any adver- sary with less than 1/(1 + 𝑒) fraction of the total stake. Moreover we propose a new family of longest chain PoS protocols with a formal proof of their security against a 50% adversary, while only requiring short-term predictability.
CCS CONCEPTS
• Security and privacy → Distributed systems security.
proof-of-stake, blockchain protocols, security analysis
ACM Reference Format:
, , , Sewoong Oh, , , Xuechao Wang, and . 2022. Proof-of-Stake Longest Chain Protocols: Security vs Predictability . In Proceedings of the 2022 ACM Workshop on Developments in Consensus (ConsensusDay ’22), November 7, 2022, Los Angeles, CA, USA. ACM, , NY, USA, 14 pages. https://doi.org/10.1145/3560829.3563559
The authors are listed alphabetically. and i were partially supported by a US-Israel BSF grant. For correspondence on the paper, please contact Xuechao Wang at
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from
ConsensusDay ’22, November 7, 2022, Los Angeles, CA, USA
© 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-9879-4/22/11. . . $15.00 https://doi.org/10.1145/3560829.3563559
Xuechao Wang University of Illinois Urbana-Champaign
Weizmann Institute of Science
1 INTRODUCTION
Bitcoin is the original blockchain, invented by Nakamoto. At the core is the permissionless consensus problem, which Nakamoto solved with a remarkably simple but powerful scheme known as the longest chain protocol. It uses only basic cryptographic primi- tives (hash functions and digital signatures). In the seminal paper [22] that introduced the original Bitcoin protocol, Nakamoto also showed that the protocol is secure against one specific attack, a private double-spend attack, if the fraction of adversarial hashing power, 𝛽, is less than half the hashing power of the network. This attack is mounted by the adversary trying to grow a long chain over a long duration in private to replace the public chain. Subsequently, the security of Bitcoin against all possible attacks is proven in [15], and further extended to a more realistic network delay model in [23].
The permissionless design (robustness to Sybil attacks) of Bitcoin is achieved via a proof-of-work (PoW) mining process, but comes at the cost of large energy consumption. Recently proof-of-stake (PoS) protocols have emerged as an energy-efficient alternative. When running a lottery to win the right to propose the next valid block on the blockchain, each node wins with probability proportional its stake in the total pool. This replaces the resource intense mining process of PoW, while ensuring fair chances to contribute and claim rewards.
There are broadly two families of PoS protocols: those derived from decades of research in Byzantine Fault Tolerant (BFT) proto- cols and those inspired by the Nakamoto longest chain protocol. At- tempts at blockchain design via the BFT approach include Algorand [8, 16] and Hotstuff [28]. The adaptation of these new protocols into blockchains is an active area of research and engineering [3, 16], with large scale permissionless deployment as yet untested.
Motivated and inspired by the time-tested Nakamoto longest chain protocol are the PoS designs of Snow White [5] and the Ouroboros family of protocols [1, 9, 19]. The inherent energy ef- ficiency of the PoS setting comes with the cost of enlarging the space of adversarial actions. In particular, the attacker can “grind” on the various sources of the randomness, i.e., attempt multiple samples from the sources of randomness to find a favorable one. Since these multiple attempts are without any cost to the attacker
ConsensusDay ’22, November 7, 2022, Los Angeles, CA, USA
this strategy is also known as a nothing-at-stake (NaS) attack. One way to prevent an NaS attack is to rely on a source of randomness on which a consensus has been reached. In Snow White [5] and the Ouroboros family [1, 9, 19], this agreed upon randomness is derived from the stabilized segment of the blockchain from a few epochs before. Each epoch is a fixed set of consecutive PoS lottery slots that use the same source of agreed upon randomness. However, this comes at a price of allowing each individual node to simulate and predict in advance whether it is going to win the PoS lottery at a given slot and add a new block to the chain. Further, as the size of each epoch is proportional to the security parameter 𝜅 (specifically, a block is confirmed if and only if it is more than 𝜅 blocks deep in the blockchain), higher security necessarily implies that the nodes can predict further ahead into the future. This is a serious security concern, as predictability makes a protocol vulnerable against other types of attacks driven by incentives, such as predictable selfish mining or bribing attacks [6].
Nakamoto-PoS. A straightforward PoS adoption of Nakamoto protocol, which in contrast to Ouroboros and Snow White can update randomness every block, runs as follows; we term the pro- tocol as Nakamoto-PoS. The protocol proceeds in discrete time units called slots, during which each node runs the “PoS lottery”, a leader election with a winning probability proportional to the stake owned by the node – winners get to propose new blocks. Each node computes h𝑎𝑠h = 𝐻 (time, secret key, parentBk.h𝑎𝑠h), where the hash function 𝐻 is a verifiable random function (VRF) (formally defined in Definition 3.2), which enables the nodes to run leader elections with their secret keys (the output h𝑎𝑠h is verified with the corresponding public key). The node 𝑛 is elected a leader if h𝑎𝑠h is smaller than a threshold 𝜌 × stake𝑛, that is proportional to its stake stake𝑛 , then the node 𝑛 proposes a new block consisting of time, parentBk.h𝑎𝑠h, public key and h𝑎𝑠h, and appends it to the parent block. A detailed algorithmic description of this protocol is in Algorithm 1 (with 𝑐 = 1). Following Nakamoto’s protocol, each honest node runs only one election, appending to the last block in the longest chain in its local view. Having the hash function depend on parentBk.h𝑎𝑠h ensures that every appended block provides a fresh source of randomness, for the following elections. However, there is no consensus on the randomness used and the randomness is block dependent, giving opportunities for the adversary to mount a NaS attack by trying its luck at many different blocks.
The analysis of the security of the Nakamoto-PoS protocol is first attempted in [14]. Just like Nakamoto’s original analysis, their analysis is on the security against a specific attack: the private double-spend attack. Due to the NaS phenomenon, they showed the adversary can grow a private chain faster than just growing at the tip, as though its stake increases by a factor of 𝑒. This shows that the PoS longest chain protocol is secure against the private double spend against if the adversarial fraction of stake 𝛽 < 1/(1+𝑒). Later, it was formally proven in [11] that the true security threshold against all attacks is the same as the private attack threshold 1/(1 + 𝑒).
However, the fraction that can be tolerated (1/(1 + 𝑒)) is still less than the fraction for the longest chain PoW protocol (1/2). In [14] and [13], modifications of the longest chain protocol (called 𝑔-greedy and 𝐷-distance-greedy) are proposed, based on improve- ments to their security against the private double-spend attack.
In the full version of this paper [2], it was shown that, unlike the longest chain protocol, these protocols are subject to worse public- private attacks, and they not only do not exhibit true improvements in security than the longest chain protocol, but in many cases, they do far worse.
S Protocol Contribution. Taking a different direction,
we propose a new family of simple longest chain PoS protocols
that we call 𝑐-Nakamoto-PoS (§4); the fork choice rule remains
the longest chain but the randomness update in the blockchain is
controlled by a parameter 𝑐, the larger the value of the parameter
𝑐, the slower the randomness is updated. The common source of
randomness used to elect a leader remains the same for 𝑐 blocks
starting from the genesis and is updated only when the current
block to be generated is at a depth that is a multiple of 𝑐. When
updating the randomness, the hash of that newly appended block is
used as the source of randomness. The basic PoS Nakamoto protocol
corresponds to 𝑐 = 1, where the NaS attack is most effective. We
can increase 𝑐 to gracefully reduce the potency of NaS attacks and 1
increase the security threshold . To analyze the formal security of this family of protocols, we combine the analysis for 𝑐 = 1 with results from the theory of branching random walks [25]; this allows us to characterize the largest adversarial fraction 𝛽𝑐∗ of stake that can be securely tolerated. As 𝑐 → ∞, 𝛽𝑐∗ → 1/2. We should point out that the Ouroboros family of protocols [1, 9] achieves security also by an infrequent update of the randomness; however, the update is much slower than what we are considering here, at the rate of once every constant multiple of 𝜅, the security parameter. This is needed because the epoch must be long enough for the blockchain in the previous epoch to stabilize in order to generate the common randomness for the current epoch. Here, we are considering 𝑐 to be a fixed parameter independent of 𝜅, and show that this is sufficient to thwart the NaS attack. Technically, we show that even if 𝑐 is small, there is no fundamental barrier to achieving any desired level of security 𝜅. Hence, achieving a high level of security 𝜅 should not come at the cost of longer predictable window, and in this paper we introduce a natural adoption of Nakamoto protocol to achieve this. The practical implication of this result is shown in Fig. 1, where we can see that 𝑐-Nakamoto can achieve comparable security with a much smaller prediction window than a current implementation of Ouroboros as part of the Cardano project [26].
Related work. PoSAT [10] is a follow-up work of this paper, which borrowed our idea of 𝑐-correlation. It uses a fancy cryptographic primitive named verifiable delay function to achieve PoW-like dy- namic availability. However, PoSAT does not support dynamic stake and it is non-trivial to add this feature. How to design a PoS protocol that solves both the problems of dynamic availability and dynamic stake remains open.
Organization. In §2 we formally define prediction windows for any PoS protocol and discuss a class of bribery attacks enabled by the predictive feature of leader elections of many PoS protocols. The seriousness of these bribery attacks is underscored by the fatal nature of the attacks (double-spends and ledger rewrites) and that they can be implemented by bribing a fraction of users possessing an arbitrarily small total stake. This sets the stage for the protocols
A proof-of-space variant of this protocol is adopted by the with a choice of 𝑐 = 32: https://docs.chia.net/docs/03consensus/attacks_and_countermeasures
Proof-of-Stake Longest Chain Protocols: Security vs Predictability
Figure 1: The security threshold 𝛽𝑐∗ of 𝑐-Nakamoto-PoS against the prediction window, equaling to 𝑐 times the inter-block time, which we set to be 20s, to match the implementation of Orouboros in Car- dano. The Cardano project currently updates the common random- ness every 5 days (21600 blocks, or 10𝜅), while the security threshold of 𝑐-Nakamoto-PoS can approach 1/2 with much higher randomness update frequency.
discussed in this paper, Nakamoto-PoS and 𝑐 -Nakamoto-PoS, which have low prediction windows and hence resistant to these bribery attacks. §3 discusses the formal security model we use to the analyze the 𝑐-Nakamoto-PoS protocols (defined formally in §4). The formal security analyses of 𝑐-Nakamoto-PoS protocols are conducted in §5. This analysis, conducted in the static stake setting, is generalized to dynamic stake settings in §6.
2 PREDICTABILITY IN POS PROTOCOLS
Proof-of-work (PoW) protocols such as Nakamoto’s protocol for Bit- coin achieve high security while maintaining a high unpredictability as to which miners can propose future blocks. A very attractive fea- ture of this PoW protocol is that nodes that mine a valid block have no further ability to update the block after they have solved the min- ing puzzle, since the nonce seals the block making it tamper-proof. Thus no node knows whether they have the power to propose the block till they solve the puzzle, and once they solve the puzzle, they have no future rights to alter the content.
This causality is reversed in proof-of-stake (PoS) protocols: usu- ally, the node that is eligible to propose a block knows a priori of its eligibility before proposing a block. This makes PoS protocols vulnerable to a new class of serious attacks not found in the PoW setting. We will show that a set of miners controlling an infinitesi- mal fraction of the stake can potentially completely undermine the security of the protocol. We demonstrate that the longer the pre- diction window, the more serious the attack space is. This raises an important questions as to whether it is possible to design a secure proof-of-stake protocol which has minimal prediction window.
We point out that an existing work [6] has already raised this issue that PoS protocols are forced make a tradeoff between pre- dictability and NaS attacks. While that work mainly concerned itself with incentive attacks, our concern here is adversarial attacks that compromise consensus. We point out that even in the adversarial setting, all provably secure PoS protocols have a long prediction
ConsensusDay ’22, November 7, 2022, Los Angeles, CA, USA
window; the main contribution of this paper is to design such a protocol and show its security up to 50% of adversarial stake.
2.1 Adaptive Adversaries and the VRF Attack
Figure 2: Structure of bribing attack
A popular model that has been proposed to capture the effect of future prediction in the PoS setting is the so-called adaptive adversary model [9, 16]. In the adaptive adversary model, a node remains honest unless corrupted by an adversary (who can change who they are corrupting based on the public state). The adversary has a bound on how many nodes it can corrupt at any given time. To defend against an adaptive adversary model, many protocols have moved from global predictability of future block proposers (i.e., everyone knows who the future block leaders are) [19] to local predictability (i.e., each miner knows when in the future they will propose a block) [9, 16]. The local predictability is achieved using a Verifiable Random Function (VRF) [20] based leader-election.
However, the adaptive adversary model assumes that miners do not have any independent agency but rather only get corrupted based on an adversary’s instructions. An adversary can easily cir- cumvent this assumption by establishing a website where it can offer a bribe to anyone who posts their credentials for proposing blocks in an upcoming epoch of time. Thus even when the node’s future proposer status is not public knowledge, this bribing website can solicit such information and help launch serious attacks (see Fig. 2).
2.2 Longest Chain protocols
We first consider longest-chain PoS protocols, in order to demon- strate our prediction attacks. We begin with a definition of predic- tion window of a protocol.
Definition 2.1 (𝑊 -predictable). Given a PoS protocol ΠPoS, let C be a valid blockchain ending with block 𝐵 with a time stamp 𝑡. We say a block 𝐵 is 𝑤 (𝐵)-predictable, if there exists a time 𝑡1 > 𝑡 and a block 𝐵1 with a time stamp 𝑡1 such that (𝑖) 𝐵1 can be mined by miner (using its private state and the common public state) at time 𝑡; and (𝑖𝑖) 𝐵1 can be appended to C′ to form a valid blockchain for any valid chain C′ that extends C by appending 𝑤 − 1 valid
ConsensusDay ’22, November 7, 2022, Los Angeles, CA, USA
Longest Chain [19] [9] [1] [5] [14]
BFT [13] Algorand [8]
Our results Nakamoto-PoS 𝑐 -Nakamoto-PoS
𝛽 2 unknown 3 1+𝑒 𝛽𝑐
Table 1: Our results decouple the prediction window 𝑊 and the security parameter 𝜅 , achieving any combination of (𝑊 , 𝜅 ) . Prediction window 𝑊 for other PoS protocols are strongly coupled with the security parameter 𝜅 = log(1/𝑃failure). The maximum threshold of adversarial stake that can be tolerated by the PoS protocols while being secure is 𝛽∗. Nakamoto-PoS is the most basic way of extending Nakamoto protocol to the PoS setting. This was originally introduced in [13, 14] but with an incomplete security analysis; In §5 we show 𝛽𝑐∗ ≈ 1/2 − Θ(√︁(1/𝑐)ln𝑐) and numerically tabulate 𝛽𝑐∗ (example: 𝛽𝑐∗ = 39% for 𝑐 = 10). [1, 9, 19] are the Ouroboros family, [5] is Snow White, [14] is 𝑔-Greedy, and [13] is 𝐷 -Distance-Greedy.
𝑊 2𝜅 3𝜅 6𝜅 6𝜅 1 1 ∗111∗
blocks with time stamps within the interval (𝑡,𝑡1). By taking the maximum over the prediction parameter over all blocks in ΠPoS, i.e., let 𝑊 = max𝐵 𝑤 (𝐵), we say ΠPoS is 𝑊 -predictable. 𝑊 is the size of the prediction window measured in units of number of blocks.
We note that our definition is similar to the definition of 𝑊 – locally predictable protocols in [6]. We note furthermore that longest chain protocols also have a 𝜅-deep confirmation policy, where a block embedded deep enough is deemed to be confirmed.
2.3 Prediction Attack on 𝑊 -predictable protocols
Let us consider a 𝑊 -predictable protocol, where the prediction window 𝑊 is longer than the confirmation window 𝜅. We note that the prediction window of many existing protocols are quite large, as demonstrated in Table 1 and therefore this is a reasonable assumption. We will consider the alternative case (𝑊 << 𝜅 in the upcoming subsection).
Figure 3: Prediction attack on .
Consider block B that has been mined at time 𝑡 (assume that B is 𝑊 -predictable, since such a block exists by definition). The adversary launches a prediction attack by launching a website where it announces a reward for miners which possess a future block proposal slot. Some of the leaders respond to this call (these are shown with a red outer circle in Fig. 3). We note that while the
adversary requires 𝜅 + 1 leaders out of 2𝜅 + 1 slots to respond to
the bribe, the total s
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com