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.

Bio:
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 blockchain.

Bio:
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, respectively.
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

Petr Kuznetsov

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 Bitcoin design.

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 directly 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 processes.