Workshop on Blockchain Technology and Theory - Abstracts
Adapting to Evolving Threats against BFT Systems with Weighted and Diverse Replication
Alysson Bessani, University of Lisbon
The success of bitcoin and other blockchains lead to a renewed interest in Byzantine fault-tolerant (BFT) consensus protocols, with many recent contributions both from industry and academia. However, there are few long-standing issues with the practical deployment of these protocols on the internet – namely, their resilience to evolving threats – that remain mostly unaddressed. In this talk, I will discuss how BFT protocols can adapt to changing network conditions (e.g., due to DDoS) and to new common vulnerabilities on the replicas software by monitoring the environment and employing risk management and weighted replication.
Alysson Bessani is an Associate Professor of the University of Lisbon Faculty of Sciences, Portugal, and a member of LASIGE research unit. He received his Ph.D. in Electrical Engineering from UFSC (Brazil) in 2006, was a visiting professor at Carnegie Mellon University (2010) and a visiting researcher at Microsoft Research Cambridge (2014). Alysson coordinated/collaborated in ten international projects and co-authored more than 100 peer-reviewed publications on dependability, security, Byzantine fault tolerance, and cloud storage. He is also the principal researcher behind the BFT-SMaRt consensus library (http://bft-smart.github.io/library/) and a co-founder of the Vawlt dependable & secure cloud storage startup (https://vawlt.io). More information about him can be found in http://www.di.fc.ul.pt/~bessani.
Algorand: A Secure, Scalable and Decentralized Blockchain
Jing Chen, Stony Brook University and Algorand
Algorand is a permissionless blockchain that is truly secure, scalable and
decentralized. It works in a highly asynchronous environment, dispenses with
"proof of work" and "miners" and requires only a negligible amount of
computation. Moreover, its transaction history does not "fork", guaranteeing
immediate finality of a transaction the moment the transaction enters the
Jing Chen is Chief Scientist and Head of Theory Research at Algorand, and
Assistant Professor in the Computer Science Department at Stony Brook
University. Her main research interests are distributed ledgers, game
theory, and algorithms. Jing received her bachelor and master's degrees in
computer science from Tsinghua University, and her PhD in computer science
from MIT. She did a one-year postdoc at the Institute for Advanced Study,
Princeton. Jing received the NSF CAREER Award in 2016.
Layer-1 Scalability of Eventual-Consensus Blockchain Protocols
Peter Gaži, Input Output - IOHK
Limited scalability of blockchain-based distributed ledgers is one of the
key hurdles preventing mass adoption of decentralized cryptocurrencies. In
this talk, I will outline a series of results that propose and analyze
constructions for improving the scalability of any eventual-consensus
blockchain protocol broadly inspired by the Nakamoto longest-chain rule.
These solutions aim at improving throughput, latency, and storage
requirements of the underlying protocols without compromising on security,
and are applicable to both the proof-of-work and proof-of-stake setting, as
I will illustrate on Bitcoin and the Ouroboros family of protocols,
More concretely, I will focus on so-called layer-1 solutions, which share
the property that all executed transactions remain a part of the ledger(s)
produced by the protocol execution; this is complementary to layer-2
solutions such as payment channels. I will talk about two sides of a
spectrum of solutions: on one hand, sidechains-based constructions that
allow for a full sharding of the transactions stored in the ledger into
several separate chains that do not need to keep track of each other's
state, but still allow for cross-chain transfers. On the other side of the
spectrum are parallel-chains based constructions maintaining a single
ledger held by all parties, but significantly improving on throughput and
latency compared to a single-chain ledger.
The Consensus Number of a Cryptocurrency
Blockchain-based algorithms, such as Bitcoin, often implement
decentralized asset transfer systems, also referred to as
cryptocurrencies. Starting from the original paper by Nakamoto,
double-spending in such systems is achieved by solving consensus on the
order of transfer operations. But is consensus is necessary?
We show that the answer is no. In the most typical case, when only a
single process—the account owner—can withdraw from each account, the
asset transfer problem allows for a simple asynchronous solution, and
thus its consensus number is one. More generally, in "k-shared" asset
transfer, when an account can be debited by up to k users, the consensus
number is k.
As an important implication of this result, we describe an asynchronous
Byzantine fault-tolerant asset transfer implementation that is both
simpler and more efficient than state-of-the-art consensus-based
solutions. Finally, we discuss how randomization can be used to
overcome complexity barriers of deterministic asset transfer systems.
Bitcoin-like blockchains from efficient proof systems
Krzysztof Pietrzak, IST Austria
Bitcoin like blockchains from efficient proof systems.
Abstract: The security of the Bitcoin blockchain crucially relies on
the fact that the available computing power (used to solve proofs of
work) can only be used towards extending a single chain. If one
naively replaces proofs of work with proof systems that can be
computed fast (like proofs of space or proofs of stake) security
breaks down for various reason, as a consequence existing designs
often use much more sophisticated protocols with rotating committees
(e.g. in Algorand or Ouroboros). In this talk I will outline the Chia
network solves those problems while being almost as simple as the
Toward a Partially Synchronous Nakamoto-Style Blockchain
Christian Matt, Concordium
Existing blockchains based on Nakamoto-style consensus rely some sort of
synchrony assumptions. A basic requirement is that when a party generates a
new block, all previously generated blocks should already be known to that
party. Otherwise, the new block gets appended to an old block, which
results in a fork of the chain. This means that the parameters of the
blockchain need to be set such that the time between the generation of two
blocks is typically larger than the network delay. In practice, however,
the network delay is not a known constant but changes over time. Setting
the parameters assuming a larger delay than the actual one results in lost
efficiency; assuming a too small delay can result in security degradation.
In this talk, I will present a novel approach to measuring the condition of
a blockchain and how it can be used to continuously adapt the parameters
without knowledge of the network delays. This leads to the first
Nakamoto-Style blockchain that achieves security and optimal efficiency in
unknown network conditions.
Crime and Punishment in Tendermint
Zarko Milosevic, Interchain Foundation, Switzerland
Tendermint consensus guarantees the consensus properties if the faulty
validators have at most 1/3 of voting power in the current validator set.
In case this assumption does not hold, each of the consensus properties may
be violated. Lite clients in Tendermint-based systems do not connect
to validator nodes, therefore we can't rely on threshold based algorithms
to detect authenticity of response and an application state.
Therefore, faulty validators may forge blocks (different from those decided
on the main chain) and attack lite clients that connect to full nodes
controlled by those faulty validators (as part of Eclipse attack). In this
talk we give a taxonomy of fork-based attacks that can be executed
against lite clients in Tendermint-based systems followed by a description
of mechanisms that are used to detect and punish misbehaving