Project Topics
Get Complete Project Material File(s) Now! »
Classical Participants
The rst two types of participants, the only ones used in Chapter 4 are the classical types we can nd in the distributed systems’ literature, as described in Section 2.2.4: the correct and the Byzantine participants. Both correct and Byzantine participants do not care about the costs of their actions, nor the global execution of the system. In this manuscript, and for the sake of clarity and consistency, we use the terminology obedient instead of correct. The term honest can also be found in the blockchain literature to designate obedient participants.
Denition 2.4 (Obedient Participant). A participant is obedient with respect to a protocol A if it always follows protocol A.
When the protocol is clear from the context, we just say that the participant is obedient. In particular, the above denition of an obedient participant encapsulates the fact that the participant is always in the system and always follows the protocol.
Denition 2.5 (Byzantine Participant). A participant is Byzantine with respect to a protocol A if it can arbitrarily deviate from protocol A. When the protocol is clear from the context, we just say that the participant is Byzantine. A Byzantine participant represents all kinds of (unfortunate) situations that can happen, e.g., a failure, or doing others actions than the prescribed. Any behaviour can be seen as Byzantine.
Rational Participants
A third class of participants is considered in Chapters 5 & 6: the rational participants. Rational participants may care about the cost of their actions, and they have preferences over all the dierent global executions of the system. In more details, a rational participant assigns a value to each possible execution of the system; between any two executions of the system, a rational participant prefers the one having a higher value. The gain of a rational participant is a function of (i) the global execution of the system, and of (ii) the actions the participant takes.
The gain has values in the set of real numbers, R. We recall that the actions of one participant may have an eect on which global execution the system will have.
Denition 2.6 (Rational Participant). A participant is rational if it is self-interested. It does an action instead of another action if and only if doing so increases its expected gain. A rational participant has preferences and takes actions to have its most preferred execution of the system, taking into account what the other participants do. It does not necessarily want to hurt the system; it wants to benet from it.
We now introduce two renements of the rational participants: the strategic, and the malicious participants. Having a property on the system’s executions, one can know whether a given execution satises that property. In particular, a property denes a partition on the executions of the system; in one hand, the executions that satisfy the property and on the other hand, the executions that do not satisfy the property.
Denition 2.7 (Strategic Participant). A participant is strategic with respect to a property P if it is rational, and it prefers executions that satisfy P, i.e., its assigns a positive value to executions where P is satised, and a negative value to executions where P is not satised. A strategic participant prefers the executions where the system achieves its properties, but think about its own interest in the rst place.Denition 2.8 (Malicious Participant). A participant is malicious with respect to a property P if it is rational, and it prefers executions that do not satisfy P, i.e., its assigns a positive value to executions where P is not satised.
A malicious participant’s objective is to hurt the system. A malicious participant takes all actions it can to increase the chance of having a global execution that does not satisfy the properties of the system.
The Byzantine-Altruistic-Rational (BAR) Model Aiyer et al. introduced the Byzantine- Altruistic-Rational model or BAR model in [7]. In the BAR model, given a protocol, there are three types of participants:
• Byzantine: Participants that can arbitrarily deviate from the protocol.
• Altruistic: Participants that always follow the protocol.
• Rational: Rational participants will deviate from the protocol if and only if doing so increases their net utility from participating in the system; in particular, rational participants receive a long-term benet from participating in the protocol.
A Comparison of Possible Executions from Participants’ Type
LetAbe a protocol. We can see from Denition 2.6 that a rational participant can be viewed as a special subclass of Byzantine participants, rational participants can deviate from the protocol, but only if that deviation is benecial to them.
Let C be a class of rational participants such that their objective is to follow the protocol A no matter what is the global execution of the system and what the other participants do. The class C consists of exactly all the obedient participants with respect to A, and only them. We can consider that some rational participants can behave as obedient, if their gain function is dened in that case. That exhibits that the behaviour of rational participants depends really on their gains. Therefore, the obedient participants are a subclass of rational participants where their objective is to follow the protocol.
Usually, a protocol is designed to solve a problem, or equivalently to satisfy a property. It can then happen for strategic participants to behave as obedient. However, if running the protocol is (too) costly, strategic participants may deviate to improve their gain. The class of obedient participants is not a subclass of strategic participants, but both can intersect. As mentioned earlier, malicious and strategic participants are rational participants, but they have opposing objectives, so they do not intersect. A summary of the comparison of possible execution can be viewed in Figure 2.2.
Bitcoin & Proof-of-Work Blockchains
Bitcoin [128], the most known, and to the best of our knowledge, the rst nancial application based on blockchain proceeds by using a technique called proof-of-work, which was introduced by Dwork and Naor in 1992 [69]. Using this technique, Bitcoin’s participants aim to reach some sort of agreement in an open and asynchronous system. In Bitcoin, some participants, called miners want to add blocks to the blockchains. Miners are block creators. To add a new block to the chain, each miner needs to prove that it worked to have the right to add a new block. Proving that a miner worked is represented by solving rst among the miners a cryptographic puzzle. The best-known way to solve such a problem is by repeated trials, hence the more computing power a miner has, the higher are its chances to solve the puzzle rst.
Proof-of-* – Alternatives to Proof-of-Work
To solve the high energy-consumption issue of proof-of-work, many proposals were made to select the next participant that should add a new block to the chain. Specically, most of the proposals replace the need for computing power by other things (such as memory, wealth, etc.) keeping the main idea of proof-of-work, namely the random selection.
In this section, we give an overview of some of the proposals. Note that there are always new mechanisms presented, therefore giving a complete and total snapshot of the proof-ofwork alternatives is not feasible.
Proof-of-stake. The main candidate alternative of proof-of-work is proof-of-stake. Even the second most known blockchain system, Ethereum [159], plans to switch their proof-of-work mechanism to proof-of-stake.
In proof-of-stake, the role of computing power is replaced by the number of stakes possessed by participants in the system. There exist many dierent ways of using stakes. For example, in PeerCoin [105] the rst blockchain proposing proof-of-stake, the information considered is the “age” of the coin. If a participant holds a coin for a long time, it has more chances to be the next to add a block relative to another participant that just received a new coin. Other blockchain systems consider the number of coins a participant has, its stake, such as Ouroboros [102], i.e., the higher stake a participant has, the higher are its chances to be selected to add a block.
Note that usually in proof-of-stake, the selection of the next participant to add a block is also random (to calque the behaviour of Bitcoin), but is proportional to the stake, i.e., it may happen that multiple participants are selected. Forks do still exist in proof-of-stake. There exist many more specic proof-of-stakes, for example, delegated proof-of-stake or DPoS in which participants can delegate part of their stakes to other participants that have more chances to be selected, the rewards are then shared among the winner and its delegators.
Proof-of-burn can also be considered as a variant of proof-of-stake. The main ingredient of proof-of-burn is that the more stakes a participant burns (stakes that cannot be used any more), the higher the chances of the participants to be selected. Several academic works address proof-of-stake based blockchains. To the best of our knowledge, the rst on this line is Snow White [58] authored by Daian et al.. Daian et al. propose a protocol for semi-synchronous systems. The execution of the protocol is organised in epochs. Similar to Bitcoin-NG [73] in each epoch a dierent committee is elected, and inside the elected committee a leader will be chosen. The leader is allowed to extend the blockchain by adding blocks. The protocol in [58] is validated via simulations and only partial proofs of correctness are provided. More recently, Kiayias et al. propose [102] Ouroboros. Ouroboros uses a sortition based proof-of-stake protocol and the article addresses mainly the security aspects of the proposed protocol. Algorand [85] also uses proof-of-stake for the blockchain. In Algorand, participants are selected to maintain the blockchain base only on their stakes and by relying on cryptographic techniques.
Our contributions to Blockchain’s Construction
In this thesis, we study how committee-based blockchains are built in a deterministic manner. Specically, we study the problem they are trying to solve in the sense of a distributed system abstraction, i.e., we dene the Byzantine repeated consensus abstraction in Byzantine environment, which represents the construction of a blockchain. Additionally, we formalise for the very rst time the Tendermint algorithm, and prove its correctness; moreover, we compute its complexity and compare it to state-of-the-art algorithms.
Fairness of Blockchains
To motivate participants to add and maintain the blockchain correctly, rewarding mechanisms are in place. Rewards are given to block creators for each block successfully added to the blockchain. In blockchains such as Bitcoin, a reward is given to the block creator that successfully adds its block to the blockchain, i.e., exactly one participant is rewarded at the time. Since only correct blocks are added to the blockchain, participants that are rewarded behave correctly for that block.
In committee-based blockchains, rewards should be given to committees. In each committee, because only some committee members can be faulty but not all, rewarding mechanisms are inherently more complex to handle than in other blockchains. The properties of reward mechanisms for committee-based blockchains must be studied. Ad minimum, the rewarding mechanism must be fair, i.e., distributing the rewards in proportion to the merit of participants, where merit abstracts the notion of eort participants invest for the construction of the blockchain. A blockchain protocol is said to be fair if any obedient participant (a participant that followed the protocol) that has a fraction of the total merit in the system will get at least fraction of the total reward that is given in the system.
In the blockchain literature, chain-quality has been dened by [83] and was later on extended by [135]. In [83], Garay et al. dene the notion of chain-quality as the proportion of blocks mined by obedient miners (block creators) in any given window; Garay et al. study the conditions under which during a given window of time, there is a bounded ratio of blocks in the chain that non-obedient participants produced, over the total blocks in the blockchain. Chain-quality can be seen as a denition of fairness in Bitcoin-like systems, and even more generally, in most forkable (proof-of-* based) blockchains. A blockchain system has the property of chain-quality if the proportion of blocks produced by obedient participants in any given window is proportional to their relative mining power. Intuitively, chain-quality ensures that non-obedient participants do not produce more blocks than their proportion of mining power.
In [102], Kiayias et al. propose Ourobouros [102] and analyse its chain-quality property. In [135], Pass and Shi propose a notion of fairness, which is an extension of the chain-quality property still dedicated to Bitcoin-like blockchains; they address one of the vulnerabilities of Bitcoin studied formally in [74]. In [74], Eyal and Sirer prove that if an adversary controls a coalition of miners holding even a minority fraction of the total computing power, this coalition can gain twice its share. Fruitchain [135] overcomes this problem by ensuring that no coalition controlling less than a majority of the computing power can gain more than a factor 1 + 3 by not respecting the protocol, where is a parameter of the protocol. We note that in the model of Fruitchain, only one participant creates a block in the blockchain and that a participant has a reward for the created block. In [90], Guerraoui andWang study the eect of the delays of message propagation in Bitcoin, and they show that in a system of two miners, one can take advantage of the delays and be rewarded exponentially more than its share.
In [92, 93], Gürcan et al. study the fairness from the point of view of the participants that do not participate in the construction of the blockchain but create transactions. Herlihy and Moir do a similar work in [96] where the authors study users’ fairness and consider as an example the Tendermint blockchain. Herlihy and Moir discussed how participants with malicious behaviour could violate fairness by choosing transactions, and then they propose modications to the original Tendermint to make some violations detectable and accountable. In [115], Lev-Ari et al. study the fairness of transactions in committee-based blockchains with synchronous assumptions by using a detectable communication abstraction allowing them to identify faulty and malicious participants.
Table of contents :
1 Introduction
1.1 Blockchains & Context
1.2 Contributions and Organisation
2 Model
2.1 Notations
2.2 System Model
2.3 Communication
2.4 Game Theory
2.5 Conclusion
3 State of the Art
3.1 Blockchains’ Construction
3.2 Fairness of Blockchains
3.3 Rational Behaviours in Blockchain Systems
3.4 Conclusion
4 Correctness and Fairness of Committee-based Blockchains
4.1 System Model
4.2 Consensus & Blockchains
4.3 Problem Denition
4.4 Fairness Analysis of Committee-based Blockchains
4.5 Case Study: Analysis of Tendermint
4.6 Conclusion
5 Strategic Behaviours in Committee-based Blockchains
5.1 Model
5.2 Reward Only Committee Members that Vote
5.3 Reward All Committee Members
5.4 Trembling Strategic Participants
5.5 Discussions
5.6 Conclusion
6 When Malicious Come into the Game
6.1 Model
6.2 Equilibrium where Validity is not Guaranteed
6.3 Equilibrium where Termination is not Guaranteed
6.4 Equilibrium where both Termination and Validity are Guaranteed
6.5 Conclusion
7 Conclusions
7.1 General Conclusions of the Thesis
7.2 Perspectives / Future Works
Bibliography
