Efficient Multiparty Fair Exchange on Bitcoin

Practical MPC on Bitcoin Today

We introduce an efficient protocol for multiple parties in a secure computation (MCP) to exchange their secret inputs fairly. By fairness, we mean the following two guarantees:

  1. An honest party following the protocol/contract faithfully never loses deposit, if any.
  2. If a malicious party deviating from the protocol obtains all secrets and can thus compute the output, he shall compensate all honest parties.

Allowing all inputs to be collected securely and economically, this opens the door for all kinds of MPC to be conduct on Bitcoin, without relying on the cooperation of all parties.

MPC

Previously, we introduce how to conduct MPC on Bitcoin, using decentralized lottery as an example. There is a severe limitation in that it assumes all parties are honest and will provide their secret inputs. This assumption is unlikely to hold in practice, especially when parties find out they will lose by disclosing their secrets.

Two Party Fair Exchange

One way to force each party to reveal their secret is to use Timed Commitment Scheme (TCS) illustrated below. P2 must reveal his secret T before time τ, otherwise P1 can take his deposit q.

TCS

A Naive Approach

Naive 2 party exchange

One might be tempted to use two TCSs between P1 and P2 to exchange secrets. However, P2 can attack the protocol by aborting after he claims P1’s q coins at step 1 and never deposits in step 2. Essentially, P1 loses his deposit even he behaves honestly, making the approach unfair according to our criteria 1.

A Fair Approach

Fair 2 party exchange

In our new scheme, for P2 to claim P1’s deposit, he has to know P1’s secret W1, besides his own W2. If he aborts at step 2, he can no longer claim it. Thus it prevents the aforementioned attack.

Multiparty Party Fair Exchange

We are going to generalize the exchange protocol to n parties, where n > 2. One straight way is to simply run the fair 2-party protocol between each pair. Running each pair takes 2 transactions. Thus, it requires O(n²) transactions in total.

We demonstrate a more efficient protocol, which only needs O(n) transactions.

A Naive Approach

Naive 2 party exchange

It is tempting to extend the 2-party fair exchange using the above approach. However, it is susceptible to an attack if P1 and P2 collude. To see why, simply regard P2 and P1 as the same party. First, P1 reveals w1 in step 3. P3, being honest, reveals w3 in step 2. P2 (essentially P1)aborts in step 1 and get his deposit back after time τ3. Now P1 has all secrets, but P3 does not know w2. It is not fair according to our criteria 2.

A Fair Approach

Fair multiparty exchange

For the exchange to be fair, it proceeds in two phases:

  1. Roof phase: each party deposits to Pn. This can happen in one round simultaneously.
  2. Ladder phase: Pi deposits to P(i-1) alternately, from n to 2. This happens one after the other.

To see why this works, it is clear that at the end of ladder claims, all parties except Pn have evened out. If Pn does not make roof claims then honest parties get q coins via roof refunds. Otherwise Pn also evens out. For a rigorous proof, please refer to paper¹.

[1] How to Use Bitcoin to Design Fair Protocols. Iddo Bentov; Ranjit Kumaresan. Lecture Notes in Computer Science | August 2014.

sCrypt Inc (https://scrypt.io) is a company with mission to providing integrated on-chain smart contracting solutions on Bitcoin SV. scrypt@moneybutton.com

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store