Published Papers

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015 and Older

Preprints

Publicly Auditable MPC-as-a-Service with succinct verification and universal setup
S. Kanjalkar, Y. Zhang, S. Gandlur, and A. Miller.

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 correctly -- 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.

GoAT: File Geolocation via Anchor Timestamping
D. Maram, I. Bentov, M. Kelkar, and A. Juels.

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 extentions 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.

Tuning PoW with Hybrid Expenditure
I. Tsabary, A. Spiegelman, and I. Eyal.

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 Colombia 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 Nakamoto's 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 compare to Nakamoto's 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.

Foundations of Distributed Consensus and Blockchains
E. Shi.

Back in the 1970s, it became clear that computers were going to be used in aircraft control. Since this was a mission-critical system, it was important to replicate it on multiple machines. But how do we make sure that the multiple machines share a consistent view and make consistent decision? To understand this problem better, NASA sponsored the Software Implemented Fault Tolerance (SIFT) project [WLG+89], whose goal was to build a resilient aircraft control system that tolerated faults of its components. The famous work of Lambort et al. [LSP82] which introduced the well-known Byzantine Generals problem, came out of this project. This work laid the foundation of distributed consensus. Since then, distributed consensus has come a long way and has been deployed in many application settings. In the past couple of decades, companies like Google and Facebook have adopted distributed consensus as part of their computing infrastructure, e.g., to replicate mission-critical services such as Google Wallet and Facebook Credit. Starting in 2009, Bitcoin and various subsequent cryptocurrencies came around and became popular. The cryptocurrencies achieved a new breakthrough in distributed consensus, since they showed, for the first time, that consensus is viable in a decentralized, permissionless environment where anyone is allowed to participate. In this course, you will learn the mathematical foundations of distributed consensus as well as how to construct consensus protocols and prove them secure. We will motivate distributed consensus with a modern narrative, and yet we will cover the classical theoretical foundations of consensus. We will cover both classical, permissioned consensus protocols, as well as modern, permissionless consensus protocols such as Bitcoin.