Efficient Multiparty Fair Exchange on Bitcoin
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:
- An honest party following the protocol/contract faithfully never loses deposit, if any.
- 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.
A Naive Approach
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
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
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
For the exchange to be fair, it proceeds in two phases:
- Roof phase: each party deposits to Pn. This can happen in one round simultaneously.
- 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.
