Executing and proving over dirty ledgers

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.

Download (ext.)

Conference Paper | Published | English

Scopus indexed

Corresponding author has ISTA affiliation

Series Title
LNCS
Abstract
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. If 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. This “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.
Publishing Year
Date Published
2023-12-01
Proceedings Title
27th International Conference on Financial Cryptography and Data Security
Publisher
Springer Nature
Acknowledgement
Eleftherios Kokoris-Kogias is partially supported by Austrian Science Fund (FWF) grant No: F8512-N.
Volume
13950
Page
3-20
Conference
FC: Financial Cryptography and Data Security
Conference Location
Bol, Brac, Croatia
Conference Date
2023-05-01 – 2023-05-05
ISSN
eISSN
IST-REx-ID

Cite this

Stefo C, Xiang Z, Kokoris Kogias E. Executing and proving over dirty ledgers. In: 27th International Conference on Financial Cryptography and Data Security. Vol 13950. Springer Nature; 2023:3-20. doi:10.1007/978-3-031-47754-6_1
Stefo, C., Xiang, Z., & Kokoris Kogias, E. (2023). Executing and proving over dirty ledgers. In 27th International Conference on Financial Cryptography and Data Security (Vol. 13950, pp. 3–20). Bol, Brac, Croatia: Springer Nature. https://doi.org/10.1007/978-3-031-47754-6_1
Stefo, Christos, Zhuolun Xiang, and Eleftherios Kokoris Kogias. “Executing and Proving over Dirty Ledgers.” In 27th International Conference on Financial Cryptography and Data Security, 13950:3–20. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-47754-6_1.
C. Stefo, Z. Xiang, and E. Kokoris Kogias, “Executing and proving over dirty ledgers,” in 27th International Conference on Financial Cryptography and Data Security, Bol, Brac, Croatia, 2023, vol. 13950, pp. 3–20.
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.
Stefo, Christos, et al. “Executing and Proving over Dirty Ledgers.” 27th International Conference on Financial Cryptography and Data Security, vol. 13950, Springer Nature, 2023, pp. 3–20, doi:10.1007/978-3-031-47754-6_1.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search