Announcements

Oct 4, 2020

Highway: A Cartel-Resistant Consensus Protocol

Highway: A Cartel-Resistant Consensus Protocol

At CasperLabs, we recently rolled out Highway, the first specification for a provably live and secure CBC Casper Proof of Stake protocol. As mentioned, Highway will include many novel features.

In this post, I will walk through one of these features — a reward distribution scheme designed to discourage cartel formation among validators.

First off: Why do people form cartels?

To see a cartel to emerge in a given market, two basic conditions need to be satisfied:

  1. It should be possible to monopolize/oligopolize the market. The nature of the business should allow for erecting barriers to entry, taking possession of the entire supply and hurting participants of smaller size.
  2. Monopoly/oligopoly profits should be high enough to compensate for the costs of sustaining the cartel and make it worth the effort. The demand should be at least a little bit inelastic, that is to say, buyers should exist who are willing to pay more for a product, after the cartel ramps up the price.

Or more succinctly, people form cartels if it pays more. If the circumstances allow it, it’s only a matter of who will do it first.

So? Why should we care if a validator cartel forms?

Decentralization is a central tenet of CasperLabs’ ethos, and one which we do not follow without a reason. Decentralized networks are more versatile, durable and harder to suppress than their centralized counterparts. These properties are sought at Layer 1, because people who want to build at Layer 2 would want to have the same level of freedom as the entrepreneurs who built the first internet businesses in the 90’s. A cartel is centralized by definition, so a Layer 1 controlled by a handful of entities would deter people from adopting and building on it. You can compare the level of adoption of Ethereum versus EOS as a prime example.

But how would that work exactly? What does a validator cartel look like?

Censorship. In analog systems, erasing someone from existence requires physical effort. However, digital systems can be programmed to ignore certain people with much higher efficiency. A validator cartel does just that: whitelists other cartel members, and blacklists everyone else. Non-cartel messages are simply ignored, and in the eyes of the consensus protocol, they appear to not have been sent.

Now, since censored participants cannot prove to the protocol that they did any work, they also cannot receive any rewards from the protocol.

How does Highway discourage cartel formation?

With most projects, if a miner or validator fails to send a message when they should, they don’t receive any rewards, and may even possibly get punished for being offline. This poses a problem for the incentive mechanism because such a fault cannot be attributed to a validator with 100% certainty. A validator could appear to be offline, but in reality could be subjected to continuous censoring by a cartel. This incentive mechanism results in the discouragement of small sized validators from the protocol. To demonstrate how this works, we will introduce a basic sequential game:

A (a cartel) and B (a non-cartel minority) are validators with 2/3 and 1/3 of the total stake respectively. With the given sizes, A can censor B, but not vice versa. 3 tokens are minted as a reward for the participants, to be delivered proportional to stake if they send a message and are not censored. Moreover, we assume that there is a cost c of sending a message, and we assume only B incurs it for the sake of simplicity.

First, B will choose whether to enter or not. If B chooses to enter, A receives 2 payoff by default, and then can choose whether to censor B or not. If B is not censored, B’s payoff is 1-c, otherwise -c. Finally, if B chooses not to enter, then A receives 3, the whole reward.

Image for post

Using backward induction, we conclude that the subgame perfect equilibrium is Don’t Enter, because B would not put himself in a position where A can censor him without a decrease in payoff. In such a protocol, the rational choice for a minority is to not participate.

In Highway, we disarm cartels by taking away their ability to hurt validators with smaller stake. To be clear, validators can still be censored. Nevertheless, they still receive rewards, despite appearing not to have sent any messages.

This concept is called payoff symmetry in game theory, and the games which admit this property are called symmetric games. In our case, it means that the reward-per-staked-token is the same for every validator, regardless of whether they have sent messages or not.

So, are you going to reward validators even though they don’t propose blocks or vote on them? That doesn’t sound right. Then why should anyone send any messages at all?

Because it’s not as simple as that. On top of payoff symmetry, we also implement reward correction. What that means is that the total reward is scaled with the degree of participation in the network. As an example, if only validators adding up to 80% of the total stake send messages to finalize a block with a block reward R, then the block reward is corrected down to 0.8*R. This way, validators are put in the same boat. The punishment of censorship, freeloading or any other liveness fault gets shared by everyone equally.

Next, we eliminate the risk of freeloading by setting a minimum stake. This puts a lower bound on the reward that can be received by becoming a validator, which itself is set to be higher than the cost of participating. This renders participating in the protocol the only rational choice for the prospective validator. The result is a network with numerous honest validators, instead of a myriad of parasitic ones.

Additionally, an increase in token price means that the stake limit can be lowered, because more validators can be sustained with the same level of rewards. If the network can support 100 validators at launch, a 100x increase in token price will let it support 10,000. The more value the network accrues, the more decentralized it will become.

Refer to this post for a more detailed analysis of freeloading.

Ok, then we can get away with rewarding offline validators… I still don’t get how this helps with cartels?

Going back to the game we introduced before, we will make some modifications to the payoff of (Enter, Censor). Since 1/3 of the network is being censored, total reward drops down from 3 to 2. Then, 2 is distributed proportionally between A (which receives 4/3) and B (which receives 2/3).

Image for post

In the new game, B has a greater payoff if he chooses to enter, regardless of A’s choice — if the cost is smaller than 2/3. Thus, knowing that B will enter regardless, A would want to end up with the outcome where he has a higher payoff, namely Don’t censor which gives him 2 points. In this setting, the subgame perfect equilibrium is (Enter, Don’t censor).

Of course, this game is a simplified version of what happens in Highway. But the analogy holds: the only rational choice for a majority is to not censor. This property makes Highway radically different than most other protocols out there: given enough time, any cartel-prone Proof of Stake protocol would have a very uneven distribution of stakes. However, being the big fish doesn’t give you as much upper hand in Highway, so its Gini coefficient would be lower than its counterparts.

Without an increased payoff from censoring, there is simply no reason to form a cartel. By setting the rules right, we effectively nip cartels in the bud.

If you liked this post and would like to learn more, you can join the conversation with our development team on our Discord.


Sign up for our newsletter!