Asymptotic Performance Analysis of Blockchain Protocols
This work provides a systematic comparison for researchers and practitioners in blockchain technology, though it is incremental in nature.
The paper tackles the challenge of formally assessing blockchain protocols by conducting a complexity analysis of various distributed algorithms to compare their practical performances, resulting in a more robust criteria for classifying protocols as permissioned or permissionless.
In the light of the recent fame of Blockchain technologies, numerous proposals and projects aiming at better practical viability have emerged. However, formally assessing their particularities and benefits has proven to be a difficult task. The aim of this work is to compare the fundamental differences of such protocols to understand how they lead to different practical performances. To reach this goal, we undertake a complexity analysis of a wide range of prominent distributed algorithms proposed for blockchain systems, under the lens of Total Order Broadcast protocols. We sampled protocols designed for very different settings and that use a broad range of techniques, thus giving a good overview of the achievements of state-of-the-art techniques. By analyzing latency and network usage, we are able to discuss each protocol's characteristics and properties in a consistent manner. One corollary result to our work is a more robust criteria to classify protocols as permissioned or permissionless.