Consensus Potpourri: Rational Behaviors in Committee-Based Blockchains
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 30 | |
| Author | ||
| License | CC Attribution 4.0 International: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/52880 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
00:00
Phase transitionVotingBlock (periodic table)ChainRoundingPropositional formulaThermodynamic equilibriumBargaining problemValidity (statistics)Message passingDatabase transactionCommunications protocolMaxima and minimaChainNumberGroup actionRoundness (object)Key (cryptography)WordType theoryDirected graphAdventure gameBootingQuicksortEvent horizonBlogArmObject (grammar)Arithmetic meanMultiplication signRational numberDecision theoryBlock (periodic table)WhiteboardText editorVotingPhase transitionUsabilityGame theory1 (number)TendonPurchasingCausalityResultantDifferent (Kate Ryan album)FamilyGoodness of fitMultiplicationDirection (geometry)InformationMathematical analysisProjective planeDivisorMetreBridging (networking)Degree (graph theory)Physical systemRevision controlCore dump40 (number)AuthorizationInformation managementPresentation of a groupTouch typingWellenwiderstand <Strömungsmechanik>Product (business)DemosceneTerm (mathematics)Endliche ModelltheorieCASE <Informatik>Coefficient of determinationInstance (computer science)Reading (process)Peer-to-peerMusical ensembleSelf-organizationLevel (video gaming)Special unitary groupVapor barrierINTEGRALSubsetWebsiteMessage passingNetwork topologyMaxima and minimaThermodynamic equilibriumCondition numberComputer simulationAutomatic differentiationWritingProof theoryView (database)Point (geometry)Cartesian coordinate systemData structureSystem callAngleMetropolitan area networkNeuroinformatikTable (information)AdditionOcean currentValidity (statistics)Subject indexingOntologySet (mathematics)Prisoner's dilemmaSocial classCategory of beingHash functionSpacetimeBitSimilarity (geometry)2 (number)Numbering schemeHypothesisFood energySynchronizationFreewareCommunications protocolTelecommunicationThresholding (image processing)AlgorithmPerturbation theoryCoordinate systemDocument management systemRadical (chemistry)FacebookDatabase transactionCohen's kappaComputer animation
Transcript: English(auto-generated)
00:00
In this presentation, we'll talk about rational behaviors in committee-based blockchains. This is a joint work with Bruno Bier, Maria Petal-Gutul-Rao, and Sara Tutti-Pierjove. In a blockchain system where we have multiple players, multiple participants, nodes, that communicate by exchanging messages to one another, the goal is to build a distributed ledger.
00:25
There is no central authority, but all the players in the system should have the exact same blockchain, the same ledger locally. The ledger should be tempo-resistant, so an information already in the ledger should be hard to modify and invert impossible,
00:43
and it should be built in an append-only manner. Basically, the structure of a blockchain, from the point of view of only one player, is just a chain of blocks, where each block is linked to the previous one by its hash, which is basically its identifier,
01:03
and so that if the block 2 is modified even slightly, the hash will totally change. That is what guarantees the tempo-resistance property. Each block contains transactions that depend on the application that one wants to implement,
01:24
and any new block that should be added to the blockchain should be coherent with the whole blockchain that is already there. To add a new block, one can think about using consensus, where a consensus algorithm is an algorithm that satisfies the three following properties.
01:44
Domination, where every correct player, players that follow and execute always the algorithm, eventually decide a value, so they decide on a block at one point. Validity, which states that a decided value should be valid with respect to a given predicate,
02:02
and the Agreements property that states that two correct players that decide should decide the exact same value, the exact same block. How one can use consensus to build a blockchain? We can do it as follows. First, the genesis block that basically sets up the whole system.
02:23
That block will also designate select a committee, which is just a subset of all the players in the system. That committee will run a consensus algorithm to produce a block. That block will be sent to the whole network,
02:42
and a new committee will be selected with respect to the whole history now of the blockchain. That committee again will run a consensus instance, produce a new block, etc, etc. And these kind of blockchains already exist out there and are even used. For example, we have Tendermint that is implemented and used in a lot of applications.
03:05
Hot stuff that is at the core, basically at the core of the Libra, excuse me, the DM, the Facebook DMs blockchain project. And one thing important in these kind of blockchains is that once a block is produced, the committee that produces that block is eventually rewarded.
03:30
These blockchains work as follows when we focus on one committee, so for producing one block. They work in multiple rounds. And each round is an attempt to produce a block, to accept the block that is proposed.
03:45
And focusing on just round one that is basically the same as the others, there is a proposed phase where a block is proposed to the whole committee. Then a vote phase where each member of the committee votes or not for the proposed block.
04:03
And if there are sufficiently many votes for a block proposed, hence a new, which is our threshold here, then we consider that the block is produced. If the block is not produced, we go to the next round, we have a new proposed phase, etc.
04:23
These kind of blockchains have been analyzed in the literature since the first time they were proposed in 2014 by Kwon. Then we had some analysis on Tendermint, which was the first algorithm. Then Hot Stuff was proposed last year in Pazzi.
04:44
And there are even new proposals about these kind of algorithms. And they have been studied formally, and that's nice. But the thing is that they were always analyzed considering only two types of players.
05:02
We have the corrects that basically always follow the algorithm, and the byzantine that can behave arbitrarily, and that can even model an adversarial behavior. But what about its third type of players, which we can call rational players,
05:21
or some people like to call selfish players. Players that want to maximize their own gain, even if they can deviate from time to time. And that is the goal of this paper, and to present our result, first our model.
05:42
We consider only one committee, so what is happening inside only one committee. And we assume that we have another set of n players, and each player knows its index in that set. That is not a huge assumption, because that is how the current consensus algorithm for blockchains are used.
06:10
We also assume that we have a synchronous communication, and messages cannot be lost. So when a message is sent by a player, it is received by all the players at the end of the corresponding phase.
06:24
And all our players are rational, so they try to maximize their expected gain, and what we will try to compute are the different Nash equilibria. A situation where all the different players cannot improve individually their own gain.
06:46
In each round, we have two phases, the propose and the vote, as I said. In this propose phase, there is one designated player that proposes a block. And first of all, assume that the proposal is always valid.
07:02
Then that block will be proposed and sent to the rest of the committee. And in the vote phase, each member, each player in that committee, will actually send a vote to all the others. Then everyone will collect the vote that were sent, and then they will count if they have enough votes to decide.
07:32
If there is enough votes, then they decide, otherwise they go to the next round. And then we will have a new proposal.
07:41
A new propose phase, a new proposal, and then they will continue until they reach a decision. There we can see multiple actions that are done. And we have cost of executing the protocol. And basically, we can see that at each round, the players can send a message or not.
08:02
If they send a message, they pay a cost they send. That is basically the cost of sending a message. And if the block is produced, meaning that we have at least new votes for that block, the players are rewarded.
08:24
And for the reward, we studied two cases. First, the case where all the players in the committee are rewarded, no matter if they vote or not for the block once it is produced. And the second one is when the block is produced, we only reward those that voted for that block.
08:46
The objective of all the players is to maximize their expected gain. And what they can do is just deciding if they can send or not a message. That's all they can do here.
09:00
And re-asking our question, which is our consensus property is guaranteed in the presence of rational players, we can change it by asking ourselves if we have equilibria that satisfy the consensus. Recall that new is the minimum number of votes to consider a block as produced.
09:26
We consider here the case where all the players are rewarded once a block is produced. Our results are the following. If we require only one vote to consider a block as produced, in equilibrium, we have exactly one player that votes.
09:50
And the others will do nothing. In this equilibrium, we have exactly one vote, which is enough. The block is produced, and since we assume that all blocks are always valid, then we have the consensus properties.
10:05
Now, when we assume that we need strictly more than one vote to consider a block as produced, we have two types of equilibria. In the first equilibrium, no player votes. Basically because they think that the others will do nothing, and so they prefer not voting as well,
10:28
because one vote is not enough to produce a block. So we do not have termination. But in the second type of equilibrium, we have exactly new players that vote.
10:45
In that case, we have enough votes to consider a block as produced, and exactly the number that is enough. Since the block is always valid, then we consider the block as produced. And so we have the consensus properties.
11:01
This is for the case where we reward all the community members or the players once the block is produced. Now, when we go to the second type of rewarding, where we reward only the players that vote for the block that is produced, then we have slightly the same kind of equilibrium.
11:23
First, the case where we need only one vote to consider a block as produced, at least one vote, we have basically the same equilibrium, but here all the players vote for the proposed block. Because if they do not vote, they will not be rewarded, so they have an incentive to vote here.
11:46
And when we consider needing more than one vote to consider a block as produced, we basically have the same type of equilibrium as before as well. Either new players vote because they think that the others will do nothing, so they do not have the incentive to do so,
12:05
or enough players vote, and over here, enough is even all of them. If they think that enough will vote, they all will vote as well. Because if they do not vote, they do not have a reward. One thing interesting here is that in this setting, when we reward only the ones that vote,
12:28
more messages are sent when at least one message is sent, which is basically the only difference with the previous setting. Now, we can consider a bit more realistic scenario where some invalid block can be proposed.
12:50
And to do that, we model it by considering Trembling Hand Effect, which basically means when the proposer wants to propose a block with a really small probability,
13:04
that block can be invalid. Everyone knows that such an event can happen, but no one knows in advance if the block is valid or not. And so, we can draw the action space now of everyone. Since the proposal can be valid or not, then they can decide to check or not the validity.
13:27
And that is the only way to know if the block is valid or not, checking the validity. If they do not check, they do not have any validity information. And basically, in any kind of scenario, they can decide to vote or not for the proposal,
13:44
knowing that the block is valid or not. And we will do this similar analysis as before. And before doing that, let us just recall the cost and highlight the new cost that we have.
14:01
Previously, we only had the cost of sending a message. Now, checking the validity also has a cost, which is a seat check. If enough votes are sent for a block that is proposed, new again, in this case, we consider the block as produced,
14:22
and we reward our players by R. Again, we'll consider the two cases where we either reward all the players or we reward only the one that votes. We assume that when an invalid block is produced,
14:41
then all the players will incur a cost kappa minus kappa. And we assume that kappa is greater than this to have a guarantee that the cost is pretty high in general. Now, each player will decide either to check or to send a vote.
15:07
They now have two kinds of actions they can manage. And their goal again is to maximize their expected game by reducing the cost of their actions, basically.
15:21
And our results are the following. If we consider that we need only one vote to consider a block as produced, and we reward all the players once a block is produced, then we have one equilibrium.
15:42
In that equilibrium, we have exactly one player, again, assuming the proposer, that checks the validity of the proposal and votes only if that proposal is valid. The others do nothing. In this equilibrium, we basically do have the consensus
16:04
because only valid blocks will be produced and we'll get the vote and invalid blocks will not get the vote. So that is a really nice equilibrium. Now, when we consider needing strictly more than one vote
16:21
to consider a block as produced, we have the following equilibrium. And they resemble the one we had where we had only valid blocks as well. Either no player votes, nor checks the proposal validity, so no block is produced anyway, we do not have termination, because all the players think that the others will do nothing.
16:46
So one vote will not be enough to produce the block. And the second type of equilibrium is equilibrium where we have exactly one player that checks the validity of the proposal and votes only if that proposal is valid.
17:03
Then we have new minus one other players that vote without checking the validity and the rest of the players do nothing. Basically here, we always have new minus one votes for any block proposed, valid or invalid,
17:20
but we'll have in addition one more only when the blocks are valid. So only valid blocks will reach the threshold of new and the block will be produced. So we have consensus because only valid blocks are produced and the invalid one are not produced.
17:40
Then we can go on what happens when we reward only the voters. Here, the equilibria are slightly different, not just slightly, we have a huge difference with the previous equilibria.
18:00
First, we have a similar equilibria as before when we consider that we require only one vote to consider a block as produced. All the players will check the validity of the proposal and they will all vote only if that block is valid. We have consensus. In this case, they all want to vote
18:21
such that only valid blocks, they want to vote to get a reward, excuse me, but they do not want to make an invalid block accepted because of themselves. So if they think that the others will check, then they will check as well. But we now have a new equilibria.
18:41
And in this equilibria, all the players vote every time without even checking the validity. So we have termination directly because any kind of block will receive n votes.
19:00
But we cannot ensure the validity because if an invalid block is proposed, then that block will be produced and we are doomed. That is the biggest difference with the previous equilibria. And actually, we have the same when we consider requiring more than one vote
19:21
to consider a block as produced. So here, either no player votes nor checks the proposal validity, so we do not have termination, or the second equilibrium is an equilibrium where everyone sends without even checking
19:42
the validity of the proposal. So all blocks are accepted and produced, but we cannot ensure the validity. And we have another type of equilibrium where as indicates where we reward all of them,
20:04
we have enough, we have all time, we have new minus one players that vote. So we always have new minus one votes for every type of blocks that is proposed.
20:21
And then in case of valid blocks, we have n minus new plus one other vote such that when the block is valid, everyone votes and everyone is rewarded, but if the block is invalid, we only have new minus one votes, and so the block is not accepted.
20:43
And this is our result for this paper. To conclude, in this paper, we analyze the rational behavior in community-based blockchains. We do that under two different reward schemes. We assume that all our players are rational in the community,
21:04
and we assume that the communication is asynchronous. We found that in all the settings we study, either having only valid blocks or not having or having invalid blocks from time to time, we always have good equilibria.
21:21
However, these good equilibria are not unique. We may have coordination failures or free writing that violate the consensus properties in the end. Moreover, our analysis shows that there is one reward scheme that seems to be better than the second one.
21:41
Basically, rewarding all the players once a block is produced is better than rewarding only the one that votes for the block. Why? Because first, in the good equilibria, less messages are sent. Energy consumption-wise, it's way better
22:01
because we require less messages. More often and more interestingly, when we reward all the players once a block is produced and when invalid blocks can be proposed, we cannot have equilibrium that violates the validity property.
22:23
Basically, no invalid blocks can be produced. Whereas when we consider rewarding only the voters and those that voted for a block produced, we do have an equilibrium that violates the validity property. So rewarding all the players
22:40
seems to be an interesting reward scheme that needs to be investigated more with respect to less hypotheses on the model and more work needs to be done. Thank you.
Recommendations
Series of 3 media