{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T16:05:34Z","timestamp":1781885134550,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T00:00:00Z","timestamp":1733097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1563098"],"award-info":[{"award-number":["CCF-1563098"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["#1443\/21"],"award-info":[{"award-number":["#1443\/21"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,12,2]]},"DOI":"10.1145\/3658644.3670347","type":"proceedings-article","created":{"date-parts":[[2024,12,9]],"date-time":"2024-12-09T12:19:20Z","timestamp":1733746760000},"page":"363-377","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Nakamoto Consensus under Bounded Processing Capacity"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2022-7993","authenticated-orcid":false,"given":"Lucianna","family":"Kiffer","sequence":"first","affiliation":[{"name":"ETH Z\u00fcrich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9777-6168","authenticated-orcid":false,"given":"Joachim","family":"Neu","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1880-570X","authenticated-orcid":false,"given":"Srivatsan","family":"Sridhar","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8539-9222","authenticated-orcid":false,"given":"Aviv","family":"Zohar","sequence":"additional","affiliation":[{"name":"The Hebrew University, Jerusalem, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1460-5900","authenticated-orcid":false,"given":"David","family":"Tse","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,12,9]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"[n. d.]. Block size limit controversy. https:\/\/en.bitcoin.it\/wiki\/Block_size_limit_controversy"},{"key":"e_1_3_2_1_2_1","unstructured":"Mustafa Al-Bassam. 2019. LazyLedger: A Distributed Data Availability Ledger With Client-Side Smart Contracts. arXiv:1905.09274v4 [cs.CR]"},{"key":"e_1_3_2_1_3_1","volume-title":"Financial Cryptography (2) (LNCS","author":"Al-Bassam Mustafa","unstructured":"Mustafa Al-Bassam, Alberto Sonnino, Vitalik Buterin, and Ismail Khoffi. 2021. Fraud and Data Availability Proofs: Detecting Invalid Blocks in Light Clients. In Financial Cryptography (2) (LNCS, Vol. 12675). Springer, 279--298."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243848"},{"key":"e_1_3_2_1_5_1","unstructured":"Vivek Bagaria Amir Dembo Sreeram Kannan Sewoong Oh David Tse Pramod Viswanath Xuechao Wang and Ofer Zeitouni. 2019. Proof-of-Stake Longest Chain Protocols: Security vs Predictability. arXiv:1910.02218v3 [cs.CR]"},{"key":"e_1_3_2_1_6_1","volume-title":"Prism: Deconstructing the Blockchain to Approach Physical Limits. In CCS. ACM, 585--602.","author":"Bagaria Vivek Kumar","year":"2019","unstructured":"Vivek Kumar Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, and Pramod Viswanath. 2019. Prism: Deconstructing the Blockchain to Approach Physical Limits. In CCS. ACM, 585--602."},{"key":"e_1_3_2_1_7_1","unstructured":"Lear Bahack. 2013. Theoretical Bitcoin Attacks with less than Half of the Computational Power (draft). arXiv:1312.7013v1 [cs.CR]"},{"key":"e_1_3_2_1_8_1","unstructured":"Bitcoin Project. [n. d.]. Running A Full Node ? Bitcoin. https:\/\/bitcoin.org\/en\/full-node#minimum-requirements"},{"key":"e_1_3_2_1_9_1","unstructured":"Bitcoin Project. 2020. Bitcoin Developer Guide -- P2P Network -- Initial Block Download -- Headers-First. https:\/\/web.archive.org\/web\/20230314181737\/https:\/\/developer.bitcoin.org\/devguide\/p2p_network.html#headers-first"},{"key":"e_1_3_2_1_10_1","volume-title":"The Combinatorics of the Longest-Chain Rule: Linear Consistency for Proof-of-Stake Blockchains","author":"Blum Erica","unstructured":"Erica Blum, Aggelos Kiayias, Cristopher Moore, Saad Quader, and Alexander Russell. 2020. The Combinatorics of the Longest-Chain Rule: Linear Consistency for Proof-of-Stake Blockchains. In SODA. SIAM, 1135--1154."},{"key":"e_1_3_2_1_11_1","unstructured":"Vitalik Buterin. [n. d.]. Proof of Stake: How I Learned to Love Weak Subjectivity. https:\/\/blog.ethereum.org\/2014\/11\/25\/proof-stake-learned-love-weak-subjectivity"},{"key":"e_1_3_2_1_12_1","unstructured":"Vitalik Buterin and Virgil Griffith. 2017. Casper the Friendly Finality Gadget. arXiv:1710.09437v4 [cs.CR]"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561927_42"},{"key":"e_1_3_2_1_14_1","unstructured":"Cl\u00e9ment Canonne. [n. d.]. A short note on Poisson tail bounds. https:\/\/github.com\/ccanonne\/probabilitydistributiontoolbox\/blob\/master\/poissonconcentration.pdf"},{"key":"e_1_3_2_1_15_1","volume-title":"FC (LNCS","volume":"165","author":"Cao Tong","year":"2023","unstructured":"Tong Cao, J\u00e9r\u00e9mie Decouchant, and Jiangshan Yu. 2023. Leveraging the Verifier's Dilemma to Double Spend in Bitcoin. In FC (LNCS, Vol. 13951). Springer, 149--165."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3381036"},{"key":"e_1_3_2_1_17_1","volume-title":"FC (LNCS","volume":"53","author":"Cohen Shir","year":"2023","unstructured":"Shir Cohen, Guy Goren, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2023. Proof of Availability and Retrieval in a Modular Blockchain Architecture. In FC (LNCS, Vol. 13951). Springer, 36--53."},{"key":"e_1_3_2_1_18_1","volume-title":"Financial Cryptography Workshops (LNCS","volume":"125","author":"Croman Kyle","year":"2016","unstructured":"Kyle Croman, Christian Decker, Ittay Eyal, Adem Efe Gencer, Ari Juels, Ahmed E. Kosba, Andrew Miller, Prateek Saxena, Elaine Shi, Emin G\u00fcn Sirer, Dawn Song, and Roger Wattenhofer. 2016. On Scaling Decentralized Blockchains - (A Position Paper). In Financial Cryptography Workshops (LNCS, Vol. 9604). Springer, 106--125."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32101-7_2"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"George Danezis Lefteris Kokoris-Kogias Alberto Sonnino and Alexander Spiegelman. 2022. Narwhal and Tusk: a DAG-based mempool and efficient BFT consensus. In EuroSys. ACM 34--50.","DOI":"10.1145\/3492321.3519594"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3491053"},{"key":"e_1_3_2_1_22_1","volume-title":"Ouroboros Praos: An Adaptively-Secure, Semi-synchronous Proof-of-Stake Blockchain. In EUROCRYPT (2) (LNCS","author":"David Bernardo","year":"2018","unstructured":"Bernardo David, Peter Gazi, Aggelos Kiayias, and Alexander Russell. 2018. Ouroboros Praos: An Adaptively-Secure, Semi-synchronous Proof-of-Stake Blockchain. In EUROCRYPT (2) (LNCS, Vol. 10821). Springer, 66--98."},{"key":"e_1_3_2_1_23_1","volume-title":"P2P","author":"Decker Christian","unstructured":"Christian Decker and Roger Wattenhofer. 2013. Information propagation in the Bitcoin network. In P2P. IEEE, 1--10."},{"key":"e_1_3_2_1_24_1","volume-title":"David Tse, Pramod Viswanath, Xuechao Wang, and Ofer Zeitouni.","author":"Dembo Amir","year":"2020","unstructured":"Amir Dembo, Sreeram Kannan, Ertem Nusret Tas, David Tse, Pramod Viswanath, Xuechao Wang, and Ofer Zeitouni. 2020. Everything is a Race and Nakamoto Always Wins. In CCS. ACM, 859--878."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-019-00357-z"},{"key":"e_1_3_2_1_26_1","unstructured":"John Duchi. [n. d.]. Hoeffding's inequality. http:\/\/cs229.stanford.edu\/extra-notes\/hoeffding.pdf"},{"key":"e_1_3_2_1_27_1","unstructured":"Matthias Fitzi Peter Ga?i Aggelos Kiayias and Alexander Russell. 2020. Proof-of-Stake Blockchain Protocols with Near-Optimal Throughput. Cryptology ePrint Archive Paper 2020\/037. https:\/\/eprint.iacr.org\/2020\/037"},{"key":"e_1_3_2_1_28_1","volume-title":"EUROCRYPT (2) (LNCS","author":"Garay Juan A.","unstructured":"Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. 2015. The Bitcoin Backbone Protocol: Analysis and Applications. In EUROCRYPT (2) (LNCS, Vol. 9057). Springer, 281--310."},{"key":"e_1_3_2_1_29_1","volume-title":"CRYPTO (1) (LNCS","author":"Garay Juan A.","unstructured":"Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. 2017. The Bitcoin Backbone Protocol with Chains of Variable Difficulty. In CRYPTO (1) (LNCS, Vol. 10401). Springer, 291--323."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Peter Gazi Aggelos Kiayias and Alexander Russell. 2020. Tight Consistency Bounds for Bitcoin. In CCS. ACM 819--838.","DOI":"10.1145\/3372297.3423365"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Arthur Gervais Ghassan O. Karame Karl W\u00fcst Vasileios Glykantzis Hubert Ritzdorf and Srdjan Capkun. 2016. On the Security and Performance of Proof of Work Blockchains. In CCS. ACM 3--16.","DOI":"10.1145\/2976749.2978341"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.04.013"},{"key":"e_1_3_2_1_33_1","volume-title":"Reiter","author":"Hendricks James","year":"2007","unstructured":"James Hendricks, Gregory R. Ganger, and Michael K. Reiter. 2007. Verifying distributed erasure-coded data. In PODC. ACM, 139--146."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_3_2_1_35_1","volume-title":"Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol. In CRYPTO (1) (LNCS","author":"Kiayias Aggelos","year":"2017","unstructured":"Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. 2017. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol. In CRYPTO (1) (LNCS, Vol. 10401). Springer, 357--388."},{"key":"e_1_3_2_1_36_1","unstructured":"Lucianna Kiffer Joachim Neu Srivatsan Sridhar Aviv Zohar and David Tse. 2023. Nakamoto Consensus under Bounded Processing Capacity. Cryptology ePrint Archive Paper 2023\/381. https:\/\/eprint.iacr.org\/2023\/381"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Lucianna Kiffer Rajmohan Rajaraman and Abhi Shelat. 2018. A Better Method to Analyze Blockchain Consistency. In CCS. ACM 729--744.","DOI":"10.1145\/3243734.3243814"},{"key":"e_1_3_2_1_38_1","volume-title":"Financial Cryptography (2) (LNCS","author":"Kiffer Lucianna","unstructured":"Lucianna Kiffer, Asad Salman, Dave Levin, Alan Mislove, and Cristina Nita-Rotaru. 2021. Under the Hood of the Ethereum Gossip Protocol. In Financial Cryptography (2) (LNCS, Vol. 12675). Springer, 437--456."},{"key":"e_1_3_2_1_39_1","unstructured":"Andreas Lenz. [n. d.]. Random walk with positive drift. https:\/\/math.stackexchange.com\/q\/4449213"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Jing Li Dongning Guo and Ling Ren. 2021. Close latency-security trade-off for the Nakamoto consensus. In AFT. ACM 100--113.","DOI":"10.1145\/3479722.3480992"},{"key":"e_1_3_2_1_41_1","volume-title":"ESORICS (3) (LNCS","author":"Lu Zhichun","unstructured":"Zhichun Lu and Ren Zhang. 2023. When is Slower Block Propagation More Profitable for Large Miners?. In ESORICS (3) (LNCS, Vol. 14346). Springer, 285--305."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Loi Luu Jason Teutsch Raghav Kulkarni and Prateek Saxena. 2015. Demystifying Incentives in the Consensus Computer. In CCS. ACM 706--719.","DOI":"10.1145\/2810103.2813659"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Andrew Miller Yu Xia Kyle Croman Elaine Shi and Dawn Song. 2016. The Honey Badger of BFT Protocols. In CCS. ACM 31--42.","DOI":"10.1145\/2976749.2978399"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Michael Mirkin Yan Ji Jonathan Pang Ariah Klages-Mundt Ittay Eyal and Ari Juels. 2020. BDoS: Blockchain Denial-of-Service. In CCS. ACM 601--619.","DOI":"10.1145\/3372297.3417247"},{"key":"e_1_3_2_1_45_1","volume-title":"Bitcoin: A Peer-to-Peer Electronic Cash System. https:\/\/bitcoin.org\/bitcoin.pdf.","author":"Nakamoto Satoshi","year":"2008","unstructured":"Satoshi Nakamoto. 2008. Bitcoin: A Peer-to-Peer Electronic Cash System. https:\/\/bitcoin.org\/bitcoin.pdf."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Kamilla Nazirkhanova Joachim Neu and David Tse. 2022. Information Dispersal with Provable Retrievability for Rollups. In AFT. ACM 180--197.","DOI":"10.1145\/3558535.3559778"},{"key":"e_1_3_2_1_47_1","unstructured":"Joachim Neu. 2022. Data Availability Sampling: From Basics to Open Problems. https:\/\/www.paradigm.xyz\/2022\/08\/das"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Joachim Neu Srivatsan Sridhar Lei Yang David Tse and Mohammad Alizadeh. 2022. Longest Chain Consensus Under Bandwidth Constraint. In AFT. ACM 126--147.","DOI":"10.1145\/3558535.3559777"},{"key":"e_1_3_2_1_49_1","volume-title":"Ertem Nusret Tas, and David Tse","author":"Neu Joachim","year":"2022","unstructured":"Joachim Neu, Ertem Nusret Tas, and David Tse. 2022. The Availability-Accountability Dilemma and Its Resolution via Accountability Gadgets. In Financial Cryptography (LNCS, Vol. 13411). Springer, 541--559."},{"key":"e_1_3_2_1_50_1","volume-title":"EUROCRYPT (2) (LNCS","author":"Pass Rafael","unstructured":"Rafael Pass, Lior Seeman, and Abhi Shelat. 2017. Analysis of the Blockchain Protocol in Asynchronous Networks. In EUROCRYPT (2) (LNCS, Vol. 10211). 643--673."},{"key":"e_1_3_2_1_51_1","unstructured":"Rafael Pass and Elaine Shi. 2016. The Sleepy Model of Consensus. Cryptology ePrint Archive Paper 2016\/918. https:\/\/eprint.iacr.org\/2016\/918"},{"key":"e_1_3_2_1_52_1","volume-title":"ASIACRYPT (2) (LNCS","author":"Pass Rafael","unstructured":"Rafael Pass and Elaine Shi. 2017. The Sleepy Model of Consensus. In ASIACRYPT (2) (LNCS, Vol. 10625). Springer, 380--409."},{"key":"e_1_3_2_1_53_1","volume-title":"Broken Metre: Attacking Resource Metering in EVM","author":"Perez Daniel","year":"2020","unstructured":"Daniel Perez and Benjamin Livshits. 2020. Broken Metre: Attacking Resource Metering in EVM. In NDSS. The Internet Society."},{"key":"e_1_3_2_1_54_1","unstructured":"Jamie Redman. [n. d.]. Running Bitcoin Cash: An Introduction to Operating a Full Node. https:\/\/news.bitcoin.com\/running-bitcoin-cash-an-introduction-to-operating-a-full-node\/"},{"key":"e_1_3_2_1_55_1","unstructured":"Ling Ren. 2019. Analysis of Nakamoto Consensus. Cryptology ePrint Archive Paper 2019\/943. https:\/\/eprint.iacr.org\/2019\/943"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2023.3302955"},{"key":"e_1_3_2_1_57_1","volume-title":"The Longest-Chain Protocol Under Random Delays. Stochastic Systems","author":"Sankagiri Suryanarayana","year":"2023","unstructured":"Suryanarayana Sankagiri, Shreyas Gandlur, and Bruce Hajek. 2023. The Longest-Chain Protocol Under Random Delays. Stochastic Systems (2023), 13(4):457--458."},{"key":"e_1_3_2_1_58_1","first-page":"1","article-title":"An Empirical Study of Speculative Concurrency in Ethereum Smart Contracts. In Tokenomics (OASIcs, Vol. 71)","volume":"4","author":"Saraph Vikram","year":"2019","unstructured":"Vikram Saraph and Maurice Herlihy. 2019. An Empirical Study of Speculative Concurrency in Ethereum Smart Contracts. In Tokenomics (OASIcs, Vol. 71). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 4:1--4:15.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"crossref","unstructured":"Peiyao Sheng Gerui Wang Kartik Nayak Sreeram Kannan and Pramod Viswanath. 2021. BFT Protocol Forensics. In CCS. ACM 1722--1743.","DOI":"10.1145\/3460120.3484566"},{"key":"e_1_3_2_1_60_1","unstructured":"Yonatan Sompolinsky and Aviv Zohar. 2016. Bitcoin?s Security Model Revisited. arXiv:1605.09193v2 [cs.CR]"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3559361"},{"key":"e_1_3_2_1_62_1","unstructured":"Shichen Wu Puwen Wei Ren Zhang and Bowen Jiang. 2023. Security-Performance Tradeoff in DAG-based Proof-of-Work Blockchain Protocols. Cryptology ePrint Archive Paper 2023\/1089. https:\/\/eprint.iacr.org\/2023\/1089"},{"key":"e_1_3_2_1_63_1","volume-title":"Mohammad Alizadeh, Sreeram Kannan, and David Tse.","author":"Yang Lei","year":"2022","unstructured":"Lei Yang, Seo Jin Park, Mohammad Alizadeh, Sreeram Kannan, and David Tse. 2022. DispersedLedger: High-Throughput Byzantine Consensus on Variable Bandwidth Networks. In NSDI. USENIX Association, 493--512."}],"event":{"name":"CCS '24: ACM SIGSAC Conference on Computer and Communications Security","location":"Salt Lake City UT USA","acronym":"CCS '24","sponsor":["SIGSAC ACM Special Interest Group on Security, Audit, and Control"]},"container-title":["Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3658644.3670347","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3658644.3670347","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T05:58:52Z","timestamp":1755842332000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3658644.3670347"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,2]]},"references-count":63,"alternative-id":["10.1145\/3658644.3670347","10.1145\/3658644"],"URL":"https:\/\/doi.org\/10.1145\/3658644.3670347","relation":{},"subject":[],"published":{"date-parts":[[2024,12,2]]},"assertion":[{"value":"2024-12-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}