Adversarial procurement in blockchains
This work provides a theoretical foundation and practical guidance for designing incentive-compatible protocols in blockchain systems that rely on asymmetric computational effort, addressing a key challenge for pseudonymous, adversarial settings.
The paper formalizes the mechanism design problem of efficiently soliciting expensive computational tasks in adversarial blockchain environments. It shows that the optimal protocol's loss scales logarithmically with liveness fault cost and adversarial fraction, and provides concrete design advice such as using a single random primary worker with a committee fallback.
An emerging blockchain protocol design pattern leverages the asymmetry between the computational effort in performing versus verifying tasks. For example, cryptographic validity proofs (e.g., SNARKS) require the prover to expend significant effort demonstrating the correctness of their claim, while the verifiers benefit from extremely easy validation. The operationalization of this paradigm requires efficiently soliciting the performance of expensive tasks in pseudonymous, adversarial environments. We formalize this as a mechanism design question. The protocol balances the economic cost of a liveness fault, where the work is not completed, with the payments required to incentivize specific behavior from candidate suppliers. We show that the loss of the optimal protocol scales logarithmically in the cost of a liveness fault, scaled up by the adversarial fraction of the network. Further, we find that the optimal equilibria have an intuitive structure, allowing us to provide concrete advice to practitioners. Specifically, in many regimes, the optimum designates a single, random node as the primary worker and a committee as a fallback, which is reminiscent of leader-based consensus mechanisms. We also characterize the asymptotic regimes where having negative payments (i.e., slashing in blockchain parlance) is especially helpful.