the morning paper

OmniLedger: A secure, scale-out, decentralized ledger via sharding Kokoris-Kogias et al., IEEE S&P 2018

OmniLedger makes a nice complement to Chainspace that we looked at yesterday. The two systems were developed independently at the same time. OmniLedger combines Visa levels of scalability (caution: the authors compare against the average Visa tps, the peak tps in the Visa network is considerably higher) with a secure decentralised ledger. It’s also a demonstration of how quickly the field is progressing, and something of a wake-up call if you’ve been working in the field of distributed systems and transaction processing but so far ignoring developments in decentralised ledgers. Standard building blocks are emerging and being combined in novel ways, and there’s a lot to learn!

This paper introduces OmniLedger, the first distributed ledger architecture that provides “scale-out” transaction processing capacity competitive with centralized payment processing systems such as Visa, without compromising security or support for permissionless decentralisation.

The goals of OmniLedger are as follows:

1. Full decentralisation, with no trusted third parties and no single points of failure
2. Shard robustness (OmniLedger partitions state into multiple shards processing in parallel) — each shard must correctly and continuously process transactions assigned to it.
3. Secure atomic transactions, but within and across shards
4. Scale-out performance with throughput that increases linearly in the number of participating validators
5. Low storage overhead so that validators do not need to store the full transaction history
6. Low latency for transaction confirmations.

   A lot of moving parts need to come together to support all of this.

First we need a way of enabling new validators to join the system, and a secure way of sharding validators so that adversaries cannot easily overpower a shard (per the discussion we had yesterday around Chainspace). Underpinning this part of the system is an identity blockchain, and secure distributed randomness generation with RandHound (a scalable secure multi-party computation protocol providing unbiased decentralised randomness in a Byzantine setting) and cryptographic sortition (that we first saw with Algorand).

Next we need a secure and reliable way of processing transactions within a shard, for which OmniLedger introduces the Omnicon protocol which combines a tree communication pattern based on groups with a PBFT-like view-change procedure. Transactions are recorded on the transaction ledger. UTXOs (the unspent transaction output model) give us a (explicit) causal+ consistency model which means we can identify non-conflicting transactions and process blocks of these in parallel. The causality graph is maintained across blocks, not individual transactions, reducing some of the metadata overheads.

It’s not enough to reach consensus within a shard though, we also need atomic transactions across shards. For this OmniLedger introduces the Atomix protocol, based an a lock-then-unlock protocol.

The pieces all come together like this:

(Enlarge)

Sharding securely

We can’t allow the validators themselves to choose a shard to join, as this would permit an adversary to concentrate all his validators in one shard. If the assignment of validators to shards is random though, then with high probability all shards will have about the same fraction of malicious nodes. Suppose we have a suitable source of randomness, then we can proceed as follows:

• Validators who wish to participate in the ledger starting from epoch have to first register to a global identity blockchain.
• Identities are created through a Sybil-attack resistant mechanism in epoch and broadcast, together with the respective proofs, on the gossip network at most before epoch ends.
• Randomness is used to elect a leader for epoch and assign nodes to shards (more on this shortly)
• The leader requests a (BFT) collective signature on a block with all identities provably established thus far. If at least of these validators endorse the block it becomes valid and the leader appends it to the identity blockchain.

The security of OmniLedger’s validator assignment mechanism is modeled as a random sampling problem with two possible outcomes (honest or malicious). Assuming an infinite pool of potential validators, we can use the binomial distribution…

A failed assignment is one which allows a shard to be controlled by an adversary. For given adversarial power (percentage of controlled nodes), the following chart shows the required shard sizes to peg the failure probability at ~$10^{-6}$.

But where does the source of randomness come from?

We require that the distributed randomness generation protocol provides unbiasability, unpredictability, third-party verifiability, and scalability. Multiple proposals exist… we focus on RandHound due to better documentation and open-source implementation.

RandHound itself relies on a leader to orchestrate the protocol run. So now we need away to select one of the validators for the role. Cryptographic sortition is used for this. Cryptographic sortition is based on verifiable random functions, VRFs.

At the beginning of an epoch , each validator computes a ticket where is the configuration containing all properly registered validators of epoch (as stored in the identity blockchain) and is a view counter.

Validators gossip the tickets for a time , after which they lock in the lowest value valid ticket they have seen thus far and accept the corresponding node as the leader of the RandHound protocol run.

To maintain operability during transition phases, OmniLedger swaps in the new validators gradually in each shard per epoch. See section IV.B for details.

Cross-shard transactions

In the UTXO model (which OmniLedger adopts), the outputs of a transaction create new UTXOs, and inputs completely “spend” existing UTXOs. With UTXOs randomly assigned to shards for processing, we can expect cross-shard transactions to be common.

OmniLedger uses a Byzantine Shard Atomic Commit protocol called Atomix to atomically process transactions across shards. It builds on the fact that shards are collectively honest, do not crash infinitely, and run ByzCoin internally (providing BFT consensus). The protocol is client-driven and proceeds in three phases:

1. In the initialize phase a client creates a cross-shard transaction spending UTXOs of some input shards, and creating new UTXOs in some output shards. The transaction is gossiped on the network and eventually reaches all input shards.
2. In the lock phase all input shards associated with a transaction first validate the transaction to be sure the inputs can be spent. Then if the transaction is valid the transaction is logged in the shard’s ledger and a proof-of-acceptance is gossiped. (Think “PREPARE” in classic 2PC). If the transaction is not accepted then a proof-of-rejection is gossiped instead. The transaction inputs are now locked, but the transaction is not yet committed. The client can inspect the input shard ledgers to verify the proofs and that the transaction was indeed locked. The client holds enough proofs to either commit the transaction or abort it and reclaim any locked funds, but not both.
3. In the unlock phase the client either unlocks-to-commit or unlocks-to-abort by creating an gossiping the appropriate unlock transaction. Each involved output shard validates the transaction and includes it in the next block of its ledger in order to update the state and enable the expenditure of the new funds.

If you’ve had any operational experience with distributed transaction systems before, you may be wondering what happens if the client crashes or otherwise fails to proceed to phase 3 leaving the transactions in-doubt in the ledger. In this case funds are not automatically reclaimed. The funds themselves provide the incentive for clients to complete transactions.

We argue that a client who crashes indefinitely is equivalent to a client who lost his private key, which prevents him from spending the corresponding UTXOs. Furthermore, any entity in the system, for example a validator in exchange for a fee, can fill in for the client to create an unlock transaction, as all necessary information is gossiped.

Scalable BFT-consensus with Omnicon

OmniLedger builds on the ByzCoin Byzantine consensus scheme, which uses collective signing (CoSi) to make PBFT more scalable. ByzCoin distributes blocks using multicast trees for performance, and falls back to a less-scalable star topology for fault tolerance.

Omnicon trades-off some of ByzCoin’s high scalability to achieve better fault tolerance without resorting to a PBFT like all-to-all communication pattern:

During the setup of OmniLedger in an epoch, the generated randomness is not only used to assign validators to shards, but also to assign them evenly to groups within a shard…. At the beginning of an Omnicon roundtrip, the protocol leader randomly selects one of the validators in each group to the group leader, who is responsible for managing communication between the protocol leader and the respective group members.

Transactions that don’t conflict can be committed in different blocks and safely processed in parallel. A block-based DAG in which each block can have multiple parents captures the concurrent processing of blocks. The metadata overhead of tracking causality is reduced by noting that UTXO dependencies are transitive, so we only need to track causality between blocks, not individual transactions within blocks.

Low latency transactions

For clients with frequent latency-sensitive low-value transactions, OmniLedger supports an optional “trust but verify” model. Optimistic validators process transaction quickly, and core validators subsequently verify the transactions again to provide finality and ensure verifiability.

As a result, some bad transactions might be committed but ultimately core validators verify all provisional commitments, detecting any inconsistencies and their culprits, which makes it possible to punish rogue validators and to compensate the defrauded customer for the damages.

Ledger pruning

Bitcoin’s blockchain grows by about 144MB per day, but next-generation systems with Visa-level throughput (e.g., 4000 tps, and 500 B/tx) can produce over 150GB per day. This is a problem if a new validator needs to download and process the entire ledger in order to bootstrap. So OmniLedger introduces stable checkpoint state blocks. At the end of an epoch, the shard’s leader stores the UTXOs in an ordered Merkle tree, and puts the Merkle tree’s root hash in the header of a state block. Validators run consensus on this block, and if approved it becomes the genesis block for the next epoch.

OmniLedger and Chainspace

Our approach is synergistic to Chainspace as we focus on an open scalable UTXO style DL (distributed ledger), whereas Chainspace focuses on sharded smart-contracts and small-scale shards that can be deployed only under weak adversaries (e.g., in a permissioned setting). As a result, combining OmniLedger and Chainspace has great potential to create an open, scalable, smart-contract platform that provides scalability and security under strong adversaries.

Chainspace: a sharded smart contracts platform Al-Bassam et al., NDSS’18

Chainspace is a DApp (decentralised application) platform based on smart contracts, designed for higher scalability than is currently achievable with Bitcoin or Ethereum.

Our modest testbed of 60 cores achieves 350 transactions per second, as compared with a peak rate of less than 7 transactions per second for Bitcoin over 6K full nodes. Ethereum currently processes 4 transactions per second, out of a theoretical maximum of 25.

Chainspace manages state in objects, which are sharded across nodes. One very interesting twist is the distinction between procedures that execute a computation, and independent checkers that can verify a computation was carried out correctly. Only one party executes a transaction, the others just need to verify it. That makes for lots to think about as you work through the paper.

Objects, contracts, and transactions

State in Chainspace is stored in objects. Every object has a unique identifier (which can be used to verify its provenance, as we’ll see later). Objects are also immutable, so the only way to ‘update’ state is to create a new object (with a new id).

Contracts define a set of initial objects that are created when the contract is first created within Chainspace. A contract defines a set of types for all the inputs and outputs, a set of procedures, and a checker.

Procedures take as input both object ‘inputs’ and references. An object that is passed to a procedure as an input is consumed by that procedure and marked inactive — it can never be passed to another procedure again. References give read-only access to object state on the chain. The output of a procedure is a set of (new) objects. Within the procedure there may be local parameters and local return values (from calling other contracts). Some of these may contain secret information and require confidentiality. Procedures do not have to be pure functions, and may be randomised, keep state, or have side effects.

Associated with each smart contract c, we define a checker denoted as v. Those checkers are pure functions (i.e., deterministic and have no side-effects), and return a Boolean value. A checker v is defined by a contract, and takes as parameters a procedure p, as well as inputs, outputs, references and locals. Note that checkers do not take any secret local parameters.

A transaction is an atomic application of one or more procedures to active input objects, and possibly some referenced objects, to create some new output objects. “A user client executes all the computations necessary to determine the outputs of one or more procedures forming a transaction, and provides enough evidence to the system to check the validity of the execution and the new objects.”

Once a transaction is accepted in the system it ‘consumes’ the input objects, that become inactive, and brings to life all new output objects that start their life by being active. References on the other hand must be active for the transaction to succeed, and remain active once a transaction has been successfully committed.

It’s all very reminiscent of ownership typing in Rust.

Within Chainspace, a transaction is represented by a sequence of traces of the executions of the procedures that compose it. Traces contain information about the contract, procedures, input objects, references and local parameters, as well as output objects and local returns (but not secret objects or returns). A trace can depend on other traces that came before it (causality), and is valid if its sequence of dependencies is valid and, (i) all inputs and references are valid, (ii) a trace that produces output objects must also consume some input objects, and (iii) all objects passed to the checker must be types defined by the smart contract.

The identifier of a trace is a cryptographic hash of all the information contained within it, and the identifier of an object is derived through the application of a cryptographic hash function to the identifier of the trace that created the object, as well as a unique name assigned to the output object by the procedures creating the trace.

An object identifier is (thus) a high-integrity handle that may be used to authenticate the full history that led to the existence of the object.

It all makes sense in principle, but I found it difficult to get my head around how I would practically write a checker for a procedure. Things clicked for me when I thought of it in terms of Hoare triples: we are given the procedure inputs, and can verify the pre-conditions. Then the procedure itself executes, which can be a black box to us. We’re left with the outputs, which we can verify meet the post-conditions (conditioned on the inputs).

Perhaps an example will also help. Consider a smart voting system with a contract SVote and three types SVote.Token, SVote.Vote, and SVote.Tally. There are three procedures: SVote.createElection, SVote.addVote, and SVote.tally. When add vote is called, it is passed a new vote to add, homomorphically encrypted and signed by the voter. The voter also provides a zero-knowledge proof certifying that her vote is a binary value and that she voted for exactly one option. The checker can assert the correctness of the votes by verifying the associated signatures and zero-knowledge proofs, without over having to learn the clear value of the votes.

Defining smart contract logic as checkers allows Chainspace to support privacy friendly-contracts by design. In such contracts some information in objects is not in the clear, but instead either encrypted using a public key, or committed using a secure commitment scheme. The transaction only contains a valid proof that the logic or invariants of the smart contract procedure were applied correctly or hold respectively, and can take the from of a zero-knowledge proof, or a Succinct Argument of Knowledge (SNARK)… the checker runs the verifier part of the proof or SNARK that validates the invariants of the transactions, without revealing the secrets within the objects to the verifiers.

System design

It’s time to take a brief look under the hood!

A Chainspace network comprises a set of nodes that manage valid objects and ensure only valid transactions get committed. Nodes are organised into shards. Shards partition the set of objects.

Nodes within a shard reach consensus on whether to accept or reject a transaction, whether an object is active or inactive, and whether traces from contracts they know check. Transactions can span shards, so there is voting at the shard level to reach consensus on commit. This requires unanimous agreement across all shards. Nodes in each shard periodically publish a signed hash chain of checkpoints, each block recording evidence of transactions processed in the current epoch.

An honest shard is one with at least 3f+1 nodes, where adversaries control no more than f faulty nodes. Safety and liveness is guaranteed in honest shards. With dishonest shards (adversary controls at least of the nodes) correctness or liveness cannot be guaranteed, but foul play is guaranteed to be detectable.

There are many options for ensuring that concerned nodes in each shard do not reach an inconsistent state for the accepted transactions, such as Nakamoto consensus through proof-of-work, two-phase commit protocols and classical consensus protocols like Paxos. However, these approaches lack in performance, scalability, and/or security. We design an open, scalable and decentralized mechanism to perform Sharded Byzantine Atomic Commit or S-BAC.

S-BAC is a combination of Byzantine agreement (using the ModSmart implementation of PBFT) and atomic commit using a two-phase commit protocol inspired by Gray and Lamport. You can find more details in §IV.C. Here’s a quick visual summary:

(Enlarge)

The higher levels of Chainspace functionality are implemented using system smart contracts:

Effectively, instantiation of Chainspace is the combination of nodes running the basic S-BAC protocol, as well as a set of system smart contracts providing flexible policies about managing shards, smart contract creation, auditing and accounting.

Since Chainspace is intended to be an open system, there is also a CSCoin smart contract for tracking value. It can be composed with other procedures to enable payments for processing transactions. Shards can advertise that they will only consider actions valid if some value of CSCoin is transferred to their constituent nodes.

Integrity

It seems much easier for an adversary to overpower one or more shards in a Chainspace system than it does in systems where all nodes are contributing globally. The set of chainspace nodes are divided into shards, and within a shard an adversary just needs to supply/control nodes. I couldn’t see anything in the paper about the rules for new nodes joining shards. If that is also open, then I could flood a shard with my own nodes? If it is not open, then is there a central point of trust for node membership?

In the limitations and future work section, the authors have this to say:

In case one or more shards are malicious, we provide an auditing mechanism for honest nodes in honest shards to detect the inconsistency and to trace the malicious shard. Through the Hash-DAG structure, it is also possible to fully audit the histories of two objects, and to ensure that the validity rules hold jointly — in particular the double-use rules. However, it is not clear how to automatically recover from detecting such an inconsistency…

Blockstack: a global naming and storage system secured by blockchains Ali et al., USENIX ATC’16

We’ll be back in the world of cryptocurrencies and blockchains for the rest of this week, kicking off with this 2016 paper on Blockstack. It’s interesting both for the lessons learned trying to build a system on top of the Namecoin blockchain, as well the subsequent design of Blockstack that was informed by those experiences. Blockstack itself has evolved since this 2016 paper (see the latest white paper) but the core ideas are all here.

A blockchain-based identity service

One good match for blockchain technology is as an immutable ledger securely binding names to values. Things you might ideally want in a naming system include human-readable names, a strong sense of ownership (name-value pairs can be owned by cryptographic keypairs), and no central trusted party. Zooko’s triangle suggested that you can’t have all three properties at once, but Namecoin showed that the combination is possible using a blockchain-based approach.

Namecoin itself was started to create an alternate DNS-like system that replaces DNS root servers with a blockchain for mapping domain names to DNS records.

Given that blockchains don’t have central points of trust, a blockchain-based DNS is much harder to censor and registered names cannot be seized from owners without getting access to their respective private keys.

Registration fees are required to prevent people from domain-squatting, but in Namecoin the recipient of the registration fees is a “black hole” cryptographic address from which money cannot be retrieved. Registration itself is a two-phase process in which a user first pre-orders a name hash, and then later registers the name-value pair by revealing the actual name and the associated value.

The authors of Blockstack wanted to create a Blockstack ID service along similar lines, which maps a name to public keys along with other profile data.

How (not to) build a decentralised PKI system

Namecoin has a d/ namespace used for domain names, and the first version of Blockstack ID was built on top of Namecoin using a new u/ namespace. After a year in production, a number of worries had started to surface around security, network reliability and throughput, selfish mining, the impact of hard forks, and the failure of merged mining. The authors distill this into five key lessons, with the following bottom line:

We strongly believe that decentralized applications and services need to be on the largest, most secure, and most actively maintained blockchain. Currently [2016] no other blockchain even comes close to Bitcoin in terms of these security requirements.

Lesson one: there is a fundamental tradeoff between blockchain security and introducing new functionality to blockchains.

Starting a new blockchain is always tempting, but new chains are significantly less secure than Bitcoin because of the much reduced mining activity.

The most important factor in the security of a blockchain is the total cost of attacking the blockchain and tampering with recently written data.

If a single miner (or pool) gets to 51% of the computational power mining on the chain, then all decentralised bets are off. In 2014, the authors noticed that a single mining pool consistently had more than 51% of the compute power on Namecoin, and it subsequently got worse with concentrations of power of up to 75% in a given week. “At such concentration, Namecoin is effectively controlled by a single party.”

Lesson two: there is currently a significant difference between the network reliability of the largest public blockchain network (Bitcoin) and network reliability of the long tail of alternate blockchains.

The authors noticed that some miners did indeed seem to be exploiting their concentrated power, either intentionally refusing or unable to package Blockstack transactions in their blocks. There were also cases of latency spikes caused by software issues in Namecoin itself.

Lesson three: selfish-mining is not just a theoretical attack, but selfish-mining like behaviour can already be observed in production blockchains.

Whenever software updates were issued on Namecoin, there was a considerable fluctuation of computing power: miners aren’t incentivised to upgrade software quickly for small chains which aren’t their main reason for operating a pool. This leads to…

Lesson four: Other than the engineering problems, consensus-breaking changes are complicated because of the fundamental incentive structures of the parties involved. System designers have never dealt with consensus-breaking changes before cryptocurrencies; it’s a novel challenge.

Finally, merged mining was supposed to address the problem of lesser mining power on smaller chains, by allowing Bitcoin miners to participate in the new network without spending extra compute cycles. Namecoin used merged mining with Bitcoin. “One of our key findings is that merged mining is currently failing in practice: the leading merged-mined blockchain, Namecoin, is vulnerable to the 51% attack.” This leads to lesson five:

Lesson five: At the current stage in the evolution of blockchains, there are not enough compute cycles dedicated to mining to support multiple secure blockchains.

After considering all of the above factors, it was an easy decision to move our PKI system from Namecoin to Bitcoin.

Blockstack v2: built on top of Bitcoin

The most fundamental idea in Blockstack will be familiar to anyone with a background in networking: separate the control plane from the data plane. In particular, Blockstack keeps the control plane on the blockchain, and the data plane off the chain but anchored in an on-chain root of trust. This alleviates problems with data storage limits in blocks (the data isn’t on the chain, go ahead and store as much as you like!). You could actually use any underlying blockchain of your choosing, the deployment chooses Bitcoin.

Blockstack maintains a naming system as a separate logical layer on top of the underlying blockchain on which it operates. Blockstack uses the underlying blockchain to achieve consensus on the state of this naming system and bind names to data records. Specifically, it uses the underlying blockchain as a communication channel for announcing state changes, as any changes to the state of name-value pairs can only be announced in new blockchain blocks.

(Enlarge)

The control plane comprises the underlying blockchain itself, and a logically separate “virtualchain” built on top of it. The data plane handles data storage and availability with a routing layer that tells you where to find things, and a storage layer that looks after the data itself.

The Virtualchain layer

A key contribution of Blockstack is the introduction of a logically separate layer on top of a blockchain that can construct an arbitrary state machine after processing information from the underlying blockchain. We call this layer a virtualchain. A virtualchain treats transactions from the underlying blockchain as inputs to the state machine and valid inputs trigger state changes. At any given time, where time is defined by the block number, the state machine can be in exactly one global state.

You could also a state machine like this using a smart contract. The paper doesn’t explicitly discuss why that option was rejected, but I can see two arguments: firstly, that would restrict the choice of underlying chain, and rule out the Bitcoin blockchain; and secondly, depending on design parameters, the state within the state machine may get too large to easily store on chain. The 2017 Blockstack white paper does touch on this issue, additionally saying, “Nodes on the network should not be required to compute complex untrusted programs just to stay synced with the network.”

Only Blockstack nodes are aware of the virtualchain layer, and blockstack operations are encoded in valid blockchain transactions as additional metadata. The virtualchain idea is independent of the actual state machine you use it with, Blockstack defines a global naming and storage system state machine. Here are the states and transitions for the naming system state machine:

What I can’t easily tell from the paper, is how I know I can trust the state machine logic. It’s not on the underlying blockchain (as it would be with a smart contract), so presumably it’s just embodied in code running on Blockstack nodes. If it essentially becomes impossible to upgrade those nodes without everyone noticing, and the code is open source, I guess that arguably gives similar properties to a smart contract. The second part of the answer here is you don’t necessarily need to inspect and validate the logic of the state machine, so long as you can validate the resulting state (i.e., the state is all that matters). Drawing again from the 2017 white paper on this topic:

Application nodes replay their logs to achieve application level consensus at each block b, such that two nodes will agree on a block if and only if the application transactions in that block leave the nodes in an identical state. If their resulting state after executing the operations in block b are identical, then their generated consensus hash for that block will be the same. Consensus hashes enable nodes to independently audit and efficiently query their histories, as well as detect forks and then migrate state between blockchains.

The routing layer

The task of routing requests is separated from the task of actually storing data. Blockstack uses zone files (c.f. DNS zone files) for storing routing information. The virtualchain binds names to their respective hash(zonefile) and stores these bindings in the control plane. The zone files themselves are stored in the routing layer.

Users do not need to trust the routing layer because the integrity of zone files can be verified by checking the hash(zonefile) in the control plane.

As of the time of writing the paper, nodes formed a DHT-based peer network for storing zone files. Only files whose hash has previously been announced on the chain will be stored. Blockstack today has migrated away from the DHT approach, and uses a new unstructured peer network called the Atlas network. All Atlas nodes maintain a 100% state replica and use gossip to keep up to date.

The storage layer

The storage layer hosts the actual data values for the name-value pairs. Stored values are signed by the key of the owner of the corresponding name.

By storing data values outside of the blockchain, Blockstack allows values of arbitrary size and allows for a variety of storage backends. Users do not need to trust the storage layer because they can verify the integrity of the data values in the control plane.

In mutable storage node, signed updates to the value can proceed as fast as the underlying storage system allows. There is a danger here though of readers consuming stale data. This problem is punted to the user: “readers and writers must employ a data versioning scheme to avoid reading stale data.” In immutable storage mode, a TXT record is also written in the zone file containing hash(data). Readers can verify data integrity by checking this hash. Throughput and latency for immutable writes is of course constrained by the underlying blockchain.

Blockstack today has implemented an overlay storage system called Gaia that sits on top of existing cloud storage providers.

Name verification

We briefly discussed the consensus hashes of state machine state in the virtualchain section. Consensus hashes also help new nodes come up to speed faster without needing to process the entire chain from block zero.

The process of verifying the authenticity of a prior name operation with a later trusted consensus hash is called Simplified Name Verification (SNV). SNV enables support for ‘thin clients,’ which can query the past state of the system without running Blockstack nodes or having access to the full blockchain history.

The construction of the consensus hash allows a user to verify the authenticity of any virtualchain operation from a block with height , less that the current height h, using only a logarithmic number of queries.

For the latest on blockstack, see https://blockstack.org.