Abstract
An important feature of Proof-of-Work (PoW) blockchains is full dynamic availability, allowing miners to go online and offline while requiring only 50% of the online miners to be honest. Existing Proof-of-stake (PoS), Proof-of-Space and related protocols are able to achieve this property only partially, either requiring the additional assumption that adversary nodes are online from the beginning and no new adversary nodes come online afterwards, or use additional trust assumptions for newly joining nodes. We propose a new PoS protocol PoSAT which can provably achieve dynamic availability fully without any additional assumptions. The protocol is based on the longest chain and uses a Verifiable Delay Function for the block proposal lottery to provide an arrow of time. The security analysis of the protocol draws on the recently proposed technique of Nakamoto blocks as well as the theory of branching random walks. An additional feature of PoSAT is the complete unpredictability of who will get to propose a block next, even by the winner itself. This unpredictability is at the same level of PoW protocols, and is stronger than that of existing PoS protocols using Verifiable Random Functions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
All jump processes are assumed to be right-continuous with left limits, so that \({\mathcal {C}}(t),{\mathcal {T}}(t)\) etc. include the new arrival if there is a new arrival at time t.
References
Azouvi, S., McCorry, P., Meiklejohn, S.: Betting on blockchain consensus with fantomette. arXiv preprint arXiv:1805.06786 (2018)
Badertscher, C., Gaži, P., Kiayias, A., Russell, A., Zikas, V.: Ouroboros genesis: composable proof-of-stake blockchains with dynamic availability. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 913–930. ACM (2018)
Bagaria, V., et al.: Proof-of-stake longest chain protocols: security vs predictability. arXiv preprint arXiv:1910.02218 (2019)
Bentov, I., Pass, R., Shi, E.: Snow white: provably secure proofs of stake. IACR Cryptol. ePrint Arch. 2016, 919 (2016)
Boneh, D., Bonneau, J., Bünz, B., Fisch, B.: Verifiable delay functions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 757–788. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_25
Brown-Cohen, J., Narayanan, A., Psomas, A., Weinberg, S.M.: Formal barriers to longest-chain proof-of-stake protocols. In: Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 459–473 (2019)
Buchman, E., Kwon, J., Milosevic, Z.: The latest gossip on BFT consensus (2018)
Cai, J.-Y., Lipton, R.J., Sedgewick, R., Yao, A.-C.: Towards uncheatable benchmarks. In: [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pp. 2–11. IEEE (1993)
Chen, J., Micali, S.: Algorand. arXiv preprint arXiv:1607.01341 (2016)
Cohen, B., Pietrzak, K.: The chia network blockchain (2019). https://www.chia.net/assets/ChiaGreenPaper.pdf
David, B., Gaži, P., Kiayias, A., Russell, A.: Ouroboros praos: an adaptively-secure, semi-synchronous proof-of-stake blockchain. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 66–98. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_3
Deb, S., Kannan, S., Tse, D.: PoSAT: proof-of-work availability and unpredictability, without the work. arXiv preprint arXiv:2010.08154 (2020)
Dembo, A., et al.: Everything is a race and Nakamoto always wins. In: ACM CCS (2020). See also arXiv preprint arXiv:2005.10484
Dodis, Y., Yampolskiy, A.: A verifiable random function with short proofs and keys. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 416–431. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30580-4_28
Ephraim, N., Freitag, C., Komargodski, I., Pass, R.: Continuous verifiable delay functions. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 125–154. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_5
Fan, L., Zhou, H.-S.A.: Scalable proof-of-stake blockchain in the open setting (or, how to mimic Nakamoto’s design via proof-of-stake). Cryptology ePrint Archive, Report 2017/656 (2018). Version 20180425:201821
Fitzi, M., Gaži, P., Kiayias, A., Russell, A.: Ledger combiners for fast settlement. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12550, pp. 322–352. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64375-1_12
Garay, J., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: analysis and applications. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 281–310. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_10
Garay, J., Kiayias, A., Leonardos, N.: Full analysis of Nakamoto consensus in bounded-delay networks. Cryptology ePrint Archive, Report 2020/277 (2020). https://eprint.iacr.org/2020/277
Garay, J.A., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol with chains of variable difficulty. Cryptology ePrint Archive, Report 2016/1048 (2016). https://eprint.iacr.org/2016/1048
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)
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_12
Long, J., Wei, R.: Nakamoto consensus with verifiable delay puzzle. arXiv preprint arXiv:1908.06394 (2019)
Mahmoody, M., Moran, T., Vadhan, S.: Publicly verifiable proofs of sequential work. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, pp. 373–388 (2013)
Micali, S., Rabin, M., Vadhan, S.: Verifiable random functions. In: 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039) (1999), pp. 120–130. IEEE
Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008)
Pass, R., Seeman, L., Shelat, A.: Analysis of the blockchain protocol in asynchronous networks. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 643–673. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_22
Pass, R., Shi, E.: FruitChains: a fair blockchain. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, pp. 315–324 (2017)
Pass, R., Shi, E.: The sleepy model of consensus. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 380–409. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_14
Pietrzak, K.: Simple verifiable delay functions. In: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
Ren, L.: Analysis of Nakamoto consensus. Technical Report. Cryptology ePrint Archive, Report 2019/943. (2019). https://eprint.iacr.org
Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release crypto (1996)
Shi, Z.: Branching Random Walks. LNM, vol. 2151. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-25372-5
Wang, X., et al.: Proof-of-stake longest chain protocol revisited. arXiv preprint arXiv:1910.02218v2 (2018)
Wesolowski, B.: Efficient verifiable delay functions. J. Cryptol. 33(4), 2113–2147 (2020). https://doi.org/10.1007/s00145-020-09364-x
Yin, M., Malkhi, D., Reiter, M.K., Gueta, G.G., Abraham, I.: HotStuff: BFT consensus in the lens of blockchain. arXiv preprint arXiv:1803.05069 (2018)
Yu, H., Nikolic, I., Hou, R., Saxena, P.: OHIE: blockchain scaling made simple. arXiv preprint arXiv:1811.12628 (2018)
Acknowledgements
DT wants to thank Ling Ren for earlier discussions on dynamic availability of Proof-of-Stake protocols.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 International Financial Cryptography Association
About this paper
Cite this paper
Deb, S., Kannan, S., Tse, D. (2021). PoSAT: Proof-of-Work Availability and Unpredictability, Without the Work. In: Borisov, N., Diaz, C. (eds) Financial Cryptography and Data Security. FC 2021. Lecture Notes in Computer Science(), vol 12675. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-64331-0_6
Download citation
DOI: https://doi.org/10.1007/978-3-662-64331-0_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-64330-3
Online ISBN: 978-3-662-64331-0
eBook Packages: Computer ScienceComputer Science (R0)