Compounding of Wealth in Proof-of-Stake Cryptocurrencies | SpringerLink Skip to main content This service is more advanced with JavaScript available Advertisement Hide Search SpringerLink Search Home Log in Financial Cryptography and Data Security International Conference on Financial Cryptography and Data Security FC 2019: Financial Cryptography and Data Security pp 42-61 | Cite as Compounding of Wealth in Proof-of-Stake Cryptocurrencies Authors Authors and affiliations Giulia Fanti Leonid Kogan Sewoong Oh Kathleen Ruan Pramod Viswanath Gerui Wang Conference paperFirst Online: 30 September 2019 12 Citations 1k Downloads Part of the Lecture Notes in Computer Science book series (LNCS, volume 11598) Abstract Proof-of-stake (PoS) is a promising approach for designing efficient blockchains, where block proposers are randomly chosen with probability proportional to their stake. A primary concern in PoS systems is the “rich getting richer” effect, whereby wealthier nodes are more likely to get elected, and hence reap the block reward, making them even wealthier. In this paper, we introduce the notion of equitability, which quantifies how much a proposer can amplify her stake compared to her initial investment. Even with everyone following protocol (i.e., honest behavior), we show that existing methods of allocating block rewards lead to poor equitability, as does initializing systems with small stake pools and/or large rewards relative to the stake pool. We identify a geometric reward function, which we prove is maximally equitable over all choices of reward functions under honest behavior and bound the deviation for strategic actions; the proofs involve the study of optimization problems and stochastic dominances of Pólya urn processes. These results allow us to provide a systematic framework to choose the parameters of a practical incentive system for PoS cryptocurrencies. Keywords Proof-of-stake Cryptocurrencies Random processes  This is a preview of subscription content, log in to check access. Supplementary material Open image in new window Appendix A Strategic Behavior We restrict ourselves in this section to two parties: A, which is adversarial, and H, which is honest. Note that this is without loss of generality, as H represent the collective set of multiple honest parties as their behavior is independent of how many parties are involved in H. The adversarial party A can also represent the collective set of multiple adversarial parties, as having a single adversary A is the worst case when all adversaries are colluding. Throughout this section, we use the terms adversarial and strategic interchangeably. Since A does not always publish its blocks on schedule, we distinguish the notion of a block slot (indexed by \(n \in [T]\)) and wall-clock time (indexed by \(t \in [T]\)). It will still be the case that each block slot n has a single leader W(n)—in practice, this is determined by a distributed protocol—and a new block slot leader is elected at every tick of the wall clock (i.e., at a given time t, W(n) is only defined for \(n\le t\)). However, due to strategic behavior (i.e., the adversary can withhold its own blocks and override honest ones), it can happen that no block occupies slot n, even at time \(t\ge n\); moreover, the occupancy of block slot n can change over time. Thus, unlike our previous setting, if we wait T time slots, the resulting chain may have fewer than T blocks. This is consistent with the adversarial model considered in PoS systems (e.g., Ouroboros [15]) that elect a single leader per block slot. Other PoS systems, like PoSv3 [8], choose an independent leader to succeed each block; such a PoS model can lead to even worse attacks, which we do not consider in this work. The honest party and the adversary have two different views of the blockchain, illustrated in Fig. 7. Both honest and adversarial parties see the main chain \(B_t\); we let \(B_t(n)\) denote the block (i.e., leader) of the nth slot, as perceived by the honest nodes at time t. If a block slot n does not have an associated block at time t (either because the nth block was withheld or overridden, or because \(n>t\)), we say that \(B_t(n)=\emptyset \). Notice that due to adversarial manipulations, it is possible for \(B_t(n)=\emptyset \) and \(B_{t-1}(n)\ne \emptyset \), and vice versa. In addition to the main chain, the adversary maintains arbitrarily many private side chains, \(\tilde{B}_t^1, \ldots , \tilde{B}_t^s\), where s denotes the number of side chains. The blocks in each side chain must respect the global leader sequence W(n). An adversary can choose at any time to publish a side chain, but we also assume that the adversary’s attacks are covert: it never publishes a side chain that conclusively proves that it is keeping side chains. For example, if the main chain contains a block B created by the adversary for block slot n, the adversary will never publish a side chain containing block \(\tilde{B}\ne B\), where \(\tilde{B}\) is also associated with block slot n. Each side chain \({\tilde{B}}_t^i\) with \(i\in [s]\) overlaps with the honest chain in at least one block (the genesis block), and may diverge from the main chain after some \(f_t^i \in \mathbb {N}_+\) (Fig. 7). That is,$$\begin{aligned} f_t^i := \max \{n \in \mathbb {N}_+ \,:\, B_t(n) = \tilde{B}_t^i(n) \}. \end{aligned}$$ Different side chains can also share blocks; in reality, the union of side chains is a tree. However, for simplicity of notation, we consider each path from the genesis block to a leaf of this forest as a separate side chain, instead of considering side trees. We use \(\ell _t\) and \(\tilde{\ell }_t^i\) to denote the chain length of \(B_t\) and \(\tilde{B}_t^i\), respectively, at time t:$$\begin{aligned} \ell _t = | \{n \in [T] \,:\, B_t(n)\ne \emptyset \} |&\;, \;\; \hbox { and } \;\;\;\; \tilde{\ell }_t^i = | \{n \in [T] \,:\, \tilde{B}_t^i(n)\ne \emptyset \} |, \end{aligned}$$ and we use the heights \(h_t\) and \(\tilde{h}_t^i\) to denote the block indices of the \(\ell _t\)th and \(\tilde{\ell }_t^i\)th blocks, respectively:$$\begin{aligned} h_t = \max \{n \in [T] \,:\, B_t(n)\ne \emptyset \}&\;, \;\; \hbox { and } \;\;\;\; \tilde{h}_t^i = \max \{n \in [T] \,:\, \tilde{B}_t^i(n)\ne \emptyset \}. \end{aligned}$$ If \(f_t^i = h_t\), then the adversary is building its ith side chain from the tip of the current main chain. Open image in new window Fig. 7. In PoS, the adversary can keep arbitrarily many side chains at negligible cost, and release (part of) a side chain whenever it chooses. State Space. The state space for the system consists of three pieces of data: (1) The current time \(t \in [T]\); (2) The main chain \(B_t\); and (3) The set of all side chains \(\{\tilde{B}_t^i\}_{i \in [s]}\). Notice in particular that the set of side chains grows exponentially in t. In practice, most systems prevent the main chain from being overtaken by a longer side chain that branches more than \(\varDelta \) blocks prior to \(h_t\); this is called a long-range attack. Hence we can upper bound the size of the side chain set by imposing the condition that for all \(i\in [s]\), \(h_t - f_t^i \le \varDelta \). Regardless, the size of the state space is considerably larger than it is in prior work on selfish mining in PoW [24], where the computational cost of creating a block forces the adversary to keep a single side chain. Objective. The adversary A’s goal is to maximize its fraction of the total stake in the main chain by the end of the experiment,$$\begin{aligned} v_{A}(t) \;\; = \;\; \frac{|\{n \in [T] \,:\, (W(n) = A) \wedge (B_T(n) \ne \emptyset ) \}|}{\ell _T}. \end{aligned}$$ This objective is closely related to the metric of prior work [24], except for the finite time duration. Strategy Space. The adversary has two primary mechanisms for achieving its objective: choosing where to append its blocks, and choosing when to release a side chain. If the honest party H is elected at time t, by the protocol, it always builds on the longest chain visible to it; since we assume small enough network latency, H appends to block \(B_{t-1}(h_{t-1})\). However, if A is elected at time t, A can append to any known block in \(B_{t-1} \cup \{\tilde{B}_{t-1}^i\}_{i \in [s]}\). The system must allow such a behavior for robustness reasons: even an honest proposer may not have received a block \(B_{t-1}(h_{t-1})\) or its predecessors due to network latency. The adversary can also choose when to release blocks. In our model, H always releases its block immediately when elected. However, an adversarial proposer elected at time t can choose to release its block at any time \( \ge t\); it can also choose not to release a given block. Late block announcements are also tolerated because of network latency; it is impossible to distinguish between a node that releases their blocks late and a node whose blocks arrive late because of a poor network connection. Notice that if A is elected at time t and chooses to withhold its block, the system advances to time \(t+1\) without appending A’s block to the main chain. This means that the next proposer \(W(t+1)\) is selected based on the stake ratios at time \(t-1\). So the adversary may have incurred a selfish mining gain from withholding its block, but it lost the opportunity to compound the \(t^{\text {th}}\) block reward. This tradeoff is the main difference between our analysis and prior work on selfish mining attacks in PoW systems. Drawing from [9, 24], at each time slot t, the adversary has three classes of actions available to it: match, override, and wait. (1) The adversary matches by choosing a side chain \(\tilde{B}_t^i\) and releasing the first \(h_t\) blocks. This means the released chain has the same height as the honest chain. In accordance with [9, 24], we assume that after a match, the honest chain will choose to build on the adversarial chain with probability \(\gamma \), which captures how connected the adversarial party is to the rest of the nodes.   (2) The adversary overrides by choosing a side chain \(\tilde{B}_t^i\) and releasing the first \(h = h_t+1\) blocks. The released chain becomes the new honest chain.   (3) If the adversary chooses to wait, it does not publish anything, and continues to build on all of its side chains.   Unlike [9, 24], we do not explicitly include an action wherein the adversary adopts the main chain. Because our model allows the adversary to keep an unbounded number of side chains, adopting the main chain is always a suboptimal strategy; it forces the adversary to throw away chains that could eventually overtake the main chain. The primary nuance in the adversary’s strategy is choosing when to match or override (rather than waiting), and which side chain to choose. Identifying an optimal mining strategy through MDP solvers as in [24] is computationally intractable due to the substantially larger state space in this PoS problem. References 1. Bitcoin energy consumption index (2018). https://digiconomist.net/BITCOIN-ENERGY-CONSUMPTION 2. Controlled supply. bitcoinwiki (2018). https://en.bitcoin.it/wiki/Controlled_supply#cite_note-2 3. Mining. Ethereum Wiki (2018). https://github.com/ethereum/wiki/wiki/Mining 4. Bambrough, B.: A bitcoin halvening is two years away – here’s what’ll happen to the bitcoin price. Forbes, May 2018Google Scholar 5. Bentov, I., Pass, R., Shi, E.: Snow white: provably secure proofs of stake. IACR Cryptology ePrint Archive 2016, p. 919 (2016)Google Scholar 6. Brünjes, L., Kiayias, A., Koutsoupias, E., Stouka, A.-P.: Reward sharing schemes for stake pools. arXiv preprint arXiv:1807.11218 (2018) 7. Duffield, E., Diaz, D.: Dash: a privacycentric cryptocurrency (2015, self-published)Google Scholar 8. Earls, J.: The missing explanation of proof of stake version 3 (2017). http://earlz.net/view/2017/07/27/1904/the-missing-explanation-of-proof-of-stake-version 9. Eyal, I., Sirer, E.G.: Majority is not enough: bitcoin mining is vulnerable. Commun. ACM 61(7), 95–102 (2018)CrossRefGoogle Scholar 10. Fanti, G., Kogan, L., Oh, S., Ruan, K., Viswanath, P., Wang, G.: Compounding of wealth in proof-of-stake cryptocurrencies. arXiv preprint arXiv:1809.07468 (2018) 11. Gaži, P., Kiayias, A., Russell, A.: Stake-bleeding attacks on proof-of-stake blockchains. In: 2018 Crypto Valley Conference on Blockchain Technology (CVCBT), pp. 85–92. IEEE (2018)Google Scholar 12. Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: scaling byzantine agreements for cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles, pp. 51–68. ACM (2017)Google Scholar 13. Hopwood, D., Bowe, S., Hornby, T., Wilcox, N.: Zcash protocol specification. Technical report, 2016–1.10. Zerocoin Electric Coin Company (2016)Google Scholar 14. Johnson, N.L., Kotz, S.: Urn Models and Their Application: An Approach to Modern Discrete Probability Theory, vol. 77. Wiley, New York (1977)zbMATHGoogle Scholar 15. Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: a provably secure proof-of-stake blockchain protocol. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 357–388. Springer, Cham (2017).  https://doi.org/10.1007/978-3-319-63688-7_12CrossRefGoogle Scholar 16. Mahmoud, H.: Pólya Urn Models. Chapman and Hall/CRC, Boca Raton (2008)CrossRefGoogle Scholar 17. moh\_man. How does pos stake concept deal with rich becoming richer issue? Reddit (2017). https://www.reddit.com/r/ethereum/comments/6x0xv8/how_does_pos_stake_concept_deal_with_rich/ 18. Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008)Google Scholar 19. Nayak, K., Kumar, S., Miller, A., Shi, E.: Stubborn mining: generalizing selfish mining and combining with an eclipse attack. In: 2016 IEEE European Symposium on Security and Privacy (EuroS&P), pp. 305–320. IEEE (2016)Google Scholar 20. Pass, R., Shi, E.: Fruitchains: a fair blockchain. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, pp. 315–324. ACM (2017)Google Scholar 21. Pemantle, R.: A time-dependent version of pólya’s urn. J. Theor. Probab. 3(4), 627–637 (1990)CrossRefGoogle Scholar 22. Rammeloo, G.: The economics of the proof of stake consensus algorithm. Medium (2017). https://medium.com/@gertrammeloo/the-economics-of-the-proof-of-stake-consensus-algorithm-e28adf63e9db 23. Ryan, D., Liang, C.-C.: Hybrid Casper FFG (2017). https://github.com/ethereum/EIPs/blob/master/EIPS/eip-1011.md 24. Sapirshtein, A., Sompolinsky, Y., Zohar, A.: Optimal selfish mining strategies in bitcoin. In: Grossklags, J., Preneel, B. (eds.) FC 2016. LNCS, vol. 9603, pp. 515–532. Springer, Heidelberg (2017).  https://doi.org/10.1007/978-3-662-54970-4_30CrossRefGoogle Scholar 25. Schrijvers, O., Bonneau, J., Boneh, D., Roughgarden, T.: Incentive compatibility of bitcoin mining pool reward functions. In: Grossklags, J., Preneel, B. (eds.) FC 2016. LNCS, vol. 9603, pp. 477–498. Springer, Heidelberg (2017).  https://doi.org/10.1007/978-3-662-54970-4_28CrossRefGoogle Scholar 26. Taylor-Copeland, J.: Coffey vs. Ripple class action complaint (2018)Google Scholar 27. Trustnodes.com. “proof of work is the rich get richer square” says vitalik buterin. Trustnodes (2018). https://www.trustnodes.com/2018/07/10/proof-work-rich-get-richer-squared-says-vitalik-buterin 28. Vukolić, M.: The quest for scalable blockchain fabric: proof-of-work vs. BFT replication. In: Camenisch, J., Kesdoğan, D. (eds.) iNetSec 2015. LNCS, vol. 9591, pp. 112–125. Springer, Cham (2016).  https://doi.org/10.1007/978-3-319-39028-4_9CrossRefGoogle Scholar 29. Wiki, E.: Proof of stake FAQs. https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQs Copyright information © International Financial Cryptography Association 2019 Authors and Affiliations Giulia Fanti 1 Email author Leonid Kogan 2 Sewoong Oh 3 Kathleen Ruan 1 Pramod Viswanath 4 Gerui Wang 4 1.Carnegie Mellon UniversityPittsburghUSA 2.Massachusetts Institute of TechnologyCambridgeUSA 3.University of WashingtonSeattleUSA 4.University of Illinois Urbana-ChampaignUrbanaUSA About this paper CrossMark Cite this paper as: Fanti G., Kogan L., Oh S., Ruan K., Viswanath P., Wang G. (2019) Compounding of Wealth in Proof-of-Stake Cryptocurrencies. In: Goldberg I., Moore T. (eds) Financial Cryptography and Data Security. FC 2019. Lecture Notes in Computer Science, vol 11598. Springer, Cham. https://doi.org/10.1007/978-3-030-32101-7_3 First Online 30 September 2019 DOI https://doi.org/10.1007/978-3-030-32101-7_3 Publisher Name Springer, Cham Print ISBN 978-3-030-32100-0 Online ISBN 978-3-030-32101-7 eBook Packages Computer Science Computer Science (R0) Buy this book on publisher's site Reprints and Permissions Personalised recommendations Cite paper How to cite? .RIS Papers Reference Manager RefWorks Zotero .ENW EndNote .BIB BibTeX JabRef Mendeley Buy options Actions Buying options Chapter USD   29.95 Price excludes VAT DOI: 10.1007/978-3-030-32101-7_3 Instant PDF download Readable on all devices Own it forever Exclusive offer for individuals only Buy Chapter eBook USD 69.99 Price excludes VAT ISBN: 978-3-030-32101-7 Instant PDF download Readable on all devices Own it forever Exclusive offer for individuals only Buy eBook Softcover Book USD 89.99 Price excludes VAT ISBN: 978-3-030-32100-0 Dispatched in 3 to 5 business days Exclusive offer for individuals only Free shipping worldwide COVID-19 restrictions may apply, check to see if you are impacted. Buy Softcover Book Learn about institutional subscriptions Cite paper How to cite? .RIS Papers Reference Manager RefWorks Zotero .ENW EndNote .BIB BibTeX JabRef Mendeley Advertisement Hide Over 10 million scientific documents at your fingertips Switch Edition Academic Edition Corporate Edition Home Impressum Legal information Privacy statement California privacy statement How we use cookies Manage cookies/Do not sell my data Accessibility Contact us Springer Nature © 2020 Springer Nature Switzerland AG. Part of Springer Nature. Not logged in Not affiliated 40.76.139.33