Blockchain Beyond Transactions

Decentralized apps need modern, data-driven algorithmic decision making

Blockchain-based systems like Ethereum are attempting to build a new generation of decentralized applications that could compete with today’s centralized software. This is an important goal — centralization around proprietary software leaves people with less freedom, and raises the barriers to entry for new innovators.

But today’s blockchains aren’t ready to compete with centralized apps, and one of the major reasons is they’re far behind in data-driven algorithmic decision making.

The Facebooks, Googles, and Amazons of the world operate algorithmically-controlled feedback loops:

Instances of this loop can be optimized for different goals. Some goals you may perceive as noble (like improving a language translation service), and some you may perceive as evil (like optimizing a newsfeed for addiction). But the basic idea applies to a diverse set of valuable and important applications. The ability to improve your application via feedback and machine learning is table stakes if you are really serious about building decentralized competitors to today’s behemoths.

The same goes for operating any financial system at scale: learning-driven fraud detection and risk management is not optional.

And the learn step in the above diagram is growing more powerful. If your app architecture doesn’t have a place for learning-driven improvement, you can’t take advantage of that trend. The benefits of differentiable programming¹ tend to increase as you throw more computation and data at them. Most discussions about improving blockchain scalability are focused only on high transaction volumes, but here I’m talking about computation several orders of magnitude bigger than that: enough to run deep models.

Why would we need to run sophisticated software models “on chain”? Because sophisticated software models increasingly mediate our lives. Making them open, transparent, and subject to distributed governance is not a theoretical problem — it’s already a practical problem, and it’s only growing more important each year.

Parallelism

Parallelism is a big deal in all of computing. Even the “single-threaded” performance of today’s processors is heavily-dependent on discovering parallel bits of work that can keep your billion transistors busy.² Today’s popular centralized applications take full advantage of parallelism at multiple levels: within a core, across cores, across servers, across data centers.

Today’s distributed blockchain apps cannot. Ethereum is effectively one single-threaded computer. Every participating processor runs every step and stores every bit of state. This makes it simpler to show the security properties of the system, but it’s incredibly expensive. There’s no way to build a distributed Google or Facebook on Ethereum when even CryptoKitties was able to degrade the global system.

To be fair, none of this is news to the creators of Ethereum, and they are investing in improvements like sharding. Current sharding proposals focus on increasing throughput by factors of 10² or 10³ without reducing security. But here we are interested in a different question: how can we support workloads at least 10⁶ times bigger (in both space and time), and what security guarantees can we maintain under those conditions?

Achieving that level of computation requires us to improve along at least two dimensions: node utilization and inter-node redundancy. The next two sections cover each of these dimensions.

Node Utilization

Node utilization is the fraction of time that nodes are doing useful work, as opposed to dealing with the overhead of coordinating the network or waiting for input. Current proof-of-work blockchains have approximately zero node utilization, because time spent solving proof-of-work puzzles dominates all other computation, and those puzzles are pure coordination overhead.

However, Ethereum is planning a switch from Proof of Work to Proof of Stake, and that will greatly improve the situation. In a proof-of-stake system there is still coordination overhead, but not so much that we can’t turn our attention to the next bottleneck: a high fraction of time spent waiting around for the next consensus block.

Hard synchronization points are always expensive, whether we’re discussing the sync(2) system call or a globally distributed system. At large enough scales, synchronization time dominates over computation time, so system designers look for ways to require the minimum amount of synchronization.

Waiting for the next synchronous block before you can execute it is expensive even in an idealized setting where all nodes are equally fast. In practice, Ethereum nodes vary in capability, which means that the fastest nodes have the worst utilization. The only simple way to take better advantage of fast nodes is to increase the amount of per-block work, which would exclude slow nodes from participating. That leads to perceived centralization risks, and proposals to raise the floor of per-block, per-node work have been historically divisive.

To break through and achieve high node utilization we need to look at designs that break the synchrony assumption. Designs that allow faster nodes to claim more work and run with it, in a fair and secure way. Solutions to that problem dovetail with solutions to our next problematic dimension: inter-node redundancy.

Inter-node Redundancy

In the design space of possible distributed systems, we can identify two extreme points. At one extreme — let’s call it max_paranoia— every operation executes on every node. Today's Ethereum operates at max_paranoia.

At the other extreme, each operation executes on exactly one node. Let’s call that min_paranoia.

Points in between these extremes are characterized by the fraction of the network’s total capacity that is used on work that is also being done elsewhere. Let’s call that the redundancy fraction R.

At our minimal extreme, none of the capacity is spent on redundantly checking other people’s work:

At the other extreme all nodes but one are doing redundant work:

Where N is the total number of nodes.

Assuming about 30,000 total nodes³, Ethereum runs with 99.997% redundancy.

If Ethereum implements their current sharding proposal and uses 100 shards, their redundancy will improve to

Evidently, sharding does not really improve the situation. As a result, adding one more marginal node doesn’t give you any marginal increase in the ability to execute programs.

To get a meaningful boost, we want to design systems where R is something more like 50%. Meaning half the network’s computation is used to validate and secure the other half.⁴ Under such conditions, adding a new node to the network allows for an immediate marginal improvement in the amount of computation the overall network can do.

The key to building such a system is to trade off instant, irrevocable finality for a stake-based, audit-driven economy. This fits nicely with our earlier result on the need for asynchrony, because the network’s audit load can be moved around in time more easily than today’s hard synchronous verification schemes.

The Tally Protocol

The Tally Protocol, under active development by Cardstack, is tackling both of the architectural challenges identified above. To give a very brief description: Tally is a Layer 2 consensus algorithm that lets decentralized apps orchestrate staked miners to perform distributed parallel computing on GPU hardware.

The goal is to make it possible to run sophisticated reward-splitting algorithms on an open, permissionless, decentralized platform — including spam and fraud detection, PageRank-like analysis, and the ingestion of high-volume analytics data from a constellation of distributed and cloud-hosted applications.

To do all that in the near term, we are implementing the Tally network separate from, but governed by, the main Ethereum network. That is, anyone will be able to join the Tally network by staking tokens into our contract on mainnet, and that contract will serve as the input to the Tally network’s own proof-of-stake consensus algorithm. The large-volume, compute-heavy parts of the workload will all stay in the Tally network, reducing only what’s necessary for periodic payment settlement back out to the Ethereum mainnet.

This approach gets us beyond merely increasing transaction volume. We’re opening the door to differentiable programming on the blockchain — and making it possible for decentralized apps, governed transparently by communities of users, to finally compete with today’s centralized digital superpowers.

Stay tuned for more on this.


¹ Differentiable programming is a general way to describe how all the leading “machine learning” / “deep learning” / “artificial intelligence” systems work today. As long as you can express your program so that the outputs are a differentiable function of the inputs, powerful learning systems can be brought to bear on optimizing it.

² As many application developers recently discovered to their horror via Spectre and Meltdown.

³ Estimate based on ethernodes.org as of January 31, 2018.

This is just an example number to illustrate the dynamics. I think redundancies even lower than 50% are plausible, and that different workloads may have different confidence requirements, such that higher-risk activities can pay higher costs and obtain higher statistical confidence.


Read More

Join our community

To learn more about Cardstack, visit https://cardstack.com.

Join the Cardstack community channel on Telegram at https://t.me/cardstack


Edward Faulkner joined the Cardstack team as the lead developer in 2014. He is a member of the Ember Core Team, and the creator of Ember’s official animation library. His open source code is running on mainstream gaming consoles, major social media sites, and hordes of enterprise applications. He was a research associate of the MIT Media Lab’s Social Computing group, and was previously lead engineer at Akamai Technologies, where he built critical, internet-scale security infrastructure. Ed has a Bachelors and Masters of Computer Science from Massachusetts Institute of Technology (MIT).


Illustration: Chris Gardella for Cardstack. “Computadora” by Tec. sistemas is licensed under CC BY-SA 2.5