Tower BFT

This design describes Solana's Tower BFT algorithm. It addresses the following problems:

Some forks may not end up accepted by the supermajority of the cluster, and voters need to recover from voting on such forks.
Many forks may be votable by different voters, and each voter may see a different set of votable forks. The selected forks should eventually converge for the cluster.
Reward based votes have an associated risk. Voters should have the ability to configure how much risk they take on.
The cost of rollback needs to be computable. It is important to clients that rely on some measurable form of Consistency. The costs to break consistency need to be computable, and increase super-linearly for older votes.
ASIC speeds are different between nodes, and attackers could employ Proof of History ASICS that are much faster than the rest of the cluster. Consensus needs to be resistant to attacks that exploit the variability in Proof of History ASIC speed.

For brevity this design assumes that a single voter with a stake is deployed as an individual validator in the cluster.

The Solana cluster generates a source of time via a Verifiable Delay Function we are calling Proof of History.

The unit of time is called a "slot". Each slot has a designated leader that can produce a block B. The slot of block B is designated slot(B). A leader does not necessarily need to generate a block for its slot, in which case there may not be blocks for some slots.

For more details, see fork generation and leader rotation.

Validators communicate which fork they think is the heaviest through votes. Each vote v is signed by the validator that produces it, and is of the form (i, B), where i is the public key of the validator producing the vote and B is a hash identifying the block being voted for.

Making votes on a particular fork incurs a lockout on that particular fork. A lockout is a designated period of time, measured in slots, within which a validator cannot vote on another fork. The purpose of the lockout is to force a validator to commit opportunity cost to a specific fork. Lockouts are measured in slots, and therefore represent a real-time forced delay that a validator needs to wait before breaking the commitment to a fork.

Validators that violate the lockouts and vote for a diverging fork within the lockout should be punished. The proposed punishment is to slash the validator stake if a concurrent vote within a lockout for a non-descendant fork can be proven to the cluster.

The basic idea to this approach is to stack consensus votes and double lockouts. Each vote in the stack is a confirmation of a fork. Each confirmed fork is an ancestor of the fork above it. Each vote has a lockout in units of slots before the validator can submit a vote that does not contain the confirmed fork as an ancestor.

We call this stack the Vote Tower.

When a vote is added to the tower, the lockouts of all the previous votes in the tower are doubled (more on this in Vote Tower). With each new vote, a validator commits the previous votes to an ever-increasing lockout. At 32 votes we can consider the vote to be at max lockout any votes with a lockout equal to or above 1<<32 are dequeued (FIFO). Dequeuing a vote is the trigger for a reward. If the vote on the top of the tower expires before it is dequeued, it and subsequent expired votes are popped in a LIFO fashion from the vote tower. The validator needs to start rebuilding the tower from that point.

Before a vote is pushed to the tower, all the votes leading up to vote with a lower lock expiration slot than the new vote are popped. After rollback lockouts are not doubled until the validator catches up to the rollback height of votes.