We present the first in-depth empirical characterization of the costs of trading on a decentralized exchange (DEX). Using quoted prices from the Uniswap Labs interface for two pools — USDC-ETH (5bps) and PEPE-ETH (30bps) — we evaluate the efficiency of trading on DEXs. Our main tool is slippage — the difference between the realized execution price of a trade, and its quoted price — which we breakdown into its benign and adversarial components. We also present an alternative way to quantify and identify slippage due to adversarial reordering of transactions, which we call reordering slippage, that does not require quoted prices or mempool data to calculate. We find that the composition of transaction costs varies tremendously with the trade’s characteristics. Specifically, while for small swaps, gas costs dominate costs, for large swaps price-impact and slippage account for the majority of it. Moreover, when trading PEPE, a popular ‘memecoin’, the probability of adversarial slippage is about 80% higher than when trading a mature asset like USDC. Overall, our results provide preliminary evidence that DEXs offer a compelling trust-less alternative to centralized exchanges for trading digital assets. For more information, see our work. Show Less

Cuttlefish addresses several limitations of existing consensus-less and consensus-minimized decentralized ledgers, including restricted programmability and the risk of deadlocked assets. The key insight of Cuttlefish is that consensus in blockchains is necessary due to contention, rather than multiple owners of an asset as suggested by prior work. Previous proposals proactively use consensus to prevent contention from blocking assets, taking a pessimistic approach. In contrast, Cuttlefish introduces collective objects and multi-owner transactions that can offer most of the functionality of classic blockchains when objects transacted on are not under contention. Additionally, in case of contention, Cuttlefish proposes a novel `Unlock' protocol that significantly reduces the latency of unblocking contented objects. By leveraging these features, Cuttlefish implements consensus-less protocols for a broader range of transactions, including asset swaps and multi-signature transactions, which were previously believed to require consensus. For more details, see our paper. Show Less

Leader-based consensus algorithms are fast and efficient under normal conditions, but lack robustness to adverse conditions due to their reliance on timeouts for liveness. We present QuePaxa, the first protocol offering state-of-the-art normal case efficiency without depending on timeouts. QuePaxa uses a novel randomized asynchronous consensus core to tolerate adverse conditions such as denial-of-service (DoS) attacks, while a one-round-trip fast path preserves the normal-case efficiency of Multi-Paxos or Raft. By allowing simultaneous proposers without destructive interference, and using short hedging delays instead of conservative timeouts to limit redundant effort, QuePaxa permits rapid recovery after leader failure without risking costly view changes due to false timeouts. By treating leader choice and hedging delay as a multi-armed-bandit optimization, QuePaxa achieves responsiveness to prevalent conditions, and can choose the best leader even if the current one has not failed. Experiments with a prototype confirm that QuePaxa achieves normal-case LAN and WAN performance of 584k and 250k cmd/sec in throughput, respectively, comparable to Multi-Paxos. Under conditions such as DoS attacks, misconfigurations, or slow leaders that severely impact existing protocols, we find that QuePaxa remains live with median latency under 380ms in WAN experiments. For more information, see our paper. Show Less

Motivated by the extended deployment of authenticated data structures (e.g., Merkle Patricia Tries) for verifying massive amounts of data in blockchain systems, we begin a systematic study of the I/O efficiency of such systems. We first explore the fundamental limitations of memory checking, a previously-proposed abstraction for verifiable storage, in terms of its locality—a complexity measure that we introduce for the first time and is defined as the number of non-contiguous memory regions a checker must query to verifiably answer a read or a write query. Our central result is an Ω(log𝑛/log log𝑛) lower bound for the locality of any memory checker. Then we turn our attention to (dense and sparse) Merkle trees, one of the most celebrated memory checkers, and provide stronger lower bounds for their locality. For example, we show that any dense Merkle tree layout will have average locality at least 1/3 log𝑛. Furthermore, if we allow node duplication, we show that if any write operation has at most polylog complexity, then the read locality cannot be less than log𝑛/log log𝑛. Our lower bounds help us construct two new locality-optimized authenticated data structures (DupTree and PrefixTree) which we implement and evaluate on random operations and real workloads, and which are shown to outperform traditional Merkle trees, especially as the number of leaves increases. For more details, see our paper. Show Less

We introduce Lanturn - a general purpose adaptive learning-based framework for measuring the cryptoeconomic security of composed decentralized-finance (DeFi) smart-contracts. Lanturn discovers strategies comprising of concrete transactions for extracting economic value from smart contracts interacting with a particular transaction environment. We formulate the strategy discovery as a black-box optimization problem and leverage a novel adaptive learning-based algorithm to address it. Lanturn features three key properties. First, it needs no contract-specific heuristics or reasoning, due to our black-box formulation of cryptoeconomic security. Second, it utilizes a simulation framework that operates natively on blockchain state and smart contract machine code, such that transactions returned by Lanturn’s learning-based optimization engine can be executed on-chain without modification. Finally, Lanturn is scalable in that it can explore strategies comprising a large number of transactions that can be reordered or subject to insertion of new transactions. We evaluate Lanturn on the historical data of the biggest and most active DeFi Applications - Sushiswap, UniswapV2, UniswapV3, and AaveV2. Our results show that Lanturn not only rediscovers existing, well-known strategies for extracting value from smart contracts, but also discovers new strategies that are previously undocumented. Lanturn also consistently discovers higher value than evidenced in the wild, surpassing a natural baseline computed using value extracted by bots and other strategic agents. For details, see our work. Show Less

Digital financial services have catalyzed financial inclusion in Africa. Commonly implemented as a mobile wallet service referred to as mobile money (MoMo), the technology provides enormous benefits to its users, some of whom have long been unbanked. While the benefits of mobile money services have largely been documented, the challenges that arise - especially in the interactions between human stakeholders - remain relatively unexplored. In this study, we investigate the practices of mobile money users in their interactions with mobile money agents. We conduct 72 structured interviews in Kenya and Tanzania (n=36 per country). The results show that users and agents design workarounds in response to limitations and challenges that users face within the ecosystem. These include advances or loans from agents, relying on the user-agent relationships in place of legal identification requirements, and altering the intended transaction execution to improve convenience. Overall, the workarounds modify one or more of what we see as the core components of mobile money - the user, the agent, and the transaction itself. The workarounds pose new risks and challenges for users and the overall ecosystem. The results suggest a need for rethinking privacy and security of various components of the ecosystem, as well as policy and regulatory controls to safeguard interactions while ensuring the usability of mobile money. For more information, see our paper. Show Less

In the past decade, blockchains have seen various financial and technological innovations, with cryptocurrencies reaching a market cap of over 1 trillion dollars. However, scalability is one of the key issues hindering the deployment of blockchains in many applications. To improve the throughput of the transactions, zkRollups and zkEVM techniques using the cryptographic primitive of zero-knowledge proofs (ZKPs) have been proposed and many companies are adopting these technologies in the layer-2 solutions. However, in these technologies, the proof generation of the ZKP is the bottleneck and the companies have to deploy powerful machines with TBs of memory to batch a large number of transactions in a ZKP. In this work, we improve the scalability of these techniques by proposing new schemes of fully distributed ZKPs. Our schemes can improve the efficiency and the scalability of ZKPs using multiple machines, while the communication among the machines is minimal. With our schemes, the ZKP generation can be distributed to multiple participants in a model similar to the mining pools. Our protocols are based on Plonk, an efficient zero-knowledge proof system with a universal trusted setup. The first protocol is for data-parallel circuits. For a computation of M sub-circuits of size T each, using M machines, the prover time is O(T log T + M log M), while the prover time of the original Plonk on a single machine is O(MT log(MT)). Our protocol incurs only O(1) communication per machine, and the proof size and verifier time are both O(1), the same as the original Plonk. Moreover, we show that with minor modifications, our second protocol can support general circuits with arbitrary connections while preserving the same proving, verifying, and communication complexity. The technique is general and may be of independent interest for other applications of ZKP. We implement Pianist (Plonk vIA uNlimited dISTribution), a fully distributed ZKP system using our protocols. Pianist can generate the proof for 8192 transactions in 313 seconds on 64 machines. This improves the scalability of the Plonk scheme by 64×. The communication per machine is only 2.1 KB, regardless of the number of machines and the size of the circuit. The proof size is 2.2 KB and the verifier time is 3.5 ms. We further show that Pianist has similar improvements for general circuits. On a randomly generated circuit with 2 25 gates, it only takes 5 s to generate the proof using 32 machines, 24.2× faster than Plonk on a single machine. For more details, see our work. Show Less

Using proprietary data from a dominant crypto exchange in India and the country’s Household Inflation Expectations Survey, we document a large positive correlation between inflation expectations and individual cryptocurrency purchases. The effect is concentrated in Bitcoin (BTC) and Tether (USDT) and among households in states with higher GDP per capita. There are no significant differences across gender or age groups. The effect also has causal interpretations, as confirmed by using idiosyncratic shocks in current perceived inflation as an instrumental variable for long-term inflation expectations. Our findings suggest that certain cryptocurrencies have already been perceived by households as inflation hedges. For more details, see our work. Show Less

We present Colordag, a blockchain protocol where following the prescribed strategy is, with high probability, a best response as long as all miners have less than 1/2 of the mining power. We prove the correctness of Colordag even if there is an extremely powerful adversary who knows future actions of the scheduler - specifically, when agents will generate blocks and when messages will arrive. The state-of-the-art protocol, Fruitchain, is an epsilon-Nash equilibrium as long as all miners have less than 1/2 of the mining power. However, there is a simple deviation that guarantees that deviators are never worse off than they would be by following Fruitchain, and can sometimes do better. Thus, agents are motivated to deviate. Colordag implements a solution concept that we call epsilon-sure Nash equilibrium and does not suffer from this problem. Because it is an epsilon-sure Nash equilibrium, Colordag is an epsilon Nash equilibrium and with probability (1 - epsilon) is a best response. For more information, see our paper. Show Less

Oblivious sorting is arguably the most important building block in the design of efficient oblivious algorithms. We propose new oblivious sorting algorithms for hardware enclaves. Our algorithms achieve asymptotic optimality in terms of both computational overhead and the number of page swaps the enclave has to make to fetch data from insecure memory or disk. We also aim to minimize the concrete constants inside the big-O. One of our algorithms achieve bounds tight to the constant in terms of the number of page swaps. We have implemented our algorithms and made them publicly available through open source. In comparison with (an unoptimized version of) bitonic sort, which is asymptotically non-optimal but the de facto algorithm used in practice, we achieve a speedup of 2000 times for 12 GB inputs. For more details, see our paper. Show Less

We introduce dynamic incentives into distributed systems via formally incorporating (decentralized) suppliers/users' reputation. Reputation aligns contributors’ incentives with platform welfare and makes myopic service providers internalize their long-term impacts. Starting with Proof-of-Stake (PoS) as an example, we show that Web3 reputation allows networks to support more throughput with same amount of staking, and averts cryptocurrency price shocks to suppliers by transferring cyclicality risks in transaction fees to users. We further analyze how dynamic incentives mitigate moral hazard in decentralized reporting game (e.g., for modeling oracle networks), and demonstrate how decentralization solves wealth concentration caused by dynamic incentives. Our findings validate proposals of adding Web3 reputation to distributed networks for efficiency improvements and long-run sustainability. For information, see our work. Show Less

On-chain mixers, such as Tornado Cash (TC), have become a popular privacy solution for many non-privacy-preserving blockchain users. These mixers enable users to deposit a fixed amount of coins and withdraw them to another address, while effectively reducing the linkability between these addresses and securely obscuring their transaction history. However, the high cost of interacting with existing on-chain mixer smart contracts prohibits standard users from using the mixer, mainly due to the use of computationally expensive cryptographic primitives. For instance, the deposit cost of TC on Ethereum is approximately 1.1M gas (i.e., 66 USD in June 2023), which is 53× higher than issuing a base transfer transaction. In this work, we introduce the Merkle Pyramid Builder approach, to incrementally build the Merkle tree in an on-chain mixer and update the tree per batch of deposits, which can therefore decrease the overall cost of using the mixer. Our evaluation results highlight the effectiveness of this approach, showcasing a significant reduction of up to 7× in the amortized cost of depositing compared to state-of-the-art on-chain mixers. Importantly, these improvements are achieved without compromising users’ privacy. Furthermore, we propose the utilization of verifiable computations to shift the responsibility of Merkle tree updates from on-chain smart contracts to off-chain clients, which can further reduce deposit costs. Additionally, our analysis demonstrates that our designs ensure fairness by distributing Merkle tree update costs among clients over time. For more details, please see our paper. Show Less

Contact discovery is a crucial component of social applications, facilitating interactions between registered contacts. This work introduces Arke, a novel approach to contact discovery that addresses the limitations of existing solutions in terms of privacy, scalability, and reliance on trusted third parties. Arke ensures the unlinkability of user interactions, mitigates enumeration attacks, and operates without single points of failure or trust. Notably, Arke is the first contact discovery system whose performance is independent of the total number of users and the first that can operate in a Byzantine setting. It achieves its privacy goals through an unlinkable handshake mechanism built on top of an identity-based non-interactive key exchange. By leveraging a custom distributed architecture, Arke forgoes the expense of consensus to achieve scalability while maintaining consistency in a Byzantine fault tolerant environment. Performance evaluations demonstrate that Arke can support enough throughput to operate at a planetary scale while maintaining sub-second latencies in a large geo-distributed setting. For more details, see our paper. Show Less

Nakamoto's consensus protocol works in a permissionless model and tolerates Byzantine failures, but only offers probabilistic agreement. Recently, the Sandglass protocol has shown such weaker guarantees are not a necessary consequence of a permissionless model; yet, Sandglass only tolerates benign failures, and operates in an unconventional partially synchronous model. We present Gorilla Sandglass, the first Byzantine tolerant consensus protocol to guarantee, in the same synchronous model adopted by Nakamoto, deterministic agreement and termination with probability 1 in a permissionless setting. We prove the correctness of Gorilla by mapping executions that would violate agreement or termination in Gorilla to executions in Sandglass, where we know such violations are impossible. Establishing termination proves particularly interesting, as the mapping requires reasoning about infinite executions and their probabilities. For further details, see our work. Show Less

Humanitarian organizations provide aid to people in need. To use their limited budget efficiently, their distribution processes must ensure that legitimate recipients cannot receive more aid than they are entitled to. Thus, it is essential that recipients can register at most once per aid program. Taking the International Committee of the Red Cross’s aid distribution registration process as a use case, we identify the requirements to detect double registration without creating new risks for aid recipients. We then design Janus, which combines privacy-enhancing technologies with biometrics to prevent double registration in a safe manner. Janus does not create plaintext biometric databases and reveals only one bit of information at registration time (whether the user registering is present in the database or not). We implement and evaluate three instantiations of Janus based on secure multiparty computation, somewhat homomorphic encryption, and trusted execution environments. We demonstrate that they support the privacy, accuracy, and performance needs of humanitarian organizations. We compare Janus with existing alternatives and show it is the first system that provides the accuracy our scenario requires while providing strong protection. For details, see our work. Show Less

We investigate the theoretical and empirical relationships between activity in on-chain markets and pricing in off-chain cryptocurrency markets (e.g., ETH/USD prices). The motivation is to develop methods for proxying off-chain market data using data and computation that is in principle verifiable on-chain and could provide an alternative approach to blockchain price oracles. We explore relationships in PoW mining, PoS validation, block space markets, network decentralization, usage and monetary velocity, and on-chain Automated Market Makers (AMMs). We select key features from these markets, which we analyze through graphical models, mutual information, and ensemble machine learning models to explore the degree to which off-chain pricing information can be recovered entirely on-chain. We find that a large amount of pricing information is contained in on-chain data, but that it is generally hard to recover precise prices except on short time scales of retraining the model. We discuss how even noisy information recovered from on-chain data could help to detect anomalies in oracle-reported prices on-chain. For more details, see our paper. Show Less

We study economies of scale in liquidity provision on decentralized exchanges, focusing on the impact of fixed transaction costs such as gas prices on liquidity providers (LPs). Small LPs are disproportionately affected by the fixed cost, resulting in liquidity supply fragmentation between low- and high-fee pools. Analyzing Uniswap data, we find that high-fee pools attract 56% of liquidity supply but execute only 35% of trading volume. Large (institutional) LPs dominate low-fee pools, frequently adjusting positions in response to substantial trading volume. In contrast, small (retail) LPs converge to high-fee pools, accepting lower execution probabilities to mitigate smaller liquidity management costs. For more details, see our work. Show Less

Public randomness is a fundamental component in many cryptographic protocols and distributed systems and often plays a crucial role in ensuring their security, fairness, and transparency properties. Driven by the surge of interest in blockchain and cryptocurrency platforms and the usefulness of such component in those areas, designing secure protocols to generate public randomness in a distributed manner has received considerable attention in recent years. This paper presents a systematization of knowledge on the topic of public randomness with a focus on cryptographic tools providing public verifiability and key themes underlying these systems. We provide concrete insights on how state-of-the-art protocols achieve this task efficiently in an adversarial setting and present various research gaps that may be suitable for future research. For details, see our work. Show Less

Traditional blockchains grant the miner of a block full control not only over which transactions but also their order. This constitutes a major flaw discovered with the introduction of decentralized finance and allows miners to perform MEV attacks. In this paper, we address the issue of sandwich attacks by providing a construction that takes as input a blockchain protocol and outputs a new blockchain protocol with the same security but in which sandwich attacks are not profitable. Furthermore, our protocol is fully decentralized with no trusted third parties or heavy cryptography primitives and carries a linear increase in latency and minimum computation overhead. For more details, see our paper. Show Less

Maximal extractable value (MEV) in the context of blockchains and cryptocurrencies refers to the highest potential profit that an actor, particularly a miner or validator, can achieve through their ability to include, exclude, or re-order transactions within the blocks. MEV has become a topic of concern within the Web3 community as it impacts the fairness and security of the cryptocurrency ecosystem. In this work, we propose and explore techniques that utilize randomized permutations to shuffle the order of transactions of a committed block before they are executed. We also show that existing MEV mitigation approaches using an encrypted mempool can be readily extended by permutation-based techniques, thus providing multi-layer protection. With a focus on BFT consensus, we then propose BlindPerm, a framework enhancing an encrypted mempool with permutation at essentially no additional overheads and present various optimizations. Finally, we demonstrate how to extend our mitigation technique to support PoW longest-chain consensus protocols. For more information, see our paper. Show Less

As the prevalence of data analysis grows, safeguarding data privacy has become a paramount concern. Consequently, there has been an upsurge in the development of mechanisms aimed at privacy-preserving data analyses. However, these approaches are task-specific, designing algorithms for new tasks is a cumbersome process. As an alternative, one can create synthetic data that is (ideally) devoid of private information. This paper focuses on privacy-preserving data synthesis (PPDS) by providing a comprehensive overview, analysis, and discussion of the field. Specifically, we put forth a master recipe that unifies two prominent strands of research in PPDS - statistical methods and deep learning (DL)-based methods. Under the master recipe, we further dissect the statistical methods into choices of modeling and representation, and investigate the DL-based methods by different generative modeling principles. To consolidate our findings, we provide comprehensive reference tables, distill key takeaways, and identify open problems in the existing literature. In doing so, we aim to answer the following questions - What are the design principles behind different PPDS methods? How can we categorize these methods, and what are the advantages and disadvantages associated with each category? Can we provide guidelines for method selection in different real-world scenarios? We proceed to benchmark several prominent DL-based methods on the task of private image synthesis and conclude that DP-MERF is an all-purpose approach. Finally, upon systematizing the work over the past decade, we identify future directions and call for actions from researchers. For further details, see our work. Show Less

Centralized data silos are not only becoming prohibitively expensive but also raise issues of data ownership and data availability. These developments are affecting the industry, researchers, and ultimately society in general. Decentralized storage solutions present a promising alternative. Furthermore, such systems can become a crucial layer for new paradigms of edge-centric computing and web3 applications. Decentralized storage solutions based on p2p networks can enable scalable and self-sustaining open-source infrastructures. However, like other p2p systems, they require well-designed incentive mechanisms for participating peers. These mechanisms should be not only effective but also fair in regard to individual participants. Even though several such systems have been studied in deployment, there is still a lack of systematic understanding regarding these issues. We investigate the interplay between incentive mechanisms, network characteristics, and fairness of peer rewards. In particular, we identify and evaluate three core and up-to-date reward mechanisms for moving data in p2p networks - distance-based payments, reciprocity, and time-limited free service. Distance-based payments are relevant since libp2p Kademlia, which enables distance-based algorithms for content lookup and retrieval, is part of various modern p2p systems. We base our model on the Swarm network that uses a combination of the three mechanisms and serves as inspiration for our Tit-for-Token model. We present our Tit-for-Token model and develop a tool to explore the behaviors of these payment mechanisms. Our evaluation provides novel insights into the functioning and interplay of these mechanisms and helps. Based on these insights, we propose modifications to these mechanisms that better address fairness concerns and outline improvement proposals for the Swarm network. For more information, please see our paper. Show Less

Secret sharing has been a promising tool in cryptographic schemes for decades. It allows a dealer to split a secret into some pieces of shares that carry no sensitive information on their own when being treated individually but lead to the original secret when having a sufficient number of them together. Existing schemes lack considering a guaranteed delay prior to secret reconstruction and implicitly assume once the dealer shares the secret, a sufficient number of shareholders will get together and recover the secret at their wish. This, however, may lead to security breaches when a timely reconstruction of the secret matters as the early knowledge of a single revealed share is catastrophic assuming a threshold adversary. This paper presents the notion of timed secret sharing (TSS), providing lower and upper time bounds for secret reconstruction with the use of time-based cryptography. The recent advances in the literature including short-lived proofs [Asiacrypt 2022], enable us to realize an upper time bound shown to be useful in breaking public goods game, an inherent issue in secret sharing-based systems. Moreover, we establish an interesting trade-off between time and fault tolerance in a secret sharing scheme by having dealer gradually release additional shares over time, offering another approach with the same goal. We propose several constructions that offer a range of security properties while maintaining practical efficiency. Our constructions leverage a variety of techniques and state-of-the-art primitives. For further details, see our work. Show Less

We present a systematic approach to detect fake transactions on cryptocurrency exchanges by exploiting robust statistical and behavioral regularities associated with authentic trading. Our sample consists of 29 centralized exchanges, among which the regulated ones feature transaction patterns consistently observed in financial markets and nature. In contrast, unregulated exchanges display abnormal first-significant-digit distributions, size rounding, and transaction tail distributions, indicating widespread manipulation unlikely driven by specific trading strategy or exchange heterogeneity. We then quantify the wash trading on each unregulated exchange, which averaged over 70% of the reported volume. We further document how these fabricated volumes (trillions of dollars annually) improve exchange ranking, temporarily distort prices, and relate to exchange characteristics (e.g., age and user base), market conditions, and regulation. Overall, our study cautions against potential market manipulations on centralized crypto exchanges with concentrated power and limited disclosure requirements, and highlights the importance of FinTech regulation. For further details, see our work. Show Less

Oracles are software components that enable data exchange between siloed blockchains and external environments, enhancing smart contract capabilities and platform interoperability. Integration through oracle networks for blockchain and DeFi platforms allows them to be informationally and financially connected to other blockchain ecosystems and off-chain environments. Using hand-collected data on hundreds of DeFi protocols and data from the market for decentralized oracle networks (DONs), we document that oracle integration generally leads to positive financial and economic ramifications. Additionally, our initial evidence suggests that symbiotic gains from enhanced interoperability between protocols on a given chain and, depending on the mass of integrated protocols, among integrated chains, translate to positive network effects. Moreover, oracle integration appears to improve risk-sharing without significant contagions; integrated protocols appear more resilient than nonintegrated protocols during times of crisis. We draw parallels between oracle integration and international economic and financial integration, offering hopefully timely insight for regulators, entrepreneurs, and practitioners in the emerging space blockchains, DeFi, and Web3 ecosystems. For further details, see our work. Show Less

At the core of each blockchain system, parties communicate through a peer-to-peer (P2P) overlay. Unfortunately, recent evidence suggests these P2P overlays represent a significant bottleneck for transaction throughput and scalability. Furthermore, they enable a number of attacks. We argue that these performance and security problems arise because current P2P overlays cannot fully capture the complexity of a blockchain system as they do not offer flexibility to accommodate node heterogeneity. We propose a novel approach to address these issues - P2P Overlay Domains with Sovereignty (PODS), which allows nodes in a single overlay to belong to multiple heterogeneous groups, called domains. Each domain features its own set of protocols, tailored to the characteristics and needs of its nodes. To demonstrate the effectiveness of PODS, we design and implement two novel node discovery protocols - FedKad and SovKad. Using a custom simulator, we show that node discovery using PODS (SovKad) architecture outperforms both single overlay (Kademlia) and multi-overlay (FedKad) architectures in terms of hop count and success rate, though FedKad requires slightly less bandwidth. For more details, see our paper. Show Less

This paper presents BBCA-LEDGER*, a Byzantine log replication technology for partially synchronous networks enabling blocks to be broadcast in parallel, such that each broadcast is finalized independently and instantaneously into an individual slot in the log. Every finalized broadcast is eventually committed to the total ordering, so that all network bandwidth has utility in disseminating blocks. Finalizing log slots in parallel achieves both high throughput and low latency. BBCA-LEDGER is composed of two principal protocols that interweave together, a low-latency/high-throughput happy path, and a high-throughput DAG-based fallback path. The happy path employs a novel primitive called BBCA, a consistent broadcast enforcing unique slot numbering. In steady state, BBCA ensures that a transaction can be committed with low latency, in just 3 network steps. Under network partitions or faults, we harness recent advances in BFT and build a fallback mechanism on a direct acyclic graph (DAG) created by BBCA broadcasts. In this manner, BBCA-LEDGER exhibits the throughput benefits of DAG-based BFT in face of gaps. For further details, see our work. Show Less

We investigate the feasibility of employing large language models (LLMs) for conducting the security audit of smart contracts, a traditionally time-consuming and costly process. Our research focuses on the optimization of prompt engineering for enhanced security analysis, and we evaluate the performance and accuracy of LLMs using a benchmark dataset comprising 52 Decentralized Finance (DeFi) smart contracts that have previously been compromised. Our findings reveal that, when applied to vulnerable contracts, both GPT-4 and Claude models correctly identify the vulnerability type in 40% of the cases. However, these models also demonstrate a high false positive rate, necessitating continued involvement from manual auditors. The LLMs tested outperform a random model by 20% in terms of F1-score. To ensure the integrity of our study, we conduct mutation testing on five newly developed and ostensibly secure smart contracts, into which we manually insert two and 15 vulnerabilities each. This testing yielded a remarkable best-case 78.7% true positive rate for the GPT-4-32k model. We tested both, asking the models to perform a binary classification on whether a contract is vulnerable, and a non-binary prompt. We also examined the influence of model temperature variations and context length on the LLM’s performance. Despite the potential for many further enhancements, this work lays the groundwork for a more efficient and economical approach to smart contract security audits. For more details, please see our paper. Show Less

Society appears to be on the verge of recognizing the need for control over sensitive data in modern web applications. Recently, many systems claim to give control to individuals, promising the preeminent goal of data sovereignty. However, despite recent attention, research and industry efforts are fragmented and lack a holistic system overview. In this paper, we provide the first transecting systematization of data sovereignty by drawing from a dispersed body of knowledge. We clarify the field by identifying its three main areas - (i) decentralized identity, (ii) decentralized access control and (iii) policy-compliant decentralized computation. We find that literature lacks a cohesive set of formal definitions. Each area is considered in isolation, and priorities in industry and academia are not aligned due to a lack of clarity regarding user control. To solve this issue, we propose formal definitions for each sub-area. By highlighting that data sovereignty transcends the domain of decentralized identity, we aim to guide future works to embrace a broader perspective on user control. In each section, we augment our definition with security and privacy properties, discuss the state of the art and proceed to identify open challenges. We conclude by highlighting synergies between areas, emphasizing the real-world benefit obtained by further developing data sovereign systems. For details, see our work. Show Less

In May 2022, an apparent speculative attack, followed by market panic, led to the precipitous downfall of UST, one of the most popular stablecoins at that time. However, UST is not the only stablecoin to have been depegged in the past. Designing resilient and long-term stable coins, therefore, appears to present a hard challenge. To further scrutinize existing stablecoin designs and ultimately lead to more robust systems, we need to understand where volatility emerges. Our work provides a game-theoretical model aiming to help identify why stablecoins suffer from a depeg. This game-theoretical model reveals thatstablecoins have different price equilibria depending on the coin’s architecture and mechanism to minimize volatility. Moreover, our theory is supported by extensive empirical data, spanning 1 year. To that end, we collect daily prices for 22 stablecoins and on-chain data from five blockchains including the Ethereum and the Terra blockchain. For more details, see our paper. Show Less

The current method for building software infrastructure in disaggregated data centers involves creating new virtual machine monitors or operating system kernels that make the underlying hardware appear as a group of logical servers. Although this approach is effective for maintaining backward compatibility, we suggest that it would be more beneficial to invest in redesigning the applications themselves to be disaggregated along physical boundaries. We propose uniservices, a new programming paradigm that utilizes the actor model and is highly specialized for a single type of hardware resource for disaggregated architecture. Applications would be built from these uniservices, communicating over fast interconnects and a shared log. This approach simplifies operating systems while making better use of available hardware resources. For information, see our paper. Show Less

The average cryptocurrency user today faces a difficult choice between centralized custodial wallets, which are notoriously prone to spontaneous collapse, or cumbersome self-custody solutions, which if not managed properly can cause a total loss of funds. In this paper, we present a “best of both worlds” cryptocurrency wallet design that looks like, and inherits the user experience of, a centralized custodial solution, while in fact being entirely decentralized in design and implementation. In our design, private keys are not stored on any device, but are instead derived directly from a user’s authentication factors, such as passwords, soft tokens (e.g., Google Authenticator), hard tokens (e.g., YubiKey), or out-of-band authentication (e.g., SMS). Public parameters (salts, one-time pads, etc.) needed to access the wallet can be safely stored in public view, such as on a public blockchain, thereby providing strong availability guarantees. Users can then simply “log in” to their decentralized wallet on any device using standard credentials and even recover from lost credentials, thereby providing the usability of a custodial wallet with the trust and security of a decentralized approach. For details, please see our work. Show Less

Since the introduction of bcrypt in 1999, adaptive password hashing functions, whereby brute-force resistance increases symmetrically with computational difficulty for legitimate users, have been our most powerful post-breach countermeasure against credential disclosure. Unfortunately, the relatively low tolerance of users to added latency places an upper bound on the deployment of this technique in most applications. In this paper, we present a multi-factor credential hashing function (MFCHF) that incorporates the additional entropy of multi-factor authentication into password hashes to provide asymmetric resistance to brute-force attacks. MFCHF provides full backward compatibility with existing authentication software (e.g., Google Authenticator) and hardware (e.g., YubiKeys), with support for common usability features like factor recovery. The result is a 10^6 to 10^48 times increase in the difficulty of cracking hashed credentials, with little added latency or usability impact. For details, see our paper. Show Less

The growth of digital wallets and popular 'buy now, pay later’ options raises concerns about social welfare and policy. This column uses data from a world-leading Chinese provider to document that 'buy now, pay later’ dominates e-wallet transactions and expands FinTech credit to underserved consumers. It also substantially boosts consumer spending, but users – especially those relying on e-wallets as their sole credit source – carefully moderate borrowing when incurring interest charges. These findings can help policymakers tackle the challenges arising from the expansion of digital wallets and 'buy now, pay later’. For more information, please see our work. Show Less

Differential obliviousness (DO) is a privacy notion which mandates that the access patterns of a program satisfy differential privacy. Earlier works have shown that in numerous applications, differential obliviousness allows us to circumvent fundamental barriers pertaining to fully oblivious algorithms, resulting in asymptotical (and sometimes even polynomial) performance improvements. Although DO has been applied to various contexts, including the design of algorithms, data structures, and protocols, its compositional properties are not explored until the recent work of Zhou et al. (Eurocrypt’23). Specifically, Zhou et al. showed that the original DO notion is not composable. They then proposed a refinement of DO called neighbor-preserving differential obliviousness (NPDO), and proved a basic composition for NPDO. In Zhou et al.’s basic composition theorm for NPDO, the privacy loss is linear in k for k-fold composition. In comparison, for standard differential privacy, we can enjoy roughly √ k loss for k-fold composition by applying the well-known advanced composition theorem. Therefore, a natural question left open by their work is whether we can also prove an analogous advanced composition for NPDO. In this paper, we answer this question affirmatively. As a key step in proving an advanced composition theorem for NPDO, we define a more operational notion called symmetric NPDO which we prove to be equivalent to NPDO. Using symmetric NPDO as a stepping stone, we also show how to generalize NPDO to more general notions of divergence, resulting in Rényi-NPDO, zero-concentrated-NPDO, Gassian-NPDO, and g-NPDO notions. We also prove composition theorems for these generalized notions of NPDO. For details, see our paper. Show Less

We design a practical algorithm for transaction ordering that takes into account both transaction timestamps and bids. The algorithm guarantees that users get their transactions published with bounded delay against a bid, while it extracts a fair value from sophisticated users that have an edge in latency, by moving expenditure from investment in latency improvement technology to bidding. The algorithm creates a score from timestamps and bids, and orders transactions based on the score. We first show that a scoring rule is the only type of rule that satisfies the independence of latency races. We provide an economic analysis of the protocol in an environment of private information, where investment in latency is made ex-ante or interim stages, while bidding happens at the interim stage where private signals have been observed. The algorithm is useful for transaction sequencing in rollups or in other environments where the sequencer has privileged access to order flows. For more details, see our paper. Show Less

Blockchain-based smart contracts can potentially replace certain traditional contracts through decentralized enforcement and reduced transaction costs. However, scalability is a key bottleneck hindering their broader application and adoption, often leading to concentrated or exclusive networks. To avoid falling short of the original promise of the technology, firms actively explore "layer-2'' methods for scaling. We provide some initial evidence on the economic implications of a layer-2 scaling solution, which moves information aggregation from on-chain to off-chain peer-to-peer networks. A parallel-system experiment allows clean identification because we observe the same unit in the treatment and control systems at the same time. We find that this scaling solution reduces operating costs by 76%, and importantly, leads to decentralization with lower market concentration and more participation, which in turn improves data accuracy. The findings provide initial evidence of how blockchain and smart contracting technologies evolve towards achieving decentralized and scalable trust. For details, see our work. Show Less

Identifying and mitigating vulnerabilities in smart contracts is crucial, especially considering the rapid growth and increasing complexity of Decentralized Finance (DeFi) platforms. To address the challenges associated with securing these contracts, we introduce a versatile dynamic analysis framework specifically designed for the Ethereum Virtual Machine (EVM). This comprehensive framework focuses on tracking contract executions, capturing valuable runtime information, while introducing and employing the Execution Property Graph (EPG) to propose a unique graph traversal technique that swiftly detects potential smart contract attacks. Our approach showcases its efficacy with rapid average graph traversal time per transaction and high true positive rates. The successful identification of a zero-day vulnerability affecting Uniswap highlights the framework’s potential to effectively uncover smart contract vulnerabilities in complex DeFi systems. For more information, please see our paper. Show Less

The collapse of FTX has underscored the critical importance of auditing, especially in the fast-growing decentralized finance (DeFi) markets. Due to the decentralized nature of DeFi platforms, which facilitate peer-to-peer transactions without intermediaries, and the rapid pace of innovation in the unregulated and highly asymmetric information environment of the DeFi market, traditional financial auditing methods face significant hurdles. This study explores the relevance of auditing in DeFi protocols and highlights its critical role in ensuring transparency, security, and trust within these decentralized systems. Through a comprehensive analysis of the unique characteristics of DeFi, including smart contracts and blockchain technology, we delve into the specific challenges and risks associated with auditing DeFi applications. Furthermore, the article discusses the demand for robust auditing practices, regulatory oversight, and industry standards to enhance resilience and stability in this fast-growing emerging market. For more details, see my paper. Show Less

This is an essay about the relationship between legal interpretation and software interpretation, and in particular about what we gain by thinking about computers and programmers as interpreters in the same way that lawyers and judges are interpreters. I wish to propose that there is something to be gained by treating software as another type of law-like text, one that has its own interpretive rules, and that can be analysed using the conceptual tools we typically apply to legal interpretation. In particular, we can usefully distinguish three types of meaning that a program can have. The first is naive functional meaning - the effects that a program has when executed on a specific computer on a specific occasion. The second is literal functional meaning - the effects that a program would have if executed on a correctly functioning computer. The third is ordinary functional meaning - the effects that a program would have if executed correctly and was free of bugs. The punchline is that literal and ordinary functional meaning are inescapably social. The notions of what makes a computer ‘correctly functioning’ and what makes a program ‘bug free’ depend on the conventions of a particular technical community. We cannot reduce the meaning and effects of software to purely technical questions, because although meaning in programming languages is conventional in a different way than meaning in natural languages, it is conventional all the same. For further information, please see my work. Show Less

Crash fault tolerant (CFT) consensus algorithms are commonly used in scenarios where system components are trusted, such as enterprise settings. CFT algorithms offer high throughput and low latency, making them an attractive option for centralized operations that require fault tolerance. However, CFT consensus is vulnerable to Byzantine faults, which can be introduced by a single corrupt component. Such faults can break consensus in the system. Byzantine fault tolerant (BFT) consensus algorithms withstand Byzantine faults, but they are not as competitive with CFT algorithms in terms of performance. In this work, we explore a middle ground between BFT and CFT consensus by exploring the role of accountability in CFT protocols. That is, if a CFT protocol node breaks protocol and affects consensus safety, we aim to identify which node was the culprit. Based on Raft, one of the most popular CFT algorithms, we present Raft-Forensics, which provides accountability over Byzantine faults. We theoretically prove that if two honest components fail to reach consensus, the Raft-Forensics auditing algorithm finds the adversarial component that caused the inconsistency. In an empirical evaluation, we demonstrate that Raft-Forensics performs similarly to Raft and significantly better than state-of-the-art BFT algorithms. With 256 byte messages, Raft-Forensics achieves peak throughput 87.8% of vanilla Raft at 46% higher latency, while state-of-the-art BFT protocol Dumbo-NG only achieves 18.9% peak throughput at nearly 6× higher latency. For details, see our work. Show Less

Web3 is used to describe the next iteration of the internet in which decentralized services are automated on blockchains. This paper describes the elements of Web3 including blockchains and tokens. It describes the largest decentralized finance protocols and some specific services where blockchain and tokens can be used. The paper concludes with a brief discussion of some regulatory challenges. For more information, please see my paper. Show Less

Succinct Non-interactive Arguments of Knowledge (SNARKs) have seen interest and development from the cryptographic community over recent years, and there are now constructions with very small proof size designed to work well in practice. A SNARK protocol can only be widely accepted as secure, however, if a rigorous proof of its security properties has been vetted by the community. Even then, it is sometimes the case that these security proofs are flawed, and it is then necessary for further research to identify these flaws and correct the record [35, 51]. To increase the rigor of these proofs, we turn to formal methods. Focusing on the soundness aspect of a widespread class of SNARKs, we formalize proofs for six different constructions, including the well-known Groth ’16. Our codebase is written in the Lean 3 theorem proving language, and uses a variety of techniques to simplify and automate these proofs as much as possible. For more information, please see our work. Show Less

Cryptocurrencies and decentralized platforms are rapidly gaining traction since Nakamoto’s discovery of Bitcoin’s blockchain protocol. These systems use Proof of Work (PoW) to achieve unprecedented security for digital assets. However, the significant power consumption and ecological impact of PoW are leading policymakers to consider stark measures against them and prominent systems to explore alternatives. But these alternatives imply stepping away from key security aspects of PoW. We present Sprints, a blockchain protocol that achieves almost the same security guarantees as PoW blockchains, but with an order-of-magnitude lower ecological impact, taking into account both power and hardware. To achieve this, Sprints forces miners to mine intermittently. It interleaves Proof of Delay (PoD, e.g., using a Verifiable Delay Function) and PoW, where only the latter bears a significant resource expenditure. We prove that in Sprints the attacker’s success probability is the same as that of legacy PoW. To evaluate practical performance, we analyze the effect of shortened PoW duration, showing a minor reduction in resilience (49% instead of 50%). We confirm the results with a full implementation using 100 patched Bitcoin clients in an emulated network. For more details, see our work. Show Less

Blockchain systems often rely on rationality assumptions for their security, expecting that nodes are motivated to maximize their profits. These systems thus design their protocols to incentivize nodes to execute the honest protocol but fail to consider out-of-band collusion. Existing works analyzing rationality assumptions are limited in their scope, either by focusing on a specific protocol or relying on non-existing financial instruments. We propose a general rational attack on rationality by leveraging an external channel that incentivizes nodes to collude against the honest protocol. Our approach involves an attacker creating an out-of-band bribery smart contract to motivate nodes to double-spend their transactions in exchange for shares in the attacker’s profits. We provide a game theory model to prove that any rational node is incentivized to follow the malicious protocol. We discuss our approach to attacking the Bitcoin and Ethereum blockchains, demonstrating that irrational behavior can be rational in real-world blockchain systems when analyzing rationality in a larger ecosystem. We conclude that rational assumptions only appear to make the system more secure and offer a false sense of security under the flawed analysis. For more information, see our paper. Show Less

This paper presents a dynamic, real-time approach to detecting anomalous blockchain transactions. The proposed tool, TXRANK, generates tracing representations of blockchain activity and trains from scratch a large language model to act as a real-time Intrusion Detection System. Unlike traditional methods, TXRANK is designed to offer an unrestricted search space and does not rely on predefined rules or patterns, enabling it to detect a broader range of anomalies. We demonstrate the effectiveness of TXRANK through its use as an anomaly detection tool for Ethereum transactions. In our experiments, it effectively identifies abnormal transactions among a dataset of 68M transactions and has a batched throughput of 2284 transactions per second on average. Our results show that, TXRANK identifies abnormal transactions by ranking 49 out of 124 attacks among the top-3 most abnormal transactions interacting with their victim contracts. This work makes contributions to the field of blockchain transaction analysis by introducing a custom data encoding compatible with the transformer architecture, a domain-specific tokenization technique, and a tree encoding method specifically crafted for the Ethereum Virtual Machine (EVM) trace representation. For more details, see our work. Show Less

Decentralized Autonomous Organizations (DAOs) have emerged as a novel way to coordinate a group of (pseudonymous) entities towards a shared vision (e.g., promoting sustainability), utilizing self-executing smart contracts on blockchains to support decentralized governance and decision-making. In just a few years, over 4,000 DAOs have been launched in various domains, such as investment, education, health, and research. Despite such rapid growth and diversity, it is unclear how these DAOs actually work in practice and to what extent they are effective in achieving their goals. Given this, we aim to unpack how (well) DAOs work in practice. We conducted an in-depth analysis of a diverse set of 10 DAOs of various categories and smart contracts, leveraging on-chain (e.g., voting results) and off-chain data (e.g., community discussions) as well as our interviews with DAO organizers/members. Specifically, we defined metrics to characterize key aspects of DAOs, such as the degrees of decentralization and autonomy. We observed CompoundDAO, AssangeDAO, Bankless, and Krausehouse having poor decentralization in voting, while decentralization has improved over time for one-person-one-vote DAOs (e.g., Proof of Humanity). Moreover, the degree of autonomy varies among DAOs, with some (e.g., Compound and Krausehouse) relying more on third parties than others. Lastly, we offer a set of design implications for future DAO systems based on our findings. For further information, see our work. Show Less

We present two abstractions for designing modular state machine replication (SMR) protocols - trees and turtles. A tree captures the set of possible state machine histories, while a turtle represents a subprotocol that tries to find agreement in this tree. We showcase the applicability of these abstractions by constructing crash-tolerant SMR protocols out of abstract tree turtles and providing examples of tree turtle implementations. The modularity of tree turtles allows a generic approach for adding a leader for liveness. We expect that these abstractions will simplify reasoning and formal verification of SMR protocols as well as facilitate innovation in protocol designs. For more details, see our paper. Show Less

New and evolving financial technologies, including the advent of cryptocurrencies and central bank digital currencies (CBDCs), will make cross-border payments cheaper and quicker. However, reduced frictions in global capital flows could also result in more capital flow and exchange rate volatility, which is of particular concern for emerging market economies. There will be greater competition among fiat currencies and certain private currencies such as stablecoins in their roles as mediums of exchange for payment and settlement of domestic as well as cross-border transactions. However, neither the advent of CBDCs nor the lowering of barriers to international financial flows will do much on their own to reorder the international monetary system or the balance of power among major currencies. Currencies such as the US dollar that are dominant stores of value will remain so because that dominance rests not just on the issuing country’s economic size and financial market depth, but also on a strong institutional foundation that is essential for maintaining investors’ trust in a currency. For more details, see my work. Show Less

With the accelerated adoption of end-to-end encryption, there is an opportunity to re-architect security and anti-abuse primitives in a manner that preserves new privacy expectations. In this paper, we consider two novel protocols for on-device blocklisting that allow a client to determine whether an object (e.g., URL, document, image, etc.) is harmful based on threat information possessed by a so-called remote enforcer in a way that is both privacy-preserving and trustworthy. Our protocols leverage a unique combination of private set intersection to promote privacy, cryptographic hashes to ensure resilience to false positives, cryptographic signatures to improve transparency, and Merkle inclusion proofs to ensure consistency and auditability. We benchmark our protocols—one that is time-efficient, and the other space-efficient—to demonstrate their practical use for applications such as email, messaging, storage, and other applications. We also highlight remaining challenges, such as privacy and censorship tensions that exist with logging or reporting. We consider our work to be a critical first step towards enabling complex, multi-stakeholder discussions on how best to provide on-device protections. For details, please see our paper. Show Less

We develop a general equilibrium model that highlights the trade-offs between physical and digital forms of retail central bank money. The key differences between cash and central bank digital currency (CBDC) include transaction efficiency, possibilities for tax evasion, and, potentially, nominal rates of return. We establish conditions under which cash and CBDC can co-exist and show how government policies can influence relative holdings of cash, CBDC, and other assets. We illustrate how a CBDC can facilitate negative nominal interest rates and helicopter drops, and also how a CBDC can be structured to prevent capital flight from other assets. For more details, see our work. Show Less

The use of blockchains for automated and adversarial trading has become commonplace. However, due to the transparent nature of blockchains, an adversary is able to observe any pending, not-yet-mined transactions, along with their execution logic. This transparency further enables a new type of adversary, which copies and front-runs profitable pending transactions in real-time, yielding significant financial gains. Shedding light on such “copy-paste” malpractice, this paper introduces the Blockchain Imitation Game and proposes a generalized imitation attack methodology called APE. Leveraging dynamic program analysis techniques, APE supports the automatic synthesis of adversarial smart contracts. Over a timeframe of one year (1st of August, 2021 to 31st of July, 2022), APE could have yielded 148.96M USD in profit on Ethereum, and 42.70M USD on BNB Smart Chain (BSC). Not only as a malicious attack, we further show the potential of transaction and contract imitation as a defensive strategy. Within one year, we find that APE could have successfully imitated 13 and 22 known Decentralized Finance (DeFi) attacks on Ethereum and BSC, respectively. Our findings suggest that blockchain validators can imitate attacks in real-time to prevent intrusions in DeFi. For further details, see our work. Show Less

Blockchain security relies on incentives to ensure participants, called miners, cooperate and behave as the protocol dictates. Such protocols have a security threshold – a miner whose relative computational power is larger than the threshold can deviate to improve her revenue. Moreover, blockchain participants can behave in a petty compliant manner - usually follow the protocol, but deviate to increase revenue when deviation cannot be distinguished externally from the prescribed behavior. The effect of petty compliant miners on the security threshold of blockchains is not well understood. Due to the complexity of the analysis, it remained an open question since Carlsten et al. identified it in 2016. In this work, we use deep Reinforcement Learning (RL) to analyze how a rational miner performs selfish mining by deviating from the protocol to maximize revenue when petty compliant miners are present. We find that a selfish miner can exploit petty compliant miners to increase her revenue by bribing them. Our method reveals that the security threshold is lower when petty compliant miners are present. In particular, with parameters estimated from the Bitcoin blockchain, we find the threshold drops from the known value of 25% to only 21% (or 19%) when 50% (or 75%) of the other miners are petty compliant. Hence, our deep RL analysis puts the open question to rest; the presence of petty compliant miners exacerbates a blockchain’s vulnerability to selfish mining and is a major security threat. For further details, please see our paper. Show Less

We present a theoretical framework for analyzing the efficiency of consensus protocols, and apply it to analyze the optimistic and pessimistic confirmation times of state-of-the-art partially-synchronous protocols in the so-called “rotating leader/random leader” model of consensus (recently popularized in the blockchain setting). We next present a new and simple consensus protocol in the partially synchronous setting, tolerating f < n/3 byzantine faults. In our eyes, this protocol is essentially as simple to describe as the simplest known protocols, but it also enjoys an even simpler security proof, while matching and, even improving, the efficiency of the state-of-the-art (according to our theoretical framework). As with the state-of-the-art protocols, our protocol assumes a (bare) PKI, a digital signature scheme, collision-resistant hash functions, and a random leader election oracle, which may be instantiated with a random oracle (or a CRS). For details, see our work. Show Less

We construct a sublinear-time single-server pre-processing Private Information Retrieval (PIR) scheme with optimal client storage and server computation (up to poly-logarithmic factors), only relying on the assumption of the existence of One Way Functions (OWF). Our scheme achieves amortized O˜( √ n) online server computation and client computation and O( √ n) online communication per query, and requires Oeλ( √ n) client storage. Unlike prior single-server PIR schemes that rely on heavy cryptographic machinery such as Homomorphic Encryption, our scheme only utilizes lightweight cryptography such as PRFs, which is easily instantiated in practice. To our knowledge, this is the first practical implementation of a single-server sublinear-time PIR scheme. Compared to existing linear time single-server solutions, our schemes are faster by 10 − 300× and are comparable to the fastest two-server schemes. In particular, for a 100GB database of 1.6 billion entries, our experiments show that our scheme has less than 40ms online computation time on a single core. For more information, see our work. Show Less

Liquidations in Decentralized Finance (DeFi) are both a blessing and a curse — whereas liquidations prevent lenders from capital loss, they simultaneously lead to liquidation spirals and system-wide failures. Since most lending and borrowing protocols assume liquidations are indispensable, there is an increased interest in alternative constructions that prevent immediate systemic-failure under uncertain circumstances. In this work, we introduce reversible call options, a novel financial primitive that enables the seller of a call option to terminate it before maturity. We apply reversible call options to lending in DeFi and devise Miqado, a protocol for lending platforms to replace the liquidation mechanisms. To the best of our knowledge, Miqado is the first protocol that actively mitigates liquidations to reduce the risk of liquidation spirals. Instead of selling collateral, Miqado incentivizes external entities, so-called supporters, to top-up a borrowing position and grant the borrower additional time to rescue the debt. Our simulation shows that Miqado reduces the amount of liquidated collateral by 89.82% in a worst-case scenario. For details, see our work. Show Less

We investigate the theoretical and empirical relationships between activity in on-chain markets and pricing in off-chain cryptocurrency markets (e.g., ETH/USD prices). The motivation is to develop methods for proxying off-chain market data using data and computation that is in principle verifiable on-chain and could provide an alternative approach to blockchain price oracles. We explore relationships in PoW mining, PoS validation, block space markets, network decentralization, usage and monetary velocity, and on-chain liquidity pools and AMMs. We select key features from these markets, which we analyze through graphical models, mutual information, and ensemble machine learning models to explore the degree to which off-chain pricing information can be recovered entirely on-chain. We find that a large amount of pricing information is contained in on-chain data, but that it is generally hard to recover precise prices except on short time scales of retraining the model. We discuss how even a noisy trustless data source such as this can be helpful toward minimizing trust requirements of oracle designs. For more information, please see our work. Show Less

TEE-based smart contracts are an emerging blockchain architecture, offering fully programmable privacy with better performance than alternatives like secure multiparty computation. They can also support compatibility with existing smart contract languages, such that existing (plaintext) applications can be readily ported, picking up privacy enhancements automatically. While previous analysis of TEE-based smart contracts have focused on failures of TEE itself, we asked whether other aspects might be understudied. We focused on state consistency, a concern area highlighted by Li et al., as well as new concerns including access pattern leakage and software upgrade mechanisms. We carried out a code review of a cohort of four TEE-based smart contract platforms. These include Secret Network, the first to market with in-use applications, as well as Oasis, Phala, and Obscuro, which have at least released public test networks. The first and most broadly applicable result is that access pattern leakage occurs when handling persistent contract storage. On Secret Network, its fine-grained access pattern is catastrophic for the transaction privacy of SNIP-20 tokens. If ERC-20 tokens were naively ported to Oasis they would be similarly vulnerable; the others in the cohort leak coarse-grained information at approximately the page level (4 kilobytes). Improving and characterizing this will require adopting techniques from ORAMs or encrypted databases. Second, the importance of state consistency has been underappreciated, in part because exploiting such vulnerabilities is thought to be impractical. We show they are fully practical by building a proof-of-concept tool that breaks all advertised privacy properties of SNIP-20 tokens, able to query the balance of individual accounts and the token amount of each transfer. We additionally demonstrate MEV attacks against the Sienna Swap application. As a final consequence of lacking state consistency, the developers have inadvertently introduced a decryption backdoor through their software upgrade process. We have helped the Secret developers mitigate this through a coordinated vulnerability disclosure, after which their state consistency should be roughly on par with the rest. For further information, please see our paper. Show Less

SCIF is a new programming language for building compositionally secure smart contracts. Smart contracts implemented in SCIF are checked by the compiler for their security properties before they are deployed. SCIF is especially designed to support building secure systems in which multiple smart contracts interact. It detects and prevents common security vulnerabilities such as use of untrusted information, reentrancy attacks, and confused deputy attacks. For more information, please see our work. Show Less

Cryptographic hash functions map data of arbitrary size to a fixed size digest, and are one of the most commonly used cryptographic objects. As it is infeasible to design an individual hash function for every input size, variable-input length hash functions are built by designing and bootstrapping a single fixed-input length function that looks sufficiently random. To prevent trivial preprocessing attacks, applications often require not just a single hash function but rather a family of keyed hash functions. The most well-known methods for designing variable-input length hash function families from a fixed idealized function are the Merkle-Damg˚ard and Sponge designs. The former underlies the SHA-1 and SHA-2 constructions and the latter underlies SHA-3. Unfortunately, recent works (Coretti et al. EUROCRYPT 2018, Coretti et al. CRYPTO 2018) show non-trivial time-space tradeoff attacks for finding collisions for both. Thus, this forces a parameter blowup (i.e., efficiency loss) for reaching a certain desired level of security. We ask whether it is possible to build families of keyed hash functions which are provably resistant to any non-trivial time-space tradeoff attacks for finding collisions, without incurring significant efficiency costs. We present several new constructions of keyed hash functions that are provably resistant to any non-trivial time-space tradeoff attacks for finding collisions. Our constructions provide various tradeoffs between their efficiency and the range of parameters where they achieve optimal security for collision resistance. Our main technical contribution is proving optimal security bounds for converting a hash function with a fixed-sized input to a keyed hash function with (potentially larger) fixed-size input. We then use this keyed function as the underlying primitive inside the standard Merkle-Damg˚ard and Merkle tree constructions. We strongly believe that this paradigm of using a keyed inner hash function in these constructions is the right one, for which non-uniform security has not been analyzed prior to this work. For more information, please see our paper. Show Less

This paper introduces protocols for authenticated private information retrieval. These schemes enable a client to fetch a record from a remote database server such that (a) the server does not learn which record the client reads, and (b) the client either obtains the “authentic” record or detects server misbehavior and safely aborts. Both properties are crucial for many applications. Standard private-information-retrieval schemes either do not ensure this form of output authenticity, or they require multiple database replicas with an honest majority. In contrast, we offer multi-server schemes that protect security as long as at least one server is honest. Moreover, if the client can obtain a short digest of the database out of band, then our schemes require only a single server. Performing an authenticated private PGP-public-key lookup on an OpenPGP key server’s database of 3.5 million keys (3 GiB), using two non-colluding servers, takes under 1.2 core-seconds of computation, essentially matching the time taken by unauthenticated private information retrieval. Our authenticated single-server schemes are 30-100× more costly than state-of-the-art unauthenticated single-server schemes, though they achieve incomparably stronger integrity properties. For more information, see our paper. Show Less

Transaction fee mechanism design is a new decentralized mechanism design problem where users bid for space on the blockchain. Several recent works showed that the transaction fee mechanism design fundamentally departs from classical mechanism design. They then systematically explored the mathematical landscape of this new decentralized mechanism design problem in two settings - in the plain setting where no cryptography is employed, and in a cryptography-assisted setting where the rules of the mechanism are enforced by a multi-party computation protocol. Unfortunately, in both settings, prior works showed that if we want the mechanism to incentivize honest behavior for both users as well as miners (possibly colluding with users), then the miner revenue has to be zero. Although adopting a relaxed, approximate notion of incentive compatibility gets around this zero miner-revenue limitation, the scaling of the miner revenue is nonetheless poor. In this paper, we show that if we make a mildly stronger reasonable-world assumption than prior works, we can circumvent the known limitations on miner revenue, and design auctions that generate optimal miner revenue. We also systematically explore the mathematical landscape of transaction fee mechanism design under the new reasonable-world and demonstrate how such assumptions can alter the feasibility and infeasibility landscape. For details, see our work. Show Less

With the recent explosive growth of interest and investment in virtual reality (VR) and the so-called “metaverse,” public attention has rightly shifted toward the unique security and privacy threats that these platforms may pose. While it has long been known that people reveal information about themselves via their motion, the extent to which this makes an individual globally identifiable within virtual reality has not yet been widely understood. In this study, we show that a large number of real VR users (N=55,541) can be uniquely and reliably identified across multiple sessions using just their head and hand motion relative to virtual objects. After training a classification model on 5 minutes of data per person, a user can be uniquely identified amongst the entire pool of 50,000+ with 94.33% accuracy from 100 seconds of motion, and with 73.20% accuracy from just 10 seconds of motion. This work is the first to truly demonstrate the extent to which biomechanics may serve as a unique identifier in VR, on par with widely used biometrics such as facial or fingerprint recognition. For more information, please see our paper. Show Less

This handbook provides an overview of various criminal activities related to cryptocurrencies, including investment scams, Ponzi schemes, rug pulls, ransomware attacks, money laundering, and darknet markets. We discuss the need for user protection and education, centralized entities and regulators' efforts to prevent scams, and the use of blockchain forensic techniques to investigate and curb cybercrimes such as ransomware attacks and money laundering. We also go beyond blockchain and access how other statistical analyses of crypto-related data emerge as a powerful tool to examine wash trading and tax evasion. Despite some success by authorities in shutting down cybercriminal activities, using cryptocurrencies and other technologies makes it challenging to identify and prosecute those involved in illicit activities, and increased collaboration between law enforcement agencies and the technology industry is needed. This handbook is an ongoing effort by the authors to provide an overall anatomy of cybercrime and potential solutions in the crypto space. For more information, please see our work. Show Less

We present a practical construction and implementation of timelock encryption, in which a ciphertext is guaranteed to be decryptable only after some specified time has passed. We employ an existing threshold network, the League of Entropy, implementing threshold BLS [BLS01, Bol03] in the context of Boneh and Franklin’s identity-based encryption [BF01] (BF-IBE). At present this threshold network broadcasts BLS signatures over each round number, equivalent to the current time interval, and as such can be considered a decentralised key holder periodically publishing private keys for the BF-IBE where identities are the round numbers. A noticeable advantage of this scheme is that only the encryptors and decryptors are required to perform any additional cryptographic operations, the threshold network can remain unaware of these computations and does not have to change to support the scheme. We also release an open-source implementation of our scheme and a live web page that can be used in production now relying on the existing League of Entropy network acting as a distributed public randomness beacon service using threshold BLS signatures. For more information, please see our paper. Show Less

We present the first performance comparison of EdDSA and BLS signatures in committee-based consensus protocols through large-scale geo-distributed benchmarks. Contrary to popular beliefs, we find that small deployments (less than 40 validators) can benefit from the small storage footprint of BLS multi-signatures while larger deployments should favor EdDSA to improve performance. As an independent contribution, we present a novel way for committee-based consensus protocols to verify BLS multi-signed certificates by manipulating the aggregated public key using pre-computed values. For more information, see our paper. Show Less

Encryption alone is not enough for secure end-to-end encrypted messaging - a server must also honestly serve public keys to users. Key transparency has been presented as an efficient solution for detecting (and hence deterring) a server that attempts to dishonestly serve keys. Key transparency involves two major components - (1) a username to public key mapping, stored and cryptographically committed to by the server, and, (2) an out-of-band consistency protocol for serving short commitments to users. In the setting of real-world deployments and supporting production scale, new challenges must be considered for both of these components. We enumerate these challenges and provide solutions to address them. In particular, we design and implement a memory-optimized and privacy-preserving verifiable data structure for committing to the username to public key store. To make this implementation viable for production, we also integrate support for persistent and distributed storage. We also propose a future-facing solution, termed “compaction”, as a mechanism for mitigating practical issues that arise from dealing with infinitely growing server data structures. Finally, we implement a consensusless solution that achieves the minimum requirements for a service that consistently distributes commitments for a transparency application, providing a much more efficient protocol for distributing small and consistent commitments to users. This culminates in our production-grade implementation of a key transparency system (Parakeet) which we have open-sourced, along with a demonstration of feasibility through our benchmarks. For more details, please see our work. Show Less

Most cryptographic protocols model a player’s knowledge of secrets in a simple way. Informally, the player knows a secret in the sense that she can directly furnish it as a (private) input to a protocol, e.g., to digitally sign a message. The growing availability of Trusted Execution Environments (TEEs) and secure multiparty computation, however, undermines this model of knowledge. Such tools can encumber a secret sk and permit a chosen player to access sk conditionally, without actually knowing sk. By permitting selective access to sk by an adversary, encumbrance of secrets can enable vote-selling in cryptographic voting schemes, illegal sale of credentials for online services, and erosion of deniability in anonymous messaging systems. Unfortunately, existing proof-of-knowledge protocols fail to demonstrate that a secret is unencumbered. We therefore introduce and formalize a new notion called complete knowledge (CK). A proof (or argument) of CK shows that a prover does not just know a secret, but also has fully unencumbered knowledge, i.e., unrestricted ability to use the secret. We introduce two practical CK schemes that use special-purpose hardware, specifically TEEs and off-the-shelf mining ASICs. We prove the security of these schemes and explore their practical deployment with a complete, end-to-end prototype that supports both. We show how CK can address encumbrance attacks identified in previous work. Finally, we introduce two new applications enabled by CK that involve proving ownership of blockchain assets. For more information, please see our work. Show Less

Designing an efficient solution for Byzantine broadcast is an important problem for many distributed computing and cryptographic tasks. There have been many attempts to achieve sub-quadratic communication complexity in several directions, both in theory and practice, all with pros and cons. This paper initiates the study of another attempt - improving the amortized communication complexity of multi-shot Byzantine broadcast. Namely, we try to improve the average cost when we have sequential multiple broadcast instances. We present a protocol that achieves optimal amortized linear complexity under an honest majority. Our core technique is to efficiently form a network for disseminating the sender’s message by keeping track of dishonest behaviors over multiple instances. We also generalize the technique for the dishonest majority to achieve amortized quadratic communication complexity. For more details, see our work. Show Less

While the advent of cryptocurrencies and digital assets holds promise for improving and disrupting financial systems by offering cheap, quick, and secure transfer of value, it also opens up new payment channels for cybercrimes. A prerequisite to solving a problem is understanding the nature of the problem. Assembling a diverse set of public, proprietary, and hand-collected data, including dark web conversations in Russian, we conduct the first detailed anatomy of crypto-enabled cybercrimes and highlight relevant economic issues. Our analyses reveal that a few organized ransomware gangs dominate the space and have evolved into sophisticated corporate-like operations with physical offices, franchising, and affiliation programs. Their techniques have also become more aggressive over time, entailing multiple layers of extortion and reputation management. Blanket restrictions on cryptocurrency usage may prove ineffective in tackling crypto-enabled cybercrime and hinder innovations. Instead, blockchain transparency and digital footprints enable effective forensics for tracking, monitoring, and shutting down dominant cybercriminal organizations. For more details, please see our work. Show Less

We develop a new type of automated market maker (AMM) that helps to maintain stability and long-term viability in a stablecoin. This primary market AMM (P-AMM) is an autonomous mechanism for pricing minting and redemption of stablecoins in all possible states and is designed to achieve several desirable properties. We first cover several case studies of current ad hoc stablecoin issuance and redemption mechanisms, several of which have contributed to recent stablecoin de-peggings, and formulate desirable properties of a P-AMM that support stability and usability. We then design a P-AMM redemption curve and show that it satisfies these properties, including bounded loss for both the protocol and stablecoin holders. We further show that this redemption curve is path independent and has properties of path deficiency in extended settings involving trading fees and a separate minting curve. This means that system health weakly improves relative to the path independent setting along any trading curve and that there is no incentive to strategically subdivide redemptions. Finally, we show how to implement the P-AMM efficiently on-chain. For further details, please see our work. Show Less

In this work we present Bingo, an adaptively secure and optimally resilient packed asynchronous verifiable secret sharing (PAVSS) protocol that allows a dealer to share f + 1 secrets or one high threshold secret with a total communication complexity of just O(λn2) words. Bingo requires a public key infrastructure and a powers-of-tau setup. Using Bingo’s packed secret sharing, we obtain an adaptively secure validated asynchronous Byzantine agreement (VABA) protocol that uses O(λn3) expected words and constant expected time. Using this agreement protocol in combination with Bingo, we obtain an adaptively secure high threshold asynchronous distributed key generation (ADKG) of standard field element secrets that uses O(λn3) expected words and constant expected time. To the best of our knowledge, Bingo is the first ADKG to have an adaptive security proof and have the same asymptotic complexity of the best known ADKG’s that only have non-adaptive security proofs. For more information, please see our paper. Show Less

An optimistic rollup (ORU) enables refereed delegation of computation from a blockchain (L1) to an untrusted remote system (L2), by allowing state updates posted on-chain to be disputed by any party via an interactive fraud proof (IFP) protocol. Existing systems that utilize this technique have demonstrated up to a 20x reduction in transaction fees. The most popular ORUs today, in active development, strive to extend existing Ethereum client software to support IFP construction, aiming to reuse prior L1 engineering efforts and replicate Ethereum Virtual Machine (EVM) semantics at L2. Unfortunately, to do so they tightly couple their on-chain IFP verifier with a specific client program binary—oblivious to its higher-level semantics. We argue that this approach (1) precludes the trust-minimized, permissionless participation of multiple Ethereum client programs, magnifying monoculture failure risk, (2) leads to an unnecessarily large and complex trusted computing base that is difficult to independently audit, and, (3) suffers from a frequently-triggered, yet opaque upgrade process—both further increasing auditing overhead, and complicating on-chain access control. In this work, we aim to build a secure, trust-minimized ORU that addresses these problems, while preserving scalability and dispute resolution efficiency. To do so, we design an IFP system native to the EVM, that enforces Ethereum’s specified semantics precisely at the level of a single EVM instruction. We present Specular, an ORU which leverages an off-the-shelf Ethereum client—modified minimally to support IFP construction—demonstrating the practicality of our approach. For further details, please see our paper. Show Less

Authentication is the first, crucial step in securing digital assets like cryptocurrencies and online services like banking and social networks. It relies on principals maintaining exclusive access to credentials like cryptographic signing keys, passwords, and physical devices. But both individuals and organizations struggle to manage their credentials, resulting in loss of assets and identity theft. Multi-factor authentication improves security, but its analysis and design are mostly limited to one-shot mechanisms, which decide immediately. In this work, we study mechanisms with back-and-forth interaction with the principals. For example, a user receives an email notification about sending money from her bank account and is given a period of time to abort the operation. We formally define the authentication problem, where an authentication mechanism interacts with a user and an attacker and tries to identify the user. A mechanism’s success depends on the scenario – whether the user / attacker know the different credentials - each credential can be safe, lost, leaked, or stolen. The profile of a mechanism is the set of all scenarios in which it succeeds. Thus, we have a partial order on mechanisms, defined by the subset relation on their profiles. We find an upper bound on the profile size and discover three types of n-credential mechanisms (for any n) that are maximally secure, meeting this bound. We show these are all the unique maximal mechanisms for n ≤ 3. We show the efficacy of our model by analyzing existing mechanisms, both theoretical and deployed in widely-used systems, and make concrete improvement proposals. We demonstrate the practicality of our mechanisms by implementing a maximally-secure cryptocurrency wallet. For more information, please see our paper. Show Less

Intel’s Software Guard Extensions (SGX) promises an isolated execution environment, protected from all software running on the machine. As such, numerous works have sought to leverage SGX to provide confidentiality and integrity guarantees for code running in adversarial environments. In the past few years however, SGX has come under heavy fire, threatened by numerous hardware attacks. With Intel repeatedly patching SGX to regain security while consistently launching new (micro)architectures, it is increasingly difficult to track the applicability of various attacks techniques across the SGX design landscape. Thus, in this paper we set out to survey and categorize various SGX attacks, their applicability to different SGX architectures, as well as the information leaked by them. We then set out to explore the effectiveness of SGX’s update mechanisms in preventing attacks on real-world deployments. Here, we study two commercial SGX applications. First, we investigate the SECRET network, an SGX-backed blockchain aiming to provide privacy preserving smart contracts. Next, we also consider PowerDVD, a UHD Blu-Ray Digital Rights Management (DRM) software licensed to play discs on PCs. We show that in both cases vendors are unable to meet security goals originally envisioned for their products, presumably due to SGX’s long update timelines and the complexities of a manual update process. This in turn forces vendors into making difficult security/usability trade offs, resulting in security compromises. For further details, see our work. Show Less

We analyze a unique data set of collateral liquidations on two Decentralized Finance lending platforms – Compound and Aave. Such liquidations require arbitrageurs to repay the loan in return for the discounted collateral. Using Blockchain transaction data, we observe if arbitrageurs liquidate positions out of their own inventory or obtain “flash loans.” To repay flash loans, arbitrageurs immediately sell the collateral asset. We document the high frequency price impact of such liquidity trades on nine different decentralized exchanges. Consistent with large block trades in equity markets there is a temporary and permanent price impact of collateral asset sales in DeFi. We document the effect of these trades on return distributions. Our work highlights the systemic fragility of decentralized markets. For more information, please see our work. Show Less

There are a number of forums where people participate under pseudonyms. One example is peer review, where the identity of reviewers for any paper is confidential. When participating in these forums, people frequently engage in “batching” - executing multiple related tasks (e.g., commenting on multiple papers) at nearly the same time. Our empirical analysis shows that batching is common in two applications we consider – peer review and Wikipedia edits. In this paper, we identify and address the risk of deanonymization arising from linking batched tasks. To protect against linkage attacks, we take the approach of adding delay to the posting time of batched tasks. We first show that under some natural assumptions, no delay mechanism can provide a meaningful differential privacy guarantee. We therefore propose a “one-sided” formulation of differential privacy for protecting against linkage attacks. We design a mechanism that adds zero-inflated uniform delay to events and we show it can preserve privacy. We prove that this noise distribution is in fact optimal in minimizing expected delay among mechanisms adding independent noise to each event, thereby establishing the Pareto frontier of the trade-off between the expected delay for batched and unbatched events. Finally, we conduct a series of experiments on Wikipedia and Bitcoin data that corroborate the practical utility of our algorithm in obfuscating batching without introducing onerous delay to a system. Link to our work. Show Less

Liquidity providers (LPs) on decentralized exchanges pay a fixed transaction cost (gas price) whenever they update their positions. Different economies of scale across LPs lead in equilibrium to the fragmentation of liquidity supply between low- and high-fee pools. Using data on liquidity updates from Uniswap, we document that while high-fee pools attract 56% of liquidity supply, they only execute 35% of trading volume. Low-fee pools cater to large (institutional) LPs, who update positions frequently in response to large trading volume. In contrast, small (retail) LPs converge to high-fee pools, trading off lower execution probabilities against a smaller liquidity management cost. For more information, please see our work. Show Less

Many blockchains utilize public peer-to-peer networks to communicate transactions. As activity on blockchain-based DeFi protocols has increased, there has been a sharp rise in strategic behaviour from bots and miners, commonly captured by the notion of Maximal Extractable Value (MEV). While many works have focused on MEV arising from the smart contract layer or consensus layer, in this work we study how a strategic agent can maximise realisable MEV through the optimal choice of network peers. Specifically, we study how existing definitions and algorithms for latency optimization [14, 17] can be augmented with information about the transactions themselves in order to optimize peering algorithms. We formally model this optimization objective for two classes of consensus protocols - 1) time-based (“fair ordering”) protocols and 2) single leader-based protocols. We present an efficient local algorithm for choosing peers strategically, and evaluate our algorithm on real world data to show that it outperforms benchmark algorithms that either choose peers randomly or do not exploit information about blockchain transactions. For more details, see our paper. Show Less

Permissionless blockchains are too slow for applications like point-of-sale payments. While several techniques have been proposed to speed up blockchain payments, none of them are satisfactory for application scenarios like retail shopping. In particular, existing solutions like payment channels require users to lock up significant funds and schemes based on pre-defined validators enable easy transaction censoring. In this paper, we develop Quicksilver, the first blockchain payment scheme that works with practical collaterals and is fast, censorship-resilient, and confidential at the same time.We implement Quicksilver for EVM-compatible chains and show that censoring-resilient payments are fast and affordable on currently popular blockchains platforms like Ethereum and Polygon. For more information, please see our paper. Show Less

Modern data centers have grown beyond CPU nodes to provide domain-specific accelerators such as GPUs and FPGAs to their customers. From a security standpoint, cloud customers want to protect their data. They are willing to pay additional costs for trusted execution environments such as enclaves provided by Intel SGX and AMD SEV. Unfortunately, the customers have to make a critical choice - either use domain-specific accelerators for speed or use CPU-based confidential computing solutions. To bridge this gap, we aim to enable data-center scale confidential computing that expands across CPUs and accelerators. We argue that having wide-scale TEE-support for accelerators presents a technically easier solution, but is far away from being a reality. Instead, our hybrid design provides enclaved execution guarantees for computation distributed over multiple CPU nodes and devices with/without TEE support. Our solution scales gracefully in two dimensions - it can handle a large number of heterogeneous nodes and it can accommodate TEE-enabled devices as and when they are available in the future. We observe marginal overheads of 0.42–8% on real-world AI data center workloads that are independent of the number of nodes in the data center. We add custom TEE support to two accelerators (AI and storage) and integrate it into our solution, thus demonstrating that it can cater to future TEE devices. Link to our work. Show Less

We provide the first constructions of SNARGs for Batch-NP and P based solely on the sub-exponential Decisional Diffie Hellman (DDH) assumption. Our schemes achieve poly-logarithmic proof sizes. Central to our results and of independent interest is a new construction of correlation-intractable hash functions for “small input” product relations verifiable in TC0 , based on sub-exponential DDH. For more details, see our paper. Show Less

We present “FairPoS”, the first blockchain protocol that achieves input fairness with adaptive security. Here, we introduce a novel notion of “input fairness” - the adversary cannot learn the plain-text of any finalized client input before it is include in a block in the chain's common-prefix. Should input fairness hold, input ordering attacks which depend on the knowledge of plain-text of client inputs are thwarted. In FairPoS, input fairness with adaptive security is achieved by means of the delay encryption scheme of DeFeo et al., a recent cryptographic primitive related to time-lock puzzles, allowing all client inputs in a given round to be encrypted under the same key, which can only be extracted after enough time has elapsed. In contrast, alternative proposals that prevent input order attacks by encrypting user inputs are not adaptively secure as they rely on small static committees to perform distributed key generation and threshold decryption for efficiency's sake. Such small committees are easily corrupted by an adaptive adversary with a corruption budget applicable over a large set of participants in a permissionless blockchain system. The key extraction task in delay encryption can, in principle, be performed by any party and is secure upon adaptive corruption, as no secret key material is learned. However, the key extraction requires highly specialized hardware in practice. Thus, FairPoS requires resource-rich, staking parties to insert extracted keys to blocks which enables light-clients to decrypt past inputs. Note that naive application of key extraction can result in chain stalls lasting the entire key extraction period. In FairPoS, this is addressed by a novel longest-extendable-chain rule. We formally prove that FairPoS achieves input fairness and the original security of Ouroborous Praos against an adaptive adversary. For more information, please see our work. Show Less

In this paper, we propose STAMP, an end-to-end 3-party MPC protocol for efficient privacy-preserving machine learning inference assisted by a lightweight TEE (LTEE), which will be far easier to secure and deploy than today’s large TEEs. STAMP provides three main advantages over the state-of-the-art - (i) STAMP achieves significant performance improvements compared to state-of-the-art MPC protocols, with only a small LTEE that is comparable to a discrete security chip such as the Trusted Platform Module (TPM) or on-chip security subsystems in SoCs similar to the Apple enclave processor. In a semi-honest setting with WAN/GPU, STAMP is 4×-63× faster than Falcon (PoPETs’21) and AriaNN (PoPETs’22) and 3.8×-12× more communication efficient. We achieve even higher performance improvements in a malicious setting. (ii) STAMP guarantees security with abort against malicious adversaries under honest majority assumption. (iii) STAMP is not limited by the size of secure memory in a TEE and can support high-capacity modern neural networks like ResNet18 and Transformer. For more information, please see our work. Show Less

Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted party. DKG is an essential building block to many decentralized protocols such as randomness beacons, threshold signatures, Byzantine consensus, and multiparty computation. While significant progress has been made recently, existing asynchronous DKG constructions are inefficient when the reconstruction threshold is larger than one-third of the total nodes. In this paper, we present a simple and concretely efficient asynchronous DKG (ADKG) protocol among n = 3t + 1 nodes that can tolerate up to t malicious nodes and support any reconstruction threshold ℓ ≥ t. Our protocol has an expected O(κn 3 ) communication cost, where κ is a security parameter, and only assumes the hardness of Discrete Logarithm. The core ingredient of our ADKG protocol is an asynchronous protocol to secret share a random polynomial of degree ℓ ≥ t, which has other applications such as asynchronous proactive secret sharing and asynchronous multiparty computation. We implement our high-threshold ADKG protocol and evaluate it using a network of up to 128 geographically distributed nodes. Our evaluation shows that our high-threshold ADKG protocol reduces the running time by 90% and reduces the bandwidth usage by 80% over state-of-the-art. For further details, see our work. Show Less

Differential obliviousness (DO) is a privacy notion which guarantees that the access patterns of a program satisfies differential privacy. Differential obliviousness was studied in a sequence of recent works as a relaxation of full obliviousness. Earlier works showed that DO not only allows us to circumvent the logarithmic-overhead barrier of fully oblivious algorithms, in many cases, it also allows us to achieve polynomial speedup over full obliviousness, since it avoids “padding to the worst-case” behavior of fully oblivious algorithms. Despite the promises of differential obliviousness (DO), a significant barrier that hinders its broad application is the lack of composability. In particular, when we apply one DO algorithm to the output of another DO algorithm, the composed algorithm may no longer be DO (with reasonable parameters). Specifically, the outputs of the first DO algorithm on two neighboring inputs may no longer be neighboring, and thus we cannot directly benefit from the DO guarantee of the second algorithm. In this work, we are the first to explore a theory of composition for differentially oblivious algorithms. We propose a refinement of the DO notion called (ϵ, δ)-neighbor-preserving-DO, or (ϵ, δ)-NPDO for short, and we prove that our new notion indeed provides nice compositional guarantees. In this way, the algorithm designer can easily track the privacy loss when composing multiple DO algorithms. We give several example applications to showcase the power and expressiveness of our new NPDO notion. One of these examples is a result of independent interest - we use the compositional framework to prove an optimal privacy amplification theorem for the differentially oblivious shuffle model. In other words, we show that for a class of distributed differentially private mechanisms in the shuffle-model, one can replace the perfectly secure shuffler with a DO shuffler, and nonetheless enjoy almost the same privacy amplification enabled by a shuffler. For more details, see our work. Show Less

Gordon and Katz, in [GK10], present a protocol for two-party computation with partial fairness which depends on presumptions on the size of the input or output of the functionality. They also show that for some other functionalities, this notion of partial fairness is impossible to achieve. In this work, we get around this impossibility result using verifiable delay functions, a primitive which brings in an assumption on the inability of an adversary to compute a certain function in a specified time. We present a gadget using VDFs which allows for any MPC to be carried out with ≈ 1/R partial fairness, where R is the number of communication rounds. Link to our work. Show Less

Blockchains have seen growing traction with cryptocurrencies reaching a market cap of over 1 trillion dollars, major institution investors taking interests, and global impacts on governments, businesses, and individuals. Also growing significantly is the heterogeneity of the ecosystem where a variety of blockchains co-exist. Cross-chain bridge is a necessary building block in this multi-chain ecosystem. Existing solutions, however, either suffer from performance issues or rely on trust assumptions of committees that significantly lower the security. Recurring attacks against bridges have cost users more than 1.5 billion USD. In this paper, we introduce zkBridge, an efficient cross-chain bridge that guarantees strong security without external trust assumptions. With succinct proofs, zkBridge not only guarantees correctness, but also significantly reduces on-chain verification cost. We propose novel succinct proof protocols that are orders-of-magnitude faster than existing solutions for workload in zkBridge. With a modular design, zkBridge enables a broad spectrum of use cases and capabilities, including message passing, token transferring, and other computational logic operating on state changes from different chains. To demonstrate the practicality of zkBridge, we implemented a prototype bridge from Cosmos to Ethereum, a particularly challenging direction that involves large proof circuits that existing systems cannot efficiently handle. Our evaluation shows that zkBridge achieves practical performance - proof generation takes less than 20 seconds, while verifying proofs on-chain costs less than 230K gas. For completeness, we also implemented and evaluated the direction from Ethereum to other EVM-compatible chains (such as BSC) which involves smaller circuits and incurs much less overhead. For more information, please see our work. Show Less

Recent works of Roughgarden (EC'21) and Chung and Shi (Highlights Beyond EC'22) initiate the study of a new decentralized mechanism design problem called transaction fee mechanism design (TFM). Unlike the classical mechanism design literature, in the decentralized environment, even the auctioneer (i.e., the miner) can be a strategic player, and it can even collude with a subset of the users facilitated by binding side contracts. Chung and Shi showed two main impossibility results that rule out the existence of a {\it dream} TFM. First, any TFM that provides incentive compatibility for individual users and miner-user coalitions must always have zero miner revenue, no matter whether the block size is finite or infinite. Second, assuming finite block size, no non-trivial TFM can simultaenously provide incentive compatibility for any individual user, and for any miner-user coalition. In this work, we explore what new models and meaningful relaxations can allow us to circumvent the impossibility results of Chung and Shi. Besides today's model that does not employ cryptography, we introduce a new MPC-assisted model where the TFM is implemented by a joint multi-party computation (MPC) protocol among the miners. We prove several feasibility and infeasibility results for achieving {\it strict} and {\it approximate} incentive compatibility, respectively, in the plain model as well as the MPC-assisted model. We show that while cryptography is not a panacea, it indeed allows us to overcome some impossibility results pertaining to the plain model, leading to non-trivial mechanisms with useful guarantees that are otherwise impossible in the plain model. Our work is also the first to characterize the mathematical landscape of transaction fee mechanism design under approximate incentive compatibility, as well as in a cryptography-assisted model. Link to our work. Show Less

Money has transformed human society, enabling commerce and trade even between widely dispersed geographic locations. It allows the transfer of wealth and resources across space and over time. But for much of human history, it has also been the object of rapacity and depredation. Money is now on the cusp of a transformation that could reshape banking, finance, and even the structure of society. Most notably, the era of physical currency, or cash, is drawing to an end, even in low- and middle-income countries - the age of digital currencies has begun. A new round of competition between official and private currencies is also looming in both the domestic and international arenas. The proliferation of digital technologies that is powering this transformation could foster useful innovations and broaden access to basic financial services. But there is a risk that the technologies could intensify the concentration of economic power and allow big corporations and governments to intrude even more into our financial and private lives. Traditional financial institutions, especially commercial banks, face challenges to their business models as new technologies give rise to online banks that can reach more customers and to web-based platforms, such as Prosper, capable of directly connecting savers and borrowers. These new institutions and platforms are intensifying competition, promoting innovation, and reducing costs. Savers are gaining access to a broader array of saving, credit, and insurance products, while small-scale entrepreneurs are able to secure financing from sources other than banks, which tend to have stringent loan-underwriting and collateral requirements. Domestic and international payments are becoming cheaper and quicker, benefiting consumers and businesses. For more information, please see our paper. Show Less

Within just four years, the blockchain-based Decentralized Finance (DeFi) ecosystem has accumulated a peak total value locked (TVL) of more than 253 billion USD. This surge in DeFi’s popularity has, unfortunately, been accompanied by many impactful incidents. According to our data, users, liquidity providers, speculators, and protocol operators suffered a total loss of at least 3.24 billion USD from Apr 30, 2018 to Apr 30, 2022. Given the blockchain’s transparency and increasing incident frequency, two questions arise - How can we systematically measure, evaluate, and compare DeFi incidents? How can we learn from past attacks to strengthen DeFi security? In this paper, we introduce a common reference frame to systematically evaluate and compare DeFi incidents. We investigate 77 academic papers, 30 audit reports, and 181 real-world incidents. Our open data reveals several gaps between academia and the practitioners’ community. For example, few academic papers address “price oracle attacks” and “permissonless interactions”, while our data suggests that they are the two most frequent incident types (15% and 10.5% correspondingly). We also investigate potential defenses, and find that - (i) 103 (56%) of the attacks are not executed atomically, granting a rescue time frame for defenders, (ii) SoTA bytecode similarity analysis can at least detect 31 vulnerable/23 adversarial contracts, and (iii) 33 (15.3%) of the adversaries leak potentially identifiable information by interacting with centralized exchanges. Link to our work. Show Less

Peer-to-peer (p2p) networks are not independent of their peers, and the network efficiency depends on peers contributing resources. Because shared resources are not free, this contribution must be rewarded. Peers across the network may share computation power, storage capacity, and bandwidth. This paper looks at how bandwidth incentive encourages peers to share bandwidth and rewards them for their contribution. With the advent of blockchain technology, many p2p networks attempt to reward contributions by crypto-assets. We conduct simulations to better understand current incentive mechanisms, assess the fairness of these mechanisms, and to look for ways to make those incentives more equitable. The following are the primary contributions of this study - (i) We investigate and simulate bandwidth incentives within Swarm, a cutting-edge p2p storage network, (ii) We demonstrate one approach to make the current bandwidth incentives more equitable, (iii) We use the Gini coefficient to define two quantifiable fairness characteristics to evaluate reward sharing in a decentralized p2p storage network. For further information, please see our paper. Show Less

Virtual reality (VR) telepresence applications and the so-called "metaverse'' promise to be the next major medium of interaction with the internet. However, with numerous recent studies showing the ease at which VR users can be profiled, deanonymized, and data harvested, metaverse platforms carry all the privacy risks of the current internet and more while at present having none of the defensive privacy tools we are accustomed to using on the web. To remedy this, we present the first known method of implementing an "incognito mode'' for VR. Our technique leverages local differential privacy to quantifiably obscure sensitive user data attributes, with a focus on intelligently adding noise when and where it is needed most to maximize privacy while minimizing usability impact. Moreover, our system is capable of flexibly adapting to the unique needs of each metaverse application to further optimize this trade-off. We implement our solution as a universal Unity (C#) plugin that we the evaluate using several popular VR applictions. Upon faithfully replicating the most well-known VR privacy attacks studies, we show a significant degradation of attacker capabilities when using our proposed solution. For more information, please see our work. Show Less

We present the first general construction of a Multi-Factor Key Derivation Function (MFKDF). Our function expands upon password-based key derivation functions (PBKDFs) with support for using other popular authentication factors like TOTP, HOTP, and hardware tokens in the key derivation process. In doing so, it provides an exponential security improvement over PBKDFs with less than 12ms of additional computational overhead in a typical web browser. We further present a threshold MFKDF construction, allowing for client-side key recovery and reconstruction if a factor is lost. Finally, by "stacking'' derived keys, we provide a means of cryptographically enforcing arbitrarily specific key derivation policies. The result is a paradigm shift toward direct cryptographic protection of user data using all available authentication factors, with no noticeable change to the user experience. We demonstrate the ability of our solution to not only significantly improve the security of existing systems implementing PBKDFs, but also to enable new applications where PBKDFs would not be considered a feasible approach. For further information, please see our paper. Show Less

We present the first non-interactive delegation scheme for P with time-tight parallel prover efficiency based on standard hardness assumptions. More precisely, in a time-tight delegation scheme—which we refer to as a SPARG (succinct parallelizable argument)—the prover’s parallel running time is t + polylog(t), while using only polylog(t) processors and where t is the length of the computation. (In other words, the proof is computed essentially in parallel with the computation, with only some minimal additive overhead in terms of time). Our main results show the existence of a publicly-verifiable, non-interactive, SPARG for P assuming polynomial hardness of LWE. Our SPARG construction relies on the elegant recent delegation construction of Choudhuri, Jain, and Jin (FOCS’21) and combines it with techniques from Ephraim et al (EuroCrypt’20). We next demonstrate how to make our SPARG time-independent—where the prover and verifier do not need to known the running-time t in advance. As far as we know, this yields the first construction of a time-tight delegation scheme with time-independence based on any hardness assumption. We finally present applications of SPARGs to the constructions of VDFs (Boneh et al, Crypto’18), resulting in the first VDF construction from standard polynomial hardness assumptions (namely LWE and the minimal assumption of a sequentially hard function). Link to our work. Show Less

Zero-knowledge proof is a powerful cryptographic primitive that has found various applications in the real world. However, existing schemes with succinct proof size suffer from a high overhead on the proof generation time that is super-linear in the size of the statement represented as an arithmetic circuit, limiting their efficiency and scalability in practice. In this paper, we present Orion, a new zero-knowledge argument system that achieves O(N) prover time of field operations and hash functions and O(log2 N) proof size. Orion is concretely efficient and our implementation shows that the prover time is 3.09s and the proof size is 1.5MB for a circuit with 2 20 multiplication gates. The prover time is the fastest among all existing succinct proof systems, and the proof size is an order of magnitude smaller than a recent scheme proposed in Golovnev et al. 2021. In particular, we develop two new techniques leading to the efficiency improvement. (1) We propose a new algorithm to test whether a random bipartite graph is a lossless expander graph or not based on the densest subgraph algorithm. It allows us to sample lossless expanders with an overwhelming probability. The technique improves the efficiency and/or security of all existing zero-knowledge argument schemes with a linear prover time. The testing algorithm based on densest subgraph may be of independent interest for other applications of expander graphs. (2) We develop an efficient proof composition scheme, code switching, to reduce the proof size from square root to polylogarithmic in the size of the computation. The scheme is built on the encoding circuit of a linear code and shows that the witness of a second zero-knowledge argument is the same as the message in the linear code. The proof composition only introduces a small overhead on the prover time. For more information, please see our paper. Show Less

Secret sharing is an essential tool for many distributed applications, including distributed key generation and multiparty computation. For many practical applications, we would like to tolerate network churn, meaning participants can dynamically enter and leave the pool of protocol participants as they please. Such protocols, called Dynamic-committee Proactive Secret Sharing (DPSS) have recently been studied. However, existing DPSS protocols do not gracefully handle faults - the presence of even one unexpectedly slow node can often slow down the whole protocol by a factor of O(n). In this work, we explore optimally fault-tolerant asynchronous DPSS that is not slowed down by crash faults and even handles byzantine faults while maintaining the same performance. We first introduce the first high-threshold DPSS, which offers favorable characteristics relative to prior non-synchronous works in the presence of faults while simultaneously supporting higher privacy thresholds. We then batch-amortize this scheme along with a parallel non-high-threshold scheme which achieves optimal bandwidth characteristics. We implement our schemes and demonstrate that they can compete with prior work in best-case performance while outperforming it in non-optimal settings. For further information, please see our paper. Show Less

The IC3 NFT license is a copyright license specifically designed for use with NFTs. This document describes the technical, conceptual, and doctrinal challenges posed by NFT licensing and explains the design decisions made in drafting a license to solve them. The license itself, which is designed to be used in conjunction with a technical process (such as the one described in Ethereum Improvement Proposal 5218), links a creative work to an NFT so that when the NFT is transferred, so is the license. Link to my work. Show Less

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. Show Less

Frequently, users on the web need to show that they are, for example, not a robot, old enough to access an age restricted video, or eligible to download an ebook from their local public library without being tracked. Anonymous credentials were developed to address these concerns. However, existing schemes do not handle the realities of deployment or the complexities of real world identity. Instead, they make (often incorrect) assumptions, e.g., that the local department of motor vehicles will issue sophisticated cryptographic tokens to show users are over 18. In reality, there are multiple trust sources for a given identity attribute, their credentials have distinctively different formats, and many, if not all, issuers are unwilling to adopt new protocols. We present and build zk-creds, a protocol that uses general-purpose zero-knowledge proofs to 1) remove the need for credential issuers to hold signing keys - credentials can be issued via a transparency log, Byzantine system, or even a blockchain, 2) convert existing identity documents into anonymous credentials without modifying documents or coordinating with their issuing authority, 3) allow for flexible, composable, and complex identity statements over multiple credentials. Concretely, identity assertions using zk-creds take less than 300ms in a real-world scenario of using a passport to anonymously access age-restricted videos. For more information, see our work. Show Less

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. Show Less

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'21) 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. Show Less

Nakamoto's 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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

Front-running attacks, which benefit from advanced knowledge of pending transactions, have proliferated in the blockchain space since the emergence of decentralized finance. Front-running causes devastating losses to honest participants and continues to endanger the fairness of the ecosystem. We present Flash Freezing Flash Boys (F3B), a blockchain architecture that addresses front-running attacks by using threshold cryptography. In F3B, a user generates a symmetric key to encrypt their transaction, and once the underlying consensus layer has finalized the transaction, a decentralized secret-management committee reveals this key. F3B mitigates front-running attacks because, before the consensus group finalizes it, an adversary can no longer read the content of a transaction, thus preventing the adversary from benefiting from advanced knowledge of pending transactions. Unlike other mitigation systems, F3B properly ensures that all unfinalized transactions, even with significant delays, remain private by adopting per-transaction protection. Furthermore, F3B addresses front-running at the execution layer; thus, our solution is agnostic to the underlying consensus algorithm and compatible with existing smart contracts. We evaluated F3B on Ethereum with a modified execution layer and found only a negligible (0.026%) increase in transaction latency, specifically due to running threshold decryption with a 128-member secret-management committee after a transaction is finalized; this indicates that F3B is both practical and low-cost. For further information, please see our paper. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

We revisit Gradecast (Feldman and Micali, STOC'88) 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. Show Less

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. Show Less

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. Show Less

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 Show Less

Money transfer is an abstraction that realizes the core of cryptocurrencies. It has been shown that, contrary to common belief, money transfer in the presence of Byzantine faults can be implemented in asynchronous networks and does not require consensus. Nonetheless, existing implementations of money transfer still require a quadratic message complexity per payment, making attempts to scale hard. In common blockchains, such as Bitcoin and Ethereum, this cost is mitigated by payment channels implemented as a second layer on top of the blockchain allowing to make many off-chain payments between two users who share a channel. Such channels only require on-chain transactions for channel opening and closing, while the intermediate payments are done off-chain with constant message complexity. But payment channels in-use today require synchrony, therefore they are inadequate for asynchronous money transfer systems. In this paper, we provide a series of possibility and impossibility results for payment channels in asynchronous money transfer systems. We first prove a quadratic lower bound on the message complexity of on-chain transfers. Then, we explore two types of payment channels, unidirectional and bidirectional. We define them as shared memory abstractions and prove that in certain cases they can be implemented as a second layer on top of an asynchronous money transfer system whereas in other cases it is impossible. For further information, please see our paper. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

We revisit decentralized random beacons with a focus on practical distributed applications. Decentralized random beacons (Beaver and So, Eurocrypt'93) 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. Show Less

Vector mean estimation is a central primitive in federated analytics. In vector mean estimation, each user i [n] holds a real-valued vector vi [−1, 1]d, and a server wants to estimate the mean of all n vectors. Not only so, we would like to protect each individual user’s privacy. In this paper, we consider the k-sparse version of the vector mean estimation problem, that is, suppose that each user’s vector has at most k non-zero coordinates in its d-dimensional vector, and moreover, k << d. In practice, since the universe size d can be very large (e.g., the space of all possible URLs), we would like the per-user communication to be succinct, i.e., independent of or (poly-)logarithmic in the universe size. In this paper, we are the first to show matching upper- and lower-bounds for the k-sparse vector mean estimation problem under local differential privacy. Specifically, we construct new mechanisms that achieve asymptotically optimal error as well as succinct communication, either under user-level-LDP or event-level-LDP. We implement our algorithms and evaluate them on synthetic as well as real-world datasets. Our experiments show that we can often achieve one or two orders of magnitude reduction in error in comparison with prior works under typical choices of parameters, while incurring insignificant communication cost. For further information, please see our paper. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

Remote Direct Memory Access (RDMA) has been used to accelerate a variety of distributed systems, by providing low-latency, CPU-bypassing access to a remote host’s memory. However, most of the distributed protocols used in these systems cannot easily be expressed in terms of the simple memory READs and WRITEs provided by RDMA. As a result, designers face a choice between introducing additional protocol complexity (e.g., additional round trips) or forgoing the benefits of RDMA entirely. This paper argues that an extension to the RDMA interface can resolve this dilemma. We introduce the PRISM interface, which adds four new primitives - indirection, allocation, enhanced compare-and-swap, and operation chaining. These increase the expressivity of the RDMA interface, while still being implementable using the same underlying hardware features. We show their utility by designing three new applications using PRISM primitives, that require little to no server-side CPU involvement - (1) PRISM-KV, a key-value store, (2) PRISM-RS, a replicated block store, and (3) PRISM-TX, a distributed transaction protocol. Using a software-based implementation of the PRISM primitives, we show that these systems outperform prior RDMA-based equivalents. For more information, please see our paper. Show Less

Strictly serializable (linearizable) services appear to execute transactions (operations) sequentially, in an order consistent with real time. This restricts a transaction’s (operation’s) possible return values and in turn, simplifies application programming. In exchange, strictly serializable (linearizable) services perform worse than those with weaker consistency. But switching to such services can break applications. This work introduces two new consistency models to ease this trade-off - regular sequential serializability (RSS) and regular sequential consistency (RSC). They are just as strong for applications - we prove any application invariant that holds when using a strictly serializable (linearizable) service also holds when using an RSS (RSC) service. Yet they relax the constraints on services—they allow new, better-performing designs. To demonstrate this, we design, implement, and evaluate variants of two systems, Spanner and Gryff, relaxing their consistency to RSS and RSC, respectively. The new variants achieve better read-only transaction and read tail latency than their counterparts. Link to our work. Show Less

Syncing the latest state of a blockchain can be a resource-intensive task, driving (especially mobile) end users towards centralized services offering instant access. To expand full decentralized access to anyone with a mobile phone, we introduce a consensus-agnostic compiler for constructing {\em ultralight clients}, providing secure and highly efficient blockchain syncing via a sequence of SNARK-based state transition proofs, and prove its security formally. Instantiating this, we present Plumo, an ultralight client for the Celo blockchain capable of syncing the latest network state summary in just a few seconds even on a low-end mobile phone. In Plumo, each transition proof covers four months of blockchain history and can be produced for just $25 USD of compute. Plumo achieves this level of efficiency thanks to two new SNARK-friendly constructions, which may also be of independent interest - a new BLS-based offline aggregate multisignature scheme in which signers do not have to know the members of their multisignature group in advance, and a new composite algebraic-symmetric cryptographic hash function. For more information, please see our paper. Show Less

Private set intersection (PSI) allows two mutually distrusting parties each with a set as input, to learn the intersection of both their sets without revealing anything more about their respective input sets. Traditionally, PSI studies the static setting where the computation is performed only once on both parties’ input sets. We initiate the study of updatable private set intersection (UPSI), which allows parties to compute the intersection of their private sets on a regular basis with sets that also constantly get updated. We consider two specific settings. In the first setting called UPSI with addition, parties can add new elements to their old sets. We construct two protocols in this setting, one allowing both parties to learn the output and the other only allowing one party to learn the output. In the second setting called UPSI with weak deletion, parties can additionally delete their old elements every t days. We present a protocol for this setting allowing both parties to learn the output. All our protocols are secure against semi-honest adversaries and have the guarantee that both the computational and communication complexity only grow with the set updates instead of the entire sets. Finally, we implement our UPSI with addition protocols and compare with the state-of-the-art PSI protocols. Our protocols compare favorably when the total set size is sufficiently large, the new updates are sufficiently small, or in networks with low bandwidth. For more information, please see our paper. Show Less

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. Show Less

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. Show Less

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'03]. 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'20]. For further information, please see our paper. Show Less

We model incentive security in non-custodial stablecoins and derive conditions for participation in a stablecoin system across risk absorbers (vaults/CDPs) and holders of governance tokens. We apply option pricing theory to derive closed form solutions to the stakeholders’ problems, and to value their positions within the capital structure of the stablecoin. We derive the optimal interest rate that is incentive compatible, as well as conditions for the existence of equilibria without governance attacks, and discuss implications for designing secure protocols. For more information, please see our paper. Show Less

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. Show Less

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. Show Less

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. Show Less

We are in the process of refining and expanding on this project to apply the techniques to other pairing-based SNARKs. Some folks from CMU asked if we could expand the net to SNARKs like Marlin and Aurora. After looking at these papers, I have concluded that these constructions are too different than the ones I am dealing with to include. Some code from this repository could be useful in formalizing a soundness proof for these SNARKs, but for now, this is future work. Link to our work. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

Financial speculators often seek to increase their potential gains with leverage. Debt is a popular form of leverage, and with over 39.88B USD of total value locked (TVL), the Decentralized Finance (DeFi) lending markets are thriving. Debts, however, entail the risks of liquidation, the process of selling the debt collateral at a discount to liquidators. Nevertheless, few quantitative insights are known about the existing liquidation mechanisms. In this paper, to the best of our knowledge, we are the first to study the breadth of the borrowing and lending markets of the Ethereum DeFi ecosystem. We focus on Aave, Compound, MakerDAO, and dYdX, which collectively represent over 85% of the lending market on Ethereum. Given extensive liquidation data measurements and insights, we systematize the prevalent liquidation mechanisms and are the first to provide a methodology to compare them objectively. We find that the existing liquidation designs well incentivize liquidators but sell excessive amounts of discounted collateral at the borrowers’ expenses. We measure various risks that liquidation participants are exposed to and quantify the instabilities of existing lending protocols. Moreover, we propose an optimal strategy that allows liquidators to increase their liquidation profit, which may aggravate the loss of borrowers. For further information, please see our paper. Show Less

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. Show Less

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. Show Less

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. Show Less

Permissioned ledger systems allow a consortium of members that do not trust one another to execute transactions safely on a set of replicas. Such systems typically use Byzantine fault tolerance (BFT) protocols to distribute trust, which only ensures safety when fewer than 1/3 of the replicas misbehave. Providing guarantees beyond this threshold is a challenge - current systems assume that the ledger is corrupt and fail to identify misbehaving replicas or hold the members that operate them accountable—instead all members share the blame. We describe IA-CCF, a new permissioned ledger system that provides individual accountability. It can assign blame to the individual members that operate misbehaving replicas regardless of the number of misbehaving replicas or members. IA-CCF achieves this by signing and logging BFT protocol messages in the ledger, and by using Merkle trees to provide clients with succinct, universally-verifiable receipts as evidence of successful transaction execution. Anyone can audit the ledger against a set of receipts to discover inconsistencies and identify replicas that signed contradictory statements. IA-CCF also supports changes to consortium membership and replicas by tracking signing keys using a sub-ledger of governance transactions. IA-CCF provides strong disincentives to misbehavior with low overhead - it executes 47,000 tx/s while providing clients with receipts in two network round trips. Link to our work. Show Less

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. Show Less

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. Show Less

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. Show Less

Zero-knowledge SNARKs (zk-SNARKs) are non-interactive proof systems with short and efficiently verifiable proofs that do not reveal anything more than the correctness of the statement. zk-SNARKs are widely used in decentralised systems to address privacy and scalability concerns. A major drawback of such proof systems in practice is the requirement to run a trusted setup for the public parameters. Moreover, these parameters set an upper bound to the size of the computations or statements to be proven, which results in new scalability problems. We design and implement SnarkPack, a new argument that further reduces the size of SNARK proofs by means of aggregation. Our goal is to provide an off-the-shelf solution that is practical in the following sense - (1) it is compatible with existing deployed SNARK systems, (2) it does not require any extra trusted setup. SnarkPack is designed to work with Groth16 scheme and has logarithmic size proofs and a verifier that runs in logarithmic time in the number of proofs to be aggregated. Most importantly, SnarkPack reuses the public parameters from Groth16 system. SnarkPack can aggregate 8192 proofs in 8.7s and verify them in 163ms, yielding a verification mechanism that is exponentially faster than other solutions. SnarkPack can be used in blockchain applications that rely on many SNARK proofs such as Proof-of-Space or roll-up solutions. For more information, please see our paper. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

Edge computing and caching have emerged as key technologies in the future communication network to enhance the user experience, reduce backhaul traffic, and enable various Internet of Things applications. Different from conventional resources like CPU and memory that can be utilized by only one party at a time, a cached data item, which can be considered as a public good, can serve multiple parties simultaneously. Therefore, instead of independent caching, it is beneficial for the parties (e.g., Telcos) to cooperate and proactively store their common items in a shared cache that can be accessed by all the parties at the same time. In this work, we present MPCCache, a novel privacy-preserving Multi-Party Cooperative Cache sharing framework, which allows multiple network operators to determine a set of common data items with the highest access frequencies to be stored in their capacity-limited shared cache while guaranteeing the privacy of their individual datasets. The technical core of our MPCCache is a new construction that allows multiple parties to compute a specific function on the intersection set of their datasets, without revealing the intersection itself to any party. We evaluate our protocols to demonstrate their practicality and show that MPCCache scales well to large datasets and achieves a few hundred times faster compared to a baseline scheme that optimally combines existing MPC protocols. Link to our paper. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

Decentralized Finance (DeFi), a blockchain powered peer-to-peer financial system, is mushrooming. One and a half years ago the total value locked in DeFi systems was approximately 700m USD, now, as of September 2021, it stands at around 100bn USD. The frenetic evolution of the ecosystem has created challenges in understanding the basic principles of these systems and their security risks. In this Systematization of Knowledge (SoK) we delineate the DeFi ecosystem along the following axes - its primitives, its operational protocol types and its security. We provide a distinction between technical security, which has a healthy literature, and economic security, which is largely unexplored, connecting the latter with new models and thereby synthesizing insights from computer science, economics and finance. Finally, we outline the open research challenges in the ecosystem across these security types. For further information, please see our paper. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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 (n/(n−f))2· poly log λ 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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

Nakamoto's famous blockchain protocol enables achieving consensus in a so-called permissionless setting -- anyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents *sybil attacks* (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. *moderately hard functions*) introduced by Dwork and Naor (Crypto 1992). Recent work by Garay et al. (EuroCrypt 2015) and Pass et al. (EuroCrypt 2017) demonstrate that this protocol provably achieves consistency and liveness assuming a) honest players control a majority of the computational power in the network, b) the puzzle-difficulty is appropriately set as a function of the maximum network message delay and the total computational power of the network, and c) the computational puzzle is modeled as a random oracle. These works, however, leave open the question of how to set the puzzle difficulty in a setting where the computational power in the network is changing. The Nakamoto protocol indeed also includes a description of a difficulty update procedure. a recent work by Garay et al. (Crypto 2017) indeed shows a variant of this difficulty adjustment procedure can be used to get a sound protocol as long as the computational power does not change too fast -- however, under two restrictions - 1) their analysis assumes that the attacker cannot delays network messages, and 2) the changes in computational power in the network changes are statically set (i.e., cannot be adapptively selected by the adversary). In this work, we show the same result but without these two restrictions, demonstrating the soundness of a (slightly different) difficulty update procedure, assuming only that the computational power in the network does not change too fast (as a function of the maximum network message delays), as an additional contribution, our analysis yields a tight bound on the *chain quality* of the protocol. Link to our work. Show Less

Investigative journalists collect large numbers of digital documents during their investigations. These documents can greatly benefit other journalists' work. However, many of these documents contain sensitive information. Hence, possessing such documents can endanger reporters, their stories, and their sources. Consequently, many documents are used only for single, local, investigations. We present DatashareNetwork, a decentralized and privacy-preserving search system that enables journalists worldwide to find documents via a dedicated network of peers. DatashareNetwork combines well-known anonymous authentication mechanisms and anonymous communication primitives, a novel asynchronous messaging system, and a novel multi-set private set intersection protocol (MS-PSI) into a *decentralized peer-to-peer private document search engine*. We prove that DatashareNetwork is secure; and show using a prototype implementation that it scales to thousands of users and millions of documents. For further information, please see our paper. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

The "Black Thursday'' crisis in cryptocurrency markets demonstrated deleveraging risks in over-collateralized non-custodial stablecoins. We develop a stochastic model that helps explain deleveraging crises in these over-collateralized systems. In our model, the stablecoin supply is decided by speculators who optimize the profitability of a leveraged position while incorporating the forward-looking cost of collateral liquidations, which involves the endogenous price of the stablecoin. We formally characterize regimes that are interpreted as stable and unstable for the stablecoin. We prove bounds on quadratic variation and the probability of large deviations in the stable domain and we demonstrate distinctly greater price variance in the unstable domain. We identify a deflationary deleveraging spiral by means of a submartingale. These deleveraging spirals, which resemble short squeezes, lead to faster collateral drawdown (and potential shortfalls) and are accompanied by higher price variance, as experienced on Black Thursday. We conclude by discussing non-custodial ways in which the issues raised in this paper can be mitigated. For further information, please see our paper. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

We present Handel, a Byzantine-tolerant aggregation protocol that allows for the quick aggregation of cryptographic signatures over a WAN. Handel has polylogarithmic time, communication and processing complexity. We implemented Handel as an open source Go library with a flexible design to support any associative and commutative aggregation function. We tested Handel on 2000 AWS instances running two nodes per instance and located in 10 AWS regions. The 4000 signatures are aggregated in less than 900 milliseconds with an average per-node communication cost of 56KB. Link to our work. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

We develop a model of stable assets, including noncustodial stablecoins backed by cryptocurrencies. Such stablecoins are popular methods for bootstrapping price stability within public blockchain settings. We demonstrate fundamental results about dynamics and liquidity in stablecoin markets, demonstrate that these markets face deleveraging spirals that cause illiquidity during crises, and show that these stablecoins have `stable' and `unstable' domains. Starting from documented market behaviors, we explain actual stablecoin movements; further our results are robust to a wide range of potential behaviors. In simulations, we show that these systems are susceptible to high tail volatility and failure. Our model builds foundations for stablecoin design. Based on our results, we suggest design improvements that can improve long-term stability and suggest methods for solving pricing problems that arise in existing stablecoins. In addition to the direct risk of instability, our dynamics results suggest a profitable economic attack during extreme events that can induce volatility in the `stable' asset. This attack additionally suggests ways in which stablecoins can cause perverse incentives for miners, posing risks to blockchain consensus. For more information, please see our paper. Show Less

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. Show Less

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. Show Less

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 paper. Show Less

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. Show Less

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. Show Less

As cryptographic tokens and altcoins are increasingly being built to serve as utility tokens, the notion of useful work consensus protocols, as opposed to number-crunching PoW consensus, is becoming ever more important. In such contexts, users get rewards from the network after they have acrried out some specific task useful for the network. While in some cases the proof of some utility or service can be proved, the majority of tasks are impossible to verify. In order to deal with such cases, we design Proof-Of-Prestige (PoP) - a reward system that can run on top of Proof-of-Stake blockchains. PoP introduces prestige which is a volatile resource and, in contrast to coins, regenerates over time. Prestige can be gained by performing useful work, spent when benefiting from services and directly translates to users minting power. PoP is resistant against Sybil and Collude attacks and can be used to reward workers for completing unverifiable tasks, while keeping the system free for the end-users. We use two exemplar use-cases to showcase the usefulness of PoP and we build a simulator to assess the cryptoeconomic behaviour of the system in terms of prestige transfer between nodes. For more information, please see our paper. Show Less

Blockchains, and specifically smart contracts, have promised to create fair and transparent trading ecosystems. Unfortunately, we show that this promise has not been met. We document and quantify the widespread and rising deployment of arbitrage bots in blockchain systems, specifically in decentralized exchanges (or "DEXes''). Like high-frequency traders on Wall Street, these bots exploit inefficiencies in DEXes, paying high transaction fees and optimizing network latency to frontrun, i.e., anticipate and exploit, ordinary users DEX trades. We study the breadth of DEX arbitrage bots in a subset of transactions that yield quantifiable revenue to these bots. We also study bots profit-making strategies, with a focus on blockchain-specific elements. We observe bots engage in what we call priority gas auctions (PGAs), competitively bidding up transaction fees in order to obtain priority ordering, i.e., early block position and execution, for their transactions. PGAs present an interesting and complex new continuous-time, partial-informtion, game-theoretic model that we formalize and study. We release an interactive web portal, frontrun.me, to provide the community with real-time data on PGAs. We additionally show that high fees paid for priority transaction ordering poses a systemic risk to consensus-layer security. We explain that such fees are just one form of a general phenomenon in DEXes and beyonf - what we call miner extractable value (MEV) - that poses concrete, measurable, consensus-layer security risks. We show empirically that MEV poses a realistic threat to Ethereum today. Our work highlights the large, complex risks created by transaction-ordering dependencies in smart contracts and the ways in which traditional forms of financial-market exploitation are adapting to and penetrating blockchain economies. For further information, please see our paper. Show Less

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. Show Less

Fighting frauds in the automotive industry is an ongoing challenge. Concerned by this problem are not only the owners and potential buyers of second-hand vehicles, but also entities like insurance companies, garages, car dealers, police, etc. In our work, we present a solution for extablishing trust between these parties, by keeping records of repairs and maintenance car checks in a decentralized ledger. For this proof of concept, we use the ByzCoin blockchain protocol together with the Calypso framework, which provides a secure way of storing and sharing confidential data over a blockchain with dynamic management of access policies and ownership of the vehicle biography. The cnducted evaluation of our implementation shows that the system works correctly also with larger networks, and up to 500 simultaneous car enrollments or repot submissions. For more information, please see our paper. Show Less

Synchronous solutions for Byzantine Fault Tolerance (BFT) can tolerate up to minority faults. In this work, we present Sync HotStuff, a surprisingly simple and intuitive synchronous BFT solution that achieves consensus with a latency of 2 delta in the steady state (where delta is a synchronous message delay upper bound). In addition, Sync HotStuff ensures safety in a weaker synchronous model in which the synchrony assumption does not have to hold for all replicas all the time. Moreover, Sync HotStuff has optimistic responsiveness, i.e., it advances at network speed when less than one-quarter of the replicas are nor responding. Borrowing from practical partially synchronous BFt solutions, Sync HotStuff has a two-phased leader-based structure, and has been fully prototyped under the standard synchrony assumption. When tolerating a single fault, Sync HotStuff achieves a throughput of over 280 Kops/sec under typical network performance, which is comparable to the best known partially synchronous solution. For more information, please see our paper. Show Less

We propose Path Oblivious Heap, an extremely simple, practical, and optimal oblivious priority queue. Our construction also implies a practical and optimal oblivious sorting algorithm which we call Path Oblivious Sort. Not only are our alogorithms asymptotically optimal, we show that their practical performance is only a small constant factor worse than insecure baselines. More specifically, assuming roughly logarithmic client private storage, Path Oblivious Heap consumes 2x to 7x more bandwidth than the ordinary insecure binary heap, and Path Oblivious Sort consumes 4.5x to 6x more bandwidth than the insecure Merge Sort. We show that these performance results improve existing works by 1-2 orders of magnitude. Finally, we evaluate our algorithm for a multi-party computation scenario and show 7x to 8x reduction in the number of symmetric encryptions relative to the state of the art. Link to my work. Show Less

State machine Replication (SMR) is an important abstraction for a set of nodes to agree on an ever-growing, linearly-ordered log of transactions. In decentralized cryptocurrency applications, we would like to design SMR protocols that 1) resist adaptive corruptions, and 2) achieve small bandwidth and small confirmation time. All past approaches towards constructing SMR fail to achieve either small confirmation time or small bandwidth under adaptive corruptions (without resorting to strong assumptions such as the erasure model of proof-of-work). We propose a novel paradigm for reaching consensus that departs significantly from classical approaches. Our protocol is inspired by a social phenomenon called herding, where people tend to make choices considered as the social norm. In our consensus protocol, leader election and voting are coalesced into a single (randomized) process - in every round, every node tries to cast a vote for what it views as the {\it most popular} item do far, such a voting attempt is not always successful, but rather, successful with a certain probability. Importantly, the probability that the node is elected to vote for v is independent from the probability it is elected to vote for v′≠v. We will show how to realize such a distributed, randomized election process using appropriate, adaptively secure cryptographic building blocks. We show that amazingly, not only can this new paradigm achieve consensus (e.g., on a batch of unconfirmed transactions in a cryptocurrency system), but it also allows us to derive the first SMR protocol which, even under adaptive corruptions, requires only polylogarithmically many rounds and polylogarithmically many honest messages to be multicast to confirm each batch of transactions, and importantly, we attain these guarantees under standard cryptographic assumptions. For more information, please see our paper. Show Less

Although Bitcoin in its original whitepaper stated that it offers anonymous transactions, de-anonymization techniques have found otherwise. Therefore, alternative cryptocurrencies, like Dash, Monero, and Zcash, were developed to provide better privacy. As Edward Snowden stated, "Zcash's privacy tech makes it the most interesting Bitcoin alternative (...) because the privacy properties of it are truly unique". Zcash's privacy is based on peer-reviewed cryptographic constructions, hence it is considered to provide the foundations for the best anonymity. However, even Zcash makes some provacy concessions. It does not protect users privacy in the presence of a global adversary who is able to observe the whole network, and hence correlate the parties exchanging money, by using their network addresses. The recent empirical analysis of Zcash shows, that users often choose naive ways while performing the protocol operations, not realizing that it degrades their anonymity. In this talk, we will discuss an extension of Zcash using mix networks to enhance the privacy guarantees of users that choose to remain anonymous by tackling two major security challenges - 1) at the application layer of the scheme and 2) at its network layer. For more information, please see our paper. Show Less

Off-chain protocols (or so-called Layer 2) are heralded as a scaling solution for cryptocurrencies. One prominent approach, state channels, allows a group of parties to transact amongst themselves and the global blockchain is only used as a last resort to self-enforce any disputed transactions. To evaluate state channels as a scaling solution, we provide a proof of concept implementation for a two-player battleship game. It fits a category of applications that are not considered reasonable to execute on the blockchain, but it is widely perceived as an ideal application for off-chain protocols. We explore the minimal modifications required to deploy the battleship game as a state channel and propose a new state channel construction, Kitsune, which combines features from existing constructions. While in the optimistic case we demonstrate the battleship game can be played efficiently in a state channel, the requirement for unanimous off-chain agreement introduces new economic and time-based attacks that can render the game as unreasonable to play. For more information, please see our work. Show Less

Murphy, Murky, Mopey, Moody, and Morose decide to write a paper together over the Internet and submit it to the prestigious CRYPTO 2019 conference that has the most amazing PC. They encounter a few problems. First, not everyone is online every day - some are lazy and go skiing on Mondays, others cannot use git correctly and they are completely unaware that they are losing messages. Second, a small subset of the co-authors may be secretly plotting to disrupt the project (e.g., because they are writing a competing paper in stealth). Suppose that each day, sufficiently many honest co-authors are online (and use git correctly), moreover, suppose that messages checked into git on Monday can be correctly received by honest and online co-authors on Tuesday or any future day. Can the honest co-authors successfully finish the paper in a small number of days such that they make the CRYPTO deadline, and perhaps importantly, can all the honest co-authors, including even those who are lazy and those who sometimes use git incorrectly, agree on the final theorem? For more information, please see our paper. Show Less

We present a family of replay attacks against sharded distributed ledgers, that target cross-shard consensus protocols, such as the recently proposed Chainspace and Omniledger. They allow the attacker, with network access only, to double-spend or lock resources with minimal efforts. The attacker can act independently without colluding with any nodes, and succeed even if all nodes are honest. Most of the attacks can also exhibit themselves as faults under periods of asynchrony. These attacks are effective against both shard-led and client-led cross-shard consensus approaches. Finally, we present Byzcuit - a new cross-shard consensus protocol that is immune to those attacks. We implement a prototype of Byzcuit and evaluate it on a real cloud-based testbed, showing that our defenses impact performance minimally, and overall performance surpasses previous works. For further information, please see our work. Show Less

Zero-knowledge proofs have become an important tool for addressing privacy and scalability concerns in cryptocurrencies and other applications. In many systems each client downloads and verifies every new proof, and so proofs must be small and cheap to verify. The most practical schemes require either a trusted setup, as in (pre-processing) zk-SNARKs, or verification complexity that scales linearly with the complexity of the relation, as in Bulletproofs. The structured reference strings required by most zk-SNARK schemes can be constructed with multi-party computation protocols, but the resulting parameters are specific to an individual relation. Groth et al. discovered a zk-SNARK protocol with a universal and updateable structured reference string, however the string scales quadratically in the size of the supported relations. Here we describe a zero-knowledge SNARK, Sonic, which supports a universal and continually updateable structured reference string that scales linearly in size. Sonic proofs are constant size, and in the batch verification context the marginal cost of verification is comparable with the most efficient SNARKs in the literature. We also describe a generally useful technique in which untrusted "helpers'' can compute advice which allows batches of proofs to be verified more efficiently. For more information, please see our paper. Show Less

Blockchain-based cryptocurrencies prioritize transactions based on their fees, creating a unique kind of fee market. Empirically, this market has failed to yield stable equilibria with predictable prices for desired levels of service. We argue that this is due to the absence of a dominant strategy equilibrium in the current fee mechanism. We propose an alternative fee setting mechanism that is inspired by generalized second price auctions. The design of such a mechanism is challenging because miners can use any criteria for including transactions and can manipulate the results of the auction after seeing the proposed fees. Nonetheless, we show that our proposed protocol is free from manipulation as the number of users increases. We further show that, for a large number of users and miners, the gain from manipulation is small for all parties. This results in users proposing fees that represent their true utility and lower variance of revenue for miners. Historical analysis shows that Bitcoin users could have saved $272,528,000 in transaction fees while miners could have reduced the variance of fee income by an average factor of 7.4 times. For further information, please see our paper. Show Less

Privacy was one of the key points mentioned in Nakamoto's Bitcoin whitepaper, and one of the selling points of Bitcoin in its early stages. In hindsight, however, de-anonymising Bitcoin users turned out to be more feasible than expected. Since then, privacy focused cryptocurrencies such as Zcash and Monero have surfaced. Both of these examples cannot be described as fully successful in their aims, as recent research has shown. Incentives are integral to the security of cryptocurrencies, so it is interesting to investigate whether they could also be aligned with privacy goals. A lack of privacy often results from low user counts, resulting in low anonymity sets. Could users be incentivised to use the privacy preserving implementations of the systems they use? Not only is Zcash much less used than Bitcoin (which forket from), but most Zcash transactions are simply transparent transactions, rather than the (at least intended to be) privacy-preserving shielded transactions. This paper and poster briefly discusses how incentives could be incorporated into systems like cryptocurrencies with the aim of achieving privacy goals. We take Zcash as example, but the ideas discussed could apply to other privacy-focused cryptocurrencies. This work was presented as a poster at OPERANDI 2018, the poster can be found within this short document. Link to our work. Show Less

Motivated by applications in blockchains and sensor networks, we consider a model of n nodes trying to reach consensus on their majority bit. Each node i is assigned a bit at time zero, and is a finite automaton with m bits of memory (i.e., 2m states) and a Poisson clock. When the clock of i rings, i can choose to communicate, and is then matched to a uniformly chosen node j. The nodes j and i may update their states based on the state of the other node. Previous work has focused on minimizing the number of communications. We show that when m>3logloglog(n), consensus can be reached at linear communication cost, but this is impossible if mpaper. Show Less

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. Show Less

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 workflows, developers can build a larger class of decentralized applications, such as provably-secure and fair loteries or e-voting. For further information, please see our paper. Show Less

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. Show Less

Zero-confirmation transactions, i.e. transactions that have been broadcast but are still pending to be included in the blockchain, have gained attention in order to enable fast payments in Bitcoin, shortening the time for performing payments. Fast payments are desirable in certain scenarios, for instance, when buying in vending machines, fast food restaurants, or withdrawing from an ATM. Despite being quickly propagated through the network, zero-confirmation transactions are not protected against double-spending attacks, since the double-spending protection Bitcoin offers relies on the blockchain and, by definition, such transactions are not yet included in it. In this paper, we propose a double-spending prevention mechanism for Bitcoin zero-confirmation transactions. Our proposal is based on exploiting the flexibility of the Bitcoin scripting language together with a well-known vulnerability of the ECDSA signature scheme to discourage attackers from performing such an attack. For more information, please see our paper. Show Less

Real world protocols often involve human choices that depend on incentives, including when they fail and require fail-safe or fail-deadly mechanisms. We look at three example systems (the EMV protocol, consensus in cryptocurrencies, and Tor) in this context, paying particular attention to the role that incentives play in fail-safe and fail-deadly situations. We argue that incentives should explicitly be taken into account in the design of security protocols, and discuss general challenges in doing so. For further information, please see our paper. Show Less

We show that PRAMs can be obliviously simulated with perfect security, incurring only O(logNloglogN) blowup in parallel runtime, O(log3N) blowup in total work, and O(1) blowup in space relative to the original PRAM. Our results advance the theoretical understanding of Oblivious (Parallel) RAM in several respects. First, prior to our work, no perfectly secure Oblivious Parallel RAM (OPRAM) construction was known, and we are the first in this respect. Second, even for the sequential special case of our algorithm (i.e., perfectly secure ORAM), we not only achieve logarithmic improvement in terms of space consumption relative to the state-of-the-art, but also significantly simplify perfectly secure ORAM constructions. Third, our perfectly secure OPRAM scheme matches the parallel runtime of earlier statistically secure schemes with negligible failure probability. Since we remove the dependence (in performance) on the security parameter, our perfectly secure OPRAM scheme in fact asymptotically outperforms known statistically secure ones if (sub-)exponentially small failure probability is desired. Our techniques for achieving small parallel runtime are novel and we employ special expander graphs to derandomize earlier statistically secure OPRAM techniques—this is the first time such techniques are used in the constructions of ORAMs/OPRAMs. For more information, please see our paper. Show Less

Most classical consensus protocols rely on a leader to coordinate nodes’ voting efforts. One novel idea that stems from blockchain-style consensus is to rely, instead, on a “longest-chain” idea for such coordination. Such a longest-chain idea was initially considered in randomized protocols, where in each round, a node has some probability of being elected a leader who can propose the next block. Recently, well-known systems have started implementing the deterministic counterpart of such longest-chain protocols — the deterministic counterpart is especially attractive since it is even simpler to implement than their randomized cousins. A notable instantiation is the Aura protocol which is shipped with Parity’s open-source Ethereum implementation. Interestingly, mathematical analyses of deterministic, longest-chain protocols are lacking even though there exist several analyses of randomized versions. In this paper, we provide the first formal analysis of deterministic, longest-chain-style consensus. We show that a variant of the Aura protocol can defend against a Byzantine adversary that controls fewer than 1/3 fraction of the nodes, and this resilience parameter is tight by some technical interpretation. Based on insights gained through our mathematical treatment, we point out that Aura’s concrete instantiation actually fails to achieve the resiliene level they claim. Finally, while our tight proof for the longest-chain protocol is rather involved and non-trivial, we show that a variant of the “longest-chain” idea which we call “largest-set” enables a textbook construction that admits a simple proof (albeit with slower confirmation). Link to my work. Show Less

Sorting extremely large datasets is a frequently occuring task in practice. These datasets are usually much larger than the computer's main memory - thus external memory sorting algorithms, first introduced by Aggarwal and Vitter (1988), are often used. The complexity of comparison based external memory sorting has been understood for decades by now, however the situation remains elusive if we assume the keys to be sorted are integers. In internal memory, one can sort a set of n integer keys of Θ(lgn) bits each in O(n) time using the classic Radix Sort algorithm, however in external memory, there are no faster integer sorting algorithms known than the simple comparison based ones. In this paper, we present a tight conditional lower bound on the complexity of external memory sorting of integers. Our lower bound is based on a famous conjecture in network coding by Li and Li, who conjectured that network coding cannot help anything beyond the standard multicommodity flow rate in undirected graphs. The only previous work connecting the Li and Li conjecture to lower bounds for algorithms is due to Adler et al. Adler et al. indeed obtain relatively simple lower bounds for oblivious algorithms (the memory access pattern is fixed and independent of the input data). Unfortunately obliviousness is a strong limitations, especially for integer sorting - we show that the Li and Li conjecture implies an Ω(nlogn) lower bound for internal memory oblivious sorting when the keys are Θ(lgn) bits. This is in sharp contrast to the classic (non-oblivious) Radix Sort algorithm. Indeed going beyond obliviousness is highly non-trivial - we need to introduce several new methods and involved techniques, which are of their own interest, to obtain our tight lower bound for external memory integer sorting. For further information, please see our paper. Show Less

Ethereum, the second-largest cryptocurrency valued at a peak of $138 billion in 2018, is a decentralized, Turing-complete computing platform. Although the stability and security of Ethereum—and blockchain systems in general—have been widely-studied, most analysis has focused on application level features of these systems such as cryptographic mining challenges, smart contract semantics, or block mining operators. Little attention has been paid to the underlying peer-to-peer (P2P) networks that are responsible for information propagation and that enable blockchain consensus. In this work, we develop NodeFinder to measure this previously opaque network at scale and illuminate the properties of its nodes. We analyze the Ethereum network from two vantage points, a three-month long view of nodes on the P2P network, and a single day snapshot of the Ethereum Mainnet peers. We uncover a noisy DEVp2p ecosystem in which fewer than half of all nodes contribute to the Ethereum Mainnet. Through a comparison with other previously studied P2P networks including BitTorrent, Gnutella, and Bitcoin, we find that Ethereum differs in both network size and geographical distribution. For more information, please see our paper. Show Less

Cryptocurrencies record transactions between parties in a blockchain maintained by a peer-to-peer network. In most cryptocurrencies, transactions explicitly identify the previous transaction providing the funds they are spending, revealing the amount and sender/recipient pseudonyms. This is a considerable privacy issue. Zerocash resolves this by using zero-knowledge proofs to hide both the source, destination and amount of the transacted funds. To receive payments in Zerocash, however, the recipient must scan the blockchain, testing if each transaction is destined for them. This is not practical for mobile and other bandwidth constrained devices. In this paper, we build ZLiTE, a system that can support the so-called “light clients”, which can receive transactions aided by a server equipped with a Trusted Execution Environment. Even with the use of a TEE, this is not a trivial problem. First, we must ensure that server processing the blockchain does not leak sensitive information via side channels. Second, we need to design a bandwidth efficient mechanism for the client to keep an up-to-date version of the witness needed in order to spend the funds they previously received. Link to our work. Show Less

Interest in cryptocurrencies has skyrocketed since their introduction a decade ago, with hundreds of billions of dollars now invested across a landscape of thousands of different cryptocurrencies. While there is significant diversity, there is also a significant number of scams as people seek to exploit the current popularity. In this paper, we seek to identify the extent of innovation in the cryptocurrency landscape using the open-source repositories associated with each one. Among other findings, we observe that while many cryptocurrencies are largely unchanged copies of Bitcoin, the use of Ethereum as a platform has enabled the deployment of cryptocurrencies with more diverse functionalities. For more information, please see our paper. Show Less

Transaction throughput, confirmation latency and confirmation reliability are fundamental performance measures of any blockchain system in addition to its security. In a decentralized setting, these measures are limited by two underlying physical network attributes - communication capacity and speed-of-light propagation delay. Existing systems operate far away from these physical limits. In this work we introduce Prism, a new proof-of-work blockchain protocol, which can achieve 1) security against up to 50% adversarial hashing power, 2) optimal throughput up to the capacity C of the network, 3) confirmation latency for honest transactions proportional to the propagation delay D, with confirmation error probability exponentially small in CD, and 4) eventual total ordering of all transactions. Our approach to the design of this protocol is based on deconstructing the blockchain into its basic functionalities and systematically scaling up these functionalities to approach their physical limits. For more information, please see our paper. Show Less

Despite their usage of pseudonyms rather than persistent identifiers, most existing cryptocurrencies do not provide users with any meaningful levels of privacy. This has prompted the creation of privacy enhanced cryptocurrencies, such as Monero and Zcash, which are specically designed to counteract the tracking analysis possible in currencies like Bitcoin. These cryptocurrencies, however, also suffer from some drawbacks - in both Monero and Zcash, the set of potential unspent coins is always growing, which means users cannot store a concise representation of the blockchain. Additionally, Zcash requires a common reference string and the fact that addresses are reused multiple times in Monero has led to attacks to its anonymity. In this paper we propose a new design for anonymous cryptocurrencies, Quisquis, that achieves provably secure notions of anonymity. Quisquis stores a relatively small amount of data, does not require trusted setup, and in Quisquis each address appears on the blockchain at most twice - once when it is generated as output of a transaction, and once when it is spent as input to a transaction. Our result is achieved by combining a DDH-based tool (that we call updatable keys) with efficient zero-knowledge arguments. For further information, please see our paper. Show Less

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. Show Less

Classical-style BFT protocols use two or more rounds of voting to confirm each block, e.g., in PBFT, they are called the “prepare” round and the “commit” round respectively. Recently, an elegant pipelining idea came out of the cryptocurrency community, i.e., if each block required two rounds of voting, why not piggyback the second round on the next block’s voting? We refer to this idea as the pipelined-BFT paradigm. We describe a simple partially synchronous blockchain protocol called PaLa that is inspired by the pipelined-BFT paradigm. In PaLa, a proposer proposes a block extending the freshest notarized chain seen so far. Consensus nodes vote on the proposal if certain conditions are met. When a block gains at least 2n 3 votes it becomes notarized. A block becomes finalized if the next immediate block becomes notarized too. We propose a conceptually simple and provably secure committee rotation algorithm for PaLa. We also describe a generalization called “doubly-pipelined PaLa” that is geared towards settings that require high throughput. For more information, please see our paper. Show Less

Ledger-based systems that support rich applications often suffer from two limitations. First, validating a transaction requires re-executing the state transition that it attests to. Second, transactions not only reveal which application had a state transition but also reveal the application’s internal state. We design, implement, and evaluate Zexe, a ledger-based system where users can execute offline computations and subsequently produce transactions, attesting to the correctness of these computations, that satisfy two main properties. First, transactions hide all information about the offline computations. Second, transactions can be validated in constant time by anyone, regardless of the offline computation. The core of Zexe is a construction for a new cryptographic primitive that we introduce, decentralized private computation (DPC) schemes. In order to achieve an efficient implementation of our construction, we leverage tools in the area of cryptographic proofs, including succinct zero knowledge proofs and recursive proof composition. Overall, transactions in Zexe are 968 bytes regardless of the offline computation, and generating them takes less than 1 min plus a time that grows with the offline computation. We demonstrate how to use Zexe to realize privacy-preserving analogues of popular applications - private user-defined assets and private decentralized exchanges for these assets. For more information, please see our paper. Show Less

The popularity surrounding blockchains has naturally led to research into its applicability in many areas. However, Nakamoto-style blockchains possess several characteristics that make them inappropriate for many purposes in the Internet of Things (IoT) domain. Notably, they are power-intensive and require high network connectivity. These requirements are fundamentally incompatible with IoT where nodes may have limited power and sporadic network access. We are designing a blockchain approach for IoT environments called Vegvisir. Vegvisir is a partition-tolerant blockchain for use in power-constrained IoT environments with limited network access. Under the hood, it is a membership-based, directed acyclic graph (DAG)-structured blockchain [1]. It is motivated by and ideally suited for paramedics and firefighters in disaster scenarios. For instance, it can be used to aid in many tasks during disaster response where network connectivity is poor or nonexistent - namely, it is a blockchain, so provides the abstraction of an append-only log of transactions that is tamperproof. Link to our work. Show Less

We describe PiLi, an extremely simple synchronous blockchain that tolerates minority corruptions. The protocol description is the extremely natural and intuitive. Informally, every epoch, an eligible proposer proposes a block (tagged with the current epoch) extending the freshest notarized chain observed so far. Nodes vote on all valid proposals from eligible proposers as long as 1) the proposed block extends from a parent chain has been notarized in the node’s view, and 2) this parent is “not too stale”. When a block gains votes from the majority of nodes, it is considered notarized but not necessarily final. If a node observes a notarized chain ending with 6 blocks of consecutive epochs and no other notarized blocks of these 6 epochs have been seen, then this notarized chain except the trailing 5 blocks are considered final. For further information, please see our paper. Show Less

This paper presents the design and implementation of Obladi, the first system to provide ACID transactions while also hiding access patterns. Obladi uses as its building block oblivious RAM, but turns the demands of supporting transactions into a performance opportunity. By executing transactions within epochs and delaying commit decisions until an epoch ends, Obladi reduces the amortized bandwidth costs of oblivious storage and increases overall system throughput. These performance gains, combined with new oblivious mechanisms for concurrency control and recovery, allow Obladi to execute OLTP workloads with reasonable throughput - it comes within 5x to 12x of a non-oblivious baseline on the TPC-C, SmallBank, and FreeHealth applications. Latency overheads, however, are higher (70x on TPC-C). Link to our work. Show Less

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. Typically, instead of validating block data, they assume that the chain favoured by the blockchain's consensus algorithm only contains valid 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, we can eliminate the honest-majority assumption, 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 (e.g. via sharding or bigger blocks) while maintaining a strong assurance that on-chain data is available and valid. We present, implement, and evaluate a novel fraud and data availability proof system. For further information, please see our paper. Show Less

Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC '87 and J. ACM '96) is a technique for provably obfuscating programs' access patterns, such that the access patterns leak no information about the programs' secret inputs. To compile a general program to an oblivious counterpart, it is well-known that Ω(logN) amortized blowup is necessary, where N is the size of the logical memory. This was shown in Goldreich and Ostrovksy's original ORAM work for statistical security and in a somewhat restricted model (the so called balls-and-bins model), and recently by Larsen and Nielsen (CRYPTO '18) for computational security. A long standing open question is whether there exists an optimal ORAM construction that matches the aforementioned logarithmic lower bounds (without making large memory word assumptions, and assuming a constant number of CPU registers). In this paper, we resolve this problem and present the first secure ORAM with O(logN) amortized blowup, assuming one-way functions. Our result is inspired by and non-trivially improves on the recent beautiful work of Patel et al. (FOCS '18) who gave a construction with O(logN⋅loglogN) amortized blowup, assuming one-way functions. One of our building blocks of independent interest is a linear-time deterministic oblivious algorithm for tight compaction. Given an array of n elements where some elements are marked, we permute the elements in the array so that all marked elements end up in the front of the array. Our O(n) algorithm improves the previously best known deterministic or randomized algorithms whose running time is O(n⋅logn) or O(n⋅loglogn), respectively. Link to our work. Show Less

Proof-of-stake (PoS) is a promising approach for designing efficient blockchains, where block proposers are randomly chosen with probability proportional to their stake. A primary concern with PoS systems is the "rich getting richer'' phenomenon, whereby wealthier nodes are more likely to get elected, and hence reap the block reward, making them even wealthier. In this paper, we introduce the notion of equitability, which quantifies how much a proposer can amplify her stake compared to her initial investment. Even with everyone following protocol (i.e., honest behavior), we show that existing methods of allocating block rewards lead to poor equitability, as does initializing systems with small stake pools and/or large rewards relative to the stake pool. We identify a \emph{geometric} reward function, which we prove is maximally equitable over all choices of reward functions under honest behavior and bound the deviation for strategic actions, the proofs involve the study of optimization problems and stochastic dominances of Polya urn processes, and are of independent mathematical interest. These results allow us to provide a systematic framework to choose the parameters of a practical incentive system for PoS cryptocurrencies. For further information, please see our work. Show Less

Decentralized blockchains offer attractive advantages over traditional payments such as the ability to operate without a trusted authority and increased user privacy. However, the verification of blockchain payments requires the user to download and process the entire chain which can be infeasible for resource-constrained devices, such as mobile phones. To address such concerns, most major blockchain systems support lightweight clients that outsource most of the computational and storage burden to full blockchain nodes. However, such payment verification methods leak considerable information about the underlying clients, thus defeating user privacy that is considered one of the main goals of decentralized cryptocurrencies. In this paper, we propose a new approach to protect the privacy of lightweight clients in blockchain systems like Bitcoin. Our main idea is to leverage commonly available trusted execution capabilities, such as SGX enclaves. We design and implement a system called BITEwhere enclaves on full nodes serve privacy-preserving requests from lightweight clients. As we will show, naive serving of client requests from within SGX enclaves still leaks user information. BITE therefore integrates several privacy preservation measures that address external leakage as well as SGX side-channels. We show that the resulting solution provides strong privacy protection and at the same time improves the performance of current lightweight clients. For more information, please see our paper. Show Less

The problem of Oblivious RAM (ORAM) has traditionally been studied in a single-server setting, but more recently the multi-server setting has also been considered. Yet it is still unclear whether the multi-server setting has any inherent advantages, e.g., whether the multi-server setting can be used to achieve stronger security goals or provably better efficiency than is possible in the single-server case. In this work, we construct a perfectly secure 3-server ORAM scheme that outperforms the best known single-server scheme by a logarithmic factor. In the process, we also show, for the first time, that there exist specific algorithms for which multiple servers can overcome known lower bounds in the single-server setting. For further information, please see our paper. Show Less

Today, we are relying on, and trusting, powerful companies (e.g., VISA, Facebook, Uber, Wells Fargo) with our data, our ability to financially transact, and engage in businesses with each other. We don’t have the option of not “trusting” them and “verifying” how they operate. The emergence of cryptocurrencies such as Bitcoin and Ethereum bring forth the promise of a new “decentralized” Internet, which is more transparent, fair, and secure. (1) Transparency - In a decentralized system, the rules of the game are public, anyone can verify the validity of transactions and computations (i.e., computer code), and users/stake-holders are not at the whim of a CEO of some company. (2) Fairness - There are no entry barriers (e.g., you don’t need a bank account to transact), censorship is impossible (e.g., money can’t be frozen), and anyone participating gets treated in the same way. (3) Security - Breaking the security of these protocols requires controlling a large fraction of the participating nodes. This is in contrast to currently standard “trusted-third party” solutions where a single company by either volition, or if hacked, can completely compromise the security of the entire system. These properties create exciting new opportunities for decentralized applications and mechanisms to incentivize entities and individuals to collaborate and transact together. The innovation that enables this development is the notion of a blockchain—that is, a method for maintaining an append-only, linearly-ordered, list of data (e.g., transactions). This notion, together with that of a smart contract—and in particular expressive (i.e., fully programmable) smart contracts as in Ethereum’s systems—are central to the potential of realizing the above-mentioned promise --- We want decentralization not only for payment systems, but rather to enable the above features for general applications. Indeed, in the last years, there has been an abundance of, so-called, DApps (i.e., Decentralized Apps) created that operate on Ethereum’s virtual machine (EVM). These include decentralized exchanges and games (such as CryptoKitties). Link to our work. Show Less

By design, existing (pre-processing) zk-SNARKs embed a secret trapdoor in a relation-dependent common reference strings (CRS). The trapdoor is exploited by a (hypothetical) simulator to prove the scheme is zero knowledge, and the secret-dependent structure facilitates a linear-size CRS and linear-time prover computation. If known by a real party, however, the trapdoor can be used to subvert the security of the system. The structured CRS that makes zk-SNARKs practical also makes deploying zk-SNARKS problematic, as it is difficult to argue why the trapdoor would not be available to the entity responsible for generating the CRS. Moreover, for pre-processing zk-SNARKs a new trusted CRS needs to be computed every time the relation is changed. In this paper, we address both issues by proposing a model where a number of users can update a universal CRS. The updatable CRS model guarantees security if at least one of the users updating the CRS is honest. We provide both a negative result, by showing that zk-SNARKs with private secret-dependent polynomials in the CRS cannot be updatable, and a positive result by constructing a zk-SNARK based on a CRS consisting only of secret-dependent monomials. The CRS is of quadratic size, is updatable, and is universal in the sense that it can be specialized into one or more relation-dependent CRS of linear size with linear-time prover computation. For more information, please see our paper. Show Less

Interacting with Ethereum smart contracts can have potentially devastating financial consequences. In light of this, several regulatory bodies have called for a need to audit smart contracts for security and correctness guarantees. Unfortunately, auditing smart contracts that do not have readily available source code can be challenging, and there are currently few tools available that aid in this process. Such contracts remain opaque to auditors. To address this, we present Erays, a reverse engineering tool for smart contracts. Erays takes in smart contract from the Ethereum blockchain, and produces high-level pseudocode suitable for manual analysis. We show how Erays can be used to provide insight into several contract properties, such as code complexity and code reuse in the ecosystem. We then leverage Erays to link contracts with no previously available source code to public source code, thus reducing the overall opacity in the ecosystem. Finally, we demonstrate how Erays can be used for reverse-engineering in four case studies --- high-value multi-signature wallets, arbitrage bots, exchange accounts, and finally, a popular smart-contract game, Cryptokitties. We conclude with a discussion regarding the value of reverse engineering in the smart contract ecosystem, and how Erays can be leveraged to address the challenges that lie ahead. Link to our work. Show Less

An apparatus in one embodiment includes a first processing device configured to communicate over a network with one or more additional processing devices including at least a second processing device. The first processing device includes a first blockchain client and a first trusted execution environment, and is configured to establish a first payment channel with a second trusted execution environment of the second processing device. The first processing device is also configured to associate at least one deposit with the first payment channel through execution of a corresponding blockchain transaction via the first blockchain client. The first processing device is further configured to utilize the deposit associated with the first payment channel to carry out multiple off-blockchain transactions between the first processing device and at least the second processing device. The first payment channel in some embodiments is part of a chain of payment channels established between trusted execution environments of respective pairs of the processing devices. For more information, please see our paper. Show Less

Sharding, or partitioning the system’s state so that different subsets of participants handle it, is a proven approach to building distributed systems whose total capacity scales horizontally with the number of participants. Many distributed ledgers have adopted this approach to increase their performance, however, they focus on the permissionless setting that assumes the existence of a strong adversary. In this paper, we deploy channels for permissioned blockchains. Our first contribution is to adapt sharding on asset-management applications for the permissioned setting, while preserving liveness and safety even on transactions spanning across-channels. Our second contribution is to leverage channels as a confidentiality boundary, enabling different organizations and consortia to preserve their privacy within their channels and still be part of a bigger collaborative ecosystem. To make our system concrete we map it on top of Hyperledger Fabric. Link to our paper. Show Less

The blockchain emerged as a novel distributed consensus scheme that allows transactions, and any other data, to be securely stored and verified without the need of any centralized authority. For some time, the notion of blockchain was tightly coupled with a now well-known proof-of-work hash-based mechanism of Bitcoin. Today, there are more than a hundred alternate blockchains - some are simple variants of Bitcoin, whereas others significantly differ in their design as well as provide different functional and security guarantees. This shows that the research community is in search of a simple, scalable, and deployable blockchain technology. Various reports further point to an increased interest in the use of blockchains across many applications and to a significant investment in the development of blockchains by different industries. It is expected that the blockchain will induce considerable change to a large number of systems and businesses. Distributed trust and therefore security and privacy are at the core of the blockchain technologies, and have the potential to either make them a success or cause them to fail. This special issue aims at collecting the most relevant ongoing research efforts in blockchain security and privacy. We are very grateful to this community, especially for its vivacity and vast participation. For further information, please see our paper. Show Less

In January 2009, Bitcoin was released into the world by its pseudonymous founder, Satoshi Nakamoto. In the ensuing years, this cryptocurrency and its underlying technology, called the blockchain, have gone on a rollercoaster ride that few could have predicted at the time of its deployment. It has been praised by governments around the world, and people have predicted that “the blockchain” will one day be like “the Internet”. It has been banned by governments around the world, and people have declared it “adrift” and “dead”. The price of Bitcoin skyrocketed in late 2013 up to $1,200 per bitcoin, only to spend the entire next year languishing at anywhere from $200 to $500 per bitcoin, before beginning a steady climb in 2016 that now has Bitcoin’s price hovering around $4,500 per bitcoin (a number that will no doubt be wildly out of date at the time of publication). After years in which discussions focused entirely on Bitcoin, people began to realize the more abstract potential of the blockchain, and “next-generation” platforms such as Ethereum, Steem, and Zcash were launched. More established companies also realized the value in the more abstract properties of the blockchain—resilience, integrity, and so forth—and repurposed it for their particular industries to create an even wider class of technologies called distributed ledgers and to form industrial consortia such as R3 and Hyperledger. These more general distributed ledgers can look, to varying degrees, quite unlike blockchains and have a somewhat clearer (or at least different) path to adoption given their association with established partners in industry. As we describe below, however, they must nevertheless overcome many of the same obstacles to become truly productive and long-lasting solutions. For more information, please see our paper. Show Less

While the intersection of blockchains and the Internet of Things (IoT) have received considerable research interest lately, Nakamoto-style blockchains possess a number of qualities that make them poorly suited for many IoT scenarios. Specifically, they require high network connectivity and are power-intensive. This is a drawback in IoT environments where battery-constrained nodes form an unreliable ad hoc network such as in digital agriculture. In this paper we present Vegvisir, a partition-tolerant blockchain for use in power-constrained IoT environments with limited network connectivity. It is a permissioned, directed acyclic graph (DAG)-structured blockchain that can be used to create a shared, tamperproof data repository that keeps track of data provenance. We discuss the use cases, architecture, and challenges of such a blockchain. For more information, please see our paper. Show Less

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. Show Less

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. Show Less

Blockchains offer a useful abstraction - a trustworthy, decentralized log of totally ordered transactions. Traditional blockchains have problems with scalability and efficiency, preventing their use for many applications. These limitations arise from the requirement that all participants agree on the total ordering of transactions. To address this fundamental shortcoming, we introduce Charlotte, a system for maintaining decentralized, authenticated data structures, including transaction logs. Each data structurestructure -- indeed, each block -- specifies its own availability and integrity properties, allowing Charlotte applications to retain the full benefits of permissioned or permissionless blockchains. In Charlotte, a block can be atomically appended to multiple logs, allowing applications to be interoperable when they want to, without inefficiently forcing all applications to share one big log. We call this open graph of interconnected blocks a blockweb. We allow new kinds of blockweb applications that operate beyond traditional chains. We demonstrate the viability of Charlotte applications with proof-of-concept servers running interoperable blockchains. Using performance data from our prototype, we estimate that when compared with traditional blockchains, Charlotte offers multiple orders of magnitude improvement in speed and energy efficiency. Link to our work. Show Less

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. Show Less

Open consensus protocols based on proof-of-work (PoW) mining are at the core of cryptocurrencies such Bitcoin and Ethereum, as well as many others. In this work, we construct a new primitive called Non-Interactive-Proofs-of-Proof-of-Work (NIPoPoWs) that can be adapted into existing PoW-based cryptocurrencies to improve their performance and extend their functionality. Unlike a traditional blockchain client which must verify the entire linearly-growing chain of PoWs, clients based on NIPoPoWs require resources only logarithmic in the length of the blockchain. NIPoPoWs are thus succinct proofs and require only a single message between the prover and the verifier of the transaction. With our construction we are able to prove a broad array of useful predicates in the context of cross PoW-based blockchain transfers of assets, including predicates about facts buried deep within a blockchain which is necessary for the basic application of accepting payments. We provide empirical validation for NIPoPoWs through an implementation and benchmark study, in the context of two new applications - (1) we consider a multi-client blockchain that supports all proof-of-work currencies rather than just one, with up to 90% reduction in bandwidth, (2) we discuss a “cross-chain ICO” application that spans multiple independent blockchains. Using our experimental data, we provide concrete parameters for our scheme. For more information, please see our paper. Show Less

Recent work has demonstrated significant anonymity vulnerabilities in Bitcoin's networking stack. In particular, the current mechanism for broadcasting Bitcoin transactions allows third-party observers to link transactions to the IP addresses that originated them. This lays the groundwork for low-cost, large-scale deanonymization attacks. In this work, we present Dandelion++, a first-principles defense against large-scale deanonymization attacks with near-optimal information-theoretic guarantees. Dandelion++ builds upon a recent proposal called Dandelion that exhibited similar goals. However, in this paper, we highlight simplifying assumptions made in Dandelion, and show how they can lead to serious deanonymization attacks when violated. In contrast, Dandelion++ defends against stronger adversaries that are allowed to disobey protocol. Dandelion++ is lightweight, scalable, and completely interoperable with the existing Bitcoin network. We evaluate it through experiments on Bitcoin's mainnet (i.e., the live Bitcoin network) to demonstrate its interoperability and low broadcast latency overhead. For further information, please see our paper. Show Less

Unspent Transaction Outputs (UTXOs) are the internal mechanism used in many cryptocurrencies to represent coins. Such representation has some clear benefits, but also entails some complexities that, if not properly handled, may leave the system in an inefficient state. Specifically, inefficiencies arise when wallets (the software responsible for transferring coins between parties) do not manage UTXOs properly when performing payments. In this paper, we study three cryptocurrencies - Bitcoin, Bitcoin Cash and Litecoin, by analyzing the actual state of their UTXO sets, that is, the status of their sets of spendable coins. These three cryptocurrencies are the top-3 UTXO based cryptocurrencies by market capitalization. Our analysis shows that the usage of each cryptocurrency is quite different, and let to different results. Furthermore, it also points out that the management of the transactions has not been always performed efficiently and then the actual state of the UTXO set for each cryptocurrency is far from ideal. Link to our work. Show Less

We present Airtnt, a novel scheme that enables users with CPUs that support Trusted Execution Environments (TEEs) and remote attestation to rent out computing time on secure enclaves to untrusted users. Airtnt makes use of the attestation capabilities of TEEs and smart contracts on distributed ledgers to guarantee the fair exchange of the payment and the result of an execution. Airtnt makes use of off-chain payment channels to allow requesters to pay executing nodes for intermediate “snapshots" of the state of an execution. Effectively, this step-by-step “compute-payment" cycle realises untrusted pay-as-you-go micropayments for computation. Neither the requester nor the executing node can walk away and incur monetary loss to the other party. This also allows requesters to continue executions on other executing nodes if the original executing node becomes unavailable or goes offline. For further information, please see our paper. Show Less

Blockchain-based consensus protocols present the opportunity to develop new protocols, due to their novel requirements of open participation and explicit incentivization of participants. To address the first requirement, it is necessary to consider the leader election inherent in consensus protocols, which can be difficult to scale to a large and untrusted set of participants. To address the second, it is important to consider ways to provide incentivization without relying on the resource-intensive proofs-of-work used in Bitcoin. In this paper, we propose a secure leader election protocol, Caucus - we next fit this protocol into a broader blockchain-based consensus protocol, Fantômette, that provides game-theoretic guarantees in addition to traditional blockchain security properties. Fantômette is the first proof-of-stake protocol to give formal game-theoretic proofs of security in the presence of non-rational players. For more information, please see our paper. Show Less

The sharing of personal data has the potential to bring sub-stantial benefits both to individuals and society, but only if people have confidence that their data will not be used in-appropriately. As more sensitive data is considered for sharing (e.g., communication records and medical records) and used to make important decisions, there is a growing need for transparency in the way that the data is processed, while protecting the privacy of individuals and the integrity of their data. We propose a system, VAMS, which allows individuals to check accesses to their personal data, and enables auditors to detect violations of policy. Furthermore, our system protects the privacy of individuals and organizations, while allowing published statistics to be publicly verified. We demonstrate the practicality of our system with two prototypes, based on Hyperledger Fabric and Trillian. For further information, please see our paper. Show Less

Distributed systems achieve scalability by distributing load across many machines, but wide-area deployments can introduce worst-case response latencies proportional to the network’s diameter. Crux is a general framework to build locality-preserving distributed systems, by transforming an existing scalable distributed algorithm A into a new locality-preserving algorithm ALP, which guarantees for any two clients u and v interacting via ALP that their interactions exhibit worst-case response latencies proportional to the network latency between u and v. Crux builds on compact-routing theory, but generalizes these techniques beyond routing applications. Crux provides weak and strong consistency flavors, and shows latency improvements for localized interactions in both cases, specifically up to several orders of magnitude for weakly-consistent Crux (from roughly 900ms to 1ms). We deployed on PlanetLab locality-preserving versions of a Memcached distributed cache, a Bamboo distributed hash table, and a Redis publish/subscribe. Our results indicate that Crux is effective and applicable to a variety of existing distributed algorithms. Link to our paper. Show Less

Decentralized cryptocurrencies based on blockchains provide attractive features, including user privacy and system transparency, but lack active control of money supply and capabilities for regulatory oversight, both existing features of modern monetary systems. These limitations are critical, especially if the cryptocurrency is to replace, or complement, existing fiat currencies. Centralized cryptocurrencies, on the other hand, provide controlled supply of money, but lack transparency and transferability. Finally, they provide only limited privacy guarantees, as they do not offer recipient anonymity or payment value secrecy. We propose a novel digital currency, called PRCash, where the control of money supply is centralized, money is represented as value-hiding transactions for transferability and improved privacy, and transactions are verified in a distributed manner and published to a public ledger for verifiability and transparency. Strong privacy and regulation are seemingly conflicting features, but we overcome this technical problem with a new regulation mechanism based on zero-knowledge proofs. Our implementation and evaluation shows that payments are fast and large-scale deployments practical. PRCash is the first digital currency to provide control of money supply, transparency, regulation, and privacy at the same time, and thus make its adoption as a fiat currency feasible. We propose a novel digital currency, called PRCash, where the control of money supply is centralized, money is represented as value-hiding transactions for transferability and improved privacy, and transactions are verified in a distributed manner and published to a public ledger for verifiability and transparency. Strong privacy and regulation are seemingly conflicting features, but we overcome this technical problem with a new regulation mechanism based on zero-knowledge proofs. Our implementation and evaluation shows that payments are fast and large-scale deployments practical. PRCash is the first digital currency to provide control of money supply, transparency, regulation, and privacy at the same time, and thus make its adoption as a fiat currency feasible. For more information, please see our paper. Show Less

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 Show Less

Among the now numerous alternative cryptocurrencies derived from Bitcoin, Zcash is often touted as the one with the strongest anonymity guarantees, due to its basis in well-regarded cryptographic research. In this paper, we examine the extent to which anonymity is achieved in the deployed version of Zcash. We investigate all facets of anonymity in Zcash’s transactions, ranging from its transparent transactions to the interactions with and within its main privacy feature, a shielded pool that acts as the anonymity set for users wishing to spend coins privately. We conclude that while it is possible to use Zcash in a private way, it is also possible to shrink its anonymity set considerably by developing simple heuristics based on identifiable patterns of usage. Link to our work. Show Less

Decentralized cryptocurrencies based on blockchains provide attractive features, including user privacy and system transparency, but lack active control of money supply and capabilities for regulatory oversight, both existing features of modern monetary systems. These limitations are critical, especially if the cryptocurrency is to replace, or complement, existing fiat currencies. Centralized cryptocurrencies, on the other hand, provide controlled supply of money, but lack transparency and transferability. Finally, they provide only limited privacy guarantees, as they do not offer recipient anonymity or payment value secrecy. We propose a novel digital currency, called PRCash, where the control of money supply is centralized, money is represented as value-hiding transactions for transferability and improved privacy, and transactions are verified in a distributed manner and published to a public ledger for verifiability and transparency. Strong privacy and regulation are seemingly conflicting features, but we overcome this technical problem with a new regulation mechanism based on zero-knowledge proofs. Our implementation and evaluation shows that payments are fast and large-scale deployments practical. PRCash is the first digital currency to provide control of money supply, transparency, regulation, and privacy at the same time, and thus make its adoption as a fiat currency feasible. For more information, please see our paper. Show Less

Many cloud and cryptocurrency applications rely on verifying the integrity of outsourced computations, in which a verifier can efficiently verify the correctness of a computation made by an untrusted prover. State-of-the-art protocols for verifiable computation require that the computation task be expressed as arithmetic circuits, and the number of multiplication gates in the circuit is the primary metric that determines performance. At the present, a programmer could rely on two approaches for expressing the computation task, either by composing the circuits directly through low-level development tools; or by expressing the computation in a high-level program and rely on compilers to perform the program-to-circuit transformation. The former approach is difficult to use but on the other hand allows an expert programmer to perform custom optimizations that minimize the resulting circuit. In comparison, the latter approach is much more friendly to non-specialist users, but existing compilers often emit suboptimal circuits. We present xJsnark, a programming framework for verifiable computation that aims to achieve the best of both worlds - offering programmability to non-specialist users, and meanwhile automating the task of circuit size minimization through a combination of techniques. Specifically, we present new circuit-friendly algorithms for frequent operations that achieve constant to asymptotic savings over existing ones; various globally aware optimizations for short - and long - integer arithmetic, as well as circuit minimization techniques that allow us to reduce redundant computation over multiple expressions. We illustrate the savings in different applications, and show the framework’s applicability in developing large application circuits, such as ZeroCash, while minimizing the circuit size as in low-level implementations. For more information, please see our paper. Show Less

Monero is a privacy-centric cryptocurrency that allows users to obscure their transactions by including chaff coins, called “mixins”, along with the actual coins they spend. In this paper, we empirically evaluate two weaknesses in Monero’s mixin sampling strategy. First, about 62% of transaction inputs with one or more mixins are vulnerable to “chain-reaction” analysis — that is, the real input can be deduced by elimination. Second, Monero mixins are sampled in such a way that they can be easily distinguished from the real coins by their age distribution - in short, the real input is usually the “newest” input. We estimate that this heuristic can be used to guess the real input with 80% accuracy over all transactions with 1 or more mixins. Next, we turn to the Monero ecosystem and study the importance of mining pools and the former anonymous marketplace AlphaBay on the transaction volume. We find that after removing mining pool activity, there remains a large amount of potentially privacy-sensitive transactions that are affected by these weaknesses. We propose and evaluate two countermeasures that can improve the privacy of future transactions. For more information, please see our paper. Show Less

Proof-of-Stake systems randomly choose, on each round, one of the participants as a consensus leader that extends the chain with the next block such that the selection probability is proportional to the owned stake. However, distributed random number generation is notoriously difficult. Systems that derive randomness from the previous blocks are completely insecure, solutions that provide secure random selection are inefficient due to their high communication complexity, and approaches that balance security and performance exhibit selection bias. When block creation is rewarded with new stake, even a minor bias can have a severe cumulative effect. In this paper, we propose Robust Round Robin, a new consensus scheme that addresses this selection problem. We create reliable long-term identities by bootstrapping from an existing infrastructure, such as Intel's SGX processors, or by mining them starting from an initial fair distribution. For leader selection we use a deterministic approach. On each round, we select a set of the previously created identities as consensus leader candidates in round robin manner. Because simple round-robin alone is vulnerable to attacks and offers poor liveness, we complement such deterministic selection policy with a lightweight endorsement mechanism that is an interactive protocol between the leader candidates and a small subset of other system participants. Our solution has low good efficiency as it requires no expensive distributed randomness generation and it provides block creation fairness which is crucial in deployments that reward it with new stake. For more information, please see our paper. Show Less

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. Show Less

This note provides a broad overview of how technological changes are likely to affect the practice of central banking. While the advent of decentralized cryptocurrencies such as Bitcoin has dominated the headlines, a broader set of changes wrought by advances in technology are likely to eventually have a more profound and lasting impact on central banks. While it is premature to speak of disruption of traditional concepts of central banking, it is worth considering if the looming changes to money, financial markets, and payments systems will have significant repercussions for the operation of central banks and their ability to deliver on key objectives such as low inflation and financial stability. New forms of money and new channels for moving funds within and between economies could also have implications for international capital flows and exchange rates, which are of particular relevance for emerging market central banks. The note touches on the relevant considerations (for monetary policy and financial stability) and catalogs the approaches that major central banks are taking towards three inter-related issues - central bank digital currencies (CBDCs), nonofficial cryptocurrencies, and fintech, a term that encompasses new and evolving financial technologies. The objective of this note is not to offer policy prescriptions but to survey the issues that central banks will have to grapple with and describe how some of them are preparing for the looming changes. The potential implications for the international monetary system will also be addressed briefly. Link to my work. Show Less

Blockchain-based cryptocurrencies have demonstrated how to securely implement traditionally centralized systems, such as currencies, in a decentralized fashion. However, there have been few measurement studies on the level of decentralization they achieve in practice. We present a measurement study on various decentralization metrics of two of the leading cryptocurrencies with the largest market capitalization and user base, Bitcoin and Ethereum. We investigate the extent of decentralization by measuring the network resources of nodes and the interconnection among them, the protocol requirements affecting the operation of nodes, and the robustness of the two systems against attacks. In particular, we adapted existing internet measurement techniques and used the Falcon Relay Network as a novel measurement tool to obtain our data. We discovered that neither Bitcoin nor Ethereum has strictly better properties than the other. We also provide concrete suggestions for improving both systems. For further information, please see our paper. Show Less

Attribute based encryption (ABE) is an advanced encryption system with a built-in mechanism to generate keys associated with functions which in turn provide restricted access to encrypted data. Most of the known candidates of attribute based encryption model the functions as circuits. This results in significant efficiency bottlenecks, especially in the setting where the function associated with the ABE key is represented by a random access machine (RAM) and a database, with the runtime of the RAM program being sublinear in the database size. In this work we study the notion of attribute based encryption for random access machines (RAMs), introduced in the work of Goldwasser, Kalai, Popa, Vaikuntanathan and Zeldovich (Crypto 2013). We present a construction of attribute based encryption for RAMs satisfying sublinear decryption complexity assuming learning with errors; this is the first construction based on standard assumptions. Previously, Goldwasser et al. achieved this result based on non-falsifiable knowledge assumptions. We also consider a dual notion of ABE for RAMs, where the database is in the ciphertext and we show how to achieve this dual notion, albeit with large attribute keys, also based on learning with errors. Link to our work. Show Less

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. HotStuff is built around a novel framework that forms a bridge between classical BFT foundations and blockchains. It allows the expression of other known protocols (DLS, PBFT, Tendermint, Casper), and ours, in a common framework. Our deployment of HotStuff over a network with over 100 replicas achieves throughput and latency comparable to that of BFT-SMaRt, while enjoying linear communication footprint during leader failover (vs. quadratic with BFT-SMaRt). For more information, please see our paper. Show Less

In this paper we initiate a quantitative study of the decentralization of the governance structures of Bitcoin and Ethereum. In particular, we scraped the open-source repositories associated with their respective codebases and improvement proposals to find the number of people contributing to the code itself and to the overall discussion. We then present different metrics to quantify decentralization, both in each of the cryptocurrencies and, for comparison, in two popular open-source programming languages - Clojure and Rust. We find that for both cryptocurrencies and programming languages, there is usually a handful of people that accounts for most of the discussion. We also look into the effect of forks in Bitcoin and Ethereum, and find that there is little intersection between the communities of the original currencies and those of the forks. Link to our work. Show Less

We present three smart contracts that allow a briber to fairly exchange bribes to miners who pursue a mining strategy benefiting the briber. The first contract, CensorshipCon, highlights that Ethereum’s uncle block reward policy can directly subsidise the cost of bribing miners. The second contract, HistoryRevisionCon, rewards miners via an in-band payment for reversing transactions or enforcing a new state of another contract. The third contract, GoldfingerCon, rewards miners in one cryptocurrency for reducing the utility of another cryptocurrency. This work is motivated by the need to understand the extent to which smart contracts can impact the incentive mechanisms involved in Nakamoto-style consensus protocols. For further information, please see our work. Show Less

It is well-known that non-comparison-based techniques can allow us to sort n elements in o(nlogn) time on a Random-Access Machine (RAM). On the other hand, it is a long-standing open question whether (non-comparison-based) circuits can sort n elements from the domain [1..2k] with o(knlogn) boolean gates. We consider weakened forms of this question - (1) we consider a restricted class of sorting where the number of distinct keys is much smaller than the input length, and (2) we explore Oblivious RAMs and probabilistic circuit families, i.e., computational models that are somewhat more powerful than circuits but much weaker than RAM. We show that Oblivious RAMs and probabilistic circuit families can sort o(logn)-bit keys in o(nlogn) time or o(knlogn) circuit complexity where n is the input length. Our algorithms work in the balls-and-bins model, i.e., not only can they sort an array of numerical keys - if each key additionally carries an opaque ball, our algorithms can also move the balls into the correct order. We further show that in such a balls-and-bins model, it is impossible to sort Ω(logn)-bit keys in o(nlogn) time, and thus the o(logn)-bit-key assumption is necessary for overcoming the nlogn barrier. Finally, we optimize the IO efficiency of our oblivious algorithms for RAMs - we show that even the 1-bit special case of our algorithm can solve open questions regarding whether there exist oblivious algorithms for tight compaction and selection in linear IO. For more information, please see our paper. Show Less

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. Show Less

Coconut is a novel selective disclosure credential scheme supporting distributed threshold issuance, public and private attributes, re-randomization, and multiple unlinkable selective attribute revelations. Coconut integrates with blockchains to ensure confidentiality, authenticity and availability even when a subset of credential issuing authorities are malicious or offline. We implement and evaluate a generic Coconut smart contract library for Chainspace and Ethereum; and present three applications related to anonymous payments, electronic petitions, and distribution of proxies for censorship resistance. Coconut uses short and computationally efficient credentials, and our evaluation shows that most Coconut cryptographic primitives take just a few milliseconds on average, with verification taking the longest time (10 milliseconds). Link to our work. Show Less

We introduce a new concept called brokered delegation. Brokered delegation allows users to flexibly delegate credentials and rights for a range of service providers to other users and third parties. We explore how brokered delegation can be implemented using novel trusted execution environments (TEEs). We introduce a system called DelegaTEE that enables users (Delegatees) to log into different online services using the credentials of other users (Owners). Credentials in DelegaTEE are never revealed to Delegatees and Owners can restrict access to their accounts using a range of rich, contextually dependent delegation policies. DelegaTEE fundamentally shifts existing access control models for centralized online services. It does so by using TEEs to permit access delegation at the user's discretion. DelegaTEE thus effectively reduces mandatory access control (MAC) in this context to discretionary access control (DAC). The system demonstrates the significant potential for TEEs to create new forms of resource sharing around online services without the direct support from those services. We present a full implementation of DelegaTEE using Intel SGX and demonstrate its use in four real-world applications --- email access (SMTP/IMAP), restricted website access using a HTTPS proxy, e-banking/credit card, and a third-party payment system (PayPal). For further information, please see our paper. Show Less

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. Show Less

The purpose of this project is to implement a decentralised witness cosigning protocol as described in the paper “Keeping Authorities “Honest or Bust” with Decentralised Witness Cosigning”. This project aims to have a complete, functional, failure resilient, documented and tested code base to allow witness cosigning using the CoSi protocol, explained in the next section. This project uses knowledge from previous tests to create a scalable network of witness using a three-level tree. At the time of the project start, a CoSi code already existed, but was not documented, nor practical. It was assembled only for testing purpose and therefore, we decided to throw it away to start anew. The main reasons for this projects were - 1) The need of a reusable, integrated with existing frameworks, code base. 2) The need to test extensively the CoSi protocol, its behaviour and resilience. The following subsections present the CoSi algorithm, the algorithm upon which the project is based as well as ONet and Kyber, the two main libraries used in this project. For more information, please see our paper. Show Less

The standard acceptance policy for a cryptocurrency transaction at most exchanges is to wait until the transaction is placed in the blockchain and followed by a certain number of blocks. However, as noted by Sompolinsky and Zohar, the amount of time for blocks to arrive should also be taken into account as it affects the probability of double spending. Specifically, they propose a dynamic policy for transaction acceptance that depends on both the number of confirmations and the amount of time since transaction broadcast. In this work we study the implications of using such a policy compared with the standard option that ignores block timing information. Using an exact expression for the probability of double spend, via numerical results, we analyze time to transaction acceptance (performance) as well as the time and cost to perform a double spend attack (security). We show that while expected time required for transaction acceptance is improved using a dynamic policy, the time and cost to perform a double spend attack for a particular transaction is reduced. For further information, please see our paper. Show Less

Many applications require the immutable and consistent sharing of data across organizational boundaries. Because conventional datastores cannot provide this functionality, blockchains have been proposed as one possible solution. Yet 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 meta-information, and also suffer from scale and performance bottlenecks. This paper presents CreDB, a datastore that provides blockchain-like guarantees of integrity using trusted execution environments. CreDB employs four novel mechanisms to support a new class of applications. First, it creates a permanent record of every transaction, known as a witness, that clients can then use not only to audit the database but to prove to third parties that desired actions took place. Second, it associates with every object an inseparable and inviolable policy, which not only performs access control but enables the datastore to implement state machines whose behavior is amenable to analysis. Third, timeline inspection allows authorized parties to inspect and reason about the history of changes made to the data. Finally, CreDB provides a protected function evaluation mechanism that allows integrity-protected computation over private data. The paper describes these mechanisms, and the applications they collectively enable, in detail. We have fully implemented a prototype of CreDB on Intel SGX. Evaluation shows that CreDB can serve as a drop-in replacement for other NoSQL stores, such as MongoDB while providing stronger integrity guarantees. For more information please see our paper. Show Less

Monero, a leading privacy-oriented cryptocurrency, supports a client/server operating mode that allows lightweight clients to avoid storing the entire blockchain, instead relying on a remote node to provide necessary information about the blockchain. However, a weakness of Monero’s current blockchain data structure is that lightweight clients cannot authenticate the responses returned from a remote node. In this paper, we show that malicious responses from a remote node can lead to reduced privacy for the client. We discuss several lightweight mitigations that reduce the attack’s effectiveness. To fully eliminate this class of attack, we also show how to augment Monero’s blockchain data structure with an additional index that clients can use to authenticate responses from remote nodes. Our proposed solution could be implemented as a hard fork, or alternatively through a “Refereed Delegation” approach without needing any fork. We developed a prototype implementation to demonstrate the feasibility of our proposal. For more information, please see our paper. Show Less

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. Show Less

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

The blockchain initially gained traction in 2008 as the technology underlying bitcoin, but now has been employed in a diverse range of applications and created a global market worth over $150B as of 2017. What distinguishes blockchains from traditional distributed databases is the ability to operate in a decentralized setting without relying on a trusted third party. As such their core technical component is consensus - how to reach agreement among a group of nodes. This has been extensively studied already in the distributed systems community for closed systems, but its application to open blockchains has revitalized the field and led to a plethora of new designs. The inherent complexity of consensus protocols and their rapid and dramatic evolution makes it hard to contextualize the design landscape. We address this challenge by conducting a systematic and comprehensive study of blockchain consensus protocols. After first discussing key themes in classical consensus protocols, we describe - first protocols based on proof-of-work (PoW), second proof-of-X (PoX) protocols that replace PoW with more energy-efficient alternatives, and third hybrid protocols that are compositions or variations of classical consensus protocols. We develop a framework to evaluate their performance, security and design properties, and use it to systematize key themes in the protocol categories described above. This evaluation leads us to identify research gaps and challenges for the community to consider in future research endeavours. For more information, please see our paper. Show Less

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. Show Less

It is well-known that a program's memory access pattern can leak information about its input. To thwart such leakage, most existing works adopt the solution of oblivious RAM (ORAM) simulation. Such a notion has stimulated much debate. Some have argued that the notion of ORAM is too strong, and suffers from a logarithmic lower bound on simulation overhead. Despite encouraging progress in designing efficient ORAM algorithms, it would nonetheless be desirable to avoid the oblivious simulation overhead. Others have argued that obliviousness, without protection of length-leakage, is too weak, and have demonstrated examples where entire databases can be reconstructed merely from length-leakage. nspired by the elegant notion of differential privacy, we initiate the study of a new notion of access pattern privacy, which we call "(ϵ,δ)-differential obliviousness''. We separate the notion of (ϵ,δ)-differential obliviousness from classical obliviousness by considering several fundamental algorithmic abstractions including sorting small-length keys, merging two sorted lists, and range query data structures (akin to binary search trees). We show that by adopting differential obliviousness with reasonable choices of ϵ and δ, not only can one circumvent several impossibilities pertaining to the classical obliviousness notion, but also in several cases, obtain meaningful privacy with little overhead relative to the non-private baselines (i.e., having privacy "almost for free''). On the other hand, we show that for very demanding choices of ϵ and δ, the same lower bounds for oblivious algorithms would be preserved for (ϵ,δ)-differential obliviousness. For more information, please see our paper. Show Less

The financial technology (FinTech) sector sees high potential value in cryptocurrency blockchain protocols, or distributed-ledger technology (DLT). However, the requirements and guarantees of blockchains for cryptocurrencies do not match those of FinTech— from transaction throughput to security primitives and privacy. The author explores how blockchain research beyond Bitcoin is closing these gaps and some of the challenges that remain. Link to my work. Show Less

State machine replication, or "consensus'', is a central abstraction for distributed systems where a set of nodes seek to agree on an ever-growing, linearly-ordered log. In this paper, we propose a practical new paradigm called Thunderella for achieving state machine replication by combining a fast, asynchronous path with a (slow) synchronous "fall-back'' path (which only gets executed if something goes wrong). As a consequence, we get simple state machine replications that essentially are as robust as the best synchronous protocols, yet "optimistically'' (if a super majority of the players are honest), the protocol "instantly'' confirms transactions. We provide instantiations of this paradigm in both permissionless (using proof-of-work) and permissioned settings. Most notably, this yields a new blockchain protocol (for the permissionless setting) that remains resilient assuming only that a majority of the computing power is controlled by honest players, yet optimistically — if 3/4 of the computing power is controlled by honest players, and a special player called the "accelerator'', is honest—transactions are confirmed as fast as the actual message delay in the network. We additionally show the 3/4 optimistic bound is tight for protocols that are resilient assuming only an honest majority. For more information, please see our paper. Show Less

Cryptocurrencies allow users to securely transfer money without relying on a trusted intermediary, and the transparency of their underlying ledgers also enables public verifiability. This openness, however, comes at a cost to privacy, as even though the pseudonyms users go by are not linked to their real-world identities, all movement of money among these pseudonyms is traceable. In this paper, we present Mobius, an Ethereum-based tumbler or mixing service. Mobius achieves strong notions of anonymity, as even malicious senders cannot identify which pseudonyms belong to the recipients to whom they sent money, and is able to resist denial-of-service attacks. It also achieves a much lower off-chain communication complexity than all existing tumblers, with senders and recipients needing to send only two initial messages in order to engage in an arbitrary number of transactions. For further information, please see our paper. Show Less

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. Show Less

Oblivious RAMs, introduced by Goldreich and Ostrovsky (JACM 1996), compile any RAM program into one that is "memory oblivious'', i.e., the access pattern to the memory is independent of the input. All previous ORAM schemes, however, completely break the locality of data accesses (for instance, by shuffling the data to pseudorandom positions in memory). In this work, we initiate the study of locality-preserving ORAMs --- ORAMs that preserve locality of the accessed memory rehions, while leaking only the lengths of contiguous memory regions accessed. Our main results demonstrate the existence of a locality-preserving ORAM with poly-logarithmic overhead both in terms of bandwidth and locality. We also study the tradeoff between locality, bandwidth and leakage, and show that any scheme that preserves locality and does not leak the lengths of the contiguous memory regions accessed, suffers from prohibitive bandwitdh. To the best of our knowledge, before our work, the only works combining locality and obliviousness were for symmetric searchable encryption (e.g., Cash and Tessaro - EUROCRYPT 2014, Asharov et al. - STOC 2016). Symmetric search encryption ensures obliviousness if each keyword is searched only once, whereas ORAM provides obliviousness to any input program. Thus, our work generalizes that line of work to the much more challenging task of preserving locality in ORAMs. For further information, please see our paper. Show Less

An internet user wanting to share observed content is typically restricted to primitive techniques such as screenshots, web caches or share button-like solutions. These acclaimed proofs, however, are either trivial to falsify or require trust in centralized entities (e.g., search engine caches). This motivates the need for a seamless and standardized internet-wide non-repudiation mechanism, allowing users to share data from news sources, social websites or financial data feeds in a provably secure manner. Additionally, blockchain oracles that enable data-rich smart contracts typically rely on a trusted third party (e.g., TLSNotary or Intel SGX). A decentralized method to transfer web-based content into a permissionless blockchain without additional trusted third party would allow for smart contract applications to flourish. In this work, we present TLS-N, the first TLS extension that provides source non-repudiation and solves both of the mentioned challenges. TLS-N generates non-interactive proofs about the content of a TLS session that can be efficiently verified by third parties and blockchain based smart contracts. As such, TLS-N increases the accountability for content provided on the web and enables a practical and decentralized blockchain oracle for web content. TLS-N is compatible with TLS 1.3 and adds a minor overhead to a typical TLS session. When a proof is generated, parts of the TLS session (e.g., passwords, cookies) can be hidden for privacy reasons, while the remaining content can be verified. Practical demonstrations can be found here. For more information, please see our paper. Show Less

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. Show Less

Blockchain is being praised as a technological innovation which allows to revolutionize how society trades and interacts. This reputation is in particular attributable to its properties of allowing mutually mistrusting entities to exchange financial value and interact without relying on a trusted third party. A blockchain moreover provides an integrity protected data storage and allows to provide process transparency. In this article we critically analyze whether a blockchain is indeed the appropriate technical solution for a particular application scenario. We differentiate between permissionless (e.g., Bitcoin/Ethereum) and permissioned (e.g., Hyperledger/Corda) blockchains and contrast their properties to those of a centrally managed database. We provide a structured methodology to determine the appropriate technical solution to solve a particular application problem. Given our methodology, we analyze in depth three use cases --- Supply Chain Management, Interbank and International Payments, and Decentralized Autonomous Organizations and conclude the article with an outlook for further opportunities. For more information, please see our paper. Show Less

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. Show Less

Mining for Bitcoins is a high-risk high-reward activity. Miners, seeking to reduce their variance and earn steadier rewards, collaborate in so-called pooling strategies where they jointly mine for Bitcoins. Whenever some pool participant is successful, the earned rewards are appropriately split among all pool participants. Currently a dozen of different pooling strategies (i.e., methods for distributing the rewards) are in use for Bitcoin mining. We here propose a formal model of utility and social welfare for Bitcoin mining (and analogous mining systems) based on the theory of discounted expected utility, and next study pooling strategies that maximize the social welfare of miners. Our main result shows that one of the pooling strategies actually employed in practice - the so-called geometric pay pool - achieves the optimal steady-state utility for miners when its parameters are set appropriately. Our results apply not only to Bitcoin mining pools, but any other form of pooled mining or crowdsourcing computations where the participants engage in repeated random trials towards a common goal, and where "partial'' solutions can be efficiently verified. For more information, please see our paper. Show Less

Blockchains show promise as potential infrastructure for financial transaction systems. The security of blockchains today, however, relies critically on Proof-of-Work (PoW), which forces participants to waste computational resources. We present REM (Resource-Efficient Mining), a new blockchain mining framework that uses trusted hardware (Intel SGX). REM achieves security guarantees similar to PoW, but leverages the partially decentralized trust model inherent in SGX to achieve a fraction of the waste of PoW. Its key idea, Proof-of-Useful-Work (PoUW), involves miners providing trustworthy reporting on CPU cycles they devote to inherently useful workloads. REM flexibly allows any entity to create a useful workload. REM ensures the trustworthiness of these workloads by means of a novel scheme of hierarchical attestations that may be of independent interest. To address the risk of compromised SGX CPUs, we develop a statistics-based formal security framework, also relevant to other trusted-hardware-based approaches such as the Intel Proof-of-Elapsed-Time (PoET). We show through economic analysis that REM achieves less waste than PoET and variant schemes. We implement REM and, as an example application, swap it into the consensus layer of Bitcoin core. The result is the first full implementation of an SGX-based blockchain. We experiment with four example applications as useful workloads for our implementation of REM, and report a computational overhead of 5-15%. Link to our work. Show Less

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. Show Less

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. Show Less

Security architectures such as Intel SGX need protection against rollback attacks, where the adversary violates the integrity of a protected application state by replaying old persistently stored data or by starting multiple application instances. Successful rollback attacks have serious consequences on applications such as financial services. In this paper, we propose a new approach for rollback protection on SGX. The intuition behind our approach is simple. A single platform cannot efficiently prevent rollback, but in many practical scenarios, multiple processors can be enrolled to assist each other. We design and implement a rollback protection system called ROTE that realizes integrity protection as a distributed system. We construct a model that captures adversarial ability to schedule enclave execution and show that our solution achieves a strong security property - the only way to violate integrity is to reset all participating platforms to their initial state. We implement ROTE and demonstrate that distributed rollback protection can provide significantly better performance than previously known solutions based on local non-volatile memory. For more information, please see our paper. Show Less

Oblivious RAM (ORAM) is a cryptographic primitive that allows a trusted CPU to securely access untrusted memory, such that the access patterns reveal nothing about sensitive data. ORAM is known to have broad applications in secure processor design and secure multi-party computation for big data. Unfortunately, due to a logarithmic lower bound by Goldreich and Ostrovsky (Journal of the ACM, 1996), ORAM is bound to incur a moderate cost in practice. In particular, with the latest developments in ORAM constructions, we are quickly approaching this limit, and the room for performance improvement is small. In this paper, we consider new models of computation in which the cost of obliviousness can be fundamentally reduced in comparison with the standard ORAM model. We propose the Oblivious Network RAM model of computation, where a CPU communicates with multiple memory banks, such that the adversary observes only which bank the CPU is communicating with, but not the address offset within each memory bank. In other words, obliviousness within each bank comes for free - either because the architecture prevents a malicious party from observing the address accessed within a bank, or because another solution is used to obfuscate memory accesses within each bank - and hence we only need to obfuscate communication patterns between the CPU and the memory banks. We present new constructions for obliviously simulating general or parallel programs in the Network RAM model. We describe applications of our new model in secure processor design and in distributed storage applications with a network adversary. For further information, please see our paper. Show Less

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. Show Less

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. Show Less

We present the a probably secure proof-of-stake protocol called Snow White. The primary application of Snow White is to be used as a "green'' consensus alternative for a decentralized cryptocurrency system with open enrollment. We break down the task of designing Snow White into the following core challenges - (1) identify a core "permissioned'' consensus protocol suitable for proof-of-stake, specifically the core consensus protocol should offer robustness in an Internet-scale, heterogeneous deployment, (2) propose a robust committee re-election mechanism such that as stake switches hands in the cryptocurrency system, the consensus committee can evolve in a timely manner and always reflect the most recent stake distribution, and (3) relying on the formal security of the underlying consensus protocol, prove the full end-to-end protocol to be secure - more specifically, we show that that any consensus protocol satisfying the desired robustness properties can be used to construct proofs-of-stake consensus, as long as money does not switch hands too quickly. Snow White was publicly released in September 2016. It provides the first formal, end-to-end proof of a proof-of-stake system in a truly decentralized, open-participation network, where nodes can join at any time (not necessarily at the creation of the system). We also give the first formal treatment of a well-known issue called "costless simulation'' in our paper, proving both upper- and lower-bounds that characterize exactly what setup assumptions are needed to defend against costless simulation attacks. We refer the reader to our detailed chronological notes on a detailed comparison of Snow White and other prior and concurrent works, as well as how subsequent works (including the Ethereum proof-of-stake design) have since extended and improved our ideas. For more information, please see our paper. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less

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. Show Less