{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T07:35:11Z","timestamp":1777102511377,"version":"3.51.4"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Syst."],"published-print":{"date-parts":[[2026,5,31]]},"abstract":"<jats:p>With the growing interest in blockchains, permissioned approaches to consensus have received increasing attention. Unfortunately, the BFT consensus algorithms that are the backbone of most of these blockchains scale poorly and offer limited throughput. In fact, many state-of-the-art BFT consensus algorithms require a single leader process to receive and validate votes from a quorum of processes and then broadcast the result, which is inherently non-scalable. Recent approaches avoid this bottleneck by using dissemination\/aggregation trees to propagate values and collect and validate votes. However, the use of trees increases the round latency, which limits the throughput for deeper trees. In this article, we propose Kauri, a BFT communication abstraction that sustains high throughput as the system size grows by leveraging a novel pipelining technique to perform scalable dissemination and aggregation on trees. Furthermore, when the number of faults is moderate (arguably the most common case in practice), our construction is able to recover from faults in an optimal number of reconfiguration steps. We implemented and experimentally evaluated Kauri with up to 800 processes. Our results show that Kauri outperforms the throughput of state-of-the-art permissioned blockchain protocols, by up to 58x without compromising latency. Interestingly, in some cases, the parallelization provided by Kauri can also decrease the latency.<\/jats:p>","DOI":"10.1145\/3769423","type":"journal-article","created":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T11:28:46Z","timestamp":1758886126000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Kauri: BFT Consensus with Pipelined Tree-Based Dissemination and Aggregation"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7227-8309","authenticated-orcid":false,"given":"Ray","family":"Neiheiser","sequence":"first","affiliation":[{"name":"DAS, UFSC","place":["Florianopolis, Brazil"]},{"name":"Pietrzak Group, ISTA - Institute of Science and Technology Austria","place":["Florianopolis, Brazil"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6916-2866","authenticated-orcid":false,"given":"Miguel","family":"Matos","sequence":"additional","affiliation":[{"name":"INESC-ID, Universidade de Lisboa Instituto Superior Tecnico","place":["Lisboa, Portugal"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0313-6590","authenticated-orcid":false,"given":"Luis","family":"Rodrigues","sequence":"additional","affiliation":[{"name":"INESC-ID, Universidade de Lisboa Instituto Superior Tecnico","place":["Lisboa, Portugal"]}]}],"member":"320","published-online":{"date-parts":[[2026,4,24]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2008.53"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190538"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070110"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2658994"},{"key":"e_1_3_3_6_2","unstructured":"Zeta Avarikioti Eleftherios Kokoris Kogias Ray Neiheiser and Christos Stefo. 2025. CoBRA: A Universal Strategyproof Confirmation Protocol for Quorum-based Proof-of-Stake Blockchains. arXiv:2503.16783. Retrieved from https:\/\/arxiv.org\/abs\/2503.16783"},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","unstructured":"Kushal Babel Andrey Chursin George Danezis Anastasios Kichidis Lefteris Kokoris-Kogias Arun Koshy Alberto Sonnino and Mingwei Tian. 2024. Mysticeti: Reaching the Limits of Latency with Uncertified DAGs. arXiv:2310.14821. Retrieved from https:\/\/arxiv.org\/abs\/2310.14821","DOI":"10.14722\/ndss.2025.240929"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36177-7_1"},{"key":"e_1_3_3_9_2","unstructured":"Daniel J. Bernstein and Tanja Lange. 2013. Safe Curves: Choosing safe curves for elliptic-curve cryptography. https:\/\/safecurves.cr.yp.to. Accessed 1 December 2014."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2014.43"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-004-0314-9"},{"key":"e_1_3_3_12_2","volume-title":"Introduction to Reliable and Secure Distributed Programming (2nd ed.)","year":"2011","unstructured":"Christian Cachin, Rachid Guerraoui, and Lu\u00eds Rodrigues. 2011. Introduction to Reliable and Secure Distributed Programming (2nd ed.). Springer, Berlin."},{"key":"e_1_3_3_13_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). USENIX Association, USA, 173\u2013186."},{"key":"e_1_3_3_14_2","unstructured":"Bram Cohen and Krzysztof Pietrzak. 2020. The Chia network blockchain. (2020). Retrieved April 18 2022 from https:\/\/www.chia.net\/assets\/ChiaGreenPaper.pdf"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3492321.3519594"},{"key":"e_1_3_3_16_2","unstructured":"Lauren Debter Millie Dent Michael del Castillo Sarah Hansen Jeff Kauflin Chloe Sorvino and Hank Tucker. 2020. c. Retrieved from https:\/\/www.forbes.com\/sites\/michaeldelcastillo\/2020\/02\/19\/blockchain-50\/?sh=77ed26207553"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/42282.42283"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/DSN-W.2018.00053"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132757"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2019.00063"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387540"},{"key":"e_1_3_3_23_2","first-page":"279","volume-title":"Proceedings of the 25th USENIX Security Symposium (USENIX Security 16)","author":"Kogias Eleftherios Kokoris","year":"2016","unstructured":"Eleftherios Kokoris Kogias, Philipp Jovanovic, Nicolas Gailly, Ismail Khoffi, Linus Gasser, and Bryan Ford. 2016. Enhancing bitcoin security and performance with strong consistency via collective signing. In Proceedings of the 25th USENIX Security Symposium (USENIX Security 16). USENIX Association, Austin, TX, 279\u2013296."},{"key":"e_1_3_3_24_2","unstructured":"Eleftherios Kokoris-Kogias. 2019. Robust and scalable consensus for sharded distributed ledgers. Retrieved from https:\/\/eprint.iacr.org\/2019\/676"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.000-5"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3419111.3421272"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.3042392"},{"key":"e_1_3_3_29_2","article-title":"Extended Abstract: HotStuff-2: Optimal Two-Phase Responsive BFT","author":"Malkhi Dahlia","year":"2023","unstructured":"Dahlia Malkhi and Kartik Nayak. 2023. Extended Abstract: HotStuff-2: Optimal Two-Phase Responsive BFT. Cryptology ePrint Archive, Paper 2023\/397. (2023). Retrieved from https:\/\/eprint.iacr.org\/2023\/397","journal-title":"Cryptology ePrint Archive, Paper 2023\/397"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICOIN.2018.8343095"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728270"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415502"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72540-4_13"},{"key":"e_1_3_3_34_2","unstructured":"Stephen Hemminger. 2005. Network emulation with NetEm. Australia\u2019s National Linux Conference 2005 (2005). Retrieved from https:\/\/cir.nii.ac.jp\/crid\/1572543024894323456"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.5070\/SR32159278"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3492321.3519579"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/SRDS.2009.36"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/HASE.2010.19"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-39028-4_9"},{"key":"e_1_3_3_40_2","unstructured":"Bitcoin Core. Optimized C library for EC operations on curve secp256k1. https:\/\/github.com\/bitcoin-core\/secp256k1"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331591"}],"container-title":["ACM Transactions on Computer Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769423","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T06:39:13Z","timestamp":1777099153000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769423"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,24]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5,31]]}},"alternative-id":["10.1145\/3769423"],"URL":"https:\/\/doi.org\/10.1145\/3769423","relation":{},"ISSN":["0734-2071","1557-7333"],"issn-type":[{"value":"0734-2071","type":"print"},{"value":"1557-7333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,24]]},"assertion":[{"value":"2022-05-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-05","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}