The Seven Grand Challenges

IC3 has many projects underway to address what we identify as seven “Grand Challenges” to widespread blockchain adoption. A number of examples are given below.

The seven Grand Challenges outlined above serve as a motivation and a project map for the following IC3 projects.

Projects

After the fall: Bitcoin true legacy may be blockchain technology
Eswar Prasad
Support Grand Challenges:
Sound Migration

Bitcoin and its peers have set off a technological revolution that will transform money, finance, and society. However, the future of cryptocurrencies as financial assets is far from certain - as can be seen from Bitcoin halving in value in six months since November 2021, the total value of all cryptocurrencies fell from $3 trillion to $1.3 trillion over this period. Rather, it is the underlying technology that enables cryptocurrency - the blockchain - that is likely to prove its true legacy. For further information, please my paper.

Blockchains as Infrasctructure and Semicommons
James Grimmelmann and A. Jason Windawi
Support Grand Challenges:
Safety and Compliance
Social Good

Blockchains are not self-executing machines. They are resources systems, designed by people, maintained by people, and governed by people. Their technical protocols help to solve some difficult problems in shared resource management, but behind those protocols there are always communities of people struggling with familiar challenges in governing their provision and use of common infrastructure. In this Essay, we describe blockchains as shared, distributed transactional ledgers using two frameworks from commons theory. According to Brett Frischmann the theory of infrastructure provides an external view, showing how blockchains provide useful, generic infrastructure for recording transactions, and why that infrastructure is most naturally made available on common, non-discriminatory terms. According to Henri Smith the theory of semicommons provides an internal view, showing how blockchains intricately combine private resources (such as physical hardware and on-chain assets) with common resources (such as the shared transactional ledger and the blockchain protocol itself). We then detail how blockchains struggle with many the governance challenges that these frameworks predict, requiring blockchain communities to engage in extensive off-chain governance work to coordinate their uses and achieve consensus. Blockchains function as infrastructure and semicommons not in spite of the human element, but because of it. For more information, please see our paper.

log*-Round Game-Theoretically-Fair Leader Election
Ilan Komargodski, Shinichiro Matsuo, Elaine Shi, and Ke Wu
Support Grand Challenges:
Sound Migration
Correctness by Design and Construction

It is well-known that in the presence of majority coalitions, strongly fair coin toss is impossible. A line of recent works have shown that by relaxing the fairness notion to game theoretic, we can overcome this classical lower bound. In particular, Chung et al. (CRYPTO, 2021) showed how to achieve approximately (game-theoretically) fair leader election in the presence of majority coalitions, with round complexity as small as O(log log n) rounds. In this paper, we revisit the round complexity of game-theoretically fair leader election. We construct O(log* n) rounds leader election protocols that achieve (1-O(1))-approximate fairness in the presence of (1-O(1))n-sized coalitions. Our protocols achieve the same round-fairness trade-offs as Chung et al. and have the advantage of being conceptually simpler. Finally, we also obtain game-theoretically fair protocols for committee election which might be of independent interest. For more information, please see our paper.

Safe Permissionless Consensus
Youer Pu, Lorenzo Alvisi, and Ittay Eyal
Support Grand Challenges:
Secure Scaling and Performance
Correctness by Design and Construction

According Nakamoto, consensus protocol works in a permissionless model, where nodes can join and leave without notice. However, it guarantees agreement only probabilistically. Is this weaker guarantee a necessary concession to the severe demands of supporting a permissionless model? This paper shows that, at least in a benign failure model, it is not. It presents Sandglass, the first permissionless consensus algorithm that guarantees deterministic agreement and termination with probability 1 under general omission failures. Like Nakamoto, Sandglass adopts a hybrid synchronous communication model, where, al the times, a majority of nodes (though their number is unknown) are correct and synchronously connected, and allows nodes to join and leave at any time. For further information, please see our paper.

Efficient and Adaptively Secure Asynchronous Binary Agreement via Binding Crusader Agreement
Ittai Abraham, Naama Ben-David, and Sravya Yandamuri
Support Grand Challenges:
Correctness by Design and Construction

We present a new abstraction based on crusader agreement called Binding Crusader Agreement (BCA) for solving binary consensus in the asynchronous setting against an adaptive adversary. BCA has the validity, agreement, and termination properties of crusader agreement in addition to a new property called binding. Binding states that before the first non-faulty party terminates, there is a value v{0,1} such that no non-faulty party can output the value v in any continuation of the execution. We believe that reasoning about binding explicitly, as a first order goal, greatly helps algorithm design, clarity, and analysis. Using our framework, we solve several versions of asynchronous binary agreement against an adaptive adversary in a simple and modular manner that either improves or matches the efficiency of state of the art solutions. We do this via new BCA protocols, given a strong common coin, and via new Graded BCA protocols given an e-good common coin. For crash failures, we reduce the expected time to terminate and we provide termination bounds that are linear in the goodness of the common coin. For Byzantine failures, we improve the expected time to terminate in the computational setting with threshold signatures, and match the state of the art in the information theoretic setting, both with a strong common coin and with an e-good common coin. For further information, please see our paper.

SHORTSTACK: Distributed, Fault-tolerant, Oblivious Data Access
Midhul Vuppalapati, Kushal Babel, Anurag Khandelwal, and Rachit Agarwal
Support Grand Challenges:
Correctness by Design and Construction
Safety and Compliance

Many applications that benefit from data offload to cloud services operate on private data. A now-long line of work has shown that, even when data is offloaded in an encrypted form, an adversary can learn sensitive information by analyzing data access patterns. Existing techniques for oblivious data access - that protect against access pattern attacks - require a centralized and stateful trusted proxy to orchestrate data accesses from applications to cloud services. We show that, in failure-prone deployments, such a centralized and stateful proxy results in violation of oblivious data access security guarantees and/or in system unavailability. We thus initiate the study of distributed, fault-tolerant, oblivious data access. We present SHORTSTACK, a distributed proxy architecture for oblivious data access in failure-prone deployments. SHORTSTACK achieves the classical obliviousness guarantee - access patterns observed by the adversary being independent of the input - even under a powerful passive persistent adversary that can force failure of arbitrary (bounded-sized) subset of proxy servers at arbitrary times. We also introduce a security model that enables studying oblivious data access with distributed, failure-prone servers. We provide a formal proof that SHORTSTACK enables oblivious data access under this model, and show empirically that SHORTSTACK performance scales near-linearly with number of distributed proxy servers. For further information, please see our paper.

How to Peel a Million: Validating and Expanding Bitcoin Clusters
George Kappos, Haaroon Yousaf, Rainer Stutz, Sofia Sollet, Bernhard Haslhofer, and Sarah Meiklejohn
Support Grand Challenges:
Correctness by Design and Construction
Safety and Compliance
Confidentiality

One of the defining features of Bitcoin and the thousands of cryptocurrencies that have been derived from it is a globally visible transaction ledger. While Bitcoin uses pseudonyms as a way to hide the identity of its participants, a long line of research has demonstrated that Bitcoin is not anonymous. This has been perhaps best exemplified by the development of clustering heuristic, which have in turn given rise to the ability to track the flow of bitcoins as they are sent from one entity to another. In this paper, we design a new heuristic that is designed to track a certain type of flow, called a peel chain, that represents many transactions performed by the same entity - in doing this, we implicitly cluster these transactions and their associated pseudonyms together. We then use this heuristic to both validate and expand the results of existing clustering heuristics. We also develop a machine learning-based validation method and, using a ground-truth dataset, evaluate all our approaches and compare them with the state of the art. Ultimately, our goal is to not only enable more powerful tracking techniques but also call attention to the limits of anonymity in these systems. For further information, please see our paper.

SoK: Kardware-supported Trusted Execution Environments
Moritz Schneider, Ramya Jayaram Masti, Shweta Shinde, Srdjan Capkun, and Ronald Perez
Support Grand Challenges:
Safety and Compliance

The growing complexity of modern computing platforms and the need for strong isolation protections among their software components has led to the increased adoption of Trusted Execution Environments (TEEs). While several commercial and academic TEE architectures have emerged in rceent times, they remain hard to compare and contrast. More generally, existing TEEs have not been subject to a holistic systematization to understand the available design alternatives for various aspects of TEE design and their corresponding pros-and-cons. Therefore, in this work, we analyze the design of existing TEEs and systematize the mechanisms that TEEs implement to achieve their security goals, namely, verifiable launch, run-time isolation, trusted IO and secure storage. More specifically, we analyze the typical architectural building blocks underlying TEE solutions, design alternatives for each of these components and the trade-offs that they entail. We focus on hardware-assisted TEEs and cover a wide range of TEE proposals from academia and the industry. Our analysis shows that although TEEs are diverse in terms of their goals, usage models and instruction set architectures, they all share many common building blocks in terms of their design. For further information, please see our paper.

Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guarantees
Banghua Zhu, Lun Wang, Qi Pang, Shuai Wang, Jiantao Jiao, Dawn Song, and Michael I. Jordan
Support Grand Challenges:
Sound Migration
Safety and Compliance

We propose Byzantine-robust federated learning protocols with nearly optimal statistical rates. In contrast to prior work, our proposed protocols improve the dimension dependence and achieve a tight statistical rate in terms of all the parameters for strongly convex losses. We benchmark against competing protocols and show the empirical superiority of the proposed protocols. Finally, we remark that our protocols with bucketing can be naturally combined with privacy-guaranteeing procedures to introduce security against a semi-honest server. The code for evaluation is provided in here. For further information, please see our paper.

It is not easy to relax: liveness in chained BFT protocols
Ittai Abraham, Natacha Crooks, Neil Giridharan, Heidi Howard, and Florian Suri-Payer
Support Grand Challenges:
Correctness by Design and Construction

Modern chained Byzantine Fault Tolerant (BFT) protocols leverage a combination of pipelining and leader rotation to maximize both efficiency and fairness. Unfortunately, this approach compromises livenss. We observe that even simple leader failures such as crashes can prevent the system from making progress, both theoretically, and practically. The root cause is simple - these protocols require a sequence of three or four consecutive honest leaders to commit operations. This paper makes two contributions - first, we show that, in the presence of arbitrary failures, consecutive honest leaders are necessary. When nodes fail by omission however, one can do better. As second contribution, we thus propose Siesta, a novel chained BFT protocol that successfully commit blocks that span multiple non-consecutive leaders. Siesta reduces the expected commit latency of Hotstuff by a factor of three under failures, and the worst-case latency by a factor of eight. For more information, please see our paper.

F3B: A Low-Latency Commit-and-Reveal Architecture to Mitigate Blockchain Front-Running
Haoqian Zhang, Louis-Henri Merino, Vero Estrada-Galinanes, and Bryan Ford
Support Grand Challenges:
Secure Scaling and Performance
Confidentiality

Front-running attacks, which benefit from advanced knowledge of pending transactions, have proliferated in the cryptocurrency space since the emergence of decentralized finance. Front-running causes devastating losses to honest participants - estimated at $280M each month - and endangers the fairness of the ecosystem. We present Flash Freezing Flash Boys (F3B), a blockchain architecture to address front-running attacks by relying on a commit-and-reveal scheme where the contents of transactions are encrypted and later revealed by a decentralized secret-management committee once the underlying consensus layer has committed the transaction. F3B mitigates front-running attacks because an adversary from benefiting from advance knowledge of pending transactions. We design F3B to be agnostic to the underlying consensus algorithm and compatible with legacy smart contracts by addressing front-running at the blockchain architecture level. Unlike existing commit-and-reveal approaches, F3B only requires writing data onto the underlying blockchain once, establishing a significant overhead reduction. An exploration of F3B shows that with a secret-management committee consisting of 8 and 128 members, F3B presents between 0.1 and 1.8 seconds of transaction-processing latency, respectively. For further information, please see our paper.

Ponyta: Foundations of Side-Contract-Resilient Fair Compliance
Hao Chung, Elisaweta Masserova, Elaine Shi, and Sri AravindaKrishnan Thyagarajan
Support Grand Challenges:
Correctness by Design and Construction
Safety and Compliance

Fair exchange is a fundamental primitive for blockchains, and is widely adopted in applications such as atomic swaps, payment channels, and DeFi. Most existing designs of blockchain-based fair exchange protocols consider only the users as strategic players, and assume honest miners. However, recent works revealed that the fairness of commonly deployed fair exchange protocols can be completely broken in the presence of user-miner collusion. In particular, a user can bribe the miners to help it cheat - a phenomenon also referred to as Miner Extractable Value (MEV). We provide the first formal treatment of side-contract-resilient fair exchange. We propose a new fair exchange protocol called Ponyta, and we prove that the protocol is incentive compatible in the presence of user-miner collusion. In particular, we show that Ponyta satisfies a coalition-resistant Nash equilibrium. Further, we show how to use Ponyta to realize a cross-chain coin swap application, and prove that our coin swap protocol also satisfies coalition-resistant Nash equilibrium. Our work helps to lay the theoretical groundwork for studying side-contract-resilient fair exchange. Finally, we present practical instantiations of Ponyta in Bitcoin and Ethereum with minimal overhead in terms of costs for the users involved in the fair exchange, thus showcasing instantiability of Ponyta with a wide range of cryptocurrencies. For further information, please see our paper.

Strategic Latency Reduction in Blockchain Peer-to-Peer Network
Weizhao Tang, Lucianna Kiffer, Giulia Fanti, and Ari Juels
Support Grand Challenges:
Secure Scaling and Performance

Most permissionless blockchain networks run on peer-to-peer (P2P) networks, which offer flexibility and decentralization at the expense of performance (e.g., network latency). Historically, this tradeoff has not been a bottleneck for most blockchains. However, an emerging host of blockchain-based applications (e.g., decentralized finance) are increasingly sensitive to latency; users who can reduce their network latency relative to other users can accrue (sometimes significant) financial gains. In this work, we initiate the study of strategic latency reduction in blockchain P2P networks. We first define two classes of latency that are of interest in blockchain applications. We then show empirically that a strategic agent who controls only their local peering decisions can manipulate both types of latency, achieving 60% of the global latency gains provided by the centralized, paid service bIoXroute, or, in targeted scenarios, comparable gains. Finally, we show that our results are not due to the poor design of existing P2P networks. Under a simple network model, we theoretically prove that an adversary can always manipulate the P2P network's latency to their advantage, provided the network experiences sufficient peer churn and transaction activity. For further information, please see our paper.

He-HTLC: Revisiting Incentives in HTLC
Sarisht Wadhwa, Jannis Stoeter, Fan Zhang, and Kartik Nayak
Support Grand Challenges:
Correctness by Design and Construction

Hashed Time-Locked Contracts (HTLCs) are a widely used primitive in blockchain systems. Unfortunately, HTLC is incentive-incompatible and is vulnerable to bribery attacks. MAD-HTLC (Oakland, 2021) is an elegant solution aiming to address the incentive incompatibility of HTLC. In this paper, we show that MAD-HTLC is also incentive-incompatible. The crux of the issue is that MAD-HTLC only considers passively rational miners. We argue that such a model fails to capture active rational behaviors. We demonstrate the importance of taking actively rational behaviors into consideration by showing three novel reverse-bribery attacks against MAD-HTLC that can be implemented using Trusted Execution Environments (TEEs) or sero-knowledge proofs (ZKPs). We further show that reverse bribery can be combined with original delaying attacks to render MAD-HTLC insecure regardless of the relationship between v col and v dep. Based on the learning from our attacks, we devise a new smart contract specification, He-HTLC, that meets the HTLC specification even in the presence of actively rational miners. For more information, please see our paper.

Exploring Security Practices of Smart Contract Developers
Tanusree Sharma, Zhixuan Zhou, Andrew Miller, and Yang Wang
Support Grand Challenges:
Safety and Compliance
Correctness by Design and Construction

Smart contracts are self-executing programs that run on blockchains (e.g., Ethereum). 680 million US dollars worth of digital assets controlled by smart contracts have been hacked or stolen due to various security vulnerabilities in 2021. Although security is a fundamental concern for smart contracts, it is unclear how smart contract developers approach security. To help fill this research gap, we conducted an exploratory qualitative study consisting of a semi-structured interview and a code review task with 29 smart contract developers with divers backgrounds, including 10 early stage (less than one year of experience) and 19 experienced (2-5 years of experience) smart contract developers. Our findings show a wide range of smart contract security perceptions and practices including various tools and resources they used. Our early-stage developer participants had a much lower success rate (15%) of identifying security vulnerabilities in the code review task than their experienced counterparts (55%). Our hierarchical task analysis of their code reviews implies that just by accessing standard documentation, reference implementations and security tools is not sufficient. Many developers checked those materials or used a security tool but still failed to identify the security issues. In addition, several participants pointed out shortcomings of current smart contract security tooling such as its usability. We discuss how future education and tools could better support developers in ensuring smart contract security. For further information, please see our paper.

NFTs for Art and Collectables: Primer and Outlook
Sarah Allen, Ari Juels, Mukti Khaire, Tyler Kell, and Siddhant Shrivastava
Support Grand Challenges:
Social Good
Sound Migration

Non-fungible tokens (NFTs) are digital objects that reside on blockchains and are tipically associated with unique digital media, such as images or music. A recent frenzy of popular interest has given rise seemingly overnight to a multi-billion NFT market. Individual NFTs can sell for millions or tens of millions of dollars, shile creators ranging from traditional artists such as Damien Hirst and Grimes to mainstream consumer-goods companies such as Coca-Cola and Nike are producing their own NFT collections. This primer's focus is on NFTs for art and collectables. Our aim is to give non-technical readers a basic familiarity with the technology behind NFTs, the history of their development, the current state of the NFT community and marketplace, and a notion of how NFTs might evolve in the future. We also offer a brief overview of the dynamics of traditional art markets and discuss the similarities, differences, and points of intersection in NFT markets. We hope that readers will come away from this primer with a basic understanding of how blockchains, smart contracts, and cryptographic keys work, an appreciation of some of the novel ways in which NFTs are empowering artists, a picture of the variety of dynamism of NFTs projects and communities, and possibly a hankering to own at least a fractional Bored Ape. For further information, please see our paper.

Baxos: Backing off for Robust and Efficient Consensus
Pasindu Tennage, Cristina Basescu, Eleftherios Kokoris-Kogias, Ewa Syta, Philipp Jovanovic, and Bryan Ford
Support Grand Challenges:
Sound Migration

Leader-based consensus algorithms are vulnerable to liveness and performance downgrade attacks. We explore the possibility of replacing leader election in Multi-Paxos with random exponential backoff (REB), a simpler approach that requires minimum modifications to the two phase Synod Paxos and achieves better resiliency under attacks. We propose Baxos, a new resilient consensus protocol that leverages a random exponential backoff scheme as a replacement for leader election in consensus algorithms. Our backoff scheme addresses the common challenges of random exponential backoff such as scalability and robustness to changing wide area latency. We extensively evaluate Baxos to illustrate its performance and robustness against two liveness and performance downgrade attackks using an implementation running on Amazon EC2 in a wide area network and a combination of a micro benchmark and YCSB-A workload on Redis. Our results show that Baxos offers more robustness to liveness and performance downgrade attacks than leader-based consensus protocols. Baxos outperforms Multi-Paxos and Raft up to 185% in throughput under liveness and performance downgrade attacks under worst case contention scenarios where each replica proposes requests concurrently while only incurring a 7% reduction on the maximum throughput in the synchronous attack-free scenario. For further information, please see our paper.

Proof of Availability & Retrieval in a Modular Blockchain Architecture
Shir Cohen, Guy Goren, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman
Support Grand Challenges:
Secure Scaling and Performance

This paper explores a modular design architecture aimed at helping blockchains (and other SMR implementation) to scale to a very large number of processes. This comes in contrast to existing monolithic architectures that interleave transaction dissemination, ordering, and execution in a single functionality. To achieve this we first split the monolith to multiple layers which can use existing distributed computing primitives. The exact specification of the data dissemination are formally defined by the Proof of Availability & Retrieval (PoA&R) abstraction. Solutions to the PoA&R problem contain two related sub-protocols - one that *pushes* information into the network and another that *pulls* this information. Regarding the latter, there is a dearth of research literature which is rectified in this paper. We present a family of pulling sub-protocols rigorously analyzing them. Extensive simulations support the theoretical claims of efficiency and robustness in case of a very large number of players. Finally, actual implementation and deployment on a small number of machines (roughly the size of several industrial systems) demonstrates the viability of the architeture paradigm. For more information, please see our paper.

Measuring Miner Decentralization in Proof-of-Work Blockchains
Soumya Basu, Sishan Long, and Emin Gun Sirer
Support Grand Challenges:
Secure Scaling and Performance

Proof-of-Work cryptocurrencies began with the promise of a more egalitarian future with a decentralized monetary system with no powerful entities in charge. While this vision is far from realized, these cryptocurrencies are still touted to be much more decentralized than traditional centralized systems. While it is well understood that cryptocurrencies are centralized, it is still unclear what the underlying causes are. This work aims to address this gap and examines some of the forces behind mining centralization. The internals of cryptocurrency mining is very opaque and difficult to study since it traditionally requires forming relationships with miners, who are typically reticent to share internal information about their competitive advantages. This work takes a different approach by combining large-scale statistical techniques with publicly available blockchain data in order to answer previously intractable questions. The crux of our analysis technique is based on the simple observation that some miners can utilize their hashpower more efficiently due to their position in the network. By teasing out that effect, we de-bias the mining power distribution to get a more accurate estimate. Using that de-biased mining power distribution, we can answer questions about the network position of miners in each cryptocurrency network. Finally, during the course of this study, we observed some unusual mining behaviors which we highlight. For more information, please see our paper.

Efficient Deterministic Execution of Smart Contracts
Enis Ceyhun Alp, Cristina Basescu, Pasindu Nivanthaka Tennage, Noemien Kocher, Gaylor Bosson, and Bryan Ford
Support Grand Challenges:
Safety and Compliance

One of the main properties of smart contracts is determinism. Execution of a smart contract has to produce the same result across all blockchain nodes so that they can reach consensus. The largest smart contract platform Ethereum enforces deterministic smart contracts at both language-and execution-level. Ethereum smart contracts are written in high-level domain-specific languages (e.g., Solidity, Vyper) and are executed on a specialized virtual machine with a restricted instruction set called the Ethereum Virtual Machine (EVM). Although EVM and its high-level languages address the determinism challenge, they also have shortcomings. First, EVM suffers from poor performance. Second, IEEE floating-point arithmetic is not strictly deterministic. Finally, since EVM languages are still immature, they lack standard libraries and development and debugging tools. This not only increases the bruden on the programmers and slow down the development process but also causes bugs in smart contracts that can potentially lead to security vulnerabilities. For further information, please see our paper.

Efficient MDP Analysis for Selfish-Mining in Blockchains
Roi Bar Zur, Ittay Eyal, and Aviv Tamar
Support Grand Challenges:
Correctness by Design and Construction
Safety and Compliance

A proof of work (PoW) blockchain protocol distributes rewards to its participants, called miners, according to their share of the total computational power. Sufficiently large miners can perform selfish mining - deviate from the protocol to gain more than their fair share. Such systems are thus secure if all miners are smaller than a threshold size so their best response following the protocol. To find the threshold, one has to identify the optimal strategy for miners of different sizes, i.e., solve a Markov Decision Process (MDP). However, because of the PoW difficulty adjustment mechanism, the miners' utility is a non-linear ratio function. We therefore call this an Average Reward Ratio (ARR) MDP. Sapishtein et al. were the first to solve ARR MDPs by solving a series of standard MDPs that converge to ARR MDP solution. In this work, we present a novel technique for solving an ARR MDP by solving a single standard MDP. The crux of our approach is to argument the MDP such that it terminates randomly, within an expected number of rounds. We call this Probabilistic Termination Optimization (PTO), and the technique applies to any MDP whose utility is a ratio function. We bound the approximation error of PTO - it is inversely proportional to the expected number of rounds before termination, a parameter that we control. Empirically, PTO's complexity is an order of magnitude lower than the state of the art. PTO can be easily applied to different blockchains. We use it to tighten the bound on the threshold for selfish mining in Ethereum. Link to our paper.

Hierarchical consensus: A horizontal scaling framework for blockchains
Alfonso de la Rocha, Eleftherios Kokoris-Kogias, Jorge M. Soares, and Marko Vukolic
Support Grand Challenges:
Secure Scaling and Performance
Correctness by Design and Construction

We present the Filecoin Hierarchical Consensus framework, which aims to overcome the throughput challenges of blockchain consensus by horizontally scaling the network. Unlike traditional sharding designs, based on partitioning the state of the network, our solution centers on the concept of subnets - which are organized hierarchically - and can be spawned on-demand to manage new state. Child subnets are firewalled from parent subnets, have their own specific policies, and run a different consensus algorithm, increasing the network capacity and enabling new applications. Moreover, they benefit from the security of parent subnets by periodically checkpointing state. In this paper, we introduce the overall system architecture, our detailed designs for cross-net transaction handling, and the open questions that we are still exploring. For further information, please see our paper.

Colordag: An Incentive-Compatible Blockchain
Ittai Abraham, Danny Dolev, Ittay Eyal, and Joseph Y. Halpern
Support Grand Challenges:
Safety and Compliance
Correctness by Design and Construction

Proof-of-work blockchain protocols rely on incentive compatibility. System participants, called miners, generate blocks that form a directed acyclic graph (blockdag). The protocols aim to compensate miners based on their mining power, that is, the fraction of computational resources they control. The protocol designates rewards, striving to make the prescribed protocol be the miners best response. The Nakamoto Bitcoin protocol achieves this for miners controlling up to almost 1/4 of the total mining power, and the Ethereum protocol does about the same. The state of the art in increasing this bound is Fruitchain, which works with a bound of 1/2. Fruitchain guarantees that miners can increase their revenue by only a negligible amount if they deviate. It is thus an e-Nash equilibrium, for a small e. However, the Fruitchain mechanism allows a rational miner to deviate without penalty. We show that a simple practical deviation guarantees a miner a small increase in expected utility without any risk. This deviation results in a violation of the protocol desiderata. We conclude that, in our context, e-Nash equilibrium is a rather fragile solution concept. We propose a more robust approach that we call e-sure Nash equilibrium, in which each miner behavior is almost always a strict best response, and present Colordag, the first blockchain protocol that is an e-sure Nash equilibrium for miners with less than 1/2 of the mining power. To achieve this, Colordag utilizes three techniques. First, it assigns blocks colors - rewards are assigned based on each color separately. By choosing sufficiently many colors, we make sensitivity to network latency negligible. Second, Colordag penalizes forking - intentional bifurcation of the blockdag. Third, Colordag prevents miners from retroactively changing rewards. All this results in an e-sure Nash equilibrium. Even when playing an extremely strong adversary with perfect knowledge of the future (specifically, when agents will generate blocks and when messages will arrive), correct behavior is a strict best response with high probability. Link to our paper.

Gradecast in Synchrony and Reliable Broadcast in Asynchrony with Optimal Resilience, Efficiency, and Unconditional Security
Ittai Abraham and Gilad Asharov
Support Grand Challenges:
Secure Scaling and Performance
Sound Migration

We revisit Gradecast (Feldman and Micali, STOC 1988) in Synchrony and Reliable Broadcast (Bracha, Information and Computation 1987) in Asynchrony. For both tasks, we provide new protocols that have three desirable properties - (1) \emph{optimal resilience}, tolerating tpaper.

Generalized Proof of Liabilities
Yan Ji and Ari Juels
Support Grand Challenges:
Confidentiality
Safety and Compliance
Social Good

Proof of Liabilities (PoL) allows a prover to prove his/her liabilities to a group of verifiers. This is a cryptographic primitive once used only for proving financial solvency but is also applicable to domains outside finance, including transparent and private donations, new algorithms for disapproval voting and publicly verifiable official reports such as COVID-19 daily cases. These applications share a common nature in incentives, it's not in the prover's interest to increase his/her total liabilities. We generalize PoL for these applications by attempting for the first time to standardize the goals it should achieve from security, privacy and efficiency perspectives. We also propose DAPOL+, a concrete PoL scheme extending the state-of-the-art DAPOL protocol but providing provable security and privacy, with benchmark results demonstrating its practicality. In addition, we explore techniques to provide additional features that might be desired in different applications of PoL and measure the asymptotic probability of failure. Link to our paper.

Copyright Vulnerabilities in NFTs
Yan Ji, Tyler Kell, and James Grimmelmann
Support Grand Challenges:
Safety and Compliance

NFTs for creative works depend on copyright law to give owners the set of rights they need but community expectations and NFT licenses are often not aligned with the actual legal rights owning an NFT conveys. We describe some of the issues, using well-known NFT projects as examples, and call for NFT developers to pay more attention to copyright licensing.

WeRLman: To Tackle Whale (Transactions), Go Deep (RL)
Roi Bar-Zur, Ameer Abu-Hanna, Ittay Eyal, and Aviv Tamar
Support Grand Challenges:
Secure Scaling and Performance
Safety and Compliance

The security of proof-of-work blockchain protocols critically rellies on incentives. Their operators, called miners, receive rewards for creating blocks containing user-generated transactions. Each block rewards its creator with newly minted tokens and with transactions fees paid by the users. The protocol stability is violated if any of the miners surpasses a threshold ratio of the computanional power-she is motivated to deviate with selfish mining and increase her rewards. Previous analyses of selfish mining strategies assumed constant rewards. But with statistics from operational systems, we show that there are occasional whales~--blocks with exceptional rewards. Modeling this behavior implies a state-space that grows exponentially with the parameters, becoming prohibitively large for existing analysis tools. We present the WeRLman framework to analyze such models. WeRLman uses deep Reinforcement Learning (RL), inspired by the state-of-the-art AlphaGo Zero algorithm. Directly extending AlphaGo Zero to a stochastic model leads to high sampling noise, which is detrimental to the learning process. Therefore, WeRLman employs novel variance reduction techniques by exploiting the recurrent nature of the system and prior knowledge of transition probabilities. Evaluating WeRLman against models we can accurately solve demonstrates it achieves unprecedented accuracy in deep RL for blockchain. We use WeRLman to analyze the incentives of a rational miner in various settings and upper-bound the security threshold of Bitcoin-like blockchains. The previoulsy known bound, with constant rewards, stands at ~0.25. We show that considering whale transactions reduces this threshold considerably. In particular, with Bitcoin historical fees and its future minting policy, its threshold for deviation will drop to ~0.2 in 10 years, ~0.17 in 20 years, ~0.12 in 30 years. With recent fees from the Ethereum smart-contract platform, the threshold drops to ~0.17. These are below the common sizes of large miners. For more information, please see our paper

Zef: Low-latency, Scalable, Private Payments
Mathieu Baudet, Alberto Sonnino, Mahimna Kelkar, and George Danezis
Support Grand Challenges:
Secure Scaling and Performance
Confidentiality

We introduce Zef, the first Byzantine-Fault Tolerant (BFT) protocol to nsupport payments in anonymous digital coins at arbitrary scale. Zef follows the communication and security model of FastPay - both protocols are asynchronous, low-latency, linearly-scalable, and powered by partially-trusted sharded authorities. In contrast with FastPay, user accounts in Zef are uniquely-identified and safely removable. Zef coins are bound to an account by a digital certificate and otherwise stored off-chain by their owners. To create and redeem coins, users interact with the protocol via privacy-preserving operations - Zef uses randomized commitments and NIZK proofs to hide coin values, and, created coins are made unlinkable using the blind and randomizable threshold anonymous credentials of Coconut. Besides the detailed specifications and our analysis of the protocol, we are making available an open-source implementation of Zef in Rust. Our extensive benchmarks on AWS confirm textbook linear scalability and demonstrate a confirmation time under one second at nominal capacity. Compared to existing anonymous payment systems based on a blockchain, this represents a latency speedup of three orders of magnitude, with no theoretical limit on throughput. For further information, please our paper.

Sliding Window Challenge Process for Congestion Detection
Ayelet Lotem, Sarah Azouvi, Patrick McCorry, and Aviv Zohar
Support Grand Challenges:
Secure Scaling and Performance
Safety and Compliance

Many prominent smart-contract applications such as payment channels, auctions, and voting systems often involve a mechanism in which some party must respond to a challenge or appeal some action within a fixed time limit. This pattern of challenge-response mechanisms poses great risks if during periods of high transaction volume, the network becomes congested. In this case fee market competition can prevent the inclusion of the repsonse in blocks, causing great harm. As a result, responders are allowed long periods to submit their response and overpay in fees. To overcome these problems and improve challenge-response protocols, we suggest a secure mechanism that detects congestion in blocks and adjusts the deadline of the response accordingly. The responder is thus guaranteed a deadline extension should congestion arise. We lay theoretical foundations for congestion signals in blockchains and then proceed to analyze and discuss possible attacks on the mechanism and evaluate its robustness. Our results show that in Ethereum, using short response deadlines as low as 3 hours, the protocol has >99% defense rate from attacks even by miners with up to 33% of the computational power. Using shorter deadlines such as one hour is also possible with a similar defense rate for attackers with up to 27% of the power. For further information, please see our paper.

Shades of Finality and Layer 2 Scaling
Bennet Yee, Dawn Song, Patrick McCorry, and Chris Buckland
Support Grand Challenges:
Secure Scaling and Performance

Blockchains combine a distributed append-only log with a virtual that defines how log entries are interpreted. By viewing transactions as state transformation functions for the virtual machine, we separate the naming of a state from the computation of its value and reaching consensus on that value. This distinction allows us to separate the notion of transaction order finality from state value finality. Further consideration of how blockchain gorvernance handles catastrophic common-mode failures such as zero day exploits lead us to the notion of checkpoint finality. Consensus on the transaction order determines the ground truth. Everything else - computing the value of a state or handling catastrophic failures such as bugs/zero-day based attacks - are just optimizations. For further information, please see our paper.

LedgerHedger: Gas Reservation for Smart-Contract Security
Itay Tsabary, Alex Manuskin, and Ittay Eyal
Support Grand Challenges:
Safety and Compliance
Correctness by Design and Construction

Smart-contract ledger platforms, like Ethereum, rate-limit their workload with incentives. Users issue orders, called transactions, with assigned fees, and system operators, called miners, confirm them and receive the fees. The combination of limited throughput and varying demand results in a volatile fee market, where underpaying transactions are not confirmed. However, the security of prominent smart contracts, securring billions of dollars, critically relies on their transactions being confirmed in specific, future time frames. Despite theoretical and practical active efforts, guaranteeing timely confirmation remained an open problem. We present LedgerHedger, a mechanism for assuring that a miner will confirm the transactions a user makes in a target time frame. As the name implies, LedgerHedger employs hedging - the user pays for the transaction in advance and the miner commits to confirm it even if the required fee rises. But unlike regulated markets, there are no external enforcers, and miners unilaterally choose which transactions to confirm. Due to the amounts at stake, relying on miner altruism does not suffice. Therefore, LedgerHedger uses a combination of collateral deposits to incentivize correct behavior. The contract requires the issuer to deposit her payment and the miner to deposit a collateral. During the target time frame, the miner is incentivized to confirm the transactions the issuer made if it exists, but is also capable of withdrawing the payment and the collateral if not. LedgerHedger gives rise to a game, where the parties can only take specific actions. For a wide range of parameter values theres is a subgame perfect equilibrium where both parties act as desired. We implement LedgerHedger and deploy it on an Ethereum test network, showing its efficacy and minor overhead. Link to our paper.

Bullshark: DAG BFT Protocols Made Practical
Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias
Support Grand Challenges:
Secure Scaling and Performance
Sound Migration

We present Bullshark, the first directed acyclic graph (DAG) based asynchronous Byzantine Atomic Broadcast protocol that is optimized for the common synchronous case. Like previous DAG-based BFT protocols, Bullshark requires no extra communication to achieve consensus on top of building the DAG. That is, parties can totally order the vertices of the DAG by interpreting their local view of the DAG edges. Unlike other asynchronous DAG-based protocols, Bullshark provides a practical low latency fast-path that exploits synchronous periods and deprecates the need for notoriously complex view-change mechanisms. Bullshark achieves this while maintaining all the desired properties of its predecessor DAG-Rider. Namely, it has optimal amortized communication complexity, it provides fairness and asynchronous liveness, and safety is guranteed even under a quantum adversary. In order to show the practicality and simplicity of our approach, we also introduce a standalone partially synchronous version of Bullshark which we evaluate against the state of the art. The implemented protocol is embarassingly simple (200 LOC on top of an existing DAG-based mempool implementation (Narwhal & Tusk). It is highly efficient, achieving for example, 125,000 transaction per second with a 2 seconds latency for a deployment of 50 parties. In the same setting the state of the art pays a steep 50% latency increase as it optimizes for asynchrony. For further information, please see our paper.

Broken Proofs of Solvency in Blockchain Custodial Wallets
Konstantinos Chalkias, Panagiotis Chatzigiannis, and Yan Ji
Support Grand Challenges:
Confidentiality
Safety and Compliance

Since the Mt. Gox Bitcoin exchange collapse in 2014, a number of custodial cryptocurrency wallets offer a form of financial solvency proofs to bolster the users confidence. We identified that despite recent academic works that highlight potential security and privacy vulnerabilities in popular auditability protocols, a number of high-profile exchanges implement these proofs incorrectly, thus defeating their initial purpose. In this paper we provide an overview of \textit{broken} liability proof systems used in production today and suggest fixes, in the hope of closing the gap between theory and practice. Surprisingly, many of these exploitable attacks are due to a) weak cryptographic operations, for instance SHA1 hashing or hash-output truncation to 8 bytes, b) lack of data binding, such as wrong Merkle tree inputs and misuse of public bulletin boards, and c) lack of user-ID uniqueness guarantees. For more information, please see our paper.

STROBE: Stake-based Threshold Raandom Beacons
Donald Beaver, Konstantinos Chalkias, Mahimna Kelkar, Lefteris Kokoris-Kogias, Kevin Lewi, Ladi de Naurois, Valeria Nicolaenko, Arnab Roy, and Alberto Sonnino
Support Grand Challenges:
Sound Migration
Correctness by Design and Construction

We revisit decentralized random beacons with a focus on practical distributed applications. Decentralized random beacons (Beaver and So, Eurocrypt 1993) provide the functionality for parties to generate an unpredictable sequence of bits in a way that cannot be biased, which is useful for any decentralized protocol requiring trusted randomness. Existing beacon contructions are highly inefficient in practical settings where protocol parties need to rejoin after crashes or disconnections, and more significantly where smart contracts may relys on arbitrary index points in high-volume streams. For this, we introduce a new notion of history-generating decentralized random beacons (HGDRBs). Roughly, the history-generation property of HGDRBs allows for previous beacon outputs to be efficiently generated knowing only the current value and the public key. At application layers, history-generation supports registering a sparser set of on-chain values if desired, so that apps like lotteries can utilize on-chain values without incurring high-frequency costs, enjoying all the benefits of DRBs implemented off-chain or with decoupled, special-purpose chains. Unlike rollups, HG is tailored specifically to recovering and verifying pseudorandom bit sequences and thus enjoys unique optimizations investigated in this work. We introduce STROBE - an efficient HGDRB construction which generalizes the original squaring-based RSA approach of Beaver and So. STROBE enjoys several useful properties that make it suited for practical applications that use beacons, (1) history-generating, it can regenerate and verify high-throughput beacon streams, supporting sparse (thus cost-effective) ledger entries, (2) concisely self-verifying, NIZK-free, with state and validation employing a single ring element, (3) eco-friendly, stake-based rather than work based, (4) unbounded, refresh-free, addressing limitations of Beaver and So, (5) delay-free, results are immediately available. For further information, please see our paper.

Practical Asynchronous Distributed Key Generation
Sourav Das, Thomas Yurek, Zhuolun Xiang, Andrew Miller, Lefteris Kokoris-Kogias, and Ling Ren
Support Grand Challenges:
Correctness by Design and Construction

Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted third party and is a building block to decentralized protocols such as randomness beacons, threshold signatures, and general multiparty computation. Until recently, DKG protocols have assumed the synchronous model and thus are vulnerable when their underlying network assumptions do not hold. The recent advancements in asynchronous DKG protocols are insufficient as they either have poor efficiency or limited functionality, resulting in a lack of concrete implementations. In this paper, we present a simple and concretely efficient asynchronous DKG (ADKG) protocol. In a network of n nodes, our ADKG protocol can tolerate up to tpaper.

SoK: Validating Bridges as a Scaling Solution for Blockchains
Patrick McCorry, Chris Buckland, Bennet Yee, and Dawn Song
Support Grand Challenges:
Secure Scaling and Performance
Sound Migration

Off-chain protocols are a promising solution to the cryptocurrency scalability dilemma. It focuses on moving transactions from a blockchain network like Ethereum to another off-chain system while ensuring users can transact with assets that reside on the underlying blockchain. Several startups have collectively raised over $100M to implement off-chain systems which rely on a validating bridge smart contract to self-enforce the safety of user funds and liveness of transaction execution. It promises to offer a Coinbase-like experience as users can transact on an off-chain system while still retaining the underlying blockchain security for all processed transactions. Unfortunately, the literature for validating bridges is highly disparate across message boards, chat rooms and for-profit ventures that fund its rapid development. This Systematization of Knowledge focuses on presenting the emerging field in an accessible manner and to bring forth the immediate research problems that must be solved before we van extend Ethereum's security to new (and experimental) off-chain systems. For further information, please see our paper.

SNARKBlock: Federated Anonymous Blocklisting from Hidden Common Input Aggregate Proofs
Michael Rosenberg, Mary Maller, and Ian Miers
Support Grand Challenges:
Correctness by Design and Construction

Moderation is an essential tool to fight harassment and prevent spam. The use of strong user identities makes moderation easier, but trends towards strong identity pose serious privacy issues, especially when identities are linked across social media platforms. Zero-knowledge blocklists allow cross-platform blocking of users but, counter-intuitively, do not link users identities inter- or intra-platform, or to the fact they were blocked. Unfortunately, existing approaches (Tsang et al. 2010), require that servers do work linear in the size of the blocklist for each verification of a non-membership proof. We design and implement SNARKBlock, a new protocol for zero-knowledge blocklisting with server-side verification that is logarithmic in the size of the blocklist. SNARKBlock is also the first approach to support ad-hoc, federated blocklisting - websites can mix and match their own blocklists and dynamically choose which identity providers they trust. Our core technical advance, of separate interest, is HICIAP, a zero-knowledge proof that aggregates n Groth16 proofs into one O(log n)-sized proof which also shows that the input proofs share a common hidden input. For further information, please see our paper.

Unity is Strength: A Formalization of Cross-Domain Maximal Extractable Value
Alexandre Obadia, Alejo Salles, Lakshman Sankar, Tarun Chitra, Vaibhav Chellani, and Phil Daian
Support Grand Challenges:
Correctness by Design and Construction

The multi-chain future is upon us. Modular architectures are coming to maturity across the ecosystem to scale bandwidth and throughput of cryptocurrency. One example of such is the Ethereum modular architecture, with its beacon chain, its execution chain, its Layer 2s, and soon its shards. These can all be thought as separate blockchains, heavily inter-connected with one another, and together forming an ecosystem. In this work, we call each of these interconnected blockchains *domains*, and study the manisfestation of Maximal Extractable Value (MEV, a generalization of *Miner Extractable Value*) across them. In other words, we investigate whether there exists extractable value that depends on the ordering of transactions in two or more domains jointly. We first recall the definitions of Extractable and Maximal Extractable Value, before introducing a definition of Cross-Domain Maximal Extractable Value. We find that Cross-Domain MEV can be used to measure the incentive for transaction sequencers in different domains to collude with one another, and study the scenarios in which there exists such an incentive. We end the work with a list of negative externalities that might arise from cross-domain MEV extraction and lay out several open questions. We note that the formalism in this work is a work in progress, and we hope that it can serve as the basis for formal analysis tools in the style of those presented in Clockwork Finance, as well as for discussion on how to mitigate the upcoming negative externalities of substantial cross-domain MEV. For further information, please see our paper.

Foundations of Transaction Fee Mechanism Design
Hao Chung and Elaine Shi
Support Grand Challenges:
Sound Migration
Correctness by Design and Construction

In blockchains such as Bitcoin and Ethereum, users compete in a transaction fee auction to get their transactions confirmed in the next block. A line of recent works set forth the desiderata for a *dream* transaction fee mechanism (TFM), and explored whether such a mechanism existed. A dream TFM should satisfy 1)user incentive compatibility (UIC), i.e., truthful bidding should be a user dominant strategy, 2) miner incentive compatibility (MIC), i.e., the miner dominant strategy is to faithfully implement the prescribed mechanism, and 3) miner-user side contract proofness (SCP), i.e., no coalition of the miner and one or more user(s) can increase their joint utility by deviating from the honest behavior. The weakest form of SCP is called 1-SCP, where we only aim to provide resilience against the collusion of the miner and single user. Sadly, despite the various attempts, to the best of knowledge, no existing mechanism can satisfy all three properties in all situations. Since the TFM departs from classical mechanism design in modeling and assumptions, to date, our understanding of the design space is relatively little. In this paper, we further unravel the mathematical structure of transaction fee mechanism design by proving the following results - Can we have a dream TFM? Rethinking the incentive compatibility notions. Do the new design elements make a difference? For more information, please see our paper.

Themis: Fast, Strong Order-Fairness in Byzantine Consensus
Mahimna Kelkar, Soubhik Deb, Sishan Long, Ari Juels, and Sreeram Kannan
Support Grand Challenges:
Correctness by Design and Construction

We introduce Themis, a scheme for introducing fair ordering of transactions into (permissioned) Byzantine consensus protocols with at most f faulty nodes among n>_4f+1. Themis is the first such scheme to achieve (optimistic) linear communication complexity. At the same time, it enforces the strongest notion of fair ordering proposed to date. Themis also achieves standard liveness, rather than the weaker notion of previous work. We show experimentally that Themis, can be integrated into state-of-the-art consensus protocols with minimal modification or performance overhead. Additionally, we introduce a suite of experiments of general interest for evaluating the practical strength of various notions of fair ordering and the resilience of fair-ordering protocols to adversarial manipulation. We use this suite of experiments to show that the notion of fair ordering enforced by Themis is significantly stronger in theory and for realistic workloads than those of competing systems. We believe Themis offers strong practical protection against many types of transactions-ordering attacks---such as front-running and back-running---that are currently impacting commonly used smart contract systems. For more information, please see our paper.

Platypus: A Central Bank Digital Currency with Unlinkable Transactions and Privacy Preserving Regulations
Karl Wüst, Kari Kostiainen, Noah Delius, and Srdjan Capkun
Support Grand Challenges:
Correctness by Design and Construction
Safety and Compliance

Due to the popularity of blockchain-based cryptocurrencies, the increasing digitalizations of payments, and the constantly reducing role of cash in society, central banks have shown an increased interest in deploying central bank digital currencies (CBDCs) that could serve as a replacement of cash. While most recent research on CBDCs focuses on blockchain technology, it is not clear that this choice of technology provides the optimal solution. In particular, the centralized trust model of a CBDC offers opportunities for different designs. In this paper, we depart from blockchain designs and instead build on ideas from traditional e-cash schemes. We propose a new style of building digital currencies that combines the transaction processing model of e-cash with the account model of managing funds that is commonly used in blockchain solutions. We argue that such a style of building digital currencies in especially well-suited to CBDCs. We also design the first such digital currency system, called Platypus, that provides strong privacy, massive scalability, and expressive but simple regulation, which are all critical features for a CBDC. Platypus achieves these properties by adapting techniques from previous anonymous blockchain cryptocurrencies like Zcash and prior research on accountable private payments and applying them to the e-cash context. For more information, please see our paper.

Be Aware of Yours Leaders
Shir Cohen, Rati Gelashvili, Lefteris Kokoris-Kogias, Zekun Li, Dahlia Malkhi, Alberto Sonnino, and Alexander Spiegelman
Support Grand Challenges:
Sound Migration
Correctness by Design and Construction

Advances in blockchains have influenced the State-Machine-Replication (SMR) world and many state-of-the-art blockchain-SMR solutions are based on two pillars - Chaining and Leader-rotation. A predetermined round-robin mechanism used for Leader-rotation, however, has an undesirable behavior, crashed parties become designated leaders infinitely often, slowing down overall system performance. In this paper, we provide a new Leader-Aware SMR framework that, among other desirable properties, formalizes a Leader-utilization requirement that bounds the number of rounds whose leaders are faulty in crash-only executions. We introduce Carousel, a novel, reputation-based Leader-rotation solution to achieve Leader-Aware SMR. The challenge in adaptive Leader-rotation is that it cannot rely on consensus to determine a leader, since consensus itself needs a leader. Carousel uses the available on-chain information to determine a leader locally and achieves Liveness despite this difficulty. A HotStuff implementation fitted with Carousel demonstrates drastic performance improvements - it increases throughput over 2x in faultless settings and provided a 20x throughput increase and 5x latency reduction in the presence of faults. For more information, please see our paper.

Basil: Breaking up BFT with ACID (transactions)
Florian Suri-Payer, Matthew Burke, Zheng Wang, Yunhao Zhang, Lorenzo Alvisi, and Natacha Crooks
Support Grand Challenges:
Sound Migration
Secure Scaling and Performance

This paper presents Basil, the first transactional, leaderless Byzantine Fault Tolerant key-value store. Basil leverages ACID transactions to scalably implement the abstraction of a trusted shared log in the presence of Byzantine actors. Unlike traditional BFT approaches, Basil executes non-conflicting operations in parallel and commits transactions in a single round-trip during fault-free executions. Basil improves throughput over traditional BFT systems by four to five times, and is only four times slower than TAPIR, a non-Byzantine replicated system. The novel recovery mechanism that Basil further minimizes the impact of failures - with 30% Byzantine clients, throughput drops by less than 25% in the worst-case. For further information, please see our paper.

Two-Round Maliciously Secure Computation with Super-Polynomial Simulation
Amit Agarwal, James Bartusek, Vipul Goyal, Dakshita Khurana, and Giulio Malavolta
Support Grand Challenges:
Safety and Compliance
Correctness by Design and Construction

We propose the first maliciously secure multi-party computation (MPC) protocol for general functionalities in two rounds, without any trusted setup. Since polynomial-time simulation is impossible in two rounds, we achieve the relaxed notion of superpolynomial-time simulation security [Pass, EUROCRYPT 2003]. Prior to our work, no such maliciously secure protocols were known even in the two-party setting for functionalities where both parties receive outputs. Our protocol is based on the sub-exponential security of standard assumptions plus a special type of non-interactive non-malleable commitment. At the heart of our approach is a two-round multi-party conditional disclosure of secrets (MCDS) protocol in the plain model from bilinear maps, which is constructed from techniques introduced in [Benhamouda and Lin, TCC 2020]. For further information, please see our paper.

Private Attacks in Longest Chain Proof-of-Stake Protocols with Single Secret Leader Elections
Sarah Azouvi and Daniele Cappelletti
Support Grand Challenges:
Safety and Compliance
Correctness by Design and Construction

Single Secret Leader Elections have recently been proposed as an improved leader election mechanism for proof-of-stake (PoS) blockchains. However, the security gain they provide has not been quantified. In this work, we present a comparison of PoS longest-chain protocols that are based on Single Secret Leader Elections (SSLE) - that elect exactly one leader per round - versus those based on Probabilistic Leader Elections (PLE) - where one leader is elected on expectation. Our analysis shows that when considering the private attack - the worst attack on longest-chain protocols - the security gained from using SSLE is substantial, the settlement time is decreased by roughly 25% for a 33% or 25% adversary. Furthermore, when considering grinding attacks, we find that the security threshold is increased by 10% (from 0.26 in the PLE case to 0.36 in the SSLE case) and the settlement time is decreased by roughly 70% for a 20% adversary in the SSLE case. For more information, please see our paper.

Clockwork Finance: Automated Analysis of Economic Security in Smart Contracts
Kushal Babel, Philip Daian, Mahimna Kelkar, and Ari Juels
Support Grand Challenges:
Correctness by Design and Construction

Clockwork Finance Framework is a general purpose, formal verification framework for mechanized reasoning about the economic security properties of composed decentralized-finance (DeFi) smart contracts. CFF features three key properties. It is contract complete, meaning that it can model any smart contract platform and all its contracts---Turing complete or otherwise. It does so with asymptotically optimal model size. It is also attack-exhaustive by construction, meaning that it can automatically and mechanically extract all possible economic attacks on cryptocurrency across modeled contracts. Thanks to these properties, CFF can support multiple goals-economic security analysis of contracts by developers, analysis of DeFi trading risks by users, and optimization of arbitrage opportunities by bots or miners. Because CFF offers composability, it can support these goals with reasoning over any desired set of potentially interacting smart contract models. We instantiate CFF as an executable model for Ethereum contracts that incorporates a state-of-the-art deductive verifier. Building on previous work, we introduce extractable value (EV), a new formal notion of economic security in composed DeFi contracts that is both a basis for CFF analyses and of general interest. We construct modular, human-readable, composable CFF models of four popular, deployed DeFi protocols in Ethereum - Uniswa, Uniswap V2, Sushiswap, and MakerDAO, representing a combined 17 billion USD in value as of August 2021. We used these models to show experimentally that CFF is practical and can drive useful, data-based insights from real world transaction activity. Without any explicitly programmed attack strategies, CFF uncovers on average an expected 56 million USD of EV per month in the recent years. For more information, please see our paper.

Aggregating and thresholdizing hash-based signatures using STARKs
Irakliy Khaburzaniya, Konstantinos Chalkias, Kevin Lewi, and Harjasleen Malvai
Support Grand Challenges:
Secure Scaling and Performance
Sound Migration
Confidentiality

This work presents an approach for compressing hash-based signatures using STARKs (Ben-Sasson et. al. 2018). We focus on constructing a hash-based t-of-n threshold signature scheme, as well as an aggregate signature scheme. In both constructions, an aggregator collects individual one-time hash-based signatures and outputs a STARK proof attesting that the signatures are valid and meet the required thresholds. This proof then serves the role of the aggregate or threshold signature. We demonstrate the concrete performance of such constructions, having implemented the algebraic intermediate representations (AIR) for them, along with an experimental evaluation over our implementation of the STARK protocol. We find that, even when we aggregate thousands of signatures, the final aggregated size ranges between 100KB and 200KB. This makes our schemes attractive when there exist at least 50 one-or-few-times hash-based signatures -- such as in the blockchain setting. We also observe that for STARK-based signature aggregation, the size of individual signatures is less important than the number of hash invocations and the complexity of the signature verification algorithm. This implies that simple hash-based signature variants (e.g. Lamport, HORST, BPQS) are well-suited for aggregation, as their large individual signatures serve only as witnesses to the ZKP circuit and are not needed for aggregate signature verification. Our constructions are directly applicable as scalable solutions for post-quantum secure blockchains which typically employ blocks of hundreds or thousands of signed transactions. Moreover, stateful hash-based one-or-few-times signatures are already used in some PQ-ready blockchains, as address reuse is typically discouraged for privacy reasons. For further information, please see our paper.

HEB: Hybrid-Expenditure Blockchains
Itay Tsabary, Alexander Spiegelman, and Ittay Eyal
Support Grand Challenges:
Safety and Compliance
Social Good

Proof of Work (PoW) is a Sybil-deterrence security mechanism. It introduces an external cost to a system by requiring computational effort to perform actions. However, since its inception, a central challenge was to tune this cost. Initial designs for deterring spam email and DoS attacks applied overhead equally to honest participants and attackers. Requiring too little effort did not deter attacks, whereas too much, encumbered honest participation. This might be the reason it was never widely adopted. Nakamoto overcame this trade-off in Bitcoin by distinguishing desired from malicious behavior and introducing internal rewards for the former. This solution gained popularity in securing cryptocurrencies and using the virtual internally-minted tokens for rewards. However, in existing blockchain protocols the internal rewards fund (almost) the same value of external expenses. Thus, as the token value soars, so does the PoW expenditure. Bitcoin PoW, for example, already expends as much electricity as Columbia or Switzerland. This amount of resource-guzzling is unsustainable and hinders even wider adoption of these systems. In this work we present Hybrid Expenditure Blockchain (HEB), a novel PoW mechanism. HEB is a generalization of the Nakamoto protocol that enables tuning the external expenditure by introducing a complementary internal-expenditure mechanism. Thus, for the first time, HEB decouples external expenditure from the reward value. We show a practical parameter choice by which HEB requires significantly less external consumption compared to the Nakamoto protocol, its resilience against rational attackers is similar, and it retains the decentralized and permissionless nature of the system. Taking the Bitcoin ecosystem as an example, HEB cuts the electricity consumption by half. For more information, please see our paper.

CedrusDB: Persistent Key-Value Store with Memory-Mapped Lazy-Trie
Maofin Yin, Hongbo Zhang, Robbert van Renesse, and Emin Gun Sirer
Support Grand Challenges:
Sound Migration
Correctness by Design and Construction

As a result of RAM becoming cheaper, there has been a trend in key-value store design towards maintaining a fast in-memory index (such as a hash table) while logging user operations to disk, allowing high performance under failure-free conditions while still being able to recover from failures. This design, however, comes at the cost of long recovery times or expensive checkpoint operations. This paper presents a new in-memory index that is also storage-friendly. A *lazy-trie* is a variant of the hash-trie data structure that achieves near-optimal height, has practical storage overhead, and can be maintained on-disk with standard write-ahead logging. We implemented CedrusDB, persistent key-value store based on a lazy-trie. The Lazy-trie is kept on disk while made available in memory using standard memory-mapping. The lazy-trie organization in virtual memory allows CedrusDB to better leverage concurrent processing than other on-disk index schemes (LSMs, B+ -trees). CedrusDB achieves comparable or superior performance to recent log-based in-memory key-value stores in mixed workloads while being able to recover quickly from failures. For further information, please see our paper.

Shard Scheduler: object placement and migration in sharded account-based blockchains
Michal Krol, Onur Ascigil, Sergi Rene, Alberto Sonnino, Mustafa Al-Bassam, and Etienne Riviere
Support Grand Challenges:
Correctness by Design and Construction
Sound Migration

We propose Shard Scheduler, a system for object placement and migration in account-based sharded blockchains. Our system calculates optimal placement and decides of object migrations across shards and supports complex multi-account transactions caused by smart contracts. Placement and migration decisions made by Shard Scheduler are fully deterministic, verifiable, and can be made part of the consensus protocol. Shard Scheduler reduces the number of costly cross-shard transactions, ensures balanced load distribution and maximizes the number of processed transactions for the blockchain as a whole. It leverages a novel incentive model motivating miners to maximize the global throughput of the entire blockchain rather than the throughput of a specific shard. Shard Scheduler reduces the number of costly cross-shard transactions by half in our simulations, ensuring equal load and increasing the throughput 3 fold when using 60 shards. We also implement and evaluate Shard Scheduler on Chainspace, more than doubling its throughput and reducing user-perceived latency by 70% when using 10 shards. For more information, please our paper.

Publicly Auditable MPC-as-a-Service with succinct verification and universal setup
Sanket Kanjalkar, Ye Zhang, Shreyas Gandlur, and Andrew Miller
Support Grand Challenges:
Confidentiality
Correctness by Design and Construction

In recent years, multiparty computation as a service (MPCaaS) has gained popularity as a way to build distributed privacy-preserving systems. We argue that for many such applications, we should also require that the MPC protocol is publicly auditable, meaning that anyone can check the given computation is carried out corectly -- even if the server nodes carrying out the computation are all corrupt. In a nutshell, the way to make an MPC protocol auditable is to combine an underlying MPC protocol with verifiable computing proof (in particular, a SNARK). Building a general-purpose MPCaaS from existing constructions would require us to perform a costly "trusted setup" every time we wish to run a new or modified application. To address this, we provide the first efficient construction for auditable MPC that has a one-time universal setup. Despite improving the trusted setup, we match the state-of-the-art in asymptotic performance--the server nodes incur a linear computation overhead and constant round communication overhead compared to the underlying MPC, and the audit size and verification are logarithmic in the application circuit size. We also provide an implementation and benchmarks that support our asymptotic analysis in example applications. Furthermore, compared with existing auditable MPC protocols, besides offering a universal setup our construction also has a 3x smaller proof, 3x faster verification time and comparable prover time. For further information, please see our paper.

Saber
Jian Liu, Peilun Li, Raymond Cheng, N. Asokan, and Dawn Song
Support Grand Challenges:
Correctness by Design and Construction
Secure Scaling and Performance

This project proposes the paradigm for parallel and asynchronous smart contract execution. Our paradigm distinguishes between consensus nodes and execution nodes. It allows different groups of execution nodes to execute transactions in parallel, and meanwhile, consensus nodes can continue ordering transactions and processing execution results in a non-blocking way. Due to our new dispute resolution strategy, it (empirically) only requires 10 execution nodes in each group. Moreover, it requires no coordination among execution nodes and can effectively prevent livelocks. For more information, please see our paper.

MPC-Friendly Symmetric Cryptography from Alternating Moduli: Candidates, Protocols, and Applications
Itai Dinur, Steven Goldfeder, Tzipora Halevi, Yuval Ishai, Mahimna Kelkar, Vivek Sharma, and Greg Zaverucha
Support Grand Challenges:
Correctness by Design and Construction
Sound Migration

We study new candidates for symmetric cryptographic primitives that leverage alternation between linear functions over Z2 and Z3 to support fast protocols for secure multi-party computation (MPC). This continues the study of weak pseudorandom functions this kind initiated by Boneh et. al. (TCC 2018) and Cheon et. al. (PKC 2021). We make the following contributions - (Candidates) We propose new designs of symmetric primitives based on alternating moduli. These include candidate one-way functions, pseudorandom generators, and weak pseudorandom functions. We propose concrete parameters based on cryptanalysis. (Protocols) We provide a unified approach for securely evaluating modulus-alternating primitives in different MPC models. For the original candidate of Boneh et. al., our protocols obtain at least 2x improvement in all performance measures. We report efficiency benchmarks of an optimized implementation. (Applications) We showcase the usefulness of our candidates for a variety of applications. This includes short *Picnic-style* signature schemes, as well as protocols for oblivious pseudorandom functions, hierarchical key derivation, and distributed key generation for function secret sharing. For further information, please see our paper.

Viaduct: An Extensible, Optimizing Compiler for Secure Distributed Programs
Cosku Acay, Rolph Recto, Joshua Gancher, Andrew C. Myers, and Elaine Shi
Support Grand Challenges:
Confidentiality
Safety and Compliance

Modern distributed systems involve interactions between principals with limited trust, so cryptographic mechanisms are needed to protect confidentiality and integrity. At the same time, most developers lack the training to securely employ cryptography. We present Viaduct, a compiler that transforms high-level programs into secure, efficient distributed realizations. the source language for Viaduct allows developers to declaratively specify security policies by annotating their programs with information flow labels. The compiler uses these labels to synthesize distributed programs that use cryptography efficiently while still defending the source-level security policy. The Viaduct approach is general, and can be easily extended with new security mechanisms. For further information, please see our paper.

Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback
Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang
Support Grand Challenges:
Authenticated Data Feeds
Sound Migration

Existing committee-based Byzantine state machine replication (SMR) protocols, typically deployed in production blockchains, face a clear trade-off - (1) they either achieve linear communication cost in the happy path, but sacrifice liveness during periods of asynchrony, or (2) they are robust (progress with probability one) but pay quadratic communication cost. We believe this trade-off is unwarranted since existing linear protocols still have asymptotic quadratic cost in the worst case. We design Ditto, a Byzantine SMR protocol that enjoys the best of both worlds, optimal communication on and off the happy path (linear and quadratic, respectively) and progress guarantee under asynchrony and DDoS attacks. We achieve this by replacing the view-synchronization of partially synchronous protocols with an asynchronous fallback mechanism at no extra asymptotic cost. Specifically, we start from HotStuff, a state-of-the-art linear protocol, and gradually build Ditto. As a separate contribution and an intermediate step, we design a 2-chain version of HotStuff, Jolteon, which leverages a quadratic view-change mechanism to reduce the latency of the standard 3-chain HotStuff. We implement and experimentally evaluate all our systems. Notably, Jolteon commit latency outperforms HotStuff by 200-300ms with varying system size. Additionally, Ditto adapts to the network and provides better performance than Jolteon under faulty conditions and better performance than VABA (a state-of-the-art asynchronous protocol) under faultless conditions. This proves our case that breaking the robustness-efficiency trade-off is the realm of practicality. For further information, please see our paper.

A Complete Characterization of Game-theoretically Fair, Multi-Party Coin Toss
Ke Wu, Gilad Asharov, and Elaine Shi
Support Grand Challenges:
Correctness by Design and Construction

Cleve celebrated lower bound (STOC'86) showed that a de facto strong fairness notion is impossible in 2-party coin toss, i.e., the corrupt party always has a strategy of biasing the outcome of the honest party by a noticeable amount. Nonetheless, Blum famous coin-tossing protocol (CRYPTO'81) achieves a strictly weaker *game-theoretic* notion of fairness - specifically, it is a 2-party coin toss protocol in which neither party can bias the outcome towards its own preference, and thus the honest protocol forms a Nash equilibrium in which neither party would want to deviate. Surprisingly, an n-party analog of Blum famous coin toss protocol was not studied till recently. The elegant work by Chung et al. was the first to explore the feasibility of game-theoretically fair n-party coin toss in the presence of corrupt majority. We may assume that each party has a publicly stated oreference for either the bit 0 or 1, and if the outcome agrees with the party preference, it obtains utility 1, else it obtains nothing. A natural game-theoretic formulation is to require that the honest protocol form a coalition-resistant Nash equilibrium, i.e., no coalition should have incentive to deviate from the honest behavior. Chung et al. phrased this game-theoretic notion as *cooperative-strategy-proofness* or *CSP-fairness* for short. Unfortunately, Chung et al. showed that under (n-1)-sized coalitions, it is impossible to design such a CSP-fair coin toss protocol, unless all parties except one prefer the same bit. In this paper, we show that the impossibility of Chung et al. is in fact not as broad as it may seem. When coalitions are majority but not n-1 in size, we can indeed get feasibility results in some meaningful parameter regimes. We give a complete characterization of the regime in which CSP-fair coin toss is possible, by providing a matching upper-and lower-bound. Our complete characterization theorem also shows that the mathematical structure of game-theoretic fairness is starkly different from the de facto strong fairness notion in the multi-party computation literature. For further information, please see our paper.

Reaching Consensus for Asynchronous Distributed Key Generation
Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, and Alin Tomescu
Support Grand Challenges:
Correctness by Design and Construction

We give a protocol for Asynchronous Distributed Key Generation (A-DKG) that is optimally resilient (can withstand f < n/3 faulty parties), has a constant expected number of rounds, has O~(n3) expected communication complexity, and assumes only the existence of a PKI. Prior to our work, the best A-DKG protocols required Omega(n) expected number of rounds, and Omega(n4) expected communication. Our A-DKG protocol relies on several building blocks that are of independent interest. We define and design a Proposal Election (PE) protocol that allows parties to retrospectively agree on a valid proposal after enough proposal have been sent from different parties. With constant probability the elected proposal was proposed by a nonfaulty party. In building our PE protocol, we design a Verifiable Gather protocol which allows parties to communicate which proposals they have and have not seen in a verifiable manner. The final building block to our A-DKG is a Validated Asynchronous Byzantine Agreement (VABA) protocol. We use our PE protocol to construct a VABA protocol that does not require leaders or an asynchronous DKG setup. Our VABA protocol can be used more generally when it is not possible to use threshold signatures. For further information, please see our paper.

Digital Currencies: Risk or Promise? The Case for Central Bank Digital Currencies
Eswar Prasad
Support Grand Challenges:
Safety and Compliance

New financial technologies-including those underpinning cryptocurrencies such as bitcoin-herald broader access to the financial system, quicker and more easily verifiable settlement of transactions and payments, and lower transaction costs. Domestic and crossborder payment systems are on the threshold of major transformation, with significant gains in speed and lowering of transaction costs on the horizon. The efficiency gains in normal times from having decentralized payment and settlement systems needs to be balanced against their potential technological vulnerabilities and the repercussions of loss of confidence during periods of financial stress. Multiple payment systems could improve the stability of the overall payments mechanism in the economy and reduce the possibility of counterparty risk associated with the payment hubs themselves. However, multiple systems without official backing could be severely tested in times of crisis of confidence and serve as channels for risk transmission. Decentralized electronic payment systems are also exposed to technological vulnerabilities that could entail significant economic as well as financial damage. For more information, please see my paper.

GoAT: File Geolocation via Anchor Timestamping
Deepak Maram, Iddo Bentov, Mahimna Kelkar, and Ari Juels
Support Grand Challenges:
Correctness by Design and Construction

Blockchain systems are rapidly gaining traction. Decentralized storage systems like Filecoin are a crucial component of this ecosystem that aim to provide robust file storage through a Proof of Replication (PoRep) or its variants. However, a PoRep actually offers limited robustness. Indeed if all the file replicas are stored on a single hard disk, a single catastrophic event is enough to lose the file. We introduce a new primitive, Proof of Geo-Retrievability or in short "GeoPoRet", that enables proving that a file is located within a strict geographic boundary. Using GeoPoRet, one can trivially construct a PoRep by proving that a file is in several distinct geographic regions. We define what it means for a GeoPoRet scheme to be complete and sound, in the process making important extensions to prior formalism. We propose GoAT, a practical GeoPoRet scheme to prove file geolocation. Unlike previous geolocation systems that rely on trusted-verifiers, GoAT bootstraps using public timestamping servers on the internet that serve as geolocation anchors, tolerating a local threshold of dishonest anchors. GoAT internally uses a communication-efficient Proof-of-Retrievability (PoRet) scheme in a novel way to achieve constant-size PoRet-component in its proofs. We validate GoAT's practicality by conducting an initial measurement study to find usable anchors and also perform a real-world experiment. The results show that a significant fraction of the internet can be used as GoAT anchors. Furthermore, GoAT achieves geolocation radii as little as 1000km. Link to our paper.

Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus
George Danezis, Eleftherios Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman
Support Grand Challenges:
Secure Scaling and Performance
Correctness by Design and Construction

We propose separating the task of reliable transaction dissemination from transaction ordering, to enable high-performance Byzantine fault-tolerant quorum-based consensus. We design and evaluate a mempool protocol, Narwhal, specializing in high-throughput reliable dissemination and storage of causal histories of transactions. Narwhal tolerates an asynchronous network and maintains high performance despite failures. Narwhal is designed to easily scale-out using multiple workers at each validator, and we demonstrate that there is no foreseeablelimit to the throughput we can achieve. Composing Narwhal with a partially synchronous consensus protocol (Narwhal-HotStuff) yields significantly better throughput even in the presence of faults or intermittent loss of liveness due to asynchrony. However, loss of liveness can result in higher latency. To achieve overall good performance when faults occur we design Tusk, a sero-message overhead asynchronous consensus protocol, to work with Narwhal. We demonstrate its high performance under a variety of configurations and faults. As a summary of results, on a WAN, Narwhal-HotStuff achieves over 130,000 tx/sec at less than 2-sec latency compared with 1,800 tx/sec at 1-sec latency for HotStuff. Additional workers increase throughput linearly to 600,000 tx/sec without any latency increase. Tusk achieves 160,000 tx/sec with about 3 seconds latency. Under faults, both protocols maintain high throughput, but Narwhal-HotStuff suffers from increased latency. Link to our paper.

Forsage: Anatomy of a Smart-Contract Pyramid Scheme
Tyler Kell, Haaroon Yousaf, Sarah Allen, Sarah Meiklejohn, and Ari Juels
Support Grand Challenges:
Confidentiality
Correctness by Design and Construction
Safety and Compliance

Pyramid schemes are investment scams in which top-level participants in a hierarchical network recruit and profit from an expanding base of defrauded newer participants. Pyramid schemes have existed for over a century, but there have been no in-depth studies of their dynamics and communities because of the opacity of participants' transactions. In this paper, we present an empirical study of Forsage, a pyramid scheme implemented as a smart contract and at its peak, one of the largest consumers of resources in Ethereum. As a smart contract, Forsage makes its (byte)code and all of its transactions visible on the blockchain. We take advantage of this unprecedented transparency to gain insight into the mechanics, impact on participants, and evolution of Forsage. We quantify the (multi-million-dollar) gains of top-level participants as well as the losses of the vast majority (around 88%) of users. We analyze Forsage code both manually and using a purpose-built transaction simulator to uncover the complex mechanics of the scheme. Through complementary study of promotional videos and social media, we show how Forsage promoters have leveraged the unique features of smart contracts to lure users with false claims of trustworthiness and profitability, and how Forsage activity is concentrated within a small number of national communities. Link to our paper.

Chainlink 2.0: Next Steps in the Evolution of Decentralization Oracle Networks
Lorenz Breidenbach, Christian Cachin, Benedict Chan, Alex Coventry, Steve Ellis, Ari Juels, Farinaz Koushanfar, Andrew Miller, Brendan Magauran, Daniel Moroz, Sergey Nazarov, Alexandru Topliceanu, Florian Tamer, and Fan Zhang
Support Grand Challenges:
Confidentiality
Safety and Compliance

In this whitepaper, we articulate a vision for the evolution of Chainlink beyond its initial conception in the original Chainlink whitepaper. We foresee an increasingly expansive role for oracle networks, one in which they complement and enhance existing and new blockchains by providing fast, reliable, and confidentiality-preserving universal connectivity and off-chain computation for smart contracts. The foundation of our plan is what we call Decentralized Oracle Networks, or DONs for short. A DON is a network maintained by a committee of Chainlink nodes. It supports any of an unlimited range of oracle functions chosen for deployment by the committee. A DON thus acts as a powerful abstraction layer, offering interfaces for smart contracts to extensive off-chain resources and highly efficient yet decentralized off-chain computing resources within the DON itself. Link to our paper.

Compositional Security for Reentrant Applications
Ethan Cecchetti, Siqiu Yao, Haobin Ni, and Andrew C. Myers
Support Grand Challenges:
Correctness by Design and Construction

The disastrous vulnerabilities in smart contracts sharply remind us of our ignorance - we do not know how to write code that is secure in composition with malicious code. Information flow control has long been proposed as a way to achieve compositional security, offering strong guarantees even then combining software from different trust domains. Unfortunately, this appealing story breaks down in the presence of reentrant attacks. We formalize a general definition of reentrancy and introduce a security condition that allows software modules like smart contracts to protect their key invariants while retaining the expressive power of safe forms of reentrancy. We present a security type system that provably enforces secure information flow. in conjunction with run-time mechanisms, it enforces secure reentrancy even in the presence of unknown code, and it helps locate and correct recent high-profile vulnerabilities. For more information, please see our paper.

Merkle Trees Optimized for Stateless Clients in Bitcoin
Bolton Bailey and Suryanarayana Sankagiri
Support Grand Challenges:
Authenticated Data Feeds

The ever-growing size of the Bitcoin UTXO state is a factor preventing nodes with limited storage capacity from validating transactions. Cryptographic accumulators, such as Merkle trees, offer a viable solution to the problem. Full nodes create a Merkle tree from the UTXO set, while stateless nodes merely store the root of the Merkle tree. When provided with a proof, stateless nodes can verify that a transaction inputs belong to the UTXO set. In this work, we present a systematic study of Merkle tree based accumulators, with a focus on factors that reduce the proof size. Based on the observation that UTXOs typically have a short lifetime, we propose that recent UTXOs be co-located in the tree. When proofs for different transactions are batched, such a design reduces the per-transaction proof size. We provide details of our implementation of this idea, describing certain optimizations that further reduce the proof size in practice. On Bitcoin data before August 2019, we show that our design achieves a 4.6x reduction in proof size vis-a-vis UTREEXO [Dryja 2019], which is a different Merkle-tree based system designed to support stateless nodes. Link to our paper.

Safer Illinois and RokWall: Privacy Preserving University Health Apps for COVID-19
Vikram Sharma Mailthody, James Wei, Nicholas Chen, Mohammad Behnia, Ruihao Yao, Qihao Wang, Vedant Agrawal, Churan He, Lijian Wang, Leihao Chen, Amit Agarwal, Edward Richter, Wen-Mei Hwu, Christopher W. Fletcher, Jinjun Xiong, Andrew Miller, and Sanjay Patel
Support Grand Challenges:
Confidentiality
Authenticated Data Feeds
Social Good

COVID-19 has fundamentally disrupted the way we live. Government bodies, universities, and companies worldwide are rapidly developing technologies to combat the COVID-19 pandemic and safely reopen society. Essential analytics tools such as contact tracing, super-spreader event detection, and exposure mapping require collecting and analyzing sensitive user information. The increasing use of such powerful data-driven applications necessitates a secure, privacy-preserving infrastructure for computation on personal data. In this paper, we analyze two such computing infrastructures under development at the University of Illinois at Urbana-Champaign to track and mitigate the spread of COVID-19. First, we present Safer Illinois, a system for decentralized health analytics supporting two applications currently deployed with widespread adoption - digital contact tracing and COVID-19 status cards. Second, we introduce the RokWall architecture for privacy-preserving centralized data analytics on sensitive user data. We discuss the architecture of these systems, desing choices, threat models considered, and the challenges we experienced in developing production-ready systems for sensitive data analytics. For further information, please see our paper.

Selfish Mining Attacks Exacerbated by Elastic Hash Supply
Yoko Shibuya, Go Yamamoto, Fuhito Kojima, Elaine Shi, Shin'ichiro Matsuo, and Aron Laszka
Support Grand Challenges:
Confidentiality
Correctness by Design and Construction

Several Attacks have been proposed against Proof-of-Work blockchains, which may increase the share of mining rewards of the attackers (e.g., selfish mining, block withholding). A further impact of such attacks, ehich has not been considered in prior work, is that decreasing the profitability of mining for honest nodes incentivizes them to stop mining or to leave the attacked chain for a more profitable one. The departure of honest nodes exacerbates the attack and may further decrease profitability and incentivize more honest nodes to leave. In this paper, we first present an empirical analysis showing that there is a statistically significant correlation between the profitability of mining and the total hash rate, confirming that miners indeed respond to changing profitability. Second, we present a theoretical analysis showing that selfish mining under such elastic hash supply leads either to the collapse of a chain, i.e., all honest nodes leaving, or to a stable equilibrium depending on the initial share of the attacker. For further information, please see our paper.

Reactive Key-Loss Protection in Blockchains
Sam Blackshear, Konstantinos Chalkias, Panagiotis Chatzigiannis, Riyaz Faizullabhoy, Irakliy Khaburzaniya, Eleftherios Kokoris-Kogias, Joshua Lind, David Wong, and Tim Zakian
Support Grand Challenges:
Safety and Compliance
Correctness by Design and Construction

We present a novel approach for blockchain asset owners to reclaim their funds in case of accidental private-key loss or transfer to a mistyped address. Our solution can be deployed upon failure or absence of proactively implemented backup mechanisms, such as secret sharing and cold storage. The main advantages against previous proposals is it does not require any prior action from users and works with both single-key and multi-sig accounts. We achieve this by a 3-phase Commit() -> Reveal() -> Claim() - or - Challenge() smart contract that enables accessing funds of addresses for which the spending key is not available. We provide an analysis of the threat and incentive models and formalize the concept of reactive KEy-Loss Protection (KELP). For more information, please see our paper.

SoK: Algorithmic Incentive Manipulation Attacks on Permissionless PoW Cryptocurrencies
Aljosha Judmayer, Nicholas Stifter, Alexei Zamyatin, Itay Tsabary, Ittay Eyal, Peter Gazi, Sarah Meiklejohn, and Edgar Weippl
Support Grand Challenges:
Safety and Compliance
Correctness by Design and Construction

A long standing question in the context of cryptocurrencies based on Nakamoto consensus is whether such constructions are incentive compatible, i.e., the intended properties of the system emerge from the appropriate utility model for participants. Bribing and other related attacks, such as front-running or Goldfinger attacks, aim to directly infleunce the incentives of actors within (or outside) of the targeted cryptocurrency system. The theoretical feasibility of bribing attacks on cryptocurrencies was first highlighted in 2016 by Bonneau, with various different techniques and approaches having since been proposed. Some of these attacks are designed to gain in-band profits, while others intend to break the mechanism design and render the cryptocurrency worthless. In this paper, we systematically expose the large but scattered body of research in this area which has accumulated over the years. We summarize these bribing attacks and similar techniques that leverage on programmatic execution and verification under the term algorthmic incentive manipulation (AIM) attacks, and show that the problem space is not yet fully explored. Based on our analysis we present several research gaps and opportunities that warrant further investigation. In particular, we highlight no- and near-fork attacks as a powerful, yet largely underestimated, AIM category that raises serious security concerns not only for smart contract platforms. For further information, pleasesee our paper.

Fraud and Data Availability Proofs: Detecting Invalid Blocks in Light Clients
Mustafa Al-Bassam, Alberto Sonnino, Vitalik Buterin, and Ismail Khoffi
Support Grand Challenges:
Confidentiality
Safety and Compliance

Light clients, also known as Simple Payment Verification (SPV) clients, are nodes which only download a small portion of the data in a blockchain, and use indirect means to verify that a given chain is valid. Instead of validating blocks, they assume that the chain favoured by the blockchain consensus algorithm only contains blocks, and that the majority of block producers are honest. By allowing such clients to receive fraud proofs generated by fully validating nodes that show that a block violates the protocol rules, and combining this with probabilistic sampling techniques to verify that all of the data in a block actually is available to be downloaded so that fraud can be detected, we can eliminate the honest-majority assumption for block validity, and instead make much weaker assumptions about a minimum number of honest nodes that rebroadcast data. Fraud and data availability proofs are key to enabling on-chain scaling of blockchains while maintaining a strong assurance that on-chain data is available and valid. We present, implement, and evaluate a fraud and data availability proof system. For more information, please see our paper.

Chainlink Off-chain Reporting Protocol
Lorenz Breidenbach, Christian Cachin, Alex Coventry, Ari Juels, and Andrew Miller
Support Grand Challenges:
Secure Scaling and Performance
Safety and Compliance

This document describes the Chainlink off-chain reporting protocol, a new, more scalable, version of the protocol driving Chainlink data feeds, realizing the vision for off-chain aggregation originally outlined in the Chainlink whitepaper [ENJ17]. There are n oracles (or nodes) that monitor an off-chain data stream, typically an API reporting a price feed like ETH-USD. Periodically, the oracles jointly run the protocols outlined in this document (off-chain) to sign a report containing observations from many oracles. Once a report is produced successfully, one or multiple transmiters sampled from the oracle set transmit the report to a smart contract C running on a *main* blockchain, which is considered to be Ethereum here, although no specific features of Ethereum are used by the off-chain reporting protocol. The contract validates the report, pays each oracle that contributed an observation to the report, and exposes the median of the reported values to consuming contracts on-chain. The first transmitter to successfully transmit the report to C is paid extra to make up for the Ethereum transaction fees she incurred during transmission of the report. Subsequent transmitters of the same report do not receive payment. For further information, please our paper.

All You Need is DAG
Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman
Support Grand Challenges:
Secure Scaling and Performance

We present DAG-Rider, the first asynchronous Byzantine Atomic Broadcast protocol that achieves optimal resilience, optimal amortized communication complexity, and optimal time complexity. DAG-Rider is post-quantum safe and ensures that all messages proposed by correct processes eventually get decided. We construct DAG-Rider in two layers - In the first layer, processes reliably broadcast their proposals and build a structured Directed Acyclic Graph (DAG) of the communication among them. In the second layer, processes locally observe their DAGs and totally order all proposals with no extra communication. For further information, please see our paper.

hbACSS: How to Robustly Share Many Secrets
Thomas Yurek, Licheng Luo, Jaiden Fairoze, Aniket Kate, and Andrew Miller
Support Grand Challenges:
Sound Migration
Correctness by Design and Construction

Despite significant recent progress toward making multi-party computation (MPC) practical, no existing MPC library offers complete robustness---meaning guaranteed output delivery, including in the offline phase---in a network that even has intermittent delays. Importantly, several theoretical MPC constructions already ensure robustness in this setting. We observe that the key reason for this gap between theory and practice is the absence of efficient verifiable/complete secret sharing (VSS/CSS) constructions - existing CSS protocols either require a) challenging broadcast channels in practice or b) introducing computation and communication overhead that is at least quadratic in the number of players. This work presents hbACSS, a suite of optimal-resilience asynchronous complete secret sharing protocols that are (quasi)linear in both computation and communication overhead. Towards developing hbACSS, we develop hbPolyCommit, an efficient polynomial commitment scheme that is (quasi)linear (in the polynomial degree) in terms of computation and communication overhead without requiring a trusted setup. We implement our hbACSS protocols, extensively analyze their practicality, and observe that our protocols scale well with an increasing number of parties. In particular, we use hbACSS to generate MPC input masks, a useful primitive which had previously only been calculated nonrobustly in practice. For further information, please see our paper.

Order-Fair Consensus in the Permissionless Setting
Mahimna Kelkar, Soubhik Deb, and Sreeram Kannan
Support Grand Challenges:
Secure Scaling and Performance
Sound Migration

Over the past five years, a significant line of research has investigated the blockchain consensus problem in the general permissionless setting, where protocol nodes can leave and join dynamically. The work of Garay et al. (Eurocrypt 2015) and Pass et al. (Eurocrypt 2017) showed the security properties of consistency and liveness for Nakamoto seminal proof-of-work protocol. However, consistency and liveness do not provide any guarantees on the relationship between the order in which transactions arrive into the network and the finalized order in the ledger, making protocols prone to transaction order-manipulation attacks. As a solution, a recent paper by Kelkar et al. (Crypto 2020) introduced a third useful property for consensus protocols, transaction-order-fairness. Their model was limited to the classical (permissioned) setting, where the set of protocol nodes is fixed a priori, and does not fit well for permissionless environments where order-manipulation attacks have been most prominent. In this work, we initiate the investigation of order-fairness in the permissionless setting and provide two protocols that realize it. Our protocols work in a synchronous network and use an underlying longest-chain blockchain. As an added contribution, we show that any fair ordering protocol achieves a powerful zero-block confirmation property, through which honest transactions can be securely confirmed even before they are included in any block. For further information, please see our paper.

Aggregatable Distributed Key Generation
Kobi Gurkan, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, and Alin Tomescu
Support Grand Challenges:
Secure Scaling and Performance

In this paper, we introduce a distributed key generation (DKG) protocol with aggregatable and publicly-verifiable transcripts. Compared with prior publicly-verifiable approaches, our DKG reduces the size of the final transcript and the time to verify it from O(n 2) to O(n log n), where n denotes the number of parties. As compared with prior non-publicly-verifiable approaches, our DKG leverages gossip rather than all-to-all communication to reduce verification and communication complexity. We also revisit existing DKGsecurity definitions, which are quite strong, and propose new and natural relaxations. As a result, we can prove the security of our aggregatable DKG as well as that of several existing DKGs, including the popular Pedersen variant. We show that, under these new definitions, these existing DKGs can be used to yield secure threshold variants of popular cryptosystems such as El-Gamal encryption and BLS signatures. We also prove that our DKG can be securely combined with a new efficient verifiable unpredictable function (VUF), whose security we prove in the random oracle model. Finally, we experimentally evaluate our DKG and show that the per party overheads scale linearly and are practical. For 64 parties, it takes 71 ms to share and 359 ms to verify the overall transcript, while for 8192 parties, it takes 8 s and 42.2 s respectively. For further information, please see our paper.

Game-Theoretic Fairness Meets Multi-Party Protocols: The Case of Leader Election
Kai-Min Chung, T-H. Hubert Chan, Ting Wen, and Elaine Shi
Support Grand Challenges:
Secure Scaling and Performance
Confidentiality

Suppose that n players want to elect a random leader and they communicate by posting messages to a common broadcast channel. This problem is called leader election, and it is fundamnetal to the distributed systems and cryptography literature. Recently, it has attracted renewed interests due to its promised applications in decentralized environments. In a game theoretically fair leader election protocol, roughly speaking, we want that even majority coalitions cannot increase its own chance of getting elected, nor hurt the chance of any honest individual. The folklore tournament-tree protocol, which completes in logarithmically many rounds, can easily be shown to satisfy game theoretic security. To the best of our knowledge, no sub-logarithmic round protocol was known in the setting that we consider. We show that by adopting an appropriate notion of approximate game-theoretic fairness, and under standard cryptographic assumption, we can achive (1-1/2 O(r))-fairness in r rounds for O(loglogn)<-r<-O(logn), where n denotes the number of players. In particular, this means that we can approximately match the fairness of the tournament tree protocol using as few as O(loglogn) rounds. We also prove a lower bound showing that logarithmically many rounds is necessary if we restrict ourselves to ''perfect" game-theretic fairness and protocols that are ''very similar in structure" to the tournament-tree protocol. Although leader election is a well-studied problem in other contexts in distributed computing, our work is the first exploration of the round complexity of {\it game-theoretically fair} leader election in the presence of a possibly majority coalition. As a by-product of our exploration, we suggest a new, approximate game-theoretic fairness notion, called ''approximate sequential fairness", whixh provides a more desirable solution concept than some previously studied approximate fairness notions. For further information, please see our paper.

AIRS: Automated Incentives for Reforestation Stewardship
Sishan Long, Ari Juels, Frederike Groschupp, Srdjan Capkun, Karl Wust, and Kari Kostiainen
Support Grand Challenges:
Social Good

The accelerating effect of global climate change is a major challenge for humanity. One critical component of any comprehensive solution is reforestation. As large and effective carbon sinks, forests are important to both conserve and expand. Not all types of forest, though, are equally effective at carbon sequestration. To create, monitor, and manage effective reforestation programs, it is essential that we be able to measure forest carbon accurately and with high geospatial precision. Our project will build infrastructure that, (1) Provides an accurate and trustworthy source of data on forest carbon and (2) Implements a system of automated monetary rewards for local inhabitants to conserve and/or increase forests that effectively reduce carbon emissions. By combining the two capabilities of reliable quantification and targeted rewards, we believe we can provide powerful support for climate change programs that aim to realize the value of forests as a part of the global economy. For instance, the REDD+ program, under development by parties to the United Nations Framework Convention on Climate Change, aims to incentivize developing countries to reduce emissions resulting from deforestation and forest degradation, thus conserving and enhancing forest carbon sticks. We will build a public performance-based payment system using two blockchain technologies. The first is an *oracle*, a trustworthy source of data for blockchain applications, it obtains and analyzes satellite data to relay trustworthy statistics on forest carbon. The second key component is a *smart contract*, a blockchain application that consumes data from the oracle and sends cryptocurrency rewards to forest stewards. Our system will also automatically identify the legitimate stakeholders/stewards of forested land by combining local land registry records, geolocation via smartphones, and fraud/anomaly detection.

Post-Quantum Multi-Party Computation
Amit Agarwal, James Bartusek, Vipul Goyal, Dakshita Khurana, and Giulio Malavolta
Support Grand Challenges:
Confidentiality

We initiate the study of multi-party computation for classical functionalities (in the plain model) with security against malicious polynomial-time quantum adversaries. We observe that existing techniques readily give a polynomial-round protocol, but our main result is a construction of constant-round post-quantum multi-party computation. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and polynomial quantum hardness of an LWE-based circular security assumption. Along the way, we develop the following cryptographic primitives that may be of independent interest - (1) A spooky encryption scheme of relations computable by quantum circuits, from the quantum hardness of an LWE-based circular security assumption. This yields the first quantum multi-key fully-homomorphic encryption scheme with classical keys. (2) Constant-round zero-knowledge secure against multiple parallel quantum verifiers from spooky encryption for relations computable by quantum circuits. To enable this, we develop a new straight-line non-black-box simulation technique against parallel verifiers that does not clone the adversary state. This forms the heart of our technical contribution and may also be relevant to the classical setting. (3) A constant-round post-quantum non-malleable commitment scheme, from the mildly super-polynomial quantum hardness of LWE. For more information, please see our paper.

Heterogeneous Paxos
Isaac Sheff, Xinwen Wang, Robbert van Renesse, and Andrew C. Myers
Support Grand Challenges:
Correctness by Design and Construction

In distributed systems, a group of learners achieve consensus when, by observing the output of some acceptors, they all arrive at the same value. Consensus is crucial for ordering transactions in failure-tolerant systems. Traditional consensus algorithms are homogeneous in three ways - (1) all learners are treated equally, (2) all acceptors are treated equally, and (3) all failures are treated equally. These assumptions, however, are unsuitable for cross-domain applications, including blockchains, where not all acceptors are equally trustworthy, and not all learners have the same assumptions and priorities. We present the first consensus algorithm to be heterogeneous in all three respects. Learners set their own mixed failure tolerances over differently trusted sets of acceptors. We express these assumptions in a novel Learner Graph, and demonstrate sufficient conditions for consensus. We present Heterogeneous Paxos, an extension of Byzantine Paxos. Heterogeneous Paxos achieves consensus for any viable Learner Graph in best-case three message sends, which is optimal. We present a proof-of-concept implementation, and demonstrate how tailoring for heterogeneous scenarios can save resources and latency. For further information, please see our paper.

Identity and Personhood in Digital Democracy: Evaluating Inclusion, Equality, Security, and Privacy in Pseudonym Parties and Other Proofs of Personhood
Bryan Ford
Support Grand Challenges:
Secure Scaling and Performance
Confidentiality
Correctness by Design and Construction

Digital identity seems like a prerequisite for digital democracy - how can we ensure ''one person, one vote" online without identifying voters? But digital identity solutions - ID checking, biometrics, self-sovereign identity, and trust networks - all present flaws, leaving users vulnerable to exclusion, identity loss or theft, and coercion. This flaws may be insurmountable because digital identity is a cart pulling the horse. We cannot achieve digital identity secure enouth for the weight of digital democracy, until we build it on a solid foundation of ''digital personhood". While identity is about distinguishing one person from another through attributes or affiliations, personhood is about giving all real people inalienable digital participation rights independent of identity, including protection against erosion of their democratic rights through identity loss, theft, coercion, or fakery. We explore and analyze alternative approaches to ''proof of personhood" that may provide this missing foundation. Pseudonym parties marry the transparency of period physical-world events with the power of digital tokens between events. These tokens represent limited-term but renewable claims usable for purposes such as online voting or liquid democracy, sampled juries or deliberative polls, abuse-resistant social communication, or minting universal basic income in a permissionless cryptocurrency. Enhancing pseudonym parties to provide participants a moment of enforced physical security and privacy can address coercion and vore-buying risks that plague E-voting systems today. We also examine other proposed approaches to proof of personhood, some of which offer conveniences such as all-online participation. These alternatives currently fall short of satisfying all the key digital personhood goals, unfortunately, but offer valuable insights into the challenges we face. For further information, please see my paper.

Economic Principles of PoPCoin, a Democratic Time-based Cryptocurrency
Haoqian Zhang, Cristina Basescu, and Bryan Ford
Support Grand Challenges:
Sound Migration
Social Good

While democracy is founded on the principle of equal opportunity to manage our lives and pursue our fortunes, the forms of money we have inherited from millenia of evolution has brought us to an unsustainable dead-end of exploding inequality. PoPCoin proposes to leverage the unique historical opportunities that digital cryptocurrencies present for a ''clean-slate" redesign of money, in particular around long-term equitability and sustainability, rather than solely stability, as our primary goals. we develop and analyze a monetary policy for PoPCoin that embodies these equitability goals in two basic rules that maybe summarized as supporting equal opportunity in ''space" and ''time" - the first by regularly distributing new money equally to all participants much like a basic income, the second by holding the aggregate value of these distributions to a constant and non-diminishing portion of total monyey supply through demurrage. Through preliminary economic analysis, we find that these rules in combination yield a unique form of money with numerous intriguing and promising properties, such as a quantifiable and provable upper bound on monetary inequality, a natural ''early adopter reward" that could incentivize rapid growth while tapering off as participation saturates, resistance to the risk of deflationary spirals, and migration incentives opposite those created by conventional basic incomes. For further information, please see our paper.

Scaling Membership of Byzantine Consensus
Burcu Canakci and Robbert van Renesse
Support Grand Challenges:
Secure Scaling and Performance

Scaling Byzantine Fault Tolerant (BFT) systems in terms of membership is important for secure applications with large participation such as blockchains. While traditional protocols have low latency, they cannot handle many processors. Conversely, blockchains often have hundreds to thousands of processors to increase robustness, but they typically have high latency or energy costs. We describe various sources of unscalability in BFT consensus protocols. To improve performance, many BFT protocols optimize the ''normal case", where there are no failures.This can be done in a modular fashion by wrapping existing BFT protocols with a building block that we call alliance. In normal case executions, alliance can scalably determine if the initial conditions of a BFT consensus protocol predetermine the outcome, obviating running the consensus protocol. We give examples of existing protocols that solve alliance. We show that a solution based on hypercubes and MACs has desirable scalability and performance in normal case executions, with only a modest overhead otherwise. We provide important optimizations. Finally, we evaluate our solution using the ns3 simulator and show that it scales up to thousands of processors and compare with prior work in various network topologies. For further information, please see our paper.

Privacy-Utility Tradeoffs in Routing Cryptocurrency over Payment Channel Network
Weizhao Tang, Weina Wang, Giulia Fanti, and Sewoong Oh
Support Grand Challenges:
Secure Scaling and Performance
Correctness by Design and Construction

Payment channel networks (PCNs) are viewed as one of the most promising scalability solutions for cryptocurrencies today. Roughly, PCNs are networks where each node represents a user and each directed, weighted edge represents funds escrowed on a blockchain, these funds can be transacted only between the endpoints of the edge. Users efficiently transmit funds from node A to B by relaying them over a path connecting A to B, as long as each edge in the path contains enough balance (escrowed funds) to support the transaction. Whenever a transaction succeeds, the edge weights are updated accordingly. In deployed PCNs, channel balances (i.e., edge weights) are not revealed to users for privacy reasons, users know only the initial weights at time 0. Hence, when routing transactions, users typically first guess a path, then check if it supports the transaction. This guess-and-check process dramatically reduces the success rate of transactions. At the other extreme, knowing full channel balances can give substantial improvements in transaction success rate at the expense of privacy. In this work, we ask whether a network can reveal noisy channel balances to trade off privacy for utility. We show fundamental limits on such a tradeoff, and propose noise mechanisms that achieve the fundamantal limit for a general class of graph topologies. Our results suggest that in practice, PCNs should operate either in the low-privacy or low-utility regime - it is not possible to get large gains in utility by giving up a little privacy, or large gains in privacy by sacrificing a little utility. For further information, please see our paper.

The Bitcoin Hunter: Detecting Bitcoin Traffic over Encrypted Channels
Fatemeh Rezaei, Shahrzad Naseri, Ittay Eyal, and Amir Houmansadr
Support Grand Challenges:
Secure Scaling and Performance
Confidentiality

Bitcoin and similar blockchain-based currencies are significant to consumers and industry because of their applications in electronic commerce and other trust-based distributed systems. Therefore, it is of paramount importance to the consumers and industry to maintain reliable access to their Bitcoin assets. In this paper, we investigate the resilience of Bitcoin to blocking by the powerful network entities such as ISPs and governments. By characterizing Bitcoin communication patterns, we design classifiers that can distinguish (and therefore block) Bitcoin traffic even if it is tunneled through an encrypted channel like Tor and even if Bitcoin traffic is being mixed with background traffic, e.g., due to browsing websites. We perform extensive experiments to demonstrate the reliability of our classifiers in identifying Bitcoin traffic even despite using obfuscation protocols like Tor Pluggable Transports. We conclude that standard obfuscation mechanisms are not enough to ensure blocking-resilient access to Bitcoin (and similar cryptocurrencies), therefore cryptocurrency operators should deploy tailored traffic obfuscation mechanisms. For further information, please see our paper.

Byzantine Ordered Consensus without Byzantine Oligarchy
Yunhao Zhang, Srinath Setty, Qi Chen, Lidong Zhou, and Lorenzo Alvisi
Support Grand Challenges:
Secure Scaling and Performance
Correctness by Design and Construction

The specific order of commands agreed upon when running state machine replication (SMR) is immaterial to fault-tolerance, all that is required is for all correct deterministic replicas to follow it. In the permissioned blockchains that rely on Byzantine fault tolerant (BFT) SMR, however, nodes have a stake in the specific sequence that ledger records, as well as in preventing other parties from manipulating the sequencing to their advantage. The traditional specification of SMR correctness, however, has no language to express these concerns. This paper introduces Byzantine ordered consensus, a new primitive that augments the correctness specification of BFT SMR to include specific guarantees on the total orders it produces, and a new architecture for BFT SMR that, by factoring out ordering from consensus, can enforce these guarantees and prevent Byzantine nodes from controlling ordering decisions (a Byzantine oligarchy). These contributions are instantiated in Pompe, a BFT SMR protocol that is guaranteed to oreder commands in a way that respects a natural extension of linearizability. For further information, please see our paper.

Optimal Oblivious Parallel RAM
Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi
Support Grand Challenges:
Sound Migration
Correctness by Design and Construction

An oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (STOC, 1987 and J. ACM, 1996), is a technique for hiding RAM access pattern. That is, for every input the distribution of the observed locations accessed by the machine is essentially independent of the machine secret inputs. Recent progress culminated in a work of Asharov et al. (EUROCRYPT, 2020), obtaining an ORAM with (amortized) logarithmic overhead in total work, which is known to be optimal. Oblivious Parallel RAM (OPRAM) is a natural extension of ORAM to the (more realistic) parallel setting where several processors make concurrent accesses to a shared memory. It is known that any OPRAM must incur logarithmic work overhead and for highly parallel RAMs a logarithmic depth blowup (in the balls and bins model). Despite the significant recent advances, there is still a large gap - all existing OPRAM schemes incur a poly-logarithmic overhead either in total work or in depth. Our main result closes the aforementioned gap and provides an essentially optimal OPRAM scheme. Specifically, assuming one-way functions, we show that any Parallel RAM with memory capacity~N can be obliviously simulated in space O(N), incurring only O(logN) blowup in (amortized) total work as well as in depth. Our transformation supports all PRAMs in the CRCW mode and the resulting simulation is in the CRCW mode as well. For further information, please see our paper.

Round-Efficient Byzantine Broadcast under Strongly Adaptive and Majority Corruptions
Jun Wan, Hanshen Xiao, Srinivas Devadas, and Elaine Shi
Support Grand Challenges:
Correctness by Design and Construction

The round complexity of Byzantine Broadcast (BB) has been a central question in distributed systems and cryptography. In the honest majority setting, expected constant round protocols have been known for decades even in the presence of a strongly adaptive adversary. In the corrupt majority setting, however, no protocol with sublinear round complexity is known, even when the adversary is allowed to {\it strongly adaptively} corrupt only 51\% of the players, and even under reasonable setup or cryptographic assumptions. Recall that a strongly adaptive adversary can examine what original message an honest player would have wanted to send in some round, adaptively corrupt the player in the same round and make it send a completely different message instead. In this paper, we are the first to construct a BB protocol with sublinear round complexity in the corrupt majority setting. Specifically, assuming the existence of time-lock puzzles with suitable hardness parameters and that the decisional linear assumption holds in suitable bilinear groups, we show how to achieve BB in (nn-f)2\polylog^ rounds with 1-\negl(^) probability, where n denotes the total number of players, f denotes the maximum number of corrupt players, and ^ is the security parameter. Our protocol completes in polylogarithmically many rounds even when 99% of the players can be corrupt. For further information, please see our paper.

Secure Massively Parallel Computation for Dishonest Majority
Rex Fernando, Ilan Komargodski, Yanyi Liu, and Elaine Shi
Support Grand Challenges:
Secure Scaling and Performance
Correctness by Design and Construction

This work concerns secure protocols in the massively parallel computation (MPC) model, which is one of the most widely-accepted models for capturing the challenges of writing protocols for the typres of parallel computing clusters which have become commonplace today (MapReduce, Hadoop, Spark, etc.). Recently, the work of Chan et al. (ITCS 2020) initiated this study, giving a way to compile any MPC protocol into a secure one in the common random string model, achieving the standard secure multi-party computation definition of security with up to 1/3 of the parties being corrupt. We are interested in achieving security for much more than 1/3 corruptions. To that end, we give two compilers for MPC protocols, which assume a simple public-key infrastructure, and achieve semi-honest security for all-but-the-one corruptions. Our first compiler assumes hardness of the learning-with-errors (LWE) problem, and works for any MPC protocol with *short* output --- that is, where the output of the protocol can fit into the storage space of one machine, fos instance protocols that output a trained machine learning model. Our second compiler works for any MPC protocol (even ones with a long output, such as sorting) but assumes, in addition to LWE, indistinguishability obfuscation and a circular secure variant of threshold FHE. Both protocols allow the attacker to choose corrupted parties based on the trusted setup, an improvement over Chan et al., whose protocol requires that the CRS is chosen independently of the attacker choices. Link to our work.

Streamlet: Textbook Blockchain Protocol
Benjamin Chan and Elaine Shi
Support Grand Challenges:
Secure Scaling and Performance

In the past five years or so, numerous blockchain projects have made tremendous progress towards improving permissioned consensus protocols (partly due to their promised applications in Proof-of-Stake cryptocurrencies). Although a significant leap has silently taken place in our understanding of consensus protocols, it is rather difficult to navigate this body of work, and knowledge of the new techniques appears scattered. In this paper, we describe an extremely simple and natural paradigm called Streamlet for constructing consensus protocols. Our protocols are inspired by the core techniques that have been uncovered in the past five years of work, but to the best of our knowledge our embodiment is simpler than ever before and we accomplish this by taking a *streamlining* idea to its full potential. We hope that our textbook constructions will help to decipher the past five years of work on consensus partly driven by the cryptocurrency community - in particular, how remarkably simple the new generation of consensus protocols has become in comparison with classical mainstream approaches such as PBFT and Paxos. For further information, please see our paper.

Early Evidence of Effectiveness of Digital Contact Tracing for SARS-CoV-2 in Switzerland
Marcel Salathe, Christian L. Althaus, Nanina Anderegg, Daniele Antonioli, Tala Ballouz, Edouard Bugnion, Srdjan Capkun, Dennis Jackson, Sang-Il Kim, James R. Larus, Nicola Low, Wouter Lueks, Dominik Menges, Cedric Moullet, Mathias Payer, Julien Riou, Theresa Stadler, Carmela Troncoso, Effy Vayena, and Viktor von Wyl
Support Grand Challenges:
Authenticated Data Feeds
Safety and Compliance
Correctness by Design and Construction
Social Good

In the wake of the pandemic of coronavirus disease 2019 (COVID-19), contact tracing has become a key element of strategies to control the spread of severe acute respiratory syndrome coronavirus 2019 (SARS-CoV-2). Given the rapid and intense spread of SARS-CoV-2, digital contact tracing has emerged as a potential complementary tool to support containment and mitigation efforts. Early modelling studies highlighted the potential of digital contact tracing to break transmission chains, and Google and Apple subsequently developed the Exposure Notification (EN) framework, making it available to the vast majority of smartphones. A growing number of governments have launched or announced EN-based contact tracing apps, but their effectiveness remains unknown. Here, we report early findings of the digital contact tracing app deployment in Switzerland. We demonstrate proof-of-principle that contact tracing reaches exposed contacts, who then test positive for SARS-CoV-2. This indicates that digital contact tracing is an effective complementary tool for controlling the spread of SARS-CoV-2. Continued technical improvement and international compatibility can further increase the efficacy, particularly also across country borders. For more information, please see our work.

SPARKs: Succinct Parallelizable Arguments of Knowledge
Naomi Ephraim, Cody Freitag, Ilan Komargodski, and Rafael Pass
Support Grand Challenges:
Sound Migration

We introduce the notion of a Succinct Parallelizable Argument of Knowledge (SPARK). This is an argument of knowledge with the following three efficiency properties for computing and proving a (non-deterministic, polynomial time) parallel RAM computation that can be computed in parallel time T with at most p processors - (1) The prover (parallel) running time is T + polylog (T*p). (In other words, the prover running time is essentially T for large computation times!) (2) The prover uses at most p*polylog(T*p) processors. (3) The communication and verifier complexity are both polylog(T*p). The combination of all three is desirable as it gives a way to leverage a moderate increase in parallelism in favot of near-optimal running time. We emphasize that even a factor two overhead in the prover parallel running time is not allowed. Our main contribution is a generic construction of SPARKs from any succinct argument of knowledge where the prover parallel running time is T*polylog (T*p) when using p processors, assuming collision-resistant hash functions. When suitably instantiating our construction, we achieve a four-round SPARK for any parallel RAM computation assuming only collision resistance. Additionally assuming the existence of a succinct non-interactive argument of knowledge (SNARK), we construct a non-interactive SPARK that also preserves the space complexity of the underlying computation up to polylog(T*p) factors. We also show the following applications of non-interactive SPARKs. First, they immediately imply delegation protocols with near optimal prover (parallel) running time. This, in turn, gives a way to construct verifiable delay functions (VDFs) from any sequential function. When the sequential function is also memory-hard, this yields the first construction of a memory-hard VDF. For further information, please see our paper.

SquiRL: Automatic Attack Analysis on Blockchain Incentive Mechanisms with Deep Reinforcement Learning
Charlie Hou, Mingxun Zhou, Yan Ji, Phil Daian, Florian Tramèr, Giulia Fanti, and Ari Juels
Support Grand Challenges:
Secure Scaling and Performance

Incentive mechanisms are central to the functionality of permissionless blockchains-they incentivize participants to run and secure the underlying consensus protocol. However, designing incentive-compatible incentive mechanisms is notoriously challenging. As a result, most public blockchains today use incentive mechanisms whose security properties are poorly understood and largely untested. In this work, we propose SquiRL, a framework for using deep reinforcement learning to analyze attacks on blockchain incentive mechanisms. We demonstrate SquiRL's power by first recovering known attacks, (1) the optimal selfish mining attack on Bitcoin [52], and (2) the Nash equilibrium in block withholding attacks [16]. We also use SquiRL to obtain several novel empirical results. First, we discover a counterintuitive flaw in the widely used rushing adversary model when applied to multi-agent Markov games with incomplete information. Second, we demonstrate that the optimal selfish mining strategy identified in [52] is actually not a Nash equilibrium in the multi-agent selfish mining setting. In fact, our results suggest (but do not prove) that when more than two competing agents engage in selfish mining, there is no profitable Nash equilibrium. This is consistent with the lack of observed selfish mining in the wild. Third, we find a novel attack on simplified version of the Ethereum finalization mechanism, Casper the Friendly Finality Gadget (FFG) that allows a strategic agent to amplify her rewards by up to 30%. Notably, [10] shows that honest voting is a Nash equilibrium in Casper FFG - our attack shows that when Casper FFG is composed with selfish mining, this is no longer the case. Altogether, our experiments demonstrate that SquiRL shows flexibility and promise as a framework for studying attack settings that have thus far eluded theoretical and empirical understanding. For more information, please see our paper.

Bucket Oblivious Sort: An Extremely Simple Oblivious Sort
Gilad Asharov, T-H. Hubert Chan, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi
Support Grand Challenges:
Correctness by Design and Construction

We propose a conceptually simple oblivious sort and oblivious random permutation algorithms called bucket oblivious sort and bucket oblivious random permutation. Bucket oblivious sort uses 6n log n time (measured by the number of memory accesses) and 2Z client storage with an error probability exponentially small in Z. The above runtime is only 3x slower than a non-oblivious merge sort baseline - for 230 elements, it is 5x faster than bitonic sort, the de facto oblivious sorting algorithm in practical implementations. Link to our work.

CanDID: Can-Do Decentralized Identity with Legacy Compatibility, Sybil-Resistance, and Accountability
Deepak Maram, Harjasleen Malvai, Fan Zhang, Nerla Jean-Louis, Alexander Frolov, Tyler Kell, Tyrone Lobban, Christine Moy, Ari Juels, and Andrew Miller
Support Grand Challenges:
Confidentiality
Safety and Compliance

CanDID is a platform for practical, user-friendly realization of decentralized identity, the idea of empowering end users with management of their own credentials. While decentralized identity promises to give users greater control over their private data, it burdens users with management of private keys, creating a significant risk of key loss. Existing and proposed approaches also presume the spontaneous availability of a credential-issuance ecosystem, creating a bootstrapping problem. They also omit essential functionality, like resistance to Sybil attacks and the ability to detect misbehaving or sanctioned users while preserving user privacy. CanDID addresses these challenges by issuing credentials in a user-friendly way that draws securely and privately on data from existing, unmodified web service providers. Such legacy compatibility similarly enables CanDID users to leverage their existing online accounts for recovery of lost keys. Using a decentralized commitee of nodes, CanDID provides strong confidentiality for user's keys, real-world identities, and data, yet prevents users from spawning multiple identites and allows identification (and blacklisting) of sanctioned users. To read more, see our paper.

Design choices for central bank digital currency: Policy and technical considerations
Sarah Allen, Srdjan Capkun, Ittay Eyal, Giulia Fanti, Bryan Ford, James Grimmelmann, Ari Juels, Kari Kostiainen, Sarah Meiklejohn, Andrew Miller, Eswar Prasad, Karl Wust, and Fan Zhang
Support Grand Challenges:
Secure Scaling and Performance
Confidentiality
Correctness by Design and Construction

Central banks around the world are exploring and in some cases even piloting Central Bank Digital Currencies (CBDCs). CBDCs promise to realize a broad range of new capabilities, including direct government disbursements to citizens, frictionless consumer payment and money-transfer systems, and a range of new financial instruments and monetary policy levers. CBDCs also give rise, however, to a host of challenging technical goals and design questions that are qualitatively and quantitatively different from those in existing government and consumer payment systems. A well-functioning CBDC will require an extremely resilient, secure, and performant new infrastructure, with the ability to onboard, authenticate, and support users on a massive scale. It will necessitate an architecture simple enough to support modular design and rigorous security analysis, but flexible enough to accommodate current and future functional requirements and use cases. A CBDC will also in some way need to address an innate tension between privacy and transparency, protecting user data from abuse while selectively permitting data mining for end-user services, policymakers, and law enforcement investigations and interventions. In this paper, we enumerate the fundamental technical design challenges facing CBDC designers, with a particular focus on performance, privacy, and security. Through a survey of relevant academic and industry research and deployed systems, we discuss the state of the art in technologies that can address the challenges involved in successful CBDC deployment. We also present a vision of the rich range of functionalities and use cases that a well-designed CBDC platform could ultimately offer users. For further information, please see our paper.

GRANPA: A Byzantine Finality Gadget
Alistair Stewart and Eleftherios Kokoris-Kogias
Support Grand Challenges:
Secure Scaling and Performance
Correctness by Design and Construction

Classic Byzantine fault-tolerant consensus protocols forfeit liveness in the face of asynchrony in order to preserve safety, whereas most deployed blockchain protocols forfeit safety in order to remain live. In this work, we achieve the best of both worlds by proposing a novel abstractions called the finality gadget. A finality gadget allows for transactions to always optimistically commit but informs the clients that these transactions might be unsafe. As a result, a blockchain can execute transactions optimistically and only commit them after they have been sufficiently and provably audited. In this work, we formally model the finality gadget abstraction, prove that it is impossible to solve it deterministically in full asynchrony (even though it is stronger than consensus) and provide a partially synchronous protocol which is currently securing a major blockchain. This way we show that the protocol designer can decouple safety and liveness in order to speed up the recovery from failures. We believe that there can be other types of finality gadgets that provide weaker safety (e.g., probabilistic) in order to gain more efficiency and this can depend on the probability that the network is not in synchrony. For more information, please see our paper.

MAD-HTCL - Because HTCL is Crazy-Cheap to Attack
Itay Tsabary, Matan Yechieli, Alex Manuskin, and Ittay Eyal
Support Grand Challenges:
Correctness by Design and Construction
Safety and Compliance

Smart contracts and transactions allow users to implement elaborate constructions on cryptocurrency blockchains like Bitcoin, Ethereum, and Libra. Many of these, including operational payment channels, use a building block called Hased Time-Locked Contract (HTLC). In this work, we distill from HTLC a specification (HTLCSpec), and present an implementation called Mutual-Assured-Distruction Hashed Time-Locked Contract (MAD-HTCL). MAD-HTLC employs a novel approach of utilizing the existing blockchain operators, called miners, as part of the design. If a user misbehaves, MAD-HTLC incentivizes the miners to confiscate all their funds. We prove that MAD-HTLC satisfies HTLC-Spec with game-theoretic analysis and instantiate it on Bitcoin's operational blockchain. Notably, current miner software makes only little effort to optimize revenue, since the advantage is relatively small. However, as the demand grows and other revenue components shrink, miners are motivated to fully optimize their fund intake. By patching the standard Bitcoin client, we demonstrate such an optimization is easy to implement, making the miners natural enforcers of MAD-HTLC. Finally, we show how vulerable HTLC is to bribery attacks. An attacker can incentivize miners to prefer their transactions by offering high transaction fees. We demonstrate this can be easily implemented by patching Bitcoin client, and use game theoretic tools to qualitatively tighten the known cost bound of such bribery attacks. For the technical paper, see here.

FalconDB: Blockchain-based Collaborative Database
Yanqing Peng, Min Du, Feifei Li, Raymond Cheng, and Dawn Song
Support Grand Challenges:
Correctness by Design and Construction
Confidentiality
Authenticated Data Feeds

Nowadays an emerging class of applications are based on collaboration over a shared database among different entities. However, the existing solutions on shared database may require trust on others, have high hardware demand that is unaffordablefor individual users, or have relatively low performance. In other words, there is a trilemma among security, compatibility and efficiency. In this paper, we present FalconDB, which enables different parties with limited hardware resources to efficiently and securely collaborate on a database. FalconDB adopts database servers with verification interfaces accessible to clients and stores the digests for query/update authentications on a blockchain. Using blockchain as a consensus platform and a distributed ledger, FalconDB is able to work without any trust on each other. Meanwhile, FalconDB requires only minimal storage cost on each client, and provides anywhere-available, real-time and concurrent access to the database. As a result, FalconDB overcomes the disadvantages of previous solutions, and enables individual users to paricipate in the collaboration with high efficiency, low storage cost and blockchain-level security guarantees. For more information, please see our paper.

Reputable List Curation from Decentralized Voting
Support Grand Challenges:
Secure Scaling and Performance
Safety and Compliance

Token-curated registries (TCRs) are a mechanism by which a set of users are able to jointly curate a reputable list about real-world information. Entries in the registry may have any form, so this primitive has been protposed for use -- and deployed -- in a variety of decentralized applications, ranging from the simple joint creation of lists to helping to prevent the spread of misinformation online. Despite this interest, the security of this primitive is not well understood, and indeed existing constructions do not achieve strong or provable notions of security or privacy. In this paper, we provide a formal cryptographic treatment of TCRs as well as a construction that provably hides the votes cast by individual curators. Along the way, we provide a model and proof of security for an underlying voting scheme, which may be of independent interest. We also demonstrate, via an implementation and evaluation, that our construction is practical enough to be deployed even on a constrained decentralized platform like Ethereum. For more information, please see our paper.

Blockchain with Varying Number of Players
T-H. Hubert Chan, Naomi Ephraim, Antonio Marcedone, Andrew Morgan, Rafael Pass, and Elaine Shi
Support Grand Challenges:
Secure Scaling and Performance
Sound Migration

Expected Constant Round Byzantine Broadcast under Dishonest Majority
Jun Wan, Hanshen Xiao, Elaine Shi, and Srinivas Devadas
Support Grand Challenges:
Secure Scaling and Performance
Sound Migration

Byzantine Broadcast (BB) is a central question in distributed systems, and an important challenge is to understand its round complexity. Under the honest majority setting, it is long known that there exist randomized protocols that can achieve BB in expected constant rounds, regardless of the number of nodes n. However, whether we can match the expected constant round complexity in the corrupt majority setting --- or more precisely, when f=>n/2+w(1) --- remains unknown, where f denotes the number of corrupt nodes. In this paper, we are the first to resolve this long-standing question. We show how to achieve BB in expected O((n/(n-f))2 rounds. Our results hold under both a static adversary and weakly adaptive adversary who cannot perform *after-the-fact removal* of messages already sent by a node before it becomes corrupt. For more information, please see our paper.

HoneyBadgerMPC
Donghang Lu, Thomas Yurek, Samarth Kulshreshtha, Rahul Govind, Rahul Mahadev, Aniket Kate, and Andrew Miller
Support Grand Challenges:
Secure Scaling and Performance
Confidentiality
Safety and Compliance

Multi-Party Computation (MPC) is a flexible paradigm for computing on confidential data. HoneyBadgerMPC is an asynchronous MPC protocol and implementation that scales to large networks and provides blockchain-grade fault tolerance and availability guarantees. For more info, please see HoneyBadgerMPC.

Multi-Perty Timed Commitments
Yael Doweck and Ittay Eyal
Support Grand Challenges:
Secure Scaling and Performance
Sound Migration

The problem of obtaining secret commitments from multiple parties and revealing them after a certain time is useful for sealed-bid auctions, games, and other applications. Existing solutions, dating back to Rivest, Shamir and Wagner, either do not scale or rely on synchrony for the commitment phase and trust of t/n parties. We formalize the problem of implementing such commitments with a probabilistic delay and without the aforementioned assumptions as Multi-Party Timed Commitments (MPTC) and present a solution -- the Time-Capsule protocol. Like previous approaches, Tmie Capsule forms a puzzle whose solution reveals the committed values. But unlike previous solutions, no party has an advantage in solving the puzzle, and individual commitments cannot be revealed before the entire set is committed. A particular application of MPTC realizes an advancement in the study of decentralized systems. The state of the art in decentralized systems is manifested in blockchain systems that utilize Proof-of-Work to achieve censorship resistance. However, they are still vulnerable to frontrunning, an issue that is plaguing operational systems. By adapting Time Capsule, we allow it to be used for Proof-of-Work, preventing frontrunning by system operators and tunning the puzzle difficulty using the blockchain mechanism. For further information, please see our paper.

SCIF: Smart Contract Information Flow
Ethan Cecchetti, Siqiu Yao, Haobin Ni, and Andrew C. Myers
Support Grand Challenges:
Safety and Compliance
Sound Migration

SCIF is a more secure programming language for building smart contracts. It automatically detects use of untrusted information, including vulnerabilities arising from reentrancy nd confused deputies. It provides a strong and decentralized security guarantee, supporting the secure construction of complex, interacting contracts. Link to our paper.

One Round Threshold ECDSA with Identifiable Abort
Rosario Gennaro and Steven Goldfeder
Support Grand Challenges:
Correctness by Design and Construction

Threshold ECDSA signatures have received much attention in recent years due to the widespread use of ECDSA in cryptocurrencies. While various protocols now exist that admit efficient distributed key generation and signing, these protocols have two main drawbacks. Firstly, if a player misbehaves, the protocol will abort, but all current protocols give no way to detect which player is responsible for the abort. In distributed settings, this can be catastrophic as any player can cause the protocol to fail without any consequence. General techniques to realize dishonest-majority MPC with identifiable abort add a prohibitive overhead, but we show how to build a tailored protocol for threshold ECDSA with minimal overhead. Secondly, current threshold ECDSA protocols (that do not rely on generic MPC) have numerous rounds of interaction. We present a highly efficient protocol with a non-interactive online phase allowing for players to asynchronously participate in the protocol without the need to be online simultaneously. We benchmark our protocols and find that our protocol simultaneously reduces the rounds and computations of current protocols, while adding significant functionality--identifiable abort and noninteractivity. For more information, please see our paper.

Confidence Clustering
Sarah Meiklejohn
Support Grand Challenges:
Correctness by Design and Construction

This project is focused on developing a set of metrics that can increase confidence in the results of cryptocurrency clustering heuristics. These new techniques, which will output a probability of two addresses belonging to the same cluster rather than a binary yes/no answer, will enable more informed decisions and strengthen the use of exisiting heuristics by providing more evidence that their results are correct.

Sublinear-Round Byzantine Agreement under Corrupt Majority
T-H. Hubert Chan, Rafael Pass, and Elaine Shi
Support Grand Challenges:
Correctness by Design and Construction
Sound Migration

Although Byzantine Agreement (BA) has been studied for three decades, perhaps somewhat surprisingly, there still exist significant gaps in our understanding regarding its round complexity. A long-standing open question is the following - can we achieve BA with sublinear round complexity under corrupt majority? Due to the beautiful works by Garay et al. (FOCS 2007) and Fitzi and Nielsen (DISC 2009), we have partial and affirmative answers to this question albeit for the narrow regime f=n/2 + O(n) where f is the number of corrupt nodes and n is the total number of nodes. So far, no positive result is known about the setting f>0.51n even for static corruption! In this paper, we make progress along this somewhat stagnant front. We show that there exists a corrupt-majority BA protocol that terminates in O(1/e log 1/delta) rounds in the worst case, satisfies consistency with probability at least 1-delta, and tolerates (1-e) fraction of corrupt nodes. Our protocol secures against an adversary that can corrupt nodes adaptively during the protocol execution but cannot perform *after-the-fact* removal of honest messages that have already been sent prior to corruption. Our upper bound is optimal up to a logarithmic factor in light of the elegant Omega(1/e) lower bound by Garay et al. (FOCS 2007). For more information, please see our paper.

An Empirical Analysis of Privacy in the Lightning Network
George Kappos, Haaroon Yousaf, Ania Piotrowska, Sanket Kanjalkar, Sergi Delgado-Segura, Andrew Miller, and Sarah Meiklejohn
Support Grand Challenges:
Secure Scaling and Performance
Correctness by Design and Construction

Payment channels networks, and the Lightning Network in particular, seem to offer a solution to the lack of scalability and privacy offered by Bitcoin and other blockchain-based cryptocurrencies. Previous research has focused on the scalability, availability, and crypto-economics of the Lightning Network, but relatively little attention has been paid to exploring the level of privacy offered by the Lightning Network, by presenting several attacks that exploit publicly available information about the network in order to learn information that is designed to be kept secret, such as how many coins a node has available or who the sender and recipient are in a payment routed through the network. For more information, please see our paper.

Democratic Value and Money for Decentralized Digital Society
Bryan Ford
Support Grand Challenges:
Secure Scaling and Performance
Correctness by Design and Construction

Classical monetary systems regularly subject the most vulnerable majority of the world population to debilitating financial shocks, and have manifestly allowed uncontrolled global inequality over the long term. Given these basic failures, how can we avoid asking whether mainstream macroeconomic principles are actually compatible with democratic principles such as equality or the protection of human rights and dignity? This idea paper takes a constructive look at this question, by exploring how alternate monetary principles might result in a form of money more compatible with democratic principles -- dare we call it *democratic money*? In this alternative macroeconomic philosophy, both the supply of and the demand for money must be rooted in people, so as to give all people both equal opportunities for economic participation. Money must be designed around equality, not only across all people alive at a given moment, but also across past and future generations of people, guaranteeing that our decendants cannot be enslaved by their ancestors economic luck of misfortune. Democratic money must reliably give all people a means to enable everyday commerce, investment, and value creation in good times and bad, and must impose hard limits on financial inequality. Democratic money must itself be governed democratically, and must economically facilitate the needs of citizens in a democracy for trustworthy and unbiased information with which to make wise collective decisions. An intriguing approach to implementing and deploying democratic money is via a cryptocurrency built on a proof-of-personhood foundation, giving each opt-in human participant one equal unit of stake. Such a cryptocurrency would have both interesting similarities to, and important differences from, a Universal Basic Income (UBI) denominated in an existing currency. Link to my work.

High Throughput Cryptocurrency Routing in Payment Channel Networks
Vibhaalakshmi Sivaraman, Shaileshh Bojja Venkatakrishnan, Kathleen Ruan, Parimarjan Negi, Lei Yang, Radhika Mittal, Giulia Fanti, and Mohammad Alizadeh
Support Grand Challenges:
Secure Scaling and Performance
Sound Migration

Despite growing adoption of cryptocurrencies, making fast payments at scale remains a challenge. Payment channel networks (PCNs) such as the Lightning Network have emerged as a viable scaling solution. However, completing payments on PCNs is challenging - payments must be routed on paths with sufficient funds. As payments flow over a single channel (link) in the same direction, the channel eventually becomes depleted and cannot support further payments in that direction, hence, naive routing schemes like shortest-path routing can deplete key payment channels and paralyze the system. Today PCNs also route payments atomically, worsening the problem. In this paper, we present Spider, a routing solution that *packetizes* transactions and uses a multi-path transport protocol to achieve high-throughput routing in PCNs. Packetization allows Spider to complete even large transactions on low-capacity payment channels over time, while the multi-path congestion control protocol ensures balanced utilization of channels and fairness across flows. extensive simulations comparing Spider with state-of-the-art approaches sjows that Spider requires less than 25% of the funds to successfully route over 95% of transactions on balanced traffic demands, and offloads 4x more transactions onto the PCN on imbalanced demandes. For more information, please see our paper.

Que Sera Consensus: Simple Asynchronous Agreement with Private Coins and Threshold Logical Clocks
Bryan Ford, Philipp Jovanovic, and Ewa Syta
Support Grand Challenges:
Sound Migration

It is commonly helt that asynchronous consensus is much more complex, difficult, and costly than partially-synchronous algorithms, especially without using common coins. This paper challenges that conventional wisdom with que sera consensus QSC, an approach to consensus that cleanly decomposes the agreement problem from that of network asynchrony. QSC uses only private coins and reaches consensus in O(1) expected communication rounds. It relies on *lock-step* synchronous broadcast, but can run atop a threshold logical clock (TLC) algorithm to time and pace partially-reliable communication atop an underlying asynchronous network. This combination is arguably simpler than partially-synchronous consensus approaches like (Multi-)Paxos or Raft with leader election, and is more robust to slow leaders or targeted network denial-of-service attacks. The simplest formulations of QSC atop TLC incur expected O(n2) messages and O(n4) bits per agreement, or O(n3) bits with straightforward optimizations. An on-demand implementation, in which clients act as *natural leaders* to execute the protocol atop stateful servers that merely implement passive key-value stores, can achieve O(n2) expected communication bits per client-driven agreement. For further information, please see our paper.

MIRAGE: Succinct Arguments for Randomized Algorithms with Applications to Universal zk-SNARKs
Ahmed Kosba, Dimitrios Papadopoulos, Charalampos Papamanthou, and Dawn Song
Support Grand Challenges:
Correctness by Design and Construction
Safety and Compliance
Sound Migration

The last few years have witnessed increasing interest in the deployment of zero-knowledge proof systems, in particular ones with succinct proofs and efficient verification (zk-SNARKs). One of the main challenges facing the wide deployment of zk-SNARKs is the requirement of a trusted key generation phase per different computation to achieve practical proving performance. Existing zero-knowledge proof systems that do not require trusted setup or have a single trusted preprocessing phase suffer from increased proof size and/or additional verification overhead. On the other hand, although universal circuit generators for zk-SNARKs (that can eliminate the need for per-computation preprocessing) have been introduced in the literature, the performance of the prover remains far from practical for real-world applications. In this paper, we first present a new zk-SNARK system that is well-suited for randomized algorithms --- in particular, it does not encode randomness generation within the arithmetic circuit allowing for more practical prover times. Then, we design a universal circuit that takes as input any arithmetic circuit of a bounded number of operations as well as a possible value assignment, and performs randomized checks to verify consistency. Our universal circuit is linear in the number of operations instead of quasi-linear like other universal circuits. By applying our new zk-SNARK system to our universal circuit, we build MIRAGE, a universal zk-SNARK with very succinct proofs --- the proof contains just one additional element compared to the per-circuit preprocessing state-of-the-art zk-SNARK by Groth (EuroCrypt 2016). Finally, we implement MIRAGE and experimentally evaluate its performance for different circuits and in the context of privacy-preserving smart contracts. For more information, please see our paper.

Order-Fairness for Byzantine Consensus
Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels
Support Grand Challenges:
Confidentiality
Sound Migration

Decades of research in both cryptography and distributed systems has extensively studied the problem of state machine replication, also known as Byzantine consensus. A consensus protocol must satisfy two properties, consistency and liveness. These properties ensure that honest participating nodes agree on the same log and dictate when fresh transactions get added. They fail, however, to ensure against adversarial manipulation of the actual ordering of transactions in the log. Indeed, in leader-based protocols (almost all protocols used today), malicious leaders can directly choose the final transaction ordering. To rectify this problem, we propose a third consensus property, transaction order-fairness. We initiate the first formal investigation of order-fairness and explain its fundamental importance. We provide several natural definitions for order-fairness and analyze the assumptions necessary to realize them. We also propose a new class of consensus protocols called Aequitas. Aequitas protocols are the first to achieve order-fairness in addition to consistency and liveness. They can be realized in a black-box way using existing broadcast and agreement primitives (or indeed using any consensus protocol), and work in both synchronous and asynchronous network models. For more information, please see our paper.

Scalog: Seamless Reconfiguration and Total Order in a Scalable Shared Log
Cong Ding, David Chu, Evan Zhao, Xiang Li, Lorenzo Alvisi, and Robbert van Renesse
Support Grand Challenges:
Secure Scaling and Performance

The shared log paradigm is at the heart of modern distributed applications in the growing cloud computing industry. Often, applications logs must be stored durably for analytics, regulations, or failure recovery, and their smooth operation depends closely on how the log is implemented. Scalog is a new implementation of the shared log abstraction that offers an unprecedented combination of features for continuous smooth delivery of service. Scalog allows applications to customize data placement, supports reconfiguration with no loss in availability, and recovers quickly from failures. At the same time, Scalog provides high throughput and total order. The paper describes the design and implementation of Scalog and presents examples of applications running upon it. To evaluate Scalog at scale, we use a combination of real experiments and emulation. Using 4KB records, a 10 Gbps infrastruture, and SSDs, Scalog can totally order up to 52 million records per second. For more information, please see our paper.

CUSTOS: Practical Tamper-Evident Auditing of Operating Systems Using Trusted Execution
Riccardo Paccagnella, Pubali Datta, Wajih Ul Hassan, Adam Bates, Christopher W. Fletcher, Andrew Miller, and Dave Tian
Support Grand Challenges:
Secure Scaling and Performance
Correctness by Design and Construction

System auditing is a central concern when investigating and responding to security incidents. Unfortunately, attackers regularly engage in anti-forensic activities after a break-in, covering their tracks from the system logs in order to frustrate the efforts of investigators. While a variety of tamper-evident logging solutions have appeared throughout the industry and the literature, these techniques do not meet the operational and scalability requirements of system-layer audit frameworks. In this work, we introduce CUSTOS, a practical framework for the detection of tampering in system logs. CUSTOS consists of a tamper-evident logging layer and a decentralized auditing protocol. The former enables the verification of log integrity with minimal changes to the underlying logging framework, while the latter enables near real-time detection of log integrity violations within an enterprise-class network. CUSTOS is made practical by the observation that we can decouple the costs of cryptographic log commitments from the act of creating and storing log events, without trading off security, leveraging features of off-the-shelf trusted execution environments. Supporting over one million events per second, we show that CUSTOS tamper-evident logging protocol is three orders of magnitude (1000x) faster than prior solutions and incurs only between 2% and 7% runtime overhead over insecure logging on intensive workloads. Further, we show that the CUSTOS auditing protocol can detect violations in near real-time even in the presence of a powerful distributed adversary and with minimal (3%) network overhead. Our case study on a real-world APT attack scenario demonstrates that CUSTOS forces anti-forensic attackers into a *lose-lose* situation, where they can either be covert and not tamper with logs (which can be used for forensics), or erase logs but then be detected by CUSTOS. For more information, please see our paper.

MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture
T-H. Hubert Chan, Kai-Min Chung, Wei-Kai Lin, and Elaine Shi
Support Grand Challenges:
Safety and Compliance
Confidentiality

Massively Parallel Computation (MPC) is a model of computation widely believed to best capture realistic parallel computing architectures such as large-scale MapReduce and Hadoop clusters. Motivated by the fact that many data analytics tasks performed on these platforms involve sensitive user data, we initiate the theoretical exploration of how to leverage MPC architectures to enable efficient, privacy-preserving computation over massive data. Clearly if a computation task does not lend itself to an efficient implementation on MPC even without security, then we cannot hope to compute it efficiently on MPC with security. We show, on the other hand, that any task that can be efficiently computed on MPC can also be securely computed with comparable efficiency. Specifically, we show the following results - (1) any MPC algorithm can be compiled to a communication-oblivious counterpart while asymptotically preserving its round and space complexity, where communication-obliviousness ensures that any network intermediary observing the communication patterns leanr no information about the secret inputs, (2) assuming the existence of Fully Homomorphic Encryption with a suitable notion of compactness and other standard cryptographic assumptions, any MPC algorithm can be compiled to a secure counterpart that defends against an adversary who controls not only intermediate network routers but additionally up to 1/3 - n fraction of machines (for an arbitrarily small constant n) - moreover, this compilation preserves the round complexity tightly, and preserves the space complexity upto a multiplicative security parameter related blowup. As an initial exploration of this important direction, our work suggests new definitions and purposes novel protocols that blend algorithmic and cryptographic techniques. For further information, please see our paper.

Replicated state machines without replicated execution
Jonathan Lee, Kirill Nikitin, and Srinath Setty
Support Grand Challenges:
Correctness by Design and Construction
Sound Migration

This paper introduces a new approach to reduce end-to-end costs in large-scale replicated systems built under a Byzantine fault model. Specifically, our approach transforms a given replicated state machine (RSM) to another RSM where nodes incur lower costs by delegating state machine execution - an unstrusted prover produces succinct cryptographic proofs of correct state transitions along with state changes, which nodes in the transformed RSM verify and apply respectively. To realize our approach, we build Piperine, a system that makes the proof machinery profitable in the context of RSMs. Specifically, Piperine reduces the costs of both proving and verifying the correctness of state machine execution while retaining liveness - a distinctive requirement in the context of RSMs. Our experimental evaluation demonstrates that, for a payment service, employing Piperine is more profitable than naive reexecution of transactions as long as there are > 104 nodes. When we apply Piperine to ERC-20 transactions in Ethereum (a real-world RSM with up to 105 nodes), it reduces per-transaction costs by 5.4x and network costs by 2.7x. For more information, please see our paper.

Selfish Mining Re-examined
Kevin Alarcón Negy, Peter R. Rizun, and Emin Gün Sirer
Support Grand Challenges:
Safety and Compliance

This project revisits the selfish mining (SM) strategy in two ways. First, we present a modified SM strategy, convert selfish mining, that, perplexingly, is more profitable than Nakamoto even when the attacker performs no selfish mining after a difficulty adjustment. This strategy has the added benefit that it is even harder to detect than pure SM, and may additionally increase token value through deflation. Second, we analyze the profitability of SM under several difficulty adjustment schemes. For further information, please see our paper.

Streamlined Blockchains: A Simple and Elegant Approach (A Tutorial and Survey)
Elaine Shi
Support Grand Challenges:
Correctness by Design and Construction
Sound Migration

A blockchain protocol (also called state machine replication) allows a set of nodes to agree on a ever-growing, linearly ordered log of transactions. The classical consensus literature suggests two approaches for constructing a blockchain protocol, (1) through composition of single-shot consensus instances often called Byzantine Agreement, and (2) through direct construction of a blockchain where there is no clear-cut boundary between single-shot consensus instances. While conceptually simple, the former approach, precludes cross-instance optimizations in a practical implementation. This perhaps explains why the latter approach has gained more traction in practice - specifically, well-known protocols such as Paxos and PBFT all follow the direct-construction approach. In this tutorial, we present a new paradigm called *streamlined blockchains* for directly constructing blockchain protocols. This paradigm enables a new family of protocols that are extremely simple and natural - every epoch, a proposer proposes a block extending from a notarized parent chain, and nodes vote if the proposal parent chain is not too old. Whenever a block gains enough votes, it becomes notarized. Whenever a node observes a notarized chain with several block of consecutive epochs at the end, then the entire chain chopping off a few blocks at the end is final. By varying the parameters highlighted in blue, we illustrate two variants for the partially synchronous and synchronous settings respectively. We present very simple proofs of consistency and liveness. We hope that this tutorial provides a compelling argument why this new family of protocols should be used in lieu of classical candidates (e.g., PBFT, Paxos, and their variants), both in practical implementation and for pedagogical purposes. For further information, please see our work.

First-Order Logic for Flow-Limited Authorization
Andrew K. Hirsch, Pedro H. Azevedo de Amorim, Ethan Cecchetti, Ross Tate, and Owen Arden
Support Grand Challenges:
Correctness by Design and Construction

We present the Flow-Limited Authorization First-Order Logic (FLAFOL), a logic for reasoning about authorization decisions in the presence of information-flow policies. We formalize the FLAFOL proof system, characterize its proof-theoretic properties, and develop its security guarantees. In particular, FLAFOL is the first logic to provide a non-interference guarantee while supporting all connectives of first-order logic. Furthermore, this guarantee is the first to combine the notions of non-interference from both authorization logic and information-flow systems. All theorems in this paper are proven in Coq. For more information, please see our paper.

ONet Implementation of Gossip-based Signature Aggregation
Elias M. Poroma Wiri, Bryan Ford, Cristina Basescu, and Gaylor Bosson
Support Grand Challenges:
Correctness by Design and Construction

Decentralized cosigning protocols have the main purpose of collecting digital signatures of a message from many peers. This type of protocols is used in two existing implementations. The first one is BLS CoSi which uses trees to get the signatures and aggregate them, the second one is a gossip protocol. This semester project develops and compares alternative implementations of the gossip-based aggregation. The main goal of the new implementations is to reduce the bandwidth used and to be relatively fast. Furthermore, this project adds an hybrid implementation of trees and gossiping inside Cothority ONet library, which is used for a new implementation of signature aggregation. Finally, there is an analysis of this protocol, measuring its performance and finding possible future improvements. For more information, please see our paper.

Snappy: Fast On-chain Payments with Practical Collaterals
Vasilios Mavroudis, Karl Wust, Aritra Dhar, Kari Kostiainen, and Srdjan Capkun
Support Grand Challenges:
Correctness by Design and Construction
Safety and Compliance

Permissionless blockchains offer many advantages but also have significant limitations including high latency. This prevents their use in important scenarios such as retail payments, where merchants should approve payments fast. Prior works have attempted to mitigate this problem by moving transactions off the chain. However, such Layer-2 solutions have their own problems --- a) payment channels require a separate deposit towards each merchant and thus significant locked-in funds from customers, b) payment hubs require very large operator deposits that depend on the number of customers, and c) side-chains require trusted validators. In this paper, we propose Snappy, a novel solution that enables recipients, like merchants, to safely accept fast payments. In Snappy, all payments are on the chain, while small customer collaterals and moderate merchant collaterals act as payment guarantees. Besides receiving payments, merchants also act as statekeepers who collectively track and approve incoming payments using majority voting. In case of a double-spending attack, the victim merchant can recover lost funds either from the collateral of the malicious customer or a colluding statekeeper (merchant). Snappy overcomes the main problems of previous solutions - (1) a single customer collateral can be used to shop with many merchants, (2) merchant collaterals are independent of the number of customers, and (3) validators do not have to be trusted. Our Ethereum prototype shows that safe, fast (<2 seconds) and cheap payments are possible on existing blockchains. For more information, please see our paper.

Virgo
Jiaheng Zhang, Tiancheng Xie, Yupeng Zhang, and Dawn Song
Support Grand Challenges:
Secure Scaling and Performance
Confidentiality

Virgo is a new zero knowledge proofs scheme for layered arithmetic circuits without trusted setup. It takes only 50 seconds to generate a proof for a circuit with 2^26 gates. And it has succinct prrof size and short verification time. It's based on a prior work Libra and a new transparent zero knowledge verifiable polynomial delegation scheme. The scheme is in the initeractive oracle proof model and based on the univeriate sumcheck. To read more, please see our paper.

BDoS: Blockchain Denial of Service
Michael Mirkin, Yan Ji, Jonathan Pang, Ariah Klages-Mundt, Ittay Eyal, and Ari Juels
Support Grand Challenges:
Correctness by Design and Construction
Safety and Compliance

We have discovered a denial-of-service attack on Bitcoin-like blockchains that is much cheaper than previously described attacks. Such blockchains rely on incentives to provide security. We show how an attacker can disrupt those incentives to cause rational miners to stop mining. Read the technical report here.

Winkle: Foiling Long-Range Attacks in Proof-of-Stake Systems
Sarah Azouvi, George Danezis, and Valeria Nikolaenko
Support Grand Challenges:
Correctness by Design and Construction

Winkle protects any validator-based byzantine fault tolerant consensus mechanisms, such as those used in modern Proof-of-Stake blockchains, against long-range attacks where old validators signature keys get compromised. Winkle is a decentralized secondary layer of client-based validation, where a client includes a single additional field into a transaction that they sign, a hash of the previously sequenced block. The block that gets a threshold of signatures (confirmations) weighted by clients coins is called a *confirmed* checkpoint. We show that under plausible and flexible security assumptions about clients the confirmed checkpoints cannot be equivocated. We discuss how client key rotation increases security, how to accommodate for coins minting and how delegation allows for faster checkpoints. We evaluate checkpoint latency experimentally using Bitcoin and Ethereum transaction graphs, with and without delegation of stake. For more information, please see our paper.

IPDL: A Probabilistic Dataflow Logic for Cryptography
Xiong Fan, Joshua Gancher, Greg Morrisett, Elaine Shi, and Kristina Sojakova
Support Grand Challenges:
Secure Scaling and Performance
Correctness by Design and Construction

While there have been many successes in verifying cryptographic security proofs of non-interactive primitives such as encryption and signatures, less attention has been paid to interactive cryptographic protocols. Interactive protocols introduce the additional verification challenge of concurrency, which is notoriously hard to reason about in a cryptographically sound manner. When proving the (approximate) observational equivalance of protocols, as is required by simulation based security in the style of Universal Composability (UC), a bisimulation is typically performed in order to reason about the nontrivial control flows induced by concurrency. Unfortunately, bisimulations are typically very tedious to carry out manually and do not capture the high-level intuitions which guide informal proofs of UC security on paper. Because of this, there is currently a large gap of formality between proofs of cryptographic protocols on paper and in mechanized theorem provers. We work towards closing this gap through a new methodology for iteratively constructing bisimulations in a manner close to on-paper intuition. We present this methodology through Interactive Probabilistic Dependency Logic (IPDL), a simple calculus and proof system for specifying and reasoning about (a certain subclass of) distributed probabilistic computations. The IPDL framework exposes an equational logic on protocols - proofs in our logic consist of a number of rewriting rules, each of which induce a single low-level bisimulation between protocols. We show how to encode simulation-based security in the style of UC in our logic, and evaluate our logic on a number of case studies - most notably, a semi-honest secure Oblivious Transfer protocol, and a simple multiparty computation protocol robust to Byzantine faults. Due to the novel design of our logic, we are able to deliver mechanized proofs of protocols which we believe are comprehensible to cryptographers without verification expertise. We provide a mechanization in Coq of IPDL and all case studies presented in this work. For further information, please see our work.

Rethinking General-Purpose Decentralized Computing
Enis Ceyhun Alp, Lefteris Kokoris-Kogias, Georgia Fragkouli, and Bryan Ford
Support Grand Challenges:
Secure Scaling and Performance
Safety and Compliance

While showing great promise, smart contracts are difficult to program correctly, as they need a deep understanding of cryptography and distributed algorithms,and offer limited functionality, as they have to be deterministic and cannot operate on secret data. In this paper we present Protean, a general-purpose decentralized computing platform that addresses these limitations by moving from a monolithic execution model, where all participating nodes store all the state and execute every computation, to a modular execution-model. Protean employs secure specialized modules, called functional units, for building decentralized applications that are currently insecure or impossible to implement with smart contracts. Each functional unit is a distributed system that provides a special-purpose functionality by exposing atomic transactions to the smart-contract developer. Combining these transactions into arbitrarily-defined worklfows, developers can build a larger class of decentralized applications, such as provably-secure and fair lotteries or e-voting. For further information, please see our paper.

Succinct Non-Interactive Secure Computation
Andrew Morgan, Rafael Pass, and Antigoni Polychroniadou
Support Grand Challenges:
Correctness by Design and Construction

We present the first maliciously secure protocol for succinct non-interactive secure two-party computation (SNISC) - Each player sends just a single message whose length is (essentially) independent of the running time of the function to be computed. The protocol does not require any trusted setup, satisfies superpolynomial-time simulation-based security (SPS), and is based on (subexponential) security of the Learning With Errors (LWE) assumption. We do not rely on SNARKs or *knowledge of exponent* - type assumptions. Since the protocol is non-interactive, the relaxation to SPS security is needed, as standard polynomial-time simulation is impossible - however, a slight variant of our main protocol yields a SNISC with polynomial-time simulation in the CRS model. For more information, please see our paper.

Bone Crusher 2.0
James Grimmelmann
Support Grand Challenges:
Safety and Compliance

The late legal scholar Greg Lastowka wrote about law, property, and self-government in virtual worlds like Ultima Online. His observations are relevant to blockchains and their communities of users. For more information, please read my paper.

A vision for autonomous blockchains backed by secure hardware
Kai Mast, Lequn Chen, and Emin Gun Sirer
Support Grand Challenges:
Secure Scaling and Performance
Correctness by Design and Construction

Blockchains have emerged as a potential mechanism to enable immutable and consistent sharing of data across organizational boundaries. While much of the discussion on blockchains to date has been structured around public versus permissioned blockchains, both of these architectures have significant drawbacks. Public blockchains are energy inefficient, hard to scale and suffer from limited throughput and high latencies, while permissioned blockchains depend on specially designated nodes, potentially leak metainformation, and also suffer from scale and performance bottlenecks. This raises the question if blockchains, in their current form, are the only class of datastores that can provide such strong integrity guarantees. We introduce autonomous blockchains, an architecture based on free-standing, immutable, eidetic databases that implement independent timelines, linked together through interactions. Autonomous blockchains can be realized using trusted execution environments in combination with audit mechanisms. This architecture does not only provide blockchain-like integrity and auditability guarantees but also supports storing and querying private data. Further, multiple autonomous blockchains can be linked together through federated transactions to exchange data and order mutual operations. These transactions are amenable to audits and yield tamper-proof witnesses. Evaluation shows that this design can achieve high throughput while providing stronger integrity guarantees than conventional datastores. Link to our paper.

Divide and Scale: Formalization of Distributed Ledger Sharding Protocols
George Avarikioti, Eleftherios Kokoris-Kogias, and Roger Wattenhofer
Support Grand Challenges:
Secure Scaling and Performance
Correctness by Design and Construction

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/log n) 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 shared blockchains (Elastico, Monoxide, OmniLedger, RapidChain) and pinpoint where they fail to meet the desired properties. For further information, please see our paper.

Rationality is Self-Defeating in Permissionless Systems
Bryan Ford and Rainer Bohme
Support Grand Challenges:
Secure Scaling and Performance

We outline a metacircular argument explaining why it is rational to be irrational when attacking open-world decentralized systems, and why systems whose security depend on rationality assumptions are insecure. Link to our paper.

SoK: Communication Across Distributed Ledgers
Alexei Zamyatin,Mustafa Al-Bassam, Dionysis Zindros, Eleftherios Kokoris-Kogias, Pedro Moreno-Sanchez, Aggelos Kiayias, and William J. Knottenbelt
Support Grand Challenges:
Secure Scaling and Performance
Correctness by Design and Construction

Since the inception of Bitcoin, a plethora of distributed ledgers differing in design and purpose has been created. While by design, blockchains provide no means to securely communicate with external systems, numerous attempts towards trustless cross-chain communication have been proposed over the years. Today, cross-chain communication (CCC) palys a fundamental role in cryptocurrency exchanges, scalability efforts via sharding, extension of existing systems through sidechains, and bootstrapping of new blockchains. Unfortunately, existing proposals are designed ad-hoc for specific use-cases, making it hard to gain confidence in their correctness and composability. We provide the first systematic exposition of cross-chain communication protocols. We formalize the underlying research problem and show that CCC is impossible without a trusted third party, contrary to common beliefs in the blockchain community. With this result in mind, we develop a framework to design new and evaluate existing CCC protocols, focusing on the inherent trust assumptions thereof, and derive a classification covering the field of cross-chain communication to date. We conclude by discussing open challenges for CCC research and the implications of interoperability on the security and privacy of blockchains. For more information, please see our paper.

All Smart Contracts Are Ambiguous
James Grimmelmann
Support Grand Challenges:
Safety and Compliance

Legal contracts are written in natural language, which can introduce ambiguity as to their meaning. Blockchain-based smart contracts are written in programming languages, which seems to give them precise, objective meanings. But because the semantics of a smart contract can change if participants fork the underlying blockchain or revise its protocol, the meaning of a smart contract is always subject to this latent ambiguity. For more information, please read my paper.

I Can't Believe It's Not Stake
Sanket Kanjalkar, Joseph Kuo, Yunqi Li, and Andrew Miller
Support Grand Challenges:
Secure Scaling and Performance
Correctness by Design and Construction

Dozens of Proof-of-Stake cryptocurrencies are vulnerable to resource exhaustion attacks due to incomplete validation of blocks prior to allocating storage resources (disk, memory) to data from untrusted peers. For further details, please see our paper.

Prism: Scaling Bitcoin by 10,000x
Lei Yang, Vivek Bagaria, Gerui Wang, Mohammad Alizadeh, David Tse, Giulia Fanti, and Pramod Viswanath
Support Grand Challenges:
Secure Scaling and Performance

Bitcoin is the first fully decentralized permissionless blockchain protocol and achieves a high level of security - the ledger it maintains has guaranteed liveness and consistency properties as long as the adversary has less compute power than the honest nodes. However, its throughput is only 7 transactions per second and the confirmation latency can be up to hours. Prism is a new blockchain protocol which is designed to achieve a natural scaling of Bitcoin performance while maintaining its full security guarantees. We present an implementation of Prism which achieves a throughput of 70,000 transactions per second and confirmation latencies of tens of seconds. For more information, please see our paper.

Barracuda: The Power of l-polling in Proof-of-Stake Blockchains
Giulia Fanti, Jiantao Jiao, Ashok Makkuva, Sewoong Oh, Ranvir Rana, and Pramod Viswanath
Support Grand Challenges:
Secure Scaling and Performance

a blockchain is a database of sequential events that is maintained by a distributed group of nodes. A key consensus problem in blockchains is that of determining the next block (data element) in the sequence. Many blockchains address this by electing a new node to propose each new block. The new block is (typically) appended to the tip of the proposer local blockchain, and subsequently broadcast tp the rest of the network. Without network delay (or adversarial behavior), this procedure would give a perfect chain, since each proposer would have the same view of the blockchain. A major challenge in practice is forking. Due to network delays, a proposer may not yet have the most recent block, and may, therefore, create a side chain that branches from the middle of the main chain. Forking reduces throughput, since only one a single main chain can survive, and all other blocks are discarded. We propose a new P2P protocol for blockchains called Barracuda, in which each proposer, prior to proposing a block, polls l other nodes for their local blocktree information. Under a stochastic network model, we prove that this lightweight primitive improves throughput as if the entire network were a factor of l faster. We provide guidelines on how to implement Barracuda in practice, gurarnteeing robustness against several real-world factors. For further information, please see our paper.

A Classification Framework for Stablecoin Designs
Amani Moin, Emin Gun Sirer, and Kevin Sekniqi
Support Grand Challenges:
Sound Migration

Stablecoins promise to bridge fiat currencies with the world of cryptocurrencies. They provide a way for users to take advantage of the benefits of digital currencies, such as ability to transfer assets over the internet, provide assurance on minting schedules and scarcity, and enable new asset classes, while also partially mitigating their volatility risks. In this paper, we systematically discuss general design, decompose existing stablecoins into various component design elements, explore their strengths and drawbacks, and identify future directions. For more information, please see our paper.

Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures
Eleftherios Kokoris-Kogias, Dahlia Malkhi, and Alexander Spiegelman
Support Grand Challenges:
Secure Scaling and Performance

In this paper, we present the first fully asynchronous distributed key generation (ADKG) algorithm as well as the first distributed key generation algorithm that can create keys with a dual (f, 2f + 1) - threshold that are necessary for scalable consensus (which so far needs a trusted dealer assumption). In order to create a DKG with a dual (f, 2f + 1) - threshold we first answer in the affirmative the open question posed by Cachin et al. how to create an AVSS protocol with recovery thresholds f + 1 < k <= 2f + 1, which is of independent interest. Our High-threshold-AVSS (\textit{HAVSS}) uses an asymmetric bi-variate polynomial, where the secret shared is hidden from any set of k nodes but an honest node that did not participate in the sharing phase can still recover his share with only n - 2f shares, hence be able to contribute in the secret reconstruction. Another building block for ADKG is a novel \textit{Eventually Perfect} Common Coin (EPCC) abstraction and protocol that enables the participants to create a common coin that might fail to agree at most f + 1 times (even if invoked a polynomial number of times). Using \textit{EPCC} we implement an Eventually Efficient Asynchronous Binary Agreement (EEABA) in which each instance takes O(n2) bits and O(1) rounds in expectation, except for at most f + 1 instances which may take O(n4) bits and O(n) rounds in total. Using EEABA we construct the first fully Asynchronous Distributed Key Generation (ADKG) which has the same overhead and expected runtime as the best partially-synchronous DKG (O(n4) words, O(n) rounds). As a corollary of our ADKG we can also create the first Validated Asynchronous Byzantine Agreement (VABA) in the authenticated setting that does not need a trusted dealer to setup threshold signature degree n - f. Our VABA has an overhead of expected O(n2) words and O(1) time per instance after an initial O(n4) words and O(n) time bootstrap via ADKG. Link to our work.

Mixicles: Simple Private Decentralized Finance
Ari Juels, Lorenz Breidenbach, Alex Coventry, Sergey Nazarov, Steve Ellis, and Brendan Magauran
Support Grand Challenges:
Secure Scaling and Performance
Safety and Compliance

We show how to use oracles to build simple, privacy-preserving decentralized finance (DeFi) instruments we call Mixicles. Mixicles ingest input payments from two or more parties and yield payouts that are conditioned on oracle reports. They are designed to provide privacy for both the terms and outcomes of the financial instruments they execute. At the same time, Mixicles can support rigorous regulatory and auditing requirements. The most appealing feature of Mixicles is their avoidance of expensive cryptography and complicated contract structures. Mixicles are conceptually simple, and have low on-chain and off-chain resource consumption. We present an example implementation to show how they work and demonstrate their benefits. For further information, please see our paper.

DECO
Fan Zhang, Sai Krishna Deepak Maram, Harjasleen Malvai, Steven Goldfeder, and Ari Juels
Support Grand Challenges:
Confidentiality
Safety and Compliance

DECO is a privacy-preserving oracle protocol. Using cryptographic techniques, it lets users prove facts about thier web (TLS) sessions to oracles while hiding privacy-sensitive data. For more information, see deco.works.

Impossibility of Full Decentralization in Permissionless Blockchains
Yujin Kwon, Jian Liu, Mingjeong Kim, Dawn Song, and Yongdae Kim
Support Grand Challenges:
Secure Scaling and Performance

Bitcoin uses the proof-of-work (PoW) mechanism where nodes earn rewards in return for the use of their computing resources. Although this incentive system has attracted many participants, power has, at the same time, been significantly biased towards a few nodes, called mining pools. In addition, poor decentralization appears not only in PoW-based coins but also in coins that adopt proof-of-stake (PoS) and delegated proof-of-stake (DPoS) mechanisms. For more information, please see our paper.

Asynchronous Consensus Without Rounds
Robbert van Renesse
Support Grand Challenges:
Sound Migration

Fault tolerant consensus protocols usually involve ordered rounds of voting between a collection of processes. In this paper, we derive a general specification of fault tolerant asynchronous consensus protocols and present a class of consensus protocols that refine this specification without using rounds. Crash-tolerant protocols in this class use 3f + 1 processes, while Byzantine-tolerant protocols use 5f + 1 processes. Link to my work.

Teechain: A Secure Payment Network with Asynchronous Blockchain Access
Joshua Lind, Oded Naor, Ittay Eyal, Florian Kelbert, Peter Pietzuch, and Emin Gün Sirer
Support Grand Challenges:
Secure Scaling and Performance

Teechain is the first asynchronous second layer payment network that allows users to execute immediate payments while not requiring parties to constantly monitor the blockchain. Teechain leverages trusted execution environments (TEEs) and uses a new variant of chain replication to ensure security against TEE compromise and side-channel attacks. Teechain achieves at least 33x better throughput than other existing payment networks. For more info, please see our paper.

FabZK: Supporting Privacy-Preserving, Auditable Smart Contracts in Hyperledger Fabric
Hui Kang, Ting Dai, Nerla Jean-Louis, Shu Tao, and Xiaohui Gu
Support Grand Challenges:
Safety and Compliance
Correctness by Design and Construction

On a Blockchain network, transaction data are exposed to all participants. To preserve privacy and confidentiality in transactions, while still maintaining data immutability, we design and implement FabZK. FabZK conceals transaction details on a shared ledger by storing only encrypted data from each transaction (e.g., payment amount), and by anonymizing the transactional relationship (e.g., payer and payee) between members in a Blockchain network. It achieves both privacy and auditability by supporting verifiable Pedersen commitments and constructing zero-knowledge proofs. FabZK is implemented as an extension to the open source Hyperledger Fabric. It provides APIs to easily enable data privacy in both client code and chaincode. It also supports on-demand, automated auditing based on encrypted data. Our evaluation shows that FabZK offers strong privacy-preserving capabilities, while delivering reasonable performance for the applications developed based on its framework. For further information, please see our paper.

HoneyBadgerMPC and AsynchroMix: Practical AsynchronousMPC and its Application to Anonymous Communication
Donghang Lu, Thomas Yurek, Samarth Kulshreshtha, Rahul Govind, Rahul Mahadev, Aniket Kate, and Andrew Miller
Support Grand Challenges:
Secure Scaling and Performance
Safety and Compliance

Multiparty computation as a service (MPSaaS) is a promising approach for building privacy-preserving communication systems. However, in this paper, we argue that existing MPC implementations are inadequate for this application as they do not address fairness, let alone robustness. Even a single malicious server can cause the protocol to abort while seeing the output for itself, which in the context of an anonymous communication service would create a vulnerability to censorship and deanonymization attacks. To remedy this we propose a new MPC implementation, HoneyBadgerMPC, that combines a robust online phase with an optimistic offline phase that is efficient enough to run continously alongside the online phase. We use HoneyBadgerMPC to develop an application case study, called AsynchroMix, that provides an anonymous broadcast functionality. AsynchroMix features a novel MPC program that trades off between computation and communication, allowing for low-latency message mixing in varying settings. In a cloud-based distributed benchmark with 100 nodes, we demonstrate mixing a batch of 512 messages in around 20 seconds and up to 4096 messages in around two minutes. For more information, please see our paper.

HotStuff: BFT Consensus with Linearity and Responsiveness
Maofan Yin, Dahlia Malkhi, Micahel K. Reiter, Guy Golan Gueta, and Itai Abraham
Support Grand Challenges:
Sound Migration
Correctness by Design and Construction

We present HotStuff, a leader-based Byzantine fault-tolerant replication protocol for the partially synchronous model. Once network communication becomes synchronous, HotStuff enables a correct leader to drive the protocol to consensus at the pace of actual (vs. maximum) network delay - a property called responsiveness - and with communication complexity that is linear in the number of replicas. To our knowledge, HotStuff is the first partially synchronous BFT replication protocol exhibiting these combined properties. Its simplicity enables it to be further pipelined and simplified into a practical, concise protocol for building large-scale replication services. For more information, please see our paper.

Bitcontracts: Supporting Smart Contracts in Legacy Blockchains
Karl Wust, Loris Diana, Kari Kostiainen, Ghassan Karame, Sinisa Matetic, and Srdjan Capkun
Support Grand Challenges:
Safety and Compliance
Confidentiality

In this paper we propose Bitcontracts, a novel solution that enables secure and efficient execution of generic smart contracts on top of unmodified legacy cryptocurrencies like Bitcoin that do not support contracts natively. The starting point of our solution is an off-chain execution model, where the contract issuers appoints a set of service providers to execute the contract code. The contract execution results are accepted if a quorum of service providers reports the same results and clients are free to choose which such contracts they trust and use. The main technical contribution of this paper is how to realize such a trust model securely and efficiently without modifying the underlying blockchain. We also identify a set of generic properties that a blockchain system must support so that expressive smart contracts can be added safely, and analyze popular existing blockchains based on these criteria. For further information, please see our paper.

ACE: Asynchronous and Concurrent Execution of Complex Smart Contracts
Karl Wust, Sinisa Matetic, Silvan Egli, Kari Kostiainen, and Srdjan Capkun
Support Grand Challenges:
Safety and Compliance
Authenticated Data Feeds

Smart contracts are programmable, decentralized and transparent financial applications. Because smart contract platforms typically support Turing-complete programming languages, such systems are often said to enable arbitrary applications. However, the current permissionless smart contract systems impose heavy restrictions on the types of computations thata can be implemented. For example, the globally-replica ted and sequential execution model of Ethereum requires low gas limits that make many computations infeasible. In this paper, we propose a novel system called ACE whose main goal is to enable more complex smart contracts on permissionless blockcahins. ACE is based on an off-chain execution model where the contract issuers appoint a set of service providers to execute the contract code independent from the consensus layer. The primary advantage of ACE over previous solutions is that it allows one contract to safely call another contract that is executed by a different set of service providers. Thus, ACE is the first solution to enable off-chain execution of interactive smart contracts with flexible trust assumptions. Our evalution shows that ACE enables several orders of magnitude more complex smart contracts than standard Ethereum. For more information, please see our paper.

Threshold Logical Clocks for Asynchronous Distributed Coordination and Consensus
Bryan Ford
Support Grand Challenges:
Sound Migration

Consensus protocols for asynchronous networks are usually complex and inefficient, leading practical systems to rely on synchronous protocols. This paper attempts to simplify asynchronous consensus by building atop a novel threshold logical clock abstraction, which enables upper layers to operate as if on a synchronous network. This approach yields an asynchronous consensus protocol for fail-stop nodes that may be simpler and more robust than Paxos and its leader-based variants, requiring no common coins and achieving consensus in a constant expected number of rounds. The same approach can be strengthened against Byzantine failures by building on well-established techniques such as tamper-evident logging and gossip, accountable state machines, threshold signatures and witness cosigning, and verifiable secret sharing. This combination of existing abstractions and threshold logical clocks yields a modular, cleanly-layered approach to building practical and efficient Byzantine consensus, distributed, timestamping, and randomness beacons, and other critical services. Link to my work.

Fair Byzantine Agreements for Blockchains
Po-Chun Kuo, Hao Chung, Tzu-Wei Chao, and Chen-Mou Cheng
Support Grand Challenges:
Correctness by Design and Construction

The Byzantine general problem is the core problem that consensus algorithms are trying to solve, which is at the heart of the design of blockchains. As a result, we have seen numerous proposals of consensus algorithms in recent years, trying to improve the level of decentralization, performance, and security of blockchains. In our opinion, there are two most challenging issues when we consider the design of such algorithms in the context of powering blockchains in practice. First, the outcome of a consensus algorithm usually depends on the underlying incentive model, so each participant should have an equal probability of receiving rewards for its work. Secondly, the protocol should be able to resist network failures, such as cloud services shutdown, while maintaining high performance otherwise. We address these two critical issues in this paper. First, we propose a new metric, called fair validity, for measuring the performance of Byzantine agreements. Intuitively, fair validity provides a lower bound for the probability of acceptances of honest nodes proposals. This is a strong notion of fairness, and we argue that it is crucial for the success of a blockchain in practice. We then show that any Byzantine agreement could not achieve fair validity in an asynchronous network, so we will focus on synchronous protocols. This leads to our second contribution - we propose a fair, responsive, and partition-resilient Byzantine agreement protocol able to tolerate up to 1/3 corruptions. As we will show in the paper, our protocol achieves fair validity and is responsive in the sense that the termination time only depends on actual network delay, as opposed to arbitrary, pre-determined time-bound. Furthermore, our proposal is partition-resilient. Last but not least, experimental results show that our Byzantine agreement protocol outperforms a wide variety of state-of-the-art synchronous protocols, combining the best from both theoretic and practical worlds. For more information, please see our paper.

Ostraka
Alex Manuskin, Michael Mirkin, and Ittay Eyal
Support Grand Challenges:
Secure Scaling and Performance

Currently, the capacity of a blockchain node can only scale by replacing hardware. For better performance, one must obtain newer hardware. Node capacity effects both initial sync time and block propagation time in the network. We utilize the parallel nature of the UTXO set to build a scalable node architecture. For more info, please see our paper.

Pay To Win: Cheap, Crowdfundable, Cross-chain Algorithmic Incentive Manipulation Attacks on PoW Cryptocurrencies
Aljosha Judmayer, Nicholas Stifter, Alexei Zamyatin, Itay Tsabary, Ittay Eyal, Peter Gazi, Sarah Meiklejohn, and Edgar Weippl
Support Grand Challenges:
Correctness by Design and Construction
Safety and Compliance

In this paper we extend the attack landscape of bribing attacks on cryptocurrencies by presenting a new method, which we call Pay-To-Win (P2W). To the best of our knowledge, it is the first approach capable of facilitating double-spend collusion across different blockchains. Moreover, our technique can also be used to specifically incentivize transaction exclusion or (re)ordering. For our construction we rely on smart contracts to render the payment and receipt of bribes trustless for the briber as well as the bribee. Attacks using our approach are operated and financed out-of-band i.e., on a funding cryptocurrency, while the consequences are induced in a different target cryptocurrency. Hereby, the main requirement is that smart contracts on the funding cryptocurrency are able to verify consensus rules of the target. For a concrete instantiation of our P2W method, we choose Bitcoin as a target and Ethereum as a funding cryptocurrency. Our P2W method is designed in a way that reimburses collaborators even in the case of an unsuccessful attack. Interestingly, this actually renders our approach approximately one order of magnitude cheaper than comparable bribing techniques (e.g., the whale attack). We demonstrate the technical feasibility of P2W attacks through publishing all relevant artifacts of this paper, ranging from calculations of success probabilities to a fully functional proof-of-concept implementation, consisting of an Ethereum smart contract and a Python client. For more information, please see our paper.

Avalanche
Team Rocket, Maofan Yin, Kevin Sekniqi, Robbert van Renesse, and Emin Gün Sirer
Support Grand Challenges:
Secure Scaling and Performance

BFT consensus used by cryptocurrencies consists of two families, traditional consensus and Nakamoto's consensus. The former is usually leader-based, quadratic in message complexity. It requires precise membership knowledge, and suffers from leader bottleneck as it scales up in size. While the latter does not require membership, it is poor in performance and wasteful in energy due to PoW. This project proposes the third, new category of consensus protocols that is PoW-free, leader-less, committee-less, permission-less. It exerts the powerful meta-stability inspired by epidemic protocols, and operators as fast as the network propagates. For more info, please see our avalabs.org.

Robust and Scalable Consensus for Sharded Distributed Ledgers
Eleftherios Kokoris-Kogias
Support Grand Challenges:
Secure Scaling and Performance

ByzCoin, a promising alternative of Bitcoin, is a scalable consensus protocol used as a building block of many research and enterprise-level decentralized systems. In this paper, we show that ByzCoin is unsuitable for deployment in an anopen, adversarial network and instead introduce MOTOR. MOTOR is designed as a secure, robust, and scalable consensus suitable for permissionless sharded blockchains. MOTOR achieves these properties by making four key design choices - (a) it prioritizes robustness in adversarial environments while maintaining adequate scalability, (b) it employees provably correct cryptography that resists DoS attacks from individual nodes, (c) it deploys unpredictable rotating leaders to defend against mildly-adaptive adversaries and prevents censorship, and (d) it creates an incentive compatible reward mechanism. These choices are materialized as (a) a *rotating subleader* communication pattern that balances the scalability needs with the robustness requirements under failures, (b) deployment of provable secure BLS multi-signatures, (c) use of deterministic threshold signatures as a source of randomness and (d) careful design of the reward allocation mechanism. We have implemented MOTOR and compare it with ByzCoin. We show that MOTOR can scale similar to ByzCoin with an at most 2x overhead whereas it maintains good performance even under high-percentage of faults, unlike ByzCoin. Link to my work.

LazyLedger: A Distributed Data Availability Ledger with Client-Side Smart Contracts
Mustafa Al-Bassam
Support Grand Challenges:
Sound Migration
Correctness by Design and Construction

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 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. Link to my work.

Tracing Transactions Across Cryptocurrency Ledgers
Haaroon Yousaf, George Kappos, and Sarah Meiklejohn
Support Grand Challenges:
Safety and Compliance
Confidentiality

One of the defining features of a cryptocurrency is that its ledger, containing all transactions that have ever taken place, is globally visible. As one consequence of this degree of transparency, a long line of recent research has demonstrated that - even in cryptocurrencies that are specifically designed to improve anonymity - it is often possible to track money as it changes hands, and in some cases to de-anonymize users entirely. With the recent proliferation of alternative cryptocurrencies, however, it becomes relevant to ask not only whether or not money can be traced as it moves within the ledger of a single cryptocurremcy, but if it can in fact be traced as it moves across ledgers. This is especially pertinent given the rise in popularity of automated trading platforms such as ShapeShift, which make it effortless to carry out such cross-currency trades. In this paper, we use data scraped from ShapeShift over a thirteen-month period and the data from eight different blockchains to explore this question. Beyond developing new heuristics and creating new types of links across cryptocurrency ledgers, we also identify various patterns of cross-currency trades and of the general usage of these platforms, with the ultimate goal of understanding whether they serve a criminal or a profit-driven agenda. For further information, please see our paper.

Outguard: Detecting In-Browser Covert Cryptocurrency Mining in the Wild
Amin Kharraz, Zane Ma, Paul Murley, Charles Lever, Joshua Mason, Andrew Miller, Nikita Borisov, Manos Antonakakis, and Michael Bailey
Support Grand Challenges:
Confidentiality

In-browser cryptojacking is a form of resource abuse that leverages end-users machines to mine cryptocurrency without obtaining the users consent. In this paper, we design, implement, and evaluate Outguard, an automated cryptojacking detection system. We construct a large ground-truth dataset, extract several features using an instrumented web browser, and ultimately select seven distinctive features that are used to build an SVM classification model. Outguard achieves a 97.9% TPR and 1.1% FPR and is reasonably tolerant to adversarial evasions. We utilized Outgurad in the wild by deploying it across the Alexa Top 1M websites and found 6,302 cryptojacking sites, of which 3,600 are new detections that were absent from the training data. These cryptojacking sites paint a broad picture of the cryptojacking ecosystem, with particular emphasis on the prevalence of cryptojacking websites and the shared infrastructure that provides clues to the operators behind the cryptojacking phenomenon. For more information, please see our < a href="http://mdbailey.ece.illinois.edu/publications/www19_cryptojacking.pdf">paper.

TEEvil: Identity Lease via Trusted Execution Environments
Ivan Puddu, Daniele Lain, Moritz Schneider, Elizaveta Tretiakova, Sinisa Matetic, and Srdjan Capkun
Support Grand Challenges:
Safety and Compliance
Confidentiality

We investigate identity lease, a new type of service in which users lease their identities to third parties by providing them with full or restricted access to their online accounts or credentials. We discuss how identity lease could be abused to subvert the digital society, facilitating the spread of fake news and subverting electronic voting by enabling the sale of votes. We show that the emrgence of Trusted Execution Environments and anonymous cryptocurrencies, for the first time, allows the implementation of such a lease service while guaranteeing fairness, plausible deniability and anonymity, therefore shielding the users and account renters from prosecution. To show that such a service can be practically implemented, we build an example service that we call TEEVIL leveraging Intel SGX and ZCash. Finally, we discuss defense mechanisms and challenges in the mitigation of identity lease services. For further information, please see our paper.

Charlotte
Isaac Sheff, Xinwen Wang, Haobin Ni, Robbert van Renesse, and Andrew C. Myers
Support Grand Challenges:
Secure Scaling and Performance

Charlotte is a new open framework for building parallel, interoperable blockchain systems. It supports a variety of consensus machanisms including proof of work as well as more classic distributed consensus protocols. For more information, please see our paper.

Libra
Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, and Dawn Song
Support Grand Challenges:
Secure Scaling and Performance
Confidentiality

We present Libra, the first zero-knowledge proof system that has both optimal prover time and succinct proof size/verification time. In particular, if C is the size of the circuit being proved (i) the prover time is O(C) irrespective of the circuit type, (ii) the proof size and verification time are both O(d log C) for d-depth log-space uniform circuits (such as RAM programs). In addition Libra features an one-time trusted setup that depends only on the size of the input to the circuit and not the circuit logic. Underlying Libra is a new linear-time algorithm for the prover of the interactive proof protocol by Goldwasser, Kalai and Rothblum (also known as GKR protocol), as well as an efficient approach to turn the GKR protocol to zero-knowledge using small masking polynomials. Not only does Libra have excellent asymptotics, but it is also efficient in practice. For example, our implementation shows that it takes 200 seconds to generate a proof for constructing a SHA2-based Merkle tree root on 256 leaves, outperforming all existing zero-knowledge proof systems. Proof size and verification time of Libra are also competitive. For more information, please see our paper.

CHURP (CHUrn-Robust Proactive secret sharing)
Sai Krishna Deepak Maram, Fan Zhang, Lun Wang, Andrew Low, Yupeng Zhang, Ari Juels, and Dawn Song
Support Grand Challenges:
Secure Scaling and Performance
Confidentiality

CHURP enables secure secret-sharing in dynamic settings where the committee of nodes storing a secret may change over time. Designed for blockchain settings, CHURP has communication complexity much lower than previous schemes; O(n) on-chain and O(n^2) off-chain in the optimistic case of no node failures. For more information, please see our paper.

TxProbe
Sergi Delgado-Segura, Surya Bakshi, Cristina Pérez-Solà, James Litton, Andrew Pachulski, Andrew Miller, and Bobby Bhattacharjee
Support Grand Challenges:
Secure Scaling and Performance

TxProbe is a mechanism for inferring the topology of the Bitcoin P2P network, making use of how nodes process out-of-order (or ("orphan")) transactions. It can be used to take snapshots of the network over a period of minutes. For more info, please see our paper.

Public Incompressible Encodings (PIEs)
Ethan Cecchetti, Ben Fisch, Ian Miers, and Ari Juels
Support Grand Challenges:
Authenticated Data Feeds

We present a provably secure approach to proving file replication (or other erasure coding) in distributed storage networks (DSNs). Storing multiple copies of a file F is essential in DSNs to ensure against file loss in the event of faulty servers or corrupt data. The public nature of DSNs, however, makes this goal challenging. Files must be encoded and decoded using public coins - i.e., without encryption or other secret-key operations - and retention of files by servers in the network must be verifiable. For more info, please see our paper.

The Gap Game
Itay Tsabary and Ittay Eyal
Support Grand Challenges:
Safety and Compliance

Incentive analysis in a PoW cryptocurrency, where transaction fees play a dominant role. We analyze suck systems as a game and show ("mining gaps") occur - periods of time where miners are incentivized to be idle instead of actively mining. We also show in such systems, miners are better off forming coalitions, which leads to a centralized system. For more info, please see our paper.

Project Chicago
Ari Juels, Lorenz Breidenbach, Phil Daian, Yan Ji, and Florian Tramèr
Support Grand Challenges:
Secure Scaling and Performance

Project Chicago is a new research initiative aiming to explore a question fundamental to all cryptocurrencies - what resources are being exchanged in blockchain markets, and how can we accurately price these resources? Read more at projectchicago.io.

PISA Outsourcing
Patrick McCorry, Surya Bakshi, Iddo Bentov, Andrew Miller, and Sarah Meiklejohn
Support Grand Challenges:
Secure Scaling and Performance
Safety and Compliance

The security guarantees of Payment Channel Networks (PCNs) rely on the availability of an online party to defend honest nodes in cases of a spurious disputes. PISA is a protocol for outsourcing this task to a limited third party while receiving a fair exchange receipt. For more info, please see our paper.

Ironwood
Haobin Ni, Greg Morrisett, and Robbert van Renesse
Support Grand Challenges:
Correctness by Design and Construction

Ironwood is a formal verification framework for Byzantine-fault tolerant consensus protocols implemented in Coq. Its goal is to produce formally verified implementations of consensus protocols with competitive performance while being flexible and compositional to support a wide range of protocols, including blockchain-style protocols such as Hotstuff. Ironwood utilizes domain-specific features of distributed systems through novel programming language constructs to reduce the verification effort of protocol implementation and enables verification of more practical, optimized protocols. For more info, please see our prototype

Ekiden
Raymond Cheng, Fan Zhang, Jernej Kos, Warren He, Nicholas Hynes, Noah Johnson, Ari Juels, Andrew Miller, and Dawn Song
Support Grand Challenges:
Confidentiality

Ekiden is a system that addresses these critical confidentiality and performance gaps in smart contracts by combining blockchains with Trusted Execution Environments (TEEs). Ekiden leverages a novel architecture that separates consensus from execution, enabling efficient TEE-backed confidentiality-preserving smart-contracts and high scalability. Our prototype (with Tendermint as the consensus layer) achieves example performance of 600x more throughput and 400x less latency at 1000x less cost than the Ethereum mainnet. For more information, please see our paper.

CALYPSO: Private Data Management for Decentralized Ledgers
Eleftherios Kokoris-Kogias, Enis Ceyhun Alp, Linus Gasser, Philipp Jovanovic, Ewa Syta, and Bryan Ford
Support Grand Challenges:
Confidentiality
Authenticated Data Feeds

CALYPSO introduces on-chain secrets, a novel abstraction that enforces atomic deposition of an auditable trace whenever users access confidential data. CALYPSO provides user-controlled consent management that ensures revocation atomicity and account anonymity. For further information, please see our paper.

Paralysis Proofs
Fan Zhang, Philip Daian, Gabriel Kaptchuk, Iddo Bentov, Ian Miers, and Ari Juels
Support Grand Challenges:
Confidentiality

A (3, 3)-multisignature cryptocurrency wallet experiences access-control paralysis upon loss of a single key, but a (2, 3)-multisig allows any two players to collude and steal funds from the third. Paralysis Proofs address this conundrum and others by allowing multisig parameters to be changed *securely* if users become unavailable. For more info, please see our paper.

Tesseract
Iddo Bentov, Yan Ji, Fan Zhang, Yunqi Li, Xueyuan Zhao, Lorenz Breidenbach, Philip Daian, and Ari Juels
Support Grand Challenges:
Confidentiality

We propose Tesseract, a secure real-time cryptocurrency exchange service. Existing centralized exchnge designs are vulnerable to theft of funds, while decentralized exchanges cannot offer real-time crrosschain trades. All currently deployed exchanges are also vulnerable to frontrunning attacks. Tesseract overcomes these flaws and achieves a best-of-bothworlds design by using Intel SGX as a trusted execution environment. For more info, please see our paper.

The Hydra Project
Lorenz Breidenbach, Philip Daian, Florian Tramèr, and Ari Juels
Support Grand Challenges:
Correctness by Design and Construction

Hydra is a cutting-edge Ethereum contract development framework for decentralized security and bug bounties rigorous cryptoeconomic security guarantees mitigating programmer and compiler error.

PriFi: Low-Latency Anonymity for Organizational Networks
Ludovic Barman, Italo Dacosta, Mahdi Zamani, Ennan Zhai, Apostolos Pyrgelis, Bryan Ford, Joan Feigenbaum, and Jean-Pierre Hubaux
Support Grand Challenges:
Confidentiality

Organizational networks are vulnerable to traffic analysis attacks that enable adversaries to infer sensitive information from network traffic - even if encryption is used. Typical anonymous communication networks are tailored to the Internet and are poorly suited for organizational networks. We present PriFi, an anonymous communication protocol for LANs, which protects users against eavesdroppers and provides high-performance traffic-analysis resistance. PriFi builds on Dining Cryptographers networks (DC-nets), but reduces the high communication latency of prior designs via a new client/relay/server architecture, in which the client packets remain on their usual network path without additional hops, and in which a set of remote servers assist the anonymization process without adding latency. PriFi also solves the challenge of equivocation attacks, which are not addressed by related work, by encrypting traffic based on communication history. Our evaluation shows that PriFi introduces modest latency overhead (~100ms for 100 clienrs) and is compatible with delay-sensitive applications such as Voice-over-IP. For more information, please see our paper.

CHAINIAC: Proactive Software-Update Transparency via Collectively Signed Skipchains and Verified Builds
Kirill Nikitin, Eleftherios Kokoris-Kogias, Philipp Jovanovic, Nicolas Gailly, Linus Gasser, Ismail Khoffi, Justin Cappos, and Bryan Ford
Support Grand Challenges:
Correctness by Design and Construction

CHAINIAC is a decentralized software update framework that aliminates single points of failure, enforces transparency, and provides efficient verifiability of integrity and authenticity for software-release processes. Independent witness servers collectively verify conformance of software updates to release policies, build verifiers validate the source-to-binary correspondence, and a tamper-proof release log stores collectively signed updates, thus ensuring that no release in accepted by clients before being widely disclosed and validated. The release log embodies a skipchain, a novel data structure, enabling arbitrarily out-of-date clients to efficiently validate updates and signing keys. Link to paper.

OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding
Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ewa Syta, and Bryan Ford
Support Grand Challenges:
Secure Scaling and Performance

OmniLedger is a novel scale-out decentralized ledger framework that preserves longterm security under permissionless operation by using bias-resistant public-randomness for choosing large, statistically representative shards that process transactions, and by introducing Atomix, an efficient cross-shard commit protocol, that atomically handles transactions affecting multiple shards. OmniLedger's throughput scales linearly in the number of active validators, supporting Visa-level workloads and beyond, while confirming typical transactions in under two seconds thanks to its low-latency "trust-but-verify" transaction validation mechanism. Link to our paper.

Proof-of-Personhood: Redemocratizing Permissionless Cryptocurrencies
Maria Borge, Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, and Bryan Ford
Support Grand Challenges:
Safety and Compliance

Proof-of-personhood (PoP) is a mechanism that binds physical entities to virtual identities in a way that enables accountability while preserving anonymity. Proof-of-personhood can be used as a democratic alternative to the commonly used proof-of-work or proof-of-stake approaches to create secure identities in permissionless cryptocurrencies. The prototype cryptocurrency to PoPCoin utilizes PoP in its consensus layer showing how a continuously fair and democratic wealth creation process could look like which paves the way for experimental basic income infrastructure. Please see our paper.

Sprites and State Channels
Andrew Miller, Iddo Bentov, Ranjit Kumaresan, Christopher Cordi, and Patrick McCorry
Support Grand Challenges:
Safety and Compliance
Secure Scaling and Performance

Off-chain payment channel networks (PCNs) are a leading approach for improving the scalability of blockchains. Sprites is an innovative construction that reduces the worst-case lockup time during which, funds must be held in escrow for a PCN payment. For more info, please see our paper.

Miniature World: A Test Bed for Simulating Real World Blockchain
Adem Efe Gencer, Ittay Eyal, Emin Gün Sirer, and Robbert van Renesse
Support Grand Challenges:
Secure Scaling and Performance

Miniature World is a large blockchain emulation test bed at Cornell University consisting of ~1000 nodes. This test bed enables us to run experiments on different blockchains, and a variety of use cases, using realistic internet latencies to evaluate real world scenarios (as referenced above for Bitcoin-NG). We make Miniature World available for our Industry Sponsors to evaluate various block chains and their use cases. For more info about becoming an IC3 Industry Sponsor, please see our website.

Town Crier: Authenticated Data Feeds for Smart Contracts
Fan Zhang, Ethan Cecchetti, Kyle Croman, Ari Juels, and Elaine Shi
Support Grand Challenges:
Confidentiality
Authenticated Data Feeds
Sound Migration

In order to reason about the real world, smart contracts in cryptocurrency systems will rely on informational input from what we call authenticated data feeds (ADFs); such information can include stock prices, meteorological reports, news, and other current events. It is therefore important that an ADF be trustworthy, in the sense of providing security against manipulation by an attacker attempting to influence the outcome of a contract. By utilizing trusted hardware to provide reliable, digitally signed attestations on data to client contracts, the Town Crier system can serve as a trustworthy ADF under minimal trust assumptions about its operator. For further details, please see our paper.

Gyges: Crime in Decentralized Smart Contracts
Ari Juels, Ahmed Kosba, and Elaine Shi
Support Grand Challenges:
Safety and Compliance

Two of the most widely desired goals for "Bitcoin 2.0" are privacy and more expressive smart contracts. Many uses of cryptocurrency have a clear and legitimate need for privacy (e.g., financial service companies are expected to protect the privacy of their clients' transactions). General purpose smart contract programming frameworks make it easy to tinker, prototype, and search for the next "killer application" for cryptocurrencies. These two directions seem to be at odds with each other; however, through the use of sophisticated cryptography (like zero knowledge proofs and multi-party computation), we explore how to achieve both goals at once. For further details, please see our paper.

ByzCoin: Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing
Eleftherios Kokoris Kogias, Philipp Jovanovic, Nicolas Gailly, Ismail Khoffi, Linus Gasser, and Bryan Ford
Support Grand Challenges:
Secure Scaling and Performance

ByzCoin is a novel Byzantine consensus protocol that leverages scalable collective signing to commit Bitcoin transactions irreversibly within seconds while preserving Bitcoin's open membership by dynamically forming hash power-proportionate consensus groups that represent recently-successful block miners. ByzCoin mitigates double spending and selfish mining attacks by producing collectively signed transaction blocks within one minute of transaction submission. ByzCoin achieves a throughput higher than Paypal currently handles (>700 tx/s), with a confirmation latency of 15-20 seconds. Learn more at USENIX 2016.

Hawk: Privacy-Preserving Blockchain & Smart Contracts
Ahmed Kosba, Andrew Miller, Elaine Shi, Zikai Wen, and Charalampos Papamanthou
Support Grand Challenges:
Correctness by Design and Construction
Confidentiality

Existing blockchain-based cryptocurrencies such as Bitcoin and Ethereum store all financial transactions in the clear on the blockchain. This compromises the privacy of financial transactions, which is essential in numerous applications. Hawk is a blockchain-based smart contract system that stores encrypted transactions on the blockchain, and relies on cryptography to retain the security of the cryptocurrency. For more info, please see our paper.

Solidus: Confidential Financial Transaction Settlement on a Distributed Ledgers
Ethan Cecchetti, Fan Zhang, Yan Ji, Ahmed Kosba, Ari Juels, and Elaine Shi
Support Grand Challenges:
Secure Scaling and Performance
Confidentiality

Solidus is a cryptocurrency ("blockchain") that can be run by a confederation or consortium of trustworthy entities--banks, governments, auditors, etc. While it retains some of the benefits of decentralization, Solidus offers higher performance and tighter governance and control than existing cryptocurrencies such as Bitcoin. Many successful peer-to- peer technologies have historically been eclipsed or supplanted by centralized or commercial systems (e.g., in the online music industry). Solidus addresses the possibility and desire by many financial institutions that cryptocurrencies and contracts will follow a similar path. For more info, please see the Solidus presentation at our 2016 IC3 Retreat in NYC.

Fruitchain: A new Approach for Incentive Compatible Blockchains
Rafael Pass and Elaine Shi
Support Grand Challenges:
Secure Scaling and Performance

Most of today's blockchains, such as Bitcoin, are not "incentive compatible", meaning they are quite vulnerable to strategic gaming by dishonest adversaries. For example, IC3 has proven that the Bitcoin blockchain can be compromised by miners or mining pools with much less than 50% of the mining hash power. Fruitchain is an innovative blockchain methodology that discourages dishonest gaming, by making it extremely unprofitable for an adversary with less than 50% of the hash power, achieving an epsilon-equilibrium or near-Nash equilibrium. For more info, please see the Fruitchain presentation by IC3 co-director Professor Elaine Shi at our 2016 IC3 Retreat in NYC.

FLAC: A Calculus for Flow-Limited Authorization
Owen Arden and Andrew C. Myers
Support Grand Challenges:
Correctness by Design and Construction

Real-world applications routinely make authorization decisions based on dynamic computation. Integrity of the system might be compromised if attackers can improperly influence the authorizing computation. Confidentiality can also be compromised by authorization, since authorization decisions are often based on sensitive data such as membership lists and passwords. Flow-Limited Authorization Calculus (FLAC) is both a simple, expressive model for reasoning about dynamic authorization and also a language for securely implementing various authorization mechanisms. FLAC provides strong end-to- end information security guarantees even for programs that incorporate and implement rich dynamic authorization mechanisms. For more info, please see the presentation by Professor Andrew Myers “Verifying Information Security of Code in Dynamic Systems” at our 2016 IC3 Retreat in NYC.

HoneyBadgerBFT: The Honey Badger of BFT Protocols
Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song
Support Grand Challenges:
Secure Scaling and Performance

HoneyBadgerBFT is the first practical asynchronous BFT protocol, which guarantees liveness without making any timing assumptions. We base our solution on a novel atomic broadcast protocol that achieves optimal asymptotic efficiency. We present an implementation and experimental results to show our system can achieve throughput of tens of thousands of transactions per second, and scales to over a hundred nodes on a wide area network. We even conduct BFT experiments over Tor, without needing to tune any parameters. Unlike the alternatives, HoneyBadgerBFT simply does not care about the underlying network. For more info, please see our paper.

Bitcoin-NG: A Next-generation Blockchain Protocol
Ittay Eyal, Adem Efe Gencer, Emin Gun Sirer, and Robbert van Renesse
Support Grand Challenges:
Secure Scaling and Performance

Bitcoin-NG is a new protocol pioneered by IC3. It addresses the scalability bottleneck of Bitcoin by enabling the Bitcoin network to achieve the highest throughput allowed by the network conditions. Paradoxically, not only does it improve transaction throughput, it also reduces transaction latencies -- it is possible to get an initial transaction confirmation in seconds rather than in minutes. And it does so without changing Bitcoin’s open architecture and trust model. Our blockchain test bed Miniature World simulated Bitcoin-NG at 15% the size of the operational Bitcoin system, where we showed that Bitcoin–NG is only limited by the network. For more info, please see our paper.