The Longest-Chain Protocol Under Random Delays

References

• Badertscher C, Gaži P, Kiayias A, Russell A, Zikas V (2018) Ouroboros genesis: Composable proof-of-stake blockchains with dynamic availability. Backes M, Wang XF, eds. Proc. ACM SIGSAC Conf. on Computer and Comm Security (Association for Computing Machinery, New York), 913–930.Google Scholar
• Bano S, Sonnino A, Al-Bassam M, Azouvi S, McCorry P, Meiklejohn S, Danezis G (2019) SoK: Consensus in the age of blockchains. Abraham I, Eyal I, Gün Sirer E, eds. Proc. 1st ACM Conf. on Advances in Financial Technologies (Association for Computing Machinery, New York), 183–198.Google Scholar
• Blum E, Kiayias A, Moore C, Quader S, Russell A (2020) The combinatorics of the longest-chain rule: Linear consistency for proof-of-stake blockchains. Chawla S, eds. Proc. 14th Annual ACM-SIAM Sympos. on Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1135–1154.Google Scholar
• David B, Gaži P, Kiayias A, Russell A (2018) Ouroboros praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain. Nielsen JB, Rijmen V, eds. Annual Internat. Conf. on the Theory and Appl. of Cryptographic Techniques (Springer International Publishing, Cham, Switzerland), 66–98.Google Scholar
• Decker C, Wattenhofer R (2013) Information propagation in the bitcoin network. Lo Cigno R, Felber P, Iamnitchi A, eds. Proc. IEEE P2P (Institute of Electrical and Electronics Engineers, New York), 1–10.Google Scholar
• Dembo A, Kannan S, Tas EN, Tse D, Viswanath P, Wang X, Zeitouni O (2020) Everything is a race and nakamoto always wins. Katz J, Vigna G, eds. Proc. 2020 ACM SIGSAC Conf. on Computer and Comm. Security (Association for Computing Machinery, New York), 859–878.Google Scholar
• Dwork C, Lynch N, Stockmeyer L (1988) Consensus in the presence of partial synchrony. J. ACM 35(2):288–323.Google Scholar
• Fanti G, Jiao J, Makkuva A, Oh S, Rana R, Viswanath P (2019) Barracuda: The power of l-polling in proof-of-stake blockchains. Subramanian V, Yi Y, eds. Proc. 20th ACM Internat. Sympos. on Mobile Ad Hoc Networking and Comput. (Association for Computing Machinery, New York), 351–360.Google Scholar
• Garay J, Kiayias A (2020) SoK: A consensus taxonomy in the blockchain era. Jarecki S, ed. Proc. Cryptographers’ Track at the RSA Conf. (Springer International Publishing, Cham), 284–318.Google Scholar
• Garay J, Kiayias A, Leonardos N (2015) The bitcoin backbone protocol: Analysis and applications. Oswald E, Fischlin M, eds. Annual Internat. Conf. on the Theory and Appl. of Cryptographic Techniques (Springer International Publishing, Cham, Switzerland), 281–310.Google Scholar
• Gaži P, Kiayias A, Russell A (2020) Tight consistency bounds for bitcoin. Katz J, Vigna G, eds. Proc. ACM SIGSAC Conf. on Computer and Comm. Security (Association for Computing Machinery, New York), 819–838.Google Scholar
• Gaži P, Ren L, Russell A (2022) Practical settlement bounds for proof-of-work blockchains. Cremers C, Shi E, eds. Proc. ACM SIGSAC Conf. on Computer and Comm. Security (Association for Computing Machinery, New York), 1217–1230.Google Scholar
• Goffard PO (2019) Fraud risk assessment within blockchain transactions. Adv. Appl. Probability 51(2):443–467.Google Scholar
• Gopalan A, Sankararaman A, Walid A, Vishwanath S (2020) Stability and scalability of blockchain systems. Proc. ACM Measures and Analysis of Computer Systems (Association for Computing Machinery, New York), 35.Google Scholar
• Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58:13–30.Google Scholar
• Kiayias A, Russell A, David B, Oliynykov R (2017) Ouroboros: A provably secure proof-of-stake blockchain protocol. Shacham H, Katz J, eds. Annual Internat. Cryptology Conf. (Springer International Publishing, Cham, Switzerland), 357–388.Google Scholar
• Kingman J (1964) A martingale inequality in the theory of queues. Cambridge Philosophical Soc. 59:359–361.Google Scholar
• Li J, Guo D, Ren L (2021) Close latency–security trade-off for the Nakamoto consensus. Baldimtsi F, Roughgarden T, eds. Proc. 3rd ACM Conf. on Adv. in Financial Technologies (Association for Computing Machinery, New York), 100–113.Google Scholar
• Nakamoto S (2008) Bitcoin: A peer-to-peer electronic cash system. Accessed October 31, 2008, https://bitcoin.org/bitcoin.pdf.Google Scholar
• Neu J, Tas EN, Tse D (2021) Ebb-and-flow protocols: A resolution of the availability-finality dilemma. Oprea A, Holz T, eds. Proc. IEEE Sympos. on Security and Privacy (IEEE, New York), 446–465.Google Scholar
• Pass R, Shi E (2017) The sleepy model of consensus. Takagi T, Peyrin T, eds. Proc. Internat. Conf. on the Theory and Appl. of Cryptology and Information Security (Springer International Publishing, Cham, Switzerland), 380–409.Google Scholar
• Pass R, Seeman L, Shelat A (2017) Analysis of the blockchain protocol in asynchronous networks. Coron J-S, Nielsen JB, eds. Proc. Annual Internat. Conf. on the Theory and Appl. of Cryptographic Techniques (Springer International Publishing, Cham, Switzerland), 643–673.Google Scholar
• Ren L (2019) Analysis of Nakamoto consensus. Preprint, submitted August 19, 2019; last revised May 18, 2020, https://eprint.iacr.org/2019/943.Google Scholar
• Rosenfeld M (2014) Analysis of hashrate-based double spending. Preprint, submitted February 9, https://arxiv.org/abs/1402.2009.Google Scholar
• Sompolinsky Y, Zohar A (2015) Secure high-rate transaction processing in bitcoin. Böhme R, Okamoto T, eds. Proc. Internat. Conf. on Financial Cryptography and Data Security (Springer International Publishing, Cham, Switzerland), 507–527.Google Scholar