HoneyBadgerSwap: Making MPC as a Sidechain

by Yunqi Li (UIUC, IC3), Sylvain Bellemare (IC3), Mikerah Quintyne-Collins (HashCloak) and Andrew Miller (UIUC, IC3) at UIUC Decentralized Systems Lab (DSL)

Have fun with HoneyBadgerSwap demo!

(You can find the tutorial at the bottom of the post)

Overview

It is well known that blockchains (just the public bulletin board part) on their own do not provide strong confidentiality and privacy, unless paired with some additional technology, such as cryptography. Ethereum has some built-in support for zero knowledge proofs (ZKP), so many developers will immediately think of this as the main way to add privacy to a smart contract application. However, as Vitalik mentioned in a blogpost about this problem, ZKP alone is not enough to provide confidentiality for many applications that involve computing functions of private inputs from many parties. In fact ZKP is insufficient for privacy-preserving versions of many important and natural applications like auctions, automated market makers, and other DeFi instruments. To provide full confidentiality (or even more fine grained selective disclosure) for these requires something else.

In this post, we show how to provide privacy for smart contracts in a general purpose way by using “Multiparty Computation (MPC) as a Sidechain”. In this model, smart contract developers can label any of their member fields as “secret”. This means that the data itself is not stored on chain, but rather is stored in a secret-shared fashion among a committee of MPC validator nodes that make up the side chain. The MPC nodes perform computations on the secret shared data according to instructions from the main chain, and write results back to the main chain as well. The secret shared data itself is never reconstructed in plaintext, not even on the MPC nodes.

The “MPC as A Sidechain” framework consists of three main components:

1. A coordinator contract written in Solidity deployed on the Ethereum Kovan test network. The coordinator stores all the public (non-confidential) information of the application, as well as metadata about the confidential information. Clients interact directly with the smart contract to request MPC computations, but the smart contract logic implements all the access control (which computations are allowed) and control flow (is the secret shared data available and the computation ready to proceed?)
2. A committee of MPC servers that run the sidechain, storing confidential data as secret shares, and carrying out private MPC computations according to instructions from the coordinator contract.
3. A web-based client front-end, implemented in-browser using Javascript and web3 (which we deliver in a radical-transparency style using JsFiddle, interesting in its own right). Connects to Ethereum via web3, and to the MPC servers through asynchronous xmlhttp calls. Reconstructs secret shares as needed locally.

In our framework, the mainchain acts as a coordinator to orchestrate MPC servers, which form a sidechain committee and perform computation collaboratively. MPC servers engage in computation with secret data according to the instructions publicly visible on the mainchain.

We propose a new unified high-level language called Ratel, that allows application developers to program all above components with a single common language.

Let’s explain a bit about our example application, HoneyBadgerSwap. Our goal is to show how to build an automated market maker (AMM), in the style of Uniswap, but that provides additional confidentiality guarantees with MPC… specifically, that the exact size of the liquidity pool and the volume of trading remain hidden. Trades are processed in batches, and only the final closing price at the end of the batch is disclosed. Traders also learn how much of their trade was matched and with what price slippage, but otherwise nothing else about the other trades in the batch.

The essence of our idea for a confidential Uniswap is to treat the liquidity pool as a secret shared value, and to use MPC computations to carry out trades and liquidity pool deposit/withdraws while keeping the liquidity pool depth itself hidden from everyone. Secret sharing in our case means that there are a quorum of N nodes, any t of which can fail (t<N/3) without harming the system (availability, confidentiality, and integrity all still guaranteed).

Our sidechain nodes implementation consists of a mashup of an existing toolkit for MPC computations (MP-SPDZ), and an Ethereum library (Go Contract Bindings) for interacting with the mainchain smart contracts. We are running a live instance of the prototype we built on the Kovan test network, at least from April 20 2021 through May 20 2021, which you can interact with using Metamask to trade testnet tokens using this AMM. If you want to skip the explanation and go straight to the demo, there’s a step by step tutorial at the bottom of the post.

Background

You’ve probably heard of Uniswap, the most famous and widely used DEX built on Ethereum. It is an automated market maker (AMM). There are two main roles in Uniswap, liquidity provider and traders…. you can become a liquidity provider by depositing a balanced basket of two tokens. In return, they get liquidity tokens, which represents their shares of the entire pool and can be used to redeem later. Traders trade against the liquidity pool while keeping the total liquidity, which is multiplication of quantities of two tokens in the pool, constant. Specifically, suppose the quantities of token. A and B are x and y respectively, then the total liquidity in the pool is k=xy. If a trade would like to sell a amount of token A, then the amount of token B they will get is b=y-k/(x+a)to keep the total liquidity staying the same.

Because there’s a delay between a transaction submission and its actual settlement, the price might have drifted relative to what it was when the order was wrapped up. The exact price you get on a trade is not determined at the time you submit the transaction, but instead depends on the price at the time your transaction is processed. To avoid surprises, traders can specify a slippage limit for their order. If the price has slipped beyond this limit, then the order is cancelled automatically. A similar mechanism is used for limiting slippage when providing liquidity as well.

Uniswap, as currently implemented, is a ”lit market”, where all information about trades are publicly visible, including both the size and side (buy or sell) of each order. As previous orders would move the price of the market, the sequence of filled orders will influence the actual closing price of the asset. It’s now well known that Ethereum has a “dark forest” of miners and/or trading bots that take advantage of privileged knowledge about pending transactions and ability to influence the transaction order in mined blocks, that can and do launch front-running attacks, i.e., changing the order of transactions in a block to make more profit and take advantage of ordinary traders.

In centralized markets, dark pools and sealed bids are useful methods to prevent front-running attacks. When it shifts to the decentralized setting, where the trusted third party is replaced by consensus, people use cryptographic techniques to make DEX confidential. MPC can be viewed as one way of providing fair transaction ordering and our MPC as a sidechain framework allows for MEV-resistant applications.

However, MPC does much more than this. Transactions are not revealed, even after they’re ordered. Fair ordering blockchains and submarine sends don’t do anything about post hoc disclosure of market information.

Background on MPC and ZKP

Why isn’t ZKP enough? We already know how to use zero-knowledge proof and commitment schemes (ZEXE, FuturesMEX, Hawk, Ekiden) to provide confidentiality of orders. However, they are limited to specific kinds of private DEXes which do not provide automatic order matching as no one has the ability to operate on secret data from different entities. MPC is a remedy to this problem. People already worked on implementing various order matching algorithms but they didn’t apply the exchange to the blockchain scenario. So we built HoneybadgerSwap, a private DEX/AMM built on top of an MPC sidechain to preserve order confidentiality.

Hasn’t this been done in MPC before? Building confidentiality-preserving applications like these has long been a motivating use of MPC. Previous works with software implementations include auctions, dark pools, avoiding satellite collision, computing gender pay gap and privacy-preserving machine learning, and in some industrial projects, MPC is used to enable distributed key management (ZenGo and Unbound) and interoperability between blockchains (Ren). However, as software demos, these are held back from reaching their potential in part because they aren’t designed to integrate with the flexibility of smart contract programming tools.

Are you saying MPC is a silver bullet? In general, MPC is also not a panacea. To be clear on the trust model, the secrecy depends on an honest majority of the side chain nodes. This is effectively a permissioned blockchain running as a sidechain to the public main chain. Also MPC has a relatively high communication cost (compared to plaintext data) that makes it unsuitable for expensive computations. The goal of this project is to offer a feasibility proof: at least for some applications, MPC can indeed be a practical system, and that running it as a sidechain is an effective way to get the best benefits of both systems.

Unified High-level Language — Ratel

To build an application like this requires writing code in a few mostly disjoint frameworks: MP-SPDZ for the MPC portion, Vyper or Solidity for the on-chain smart contract, and javascript or some other language with a web3 library to interface between them. We are using our example application to guide the design of a new language called Ratel, that simplifies development of MPC-sidechain applications by providing a single common language for programming all these components.

As we mentioned before, developers can write programs in Ratel language and a specialized compiler will later compile the program into two separate parts: one running on Ethereum and the other running on MPC network. We show the Ratel code snippet of handling trade and secretDeposit requests below. The main value to developers is that the compiler automatically inserts the code necessary to convert between the on-chain and secret shared components. Full code can be found in the appendix.

mapping { address, address => int } publicBalance
mapping { address, address => sint } secretBalance
mapping { address, address => sint, sint } poolSize
func secretDeposit(address token, int amt) {
  address user = msg.sender
  require(publicBalance[token][user] >= amt)
  publicBalance[token][user] -= amt
  secretBalance[token][user] += amt
}
func trade(address tokenA, address tokenB, sint amtA, sint amtB) {
  require(tokenA < tokenB)
  address user = msg.sender
  sint poolA, poolB = poolSize[tokenA][tokenB]
  sint validOrder = (amtA * amtB < 0)
  sint buyA = (amtA > 0)
  sint enoughB = (-amtB  <= secretBalance[tokenB][user])
  sint actualAmtA = poolA  - poolA * poolB / (poolB  - amtB)
  sint acceptA = (actualAmtA  >= amtA)
  sint flagBuyA = validOrder * buyA * enoughB * acceptA
  sint buyB = 1 - buyA
  sint enoughA = (-amtA  <= secretBalance[tokenA][user])
  sint actualAmtB = poolB  - poolA * poolB / (poolA  - amtA)
  sint acceptB = (actualAmtB  >= amtB)
  sint flatBuyB = validOrder * buyB * enoughA * acceptB
  sint changeA = flagBuyA * actualAmtA + flagBuyB * amtA
  sint changeB = flagBuyA * amtB + flagBuyB * actualAmtB
  poolSize[tokenA][tokenB] = poolA - changeA, poolB - changeB
  secretBalance[tokenA][user] += changeA
  secretBalance[tokenB][user] += changeB
}

The secretDeposit function moves users funds from mainchain to MPC sidechain, where funds are burnt on mainchain contract and minted on the sidechain. Before calling the secretDeposit function, users have to call another publicDeposit function to transfer deposit from their personal account to HbSwap contract, which is omitted in the code snippet.

Variables of type sint are private data. In public contract code, an sint variable a is masked by a random number r, which is called an inputmask, generated by MPC servers in advance. Users put a+r on the mainchain which keeps a’s secrecy. Each server owns a share of r so that they can retrieve their respective share [a] using r’s index i that is passed along with masked value a+r. Local MPC functions then operate over shares of secret data.

The compiler splits code into smart contract code and MPC sidechain code on the basis of whether the expression contains sint variables. For example, in secretDeposit function, only the last line of code contains computation over secret data so we mark it in red which represents it belongs to MPC sidechain code while line above are all public contract code.

Once the compiler splits the code into two parts, it then infers which parameters need to pass from contract code to MPC code in the form of emitting events. The workflow of our framework is always client first sending transactions to mainchain and the logs in the transactions instructing MPC servers to accomplish the following computation over secret data. The event emitted by secretDeposit function would be SecretDeposit(address token, address user,uint amt) because updating the user’s secret balance requires these three variables.

Testnet Deployment

To follow along with our demo, we deployed our coordinating contract on Kovan with source code verified. The public address is: 0xe35b498c3e11f22dcf96695d881fe524b1a9ee8e.

How to use HoneybadgerSwap?

Connect to MetaMask

Access our website with a MetaMask extension enabled browser and login to your MetaMask wallet. Connect your account with our site and then your account address will be displayed on the top-right of the window.

Deposit/Withdraw

Users are firstly required to move their funds from the Ethereum mainchain to the MPC sidechain that operates HoneybadgerSwap so that later operations, including token swapping and providing liquidity, can be performed in a way that preserves the exact amounts private. Note that amounts in deposit/withdraw are public as anyone can infer them by checking how much money has been burnt on the mainchain contract. A user’s secret balance will be obfuscated later by secret trading amounts.

Steps to deposit:

1. Select token type. Your current secret balance in HoneybadgerSwap is displayed in the “balance” window. The secret balance is only visible to you, the account owner.
2. Enter the amount to deposit and click the “deposit” button. Several metamask windows will pop up which need your approval to submit transactions to do the following two things:

• PublicDeposit: moving funds from the user’s personal account to the Hbswap(coordinating) contract on the mainchain. Depending on the token type, you are required to submit either one or two transactions at this step as for ERC20 tokens, you need to approve before transferring.
• SecretDeposit: burning funds on the Hbswap contract on the mainchain and minting equal amounts of funds on the user’s secret account on the sidechain.

When the deposit operation is finished, the user’s secret balance will be updated. The frontend reconstructs the secret balance locally from shares received from MPC servers. For demonstration purposes, except for the reconstructed secret balance, we also display each MPC node share on the window.

Similarly, with the “withdraw” button, you can move funds back to your personal account on the mainchain.

Trade

As for sending trade requests to get one type of token with another, the volume and side of the order are kept secret to anyone else. The trade operation consists of several steps as below:

1. Select token pair. Once a valid (tokenFrom!=tokenTo) token pair is selected, you will be able to see your available balances for both tokens in HoneybadgerSwap and the estimated trading price for the pair. The displayed price is the average price of transactions from the previous batch, which is for reference only. The actual trading price of each order is not known until the order has been executed.
2. Enter amounts. The value entered in the “From” token is the amount you’d like to sell and the amount in the “To” window represents the minimum amount you would like to receive. The webpage will calculate the minimum amount you will receive according to the slippage limit you set and also the transaction fee automatically.
3. Click the “trade” button and submit the order. The front-end will execute the following steps:

• Submit a transaction to HbSwap contract to reserve two inputmasks to hide selling amount and buying amount.
• Send HTTP requests to MPC servers to get shares of your input masks and reconstruct them.
• Obfuscate the amounts of your order and submit another transaction to HbSwap contract to publish your order. The transaction will return the sequence number of your new order, which can be used later to retrieve the result(price) of your trade.

Once an order has been submitted, the front-end periodically requests for the result of the order. If the order has been executed, you will get shares of the trading price from MPC servers, which is displayed on the webpage. By constructing the price, you can tell whether your trade is successful(the price is non-zero) or not.

Liquidity Provider

In addition to trading tokens, users can also put their funds into liquidity pools and earn profit as the reward to provide liquidity to the market. Same as trade, the first thing you need to do is selecting a token pair. (We require the address of tokenA to be smaller than tokenB in our implementation) Once a valid token pair is selected, you can also see the estimated price.

Create New Pool

If the estimated price is “Pool not initialized”, it means the pool for the selected token pair has not been initiated. In this case, you can create a new pool by depositing any amount of tokens to it. (In the current version, we do not guarantee the initial price of a pool to be closed to market price.) Of course you need to have enough secret balance to pay for your operation.

Once the initialization is completed, the user’s secret balances will be updated. You get some liquidity tokens which could be used to redeem money back when you withdraw your funds from the pool. Suppose the amounts you just deposit for tokenA and tokenB are amtA and amtB respectively. The amount of liquidity token is sqrt(amtA*amtB).

Add/Remove Liquidity

When the estimated price is non-zero, which means the pool has already been created, you can add liquidity to it while preserving the current ratio of the pool. As the price given is just an estimate and the accurate price is not known until the transaction is actually settled, the amounts entered are the maximal value you’d like to deposit and the exchange will compute the actual amounts according to the real-time price which would not exceed the values you set. For example, suppose the value you would like to deposit is amtA and amtB and the volume of trading pool is poolA and poolB when the order is being executed. Then the actual amount of tokenA deposited to the pool is min{amtA,poolA*amtB/poolB}.

After adding liquidity to the pool, you will get liquidity tokens with an amount representing the proportion of your deposit in the pool, which is totalSupply*amtA/poolA.

By entering the amount of liquidity token you would like to redeem and clicking the “remove” button, you can withdraw your money from the pool to your secret account on the sidechain.

Backend in more detail

In the background, nodes maintain the sidechain and operate the exchange cooperatively. Nodes perform the following functionalities:

1. Respond to http requests received from clients. The http server reads the information from persistent database, which is implemented with leveldb in our demo and sends back to client side. Supported http requests include: GET inputmask, GET trade price and GET secret balance.
2. Generate input masks and write them into leveldb. This is done by a standalone custom MP-SPDZ preprocessing phase that generates random shares.
3. Perform computation in secret form according to the instructions of HbSwap contract. The MPC server keeps monitoring events emitted by the HbSwap contract on the mainchain and takes action accordingly. Events being monitored and corresponding actions can be found in appendix A.

Our website displays the log of one MPC server at the bottom to let you see what is happening on the backend in real-time.

In our demo, we choose the Shamir’s secret sharing with malicious adversaries of MP-SPDZ to implement all MPC operations. Each MPC computation consists of the following steps:

1. Set up input data for MPC program;
2. Run MPC program;
3. Update data in leveldb according to the output of MPC program.

What remains for future work

1. As we mentioned, we have a vision for what the high level Ratel language for unifying smart contracts and MPC will look like, but our next step is to actually implement the compiler. For this demo the “compiler” has been a manual process.
2. The software we use to implement this demo, MP-SPDZ, does not provide support for robust MPC. We plan to integrate the robust MPC approach from HoneyBadgerMPC into this software.
3. In the demo, if a MPC server crashed, we have to shut down the whole service and re-deploy the service from scratch. We are currently working on the design and implementation of an elegant crash recovery mechanism to improve off-chain data persistency.
4. Out current implementation only support running a single MPC program at a time. We plan to do data base sharding and enable parallel computation to improve the performance of the framework.

Overall HoneybadgerSwap is just the starting point of the Stoffel Finance DeFi empire. Look forward to more research articles and demos from us.

Appendix

A. Events and Actions

1. InitPool: move user’s funds from their secret accounts to new pool and mint liquidity tokens for the user.
2. AddLiquidity: calculate the amount of tokens the user could deposit into the pool according to the current price and move user’s funds from secret accounts to pool and mints liquidity tokens for the user.
3. RemoveLiquidity: burn liquidity tokens and withdraw tokens to the user’s secret account.
4. Trade: try to fulfill new orders. If the user’s requirement could be satisfied, then execute the order. Calculate the price of the current trade and reveal it to the order maker after a period of time (for privacy reasons). Update estimated price in batch.
5. SecretDeposit: mint tokens and transfer it into the user’s secret account.
6. SecretWithdraw: burn tokens and submit transactions to mint equal amounts of tokens on the mainchain.

B. Full Ratel Code

Full code for HoneybadgerSwap in Ratel

Corresponding author: Yunqi Li (yunqil3@illinois.edu)

We thank Sarah Allen, IC3 Community Manager, for her help in writing this blog post.