Resilience to Chain-Quality Attacks in Fair Separability

In recent years, a new research area called order-fairness has emerged within State Machine Replication (SMR). Its goal is to prevent malicious processes from reordering transactions, ensuring that the SMR output reflects the local orderings observed by processes. One of the advanced approaches to addressing this challenge is fair separability, which is designed to mitigate cyclic dependencies present in transaction dependency graphs. However, in the existing implementation of fair separability, a transaction input by a Byzantine process can be output with only \(\mathcal {O}(1)\) resources, whereas outputting a transaction input by a correct process requires \(\mathcal {O}(n)\) resources. This vulnerability exposes the protocol to chain-quality attacks. In this paper, we propose an implementation of fair separability where the cost of outputting transactions remains consistent for the inputs of all processes, which enhances resilience to chain-quality attacks.