  Fair exchange protocols let two mutually distrustful parties exchange digital
data in a way that neither party can cheat. They have various applications such
as the exchange of digital items, or the exchange of digital coins and digital
services between a buyer/client and seller/server.
  In this work, we formally define and propose a generic blockchain-based
construction called "Recurring Contingent Service Payment" (RC-S-P). It (i)
lets a fair exchange of digital coins and verifiable service reoccur securely
between clients and a server while ensuring that the server is paid if and only
if it delivers a valid service, and (ii) ensures the parties' privacy is
preserved. RC-S-P supports arbitrary verifiable services, such as "Proofs of
Retrievability" (PoR) or verifiable computation and imposes low on-chain
overheads. Our formal treatment and construction, for the first time, consider
the setting where either client or server is malicious.
  We also present a concrete efficient instantiation of RC- S-P when the
verifiable service is PoR. We implemented the concrete instantiation and
analysed its cost. When it deals with a 4-GB outsourced file, a verifier can
check a proof in only 90 milliseconds, and a dispute between a prover and
verifier is resolved in 0.1 milliseconds.
  At CCS 2017, two blockchain-based protocols were proposed to support the fair
exchange of digital coins and a certain verifiable service; namely, PoR. In
this work, we show that these protocols (i) are susceptible to a free-riding
attack which enables a client to receive the service without paying the server,
and (ii) are not suitable for cases where parties' privacy matters, e.g., when
the server's proof status or buyer's file size must remain private from the
public. RC- S-P simultaneously mitigates the above attack and preserves the
parties' privacy.
