Jude Nelson
Jul 25, 2016 · 6 min read

Blockchains may be the current new hot technology, but what else can we do with them besides build cryptocurrencies? At Blockstack Labs, we use them to build replicated state machines. Replicated state machines (RSMs) are a well-understood, widely-used design pattern for building distributed systems. Lots of highly-reliable systems — from databases to warships to stock exchanges — are implemented using RSMs.

By some estimates, cloud industry is over 10x more valuable than the whole cryptocurrency market today. Using blockchains to construct decentralized applications that disrupt the cloud industry represents a considerable value proposition; hence our interest in this line of research.

What’s in a Blockchain?

Let’s pretend for a moment that the cryptocurrencies don’t exist. What’s so interesting about proof-of-work blockchains?

  1. They are totally-ordered. Everyone sees the same transactions, in the same order, everywhere.
  2. The order is “stable.” Not 100% stable or durable, though — forks and chain reorgs can happen (but are rare)— but outside of these two pathological cases, a client’s view of the transaction order doesn’t change.
  3. They are append-only. There’s no such thing as random-write. To change a prior write, you have to re-do all the writes between then and now. But…
  4. They are tamper-resistant. It’s expensive to retroactively change or reorder prior writes (thanks to proof-of-work).
  5. They grow at a fixed rate. No matter how many or few writers there are, the amount of space used grows linearly.
  6. Anyone can write. All you have to do is participate in securing the network by trading compute-time for space.

To a first approximation, this is how Bitcoin, Ethereum, and most others work today. The cryptocurrency use-case arises from how you help secure the network: paying for space using transaction fees.

Blockchains as Replicated State Machine Logs

So what are PoW blockchains useful for? As a distributed systems researcher, the first thing that comes to my mind is building replicated state machines. Each peer maintains a copy of the program state, a state-transition function, and an output function. Peers receive inputs from clients, and execute an agreement protocol to determine the next state-transition.

Bootstrapping an RSM from an input stream on the blockchain. The blockchain holds multiple input streams (yellow and red bars), so one challenge is to make sure RSMs only consume inputs meant for them.

If we use a blockchain as an “input stream,” we can build distributed applications with some really nice properties:

  1. Independently bootstrap global state. RSM peers can independently boot up and reach the same state, without having to trust one another (or even talk to one another). Anyone can run a peer, and know that they have the same state as other peers.
  2. Open-membership apps. Anyone can submit inputs. But, their inputs will only be accepted if they are valid in the context of the same “shared ground truth” that everyone else has.
  3. App continuity. Even if all peers go offline, you can still boot up your own using the blockchain. It’ll pick up where the others left off, and other future peers will see and process your inputs.

Getting the Most out of a Blockchain

My goal is to design applications that reach consensus while remaining off-chain. This would mean that the blockchain doesn’t need to be aware of the applications, allowing us to use any blockchain we want. It also means that the only people running the app are the people who want to do so.

However, there are two hurdles to overcome, which we detail in our recent DCCL paper:

  1. How do peers reach consensus using only the input sequence from the blockchain?
  2. How does the application recover from blockchain forks, reorganizations, and failures?

Reaching Consensus

Two application nodes reach agreement on a block if they process the same input transactions the same way in the same order. As we describe in our paper, nodes prove this using a consensus hash.

Consensus hashes let us build fork*-consistent state. To send a new input, the client includes the last-processed block’s consensus hash in the transaction (obtained from a trusted peer). A peer only considers the transaction as an input if it contains a recently-calculated consensus hash from the client. In other words, consensus hashes partition the set of all running RSMs into fork sets.

A blockchain fork can break the application peers into two or more fork sets

Different applications’ peers should be in different fork sets — we don’t want different applications trying to read each other’s inputs! However, blockchain forks and reorganizations can partition the same application’s peers into different fork sets. This is something that we need to recover from if we want all peers to have the same state.

Blockchain Fork Recovery

What happens if the blockchain forks? Most forks are short-lived in practice, so we can avoid them by having the application peers read from slightly behind the chain tip (so transactions are sufficiently confirmed first). However, a long-lived fork will lead to a chain reorganization that will alter the input sequence, causing all subsequently-bootstrapping nodes to arrive at a different state than what had been processed (i.e. new nodes will be in a separate fork set, since they’ll calculate a different consensus hash). It can also put different peers on different branches of different fork sets.

Fortunately, fork sets share a common state-transition history. To join two fork sets, we just need to reconcile the divergent forked history. It should be obvious from the chain state where the fork occurred.

Checkpoint-based fork/reorg recovery. When the RSM reaches block n+2, it fetches the off-chain state transition history (journal) that the CHECKPOINT designates as the “correct” fork. It verifies its integrity with the CHECKPOINT’s consensus hash, and reaches the same state as the already-running RSMs.

To recover automatically, peers designate a trusted “fork resolver,” like the application’s developer. To resolve the fork, the application developer sends a CHECKPOINT transaction with the correct consensus hash, and creates an off-chain replica of the inputs needed to generate it. Application peers would be configured to trust the developer’s public key and replica locations, so they would know to use the off-chain inputs.

The same technique facilitates cross-chain migration — the CHECKPOINT transaction on the new blockchain becomes the starting state for the application peers on that chain. The developers host the associated state from the old blockchain themselves (or ship it within the application).

How do we know whether or not a CHECKPOINT is legitimate? We only expect it to be used only when there’s a deep fork or a blockchain migration. Since these things are easy to independently confirm, we can detect injudicious behavior. If there is a controversial CHECKPOINT, forking the application is trivial: the dissenting peers only need to ignore it. This is achieved with no loss of security, since it only puts the dissenters into a separate fork set without affecting the blockchain.

So where does this leave cryptocurrencies?

“Cryptocurrency” is synonymous in my mind with “input rate-limiting token.” Applications effectively bid on blockchain space for inputs, since the fixed growth rate limits how many can be appended per block time. Buying and selling rate-limiting tokens is the secondary market that makes up the cryptocurrency use-case.

I personally believe that using blockchains as input streams increases the value of the cryptocurrency. In fact, I think cryptocurrencies are significantly undervalued because the world has only just started building blockchain-powered RSMs.

Great! Is there code I can hack on?

Yes! At Blockstack Labs, we have created Virtualchain, a Python library for creating fork*-consistent RSMs on Bitcoin (support for more blockchains is being worked on). The Blockstack Server was built with Virtualchain, and is an implementation of a fork*-consistent RSM described in this post.

Jude Nelson

Written by

1st engineering hire at Blockstack PBC, CS PhD candidate at Princeton University in distributed systems

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade