Adversaries, Distributed Ledgers & Decentralization

A number of alternative structures for distributed ledgers have been proposed in recent years. All of these solutions offer better decentralization, faster and more numerous transactions serving a larger number of nodes.

I have been skeptical of such systems for a long time.

Given an adversarial environment I don’t believe you can maintain secure decentralized consensus AND have timely confirmation between arbitrary parties AND scale up to a large number of nodes/transactions.

Each word in that statement is very important. We can easily throw away decentralization to scale up processing and transaction rate. However, considering that one of the core motivations of distributed ledgers is to remove trusted third parties I don’t see wide adoption of such systems appealing. As such I will limit my discussion to decentralized consensus.

There is an inherent trade-off when decentralizing, the more nodes/transactions the more processing/communication between nodes, the longer it takes for an arbitrary party to be aware of the global state.

In order to have secure transactions between parties, each party must be aware of the global state of the network. We can easily throw away security and have really fast transactions, but our system would be worthless.

Proof-of-Work blockchains solve this security of global state problem through mining (or rather, through the computational power required to produce valid blocks). An adversary can’t doublespend without investing considerable resources to acquire the computational power required to produce valid blocks faster than the rest of the network.

The tradeoff proof-of-work blockchains make for this secure decentralization, is necessarily against scalability. Mining blocks is computationally expensive and takes time. The transactions per second is therefore tightly bound to the size of the produced blocks and the rate at which they are produced.

Any alternative system must provide a mechanism for achieving secure global state (and further, they must do so in a way that is more efficient than a proof-of-work blockchain).

And there we hit the crux of my issue with the new generation of distributed ledger structures, they all fundamentally fail to achieve the above.

It isn’t that many of these systems aren’t mathematically sound, they are. The issue is that the adversarial models presented by these systems are incompatible with real world networks.

Without questions, they require us to make one (or more) of the following assumptions:

  • All peers have a timely, complete/uncompromised view of the network.
  • All peers (an honest, total majority, or a partial but delegated majority) are online/reachable at all times.

Again, all those words are important.

A timely and complete view of a network is a very hard task in an adversarial network. Adversaries may partition the network, transactions may get dropped by relay nodes, undersea cables get cut etc. In proof-of-work blockchain systems, any peer is able to estimate how complete their view of the network is at any given time. Further, peers will only accept blocks in order and with expected difficulty.

That mechanism is missing in many proposals. Without the convergence provided by a difficult-to-construct block, peers have no way of establishing trust in the transactions or other messages they are receiving.

Implementing “trusted witnesses” solves that problem. Trusted witnesses are nodes that are known to have greater connectivity, or are otherwise trusted to maintain the canonical global state. While it is conjecture, I believe that any mechanism to “decentralize” such a witness will rapidly resemble a blockchain.

Vote driven consensus, where peers directly or indirectly vote (weighted by their stake in the system) on new blocks, can be seen as a special case of “trusted witnesses”, albeit one with a sound economic argument - peers with a greater stake in the system are unlikely to harm it, otherwise they would harm their own interests.

(There are arguments to be made about the relative centralization of proof-of-work verses stake distribution that I won’t go into. I instead want to address my core complaint of such constructions: availability.)

To ensure that transactions are confirmed in a timely manner, voting must also happen in a timely manner.

In order for voting to be secure, all parties with stake in the system must vote (or some statistically random sample of parties must vote, or some delegated representatives of parties must vote) in every round.

This requires active participation in the system (peers must be online), and a significant amount of cross communication (every party must receive, and verify every other parties vote).

If a party with a large stake in the system drops offline, the system either grinds to a halt, or the stake required to produce an adversarial block decreases substantially.

It does not seem practical for systems to require that all parties remain online indefinitely. Delegated voting systems trend towards centralization, and are difficult to reconcile with a large user base who may be uninterested in how the system operates (as such they are likely vulnerable to vote-buying and other electoral rigging).

I hope that I am wrong. Maybe there is a way to provide secure decentralized consensus AND have timely confirmation between arbitrary parties AND scale up to a large number of nodes/transactions.

However, there is no system today which can promise all three, despite an epidemic of systems making such promises.