In this paper, we propose a methodology to design and analyze the correctness and fairness of committee-based blockchains. We specify the problem that these blockchains implement, specifically, the Byzantine repeated consensus problem. Moreover, we define the problem of fair reward distribution among committee members and study the impact of synchronous assumptions on fairness . It is common knowledge that in permisionless blockchain systems, the main threat is the tragedy of commons that may yield the system to collapse if the rewarding mechanism is not adequate. At minimum, the reward mechanism must be fair , i.e., distribute the rewards in proportion to the merit of the participants. We prove, for the first time in blockchain systems, that in repeated-consensus based blockchains there exists an (eventual) fair rewarding mechanism if and only if the system is (eventual) synchronous. As a case study, we study Tendermint both from Byzantine Repeated Consensus perspective and its fairness with respect to the rewarding of committee members. We prove that in eventual synchronous systems, a modified version of Tendermint solves: (i) one-shot consensus for the validation of one single block with message complexity O ( n 3 ) where is the size of the validators set and (ii) a variant of the repeated consensus problem for multiple blocks. Our second contribution is related to the fairness of the Tendermint rewarding mechanism. We show that the rewarding in Tendermint is not fair, but a small modification of Tendermint is eventually fair.

Federated Learning is a decentralized framework that enables multiple clients to collaboratively train a machine learning model under the orchestration of a central server without sharing their local data. The centrality of this framework represents a point of failure which is addressed in literature by blockchain-based federated learning approaches. While ensuring a fully-decentralized solution with traceability, such approaches still face several challenges about integrity, confidentiality and scalability to be practically deployed. In this paper we propose Fantastyc, a solution designed to address these challenges that have been never met together in the state of the art.

An auditable register extends the classical register with an audit operation that returns information on the read operations performed on the register. In this paper, we study Byzantine resilient auditable registers implementations in an asynchronous message-passing system. Existing solutions implement the auditable register on top of at least$4\mathrm{f}+1$servers, where at most$f$can be Byzantine. We show that$4\mathrm{f}+1$servers are necessary to implement auditability without communication between servers. Then, we pursue the study by relaxing the constraint on the servers' communication, letting them interact with each other. In this setting, we prove that$3\mathrm{f}+1$servers are sufficient. This result establishes that with communication between servers, auditability does not come with an additional cost in terms of the number of servers.

This paper is the first to specify blockchains as a composition of abstract data types all together with a hierarchy of consistency criteria that formally characterizes the histories admissible for distributed programs that use them. The paper presents as well some results on implementability of the presented abstractions and a mapping of representative existing blockchains from both academia and industry in our framework.

The presented work continues the line of recent distributed computing community efforts dedicated to the theoretical aspects of blockchains. This paper is the first to specify blockchains as a composition of abstract data types all together with a hierarchy of consistency criteria that formally characterizes the histories admissible for distributed programs that use them. Our work is based on an original oracle-based construction that, along with new consistency definitions, captures the eventual convergence process in blockchain systems. The paper presents as well some results on implementability of the presented abstractions and a mapping of representative existing blockchains from both academia and industry in our framework.

Committee-based blockchains are among the most popular alternatives of proof-of-work based blockchains, such as Bitcoin. They provide strong consistency (no fork) under classical assumptions, and avoid using energy-consuming mechanisms to add new blocks in the blockchain. For each block, these blockchains use a committee that executes Byzantine-fault tolerant distributed consensus to decide the next block they will add in the blockchain. Unlike Bitcoin, where there is only one creator per block, in committee-based blockchain any block is cooperatively created. In order to incentivize committee members to participate in the creation of new blocks, rewarding schemes have to be designed. In this paper, we study the fairness of rewarding in committee-based blockchains and we provide necessary and sufficient conditions on the system communication under which it is possible to have a fair reward mechanism.

In this paper we prove lower and matching upper bounds for the number of servers required to implement a regular shared register that tolerates unsynchronized Mobile Byzantine failures. We consider the strongest model of Mobile Byzantine failures to date: agents are moved arbitrarily by an omniscient adversary from a server to another in order to deviate their computation in an unforeseen manner. When a server is infected by an Byzantine agent, it behaves arbitrarily until the adversary decides to move the agent to another server. Previous approaches considered asynchronous servers with synchronous mobile Byzantine agents (yielding impossibility results), and synchronous servers with synchronous mobile Byzantine agents (yielding optimal solutions for regular register implementation, even in the case where servers and agents periods are decoupled). We consider the remaining open case of synchronous servers with unsynchronized agents, that can move at their own pace, and change their pace during the execution of the protocol. Most of our findings relate to lower bounds, and characterizing the model parameters that make the problem solvable. It turns out that unsynchronized mobile Byzantine agent movements requires completely new proof arguments, that can be of independent interest when studying other problems in this model. Additionally, we propose a generic server-based algorithm that emulates a regular register in this model, that is tight with respect to the number of mobile Byzantine agents that can be tolerated. Our emulation spans two awareness models: servers with and without self-diagnose mechanisms. In the first case servers are aware that the mobile Byzantine agent has left and hence they can stop running the protocol until they recover a correct state while in the second case, servers are not aware of their faulty state and continue to run the protocol using an incorrect local state.

This paper considers the Approximate Agreement problem in presence of mobile Byzantine agents. We prove lower bounds on the number of correct processes to solve such problem. To do that we prove that the existing solutions tolerant to Byzantine agents still holds in such case and under which conditions.

We present an optimal emulation of a server based regular read/write storage in a synchronous round-free message-passing system that is subject to mobile Byzantine failures and prove that the problem is impossible to solve in asynchronous settings. In a system with n servers implementing a regular register, our construction tolerates faults (or attacks) that can be abstracted by agents that are moved (in an arbitrary and unforeseen manner) by a computationally unbounded adversary from a server to another in order to deviate the server's computation. When a server is infected by an adversarial agent, it behaves arbitrarily until the adversary decides to "move" the agent to another server. We investigate the case where the movements of the mobile Byzantine agents are decided by the adversary and are completely decoupled from the message communication delay. Our emulation spans two awareness models: servers with and without self-diagnosis mechanism. In the first case servers are aware that the mobile Byzantine agent has left and hence they can stop running the protocol until they recover a correct state while in the second case, servers are not aware of their faulty state and continue to run the protocol using an incorrect local state. Our results, proven optimal with respect to the threshold of the tolerated mobile Byzantine faults in the first model, are significantly different from the round-based synchronous models. Another interesting side result of our study is that, contrary to the round-based synchronous consensus implementation for systems prone to mobile Byzantine faults, our storage emulation does not rely on the necessity of a core of correct processes all along the computation. That is, every server in the system can be compromised by the mobile Byzantine agents at some point in the computation. This leads to another interesting conclusion: storage is easier than consensus in synchronous settings, when the system is hit by mobile Byzantine failures.