Intro to Secure Multi-Party Computation
In this post, we will provide a short background on multi-party computation and garbled circuits, explain how we utilize MPC techniques to build private payment channels and discuss how we chose an appropriate software framework to implement our MPC protocol.
Overview
Secure multi-party computation (MPC) allows mutually distrustful parties to correctly compute any function in a way that preserves the secrecy of each party’s inputs and outputs. MPC can be viewed as a way to provide the capabilities of a trusted third party without actually needing that trusted party. In an ideal world, a trusted third party can take private inputs from all parties, compute the function and securely return the results to each party. In practice, we can replace that third party with an MPC.
MPC technology today is being actively applied to solve a number of problems with respect to online advertising, private contact discovery for messaging, and distributed key management, just to name a few. In our setting, the function we are computing checks the correctness of a payment token with respect to off-chain state, computes an ECDSA signature over a Bitcoin transaction and issues a fresh payment token. One party’s input is their secret signing key and the other party provides a Bitcoin transaction and payment token.
Before we dive into the details, we will define two high-level properties central to any joint computation under MPC: privacy and correctness. For privacy, no single party should learn anything more than what can be gleaned from their own output. Each party should also be guaranteed that the output they receive from the MPC is correct.
There are two basic adversarial models typically considered in MPC protocols: semi-honest and malicious. If an MPC protocol is secure in the semi-honest model, this guarantees privacy and correctness as long as the parties involved follow the protocol specification. The malicious secure model, on the other hand, guarantees security for honest parties even if some subset of the participants deviates from the protocol specification in an attempt to learn more.
To understand MPC, we provide some background on the building blocks: oblivious transfer and Andrew Yao’s garbled circuits protocol.
Oblivious Transfer
An oblivious transfer (OT) protocol allows a sender Alice to transfer a requested data item to a receiver Bob without Alice actually learning which data item was sent. In the basic case, there are only two possible data items, say 𝘟₀ and 𝘟₁. Bob selects a bit a ∈ {0, 1}. The OT protocol guarantees that the sender learns nothing about the receiver’s choice of bit a and the receiver learns 𝘟ₐ only. OT is interactive and guarantees the correctness of the output in addition to preserving the sender’s and receiver’s privacy. This is a critical ingredient in garbled circuit protocols to preserve the privacy of the computation.
Garbled Circuits
Garbled Circuits (GC) are a method for implementing MPC. The basic 2-party protocol represents the desired function as a boolean circuit, which makes it efficient for computing functions with lots of bitwise operations, like SHA256. It has a constant number of rounds of communication, which is useful for slow networks.
More specifically, garbled circuits protocols are executed between two parties: a garbler and an evaluator, who jointly evaluate an arbitrary function f on their respective private inputs. Here we will treat the special case where f is a single-output function. The function f is encoded as a boolean circuit using a combination of XOR and AND gates. For each input i of the circuit, the generator picks a pair of random keys k⁰ᵢ and k¹ᵢ (sometimes called wire labels), which represent the possible input bits 0 and 1, respectively. With these keys, the garbler generates an encrypted table for the possible output across all the gates in the circuit. The evaluator can obtain the correct output if they have the keys that correspond to the actual inputs.
The circuit is known by both parties: Alice (as garbler) and Bob (as evaluator). Alice has a private input x and Bob has a private input y. They both want to securely compute f(x,y). Alice encrypts the circuit and sends the garbled circuit f′ to Bob along with her encrypted input (or garbled x′). Using an oblivious transfer protocol, Bob (as receiver) interacts with Alice (as sender) to learn his encrypted inputs y′ (or garbled y′) without Alice learning his private input y.
Once Bob has the encrypted circuit and encrypted inputs, he proceeds to compute the circuit gate by gate and obtains the output f(x, y). The garbled circuit construction guarantees that Bob learns only f(x,y), that is, the function f for the specified inputs, and nothing else. For a more in-depth treatment of garbled circuits, we refer the reader to Vitalik’s primer here.
Applications of MPC to zkChannels
At Bolt Labs, we’re developing a privacy-preserving payment channel between a customer and a merchant (see our blog post on the zkChannels protocol). This lets two parties lock funds in escrow and then perform unlimited transfers/payments of Bitcoin off chain. With each transfer, the parties cooperate to update the channel balances and ensure that both parties can close down the channel on the new balance without the risk of losing funds.
We use MPC techniques to achieve this cooperation in a privacy-preserving way. That is, each payment is anonymous: the merchant knows they are being paid, but they cannot link that payment to a specific customer. The MPC computes two outputs for the customer: an ECDSA signature on a Bitcoin transaction and a payment token. If the customer is ready to close the channel, they can use the Bitcoin transaction; otherwise, they can use the payment token for a future state update (i.e., another payment). The beauty of MPC is that both of these outputs are issued to the customer without the merchant learning any information that could reveal which customer participated in the protocol.
We accomplish this as follows: the customer and merchant begin by specifying their private inputs. The customer’s private inputs consist of information about the channel, including both the current state and the next state. The merchant’s private inputs consist of an ECDSA signing key and an HMAC key.
Under MPC, they construct a correctly formatted Bitcoin transaction digest that reflects the payment amount, and then hash and sign that digest with the merchant’s ECDSA signing key. They also compute an HMAC on the updated state to form a new payment token. This payment token enables the customer to prove under MPC that they interacted with the merchant in the past and have sufficient balance in the channel.
In summary, the MPC execution guarantees that each party learns nothing about the other’s private inputs: the merchant does not learn the identity of the customer or channel balance information, and the customer does not learn the merchant’s private keys. In the above, we described the high-level aspects of our MPC functionality; we’ll release technical details in a forthcoming academic paper.
Software Framework Selection & Performance Tradeoffs
To implement our MPC protocol, we used an existing software framework that runs MPC on an arbitrary function. We chose the Efficient Multi-Party (EMP) computation toolkit. This framework has several advantages that make it well-suited for our application: in particular, it supports multiple protocols in both the semi-honest and malicious security models, and all of these protocols are in the garbled circuit paradigm.
In our implementation, the merchant plays the role of the garbler, and the customer evaluates. This was a natural choice as only the customer is supposed to receive an output from the computation. Additionally, the garbling party also has slightly higher resource requirements, since garbling a circuit requires lots of encryption operations to build the truth tables for each gate. In the EMP toolkit, this isn’t a significant overhead, but a merchant can customize their hardware setup to handle this load.
EMP toolkit implements a C library used to describe secure functionalities. The library either executes a semi-honest protocol or compiles the function into a boolean circuit. This circuit can be passed to one of several additional MPC protocol implementations (including several that are secure against a malicious adversary).
Our application breaks down into several main functionalities, including lots of SHA256 hashes, lots of input validation, and ECDSA signatures. With the exception of the signatures, all of these functions are basically boolean operations: bit shifts, equality checks, and XOR masks.
EMP-toolkit represents data as encrypted (garbled) bits and functions as boolean circuits. The other common paradigm in MPC literature represents data as secret-shares in a finite field and functions as arithmetic circuits. Such protocols are less efficient on bit-based operations that make up the majority of our application.
Some modern frameworks [2] allow mixing boolean and arithmetic circuits within a single computation to optimize based on the strengths of each individual approach. In the future, we will investigate these frameworks to optimize the ECDSA signatures in our application. For more details on other MPC software frameworks, we refer the reader to a more comprehensive evaluation by Hastings et al [1].
Special thanks to Colleen Swanson and Marcella Hastings for proofreading and providing valuable feedback on this post.
References
