Brief Announcement: Breaking the f + 1 Barrier: Executing Payment Transactions in Parallel with Less than f + 1 Validations

DOI10.1145/3583668.3594580arXiv2301.10149OpenAlexW4380881568MaRDI QIDQ6202260FDOQ6202260

Authors: Rida A. Bazzi, Sara Tucci Piergiovanni

Publication date: 26 March 2024

Published in: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: We consider the problem of supporting payment transactions in an asynchronous system in which up to

f

validators are subject to Byzantine failures under the control of an adaptive adversary. It was shown that this problem can be solved without consensus by using byzantine quorum systems (requiring at least

2 f + 1

validations per transaction in asynchronous systems). We show that it is possible to validate transactions in parallel with less than

f

validations per transaction if each transaction spends no more that a small fraction of a balance. Our solution relies on a novel quorum system that we introduce in this paper and that we call

(k_{1}, k_{2})

-quorum systems. In the presence of a non-adaptive adversary, these systems can be used to allow up to

k_{1}

transactions to be validated concurrently and asynchronously but prevent more than

k_{2}

transactions from being validated. If the adversary is adaptive, these systems can be used to allow

k_{1}

transaction to be validated and prevent more than

k'_{2} > k_{2}

transactions from being validated, the difference

k'_{2} - k_{2}

being dependent on the quorum system's {em validation slack}, which we define in this paper. Using

(k_{1}, k_{2})

-quorum systems, a payer can execute multiple partial spending transactions to spend a portion of its initial balance with less than full quorum validation (less than

f

validations per transaction) then reclaim any remaining funds using one fully validated transaction, which we call a {em settlement} transaction.

Full work available at URL: https://arxiv.org/abs/2301.10149

zbMATH Keywords

distributed systems fault tolerance quorums blockchain

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

This page was built for publication: Brief Announcement: Breaking the f + 1 Barrier: Executing Payment Transactions in Parallel with Less than f + 1 Validations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202260)