Post Alpenglow consensus improvements

[AshwinSekar]

We activated Alpenglow on testnet and devnet successfully, and we are gearing up to activate on mainnet soon.
I wanted to share my thoughts on potential next steps for solana consensus.

Motivation

Alpenglow consensus is a major improvement over Tower. It's both simpler to understand and faster to achieve finality.

The next long term goal for Solana is to transition into a multiple proposer architecture (Constellation). There are ongoing efforts to enable this on the block production side. From a consensus perspective the next step in the roadmap is to transition into a simple multiple proposer setup (minCP) with 2 proposers.

In minCP we don’t add all the machinery of constellation (attesters, aggregate attestations etc.) and instead use the current flow simply with 2 proposers. Voters then adjust Alpenglow to consider vectors of blocks rather than voting on a single block.

But going straight to minCP with Alpenglow in its current form as the underlying consensus has a few issues.

1. Alpenglow still gives enough grace for significant slot stretching behaviors which can be dangerous for minCP. In minCP consensus is limited by the worst proposer. As there are now more proposers, a higher frequency of slots can end up taking the skip or fallback paths leading to consensus instability / slowdown.
2. This slot stretching grace also has economic implications since it can allow the stretching proposer to view other proposers and frontrun transactions in those proposals or otherwise mess with the ordering with a significant information advantage.
3. The fallback path adds significant complexity to the protocol which it would be nice to remove as we add more complexity through multiple proposers.

Remove fast path & fallback path for even faster finality

Is the fast path actually faster?

Below is simulated data based on mainnet stake distribution see https://maxresnick.github.io/votor-post/ for more details.

Simulated data shows that in the vast majority of cases the fast path is actually slower than the slow path. In this case, it would be better to remove the fast path and instead revert to an earlier version of alpenglow where nodes are allowed to vote skip after notarize

The benefit here is reduced complexity while also mandating a higher penalty for slot stretchers. Under the fallback path, it's possible and profitable for a slot stretcher to toe the timeout, as a block with 50% Notarize and 50% Skip can still end up being finalized. Removing the fallback path denies this result.

Even faster finality

Removing the fast & fallback paths simplifies the protocol. This doesn't improve finality on its own, but this allows for a technique to achieve even faster finality.

The crux of this technique comes from the observation that the first round vote (Notarize), only requires the block id in order to be cast. This does not require the block to be fully executed, in fact it only requires that one shred from each FEC set of the block (1 / 64 total shreds) to be received in order to construct the block id.

Each FEC set is dispersed through turbine / rotor, such that 64 root / relays are selected. It's highly likely that at least one of these 64 are within a validator's locale, allowing the block id to be constructed well before the full block is received.

Thus we vote Notarize as soon as the block id can be constructed and vote Finalize once the full block has been received and executed.

Note that this optimization is only possible without the fast path. If the fast path was still present, a leader could withhold the remaining shreds after receiving 80% Notarize, and we would finalize a non-existent block.

Simulating this technique shows us an improvement over current Alpenglow (best of slow or fast path) for the majority of leader locations

At this point we have a protocol that is simpler than current Alpenglow while also achieving faster finality while giving less flexibility to slot stretchers that exploit the fallback path.

One more benefit of this protocol is that we can also get a fast skip confirmation when the leader does not produce a block on time. A skip certificate made up of only first round skip votes tells us immediately that no block can be notarized or finalized in this slot. This tool can be helpful for future multi proposer and slot times less than network delay style consensus improvements.

Leader predictability and further addressing slot stretching

Even with this improved protocol, we have more wiggle room than we would like for slot stretchers. Alpenglow is a responsive protocol which means every node keeps track of its own local timeouts for each slot. Whenever a node receives the parent_ready event, it starts a local timer for when it must receive the block. But this local timeout has to be set with a lot of grace.

In particular, we set it to 2 where Delta is the maximum network delay of a message. This comes from one network delay for the leader to send us the block and another network delay because we may have entered the leader window up to a network delay earlier than the leader. For example, if the leader is in Tokyo and we are in London, the leader would receive their parent_ready event about 75ms later than us and it would take another 75ms for them to send their proposal to us.

Ideally we could get this leniency down to one network delay. This is possible by using a globally synchronized clock. This seems scary since it requires introducing a new component to the protocol but byzantine clock synchronization has been studied extensively and there are solutions in the literature that would be compatible with our current security assumptions and give us a very accurate synchronized clock anza-xyz/agave#13981..

Once the BFT clock synchronization primitive is in place, we can adjust timeouts to be based on the global clock instead.

With this protocol we managed to reduce the initial deadline for a notarize vote from 2 network delays after the start of the slot (in our local view) to 1 network delay after the start of the slot (in the global view). This significantly reduces the surface area for slot stretching behaviors.

In addition to tighter timeouts this change would improve the predictability and determinism of the leader schedule improving leader targeting. Transaction senders now only need to measure the latency to each leader along with the global clock and leader schedule.

This also fixes epochs at a set amount of time. Finally, it would improve the read layer since transactions could be more easily associated with timestamps derived from the global clock, rather than relying on leader reported values.

Tradeoffs of Fixed View vs Responsive View Protocols

The advantage of responsive view protocols is that they proceed as fast as the network allows. Maybe it would be more accurate to say they proceed as fast as the leaders propagate their blocks and the network allows. What this means is that with honest leaders who propose right away, responsive view protocols can potentially be faster than fixed view protocols.

It's up to us to decide how much we can trust our leaders to behave in the best interest of the protocol when that conflicts with their own protocol rewards. So far I would say the evidence is mixed. We see some slot stretching behavior but not nearly as much as the fully selfish equilibrium predicts.

Another difference between fixed and responsive protocols is that during periods of asynchrony (when the network delay exceeds ), a responsive protocol does not advance the slot number while a fixed view schedule continues to advance the slot number. This requires careful handling of intermediate skip certificates to preserve liveness.

Conclusion

These improvements are relatively minor and can be independently delivered on a quick timeline. I believe that with these changes we'll be in a great spot to transition to minCP and full MCP in the future.