which means, according to Equation 3, the server is credited
$\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o$ coins
for the $j$-th verification, with a high probability. Furthermore, if the
adversary invokes the arbiter, the arbiter with a high probability outputs
$I_{\scriptscriptstyle j}=\bot$ which yields
$y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=1$. Also, as stated above,
$y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=0$. Hence, according to Equation
2, the arbiter for the $j$-th verification is credited $l$ coins, if it is
unnecessarily invoked. As previously stated, due to the security of SAP, the
client cannot make the arbiter withdraw incorrect amounts of coin by changing
the payment parameters and 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 negligible probability.
We now turn our attention to

$\Big{(}M(u^{\scriptscriptstyle*},k,{pp})\neq\sigma\ \wedge\ a=1\Big{)}$

that captures the case where the server accepts an ill-formed metadata.
However, due to inputs well-formedness of VSID, the probability that event
happens is negligible. So, with a high probability $a=0$. Note, in the case
where $a=0$, the server does not raise any dispute, instead it avoids serving
the client. Next, we move on to

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

This event considers the case where the client provides an invalid query, but
either convinces the server or arbiter to accept it, or makes the server or
arbiter withdraw an incorrect amount of coins, i.e.,
$coin_{\scriptscriptstyle\mathcal{S},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o$
or $coin_{\scriptscriptstyle\mathcal{R},j}\neq l$ respectively. Nevertheless,
due to inputs well-formedness of VSID, the probability that the server outputs
$b_{\scriptscriptstyle j}=1$ in this case is negligible. When the server
rejects the query and raises a dispute, the client may try to convince the
arbiter and make it output $y_{\scriptscriptstyle\mathcal{C},j}=0$, e.g., by
sending a complaint. However, for the adversary to win, either

  1. 1.

it has to provide a different accepting statement
$\ddot{x}^{\prime}_{\scriptscriptstyle qp}$, than what was initially agreed
with the server (i.e., $\ddot{x}^{\prime}_{\scriptscriptstyle
qp}\neq\ddot{x}_{\scriptscriptstyle qp}$) and passes the verification. Due to
the security of SAP, its probability of success is negligible. Or,

  2. 2.

it has to make the arbiter accept an invalid query, i.e., makes the arbiter
output $y_{\scriptscriptstyle\mathcal{C},j}=0$. Due to the detectable abort
property of VSID, its probability of success is negligible too.

Therefore, with a high probability, we have
$y_{\scriptscriptstyle\mathcal{C},j}=1$. Also, as discussed above (due to the
security of SAP), the client cannot make the arbiter recognise the honest
server as a misbehaving party with a probability significantly greater than
negligible. That means with a high probability
$y_{\scriptscriptstyle\mathcal{S},j}=0$. Furthermore, as we already discussed,
since the arbiter has identified a misbehaving party, the following holds
$y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=0$.
Hence, according to Equation 3 the server is credited
$\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o$ coins
for this verification. Also, the arbiter is credited $l$ coins, according to
Equation 2. Note that the adversary may still try to make them withdraw an
incorrect amount of coins (e.g., if the adversary does not succeed in
convincing the server or arbiter). To this end, at the coin transfer phase, it
has to send a different accepting statement than what was initially agreed
with the server. However, due to the security of SAP (i.e., binding property),
its success probability is negligible. ∎

Prior to proving RC-S-P’s privacy, we provide a lemma that will be used in the
privacy’s proof. Informally, the lemma states that encoded coins leaks no
information about the actual amount of coins $(o,l)$, agreed between the
client and server.

######  Lemma 3.

Let
$\beta\stackrel{{\scriptstyle\scriptscriptstyle\$}}{{\leftarrow}}\\{0,1\\}$,
price list be $\\{(o_{\scriptscriptstyle 0},l_{\scriptscriptstyle
0}),(o_{\scriptscriptstyle 1},l_{\scriptscriptstyle 1})\\}$, and encoded coin
amounts be
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}=z\cdot(Max(o_{\scriptscriptstyle\beta},$
$o_{\scriptscriptstyle 1-\beta})$
$+Max(l_{\scriptscriptstyle\beta},l_{\scriptscriptstyle 1-\beta}))$ and
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}=z\cdot(Max(l_{\scriptscriptstyle\beta},l_{\scriptscriptstyle
1-\beta}))$. Then, given the price list, $z$,
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}$, and
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}$, an adversary
$\mathcal{A}$ cannot tell the value of $\beta$ with a probability
significantly greater than $\frac{1}{2}$ (where the probability is taken over
the choice of $\beta$ and the randomness of $\mathcal{A}$).

###### Proof.

As it is evident, the list and $z$ contains no information about $\beta$.
Also, since $z$ is a public value, it holds that
$coin^{\prime\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}=\frac{coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}}{z}=Max(o_{\scriptscriptstyle\beta},o_{\scriptscriptstyle
1-\beta})+Max(l_{\scriptscriptstyle\beta},l_{\scriptscriptstyle 1-\beta})$. It
is not hard to see
$coin^{\prime\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}$ is a
function of maximum value of $(o_{\scriptscriptstyle 0},o_{\scriptscriptstyle
1})$, and maximum value of $(l_{\scriptscriptstyle 0},l_{\scriptscriptstyle
1})$. It is also independent of $\beta$. Therefore (given the list, $z$ and
$coin^{\prime\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}$) the
adversary learns nothing about $\beta$, unless it guesses the value, with
success probability $\frac{1}{2}$. The same also holds for
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}$. ∎

######  Lemma 4.

If SAP is secure and the symmetric-key encryption scheme is IND-CPA secure,
then the RC-S-P protocol presented in Section G.1 preserves privacy for
auxiliary information aux, (cf. Definition 5).

###### Proof.

We start with case $1$, i.e., the privacy of service input. Due to the privacy
property of SAP, that stems from the hiding property of the commitment scheme,
given the commitments $g_{\scriptscriptstyle qp}$ and $g_{\scriptscriptstyle
cp}$, (that are stored in the blockchain as a result of running SAP) the
adversary learns no information about the committed values (e.g.,
$o,l,pad_{\scriptscriptstyle\pi},pad_{\scriptscriptstyle q},$ and $\bar{k}$),
except with a negligible probability. Also, given price list $pl$, encoded
coins
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}=z\cdot(o_{\scriptscriptstyle
max}+l_{\scriptscriptstyle max})$ and
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}=z\cdot
l_{\scriptscriptstyle max}$, the adversary learns nothing about the actual
price that was agreed between the server and client, $(o,l)$, for each
verification, due to Lemma 3. Next we analyse the privacy of padded encrypted
query vector $\bm{c}^{\scriptscriptstyle*}$. For the sake of simplicity, we
focus on $\bm{q}^{\scriptscriptstyle*}_{\scriptscriptstyle j}\in
c^{\scriptscriptstyle*}_{\scriptscriptstyle
j}\in\bm{c}^{\scriptscriptstyle*}$, that is a padded encrypted query vector
for $j$-th verification. Let $\bm{q}_{\scriptscriptstyle j,0}$ and
$\bm{q}_{\scriptscriptstyle j,1}$ be query vectors, for $j$-th verification,
related to the service inputs $u_{\scriptscriptstyle 0}$ and
$u_{\scriptscriptstyle 1}$ that are picked by the adversary according to
Definition 5 which lets the environment pick
$\beta\stackrel{{\scriptstyle\scriptscriptstyle\$}}{{\leftarrow}}\\{0,1\\}$.
Also, let $\\{\bm{q}_{\scriptscriptstyle j,0},...,\bm{q}_{\scriptscriptstyle
j,\bar{m}}\\}$ be a list of all queries of different sizes. In the experiment,
if $\bm{q}_{\scriptscriptstyle j,\beta}$ is only encrypted (but not padded),
then given the ciphertext, due to semantical security of the encryption, an
adversary cannot tell if the ciphertext corresponds to
$\bm{q}_{\scriptscriptstyle j,0}$ or $\bm{q}_{\scriptscriptstyle j,1}$
(accordingly to $u_{\scriptscriptstyle 0}$ or $u_{\scriptscriptstyle 1}$) with
probability significantly greater than $\frac{1}{2}+\mathsf{negl}(\lambda)$,
under the assumption that the size of $\bm{q}_{\scriptscriptstyle j,\beta}$ is
equal to the size of largest query size 888The assumption that all queries
have the same size is subsumed under the above assumption., i.e.,
$Max(|\bm{q}_{\scriptscriptstyle j,0}|,...,|\bm{q}_{\scriptscriptstyle
j,\bar{m}}|)=|\bm{q}_{\scriptscriptstyle j,\beta}|$. The above assumption is
relaxed with the use of a pad; as each encrypted query is padded to the
queries’ maximum size, i.e., $Max(|\bm{q}_{\scriptscriptstyle
j,0}|,...,|\bm{q}_{\scriptscriptstyle j,\bar{m}}|)$, the adversary cannot tell
with a probability greater than $\frac{1}{2}+\mathsf{negl}(\lambda)$ if the
padded encrypted proof corresponds to $\bm{q}_{\scriptscriptstyle j,0}$ or
$\bm{q}_{\scriptscriptstyle j,1}$, as the padded encrypted query _always has
the same size_ and the pad values are picked from the same range as the
encryption’s ciphertext are defined. The same argument holds for
$\bm{w}^{\scriptscriptstyle*}_{\scriptscriptstyle
q_{{}_{\scaleto{j}{3.3pt}}}}\in c^{\scriptscriptstyle*}_{\scriptscriptstyle
j}\in\bm{c}^{\scriptscriptstyle*}$. Next we analyse the privacy of padded
encrypted proof vector $\bm{\pi}^{\scriptscriptstyle*}$. The argument is
similar to the one presented above, however, we provide it for the sake of
completeness. We focus on an element of the vector, $\pi_{\scriptscriptstyle
j}^{\scriptscriptstyle*}\in\bm{\pi}^{\scriptscriptstyle*}$, that is a padded
encrypted proof for $j$-th verification. Let $\pi_{\scriptscriptstyle j,0}$
and $\pi_{\scriptscriptstyle j,1}$ be proofs, for $j$-th verification, related
to the service inputs $u_{\scriptscriptstyle 0}$ and $u_{\scriptscriptstyle
1}$, where the inputs are picked by the adversary, w.r.t. Definition 5 in
which the environment picks
$\beta\stackrel{{\scriptstyle\scriptscriptstyle\$}}{{\leftarrow}}\\{0,1\\}$.
Let $\\{\pi_{\scriptscriptstyle j,0},...,\pi_{\scriptscriptstyle
j,\bar{m}}\\}$ be proof list including all proofs of different sizes. If we
assume $\pi_{\scriptscriptstyle j,\beta}$ is only encrypted, then given the
ciphertext, due to semantical security of the encryption, an adversary cannot
tell if the ciphertext corresponds to $\pi_{\scriptscriptstyle j,0}$ or
$\pi_{\scriptscriptstyle j,1}$ (accordingly to $u_{\scriptscriptstyle 0}$ or
$u_{\scriptscriptstyle 1}$) with a probability significantly greater than
$\frac{1}{2}+\mathsf{negl}(\lambda)$, if $Max(|\pi_{\scriptscriptstyle
j,0}|,...,|\pi_{\scriptscriptstyle j,\bar{m}}|)=|\pi_{\scriptscriptstyle
j,\beta}|$. However, the assumption is relaxed with the use of a pad. In
particular, since each encrypted proof is padded to the proofs’ maximum size,
the adversary cannot tell with a probability greater than
$\frac{1}{2}+\mathsf{negl}(\lambda)$ if the padded encrypted proof corresponds
to $\pi_{\scriptscriptstyle j,0}$ or $\pi_{\scriptscriptstyle j,1}$. Also,
since the value of $a$ is independent of $u_{\scriptscriptstyle 0}$ or
$u_{\scriptscriptstyle 1}$, and only depends on whether the metadata is well-
formed, it leaks nothing about the service input
$u_{\scriptscriptstyle\beta}$, $\beta$, the query-proof pair and service
proof. Thus (given
$\bm{c}^{\scriptscriptstyle*},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}},g_{\scriptscriptstyle
cp},g_{\scriptscriptstyle qp},$ $\bm{\pi}^{\scriptscriptstyle*},pl$, and $a$)
the probability that the adversary can tell the value of $\beta$ is at most
$\frac{1}{2}+\mathsf{negl}(\lambda)$, due to IND-CPA security of the
symmetric-key encryption scheme.

Now we move on to case 2, i.e., the privacy of proof’s status. Recall that in
the experiment, an _invalid_ query-proof pair is generated with probability
$Pr_{\scriptscriptstyle 0,j}$ and a _valid_ query-proof pair is generated with
probability $Pr_{\scriptscriptstyle 1,j}$. As stated above, each encoded
query-proof pair $c^{\scriptscriptstyle*}_{\scriptscriptstyle
j}\in\bm{c}^{\scriptscriptstyle*}$ has a fixed size and contains random
elements of $U$, i.e., they are uniformly random elements in the symmetric-key
encryption scheme’s output range. Also, it is assumed that for each $j$-th
verification, an encoded query-proof is always provided to the contract.
Therefore, each encoded pair leaks nothing, not even the query’s status to the
adversary (due to the use of padding and IND-CPA security of the encryption).
So, given only a vector of $c^{\scriptscriptstyle*}_{\scriptscriptstyle j}$
(i.e., $\bm{c}^{\scriptscriptstyle*}$) it can learn a query-proof’s status
with probability at most $Pr^{\prime}+\mu(\lambda)$, where
$Pr^{\prime}:=Max\\{Pr_{\scriptscriptstyle 0,1},Pr_{\scriptscriptstyle
1,1},...,Pr_{\scriptscriptstyle 0,z},Pr_{\scriptscriptstyle 1,z}\\}$. On the
other hand, for each $j$-th verification, an encoded service proof
$\pi_{\scriptscriptstyle
j}^{\scriptscriptstyle*}\in\bm{\pi}^{\scriptscriptstyle*}$ is always provided
to the contract, regardless of the query’s status. As stated above, each
$\pi_{\scriptscriptstyle j}^{\scriptscriptstyle*}$ has a fixed size and
contains random element of $U$ too. As we showed above, $g_{\scriptscriptstyle
cp},g_{\scriptscriptstyle qp},pl$, and $a$ leak no information about the
service input, except with a negligible probability, $\mu(\lambda)$. They are
also independent of the query-proof pair and service proof, so they leak no
information about the pair and service proof too. So, given
$\bm{c}^{\scriptscriptstyle*},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}},g_{\scriptscriptstyle
cp},g_{\scriptscriptstyle qp},$ $\bm{\pi}^{\scriptscriptstyle*},pl$, and $a$,
an adversary has to learn a proof’s status from the aforementioned values or
by correctly guessing a query’s status. In other words, its probability of
learning a proof’ status is at most $Pr^{\prime}+\mu(\lambda)$. ∎

##  Appendix H Trade-offs

As we highlighted in Section 6, to design an efficient RC-S-P we have made
certain trad-offs compared to the previous work in [15]. In this section, we
explain the main trad-offs that we have made.

###  H.1 Involving a Third-party Arbiter

Similar to various works that aim for efficiency (e.g., in [7, 8, 10, 21]) in
the RC-S-P we involved an arbiter third party that remains offline for the
most part of the protocol execution and is invoked only in the case where
parties raise a dispute. This is a trade-off because the original (but
insecure) zkCSP in [15] did not involve any additional (third) party.

Instead, we could allow Ethereum smart contracts to play the arbiter’s role if
we would use only publicly verifiable proofs and delegate the arbiter-side
computations to the smart contracts. However, this would impose a much higher
financial cost on the parties than what RC-S-P does. Because performing a
certain computation by smart contract would cost much more than a third party
performing the same computation locally.

###  H.2 Requiring Parties to Deposit Extra Coins

The amount of coins that the RC-S-P requires parties to deposit is higher than
what zkCSP in [15] requires; for two reasons. First, in the RC-S-P, parties
hide the amount of the deposit by masking it; to do that, they increase the
amount to the maximum amount of coins in the server’s price list. This trade-
off has been made to achieve privacy while keeping the computation cost low.

Second, in the RC-S-P, every party needs to deposit a certain amount to cover
the cost of the arbiter’s computation; this deposit will be transferred to the
arbiter in the case where the arbiter is invoked and the party was identified
as misbehaving; however, when the party is honest, it can retrieve its deposit
when the protocol terminates. This trade-off has been made to efficiently
detect a misbehaving party.

###  H.3 Storing more Messages on Blockchain

In the RC-S-P most of the messages exchanged between the client and server are
stored in the blockchain, unlike the original zkCSK which requires a few
messages to be stored on the blockchain. Therefore, the RC-S-P would impose a
higher communication cost than the zkCSK does. This trade-off has been made to
satisfy the RC-S-P security requirement. Specifically, in the RC-S-P, both
parties can be malicious, whereas the zkCSK (wrongly) assumes that only the
server is malicious. in particular, to ensure a malicious party cannot deny
receiving a message.

###  H.4 Use of Ethereum Smart Contracts

Unlike the original zkCSP that can be implemented in Bitcoin (which supports
very limited functionalities from smart contracts), the RC-S-P relies on
Ethereum smart contracts that support wider functionalities. However, the RC-
S-P relies on very minimal capabilities of Ethereum smart contracts, such as
running very simple functions and distributing deposits according to the
output of the functions. This trade-off has been made to satisfy the RC-S-P
security requirements, e.g., privacy, ensuring a malicious client cannot waste
the server’s resources, and ensuring a fair exchange.

##  Appendix I Further Discussion of the SAP

In this section, first we outline why the SAP satisfies all four security
properties set out in Section 8.1 and then discuss why naive solutions are not
suitable replacements of the SAP. After that, we highlight that the SAP’s
verification phase can be locally performed with low costs.

###  I.1 SAP’s Security Analysis

Intuitively, the SAP meets Property 1 due to the binding property of the
commitment scheme. Property 2 is satisfied due to the security of the
blockchain and smart contract; namely, due to blockchain’s liveness property
an honestly generated transaction, containing the opening, eventually gets
into chains of honest miners, and due to the security and correctness of smart
contracts a valid opening is always accepted by the contract. Property 3 is
met due to the hiding property of the commitment, while Property 4 is
satisfied due to the signature scheme’s security.

###  I.2 Unsuitability of Naive Solutions

As a replacement of the SAP, one may let each party sign the statement and
send it to the other party, so later each party can send both signatures to
the contract which verifies them. However, this would not work, as the party
who first receives the other party’s signature may refuse to send its own
signature, that prevents the other party from proving that it has agreed on
the statement with its counter-party, i.e., cannot satisfy Property 2.
Alternatively, one may want to use a protocol for a fair exchange of digital
signature (or fair contract signing) such as those in [14, 28]. In this case,
after both parties have the other party’s signature, they can sign the
statement themselves and send the two signatures to the contract which first
checks the validity of both signatures. Although this satisfies the four
security requirements, it yields two main _efficiency_ and _practical_ issues;
namely, it (a) imposes very high computation costs, as protocols for a fair
exchange of signatures involve generic zero-knowledge proofs and require a
high number of modular exponentiations, and (b) is impractical because
protocols for the fair exchange of signatures support only certain signature
schemes (e.g., RSA, Rabin, or Schnorr) that are not directly supported by the
most predominant smart contract framework, Ethereum, that only supports
Elliptic Curve Digital Signature Algorithm (EDCSA).

###  I.3 Off-chain Verification in the SAP

The SAP’s verification algorithm can be executed _off-chain_. In particular,
given statement $\ddot{x}$, anyone can read
$(g_{\scriptscriptstyle\mathcal{C}},g_{\scriptscriptstyle\mathcal{S}},adr_{\scriptscriptstyle\mathcal{C}},adr_{\scriptscriptstyle\mathcal{S}})$
from the SAP smart contract and locally run
$\mathtt{SAP.verify}(\ddot{x},g_{\scriptscriptstyle\mathcal{C}},g_{\scriptscriptstyle\mathcal{S}},adr_{\scriptscriptstyle\mathcal{C}},$
$adr_{\scriptscriptstyle\mathcal{S}})$ to check the statement’s correctness.
This relieves the verifier from the transaction and smart contract’s execution
costs.

##  Appendix J RC-PoR-P’s Correctness

In this section, we briefly discuss why the correctness of the RC-PoR-P
protocol holds, w.r.t. Definition 2. Recall, correctness requires that
$\mathcal{S}$ accepts an honest $\mathcal{C}$’s encoded data and query while
honest $\mathcal{C}$ accepts $\mathcal{S}$’s valid service proof. Also, honest
$\mathcal{C}$ gets back all its deposited coins minus the service payment, the
honest $\mathcal{S}$ gets back all its deposited coins plus the service
payment and the arbiter receives nothing. In short, this protocol’s
correctness holds dues to the correctness of PoR, symmetric key encryption,
SAP, and smart contract. Below, we elaborate on that:

  1. 1.

due to the correctness of smart contracts, any message sent by a party (i.e.,
$\mathcal{C}$ or $\mathcal{S}$) to a contract is kept intact by the contract.

  2. 2.

due to the correctness of symmetric key encryption, the encrypted messages
sent by a party to another one can be correctly decrypted by its counterparty
who knows the correct key.

  3. 3.

due to points 1 and 2 above, an encrypted message sent to a contract by a
party can be correctly decrypted by its counterparty who knows the correct
key.

  4. 4.

due to the correctness of the underlying PoR scheme, proofs generated by
honest $\mathcal{S}$ are always accepted by honest $\mathcal{C}$. Also, for
the same reason, a query generated by honest $\mathcal{C}$ is always accepted
by honest $\mathcal{S}$.

  5. 5.

due to points 1-4, the counters remain $0$, i.e.,
$y_{\scriptscriptstyle\mathcal{S}}=y_{\scriptscriptstyle\mathcal{C}}=y^{\prime}_{\scriptscriptstyle\mathcal{S}}=y^{\prime}_{\scriptscriptstyle\mathcal{C}}=0$.

  6. 6.

due to the correctness of SAP and point 1, a private statement’s proof (e.g.,
$\ddot{x}_{\scriptscriptstyle cp}\in T_{\scriptscriptstyle cp}$) sent by an
honest $\mathcal{C}$ or $\mathcal{S}$ will always be accepted by the smart
contract.

Therefore, $\mathcal{C}$ receives
$coin_{\scriptscriptstyle\mathcal{C}}=coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}-o\cdot
z$ coins, $\mathcal{S}$ receives
$coin_{\scriptscriptstyle\mathcal{S}}=coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}+o\cdot
z$, and arbiter receives $0$ coins.

##  Appendix K Proof of Theorem 1

This section contains the security analysis of the RC-PoR-P consrtuction
presented in Section 9. First, we prove the security of the PoR scheme in
Subsection 9.1 in the following lemma.

######  Lemma 5.

Let $\epsilon$ be non-negligible in the security paramenter $\lambda$. Then,
the PoR scheme presented in Subsection 9.1 is $\epsilon$-sound w.r.t.
Definition 8, if the underlying Merkle tree and pseudorandom function
$\mathtt{PRF}$ are secure.

###### Proof (sketch).

As stated above, the proposed PoR differs from the standard Merkle tree-based
PoR by a couple of perspectives. However, the changes do not affect the
security and soundness of the proposed PoR. Its security proof is similar to
the existing Merkle tree-based PoR schemes, e.g., [34, 38, 50]. Alternatively,
our protocol can be proven based on the security analysis of the PoR schemes
that use MACs or BLS signatures, e.g., [56]. In this case, the extractor
design (in the Merkle tree-based PoR) would be simpler because it does not
need to extract blocks from a linear combination of MACs or signatures, as the
blocks are included in proofs, i.e., they are part of the Merkle tree proofs.
Intuitively, in either case, the extractor interacts with any adversarial
prover that passes a non-negligible $\epsilon$ fraction of audits. It
initialises an empty array. Then it challenges a subset of file blocks and
asks the prover (server) to generate a proof. If the received proof passes the
verification, then it adds the related block (in the proof) to the array. It
then rewinds the prover and challenges a fresh set of blocks, and repeats the
process many times. Since the prover has a good chance of passing the audit,
it is easy to show that the extractor can eventually extract a large fraction
of the entire file, as it is shown in [56]. In particular, the following hold:

  1. 1.

Due to the security of the Merkle tree, which relies on the collision
resistance of the utlized hash function, whenever the extractor is convinced
of a prover’s proof of membership, it is ascertained that the retrieved values
are the valid and correct file blocks.

  2. 2.

Due to the security of the pseudorandom function, the challenges
$q_{\scriptscriptstyle i}=\big{(}\mathtt{PRF}(\hat{k},i)\bmod m\big{)}+1$, for
$i=1,\ldots,\phi$ are not predictable by $\mathcal{S}$ before the time that
the server receives the PRF key $\hat{k}$ by $\mathcal{C}$.

After collecting a sufficient number of blocks, the extractor can use the
error-correcting code to decode and recover the entire file blocks, given the
retrieved ones. ∎

By applying Lemma 5, we prove the main theorem of Section 9. Note that, given
the value of a counter, e.g., $y_{\scriptscriptstyle\mathcal{S}}$, we can
easily parse it as a binary vector, e.g.
$y_{\scriptscriptstyle\mathcal{S},1},...,y_{\scriptscriptstyle\mathcal{S},z}$.
This is because each counter is maintained and incremented by the smart
contract, hence the counter’s history/log can be retrieved from the
blockchain.

Theorem 1. _The RC-PoR-P scheme with functions
$F_{\scriptscriptstyle\mathsf{PoR}},M_{\scriptscriptstyle\mathsf{PoR}},E_{\scriptscriptstyle\mathsf{PoR}},$
$D_{\scriptscriptstyle\mathsf{PoR}},Q_{\scriptscriptstyle\mathsf{PoR}}$
described in Subsections 9.1 and 9.2 is secure (cf. Definition 6), if the
underlying Merkle tree, pseudorandom function, commitment scheme, digital
signature scheme are secure, and the underlying symmetric-key encryption
scheme is IND-CPA secure._

###### Proof.

We show that the RC-PoR-P scheme meets all security properties defined in
Section 7 by proving a series of claims. First, we recall that
$coin_{\scriptscriptstyle\mathcal{P},j}$ denotes the coins that are credited
to the party $\mathcal{P}\in\\{\mathcal{C},\mathcal{S},\mathcal{R}\\}$ for the
$j$-th verification and $h_{\scriptscriptstyle j}$ is a value included in the
decoded proof $\mathbf{\pi}_{\scriptscriptstyle j}$ that should match
$F_{\scriptscriptstyle\mathsf{PoR}}(u^{\scriptscriptstyle*},\hat{k}_{\scriptscriptstyle
j},{pp})$. In addition, $y_{\scriptscriptstyle\mathcal{C},j}=1$ (resp.
$y_{\scriptscriptstyle\mathcal{S},j}=1$) if $\mathcal{C}$ (resp.
$\mathcal{S}$) misbehaved in the $j$-th billing cycle, and
$y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=1$ (resp.
$y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=1$) if $\mathcal{C}$ (resp.
$\mathcal{S}$) has provided a complaint that does not allow $\mathcal{R}$ to
identify a misbehaved party in the $j$-th verification .

######  Claim 1.

The RC-PoR-P scheme with functions
$F_{\scriptscriptstyle\mathsf{PoR}},M_{\scriptscriptstyle\mathsf{PoR}},E_{\scriptscriptstyle\mathsf{PoR}},$
$D_{\scriptscriptstyle\mathsf{PoR}},Q_{\scriptscriptstyle\mathsf{PoR}}$ is
secure against a malicious server (cf. Definition 3), if the SAP and signature
scheme are secure, and the PoR scheme satisfies correctness and soundness.

Proof of Claim 1. First, we consider the event
$\Big{(}F_{\scriptscriptstyle\mathsf{PoR}}(u^{\scriptscriptstyle*},\hat{k}_{\scriptscriptstyle
j},{pp})=h_{\scriptscriptstyle j}\
\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{)}\Big{)}$ that
captures the case where the server provides an accepting proof, but one of the
following happen:

  1. 1.

an honest client withdraws an incorrect amount of coins, i.e.,
$coin_{\scriptscriptstyle\mathcal{C},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{C}}^{\scriptscriptstyle*}}{z}-o$,
or

  2. 2.

the arbiter withdraws an incorrect amount of coins, i.e.,
$coin_{\scriptscriptstyle\mathcal{R},j}\neq l$, if the server unnecessarily
invokes the arbiter, i.e., $y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=1$

Because the proof is valid, an honest client accepts it and does not raise a
dispute. However, the server could make the client withdraw incorrect amount
of coins, if it manages to (i) 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 (ii) submit an accepting statement $\ddot{x}^{\prime}_{\scriptscriptstyle
cp}$ to SC which is 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, or (iii) send a message on
the client’s behalf to unnecessarily invoke the arbiter. We argue that in any
of the above three cases, the server cannot falsely accuse the client of
misbehaviour.

First, due to the binding property of the SAP commitment scheme, $\mathcal{S}$
cannot convince the arbiter to accept a different decryption key (that will be
used to decrypt queries) other than what was agreed with the client in the SAP
initiation phase. In particular, 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 $\mathsf{negl}(\lambda)$ probability. This ensures that the
honest client’s queries are accessed by the arbiter with a high probability.
Furthermore, if the adversary provides a valid statement, i.e.,
$\ddot{x}_{\scriptscriptstyle qp}$, then due to the correctness of the PoR and
query-checking process (specified in step 5b), no one is identified as a
misbehaving party in the dispute resolution phase, i.e., so we would have
$I_{\scriptscriptstyle j}=\bot$. Therefore, due to the binding property of SAP
and correctness of PoR and query-checking process, the following holds
$y_{\scriptscriptstyle\mathcal{C},j}=y_{\scriptscriptstyle\mathcal{S},j}=0$.

Moreover, due to the binding property of the SAP commitment scheme, the server
cannot change the payment parameters by convincing the contract to accept any
statement $\ddot{x}^{\prime}_{\scriptscriptstyle cp}$ other than what was
agreed initially between the client and server, except with
$\mathsf{negl}(\lambda)$ probability. Also, due to the EUF-CMA security of the
underlying digital signature scheme, the adversary cannot send a message on
behalf of the client to unnecessarily invoke the arbiter and make it output
$y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=1$, except with
$\mathsf{negl}(\lambda)$ probability; so with high probability, it holds that
$y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=0$. Recall that by the
description of the coin transfer phase, in RC-PoR-P or RC-S-P protocol,
according to Equation (1), the amount of coins that should be credited to the
client for the $j$-th 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})$.
Since it holds that
$y_{\scriptscriptstyle\mathcal{C},j}=y_{\scriptscriptstyle\mathcal{S},j}=y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=0$,
the client is credited
$\frac{coin_{\scriptscriptstyle\mathcal{C}}^{\scriptscriptstyle*}}{z}-o$ coins
for the $j$-th verification, with high probability.

As stated above, if the adversary invokes the arbiter, the arbiter with a high
probability outputs $I_{\scriptscriptstyle j}=\bot$ that yields
$y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=1$. In RC-PoR-P or RC-S-P
protocol, according to Equation 2, the amount of coins the arbiter should be
credited for $j$-th verification is
$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})$.
As shown above
$y_{\scriptscriptstyle\mathcal{C},j}=y_{\scriptscriptstyle\mathcal{S},j}=y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=0$
and $y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=1$, which means $l$ coins is
credited to the arbiter for the $j$-th verification if it is unnecessarily
invoked by the adversary. In this case, for the server to make the arbiter
withdraw other than this amount, it has to send to SC (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. However, as stated above, it
cannot succeed with a probability significantly greater than
$\mathsf{negl}(\lambda)$ due to the binding property of the underlying
commitment scheme.

We now study the event
$\Big{(}\Big{(}F_{\scriptscriptstyle\mathsf{PoR}}(u^{\scriptscriptstyle*},\hat{k}_{\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{)}\Big{)}$, which
captures the case where the server provides an invalid proof and causes at
least one of the following to happen:

  1. 1.

convinces the client/arbiter to accept the proof, or

  2. 2.

persuades the arbiter to consider it as honest, i.e., keep
$y_{\scriptscriptstyle\mathcal{S},j}=0$, or

  3. 3.

makes the client or arbiter withdraw 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.

By the security of the underlying pseudorandom function and the Merkle tree,
Lemma 5 holds, i.e., the tree-based PoR building block is sound. This implies
that (i) the probability that the adversary can convince an honest
client/arbiter to accept invalid proof is $\mathsf{negl}(\lambda)$ and (ii)
the file is extractable within a polynomial number of interactions with an
$\epsilon$-admissible adversary, where $\epsilon$ is some non-negligible
function. Therefore, the client outputs $d_{\scriptscriptstyle j}=0$ with a
high probability and raises a dispute.

Furthermore, the server may try to convince the arbiter that the client has
misbehaved, and output $y_{\scriptscriptstyle\mathcal{C},j}=1$; if it
succeeds, then the arbiter would consider the server as honest. Therefore, it
would keep $y_{\scriptscriptstyle\mathcal{S},j}=0$ (according to the
protocol’s description). In this case, according to RC-PoR-P protocol, if the
honest client sends a complaint, its complaint (for the $j$-th verification)
would not be processed by the arbiter, because the arbiter has already
detected a misbehaving party, i.e., the client in this case. This allows
$y_{\scriptscriptstyle\mathcal{S},j}$ to remain $0$. Nonetheless, as we argued
in the study of the previous event, due to the binding property of the SAP
commitment scheme and the EUF-CMA security of the digital signature scheme,
the probability that the adversary makes the arbiter recognise the client as
misbehaving is $\mathsf{negl}(\lambda)$.

By the above two paragraphs, with high probability the honest client will
raise a dispute and the malicious server cannot convince the arbiter that the
client has misbehaved. This means that, with high probability,
$y_{\scriptscriptstyle\mathcal{S},j}=1$ and
$y_{\scriptscriptstyle\mathcal{C},j}=0$, after the arbiter is invoked by the
client or server.

In addition, it holds that $y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=0$
with a high probability, as the honest client will not unnecessarily invoke
the arbiter and the server cannot send a message to the arbiter (to
unnecessarily invoke it) on behalf of the client (to make the arbiter set
$y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=1$), due to the digital
signature’s EUF-CMA security. Also, it holds that
$y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=0$, because if the malicious
server unnecessarily invokes the arbiter after it is detected, then the
arbiter discards its complaint without carrying out any
investigation/computation as a malicious party (i.e., the server in this case)
has already been identified. Moreover, due to the binding property of the SAP
commitment scheme, the probability that the adversary succeeds in changing the
payment parameters to make the client or arbiter withdraw an incorrect amount
of coins is $\mathsf{negl}(\lambda)$ too. So, according to Equations (1) and
(2) the client and arbiter are credited
$\frac{coin_{\scriptscriptstyle\mathcal{C}}^{\scriptscriptstyle*}}{z}$ and $l$
coins for the $j$-th verification respectively. Also, due to the liveness of
the blockchain and the security and correctness of the smart contract (cf.
Appendix I), the second security property of SAP holds, i.e., after the
parties agree on the statement, an honest party can almost always prove to the
verifier that it has the agreement. Thus, the adversary cannot block an honest
client’s messages, “pay” and $\ddot{x}_{\scriptscriptstyle cp}$, to the
contract in the coin transfer phase. $\dashv$

######  Claim 2.

The RC-PoR-P scheme with functions
$F_{\scriptscriptstyle\mathsf{PoR}},M_{\scriptscriptstyle\mathsf{PoR}},E_{\scriptscriptstyle\mathsf{PoR}},$
$D_{\scriptscriptstyle\mathsf{PoR}},Q_{\scriptscriptstyle\mathsf{PoR}}$ is
secure against a malicious client (cf. Definition 4), if SAP and signature
scheme are secure and the Merkle tree scheme is secure.

Proof of Claim 2. We first consider the event
$\Big{(}\Big{(}M_{\scriptscriptstyle\mathsf{PoR}}(u^{\scriptscriptstyle*},k,{pp})=\sigma\
\wedge\ Q_{\scriptscriptstyle\mathsf{PoR}}(\text{aux},k,$
${pp})=\hat{k}_{\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{)}\Big{)}$. It captures
the case where the client provides accepting metadata (i.e., a Merkle tree and
its root) and query but one the following happen:

  1. 1.

the server withdraws incorrect amount of coins, i.e.,
$coin_{\scriptscriptstyle\mathcal{S},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o$,
or

  2. 2.

the arbiter withdraw incorrect amount of coins, i.e.
$coin_{\scriptscriptstyle\mathcal{R},j}\neq l$, when the client unnecessarily
invokes the arbiter.

Since the metadata and queries are valid and correctly structured, an honest
server accepts them and does not raise a dispute, so
$y_{\scriptscriptstyle\mathcal{C},j}=0$. However, the client could make the
server withdraw an incorrect amount of coins if it manages to (i) persuade the
arbiter to recognise the server as misbehaving, i.e., makes the arbiter output
$y_{\scriptscriptstyle\mathcal{S},j}=1$, or (ii) 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}$, or (iii) send a message on the server’s behalf to unnecessarily invoke
the arbiter. Nevertheless, it cannot falsely accuse the server of
misbehaviour, as, due to the binding property of SAP commitment scheme, it
cannot convince the arbiter to accept different decryption key and pads’
details 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
$\mathsf{negl}(\lambda)$ probability. This ensures that the arbiter is given
the honest server’s messages, with high probability. Therefore, with high
probability, (i) and (ii) cannot happen, implying that
$y_{\scriptscriptstyle\mathcal{S},j}=0$. In addition, (iii) may happen only
with $\mathsf{negl}(\lambda)$ probability, as due to the signature scheme’s
EUF-CMA security, the client cannot send a message on the server’s behalf to
unnecessarily invoke the arbiter.

Moreover, it holds that $y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=0$
because (a) the honest server never invokes the arbiter when the client’s
queries are well-structured and (b) due to the signature scheme’s EUF-CMA
security, the client cannot send a message on the server’s behalf to
unnecessarily invoke the arbiter. Note that, due to the binding property of
the SAP commitment scheme, the client cannot change the payment parameters by
convincing 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 a negligible probability, $\mathsf{negl}(\lambda)$. Recall,
according to Equation 3, in RC-PoR-P or RC-S-P protocol, the total coins the
server should be credited for $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})$.
Therefore, given
$y_{\scriptscriptstyle\mathcal{S},j}=y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=0$,
the server is credited
$\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o$ coins
for the $j$-th verification, with high probability.

Furthermore, as stated above, if the adversary invokes the arbiter, the
arbiter with high probability outputs $I_{\scriptscriptstyle j}=\bot$ which
yields $y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=1$. According to Equation
2, the amount of coins the arbiter should be credited for $j$-th verification
is
$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})$.
As shown above
$y_{\scriptscriptstyle\mathcal{C},j}=y_{\scriptscriptstyle\mathcal{S},j}=y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=0$
and $y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=1$, which implies that with
high probability, $l$ coins are credited to the arbiter for the $j$-th
verification if it is unnecessarily invoked by the adversary.

We now turn our attention to
$\Big{(}M_{\scriptscriptstyle\mathsf{PoR}}(u^{\scriptscriptstyle*},k,{pp})\neq\sigma\
\wedge\ a=1\Big{)}$ which captures the case where the server accepts ill-
formed metadata. However, due to the security of the Merkle tree scheme that
relies on the collision resistance of the utlized hash function, the
probability this event happens is $\mathsf{negl}(\lambda)$; therefore, with a
high probability $a=0$. In this case, the server does not raise any dispute,
instead it avoids serving the client.

Next, we move on to
$\Big{(}(Q_{\scriptscriptstyle\mathsf{PoR}}(\text{aux},k,{pp})\neq\hat{k}_{\scriptscriptstyle
j})\wedge(b_{\scriptscriptstyle j}=1\vee
y_{\scriptscriptstyle\mathcal{C},j}=0\vee
coin_{\scriptscriptstyle\mathcal{S},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o\vee
coin_{\scriptscriptstyle\mathcal{R},j}\neq l)\Big{)}$, i.e. the event that
considers the case where the client provides an invalid query, and causes at
least one of the following to happen:

  1. 1.

convinces the server or arbiter to accept the query, i.e.,
$b_{\scriptscriptstyle j}=1$ or $y_{\scriptscriptstyle\mathcal{C},j}=0$, or

  2. 2.

makes the server or arbiter withdraw an incorrect amount of coins, i.e.,
$coin_{\scriptscriptstyle\mathcal{S},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o$
or $coin_{\scriptscriptstyle\mathcal{R},j}\neq l$ respectively.

Due to the correctness of the query-checking process, the probability that the
server outputs $b_{\scriptscriptstyle j}=1$ is $0$. Note that, when the honest
server rejects the query and raises a dispute, the arbiter checks the query
and sets $y_{\scriptscriptstyle\mathcal{C},j}=1$. After that, due to RC-PoR-P
design, the client cannot make the arbiter set
$y_{\scriptscriptstyle\mathcal{C},j}=0$ (unless it manages to modify the
blockchain’s content later on, but its probability of success is negligible
due to the security of blockchain). As already stated, due to the binding
property of the SAP commitment scheme and the EUF-CMA security of the digital
signature scheme, the client cannot make the arbiter recognise the honest
server as a misbehaving party with a probability significantly greater than
$\mathsf{negl}(\lambda)$. So, with high probability
$y_{\scriptscriptstyle\mathcal{S},j}=0$. Furthermore, since the arbiter has
identified a misbehaving party, it holds that
$y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=0$.
The adversary may still try to make them withdraw incorrect amount of coins.
To this end, in the coin transfer phase, it has to send a different accepting
statement than what was initially agreed with the server. But, due to the
binding property of the SAP commitment scheme, its success probability is
$\mathsf{negl}(\lambda)$. Hence with high probability, according to Equations
3 and 2, for
$y_{\scriptscriptstyle\mathcal{S},j}=y^{\prime}_{\scriptscriptstyle\mathcal{C},j}=y^{\prime}_{\scriptscriptstyle\mathcal{S},j}=0$
and $y_{\scriptscriptstyle\mathcal{C},j}=1$, the server and arbiter are
credited
$\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o$ and
$l$ coins respectively for the $j$-th verification. Furthermore, due to the
liveness of the blockchain and the security and correctness of the smart
contract (cf. Appendix I), the second security property of SAP holds, i.e.,
after the parties agree on the statement, an honest party can almost always
prove to the verifier that it has the agreement. Thus, the adversary cannot
block an honest server’s messages, “pay” and $\ddot{x}_{\scriptscriptstyle
cp}$, to the smart contract in the coin transfer phase. $\dashv$

######  Claim 3.

The RC-PoR-P scheme with functions
$F_{\scriptscriptstyle\mathsf{PoR}},M_{\scriptscriptstyle\mathsf{PoR}},E_{\scriptscriptstyle\mathsf{PoR}},$
$D_{\scriptscriptstyle\mathsf{PoR}},Q_{\scriptscriptstyle\mathsf{PoR}}$
preserves privacy (cf. Definition 5), if SAP is secure and the symmetric-key
encryption scheme is IND-CPA secure.

Proof of Claim 3. First, we show that the scheme guarantees the privacy of the
service input. According to the associated experiment, let
$\mathcal{A}_{\scriptscriptstyle 1}$ be an adversary that given
$pk,F,M,E,D,Q,z,pl$, outputs its choice of challenge files,
$u_{\scriptscriptstyle 0}$ and $u_{\scriptscriptstyle 1}$. Then,
$\mathcal{A}_{\scriptscriptstyle 1}$ is provided with the vector of encrypted
queries $\bm{c}^{\scriptscriptstyle*}$, the parties encoded coins
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}$,
the SAP commitments $g_{\scriptscriptstyle cp},g_{\scriptscriptstyle qp}$,
$\bm{\pi}^{\scriptscriptstyle*}$, the price list $pl$, and the sender’s
decision bit $a$ on the verification of the parameters and the metadata
validity; given the aforementioned input, $\mathcal{A}_{\scriptscriptstyle 1}$
attempts to guess the challenge bit $\beta$.

Due to the hiding property of the commitment scheme, given commitments
$g_{\scriptscriptstyle qp}$ and $g_{\scriptscriptstyle cp}$ (stored in the
blockchain as a result of running SAP), the adversary learns no information
about the committed values (e.g. $o,l,pad_{\scriptscriptstyle\pi}$ and
$\bar{k}$), except with $\mathsf{negl}(\lambda)$ probability. Moreover, given
price list $pl$, $coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}$
and $coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}$, the
adversary learns nothing about the actual price agreed between the server and
client, i.e., $(o,l)$, for each verification, due to Lemma 3. Also, since each
proof $\bm{\pi}^{\scriptscriptstyle*}_{\scriptscriptstyle j}$ is encrypted
with the IND-CPA secure encryption scheme and then padded, given
$\bm{\pi}^{\scriptscriptstyle*}_{\scriptscriptstyle j}$ the adversary cannot
tell whether $\bm{\pi}^{\scriptscriptstyle*}_{\scriptscriptstyle j}$ is
associated with $u_{\scriptscriptstyle 0}$ or with $u_{\scriptscriptstyle 1}$
with probability significantly greater than
$\frac{1}{2}+\mathsf{negl}(\lambda)$. As each
$c^{\scriptscriptstyle*}_{\scriptscriptstyle j}$ is an output of IND-CPA
secure symmetric-key encryption and its size is fixed, it leaks no information
to the adversary. The value of $a$ is also independent of
$u_{\scriptscriptstyle 0}$ or $u_{\scriptscriptstyle 1}$, and only depends on
whether the parameters and metadata are well-formed, so it leaks nothing about
the choice of input file $u_{\scriptscriptstyle\beta}$ and
$\beta\in\\{0,1\\}$. Overall, the adversary $\mathcal{A}_{\scriptscriptstyle
1}$ cannot distinguish with a probability significantly greater than
$\frac{1}{2}+\mathsf{negl}(\lambda)$ which file of its choice has been used as
the server input.

Next, we show that the scheme guarantees privacy of the service proof’s
status. For adversaries $\mathcal{A}_{\scriptscriptstyle 2}$,
$\mathcal{A}_{\scriptscriptstyle 3}$ consider the experiment
$Exp_{\scriptscriptstyle\mathsf{priv}}^{\scriptscriptstyle\mathcal{A}_{2},\mathcal{A}_{3}}(1^{\scriptscriptstyle\lambda})$
defined in Definition 5. Namely, $\mathcal{A}_{\scriptscriptstyle 2}$ is
initially given $pk,F,M,E,D,Q,z,pl$ and outputs a file $u$. After client-side
and server-side initiation steps have been honestly completed,
$\mathcal{A}_{\scriptscriptstyle 2}$ acts as a client that creates potentially
invalid queries that are provided to $\mathcal{A}_{\scriptscriptstyle 3}$
which, in turn, responds with potentially invalid proofs. For each $j$-th
verification, the adversary $\mathcal{A}_{\scriptscriptstyle 2}$ or
$\mathcal{A}_{\scriptscriptstyle 3}$ produces an invalid query or invalid
proof, respectively, with probability $Pr_{\scriptscriptstyle 0,j}$ and a
valid query or valid proof, respectively, with probability
$Pr_{\scriptscriptstyle 1,j}$. Finally, an adversary
$\mathcal{A}_{\scriptscriptstyle 4}$, given
$F,M,E,D,Q,\bm{c}^{\scriptscriptstyle*},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}},g_{\scriptscriptstyle
cp},g_{\scriptscriptstyle qp},\bm{\pi}^{\scriptscriptstyle*},pl,a$ is
challenged to output a proof’s verification bit $d_{\scriptscriptstyle j}$ for
some $j$-th verification. Intuitively, the values $Pr_{\scriptscriptstyle
0,1},Pr_{\scriptscriptstyle 1,1},...,Pr_{\scriptscriptstyle
0,z},Pr_{\scriptscriptstyle 1,z}$ express the “background knowledge” that
$\mathcal{A}_{\scriptscriptstyle 4}$ has on the behavior of
$\mathcal{A}_{\scriptscriptstyle 2}$ and $\mathcal{A}_{\scriptscriptstyle 3}$.

We know that each encoded query $c^{\scriptscriptstyle*}_{\scriptscriptstyle
j}\in\bm{c}^{\scriptscriptstyle*}$ is an IND-CPA encryption of a fresh PRF key
that is always provided to the contract. So,
$c^{\scriptscriptstyle*}_{\scriptscriptstyle j}$ leaks no information (except
with $\mathsf{negl}(\lambda)$ probability), not even the query’s status to the
adversary. Furthermore, each padded IND-CPA encrypted proof
$\bm{\pi}^{\scriptscriptstyle*}_{\scriptscriptstyle j}$ leaks no information
(except with $\mathsf{negl}(\lambda)$ probability) and always contains a fixed
number of elements. Besides, due to the hiding property of the SAP commitment
scheme, the commitments $g_{\scriptscriptstyle cp},g_{\scriptscriptstyle qp}$
leak no information about the committed values (e.g.
$o,l,pad_{\scriptscriptstyle\pi}$ and $\bar{k}$), except with
$\mathsf{negl}(\lambda)$ probability. In addition, the client-side and server-
side initiation steps are carried out honestly in the experiment
$Exp_{\scriptscriptstyle\mathsf{priv}}^{\scriptscriptstyle\mathcal{A}_{2},\mathcal{A}_{3}}(1^{\scriptscriptstyle\lambda})$,
which implies that $a$ is always $1$ and thus, it leaks no information about
the proof and query validity. Finally, $pl$,
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}}$ and
$coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}}$ are generated
independently and contain no information about the query’s or proof’s status.

By the above, the input
$(F,M,E,D,Q,\bm{c}^{\scriptscriptstyle*},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}},g_{\scriptscriptstyle
cp},g_{\scriptscriptstyle qp},\bm{\pi}^{\scriptscriptstyle*},pl,a)$ does not
provide $\mathcal{A}_{\scriptscriptstyle 4}$ with any more than
$\mathsf{negl}(\lambda)$ advantage compared to any background knowledge
$\mathcal{A}_{\scriptscriptstyle 4}$ may have on the behavior of
$\mathcal{A}_{\scriptscriptstyle 2}$ and $\mathcal{A}_{\scriptscriptstyle 3}$.
Therefore, for each $j$-th verification, the probability of
$\mathcal{A}_{\scriptscriptstyle
4}(F,M,E,D,Q,\bm{c}^{\scriptscriptstyle*},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}},g_{\scriptscriptstyle
cp},g_{\scriptscriptstyle qp},\bm{\pi}^{\scriptscriptstyle*},pl,a)$ guessing
$d_{\scriptscriptstyle j}$ is maximized when $\mathcal{A}_{\scriptscriptstyle
4}$ exploits its background knowledge, so it is upper bounded by
$\mathrm{max}\\{Pr_{\scriptscriptstyle 0,j},Pr_{\scriptscriptstyle
1,j}\\}+\mathsf{negl}(\lambda)$. Overall, the probability of
$\mathcal{A}_{\scriptscriptstyle
4}(F,M,E,D,Q,\bm{c}^{\scriptscriptstyle*},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}},g_{\scriptscriptstyle
cp},g_{\scriptscriptstyle qp},\bm{\pi}^{\scriptscriptstyle*},pl,a)$ guessing
$(d_{\scriptscriptstyle j},j)$ for some $j\in\\{1,\ldots,z\\}$ is upper
bounded by

$\begin{split}&\mathrm{max}\big{\\{}\mathrm{max}\\{Pr_{\scriptscriptstyle
0,1},Pr_{\scriptscriptstyle 1,1}\\}+\mathsf{negl}(\lambda),\ldots,\\\
&\quad\mathrm{max}\\{Pr_{\scriptscriptstyle 0,z},Pr_{\scriptscriptstyle
1,z}\\}+\mathsf{negl}(\lambda)\big{\\}}\leq\\\
\leq&\mathrm{max}\big{\\{}\mathrm{max}\\{Pr_{\scriptscriptstyle
0,1},Pr_{\scriptscriptstyle
1,1}\\},\ldots,\mathrm{max}\\{Pr_{\scriptscriptstyle
0,z},Pr_{\scriptscriptstyle 1,z}\\}\big{\\}}+\\\
&\quad+\mathsf{negl}(\lambda)\leq\\\
\leq&\mathrm{max}\big{\\{}Pr_{\scriptscriptstyle 0,1},Pr_{\scriptscriptstyle
1,1},\ldots,Pr_{\scriptscriptstyle 0,z},Pr_{\scriptscriptstyle
1,z}\big{\\}}+\mathsf{negl}(\lambda)=\\\
=&Pr_{\mathrm{max}}+\mathsf{negl}(\lambda)\;,\end{split}$

so the privacy of the service proof is guaranteed. $\dashv$

The security of the construction follows from Claims 1, 2, and 3. ∎

##  Appendix L Further Details on RC-PoR-P Without Arbiter’s Involvement

As already stated, in the RC-PoR protocol, due to the efficiency of the
arbiter-side algorithm we can delegate the arbiter’s role to the smart
contract, SC. To have the new variant of RC-PoR-P, we need to amend the
original RC-PoR-P’s protocol and definition. In the remainder of this section,
we elaborate on how exactly the definition and protocol must change.

###  L.1 Definition of RC-S-P Without Arbiter’s Involvement

There are cases, in RC-S-P schemes, where the third party arbiter’s role can
be efficiently delegated to a smart contract. In this variant of the RC-S-P
scheme, denoted by ${\text{RC-}\overline{\text{S}}\text{-P}}$, the arbiter’s
involvement is not needed anymore. The primary difference between RC-S-P and
${\text{RC-}\overline{\text{S}}\text{-P}}$ is the way a party pays to resolve
a dispute. In particular, in RC-S-P, the party which raises a dispute does not
pay the arbiter when it sends to it a dispute query. Instead, loosely
speaking, the arbiter at coin distribution is paid by a misbehaving party.
Whereas, in ${\text{RC-}\overline{\text{S}}\text{-P}}$, the party which raises
a dispute and sends a dispute query to the contract, (due to the nature of the
smart contracts’ platform) has to pay the contract, before the contract
processes its query. In this section, we show how the RC-S-P definition
(presented in Section 7) can be adjusted to capture
${\text{RC-}\overline{\text{S}}\text{-P}}$. In the following, we highlight the
main changes that should be applied to the RC-S-P definition.

  * $\bullet$

In Definition 1:

    * $\bullet$

Three parties are involved; namely, client, server, and smart contract (so an
arbiter is not involved anymore).

    * $\bullet$

Vectors $\bm{y}^{\prime}_{\scriptscriptstyle\mathcal{C}}$ and
$\bm{y}^{\prime}_{\scriptscriptstyle\mathcal{S}}$ are not needed anymore.
Because a misbehaving party, which unnecessarily invokes the contract, pays
the contract ahead of time. Therefore, there is no need to keep track of
unnecessary contract’s invocation.

    * $\bullet$

$\mathtt{RCSP}.\mathtt{resolve}(\cdot)$ is run by a smart contract.

    * $\bullet$

$\mathtt{RCSP}.\mathtt{pay}(\cdot)$ outputs
$({\bm{coin}}_{\scriptscriptstyle\mathcal{C}},{\bm{coin}}_{\scriptscriptstyle\mathcal{S}})$,
so ${\bm{coin}}_{\scriptscriptstyle\mathcal{R}}$ is excluded from the output,
as a third party arbiter plays no role anymore.

  * $\bullet$

In Definition 2: only the above changes are applied to it.

  * $\bullet$

In Definition 3: the above changes are applied to the algorithms’ syntax in
the experiment. Moreover, the events are slightly modified, i.e. the amount of
coins each party receives. For the sake of clarity and completeness, we state
the entire modified definition below.

######  Definition 17 (${\text{RC-}\overline{\text{S}}\text{-P}}$ Security
Against Malicious Server).

An ${\text{RC-}\overline{\text{S}}\text{-P}}$ scheme with functions
$F,M,E,D,Q$ is secure against a malicious server for auxiliary information
aux, if for any $z$ polynomial in $\lambda$, any price list $pl$, every $j$
(where $1\leq j\leq z$), and any PPT adversary $\mathcal{A}$, the following
probability is $\mathsf{negl}(\lambda)$:

$\Pr\left[{\small{\begin{array}[]{l}\mathtt{RCSP.keyGen}(1^{\lambda},)\rightarrow\bm{k}\\\
\mathcal{A}(1^{\lambda},pk,F,M,E,D,Q,z,pl)\rightarrow u\\\
\mathtt{RCSP}.\mathtt{cInit}(1^{\lambda},u,\bm{k},z,pl)\rightarrow(u^{\scriptscriptstyle*},e,T,p_{\scriptscriptstyle\mathcal{S}},\bm{y},\\\
coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}})\\\
\mathcal{A}(u^{\scriptscriptstyle*},e,pk,z,T,p_{\scriptscriptstyle\mathcal{S}},\bm{y})\rightarrow(coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}},a)\\\
\mathtt{RCSP}.\mathtt{genQuery}(1^{\lambda},\text{aux},k,T_{\scriptscriptstyle
qp})\rightarrow c^{\scriptscriptstyle*}_{\scriptscriptstyle j}\\\
\mathcal{A}(c^{\scriptscriptstyle*}_{\scriptscriptstyle
j},\sigma,u^{\scriptscriptstyle*},a)\rightarrow(b_{\scriptscriptstyle
j},m_{\scriptscriptstyle\mathcal{S},j},h^{\scriptscriptstyle*}_{\scriptscriptstyle
j},\delta^{\scriptscriptstyle*}_{\scriptscriptstyle j})\\\
\mathtt{RCSP}.\mathtt{verify}(\pi^{\scriptscriptstyle*}_{\scriptscriptstyle
j},c^{\scriptscriptstyle*}_{\scriptscriptstyle j},k,T_{\scriptscriptstyle
qp})\rightarrow(d_{\scriptscriptstyle
j},m_{\scriptscriptstyle\mathcal{C},j})\\\
\mathtt{RCSP}.\mathtt{resolve}(m_{\scriptscriptstyle\mathcal{C}},m_{\scriptscriptstyle\mathcal{S}},z,{\bm{\pi}}^{\scriptscriptstyle*},{\bm{c}}^{\scriptscriptstyle*},pk,T_{\scriptscriptstyle
qp})\rightarrow\bm{y}\\\
\mathtt{RCSP}.\mathtt{pay}(\bm{y},T_{\scriptscriptstyle
cp},a,p_{\scriptscriptstyle\mathcal{S}},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}})\rightarrow({\bm{coin}}_{\scriptscriptstyle\mathcal{C}},\\\
{\bm{coin}}_{\scriptscriptstyle\mathcal{S}})\\\
\hline\cr\Big{(}F(u^{\scriptscriptstyle*},\bm{q}_{\scriptscriptstyle
j},{pp})=h_{\scriptscriptstyle j}\
\wedge(coin_{\scriptscriptstyle\mathcal{C},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{C}}^{\scriptscriptstyle*}}{z}-o)\Big{)}\
\vee\\\ \Big{(}F(u^{\scriptscriptstyle*},\bm{q}_{\scriptscriptstyle
j},{pp})\neq h_{\scriptscriptstyle j}\ \wedge\\\ (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}+l})\Big{)}\\\
\end{array}}}\right]$

where $\bm{q}_{\scriptscriptstyle j}\in
D(c^{\scriptscriptstyle*}_{\scriptscriptstyle j},t_{\scriptscriptstyle qp})$,
$\pi^{\scriptscriptstyle*}_{\scriptscriptstyle
j}:=(h^{\scriptscriptstyle*}_{\scriptscriptstyle
j},\delta^{\scriptscriptstyle*}_{\scriptscriptstyle j}),h_{\scriptscriptstyle
j}=D(h^{\scriptscriptstyle*}_{\scriptscriptstyle j},T_{\scriptscriptstyle
qp})$, $\sigma\in e$, $m_{\scriptscriptstyle\mathcal{C},j}\in
m_{\scriptscriptstyle\mathcal{C}},m_{\scriptscriptstyle\mathcal{S},j}\in
m_{\scriptscriptstyle\mathcal{S}}$,
$y_{\scriptscriptstyle\mathcal{S},j}\in\bm{y}_{\scriptscriptstyle\mathcal{S}}\in\bm{y}$,
and ${pp}\in T_{\scriptscriptstyle qp}$.

  * $\bullet$

In Definition 4: similar to the previous point, only the algorithms’ syntax
(in the experiment) and the amount of coins each party receives changes.
Below, we state the entire modified definition.

######  Definition 18 (${\text{RC-}\overline{\text{S}}\text{-P}}$ Security
Against Malicious Client).

An ${\text{RC-}\overline{\text{S}}\text{-P}}$ scheme wih functions $F,M,E,D,Q$
is secure against a malicious client for auxiliary information aux, if for any
$z$ polynomial in $\lambda$, every $j$ (where $1\leq j\leq z$), and any PPT
adversary $\mathcal{A}$, the following probability is
$\mathsf{negl}(\lambda)$:

$\Pr\left[{\small{\begin{array}[]{l}\mathcal{A}(1^{\lambda},F,M,E,Q,D,z,pl)\rightarrow(u^{\scriptscriptstyle*},\bm{k},e,T,p_{\scriptscriptstyle\mathcal{S}},\\\
coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}},enc,\bm{y},enc,pk)\\\
\mathtt{RCSP}.\mathtt{sInit}(u^{\scriptscriptstyle*},e,pk,z,T,p_{\scriptscriptstyle\mathcal{S}},\bm{y})\rightarrow(coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}},a)\\\
\mathcal{A}(coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}},a,1^{\lambda},\text{aux},k,T_{\scriptscriptstyle
qp})\rightarrow c^{\scriptscriptstyle*}_{\scriptscriptstyle j}\\\
\mathtt{RCSP}.\mathtt{prove}(u^{\scriptscriptstyle*},\sigma,c^{\scriptscriptstyle*}_{\scriptscriptstyle
j},pk,T_{\scriptscriptstyle qp})\rightarrow(b_{\scriptscriptstyle
j},m_{\scriptscriptstyle\mathcal{S},j},\pi^{\scriptscriptstyle*}_{\scriptscriptstyle
j})\\\ \mathcal{A}(\pi^{\scriptscriptstyle*}_{\scriptscriptstyle
j},\bm{q}_{\scriptscriptstyle j},k,T_{\scriptscriptstyle
qp})\rightarrow(d_{\scriptscriptstyle
j},m_{\scriptscriptstyle\mathcal{S},j})\\\
\mathtt{RCSP}.\mathtt{resolve}(m_{\scriptscriptstyle\mathcal{C}},m_{\scriptscriptstyle\mathcal{S}},z,{\bm{\pi}}^{\scriptscriptstyle*},{\bm{c}}^{\scriptscriptstyle*},pk,T_{\scriptscriptstyle
qp})\rightarrow\bm{y}\\\
\mathtt{RCSP}.\mathtt{pay}(\bm{y},T_{\scriptscriptstyle
cp},a,p_{\scriptscriptstyle\mathcal{S}},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{C}},coin^{\scriptscriptstyle*}_{\scriptscriptstyle\mathcal{S}})\rightarrow({\bm{coin}}_{\scriptscriptstyle\mathcal{C}},\\\
{\bm{coin}}_{\scriptscriptstyle\mathcal{S}})\\\
\hline\cr\Big{(}(M(u^{\scriptscriptstyle*},k,{pp})=\sigma\wedge
Q(\text{aux},k,{pp})=\bm{q}_{\scriptscriptstyle j})\ \wedge\\\
(coin_{\scriptscriptstyle\mathcal{S},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o)\Big{)}\
\vee\\\ \Big{(}M(u^{\scriptscriptstyle*},k,{pp})\neq\sigma\wedge a=1\Big{)}\
\vee\\\ \Big{(}Q(\text{aux},k,{pp})\neq\bm{q}_{\scriptscriptstyle j}\
\wedge\\\ (b_{\scriptscriptstyle j}=1\ \vee\
y_{\scriptscriptstyle\mathcal{C},j}=0\
\vee{coin_{\scriptscriptstyle\mathcal{S},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o+l})\Big{)}\\\
\end{array}}}\right]$

where $\bm{q}_{\scriptscriptstyle j}\in
D(c^{\scriptscriptstyle*}_{\scriptscriptstyle j},t_{\scriptscriptstyle qp})$,
$D\in enc$, $\sigma\in e$,
$y_{\scriptscriptstyle\mathcal{C},j}\in\bm{y}_{\scriptscriptstyle\mathcal{C}}\in\bm{y}$,
and ${pp}\in T_{\scriptscriptstyle qp}$.

Note that Definition 5 remains almost the same with a minor change, that is
vectors
$(\bm{y}^{\prime}_{\scriptscriptstyle\mathcal{C}},\bm{y}^{\prime}_{\scriptscriptstyle\mathcal{S}})$
are excluded from the related algorithms input/output.

######  Definition 19.

An ${\text{RC-}\overline{\text{S}}\text{-P}}$ scheme is secure if it satisfies
security against malicious server, security against malicious client, and
preserves privacy (cf. . Definitions 17,18, and 5).

###  L.2 Protocol For RC-PoR-P Without Arbiter’s Involvement

Below we present the modifications that must be applied to the phases 7 and 8
of the RC-PoR-P protocol to allow the smart contract to play the role of the
auditor.

  1. 7.

Dispute Resolution.
$\mathtt{RCPoRP}.\mathtt{resolve}(m_{\scriptscriptstyle\mathcal{C}},m_{\scriptscriptstyle\mathcal{S}},z,{\bm{\pi}}^{\scriptscriptstyle*},\bm{q}^{\scriptscriptstyle*},T_{\scriptscriptstyle
qp})$

The phase takes place only in case of dispute, i.e., when $\mathcal{C}$
rejects service proofs or $\mathcal{S}$ rejects the queries.

    1. (a)

$\mathcal{S}$ sends ${m}_{\scriptscriptstyle\mathcal{S}}$ and
$\ddot{x}_{\scriptscriptstyle qp}$ to SC, at time
$\texttt{K}_{\scriptscriptstyle 1}$, where $\texttt{K}_{\scriptscriptstyle
1}>\texttt{G}_{\scriptscriptstyle z,2}+\texttt{J}$

    2. (b)

SC upon receiving ${m}_{\scriptscriptstyle\mathcal{S}}$ does the following a
time $\texttt{K}_{\scriptscriptstyle 2}$.

      1. i.

Checks the validity of statement $\ddot{x}_{\scriptscriptstyle qp}$, by
sending it to the SAP contract which returns $1$ or $0$. If the output is $0$,
then SC discards the server’s complaint, $m_{\scriptscriptstyle\mathcal{S}}$,
and does not take steps 7(c)ii and 7(c)iii. Otherwise, it proceeds to the next
step.

      2. ii.

Removes from ${\bm{v}}_{\scriptscriptstyle\mathcal{S}}$ any element that is
duplicated or not in the range $[1,z]$. It also constructs an empty vector
${\bm{v}}$.

      3. iii.

For any element $i\in{\bm{v}}_{\scriptscriptstyle\mathcal{S}}$:

         * $\bullet$

Fetches the related encrypted query
$\hat{k}^{\scriptscriptstyle*}_{\scriptscriptstyle
i}\in\bm{q}^{\scriptscriptstyle*}$, and decrypts it,
$\hat{k}_{\scriptscriptstyle
i}=\mathtt{Dec}(\bar{k},\hat{k}^{\scriptscriptstyle*}_{\scriptscriptstyle
i})$.

         * $\bullet$

Checks if the query is well-formed, by doing the same checks performed in step
5b (of the RC-PoR-P). If the query is rejected, then it increments
$y_{\scriptscriptstyle\mathcal{C}}$ by $1$ and appends $i$ to ${\bm{v}}$.

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

    3. (c)

$\mathcal{C}$ sends $m_{\scriptscriptstyle\mathcal{C}}$ and
$\ddot{x}_{\scriptscriptstyle qp}$ to SC, at time
$\texttt{K}_{\scriptscriptstyle 4}$.

    4. (d)

SC upon receiving $m_{\scriptscriptstyle\mathcal{C}}$, does the following at
time $\texttt{K}_{\scriptscriptstyle 5}$.

      1. i.

Checks the validity of statement $\ddot{x}_{\scriptscriptstyle qp}$, by
sending $\ddot{x}_{\scriptscriptstyle qp}$ to the SAP contract which returns
either $1$ or $0$. If the output is $0$, then SC discards the client’s
complaint, ${m}_{\scriptscriptstyle\mathcal{C}}$, and does not take steps
7(e)ii-7(e)iii. Otherwise, it proceeds to the next step.

      2. ii.

Ensures each vector ${\bm{m}}\in{\bm{m}}_{\scriptscriptstyle\mathcal{C}}$ is
well-formed. In particular, it verifies there exist no two vectors:
${\bm{m}},{\bm{m}}^{\prime}\in{\bm{m}}_{\scriptscriptstyle\mathcal{C}}$ such
that ${\bm{m}}[0]={\bm{m}}^{\prime}[0]$. If such vectors exist, it deletes the
redundant ones from ${\bm{m}}_{\scriptscriptstyle\mathcal{C}}$. This ensures
no two claims refer to the same verification. Also, it removes any vector
${\bm{m}}$ from ${\bm{m}}_{\scriptscriptstyle\mathcal{C}}$ if ${\bm{m}}[0]$ is
not in the range $[1,z]$ or if ${\bm{m}}[0]\in{\bm{v}}$. Note the latter check
(i.e., ${\bm{m}}[0]\in{\bm{v}}$) ensures $\mathcal{C}$ cannot hold
$\mathcal{S}$ accountable if $\mathcal{C}$ has generated an ill-formed query
for the same verification.

      3. iii.

For every vector ${\bm{m}}\in{\bm{m}}_{\scriptscriptstyle\mathcal{C}}$:

        1. A.

retrieves a rejected proof’s details by setting $j={\bm{m}}[0]$ and
$g={\bm{m}}[1]$. Recall that $g$ refers to the index of a rejected proof in
the proof vector which was generated for $j$-th verification, i.e.,
${\bm{\pi}}_{\scriptscriptstyle j}$.

        2. B.

fetches the related encrypted query
$c^{\scriptscriptstyle*}_{\scriptscriptstyle
j}\in\bm{c}^{\scriptscriptstyle*}$ from SC and decrypts it as
$\hat{k}_{\scriptscriptstyle
j}=\mathtt{Dec}(\bar{k},c^{\scriptscriptstyle*}_{\scriptscriptstyle j})$. It
removes the pads only from $g$-th padded encrypted proof. Let
${\bm{\pi}}^{\prime}_{\scriptscriptstyle j}[g]$ be the result. Next, it
decrypts the encrypted proof,
$\mathtt{Dec}(\bar{k},{\bm{\pi}}^{\prime}_{\scriptscriptstyle
j}[g]))={\bm{\pi}}_{\scriptscriptstyle j}[g]$.

        3. C.

identifies the misbehaving party as follows.

           * •

verifies $\hat{k}_{\scriptscriptstyle j}$ by doing the same checks done in
step 5b (of the RC-PoR-P). If the checks do not pass, it sets
$I_{\scriptscriptstyle j}=\mathcal{C}$ and skips the next two steps;
otherwise, it proceeds to the next step.

           * •

derives the related challenged block’s index from $\hat{k}_{\scriptscriptstyle
j}$, by computing $q_{\scriptscriptstyle
g}=\big{(}\mathtt{PRF}(\hat{k}_{\scriptscriptstyle j},g)\bmod m\big{)}+1$.

           * •

verifies only $g$-th proof, by calling
$\mathtt{PoR.verify}({\bm{\pi}}_{\scriptscriptstyle j}[g],$
$q_{\scriptscriptstyle g},$ $pp)\rightarrow{\bm{d}}^{\prime}$. If
${\bm{d}}^{\prime}[0]=0$, then it sets $I_{\scriptscriptstyle j}=\mathcal{S}$.
Otherwise, it outputs $I_{\scriptscriptstyle j}=\bot$.

           * •

if $I_{\scriptscriptstyle j}=\mathcal{C}$, it increments
$y_{\scriptscriptstyle\mathcal{C}}$ by $1$. If $I_{\scriptscriptstyle
j}=\mathcal{S}$, it increments $y_{\scriptscriptstyle\mathcal{S}}$ by $1$.

Let $\texttt{K}_{\scriptscriptstyle 6}$ be the time that SC finishes all the
above checks.

  2. 8.

Coin Transfer.
$\mathtt{\mathtt{RCPoRP}}.\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}_{\scriptscriptstyle 2}$,
where $a=0$ or
$coins^{\scriptscriptstyle*}_{\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}$. Otherwise (i.e., they reach an agreement), they take the
following step.

    2. (b)

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

    3. (c)

SC checks the validity of the statement by sending it to the SAP contract that
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*}_{\scriptscriptstyle\mathcal{C}}-o\cdot(z-y_{\scriptscriptstyle\mathcal{S}})+l\cdot(y_{\scriptscriptstyle\mathcal{S}}-y_{\scriptscriptstyle\mathcal{C}})$
coins to $\mathcal{C}$.

       * $\bullet$

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

######  Theorem 4.

The ${\text{RC-}\overline{\text{PoR}}\text{-P}}$ protocol is secure, w.r.t.
Definition 19, if PoR and SAP are secure and correct and the encryption scheme
is IND-CPA secure.

###  L.3 Proof of the RC-PoR-P Without Arbiter

To prove Theorem 4, we show that ${\text{RC-}\overline{\text{PoR}}\text{-P}}$
meets all security properties defined in Appendix L.1. We start by proving
that ${\text{RC-}\overline{\text{PoR}}\text{-P}}$ meets security against a
malicious server. The proof to some extent is simpler to that of RC-PoR-P
against a malicious server (i.e., proof of Claim 1) as it does not involve any
third party arbiter.

######  Lemma 6.

If the SAP is secure, and the PoR scheme satisfies correctness and soundness,
then ${\text{RC-}\overline{\text{PoR}}\text{-P}}$ is secure against a
malicious server, w.r.t. Definition 17.

###### Proof.

First, we consider event

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

that captures the case where the server provides an accepting proof, i.e. PoR,
but makes an honest client withdraw incorrect amounts of coin, i.e.,
$coin_{\scriptscriptstyle\mathcal{C},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{C}}^{\scriptscriptstyle*}}{z}-o$.
Note, in ${\text{RC-}\overline{\text{PoR}}\text{-P}}$ 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{S}}-y_{\scriptscriptstyle\mathcal{C}})$.
Since we focus on $j$-th verification, the amounts of coin that should be
credited to the client for this 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{S},j}-y_{\scriptscriptstyle\mathcal{C},j})$
(4)

As the proof is valid, an honest client accepts it and does not raise any
dispute. But, the server would be able to make the client withdraw incorrect
amounts of coin, if it manages to either convince the contract that the client
has misbehaved, by making the contract output
$y_{\scriptscriptstyle\mathcal{C},j}=1$ through the dispute resolution phase,
or 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$. Nevertheless, it cannot falsely accuse the
client of misbehaviour. As, due to the security of SAP (i.e., the binding
property of the underlying commitment scheme), it cannot convince the contract
to accept different query’s parameters other than what was agreed with the
client in the initiation phase. In particular, it cannot persuade the contract
to accept $\ddot{x}^{\prime}_{\scriptscriptstyle qp}$ such that
$\ddot{x}^{\prime}_{\scriptscriptstyle qp}\neq\ddot{x}_{\scriptscriptstyle
qp}$, except with a negligible probability, $\mathsf{negl}(\lambda)$.
Furthermore, if the adversary provides a valid statement then, then due to the
correctness of the PoR and query-checking process, values
$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 of the used commitment
scheme), 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 $\mathsf{negl}(\lambda)$. Therefore, according
to Equation 4, the client is credited
$\frac{coin_{\scriptscriptstyle\mathcal{C}}^{\scriptscriptstyle*}}{z}-o$ coins
for the $j$-th verification, with a high probability. We now move on to event

$F(u^{\scriptscriptstyle*},\bm{q}_{\scriptscriptstyle j},{pp})\neq
h_{\scriptscriptstyle j}\ \wedge$ $(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}+l})$

It captures the case where the server provides an invalid proof however either
persuades the client to accept the proof, or persuades the contract to set
$y_{\scriptscriptstyle\mathcal{S},j}=0$ or makes the client withdraw incorrect
amounts of coin, i.e.
$coin_{\scriptscriptstyle\mathcal{C},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{C}}^{\scriptscriptstyle*}}{z}+l$.
Nevertheless, due to the soundness of PoR, the probability that a corrupt
server can convince an honest client to accept invalid proof, i.e. outputs
$d_{\scriptscriptstyle j}=1$, is negligible, $\mathsf{negl}(\lambda)$. So, the
client detects it with a high probability and raises a dispute. Also, the
server may try to make the contract keep
$y_{\scriptscriptstyle\mathcal{S},j}=0$. For
$y_{\scriptscriptstyle\mathcal{S},j}=0$ to happen, it has to make the contract
recognise the client as the misbehaving party, i.e., makes the contract output
$y_{\scriptscriptstyle\mathcal{C},j}=1$. In this case, the client’s complaint
would not be processed by the contract; therefore,
$y_{\scriptscriptstyle\mathcal{S},j}$ remains $0$. Nevertheless, as we
discussed above (due to the binding property of the commitment), the
probability that the adversary makes the contract recognise the client as
misbehaving is negligible, $\mathsf{negl}(\lambda)$. Therefore, with a high
probability $y_{\scriptscriptstyle\mathcal{S},j}=1$ and
$y_{\scriptscriptstyle\mathcal{C},j}=0$, after the contract is invoked by the
client or server. The adversary may try to make the client withdraw incorrect
amounts of coin, e.g., in the case where it does not succeed in convincing the
client or contract. To do so, 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,
$\mathsf{negl}(\lambda)$, due to the security of SAP, i.e., the binding
property of the commitment. So, according to Equation 4, the client is
credited
$\frac{coin_{\scriptscriptstyle\mathcal{C}}^{\scriptscriptstyle*}}{z}+l$ coins
for the $j$-th verification, with a high probability. ∎

Next, we prove that ${\text{RC-}\overline{\text{PoR}}\text{-P}}$ satisfies
security against a malicious client. The proof is also slightly simpler than
that of RC-PoR-P against a malicious client (i.e., proof of Claim 2) as it
does not involve any third party arbiter.

######  Lemma 7.

If SAP and the PoR’s Merkle tree scheme are secure, then
${\text{RC-}\overline{\text{PoR}}\text{-P}}$ is secure against a malicious
client, w.r.t. Definition 18.

###### Proof.

First, we consider event

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

It captures the case where the client provides accepting metadata and query
but makes the server withdraw an incorrect amounts of coin, i.e.
$coin_{\scriptscriptstyle\mathcal{S},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o$.
According to ${\text{RC-}\overline{\text{PoR}}\text{-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{C}}-y_{\scriptscriptstyle\mathcal{S}})$.
As we focus on $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{C},j}-y_{\scriptscriptstyle\mathcal{S},j})$
(5)

Since the metadata and query are valid, an honest server accepts them and does
not raise any dispute, so we have $y_{\scriptscriptstyle\mathcal{C},j}=0$. The
client however could make the server withdraw incorrect amounts of coin, if it
manages to either convince the contract, in the dispute resolution phase, that
the server has misbehaved, i.e., makes the contract 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 the coin transfer phase. But, it cannot falsely accuse the server of
misbehaviour, because due to the security of SAP (i.e., the commitment’s
binding property), it cannot convince the contract 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 a
negligible probability, $\mathsf{negl}(\lambda)$. 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 the PoR and query-checking process, we would have
$I_{\scriptscriptstyle j}=\bot$. Thus, due to the security of SAP and the
correctness of the PoR and query-checking process, we would have
$y_{\scriptscriptstyle\mathcal{C},j}=y_{\scriptscriptstyle\mathcal{S},j}=0$
with a high probability. Also, due to the security of SAP (i.e., the
commitment’s binding property), the client cannot change the payment
parameters by convincing the contract to accept any accepting 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 a negligible probability, $\mathsf{negl}(\lambda)$. That
means, according to Equation 5, the server is credited
$\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o$ coins
for that verification, with a high probability. We now move on to

$\Big{(}M(u^{\scriptscriptstyle*},k,{pp})\neq\sigma\ \wedge\ a=1\Big{)}$

It captures the case where the server accepts ill-formed metadata. But, due to
the security of the PoR’s Merkle tree scheme (i.e., the collision resistance
of the underlying hash function), the probability of the event happening is
negligible, $\mathsf{negl}(\lambda)$. So, with a high probability $a=0$; in
this case, the server does not raise any dispute, instead it avoids serving
the client. Next, we turn our attention to

$\Big{(}Q(\text{aux},k,{pp})\neq\bm{q}_{\scriptscriptstyle j})\ \wedge$
$(b_{\scriptscriptstyle j}=1\ \vee\ y_{\scriptscriptstyle\mathcal{C},j}=0\
\vee\
coin_{\scriptscriptstyle\mathcal{S},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o+l)\Big{)}$

It considers the case where the client provides an invalid query, but either
convinces the server or contract to accept it, or makes the server withdraw
incorrect amounts of coin, i.e.
$coin_{\scriptscriptstyle\mathcal{S},j}\neq\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o+l$.
Due to the correctness of the query-checking process, the probability that the
server outputs $b_{\scriptscriptstyle j}=1$ is $0$. When the honest server
rejects the query and raises a dispute, the contract checks the server’s query
and sets $y_{\scriptscriptstyle\mathcal{C},j}=1$. Also, as discussed above
(due to the commitment’s binding property), the client cannot make the
contract recognise the honest server as a misbehaving party with a probability
significantly greater than $\mathsf{negl}(\lambda)$. That means with a high
probability $y_{\scriptscriptstyle\mathcal{S},j}=0$. The adversary may still
try to make the server withdraw incorrect amounts of coin (e.g., if the
adversary does not succeed in convincing the server). To this end, at the coin
transfer phase, it has to convince the contract to accept a different
statement than what was initially agreed with the server. However, due to the
security of SAP, its success probability is negligible,
$\mathsf{negl}(\lambda)$. Hence, according to Equation 5, the server is
credited
$\frac{coin_{\scriptscriptstyle\mathcal{S}}^{\scriptscriptstyle*}}{z}+o+l$
coins for the $j$-th verification. ∎

In the following, we provide a lemma for
${\text{RC-}\overline{\text{PoR}}\text{-P}}$’s privacy. For the lemma’s proof,
we refer readers to the proof of Claim 3.

######  Lemma 8.

If SAP is secure and the encryption scheme is IND-CPA secure, then
${\text{RC-}\overline{\text{PoR}}\text{-P}}$ preserves privacy, w.r.t.
Definition 5.

##  Appendix M A Table Summarizing RC-PoR-P Assymptotic Costs

Table IV:  RC-PoR-P asymptotic complexity, of $z$ verifications, breakdown by
parties.

Phase | Party | Computation Cost | Communication Cost
---|---|---|---
Client-side and Server-side Init. |  Client | $O(m)$ | $O(||u^{*}||)$
(i.e., outsourcing: 2 and 3) | Server | $O(m)$ | $O(1)$
|  Client | $O(z\phi\log_{\scriptscriptstyle 2}(m))$ | $O(z\log_{\scriptscriptstyle 2}(||u^{\scriptscriptstyle*}||))$
|  Server | $O(z\phi\log_{\scriptscriptstyle 2}(m))$ | $O(z||\bm{\pi}^{\scriptscriptstyle*}_{\scriptscriptstyle j}||)$
|  Arbiter | $O(z^{\prime}\log_{\scriptscriptstyle 2}(m))$ | $O(1)$
The rest of phases (i.e., 4\- 8) | Smart Contract | $O(1)$ | -

Table IV summarizes the RC-PoR-P’s asymptotic costs of $z$ verifications,
breakdown by parties. In the table, $\phi$ is the number of challenged blocks,
$z^{\prime}$ is the maximum number of complaints the client and server send to
the arbiter, $m$ is the number of blocks in a file,
$||{u^{\scriptscriptstyle*}}||$ is the file bit-size, and
$||\bm{\pi}^{\scriptscriptstyle*}||$ is the number of elements in the padded
encrypted proof vector.