the first scheme of its kind that remains secure if either the client or
server is malicious. It also preserves the two parties’ privacy. We have also
proposed an efficient concrete instantiation of RC-S-P when the service is PoR
and implemented this concrete instantiation. Our run-time evaluation has
demonstrated that the instantiation is computationally more efficient than the
state-of-the-art.

We also showed that the state-of-the-art fair exchange protocols that have
been designed to allow a fair exchange of digital coins and a digital
(verifiable) service are susceptible to a free-riding attack. We also showed
that these protocols do not preserve the parties’ privacy.

As illustrated in this work, a free-rider attacker can directly benefit from
the lack of privacy in the schemes we studied. The lack of privacy is common
among other blockchain-based fair exchange protocols too, e.g., those in [26,
25, 58]. We hope the attack we described will shed light on the seriousness of
the lack of privacy in fair exchange protocols.

## Acknowledgements

Aydin Abadi and Steven J. Murdoch were supported in part by REPHRAIN: The
National Research Centre on Privacy, Harm Reduction and Adversarial Influence
Online, under UKRI grant: EP/V011189/1. Steven J. Murdoch was also supported
by The Royal Society under grant UF160505.

## References

  * [1] Aydin Abadi and Aggelos Kiayias.  Multi-instance publicly verifiable time-lock puzzle and its applications.  In , FC, 2021.
  * [2] Amazon.  Amazon s3 pricing, 2021.
  * [3] Elli Androulaki, Ghassan Karame, Marc Roeschlin, Tobias Scherer, and Srdjan Capkun.  Evaluating user privacy in bitcoin.  In FC, 2013.
  * [4] Anonymous.  Off-chain source code of “recurring contingent proofs of retrievability payment” (RC-PoR-P), 2021.  https://github.com/Anonymised-RCSP/RC-PoR-P-Source-code/blob/main/RC-PoR-P.cpp.
  * [5] Anonymous.  On-chain source code of “recurring contingent proofs of retrievability payment” (RC-PoR-P), 2021.  https://github.com/Anonymised-RCSP/RC-PoR-P-Source-code/blob/main/RC-PoR-P-Smart-Contract.sol.
  * [6] Frederik Armknecht, Jens-Matthias Bohli, Ghassan O Karame, Zongren Liu, and Christian A Reuter.  Outsourced proofs of retrievability.  In CCS, 2010.
  * [7] N. Asokan, Matthias Schunter, and Michael Waidner.  Optimistic protocols for fair exchange.  In CCS, 1997.
  * [8] N. Asokan, Victor Shoup, and Michael Waidner.  Optimistic fair exchange of digital signatures (extended abstract).  In EUROCRYPT, 1998.
  * [9] Giuseppe Ateniese, Randal C. Burns, Reza Curtmola, Joseph Herring, Lea Kissner, Zachary N. J. Peterson, and Dawn Xiaodong Song.  Provable data possession at untrusted stores.  In CCS, 2007.
  * [10] Feng Bao, Robert H. Deng, and Wenbo Mao.  Efficient and practical fair exchange protocols with off-line TTP.  In S&P, 1998.
  * [11] Simon Barber, Xavier Boyen, Elaine Shi, and Ersin Uzun.  Bitter to better - how to make bitcoin a better currency.  In FC, 2012.
  * [12] Emily Bary.  Zoom stock falls after service outage, 2020.
  * [13] Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza.  Zerocash: Decentralized anonymous payments from bitcoin.  In S&P, 2014.
  * [14] Dan Boneh and Moni Naor.  Timed commitments.  In CRYPTO, 2000.
  * [15] Matteo Campanelli, Rosario Gennaro, Steven Goldfeder, and Luca Nizzardo.  Zero-knowledge contingent payments revisited: Attacks and payments for services.  In CCS, 2017.
  * [16] Ran Canetti, Ben Riva, and Guy N. Rothblum.  Practical delegation of computation using multiple servers.  In CCS, 2011.
  * [17] Richard Cleve.  Limits on the security of coin flips when half the processors are faulty (extended abstract).  In STOC, 1986.
  * [18] Ronald Cramer, Ivan Damgård, and Yuval Ishai.  Share conversion, pseudorandom secret-sharing and applications to secure computation.  In TCC, 2005.
  * [19] Wei Dai.  Crypto++ library, 2014.  https://cryptopp.com.
  * [20] Ivan Damgård and Yuval Ishai.  Constant-round multiparty computation using a black-box pseudorandom generator.  In CRYPTO, 2005, Proceedings, 2005.
  * [21] Changyu Dong, Liqun Chen, Jan Camenisch, and Giovanni Russello.  Fair private set intersection with a semi-trusted arbiter.  In DBSec, 2013.
  * [22] Changyu Dong, Yilei Wang, Amjad Aldweesh, Patrick McCorry, and Aad van Moorsel.  Betrayal, distrust, and rationality: Smart counter-collusion contracts for verifiable cloud computing.  In CCS, 2017.
  * [23] Dropbox.  Choose the right dropbox for you, 2021.
  * [24] Yuefeng Du, Huayi Duan, Anxin Zhou, Cong Wang, Man Ho Au, and Qian Wang.  Enabling secure and efficient decentralized storage auditing with blockchain.  TDSC, 2021.
  * [25] Stefan Dziembowski, Lisa Eckey, and Sebastian Faust.  Fairswap: How to fairly exchange digital goods.  In CCS, 2018.
  * [26] Lisa Eckey, Sebastian Faust, and Benjamin Schlosser.  Optiswap: Fast optimistic fair exchange.  In ASIA CCS, 2020.
  * [27] Georg Fuchsbauer.  WI is not enough: Zero-knowledge contingent (service) payments revisited.  In CCS, 2019.
  * [28] Juan A. Garay and Markus Jakobsson.  Timed release of standard digital signatures.  In FC, 2002.
  * [29] Rosario Gennaro, Craig Gentry, and Bryan Parno.  Non-interactive verifiable computing: Outsourcing computation to untrusted workers.  In CRYPTO, 2010.
  * [30] Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova.  Quadratic span programs and succinct nizks without pcps.  In EUROCRYPT, 2013.
  * [31] Satrajit Ghosh and Tobias Nilges.  An algebraic approach to maliciously secure private set intersection.  In EUROCRYPT, 2019.
  * [32] Oded Goldreich.  The Foundations of Cryptography - Volume 1: Basic Techniques.  Cambridge University Press, 2001.
  * [33] GoogleOne.  Upgrade to a plan that works for you, 2021.
  * [34] Shai Halevi, Danny Harnik, Benny Pinkas, and Alexandra Shulman-Peleg.  Proofs of ownership in remote storage systems.  In CCS, 2011.
  * [35] Todd Haselton.  Slack service goes down for more than three hours, 2021.
  * [36] Chunqiang Hu, Xiuzhen Cheng, Zhi Tian, Jiguo Yu, and Weifeng Lv.  Achieving privacy preservation and billing via delayed information release.  IEEE/ACM Transactions on Networking, 2021.
  * [37] Yuval Ishai, Rafail Ostrovsky, and Vassilis Zikas.  Secure multi-party computation with identifiable abort.  In CRYPTO, 2014.
  * [38] Ari Juels and Burton S. Kaliski Jr.  Pors: Proofs of retrievability for large files.  In CCS, 2007.
  * [39] Harry A. Kalodner, Steven Goldfeder, Xiaoqi Chen, S. Matthew Weinberg, and Edward W. Felten.  Arbitrum: Scalable, private smart contracts.  In USENIX Security, 2018.
  * [40] Jonathan Katz and Yehuda Lindell.  Introduction to Modern Cryptography.  Chapman and Hall/CRC Press, 2007.
  * [41] Ahmed E. Kosba, Andrew Miller, Elaine Shi, Zikai Wen, and Charalampos Papamanthou.  Hawk: The blockchain model of cryptography and privacy-preserving smart contracts.  In S&P, 2016.
  * [42] Kaspersky Lab.  Understanding security of the cloud: from adoption benefits to threats and concerns.  Kaspersky daily, 2018.
  * [43] Junzuo Lai, Robert H. Deng, HweeHwa Pang, and Jian Weng.  Verifiable computation on outsourced encrypted data.  In ESORICS 2014, 2014.
  * [44] Zheli Liu, Tong Li, Ping Li, Chunfu Jia, and Jin Li.  Verifiable searchable encryption with aggregate keys for data sharing system.  Future Gener. Comput. Syst., 2018.
  * [45] Gregory Maxwell.  Zero knowledge contingent payment, 2011.
  * [46] Ralph C. Merkle.  Protocols for public key cryptosystems.  In S&P, 1980.
  * [47] Ralph C. Merkle.  A certified digital signature.  In CRYPTO, 1989.
  * [48] Lauren Merryweather.  Three in five people have received a scam delivery text in the past year, 2021.  https://www.which.co.uk/news/2021/06/three-in-five-people-have-received-a-scam-delivery-text-in-the-last-year.
  * [49] Y. Miao, Q. Tong, R. Deng, K. R. Choo, X. Liu, and H. Li.  Verifiable searchable encryption framework against insider keyword-guessing attack in cloud storage.  IEEE Transactions on Cloud Computing, 2020.
  * [50] Andrew Miller, Ari Juels, Elaine Shi, Bryan Parno, and Jonathan Katz.  Permacoin: Repurposing bitcoin work for data preservation.  In S&P’14.
  * [51] Satoshi Nakamoto.  Bitcoin: A peer-to-peer electronic cash system.  Technical report, 2019.
  * [52] Ky Nguyen, Miguel Ambrona, and Masayuki Abe.  WI is almost enough: Contingent payment all over again.  In CCS, 2020.
  * [53] Torben P. Pedersen.  Non-interactive and information-theoretic secure verifiable secret sharing.  In CRYPTO, 1991.
  * [54] GNU Project.  The gnu multiple precision arithmetic library, 1991.  https://gmplib.org/.
  * [55] Fergal Reid and Martin Harrigan.  An analysis of anonymity in the bitcoin system.  In PASSAT, 2011.
  * [56] Hovav Shacham and Brent Waters.  Compact proofs of retrievability.  In ASIACRYPT, 2008.
  * [57] Shiuan-Tzuo Shen and Wen-Guey Tzeng.  Delegable provable data possession for remote data in the clouds.  In ICICS 2011.
  * [58] Florian Tramèr, Fan Zhang, Huang Lin, Jean-Pierre Hubaux, Ari Juels, and Elaine Shi.  Sealed-glass proofs: Using transparent enclaves to prove and sell knowledge.  In EuroS&P, 2017.
  * [59] UK Finance.  2021 half year fraud update, 2021.  https://www.ukfinance.org.uk/system/files/Half-year-fraud-update-2021-FINAL.pdf.
  * [60] Xingfeng Wang and Liang Zhao.  Verifiable single-server private information retrieval.  In ICICS, 2018.
  * [61] Gavin Wood et al.  Ethereum: A secure decentralised generalised transaction ledger.  Ethereum project yellow paper, 2014.
  * [62] Liang Feng Zhang and Reihaneh Safavi-Naini.  Verifiable multi-server private information retrieval.  In ACNS, 2014.

##  Appendix A Survey of Related Work

As stated in the introduction, blockchain technology and in particular smart
contracts have the potentials to replace the third party in fair exchange
protocols. Ethereum is the most predominant generic smart contract platform.
Although the third-party’s role can be directly encoded/programmed in an
Ethereum smart contract, it would not be efficient. Moreover, Bitcoin, as the
most popular cryptocurrency, supports smart contracts with very limited
functionalities. Therefore, the third party’s full role cannot be directly
encoded in a contract on the Bitcoin blockchain.

###  A.1 Zero-knowledge Contingent Payment

For the first time in [45] it was shown how to construct a fair exchange
protocol, called “zero-knowledge contingent payment”, that utilises Bitcoin’s
smart contract capabilities. The protocol allows a fair exchange of digital
goods and payments over Bitcoin’s network. Its main security requirement is
that a seller is paid if and only if a buyer learns a correct secret. The
protocol uses a feature of Bitcoin’s scripting language, called “hash-lock
transaction”. This type of transaction lets one create a payment transaction
that specifies a hash value $y$ and allows anyone that can provide its
preimage $k$, i.e $\mathtt{H}(k)=y$, to claim the amount of coin specified in
the transaction. The contingent payment protocol in [45] works as follows. The
seller first picks a secret key, $k$, of a symmetric-key encryption and uses
it to encrypt the secret information, $s$. This yields a ciphertext, $c$. It
also computes the key’s hash, $y=\mathtt{H}(k)$. The seller sends $c,y$, and a
(zero-knowledge) proof to the buyer, where the proof asserts that $c$ is the
encryption of $s$ under key $k$ and $\mathtt{H}(k)=y$.

After the buyer verifies and accepts the proof, it sends a transaction to the
blockchain that pays the seller a fixed amount of coin if the seller provides,
to the blockchain, a value $k$ such that $\mathtt{H}(k)=y$. Next, the seller
sends $k$ to the blockchain and receives the coins. Now, the buyer can read
the blockchain and learn $k$ which allows it to decrypt $c$, and extract the
secret, $s$. Later, after the advancement of the “succinct non-interactive
argument of knowledge” (zk-SNARK) [30], that results in a more efficient
implementation of zero-knowledge proofs, the contingent payment protocol was
modified to use zk-SNARK. However, all zk-SNARKs require a trusted third party
for a trusted setup, i.e., to generate a “common reference string” (CRS),
which means there would be a need for the involvement of an additional third
party in those protocols that use them, including the contingent payment
protocol. As such involvement is undesirable, the contingent payment protocol,
that uses zk-SNARK, lets the buyer play the role of the third party and
generate the parameter.

###  A.2 Zero-knowledge Contingent Service Payment

Later, Campanelli et al. [15] identify a serious security issue of the above
contingent payment (that uses zk-SNARK and lets a buyer pick a CRS). In
particular, the authors show that a malicious buyer (which generates the CRS)
can construct the CRS in a way that lets it learn the secret from the seller’s
proof without paying the seller. Campanelli et al. propose a set of fixes;
namely, (a) jointly computing the CRS using a secure two-party computation,
(b) allowing the seller to check the well-formedness of the buyer’s CRS, or
(c) using a new scheme called “zero-knowledge Contingent Service Payments”
(zkCSP). The latter solution is a more efficient approach than the other two
and offers an additional interesting feature; namely, supporting contingent
payment for _digital (verifiable) services_. In short, zkCSP works as follows.
Let $\mathtt{v}(.)$ be the verification algorithm for a certain service and
$s$ be the service’s proof, where if the proof is valid it holds that
$\mathtt{v}(s)=1$. The parties agree on two claw-free hash functions, e.g.,
$\mathtt{H}_{\scriptscriptstyle 1}(.)$ and $\mathtt{H}_{\scriptscriptstyle
2}(.)$. The seller picks a random value, $r$. Then, it computes either
$y=\mathtt{H}_{\scriptscriptstyle 1}(r)$ if it knows $s$ such that
$\mathtt{v}(s)=1$, or $y=\mathtt{H}_{\scriptscriptstyle 2}(r)$ otherwise. The
seller also generates a witness indistinguishable proof of knowledge (WIPoK),
$\pi$, using a compound sigma protocol to prove that it knows either the
preimage of $y=\mathtt{H}_{\scriptscriptstyle 1}(r)$ if it knows a valid $s$,
i.e., $\mathtt{v}(s)=1$, or the preimage of $y=\mathtt{H}_{\scriptscriptstyle
2}(r)$. Note, due to the witness indistinguishability of $\pi$ and the flaw-
freeness of the hash functions, the verifier cannot tell which statement the
prover is proving.

The seller sends the proof along with $y$ to the buyer which first ensures
$\pi$ is valid. Then, if the check passes, the buyer sends to the blockchain a
hash-lock transaction that would send $n$ coins to the party that can provide
$r$ to the blockchain such that $y=\mathtt{H}_{\scriptscriptstyle 1}(r)$.
After a seller provides a valid $r$ to the blockchain it gets paid,
accordingly the buyer concludes that it has been served honestly by the
seller, as the seller demonstrated the knowledge of the service proof, $s$.
Otherwise (if the seller does not provide a valid $r$) it would not get paid
and the buyer learns nothing about $s$. To improve the efficiency of the above
zkCSP and to make it practical, the authors suggest using SNARKs in the
setting that the buyer generates the CRS but the seller initially performs
minimal efficient checks. Also, as concrete instantiations of the zkCSP, the
authors propose two schemes in which the service is “proof of retrievability”
(PoR) [56]. One of the schemes relies on a publicly verifiable PoR and the
other one relies on a privately verifiable one. In these schemes, the buyer
uploads its data to a server and pays if and only if the server provides valid
proof that asserts the buyer’s data is retrievable.

###  A.3 Known Zero-knowledge Contingent (Service) Payment’s Flaw in the
Literature

Fuchsbauer [27] identifies a flaw in the above zkCSP. The author shows that
the minimal efficient check that the seller performs in the zkCSP is not
sufficient, because it does not prevent the buyer from cheating and learning
the secret. He highlights that the use of computationally expensive
verification on the CRS is inevitable to address the issue. Very recently,
Nguyen et al. [52] show that by relying on a slightly stronger notion of WI
(i.e., trapdoor subversion witness indistinguishability), the zkCSP can remain
secure and would not be susceptible to the issues Fuchsbauer pointed out.
Moreover, they propose an efficient scheme that relies on an _interactive_ ZK
proof system which is based on garbled circuits and oblivious transfer.
However, the two issues (i.e., the attack and the lack of privacy), we
highlighted in Section 5, are not identified and addressed in [27, 52].

###  A.4 Using Ethereum Smart Contracts in Contingent Payment

Tramer et al. [58] propose a fair exchange scheme that uses a combination of
trusted hardware, i.e., Intel SGX, and Ethereum smart contracts.
Interestingly, unlike the common assumption that secure hardware maintains
private states, this scheme relies on weaker security assumptions, i.e., it
only relies on the integrity of SGX’s computation and the authenticity of a
message it sends. At a high level, in this scheme, the buyer and seller agree
on a smart contract and then the buyer deposits a fixed amount of coin in the
smart contract. Then, the seller sends its messages (that contains proofs) to
SGX which verifies the messages’ correctness and then sends its verdict to the
smart contract. Next, the contract distributes the deposit according to the
SGX’s verdicts. The scheme in addition to achieving fair exchange wants to
ensure that after the parties’ initial interaction and after the seller makes
an offer, the buyer cannot abort without paying the seller. To this end, in
the scheme, the contract needs to validate SGX’s signature (or in general
attestation). However, as the authors state, in practice the signature scheme
used in SGX (i.e., EPID signature) is not supported by standard Ethereum
contracts. Therefore, the suggested technique, to ensure the buyer cannot
abort, remains only of theoretical interest. Also, in the protocol SGX is
always involved, regardless of the parties’ behaviour.

Later, Dziembowski et al. [25] propose FairSwap, an efficient protocol for a
fair exchange of digital goods (i.e., files) and coins. It is mainly based on
the Ethereum smart contracts and the notion of proof of misbehaviour [16].
Briefly, a proof of misbehaviour scheme is usually based on a Merkle tree; in
this scheme, proving that a party has misbehaved is much cheaper than proving
it has behaved honestly. FairSwap offers two main features: (a) imposes a low
computation cost to a smart contract, and (b) avoids using zero-knowledge
proofs. At a high level, FairSwap works as follows. First, the seller and
buyer agree on a smart contract. Then, the seller picks a key $k$ (for
symmetric-key encryption), encrypts the secret (i.e., file) under $k$, and
sends the ciphertext to the buyer. The seller also commits to $k$ and sends
the commitment to the smart contract. Next, the buyer verifies the correctness
of the buyer’s messages and if approved, it sends a fixed amount of coin to
the smart contract. After that, the seller reveals the opening of the
commitment, that contains $k$, to the smart contract. This allows the buyer to
read from the contract and learn $k$ with which it can decrypt the ciphertext,
extract the secret, and then verify the secret’s correctness. In the case
where the buyer rejects the secret, it can send a short proof (of
misbehaviour) to the contract which performs an efficient verification and
distributes the deposit according to the verification’s result.

Very recently, Eckey et al. [26] propose OPTISWAP that improves FairSwap’s
performance. It also ensures a malicious seller cannot force the buyer to
submit a large transaction to the blockchain, which ultimately imposes
transaction costs to the buyer, i.e., the grieving attack. Similar to
FairSwap, OPTISWAP uses a smart contract and proof of misbehaviour.
Nevertheless, to achieve a better efficiency (than FairSwap), OPTISWAP uses an
_interactive_ dispute resolution protocol, previously proposed and used in
[39]. The interactive phase is a challenge-response procedure between the two
parties and lets an honest buyer efficiently generate proof of misbehaviour.
After computing the proof, the buyer sends it to the contract which verifies
the proof and distributes the deposit according to the verification result. To
prevent the grieving attack, the protocol requires the seller to deposit coins
to the contract as well, which allows the contract to compensate an honest
buyer which reports the seller’s misbehaviour.

We highlight that the protocols in [25, 26, 58] have been designed and are
suitable for a fair exchange of digital items, e.g., file, and digital coins.
Nevertheless, they are not suitable for verifiable services, e.g., PoR. If
they are _directly_ used for verifiable services, then they would suffer from
the two issues we stated in Section 5 (i.e., a malicious client can mount a
free-riding attack and lack of privacy). For instance, if they are naively
used for PoR, then a malicious client (as a buyer) can simply avoid engaging
in the payment protocol with the server (as a seller), even though the server
has honestly maintained the buyer’s data. This means the client can waste the
server’s resources. This issue would not be fully addressed by simply forcing
the client to deposit coins at the point where it outsources its data.
Because, the client can encode its data in a way that makes the server compute
an invalid proof, that ultimately allows the client to withdraw its deposit
and avoid paying the server. Moreover, the amount of deposit leaks non-trivial
information about the secret (or the file in the PoR context) in real-time to
the public.

Very recently, outsourced (fair) PoR schemes that allow a client to delegate
the verifications to a smart contract have been proposed in [1, 24]. The
scheme in [1] uses message authentication code (MAC) and time-lock puzzle that
results in low cost in the proof generation and verification phases while the
one in [24] is based on polynomial commitment and involves a high number of
modular exponentiations that lead to higher proof generation and verification
cost than the former scheme. The schemes in [1, 24] do not address the above
privacy issue either and rely on a stronger security assumption than the rest
of the work studied in this section, as these two protocols assume the client
is fully honest while the rest assume either party can be corrupt.

##  Appendix B Notations

We summarise our notation in Table III.

Table III:  Notation Table.

Setting | Symbol | Description
---|---|---
Generic | $z$ | Number of verifications
$\lambda$ | Security parameter
$\mathtt{PRF}$ | Pseudorandom function
$\zeta$ |  $\mathtt{PRF}$’s description
$Pr$ | Probability
$\mathtt{Com}$ | Commit algorithm in commitment
$\mathtt{Ver}$ | Verify algorithm in commitment
$\mu$ | Negligible function
$\mathtt{H}$ | Hash function
$\mathtt{MT}$ | Merkle tree
${sk,pk}$ | Secret and public keys
$\mathtt{PoR}$ | Proof of retrievability
$u$ | Service input, e.g., file
$u^{\scriptscriptstyle*}$ | Encoded input
$\sigma$ | Metadata
$\omega_{\scriptscriptstyle\sigma}$ | Proof for metadata’s correctness
$e$ | $e:=(\sigma,\omega_{\scriptscriptstyle\sigma})$
$pp$ | Public parameter
$q,\bm{q}$ | Query and query vector
$\bm{\omega}_{\scriptscriptstyle q}$ | Proof for $\bm{q}$’s correctness
$c$ | $c:=(\bm{q},\bm{\omega}_{\scriptscriptstyle q})$
$\pi,\bm{\pi}$ | Service proof and proof vector
$\mathtt{VS}$ | Verifiable service
$\mathtt{VSID}$ | Verifiable service with identifiable abort
$\mathtt{RCSP}$ | Recurring contingent service payment
$\mathtt{SAP}$ | Statement agreement protocol
$\mathcal{C}$ | Client
$\mathcal{S}$ | Server
$\mathcal{R}$ | Arbiter
| SC | Smart contract
Generic | ${F}$ | Function run on $u^{\scriptscriptstyle*}$ by $\mathcal{S}$
${M}$ | Metadata generator function
${Q}$ | Query generator function
aux | Auxiliary information
$m$ | Number of a file blocks, $m=|u^{\scriptscriptstyle*}|$
$||u^{\scriptscriptstyle*}||$ | Bit size of $u^{\scriptscriptstyle*}$
$\delta$ | Proof of $F$’s evaluation correctness
$j$ | Verification index, $1\leq j\leq z$
$adr$ | Address
$\phi$ | Number of challenged blocks
RC-S-P or RC-PoR-P | $r_{\scriptscriptstyle qp},r_{\scriptscriptstyle cp}$ | Random values
$\ddot{x}_{\scriptscriptstyle qp},\ddot{x}_{\scriptscriptstyle cp}$ | $\ddot{x}_{\scriptscriptstyle qp}:=(qp,r_{\scriptscriptstyle qp}),\ddot{x}_{\scriptscriptstyle cp}:=(cp,r_{\scriptscriptstyle cp})$
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}$ | Encoded coins deposited by $\mathcal{C}$ and $\mathcal{S}$
$enc$ | Encoding/decoding functions $enc:=(E,D)$
$m_{\scriptscriptstyle\mathcal{C}},m_{\scriptscriptstyle\mathcal{S}}$ | Complaints of $\mathcal{C}$ and $\mathcal{S}$
$pad_{\scriptscriptstyle\pi},pad_{\scriptscriptstyle q}$ | Number of elements used to pad $\pi$ and $q$
$y_{\scriptscriptstyle\mathcal{C}},y_{\scriptscriptstyle\mathcal{S}}$ | Number of times $\mathcal{C}$ and $\mathcal{S}$ misbehave towards each other
$y^{\prime}_{\scriptscriptstyle\mathcal{C}},y^{\prime}_{\scriptscriptstyle\mathcal{S}}$ | Number of times $\mathcal{C}$ and $\mathcal{S}$ unnecessarily invoke $\mathcal{A}r$
${cp}$ | Coin secret parameters
$T_{\scriptscriptstyle cp}$ | Coin encoding token
${qp}$ | Query/proof secret parameters
$T_{\scriptscriptstyle qp}$ | Query/proof encoding token
$T$ | $T:=(T_{\scriptscriptstyle cp},T_{\scriptscriptstyle qp})$
$g_{\scriptscriptstyle\mathcal{C}},g_{\scriptscriptstyle\mathcal{S}}$ | Commitments computed by $\mathcal{C}$ and $\mathcal{S}$
$pl$ | Price list: $\\{(o,l),...,(o^{\prime\prime},l^{\prime\prime})\\}$
$o$ | Coins $\mathcal{S}$ must get for a valid proof, where $o\in pl$
$l$ | Coins $\mathcal{A}r$ must get for resolving a dispute, where $l\in pl$
$l_{\scriptscriptstyle max}$ | $Max(l,...,l^{\prime\prime})$
| $o_{\scriptscriptstyle max}$ | $Max(o,...,o^{\prime\prime})$
| $p_{\scriptscriptstyle\mathcal{S}}$ | Total coins $\mathcal{S}$ should deposit

##  Appendix C Preliminaries

###  C.1 Details on Building Blocks

####  C.1.1 Pseudorandom Function

Informally, a pseudorandom function ($\mathtt{PRF}$) is a deterministic
function that takes as input a key and some argument and outputs a value
indistinguishable from that of a truly random function with the same domain
and range. Pseudorandom functions have many applications in cryptography as
they provide an efficient and deterministic way to turn input into a value
that looks random. Below, we restate the formal definition of $\mathtt{PRF}$,
taken from [40].

######  Definition 7.

Let
$W:\\{0,1\\}^{\scriptscriptstyle\psi}\times\\{0,1\\}^{\scriptscriptstyle\eta}\rightarrow\\{0,1\\}^{\scriptscriptstyle\iota}$
be an efficient keyed function. It is said $W$ is a pseudorandom function if
for all probabilistic polynomial-time distinguishers $B$, there is a
negligible function, $\mu(.)$, such that:

$\bigg{|}\Pr[B^{\scriptscriptstyle
W_{\hat{k}}(.)}(1^{\scriptscriptstyle\psi})=1]-\Pr[B^{\scriptscriptstyle\omega(.)}(1^{\scriptscriptstyle\psi})=1]\bigg{|}\leq\mu(\psi)$

where the key,
$\hat{k}\stackrel{{\scriptstyle\scriptscriptstyle\$}}{{\leftarrow}}\\{0,1\\}^{\scriptscriptstyle\psi}$,
is chosen uniformly at random and $\omega$ is chosen uniformly at random from
the set of functions mapping $\eta$-bit strings to $\iota$-bit strings.

####  C.1.2 Commitment Scheme

A commitment scheme involves two parties, _sender_ and _receiver_ , and
includes two phases: _commit_ and _open_. In the commit phase, the sender
commits to a message: $x$ as
$\mathtt{Com}(x,r)=\mathtt{Com}_{\scriptscriptstyle x}$, that involves a
secret value:
$r\stackrel{{\scriptstyle\scriptscriptstyle\$}}{{\leftarrow}}\\{0,1\\}^{\scriptscriptstyle\lambda}$.
In the end of the commit phase, the commitment
$\mathtt{Com}_{\scriptscriptstyle x}$ is sent to the receiver. In the open
phase, the sender sends the opening $\ddot{x}:=(x,r)$ to the receiver who
verifies its correctness: $\mathtt{Ver}(\mathtt{Com}_{\scriptscriptstyle
x},\ddot{x})\stackrel{{\scriptstyle\scriptscriptstyle?}}{{=}}1$ and accepts if
the output is $1$. A commitment scheme must satisfy two properties: (a)
hiding: it is infeasible for an adversary (i.e., the receiver) to learn any
information about the committed message $x$, until the commitment
$\mathtt{Com}_{\scriptscriptstyle x}$ is opened, and (b) binding: it is
infeasible for an adversary (i.e., the sender) to open a commitment
$\mathtt{Com}_{\scriptscriptstyle x}$ to different values
$\ddot{x}^{\prime}:=(x^{\prime},r^{\prime})$ than that was used in the commit
phase, i.e., infeasible to find $\ddot{x}^{\prime}$, s.t.
$\mathtt{Ver}(\mathtt{Com}_{\scriptscriptstyle
x},\ddot{x})=\mathtt{Ver}(\mathtt{Com}_{\scriptscriptstyle
x},\ddot{x}^{\prime})=1$, where $\ddot{x}\neq\ddot{x}^{\prime}$. There exist
efficient non-interactive commitment schemes both in (a) the standard model,
e.g., Pedersen scheme [53], and (b) the random oracle model using the well-
known hash-based scheme such that committing is :
$\mathtt{H}(x||r)=\mathtt{Com}_{\scriptscriptstyle x}$ and
$\mathtt{Ver}(\mathtt{Com}_{\scriptscriptstyle x},\ddot{x})$ requires
checking:
$\mathtt{H}(x||r)\stackrel{{\scriptstyle\scriptscriptstyle?}}{{=}}\mathtt{Com}_{\scriptscriptstyle
x}$, where
$\mathtt{H}:\\{0,1\\}^{\scriptscriptstyle*}\rightarrow\\{0,1\\}^{\scriptscriptstyle\lambda}$
is a collision resistant hash function; i.e., the probability to find $x$ and
$x^{\prime}$ such that $\mathtt{H}(x)=\mathtt{H}(x^{\prime})$ is negligible in
the security parameter $\lambda$.

####  C.1.3 Publicly Verifiable Non-interactive Zero-knowledge Proof

In a non-interactive zero-knowledge proof (NIZK), a prover $\mathcal{P}$,
given a witness $w$ for some statement $x$ in an NP language $L$, wants to
convince a verifier $\mathcal{V}$ of the validity of $x\in L$. The main
security property of the scheme is _Zero-knowledge_ ; meaning, a potentially
malicious verifier cannot learn anything beyond the validity of the statement.
The procedure is non-interactive, i.e., $\mathcal{P}$ generates a proof $\pi$
and provides $\mathcal{V}$ with $\pi$, who accepts (or rejects) verification.
A NIZK is publicly verifiable when any party by obtaining $\pi$ can verify the
validity of $x\in L$. Publicly verifiable NIZKs have been constructed under
trust assumptions such as the presence of a common reference string, or setup
assumptions such as the existence of a random oracle which is used in this
work. For a formal definition of NIZKs we refer the reader to [32].

####  C.1.4 Symmetric-key Encryption Scheme

A symmetric-key encryption scheme consists of three algorithms
$(\mathtt{SKE.keyGen},\mathtt{Enc},\mathtt{Dec})$, defined as follows. (1)
$\mathtt{SKE.keyGen}(1^{\scriptscriptstyle\lambda})\rightarrow k$ is a
probabilistic algorithm that outputs a symmetric key $k$. (2)
$\mathtt{Enc}(k,m)\rightarrow c$ takes as input $k$ and a message $m$ in some
message space and outputs a ciphertext $c$. (3) $\mathtt{Enc}(k,c)\rightarrow
m$ takes as input $k$ and a ciphertext $c$ and outputs a message $m$.

The correctness requirement is that for all messages $m$ in the message space,
it holds that

$\Pr\Big{[}\ \
\mathtt{Dec}(k,\mathtt{Enc}(k,m))=m:\mathtt{SKE.keyGen}(1^{\scriptscriptstyle\lambda})\rightarrow
k\Big{]}=1\;.$

The symmetric-key encryption scheme satisfies _indistinguishability against
chosen-plaintext attacks (IND-CPA)_ , if any probabilistic polynomial time
(PPT) adversary $\mathcal{A}$ has no more than
$\frac{1}{2}+\mathsf{negl}(\lambda)$ probability in winning the following
game: the challenger generates a symmetric key
$\mathtt{SKE.keyGen}(1^{\scriptscriptstyle\lambda})\rightarrow k$ . The
adversary $\mathcal{A}$ is given access to an encryption oracle
$\mathtt{Enc}(k,\cdot)$ and eventually sends to the challenger a pair of
messages $m_{0},m_{1}$ of equal length. In turn, the challenger chooses a
random bit $b$ and provides $\mathcal{A}$ with a ciphertext
$\mathtt{Enc}(k,m_{b})\rightarrow c_{b}$. Upon receiving $c_{b}$,
$\mathcal{A}$ continues to have access to $\mathtt{Enc}(k,\cdot)$ and wins if
its guess $b^{\prime}$ is equal to $b$.

####  C.1.5 Digital Signature Scheme

A digital signature is a scheme for verifying the authenticity of digital
messages. It involves three algorithms,
$(\mathtt{Sig.keyGen},\mathtt{Sig.sign},$ $\mathtt{Sig.ver})$, defined as
follows. (1)
$\mathtt{Sig.keyGen}(1^{\scriptscriptstyle\lambda})\rightarrow(sk,pk)$ is
probabilistic algorithm run by a signer that outputs a key pair $(sk,pk)$,
consisting of secret key $sk$, and public key $pk$. (2)
$\mathtt{Sig.sign}(sk,pk,u)\rightarrow sig$ is an algorithm run by the signer.
It takes as input key pair $(sk,pk)$ and a message $u$. It outputs a signature
$sig$. (3) $\mathtt{Sig.ver}(pk,u,sig)\rightarrow h\in\\{0,1\\}$ is an
algorithm run by a verifier. It takes as input public key $pk$, message $u$,
and signature $sig$. It checks the signature’s validity. If the verification
passes, then it outputs $1$; otherwise, it outputs $0$.

A digital signature scheme should meet two properties. (1) Correctness: for
every input $u$ it holds that:

$\begin{split}\Pr\Big{[}\mathtt{Sig.ver}&(pk,u,\mathtt{Sig.sign}(sk,pk,u))=1:\\\
&\mathtt{Sig.keyGen}(1^{\scriptscriptstyle\lambda})\rightarrow(sk,pk)\Big{]}=1\end{split}$

(2) Existential unforgeability under chosen message attacks (EUF-CMA): a
probabilistic polynomial time PPT adversary that obtains $pk$ and has access
to a signing oracle for messages of its choice, cannot create a valid pair
$(u^{\scriptscriptstyle*},sig^{\scriptscriptstyle*})$ for a new message
$u^{\scriptscriptstyle*}$, except with a negligible probability, $\sigma$. For
a formal definition of digital signatures, we refer readers to [40].

####  C.1.6 Merkle Tree

In the setting where a Merkle tree is used to remotely check a file, the file
is split into blocks and the tree is built on top of the file blocks. Usually,
for the sake of simplicity, it is assumed the number of blocks, $m$, is a
power of $2$. The height of the tree, constructed on $m$ blocks, is
$\log_{\scriptscriptstyle 2}(m)$. The Merkle tree scheme includes three
algorithms $(\mathtt{MT.genTree},\mathtt{MT.prove},\mathtt{MT.verify})$ as
follows:

  * $\bullet$

The algorithm that constructs a Merkle tree, $\mathtt{MT.genTree}$, is run by
$\mathcal{V}$. It takes file blocks, $u:=u_{\scriptscriptstyle
1},...,u_{\scriptscriptstyle m}$, as input. Then, it groups the blocks in
pairs. Next, a collision-resistant hash function, $\mathtt{H}(.)$, is used to
hash each pair. After that, the hash values are grouped in pairs and each pair
is further hashed, and this process is repeated until only a single hash
value, called “root”, remains. This yields a tree with the leaves
corresponding to the blocks of the input file and the root corresponding to
the last remaining hash value. $\mathcal{V}$ locally stores the root, and
sends the file and tree to $\mathcal{P}$.

  * $\bullet$

The proving algorithm, $\mathtt{MT.prove}$, is run by $\mathcal{P}$. It takes
a block index, $i$, and a tree as inputs. It outputs a vector proof, of
$\log_{\scriptscriptstyle 2}(m)$ elements. The proof asserts the membership of
$i$-th block in the tree, and consists of all the sibling nodes on a path from
the $i$-th block to the root of the Merkle tree (including $i$-th block). The
proof is given to $\mathcal{V}$.

  * $\bullet$

The verification algorithm, $\mathtt{MT.verify}$, is run by $\mathcal{V}$. It
takes as input $i$-th block, a proof and tree’s root. It checks if the $i$-th
block corresponds to the root. If the verification passes, it outputs $1$;
otherwise, it outputs $0$.

The Merkle tree-based scheme has two properties: _correctness_ and _security_.
Informally, the correctness requires that if both parties run the algorithms
correctly, then a proof is always accepted by $\mathcal{V}$. The security
requires that a computationally bounded malicious $\mathcal{P}$ cannot
convince $\mathcal{V}$ into accepting an incorrect proof, e.g., proof for non-
member block. The security relies on the assumption that it is computationally
infeasible to find the hash function’s collision.

###  C.2 Definition of PoR

A PoR scheme considers the case where an honest client wants to outsource the
storage of its file to a potentially malicious server, i.e., an active
adversary. It is a challenge-response interactive protocol, where the server
proves to the client that its file is intact and retrievable. Below, we
restate PoR’s formal definition initially proposed in [38, 56]. A PoR scheme
comprises of five algorithms:

  * $\bullet$

$\mathtt{PoR.keyGen}(1^{\scriptscriptstyle\lambda})\rightarrow k:=(sk,pk)$. A
probabilistic algorithm, run by a client, $\mathcal{C}$. It takes as input the
security parameter $1^{\scriptscriptstyle\lambda}$. It outputs private-public
verification key, $k:=(sk,pk)$.

  * $\bullet$

$\mathtt{PoR.setup}(1^{\scriptscriptstyle\lambda},u,k)\rightarrow(u^{\scriptscriptstyle*},\sigma,{pp})$.
A probabilistic algorithm, run by $\mathcal{C}$. It takes as input
$1^{\scriptscriptstyle\lambda}$, a file $u$, and key $k$. It encodes $u$
yielding $u^{\scriptscriptstyle*}$ and generates metadata, $\sigma$. It
outputs $u^{\scriptscriptstyle*}$, $\sigma$, and public parameters $pp$.

  * $\bullet$

$\mathtt{PoR.genQuery}(1^{\scriptscriptstyle\lambda},k,{pp})\rightarrow\bm{q}$.
A probabilistic algorithm, run by $\mathcal{C}$. It takes as input
$1^{\scriptscriptstyle\lambda}$, key $k$, and public parameters $pp$. It
outputs a query vector $\bm{q}$, possibly picked uniformly at random.

  * $\bullet$

$\mathtt{PoR.prove}(u^{\scriptscriptstyle*},\sigma,\bm{q},pk,{pp})\rightarrow\pi$.
It is run by the server, $\mathcal{S}$. It takes as input the encoded file
$u^{\scriptscriptstyle*}$, metadata $\sigma$, query $\bm{q}$, public key $pk$,
and public parameters $pp$. It outputs a proof, $\pi$.

  * $\bullet$

$\mathtt{PoR.verify}(\pi,\bm{q},k,{pp})\rightarrow d\in\\{0,1\\}$. It is run
by $\mathcal{C}$. It takes as input $\pi$, $\bm{q}$, $k$, and $pp$. It outputs
$0$ if it rejects the proof, or $1$ if it accepts the proof.

A PoR scheme has two properties: _correctness_ and _soundness_. Correctness
requires that the verification algorithm accepts proofs generated by an honest
verifier; formally, PoR requires that for any key $k$, any file
$u\in\\{0,1\\}^{\scriptscriptstyle*}$, and any pair
$(u^{\scriptscriptstyle*},\sigma)$ output by
$\mathtt{PoR.setup}(1^{\scriptscriptstyle\lambda},u,k)$, and any query
$\bm{q}$, the verifier accepts when it interacts with an honest prover.
Soundness requires that if a prover convinces the verifier (with high
probability) then the file is stored by the prover. This is formalized via the
notion of an extractor algorithm, that is able to extract the file in
interaction with the adversary using a polynomial number of rounds. Before we
define soundness, we restate the experiment, defined in [56], that takes place
between an environment $\mathcal{E}$ and adversary $\mathcal{A}$. In this
experiment, $\mathcal{A}$ plays the role of a corrupt party and $\mathcal{E}$
simulates an honest party’s role.

  1. 1.

$\mathcal{E}$ executes $\mathtt{PoR.keyGen}(1^{\scriptscriptstyle\lambda})$
algorithm and provides public key, $pk$, to $\mathcal{A}$.

  2. 2.

$\mathcal{A}$ can pick arbitrary file $u$, and uses it to make queries to
$\mathcal{E}$ who runs
$\mathtt{PoR.setup}(1^{\scriptscriptstyle\lambda},u,k)\rightarrow(u^{\scriptscriptstyle*},\sigma,{pp})$
and returns the output to $\mathcal{A}$. Also, upon receiving the output of
$\mathtt{PoR.setup}(1^{\scriptscriptstyle\lambda},u,k)$, $\mathcal{A}$ can ask
$\mathcal{E}$ to run $\mathtt{PoR.genQuery}(1^{\scriptscriptstyle\lambda}$
$,k,{pp})\rightarrow\bm{q}$ and give the output to it. $\mathcal{A}$ can
locally run $\mathtt{PoR.prove}(u^{\scriptscriptstyle*},\sigma,\bm{q},$
$pk,{pp})\rightarrow\pi$ to get its outputs as well.

  3. 3.

$\mathcal{A}$ can request from $\mathcal{E}$ the execution of
$\mathtt{PoR.verify}(\pi,\bm{q},k,$ ${pp})$ for any $u$ used to query
$\mathtt{PoR.setup}(\cdot)$. Accordingly, $\mathcal{E}$ informs $\mathcal{A}$
about the verification output. The adversary can send to $\mathcal{E}$ a
polynomial number of queries. Finally, $\mathcal{A}$ outputs metadata $\sigma$
returned from a setup query and the description of a prover,
$\mathcal{\hat{A}}$, for any file it has already chosen above.

It is said that a cheating prover, $\mathcal{\hat{A}}_{\epsilon}$, is
_$\epsilon$ -admissible_ if it convincingly answers $\epsilon$ fraction of
verification challenges (for a certain file). Informally, a PoR scheme
supports extractability, if there is an extractor algorithm
$\mathtt{Ext}(k,\sigma,\mathcal{\hat{A}}_{\epsilon})$, that takes as input the
key $k$, metadata $\sigma$, and the description of the machine implementing
the prover’s role $\mathcal{\hat{A}}_{\epsilon}$ and outputs the file, $u$.
The extractor has the ability to reset the adversary to the beginning of the
challenge phase and repeat this step polynomially many times for the purpose
of extraction, i.e., the extractor can rewind $\mathcal{\hat{A}}_{\epsilon}$.

######  Definition 8 ($\epsilon$-soundness).

A PoR scheme is $\epsilon$-sound if there exists an extraction algorithm
$\mathtt{Ext}(\cdot)$ such that, for every adversary $\mathcal{A}$ who plays
experiment $\mathsf{Exp}^{\mathcal{\scriptscriptstyle
A}}_{\scriptscriptstyle\mathsf{PoR}}$ and outputs an $\epsilon$-admissible
cheating prover $\mathcal{\hat{A}}_{\epsilon}$ for a file $u$, the extraction
algorithm recovers $u$ from $\mathcal{\hat{A}}_{\epsilon}$, given honest
party’s private key, public parameters, metadata and the description of
$\mathcal{\hat{A}}_{\epsilon}$, except with $\mathsf{negl}(\lambda)$
probability. Formally:

$\Pr\left[{\small{\begin{array}[]{l}\mathtt{PoR.keyGen}(1^{\scriptscriptstyle\lambda})\rightarrow
k:=(sk,pk)\\\ \mathcal{A}(1^{\lambda},pk)\rightarrow u\\\
\mathtt{PoR.setup}(1^{\lambda},u,k)\rightarrow(u^{\scriptscriptstyle*},\sigma,{pp})\\\
\mathcal{A}(u^{\scriptscriptstyle*},\sigma,{pp})\rightarrow\text{state}\\\
\mathtt{PoR.genQuery}(1^{\lambda},k,{pp})\rightarrow\bm{q}\\\
\Big{(}\big{(}\mathcal{A}(\bm{q},\text{state})\rightarrow\pi)\rightleftharpoons(\mathtt{PoR.verify}(\pi,\\\
\bm{q},k,{pp})\big{)}\Big{)}\rightarrow\mathcal{\hat{A}}_{\epsilon}\\\
\hline\cr\mathtt{Ext}(k,{pp},\sigma,\mathcal{\hat{A}}_{\epsilon})\neq
u\end{array}}}\right]=\mathsf{negl}(\lambda)$

In contrast to the PoR definition in [38, 56] where
$\mathtt{PoR.genQuery}(\cdot)$ is implicit, in the above definition we have
explicitly defined
$\mathtt{PoR.genQuery}(\cdot)$, as it plays an important role in this paper.
Also, there are PoR protocols, e.g., in [50], that do not involve
$\mathtt{PoR.keyGen}(\cdot)$. Instead, a set of public parameters/keys (e.g.,
file size or a root of Merkle tree) are output by $\mathtt{PoR.setup}(\cdot)$.
To make the PoR definition generic to capture both cases, we have explicitly
included the public parameters $pp$ in the algorithms’ definitions too.

##  Appendix D Further Discussion on Proof Status Leakage

As we already highlighted, the leakage of proof status (which reveals whether
the server is suffering from hardware/software failure) might be problematic
in certain circumstances. In Section 5, we have described a case where such
leakage could benefit adversaries.

However, this is not the only case. An adversary may directly target business
and/or individual clients by mounting social engineering attacks on them. It
can exploit such leakage to increase the chance of success in its attack. A
survey conducted by Kaspersky lab suggests that 33% of attacks that affect
business clients of cloud servers are of type social engineering [42] which is
a high rate. Moreover, social engineering attacks on individuals are still
prevalent. In the UK, scammers have been impersonating the Post Office and
sending “extremely convincing” text messages to the citizens and asking them
to use the link provided in the message to schedule redelivery and pay for the
redelivery using the given online form. The attackers would steal victims’
payment details once they use the form and insert their card details. This
message may seem relevant and convincing to a certain percentage of recipients
as they are indeed waiting for parcel delivery. A survey conducted by a UK-
based consumer protection organisation suggests that 61% of surveyed people
had received such a text message [48].

The same scam can be simply adjusted to target users of the cloud servers
which are suffering a failure. Given real-time evidence of servers’ failure
(that is also known to the clients), an adversary can provide more convincing
evidence to their victims as a part of social engineering. This ultimately
increases the adversary’s chance of success. The adversary can target a large
set of people a subset of which is likely to be the cloud’s clients (akin to
the above parcel delivery scam), or it can target specific cloud clients by
using the techniques used to link the blockchain’s addresses to certain
parties [3, 11, 55].

##  Appendix E Verifiable Service (VS) Definition

At a high level, a verifiable service scheme is a two-party protocol in which
a client chooses a function, $F$, and provides (an encoding of) $F$, its input
$u$, and a query $\bm{q}$ to a server. The server is expected to evaluate $F$
on $u$ and $\bm{q}$ (and some public parameters) and respond with the output.
Then, the client verifies that the output is indeed the output of the function
computed on the provided input. In verifiable services, either the computation
(on the input) or both the computation and storage of the input are delegated
to the server. A verifiable service is defined as follows.

######  Definition 9 (VS Scheme).

A verifiable service scheme VS
$:=(\mathtt{VS.keyGen},\mathtt{VS.setup},\mathtt{VS.genQuery},$
$\mathtt{VS.prove},$ $\mathtt{VS.verify})$ with function $F$, metadata
generator function $M$, and query generator function $Q$ consists of five
algorithms defined as follows.

  * $\bullet$

$\mathtt{VS.keyGen}(1^{\lambda})\rightarrow k:=(sk,pk)$. A probabilistic
algorithm run by the client. It takes as input the security parameter
$1^{\lambda}$ and outputs a secret/public verification key pair $k$. The
server is given $pk$.

  * $\bullet$

$\mathtt{VS.setup}(1^{\lambda},u,k)\rightarrow(u^{\scriptscriptstyle*},\sigma,{pp})$.
It is run by the client. It takes as input the security parameter
$1^{\lambda}$, the service input $u$, and key pair $k$. If an encoding is
needed, then it encodes $u$, that results in $u^{\scriptscriptstyle*}$;
otherwise, $u^{*}=u$. It outputs encoded input $u^{\scriptscriptstyle*}$,
metadata $\sigma=M(u^{\scriptscriptstyle*},k,{pp})$, and (possibly input
dependent) public parameters $pp$. Right after that, the server is given
$u^{\scriptscriptstyle*}$, $\sigma$, and $pp$.

  * $\bullet$

$\mathtt{VS.genQuery}(1^{\lambda},\text{aux},k,{pp})\rightarrow\bm{q}$. A
probabilistic algorithm run by the client. It takes as input the security
parameter $1^{\lambda}$, auxiliary information aux, the key pair $k$, and
public parameters $pp$. It outputs a query vector
$\bm{q}=Q(\text{aux},k,{pp})$. Depending on service types, $\bm{q}$ may be
empty or contain only random strings. The output is given to the server.

  * $\bullet$

$\mathtt{VS.prove}(u^{\scriptscriptstyle*},\sigma,\bm{q},pk,{pp})\rightarrow\bm{\pi}$.
It is run by the server. It takes as input the service encoded input
$u^{\scriptscriptstyle*}$, metadata $\sigma$, queries $\bm{q}$, public key
$pk$, and public parameters $pp$. It outputs a proof,
$\bm{\pi}=[F(u^{\scriptscriptstyle*},\bm{q},{pp}),\delta]$, containing the
function evaluation for service input $u$, public parameters $pp$, and query
$\bm{q}$, i.e., $h=F(u^{\scriptscriptstyle*},\bm{q},{pp})$, and a proof
$\delta$ asserting the evaluation is performed correctly, where generating
$\delta$ may involve $\sigma$. The output is given to the client.

  * $\bullet$

$\mathtt{VS.verify}(\bm{\pi},\bm{q},k,{pp})\rightarrow d\in\\{0,1\\}$. It is
run by the client. It takes as input the proof $\bm{\pi}$, query vector
$\bm{q}$, key $k$, and public parameters $pp$. In the case where
$\mathtt{VS.verify}(\cdot)$ is publicly verifiable then $k:=(\bot,pk)$, and
when it is privately verifiable $k:=(sk,pk)$. The algorithm outputs $d=1$, if
the proof is accepted; otherwise, it outputs $d=0$.

A verifiable service scheme has two main properties, _correctness_ and
_soundness_. Correctness requires that the verification algorithm always
accepts a proof generated by an honest prover. It is formally stated below.

######  Definition 10 (VS Correctness).

A verifiable service scheme VS with functions $F,M,Q$ is correct for an
auxiliary information $aux$, if for any service input $u$ it holds that:

$\Pr\left[{\small{\begin{array}[]{l}\mathtt{VS.keyGen}(1^{\lambda})\rightarrow
k:=(sk,pk)\\\
\mathtt{VS.setup}(1^{\lambda},u,k)\rightarrow(u^{\scriptscriptstyle*},\sigma,{pp})\\\
\mathtt{VS.genQuery}(1^{\lambda},\text{aux},k,{pp})\rightarrow\bm{q}\\\
\mathtt{VS.prove}(u^{\scriptscriptstyle*},\sigma,\bm{q},pk,{pp})\rightarrow\bm{\pi}\\\
\hline\cr\mathtt{VS.verify}(\bm{\pi},\bm{q},k,{pp})\rightarrow 1.\\\
\end{array}}}\right]=1$

Intuitively, a verifiable service is sound if a malicious server cannot
convince the verification algorithm to accept an incorrect output of $F$
except with negligible probability. Soundness is formally stated as follows.

######  Definition 11 (VS Soundness).

A verifiable service VS with functions $F,M,Q$ is sound for an auxiliary
information aux, if for any probabilistic polynomial time adversary
$\mathcal{A}$, it holds that:

$\Pr\left[{\small{\begin{array}[]{l}\mathtt{VS.keyGen}(1^{\scriptscriptstyle\lambda})\rightarrow
k:=(sk,pk)\\\ \mathcal{A}(1^{\lambda},pk,F,M,Q)\rightarrow u\\\
\mathtt{VS.setup}(1^{\lambda},u,k)\rightarrow(u^{\scriptscriptstyle*},\sigma,{pp})\\\
\mathtt{VS.genQuery}(1^{\lambda},\text{aux},k,{pp})\rightarrow\bm{q}\\\
\mathcal{A}(\bm{q},u^{\scriptscriptstyle*},\sigma,{pp})\rightarrow\bm{\pi}=[h,\delta]\\\
\mathtt{VS.verify}(\bm{\pi},\bm{q},k,{pp})\rightarrow d\\\ \hline\cr
F(u^{\scriptscriptstyle*},\bm{q},{pp})\neq h\wedge
d=1\end{array}}}\right]=\mathsf{negl}(\lambda)$

The above generic definition captures the core requirements of a wide range of
verifiable services such as verifiable outsourced storage, i.e., Proofs of
Retrievability [38, 56] or Provable Data Possession [9, 57], verifiable
computation [29, 43], verifiable searchable encryption [49, 44], and
verifiable information retrieval [62, 60], to name a few. Other additional
security properties (e.g., privacy) mandated by certain services can be added
to the above definition. Alternatively, the definition can be upgraded to
capture the additional requirements. The verifiable service with identifiable
abort (VSID) and recurring contingent service payment (RC-S-P) definitions
presented in this paper are two examples.

######  Remark 1.

It is not hard to see that the original PoR definition (presented in Section
3.3) is a VS’s special case. In particular, PoR’s $\epsilon$-soundness
captures VS’s soundness; in $\epsilon$-soundness, the extractor algorithm
interacts (many times) with the cheating prover which must not be able to
persuade the extractor to accept an invalid proof with a high probability and
should provide accepting proofs for non-negligible $\epsilon$ fraction of
verification challenges. The former property is exactly what VS soundness
states.

##  Appendix F Verifiable Service with Identifiable Abort (VSID)

A protocol that realises only VS’s definition (cf. Appendix E) would be merely
secure against a malicious server and assumes the client is honest. Although
this assumption would suffice in certain settings and has been used before
(e.g., in [57, 49]), it is rather strong and not suitable in the real world,
especially when there are monetary incentives (e.g., service payment) that
encourage a client to misbehave. Therefore, in the following we enhance the VS
notion to allow (a) either party to be malicious and (b) a trusted third
party, _arbiter_ , to identify a corrupt party. We call an upgraded verifiable
service scheme with these features _verifiable service with identifiable
abort_ (VSID), inspired by the notion of secure multi-party computation with
identifiable abort [37].

###  F.1 VSID Definition

The definition of a VSID scheme is provided below.

######  Definition 12 (VSID Scheme).

A verifiable service with identifiable abort
VSID $:=(\mathtt{VSID.keyGen},$ $\mathtt{VSID.setup},$ $\mathtt{VSID.serve},$
$\mathtt{VSID.genQuery}$,
$\mathtt{VSID.checkQuery},$ $\mathtt{VSID.prove},$
$\mathtt{VSID.verify},\mathtt{VSID.identify})$
with function $F$, metadata generator function $M$, and query generator
function $Q$ involves four entities; namely, client, server, arbiter, and
bulletin board. It consists of eight algorithms defined below.

  * $\bullet$

$\mathtt{VSID.keyGen}(1^{\lambda})\rightarrow k:=(sk,pk)$. A probabilistic
algorithm run by the client $\mathcal{C}$. It takes as input the security
parameter $1^{\scriptscriptstyle\lambda}$ and outputs a secret/public
verification key pair $k$. It sends $pk$ to the bulletin board.

  * $\bullet$

$\mathtt{VSID.setup}(1^{\lambda},u,k)\rightarrow(u^{\scriptscriptstyle*},{pp},e)$.
It is run by the client. It takes as input the security parameter
$1^{\scriptscriptstyle\lambda}$, the service input $u$, and the key pair $k$.
If an encoding is needed, then it encodes $u$, that results
$u^{\scriptscriptstyle*}$; otherwise, $u^{\scriptscriptstyle*}=u$. It outputs
$u^{\scriptscriptstyle*}$, (possibly file dependent) public parameters $pp$
and $e:=(\sigma,w_{\sigma})$, where $\sigma=M(u^{\scriptscriptstyle*},k,{pp})$
is metadata and $w_{\sigma}$ is a proof asserting the metadata is well-
structured. It sends the output (i.e., $u^{\scriptscriptstyle*},{pp},e$) to
the bulletin board.

  * $\bullet$

$\mathtt{VSID.serve}(u^{\scriptscriptstyle*},e,pk,{pp})\rightarrow
a\in\\{0,1\\}$. It is run by the server $\mathcal{S}$. It takes as input the
encoded service input $u^{\scriptscriptstyle*}$, the pair
$e:=(\sigma,w_{\sigma})$, public key $pk$, and public parameters $pp$. It
outputs $a=1$, if the proof $w_{\sigma}$ is accepted, i.e., if the metadata is
well-formed. Otherwise, it outputs $a=0$. The output is sent to the bulletin
board.

  * $\bullet$

$\mathtt{VSID.genQuery}(1^{\lambda},\text{aux},k,{pp})\rightarrow
c:=(\bm{q},\bm{w}_{\scriptscriptstyle q})$. A probabilistic algorithm run by
the client. It takes as input the security parameter $1^{\lambda}$, auxiliary
information aux, the key pair $k$, and public parameters $pp$. It outputs a
pair $c$ containing a query vector, $\bm{q}=Q(\text{aux},k,{pp})$, and proofs,
$\bm{w}_{\scriptscriptstyle q}$, proving the queries are well-structured.
Depending on service types, $c$ might be empty or contain only random strings.
It sends $c$ to the bulletin board.

  * $\bullet$

$\mathtt{VSID.checkQuery}(c,pk,{pp})\rightarrow b\in\\{0,1\\}$. It is run by
the server. It takes as input a pair $c:=(\bm{q},\bm{w}_{\scriptscriptstyle
q})$ including queries and their proofs, as well as public key $pk$, and
public parameters $pp$. It outputs $b=1$ if the proofs
$\bm{w}_{\scriptscriptstyle\sigma}$ are accepted, i.e., the queries are well-
structured. Otherwise, it outputs $b=0$.

  * $\bullet$

$\mathtt{VSID.prove}(u^{\scriptscriptstyle*},\sigma,c,pk,{pp})\rightarrow\bm{\pi}$.
It is run by the server. It takes as input the encoded service input
$u^{\scriptscriptstyle*}$, metadata $\sigma$, a pair
$c:=(\bm{q},\bm{w}_{\scriptscriptstyle q})$, public key $pk$, and public
parameters $pp$. It outputs a proof,
$\bm{\pi}=[F(u^{\scriptscriptstyle*},\bm{q},{pp}),\delta)]$ containing the
function evaluation, i.e., $h=F(u^{\scriptscriptstyle*},\bm{q},{pp})$, and a
proof $\delta$ asserting the evaluation is performed correctly, where
computing $h$ may involve $pk$ and computing $\delta$ may involve $\sigma$. It
sends $\bm{\pi}$ to the board.

  * $\bullet$

$\mathtt{VSID.verify}(\bm{\pi},\bm{q},k,{pp})\rightarrow d\in\\{0,1\\}$. It is
run by the client. It takes as input the proof $\bm{\pi}$, queries $\bm{q}$,
key pair $k$, and public parameters pp. If the proof is accepted, it outputs
$d=1$; otherwise, it outputs $d=0$.

  * $\bullet$

$\mathtt{VSID.identify}(\bm{\pi},c,k,e,u^{\scriptscriptstyle*},{pp})\rightarrow
I\in\\{\mathcal{C},\mathcal{S},\bot\\}$. It is run by a third party arbiter.
It takes as input the proof $\bm{\pi}$, query pair
$c:=(\bm{q},\bm{w}_{\scriptscriptstyle q})$, key pair $k$, metadata pair
$e:=(\sigma,w_{\sigma})$, $u^{\scriptscriptstyle*}$, and public parameters pp.
If proof $w_{\scriptscriptstyle\sigma}$ or $\bm{w}_{\scriptscriptstyle q}$ is
rejected, then it outputs $I=\mathcal{C}$; otherwise, if proof $\bm{\pi}$ is
rejected it outputs $I=\mathcal{S}$. Otherwise, if
$w_{\scriptscriptstyle\sigma},\bm{w}_{\scriptscriptstyle q}$, and $\bm{\pi}$
are accepted, it outputs $I=\bot$.

A VSID scheme has four main properties; namely, it is (a) correct, (b) sound,
(c) inputs of clients are well-formed, and (d) a corrupt party can be
identified by an arbiter, i.e., detectable abort. In the following, we
formally define each of them. Correctness requires that the verification
algorithm always accepts a proof generated by an honest prover and both
parties are identified as honest. It is formally stated as follows.

######  Definition 13 (VSID Correctness).

A verifiable service with identifiable abort scheme with functions $F,M,Q$ is
correct for an auxiliary information aux, if for any service input $u$ it
holds that:

$\Pr\left[{\small{\begin{array}[]{l}\mathtt{VSID.keyGen}(1^{\lambda})\rightarrow
k:=(sk,pk)\\\
\mathtt{VSID.setup}(1^{\lambda},u,k)\rightarrow(u^{\scriptscriptstyle*},{pp},e)\\\
\mathtt{VSID.serve}(u^{\scriptscriptstyle*},e,pk,{pp})\rightarrow a\\\
\mathtt{VSID.genQuery}(1^{\lambda},\text{aux},k,{pp})\rightarrow c\\\
\mathtt{VSID.checkQuery}(c,pk,{pp})\rightarrow b\\\
\mathtt{VSID.prove}(u^{\scriptscriptstyle*},\sigma,c,pk,{pp})\rightarrow\bm{\pi}\\\
\mathtt{VSID.verify}(\bm{\pi},\bm{q},k,{pp})\rightarrow d\\\
\hline\cr\mathtt{VSID.identify}(\bm{\pi},c,k,e,u^{\scriptscriptstyle*},{pp})\rightarrow
I=\bot\ \ \wedge\\\ a=1\ \ \wedge\ b=1\ \ \wedge\ d=1\end{array}}}\right]=1$

Intuitively, a VSID is sound if a malicious server cannot convince the client
to accept an incorrect output of $F$ except with negligible probability. It is
formally stated as follows.

######  Definition 14 (VSID Soundness).

A VSID with functions $F,M,Q$ is sound for an auxiliary information aux, if
for any probabilistic polynomial time adversary $\mathcal{A}$, it holds that
the following probability is $\mathsf{negl}(\lambda)$:

$\Pr\left[{\small{\begin{array}[]{l}\mathtt{VSID.keyGen}(1^{\lambda})\rightarrow
k:=(sk,pk)\\\ \mathcal{A}(1^{\lambda},pk,F,M,Q)\rightarrow u\\\
\mathtt{VSID.setup}(1^{\lambda},u,k)\rightarrow(u^{\scriptscriptstyle*},{pp},e)\\\
\mathtt{VSID.genQuery}(1^{\lambda},\text{aux},k,{pp})\rightarrow
c:=(\bm{q},\bm{w}_{q})\\\
\mathcal{A}(c,e,u^{\scriptscriptstyle*},{pp})\rightarrow\bm{\pi}=[h,\delta]\\\
\mathtt{VSID.verify}(\bm{\pi},\bm{q},k,{pp})\rightarrow d\\\ \hline\cr
F(u^{\scriptscriptstyle*},\bm{q},{pp})\neq h\wedge d=1\end{array}}}\right]$

A VSID has well-formed inputs, if a malicious client cannot persuade a server
to serve it on ill-structured inputs (i.e., to accept incorrect outputs of $M$
or $Q$). Below, we state the property formally.

######  Definition 15 (VSID Inputs Well-formedness).

A VSID with functions $F,M,Q$ has well-formed inputs for an auxiliary
information aux, if for any probabilistic polynomial time adversary
$\mathcal{A}$, it holds that the following probability is
$\mathsf{negl}(\lambda)$:

$\Pr\left[{\small{\begin{array}[]{l}\mathcal{A}(1^{\lambda},F,M,Q)\rightarrow\Big{(}u^{\scriptscriptstyle*},k:=(sk,pk),\\\
e:=(\sigma,w_{\sigma}),{pp}\Big{)}\\\
\mathtt{VSID.serve}(u^{\scriptscriptstyle*},e,pk,{pp})\rightarrow a\\\
\mathcal{A}(1^{\lambda},\text{aux},k,{pp})\rightarrow
c:=(\bm{q},\bm{w}_{\scriptscriptstyle q})\\\
\mathtt{VSID.checkQuery}(c,pk,{pp})\rightarrow b\\\
\hline\cr(M(u^{\scriptscriptstyle*},k,{pp})\neq\sigma\wedge a=1)\vee\\\
(Q(\text{aux},k,{pp})\neq\bm{q}\wedge b=1)\\\ \end{array}}}\right]$

The above property ensures an honest server can detect a malicious client if
the client provides ill-structured inputs. It is further required that a
malicious party be identified by an honest third party, arbiter. This ensures
that in the case of dispute (or false accusation) a malicious party can be
pinpointed. A VSID supports detectable abort if a corrupt party can escape
from being identified, by the arbiter, with only negligible probability.
Formally:

######  Definition 16 (VSID Detectable Abort).

A VSID with functions $F,M,Q$ supports detectable abort for an auxiliary
information aux, if the following hold:

  1. 1.

For any PPT adversary $\mathcal{A}_{\scriptscriptstyle 1}$, the following
probability is $\mathsf{negl}(\lambda)$:

$\Pr\left[{\small{\begin{array}[]{l}\mathtt{VSID.keyGen}(1^{\scriptscriptstyle\lambda})\rightarrow
k:=(sk,pk)\\\ \mathcal{A}_{\scriptscriptstyle
1}(1^{\lambda},pk,F,M,Q)\rightarrow u\\\
\mathtt{VSID.setup}(1^{\lambda},u,k)\rightarrow(u^{\scriptscriptstyle*},pp,e)\\\
\mathtt{VSID.genQuery}(1^{\lambda},\text{aux},k,{pp})\rightarrow
c:=(\bm{q},\bm{w}_{q})\\\ \mathcal{A}_{\scriptscriptstyle
1}(c,e,u^{\scriptscriptstyle*},{pp})\rightarrow\bm{\pi}=[h,\delta]\\\
\mathtt{VSID.verify}(\bm{\pi},\bm{q},k,{pp})\rightarrow d\\\
\mathtt{VSID.identify}(\bm{\pi},c,k,e,u^{\scriptscriptstyle*},{pp})\rightarrow
I\\\ \hline\cr d=0\wedge I\neq\mathcal{S}\\\ \end{array}}}\right]$

  2. 2.

For any PPT adversary $\mathcal{A}_{\scriptscriptstyle 2}$, the following
probability is $\mathsf{negl}(\lambda)$:

$\Pr\left[{\small{\begin{array}[]{l}\mathcal{A}_{\scriptscriptstyle
2}(1^{\lambda},F,M,Q)\rightarrow\Big{(}u^{\scriptscriptstyle*},k:=(sk,pk),\\\
e:=(\sigma,w_{\sigma}),{pp}\Big{)}\\\
\mathtt{VSID.serve}(u^{\scriptscriptstyle*},e,pk,{pp})\rightarrow a\\\
\mathcal{A}_{\scriptscriptstyle 2}(\text{aux},k)\rightarrow
c:=(\bm{q},\bm{w}_{\scriptscriptstyle q})\\\
\mathtt{VSID.checkQuery}(c,pk,{pp})\rightarrow b\\\
\mathtt{VSID.prove}(u^{\scriptscriptstyle*},\sigma,c,pk,{pp})\rightarrow\bm{\pi}\\\
\mathtt{VSID.identify}(\bm{\pi},c,k,e,u^{\scriptscriptstyle*},{pp})\rightarrow
I\\\ \hline\cr(a=0\vee b=0)\wedge I\neq\mathcal{C}\\\ \end{array}}}\right]$

####  F.1.1 Lighter VSID Scheme
($\text{VSID}_{\scriptscriptstyle\text{light}}$)

In the VSID definition, algorithm $\mathtt{VSID.identify}(\cdot)$ allows an
arbiter to identify a misbehaving client even in the setup phase.
Nevertheless, it is often sufficient to let the arbiter pinpoint a corrupt
party _after_ the client and server agree to deal with each other, i.e., after
the setup when the server runs $\mathtt{VSID.serve}(\cdot)$ and outputs $1$. A
VSID protocol that meets the latter (lighter) requirements, denoted by
$\text{VSID}_{\scriptscriptstyle\text{light}}$, would impose lower costs
especially when $u$ and elements of $e$ are of large size. Because the arbiter
is not required to identify a misbehaving client in setup; therefore, it does
not need to have access to the entire file $u^{\scriptscriptstyle*}$ and
metadata $e$. This means (a) the server or client does not need to send
$u^{\scriptscriptstyle*}$ and $e$ to the arbiter that leads to lower
communication cost, and (b) the arbiter skips checking the correctness of
metadata in $\mathtt{VSID.identify}(\cdot)$, which ultimately saves it
computation cost too. In $\text{VSID}_{\scriptscriptstyle\text{light}}$,
algorithm $\mathtt{VSID.identify}(\cdot)$ needs to take only
$(\pi,c,k,e^{\prime},{pp})$ as input, where $e^{\prime}\subset e$. So, this
requires two changes to the VSID definition, (a) the arbiter algorithm would
be $\mathtt{VSID.identify}(\pi,c,k,e^{\prime},{pp})\rightarrow I$, and (b) in
case 2, in Definition 16 we would have $b=0\wedge I\neq\mathcal{C}$, so event
$a=0$ is excluded. In this paper, any time we refer to
$\text{VSID}_{\scriptscriptstyle\text{light}}$, we assume the above minor
adjustments are applied to the VSID definition.

###  F.2 VSID Protocol

In this section, we present the VSID protocol. We show how it can be built
upon a protocol that satisfies the VS definition. As stated previously, a VS
scheme inherently protects an honest client from a malicious server.
Therefore, at a high-level, VSID needs to have two added features; namely, it
protects an honest server from a malicious client and allows an arbiter to
detect a corrupt party. VSID can be built upon VS using the following standard
techniques; Briefly, (a) all parties sign their outgoing messages, (b) they
post the signed messages on a bulletin board, and (c) the client, using a
publicly verifiable NIZK scheme, proves to the server that its inputs have
been correctly constructed. In particular, like VS, the client first generates
its secret and public parameters. Then, in the setup, it processes its input,
$u$, to generate encoded input and metadata using the metadata generation
function, $M$. Also, the client utilizes a publicly verifiable NIZK scheme to
prove to the server that the metadata has been constructed correctly. The
client posts the encoded input, metadata and the proofs along with their
signatures to a bulletin board. Next, the server verifies the signatures and
proofs. It agrees to serve the client, if they are accepted. Like VS, when the
client wants the server to run function $F$ on its input, it uses function $Q$
to generate a query. However, it uses the zero-knowledge scheme to prove to
the server that the query has been constructed correctly. The client posts the
query, proofs, and their signatures to the board. After that, the server
verifies the signatures and proofs. The server-side proves and client-side
verifies algorithms remain unchanged with a difference that the server posts
its proofs (i.e., the output of the prove algorithm) and their signatures to
the board and the client first verifies the signatures before checking the
proofs. In the case of any dispute/abort, either party invokes the arbiter
which, given the signed posted messages, checks the signatures and proofs in
turn to identify a corrupt party. Below, we present the VSID protocol in which
we assume all parties sign their outgoing messages and their counter-party
first verifies the signature on the messages, before they feed them to their
local algorithms.

  1. 1.

Key Generation. $\mathtt{VSID.keyGen}(1^{\lambda})$

    1. (a)

Calls $\mathtt{VS.keyGen}(1^{\lambda})$ to generate a pair of secret and
public keys, $k:(sk,pk)$.

    2. (b)

Commits to the secret key and appends the commitment:
$\mathtt{Com}_{\scriptscriptstyle sk}$ to $pk$.

    3. (c)

Posts $pk$ to a bulletin board.

  2. 2.

Client-side Setup. $\mathtt{VSID.setup}(1^{\lambda},u,k)$

    1. (a)

Calls
$\mathtt{VS.setup}(1^{\lambda},u,k)\rightarrow(\sigma,u^{\scriptscriptstyle*})$,
to generate a metadata: $\sigma=M(u^{\scriptscriptstyle*},k,{pp})$, encoded
file service input and (input dependent) parameters $pp$.

    2. (b)

Generates non-interactive publicly verifiable zero-knowledge proofs asserting
$\sigma$ has been generated correctly, i.e., $\sigma$ is the output of $M$
that is evaluated on $u^{\scriptscriptstyle*}$, $pk$, $sk$, and $pp$ without
revealing $sk$. Let $w_{\scriptscriptstyle\sigma}$ contain the proofs.

    3. (c)

Posts $e:=(\sigma,w_{\scriptscriptstyle\sigma})$, $pp$, and
$u^{\scriptscriptstyle*}$ to the bulletin board.

  3. 3.

Server-side Setup. $\mathtt{VSID.serve}(u^{\scriptscriptstyle*},e,pk,{pp})$

Ensures the metadata $\sigma$ has been constructed correctly, by verifying the
proofs in $w_{\sigma}$ (where $\sigma,w_{\scriptscriptstyle\sigma}\in e$). If
the proofs are accepted, then it outputs $a=1$ and proceeds to the next step;
otherwise, it outputs $a=0$ and halts.

  4. 4.

Client-side Query Generation.
$\mathtt{VSID.genQuery}(1^{\lambda},\text{aux},k,$ ${pp})$.

    1. (a)

Calls $\mathtt{VS.genQuery}(1^{\lambda},\text{aux},k,{pp})\rightarrow\bm{q}$,
to generate a query vector, $\bm{q}=Q(\text{aux},k,{pp})$. If aux is a private
input, then it also commits to it, that yields
$\mathtt{Com}_{\scriptscriptstyle\text{aux}}$

    2. (b)

Generates non-interactive publicly verifiable zero-knowledge proofs proving
$\bm{q}$ has been generated correctly, i.e., $\bm{q}$ is the output of $Q$
which is evaluated on aux, $pk$, $sk$, and $pp$ without revealing $sk$ (and
aux, if it is a private input). Let $\bm{w}_{\scriptscriptstyle q}$ contain
the proofs and aux (or $\mathtt{Com}_{\scriptscriptstyle\text{aux}}$ if aux is
a private input).

    3. (c)

Posts $c:(\bm{q},\bm{w}_{\scriptscriptstyle q})$ to the board.

  5. 5.

Server-side Query Verification.
$\mathtt{VSID.checkQuery}(c,pk,$ ${pp})$

Checks if the query: $\bm{q}\in c$ has been constructed correctly by verifying
the proofs $\bm{w}_{\scriptscriptstyle q}\in c$. If the check passes, then it
outputs $b=1$; otherwise, it outputs $b=0$.

  6. 6.

Server-side Service Proof Generation.
$\mathtt{VSID.prove}(u^{\scriptscriptstyle*},\sigma,$ $c,$ $pk,{pp})$ This
phase starts only if the query was accepted, i.e., $b=1$ .

    1. (a)

Calls $\mathtt{VS.prove}(u^{\scriptscriptstyle*},$
$\sigma,\bm{q},pk,{pp})\rightarrow\bm{\pi}$, to generate
$\bm{\pi}=[F(u^{\scriptscriptstyle*},$ $\bm{q},{pp}),\delta]$. Recall that
$\bm{q}\in c$.

    2. (b)

Posts $\bm{\pi}$ to the board.

  7. 7.

Client-side Proof Verification.
$\mathtt{VSID.verify}(\bm{\pi},\bm{q},k,{pp})$

Calls $\mathtt{VS.verify}(\bm{\pi},\bm{q},k,{pp})\rightarrow d$, to verify
proof $\bm{\pi}$. It accepts the proof if $d=1$; otherwise, it rejects it.

  8. 8.

Arbiter-side Identification.
$\mathtt{VSID.identify}(\bm{\pi},c,k,e,u^{\scriptscriptstyle*},{pp})$

    1. (a)

Calls $\mathtt{VSID.serve}(u^{\scriptscriptstyle*},e,pk,{pp})\rightarrow a$.
If $a=1$, then it proceeds to the next step. Otherwise, it outputs
$I=\mathcal{C}$ and halts.

    2. (b)

Calls $\mathtt{VSID.checkQuery}(c,pk,{pp})\rightarrow b$. If $b=1$, then it
proceeds to the next step. Otherwise, it outputs $I=\mathcal{C}$ and halts.

    3. (c)

If $\bm{\pi}$ is privately verifiable, then the arbiter first checks if $sk\in
k$ (provided by the client along with other opening information) matches
$\mathtt{Com}_{\scriptscriptstyle sk}\in pk$. If they do not match, then the
arbiter outputs $I=\mathcal{C}$. Otherwise, it calls
$\mathtt{VS.verify}(\bm{\pi},\bm{q},k,{pp})\rightarrow d$. If $d=1$, then it
outputs $I=\bot$; otherwise, it outputs $I=\mathcal{S}$.

######  Theorem 2.

The VSID protocol with functions $F,M,Q$ satisfies the correctness, soundness,
inputs well-formedness, and detectable abort properties for auxiliary
information aux, (cf. Definitions 13-16), if the underlying VS protocol with
functions $F,M,Q$ is correct and sound for aux and the underlying commitment,
publicly verifiable non-interactive zero-knowledge, and signature schemes are
correct/complete and secure.

###### Proof (sketch).

Correctness is implied by the correctness/completeness of the underlying
primitives. The soundness of VSID stems from the hiding property of the
commitment, zero-knowledge property of the publicly verifiable NIZK proofs,
and soundness of the verifiable service (VS) schemes. In particular, in VSID,
the verifier (i.e., in this case, the client) makes block-box calls to the
algorithms of VS to ensure soundness. However, the prover (i.e., the server)
is given additional messages, i.e., $\mathtt{Com}_{\scriptscriptstyle sk}$,
$\mathtt{Com}_{\scriptscriptstyle\text{aux}}$, $w_{\scriptscriptstyle\sigma}$
and $w_{\scriptscriptstyle q}$. The hiding property of the commitment scheme
and zero-knowledge property of the zero-knowledge system ensure, given the
messages, the prover learns nothing about the verification key and auxiliary
information, except with negligible probability. Moreover, the soundness of VS
scheme ensures a corrupt prover cannot convince an honest verifier, except
with a negligible probability. Inputs well-formedness property boils down to
the security of the commitment and publicly verifiable NIZK proofs schemes
that are used in steps 1, 2 and 4 in VSID protocol. Specifically, the binding
property of the commitment and the soundness of the publicly verifiable NIZK
proofs schemes ensure that a corrupt prover (i.e., in this case the client)
cannot convince a verifier (i.e., the server) to accept metadata proofs,
$w_{\scriptscriptstyle\sigma}$ and $\mathtt{Com}_{\scriptscriptstyle sk}\in
pk$, while $M(u^{\scriptscriptstyle*},k,{pp})\neq\sigma$ or to accept query
proofs, $\bm{w}_{\scriptscriptstyle q}$ and
$\mathtt{Com}_{\scriptscriptstyle\text{aux}}$, while
$Q(\text{aux},k,{pp})\neq\bm{q}$, except with negligible probability.

Moreover, the detectable abort property holds as long as both previous
properties (i.e., soundness and inputs well-formedness) hold, the commitment
is secure, the zero-knowledge proofs are publicly verifiable and the signature
scheme is secure. The reason is that the algorithm
$\mathtt{VSID.identify}(\cdot)$, which ensures detectable abort, is a wrapper
function that is invoked by the arbiter, and sequentially makes subroutine
calls to algorithms $\mathtt{VSID.serve}(\cdot)$,
$\mathtt{VSID.checkQuery}(\cdot)$ and $\mathtt{VS.verify}(\cdot)$, where the
first two ensure input well-formedness, and the last one ensures soundness.
Also, due to the security of the commitment (i.e., binding), the malicious
client cannot provide the arbiter with another secret verification key than
what was initially committed. Moreover, due to the public verifiability of the
zero-knowledge proofs, the arbiter can verify all proofs input to
$\mathtt{VSID.serve}(\cdot)$ and $\mathtt{VSID.checkQuery}(\cdot)$. The
signature’s security ensures if a proof is not signed correctly, then it can
also be rejected by the arbiter; on the other hand, if a proof is signed
correctly, then it cannot be repudiated by the signer later on (due to
signature’s unforgeability); this guarantees that the signer is held
accountable for a rejected proof it provides. ∎

######  Remark 2.

As we mentioned before, it is often sufficient to let the arbiter pinpoint a
corrupt party _after_ the client and server agree to deal with each other. We
denoted a VSID protocol that meets the latter (lighter) requirement, by
$\text{VSID}_{\scriptscriptstyle\text{light}}$. This version would impose
lower costs, when $u$ and elements of $e$ are of large size. In
$\text{VSID}_{\scriptscriptstyle\text{light}}$ protocol, the client and server
run phases 1-3 of the VSID protocol as before, with a difference that the
client does not post $e$ and $u^{\scriptscriptstyle*}$ to the board; instead,
it sends them directly to the server. In
$\text{VSID}_{\scriptscriptstyle\text{light}}$ the arbiter algorithm, i.e.,
$\mathtt{VSID.identify}(\cdot)$, needs to take only
$(\bm{\pi},c,k,e^{\prime},{pp})$ as input, where $e^{\prime}$ contains the
opening of $\mathtt{Com}_{\scriptscriptstyle{sk}}$ if
$\mathtt{VSID.verify}(\cdot)$ is privately verifiable or $e^{\prime}=\bot$ if
it is publicly verifiable. In this light version, the arbiter skips step 8a.
Thus, $\text{VSID}_{\scriptscriptstyle\text{light}}$ saves (a) communication
cost, as $u^{\scriptscriptstyle*}$ and $e$ are never sent to the board and
arbiter, and (b) computation cost as the arbiter does not need to run
$\mathtt{VSID.serve}(\cdot)$ anymore.

##  Appendix G Recurring Contingent Service Payment (RC-S-P) Protocol

In this section, we present our RC-S-P protocol.

###  G.1 Recurring Contingent Service Payment (RC-S-P) Protocol

In this section, we present the “recurring contingent service payment” (RC-
S-P) protocol for a generic service. It utilises a novel combination of
$\text{VSID}_{\scriptscriptstyle\text{light}}$, SAP, the private time bubble
notion, and symmetric-key encryption schemes along with the coin masking and
padding techniques. At a high level, the protocol works as follows. The client
and server use SAP to provably agree on two private statements; the first
statement includes payment details, while another one specifies a secret key,
$k$, and the pads’ length. They also agree on public parameters such as (a)
the private time bubble’s length, that is the total number of billing cycles,
$z$, plus a waiting period, J, and (b) a smart contract which specifies $z$
and the total amount of masked coins each party should deposit. The client
deploys the contract. Each party deposits its masked coins in the contract. If
either party does not deposit enough coins on time, later each party has a
chance to withdraw its coins and terminate the contract. To start
using/providing the service, they invoke
$\text{VSID}_{\scriptscriptstyle\text{light}}$ protocol. In particular, they
engage in the $\mathtt{VSID.keyGen}(\cdot)$, $\mathtt{VSID.setup}(\cdot)$, and
$\mathtt{VSID.serve}(\cdot)$ algorithms. If the server decides not to serve,
e.g., it detects the client’s misbehaviour, it sends $0$ within a fixed time;
in this case, the parties can withdraw their deposit and terminate the
contract. Otherwise, the server sends $1$ to the contract.

At the end of each billing cycle, the client generates an encrypted query, by
calling $\mathtt{VSID.genQuery}(\cdot)$ and encrypting its output using the
key, $k$. It pads the encrypted query and sends the result to the contract.
The encryption and pads ensure nothing about the client’s input (e.g.,
outsourced file) is revealed to the public within the private time bubble. In
the same cycle, the server retrieves the query, removes the pads and decrypts
the result. Then, it locally checks its validity, by calling
$\mathtt{VSID.checkQuery}(\cdot)$. If the query is rejected, the server
locally stores the index of the billing cycle and then generates a dummy
proof. Otherwise, if the server accepts the query, it generates a proof of
service by calling $\mathtt{VSID.prove}(\cdot)$. In either case, the server
encrypts the proof, pads it and sends the result to the contract. Note that
sending (padded encrypted) dummy proofs ensures that the public, during the
private time bubble, does not learn if the client generates invalid queries.
After the server sends the messages to the contract, the client removes the
pads, decrypts the proof and locally verifies it, by calling
$\mathtt{VSID.verify}(\cdot)$. If the verification is passed, then the client
knows the server has delivered the service honestly. But, if the proof is
rejected, it waits until the private time bubble passes and dispute resolution
time arrives. During the dispute resolution period, in the case the client or
server rejects any proofs, it invokes the arbiter, refers it to the invalid
encrypted proofs in the contract, and sends to it the decryption key and the
pads’ detail. The arbiter checks the validity of the key and pads, by using
SAP. If they are accepted, then the arbiter locally removes the pads from the
encrypted proofs, decrypts the related proofs, and runs
$\mathtt{VSID.identify}(\cdot)$ to check the validity of the party’s claim.
The arbiter sends to the contract a report of its findings that includes the
total number of times the server and client provided invalid proofs. In the
next phase, to distribute the coins, either client or server sends: (a) “pay”
message, (b) the agreed statement that specifies the payment details, and (c)
the statement’s proof to the contract which verifies the statement and if
approved it distributes the coins according to the statement’s detail, and the
arbiter’s report.

Now we outline why RC-S-P addresses the issues, raised in Section 5. In the
setup, if the client provides ill-formed inputs (so later it can accuse the
server) then the server can detect and avoid serving it. After the setup, if
the client avoids sending any input, then the server still gets paid for the
service it provided. Also, in the case of a dispute between the parties, their
claim is checked, and the corrupt party is identified. The corrupt party has
to pay the arbiter and if that is the client, then it has to pay the server as
well. These features not only do guarantee the server’s resource is not
wasted, but also ensures fairness (i.e., if a potentially malicious server is
paid, then it must have provided the service and if a potentially malicious
client does not pay, then it will learn nothing). Furthermore, as during the
private time bubble (a) no plaintext proof is given to the contract, and (b)
no dispute resolution and coin transfer take place on contract, the public
cannot figure out the outcome of each verification. This preserves the
server’s privacy. Also, because the deposited coins are masked and the agreed
statement is kept private, nothing about the detail of the service is leaked
to the public before the bubble bursts. This preserves the client’s privacy.
Also, as either party can prove to the contract the validity of the agreed
statement, and ask the contract to distribute the coins, the coins will be not
be locked forever.

####  G.1.1 Protocol description

The RC-S-P protocol is parameterized by the functions $F,M,Q$ of the
underlying VSID and encoding/decoding functions $(E,D)$ that refer to “encrypt
then pad”/“remove pad then decrypt” procedures, respectively. It is assumed
that (a) each party $\mathcal{P}\in\\{\mathcal{C,S,R}\\}$ already has a
blockchain public address, $adr_{\scriptscriptstyle\mathcal{P}}$, which is
known to all parties, (b) it uses that (authorised) address to send
transactions to the smart contract, (c) the contract before recording a
transaction, ensures the transaction is originated from an authorised address,
and (d) there is a public price list $pl$ known to everyone. The protocol is
presented below.

  1. 1.

Key Generation. $\mathtt{RCSP}.\mathtt{keyGen}(1^{\lambda})$

    1. (a)

$\mathcal{C}$ runs $\mathtt{VSID.keyGen}(1^{\lambda})\rightarrow k:=(sk,pk)$.
It picks a random secret key $\bar{k}$ for a symmetric-key encryption. Also,
it sets two parameters: $pad_{\scriptscriptstyle\pi}$ and
$pad_{\scriptscriptstyle q}$, where $pad_{\scriptscriptstyle\pi}$ and
$pad_{\scriptscriptstyle q}$ refer to the number of dummy values that will be
used to pad encrypted proofs and encrypted queries respectively777The values
of $pad_{\scriptscriptstyle\pi}$ and $pad_{\scriptscriptstyle q}$ is
determined as follows, $pad_{\scriptscriptstyle\pi}=\pi_{\scriptscriptstyle
max}-\pi_{\scriptscriptstyle act}$ and $pad_{\scriptscriptstyle
q}=q_{\scriptscriptstyle max}-q_{\scriptscriptstyle act}$, where
$\pi_{\scriptscriptstyle max}$ and $\pi_{\scriptscriptstyle act}$ refer to the
maximum and actual the service’s proof size while $q_{\scriptscriptstyle max}$
and $q_{\scriptscriptstyle act}$ refer to the maximum and actual the service’s
query size, respectively., determined by the security parameter and
description of $F$. Let
$sk^{\prime}:=(pad_{\scriptscriptstyle\pi},pad_{\scriptscriptstyle
q},\bar{k})$. The keys’ size is part of the security parameter. Let
$\bm{k}=[k,k^{\prime}]$, where $k^{\prime}:=(sk^{\prime},pk^{\prime})$ and
$pk^{\prime}:=(adr_{\scriptscriptstyle\mathcal{C}},adr_{\scriptscriptstyle\mathcal{S}})$.

  2. 2.

Client-side Initiation.
$\mathtt{RCSP}.\mathtt{cInit}(1^{\lambda},u,\bm{k},z,pl)$

    1. (a)

Calls
$\mathtt{VSID.setup}(1^{\lambda},u,k)\rightarrow(u^{\scriptscriptstyle*},{pp},e)$,
to encode service input, and generate metadata. It sets $qp=sk^{\prime}$ and
appends $pp$ to $qp$.

    2. (b)

Calls
$\mathtt{SAP.init}(1^{\lambda},adr_{\scriptscriptstyle\mathcal{C}},adr_{\scriptscriptstyle\mathcal{S}},qp)\rightarrow(r_{\scriptscriptstyle
qp},g_{\scriptscriptstyle qp},\\\
adr_{\scriptscriptstyle\text{SAP}_{\scriptscriptstyle 1}})$, to initiate an
agreement (with $\mathcal{S}$) on $qp$. Let $T_{\scriptscriptstyle
qp}:=(\ddot{x}_{\scriptscriptstyle qp},g_{\scriptscriptstyle qp})$ be
proof/query encoding token, where $\ddot{x}_{\scriptscriptstyle
qp}:=(qp,r_{\scriptscriptstyle qp})$ is the opening and $g_{\scriptscriptstyle
qp}$ is the commitment stored on the contract as a result of running SAP.

    3. (c)

Sets coin parameters as follows, $o$: the amount of coins for each accepting
proof, and $l$: the amount of coins to cover the cost of each potential
dispute resolution, given price list $pl$.

    4. (d)

Sets $cp:=(o,o_{\scriptscriptstyle max},l,l_{\scriptscriptstyle max},z)$,
where $o_{\scriptscriptstyle max}$ is the maximum amount of coins for an
accepting service proof, $l_{\scriptscriptstyle max}$ is the maximum amount of
coins to resolve a potential dispute, and $z$ is the number of service
proofs/verifications. Then, $\mathcal{C}$ calls
$\mathtt{SAP.init}(1^{\lambda},adr_{\scriptscriptstyle\mathcal{C}},adr_{\scriptscriptstyle\mathcal{S}},cp)\rightarrow(r_{\scriptscriptstyle
cp},g_{\scriptscriptstyle
cp},adr_{\scriptscriptstyle\text{SAP}_{\scriptscriptstyle 2}})$, to initiate
an agreement (with $\mathcal{S}$) on $cp$. Let $T_{\scriptscriptstyle
cp}:=(\ddot{x}_{\scriptscriptstyle cp},g_{\scriptscriptstyle cp})$ be coin
encoding token, where $\ddot{x}_{\scriptscriptstyle
cp}:=(cp,r_{\scriptscriptstyle cp})$ is the opening and $g_{\scriptscriptstyle
cp}$ is the commitment stored on the contract as a result of executing SAP.
Let $T:=\\{T_{\scriptscriptstyle qp},T_{\scriptscriptstyle cp}\\}$.

    5. (e)

Set parameters
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}=z\cdot(o_{\scriptscriptstyle
max}+l_{\scriptscriptstyle max})$ and
$p_{\scriptscriptstyle\mathcal{S}}=z\cdot l_{\scriptscriptstyle max}$, where
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}$ and
$p_{\scriptscriptstyle\mathcal{S}}$ are the total number of masked coins
$\mathcal{C}$ and $\mathcal{S}$ should deposit respectively. It also designs a
smart contract, SC, that explicitly specifies parameters $z$,
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}$,
$p_{\scriptscriptstyle\mathcal{S}}$,
$adr_{\scriptscriptstyle\text{SAP}_{\scriptscriptstyle 1}}$,
$adr_{\scriptscriptstyle\text{SAP}_{\scriptscriptstyle 2}},pk$, and
$pk^{\prime}$. It sets a set of time points/windows,
$\texttt{Time}:\\{\texttt{T}_{\scriptscriptstyle
0},...,\texttt{T}_{\scriptscriptstyle 2},\texttt{G}_{\scriptscriptstyle
1,1},...,\texttt{G}_{\scriptscriptstyle z,2},\texttt{J},$
$\texttt{K}_{\scriptscriptstyle 1},...,\texttt{K}_{\scriptscriptstyle
3},\texttt{L}\\}$, that are explicitly specified in the contract which will
accept a certain party’s message only in a specified time point/window. The
time allocation will become clear in the next phases.

    6. (f)

Sets also four counters
$[y_{\scriptscriptstyle\mathcal{C}},y^{\prime}_{\scriptscriptstyle\mathcal{C}},y_{\scriptscriptstyle\mathcal{S}},y^{\prime}_{\scriptscriptstyle\mathcal{S}}]$
in SC, where their initial value is $0$. It signs and deploys SC to the
blockchain. Let $adr_{\scriptscriptstyle\text{SC}}$ be the address of the
deployed SC, and $\bm{y}:[y_{\scriptscriptstyle\mathcal{C}},$
$y^{\prime}_{\scriptscriptstyle\mathcal{C}},y_{\scriptscriptstyle\mathcal{S}},y^{\prime}_{\scriptscriptstyle\mathcal{S}},adr_{\scriptscriptstyle\text{SC}}]$.

    7. (g)

Deposits $coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}$ coins in
the contract. It sends
$u^{\scriptscriptstyle*},z,e,\ddot{x}_{\scriptscriptstyle qp}$, and
$\ddot{x}_{\scriptscriptstyle cp}$ (along with
$adr_{\scriptscriptstyle\text{SC}}$) to $\mathcal{S}$. Let
$\texttt{T}_{\scriptscriptstyle 0}$ be the time that the above process
finishes.

  3. 3.

Server-side Initiation.
$\mathtt{RCSP}.\mathtt{sInit}(u^{\scriptscriptstyle*},e,pk,z,T,p_{\scriptscriptstyle\mathcal{S}},\bm{y})$

    1. (a)

Checks the parameters in $T$ (e.g., $qp$ and $cp$) and in SC (e.g.,
$p_{\scriptscriptstyle\mathcal{S}},\bm{y}$) and ensures a sufficient amount of
coins has been deposited by $\mathcal{C}$.

    2. (b)

Calls $\mathtt{SAP.agree}(qp,r_{\scriptscriptstyle qp},g_{\scriptscriptstyle
qp},adr_{\scriptscriptstyle\mathcal{C}},adr_{\scriptscriptstyle\text{SAP}_{1}})\rightarrow(g^{\prime}_{\scriptscriptstyle
qp},b_{\scriptscriptstyle 1})$ and
$\mathtt{SAP.agree}(cp,r_{\scriptscriptstyle cp},g_{\scriptscriptstyle
cp},adr_{\scriptscriptstyle\mathcal{C}},adr_{\scriptscriptstyle\text{SAP}_{2}})\rightarrow(g^{\prime}_{\scriptscriptstyle
cp},b_{\scriptscriptstyle 2})$, to verify the correctness of tokens in $T$ and
to agree on the tokens’ parameters, where $qp,r_{\scriptscriptstyle
qp}\in\ddot{x}_{\scriptscriptstyle qp},\text{and }cp,r_{\scriptscriptstyle
cp}\in\ddot{x}_{\scriptscriptstyle cp}$. Recall that if both $\mathcal{C}$ and
$\mathcal{S}$ are honest, then $g_{\scriptscriptstyle
qp}=g^{\prime}_{\scriptscriptstyle qp}$ and $g_{\scriptscriptstyle
cp}=g^{\prime}_{\scriptscriptstyle cp}$.

    3. (c)

If any above check is rejected, then it sets $a=0$. Otherwise, it calls
$\mathtt{VSID.serve}(u^{\scriptscriptstyle*},e,pk,{pp})\rightarrow a$.

    4. (d)

Sends $a$ and
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}=p_{\scriptscriptstyle\mathcal{S}}$
coins to SC at time $\texttt{T}_{\scriptscriptstyle 1}$, where
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}=\bot$ if $a=0$

Note that, $\mathcal{S}$ and $\mathcal{C}$ can withdraw their coins at time
$\texttt{T}_{\scriptscriptstyle 2}$, if $\mathcal{S}$ sends $a=0$, fewer coins
than $p_{\scriptscriptstyle\mathcal{S}}$, or nothing to the SC. To withdraw,
$\mathcal{S}$ or $\mathcal{C}$ simply sends a “pay” message to
$\mathtt{RCSP}.\mathtt{pay}(\cdot)$ algorithm (only) at time
$\texttt{T}_{\scriptscriptstyle 2}$.

Billing-cycles Onset. $\mathcal{C}$ and $\mathcal{S}$ engage in the following
three phases, i.e., phases 4-6, at the end of every $j$-th billing cycle,
where $1\leq j\leq z$. Each $j$-th cycle includes two time points,
$\texttt{G}_{\scriptscriptstyle j,1}$ and $\texttt{G}_{\scriptscriptstyle
j,2}$, where $\texttt{G}_{\scriptscriptstyle
j,2}>\texttt{G}_{\scriptscriptstyle j,1}$, and $\texttt{G}_{\scriptscriptstyle
1,1}>\texttt{T}_{\scriptscriptstyle 2}$.

  4. 4.

Client-side Query Generation.
$\mathtt{RCSP}.\mathtt{genQuery}(1^{\lambda},\text{aux},$ $k,$
$T_{\scriptscriptstyle qp})$

    1. (a)

Calls $\mathtt{VSID.genQuery}(1^{\lambda},\text{aux},k,{pp})\rightarrow
c_{\scriptscriptstyle j}:=(\bm{q}_{\scriptscriptstyle
j},\bm{w}_{\scriptscriptstyle q_{{}_{\scaleto{j}{3.3pt}}}})$, to generate a
query-proof pair.

    2. (b)

Encodes $c_{\scriptscriptstyle j}$, by first encrypting it,
$\mathtt{Enc}(\bar{k},c_{\scriptscriptstyle j})=c^{\prime}_{\scriptscriptstyle
j}$, where $\bar{k}\in T_{\scriptscriptstyle qp}$; and then, padding (each
element of) the result with ${pad}_{\scriptscriptstyle q}\in
T_{\scriptscriptstyle qp}$ random values that are picked uniformly at random
from the encryption’s output range, $U$. Let
$c^{\scriptscriptstyle*}_{\scriptscriptstyle j}$ be the result.

    3. (c)

Sends the padded encrypted query-proof pair,
$c^{\scriptscriptstyle*}_{\scriptscriptstyle j}$, to SC at time
$\texttt{G}_{\scriptscriptstyle j,1}$.

  5. 5.

Server-side Proof Generation.
$\mathtt{RCSP}.\mathtt{prove}(u^{\scriptscriptstyle*},\sigma,c^{\scriptscriptstyle*}_{\scriptscriptstyle
j},pk,T_{\scriptscriptstyle qp})$

    1. (a)

Constructs an empty vector, $\bm{m}_{\scriptscriptstyle\mathcal{S}}=\bot$, if
$j=1$.

    2. (b)

Removes the pads from $c^{\scriptscriptstyle*}_{\scriptscriptstyle j}$, using
parameters of $T_{\scriptscriptstyle qp}$. Let $c^{\prime}_{\scriptscriptstyle
j}$ be the result. Next, it decrypts the result,
$\mathtt{Dec(}\bar{k},c^{\prime}_{\scriptscriptstyle j})=c_{\scriptscriptstyle
j}$. Then, it runs $\mathtt{VSID.checkQuery}(c_{\scriptscriptstyle
j},pk,{pp})\rightarrow b_{\scriptscriptstyle j}$, to check the correctness of
the queries.

       * $\bullet$

If $\mathcal{S}$ accepts the query, i.e., $b_{\scriptscriptstyle j}=1$, then
calls
$\mathtt{VSID.prove}(u^{\scriptscriptstyle*},\sigma,c_{\scriptscriptstyle
j},pk,{pp})\rightarrow\bm{\pi}_{\scriptscriptstyle j}$, to generate the
service proof. In this case, $\mathcal{S}$ encrypts it,
$\mathtt{Enc}(\bar{k},\bm{\pi}_{\scriptscriptstyle
j})=\bm{\pi}^{\prime}_{\scriptscriptstyle j}$. Next, it pads (every element
of) the encrypted proof with ${pad}_{\scriptscriptstyle\pi}\in
T_{\scriptscriptstyle qp}$ random values picked uniformly at random from $U$.
Let $\bm{\pi}^{\scriptscriptstyle*}_{\scriptscriptstyle j}$ be the result. It
sends the padded encrypted proof to SC at time $\texttt{G}_{\scriptscriptstyle
j,2}$.

       * $\bullet$

Otherwise (if $\mathcal{S}$ rejects the query), it appends $j$ to
$\bm{m}_{\scriptscriptstyle\mathcal{S}}$, constructs a dummy proof
$\bm{\pi}^{\prime}_{\scriptscriptstyle j}$, picked uniformly at random from
$U$, pads the result as above, and sends the padded dummy proof,
$\bm{\pi}^{\scriptscriptstyle*}_{\scriptscriptstyle j}$, to SC at time
$\texttt{G}_{\scriptscriptstyle j,2}$.

When $j=z$ and $\bm{m}_{\scriptscriptstyle\mathcal{S}}\neq\bot$, $\mathcal{S}$
sets
$m_{\scriptscriptstyle\mathcal{S}}:=(\bm{m}_{\scriptscriptstyle\mathcal{S}},adr_{\scriptscriptstyle\text{SC}})$.

  6. 6.

Client-side Proof Verification.
$\mathtt{RCSP}.\mathtt{verify}(\bm{\pi}^{\scriptscriptstyle*}_{\scriptscriptstyle
j},c^{\scriptscriptstyle*}_{\scriptscriptstyle j},k,T_{\scriptscriptstyle
qp})$

    1. (a)

Constructs an empty vector, $\bm{m}_{\scriptscriptstyle\mathcal{C}}=\bot$, if
$j=1$.

    2. (b)

Removes the pads from $\bm{\pi}^{\scriptscriptstyle*}_{\scriptscriptstyle j}$,
utilising parameters of $T_{\scriptscriptstyle qp}$. Let
$\bm{\pi}^{\prime}_{\scriptscriptstyle j}$ be the result. It decrypts the
service proof: $\mathtt{Dec}(\bar{k},\bm{\pi}^{\prime}_{\scriptscriptstyle
j})=\bm{\pi}^{\prime\prime}_{\scriptscriptstyle j}$ and then calls
$\mathtt{VSID.verify}(\bm{\pi}^{\prime\prime}_{\scriptscriptstyle
j},\bm{q}_{\scriptscriptstyle j},k,{pp})\rightarrow d_{\scriptscriptstyle j}$,
to verify the proof, where $\bm{q}_{\scriptscriptstyle j}\in
c_{\scriptscriptstyle j}$ (and $c_{\scriptscriptstyle j}$ is the result of
removing pads from $c^{\scriptscriptstyle*}_{\scriptscriptstyle j}$ and then
decrypting the result). Note that if $\bm{\pi}^{\prime}_{\scriptscriptstyle
j}=\mathtt{Enc}(\bar{k},\bm{\pi}_{\scriptscriptstyle j})$, then
$\bm{\pi}^{\prime\prime}_{\scriptscriptstyle j}=\bm{\pi}_{\scriptscriptstyle
j}$.

       * $\bullet$

If $\bm{\pi}^{\prime\prime}_{\scriptscriptstyle j}$ passes the verification
(i.e., $d_{\scriptscriptstyle j}=1$), then $\mathcal{C}$ concludes that the
service for this verification has been delivered successfully.

       * $\bullet$

Otherwise (when $\bm{\pi}^{\prime\prime}_{\scriptscriptstyle j}$ is rejected),
$\mathcal{C}$ appends $j$ to $\bm{m}_{\scriptscriptstyle\mathcal{C}}$.

When $j=z$ and $\bm{m}_{\scriptscriptstyle\mathcal{C}}\neq\bot$, $\mathcal{C}$
sets
${m}_{\scriptscriptstyle\mathcal{C}}:=(\bm{m}_{\scriptscriptstyle\mathcal{C}},adr_{\scriptscriptstyle\text{SC}},e^{\prime})$,
where $e^{\prime}$ contains the opening of $\mathtt{Com}_{\scriptscriptstyle
sk}$ or $\bot$, as stated in Remark 2.

  7. 7.

Dispute Resolution.
$\mathtt{RCSP}.\mathtt{resolve}(\bm{m}_{\scriptscriptstyle\mathcal{C}},\bm{m}_{\scriptscriptstyle\mathcal{S}},z,{\bm{\pi}}^{\scriptscriptstyle*},{\bm{c}}^{\scriptscriptstyle*},pk,T_{\scriptscriptstyle
qp})$

The phase takes place only in case of dispute, e.g., when $\mathcal{C}$ and/or
$\mathcal{S}$ reject any proofs in the previous phases.

    1. (a)

The arbiter sets counters:
$y_{\scriptscriptstyle\mathcal{C}},y^{\prime}_{\scriptscriptstyle\mathcal{C}},y_{\scriptscriptstyle\mathcal{S}}$
and $y^{\prime}_{\scriptscriptstyle\mathcal{S}}$, that are initially set to
$0$, before time $\texttt{K}_{\scriptscriptstyle 1}$, where
$\texttt{K}_{\scriptscriptstyle 1}>\texttt{G}_{\scriptscriptstyle
z,2}+\texttt{J}$.

    2. (b)

$\mathcal{C}$ sends $m_{\scriptscriptstyle\mathcal{C}}$ and
$\ddot{x}_{\scriptscriptstyle qp}$ to the arbiter at time
$\texttt{K}_{\scriptscriptstyle 1}$. Or, $\mathcal{S}$ sends
$m_{\scriptscriptstyle\mathcal{S}}$ and $\ddot{x}_{\scriptscriptstyle qp}$ to
the arbiter at time $\texttt{K}_{\scriptscriptstyle 1}$.

    3. (c)

At time $\texttt{K}_{\scriptscriptstyle 2}$, the arbiter checks the validity
of statement $\ddot{x}_{\scriptscriptstyle qp}$ sent by each party
$\mathcal{P}\in\\{\mathcal{C,S}\\}$. To do so, it sends each
$\ddot{x}_{\scriptscriptstyle qp}$ to SAP contract which returns either $1$ or
$0$. The arbiter constructs an empty vector, $\bm{v}$. If party
$\mathcal{P}$’s statement is accepted, then it appends every element of
$\bm{m}_{\scriptscriptstyle\mathcal{P}}$ to $\bm{v}$. It ensures $\bm{v}$
contains only distinct elements which are in the range $[1,z]$. Otherwise (if
the party’s statement is rejected) it discards the party’s request,
$\bm{m}_{\scriptscriptstyle\mathcal{P}}$. It proceeds to the next step if
$\bm{v}$ is not empty, otherwise it halts.

    4. (d)

The arbiter for every element $i\in\bm{v}$:

      1. i.

removes the pads from the related encrypted query-proof pair and from
encrypted service proof. Let $c^{\prime}_{\scriptscriptstyle i}$ and
$\bm{\pi}^{\prime}_{\scriptscriptstyle i}$ be the result.

      2. ii.

decrypts the encrypted query-proof pair and encrypted service proof as
follows, $\mathtt{Dec}(\bar{k},c^{\prime}_{\scriptscriptstyle
i})=c_{\scriptscriptstyle i}$ and
$\mathtt{Dec}(\bar{k},\bm{\pi}^{\prime}_{\scriptscriptstyle
i})=\bm{\pi}^{\prime\prime}_{\scriptscriptstyle i}$.

      3. iii.

calls $\mathtt{VSID.identify}(\bm{\pi}^{\prime\prime}_{\scriptscriptstyle
i},c_{\scriptscriptstyle i},k,e^{\prime},{pp})\rightarrow
I_{\scriptscriptstyle i}$

        1. $\bullet$

if $I_{\scriptscriptstyle i}=\mathcal{C}$ and
$y^{\prime}_{\scriptscriptstyle\mathcal{C}}$ was not incremented for $i$-th
verification, it increments $y_{\scriptscriptstyle\mathcal{C}}$ by $1$.

        2. $\bullet$

if $I_{\scriptscriptstyle i}=\mathcal{S}$ and
$y^{\prime}_{\scriptscriptstyle\mathcal{S}}$ was not incremented for $i$-th
verification, it increments $y_{\scriptscriptstyle\mathcal{S}}$ by $1$.

        3. $\bullet$

if $I_{\scriptscriptstyle i}=\bot$, then it increments
$y^{\prime}_{\scriptscriptstyle\mathcal{C}}$ or
$y^{\prime}_{\scriptscriptstyle\mathcal{S}}$ by $1$, if $i$ is in the
complaint of $\mathcal{C}$ or $\mathcal{S}$ respectively and
$y_{\scriptscriptstyle\mathcal{C}}$ or $y_{\scriptscriptstyle\mathcal{S}}$ was
not incremented in $i$-th verification.

Let $\texttt{K}_{\scriptscriptstyle 3}$ be the time that the arbiter finishes
the above checks.

    5. (e)

The arbiter at time $\texttt{K}_{\scriptscriptstyle 3}$ sends
$[y_{\scriptscriptstyle\mathcal{C}},y_{\scriptscriptstyle\mathcal{S}},y^{\prime}_{\scriptscriptstyle\mathcal{C}},y^{\prime}_{\scriptscriptstyle\mathcal{S}}]$
to SC that accordingly overwrites the elements it holds (i.e., elements of
$\bm{y}$) by the related vectors elements the arbiter sent.

  8. 8.

Coin Transfer. $\mathtt{RCSP}.\mathtt{pay}(\bm{y},T_{\scriptscriptstyle
cp},a,p_{\scriptscriptstyle\mathcal{S}},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}})$

    1. (a)

If SC receives “pay” message at time $\texttt{T}_{2}$, where $a=0$ or
$coins^{*}_{\scriptscriptstyle\mathcal{S}}<p_{\scriptscriptstyle\mathcal{S}}$,
then it sends $coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}$
coins to $\mathcal{C}$ and
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}$ coins to
$\mathcal{S}$. In other words, the parties can withdraw their coins if they do
not reach to an agreement in the end of phase 3, i.e., server-side initiation.
Otherwise (i.e., they reach to an agreement), they take the following steps.

    2. (b)

Either $\mathcal{C}$ or $\mathcal{S}$ sends “pay” message and the statement,
$\ddot{x}_{\scriptscriptstyle cp}\in T_{\scriptscriptstyle cp}$, to SC at time
$\texttt{L}>\texttt{K}_{\scriptscriptstyle 3}$.

    3. (c)

SC checks the validity of the statement by sending
$\ddot{x}_{\scriptscriptstyle cp}$ to the SAP contract which returns either
$1$ or $0$. SC only proceeds to the next step if the output is $1$.

    4. (d)

SC distributes the coins to the parties as follows:

       * $\bullet$

$coin_{\scriptscriptstyle\mathcal{C}}=coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}-o\cdot(z-y_{\scriptscriptstyle\mathcal{S}})-l\cdot(y_{\scriptscriptstyle\mathcal{C}}+y^{\prime}_{\scriptscriptstyle\mathcal{C}})$
coins to $\mathcal{C}$.

       * $\bullet$

$coin_{\scriptscriptstyle\mathcal{S}}=coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}+o\cdot(z-y_{\scriptscriptstyle\mathcal{S}})-l\cdot(y_{\scriptscriptstyle\mathcal{S}}+y^{\prime}_{\scriptscriptstyle\mathcal{S}})$
coins to $\mathcal{S}$.

       * $\bullet$

$coin_{\scriptscriptstyle\mathcal{R}}=l\cdot(y_{\scriptscriptstyle\mathcal{S}}+y_{\scriptscriptstyle\mathcal{C}}+y^{\prime}_{\scriptscriptstyle\mathcal{S}}+y^{\prime}_{\scriptscriptstyle\mathcal{C}})$
coins to the arbiter.

####  G.1.2 Discussion on the RC-S-P protocol description

We conclude Subsection G.1 with the following remarks:

  * •

The length of a private time bubble can be agreed between the server and
client to be of any size that suits them and can exceed the point where the
$z$-th verifications is completed.

  * •

For the sake of simplicity, in the RC-S-P protocol, we let each
$y\in\\{y_{\scriptscriptstyle\mathcal{C}},y^{\prime}_{\scriptscriptstyle\mathcal{C}},y_{\scriptscriptstyle\mathcal{S}},y^{\prime}_{\scriptscriptstyle\mathcal{S}}\\}$
be a counter; instead of a binary vector,
$\bm{y}\in\\{\bm{y}_{\scriptscriptstyle\mathcal{C}},\bm{y}^{\prime}_{\scriptscriptstyle\mathcal{C}},\bm{y}_{\scriptscriptstyle\mathcal{S}},\bm{y}^{\prime}_{\scriptscriptstyle\mathcal{S}}\\}$,
defined in the RC-S-P definition. However, it is not hard to see that the sum
of all elements $\bm{y}$ of equal $y$, i.e.,
$y=\sum\limits_{\scriptscriptstyle j=1}^{\scriptscriptstyle
z}\bm{y}_{\scriptscriptstyle j}$. The same holds for the amounts of coin each
party receives,
$coin\in\\{coin_{\scriptscriptstyle\mathcal{C}},coin_{\scriptscriptstyle\mathcal{S}},coin_{\scriptscriptstyle\mathcal{R}}\\}$,
in the protocol and the coin vector used in the definition,
$\bm{coin}\in\\{\bm{coin}_{\scriptscriptstyle\mathcal{C}},\bm{coin}_{\scriptscriptstyle\mathcal{S}},\bm{coin}_{\scriptscriptstyle\mathcal{R}}\\}$.

  * •

In the protocol, the pads are added _after_ the actual values are encrypted.
This is done to save computation cost. Otherwise (if the pads are added prior
to the encryption), then the pads would have to be encrypted too, which
imposes additional computation cost.

  * •

As stated in Section 7,
$\mathtt{RCSP}.\mathtt{genQuery}(\cdot),\mathtt{RCSP}.\mathtt{prove}(\cdot),\\\
\mathtt{RCSP}.\mathtt{verify}(\cdot)$ and
$\mathtt{RCSP}.\mathtt{resolve}(\cdot)$ implicitly take
$a,coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}},$
$p_{\scriptscriptstyle\mathcal{S}}$ as another inputs and execute only if
$a=1$ and
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}=p_{\scriptscriptstyle\mathcal{S}}$.
For the sake of simplicity, we avoided explicitly stating it in the protocol.
Also, keeping track of
$(y^{\prime}_{\scriptscriptstyle\mathcal{C}},y^{\prime}_{\scriptscriptstyle\mathcal{S}})$
enables the arbiter to make malicious parties, that _unnecessarily_ invoke it
for accepting proofs in step 7(d)iii, pay for the verifications it performs.

  * •

The total coin amounts the client receives is as follows; its initial deposit,
i.e., $coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}$, minus the
total coin amounts that the server should be paid for those verifications that
it has acted honestly towards the client, i.e.,
$o\cdot(z-y_{\scriptscriptstyle\mathcal{S}})$, minus the total coin amounts
the client has to pay to the arbiter when it misbehaved towards the server and
the arbiter, i.e.,
$l\cdot(y_{\scriptscriptstyle\mathcal{C}}+y^{\prime}_{\scriptscriptstyle\mathcal{C}})$.
The total coin amounts the server receives is as follows. Its initial deposit,
i.e., $coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}$, plus the
total coin amounts that it should get paid for those verifications that it
acted honestly towards the client, i.e.,
$o\cdot(z-y_{\scriptscriptstyle\mathcal{S}})$, minus the total coin amounts it
has to pay to the arbiter when it misbehaved towards the client and the
arbiter, i.e.,
$l\cdot(y_{\scriptscriptstyle\mathcal{S}}+y^{\prime}_{\scriptscriptstyle\mathcal{S}})$.
Moreover the arbiter receives in total
$l\cdot(y_{\scriptscriptstyle\mathcal{S}}+y_{\scriptscriptstyle\mathcal{C}}+y^{\prime}_{\scriptscriptstyle\mathcal{S}}+y^{\prime}_{\scriptscriptstyle\mathcal{C}})$
coins to cover its cost of resolving disputes, i.e.,
$l\cdot(y_{\scriptscriptstyle\mathcal{S}}+y_{\scriptscriptstyle\mathcal{C}})$,
plus the cost imposed to it when it is unnecessarily invoked, i.e.,
$l\cdot(y^{\prime}_{\scriptscriptstyle\mathcal{S}}+y^{\prime}_{\scriptscriptstyle\mathcal{C}})$.
If all parties behave honestly, then the server receives all its deposit back
plus the coin amounts they initially agreed to pay the server if it delivers
accepting proofs for all $z$ cycles, i.e., in total it receives
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}+o\cdot z$ coins.
Also, in this case an honest client receives all coins minus the coin amounts
paid to the server for delivering accepting proofs for $z$ cycles, i.e., in
total it receives
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}-o\cdot z$ coins.
However, the arbiter receives no coins, as it is never invoked.

  * •

The VSID scheme does not (need to) preserve the privacy of the proofs.
However, in RC-S-P protocol each proof’s privacy must be preserved, for a
certain time; otherwise, the proof itself can leak its status, e.g., when it
can be publicly verified. This is the reason why in the RC-S-P protocol,
_encrypted_ proofs are sent to the contract. Moreover, for the sake of
simplicity, in the above protocol, we assumed that each arbiter’s invocation
has a fixed cost regardless of the number of steps it takes. To define a fine-
grained costing, one can simply allocate to each step the arbiter takes a
certain rate and also separate counter for the client and server.

  * •

In the case where $\mathtt{VSID.verify}(\cdot)$ is privately verifiable and
the server invokes the arbiter, the client needs to provide inputs to the
arbiter too. Otherwise (when it is publicly verifiable and the server invokes
the arbiter), the client’s involvement is not required in the dispute
resolution phase. In contrast, if the client invokes the arbiter, the server’s
involvement is not required in that phase, regardless of the type of
verifiability $\mathtt{VSID.verify}(\cdot)$ supports. Furthermore, with a
minor adjustment to the RC-S-P protocol, we can let the client and server be
compensated (by a misbehaving party) for the transaction they send to the
contract. To do so, briefly, we can let the parties, in initiation phases,
agree on and include in $cp$ parameters, $l^{\prime}$ and $l^{\prime\prime}$,
that cover the client’s and server’s cost of sending a transaction,
respectively. The parameters are encoded the same way as $l$ is encoded. In
this setting, in the coin transfer phase, the client and server receive
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}-o\cdot(z-y_{\scriptscriptstyle\mathcal{S}})-l\cdot(y_{\scriptscriptstyle\mathcal{C}}+y^{\prime}_{\scriptscriptstyle\mathcal{C}})+l^{\prime}\cdot
y_{\scriptscriptstyle\mathcal{S}}-l^{\prime\prime}\cdot
y_{\scriptscriptstyle\mathcal{C}}$ and
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}+o\cdot(z-y_{\scriptscriptstyle\mathcal{S}})-l\cdot(y_{\scriptscriptstyle\mathcal{S}}+y^{\prime}_{\scriptscriptstyle\mathcal{S}})-l^{\prime}\cdot
y_{\scriptscriptstyle\mathcal{S}}+l^{\prime\prime}\cdot
y_{\scriptscriptstyle\mathcal{C}}$, coins respectively. The amount of coins
the arbiter receives remains unchanged.

  * •

The server or client, even during the private time bubble, can spend (or more
accurately promise to a third party) the amount of coins kept in the contract
and will ultimately be transferred to it. With slight adjustments to the RC-
S-P, they can do so in a privacy-preserving manner. We briefly explain how it
can be done. For the sake of simplicity, we assume the server will receive
$coin_{\scriptscriptstyle\mathcal{S}}$ coins after the bubble bursts and wants
to promise $\hat{coin}_{\scriptscriptstyle\mathcal{S}}$ coins (where
$\hat{coin}_{\scriptscriptstyle\mathcal{S}}\leq
coin_{\scriptscriptstyle\mathcal{S}}$) to the third party $\mathcal{D}$ within
the bubble. First, the server proves to $\mathcal{D}$ that it will receive
$coin_{\scriptscriptstyle\mathcal{S}}$ coins after the bubble bursts. To do
that, it sends the RC-S-P transcripts (that includes all proofs) to
$\mathcal{D}$ which can verify the server’s claim, as all proofs are publicly
verifiable. Next, if $\mathcal{D}$ is convinced, the server and $\mathcal{D}$
invoke a new instance of the SAP and insert the value
$\hat{coin}_{\scriptscriptstyle\mathcal{S}}$ into the SAP’s private statement.
This results in a smart contract,
$\text{SC}_{\scriptscriptstyle\text{SAP}_{\scriptscriptstyle 3}}$. Next, if
both parties agree on the parameters of
$\text{SC}_{\scriptscriptstyle\text{SAP}_{\scriptscriptstyle 3}}$, then the
server sends the address of
$\text{SC}_{\scriptscriptstyle\text{SAP}_{\scriptscriptstyle 3}}$ to the main
contract of RC-S-P, i.e., SC. When the bubble bursts, SC transfers the
client’s share of coins to the client as before. But, SC distributes the
server’s coins if the server or $\mathcal{D}$ sends to it a valid proof for
the above private statement (in addition to the proofs required in the Phase 8
of the original RC-S-P). Upon receiving that proof, SC invokes
$\text{SC}_{\scriptscriptstyle\text{SAP}_{\scriptscriptstyle 3}}$ to check the
validity of the proof. If the proof is accepted, then SC sends
$\hat{coin}_{\scriptscriptstyle\mathcal{S}}$ to $\mathcal{D}$ and
$coin_{\scriptscriptstyle\mathcal{S}}-\hat{coin}_{\scriptscriptstyle\mathcal{S}}$
to the server. It is evident that this approach leaks no information about the
coins amount (including $\hat{coin}_{\scriptscriptstyle\mathcal{S}}$) during
the bubble to the public, due to the security of the SAP. The above idea can
be further extended to support multiple parties. For instance, if the server
wants to promise
$coin_{\scriptscriptstyle\mathcal{S}}-\hat{coin}_{\scriptscriptstyle\mathcal{S}}$
coins to $\mathcal{D}^{\prime}$ (after its promise to $\mathcal{D}$), it needs
to send to $\mathcal{D}^{\prime}$ all the proofs, including the one related to
the above private statement.

  * •

As stated previously, the proofs are sent to the contract to avoid running
into the deniability issue, i.e., a malicious client wrongly claims the server
never sent a proof for a certain verification or a malicious server wrongly
claims it sent its proof to the client. However, in the case where the proof
size is large and posting it to the smart contract would impose a high cost,
the parties can use the following technique to directly communicate with each
other to send and receive the proof. The server sends a signed proof directly
to the client which needs to send back to the server a signed acknowledgment
stating that it received the proof, within a fixed time period. If the server
does not receive a valid acknowledgment on time, it sends the signed proof to
the arbiter. Moreover, if the client does not receive the proof on time, it
needs to let the arbiter know about it. In this case, if the arbiter has
already received the proof, it sends the proof to the client which allows the
client to perform the rest of the computation. On the other hand, if the
arbiter does not have the proof, it asks the server to send to it the client’s
acknowledgment. If the server provides a valid acknowledgment, then the
arbiter considers the client as a misbehaving party; otherwise (if the server
could not provide the acknowledgment), it considers the server as a
misbehaving one. However, if both the server and client behave honestly in
sending and receiving the proof, then they do not need to invoke the arbiter
for this matter and the proof is never stored on the blockchain.

###  G.2 Security Analysis of RC-S-P Protocol

In this section, we analyse the security of RC-S-P protocol, presented in
Section G.1. First, we present the protocol’s primary security theorem.

######  Theorem 3.

The RC-S-P protocol with functions $F,M,E,D,Q$ presented in Section G.1 is
secure for auxiliary information aux, (cf. Definition 6), if the underlying
VSID protocol with functions $F,M,Q$ satisfies correctness, soundness, inputs
well-formedness, and detectable abort for $\text{aux}_{j}$, the SAP is secure,
the signature scheme is secure, and the symmetric-key encryption scheme is
IND-CPA secure.

To prove Theorem 3, we show that RC-S-P meets all security properties defined
in Section 7. We start by proving that RC-S-P satisfies security against a
malicious server.

######  Lemma 1.

If the SAP and signature scheme are secure and the VSID protocol satisfies
correctness, soundness, and detectable abort for auxiliary information aux,
then the RC-S-P protocol presented in Section G.1 is secure against malicious
server for aux.(cf. Definition 3).

###### Proof.

We first consider event

$\Big{(}F(u^{\scriptscriptstyle*},\bm{q}_{\scriptscriptstyle
j},{pp})=h_{\scriptscriptstyle j}\Big{)}\ \wedge$
$\Big{(}(coin_{\scriptscriptstyle\mathcal{C},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{C}}^{\scriptscriptstyle*}}{z}-o)\vee(coin_{\scriptscriptstyle\mathcal{R},j}\neq
l\ \wedge\ y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=1)\Big{)}$

that captures the case where the server provides an accepting service proof
but makes an honest client withdraw an incorrect amount of coins, i.e.,
$coin_{\scriptscriptstyle\mathcal{C},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{C}}^{\scriptscriptstyle*}}{z}-o$,
or it makes the arbiter withdraw an incorrect amount of coins, i.e.,
$coin_{\scriptscriptstyle\mathcal{R},j}\neq l$, if it unnecessarily invokes
the arbiter. As the service proof is valid, an honest client accepts it and
does not raise any dispute. However, the server would be able to make the
client withdraw incorrect amounts of coins, if it manages to either

  1. 1.

convince the arbiter that the client has misbehaved, by making the arbiter
output $y_{\scriptscriptstyle\mathcal{C},j}=1$ through the dispute resolution
phase, or

  2. 2.

submit to the contract, in the coin transfer phase, an accepting statement
$\ddot{x}^{\prime}_{\scriptscriptstyle cp}$ other than what was agreed in the
initiation phase, i.e., $\ddot{x}^{\prime}_{\scriptscriptstyle
cp}\neq\ddot{x}_{\scriptscriptstyle cp}$, so it can change the payments’
parameters (e.g., $l$ or $o$) or send a message on the client’s behalf to
invoke the arbiter unnecessarily.

Nevertheless, the server cannot falsely accuse the client of misbehaviour.
This is because, due to the security of SAP (i.e., the underlying commitment’s
binding property), it cannot convince the arbiter to accept different
decryption key or pads other than what was agreed with the client in the
initiation phase. Specifically, it cannot persuade the arbiter to accept
$\ddot{x}^{\prime}_{\scriptscriptstyle qp}$, where
$\ddot{x}^{\prime}_{\scriptscriptstyle qp}\neq\ddot{x}_{\scriptscriptstyle
qp}$, except with a negligible probability. This ensures that the honest
client’s message is accessed by the arbiter with a high probability, as the
arbiter can extract the client’s message using valid pad information and
decryption key. On the other hand, if the adversary provides a valid
statement, i.e., $\ddot{x}_{\scriptscriptstyle qp}$, then due to the
correctness of VSID, algorithm $\mathtt{VSID.identify}(\cdot)$ outputs
$I_{\scriptscriptstyle j}=\bot$. Therefore, due to the security of SAP (i.e.,
the binding property) and correctness of VSID,
$y_{\scriptscriptstyle\mathcal{C}}$ and $y_{\scriptscriptstyle\mathcal{S}}$
are not incremented by $1$ in the $j$-th verification, i.e.,
$y_{\scriptscriptstyle\mathcal{C},j}=y_{\scriptscriptstyle\mathcal{S},j}=0$.
Also, due to the security of SAP (i.e., the binding property), the server
cannot change the payment parameters by persuading the contract to accept any
statement $\ddot{x}^{\prime}_{\scriptscriptstyle cp}$ other than what was
agreed initially between the client and server, except with a negligible
probability when it finds the hash function’s collision (in the SAP scheme).
Moreover, since the proof is valid the client never raises a dispute, also due
to the digital signature’s unforgeability, the server cannot send a message on
behalf of the client (to unnecessarily invoke the arbiter), and make the
arbiter output $y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=1$ for the $j$-th
verification, except with a negligible probability. So with a high probability
$y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=0$. Recall, in the protocol, the
total coins the client should receive after $z$ verifications is
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}-o\cdot(z-y_{\scriptscriptstyle\mathcal{S}})-l\cdot(y_{\scriptscriptstyle\mathcal{C}}+y^{\prime}_{\scriptscriptstyle\mathcal{C}})$.
Since we focus on the $j$-th verification, the amount of coins that should be
credited to the client for that verification is

$coin_{\scriptscriptstyle\mathcal{C},j}=\frac{coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}}{z}-o\cdot(1-y_{\scriptscriptstyle\mathcal{S},j})-l\cdot(y_{\scriptscriptstyle\mathcal{C},j}+y^{\prime}_{\scriptscriptstyle\mathcal{C},j})$
(1)

As shown above
$y_{\scriptscriptstyle\mathcal{C},j}=y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=y_{\scriptscriptstyle\mathcal{S},j}=0$.
So, according to Equation 1, the client is credited
$\frac{coin_{\scriptscriptstyle\mathcal{C}}^{\scriptscriptstyle*}}{z}-o$ coins
for $j$-th verification, with a high probability. On the other hand, as stated
above, if the adversary invokes the arbiter, the arbiter with a high
probability outputs $I_{\scriptscriptstyle j}=\bot$ which results in
$y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=1$. Recall, in the RC-S-P
protocol, the total coins the arbiter should receive for $z$ verifications is
$l\cdot(y_{\scriptscriptstyle\mathcal{S}}+y_{\scriptscriptstyle\mathcal{C}}+y^{\prime}_{\scriptscriptstyle\mathcal{S}}+y^{\prime}_{\scriptscriptstyle\mathcal{C}})$,
so for the $j$-th the credited coins should be:

$coin_{\scriptscriptstyle\mathcal{R},j}=l\cdot(y_{\scriptscriptstyle\mathcal{S},j}+y_{\scriptscriptstyle\mathcal{C},j}+y^{\prime}_{\scriptscriptstyle\mathcal{S},j}+y^{\prime}_{\scriptscriptstyle\mathcal{C},j})$
(2)

As already shown, in the case where arbiter is unnecessarily invoked by the
server, it holds that $y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=1$; So,
according to Equation 2, $l$ coins is credited to the arbiter for the $j$-th
verification. For the server to make the arbiter withdraw other than that
amount (for the $j$-th verification), in the coin transfer phase, it has to
send to the contract an accepting statement
$\ddot{x}^{\prime}_{\scriptscriptstyle cp}$ other than what was agreed in the
initiation phase, i.e., $\ddot{x}^{\prime}_{\scriptscriptstyle
cp}\neq\ddot{x}_{\scriptscriptstyle cp}$, so it can change the payments’
parameters, e.g., $l$ or $o$. But, as argued above, it cannot succeed with a
probability significantly greater than negligible, due to the binding property
of the SAP’s commitment. We now move on to the following event

$\Big{(}F(u^{\scriptscriptstyle*},\bm{q}_{\scriptscriptstyle j},{pp})\neq
h_{\scriptscriptstyle j}\Big{)}\ \wedge$ $\Big{(}d_{\scriptscriptstyle
j}=1\vee y_{\scriptscriptstyle\mathcal{S},j}=0\ \vee
coin_{\scriptscriptstyle\mathcal{C},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{C}}^{\scriptscriptstyle*}}{z}\
\vee coin_{\scriptscriptstyle\mathcal{R},j}\neq l\Big{)}$

This event captures the case where the server provides an invalid service
proof but either persuades the client to accept the proof, or persuades the
arbiter to accept the proof (e.g., when the client raises a dispute) or makes
the client or arbiter withdraw an incorrect amount of coins, i.e.,
$coin_{\scriptscriptstyle\mathcal{C},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{C}}^{\scriptscriptstyle*}}{z}$
or $coin_{\scriptscriptstyle\mathcal{R},j}\neq l$ respectively. Nevertheless,
due to the soundness of VSID, the probability that a corrupt server can
convince an honest client to accept invalid proof (i.e., outputs
$d_{\scriptscriptstyle j}=1$) is negligible. So, the client detects it with a
high probability and raises a dispute. On the other hand, the server may try
to convince the arbiter, and make it output
$y_{\scriptscriptstyle\mathcal{S},j}=0$, e.g., by sending a complaint. For
$y_{\scriptscriptstyle\mathcal{S},j}=0$ to happen, the server has to either
provide a different accepting statement $\ddot{x}^{\prime}_{\scriptscriptstyle
qp}$, than what was initially agreed with the client (i.e.,
$\ddot{x}^{\prime}_{\scriptscriptstyle qp}\neq\ddot{x}_{\scriptscriptstyle
qp}$) and passes the verification, which requires finding the hash function’s
collision (in the SAP scheme), and its probability of success is negligible.
Or it makes the arbiter accept an invalid proof, but due to the detectable
abort property of VSID, its probability of success is also negligible. Also,
as we discussed above, the probability that the adversary makes the arbiter to
recognise the client as misbehaving, and output
$y_{\scriptscriptstyle\mathcal{C},j}=1$ is negligible too. Therefore, the
arbiter outputs $y_{\scriptscriptstyle\mathcal{S},j}=1$ and
$y_{\scriptscriptstyle\mathcal{C},j}=0$ with a high probability, in both
events when it is invoked by the client or server. Also, in this case,
$y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=0$
as the arbiter has already identified a misbehaving party. So, according to
Equation 1, the client is credited
$\frac{coin_{\scriptscriptstyle\mathcal{C}}^{\scriptscriptstyle*}}{z}$ coins
for that verification, with a high probability. Moreover, according to
Equation 2, the arbiter is credited $l$ coins for that verification, with a
high probability. The adversary may try to make them withdraw an incorrect
amount of coins, e.g., in the case where it does not succeed in convincing the
client or arbiter. To this end, in the coin transfer phase, it has to send a
different accepting statement than what was initially agreed with the client.
But, it would succeed only with a negligible probability, due to the security
of SAP, i.e., its binding property. ∎

######  Lemma 2.

If the SAP and signature scheme are secure and the VSID scheme satisfies
correctness, inputs well-formedness, and detectable abort for auxiliary
information aux, then the RC-S-P protocol presented in Section G.1 is secure
against malicious client for aux (cf. Definition 4).

###### Proof.

First, we consider event

$\Big{(}M(u^{\scriptscriptstyle*},k,{pp})=\sigma\ \wedge\
Q(\text{aux},k,{pp})=\bm{q}_{\scriptscriptstyle j}\Big{)}\ \wedge$
$\Big{(}(coin_{\scriptscriptstyle\mathcal{S},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o)\
\vee\ (coin_{\scriptscriptstyle\mathcal{R},j}\neq l\ \wedge\
y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=1)\Big{)}$

This event captures the case where the client provides accepting metadata and
query but makes the server withdraw an incorrect amount of coins, i.e.,
$coin_{\scriptscriptstyle\mathcal{S},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o$,
or makes the arbiter withdraw an incorrect amount of coins, i.e.,
$coin_{\scriptscriptstyle\mathcal{R},j}\neq l$, if it unnecessarily invokes
the arbiter. Since the metadata and query’s proofs are valid, an honest server
accepts them and does not raise any dispute, so we have
$y_{\scriptscriptstyle\mathcal{C},j}=0$. The client could make the server
withdraw incorrect amount of coins, if it manages to either convince the
arbiter, in phase 7, that the server has misbehaved, i.e., makes the arbiter
output $y_{\scriptscriptstyle\mathcal{S},j}=1$, or submit to the contract an
accepting statement $\ddot{x}^{\prime}_{\scriptscriptstyle cp}$ other than
what was agreed at the initiation phase, i.e., $\ddot{x}_{\scriptscriptstyle
cp}$, in phase 8, or send a message on the server’s behalf to invoke the
arbiter unnecessarily. However, it cannot falsely accuse the server of
misbehaviour, as due to the security of SAP (i.e., the binding property) it
cannot convince the arbiter to accept different decryption key and pads’
detail, by providing a different accepting statement
$\ddot{x}^{\prime}_{\scriptscriptstyle qp}$ (where
$\ddot{x}^{\prime}_{\scriptscriptstyle qp}\neq\ddot{x}_{\scriptscriptstyle
qp}$), than what was initially agreed with the server, except with negligible
probability. This ensures the arbiter is given the honest server’s messages,
with a high probability. So, with a high probability
$y_{\scriptscriptstyle\mathcal{S},j}=0$. On the other hand, if the adversary
provides a valid statement, i.e., $\ddot{x}_{\scriptscriptstyle qp}$, then due
to the correctness of VSID, algorithm $\mathtt{VSID.identify}(\cdot)$ outputs
$I_{\scriptscriptstyle j}=\bot$. So, due to the security of SAP and
correctness of VSID, we would have
$y_{\scriptscriptstyle\mathcal{C},j}=y_{\scriptscriptstyle\mathcal{S},j}=0$
with a high probability. Moreover, due to the security of SAP, the client
cannot convince the contract to accept any statement
$\ddot{x}^{\prime}_{\scriptscriptstyle cp}$ other than what was initially
agreed between the client and server (i.e.,
$\ddot{x}^{\prime}_{\scriptscriptstyle cp}\neq\ddot{x}_{\scriptscriptstyle
cp}$), except with negligible probability. Also, it holds that
$y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=0$ because an honest server
never invokes the arbiter when the client’s messages are well-structured and
due to the signature’s unforgeability, the client cannot send a signed message
on the server’s behalf to unnecessarily invoke the arbiter. According to RC-
S-P protocol, the total coins the server should receive after $z$
verifications is
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}+o\cdot(z-y_{\scriptscriptstyle\mathcal{S}})-l\cdot(y_{\scriptscriptstyle\mathcal{S}}+y^{\prime}_{\scriptscriptstyle\mathcal{S}})$.
Since we focus on the $j$-th verification, the amount of coins that should be
credited to the server for the $j$-th verification is

$coin_{\scriptscriptstyle\mathcal{S},j}=\frac{coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}}{z}+o\cdot(1-y_{\scriptscriptstyle\mathcal{S},j})-l\cdot(y_{\scriptscriptstyle\mathcal{S},j}+y^{\prime}_{\scriptscriptstyle\mathcal{S},j})$
(3)

As shown above, the following holds
$y_{\scriptscriptstyle\mathcal{S},j}=y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=0$,