Thoughts on a (CAP “like”) impossibility result for consensus protocols.

Thoughts and an ELI5(hopefully) explanation of Impossibility result proved by — Andrew Lewis-Pye & Tim Roughgarden 2021.

I will use an “Amphitheater DAO” story as a backdrop for explaining the result.

Story backdrop: The “Amphitheater DAO”

In a duel, once a gladiator overcomes his opponent, “The Editor” (designated person) decides whether the vanquished lives on to fight another day. This editor guy is usually depicted in movies as an evil person casting his thumb up, down or, sideways. Let’s replace this evil Editor — with an amphitheater decentralized autonomous organization(DAO) where spectators decide the fate of the fallen gladiator.

https://www.thoughtco.com/how-did-gladiator-fights-end-118422

A consensus protocol will help us build this DAO. A good protocol will allow the DAO to agree on a “fair random & final” result that cannot be predicted a-prior

After reading this post hopefully, one would understand that no conceived consensus protocol can satisfy a certain set of properties.

What impossibility result was proved?

Abstracting all known BFT consensus protocols (pBFT, Nakamoto, Eth, Algorand, Tendermint, Dfinity) the proof claims that, it’s impossible for any consensus protocol to satisfy ALL of the following three properties.

  1. Be permissionless

2. Guarantee liveliness independent of consensus-clout(explained later) in synchronous setting.

3. Algorithmic finality in a partially-synchronous setting.

Mapping the above impossibility result to the “Amphitheater DAO”

What does it mean to be permissionless?

A permissionless amphitheater would have no admissions limits for the spectators. Anybody and any number or spectators can join in to vote. Let’s envision the duel being hosted as a virtual event and there are no physical seating constraints. Anybody can join and vote over the internet.

A permissioned amphitheater on the other hand would have a fixed number of preassigned and pre-ticketed seats (physical or virtual). The spectators have to be vetted such that they are not biased towards any particular outcome. Biased spectators won’t allow for to fair and equally probable consensus results.

In the blockchain world Proof of work (POW) protocols like bitcoin’s consensus are permissionless theaters. While most proof of stake(POS) consensus protocol viz Algorand Tendermint are permissioned. The key takeaway here is: in permission theaters, cardinality information is “known and available” a-prior for the consensus protocol to use. A permissioned theater knows the number of spectators before the protocol is executed. A permissionless amphitheater lacks cardinality information.

The protocol design space lets us decide the type of amphitheater, permissioned or permissonless.

Ideally, we’d prefer permissionless amphitheaters because permissioned models can be reduced to permissionless.

What does it mean for liveness to be independent of consensus-clout?

Define: liveness & consensus-clout

Roughly speaking Liveness means, given some minimal optimal conditions are met the protocol must decide on the fate of the fallen gladiator. The decision cannot remain in abeyance ad-infinitum.

So what is consensus clout? It’s some meta embodiment of “decision” horse-power. That is, how much can a single spectator influence the outcome?

There are at least 2 consensus protocol paradigms to choose from based on clout classification.

a. Lottery based clout (POW protocols)

There exists a random oracle that picks a random person from the “universe” who then decides about the gladiator. If the chosen person is not present, unwilling, or unresponsive — we just run another draw from the random oracle.

b. Vote based clout (POS protocols)

Spectators can vote with some pre-agreed voting rules. Thus Majority/Super-majority can decide the fate of the losing gladiator. Calculating the majority requires knowing the cardinality for the clout.

Thus liveness has to be guaranteed independent of fluctuations in consensus- clout. Such independence is trivially achieved in the voting-based protocols. Same voting protocols work for 3,5,7,11,91…infinity number of voting agents/spectators (known upfront). In the lottery-model, the property of independence is not trivially guaranteed. Let me explain: I just presented a lottery solution, where the oracle’s random draw is independent of the number of spectators in the universe. However in the computational universe, true random oracles cannot be implemented or expressed as Turing machines. True random oracles with unknown domain cardinality, need an undefined amount of description. (Description doesn’t refer to the length of the tape which can be infinite)

Summary: Voting-based (POS) protocols can guarantee liveness and safety with arbitrarily small or large amounts of consensus-clout. However, the same guarantees are difficult (maybe impossible) to achieve in the proof of work/permissionless blockchains where the definition of consensus-clout’s is left outside the scope of the protocol.

In the fictional lottery-based protocol, “random oracles” were convenient fictional gadgets that don’t have known computational reductions (aka algorithms). Roughgarden formalizes consensus-clout as resource pools in his paper.

The protocol design space lets us decide the type of consensus-clout, lottery or voting based.

Any consensus-clout mechanism is acceptable as a solution.

What is algorithmic finality in the partially synchronous setting?

The consensus protocol must guarantee that at “some” point in time the fate of the gladiator is permanently sealed. Beyond that point, there exists no flaw or glitch in the protocol, that the losing gladiator can use to appeal against the result. This concept of permanent seal seems trivial but it’s not ..

In our gladiator story, in the permission-less(POW) oracle-based protocol the gladiator can always contest the decision’s finality in the following scenario.

The random oracle chose ‘spectatorX’ but then moved onto the ‘spectatorY’ as X didn’t respond. Y’s decision was agreed upon, but maybe the result would have been different if we would have waited long enough for person X to respond. Many such arguments can be bought up including refuting the veracity of the oracle itself in the lottery-based clout model.

Above phenomenon results in the following problems in the bitcoin POW consensus — confirmations, forks, selfish mining, etc. In POW, finality is never algorithmically guaranteed instead, it’s a probabilistic guarantee (based on length of the chain). POS chains employ voting based protocols and they provide algorithmic finality guarantees (simply put: it’s absurd to argue against a hypothetical voting outcome where 10 authenticated votes are cast in favor and 9 were against. The 10 in favor and 9 against decision is final)

The protocol design space lets us decide the type of finality, algorithmic or probabilistic.

Ideally we would prefer algorithmic finality as it’s a stronger guarantee.

So what protocols are impossible to be built for our gladiators.

Roughgarden’s result states that a consensus protocol CANNOT simultaneously satisfy all of the following conditions.

1. Be Permissionless: A open amphitheater, free for anyone to join
2. Liveness: Guaranteed decision within some time frame
3. Algorithmic Finality: Bulletproof sealing of the gladiator’s fate.

If we deploy known (POS and POW) consensus algorithms to solve the gladiator problem, we get the following feature matrix.

References:
Byzantine Generals in the Permissionless Setting: Andrew Lewis-Pye, Tim Rough Garden
https://arxiv.org/abs/2101.07095

How Did Gladiator Fights End? — N.S. Gill
https://www.thoughtco.com/how-did-gladiator-fights-end-118422

Random oracle
https://en.wikipedia.org/wiki/Random_oracle#Limitations

Digital physics hypothesis
https://en.wikipedia.org/wiki/Digital_physics

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store