Models For Scaling Trustless Computation by Kyle Samani
Each of the major smart contract platforms is making a unique set of trade-offs. These trade-offs are not simply the presence or absence of specific features, but rather represent fundamentally different views of what trustless computation means.
This essay aims to provide a coherent framework through which one can understand these trade-offs and how they impact some of the predominant narratives in crypto such as digital gold, programmable money, censorship resistance, and permissionless-ness. Some definitions:
Censorship resistance – complete freedom of expression. In more technical terms, the ability to commit any arbitrary record to the blockchain.
Permissionless-ness – the ability to access the network and verify the integrity of the chain without asking a 3rd party for permission.
I will not explore layer 2 scaling solutions such as Lightning , Raiden , and Plasma .
But first, we need to establish context for the term “trustless.” Nick Szabo frames trustlessness as an inverse function of technical efficiency. Basically, the less efficient the computer, the more difficult it is to manipulate. The more difficult it is to manipulate, the more you can trust it, therefore making it trustless.
In other words, to paraphrase Szabo, blockchains trade technical efficiency for social scalability.
The ultimate manifestation of crypto is not just a trustless database (or blockchain) in which everyone agrees on its current state—it’s trustless general purpose computation, which is a superset of a database. This can be a little bit challenging to grasp.
Blockchains enable everyone on the planet to come to consensus about the state of the world.
Trustless general purpose computation is a step beyond that. It’s the ability to not just know the state of the world but to prove that a specific computation was run correctly .
Although Bitcoin is technically programmable—enabling trustless general purpose computation through its Script language—in practice Bitcoin is just a trustless database.
Although there are some efforts to make Bitcoin more expressive (such as MAST , taproot , scriptless scripts , and RSK ) none of these are in production today. To put it bluntly, developers have left Bitcoin for greener pastures.
Ethereum provided the first accessible platform on which developers could run any arbitrary computation trustlessly. Today, Ethereum owns the vast majority of the developer mindshare in crypto.
Many have called Ethereum a world computer . While this is technically true, in practice it’s not because of two related factors: throughput and cost.
Running a computation on Ethereum is on the order of 100,000,000x more expensive than running the same computation on Amazon Web Services (AWS).
The Scalability Trilemma
The challenge of scaling trustless computation can be thought of as a trilemma. The scalability trilemma posits that blockchains in which every node processes every computation and in which every node comes to consensus about the order of those computations can have two of three properties: safety, scalability, and decentralization of block production (DBP). DBP can be quantified as the number of block producers.
Scalability can be quantified as the number of transactions per unit of time that the system can process. Safety can be quantified as the cost of mounting a Byzantine attack that affects liveness or transaction ordering .
Note that safety does not refer to the integrity of cryptographic signatures, or the ability of a 3rd party to derive a set of private keys from public keys.
What causes a system to achieve one set of trade-offs vs another? A combination of consensus scheme and system architecture.
The remainder of this essay will explore these concepts, and lastly, loop in some interesting work in off-chain computation.
Each of the systems below makes a different set of trade-offs in pursuit of scalable trustless computation. Throughout this essay, I’ll refer to each leg of the triangle using these numbers:
A Fourth Dimension: Time To Finality (AKA Latency)
Although not explicitly part of the scalability trilemma, there’s a fourth dimension to consider in scaling systems for trustless computation: time to finality (TTF), which directly impacts latency.
Some systems never guarantee finality, but rather probabilistically approach finality (e.g. Bitcoin). Others offer a finality guarantee after some period of time. Finality is important not only to avoid double-spend attacks, but also because finality guarantees are necessary to enable cross-chain communications.
The slower the TTF, the higher the latency in cross-chain communications.
There’s not a visually clean way to represent TTF on a two-dimensional triangle. As such, I’ll use dark background colors to indicate fast TTF and light background colors to represent slower TTF.
Leg 1: Permissionless Proof-of-Work (Bitcoin, Ethereum 1.0, others)
Prior to Bitcoin, all digital cash systems suffered from the same fundamental flaw: users had to trust a 3rd party to administer the system.
This 3rd party could censor transactions. Designing a system in which anyone could verify the integrity of the chain and in which no single 3rd party could censor transactions was the primary design goal of Bitcoin. Proof-of-work (PoW) consensus made a censorship-resistant, permissionless ledger possible.
The downside of optimizing so strongly in favor of censorship resistance is that modern PoW systems don’t scale without centralizing block production. This fundamental tradeoff ultimately resulted in the Bitcoin Cash fork, which, relative to Bitcoin, will centralize block production (though there are debates about this practice).
Of the consensus models presented in this essay, PoW is the most permissionless. Literally anyone with a computer and an Internet connection can begin validating transactions and mining. This theoretically enables maximal DBP.
In practice, all permissionless PoW systems centralize block production. We know this empirically. Mining for all major PoW-based blockchains centralizes due to economies of scale in mining operations.
Today, no more than 20 organizations/pools control the vast majority of mining power in both the Bitcoin and Ethereum blockchains. Given our admittedly limited history, it seems likely this centralization of block production will always occur for both ASIC and GPU-based mining algorithms.
PoW systems suffer from slow TTF. They do not, by design, ever guarantee finality.
Instead, as new blocks are added to PoW-based chains, older transactions become exponentially more likely to be final. This is why many don’t consider Bitcoin transactions “final” until there have been six additional blocks confirming the transaction. Given 10-minute blocks, it can take an hour or even longer to finalize a Bitcoin transaction. At that point, the probability of a chain reorganization is close enough to 0 to consider the transaction final.
In practice, because of the economies of scale of PoW mining, PoW chains fall in the lower right-hand corner of the triangle:
Braided PoW (Kadena)
Kadena is the only system I’m aware of that’s attempting to solve the scalability trilemma using a PoW scheme.
Kadena accomplishes this by creating a “braid” of chains that it calls Chainweb. In Chainweb, each chain must, in addition to validating transactions in its own chain, validate block headers of some number of pre-specified chains in order to produce a new block.
To relay messages and value across chains, users need to submit Merkle proofs asserting the state of one chain to other chains in the Chainweb.
Because not all chains are directly connected, users may have to “hop” a few times to relay a message from one chain to another.
At first glance, this looks like Ethereum’s proposal for sharding (more on that below).
However, whereas Ethereum’s sharding implementation separates transaction collation and validation into spoke chains and a single hub chain respectively, Kadena doesn’t unbundle transaction verification and consensus. In Chainweb, every chain maintains its own consensus.
Kadena presents a fundamentally unique approach.
Kadena visualizes ChainWeb as follows:
One of unique traits of ChainWeb is that scaling the system explicitly increases security. Why? Because it becomes harder to mount 51% attacks across an increasing number of chains, each of which references blocks from every other chain.
In this model, undoing a transaction on one chain requires undoing transactions on every other chain in the system. Given how naturally intertwined the chains are, this becomes exponentially more difficult as the number of chains grows. This stands in contrast to blockchains on leg 3 of the triangle, in which the safety of the system in aggregate doesn’t substantially increase as the number of chains grows.
This design basically solves the scalability trilemma. But there is one major trade off: TTF and cross-chain latency.
Individual chains could be many hops from one another. Kadena aims to offer <1 minute TTF in a PoW scheme. Sending messages across the entire Chainweb will take a few hops, requiring a few minutes.
Despite this limitation, Kadena presents a real solution to solving the scalability trilemma that’s built on a proven consensus model: PoW.
Although braiding adds a new dynamics to the system as a whole, each chain is a PoW chain. PoW has undergone much more scrutiny than proof-of-stake (PoS). It takes years to demonstrate the safety of a consensus scheme in the real world. Because of this, there is real value and opportunity for Kadena in building a scalable system on PoW consensus.
On the triangle, Kadena falls here:
Proof-of-Stake
The schemes presented above were PoW-based. The schemes below are PoS schemes.
In practice, all PoS systems centralize block production relative to purely permissionless PoW schemes by design .
This is due to the intrinsic trade-off between number of block producers and throughput. (This excellent essay by Vitalik Buterin details the tradeoffs.)
However, this doesn’t mean that all PoS schemes centralize block production equally. As we’ll see, there’s a wide range of DBP that’s achievable using PoS schemes.
PoS schemes are far less battle-tested than PoW schemes in real-world settings.
For example, the first PoS implementation, Peercoin, faced nothing-at-stake attacks, among others. As such, PoS schemes should be considered fundamentally riskier.
Leg 2: Centralizing Block Production (EOS, Cardano, NEO, others)
Delegated proof-of-stake (DPoS) schemes embrace centralization by recognizing that PoW schemes naturally centralize due to economies of scale in mining. Given this practical reality, Dan Larimer invented DPoS, which embraces the fact that blockchains naturally centralize anyways, and uses that to achieve scalability.
For example, EOS , Larimer’s most recent effort, publicly boasts that the system will only have 21 block producers at a time. It’s expected that, in time, it will only be possible to run an EOS node in a datacenter.
By limiting the number of block producers, it can be assumed that each block producer has more resources. Additionally, reducing the number of block producers reduces latency in Byzantine Fault Tolerant (BFT) algorithms, which typically require n^ 2 messages to achieve consensus.
Reducing DBP explicitly increases scalability
DPoS based chains not only offer scalability but fast TTF, and therefore, low latency. EOS specifically is aiming for .5-second block times, which is simply not feasible in other consensus schemes. This is a major advantage for DPoS systems. Many applications require low latency and high throughput.
Take, for example, decentralized exchanges. This is becoming painfully obvious as the 0x ecosystem matures on Ethereum. One of the largest problems in 0x today is the rapidly growing number of order collisions, which are a direct result of slow block times and high latency in Ethereum.
The 0x team has proposed solutions . It’s unclear how effective these will be given the intrinsic limits of the underlying Ethereum blockchain. This wouldn’t be a problem at all given the fast blocks, high throughput, and low latency that DPoS systems offer.
Overall, a bet on DPoS is a bet on a few things: There are certain applications that require high throughput and low latency on a neutral database . Not all distributed systems need to be that distributed so as to able to withstand full-frontal government.
On the triangle, DPoS systems will cluster along the bottom of the triangle. Note that, relative to the prior two triangles, which illustrated systems with slow TTF, DPoS systems offer fast TTF and are therefore presented using a darker background color.
Leg 3: A Universe Of Many Chains (Cosmos, AION, ICON, Ark)
The Cosmos , AION , ICON , and Ark teams believe that there will be hundreds of thousands or even millions of chains.
Rather than monolithic chains, such as a Ethereum or EOS, the teams building systems on leg 3 of the triangle believe that different applications should not necessarily share a single set of validators. Instead, they should have unique validator sets.
In the context of the scalability trilemma, each chain on systems in leg 3 comprise less value. In both PoW and PoS schemes, safety increases with value. However, in exchange for that additional risk, each chain gains sovereignty (which may not be necessary or even valuable), scalability, and fast TTF.
Why is sovereignty valuable? This is easiest way to understand is to walk through some examples. As countries adopt chains for administrative purposes, they will want their own validator sets that enforce their social values and not those of some other country or a global commune. Ethereum and Ethereum Classic, for example, should not share validators.
The obvious counter to the case for sovereignty is Ethereum itself. In 2013, Vitalik set out to build Ethereum because he recognized that every app developer in crypto was dealing with the same challenges around mining and consensus. He recognized the opportunity to abstract all of that complexity so that developers can focus on the application layer.
There are some interesting parallels to draw in the history of cloud computing. In the early 2000s, many web-hosts hosted multiple websites on a single server.
Whenever one site received too much traffic, the server would crash, taking down other websites that were hosted on the same server.
In many ways, Ethereum is like the early web-hosts.
It simply bundled too many things together, creating a system that in aggregate was unstable.
When one application broke the system, it broke the system for everyone.
The solution to the web-hosting problem was virtual machines (VM). By isolating every application into a separate VM, a single server could run multiple applications, maximizing hardware utilization and driving down cost while still preserving integrity. In the event of an influx of traffic, a single VM would crash, rather than all the VMs on the server.
In time, VMs became portable across physical servers, increasing redundancy and security even further. Combined with systems enabling massive horizontal scalability, VMs became one of the key components of cloud computing. More recently, Docker containers have come to replace VMs, but Docker containers don’t fundamentally change this analogy.
If distributed apps must live on separate chains for the reasons outlined above, then there will be a great opportunity for the systems on leg 3 of the triangle.
To support this future, systems on leg 3 need to make it trivially easy to spin up new chains, and for chains to interoperate with one another.
Cosmos is making this vision a reality with Ethermint . Ethermint is a 100% open and free.
It’s a blank-slate template chain that runs the Ethereum Virtual Machine (EVM) on top of Tendermint, the semi-centralized, high throughput, low TTF consensus algorithm pioneered by the Cosmos team. By making it trivially easy for developers to spin up new chains, Cosmos hopes that developers will do just that. AION, ICON, and Ark share the same general vision and are working to provide template-ized ways for developers to spin up chains quickly and easily.
(Note that although Wanchain is often listed as a “interoperable chain” solution, it is substantially different than everything else in this section and does not provide the same functionality.)
Note that these systems offer fast TTF.
That’s because each chain is relatively centralized, allowing for low latency. Despite each chain being relatively centralized, the system in aggregate is rather decentralized because there are so many chains with independent validator sets, each of which may leverage novel consensus mechanisms.
On the triangle, vision of many smaller, interoperable chains can be visualized as follows:
Sharding (Ethereum 2.0, Polkadot)
Vitalik and Gavin Wood have openly discussed sharding Ethereum for years (see here and here ).
Each shard is basically a unique chain. The difference between a shard in Ethereum and an independent chain in the Cosmos ecosystem is that in Cosmos, each chain must manage its own consensus (and therefore safety), whereas Ethereum shards do not. In sharding, consensus and therefore safety are pooled across all shards and managed by a Validator Manager Contract in a master shard. In most cases, pooled safety should be better than many chains with lower safety.
No one has put a sharded blockchain into production—yet ( Zilliqa claims to; however, their implementation is not full state-sharding).
Sharding solves the scalability trilemma, albeit at the expense of chain sovereignty. Additionally, cross-shard communications are subject to latency. Latency is primarily a function of the consensus algorithm per shard.
Ethereum is going to use Casper to finalize each shard. Although the specific parameters are not yet set, it seems likely that Casper will offer TTF measured in minutes, making sharded Ethereum a high-latency system.
Using a novel consensus algorithm called threshold relay, Dfinity and Algorand aim to offer DBP, safety, more scalability than Ethereum within a single shard (though far less than the scalability offered by DPoS), and fast TTF. If threshold relay works in practice as well it has in test environments, we can expect to see Dfinity and Alogrand shard their chains and leverage the fast TTF and low latency to provide for efficient cross-shard communications.
Polkadot will launch as a sharded network that uses a TBA BFT consensus algorithm that offers fast finality at the expense of DBP (with a similar set of trade-offs as Tendermint). However, Polkadot is likely to launch a sharded network before Ethereum or Dfinity. Unlike Ethereum and Dfinity, Polkadot does not require shards to use a particular state machine, such as the EVM or WebAssembly (WASM). Rather, Polkadot allows each chain to define its own state machine. This would allow protocols such as Stellar , which focus on issuing arbitrary digital assets without any smart contract functionality, or Zcash , which requires a highly optimized state-machine to process SNARK proofs, to move its self-contained consensus systems onto Polkadot.
To summarize the above: .
