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
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
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
on Proof-of-Work (PoW), which forces participants to waste computational
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
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.
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.