[{"publication_status":"published","year":"2023","quality_controlled":"1","intvolume":"     13950","conference":{"name":"FC: Financial Cryptography and Data Security","end_date":"2023-05-05","start_date":"2023-05-01","location":"Bol, Brac, Croatia"},"alternative_title":["LNCS"],"date_published":"2023-12-01T00:00:00Z","article_processing_charge":"No","fulldoi":"https://doi.org/10.1007/978-3-031-47754-6_1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2022/1554"}],"day":"01","corr_author":"1","oa":1,"external_id":{"isi":["001150222600001"]},"publisher":"Springer Nature","month":"12","department":[{"_id":"ElKo"},{"_id":"GradSch"}],"isi":1,"volume":13950,"doi":"10.1007/978-3-031-47754-6_1","title":"Executing and proving over dirty ledgers","_id":"14735","date_created":"2024-01-08T09:17:38Z","author":[{"first_name":"Christos","last_name":"Stefo","id":"a20e8902-32b0-11ee-9fa8-b23fa638b793","full_name":"Stefo, Christos"},{"last_name":"Xiang","first_name":"Zhuolun","full_name":"Xiang, Zhuolun"},{"first_name":"Eleftherios","last_name":"Kokoris Kogias","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","full_name":"Kokoris Kogias, Eleftherios"}],"status":"public","type":"conference","oa_version":"Preprint","abstract":[{"lang":"eng","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."}],"citation":{"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>","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>.","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.","short":"C. Stefo, Z. Xiang, E. Kokoris Kogias, in:, 27th International Conference on Financial Cryptography and Data Security, Springer Nature, 2023, pp. 3–20.","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.","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>.","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>"},"page":"3-20","project":[{"grant_number":"F8512","name":"Security and Privacy by Design for Complex Systems","_id":"34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f"}],"date_updated":"2025-09-09T14:07:16Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication":"27th International Conference on Financial Cryptography and Data Security","scopus_import":"1","acknowledgement":"Eleftherios Kokoris-Kogias is partially supported by Austrian Science Fund (FWF) grant No: F8512-N.","publication_identifier":{"eissn":["0302-9743"],"eisbn":["9783031477546"],"isbn":["9783031477539"],"issn":["1611-3349"]},"language":[{"iso":"eng"}]},{"volume":10000,"doi":"10.1007/978-3-319-91908-9_22","series_title":"LNCS","publisher":"Springer Nature","department":[{"_id":"ToHe"}],"month":"10","day":"05","oa":1,"fulldoi":"https://doi.org/10.1007/978-3-319-91908-9_22","main_file_link":[{"url":"https://doi.org/10.1007/978-3-319-91908-9_22","open_access":"1"}],"alternative_title":["Lecture Notes in Computer Science"],"date_published":"2019-10-05T00:00:00Z","article_processing_charge":"No","publication_status":"published","year":"2019","quality_controlled":"1","intvolume":"     10000","editor":[{"last_name":"Steffen","first_name":"Bernhard","full_name":"Steffen, Bernhard"},{"first_name":"Gerhard","last_name":"Woeginger","full_name":"Woeginger, Gerhard"}],"ddc":["000"],"language":[{"iso":"eng"}],"publication_identifier":{"eisbn":["9783319919089"],"isbn":["9783319919072"],"issn":["1611-3349"],"eissn":["0302-9743"]},"acknowledgement":"This research was supported in part by the Austrian Science Fund (FWF) under grants S11402-N23(RiSE/SHiNE) and Z211-N23 (Wittgenstein Award). This research has received funding from the Sino-Danish Basic Research Centre, IDEA4CPS, funded by the Danish National Research Foundation and the National Science Foundation, China, the Innovation Fund Denmark centre DiCyPS, as well as the ERC Advanced Grant LASSO.","publication":"Computing and Software Science","scopus_import":"1","date_updated":"2026-06-18T19:21:28Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"452-477","citation":{"mla":"Alur, Rajeev, et al. “Continuous-Time Models for System Design and Analysis.” <i>Computing and Software Science</i>, edited by Bernhard Steffen and Gerhard Woeginger, vol. 10000, Springer Nature, 2019, pp. 452–77, doi:<a href=\"https://doi.org/10.1007/978-3-319-91908-9_22\">10.1007/978-3-319-91908-9_22</a>.","ama":"Alur R, Giacobbe M, Henzinger TA, Larsen KG, Mikučionis M. Continuous-time models for system design and analysis. In: Steffen B, Woeginger G, eds. <i>Computing and Software Science</i>. Vol 10000. LNCS. Springer Nature; 2019:452-477. doi:<a href=\"https://doi.org/10.1007/978-3-319-91908-9_22\">10.1007/978-3-319-91908-9_22</a>","ista":"Alur R, Giacobbe M, Henzinger TA, Larsen KG, Mikučionis M. 2019.Continuous-time models for system design and analysis. In: Computing and Software Science. Lecture Notes in Computer Science, vol. 10000, 452–477.","short":"R. Alur, M. Giacobbe, T.A. Henzinger, K.G. Larsen, M. Mikučionis, in:, B. Steffen, G. Woeginger (Eds.), Computing and Software Science, Springer Nature, 2019, pp. 452–477.","ieee":"R. Alur, M. Giacobbe, T. A. Henzinger, K. G. Larsen, and M. Mikučionis, “Continuous-time models for system design and analysis,” in <i>Computing and Software Science</i>, vol. 10000, B. Steffen and G. Woeginger, Eds. Springer Nature, 2019, pp. 452–477.","chicago":"Alur, Rajeev, Mirco Giacobbe, Thomas A Henzinger, Kim G. Larsen, and Marius Mikučionis. “Continuous-Time Models for System Design and Analysis.” In <i>Computing and Software Science</i>, edited by Bernhard Steffen and Gerhard Woeginger, 10000:452–77. LNCS. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-319-91908-9_22\">https://doi.org/10.1007/978-3-319-91908-9_22</a>.","apa":"Alur, R., Giacobbe, M., Henzinger, T. A., Larsen, K. G., &#38; Mikučionis, M. (2019). Continuous-time models for system design and analysis. In B. Steffen &#38; G. Woeginger (Eds.), <i>Computing and Software Science</i> (Vol. 10000, pp. 452–477). Springer Nature. <a href=\"https://doi.org/10.1007/978-3-319-91908-9_22\">https://doi.org/10.1007/978-3-319-91908-9_22</a>"},"project":[{"_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S11402-N23"},{"grant_number":"Z211","name":"Formal methods for the design and analysis of complex systems","call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425"}],"oa_version":"Published Version","type":"book_chapter","abstract":[{"text":"We illustrate the ingredients of the state-of-the-art of model-based approach for the formal design and verification of cyber-physical systems. To capture the interaction between a discrete controller and its continuously evolving environment, we use the formal models of timed and hybrid automata. We explain the steps of modeling and verification in the tools Uppaal and SpaceEx using a case study based on a dual-chamber implantable pacemaker monitoring a human heart. We show how to design a model as a composition of components, how to construct models at varying levels of detail, how to establish that one model is an abstraction of another, how to specify correctness requirements using temporal logic, and how to verify that a model satisfies a logical requirement.","lang":"eng"}],"title":"Continuous-time models for system design and analysis","_id":"7453","date_created":"2020-02-05T10:51:44Z","status":"public","author":[{"full_name":"Alur, Rajeev","last_name":"Alur","first_name":"Rajeev"},{"id":"3444EA5E-F248-11E8-B48F-1D18A9856A87","first_name":"Mirco","last_name":"Giacobbe","orcid":"0000-0001-8180-0904","full_name":"Giacobbe, Mirco"},{"first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724"},{"last_name":"Larsen","first_name":"Kim G.","full_name":"Larsen, Kim G."},{"full_name":"Mikučionis, Marius","first_name":"Marius","last_name":"Mikučionis"}]},{"date_updated":"2024-11-18T10:22:43Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"143-154","citation":{"ieee":"A. M. Bronstein and M. M. Bronstein, “Regularized partial matching of rigid shapes,” in <i>10th European Conference on Computer Vision</i>, Marseille, France, 2008, vol. 5303, pp. 143–154.","short":"A.M. Bronstein, M.M. Bronstein, in:, 10th European Conference on Computer Vision, Springer Berlin Heidelberg, 2008, pp. 143–154.","ista":"Bronstein AM, Bronstein MM. 2008. Regularized partial matching of rigid shapes. 10th European Conference on Computer Vision. ECCV: European Conference on Computer Vision, LNCS, vol. 5303, 143–154.","ama":"Bronstein AM, Bronstein MM. Regularized partial matching of rigid shapes. In: <i>10th European Conference on Computer Vision</i>. Vol 5303. Springer Berlin Heidelberg; 2008:143-154. doi:<a href=\"https://doi.org/10.1007/978-3-540-88688-4_11\">10.1007/978-3-540-88688-4_11</a>","mla":"Bronstein, Alex M., and Michael M. Bronstein. “Regularized Partial Matching of Rigid Shapes.” <i>10th European Conference on Computer Vision</i>, vol. 5303, Springer Berlin Heidelberg, 2008, pp. 143–54, doi:<a href=\"https://doi.org/10.1007/978-3-540-88688-4_11\">10.1007/978-3-540-88688-4_11</a>.","apa":"Bronstein, A. M., &#38; Bronstein, M. M. (2008). Regularized partial matching of rigid shapes. In <i>10th European Conference on Computer Vision</i> (Vol. 5303, pp. 143–154). Marseille, France: Springer Berlin Heidelberg. <a href=\"https://doi.org/10.1007/978-3-540-88688-4_11\">https://doi.org/10.1007/978-3-540-88688-4_11</a>","chicago":"Bronstein, Alex M., and Michael M. Bronstein. “Regularized Partial Matching of Rigid Shapes.” In <i>10th European Conference on Computer Vision</i>, 5303:143–54. Springer Berlin Heidelberg, 2008. <a href=\"https://doi.org/10.1007/978-3-540-88688-4_11\">https://doi.org/10.1007/978-3-540-88688-4_11</a>."},"extern":"1","abstract":[{"text":"Matching of rigid shapes is an important problem in numerous applications across the boundary of computer vision, pattern recognition and computer graphics communities. A particularly challenging setting of this problem is partial matching, where the two shapes are dissimilar in general, but have significant similar parts. In this paper, we show a rigorous approach allowing to find matching parts of rigid shapes with controllable size and regularity. The regularity term we use is similar to the spirit of the Mumford-Shah functional, extended to non-Euclidean spaces. Numerical experiments show that the regularized partial matching produces better results compared to the non-regularized one.","lang":"eng"}],"oa_version":"None","type":"conference","status":"public","date_created":"2024-10-15T11:20:54Z","author":[{"id":"58f3726e-7cba-11ef-ad8b-e6e8cb3904e6","first_name":"Alexander","last_name":"Bronstein","orcid":"0000-0001-9699-8730","full_name":"Bronstein, Alexander"},{"last_name":"Bronstein","first_name":"Michael M.","full_name":"Bronstein, Michael M."}],"title":"Regularized partial matching of rigid shapes","_id":"18337","language":[{"iso":"eng"}],"publication_identifier":{"eisbn":["9783540886884"],"isbn":["9783540886853"],"issn":["1611-3349"],"eissn":["0302-9743"]},"scopus_import":"1","publication":"10th European Conference on Computer Vision","fulldoi":"https://doi.org/10.1007/978-3-540-88688-4_11","article_processing_charge":"No","conference":{"name":"ECCV: European Conference on Computer Vision","end_date":"2008-10-18","start_date":"2008-10-12","location":"Marseille, France"},"date_published":"2008-11-01T00:00:00Z","alternative_title":["LNCS"],"intvolume":"      5303","publication_status":"published","quality_controlled":"1","year":"2008","doi":"10.1007/978-3-540-88688-4_11","volume":5303,"publisher":"Springer Berlin Heidelberg","month":"11","day":"01"}]