Home

I'm a Research Scientist at Visa Research in Palo Alto, California, USA, where I'm working on research problems related to building secure, scalable, and privacy-preserving blockchain protocols ranging from distributed consensus to secure computations over blockchains. I'm equally interested in theoretical and applied approaches for solving these problems.

Before Visa Research, I was a postdoctoral associate in Computer Science at Yale University supervised by Joan Feigenbaum.

Interests

Security and Privacy of Distributed Algorithms [more]

I am interested in:
  1. Designing distributed algorithms that can scale to large networks;
  2. Making them provably robust against adversarial or non-adversarial faults;
  3. Guaranteeing their users' privacy;
  4. Rigorously analyzing their performance to find bottlenecks that limit their practicality;
  5. Building software systems based on them to solve a day-to-day problem.

Current projects

  • RapidChain: RapidChain: Scaling Blockchain Consensus with Full Decentralization [abstract]

    Most decentralized cryptocurrencies such as Bitcoin rely on a consensus protocol that allows a group of mutually-untrusted participants to agree on a public ledger of transactions known as the blockchain. Unlike traditional consensus mechanisms, a blockchain consensus often happens in a peer-to-peer network with open membership, where new participants (with no identities established yet) can join the system during the protocol execution. This setting introduces new fundamental challenges, such as handling Sybil attacks and node churn while providing scalability, that have only recently been studied in the area of Byzantine consensus protocols. Unfortunately, known techniques still fall short of solving these challenges due to major trust assumptions, poor scalability and load-balancing, and high latency, making them impractical and/or insecure for large-scale transaction processing. In this paper, we introduce RapidChain, a scalable consensus protocol for public blockchains that is resilient to Byzantine faults from close to a $1/3$ fraction of the nodes and requires each node to exchange only a sublinear (in the number of participants) amount of information. Unlike previous work, RapidChain does not rely on any public-key infrastructure, trusted setup, or initial public randomness. Moreover, it allows new participants to join or leave the protocol without delaying its execution. To the best of our knowledge, RapidChain is the first blockchain protocol that can, without any trusted setup, shard both the communication and storage overhead of blockchain among smaller committees of nodes such that each node exchanges only a sublinear amount of information. Our empirical evaluations suggest that fully-decentralized blockchains, such as RapidChain, can be practical and, unlike most cryptocurrencies, can scale up their throughput with more resources (\ie, nodes) added to the system.

    [Full paper]
  • FlyClient: Super-Light Clients for Cryptocurrencies [abstract]

    To ensure the validity of transactions, cryptocurrencies rely on a mechanism to verify if particular transactions are included in the blockchain. For example, each node has to check if the inputs to a transaction are valid coins recorded in the blockchain and the current block belongs to the longest chain in case of a fork. To perform these checks, the node has to download all blocks and verify all of them. Currently, syncing all these data blocks in Bitcoin or Ethereum requires a node to send/receive hundreds of Gigabytes of data, taking days for both downloading and verification. Bitcoin has a synchronization mechanism, called simplified payment verification (SPV), that allows clients with limited resources such as mobile phones and tablets to verify transactions without downloading the entire blocks. SPV clients only download block headers which have much smaller size than the full block (80 bytes vs 1 MB in Bitcoin). However, the storage and bandwidth required for each light client still increases linearly with the blockchain size. For example, the Ethereum blockchain currently has about 3.5 million blocks, given that each block header is of size 528 bytes, an SPV client would have to download and store more than 1.5 GB of data to verify any transaction on the Ethereum blockchain. In this paper, we introduce FlyClient, a novel transaction verification protocol for light clients in blockchain protocols that are based on the longest chain principle. FlyClient requires each verifier client to download and store only a logarithmic (rather than a linear) number of block headers to verify any transaction. FlyClient utilizes a non-interactive probabilistic protocol to sample a small (logarithmic) set of random block headers from a full node to limit its likelihood of cheating in the longest-chain verification process given the adversary's limited computational power in creating invalid blocks. We discuss how to implement FlyClient in the current Bitcoin/Ethereum network via a soft fork.

  • PriFi: A low-latency protocol for anonymous communication in local-area networks [abstract]

    Popular anonymity mechanisms such as Tor provide small communication latency, but are vulnerable to traffic-analysis attacks that can de-anonymize users. Besides, known traffic-analysis resistant techniques such as Dissent are impractical for use in latency-sensitive settings such as wireless networks. We propose PriFi, a low-latency protocol for anonymous communication that is provably-secure against traffic-analysis attacks. PriFi allows members of an organization to access the Internet anonymously while they are on-site (via privacy-preserving WiFi networking) or off-site (via privacy-preserving virtual private networking or VPN).

    We reduce communication latency by using a client-relay-server architecture, where a set of servers pre-compute cryptographic material that can cause a major latency bottleneck in the anonymization process when computed on the fly. This architecture, however, introduces vulnerability to equivocation attacks that can be run by a malicious relay to de-anonymize the clients. We describe a simple technique that can prevent such attacks without adding extra latency to the communication.

Previous projects

  • TorBricks: A bridge distribution algorithm for Tor with blocking-resistance and privacy-preserving properties [abstract]
    Tor is currently the most popular network for anonymous Internet access. It critically relies on volunteer nodes called bridges for relaying Internet traffic when a user's ISP blocks connections to Tor. Unfortunately, current methods for distributing bridges are vulnerable to malicious users who obtain and block bridge addresses.

    We propose TorBricks, a protocol for distributing Tor bridges to $n$ users, even when an unknown number ${t < n}$ of these users are controlled by a malicious adversary. TorBricks distributes $O(t\log{n})$ bridges and guarantees that all honest users can connect to Tor with high probability after $O(\log{t})$ rounds of communication with the distributor. We also extend our algorithm to perform privacy-preserving bridge distribution when run among multiple untrusted distributors. This not only prevents the distributors from learning bridge addresses and bridge assignment information, but also provides resistance against malicious attacks from a $\lfloor m/3 \rfloor$ fraction of the distributors, where $m$ is the number of distributors.

  • Scalable Multi-Party Computation: A secure multi-party computation protocol scalable to millions of nodes [abstract]
    We propose scalable protocols for solving the secure multi-party computation (MPC) problem among a large number of parties. We consider both the synchronous and the asynchronous communication models. In the synchronous setting, our protocol is secure against a static malicious adversary corrupting less than a $1/3$ fraction of the parties. In the asynchronous setting, we allow the adversary to corrupt less than a $1/8$ fraction of parties.

    For any deterministic function that can be computed by an arithmetic circuit with $m$ gates, both of our protocols require each party to send a number of field elements and perform an amount of computation that is $\tilde{O}(m/n + \sqrt n)$. We also show that our protocols provide statistical and universally-composable security. To achieve our asynchronous MPC result, we define the threshold counting problem and present a distributed protocol to solve it in the asynchronous setting. This protocol is load balanced, with computation, communication and latency complexity of $O(\log{n})$, and can also be used for designing other load-balanced applications in the asynchronous communication model./>

  • Secure Decentralized Shuffling: A multi-party shuffling protocol robust against malicious faults [abstract]
    In secure multi-party shuffling, multiple parties, each holding an input, want to agree on a random permutation of their inputs while keeping the permutation secret. This problem is important as a primitive in many privacy-preserving applications such as anonymous communication, location-based services, and electronic voting. Known techniques for solving this problem suffer from poor scalability, load-balancing issues, trusted party assumptions, and/or weak security guarantees.

    We propose an unconditionally-secure protocol for multi-party shuffling that scales well with the number of parties and is load-balanced. In particular, we require each party to send only a polylogarithmic number of bits and perform a polylogarithmic number of operations while incurring only a logarithmic round complexity. We show security under universal composability against up to about $n/3$ fully-malicious parties. We also provide simulation results showing that our protocol improves significantly over previous work. For example, for one million parties, when compared to the state of the art, our protocol reduces the communication and computation costs by at least three orders of magnitude and slightly decreases the number of communication rounds.