The Decrypto Seminar is a weekly seminar in which members of our group present a research-level topic in the area of blockchain research. The presentations take place online every Wednesday and last about one hour, with discussion and questions following. The presenter is an expert on the topic they are presenting, usually one of the co-authors of the paper presented or a software engineer in the implementation discussed. The presentations concern peer reviewed and upcoming research papers, technical proposals, experiments and measurements, as well as implementation and engineering topics on blockchains and cryptocurrencies. Subscribe for Seminar Updates

Upcoming Seminars

June 2, 2021, 03:00 PM UTC

Divide and Scale: Formalization of Distributed Ledger Sharding Protocols
Zeta Avarikioti, ETH Zurich and IST Austria

Sharding distributed ledgers is the most promising on-chain solution for scaling blockchain technology. In this work, we define and analyze the properties a sharded distributed ledger should fulfill. More specifically, we show that a sharded blockchain cannot be scalable under a fully adaptive adversary, but it can scale up to O(n/logn) under an epoch-adaptive adversary. This is possible only if the distributed ledger creates succinct proofs of the valid state updates at the end of each epoch. Our model builds upon and extends the Bitcoin backbone protocol by defining consistency and scalability. Consistency encompasses the need for atomic execution of cross-shard transactions to preserve safety, whereas scalability encapsulates the speedup a sharded system can gain in comparison to a non-sharded system. We introduce a protocol abstraction and highlight the sufficient components for secure and efficient sharding in our model. In order to show the power of our framework, we analyze the most prominent sharded blockchains (Elastico, Monoxide, OmniLedger, RapidChain) and pinpoint where they fail to meet the desired properties.

Join seminar
Password: 5SBwfj
On Wednesday, June 2, 2021, 03:00 PM UTC, Zeta Avarikioti from ETH Zurich and IST Austria will present "Divide and Scale: Formalization of Distributed Ledger Sharding Protocols". Abstract: Sharding distributed ledgers is the most promising on-chain solution for scaling blockchain technology. In this work, we define and analyze the properties a sharded distributed ledger should fulfill. More specifically, we show that a sharded blockchain cannot be scalable under a fully adaptive adversary, but it can scale up to O(n/logn) under an epoch-adaptive adversary. This is possible only if the distributed ledger creates succinct proofs of the valid state updates at the end of each epoch. Our model builds upon and extends the Bitcoin backbone protocol by defining consistency and scalability. Consistency encompasses the need for atomic execution of cross-shard transactions to preserve safety, whereas scalability encapsulates the speedup a sharded system can gain in comparison to a non-sharded system. We introduce a protocol abstraction and highlight the sufficient components for secure and efficient sharding in our model. In order to show the power of our framework, we analyze the most prominent sharded blockchains (Elastico, Monoxide, OmniLedger, RapidChain) and pinpoint where they fail to meet the desired properties. Join here: https://zoom.us/j/96976751658?pwd=TjN3VmhRWjRuWVNLWHJha0dITVZtZz09 Password: 5SBwfj More seminars: https://decrypto.org/seminar

June 9, 2021, 03:00 PM UTC

(To be determined)
Nikos Karayannidis, IOHK

Join seminar
Password: x7Eg5a
On Wednesday, June 9, 2021, 03:00 PM UTC, Nikos Karayannidis from IOHK will present "(To be determined)". Abstract: Join here: https://zoom.us/j/95803314057?pwd=NzB2bkY5YzdVMDlBSTluZ3RwUGhndz09 Password: x7Eg5a More seminars: https://decrypto.org/seminar

June 16, 2021, 03:00 PM UTC

SNACKs: Proofs of Sequentiality for Light-Client Blockchain Protocols
Hamza Abusalah, TU Wien

The remarkable success of blockchain technologies has resulted in ever-growing blockchains that are stored by all participating full nodes. On the other hand, nodes called light clients only store a very limited amount of blockchain-related data, and rely on the mediation of full nodes whenever interacting with the blockchain. It is essential for broader adoption of blockchains to design protocols that allow this interaction to be trustless from the light-client perspective. In this work, we revisit the problem of designing light-client blockchain protocols and approach it from the perspective of classical proof system theory, resulting in a framework that allows to quantify the security guarantees provided to a verifier (a light client) even when interacting only with a single dishonest prover (a full node). More precisely, we define a new general primitive called succinct non-interactive argument of chain knowledge (SNACK) capturing this intuition, and show how to augment any blockchain with a graph-labeling proof of sequential work (GL-PoSW) to enable SNACK proofs for this blockchain. Along the way, we provide a unified and extended definition of GL-PoSW covering all previous constructions, and describe two new variants of GL-PoSWs suitable for our application. We show how SNACKs can be used to construct light-client blockchain protocols and compare to existing solutions.

Join seminar
Password: P4LXiA
On Wednesday, June 16, 2021, 03:00 PM UTC, Hamza Abusalah from TU Wien will present "SNACKs: Proofs of Sequentiality for Light-Client Blockchain Protocols". Abstract: The remarkable success of blockchain technologies has resulted in ever-growing blockchains that are stored by all participating full nodes. On the other hand, nodes called light clients only store a very limited amount of blockchain-related data, and rely on the mediation of full nodes whenever interacting with the blockchain. It is essential for broader adoption of blockchains to design protocols that allow this interaction to be trustless from the light-client perspective. In this work, we revisit the problem of designing light-client blockchain protocols and approach it from the perspective of classical proof system theory, resulting in a framework that allows to quantify the security guarantees provided to a verifier (a light client) even when interacting only with a single dishonest prover (a full node). More precisely, we define a new general primitive called succinct non-interactive argument of chain knowledge (SNACK) capturing this intuition, and show how to augment any blockchain with a graph-labeling proof of sequential work (GL-PoSW) to enable SNACK proofs for this blockchain. Along the way, we provide a unified and extended definition of GL-PoSW covering all previous constructions, and describe two new variants of GL-PoSWs suitable for our application. We show how SNACKs can be used to construct light-client blockchain protocols and compare to existing solutions. Join here: https://zoom.us/j/99659360882?pwd=cDJzS3BoVGh0eWZpV0J6cG1rd2ZxUT09 Password: P4LXiA More seminars: https://decrypto.org/seminar

Past Seminars

May 5, 2021

Resource-Aware Session Types for Digital Contracts
Ankush Das, Carnegie Mellon University

While there exist several successful techniques for supporting programmers in deriving static resource bounds for sequential code, analyzing the resource usage of message-passing concurrent processes poses additional challenges. To meet these challenges, this talk presents an analysis for statically deriving worst-case bounds on the computational complexity of message-passing processes. The analysis is based on novel resource-aware session types that describe resource contracts by allowing both messages and processes to carry potential and amortize cost. The talk then applies session types to implement digital contracts. Digital contracts are protocols that describe and enforce execution of a contract, often among mutually distrusting parties. Programming digital contracts comes with its unique challenges, which include describing and enforcing protocols of interaction, analyzing resource usage and tracking linear assets. The talk presents the type-theoretic foundations of Nomos, a programming language for digital contracts whose type system addresses the aforementioned domain-specific requirements. To express and enforce protocols, Nomos is based on shared binary session types rooted in linear logic. To control resource usage, Nomos uses resource-aware session types and automatic amortized resource analysis, a type-based technique for inferring resource bounds. To track assets, Nomos employs a linear type system that prevents assets from being duplicated or discarded. The talk concludes with future work directions on designing an efficient implementation for Nomos and making it robust to attacks from malicious entities.

April 28, 2021

Fast Isomorphic State Channels
Sandro Coretti-Drayton, IOHK

In this talk we’ll look at a construction of isomorphic multi-party state channels, where “isomorphic” refers to directly adopting the layer-one smart contract system; this allows the same code to be used on- and off-chain. The ledger model used is the so-called Extended UTxO (EUTxO) model, which brings Turing-complete smart contracts to the UTXO model first used by Bitcoin. In order to achieve such state channels, so-called “heads,” an arbitrary set of parties can “commit” a subset of the mainchain UTxO set to a state machine, evolve it offchain with a head protocol, and eventually (or in case of corruption among the parties) return the evolved UTxO set back to the mainchain. The head protocol has smaller round complexity than all previous proposals and enables the state-channel processing to advance on-demand, concurrently, and asynchronously. We establish strong security properties for the protocol and present and evaluate extensive simulation results that demonstrate that Hydra approaches the physical limits of the network in terms of transaction confirmation time and throughput while keeping storage requirements at the lowest possible.

Watch video

April 21, 2021

Threshold Garbled Circuits and Ad Hoc Secure Computation
Michele Ciampi, University of Edinburgh

Garbled Circuits (GCs) represent fundamental and powerful tools in cryptography, and many variants of GCs have been considered since their introduction. An important property of the garbled circuits is that they can be evaluated securely if and only if exactly 1 key for each input wire is obtained: no less and no more. In this work we study the case when: 1) some of the wire-keys are missing, but we are still interested in computing the output of the garbled circuit and 2) the evaluator of the GC might have both keys for a constant number of wires. We start to study this question in terms of non-interactive multi-party computation (NIMPC) which is strongly connected with GCs. In this notion, there is a fixed number of parties (n) that can get correlated information from a trusted setup. Then these parties can send an encoding of their input to an evaluator, which can compute the output of the function. Similarly to the notion of ad hoc secure computation proposed by Beimel et al. [ITCS 2016], we consider the case when less than n parties participate in the online phase, and in addition we let these parties collude with the evaluator. We refer to this notion as Threshold NIMPC. In addition, we show that when the number of parties participating in the online phase is a fixed threshold l ≤ n then it is possible to securely evaluate any l-input function.

Watch video

April 14, 2021

Everything is a Race and Nakamoto Always Wins
Ertem Nusret Tas, Stanford University

Nakamoto invented the longest chain protocol, and claimed its security by analyzing the private double-spend attack, a race between the adversary and the honest nodes to grow a longer chain. But is it the worst attack? We answer the question in the affirmative for three classes of longest chain protocols, designed for different consensus models: 1) Nakamoto's original Proof-of-Work protocol; 2) Ouroboros and SnowWhite Proof-of-Stake protocols; 3) Chia Proof-of-Space protocol. As a consequence, exact characterization of the maximum tolerable adversary power is obtained for each protocol as a function of the average block time normalized by the network delay. The security analysis of these protocols is performed in a unified manner by a novel method of reducing all attacks to a race between the adversary and the honest nodes.

Watch video

April 7, 2021

Resolving the Availability-Finality Dilemma, or, Fixing Ethereum 2.0's Consensus Protocol
Joachim Neu, Stanford University

The CAP theorem says that no consensus protocol can be live under dynamic participation and safe under network partitions. To resolve this availability-finality dilemma, we formalize a new class of flexible consensus protocols, ebb-and-flow protocols, which support a full dynamically available ledger in conjunction with a finalized prefix ledger. The finalized ledger falls behind the full ledger when the network partitions but catches up when the network heals. Gasper, the current candidate for Ethereum 2.0's beacon chain, aims to achieve this property, but we discovered an attack in the standard synchronous network model. We present a construction of provably secure ebb-and- flow protocols with optimal resilience, based on black-box composition of an off-the-shelf dynamically available and an off-the-shelf partially synchronous BFT protocol.

Get slides

March 31, 2021

FnF-BFT: Exploring Performance Limits of BFT Protocols
Lioba Heimbach, ETH Zurich

We introduce FnF-BFT, a parallel-leader byzantine fault-tolerant state-machine replication protocol for the partially synchronous model with theoretical performance bounds during synchrony. By allowing all replicas to act as leaders and propose requests independently, FnF-BFT parallelizes the execution of requests. Leader parallelization distributes the load over the entire network – increasing throughput by overcoming the single-leader bottleneck. We further use historical data to ensure that well-performing replicas are in command. FnF-BFT’s communication complexity is linear in the number of replicas during synchrony and thus competitive with state-of-the-art protocols. Finally, with FnF-BFT, we introduce the first BFT protocol with performance guarantees in stable network conditions under truly byzantine attacks. A prototype implementation of FnF-BFT outperforms (state-of-the-art) HotStuff’s throughput, especially as replicas increase, showcasing FnF-BFT’s significantly improved scaling capabilities.

Get slides

March 24, 2021

A Brief History of Currency Stability
Dimitris Karakostas, University of Edinburgh

What connects the 1600s Dutch Republic to the early 21st century digital space? What were the biggest economic and monetary debates since Adam Smith wrote the "Wealth of Nations"? What do cryptocurrencies stand to learn from the Great Crises of capitalism? Why is Bitcoin's price volatile and how do stablecoins attempt to solve this problem? In our presentation, we try to answer these questions and understand how Bitcoin and stablecoins fit in the brief history of economics.

Get slides Watch video

March 17, 2021

Gossiping For Communication-Efficient Broadcast
Giorgos Tsimos, University of Maryland

Broadcast (BC) is a crucial ingredient for a plethora of cryptographic protocols such as secret sharing and multiparty computation. In this talk, we present new randomized BC protocols with improved communication complexity and secure against an adversary controlling the majority of parties. We utilize gossiping i.e. propagating a message by sending to a few random parties who in turn do the same, until the message is delivered. We show a protocol for single-sender BC that achieves O (n^2 κ^2) bits of communication and where no trusted setup is required. We also present, to the best of our knowledge, the first non-trivial, adaptively-secure parallel BC protocol (widely used in MPC) with O (n^2 κ^4) communication complexity, improving existing parallel BC protocols of O(n^3) communication.

Get slides Watch video

March 10, 2021

Mir-BFT: High-Throughput Robust BFT for Decentralized Networks
Chrysoula Stathakopoulou, IBM Research

This paper presents Mir-BFT, a robust Byzantine fault-tolerant (BFT) total order broadcast protocol aimed at maximizing throughput on wide-area networks (WANs), targeting deployments in decentralized networks, such as permissioned and Proof-of-Stake permissionless blockchain systems. Mir-BFT is the first BFT protocol that allows multiple leaders to propose request batches independently (i.e., parallel leaders), in a way that precludes request duplication attacks by malicious (Byzantine) clients, by rotating the assignment of a partitioned request hash space to leaders. As this mechanism removes a single-leader bandwidth bottleneck and exposes a computation bottleneck related to authenticating clients even on a WAN, our protocol further boosts throughput using a client signature verification sharding optimization. Our evaluation shows that Mir-BFT outperforms state-of-the-art and orders more than 60000 signed Bitcoin-sized (500-byte) transactions per second on a widely distributed 100 nodes, 1 Gbps WAN setup, with typical latencies of few seconds. We also evaluate Mir-BFT under different crash and Byzantine faults, demonstrating its performance robustness. Mir-BFT relies on classical BFT protocol constructs, which simplifies reasoning about its correctness. Specifically, Mir-BFT is a generalization of the celebrated and scrutinized PBFT protocol. In a nutshell, Mir-BFT follows PBFT "safety-wise", with changes needed to accommodate novel features restricted to PBFT liveness.

Watch video

February 24, 2021

Blitz: Secure Multi-Hop Payments Without Two-Phase-Commits
Lukas Aumayr, TU Wien

Payment-channel networks (PCN) are the most prominent approach to tackle the scalability issues of current permissionless blockchains. A PCN reduces the load on-chain by allowing arbitrarily many off-chain multi-hop payments (MHP) between any two users connected through a path of payment channels. Unfortunately, current protocols for MHP are far from satisfactory. One round MHP (e.g., Interledger) are insecure as a malicious intermediary can steal the payment funds. Two-round MHP (e.g., Lightning Network (LN)) follow the 2-phase-commit paradigm as in databases to overcome this issue. However, when tied with economical incentives, 2-phase-commit brings other security threats (i.e., wormhole attacks), staggered collateral (i.e., funds are locked for a time proportional to the payment path length) and dependency on specific scripting language functionality (e.g., hash time lock contracts) that hinders a wider deployment in practice. We present Blitz, a novel MHP protocol that demonstrates for the first time that we can achieve the best of the two worlds: a single round MHP where no malicious intermediary can steal coins. Moreover, Blitz provides privacy for sender and receiver, it is not prone to the wormhole attack and it requires only constant collateral. Additionally, we construct MHP using only digital signatures and a timelock functionality, both available at the core of virtually every cryptocurrency today. We provide the cryptographic details of Blitz and we formally prove its security. Furthermore, our experimental evaluation on an LN snapshot shows that the LN collateral results in between 4x and 33x more unsuccessful payments than the Blitz collateral (both compared to a baseline). Blitz reduces the size of the payment contract by 26% and prevents up to 0.3 BTC (3397 USD in October 2020) in fees being stolen over a three day period as it avoids wormhole attacks by design.

Get slides Watch video

February 17, 2021

Using Universal Composability to implement off-chain payment channels
Andrew Miller, University of Illinois Urbana-Champaign

In this talk we’ll discuss work in progress on implementing payment channels in Python-SaUCy, a library for distributed protocols based on Universal Composability (UC). UC is a formal framework originating in cryptography and used for the on-paper analysis of protocols including blockchains and off-chain payment channels, but it isn’t something that software developers use. Our experience building a simple payment channel in Python-SaUCy shows that there are already several benefits. The software comes with an executable specification, in the form of a UC ideal functionality. You can execute our payment channel specification to better understand what the protocol does. We also support test driven fault tolerance analysis directly based on the security specification. It can represent test cases where the environment produces different output in the ideal world than in the real world. This gives some view of how in the future, formal security specifications could be packaged along with full-featured payment channels and other blockchain software releases.

February 10, 2021

Cross-Layer Deanonymization Methods in the Lightning Protocol
Romiti Matteo and Friedhelm Victor, Austrian Institute of Technology and Technische Universität Berlin

Bitcoin (BTC) pseudonyms (layer 1) can effectively be deanonymized using heuristic clustering techniques. However, while performing transactions off-chain (layer 2) in the Lightning Network (LN) seems to enhance privacy, a systematic analysis of the anonymity and privacy leakages due to the interaction between the two layers is missing. We present clustering heuristics that group BTC addresses, based on their interaction with the LN, as well as LN nodes, based on shared naming and hosting information. We also present linking heuristics that link 45.97% of all LN nodes to 29.61% BTC addresses interacting with the LN. These links allow us to attribute information (e.g., aliases, IP addresses) to 21.19% of the BTC addresses contributing to their deanonymization. Further, these deanonymization results suggest that the security and privacy of LN payments are weaker than commonly believed, with LN users being at the mercy of as few as five actors that control 36 nodes and over 33% of the total capacity. Overall, this is the first paper to present a method for linking LN nodes with BTC addresses across layers and to discuss privacy and security implications.

Get slides Watch video

February 3, 2021

Leader Based Consensus in Proof of Stake Networks
Giorgos Vlachos, Axelar

Byzantine fault tolerant state machine replication protocols are core building blocks for Proof of Stake (PoS) networks. The starting point for many such systems is Practical Byzantine Fault Tolerance (PBFT). Unfortunately, PBFT is not suitable for the permissionless setting, because it works best when the leader that proposes blocks of transactions is fixed for a long time period and always behaves honestly. For PoS networks, anybody should be able to become a leader, and thus this assumption is easily violated. Several recent protocols such as Casper, Algorand, Tendermint, and HotStuff, allow for efficient leader rotation and are thus more suitable for the permissionless setting. In this talk, we will review some of these protocols and compare their models and efficiency.

January 27, 2021

Distributed Authenticated Data Structures and their Applications
Charalampos Papamanthou, University of Maryland

We put forth a new model for distributed authenticated data structures. In a distributed authenticated data structure of n elements and p parties, every party stores n/p elements along with their corresponding proofs; a designated trusted party holds the digest of the authenticated data structure. Whenever an update is issued to the data structure, all parties should be able to efficiently update their local proofs and digests. Additionally, a party that has received multiple (verifying) proofs from other parties should be able to produce a small aggregate proof and forward it to another party for verification. Traditional Merkle trees and other vector commitments are not distributed since they fail to support efficient distributed updates or to achieve aggregation. After a short literature review, we will present a new distributed authenticated data structure, called multilinear tree, that satisfies our objectives. We will conclude with some open problems in the area, along with applications of distributed authenticated data structures in stateless validation for cryptocurrencies.

Get slides Watch video

January 20, 2021

Payment Trees: Low Collateral Payments for Payment Channel Networks
Maxim Jourenko, Tokyo Institute of Technology

The security of blockchain based decentralized ledgers relies on consensus protocols executed between mutually distrustful parties. Such protocols incur delays which severely limit the throughput of such ledgers. Payment and state channels enable execution of offchain protocols that allow interaction between parties without involving the consensus protocol. Protocols such as Hashed Timelock Contracts (HTLC) and Sprites (FC'19) connect channels into Payment Channel Networks (PCN) allowing payments across a path of payment channels. Such a payment requires each party to lock away funds for an amount of time. The product of funds and locktime is the collateral of the party, i.e., their cost of opportunity to forward a payment. In the case of HTLC, the locktime is linear to the length of the path, making the total collateral invested across the path quadratic in size of its length. Sprites improved on this by reducing the locktime to a constant by utilizing smart contracts. We propose the Payment Trees protocol that allows payments across a PCN with linear total collateral without the aid of smart contracts. A competitive performance similar to Sprites, and yet compatible to Bitcoin.

Get slides Watch video

December 9, 2020

Post-Quantum Adaptor Signatures for Privacy-Preserving Off-Chain Payments
Erkan Tairi, TU Wien

Adaptor signatures (AS) are an extension of digital signatures that enable the encoding of a cryptographic hard problem (e.g., discrete logarithm) within the signature itself. An AS scheme ensures that (i) the signature can be created only by the user knowing the solution to the cryptographic problem; (ii) the signature reveals the solution itself; (iii) the signature can be verified with the standard verification algorithm. These properties have made AS a salient building block for many blockchain applications, in particular, off-chain payment systems such as payment-channel networks, payment-channel hubs, atomic swaps or discrete log contracts. Current AS constructions, however, are not secure against adversaries with access to a quantum computer. In this talk, we present constructions for adaptor signatures that rely on cryptographic assumptions that are post-quantum secure, and show how they can be seamlessly leveraged to build post-quantum off-chain payment applications such as payment-channel networks without harming their security and privacy.

Get slides

December 2, 2020

LazyLedger: A Distributed Data Availability Ledger With Client-Side Smart Contracts
Mustafa Al-Bassam, University College London

We propose LazyLedger, a design for distributed ledgers where the blockchain is optimised for solely ordering and guaranteeing the availability of transaction data. Responsibility for executing and validating transactions is shifted to only the clients that have an interest in specific transactions relating to blockchain applications that they use. As the core function of the consensus system of a distributed ledger is to order transactions and ensure their availability, consensus participants do not necessarily need to be concerned with the contents of those transactions. This reduces the problem of block verification to data availability verification, which can be achieved probabilistically with sub-linear complexity, without downloading the whole block. The amount of resources required to reach consensus can thus be minimised, as transaction validity rules can be decoupled from consensus rules. We also implement and evaluate several example LazyLedger applications, and validate that the workload of clients of specific applications does not significantly increase when the workload of other applications that use the same chain increase.

Get slides

November 25, 2020

RandChain: Decentralised Randomness Beacon from Sequential Proof-of-Work
Runchao Han, Monash University

Decentralised Randomness Beacon (DRB) is a service that generates publicly verifiable randomness. Constructing DRB protocols is challenging. Existing DRB protocols suffer from strong network synchrony assumptions, high communication complexity and/or various attacks. In this paper, we propose RandChain, a new family of DRB protocols. RandChain is constructed from Sequential Proof-of-Work (SeqPoW), a Proof-of-Work (PoW) variant that is sequential, i.e., the work can only be done by a single processor. In RandChain, nodes jointly maintain a blockchain, and each block derives a random output. To append a block to the blockchain, each node should keep mining, i.e., solve a SeqPoW puzzle derived from the last block and its identity. Given the SeqPoW and its fixed input, mining is non-parallelisable. RandChain applies Nakamoto consensus so that nodes agree on a unique blockchain. While inheriting simplicity and scalability from Nakamoto consensus, RandChain produces strongly unpredictable randomness and remains energy-efficient and decentralised. RandChain does not require nodes to provide local entropy, thus giving no opportunity to bias randomness. Solutions of SeqPoW puzzles are unpredictable, so nodes cannot predict randomness. As each node can use at most a single processor for mining, RandChain remains energy-efficient. The mining speed is bounded by processors’ clock rate, which is hard to improve further. Thus, powerful nodes can gain limited advantage over mining, and RandChain achieves a high degree of decentralisation.

Get slides Watch video

November 18, 2020

Trustless Cross-Chain Communication: Impossible but Incentive Compatible
Alexei Zamyatin, Imperial College London and Interlay

Since the advent of Bitcoin, a plethora of distributed ledgers has been created, differing in design and purpose. Considering it is unlikely that there will be "one coin to rule them all", interoperability has shifted into the focus of industry and academia. Today, cross-chain communication (CCC) plays a fundamental role not only in cryptocurrency exchanges, but also in scalability efforts via sharding, extension of existing systems through sidechains, and bootstrapping of new blockchains. In this talk, we formulate the problem of cross-chain communication (CCC) and show that CCC is impossible without a trusted third party, contrary to common beliefs in the blockchain community. We then present XCLAIM, a framework for migrating assets across blockchains which works around this result by leveraging incentives. XCLAIM employs a dynamic and permissionless set of collateralized intermediaries, combined with cross-chain state verification and punishment. This construction ensures that users do not face financial damage from theft or collusion of intermediaries, while maintaining transparency and usability.

Watch video

November 11, 2020

Blockchains from Non-Idealized Hash Functions
Giorgos Panagiotakos, University of Athens

The formalization of concrete, non-idealized hash function properties sufficient to prove the security of Bitcoin and related protocols has been elusive, as all previous security analyses of blockchain protocols have been performed in the random oracle model. In this paper we identify three such properties, and then construct a blockchain protocol whose security can be reduced to them in the standard model assuming a common reference string (CRS).The three properties are: collision resistance, computational randomness extraction and iterated hardness. While the first two properties have been extensively studied, iterated hardness has been empirically stress-tested since the rise of Bitcoin; in fact, as we demonstrate in this paper, any attack against it (assuming the other two properties hold) results in an attack against Bitcoin.In addition, iterated hardness puts forth a new class of search problems which we term iterated search problems (ISP). ISPs enable the concise and modular specification of blockchain protocols, and may be of independent interest.

Get slides

November 4, 2020

Committing to Quantum Resistance: Defences for Bitcoin Quantum Adversaries
Dragos Ilie, Imperial College London

Quantum computers are expected to have a dramatic impact on numerous fields, due to their anticipated ability to solve classes of mathematical problems much more efficiently than their classical counterparts. This particularly applies to domains involving integer factorisation and discrete logarithms, such as public key cryptography. In this talk, we consider the threats a quantum-capable adversary could pose to Bitcoin, which currently uses the Elliptic Curve Digital Signature Algorithm (ECDSA) to sign transactions. We then propose a simple commit--delay--reveal protocol and a variant of it where the security parameter is configurable. These schemes allow users to securely move their funds from old (non-quantum-resistant) outputs to those adhering to a quantum-resistant digital signature scheme.

Watch video

October 21, 2020

Updatable Blockchains
Michele Ciampi, University of Edinburgh

Software updates for blockchain systems become a real challenge when they impact the underlying consensus mechanism. The activation of such changes might jeopardize the integrity of the blockchain by resulting in chain splits. Moreover, the software update process should be handed over to the community and this means that the blockchain should support updates without relying on a trusted party. In this paper, we introduce the notion of updatable blockchains and show how to construct blockchains that satisfy this definition. Informally, an updatable blockchain is a secure blockchain and in addition it allows to update its protocol preserving the history of the chain. In this work, we focus only on the processes that allow securely switching from one blockchain protocol to another assuming that the blockchain protocols are correct. That is, we do not aim at providing a mechanism that allows reaching consensus on what is the code of the new blockchain protocol. We just assume that such a mechanism exists (like the one proposed in NDSS 2019 by Zhang et. al), and show how to securely go from the old protocol to the new one. The contribution of this paper can be summarized as follows. We provide the first formal definition of updatable ledgers and propose the description of two compilers. These compilers take a blockchain and turn it into an updatable blockchain. The first compiler requires the structure of the current and the updated blockchain to be very similar (only the structure of the blocks can be different) but it allows for an update process more simple, efficient. The second compiler that we propose is very generic (i.e., makes few assumptions on the similarities between the structure of the current blockchain and the update blockchain). The drawback of this compiler is that it requires the new blockchain to be resilient against a specific adversarial behaviour and requires all the honest parties to be online during the update process. However, we show how to get rid of the latest requirement (the honest parties being online during the update) in the case of proof-of-work and proof-of-stake ledgers.

Get slides Watch video

October 14, 2020

Aggregate weighted signatures for Blockchain Bootstrapping
Pyrros Chaidos, University of Athens

Proof of Stake Blockchains operate by having participants demonstrate that they control a certain piece of stake, chosen by some selection mechanism. In contrast, proof of work blockchains require that participants provide a solution to some computational problem with restrictions indicated by the context. Such solutions can usually be verified in isolation and at low computational cost. In many current Proof of Stake implementations, verifying a claim of stake either requires a large context or a somewhat complex proof. These costs are exacerbated when a new user wishes to participate for the first time, as verifying the current state will often require replaying operations since the genesis. We introduce the primitive of weighted aggregate signatures and use it to offer a simple solution to speed up bootstrapping: we produce an aggregate signature for verifying a succinct checkpoint for each epoch. Our approach minimizes computational costs to small stakeholders and is compatible with recent advances such as key-evolving signatures and delegation.

Get slides Watch video

October 7, 2020

Digital Trust and Decentralization
Lefteris Kokoris-Kogias, IST Austria

In the last decades, computing managed to scale societies and bring everyone closer. We live in an era of efficiency and speed. Speed, however, is the enemy of trust. Trust needs friction and time to be built. In this talk, we are going to explore the evolution of trust and investigate the latest explosion of interest in digital and decentralized trust technologies. To this end, I am going to present both theoretical and practical advancements of my research in the last few years focusing on Byzantine Fault Tolerant systems and algorithms, answering questions such as: how can we get scalable decentralized systems able to support the current financial ecosystems, and how can we scavenge randomness from multiple semi-trustworthy players to run publicly-verifiable lotteries or to audit elections?

Get slides Watch video

September 30, 2020

ZeroJoin: Combining Zerocoin and CoinJoin
Amitabh Saxena, Ergo Platform

We present ZeroJoin, a practical privacy-enhancing protocol for blockchain transactions. ZeroJoin can be considered a combination of Zerocoin and CoinJoin. Like Zerocoin, our protocol uses zero-knowledge proofs and a pool of participants. However, unlike Zerocoin, our proofs are very efficient, and our pool size is not monotonically increasing. Thus, our protocol overcomes the two major drawbacks of Zerocoin. Our approach can also be considered a non-interactive variant of CoinJoin, where the interaction is replaced by a public transaction on the blockchain. We also present ErgoMix, a practical implementation of ZeroJoin on top of Ergo, a smart contract platform based on Sigma protocols. While ZeroJoin contains the key ideas, it leaves open the practical issue of handling fees. The key contribution of ErgoMix is a novel approach to handle fee in ZeroJoin.

Watch video

September 23, 2020

Privacy & Smart Contracts
Thomas Kerber, University of Edinburgh

Smart contracts have drastically lowered the barrier to entry for designing and deploying distributed systems. Largely they have done so at a great cost to privacy however, which smart contracts often ignore completely. In this talk we will see various approaches to re-introducing privacy in this setting, and what difficulties they encounter.

Get slides Watch video

September 16, 2020

Proving Work Over Onions: PoW applications in Tor
George Kadianakis, University of Athens, Tor Project

September 9, 2020

Efficient State Management in Distributed Ledgers
Dimitris Karakostas, University of Edinburgh

Distributed ledgers implement a storage layer, on top of which a shared state which is maintained by all participants in a decentralized manner. In UTxO-based ledgers, like Bitcoin, the shared state is the set of all unspent outputs (UTxOs), which serve as inputs to future transactions. However, decentralized systems lack centrally planned policies to enforce proper maintenance of the shared state, such as garbage collection, which would enhance performance and prevent Denial-of-Service (DoS) attacks. Instead, the system's design aims at incentivizing participants to act as intended. In this talk we investigate correct practices, such that the shared state in distributed ledgers is managed efficiently. We consider an abstract ledger model and investigate a set of transaction optimization techniques, including a coin selection algorithm which aims at minimizing the shared state. We also define state efficiency, which is the necessary property that a distributed ledger's fee scheme should possess in order to incentivize efficient state management, and propose an amended, efficient fee function for Bitcoin.

Get slides

September 2, 2020

Bypassing Non-Outsourceable Proof-of-Work Schemes Using Collateralized Smart Contracts
Alex Chepurnoy, Ergo Platform

Centralized pools and renting of mining power are considered as sources of possible censorship threats and even 51% attacks for decentralized cryptocurrencies. Non-outsourceable Proof-of-Work schemes have been proposed to tackle these issues. However, tenets in the folklore say that such schemes could potentially be bypassed by using escrow mechanisms. We consider how to bypass non-outsourceable Proof-of-Work schemes using collateralized smart contracts. Our approach allows for that if the underlying blockchain platform supports smart contracts in a sufficiently advanced language. In particular, the language should allow access to the PoW solution. At a high level, our approach requires the miner to lock collateral covering the reward amount and protected by a smart contract that acts as an escrow. The smart contract has logic that allows the pool to collect the collateral as soon as the miner collects any block reward. We propose two variants of the approach depending on when the collateral is bound to the block solution. Using this, we show how to bypass previously proposed non-outsourceable Proof-of-Work schemes (with the notable exception for strong non-outsourceable schemes) and show how to build mining pools for such schemes.

Watch video

July 22, 2020

A Study on Superlight Blockchain Clients under Velvet Fork
Andrianna Polydouri, University of Athens

In this presentation, we investigate how a blockchain can be upgraded to support superblock clients without a soft fork. We show that it is possible to implement the needed changes without modifying the consensus protocol and by requiring only a minority of miners to upgrade, a process termed a velvet fork in the literature. While previous work conjectured that Superblock and FlyClient clients can be safely deployed using velvet forks as-is, we show that previous constructions are insecure. We describe a novel class of attacks, called chain-sewing, which arise in the velvet fork setting: an adversary can cut-and-paste portions of various chains from independent forks, sewing them together to fool a superlight client into accepting a false claim. We show how previous velvet fork constructions can be attacked via chain-sewing. Next we put forth the first provably secure velvet superblock client construction which we show secure against adversaries that are bounded by 1/3 of the upgraded honest miner population.

Get slides Watch video

July 15, 2020

From Channels to Network: Off-chain Multi-hop Payments in Lightning
Orfeas Stefanos Thyfronitis Litos, University of Edinburgh

Building upon the ideas of pairwise Lightning channels, we explore Hashed TimeLocked Contracts (HTLCs), the technique that allows atomic payments along paths over channels. This technique expands the individual channels into an interconnected network of nodes that can freely exchange funds off-chain with any reachable node with minimal latency. Nodes can now transact even without having a direct channel, thus the need for a complete graph between nodes is relaxed -- just a connected graph with sufficient capacity is enough for any party to transact with any other. We will understand why parties along a payment path can trustlessly and securely send, receive, or facilitate the transfer of value. We will also discuss a number of tricks and optimizations in LN that turn the theoretical ideas of payment channels into a practical, incentivized, deployable and robust layer-2 payment network.

Get slides Watch video

July 8, 2020

A Taxonomy of Cryptocurrency Wallets
Kostis Karantias, IOHK

The primary function of a cryptocurrency is money transfer between individuals. The wallet is the software that facilitates such transfers. Wallets are nowadays ubiquitous in the cryptocurrency space and a cryptocurrency is usually supported by many wallets. Despite that, the functionality of wallets has never been formally defined. Additionally, the mechanisms employed by the many wallets in the wild remain hidden in their respective codebases. In this work we provide the first definition of a cryptocurrency wallet, which we model as a client to a server, or set of servers. We provide a distinction of wallets in various categories, based on whether they work for transparent or private cryptocurrencies, what trust assumptions they require, their performance and their communication overhead. For each type of wallet we provide a description of its client and server protocols. Additionally, we explore the superlight wallets and describe their difference to superlight clients that have appeared in recent literature. We demonstrate how new wallet protocols can be produced by combining concepts from existing protocols. Finally we evaluate the performance and security characteristics of all wallet protocols and compare them.

Get slides Watch video

July 1, 2020

The Smart Contract Development Ecosystem in Ethereum
Christos Nasikas, University of Athens

In this presentation, we will give an overview of how we can develop Ethereum Dapps using the tools availbable in the Ethereum ecosystem. We will discuss Truffle, a Javascript library and framework used to develop and test smart contracts in Solidity; Ganache and Ganache-cli, a local blockchain system which can be used to deploy smart contracts locally for developmpent purposes; Metamask, a browser-based wallet which is particularly user-friendly when used with DApps; and, finally, Remix, a web-based editor for your Solidity code which includes powerful syntax checking and debugging capabilities. During the talk, we will include live demonstrations and show you how these tools can be used together to develop complete and robust DApps.

June 24, 2020

Brick: Asynchronous Payment Channels
Zeta Avarikioti, ETH Zürich

Off-chain protocols (channels) are a promising solution to the scalability and privacy challenges of blockchain payments. Current proposals, however, require synchrony assumptions to preserve the safety of a channel, leaking to an adversary the exact amount of time needed to control the network for a successful attack. In this talk, we discuss BRICK, the first payment channel that remains secure under network asynchrony and concurrently provides correct incentives. The core idea is to incorporate the conflict resolution process within the channel by introducing a rational committee of external parties, called wardens. Hence, if a party wants to close a channel unilaterally, it can only get the committee's approval for the last valid state. BRICK provides sub-second latency because it does not employ heavy-weight consensus. Instead, BRICK uses consistent broadcast to announce updates and close the channel, a light-weight abstraction that is powerful enough to preserve safety and liveness to any rational parties.

Get slides

June 17, 2020

Implementing a practical superlight Bitcoin client
Stelios Daveas, University of Athens

During the last years, significant effort has been put into enabling blockchain interoperability. Towards this goal, a new generation of verifiers have emerged called superlight clients. We focus on Non-Interactive Proofs of Proof of Work (NIPoPoW) superblock protocol, and we discuss a gas-efficient implementation for the verification of NIPoPoWs in Solidity. In particular, we explore patterns and techniques that considerably reduce gas consumption, and may also have applications to other smart contracts. We introduce a pattern that we term "hash-and-resubmit" that eliminates persistent storage almost entirely, leading to significant increase of performance. Furthermore, we alleviate the burden of expensive on-chain operations, which we transfer off-chain, and we make use of an optimistic schema that replaces functionalities of linear complexity with constant operations. Lastly, we make a cryptoeconomic analysis, and set concrete values regarding the cost of usage of our client. Github: https://github.com/sdaveas/nipopow-verifier

Get slides Watch video

June 10, 2020

What is the Lightning Network?
Orfeas Stefanos Thyfronitis Litos, University of Edinburgh

The high latency and low throughput of Bitcoin constitute two fundamental barriers for its wider adoption. The Lightning Network, an overlay protocol that can be run on top of Bitcoin, provides the most comprehensive solution to those issues by enabling unlimited off-chain payments with minimal latency between parties that share a payment channel. In this talk we give an intuitive exposition of the Lightning protocol and its various capabilities. We describe the steps needed for setting up, using, and closing a 2-party Lightning channel, arguing that they are secure. We discuss the single disadvantage of Lightning compared to using the blockchain directly, namely that parties have to actively sync with the blockchain often to avoid losing funds. Finally, we highlight one of the most important -- and complex -- features of Lightning, multi-hop payments: leveraging well-understood cryptographic primitives and finely-tuned timeouts, a buyer can pay a seller even if they don't have an open channel between them.

Get slides

June 3, 2020

Introduction to NIPoPoWs
Dionysis Zindros, University of Athens

In this seminar, we will give an overview of Non-Interactive Proofs of Proof-of-Work and describe how we can leverage superblocks to build them. We will also discuss the interlinking data structure necessary to upgrade a blockchain for superblock support.