[{"article_processing_charge":"No","volume":13950,"day":"01","citation":{"chicago":"Stefo, Christos, Zhuolun Xiang, and Eleftherios Kokoris Kogias. “Executing and Proving over Dirty Ledgers.” In <i>27th International Conference on Financial Cryptography and Data Security</i>, 13950:3–20. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/978-3-031-47754-6_1\">https://doi.org/10.1007/978-3-031-47754-6_1</a>.","mla":"Stefo, Christos, et al. “Executing and Proving over Dirty Ledgers.” <i>27th International Conference on Financial Cryptography and Data Security</i>, vol. 13950, Springer Nature, 2023, pp. 3–20, doi:<a href=\"https://doi.org/10.1007/978-3-031-47754-6_1\">10.1007/978-3-031-47754-6_1</a>.","ista":"Stefo C, Xiang Z, Kokoris Kogias E. 2023. Executing and proving over dirty ledgers. 27th International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 13950, 3–20.","short":"C. Stefo, Z. Xiang, E. Kokoris Kogias, in:, 27th International Conference on Financial Cryptography and Data Security, Springer Nature, 2023, pp. 3–20.","ama":"Stefo C, Xiang Z, Kokoris Kogias E. Executing and proving over dirty ledgers. In: <i>27th International Conference on Financial Cryptography and Data Security</i>. Vol 13950. Springer Nature; 2023:3-20. doi:<a href=\"https://doi.org/10.1007/978-3-031-47754-6_1\">10.1007/978-3-031-47754-6_1</a>","apa":"Stefo, C., Xiang, Z., &#38; Kokoris Kogias, E. (2023). Executing and proving over dirty ledgers. In <i>27th International Conference on Financial Cryptography and Data Security</i> (Vol. 13950, pp. 3–20). Bol, Brac, Croatia: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-47754-6_1\">https://doi.org/10.1007/978-3-031-47754-6_1</a>","ieee":"C. Stefo, Z. Xiang, and E. Kokoris Kogias, “Executing and proving over dirty ledgers,” in <i>27th International Conference on Financial Cryptography and Data Security</i>, Bol, Brac, Croatia, 2023, vol. 13950, pp. 3–20."},"month":"12","conference":{"end_date":"2023-05-05","location":"Bol, Brac, Croatia","start_date":"2023-05-01","name":"FC: Financial Cryptography and Data Security"},"oa_version":"Preprint","publication_identifier":{"eissn":["0302-9743"],"eisbn":["9783031477546"],"issn":["1611-3349"],"isbn":["9783031477539"]},"project":[{"name":"Secure Network and Hardware for Efficient Blockchains","_id":"34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f","grant_number":"F8512"}],"acknowledgement":"Eleftherios Kokoris-Kogias is partially supported by Austrian Science Fund (FWF) grant No: F8512-N.","publication_status":"published","status":"public","author":[{"first_name":"Christos","id":"a20e8902-32b0-11ee-9fa8-b23fa638b793","last_name":"Stefo","full_name":"Stefo, Christos"},{"last_name":"Xiang","full_name":"Xiang, Zhuolun","first_name":"Zhuolun"},{"first_name":"Eleftherios","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","last_name":"Kokoris Kogias","full_name":"Kokoris Kogias, Eleftherios"}],"title":"Executing and proving over dirty ledgers","_id":"14735","abstract":[{"text":"Scaling blockchain protocols to perform on par with the expected needs of Web3.0 has been proven to be a challenging task with almost a decade of research. In the forefront of the current solution is the idea of separating the execution of the updates encoded in a block from the ordering of blocks. In order to achieve this, a new class of protocols called rollups has emerged. Rollups have as input a total ordering of valid and invalid transactions and as output a new valid state-transition.\r\nIf we study rollups from a distributed computing perspective, we uncover that rollups take as input the output of a Byzantine Atomic Broadcast (BAB) protocol and convert it to a State Machine Replication (SMR) protocol. BAB and SMR, however, are considered equivalent as far as distributed computing is concerned and a solution to one can easily be retrofitted to solve the other simply by adding/removing an execution step before the validation of the input.\r\nThis “easy” step of retrofitting an atomic broadcast solution to implement an SMR has, however, been overlooked in practice. In this paper, we formalize the problem and show that after BAB is solved, traditional impossibility results for consensus no longer apply towards an SMR. Leveraging this we propose a distributed execution protocol that allows reduced execution and storage cost per executor (O(log2n/n)) without relaxing the network assumptions of the underlying BAB protocol and providing censorship-resistance. Finally, we propose efficient non-interactive light client constructions that leverage our efficient execution protocols and do not require any synchrony assumptions or expensive ZK-proofs.","lang":"eng"}],"doi":"10.1007/978-3-031-47754-6_1","main_file_link":[{"url":"https://eprint.iacr.org/2022/1554","open_access":"1"}],"intvolume":"     13950","publisher":"Springer Nature","quality_controlled":"1","language":[{"iso":"eng"}],"type":"conference","department":[{"_id":"ElKo"},{"_id":"GradSch"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2023-12-01T00:00:00Z","scopus_import":"1","date_created":"2024-01-08T09:17:38Z","publication":"27th International Conference on Financial Cryptography and Data Security","date_updated":"2024-01-08T09:28:14Z","page":"3-20","oa":1,"alternative_title":["LNCS"],"year":"2023"},{"author":[{"first_name":"Mahsa","full_name":"Bastankhah, Mahsa","last_name":"Bastankhah"},{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Mohammad Ali","last_name":"Maddah-Ali","full_name":"Maddah-Ali, Mohammad Ali"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"},{"full_name":"Svoboda, Jakub","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub","orcid":"0000-0002-1419-3267"},{"orcid":"0009-0001-3676-4809","last_name":"Yeo","full_name":"Yeo, Michelle X","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"title":"R2: Boosting liquidity in payment channel networks with online admission control","_id":"14736","abstract":[{"lang":"eng","text":"Payment channel networks (PCNs) are a promising technology to improve the scalability of cryptocurrencies. PCNs, however, face the challenge that the frequent usage of certain routes may deplete channels in one direction, and hence prevent further transactions. In order to reap the full potential of PCNs, recharging and rebalancing mechanisms are required to provision channels, as well as an admission control logic to decide which transactions to reject in case capacity is insufficient. This paper presents a formal model of this optimisation problem. In particular, we consider an online algorithms perspective, where transactions arrive over time in an unpredictable manner. Our main contributions are competitive online algorithms which come with provable guarantees over time. We empirically evaluate our algorithms on randomly generated transactions to compare the average performance of our algorithms to our theoretical bounds. We also show how this model and approach differs from related problems in classic communication networks."}],"doi":"10.1007/978-3-031-47754-6_18","publication_identifier":{"eisbn":["9783031477546"],"issn":["0302-9743"],"isbn":["9783031477539"],"eissn":["1611-3349"]},"project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020"}],"publication_status":"published","acknowledgement":"Supported by the German Federal Ministry of Education and Research (BMBF), grant 16KISK020K (6G-RIC), 2021–2025, and ERC CoG 863818 (ForM-SMArt).","status":"public","ec_funded":1,"day":"01","citation":{"chicago":"Bastankhah, Mahsa, Krishnendu Chatterjee, Mohammad Ali Maddah-Ali, Stefan Schmid, Jakub Svoboda, and Michelle X Yeo. “R2: Boosting Liquidity in Payment Channel Networks with Online Admission Control.” In <i>27th International Conference on Financial Cryptography and Data Security</i>, 13950:309–25. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/978-3-031-47754-6_18\">https://doi.org/10.1007/978-3-031-47754-6_18</a>.","mla":"Bastankhah, Mahsa, et al. “R2: Boosting Liquidity in Payment Channel Networks with Online Admission Control.” <i>27th International Conference on Financial Cryptography and Data Security</i>, vol. 13950, Springer Nature, 2023, pp. 309–25, doi:<a href=\"https://doi.org/10.1007/978-3-031-47754-6_18\">10.1007/978-3-031-47754-6_18</a>.","ieee":"M. Bastankhah, K. Chatterjee, M. A. Maddah-Ali, S. Schmid, J. Svoboda, and M. X. Yeo, “R2: Boosting liquidity in payment channel networks with online admission control,” in <i>27th International Conference on Financial Cryptography and Data Security</i>, Bol, Brac, Croatia, 2023, vol. 13950, pp. 309–325.","apa":"Bastankhah, M., Chatterjee, K., Maddah-Ali, M. A., Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2023). R2: Boosting liquidity in payment channel networks with online admission control. In <i>27th International Conference on Financial Cryptography and Data Security</i> (Vol. 13950, pp. 309–325). Bol, Brac, Croatia: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-47754-6_18\">https://doi.org/10.1007/978-3-031-47754-6_18</a>","ama":"Bastankhah M, Chatterjee K, Maddah-Ali MA, Schmid S, Svoboda J, Yeo MX. R2: Boosting liquidity in payment channel networks with online admission control. In: <i>27th International Conference on Financial Cryptography and Data Security</i>. Vol 13950. Springer Nature; 2023:309-325. doi:<a href=\"https://doi.org/10.1007/978-3-031-47754-6_18\">10.1007/978-3-031-47754-6_18</a>","short":"M. Bastankhah, K. Chatterjee, M.A. Maddah-Ali, S. Schmid, J. Svoboda, M.X. Yeo, in:, 27th International Conference on Financial Cryptography and Data Security, Springer Nature, 2023, pp. 309–325.","ista":"Bastankhah M, Chatterjee K, Maddah-Ali MA, Schmid S, Svoboda J, Yeo MX. 2023. R2: Boosting liquidity in payment channel networks with online admission control. 27th International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 13950, 309–325."},"month":"12","conference":{"name":"FC: Financial Cryptography and Data Security","location":"Bol, Brac, Croatia","start_date":"2023-05-01","end_date":"2023-05-05"},"oa_version":"None","article_processing_charge":"No","volume":13950,"alternative_title":["LNCS"],"year":"2023","publication":"27th International Conference on Financial Cryptography and Data Security","date_updated":"2025-07-14T09:10:01Z","page":"309-325","department":[{"_id":"KrCh"},{"_id":"KrPi"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2023-12-01T00:00:00Z","date_created":"2024-01-08T09:30:22Z","intvolume":"     13950","publisher":"Springer Nature","quality_controlled":"1","language":[{"iso":"eng"}],"type":"conference"}]