Secure distributed systems rely on trust. A trust assumption specifies the failures that a system can tolerate and determines the conditions under which it operates correctly. Trust in secure distributed systems has traditionally been devised in a symmetric way, where every participant in the system adheres to the same, global notion of trust through a fail-prone system, a collection of subsets of participants that can fail together and are tolerated to fail in an execution. However, recent advances in the field, particularly in the context of blockchain networks, have led to the development of new models of trust that allow participants to express their own beliefs in a subjective way.
In this thesis, we study in detail and extend with new results the model of asymmetric trust first introduced by Damgård, Desmedt, Fitzi, and Nielsen (ASIACRYPT 2007), and carried on by Cachin and Tackmann (OPODIS 2019). We develop the first asynchronous consensus protocol that works in this model and evaluate its properties and resilience against Byzantine failures. This protocol results in an optimal randomized Byzantine consensus protocol with subjective, asymmetric trust and constant expected running time.
Furthermore, we define a composition rule that allows for the joining of distributed systems based on asymmetric trust. These composition rule ensures that if the original systems allow for running a particular protocol (guaranteeing consistency and availability), then the joint system will as well, while tolerating as many faults as possible.
Finally, we expand the asymmetric trust model to work in permissionless settings, where the number of participants in the system is not known, such as in blockchain systems. We do so by enabling processes not only to make assumptions about failures, but also to make assumptions about the assumptions of other processes. The resulting model generalizes existing models such as the classic fail-prone system model [Malkhi and Reiter, 1998] and the asymmetric fail-prone system model.
Our contributions provide new insights into the notion of trust in secure distributed systems and offer solutions for enhancing the security and reliability of these systems in the presence of Byzantine failures. The results of this thesis have the potential to improve the security of distributed systems, particularly in applications such as blockchain systems.