Elastico – a new scalable blockchain protocol proposal

Recently I have been researching and witnessed some nice papers on the topic of crytocurrencies and the blockchain protocols. It appears that these topics are gaining some academic traction within the Computer Science and computer security communities. As to the broader applicability and functionality of the major developments of the protocols, namely Bitcoin and Ethereum cryptocurrencies, it seems that the challenges to overcome will increase in the following months or years. That is not to diminish their remarkable innovative potential and the promise they bring to establish alternative new forms of digital value creation, sharing and enhancement of transactional  capacity.

But these protocols are still somewhat challenged by two shortcomings that plague their capacity to become de facto mainstream new value tokens: the anonymity limitations proved within blockchain networks and the scalability issues in currencies such as Bitcoin (Ethereum is better at the scalability issue, but not on the anonymity and robust security fronts).

While I was researching these issues I came to a nice paper that supported a talk (video) delivered at last year’s ACM CCS 2016 Conference on Computer and Communications Security. I will share both the video and briefly review the paper for the The Information Age viewers and followers today.

The paper introduces a new blockchain protocol paradigm aimed at resolving the scalability issues of current blockchain networks. The relatively long (but certainly bright) group of authors from the National University of Singapore present us with one such proposal that is called ELASTICO. Interestingly the proposal merges two disjoint management paradigms in datacenter data administration: that of sharding and fault-tolerant byzantine transactions, and they claim to demonstrate ELASTICO scaling properties beyond the theoretical assumptions.

A Secure Sharding Protocol For Open Blockchains

ABSTRACT

Cryptocurrencies, such as Bitcoin and 250 similar alt-coins, embody at their core a blockchain protocol — a mechanism for a distributed network of computational nodes to periodically agree on a set of new transactions. Designing a secure blockchain protocol relies on an open challenge in security, that of designing a highly scalable agreement protocol open to manipulation by byzantine or arbitrarily malicious nodes. Bitcoin’s blockchain agreement protocol exhibits security, but does not scale: it processes 3–7 transactions per second at present, irrespective of the available computation capacity at hand. In this paper, we propose a new distributed agreement protocol for permission-less blockchains called ELASTICO. ELASTICO scales transaction rates almost linearly with available computation for mining: the more the computation power in the network, the higher the number of transaction blocks selected per unit time. ELASTICO is efficient in its network messages and tolerates byzantine adversaries of up to one-fourth of the total computational power. Technically, ELASTICO uniformly partitions or parallelizes the mining network (securely) into smaller committees, each of which processes a disjoint set of transactions (or “shards”). While sharding is common in non-byzantine settings, ELASTICO is the first candidate for a secure sharding protocol with presence of byzantine adversaries. Our scalability experiments on Amazon EC2 with up to 1, 600 nodes confirm ELASTICO’s theoretical scaling properties.

Brief review of the paper

The video and the paper are a bit of technical stuff, requiring adequate background to properly follow the line of argumentation ( the view count on the YouTube channel is indication enough…). But the technically minded will find it enjoyable read, especially if they have been following, or have been involved with the topic of cryptocurrencies and blockchains. I will just briefly review the paper now, and after that I will share the video talk.

From the outset in the introductory paragraphs of the paper we can learn about the blockchain and Bitcoin protocols and their scaling properties:

At a high level, the blockchain protocol in Bitcoin randomly selects one processor per epoch (say 10 minutes) which issues a proposal that everyone adopts, thus requiring only a single broadcast to reach agreement [1]. There may be temporary disagreement if two proposals occur at the same time; eventually, with very high probability, one proposal will be established by picking the longest blockchain. Nakamoto consensus uses a proof-of-work (PoW) mechanism to probabilistically elect the leader, ensuring a fair choice of leaders. In terms of scale, Bitcoin employs billions of CPUs worth of computational power today (by observable hashrates [2]), and is one of the largest completely decentralized systems of such scale.

Unfortunately, Bitcoin’s transaction throughput does not scale well. The Bitcoin network consumes massive computational power and presently processes up to 7 transactions per second [3]. Other centralized fiat payment processing systems, like MasterCard or Visa are reported to processing 1, 200 to 56, 000 transactions per second [4, 5]. The demand from practical applications is 3 to 4 orders of magnitude higher. Modification to scale up existing protocol is a raging debate in the Bitcoin community [6–9]. Recent work shows that these proposals have fundamental scalability limits [10].

Furthermore – and this was an eye opener to me – current Byzantine consensus mechanisms and protocols introduce limitations in bandwidth capacity as the network grow large at a non linear rate. Hence the heart of the scalability issues with public blockchains has to do with how is it possible to linearize this process:

On the other hand, solutions which use classical Byzantine consensus protocols [11–14] do not work in an open environment like cryptocurrencies because of two fundamental challenges. First, many of these papers assume that the network nodes have preestablished identities or public-key infrastructure in place, which does not exist in open environments like Bitcoin. Second, practical byzantine consensus protocols such as PBFT [13] require at least a quadratic number of messages in the number of participants, thus they are bandwidth-limited — more network identities leads to worse performance. Network bandwidth limits the transaction throughputs for a network of even a few hundred nodes severely. This raises a fundamental question — are there any blockchain protocols that scale throughput linearly with the increase in the size of the network?

This was the challenge that the paper propose to tackle. Briefly the descriptions of the author’s approach will follow.

Problem and approach

Problem & Approach.

Our goal is to seek a protocol for the open, permissionless network wherein participating processors have no pre-established identities, and where the transaction throughput scales. We provide a new blockchain protocol called ELASTICO, which achieves a sweet spot between classical byzantine consensus and Nakamoto consensus protocols. The key idea in our approach is to partition the network into smaller committees, each of which processes a disjoint set of transactions (or a “shard”). Specifically, the number of committees grows near linearly in the total computational power of the network.

The assumption here is made, and actually proved, that the scaling problems with the current public blockchains and the Nakamoto blockchain has to do with reliance on trusted infrastructure or on federated identities. As such, only a new sharding approach could obviate those shortcomings:

The key idea in our approach is to partition the network into smaller committees, each of which processes a disjoint set of transactions (or a “shard”). Specifically, the number of committees grows near linearly in the total computational power of the network. Each committee has a reasonably small number of members so they can run a classical byzantine consensus protocol to decide their agreed set of transactions in parallel. Sharding protocols are commonly used in distributed databases and in cloud infrastructure, wherein certain network infrastructure can be trusted (e.g., see the commonly used two-phase commit protocol) or where the goal is to tolerate crash (non-byzantine) failures [15–17]. Note that several commercial and open-source blockchains do not target the permissionless (open) setting, and as a result, promise to scale by relying on trusted infrastructure [18–20] or by using federated identities [21, 22] (see Section 6). To our knowledge, we provide the first sharding protocol for permissionless blockchains tolerating a constant fraction of byzantine network nodes. This is a well-recognized open problem [10]. Our protocol makes the same assumptions as those implied in Bitcoin and other cryptocurrencies, and we provide security proofs for key invariants in our protocol.

In this brief sketch I will disclose the results from this paper. The paper then goes on describing in detail the implementation that is recommend read to the more technical and literate reader (I myself admit here now to have read only a few pages, but I intend to read it full…). I think ELASTICO, or its new distributed computing  consensus proposal might be of significance in the future for resolving and settle the scalability issues within public blockchains and the Nakamoto blockchain. From efforts such as these only better and improved ecosystems for blockchains and cryptocurrencies will emerge, I hope.

Results. Without loss of generality, we assume that the network contains n processors which have equivalent computational power. ELASTICO exhibits almost linear scalability with computation capacity and does not require quadratic number of messages as the network grows. ELASTICO tolerates up to f < n/4 adaptive byzantine adversaries, where f and n are bounds on the adversarial and total computational power respectively. 1 The protocol can support the same blockchain data structure format (a hash-chain) as Bitcoin; but, for further scalability, we propose a modification that permits better efficiency parameters.

(…)

We implement ELASTICO based on the most popular client for Bitcoin [23]. Our implementation adds roughly 5, 000 C++ LoCs (lines of code) on top of Bitcoin. The throughput of our prototype scales near linearly with respect to available computation i.e., O(n/ log log(n)), when runs on our network simulation. With the same network implementation as in Bitcoin, the scale up (blocks per epoch) for 100, 200, 400, 800 and 1, 600 nodes with equal computational power 2 are as theoretical expectation, namely 1, 1.89, 3.61, 6.98 and 13.5 times respectively. Finally, ELASTICO’s clean-slate design decouples the consensus from block-data broadcasts, hence the bandwidth spent by each node remains almost constant, regardless of the size of the network. Our simulations are necessarily on a smaller scale than Bitcoin; however, if we project our results to a full deployment to a network of Bitcoin’s scale, we can expect a scale up of 10, 000 in the number of agreed values per epoch. This agreement throughput is 4 orders of magnitude larger than Bitcoin’s.

The pseudocode of the algorithm below for setting up of the directory committee within the consensus protocol is well worth to display here for the followers and readers. To read code is becoming more important than ever, starting to beat the common language readership…(it will always be a complementary relationship though, at least for the foreseeable human only capacity to read text with sufficient complexity, but even then…), so:

shardblockalgo1

The video  of the talk supporting the paper

Authors: Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert and Prateek Saxena (National University of Singapore)

presented at CCS 2016 – the 23rd ACM Conference on Computer and Communications Security (Hofburg Palace Vienna, Austria / October 24-28, 2016) – organized by SBA Research.

Final remarks and conclusion

I will just close the post with a table from the paper (Table 1) describing the mathematical statements and lemmas found within the paper together with the problems ELASTICO and its sources of byzantine advantage managed to solve.It conveys a nice brief wrap up of the achievements of this effort:

shardblocktab1

featured image: CCS 2016 – A Secure Sharding Protocol For Open Blockchains

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s