GRUZ: Practical Resource Fair Exchange Without Blockchain

A fair exchange protocol allows two parties to exchange their secret messages fairly. The protocol is said to be fair if either both parties receive secrets from each other or neither of them does. However, complete fairness was proven not always possible by Cleve (STOC 1986) as a corrupted party can always abort early to obtain more advantages than the other party. Thus, we should consider partial fairness. In this paper, we specifically discuss resource fairness (one of partial fairness), which means parties require similar computation resources to recover secrets even if the protocol is aborted at an arbitrary round. One of the methods used to achieve resource fairness is gradual release, where two parties gradually release their private information. We put forward a protocol named GRUZ (Gradual Release Using Zero-knowledge) to realize gradual release in the two-party exchange problem using zero-knowledge from garbled circuits (ZKGC) without blockchain that many past works rely on. Two parties first encrypt messages with their secret keys. Then they gradually release their secret keys one bit at a time alternately so that either party gains an advantage of at most one bit if he/she aborts. The authenticity of the exchanged keys is guaranteed by zero-knowledge proof. We implement this protocol with standard primitives AES, SHA256, and ECDSA, which are compatible with real-world applications such as digital currency exchange. We show that our protocol is practical by analyzing its running time and communication costs.