{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T07:50:36Z","timestamp":1774684236328,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T00:00:00Z","timestamp":1684368000000},"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":["ACM Trans. Internet Technol."],"published-print":{"date-parts":[[2023,5,31]]},"abstract":"<jats:p>\n            Blockchain sharding splits a blockchain into several shards where consensus is reached at the shard level rather than over the entire blockchain. It improves transaction throughput and reduces the computational resources required of individual nodes. But a derivation of trustworthy consensus within a shard becomes an issue as the longest chain based mechanisms used in conventional blockchains can no longer be used. Instead, a vote-based consensus mechanism must be employed. However, existing vote-based Byzantine fault tolerance consensus protocols do not offer sufficient security guarantees for sharded blockchains. First, when used to support consensus where only one block is allowed at a time (binary consensus), these protocols are susceptible to progress-hindering attacks (i.e., unable to reach a consensus). Second, when used to support a stronger type of consensus where multiple concurrent blocks are allowed (strong consensus), their tolerance of adversary nodes is low. This article proposes a new consensus protocol to address all these issues. We call the new protocol\n            <jats:italic>MWPoW<\/jats:italic>\n            +, as its basic framework is based on the existing Multiple Winners Proof of Work (MWPoW) protocol but includes new mechanisms to address the issues mentioned previously. MWPoW+ is a vote-based protocol for strong consensus, asynchronous in consensus derivation but synchronous in communication. We prove that it can tolerate up to\n            <jats:italic>f<\/jats:italic>\n            &lt;\n            <jats:italic>n<\/jats:italic>\n            \/2 adversary nodes in a n-node system as if using a binary consensus protocol and does not suffer from progress-hindering attacks.\n          <\/jats:p>","DOI":"10.1145\/3584020","type":"journal-article","created":{"date-parts":[[2023,2,13]],"date-time":"2023-02-13T12:48:43Z","timestamp":1676292523000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["MWPoW+: A Strong Consensus Protocol for Intra-Shard Consensus in Blockchain Sharding"],"prefix":"10.1145","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8490-5285","authenticated-orcid":false,"given":"Yibin","family":"Xu","sequence":"first","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8461-1471","authenticated-orcid":false,"given":"Jianhua","family":"Shao","sequence":"additional","affiliation":[{"name":"Cardiff University, Cardiff, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6244-6970","authenticated-orcid":false,"given":"Tijs","family":"Slaats","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0241-7729","authenticated-orcid":false,"given":"Boris","family":"D\u00fcdder","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2023,5,18]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/844128.844130"},{"key":"e_1_3_1_3_2","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1109\/Blockchain.2019.00044","volume-title":"Proceedings of the 2019 IEEE International Conference on Blockchain (Blockchain)","author":"Amiri Mohammad Javad","year":"2019","unstructured":"Mohammad Javad Amiri, Divyakant Agrawal, and Amr El Abbadi. 2019. On sharding permissioned blockchains. In Proceedings of the 2019 IEEE International Conference on Blockchain (Blockchain). IEEE, Los Alamitos, CA, 282\u2013285."},{"key":"e_1_3_1_4_2","unstructured":"Adam Back. 2002. Hashcash: A Denial of Service Counter-Measure. Retrieved February 21 2023 from http:\/\/hashcash.org\/papers\/hashcash.pdf."},{"key":"e_1_3_1_5_2","first-page":"173","volume-title":"Proceedings of the 3rd Symposium on Operating Systems Design and Implementation (OSDI\u201999)","author":"Castro Miguel","year":"1999","unstructured":"Miguel Castro and Barbara Liskov. 1999. Practical Byzantine fault tolerance. In Proceedings of the 3rd Symposium on Operating Systems Design and Implementation (OSDI\u201999). 173\u2013186."},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/571637.571640"},{"key":"e_1_3_1_7_2","article-title":"Centrally banked cryptocurrencies","author":"Danezis George","year":"2015","unstructured":"George Danezis and Sarah Meiklejohn. 2015. Centrally banked cryptocurrencies. arXiv preprint arXiv:1505.06895 (2015).","journal-title":"arXiv preprint arXiv:1505.06895"},{"key":"e_1_3_1_8_2","first-page":"426","volume-title":"Proceedings of the Annual International Cryptology Conference","author":"Dwork Cynthia","year":"2003","unstructured":"Cynthia Dwork, Andrew Goldberg, and Moni Naor. 2003. On memory-bound functions for fighting spam. In Proceedings of the Annual International Cryptology Conference. 426\u2013444."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872066"},{"key":"e_1_3_1_10_2","first-page":"31","volume-title":"Proceedings of the 25th Annual ACM Symposium on Theory of Computing","author":"Garay Juan A.","year":"1993","unstructured":"Juan A. Garay and Yoram Moses. 1993. Fully polynomial Byzantine agreement in t + 1 rounds. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing. 31\u201341."},{"key":"e_1_3_1_11_2","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1109\/Allerton.2011.6120248","volume-title":"Proceedings of the 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton\u201911)","author":"Goodrich Michael T.","year":"2011","unstructured":"Michael T. Goodrich and Michael Mitzenmacher. 2011. Invertible Bloom lookup tables. In Proceedings of the 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton\u201911). IEEE, Los Alamitos, CA, 792\u2013799."},{"key":"e_1_3_1_12_2","first-page":"445","volume-title":"Proceedings of the Annual International Cryptology Conference","author":"Katz Jonathan","year":"2006","unstructured":"Jonathan Katz and Chiu-Yuen Koo. 2006. On expected constant-round protocols for Byzantine agreement. In Proceedings of the Annual International Cryptology Conference. 445\u2013462."},{"key":"e_1_3_1_13_2","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1109\/SP.2018.000-5","volume-title":"Proceedings of the 2018 IEEE Symposium on Security and Privacy (SP\u201918)","author":"Kokoris-Kogias Eleftherios","year":"2018","unstructured":"Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ewa Syta, and Bryan Ford. 2018. Omniledger: A secure, scale-out, decentralized ledger via sharding. In Proceedings of the 2018 IEEE Symposium on Security and Privacy (SP\u201918). IEEE, Los Alamitos, CA, 583\u2013598."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/356989.357007"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/279227.279229"},{"key":"e_1_3_1_16_2","first-page":"1","volume-title":"Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI\u201904)","author":"Li Jinyuan","year":"2004","unstructured":"Jinyuan Li, Maxwell N. Krohn, David Mazieres, and Dennis E. Shasha. 2004. Secure untrusted data repository (SUNDR). In Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI\u201904). 1\u20139."},{"key":"e_1_3_1_17_2","unstructured":"Julian Loss and Tal Moran. 2018. Combining asynchronous and synchronous Byzantine agreement: The best of both worlds. Cryptology ePrint Archive Report 2018\/235. https:\/\/eprint.iacr.org\/2018\/235."},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978389"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/358161.358167"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90011-6"},{"key":"e_1_3_1_21_2","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1007\/978-3-319-67816-0_24","volume-title":"Data Privacy Management, Cryptocurrencies and Blockchain Technology","author":"Ozisik A. Pinar","year":"2017","unstructured":"A. Pinar Ozisik, Gavin Andresen, George Bissias, Amir Houmansadr, and Brian Levine. 2017. Graphene: A new protocol for block propagation using set reconciliation. In Data Privacy Management, Cryptocurrencies and Blockchain Technology. Springer, 420\u2013428."},{"key":"e_1_3_1_22_2","article-title":"Practical synchronous Byzantine consensus","author":"Ren Ling","year":"2017","unstructured":"Ling Ren, Kartik Nayak, Ittai Abraham, and Srinivas Devadas. 2017. Practical synchronous Byzantine consensus. arXiv preprint arXiv:1704.02397 (2017).","journal-title":"arXiv preprint arXiv:1704.02397"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/502059.502037"},{"key":"e_1_3_1_24_2","doi-asserted-by":"crossref","unstructured":"Fahad Saleh. 2021. Blockchain without waste: Proof-of-stake. Review of Financial Studies 34 3 (2021) 1156\u20131190.","DOI":"10.1093\/rfs\/hhaa075"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/98163.98167"},{"key":"e_1_3_1_26_2","article-title":"Replay attacks and defenses against cross-shard consensus in sharded distributed ledgers","author":"Sonnino Alberto","year":"2019","unstructured":"Alberto Sonnino, Shehar Bano, Mustafa Al-Bassam, and George Danezis. 2019. Replay attacks and defenses against cross-shard consensus in sharded distributed ledgers. arXiv preprint arXiv:1901.11218 (2019).","journal-title":"arXiv preprint arXiv:1901.11218"},{"key":"e_1_3_1_27_2","volume-title":"Guaranteed-TX: The Exploration of a Guaranteed Cross-Shard Transaction Execution Protocol for Ethereum 2.0.","author":"Wels S. J.","year":"2019","unstructured":"S. J. Wels. 2019. Guaranteed-TX: The Exploration of a Guaranteed Cross-Shard Transaction Execution Protocol for Ethereum 2.0.Master\u2019s Thesis. University of Twente."},{"key":"e_1_3_1_28_2","article-title":"MWPoW: Multiple Winners Proof of Work Protocol, a decentralisation strengthened fast-confirm blockchain protocol","volume":"2019","author":"Xu Yibin","year":"2019","unstructured":"Yibin Xu and Yangyu Huang. 2019. MWPoW: Multiple Winners Proof of Work Protocol, a decentralisation strengthened fast-confirm blockchain protocol. Security and Communication Networks 2019 (2019), Article 3674274.","journal-title":"Security and Communication Networks"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341105.3374069"},{"key":"e_1_3_1_30_2","doi-asserted-by":"crossref","unstructured":"Yibin Xu Yangyu Huang Jianhua Shao and George Theodorakopoulos. 2020. A flexible n\/2 adversary node resistant and halting recoverable blockchain sharding protocol. Concurrency and Computation: Practice and Experience 32 19 (2020) e5773.","DOI":"10.1002\/cpe.5773"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3563506"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243853"}],"container-title":["ACM Transactions on Internet Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584020","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3584020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:05Z","timestamp":1750183685000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,18]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,5,31]]}},"alternative-id":["10.1145\/3584020"],"URL":"https:\/\/doi.org\/10.1145\/3584020","relation":{},"ISSN":["1533-5399","1557-6051"],"issn-type":[{"value":"1533-5399","type":"print"},{"value":"1557-6051","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,18]]},"assertion":[{"value":"2021-02-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-31","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}