{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T16:29:46Z","timestamp":1747153786588,"version":"3.40.5"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,5,28]],"date-time":"2022-05-28T00:00:00Z","timestamp":1653696000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,28]],"date-time":"2022-05-28T00:00:00Z","timestamp":1653696000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib Parallel Databases"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we extend the <jats:italic>Multidimensional Byzantine Agreement (MBA) Protocol<\/jats:italic>, a leaderless Byzantine agreement for lists of arbitrary values, into a protocol suitable for wide gossiping networks: <jats:italic>Cob<\/jats:italic>. This generalization allows the consensus process to be run by an incomplete network of nodes provided with (non-synchronized) same-speed clocks. Not all nodes are active in every step, so the network size does not hamper the efficiency, as long as the gossiping broadcast delivers the messages to every node in reasonable time. These network assumptions model more closely real-life communication channels, so Cob may be applicable to a variety of practical problems, such as blockchain platforms implementing sharding. Cob has the same Bernoulli-like distribution that upper-bounds the number of steps as the MBA protocol. We prove its correctness and security assuming a supermajority of honest nodes in the network, and compare its performance with Algorand.<\/jats:p>","DOI":"10.1007\/s10619-022-07410-0","type":"journal-article","created":{"date-parts":[[2022,5,28]],"date-time":"2022-05-28T09:03:03Z","timestamp":1653728583000},"page":"179-216","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Cob: a leaderless protocol for parallel Byzantine agreement in incomplete networks"],"prefix":"10.1007","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3872-7251","authenticated-orcid":false,"given":"Andrea","family":"Flamini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8739-3091","authenticated-orcid":false,"given":"Riccardo","family":"Longo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5159-7252","authenticated-orcid":false,"given":"Alessio","family":"Meneghetti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,5,28]]},"reference":[{"key":"7410_CR1","doi-asserted-by":"crossref","unstructured":"Meneghetti, A., Parise, T., Sala, M., Taufer, D.: A survey on efficient parallelization of blockchain-based smart contracts. AETiC, 3(5) (2019)","DOI":"10.33166\/AETiC.2019.05.002"},{"key":"7410_CR2","unstructured":"Buterin, V.: A next-generation smart contract and decentralized application platform. White Paper, 3(37) (2014)"},{"key":"7410_CR3","doi-asserted-by":"crossref","unstructured":"Zilliqa Team.: The zilliqa technical whitepaper. Accessed 16 Sept 2019 (2017)","DOI":"10.2139\/ssrn.3442330"},{"key":"7410_CR4","unstructured":"EOS IO.: EOS. IO technical white paper. EOS. IO https:\/\/github.com\/EOSIO\/Documentation. Accessed 18 Dec 2017 (2017)"},{"key":"7410_CR5","unstructured":"Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system. Decent. Bus. Rev. (2008)"},{"key":"7410_CR6","unstructured":"Wood, G.: Ethereum: a secure decentralised generalised transaction ledger. Ethereum project yellow paper 151(2014), 1\u201332 (2014)"},{"key":"7410_CR7","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.tcs.2019.02.001","volume":"777","author":"J Chen","year":"2019","unstructured":"Chen, J., Micali, Silvio: Algorand: a secure and efficient distributed ledger. Theoret. Comput. Sci. 777, 155\u2013183 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"7410_CR8","doi-asserted-by":"crossref","unstructured":"Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: a provably secure proof-of-stake blockchain protocol. In: Annual International Cryptology Conference, pp. 357\u2013388. Springer (2017)","DOI":"10.1007\/978-3-319-63688-7_12"},{"key":"7410_CR9","doi-asserted-by":"crossref","unstructured":"Flamini, A., Longo, R., Meneghetti, A.: Multidimensional byzantine agreement in a synchronous setting (2021)","DOI":"10.1007\/s00200-022-00548-5"},{"key":"7410_CR10","doi-asserted-by":"crossref","unstructured":"Miller, A., Xia, Y., Croman, K., Shi, E., Song, D.: The honey badger of bft protocols. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 31\u201342 (2016)","DOI":"10.1145\/2976749.2978399"},{"key":"7410_CR11","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Kelmer, B., Rabin, T.: Asynchronous secure computations with optimal resilience. In: Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 183\u2013192 (1994)","DOI":"10.1145\/197917.198088"},{"key":"7410_CR12","doi-asserted-by":"crossref","unstructured":"Cachin, C., Kursawe, K., Petzold, F., Shoup, V.: Secure and efficient asynchronous broadcast protocols. In: Annual International Cryptology Conference, pp. 524\u2013541. Springer (2001)","DOI":"10.1007\/3-540-44647-8_31"},{"key":"7410_CR13","unstructured":"Cachin, C., Poritz, J.A: Secure intrusion-tolerant replication on the internet. In: Proceedings International Conference on Dependable Systems and Networks, pp. 167\u2013176. IEEE (2002)"},{"key":"7410_CR14","unstructured":"Mostefaoui, A., Moumen, H., Raynal, M.: Signature-free asynchronous byzantine consensus with t< n\/3 and o (n2) messages. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, pp. 2\u20139 (2014)"},{"key":"7410_CR15","doi-asserted-by":"crossref","unstructured":"Duan, S., Reiter, M.K, Zhang, H.: Beat: asynchronous bft made practical. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 2028\u20132041 (2018)","DOI":"10.1145\/3243734.3243812"},{"key":"7410_CR16","doi-asserted-by":"crossref","unstructured":"Guo, B., Lu, Z., Tang, Q., Xu, J., Zhang, Z.: Dumbo: faster asynchronous bft protocols. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 803\u2013818 (2020)","DOI":"10.1145\/3372297.3417262"},{"key":"7410_CR17","first-page":"173","volume":"99","author":"M Castro","year":"1999","unstructured":"Castro, M., Liskov, B.: Practical byzantine fault tolerance. OSDI 99, 173\u2013186 (1999)","journal-title":"Practical byzantine fault tolerance. OSDI"},{"key":"7410_CR18","unstructured":"Stathakopoulou, C., David, T., Vukolic, M.: Mir-BFT: high-throughput BFT for blockchains. arXiv:1906.05552 (2019)"},{"key":"7410_CR19","doi-asserted-by":"crossref","unstructured":"Gupta, S., Hellings, J., Sadoghi, M.: Rcc: resilient concurrent consensus for high-throughput secure transaction processing. In: 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp. 1392\u20131403. IEEE (2021)","DOI":"10.1109\/ICDE51399.2021.00124"},{"key":"7410_CR20","doi-asserted-by":"crossref","unstructured":"Rabin, M.O: Randomized byzantine generals. In: 24th Annual Symposium on Foundations of Computer Science (sfcs 1983), pp. 403\u2013409. IEEE (1983)","DOI":"10.1109\/SFCS.1983.48"},{"key":"7410_CR21","doi-asserted-by":"crossref","unstructured":"Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: scaling byzantine agreements for cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles, pp. 51\u201368 (2017)","DOI":"10.1145\/3132747.3132757"},{"key":"7410_CR22","unstructured":"Cai, S.: Analysis of committee selection mechanism in blockchain. arXiv:1905.05079 (2019)"},{"key":"7410_CR23","unstructured":"Micali, S.: Byzantine agreement, made trivial (2016)"},{"issue":"4","key":"7410_CR24","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539790187084","volume":"26","author":"P Feldman","year":"1997","unstructured":"Feldman, P.: Micali, Silvio: An optimal probabilistic protocol for synchronous byzantine agreement. SIAM J. Comput. 26(4), 873\u2013933 (1997)","journal-title":"SIAM J. Comput."}],"container-title":["Distributed and Parallel Databases"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10619-022-07410-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10619-022-07410-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10619-022-07410-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,4]],"date-time":"2024-05-04T13:07:11Z","timestamp":1714828031000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10619-022-07410-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,28]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["7410"],"URL":"https:\/\/doi.org\/10.1007\/s10619-022-07410-0","relation":{},"ISSN":["0926-8782","1573-7578"],"issn-type":[{"type":"print","value":"0926-8782"},{"type":"electronic","value":"1573-7578"}],"subject":[],"published":{"date-parts":[[2022,5,28]]},"assertion":[{"value":"8 April 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2022","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Missing Open Access funding information has been added in the Funding Note.","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose. The authors have no conflicts of interest to declare that are relevant to the content of this article. The authors have no financial or proprietary interests in any material discussed in this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}