Proof-of-Stake consensus protocols give rise to complex modeling challenges. We analyze the Babylon update (October 2019) to the Proof-of-Stake protocol on the Tezos blockchain, and demonstrate that, under certain conditions, rational participants are incentivized to behave dishonestly. In doing so, we provide a theoretical analysis of the feasibility and profitability of a block stealing attack that we call selfish endorsing, a concrete instance of an attack previously only theoretically considered. We propose and analyze a simple change to the Tezos protocol which significantly reduces the (already small) profitability of this dishonest behavior, and introduce a new delay and reward scheme that is provably secure against length-1 and length-2 selfish endorsing attacks. Our framework provides a template for analyzing other Proof-of-Stake protocols for the possibility of selfish behavior.
Blockchain technologies have received significant attention since the release of the Bitcoin protocol in 2008 [1]. Blockchains arose as a solution to a critical problem in enabling permissionless, decentralized cryptocurrencies: how to maintain a global consensus on user account balances. The Bitcoin network addressed this problem by putting every transaction into a globally visible ledger protected by a Proof-of-Work (PoW) consensus protocol. In PoW, each block creator is tasked with assembling a list of valid transactions and doing costly computational work, and is rewarded with some amount of the native asset, Bitcoin.
Proof-of-Stake (PoS) protocols are seen as potential successors of PoW protocols. Both kinds of protocols run a lottery to select the creator of the next block (the lottery is implicit in PoW, explicit in PoS), and in order to prevent malicious participants from creating many identities to increase their chances of winning, entry into these lotteries must be costly. PoW requires that lottery entrants burn computational cycles in order to join, while PoS requires participants to forego the use of staking capital for some duration of time. In particular, PoS protocols require that staked capital be forfeited if the behavior of a miner is not consistent with that specified by the rules of the protocol. While both approaches reward participants proportionally to expenditure, PoW has received criticism, and PoS is thought to provide an important step forward for consensus protocols on blockchains.
The three main critiques of PoW protocols are the environmental impact, the inflationary tendencies, and the centralization found in many digital currencies. The environmental argument is a result of PoW using significant amounts of energy; by some estimates, the annual energy consumption of the Bitcoin network is equivalent to that of Austria [2]. The related inflationary criticism stems from the fact that it requires substantial real world expenditures by miners on hardware and electricity. These miners are in turn compensated by large block rewards that lead to inflationary pressure on the currency, and if the rewards are reduced, fewer miners participate and the security of the network degrades. PoS protocols do not suffer from these limitations. Another critique of PoW arises from concerns around the concentration of mining power. As of November 2019, F2Pool owned 18% of the hashpower in the Bitcoin network, and the top four mining pools combined controlled more than 50% of the hashpower [3]. However, because the ownership of cryptocurrencies is far from decentralized [4], PoS may not address this issue either.
Tezos [5], EOS [6], Cardano (ADA) [7], BlackCoin [8], and Nxt [9] represent the major PoS networks that are currently running.1 One of the distinguishing features of Tezos is that it has a built-in governance protocol, which allows changes to the specification to be voted on by participants in the P2P network. In contrast, the development of Bitcoin has been slow because few developers want to risk forking the network over a protocol change [10]. The design of the Tezos network hopes to encourage agreement on upgrades by creating a specific venue and timeline for voting on software updates. As of January 2020, each change required a quorum of participants and over 80% approval to be instantiated [11]. On October 17, 2019, an update called Babylon [12][13] was accepted into the Tezos protocol.
In the paper, we analyze a large component of this upgrade: a new consensus protocol called Emmy [14]. In particular, we identify an incentive vulnerability in the Tezos PoS mechanism, analyze the severity of an attack, and establish security properties of alternative mechanisms. In doing so, we provide a simple theoretical framework that can be used to analyze other implementations, and that we hope will encourage a more formal treatment of the security properties of PoS protocols.
Section 2 describes how PoS is implemented in Tezos, Section 3 formalizes the attack that we call selfish endorsing and assesses the probability of it being profitable for a rational agent, Section 4 proposes a simple heuristic fix to the Emmy protocol, and Section 5 proposes an alternative mechanism and proves that it is secure against a subset of selfish endorsing attacks, before concluding in Section 6.
We seek to understand the extent to which rational participants in a particular PoS system can benefit by not behaving according to the protocol. This is analogous to the question asked by Eyal and Sirer (2013) [15], who demonstrate that miners can earn a higher proportion of rewards in a PoW protocol by deviating from the honest protocol and following a selfish mining strategy. Follow-up work includes Sapirshtein et al. (2016) [16], who identify the optimal such policy; Nayak et al. (2016) [17], who consider network attacks; and Kwon et al. (2017) [18], who consider the impact of selfish mining in the context of mining pools.
In regard to PoS, Brown-Cohen et al. (2019) show that complete security in their model of longest-chain PoS protocols is not possible [19]. The dishonest behavior that we refer to as selfish endorsing is a real-world instance of the theoretical predictable selfish mine attack that appears in their work. We are not aware of any other academic work that formally analyzes the incentives of the Tezos PoS protocol. Nomadic Labs, the team that implemented Emmy [14], did provide a blog post with the results of an incentive analysis [20], but without providing an explicit formalism for the model used or the probabilistic analysis.2 In this work, we present the complete derivation of an attack model, and make explicit the methods used to obtain our results.
Tezos implements an optional Delegated Proof-of-Stake (DPoS) protocol [5][11], which is sometimes referred to as Liquid Proof-of-Stake [21] to distinguish it from other, more rigid DPoS implementations [6].3
Members of the Tezos consensus layer are called delegates and are considered active when they participate in the creation and validation of blocks (and passive otherwise). The Tezos unit of account (XTZ) is split into groups of 8,000 tokens called rolls, and each delegate is associated with a set of rolls. Active delegates participate in a lottery to bake and endorse a block at every block-height in the chain. Bakers are responsible for including transactions in blocks, while endorsers cryptographically sign the “best” block that they have seen at each height.
The baking-and-endorsing priority lottery is carried out by randomly selecting rolls and giving the next available priority to the owner of that roll, a technique known as follow-the-Satoshi [22]. For each block-height, a list of bakers is created using the random roll selection process, and the index of a baker in this list determines the priority with which they can create a block at this height. Additionally, a set of 32 endorsers is created for each block-height. There is no priority list for endorsers, and each has equal weight. Each draw from the set of rolls is done with replacement, so the same delegate may appear many times on the baking priority list as well as in the set of endorsers.
Bakers and endorsers are rewarded based on participation, which creates an incentive for delegates to remain active. Figure 1 shows how the blocks are created and endorsed as well as the value of each, which is a function of the reward scheme described below.
The new consensus protocol, Emmy, which was part of the October 2019 Babylon update, is distinct from its predecessor, Emmy, in three important ways:
1. A block’s validity-time is a function of the number of endorsements it includes, in addition to the priority of the baker. Each block includes a timestamp for when it was created. In order to regulate the rate at which blocks are created, Emmy uses a minimum delay between blocks (see Equation 1), which is what we refer to as the validity-time. When a node in the P2P network checks an incoming block, it ensures that the difference in the timestamp of that block and the previous block in the chain is greater than the validity-time.
Before Emmy the validity-time was only a function of the priority of the baker, but now it is also a function of the number of endorsements it includes. Importantly, the number of endorsements is not the number of delegates who endorse the block itself, but rather the number of endorsements for the previous block that this block includes. Since endorsements are operations that are heard over the network, including an endorsement in a block is analogous to including a transaction.
In order for a block to be considered valid, its timestamp must differ from the previous block’s timestamp by at least seconds, where defines the validity-time and is the following function of the baker’s priority, and the number of endorsements included in the block, (see Minimal block delays in [11]):
The effect is that for each priority-level that a baker is below the highest-priority (0), the validity-time for the block increases by 40 seconds. Also, for each endorsement that is missed below 24 of the 32 endorsers, the validity-time increases by 8 seconds. A block may miss up to 8 endorsements without incurring a time penalty, but each additional missed signature slows validity by 8 seconds.4 If each block is baked by the priority delegate and endorsed by most of the endorser set, then a block will be created every 60 seconds and the Tezos network is considered healthy.
2. The fork-choice rule was changed. The fork-choice rule is used by nodes in a P2P network to choose the branch that they will extend. Before this update, the canonical fork (i.e., the currently active fork) was the one with the most endorsements (i.e., a heaviest-chain rule [5]). After the update, the best fork became the one with the longest chain from the genesis block. This modified rule makes evaluation of branches easier, and alleviates a baker’s uncertainty as to when to publish blocks in order to avoid missing out on late endorsements.5 Brown-Cohen et al. [19] already showed that this longest-chain rule can lead to theoretical vulnerabilities. Here we focus on one of these, predictable selfish mining, and our work represents a real-world instance of this vulnerability.
3. The rewards for baking and endorsing blocks were modified. Before the change, baking a block earned the delegate a constant reward of 16 XTZ, but in Emmy the block rewards are a function of the baker’s priority, and the number of endorsements for the previous block that are included in this block (see Rewards in [11]). Let be the baking reward. In Emmy, we have
The rewards for endorsements were also modified. Previously, endorsement rewards were a function of the priority of the block that the endorsement signed, but in Emmy they are a function of the priority of the block that includes the endorsements. Denote the priority of the baker who baked the block that includes an endorsement as Then the endorsing reward, , is calculated as
Figure 1 illustrates the rewards that the bakers and endorsers earn under the Emmy rules.
We now give an example of the vulnerability that we call selfish endorsing, which with some probability incentivizes a rational baker to ignore the longest-chain rule and create a separate two-block fork faster than the rest of the network can publish two blocks. We give an example to illustrate that selfish endorsing is a profitable deviation from the intended protocol based on block and endorsement rewards alone. Additionally, this attack provides an opportunity for a 1-confirmation double-spend.6
Let be a rational delegate who is willing to deviate from the Emmy protocol. We describe baking and endorsing rights in terms of slots that correspond to a specific length of the chain (e.g., a block baked at height from the genesis block occupies the slot). In the Emmy implementation, delegates see exactly who will have baking and endorsing rights for the next several thousand () blocks. For a given slot let be the highest priority and the number of endorsement rights that is randomly allocated. Priorities are zero-indexed, with 0 being the highest. Additionally, let denote the number of consecutive top baking priorities given to at slot (e.g., if the baking priority list for the slot is , then ).
In our analysis, we make the assumption that messages are sent and received instantaneously. While it is out of scope handle propagation delays in this paper, this question has been studied in the context of Bitcoin [23] and offers an interesting avenue for future work.
Figure 2 shows that an attacker with second priority () at slot can bake a block that will end up on the final chain despite the first-priority delegate publishing on time. This is malicious because the baker with the lower priority stole the block reward from the highest priority baker.
Delegate is able to look ahead and calculate when this attack can be executed because the baking priorities and endorsing rights are publicly known into the future. We verify that the selfish chain will create two blocks faster than the honest chain using Equation 1.
Let and be the total time to create two blocks for the honest and selfish chains, respectively. We have,
The combination of having a large share of endorsements for slot and the two highest priorities for slot allows to slow down the honest network by only endorsing a private block at slot Attacker can then produce a second valid block before the honest network does, and create the unique longest chain. Using Equation 2 and Equation 3, we can verify that this selfish behavior also results in a greater reward than following the honest protocol, thus demonstrating that this is a profitable deviation in its own right, and not just an opportunity for a 1-confirmation double spend.
For this, let denote the total reward earned by over the next two blocks while behaving honestly. The labels underneath the expressions indicate the reason each reward is added. We have
Similarly we can calculate the total rewards that the attacker earns while selfishly endorsing, denoted We have
This demonstrates that the gain in reward from creating a new block at slot outweighs the loss in reward from the endorsements on slot ending up on a lower priority block. Critically, the rewards for the 14 endorsements for slot (which are essential in slowing down the honest network) do not decrease at all because these endorsements are still included on the block baked by at slot which has priority 0.
Similarly to selfish mining, if this attack were to be executed it would be easily detected through the increased presence of orphan blocks, and the baker who was stealing the block would be identified, which may act as a deterrent from this behavior. However, it is worth noting that there is no mechanism within the Emmy mechanism to punish this block stealing attack. The protocol, as originally defined, has the ability to slash a delegate’s block and endorsement rewards if they are caught signing multiple blocks of the same height [5], but selfish endorsing is different in that is impossible to cryptographically prove that a delegate is misbehaving and thus a punishment cannot be programmed in to the protocol.
Figure 2 describes just one instance of a whole family of length-2 selfish endorsing attacks. In order to calculate the probability that any such attack is possible, we develop a generalized model. Consider tuples of the form . We define as feasible if the selfish chain can create two valid blocks faster than the honest chain with this combination of parameters. Figure 2 demonstrates an attack that is feasible with the tuple , but we want to find all such combinations of parameters with this property. As above, we use to denote the total time to create two blocks, for the honest and selfish networks respectively. Let be the difference in the selfish and honest times, i.e.,
An attack is feasible if which implies
PROOF: First, we can express in terms of , and using Equation 1, as
Similarly, we can express as
Now we solve for :
Now if , then the attack is feasible. Notice that is not a function of because both chains will always include all the endorsement operations for the slot.
Now we need to parameterize the reward functions. As above, we use to denote the reward for delegate playing honestly for the next two blocks, and to denote the reward for selfish endorsing over that same span. Further, let denote the difference in selfish and honest rewards, i.e.,
An attack is profitable if the amount of reward that receives playing selfishly is greater than that which they would receive playing honestly, or if . We are slightly abusing notation here, in that for the delay ( and ), the subscripts refer to the delay for versus the delay for the rest of the network. In the case of rewards, the subscripts both refer to delegate and correspond to selfish or honest behavior.
We express as a function of the tuple . In this case, does not depend on
PROOF: First we focus on the reward for behaving honestly. We must take into account the endorsement rewards and the block rewards for the next two blocks. Using Equation 2 and Equation 3, we define the total reward for honest behavior over the next two blocks as,
We categorize the rewards for the endorsements under the next slot because that is where they are included in a block. Similarly, we calculate the total reward for selfish behavior over the next two blocks as,
Now we solve for obtaining
Now if then an attack parameterized in this manner is profitable.
As a third step, we can calculate the probability of a tuple occurring randomly on the chain. Let denote the fraction of active rolls that owns. Given this, the probability of receiving any priority or endorsement for slot is Let be the random variable representing the number of consecutive slots not owned by 7 The distribution on being allocated each of the first priorities in slot is also a geometric random variable, but with probability , and denoted . Lastly, the distribution on being allocated endorsement rights for slot is a binomial random variable with 32 draws, denoted . Thus, we can calculate the probability of tuple given as
We can now calculate the probability of this family of length-2 attacks occurring. Let denote all tuples for which the attack is feasible (i.e., it creates two blocks faster than the honest network) and profitable (i.e., it has higher rewards than playing honestly). We have,
We also want to measure how profitable these attacks are. Let be the expected increase in reward of the attacks in (i.e., how much more profit the selfish behavior will generate than by playing honestly). We have,
Procedure 1 (in Appendix B) demonstrates these calculations, and the blue columns in Table 1 show the results of the analysis. Let represent the number of minutes in a year, so is the expected number of attacks per year and is the expected increase in value (in XTZ) for following the selfish policy for a year. This shows the attack is not a serious threat, given that even with 40% of the stake, is only expected to earn 254.94 XTC ( US $307.23 in November 2019) more than if they had played honestly for the year. Regardless, this is an example of how this type of attack could be formulated against a longest-chain PoS system.
The profit from the attack can be reduced by introducing a simple modification to the Emmy consensus protocol. Recall that in Emmy the endorsement reward defined in Equation 3 is a function of the priority of the block that includes the endorsement, denoted If the rewards for endorsements are switched to being a function of the block that they endorse, denoted the attacks occur less frequently.
The green columns in Table 1 represent the probability and value of the attack at different levels of after this fix, and the % column reports the improvement over the status quo. Recall that represents the fraction of active rolls that are owned by The only exception to this reduction is the case of where we observe that both the probability and the value of the attacks rise as a result of the suggested change. Since the expected increase in value of 0.21 XTZ over a year is effectively no increase in profit, the fix still seems reasonable. See the caption of Table 1 for more discussion.
The values of the green columns in Table 1 were calculated using Procedure 1 in Appendix B, but with the reward function presented in Lemma 4.1. We defer the proof of this lemma to the Appendix because it is similar to Lemma 3.2.
If the endorsement rewards are instead a function of the block that they endorse, , then .
PROOF: See Appendix A.
This is not a security proof, but rather a heuristic change that decreases the probability and profitability of selfish endorsing for most values of
In this section, we present modifications to both the delay and reward functions that would make the PoS protocol provably secure against a specific attack vector (in this case, length-1 and length-2 selfish endorsing). In contrast to the heuristic fix in Section 4, we change the validity-time and reward functions, as opposed to simply switching which block is used to calculate endorsement rewards.8 In practice, creating a fully secure PoS protocol is not as simple as implementing these functions, because there are other long-range forking attacks that must be taken into account. If the delay for each drop in baker priority is too large, then the honest network is slowed dramatically, which allows for an attacker to have more time to create a longer private chain.
Let be the new delay function for a block being valid, which is a function of the priority of the baker, and the number of endorsements it includes, We define this as,
Relative to Emmy the new component is the amount of time added for each drop in priority of the baker. In Emmy this value is 40, while in this revised expression it is 193. This delay function was constructed to ensure that the highest priority block can always be published before the second highest priority (see Lemma 5.2). This is because given the following reward functions, length-1 block stealing attacks are profitable in some cases (they are not profitable in Emmy because of Lemma 5.1), so in order to insure they do not occur, the delay function ensures that they are never feasible.
Let be the modified reward function for a block baked with priority and including endorsements. It maintains an 80 XTZ per block inflation rate, but splits the rewards 40/40 between the baker and the endorsers:
Let denote the reward for an endorsement that is included in a block baked with priority We have,
We see that if a block is baked with priority 0 and all 32 endorsements are included from the previous block, then the total reward for the block becomes XTZ.
In Section 5.1, we prove that length-1 selfish endorsing attacks are not feasible under this new delay schedule. In Section 5.2, we prove that length-2 selfish endorsing attacks are not profitable under this new reward protocol.
Lemma 5.1 establishes a useful result. It explains why we have not needed to consider single-block selfish endorsing attacks until this point.
For any tuple , the length-1 selfish endorsing attack is not profitable under Emmy
PROOF: See Appendix C.
What about the new delay schedule (Equation 19)? In fact, we show that a length-1 selfish endorsing attack is never even feasible. Assuming the honest network has the highest priority baking rights, let be the time for the honest network to create a single block under the new delay function, and be the time for the selfish delegate to create a single block.
Under the modified PoS protocol, for any tuple , we have .
PROOF: In the worst case, the honest network will not receive any endorsements, so the slowest the block creation could be is,
In the best case for the attacker, they will own all 32 endorsements, and a priority of 1 ( best) in the block, and
Putting this together, we have
We now turn to length-2 selfish endorsing attacks, and will establish that they are never profitable under the modified protocol. We first need a closed-form representation of the rewards would receive under the new reward function, denoted and for playing honestly and selfishly, respectively. The derivation of Lemma 5.3 is similar to Lemma 3.2, and deferred to Appendix D.
Under the modified PoS protocol, the total reward for a rational delegate playing honestly over the next two blocks with the tuple is
and the total reward for to play selfishly over the next two blocks is
PROOF: See Appendix D.
We now prove that length-2 selfish endorsing under this reward system is never profitable.
Under the modified PoS protocol, for any tuples , we have .
PROOF: Assume for contradiction that and so
Collecting terms and simplifying, this is equivalent to
Because we have
This along with the fact that implies
Substituting this into (Equation 28) implies that we would need for profitability, which is a contradiction since .
This is a useful result in the context of defending against length-1 and length-2 selfish endorsing. And yet, this modification actually weakens the PoS system against longer forking attacks. This is because, under the modified delay schedule, the time penalty for each drop in priority is so large that an attacker with a couple first priorities in the coming slots could withhold their blocks, and during the intermediate time work on creating a longer chain, while the honest nodes have to wait 193 extra seconds each time the attack has the priority. The last section of the analysis of Emmy provided by Nomadic Labs discusses these kinds of trade-offs, and how the exact constants were selected for Emmy [20].
We have demonstrated that live PoS systems can be formally analyzed for their incentive vulnerabilities. Our analysis of Tezos also serves as a real-world example of the predictable selfish mining attack that was theorized by Brown-Cohen et al. [19]. At the same time, we recognize that, as of November 2019, length-2 selfish endorsing attacks do not seem to be a major threat to the Tezos network because the profit from executing such an attack is so low. However, we have also suggested a simple, heuristic fix that would reduce the probability and value of many of the attacks by an order of magnitude. We have further presented a modified delay schedule and reward function that is provably secure against length-1 and length-2 selfish endorsing (though we acknowledge that, in practice, other attack vectors must also be considered when implementing these protocols).
By no means have we provided a complete security analysis of the Tezos protocol. Future work combining selfish endorsing with other deviating strategies, as was done in the PoW literature [17][18], is critical to assessing the total security of the system. The formal framework introduced in our work can be used to check other PoS protocols for potential vulnerabilities to selfish behavior by parameterizing a model of time and reward with respect to a specific protocol. In fact, a new reward scheme was recently proposed by the Nomadic Labs developers under the name Carthage [24], and this framework can be applied directly to the new delay and reward functions. Nomadic Labs provides an analysis of the effect of this reward scheme on a few different off-protocol strategies, including the selfish endorsing attack [25].
We hope that our work serves as a starting point for analyses and a more formal treatment of the security properties of PoS systems. For immediate future directions, the first is to develop a theory of profitable selfish-endorsing attacks beyond length-2. This is non-trivial because the technique described in Appendix B scales exponentially due to the Cartesian product of each of the state variables. The second direction is to consider a more general forking attack that, on its own, would earn a smaller staking reward relative to honest behavior, but allow for an attacker to include a double-spend transaction.9 Additionally, more analysis needs to be done in regard to modeling the presence of multiple selfish delegates, which also remains an active area of research in the Bitcoin PoW literature [26][27].
The authors would like to thank Eugen Zalinescu and Arthur Breitman for helpful discussions and for proposing new reward schemes to analyze. Additional thanks are due to Dan Robinson and the two anonymous reviewers for helpful comments as we prepared the manuscript for the 2020 Cryptoeconomic Systems Conference. This work is supported in part by two generous gifts to the Center for Research on Computation and Society at Harvard University, both to support research on applied cryptography and society. Daniel J. Moroz was also supported in part by the Ethereum Foundation.
PROOF: First we focus on the reward for behaving honestly. We must take into account the endorsement rewards and the block rewards for the next two blocks. We define the total reward for honest behavior over the next two blocks as
Similarly we calculate the rewards while following the selfish endorsing policy as
Now we can solve for :
This procedure is used to calculate the total probability and value of a length-2 selfish endorsing attack. Note that is the Cartesian Product of lists.
For any tuple , the length-1 selfish endorsing attack is not profitable under Emmy
PROOF: First we consider the time it takes the honest network to produce a single block at height Denote this value We have,
Now we find the time it takes for the selfish delegate to create a block, We have,
The best case scenario for the attacker is when and for this we have
Now we find the number of endorsements required for the selfish delegate to produce a valid block faster than the honest network to be We verify this with the following calculations:
Now we know that is the best case scenario for the attack being feasible. If then the selfish network will not be able to create a block fast enough, and if then the reward will be lower because additional endorsements will end up on the lower priority stolen block. Additionally, we know that the reward for playing honestly is because we will get all the endorsement rewards, and the reward for playing selfishly is,
Plugging in we have
We see that even for the smallest value of that makes the attack feasible, the profit gained from creating a new block does not outweigh the profit lost as a result of the endorsements ending up on a worse block. So because a single block selfish endorsing attack is not profitable under Emmy
Under the modified PoS protocol, the total reward for a rational delegate playing honestly over the next two blocks with the tuple is
and the total reward for to play selfishly over the next two blocks is