---
_id: '14735'
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."
acknowledgement: 'Eleftherios Kokoris-Kogias is partially supported by Austrian Science
Fund (FWF) grant No: F8512-N.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Christos
full_name: Stefo, Christos
id: a20e8902-32b0-11ee-9fa8-b23fa638b793
last_name: Stefo
- first_name: Zhuolun
full_name: Xiang, Zhuolun
last_name: Xiang
- first_name: Eleftherios
full_name: Kokoris Kogias, Eleftherios
id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
last_name: Kokoris Kogias
citation:
ama: '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'
apa: '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'
chicago: 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.
ieee: 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.
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.'
mla: 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.
short: C. Stefo, Z. Xiang, E. Kokoris Kogias, in:, 27th International Conference
on Financial Cryptography and Data Security, Springer Nature, 2023, pp. 3–20.
conference:
end_date: 2023-05-05
location: Bol, Brac, Croatia
name: 'FC: Financial Cryptography and Data Security'
start_date: 2023-05-01
date_created: 2024-01-08T09:17:38Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2024-01-08T09:28:14Z
day: '01'
department:
- _id: ElKo
- _id: GradSch
doi: 10.1007/978-3-031-47754-6_1
intvolume: ' 13950'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2022/1554
month: '12'
oa: 1
oa_version: Preprint
page: 3-20
project:
- _id: 34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f
grant_number: F8512
name: Secure Network and Hardware for Efficient Blockchains
publication: 27th International Conference on Financial Cryptography and Data Security
publication_identifier:
eisbn:
- '9783031477546'
eissn:
- 0302-9743
isbn:
- '9783031477539'
issn:
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Executing and proving over dirty ledgers
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13950
year: '2023'
...
---
_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.
acknowledgement: Supported by the German Federal Ministry of Education and Research
(BMBF), grant 16KISK020K (6G-RIC), 2021–2025, and ERC CoG 863818 (ForM-SMArt).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Mahsa
full_name: Bastankhah, Mahsa
last_name: Bastankhah
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Mohammad Ali
full_name: Maddah-Ali, Mohammad Ali
last_name: Maddah-Ali
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
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: 27th International Conference on Financial Cryptography and Data Security.
Vol 13950. Springer Nature; 2023:309-325. doi:10.1007/978-3-031-47754-6_18'
apa: 'Bastankhah, M., Chatterjee, K., Maddah-Ali, M. A., Schmid, S., Svoboda, J.,
& Yeo, M. X. (2023). R2: Boosting liquidity in payment channel networks with online
admission control. In 27th International Conference on Financial Cryptography
and Data Security (Vol. 13950, pp. 309–325). Bol, Brac, Croatia: Springer
Nature. https://doi.org/10.1007/978-3-031-47754-6_18'
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 27th International Conference
on Financial Cryptography and Data Security, 13950:309–25. Springer Nature,
2023. https://doi.org/10.1007/978-3-031-47754-6_18.'
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 27th International Conference on Financial Cryptography and Data
Security, Bol, Brac, Croatia, 2023, vol. 13950, 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.'
mla: 'Bastankhah, Mahsa, et al. “R2: Boosting Liquidity in Payment Channel Networks
with Online Admission Control.” 27th International Conference on Financial
Cryptography and Data Security, vol. 13950, Springer Nature, 2023, pp. 309–25,
doi:10.1007/978-3-031-47754-6_18.'
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.
conference:
end_date: 2023-05-05
location: Bol, Brac, Croatia
name: 'FC: Financial Cryptography and Data Security'
start_date: 2023-05-01
date_created: 2024-01-08T09:30:22Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2025-07-14T09:10:01Z
day: '01'
department:
- _id: KrCh
- _id: KrPi
doi: 10.1007/978-3-031-47754-6_18
ec_funded: 1
intvolume: ' 13950'
language:
- iso: eng
month: '12'
oa_version: None
page: 309-325
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 27th International Conference on Financial Cryptography and Data Security
publication_identifier:
eisbn:
- '9783031477546'
eissn:
- 1611-3349
isbn:
- '9783031477539'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: 'R2: Boosting liquidity in payment channel networks with online admission control'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13950
year: '2023'
...