Program >
Venue >
Registration >
Contact >

Workshop on Blockchain Technology and Theory - Abstracts


Blockchain and BFT Design Choices: A Distributed Computing Perspective

Ittai Abraham, VMWare Research, Israel

At first sight Blockchain technologies and Byzantine Fault Tolerant (BFT) protocols seem fundamentally different. Using the lens of the theory of distributed computing I will suggest a more unified model that shows many of the similarities and highlights the foundational differences. After surveying some of the recent advances in the field I will discuss some emerging new hybrid approaches: how BFT protocols can help improve Blockchains and how Blockchain abstractions can be used to build more scalable and permissionless BFT solutions.

But Why Does It Work? A Rational Protocol Design Treatment of Bitcoin

Juan Garay, Texas A&M University, USA

An exciting recent line of work has focused on formally investigating the core cryptographic assumptions underlying the security of Bitcoin. In a nutshell, these works conclude that Bitcoin is secure if and only if the majority of the mining power is honest Despite their great impact, however, these works do not address an incisive question by positivists and Bitcoin critics, which is fueled by the fact that Bitcoin indeed works in reality: Why should the real-world system adhere to these assumptions?

In this work we employ the machinery from the Rational Protocol Design (RPD) framework by Garay *et al. *[FOCS '13] to analyze Bitcoin and address questions such as the above. We show that under the natural class of incentives for the miners' behavior---i.e., rewarding them for adding blocks to the blockchain but having them pay for mining---we can reserve the honest majority assumption as a fallback, or even, depending on the application, completely replace it by the assumption that the miners aim to maximize their revenue.

Our results underscore the appropriateness of RPD as a "rational cryptography'' framework for analyzing Bitcoin. Along the way, we devise significant extensions to the original RPD machinery that broaden its applicability to cryptocurrencies, which we believe can be of independent interest.

This is joint work with Christian Badertscher, Ueli Maurer, Daniel Tschudi, and Vassilis Zikas.

OmniLedger: A Secure, Scale-Out, Decentralized Ledger

Philipp Jovanovic, EPFL, Switzerland

Designing a secure, permissionless distributed ledger system that performs on par with classic payment service providers such as Visa is a challenging task. While many distributed ledger architectures have been proposed, they are either unable to scale-out or do so by prioritizing scalability over security or decentralization. In this work we propose OmniLedger, the first scale-out distributed ledger framework that provides throughput and latency appropriate for demanding real world applications. OmniLedger achieves its goals of decentralization, security, and scalability through several interesting subprotocols and techniques that offer secure and efficient 1) sharding via distributed randomness, 2) continuous operability, 3) intra-shard transactions (via ByzCoinX, an improved version of ByzCoin), 4) cross-shard transactions (via Atomix, a new atomic commit protocol for cross-shard transaction), 5) ledger pruning (via state blocks), and 6) real-time transaction confirmation (via trust-but-verify transaction validation). The evaluation of our Omniledger prototype shows that, given a sufficient number of validators, OmniLedger's throughput scales linear in the number of shards, capable of going to Visa-level and beyond, while providing low-latency for transaction confirmations on the order of a few seconds.

Message Passing and Shared Memory Blockchain Abbreviation

Shlomi Dolev, Ben-Gurion University, Israel

Blockchains' ever increasing size has become a major problem. Bitcoin, for example, has grown to 115120 MB as of May 2017, which is roughly 115 GB. This uncontrollable growth of the Blockchain is bound to become an issue in the future, as hard disks may become too small to store the entire Blockchain history and traversing the transactions databases may become increasingly slow. Already, there are lightweight clients in various Blockchain platforms (Bitcoin included), which do not store the entire chains locally but rely on a third party to send them the blocks they need. There are many issues with these clients, mainly security problems, since they go back to trusting a central authority rather than gaining trust from several distributed peers. Namely, these clients' knowledge of the Blockchain is solely based on some third party that should be trusted, while the conceptual base for Blockchain is trust distributing. In this research we present two Blockchain abbreviation schemes. The first one is based on the Ethereum project and proposes replacing the full Blockchain with a new Genesis block, which summarizes everyone's account balances at a certain point in time. One possible benefit is to use less communication while still storing the prefix of the old Blockchain (or signature of the Blockchain that can validate a version archived by other participants) in a local archive. Here we trade loss of transaction history for efficiency. Our second contribution is a UNIX based architecture using the file system, for implementing Blockchain. We demonstrate a Blockchain abbreviation technique for this architecture too.

Proof of Stake Blockchain Protocols

Aggelos Kiayias, University of Edinburgh, UK & IOHK

We present recent results in the design and analysis of proof of stake blockchain protocols. The talk will cover the design strategy behind Ouroboros and Ouroboros Praos, as well as we will introduce and analyze the concept of forkable strings as well as string divergence which is at the core of the security analysis. The security analysis covers both the synchronous and partial synchronous model as well as static, delayed and fully adaptive corruptions.

REM: Resource-Efficient Mining for Blockchains

Ittay Eyal, Cornell University, USA and Technion, Israel

Blockchains show promise as potential infrastructure for financial transaction systems. The security of blockchains today, however, relies critically on Proof-of-Work (PoW), which forces participants to waste computational resources.

We present REM (Resource Efficient Mining), a new blockchain mining framework that uses trusted hardware (Intel SGX). REM achieves security guarantees similar to PoW, but leverages the partially decentralized trust model inherent in SGX to achieve a fraction of the waste of PoW. Its key idea, Proof-of-Useful-Work (PoUW), involves miners providing trustworthy reporting on CPU cycles they devote to inherently useful workloads. REM flexibly allows any entity to create a useful workload. REM ensures the trustworthiness of these workloads by means of a novel scheme of hierarchical attestations that may be of independent interest.

To address the risk of compromised SGX CPUs, we develop a statistics-based formal security framework, also relevant to other trusted-hardware-based approaches such as Intel's Proof of Elapsed Time (PoET). We show through economic analysis that REM achieves less waste than PoET and variant schemes.

We implement REM and, as an example application, swap it into the consensus layer of Bitcoin core. The result is the first full implementation of an SGX-based blockchain. We experiment with four example applications as useful workloads for our implementation of REM, and report a computational overhead of 5-15%.

On Sustainable Economic Incentives for Blockchains

Fabio Pianese, Nokia - Bell Labs, France

Public blockchain networks such as Bitcoin constitute a novel type of economic system whose properties and likelihood to survive over time are entirely defined by algorithmic choices introduced in software. The relationship among blockchain nodes (who "mine" the currency by solving PoW challenges) and users (who decide whether to generate blockchain transactions) are dictated by a number of incentive mechanisms that make it more or less worthwhile for either category to engage with the system.

We attempt to model the dynamic behavior of a blockchain based on the concept of sustainability, expressed as the ratio between the revenue extracted by system participants versus the cost incurred. In this talk we frame the impact of algorithmic choices such as fixed-size transaction fees, proportional fees, and block reward size on blockchain behavior under variable hypotheses and external conditions, survey recent related results, and propose a set of guidelines for sustainable blockchain incentive design.

Bitcoin Blockchain as a Shared Distributed Register

Romaric Ludinard, IMT Atlantique, France

Since a couple of months, distributed ledgers gained a very large audience reaching economical, political and daily media. However, there are few studies that provides properties and abstractions that fully capture the behavior of distributed ledgers. The interest in formalizing the behavior of distributed ledgers is twofold. Firstly, it helps to prove the correctness of the algorithms that implement existing distributed ledgers and explore their limits with respect to an unfriendly environment and target applications. Secondly, it facilitates the identification of the minimal building blocks necessary to implement the distributed ledger in a specific environment. Even though the behavior of distributed ledgers is similar to abstractions that have been deeply studied for decades in distributed systems no abstraction is sufficiently powerful to capture the distributed ledger behavior. We introduce the Distributed Ledger Register, a register that mimics the behavior of one of the most popular distributed ledger, i.e. the Bitcoin ledger. The aim of our work is to provide formal guarantees on the coherent evolution of Bitcoin. we prove that the Distributed Ledger Register verifies the regularity register specification. It follows that the strongest coherency implemented by Bitcoin is regularity under strong assumptions (i.e. partial synchronous systems and sparse reads). This study contradicts the common belief that Bitcoin implements strong coherency criteria in a totally asynchronous system.

Thunderella: A Fast and Scalable Blockchain

Elaine Shi, Cornell University, USA

State machine replication, or “consensus”, is a central abstraction for distributed systems where a set of nodes seek to agree on an ever-growing, linearly-ordered log. In this paper, we propose a practical new paradigm called Thunderella for achieving state machine replication by combining a fast, asynchronous path with a (slow) synchronous “fall-back” path (which only gets executed if something goes wrong); as a consequence, we get simple state machine replications that essentially are as robust as the best synchronous protocols, yet “optimistically” (if a super majority of the players are honest), the protocol “instantly” confirms transactions. We provide instantiations of this paradigm in both permissionless (using proof-of-work) and permissioned settings. Most notably, this yields a new blockchain protocol (for the permissionless setting) that remains resilient assuming only that a majority of the computing power is controlled by honest players, yet optimistically—if 3/4 of the computing power is controlled by honest players, and a special player called the “accelerator”, is honest—transactions are confirmed as fast as the actual message delay in the network. We additionally show the 3/4 optimistic bound is tight for protocols that are resilient assuming only an honest majority.

Sleepy Consensus

Rafael Pass, Cornell University, USA

The distributed systems literature adopts two primary network models, the synchronous model where honest messages are delivered in the next round, and the partially synchronous (or asynchronous) model where honest messages are subject to unpredictable adversarial delays. In this paper, we show that more nuanced formal models exist beyond the traditional synchrony and asynchrony stratification -- and interestingly, such new models allow us to articulate new robustness properties that traditional models would have failed to capture. More specifically, we articulate a new formal model called “the sleepy model of consensus”, where we classify honest nodes as being either alert or sleepy. Alertness implies that the node is online and has good network connections; whereas sleepiness captures any type of failure or network jitter. We then describe the Sleepy consensus protocol that achieves security as long as at any time, the number of alert nodes outnumber corrupt ones. No classical synchronous or asynchronous protocols attain such robustness guarantees, and yet we show how to leverage Nakamoto’s blockchain protocol, but without proofs-of-work, to achieve these properties, assuming collision resistant hash functions, the existence of a public-key infrastructure and a common reference string.

On Bitcoin's Limitations to Deliver Fairness to Users

Sara Tucci-Piergiovanni, CEA LIST, France

While current Bitcoin literature mainly focuses on miners behavior, little has been done to analyze user participation. Because Bitcoin’s users do not benefit from any incentive, their participation in the system is conditional upon system ability to provide a transactional service at a reasonable cost and acceptable quality. A recent observed trend on a growing number of unconfirmed transactions seems, however, to substantiate that Bitcoin is facing service degradation. The objective of this talk is to shed some light on user participation in Bitcoin against a notion of system fairness, using a utility-based approach. We first introduce fairness to quantify participants' satisfaction degree with respect to justified expectations. We then characterize user strategies, deriving a necessary condition for fairness, and we show Bitcoin limitations in delivering it. The utility-based model allows to draw conclusions on possible improvements for fairness to promote user participation.

Hyperledger Fabric V1

Christian Cachin, IBM Research - Zurich, Switzerland

Hyperledger Fabric V1 is a modular blockchain operating system for running a distributed ledger among a consortium. It is being developed open-source under the Hyperledger Project. Fabric V1 goes beyond previous blockchain platforms several ways. The consensus mechanism is modular, such that every deployment can be tailored to a specific trust model; crash-tolerant and Byzantine-fault-tolerant consensus protocol implementations currently exist. Furthermore, by exploiting ideas from replicated databases, it supports performance, scalability, confidentiality for data, and non-deterministic execution. As a contributor to Fabric V1, I will explain its architecture and the current status.

Scalable and Resilient Block Diffusion for Permissioned Distributed Ledgers

Gregory Chockler, Royal Holloway, University of London (RHUL), UK


The Red Belly Blockchain: BFT is Back but is it the Same?

Vincent Gramoli, University of Sydney, Australia

Most consensus protocols used in consistent blockchains were designed in a context that predates the concept of blockchain. In this talk, I will present the difference between the new Blockchain consensus problem and the classic consensus problem and explains how this difference helped us develop the Red Belly Blockchain.

Vincent Gramoli is the head of the Concurrent Systems Research Group at the University of Sydney and a Senior Researcher at Data61-CSIRO. Prior to this, he was affiliated with Cornell and EPFL, and obtained his PhD from Rennes and his habilitation from UPMC Sorbonne University.

Subversion Resistance of SNARKs

Georg Fuchsbauer, Inria and Ecole Normale Superieure, Paris, France

Zero-knowledge (ZK) SNARKs let one give succinct proofs which do not reveal anything apart from the truth of the proved statement. They are the central cryptographic component behind Zcash and ZK contingent payments in Bitcoin. Their main drawback is that they require parameters that must be set up in a trusted way. While it is known that soundness breaks down when the parameters are subverted, we investigate the implications of subversion for zero knowledge. We show that under plausible hardness assumptions, many SNARK schemes proposed in the literature are subversion-resistant ZK or can be made at very little cost.