Skip to main content

Selfish Behavior in the Tezos Proof-of-Stake Protocol

Published onApr 05, 2021
Selfish Behavior in the Tezos Proof-of-Stake Protocol
·

Abstract

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.

1. Introduction

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+\text{}^+ [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.

2. Proof-of-Stake in Tezos

2.1 The Basics

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.

Figure 1: Let (Rb(p,e))(\mathcal{R}_b(p, e)) be as defined in Equation 2 and let Re(p)\mathcal{R}_e(p) be as defined in Equation 3. In this scenario, block \ell will earn the baker a reward of Rb(1,32)=8XTZ,\mathcal{R}_b (1, 32) = 8 XTZ, and block +1\ell +1 will earn the baker Rb(0,31)=15.9XTZ.\mathcal{R}_b (0, 31) = 15.9 XTZ. The endorsements for slot 1\ell -1 will each earn Re(1)=1XTZ\mathcal{R}_e (1) = 1 XTZ and the endorsements for slot \ell will each earn Re(0)=2XTZ.\mathcal{R}_e (0) = 2 XTZ. Notice that the slot \ell endorsements still get the full reward when signing a lower priority block, simply because they are included in the 0th priority block at the +1\ell + 1 slot. Before the Emmy+^+ upgrade the slot \ell endorsements would only earn 1XTZ1XTZ each.

2.2 The Babylon Upgrade and Emmy+^+

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 D\mathcal{D} seconds, where D\mathcal{D} defines the validity-time and is the following function of the baker’s priority, p,p, and the number of endorsements included in the block, ee (see Minimal block delays in [11]):

D(p,e)=60+40p+8max(24e),0).\mathcal{D}(p,e) = 60 + 40p + 8max(24 - e), 0). (1)

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 0th0^{th} 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, p,p, and the number of endorsements ee for the previous block that are included in this block (see Rewards in [11]). Let Rb\mathcal{R}_{b} be the baking reward. In Emmy+^+, we have

Rb(p,e)=16p+1(45+15e32).\begin{aligned} \mathcal{R}_{b}(p, e) &= \frac{16}{p+1} \left(\frac{4}{5} + \frac{1}{5} \cdot \frac{e}{32}\right). % \label{rewardblock} \end{aligned}(2)

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 pi.p_i. Then the endorsing reward, Re\mathcal{R}_{e}, is calculated as

Re(pi)=2pi+1.\begin{aligned} \mathcal{R}_{e}(p_i) &= \frac{2}{p_i +1}. %\label{rewardendorse} \end{aligned}(3)

Figure 1 illustrates the rewards that the bakers and endorsers earn under the Emmy+^+ rules.

3. The Selfish Endorsing Attack

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 X\mathcal{X} 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 nn from the genesis block occupies the nthn^{th} slot). In the Emmy+^+ implementation, delegates see exactly who will have baking and endorsing rights for the next several thousand (5×4096\approx 5 \times 4096) blocks. For a given slot ,\ell, let pp_\ell be the highest priority and ee_\ell the number of endorsement rights that X\mathcal{X} is randomly allocated. Priorities are zero-indexed, with 0 being the highest. Additionally, let n+1n_{\ell+1} denote the number of consecutive top baking priorities given to X\mathcal{X} at slot +1\ell+1 (e.g., if the baking priority list for the +1\ell+1 slot is [X,X,other,X,...][\mathcal{X}, \mathcal{X}, \texttt{other}, \mathcal{X}, ...], then p+1=0 and n+1=2p_{\ell+1} = 0 \text{ and } n_{\ell+1}=2).

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.

3.1 An Illustrative Attack on Emmy+^+

Figure 2 shows that an attacker X\mathcal{X} with second priority (p=1p_\ell =1) at slot \ell can bake a block that will end up on the final chain despite the first-priority (p=0)(p_\ell =0) delegate publishing on time. This is malicious because the baker with the lower priority stole the block reward from the highest priority baker.

Figure 2: Let pp_\ell be the highest priority allocated to the attacker at slot \ell, and n+1n_{\ell+1} be the number of consecutive top priorities allocated to the attacker at slot +1.\ell + 1. Additionally, let ee_{\ell} be the number of endorsement rights that the attacker owns at slot .\ell. This figure illustrates the selfish endorsing attack with e1=2e_{\ell-1} = 2, e=14e_{\ell} = 14, p=1,p_{\ell} = 1, and n+1=2.n_{\ell+1} = 2. The top and bottom forks show the next two blocks for the honest and selfish chains respectively. Each block shows the priority of the baker who created it, p,p, and the number of endorsements that it includes, e.e. Note that ee is not the number of endorsements that this block receives, but rather the number of endorsements for the block baked in the previous slot that it includes, thus both blocks created at slot \ell have e=32e = 32 because they both include all 32 endorsements of the block baked at slot 1.\ell - 1. The empty blocks labelled A,A, B,B, and CC correspond to timestamps when the honest network would expect the second block to appear. AA and BB are empty because X\mathcal{X} holds the top two priorities for slot +1.\ell + 1. CC is empty because the baker with priority 2 for slot +1\ell + 1 is missing X\mathcal{X} ‘s 14 endorsements from slot ,\ell, which incurs a 48 second penalty.

Delegate X\mathcal{X} 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 Dh\mathcal{D}_h and Ds\mathcal{D}_s be the total time to create two blocks for the honest and selfish chains, respectively. We have,

Dh=D(0,32)+D(2,18)=248\begin{aligned} \mathcal{D}_h &= \mathcal{D}(0, 32) + \mathcal{D}(2, 18) = 248 \\ \end{aligned}(4)
Ds=D(1,32)+D(0,14)=240\begin{aligned} \mathcal{D}_s &= \mathcal{D}(1, 32) + \mathcal{D}(0, 14) = 240 \end{aligned}(5)

The combination of having a large share of endorsements for slot \ell and the two highest priorities for slot +1\ell+1 allows X\mathcal{X} to slow down the honest network by only endorsing a private block at slot .\ell. Attacker X\mathcal{X} 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 Rh\mathcal{R}_{h} denote the total reward earned by X\mathcal{X} over the next two blocks while behaving honestly. The labels underneath the expressions indicate the reason each reward is added. We have

Rh=2Re(0)e1=2+14Re(0)e=14+Rb(0,32)p+1=0\begin{aligned} \mathcal{R}_{h} &= \underbrace{2 \mathcal{R}_{e}(0)}_{e_{\ell-1}=2} + \underbrace{14 \mathcal{R}_{e}(0)}_{e_{\ell}=14} + \underbrace{\mathcal{R}_{b} (0, 32)}_{p_{\ell+1}=0} \end{aligned}
=4+28+16=48.\begin{aligned} &= 4 + 28 + 16 = 48.\end{aligned}(6)

Similarly we can calculate the total rewards that the attacker X\mathcal{X} earns while selfishly endorsing, denoted Rs.\mathcal{R}_{s}. We have

Rs=2Re(1)e1=2+14Re(0)e=14+Rb(1,32)p=1+Rb(0,14)p+1=0&e=14\begin{aligned} \mathcal{R}_{s} &= \underbrace{2 \mathcal{R}_{e}(1)}_{e_{\ell-1}=2} + \underbrace{14 \mathcal{R}_{e}(0)}_{e_{\ell}=14} + \underbrace{\mathcal{R}_{b}(1, 32)}_{p_\ell = 1} + \underbrace{\mathcal{R}_{b}(0, 14)}_{p_{\ell+1}=0 \And e_{\ell}=14} \end{aligned}
=2+28+8+14.2=52.2.\begin{aligned} &= 2 + 28 + 8 + 14.2= 52.2.\end{aligned}(7)

This demonstrates that the gain in reward from creating a new block at slot \ell outweighs the loss in reward from the endorsements on slot 1\ell-1 ending up on a lower priority block. Critically, the rewards for the 14 endorsements for slot \ell (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 X\mathcal{X} at slot +1,\ell+1, 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.

3.2 Feasibility

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 t=(e1,e,p,n+1)t = (e_{\ell-1}, \: e_\ell,\: p_\ell,\: n_{\ell+1}). We define tt 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 t0=(e1=2,e=14,p=1,n+1=2)t_0 = (e_{\ell-1}=2,\: e_\ell=14, \: p_\ell=1, \: n_{\ell+1}=2), but we want to find all such combinations of parameters with this property. As above, we use Dh and Ds\mathcal{D}_h \text{ and } \mathcal{D}_s to denote the total time to create two blocks, for the honest and selfish networks respectively. Let D2\mathcal{D}_2 be the difference in the selfish and honest times, i.e.,

D2=DsDh.\begin{aligned} \mathcal{D}_2 = \mathcal{D}_s - \mathcal{D}_h. \end{aligned}(8)

An attack is feasible if Ds<Dh,\mathcal{D}_s < \mathcal{D}_h, which implies D2<0.\mathcal{D}_2 < 0.

Lemma 3.1 D2(p,e,n+1)=40(pn+1)+8max(24e,0)8max(e8,0).\mathcal{D}_2(p_\ell, e_{\ell}, n_{\ell+1}) = 40 (p_\ell - n_{\ell+1}) + 8 \max(24 - e_\ell, 0) - 8 \max(e_\ell -8, 0).

PROOF: First, we can express Dh\mathcal{D}_h in terms of e,pe_\ell, p_\ell, and n+1n_{\ell+1} using Equation 1, as

Dh(p,e,n+1)=60D(0,32)+60+40n+1D(n+1,32e)+8max(24(32e),0)D(n+1,32e)\begin{aligned} \mathcal{D}_h(p_\ell, e_\ell, n_{\ell+1}) ={}& \underbrace{60}_{\mathcal{D}(0, 32)} + \underbrace{60 + 40 n_{\ell+1}}_{\mathcal{D}(n_{\ell+1}, 32-e_\ell)} \\ \quad{}&+ \underbrace{8 \max(24 - (32-e_\ell), 0)}_{\mathcal{D}(n_{\ell+1}, 32-e_\ell)} \\ \end{aligned}
=120+40n+1+8max(e8,0). =120 + 40 n_{\ell+1} + 8 \max(e_\ell - 8, 0).(9)

Similarly, we can express Ds\mathcal{D}_s as

Ds(p,e,n+1)=60+40pD(p,32)+60+8max(24e,0)D(0,e)\begin{aligned} \mathcal{D}_s(p_\ell, e_\ell, n_{\ell+1}) &= \underbrace{60 + 40 p_\ell}_{\mathcal{D}(p_\ell, 32)} + \underbrace{60 + 8 \max(24-e_\ell, 0)}_{\mathcal{D}(0, e_\ell)} \\ \end{aligned}
=120+40p+8max(24e,0).= 120 + 40 p_\ell + 8 \max(24 - e_\ell, 0).(10)

Now we solve for D2\mathcal{D}_2:

D2(p,e,n+1)=Ds(p,e,n+1)Dh(p,e,n+1)=120+40p+8max(24e,0)[120+40n+1+8max(e8,0)]=40(pn+1)+8max(24e,0)\begin{aligned} %\begin{split} \mathcal{D}_2(p_\ell, e_\ell, n_{\ell+1}) ={}& \mathcal{D}_s(p_\ell, e_\ell, n_{\ell+1}) - \mathcal{D}_h(p_\ell, e_\ell, n_{\ell+1}) \\ ={}& 120 + 40 p_\ell + 8 \max(24 - e_\ell, 0) \\ \quad{}&- \left[120 + 40 n_{\ell+1} + 8 \max(e_\ell - 8, 0) \right] \\ ={}& 40 (p_\ell - n_{\ell+1}) + 8 \max(24 - e_\ell, 0) \\ %\end{split} \end{aligned}
8max(e8,0).- 8 \max(e_\ell -8, 0).(11)

Now if D2<0\mathcal{D}_2<0, then the attack is feasible. Notice that D2\mathcal{D}_2 is not a function of e1e_{\ell-1} because both chains will always include all the endorsement operations for the n1n-1 slot.

3.3 Profitability

Now we need to parameterize the reward functions. As above, we use Rh\mathcal{R}_{h} to denote the reward for delegate X\mathcal{X} playing honestly for the next two blocks, and Rs\mathcal{R}_{s} to denote the reward for selfish endorsing over that same span. Further, let R2\mathcal{R}_{2} denote the difference in selfish and honest rewards, i.e.,

R2=RsRh.\begin{aligned} \mathcal{R}_{2} &= \mathcal{R}_{s} - \mathcal{R}_{h}. \end{aligned}(12)

An attack is profitable if the amount of reward that X\mathcal{X} receives playing selfishly is greater than that which they would receive playing honestly, or if R2>0\mathcal{R}_{2} > 0. We are slightly abusing notation here, in that for the delay (Ds\mathcal{D}_s and Dh\mathcal{D}_h), the subscripts s and hs \text{ and } h refer to the delay for X\mathcal{X} versus the delay for the rest of the network. In the case of rewards, the subscripts both refer to delegate X\mathcal{X} and correspond to selfish or honest behavior.

We express R2\mathcal{R}_{2} as a function of the tuple t=(e1,e,p,n+1)t = (e_{\ell-1}, e_\ell, p_\ell, n_{\ell+1}). In this case, R2\mathcal{R}_{2} does not depend on n+1.n_{\ell+1}.

Lemma 3.2
R2(p,e1,e)=16 ⁣(1p+1+e16015)+2e1 ⁣(1p+11).\mathcal{R}_{2}(p_\ell, e_{\ell-1}, e_\ell) = 16 \!\left(\frac{1}{p_\ell +1} + \frac{e_\ell}{160} - \frac{1}{5} \right) + 2e_{\ell-1} \!\left( \frac{1}{ p_\ell+1} - 1\right).

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,

Rh(e1,e)=e1Re(0)slot  rewards+eRe(0)+Rb(0,32)slot +1 rewards\begin{aligned} \mathcal{R}_{h}(e_{\ell-1}, e_\ell) &= \underbrace{e_{\ell-1} \cdot \mathcal{R}_{e}(0)}_{\texttt{slot } \ell \texttt{ rewards}} + \underbrace{e_\ell \cdot \mathcal{R}_{e}(0) + \mathcal{R}_{b} (0, 32)}_{\texttt{slot } \ell +1\texttt{ rewards}} \\ \end{aligned}
=2e1+2e+16=2(e1+e)+16.= 2e_{\ell-1} + 2 e_\ell + 16 = 2 (e_{\ell-1} + e_\ell) + 16.(13)

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,

Rs(e1,e,p)=e1Re(p)+Rb(p,32)slot  rewards+eRe(0)+Rb(0,e)slot +1 rewards=2p+1e1+16p+1+2e+16(45+15e32)\begin{aligned} \mathcal{R}_{s}(&e_{\ell-1}, e_\ell, p_\ell) ={} \underbrace{e_{\ell-1} \cdot \mathcal{R}_{e}(p_\ell) + \mathcal{R}_{b}(p_\ell, 32)}_{\texttt{slot } \ell \texttt{ rewards}} \\ & \quad \quad \quad \quad \quad \quad + \underbrace{e_\ell \cdot \mathcal{R}_{e}(0) + \mathcal{R}_{b}(0, e_\ell)}_{\texttt{slot } \ell +1 \texttt{ rewards}} \\ ={}& \frac{2}{p_\ell +1} e_{\ell-1} + \frac{16}{p_\ell+1} + 2 e_\ell + 16 \left(\frac{4}{5} + \frac{1}{5} \cdot \frac{e_\ell}{32}\right) \\ \end{aligned}
=2(e1p+1+e)+16(1p+1+45+e160). =2 \left( \frac{e_{\ell-1}}{p_\ell +1} + e_\ell \right) + 16 \left(\frac{1}{p_\ell+ 1} + \frac{4}{5} + \frac{e_\ell}{160} \right).(14)

Now we solve for R2,\mathcal{R}_{2}, obtaining

R2(e1,e,p)=Rs(e1,e,p)Rh(e1,e)=2(e1p+1+ee1e)+16(1p+1+45+e1601)\begin{aligned} & \mathcal{R}_{2} (e_{\ell-1}, e_\ell, p_\ell) ={} \mathcal{R}_{s}(e_{\ell-1}, e_\ell, p_\ell) - \mathcal{R}_{h}(e_{\ell-1}, e_\ell) \\ ={}& 2 \left( \frac{e_{\ell-1}}{p_\ell +1} + e_\ell - e_{\ell-1} - e_\ell \right) \\ \quad{}&+ 16 \left(\frac{1}{p_\ell+ 1} + \frac{4}{5} + \frac{e_\ell}{160} - 1\right) \\ \end{aligned}
=2e1(1p+11)+16(1p+1+e16015).= 2e_{\ell-1} \left( \frac{1}{p_\ell + 1} - 1\right) + 16 \left(\frac{1}{p_\ell+1} + \frac{e_\ell}{160} - \frac{1}{5} \right).(15)

Now if R2>0,\mathcal{R}_{2} > 0, then an attack parameterized in this manner is profitable.

3.4 Probability

As a third step, we can calculate the probability of a tuple t=(e1,e,p,n+1)t = (e_{\ell-1}, e_\ell, p_\ell, n_{\ell+1}) occurring randomly on the chain. Let α\alpha denote the fraction of active rolls that X\mathcal{X} owns. Given this, the probability of X\mathcal{X} receiving any priority or endorsement for slot \ell is α.\alpha. Let PGeometric(α)\mathcal{P} \sim \text{Geometric}(\alpha) be the random variable representing the number of consecutive slots not owned by X.\mathcal{X}.7 The distribution on X\mathcal{X} being allocated each of the first nn priorities in slot +1\ell+1 is also a geometric random variable, but with probability (1α)(1-\alpha), and denoted NGeometric(1α)\mathcal{N} \sim \text{Geometric}(1-\alpha). Lastly, the distribution on X\mathcal{X} being allocated ee_\ell endorsement rights for slot \ell is a binomial random variable with 32 draws, denoted EBinomial(32,α)\mathcal{E} \sim \text{Binomial}(32, \alpha). Thus, we can calculate the probability of tuple t=(e1,e,p,n+1)t= (e_{\ell-1}, e_\ell, p_\ell, n_{\ell+1}) given α,\alpha, as

Pr[tα]=(1α)pαPr[P=p]×αn+1(1α)Pr[N=n+1]×(32e1)αe1(1α)32e1Pr[E=e1]×(32e)αe(1α)32ePr[E=e]\begin{aligned} & \mathrm{Pr} [ \, t \: | \: \alpha \,] ={} \underbrace{(1 - \alpha)^{p_\ell}\alpha}_{\mathrm{Pr}[\mathcal{P} = p_\ell]} \times \underbrace{\alpha^{n_{\ell+1}} (1 - \alpha)}_{\mathrm{Pr}[\mathcal{N} = n_{\ell+1}]} \\ \quad{}&\times \underbrace{ \binom{32}{e_{\ell-1}} \alpha^{e_{\ell-1}} (1-\alpha)^{32-e_{\ell-1}}}_{\mathrm{Pr}[\mathcal{E} = e_{\ell-1}]} \times\underbrace{\binom{32}{e_{\ell}} \alpha^{e_{\ell}}(1-\alpha)^{32-e_{\ell}}}_{\mathrm{Pr}[\mathcal{E} = e_\ell]} \\ \end{aligned}
=(32e1)(32e)αn+1+e1+e+1(1α)65+pe1e. = \binom{32}{e_{\ell-1}} \cdot \binom{32}{e_{\ell}} \cdot \alpha^{n_{\ell+1} + e_{\ell-1} + e_\ell + 1}\cdot(1 - \alpha)^{65 +p_\ell - e_{\ell-1} - e_{\ell}}.(16)

3.5 Generalizing

We can now calculate the probability of this family of length-2 attacks occurring. Let A2\mathcal{A}_2 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,

A2={(e1,e,p,n+1)D2<0R2>0}.\begin{aligned} \mathcal{A}_2 &= %\{(e_{\ell-1}, e_\ell, p_\ell, n_{\ell+1}) \: | \: \mathcal{D}_s < \mathcal{D}_h \: \land \: \mathcal{R}_{h} < \mathcal{R}_{s} \} \\ %&= \{(e_{\ell-1}, e_\ell, p_\ell, n_{\ell+1}) \: | \: \mathcal{D}_2 < 0 \: \land \: \mathcal{R}_{2} > 0 \}. \end{aligned}(17)

We also want to measure how profitable these attacks are. Let V2\mathcal{V}_2 be the expected increase in reward of the attacks in A2\mathcal{A}_2 (i.e., how much more profit the selfish behavior will generate than by playing honestly). We have,

V2=tA2Pr[tα](Rs(t)Rh(t)).\begin{aligned} \mathcal{V}_2 &= \sum_{t \in \mathcal{A}_2} \mathrm{Pr} [ \, t \: | \: \alpha \,] (\mathcal{R}_{s} (t) - \mathcal{R}_{h}(t)). \end{aligned}(18)

Procedure 1 (in Appendix B) demonstrates these calculations, and the blue columns in Table 1 show the results of the analysis. Let C=3652460\mathcal{C} = 365 \cdot 24 \cdot 60 represent the number of minutes in a year, so CPr[A2]\mathcal{C} \cdot \mathrm{Pr}[\mathcal{A}_2] is the expected number of attacks per year and CV2\mathcal{C} \cdot \mathcal{V}_2 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, X\mathcal{X} is only expected to earn 254.94 XTC (\approx 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.

Table 1: Let α\alpha be the percentage of rolls that the attacker owns, and let C=3652460C = 365 · 24 · 60 be the number of minutes in a year. Then CPr[A2]C·Pr[A_2] represents the number of times the attack will be feasible and profitable over the course of a year, and CV2C·V_2 will be the additional profit over honest behavior that the attacker makes in a year. The light blue cells represent the results under the current implementation and the green cells represent the results after our heuristic fix (described in Section 4) is applied. The % column shows the respective ratio of the green column to the blue column (e.g., 1% means that after the fix, the value of the attack is 1% of what it is currently). A subtle feature of these results is that the probability of an attack being profitable and feasible is not monotone increasing with respect to α.\alpha. This is due to the fact that the endorsements owned by the attacker for the 1\ell - 1 slot will end up on a lower priority block and thus be worth less in the case of an attack. As a result, the more endorsement slots owned by the attacker at 1,\ell - 1, the less profit they stand to gain by stealing the block. We see that there is a balance between having a large enough α\alpha to make the attack feasible, but not too large as to have a high probability of having many endorsement rights. We numerically calculated that an attacker makes the most profit when α=0.351.\alpha = 0.351.

4. A Heuristic Fix to Emmy+^+

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 pi.p_i. If the rewards for endorsements are switched to being a function of the block that they endorse, denoted pe,p_e, the attacks occur less frequently.

The green columns in Table 1 represent the probability and value of the attack at different levels of α\alpha after this fix, and the % column reports the improvement over the status quo. Recall that α\alpha represents the fraction of active rolls that are owned by X.\mathcal{X}. The only exception to this reduction is the case of α=0.1,\alpha=0.1, 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 $0.25\approx \$0.25 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.

Lemma 4.1

If the endorsement rewards Re\mathcal{R}_{e} are instead a function of the block that they endorse, pep_e, then R2(p,e1,e)=16(1p+1+e16015)+2e(1p+11)\mathcal{R}_{2}(p_\ell, e_{\ell-1}, e_\ell) = 16 \cdot \left(\frac{1}{p_\ell +1} + \frac{e_\ell}{160} - \frac{1}{5} \right) + 2e_{\ell} \left( \frac{1}{ p_\ell+1} - 1\right).

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 α.\alpha.

5. Alternative Fix: New Delay and Reward Functions

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 D\mathcal{D}' be the new delay function for a block being valid, which is a function of the priority of the baker, p,p, and the number of endorsements it includes, e.e. We define this as,

D(p,e)=60+193p+8max(24e,0).\begin{aligned} %\label{eq:newdelay} \mathcal{D}'(p, e) &= 60 + 193 p + 8 \max(24-e,0). \end{aligned}(19)

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 D\mathcal{D}' 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 Rb\mathcal{R}_{b}' be the modified reward function for a block baked with priority p,p, and including ee endorsements. It maintains an 80 XTZ per block inflation rate, but splits the rewards 40/40 between the baker and the endorsers:

Rb(p,e)=54ep+1\begin{aligned} %\label{newrewardblock} \mathcal{R}_{b}'(p, e) = \frac{5}{4} \cdot \frac{e}{p+1} \end{aligned}(20)

Let Re(pi)\mathcal{R}_{e}'(p_i) denote the reward for an endorsement that is included in a block baked with priority pi.p_i. We have,

Re(pi)=541pi+1\begin{aligned} %\label{newrewardendorse} \mathcal{R}_{e}'(p_i) = \frac{5}{4} \cdot \frac{1}{p_i+1} \end{aligned}(21)

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 Rb(0,32)+32Re(0)=40+40=80\mathcal{R}_{b}'(0,32) + 32 \mathcal{R}_{e}'(0) = 40 + 40 = 80 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.

5.1 Security Against Length-1 Attacks

Lemma 5.1 establishes a useful result. It explains why we have not needed to consider single-block selfish endorsing attacks until this point.

Lemma 5.1

For any tuple (e1,p)(e_{\ell-1}, p_\ell), 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 Dh,1\mathcal{D}'_{h,1} be the time for the honest network to create a single block under the new delay function, and Ds,1\mathcal{D}'_{s,1} be the time for the selfish delegate to create a single block.

Lemma 5.2

Under the modified PoS protocol, for any tuple (e1,p)(e_{\ell-1}, p_\ell), we have Dh,1(p,e1)<Ds,1(p,e1)\mathcal{D}'_{h,1}(p_\ell, e_{\ell-1}) < \mathcal{D}'_{s,1}(p_\ell, e_{\ell-1}).

PROOF: In the worst case, the honest network will not receive any endorsements, so the slowest the block creation could be is,

Dh,1(p,e1)Dh,1(0,0)=60+824252.\begin{aligned} \mathcal{D}'_{h,1}(p_\ell, e_{\ell-1}) &\leq \mathcal{D}'_{h,1}(0, 0) = 60 + 8 \cdot 24 \leq 252. \end{aligned}(22)

In the best case for the attacker, they will own all 32 endorsements, and a priority of 1 (2nd2^{nd} best) in the block, and

Ds,1(p,e1)Ds,1(1,32)=60+193=253.\begin{aligned} \mathcal{D}'_{s,1}(p_\ell, e_{\ell-1}) &\geq \mathcal{D}'_{s,1}(1, 32) = 60 + 193 = 253. \end{aligned}(23)

Putting this together, we have

Dh,1252<253Ds,1  Dh,1<Ds,1.\begin{aligned} \mathcal{D}'_{h,1} \leq 252 < 253 \leq \mathcal{D}'_{s,1}\ \Rightarrow \ \mathcal{D}'_{h,1} < \mathcal{D}'_{s,1}. \end{aligned}(24)

5.2 Security Against Length-2 Attacks

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 X\mathcal{X} would receive under the new reward function, denoted Rh\mathcal{R}'_{h} and Rs\mathcal{R}'_{s} for playing honestly and selfishly, respectively. The derivation of Lemma 5.3 is similar to Lemma 3.2, and deferred to Appendix D.

Lemma 5.3

Under the modified PoS protocol, the total reward for a rational delegate X\mathcal{X} playing honestly over the next two blocks with the tuple (e1,e,p)(e_{\ell-1}, e_\ell, p_\ell) is

Rh(e1,e)=1.25(e1+e+32),\begin{aligned} \mathcal{R}'_{h}(e_{\ell-1}, e_\ell) &= 1.25 (e_{\ell-1} + e_\ell + 32), \end{aligned}(25)

and the total reward for X\mathcal{X} to play selfishly over the next two blocks is

Rs(e1,e,p)=2.5(e1p+1+e).\begin{aligned} \mathcal{R}'_{s}(e_{\ell-1}, e_\ell, p_\ell) &= 2.5 \left( \frac{e_{\ell-1}}{p_\ell+1} + e_\ell\right). \end{aligned}(26)

PROOF: See Appendix D.

We now prove that length-2 selfish endorsing under this reward system is never profitable.

Lemma 5.4

Under the modified PoS protocol, for any tuples (e1,e,p)(e_{\ell-1}, e_\ell, p_\ell), we have Rs(e1,e,p)Rh(e1,e)\mathcal{R}_{s}'(e_{\ell-1}, e_\ell, p_\ell) \leq \mathcal{R}_{h}'(e_{\ell-1}, e_\ell).

PROOF: Assume for contradiction that Rs>Rh,\mathcal{R}_{s}' > \mathcal{R}_{h}', and so

2.5(e1p+1+e)>1.25(e1+e+32).\begin{aligned} 2.5 \left( \frac{e_{\ell-1}}{p_\ell+1} + e_\ell\right) &> 1.25 (e_{\ell-1} + e_\ell + 32). \end{aligned}(27)

Collecting terms and simplifying, this is equivalent to

e1(1pp+1)+e>32.\begin{aligned} %\label{eq:simple} e_{\ell-1} \left( \frac{1 - p_\ell}{p_\ell+1}\right) + e_\ell &> 32. \end{aligned}(28)

Because p1,p_\ell \geq 1, we have

1pp+10.\begin{aligned} \frac{1 - p_\ell}{p_\ell+1} \leq 0. \end{aligned}(29)

This along with the fact that e10e_{\ell-1} \geq 0 implies

e1(1pp+1)0.\begin{aligned} e_{\ell-1} \left( \frac{1 - p_\ell}{p_\ell+1}\right) \leq 0. \end{aligned}

Substituting this into (Equation 28) implies that we would need e>32e_\ell > 32 for profitability, which is a contradiction since e{0,1,...,32}e_\ell \in \{0, 1, ..., 32\}.

5.3 Discussion

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 0th0^{th} 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].

6. Conclusion

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].

Acknowledgments

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.

Appendix

A. Proof of Lemma 4.1

Lemma A.1.
R2(p,e1,e)=16(1p+1+e16015)+2e(1p+11)\mathcal{R}_{2}(p_\ell, e_{\ell-1}, e_\ell) = 16 \left(\frac{1}{p_\ell +1} + \frac{e_\ell}{160} - \frac{1}{5} \right) + 2e_{\ell} \left( \frac{1}{ p_\ell+1} - 1\right)

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

Rh(e1,e)=e1Re(0)slot 1 rewards+eRe(0)slot  rewards+Rb(0,32)slot +1 rewards\begin{aligned} \mathcal{R}_{h}(e_{\ell-1}, e_\ell) &= \underbrace{e_{\ell-1} \cdot \mathcal{R}_{e}(0)}_{\texttt{slot } \ell -1 \texttt{ rewards}} + \underbrace{e_\ell \cdot \mathcal{R}_{e}(0) }_{\texttt{slot } \ell \texttt{ rewards}}+ \underbrace{\mathcal{R}_{b} (0, 32)}_{\texttt{slot } \ell+1 \texttt{ rewards}} \\ \end{aligned}
=2e1+2e+16=2(e1+e)+16. = 2e_{\ell-1} + 2 e_\ell + 16 = 2 (e_{\ell-1} + e_\ell) + 16.(30)

Similarly we calculate the rewards while following the selfish endorsing policy as

Rs(e1,e,p)=e1Re(0)slot 1 rewards+Rb(p,32)+eRe(p)slot  rewards+Rb(0,e)slot +1 rewards=2e1+16p+1+2p+1e+16(45+15e32)\begin{aligned} \mathcal{R}_{s}(&e_{\ell-1}, e_\ell, p_\ell) ={} \underbrace{e_{\ell-1} \cdot \mathcal{R}_{e}(0)}_{\texttt{slot } \ell-1 \texttt{ rewards}}+\underbrace{ \mathcal{R}_{b}(p_\ell, 32)+e_\ell \cdot \mathcal{R}_{e}(p_\ell) }_{\texttt{slot } \ell \texttt{ rewards}} \\ & + \underbrace{ \mathcal{R}_{b}(0, e_\ell)}_{\texttt{slot } \ell +1 \texttt{ rewards}} \\ ={}& 2 e_{\ell-1} + \frac{16}{p_\ell+1} + \frac{2}{p_\ell+1} e_\ell +16 \left(\frac{4}{5} + \frac{1}{5} \cdot \frac{e_\ell}{32}\right) \\ \end{aligned}
=2(ep+1+e1)+16(1p+1+45+e160). = 2 \left( \frac{e_{\ell}}{p_\ell +1} + e_{\ell-1} \right) + 16 \left(\frac{1}{p_\ell+ 1} + \frac{4}{5} + \frac{e_\ell}{160} \right).(31)

Now we can solve for R2\mathcal{R}_{2}:

R2(e1,e,p)=Rs(e1,e,p)Rh(e1,e)=2(ep+1+e1e1e)+16(1p+1+45+e1601)\begin{aligned} \mathcal{R}_{2} &(e_{\ell-1}, e_\ell, p_\ell) ={} \mathcal{R}_{s}(e_{\ell-1}, e_\ell, p_\ell) - \mathcal{R}_{h}(e_{\ell-1}, e_\ell) \\ ={}& 2 \left( \frac{e_{\ell}}{p_\ell +1} + e_{\ell-1} - e_{\ell-1} - e_\ell \right) + 16 \left(\frac{1}{p_\ell+ 1} + \frac{4}{5} + \frac{e_\ell}{160} - 1\right) \\ \end{aligned}
=2e(1p+11)+16(1p+1+e16015).= 2e_{\ell} \left( \frac{1}{p_\ell + 1} - 1\right) + 16 \left(\frac{1}{p_\ell+1} + \frac{e_\ell}{160} - \frac{1}{5} \right).(32)

B. Procedure 1

This procedure is used to calculate the total probability and value of a length-2 selfish endorsing attack. Note that ×\times is the Cartesian Product of lists.

C. Proof of Lemma 5.1

Lemma C. 1.

For any tuple (e1,p)(e_{\ell-1}, p_\ell), 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 .\ell. Denote this value Dh,1.\mathcal{D}_{h,1}. We have,

Dh,1(e1)=60+8max(24(32e1),0)\begin{aligned} \mathcal{D}_{h,1}(e_{\ell-1}) &= 60 + 8 \max(24-(32-e_{\ell-1}), 0) \end{aligned}
=60+8max(e18,0).\begin{aligned} &= 60 + 8 \max(e_{\ell-1}-8, 0). \end{aligned}(33)

Now we find the time it takes for the selfish delegate to create a block, Ds,1.\mathcal{D}_{s,1}. We have,

Ds,1(p,e1)=60+40p+max(24e1,0).\begin{aligned} \mathcal{D}_{s,1}(p_{\ell}, e_{\ell-1}) &= 60 + 40p_{\ell} + \max(24-e_{\ell-1}, 0). \end{aligned}(34)

The best case scenario for the attacker is when p=1,p_\ell=1, and for this we have

Ds,1(e1)=100+max(24e1,0).\begin{aligned} \mathcal{D}_{s,1}(e_{\ell-1}) &= 100 + \max(24-e_{\ell-1}, 0). \end{aligned}(35)

Now we find the number of endorsements required for the selfish delegate to produce a valid block faster than the honest network to be e1=19.e_{\ell-1}=19. We verify this with the following calculations:

Ds,1(19)=100+8(5)=140\begin{aligned} \mathcal{D}_{s,1}(19) &= 100 + 8 (5)= 140 \end{aligned}(36)
Dh,1(19)=60+8(11)=148\begin{aligned} \mathcal{D}_{h,1}(19) &= 60 + 8 (11)= 148 \end{aligned}(37)

Now we know that e1=19e_{\ell-1}= 19 is the best case scenario for the attack being feasible. If e1<19,e_{\ell-1} < 19, then the selfish network will not be able to create a block fast enough, and if e1>19,e_{\ell-1} > 19, 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 Rh,1(e1)=2e1\mathcal{R}_{h,1}(e_{\ell-1}) = 2e_{\ell-1} because we will get all the endorsement rewards, and the reward for playing selfishly is,

Rs,1(e1)=8(45+15e132)Rb(1,e1)+e11Re(1)\begin{aligned} \mathcal{R}_{s,1}(e_{\ell-1}) &= \underbrace{8 \left(\frac{4}{5} + \frac{1}{5} \cdot \frac{e_{\ell-1}}{32}\right)}_{\mathcal{R}_{b}(1,e_{\ell-1})} + e_{\ell-1} \cdot \underbrace{1}_{\mathcal{R}_{e}(1)} \end{aligned}(38)

Plugging in e1=19,e_{\ell-1}=19, we have

Rh,1(19)=19(2)=38\begin{aligned} \mathcal{R}_{h,1}(19) &= 19 ( 2) = 38 \end{aligned}(39)
Rs,1(19)=8(45+151932)+19=26.35\begin{aligned} \mathcal{R}_{s,1}(19) &= 8 \left(\frac{4}{5} + \frac{1}{5} \cdot \frac{19}{32}\right) + 19 = 26.35\end{aligned}(40)

We see that even for the smallest value of e1e_{\ell-1} 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 Rh,1>Rs,1,\mathcal{R}_{h,1} > \mathcal{R}_{s,1}, a single block selfish endorsing attack is not profitable under Emmy+.^+.

D. Proof of Lemma 5.3

Lemma D.1.

Under the modified PoS protocol, the total reward for a rational delegate X\mathcal{X} playing honestly over the next two blocks with the tuple (e1,e,p)(e_{\ell-1}, e_\ell, p_\ell) is

Rh(e1,e)=1.25(e1+e+32),\begin{aligned} \mathcal{R}'_{h}(e_{\ell-1}, e_\ell) &= 1.25 (e_{\ell-1} + e_\ell + 32), \end{aligned}

and the total reward for X\mathcal{X} to play selfishly over the next two blocks is

Rs(e1,e,p)=2.5(e1p+1+e).\begin{aligned} \mathcal{R}'_{s}(e_{\ell-1}, e_\ell, p_\ell) &= 2.5 \left( \frac{e_{\ell-1}}{p_\ell+1} + e_\ell\right). \end{aligned}