Building new state machines with Virtualchain

We are pleased to announce that our work on the open-source Virtualchain library has been published at the first workshop on Distributed Cryptocurrencies and Consensus Ledgers (DCCL'16). Virtualchain is a protocol for building new services and apps on top of existing blockchains. We've released Virtualchain v0.14 with the paper as well.

How Virtualchain works:

An application or service uses Virtualchain to define a replicated state machine (RSM). The state machine is defined in terms of its inputs and its state transitions. Users send new inputs as specially-crafted transactions by writing them to the blockchain, and the blockchain ensures that application nodes read the same inputs in the same order.

This opens the door to building general-purpose state machines that are secured by blockchains. These state machines have no central point of control or failure and do not require any modifications to the underlying blockchain.

The above figure shows how Virtualchain ensures that honest nodes can detect and recover from blockchain forks and malicious inputs. An application’s replicated state machine (RSM) processes specially-crafted transactions in the underlying blockchain as input. Virtualchain ensures that it ignores invalid or malicious inputs (shown in red). In doing so, all application nodes reach the same state at the chain tip.

How Blockstack uses Virtualchain:

At Blockstack, we use Virtualchain to implement a simple replicated state machine that registers names on Bitcoin’s blockchain. Our state machine defines state transition functions for operations like claiming a name if it is currently unclaimed, or transferring a name over to a new public key.

These state transition functions enforce the naming system’s rules. For example, a name can’t be claimed if it’s already taken, and only the name’s current owner can transfer it to a new public key.

When a user wants to carry out an operation, she uses the Virtualchain protocol to generate and broadcast a specially-crafted Bitcoin transaction that encodes it. Bitcoin, being oblivious to the naming system’s rules, simply picks these transactions up and incorporates them into a subsequent block.

When all the Blockstack nodes process that block, they apply the naming system rules to parse the transaction into an input and decide whether or not to accept it or reject it. If they accept it, they carry out the resulting state transition (e.g. creating the name, changing a name’s public key).
In this way, we have built a decentralized naming system without having to build a separate blockchain.

Building new state machines:

Virtualchain is general-purpose and can be used to define any state machine on top of any blockchain. The Virtualchain library is available as open-source on Github and you can read the full paper below:

Extending Existing Blockchains with Virtualchain
(PDF), (slides)

If you want to cite our work, here is the BibTeX entry:

@inproceedings{virtualchain:dccl16,
  author = {Jude Nelson and Muneeb Ali and Ryan Shea and Michael J Freedman},
  title = {Extending Existing Blockchains with Virtualchain},
  booktitle = {Workshop on Distributed Cryptocurrencies and Consensus Ledgers (DCCL'16)},
  year = {2016},
  month = Jun,
  url = {https://www.zurich.ibm.com/dccl/papers/nelson_dccl.pdf},
}

The best way to start building new state machines is by going through the reference naming system state machine. We plan to post more documentation and tutorials in the future.