MPC for the Real World: Improving Performance and Usability via Program Analysis, and Applications to Decentralized Finance

Multi-Party Computation (MPC) is a cryptographic technique that enables a number of parties to perform useful computations while keeping their inputs private. The challenge is that, despite many significant advances over the last decade, (1) it remains orders of magnitude slower than its insecure counterpart, and (2) it is largely inaccessible to non-experts; writing efficient applications requires a deep understanding of strengths and weaknesses of various MPC primitives. The primary focus of this work is to make contributions toward overcoming these challenges. To this end, we develop black-box optimization techniques that require no input from the application programmer.

Our first contribution is optimal protocol mixing. Various MPC protocols are inherently well-suited for some tasks and not for others. Thus mixing protocols according to their strengths achieves better efficiency. Unfortunately, a straightforward greedy approach does not work because various protocols have incompatible states. One must appropriately convert the state from one protocol to another when stitching protocols together. We call this problem the Optimal Protocol Assignment (OPA) problem and formulate it as an Integer Program (IP). We prove that, contrary to the long-held conjecture that OPA is NP-Hard, the problem can be solved in polynomial time for the case of 2 protocols. We have implemented our technique. Our evaluation shows that, whereas previous heuristics-based techniques could take from several minutes to several hours, our optimal solution takes seconds to mix a variety of benchmarks.

Our second contribution is better MPC scheduling. We first prove that, like its classical counterpart, optimal scheduling remains NP-Hard despite the simpler structure of MPC programs. We propose a compiler framework (front-end, middle-end, and back-end), and for the middle-end, we provide a formal description of an intermediate representation (IR) that we call MPC-IR. Next, we devise a backend-independent technique for automatic vectorization. Our vectorization algorithm takes un-optimized MPC-IR, replaces scalar operations with vectorized counterparts, and outputs optimized MPC-IR. We prove the correctness of this transformation and our extensive evaluation---on a set of 15 benchmarks, the largest in this area---shows that vectorization reduces circuit evaluation time by upto 55x (BMR, 3-party setting) and communication per channel by up to 13x (GMW setting).

Finally, recognizing that blockchains provide a unique opportunity to  solve "trust" problem through rewards and punishments, we present a design for fast blockchain-based applications. The specific application we devise is a frontrunning resilient market maker (MM). In contrast to the previous works that either require expensive cryptographic tools or additional trust assumptions, we only use lightweight cryptography and game theory. We prove the correctness and security of our construction. Our evaluation shows our performance to be an order of magnitude better than MPC-based constructions. Compared to Uniswap, the largest Decentralized Exchange (DEX), we are 2x better in performance. Moreover, our transactions---being essentially payment transactions---have constant gas costs compared to the variable gas costs of DEXes. This is despite that no current DEX provides defense against frontrunning.