Reducing Fair Exchange to Atomic Commit

The fair exchange problem is key to trading electronic items in systems of mutually untrusted parties. We consider modern variants of such systems where each party is equipped with a tamper proof security module. The security modules trust each other but can only communicate by exchanging messages through their host parties. These are untrusted and could intercept and drop those messages. We show that the fair exchange problem at the level of untrusted parties can be reduced to an atomic commit problem at the level of trusted security modules. This reduction offers a new perspective with which fair exchange protocols can be designed. In particular, we present a new atomic commit protocol, called Monte Carlo NBAC, which helps build a new and practical fair exchange solution. The exchange does always terminate and no party commits the exchange with the wrong items. Furthermore, there is an upper bound on the the probability that the exchange ends up being unfair, and this bound is out of the control of the untrusted parties.