{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:41:25Z","timestamp":1755999685252,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,12,14]],"date-time":"2021-12-14T00:00:00Z","timestamp":1639440000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2021,12,14]]},"abstract":"<jats:p>Proof-of-Work (PoW) based blockchains typically allocate only a tiny fraction (e.g., less than 1% for Ethereum) of the average interarrival time (I) between blocks for validating smart contracts present in transactions. In such systems, block validation and PoW mining are typically performed sequentially, the former by CPUs and the latter by ASICs. A trivial increase in validation time (\u03c4) introduces the popularly known Verifier's Dilemma, and as we demonstrate, causes more forking and hurts fairness. Large \u03c4 also reduces the tolerance for safety against a Byzantine adversary. Solutions that offload validation to a set of non-chain nodes (a.k.a. off-chain approaches) suffer from trust and performance issues that are non-trivial to resolve. In this paper, we present Tuxedo, the first on-chain protocol to theoretically scale \u03c4\/I \u22481 in PoW blockchains. The key innovation in Tuxedo is to perform CPU-based block processing in parallel to ASIC mining. We achieve this by allowing miners to delay validation of transactions in a block by up to \u03b6 blocks, where \u03b6 is a system parameter. We perform security analysis of Tuxedo considering all possible adversarial strategies in a synchronous network with maximum end-to-end delay \u0394 and demonstrate that Tuxedo achieves security equivalent to known results for longest chain PoW Nakamoto consensus. Our prototype implementation of Tuxedo atop Ethereum demonstrates that it can scale \u03c4 without suffering the harmful effects of naive scaling up of \u03c4\/I in existing blockchains<\/jats:p>","DOI":"10.1145\/3491053","type":"journal-article","created":{"date-parts":[[2021,12,15]],"date-time":"2021-12-15T18:32:19Z","timestamp":1639593139000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Tuxedo: Maximizing Smart Contract Computation in PoW Blockchains"],"prefix":"10.1145","volume":"5","author":[{"given":"Sourav","family":"Das","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Champaign, IL, USA"}]},{"given":"Nitin","family":"Awathare","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Bombay, Mumbai, India"}]},{"given":"Ling","family":"Ren","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Champaign, IL, USA"}]},{"given":"Vinay J.","family":"Ribeiro","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Bombay, Mumbai, India"}]},{"given":"Umesh","family":"Bellur","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Bombay, Mumbai, India"}]}],"member":"320","published-online":{"date-parts":[[2021,12,15]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Chainspace: A Sharded Smart Contract Platform. In Network and Distributed System Security Symposium 2018 (NDSS 2018)","author":"Al-Bassam Mustafa","year":"2018","unstructured":"Mustafa Al-Bassam, Alberto Sonnino, Shehar Bano, Dave Hrycyszyn, and George Danezis. 2018. Chainspace: A Sharded Smart Contract Platform. In Network and Distributed System Security Symposium 2018 (NDSS 2018) ."},{"key":"e_1_2_1_2_1","volume-title":"An Efficient Framework for Concurrent Execution of Smart Contracts. CoRR","author":"Anjana Parwat Singh","year":"2018","unstructured":"Parwat Singh Anjana, Sweta Kumari, Sathya Peri, Sachin Rathor, and Archit Somani. 2018. An Efficient Framework for Concurrent Execution of Smart Contracts. CoRR , Vol. abs\/1809.01326 (2018). arxiv: 1809.01326 http:\/\/arxiv.org\/abs\/1809.01326"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40000.2020.00050"},{"key":"e_1_2_1_4_1","volume-title":"11th USENIX Workshop on Offensive Technologies (WOOT 17)","author":"Brasser Ferdinand","year":"2017","unstructured":"Ferdinand Brasser, Urs M\u00fcller, Alexandra Dmitrienko, Kari Kostiainen, Srdjan Capkun, and Ahmad-Reza Sadeghi. 2017. Software grand exposure:SGX cache attacks are practical. In 11th USENIX Workshop on Offensive Technologies (WOOT 17) ."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/EuroSP.2019.00023"},{"key":"e_1_2_1_6_1","volume-title":"Edrax: A Cryptocurrency with Stateless Transaction Validation.","author":"Chepurnoy Alexander","year":"2018","unstructured":"Alexander Chepurnoy, Charalampos Papamanthou, and Yupeng Zhang. 2018. Edrax: A Cryptocurrency with Stateless Transaction Validation. (2018)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2019.23142"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417290"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087835"},{"key":"e_1_2_1_10_1","volume-title":"ZoKrates-Scalable Privacy-Preserving Off-Chain Computations. In IEEE International Conference on Blockchain .","author":"Eberhardt Jacob","year":"2018","unstructured":"Jacob Eberhardt and Stefan Tai. 2018. ZoKrates-Scalable Privacy-Preserving Off-Chain Computations. In IEEE International Conference on Blockchain ."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46803-6_10"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. 819--838","author":"Peter Gavz","year":"2020","unstructured":"Peter Gavz i, Aggelos Kiayias, and Alexander Russell. 2020. Tight consistency bounds for bitcoin. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. 819--838."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-58387-6_24"},{"key":"e_1_2_1_14_1","volume-title":"27th USENIX Security Symposium (USENIX Security 18)","author":"Kalodner Harry","year":"2018","unstructured":"Harry Kalodner, Steven Goldfeder, Xiaoqi Chen, S Matthew Weinberg, and Edward W Felten. 2018. Arbitrum: Scalable, private smart contracts. In 27th USENIX Security Symposium (USENIX Security 18). 1353--1370."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243814"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.000-5"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40000.2020.00068"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978389"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813659"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/PST.2016.7906988"},{"key":"e_1_2_1_21_1","volume-title":"mbox","author":"Satoshi Nakamoto","year":"2008","unstructured":"Satoshi Nakamoto et almbox. 2008. Bitcoin: A peer-to-peer electronic cash system. (2008)."},{"key":"e_1_2_1_22_1","volume-title":"A storage model with self-similar input. Queueing systems","author":"Norros Ilkka","year":"1994","unstructured":"Ilkka Norros. 1994. A storage model with self-similar input. Queueing systems , Vol. 16, 3--4 (1994), 387--396."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-56614-6_22"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2018.23272"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452789"},{"key":"e_1_2_1_27_1","series-title":"Series A (General)","volume-title":"The frequency distribution of the difference between two Poisson variates belonging to different populations. Journal of the Royal Statistical Society","author":"Skellam John G","year":"1946","unstructured":"John G Skellam. 1946. The frequency distribution of the difference between two Poisson variates belonging to different populations. Journal of the Royal Statistical Society. Series A (General) , Vol. 109, Pt 3 (1946), 296--296."},{"key":"e_1_2_1_28_1","unstructured":"Jason Teutsch and Christian Reitwie\u00dfner. 2017. A scalable verification solution for blockchains. (2017)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-57990-6_3"},{"key":"e_1_2_1_30_1","volume-title":"27th USENIX Security Symposium (USENIX Security 18)","author":"Bulck Jo Van","year":"2018","unstructured":"Jo Van Bulck, Marina Minkin, Ofir Weisse, Daniel Genkin, Baris Kasikci, Frank Piessens, Mark Silberstein, Thomas F Wenisch, Yuval Yarom, and Raoul Strackx. 2018. Foreshadow: Extracting the keys to the intel SGX kingdom with transient out-of-order execution. In 27th USENIX Security Symposium (USENIX Security 18). 991--1008."},{"key":"e_1_2_1_31_1","volume-title":"16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19)","author":"Wang Jiaping","year":"2019","unstructured":"Jiaping Wang and Hao Wang. 2019. Monoxide: Scale out Blockchains with Asynchronous Consensus Zones. In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19) . 95--112."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417243"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243853"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96893-3_32"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3491053","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3491053","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:25:06Z","timestamp":1750195506000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3491053"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,14]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,12,14]]}},"alternative-id":["10.1145\/3491053"],"URL":"https:\/\/doi.org\/10.1145\/3491053","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2021,12,14]]},"assertion":[{"value":"2021-12-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}