Thread by @jadler0

What Avalanche is Not, Episode 2

Last episode, we discussed fees and how it's impossible for Avalanche's X-Chain to have non-fixed fees without making fundamental trade-offs. On today's episode: rewards, and how they're similarly impossible.

Let's start by clearing up some confusion from last time. It's not “impossible, period” to have non-fixed fees in Avalanche; rather, it's impossible without making some additional trade-offs to fundamental assumptions or guarantees provided by AC.

The recurring thesis of these threads is that there's no silver bullet solution. Everything is simply a point in the trade-off space. And we'll explore the concessions Avalanche needs to make in order to provide the guarantees and performance it promises.

Before we dive into today's episode, let's do a quick overview of how Classical Consensus protocols and Avalanche Consensus (AC), used by Avalanche's X-Chain, work.
In Classical Consensus, all validators talk to all other validators to vote on the next block proposed by a leader.

All-to-all communication is expensive, and this generally requires quadratic message complexity that must be processed by all validators, i.e. at least cubic network overhead (excluding cryptographic optimizations, e.g. signature aggregation, which is a story for another day).

As a result of this communication complexity, classical consensus protocols generally don't scale beyond a few hundred validators before consensus overhead becomes unwieldy.

Avalanche Consensus on the other hand uses random subsampling. Every round, each validator asks a fixed number of other validators (weighted by stake) for their votes. They repeat this for a number of rounds, progressively building their confidence in the network's opinion.

The proofs are involved, but show that under certain assumptions AC can come to consensus with no leader on a DAG of transaction batches with negligible probability of failure. With constant communication complexity, AC can handle millions of validators!

arxiv.org/abs/1906.08936

With that out of the way, let's get to the meat of today's episode: rewards. Permissionless consensus protocols require some sort of incentive, otherwise they rely purely on altruism. And we all know how well altruism works long-term, especially when that altruism is expensive.

Nakamoto Consensus introduced the Nakamoto Incentive, a pair of carrot and stick. The carrot (incentive) is a block reward (+ fees), while the stick (disincentive) is a penalty if a majority attack is attempted. We'll look at penalties in the next episode.

So, how does Avalanche handle rewards? In the same PR that was merged around 24 hours prior to mainnet launch, (somewhat) explicit validator rewards were added to the docs for the first time. Let's take a closer look!

Here are the validator rewards:

“A validator only receives a reward if they are sufficiently correct and responsive while it was validating. The size of the reward depends on how long they validate, how much they stake, and how many AVAX tokens exist.”

"Sufficiently correct and responsive" isn’t particularly informative, so let's examine the token whitepaper:

files.avalabs.org/papers/token.p…

Here's the relevant section in question, on the token minting (i.e. reward) mechanism. Not much information here either! 🤔

Let's break down the two facets of the reward structure.

First, uptime/correctness. The whole reason AC scales to a much larger validator set than Classical protocols is that at no point are validators privy to the votes of the entire validator set. That's kind of the whole point!

If validators don't know how all other validators have voted, we can't reliably come to consensus automatically on the uptime of a validator (without regressing to all-to-all communication of course). It's, quite simply, impossible.

Consider this scenario: Alice refuses to communicate with Bob, but communicates with all other nodes. Bob can't prove to other nodes that Alice is doing this. When it's time to mint coins, Alice is assigned a nice reward because she had 100% uptime, as seen by everyone but Bob.

What is Bob to do?

Reject the state transition, permanently forking himself off the network irrecoverably? Congrats, you've just introduced a DoS vector!

Accept the state transition? Congrats, you're not actually coming to consensus on uptime!

Second, responsiveness. Again, we can't come to consensus on this without making a fundamental concession, e.g. extremely aggressive synchrony assumptions.

To show this, consider two groups of nodes, geographically separated. They have low-latency communication within a group but high latency between groups. Clearly the two groups cannot come to agreement on the latency of any one node. Latency is a two-way street after all!

And that's a wrap for today's thread. We discussed why coming to consensus on rewards is impossible given the current assumptions and guarantees AC, and Avalanche, promise. Next episode, we'll discuss the other facet of the Nakamoto Incentive: penalties.