{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,20]],"date-time":"2026-10-20T12:38:01Z","timestamp":1792499881557,"version":"4.5.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T00:00:00Z","timestamp":1718668800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"PRODIGY","award":["TED2021-132464B-I00, and MCIN\/AEI\/10.13039\/501100011033\/"],"award-info":[{"award-number":["TED2021-132464B-I00, and MCIN\/AEI\/10.13039\/501100011033\/"]}]},{"name":"European Union NextGenerationEU\/PRTR\u2014by DECO","award":["PID2022-138072OB-I00, and MCIN\/AEI\/10.13039\/501100011033"],"award-info":[{"award-number":["PID2022-138072OB-I00, and MCIN\/AEI\/10.13039\/501100011033"]}]},{"name":"Nomadic Labs and the Tezos Foundation"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Distrib. Ledger Technol."],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>\n            Blockchain technologies are facing a scalability challenge, which must be overcome to guarantee a wider adoption of the technology. This scalability issue is due to the use of consensus algorithms to guarantee the total order of the chain of blocks (and of the transactions within each block). However, total order is often not fully necessary, since important advanced applications of smart-contracts do not require a total order among\n            <jats:italic>all<\/jats:italic>\n            operations. A much higher scalability can potentially be achieved if a more relaxed order (instead of a total order) can be exploited.\n          <\/jats:p>\n          <jats:p>\n            In this article, we propose a novel distributed concurrent data type,\n            <jats:italic>Setchain<\/jats:italic>\n            , which significantly improves scalability. A Setchain implements a\n            <jats:italic>grow-only set<\/jats:italic>\n            whose elements are not ordered, unlike conventional blockchain operations. When convenient, the Setchain allows forcing a synchronization barrier that assigns permanently an epoch number to a subset of the latest elements added, agreed by consensus. Therefore, two operations in the same epoch are not ordered, while two operations in different epochs are ordered by their respective epoch number. We present different Byzantine-tolerant implementations of Setchain, prove their correctness, and report on an empirical evaluation of a prototype implementation. Our results show that Setchain is orders of magnitude faster than consensus-based ledgers, since it implements grow-only sets with epoch synchronization instead of total order.\n          <\/jats:p>\n          <jats:p>\n            Since the Setchain barriers can be synchronized with the underlying blockchain, Setchain objects can be used as a\n            <jats:italic>sidechain<\/jats:italic>\n            to implement many decentralized solutions with much faster operations than direct implementations on top of blockchains.\n          <\/jats:p>\n          <jats:p>Finally, we also present an algorithm that encompasses into a single process the combined behavior of the Byzantine servers, which simplifies correctness proofs by encoding the general attacker in a concrete implementation.<\/jats:p>","DOI":"10.1145\/3626963","type":"journal-article","created":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T15:25:03Z","timestamp":1697210703000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Improving Blockchain Scalability with the Setchain Data-Type"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2329-3769","authenticated-orcid":false,"given":"Margarita","family":"Capretto","sequence":"first","affiliation":[{"name":"IMDEA Software Inst., Pozuelo de Alarcon Spain and Universidad Polit\u00e9cnica de Madrid, Pozuelo de Alarcon, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4691-5831","authenticated-orcid":false,"given":"Mart\u00edn","family":"Ceresa","sequence":"additional","affiliation":[{"name":"IMDEA Software Inst., Pozuelo de Alarcon, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6501-2377","authenticated-orcid":false,"given":"Antonio","family":"Fndez Anta","sequence":"additional","affiliation":[{"name":"IMDEA Networks Inst., Leganes, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3795-3000","authenticated-orcid":false,"given":"Antonio","family":"Russo","sequence":"additional","affiliation":[{"name":"IMDEA Networks Inst., Leganes, Spain and Universidad Carlos III de Madrid, Leganes, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3927-4773","authenticated-orcid":false,"given":"C\u00e9sar","family":"S\u00e1nchez","sequence":"additional","affiliation":[{"name":"IMDEA Software Inst., Pozuelo de Alarcon, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,18]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2014.36"},{"key":"e_1_3_3_3_2","first-page":"781","volume-title":"Proceedings of the USENIX Sec.\u201914","author":"Ben-Sasson Eli","year":"2014","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. 2014. Succinct non-interactive Zero Knowledge for a von Neumann architecture. In Proceedings of the USENIX Sec.\u201914. USENIX, 781\u2013796. Retrieved fromhttps:\/\/www.usenix.org\/conference\/usenixsecurity14\/technical-sessions\/presentation\/ben-sasson"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90054-X"},{"key":"e_1_3_3_5_2","article-title":"Improving blockchain scalability with setchain data-type","author":"Capretto Margarita","year":"2022","unstructured":"Margarita Capretto, Mart\u00edn Ceresa, Antonio Fern\u00e1ndez Anta, Antonio Russo, and C\u00e9sar S\u00e1nchez. 2022. Improving blockchain scalability with setchain data-type. arXiv (2022).","journal-title":"arXiv"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226647"},{"key":"e_1_3_3_7_2","first-page":"2:1\u20132:19","volume-title":"Proceedings of the FAB\u201921","author":"Cholvi Vicent","year":"2021","unstructured":"Vicent Cholvi, Antonio Fern\u00e1ndez Anta, Chryssis Georgiou, Nicolas Nicolaou, Michel Raynal, and Antonio Russo. 2021. Byzantine-tolerant distributed grow-only sets: Specification and applications. In Proceedings of the FAB\u201921. 2:1\u20132:19."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00087"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","unstructured":"Flaviu Cristian Houtan Aghili H. Raymond Strong and Danny Dolev. 1995. Atomic broadcast: from simple message diffusion to Byzantine agreement. Information and Computation 118 1 (1995) 158\u2013179. DOI:10.1006\/inco.1995.1060","DOI":"10.1006\/inco.1995.1060"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53357-4_8"},{"key":"e_1_3_3_11_2","first-page":"910","article-title":"Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability","author":"Daian Philip","year":"2020","unstructured":"Philip Daian, Steven Goldfeder, T. Kell, Yunqi Li, X. Zhao, Iddo Bentov, Lorenz Breidenbach, and A. Juels. 2020. Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In Proceedings of the S&P\u201920 (2020), 910\u2013927.","journal-title":"Proceedings of the S&P\u201920"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319889"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1041680.1041682"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/2851099"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-01807-7"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3232679.3232691"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331589"},{"key":"e_1_3_3_19_2","unstructured":"Maxim Jourenko Kanta Kurazumi Mario Larangeira and Keisuke Tanaka. 2019. SoK: A taxonomy for layer-2 scalability related protocols for cryptocurrencies. Cryptology ePrint Archive Paper 2019\/352."},{"key":"e_1_3_3_20_2","first-page":"1353","volume-title":"Proceedings of the 27th USENIX Security Symposium","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 Proceedings of the 27th USENIX Security Symposium. USENIX Assoc., 1353\u20131370. Retrieved fromhttps:\/\/www.usenix.org\/conference\/usenixsecurity18\/presentation\/kalodner"},{"key":"e_1_3_3_21_2","unstructured":"Jae Kwon and Ethan Buchman. 2019. Cosmos whitepaper. (2019)."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243853"},{"key":"e_1_3_3_23_2","unstructured":"Satoshi Nakamoto. 2009. Bitcoin: A Peer-To-Peer Electronic Cash System."},{"key":"e_1_3_3_24_2","unstructured":"Joseph Poon and Thaddeus Dryja. 2016. The Bitcoin Lightning Network: Scalable Off-Chain Instant Payments."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","unstructured":"Michel Raynal. 2018. Fault-Tolerant Message-Passing Distributed Systems: An Algorithmic Approach. Springer Cham. DOI:10.1007\/978-3-319-94141-7","DOI":"10.1007\/978-3-319-94141-7"},{"key":"e_1_3_3_26_2","unstructured":"Robinson Dan and Konstantopoulos Georgios. 2020. Ethereum is a Dark Forest. (2020). Retrieved from https:\/\/medium.com\/@danrobinson\/ethereum-is-a-dark-forest-ecc5f0505dff"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/BLOC.2019.8751476"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3196494.3201584"},{"key":"e_1_3_3_29_2","unstructured":"Marc Shapiro Nuno Pregui\u00e7a Carlos Baquero and Marek Zawirski. 2011. Convergent and commutative replicated data types. Bulletin- European Association for Theoretical Computer Science 104 (June 2011) 67\u201388. Retrieved from https:\/\/hal.inria.fr\/hal-00932833"},{"key":"e_1_3_3_30_2","article-title":"Smart contracts: Building blocks for digital markets","volume":"16","author":"Szabo Nick","year":"1996","unstructured":"Nick Szabo. 1996. Smart contracts: Building blocks for digital markets. Extropy 16 (1996).","journal-title":"Extropy"},{"key":"e_1_3_3_31_2","unstructured":"The ZeroMQ authors. 2021. ZeroMQ. (2021). Retrieved from https:\/\/zeromq.org"},{"key":"e_1_3_3_32_2","first-page":"1343","volume-title":"Proc of USENIX Sec.\u201921","author":"Torres Christof Ferreira","year":"2021","unstructured":"Christof Ferreira Torres, Ramiro Camino, and Radu State. 2021. Frontrunner jones and the raiders of the dark Forest: An empirical study of frontrunning on the Ethereum blockchain. In Proc of USENIX Sec.\u201921. 1343\u20131359. Retrieved from https:\/\/www.usenix.org\/conference\/usenixsecurity21\/presentation\/torres"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3474124.3474184"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/Blockchain.2019.00058"},{"key":"e_1_3_3_35_2","unstructured":"Gavin Wood. 2014. Ethereum: A secure decentralised generalised transaction ledger. Ethereum Project Yellow Paper 151."},{"key":"e_1_3_3_36_2","unstructured":"Gavin Wood. 2016. Polkadot: Vision for a Heterogeneous Multi-chain Framework. White Paper."},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476283"}],"container-title":["Distributed Ledger Technologies: Research and Practice"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626963","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626963","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:44:16Z","timestamp":1750290256000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626963"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,18]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3626963"],"URL":"https:\/\/doi.org\/10.1145\/3626963","relation":{},"ISSN":["2769-6480","2769-6480"],"issn-type":[{"value":"2769-6480","type":"print"},{"value":"2769-6480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,18]]},"assertion":[{"value":"2022-12-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-22","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}