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 $2f+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.
翻译:我们考虑在一个无序系统中支持支付交易的问题,在这种系统中,最多不超过$f的验证器在适应性对手的控制下会受到Byzantine失败的影响。 事实表明,这个问题可以不协商一致地通过使用Byzantine法定人数系统(在非同步系统中,每笔交易至少需要2f+1美元验证)来解决。 我们表明,如果每笔交易的支出不超过一小部分余额,则可以同时与低于$f美元的交易同时验证交易。 我们的解决方案依赖于我们在本文件中推出的新颖的法定人数系统,以及我们调用$(k_1,k_2)$(美元)的配额系统。 在非适应性对手的法定人数系统中,这些系统可以用来允许最多为$_1美元的交易同时验证,但防止超过美元2美元的交易被验证。 如果对手适应性,这些系统可以允许任何k_1美元的交易被验证,并且防止超过$2美元(k_2美元)的剩余交易,我们用全额的金额来验证交易。 在纸质交易中,这种交易的金额交易的金额比美元交易的全额确认。