




\section{Introduction}
Outsourcing data storage (e.g., Dropbox, Amazon S3) is a common computing paradigm in clouds with advantages in accessibility, cost effectiveness, availability, etc. However, in emerging security-sensitive applications such as Internet-of-things (IoT) and healthcare, cloud clients may feel reluctant to share personal data with the third-party cloud; this lack of trust becomes increasingly concerning with emerging cloud incidents (external hacks as in CloudFlare case, or untrusted cloud companies as in the Facebook-Cambridge-Analytica case). It becomes an important and urgent research task to enhance the security and trustworthiness of the public cloud. 

An important property of cloud service is the data-storage consistency, which dictates the ordering of reads/writes across clients and the freshness of data reads. In security-sensitive applications, such as public-key directory supporting key revocation, the directory consistency directly affects the key freshness. Returning a revoked key leads to consequences such as the unauthorized access to confidential data.
There are existing real attacks (e.g., man-in-the-middle attacks) that compromise storage consistency and returns stale results. 
Note that even when the cloud is end-to-end encrypted, consistency attacks can still be pulled off~\cite{DBLP:conf/wdag/OpreaR06}.

Consistency verification is an important measure that gives data control back to client and defends man-in-the-middle attacks by a malicious cloud. In practice, consistency verification can help enforce consistency-based service level agreement~\cite{DBLP:conf/sosp/TerryPKBAA13} and boost clients' trust in the cloud.

In theory, verifying the consistency of remote storage entails establishing a consistent view of operation history across clients (W1) and audit the log for storage consistency (W2). Most existing work, including SUNDR~\cite{DBLP:conf/osdi/LiKMS04}, Caelus~\cite{DBLP:conf/sp/KimL15}, CloudProof~\cite{DBLP:conf/usenix/PopaLMWZ11}, etc., rely on trusted clients to carry out these functions (i.e., W1,W2). The cumbersome work imposed on clients renders the protocols impractical for emerging cloud applications where clients are increasingly low power such as IoT devices.

Instead of trusting only clients, it is promising to design a lightweight verification protocol by assuming a trusted third party (TTP). 
A lightweight verification protocol lends itself to emerging application scenarios such as in mobile clouds with batter-power client devices, and IoT devices deployed in rural areas with unreliable networks and low availability.
A modern TTP candidate is the Blockchain technology that underlies existing deployed cryptocurrency like BitCoin and Ethereum. In this work, we propose Blockchain-based log auditing for consistency guarantees. The approach is to delegate to the Blockchain TTP the cumbersome consistency-related computations (W1 and W2), such that the low-power clients are relieved from them. 

Note that this approach is different from Catena~\cite{DBLP:conf/sp/TomescuD17} and few related works for Blockchain-based public logging. The Catena style work focuses on logging application-level statements and the prevention of forking attacks. Log auditing for consistency in Catena still rely on clients and as mentioned it incurs high client costs, impractical for low-power clients. A detailed analysis of related work is presented in \S~\ref{sec:analsysisexisting}.

We propose ContractChecker, a security protocol and middleware system for the Blockchain-based consistency log auditing. 
ContractChecker uniquely delegates the log auditing to blockchain for lightweight consistency guarantees.
This approach mitigates the limitations of existing client-based work for log auditing. 
To do so, ContractChecker expresses the logic of consistency checks in smart contract programs and runs these programs on the Blockchain. The security of ContractChecker against a malicious storage server stems from the truthful execution of smart contract programs. A client's overhead is reduced to checks and computations based on the state of local operations.

The use of Blockchain in ContractChecker, while ensuring the security in some aspect, presents new challenges in security and cost-effectiveness: First, the long delay of finalizing a transaction in Blockchain invites new attacks. Specifically, updating a state stored on the Blockchain takes a long time to finalize. If the logical checks on chain are not well coordinated with the life cycle of an on-chain state update, it opens a time window to invite new attacks. The new attacks can be launched by the untrusted server in collusion with malicious minority miners. To fix this security issues, we propose an attack-resilient scheduling where the on-chain checks occur only after the finalization of collected operations on the Blockchain. 

Second, the high cost in running programs on Blockchain is in conflict with the cost-effectiveness of cloud storage. The baseline designs by logging every operation in a dedicated transaction and by storing the entire dataset on chain would lead to high cost as sending an empty transaction and writing a data unit on chain charges high fee. The high cost is in conflict with the very first reason of outsourcing data to the cloud storage, the cost effectiveness. To improve the cost effectiveness, we propose techniques exploring the design choices of on-/off-chain storage and operation-transaction batching, etc.

We build a prototype system materializing the ContractChecker design on Ethereum. We write smart contracts expressing the logical checks and cryptographic operations on chain. We conduct comprehensive security analysis by considering existing consistency attacks and new Blockchain-specific attacks. We evaluate the cost effectiveness of the optimization techniques proposed in ContractChecker; we conducted extensive experiments by micro-benchmark measurement studies and macro-benchmark evaluation with YCSB. The results show that ContractChecker reduces the Blockchain cost by up to $42\%$ and incurs low cost per operations.

The contributions of this work include the following:

1. {\bf New approach}: This work proposes a new use of Blockchain for cloud-storage verification. Unlike existing research, the work leverages Blockchain for both forking-secure logging and delegated log auditing (\S~\ref{sec:analsysisexisting}). 

2. {\bf New security protocols}: New security attacks are identified due to the new use of Blockchain, and new security protocols that schedule the on-chain events for consistency checking are proposed.

3. {\bf New cost optimization}: Delegated log auditing requires placing individual operations on chain. To save the cost, we propose a series of techniques for reducing the Blockchain cost for practical use. The techniques are proposed by examining the design space in on-chain/off-chain log storage, operation batching and compression, etc.

4. {\bf Prototyping and evaluation}: We implement the proposed design in Ethereum. We conduct extensive study, both micro-benchmarks and macro-benchmarks based on industrial-standard YCSB framework. Our study shows the cost effectiveness of the ContractChecker protocol.

\section{Research Formulation}
\subsection{Preliminaries}
\subsubsection{Secure Consistency Verification Protocols}
\label{sec:rw:consistency}
Verifying the consistency of untrusted storage entails two steps: establishing a global log from clients and untrusted server and auditing the log to ensure the consistency. In the logging step, a trusted third party (TTP) is assumed to be an attester: The server attests to the global log against the TTP attester and the clients verify the global-log attestation is correct. The purpose of the attester is to ensure there is only a single view of the global log and to prevent the server from forking. Without the TTP attester, the server can launch forking attacks by attesting to different log views when asking different clients to verify.

SUNDR~\cite{DBLP:conf/osdi/LiKMS04} is a client-oriented logging scheme that removes the attester TTP and achieves fork consistency. Concretely, instead of asking the untrusted server to send attestation to an TTP attester, SUNDR sends the server attestation directly to individual clients. This essentially distributes the role of attester among multiple clients. A security implication of this new design is that the system is vulnerable to the server launching forking attacks (the server attesting to different log views with different clients). SUNDR achieves the so-called fork consistency, that is, the forking attack is made detectable and \emph{any attempt to conceal forks, such as merging forks, is prevented in SUNDR}. The detection can be done by an external mechanism, such as client gossiping. In mechanism design, SUNDR uses a succinct data structure, version vector (VST), to represent the server attestation to individual clients and operations.

Caelus~\cite{DBLP:conf/sp/KimL15} follows the TTP attester design by rotating (or time-sharing) the attester among a group of personal devices. Caelus carries out the log attestation/verification in epoch and audits the log for verifying a variety of consistency models.

Catena~\cite{DBLP:conf/sp/TomescuD17} is Blockchain-based logging scheme where the Blockchain plays the role of TTP attester. Catena \emph{prevents} server forking attack by re-purposing Blockchain security in preventing double-spending attacks. To achieve this, Catena reduces a successful forking attack to two double-spending transactions, and the reduction is realized by extra logical checks in log verification. 

\subsubsection{Blockchains and Smart Contract}
Blockchain is the backend system that underlies today's cryptocurrencies such as BitCoin and Ethereum. To support cryptocurrency, the Blockchain stores the transaction history in cryptocurrency and arbitrates transaction validity. 

The Blockchain runs on a peer-to-peer network where the trust is decentralized over peers and the system is large enough such that it is practical to assume the majority of peer nodes are honest (honest majority). The honest majority assumption is critical to the security of Blockchain system. In order to reach the large scale, the Blockchain's internal design features two goals: 1) Open-membership in the sense that anyone can freely join without registration or even disclosing her identity, and 2) Incentive compatibility in the sense that prospective Blockchain nodes are incentivized to join the network, with rewards for their honest behavior.

The Blockchain system exposes different interfaces to external players and performs different cryptocurrency functions: First, the Blockchain is a storage system of transaction history. Second, the Blockchain is a cryptocurrency mine that rewards the nodes joining the system and behaving honestly. Third, the Blockchain, especially the latest version such as Ethereum, is a trusted program-execution platform exposing programming language, e.g., smart contract, to the developers.

As a storage system, the Blockchain stores the history of cryptocurrency transactions. The storage is publicly readable (transparency). It supports a transaction write by append-only operations without overwriting existing transactions. A transaction, once finalized in the Blockchain, becomes immutable and its on-chain status cannot be changed. The Blockchain validates transactions and admits only valid ones in the Blockchain. One of the basic validation rules is no double-spending transactions.

As a smart-contract execution platform, the Blockchain supports secure, non-stoppable program execution which is essential for ensuring transaction fairness. In BitCoin, it supports programs written in domain-specific languages (i.e., BitCoin Script) to extend the transaction validation logic. In Ethereum, it supports the programming in a Turing-complete language and general-purpose applications. 

\subsection{Analysis of Existing Work}
\label{sec:analsysisexisting}

Recall that consistency verification entails operation logging and consistency auditing. In the classic client-server setting, there are protocols proposed for secure logging against forking attacks and trusted consistency auditing. SUNDR~\cite{DBLP:conf/osdi/LiKMS04} is a logging scheme against malicious server.
Without any trusted third-party, SUNDR achieves the security level of fork consistency, that is, making the forking attack detectable. SUNDR does not address fork prevention or the log auditing. Caelus~\cite{DBLP:conf/sp/KimL15} tackles fork prevention by assuming a trusted-third party (TTP) for log attestation. It replicates the log across clients and rely on clients to conduct log auditing for consistency. CloudProof~\cite{DBLP:conf/usenix/PopaLMWZ11} similarly relies on a TTP (data owner) to record operation history and to audit the history for consistency.

Catena re-purposes Blockchain for an efficient log attestation scheme preventing forking attacks. Catena does not address the log auditing or consistency guarantees. Instead, it relies on clients to collectively audit the log.

In ContractChecker, we propose a new approach, that is, leveraging Blockchain not only for forking-secure logging but also for delegated log auditing and for consistency guarantees. 

The motivation of ContractChecker is that by delegating cumbersome auditing work to the Blockchain, it relieves busy and low-power clients from the auditing work and saves client-side overhead.
As shown in Table~\ref{tab:distinct}, ContractChecker does not address the security of fork attack. Instead, it relies on and is compatible with Catena for the defense of forking attacks.

\begin{table}[!htbp] 
\caption{Distinction of the ContractChecker approach with existing work}
\label{tab:distinct}\centering{\small
\begin{tabularx}{0.5\textwidth}{ |X|c|c| }
  \hline
Settings   & Fork-secure logging & Log auditing for consistency 
\\ \hline
Untrusted server & SUNDR~\cite{DBLP:conf/osdi/LiKMS04} & Caelus~\cite{DBLP:conf/sp/KimL15}, CloudProof~\cite{DBLP:conf/usenix/PopaLMWZ11}
\\ \hline
Blockchain TTP & Catena~\cite{DBLP:conf/sp/TomescuD17} & {\bf ContractChecker} (this work)
\\ \hline
\end{tabularx}
}
\end{table}


\subsection{System Model}

\begin{figure}[!ht]
\begin{center}
    \includegraphics[width=0.4\textwidth]{figures/protocol1.ps}
\end{center}
\caption{System model in ContractChecker}
\label{fig:model}
\vspace{-0.10in}
\end{figure}

Our target system consists of four parties, the Blockchain, the cloud server, clients and an identity provider. The parties are involved in two phases: system setup and serving online operations.  In the system setup, clients register themselves with identity provider who provide the identities to the Blockchain and to cloud storage server. At the end of the first phase, each legitimate client is identified by a token, say a public key whose private key is only known by the client. 

In serving online operations, it excludes the identity provider and involves client, Blockchain and the storage server. Our ContractChecker protocol focuses on the online-operation phase. The client and server run the storage service where the clients outsource the data storage to the cloud server. Figure~\ref{fig:model} illustrates the system model.

{\bf Data model}: We consider the standard key-value data model where a record is represented by a key-value pair. The storage server serves record reads/writes. We focus on verifying strong consistency in this work, because it is the most security-sensitive consistency level. The extension to weak consistency is left for future work. In strong consistency, reads/writes are total-ordered by time and a read should return the latest write in this total order. 

We represent each read/write by $r/w$ followed by its index in the total-order sequence as the subscription. For read, the result returned is in a pair of square brackets. For instance, $w_1r_2[w_1]$ is a sequence of a write and a read. The write (of index $1$) is ordered before the read (of index $2$). The read returns the results of the write. Optionally, data key in an operation is wrapped in a pair of brackets. For instance, $w_1(K_a)$ is a write of key-value pair of key $K_a$. 

\subsection{Threat Model}
The clients are trusted and behave honestly by following the ContractChecker protocol. The clients do not communicate each other (i.e., isolated clients).

The server can behave maliciously. The malicious server can exploit the freedom to violate consistency when serving clients'  request. She particularly wants to conceal the consistency violation from clients. Clients, given inconsistent results, may unwarily misuse the inconsistent data and lead to security consequences. For instance, if the storage is a public-key directory, violating the consistency leads to the client obtaining a stolen (and timely revoked) key from the cloud storage and falsely uses it to encrypt her private data. The data will be disclosed to the one stealing the stale key.  In \S~\ref{sec:secanal}, we will discuss a series of detailed attacks that aim at inconsistency violation.

The Blockchain is trusted in the following senses: 1) Immutable transaction storage: Given a transaction finalized, the state of the transaction in the Blockchain becomes immutable; that is, after a transaction has been confirmed several times (e.g., 6 times), the transaction cannot be removed, modified or replayed in the Blockchain. 2) Truthful and unstoppable execution of smart contracts: Given a smart-contract program, once it is loaded and starts to execute, the execution will truthfully follow the program and input data. And the execution cannot be stopped. Note that the Blockchain network is open-membership; given a smart-contract, anyone who pays the Gas can run a contract function. However, for the transactions submitted to the Blockchain before finalization, Blockchain loses the transactions (e.g., when the target throughput is too high, or when the Blockchain is under attacks). 


\subsection{Research Overview}
We present the research overview by formulating the problem statement and describing the design space of the problem.

{\bf Problem Statement}: \emph{This work aims at providing storage-consistency guarantees, 1) with security against a malicious storage server, 2) in a lightweight fashion to clients, by delegating log auditing to the Blockchain, and 3) with cost-effective use of Blockchain.}

{
\color{blue}
This work considers the setting of low-throughput logging limited by the throughput of the Blockchain. The main part of the paper focuses on the cost effectiveness and security in low-throughput application logging. The issues of privacy are discussed in \S~\ref{sec:discussion}.

{\bf Target scenarios}:  ContractChecker aims at low-throughput application scenarios where operations occur on a hourly, daily or weekly basis. Typically these scenarios have operations emitted with a throughput lower than that of Blockchain (note that Blockchain is limited to handle tens of transactions per second).  The target scenarios for ContractChecker are a small amount of cloud users, for instance, individual homes, small organizations, etc.
}

{\bf Design Space}: The new approach raises new design issues. In security, the log exposure to the public Blockchain invites new attacks, launched by adversarial server in collusion with malicious Blockchain miners. In particular, the Blockchain is known to be non-deterministic to writes before confirmation and has the vulnerability window for exploit. 

In cost, the consistency-based log auditing requires the Blockchain to record individual operations on chain, which causes high overhead. The high overhead stems from not only transaction fee for data movement on to Blockchain, but also the Gas for on-chain storage. 

Our research addresses both the security and cost-effectiveness of Blockchain-based log auditing schemes. Figure~\ref{fig:securecost} presents the research goals of ContractChecker.

\begin{figure}[!ht]
\begin{center}
    \includegraphics[width=0.35\textwidth]{figures/design.ps}
\end{center}
\caption{Design goals of ContractChecker in Security and cost-effectiveness}
\label{fig:securecost}
\vspace{-0.10in}
\end{figure}

\section{The Security Protocols}
\label{sec:secureprotocols}
\subsection{The Basic Protocol}

\begin{figure}[!ht]
\begin{center}
    \includegraphics[width=0.35\textwidth]{figures/protocol2.ps}
\end{center}
\caption{Running the ContractChecker protocol: Note that the smart contract performs checks among different representations of the logs at different locations. After the log segment is verified and audited in consistency, it is merged to the persistent log.
}
\label{fig:basicprotocol}
\vspace{-0.10in}
\end{figure}

{\bf Design choices}: Recall that the Blockchain is a highly-available trusted third party with state-update finality delays. Verifying operation consistency leveraging the Blockchain TTP entails several logical checks: C1) Server attestation: Because the total order among operations is dictated by the storage server, the storage server has to attest to the total order. Note that even though operation events (e.g., start and completion) are assigned with global timestamp, it is not sufficient to establish total-order under concurrent operations. C2) Agreement between client- and server- views: Because the server is untrusted and can forge arbitrary data in the log, it is necessary to compare the server view with the client view. Note that the server view has some information more than the union of all client views, namely the total order. The agreement does not apply to total-order information. C3) Agreement between acknowledged write and confirmed writes: Because there is a delay in finalizing a write on Blockchain (e.g., for smart-contract state update) and there is a chance to lose a write on Blockchain under denial-of-service attacks, it is necessary to check and confirm a write is included in the Blockchain. C4) Consistency auditing: The consistency of a ground-truth log needs to be checked based on the consistency conditions.

The basic ContractChecker protocol runs the above logical checks in a way that is compatible with the transaction life cycle in the Blockchain. The protocol is scheduled to run in epoch. Each epoch is equal to the average time interval a block is mined in Blockchain (e.g., in BitCoin an epoch is 10 minutes). At the beginning, read/write operations are submit by clients and get processed by the storage server. At the end of each epoch, the clients send their local log segments to the Blockchain (\texttt{verifyLog}). For each operation in the local log, it records the timestamps of the begin and end of the operation. The timestamp comes from a trusted global timestamp service or an NTP alike distributed protocol.

The server declares the total-order among all operations received from the clients in that epoch, and attests to it by sending the global log segment to the Blockchain (\texttt{attestLog}). At the end of the epoch, the Blockchain maintains $N$ per-client log segments and one server log segment. 

After $K$ epochs, say $K=6$ for Ethereum, the transactions are finalized and recorded log segments are stored in smart-contract state with commitment. The Blockchain also fails to finalize or even not to include the transaction. This can be done by either malicious miners or by malicious Blockchain clients submitting oversubscribed volume of operations (denial-of-service attack). Thus, the protocol then runs finality checks (C2) by having each client to trigger the \texttt{verifyLog} function on chain. In \texttt{verifyLog}, an owner client reads the transaction that encodes her log segment $K$ epochs ago and checks if there are more than $K$ blocks added to the Blockchain. In addition, she checks if the transaction data is equal to her local segment (or simply comparing their hashes). 

Then, after \emph{all} clients have done finality checks, the Blockchain checks (C3) if the global log attested by the server is exactly the same to the union of log segments of all clients. If the check passes, the operation timestamps stored in the local log will be copied to the global log.

The protocol audits (C4) the consistency of operations in the global log segment. Concretely, it checks if the writes are ordered in accordance to their timestamps. It also checks if a read operation returns the fresh result in the total-ordered write sequence. During the audit of reads, it accesses the log of historical operations. Once the consistency auditing is completed, the log segment of writes is merged to the persistent log for auditing future operations. The life cycle of an operation in ContractChecker is illustrated in Figure~\ref{fig:basicprotocol}. 

\subsection{Security Analysis of Basic Protocol}
\label{sec:secanal}
Recall that our untrusted server plays the role of storage server who handles the read/write requests, and the role of ContractChecker server who follows the protocol and attests to read/writes in epoch. 

In this part, we consider three attacks: A0) The storage server misbehaves by violating the consistency, but honestly executes the ContractChecker protocol. A1) The malicious server can deviate from the ContractChecker protocol and forge arbitrary data in the log attestation. From smart-contract point of view,  A1) and A0) attack by providing invalid input to the on-chain functions. We also consider attack A2) that an external adversary directly attacks the ContractChecker's computations executed on the open Blockchain.

The attacks are shown in Table~\ref{tab:auth-attack}.

\begin{table}[!htbp] 
\caption{Attacks}
\label{tab:auth-attack}\centering{\scriptsize
\begin{tabularx}{0.5\textwidth}{ |X|c|c| }
  \hline
Attacks & Adversary & Target
\\ \hline
A0 & Storage server & Invalid smart-contract input
\\ \hline 
A1 & ContractChecker server & Invalid smart-contract input
\\ \hline
A2 & External adversary & Intermediate computation on chain
\\ \hline
\end{tabularx}
}
\end{table}

{\bf Attack A0: Consistency violation}: In Attack A0, the storage server violates the consistency, that is, returning stale writes to serve a read (e.g., $w_1w_2r_3[w_1]$). The server honestly follows the ContractChecker protocol in the log attestation. The ContractChecker protocol ensures that any consistency violation can be detected as any inconsistency will be captured by logical checks in C4.

{\bf Attack A1: Server forging attestation}: A malicious ContractChecker server can deviate from the protocol and forge arbitrary data in the log to attest. She can attack by forging arbitrary data or she can do it more strategically: She can work with a malicious storage server (A0) and forge attestation accordingly to conceal the consistency violation (A0) from the Blockchain and clients. Specifically, the malicious server could modify, omit, reorder and replay operations in the global log attestation. For instance, given Operations $w_1w_2r_3[w_1]$, the server may reorder operations ($w_2w_1$) or omit operation $w_2$ such that the forged attestation $w_1r_3[w_1]$, if it passes ContractChecker checks, can conceal an incident of operation inconsistency.

We consider the case that the forged log attestation has one edit distance to the truthful attestation. An operation edit can be modifying an operation (e.g., from read to write), deleting an existing operation, or adding a non-exist operation. The more general case that forged log is more than one edit distance to the truthful log can be reduced to the one-edit-distance case. 

If the operation edit is one of modification, deletion and addition, it can be detected by the check between the local logs and global log (C2). If the operation edit is reordering of two operations, we consider two cases: If the reordered operations are from one client, it can be detected by the local-global check (C2). If the reordered operations are from two clients, it can be detected by the mismatch of their timestamps in consistency auditing (C4).

{\bf Attack A2: Cloud mining}: In ContractChecker, the server sends the attestation of global log to the Blockchain. A malicious cloud server could aim at controlling a significant portion of mining power to equivocate. Equivocation may trick the Blockchain to conduct checks on one version of the attestation, and to persist another version into the long-term log. This way, it can hide the inconsistent read $r_3[w_1]$. This may occur if the logical checks are ordered inappropriately. 
Details are in Technical report~\cite{me:cc18}.

After the server and clients send their attestation to the Blockchain, the adversary can collude with the server to first send an equivocation of the attestation and then to get engaged in mining the equivocation branch of the Blockchain. For instance, suppose two clients respectively have logs $w_1r_3[w_1]$ and $w_2$, the malicious server may attest to two total-order logs, $w_1w_2r_3[w_1]$ and $w_2w_1r_3[w_1]$. Assume $w_1$ and $w_2$ are concurrent and the server can reorder the two writes without violating the timestamps. The malicious server may want to first send the attestation $w_2w_1r_3[w_1]$ to pass consistency auditing (C3) and then send forked attestation $w_1w_2r_3[w_1]$ to get it persisted in the long-term log. 

In ContractChecker, the protocol design enforces the invariant that any logical checks only occur when the state gets finalized on chain. In Figure~\ref{fig:miningattack}, suppose malicious miners in collusion with the server launch attacks by equivocation to hide an inconsistent global log $w_1w_2r_3[w_1]$. The adversary attests to a forged log segment $w_2w_1r_3[w_1]$ on the Blockchain. After $X$ block confirmations, \emph{the finality of the attestation will be confirmed by one of clients}. It triggers all the checks which assume to be passed. The server cannot equivocate and generate another log segment, say $w_1w_2r_3[w_1]$, to the persistent log. Had this been possible, the adversary would have controlled more than a significant portion of the miners (e.g., $51\%$) over the network, which is assumed to be hard on a public, large-scale Blockchain.

\begin{figure}[!ht]
\begin{center}
    \includegraphics[width=0.45\textwidth]{figures/protocol4.ps}
\end{center}
\caption{Attack surface of ContractChecker: Possible attacks can be launched by malicious server (attacks A0 and A1) and malicious miners (attack A2). The figure also shows the three states involved in the computation of ContractChecker.}
\label{fig:miningattack}
\vspace{-0.10in}
\end{figure}

{\bf Cost Analysis}: In the basic protocol, all checking-related computations are outsourced to the Blockchain, including log verification and consistency checking. A client's job is minimized to the logging operations to the Blockchain. 

The basic protocol maximally offloads client's work to the Blockchain at the expense of high cost. In the next section (\S~\ref{sec:costopt}), we will propose various cost optimization techniques with reduced Blockchain costs.


\subsubsection{Security Analysis under Forking Attacks}

In ContractChecker, the Blockchain assumes the role of attester. First, let's simplify the problem by viewing the Blockchain as a single party. In this setting, the forking attack is prevented by the fact that the on-chain program enforces the invariant that each epoch there is only one log segment from the server that gets signed. Then, in reality, the Blockchain is itself a distributed system running over multiple miner nodes. The forking attack can manifest in the form of the server attesting to different sets of operations with different miner nodes. In existing Ethereum architecture, this will be treated as separate calls to the same smart-contract procedure (e.g., \texttt{attestLog}). The Blockchain architecture is responsible for admitting a single call (out of the forks) to update the ContractChecker log. Concretely, the two calls will be propagated to all miners and they are non-deterministically ordered. Every miner will run the two calls in the ordering specific to the miner, and based on the smart-contract program, the global state will admit only one call. The Blockchain's internal consensus protocol will resolve the conflict caused by non-deterministic ordering and consistently update the smart-contract state across all miners.

\subsection{Client Identity Management}

In ContractChecker, clients and the server are pseudo-identified by their Blockchain addresses (public keys). However, unlike a raw Blockchain, the server and clients form a closed membership network in that not everyone can join the system as a client.

For now, we consider the static membership and assume the Blockchain addresses of clients and server are hardcoded in smart contract; We will consider the dynamic client membership in Section~\ref{sec:dynmember}.

Each function call in ContractChecker performs the authentication of the caller. This is simply done by checking the equality of the RPC call's address and the hard-coded address. For instance, serving the \texttt{attestLog}, the ContractChecker authenticates the caller and checks if she is the server. Serving other calls such as \texttt{attestLog}, the ContractChecker authenticates the caller and checks if she is one of the clients. The execution of these functions proceed only when the authentication succeeds.

{\bf Client-impersonation attacks}: We consider the attack where an adversary (e.g., the untrusted server) impersonates one of the clients.\footnote{ An adversary can of course impersonate a server and send a fake log. This case can be reduced to the untrusted server in our trust mode. We don't explicitly consider this case here.} The client impersonator can validate an operation forged by the malicious server. 

Without the client authentication, client-impersonation attack can easily succeed, as anyone can call any ContractChecker function on chain and inject arbitrary data to the log. The forged log can confuse downstream computations for the consistency checking. For instance, suppose the sequence of operations is $w_1w_2r_3$. The server can forge an operation $w_3$ in sequence $w_1w_2w_3r_3$ and impersonates a client who runs \texttt{verifyLog} to validate $w_3$. The server can return $r_3[w_3]$, an incorrect result, to a genuine client. Because log $w_1w_2w_3r_3$ can be verified, this incorrect result can be detected by ContractChecker. More severely, if a delete operation is supported, the server can forge a delete operation, say $d_3[w_2]$ as in $w_1w_2d_3[w_2]r_3$, which will be validated by the impersonated client. The server can then return stale write $w_1$ as the result to the client $r_3[w_1]$, without being detected by ContractChecker.

{\bf Security analysis}: The client authentication in ContractChecker is based on public key distribution and digital signature. A client impersonator who aims at passing the authentication code on chain may need to generate a signature that can be verified by one of these public keys hard-coded (Impersonation Attack 1 or IA1). The unforgeability of digital signature~\cite{DBLP:books/crc/KatzLindell2007} ensures the client's inability to forge a signature without its private key. The impersonator can also attack by stealing the victim client's private key (IA2). We assume the private key is securely stored in each client's off-chain wallet and is not disclosed externally. The impersonator can attack by modifying the hard-coded list of client addresses and by adding its own address there (IA3). We assume the hard-coded client addresses is a read-only variable in the smart contract and we assume the memory safety of smart contract. 
\subsubsection{Dynamic Client Membership}
\label{sec:dynmember}

In this section, we address the dynamic client membership where clients can join and leave the cloud-storage system. 

The dynamic client membership is handled by an external trusted identity provider (IdP). Instead of hard-coding client membership as in the static case, the ContractChecker maintains a directory (in a mapping variable) storing the Blockchain addresses of all registered clients. During the function calls, the caller clients are authenticated using the dynamic directory of addresses. When a new client joins the system, the IdP performs its own client registration using the standard InfoSec procedure. The Blockchain address of the client is included as one of her identities. Once the registration completes, the IdP server will add the new account and her Blockchain address to the ContractChecker. When a client leaves the system, the IdP deregisters the client account and removes the Blockchain address from the ContractChecker directory.

To authenticate the IdP itself, the Blockchain address of the IdP server is static and is hard-coded in the smart contracts. 
Recall that Figure~\ref{fig:model} has shown that the Blockchain interacts the IdP server to manage identity on chain.

\section{Cost Optimization Techniques}
\label{sec:costopt}
The ContractChecker design runs log audits on the Blockchain and entails the Blockchain tor record individual operations. This incurs high cost per operation. In this section, we propose a series of techniques to optimize the Blockchain cost in ContractChecker.

\subsection{Cost Model}

The ContractChecker computation incurs the typical cost as below: 1) the data-movement cost from off-chain to on-chain; the cost manifests in transaction fees, 2) on-chain storage write cost that manifests in Gas consumption, 3) on-chain hash computation cost in Gas. Here, we only consider expensive Blockchain operations and ignore the cheap ones such as memory word access and single CPU operation. This is based on Ethereum cost model.


\subsection{Problem of Storage Placement}

Instantiating the ContractChecker computation, it entails the placement of the states. For a computation state, there are two places the store can be stored, on the Blockchain (hence called on-chain) or off the Blockchain (off chain) such as on the server or clients. 
General speaking, placing storage on-chain incurs the Gas cost for on-chain storage writes, while off-chain storage placement incurs transaction fees for data movement. We systematically examine the cases of the three states (i.e., client log, server log and persistent log) and propose storage placement strategies.  


\subsection{Placing Client Log}
The client log can be stored either on chain or off chain. 

{\bf On-chain client log}: The client submits the local operations to the Blockchain at the end of each epoch. The client then only digests the submitted operations, free the operation storage, and stores only the digest locally. After $X$ epochs when the transaction is finalized, the client calls \texttt{verifyLog} by providing digest to check the integrity of the client log on chain.


{\bf Off-chain client log}: The client keeps the local operations until $X$ epochs after the operations are submitted to the cloud. Then, the client sends the operations to the Blockchain and truncates the local client log. The client log is stored in on-chain memory and is only referenced when the Blockchain processes function \texttt{verifyLog}. After that, the client log can be discarded on chain. That is, the access pattern of client log is \emph{read once}.

{\bf Cost analysis}: The off-chain client log requires the clients to maintain the operation log extra time (i.e., $X$ epochs after the operation submission). The on-chain solution incurs hash computation off chain and storage write cost on chain. The exact comparison between the two options depends on application specific settings (e.g., the relative expensiveness between hashing and storage on client devices). We provide both the options in the mechanism of our system. 

\subsection{Placing Server Log}
{\bf On-chain server log}: The server submits to the Blockchain the server log with declared total order over the global operation history (i.e., in function \texttt{attestLog}). The server log is stored on chain and is referenced multiple time when the Blockchain processes different functions (e.g., \texttt{verifyLog} and \texttt{auditLog}). That is, the server log access pattern is \emph{write-once, read multiple times}. 

{\bf Off-chain server log}: The server keeps the log storage locally. At the attestation time, the server submits the digest of the operation history in the given epoch to the Blockchain which stores the digest. That is, the off-chain server log is represented by a digest storage on chain. After that, when the server log needs to be accessed in \texttt{verifyLog} and \texttt{auditLog}, the off-chain server presents the requested operation associated with a proof. The off-chain server log forms a proof system and can be typically organized by a Merkle tree over the operations sorted by data keys. The on-chain functions, once receiving the proof, verify the proof by running hash computations and present the authenticated operation for further processing.

{\bf Cost analysis}: The cost of on-chain server log is on-chain storage writes. The cost of off-chain server log is attributed to the transaction fee per operation read (in \texttt{attestLog}, \texttt{verifyLog} and \texttt{auditLog}), as well as on-chain hashing per operation read. Note that unlike the case of client log, the server log is originated from an untrusted party (i.e., server), so there is an extra off-chain cost due to the security protocol.

\subsection{Placing Persistent Log}
\label{sec:persistentlog}

{\bf On-chain persistent log}: The persistent log is written on chain as a result of \texttt{auditLog}, and is read multiple times also in \texttt{auditLog} for future epochs. Unlike the temporary logs, the persistent log only stores the write operations. It is referenced mainly when the Blockchain audits future read operations. Whether it is referenced depends on the workload. For instance, for sequence $w_1(K_a),w_2(K_b),r_3(K_a)[w_1]$, when $w_1$ and $w_2$ are in persistent log, auditing $r_3$ may require accessing both $w_1$ and $w_2$.

{\bf Off-chain persistent log}: The persistent log can be stored off-chain. When it is written by the on-chain \texttt{auditLog} function, the Blockchain simply updates the log digest on chain. The server will merge the newest epoch log to the persistent log off chain. Upon reads (in future auditing), the server sends to the Blockchain the requested operation as well as the proof such that the on-chain part can verify the integrity of off-chain operations. 
The on-chain and off-chain solutions for persistent log are illustrated in Figure~\ref{fig:onofflog}


{\bf Cost analysis}: The cost of on-chain solution is dominated by the storage write on chain. The cost of off-chain solution is dominated by the on-chain hashing and transaction fees per each read. Note that the storage read on chain is negligible as demonstrated in measurement study in \S~\ref{sec:measure}. Therefore, it can be foreseen that the on-chain solution is favored when the persistent log is read more frequently. The off-chain solution is favored when the persistent log is barely read. The access pattern of persistent log is dependent on the cloud-storage workload: When the storage workload is read intensive, the persistent log will be read more frequently. Otherwise, he persistent log is read less. Our evaluation shows the trade-off between on-chain and off-chain storage under different workloads (see Figure~\ref{exp:tradeoffrw}). We also tried the on-chain buffer to store recent writes, which however did not save the overall cost (See 
Technical report~\cite{me:cc18}
).

In summary, the three states in ContractChecker can be characterized in multiple metrics and they affect the preferred placement strategy. We illustrate the details in Table~\ref{tab:placingstates}.

\begin{figure}[!ht]
\begin{center}
    \includegraphics[width=0.5\textwidth]{figures/protocol3.ps}
\end{center}
\caption{
The computation states in ContractChecker and the placement of their storage. There are three states in the log computation (client log, server log, and persistent log as in Figure~\ref{fig:miningattack}). The placement of three states can be on the Blockchain (on-chain) or off the Blockchain (off-chain). For each read or write of the state, there is a cost profile. The cost is illustrated by the thickness of the arrows representing the access of on-/off-chain state in the figure. Reading the client log stored in the off-chain client entails transaction fee, which is moderate cost. Accessing a persistent log stored on-chain server entails writes to on-chain storage, which is expensive.
}
\label{fig:onofflog}
\vspace{-0.10in}
\end{figure}

\begin{table}[!htbp] 
\caption{
Characterization and on-chain/off-chain placement of the three states in ContractChecker:
Each state can be placed off-chain to the originator that generates the data. The table characterizes the (off-chain) state originator by its trustworthiness and the state's access pattern. The client log is accessed only once by the Blockchain and it is originated from clients who are trusted. The default (or preferable) option is to store the log off-chain.
}
\label{tab:placingstates}
\centering{\scriptsize
\begin{tabularx}{0.5\textwidth}{ |X|c|c|c| }
  \hline
States & Off-chain trustworthiness & Access pattern & Default placement 
\\ \hline
Client log & Trusted & Read once & Off-chain 
\\ \hline
Server log & Untrusted  & Read twice & On-chain
\\ \hline
Persistent log & N/A & Read multiple times & On-chain
\\ \hline
\end{tabularx}
}
\end{table}

\subsection{Operation Batching in Transactions}
Another cost factor is the number of operations batched in a transaction. The more operations are batched, the more the transaction fee is amortized over the batched operations. We propose techniques for operation batching with reduced transaction fee.

ContractChecker needs to move the operations from off-chain to on-chain for log auditing (e.g., in \texttt{attestLog} and \texttt{verifyLog}). This process costs transaction fee, as operations need to be packed in transactions. To save the fee, one can pack as many operations in a single transaction to amortize the transaction fee. Although the transaction fee is proportional to the transaction size, operation batching can still amortize the fix cost of an empty transaction.

\section{ContractChecker Middleware System}

The ContractChecker middleware is a distributed system that runs several jobs on individual nodes and runs remote-procedure calls (RPCs) to connect them together. Concretely, the server and clients run local logging jobs (Job 1) that log the operation histories in their respective views. The server calls a log-attestation RPC to the Blockchain by the end of each epoch (Job 2). Each client calls a log-verification RPC to the Blockchain by the end of each epoch (Job 3); This job is about the client's operation history $X$ epochs ago. The Blockchain runs log-auditing job on chain (Job 4). The overall implementation of ContractChecker middleware is presented in Listing~\ref{lst:middleware}.

The local jobs such as logging (Job 1) and \texttt{auditLog} (Job 4) are implemented using native programming language. In particular, Job 4 is a smart-contract program triggered by the log-verification job. The scheduling of the jobs and events is described before in Section~\ref{sec:secureprotocols}.

Most RPCs in ContractChecker are initiated by the off-chain parties; \texttt{attestLog} is initiated by the server and \texttt{verifyLog} is initiated by individual clients. They are implemented as a smart-contract function on chain as the RPC callee and a program off-chain as the RPC caller. 

\input{text/lst1.tex}

\subsection{Off-chain Notification}

Some variants of ContractChecker require a reversed RPC for notification of off-chain parties. For instance, in off-chain persistent log (\S~\ref{sec:persistentlog}), the Blockchain needs to access the operations stored off-chain on server. Sending a notification from on-chain to off-chain, it presents a challenge in current Blockchain system, where transactions are sent from off-chain to on-chain. 

We implemented a basic off-chain service that virtually supports Blockchain-initiated RPCs. In this service, the Blockchain and off-chain server conceptually share a variable on-chain. The server periodically sends heartbeat messages to a smart-contract function that simply reads and returns the shared variable. The Blockchain has the write access to the shared variable. When it wants to notify the off-chain server, the Blockchain sets the value of the variable. Next time, when the server sends heartbeat transactions and calls the variable-check function, she will get a non-zero value in return. The server gets notified in a timely fashion (depending on how frequently it sends heartbeats).

\section{Evaluation}
\label{sec:eval}

In this section, we evaluate the ContractChecker system in terms of cost effectiveness. We will answer the following questions:

1. How do the choices of placing ContractChecker states (client log in \S~\ref{sec:micro:clientlog} and persistent log in \S~\ref{sec:micro:persistentlog}) affect the cost of on-chain storage?

2. How much bandwidth does ContractChecker cost (\S~\ref{sec:micro:bandwidth})?

To answer these questions, we conduct measurement study (\S~\ref{sec:measure}) to understand the cost distribution in Ethereum, conduct micro-benchmark studies (\S~\ref{sec:micro}) to understand individual cost components in ContractChecker, and evaluate the overall system under the YCSB workloads to understand its macro-benchmark behavior (\S~\ref{sec:macro}).
We also conduct other experiments and present the results in 
Technical report~\cite{me:cc18}, due to space limit.

{\bf Experiment setup}: We set up a private Ethereum network in an LAN environment. The Ethereum
runs on machines of the following specs: Intel 8-core i7-6820HK CPU of 2.70GHz, 
32KB L1 and 8MB LL cache, 32 GB RAM and 1 TB Disk. When setting up the network,
we use the default configuration (e.g., difficulty levels) for Ethereum. Note that we only measure the 
cost (e.g., transaction fee and Gas), which is independent of network scale. The metrics dependent on
the network scale, such as throughput, are not the interest of this work.
We deploy our smart-contract program written in Solidity to the Blockchain, by leveraging an online python tool\footnote{\url{https://github.com/ConsenSys/ethjsonrpc}}.
The Gas cost is collected from the transaction receipts from the Blockchain.

\subsection{Measurement Study}
\label{sec:measure}

\begin{figure}[!ht]
\begin{center}
    \subfloat[Write cost]{
    \includegraphics[width=0.4\textwidth]{figures_onoffchain/exp-Gas-Operationsequence.eps}
\label{exp:write}
}
\\
    \subfloat[Read cost]{
    \includegraphics[width=0.4\textwidth]{figures_onoffchain/exp-Gas-Readsize.eps}
\label{exp:read}
}
\end{center}
\caption{Unit cost of reads/writes: On-chain versus off-chain}
\vspace{-0.10in}
\end{figure}

In the experiment, we drive the write-only and read-only workloads to the Blockchain and measure the Gas consumption. We consider both on-chain storage and off-chain storage. For off-chain storage, we implement the approach using different hash functions, including SHA3, SHA256 and RIPEMD160 which are built-in functions in Ethereum library. For write cost, we report the Gas consumption along with the operation sequence. We omit the cost of initializing the system and report the cost when it become stable. The result is in Figure~\ref{exp:write}. All off-chain solutions consume less Gas than the on-chain solutions, despite which hash algorithms are used. For on-chain storage, the Gas consumption fluctuates: the periodic peaks in Gas consumption correspond to the events of allocating on-chain storage for new writes. On average, the on-chain storage incurs more than two times of the cost of the off-chain storage.

For read cost, we use the workloads of sequentially reading a series of operations in the log, instead of a single random-access read. This resembles the workload of ContractChecker as auditing the consistency of an operation entails sequential read of multiple prior operations. We vary the number of operations read (i.e., the read size) and report the Gas consumption averaged by three times. The result is reported in Figure~\ref{exp:read}. The gas cost increases linearly with the read size (note that both axis's are plotted in the log scale). On-chain storage has the lowest cost comparing the cost of all off-chain storage solutions.

Summarizing the results of above two experiments, the on-chain storage has higher write cost but lower read cost than the off-chain storage. The reason behind this is due to the cost model in Ethereum that charges a lot for on-chain storage write and very little for on-chain read. The cost of transaction fee and on-chain hashing falls in the middle. 

\subsection{Micro-Benchmarks}
\label{sec:micro}

\subsubsection{Cost of Placing Persistent Log}
\label{sec:micro:persistentlog}

\begin{figure}[!ht]
\begin{center}
    \subfloat[Cost with 4-reads-1-write sequence]{
    \includegraphics[width=0.4\textwidth]{figures_onoffchain/micro2-interval4/exp-Gas-Operationsequence.eps}
\label{exp:4r1w}
}
\\
    \subfloat[Read-write cost]{
    \includegraphics[width=0.4\textwidth]{figures_onoffchain/exp-Gasperoperation-Read-writeratio.eps}
\label{exp:tradeoffrw}
}
\end{center}
\caption{Cost of persistent log: On-chain versus off-chain}
\label{fig:easy2}
\vspace{-0.10in}
\end{figure}

In this experiment, we study the cost of placing the persistent log on- or off-chain. 
We conduct two micro-benchmark studies for mixed read and write workloads. In Figure~\ref{exp:4r1w}, the workload consists of four writes (of different keys) followed by four reads (of the same set of keys) such that a read needs to iterate through up to four prior writes to get its consistency audited. The results clearly shows the comparison between the two solutions: During the write period on-chain storage incurs higher cost and during the read period, the off-chain storage has higher cost. Figure~\ref{exp:tradeoffrw} shows the average read-write cost with changing the read/write ratio. For ratio smaller than 1, we consider a single data key and generate multiple writes with one read. In the result, the on-chain storage is advantageous in serving read-dominant workloads and the off-chain storage is advantageous in serving write-dominant workloads.

\subsubsection{Cost of Placing Client Log}
\label{sec:micro:clientlog}
\begin{figure}[!ht]
\begin{center}
    \includegraphics[width=0.4\textwidth]{figures_onoffchainclient/exp-Gasperoperation-Sequenceofoperations.eps}
\end{center}
\caption{Storage placement of client log: On-chain versus off-chain}
\label{exp:onoffclient}
\vspace{-0.10in}
\end{figure}


We measure the cost of placing client log off-chain in comparison with the on-chain placement. In the off-chain client log, a client sends her log to the Blockchain which processes the log in memory. In the on-chain client log, the client sends her log to the Blockchain which stores the log before processing it later. 

In the experiment, we drive a series of operations to the system and measure the Gas consumption. In the microbenchmark study, we run an empty smart contract function on chain which does nothing more than taking as argument the client log. We deliberately don't run any computation on chain to focus on the cost introduced by the log placement. The result is reported in Figure~\ref{exp:onoffclient}. The per-operation cost of off-chain log stays the same over time and is $60\%$ lower than that of on-chain client log. The cost efficiency comes from the on-chain storage writes saved in the off-chain client log.

\subsection{YCSB Macro-Benchmark}
\label{sec:macro}

{\bf Adapting YCSB to ContractChecker}: For conducting macro-benchmark, we use the Yahoo cloud serving benchmark (YCSB) to generate the target workload. We first play the native YCSB program and record the sequence of read/write operations. Then, we replay the recorded operation sequence and drive it to the ContractChecker. We carefully limit the rate such that it does not saturate the Blockchain. In our current setting, we limit 140 operations per mining one block (that is, X seconds). Every X seconds, clients submit 140 operations to  transactions sent to the Blockchain. They wait until 6X seconds later to check the finality of the transactions on chain. If transactions are finalized, clients notify the Blockchain to audit the log.

\subsubsection{Gas Cost under YCSB Workloads}

\begin{figure}[!ht]
\begin{center}
    \includegraphics[width=0.4\textwidth]{figures_macroycsb/exp-Gasperepoch-Sequenceofepochs.eps}
\end{center}
\caption{Gas cost under different YCSB workloads}
\label{exp:ycsb}
\vspace{-0.10in}
\end{figure}

We drive YCSB workloads into ContractChecker using the record and replay approach mentioned above. We consider three YCSB workloads: Workload A has $50\%$ read operations and generates data keys using Zipfian distribution. Workload B has $95\%$ read operations and generated zipfian keys. Workload D has $95\%$ read operations, and generates data keys in the 'latest' distribution where a read returns the latest write. 

We consider both on-chain and off-chain storage of the client log, whose setups are described in the previous experiment.
We measured the Gas cost and reported the result in Figure~\ref{exp:ycsb}. 
The process runs in $81$ epochs, each of which runs $140$ operations. In the figure, the first 10 epochs run the YCSB load phase, which generates pure write operations. After that, it runs the YCSB evaluation phase where read/write operations are generated based on the workload specification. 

The result shows that the off-chain storage saves  $42\%$ Gas cost comparing the on-chain design. The saving comes from no writes of on-chain storage in the off-chain client log. Among the different workloads, workload A incurs the highest gas cost, because workload A is write intensive, and a write tends to cost more gas than a read(for instance, a cloud write operation will entail writing to on-chain storage twice, a read operation doesn't cost any on-chain write). In the first $10$ epochs in the figure, it generates write-only workload to populate the system, and costs higher than the evaluation phase.

\subsubsection{Gas Cost under Placement Strategies}

\begin{figure}[!ht]
\begin{center}
    \includegraphics[width=0.4\textwidth]{figures_macroycsb/server_client_persis_on_off/exp-Gasperepoch-Sequenceofepochs.eps}
\end{center}
\caption{Gas cost with different placement strategies (YCSB Workload D)}
\label{exp:ycsbonoff}
\vspace{-0.10in}
\end{figure}

In this experiment, we drive YCSB workload D into ContractChecker under different state placements. Recall that both client and server log can be placed either on- or off-chain. In this experiment, we explore all four combinations with their implementation described below. In each setting, we run the workload in 81 epochs, each of which consists of 140 operations. The first 10 epochs run the YCSB load phase, which consists of pure write operations. After that, it runs the YCSB evaluation phase where read/write operations are generated under workload D. We measure the Gas cost per operation and report the results in Figure~\ref{exp:ycsbonoff}.

We implemented the different combinations in the following way:  
For the placement with on-chain client log and off-chain server log, both server and clients send their log segments to on-chain storage by sending a transaction. It then invokes the \texttt{auditLog} function which reads the on-chain storage for client and server logs. 
For the placement with off-chain client log and on-chain server log, the server uploads her log segment with the declared order to the on-chain storage by sending a transaction, and then each client invoke log verification by sending her local log to on-chain memory. Then, the \texttt{auditLog} function runs by reading the in-memory client log and on-storage server log. 
For the placement with on-chain client log and off-chain server log, the server waits until all clients have uploaded their local logs to the on-chain storage. She then uploads the server log to on-chain memory and runs the \texttt{auditLog} function on the in-memory server log and stored client log. 
For the placement with off-chain client log and off-chain server log, both server and clients upload the individual operations to the Blockchain in such a way that for each operation, the server copy is uploaded right after the client copy. 
The server log is persisted on chain (at O(1) space) and the client log is stored in on-chain memory. Note that the off-chain placement of both server and client logs entails packing each operation in a dedicated transaction and is expected to cause higher transaction fee.
The \texttt{auditLog} function is invoked that processes the in-memory client log and stored server log. 

The figure shows that the placement of on-chain client log and on-chain server log costs the most Gas, and the placement of off-chain client log and off-chain server log costs the least Gas. 
This result is interesting as it reveals what is dominating cost component in smart contract programs. More specifically, the placement strategy of off-chain server log and off-chain client log minimizes the on-chain storage at the expense of transaction fee. Yet the cost of this placement is still the lowest, which implies that the dominating cost component in ContractChecker is the on-chain storage and the transaction fee comes secondary.

For the other two placements, the placement strategy of off-chain client log and on-chain server log costs more Gas than that of on-chain client log and off-chain server log. The cost difference comes from the different read/write profiles of the two logs: The server log is read twice (one for \texttt{verifyLog} and one for \texttt{auditLog}), while the client log on chain is read once for \texttt{verifyLog}. The addition read of server log makes the on-chain storage save more Gas.

\subsubsection{Bandwidth}
\label{sec:micro:bandwidth}

\begin{figure}[!ht]
\begin{center}
    \includegraphics[width=0.4\textwidth]{figures_macroycsb/exp-Bandwidth-Sequenceofepochs.eps}
\end{center}
\caption{Client-side bandwidth cost}
\label{exp:bandwidth}
\vspace{-0.10in}
\end{figure}

In this experiment, we drive the YCSB workload A operation sequence to the ContractChecker. On the ``data plane'', we measure the size of operations sent to the cloud server. We rely on Google protobuf~\cite{me:protobuf} for client-cloud communication and use its utility to measure the message size. On the ``security plane'', we measure the size of data embedded in the Blockchain transactions for running ContractChecker functions. The results are reported in Figure~\ref{exp:bandwidth}. As before, the first 10 epochs run the YCSB load phase and the rest runs the YCSB evaluation phase.
In the result, the bandwidth induced by ContractChecker transactions is slightly lower than that by operations sent to the cloud. Over time, the bandwidth cost of ContractChecker transactions stays the same, because it is insensitive to read/write operations. The messages to the cloud have their sizes varied over time: In the load phase (the initial plateau), the bandwidth stays constant and is higher than the later operations. YCSB workload A has $50\%$ operations to be reads and uses Zipfian distribution to generate read keys. The bandwidth varies based on the exact read/write distribution in an epoch. 

{
\color{blue}
\section{Discussion}

{\bf Out-of-order execution}: ContractChecker can handle the common case in practice that requests are processed in an order different from the order they are received (out of order processing). This is well captured in the consistency model used in ContractChecker. 

Suppose a read request, say $r$, is received before a write and is processed after the write, $w$. In the consistency model, the two requests are processed concurrently. Strong consistency (e.g., linearizability) allows concurrent requests to be ordered in whichever way to match their causal relation (that is, whether $r$ result reflects $w$). In this case, the ContractChecker simply follows the specification in the consistency model and checks it on the log of operations.

{\bf Privacy}: We assume what is logged on Blockchain only includes non-identifiable information (e.g. operation type, time, data key being accessed). The identifiable information is securely stored. We don’t consider side-channel security in our work.

}

\section{Related Work}

Recall that Section~\ref{sec:rw:consistency} reviews the storage-consistency protocols including SUNDR, CloudProof, Caelus and Catena. In this section, we briefly review other related work.

{\bf
Blockchain applications}: Blockchain has been applied in both financial and non-financial applications. In the application scenarios, Blockchain and its security properties are repurposed to address application-specific security needs. CSC~\cite{DBLP:journals/corr/abs-1804-05141} runs criminal smart contract on Blockchain for facilitating commissioned crimes. Paralysis~\cite{DBLP:journals/iacr/ZhangDBJ18} supports practical wallet management under key loss/compromise by using Blockchain as trusted clock to detect client unavailability. Blockstack~\cite{DBLP:conf/usenix/AliNSF16} runs trusted directory on Blockchain by treating it as immutable data storage. IKP proposes an incentive scheme based on Blockchain to address the certificate mis-issuance problems. Blockchain is also used as the source of randomness~\cite{DBLP:books/daglib/0040621}, non-equivocation log as in Catena~\cite{DBLP:conf/sp/TomescuD17}, etc. in many novel applications.

{\bf
Blockchain throughput improvement}: There are known performance problems in Blockchain notably the limited throughput. There are protocol-analysis works on Blockchain that try to understand the throughput limitation (e.g., by block sizing~\cite{DBLP:conf/fc/CromanDEGJKMSSS16}). Lightning network~\cite{me:lightning,DBLP:journals/corr/MillerBKM17} is an off-chain scheme that batches multiple micro-payment transactions to reduce the load on chain. Lightweight mining protocols are proposed including proof-of-stake~\cite{me:pos1,me:pos2}, proof-of-elapsed-time~\cite{me:poet,DBLP:conf/uss/ZhangEEJR17}, etc. Ekiden~\cite{DBLP:journals/corr/abs-1804-05141} combines Blockchain with trusted hardware to form a virtual high-throughput Blockchain system. Blockchain sharding~\cite{me:omniledger,DBLP:conf/ccs/LuuNZBGS16} partitions the state of transaction graph among multiple miners, in a way to improve its scalability. 

{\bf
Cloud verification}: Authenticated data structure (ADS)\cite{DBLP:conf/esa/Tamassia03,DBLP:journals/algorithmica/PapamanthouTT16,DBLP:conf/isw/AnagnostopoulosGT01} is a proof system that a client can verify the authenticity of data stored on a remote server. ADS typically assumes that data updates are signed by the data-owner client and focuses on the authenticity of read queries. ADS schemes are constructed using Merkle hash trees~\cite{DBLP:conf/sigmod/LiHKR06}) or other cryptographic primitives. ADS complements a secure logging scheme as in ContractChecker and forms an overall secure storage scheme.

In addition, CloudVerifier~\cite{DBLP:conf/services/SchiffmanSVJ13} builds a chain of trust from the clients to their hosted virtual machine (VM) instances, and it checks client-specified requirements on VM's load-time and run-time properties. 

\section{Conclusion}
This work presents ContractChecker, a lightweight consistency verification protocol based on Blockchain. 
ContractChecker is designed based on a new approach that runs log auditing on the Blockchain. This approach is advantageous in guaranteeing the strong consistency of the cloud storage and in saving the execution effort and storage cost of low-power and low-available clients.
ContractChecker addresses the security of malicious cloud mining by carefully scheduling logical checks on chain.
For cost-effective use of Blockchain, ContractChecker utilizes a series of cost-optimization techniques by exploring on-/off-chain storage placement, operation batching, etc.
ContractChecker is implemented in a middleware system federating cloud services, clients and the Blockchain. 
Through evaluation based on YCSB workloads, up to 42\% Blockchain cost can be saved by ContractChecker's optimization techniques.

\chapter{Ch 1 (only in report mode)}
\chapter{Ch 2 (only in report mode)}
\fi

Prior work~\cite{DBLP:books/crc/KatzLindell2007}




\section{Blockchain}

Ethereum Blockchain is a P2P network that stores valid transactions in the digital coin called Ether and executes any smart contracts written in language Solidity. Concretely, Ethereum Blockchain is an open-membership P2P network that accepts any nodes on the Internet to join as Ethereum users and/or miners. An Ethereum user who pays other users in Ether sends a transaction recording the payment to the Blockchain. Blockchain network consists of miner nodes, each of whom stores a copy of Blockchain data structure.

The purpose of Blockchain is to store the transaction history. The core data structure is a hash chain of ``blocks’’, where each block has a header that records the hash of previous block header and the Merle hash of all transactions that belong to the block. A valid block header also stores a solution to a computationally difficult puzzle.

The Blockchain runs decentralized consensus to synchronize minders’ views about the latest Blockchain in the presence of newly added transactions. The consensus runs asynchronously and it takes multiple rounds to reach a consensus on including a block. In each round, all miners race to solve a computationally difficult puzzle (i.e., proof of work) and the first one who find the solution gets to propose the next block, with rewards in Ether. The new block associated with the puzzle solution is broadcast to all other miners who will merge it with their local branch. For blocks that are deep enough, the Blockchain is fully synchronized among all miners. For blocks that are recently found, miners may have different views; that is, there are concurrent branches, the so-called accidental forks, that exist among different miners. As time goes by, among multiple concurrent branches, there will be one branch chosen and agreed by all miners, and other branches are orphaned. 

Ethereum Blockchain takes as input newly sent transactions, validates the transactions based on some predefined rules (e.g., no double-spending transactions are included), and add them to the Blockchain through mining-based consensus protocols. It is common to assume that a transaction in Blockchain is finalized only after a certain number of blocks are added.

Blockchain in this work is parameterized from two arguments: 1) the block time $B$ that is the average time a block is found in the Blockchain, and 2) the finality delay $F$ which is the number of consensus rounds needed to finalize a block on the Blockchain. 

Ethereum Blockchain supports smart contract. Conceptually the Blockchain is extended as a replicated state machine where the initial program state stored in one block is transitioned by a transaction into the end state stored in the next block. All miners in the Blockchain network faithfully execute the program and stores the result in their local chains. The smart contract is executed as an extension of transaction validation process where a validated transaction triggers the execution of contract encoded in it.
The Blockchain security provides the integrity and unstoppability of smart contract execution.

Ethereum exposes a Turing-complete programming language, called Solidity~\cite{me:sol}. 
An author writing a smart contract in Solidity deploys the contract to the Blockchain by encoding the compiled contract code in a transaction and assigning to it an address. 

{\it Blockchain forks}: A Blockchain system is subject to forks of different kinds, both theoretically and practically. In theory, a significant portion of malicious miners can collude and effectively fork the Blockchain. For instance, with $51\%$ computing power, the adversarial miners can choose a block in the past (arbitrarily deep in the Blockchain) and focus on mining on a fork. The majority of computing power makes sure the fork will eventually catch up. There are advanced mining strategies (e.g., selfish mining) that require lower mining power (e.g., $33\%$). In practice, controlling a significant portion of computing power in large Blockchain is hard. This class of forking attacks is not observed in large, deployed Blockchains, such as Bitcoin and Ethereum.
 
A Blockchain fork can be a transient fork among disconnected miners on recently found blocks. In a network of honest majority, transient forks will be eventually resolved. Be more specific, after the finality delay, there will be one transient fork that survive and all other computing forks will be orphaned. 

A Blockchain fork can also be a performant fork due to the need of updating Blockchain software and supporting Altcoin applications. This is the most ``practical’’ class of Blockchain forks. In the past, Bitcoin has been hard-forked into Bitcoin cash and Bitcoin core due to the different development plan of Bitcoin codebase. A miner can create an Altcoin by changing the transaction-validity rules on an existing Blockchain and starting to mine by herself.

Forking a Blockchain can be used to double-spend a transaction, withdraw a payment, enforce censorship, etc.

{\it Blockchain costs}: Blockchain charges transaction fees to include a transaction. There is a minimal transaction fee. Miners decide what’s in the next block based on the provided transaction fee. So a sender can increase the fee to improve the chance her transaction is included in the next block. 

Blockchain also charges ``Gas’’ when executing a smart contract. A user needs to specify the Gas budget when initiating a contract to run on Blockchain. The contract keeps execution until the Gas budget is consumed (by the miners running the contract). The unit Gas cost is defined for running different contract instructions~\cite{wood2014ethereum}. Gas prevents denial of service attacks in Blockchain.

\subsection{Preliminary}
{\it Blockchain forks}: A Blockchain system is subject to forks of different kinds, both theoretically and practically. In theory, a significant portion of malicious miners can collude and effectively fork the Blockchain. For instance, with $51\%$ computing power, the adversarial miners can choose a block in the past (arbitrarily deep in the Blockchain) and focus on mining on a fork. The majority of computing power makes sure the fork will eventually catch up. There are advanced mining strategies (e.g., selfish mining) that require lower mining power (e.g., $33\%$). In practice, controlling a significant portion of computing power in large Blockchain is hard. This class of forking attacks is not observed in large, deployed Blockchains, such as Bitcoin and Ethereum.
 
A Blockchain fork can be a transient fork among disconnected miners on recently found blocks. In a network of honest majority, transient forks will be eventually resolved. Be more specific, after the finality delay, there will be one transient fork that survive and all other computing forks will be orphaned. 

A Blockchain fork can also be a performant fork due to the need of updating Blockchain software and supporting Altcoin applications. This is the most ``practical’’ class of Blockchain forks. In the past, Bitcoin has been hard-forked into Bitcoin cash and Bitcoin core due to the different development plan of Bitcoin codebase. A miner can create an Altcoin by changing the transaction-validity rules on an existing Blockchain and starting to mine by herself.

Forking a Blockchain can be used to double-spend a transaction, withdraw a payment, enforce censorship, etc.

{\it Blockchain costs}: Blockchain charges transaction fees to include a transaction. There is a minimal transaction fee. Miners decide what’s in the next block based on the provided transaction fee. So a sender can increase the fee to improve the chance her transaction is included in the next block. 

Blockchain also charges ``Gas’’ when executing a smart contract. A user needs to specify the Gas budget when initiating a contract to run on Blockchain. The contract keeps execution until the Gas budget is consumed (by the miners running the contract). The unit Gas cost is defined for running different contract instructions~\cite{wood2014ethereum}. Gas prevents denial of service attacks in Blockchain.



\section{Technical Extension on Cost Optimization}

\subsubsection{Design Alternative: On-chain storage of operations}

{\bf Use Blockchain for actual log storage}: In our protocol, all operations are uploaded to the Blockchain. An alternative design is to use the Blockchain as the actual data storage. However, Blockchain is ill-suited to be data storage serving online operations. First, Blockchain incurs multiple rounds of confirmations for persisting data, leading to perceivable write latency. Second, when operations access large data records (e.g., multimedia data), storing them directly on Blockchain incurs a high cost. Therefore, in our work, we use Blockchain as a log auditor off the critical path. It records operations at a certain frequency (e.g., every 10 minutes) and only publishes the record hashes\footnote{More precisely, given a key-value record, we can publish to the Blockchain the key hash and the value hash.} to the Blockchain.

\subsubsection{Design: Storage of Historical Operations}
For consistency verification, historical operations need to be persisted. Historical operations are those operations in the previous epochs. They are needed because an operation in the current epoch returns the record written by a historical operation.

A baseline is to maintain all historical operations on chain (e.g., in a smart-contract container). A slightly better approach is to store the ``latest'' snapshot of the records in smart contract. These baselines, however, cause high Blockchain cost as 
they directly persist data on Blockchain and Blockchain is known to be expensive for data storage.

We build a Merkle tree to enable authenticated query processing between the untrusted server and the Blockchain. Briefly, the dataset that historical operations lead to is stored on the untrusted server. The historical dataset is digested by an Merkle tree. The root hash of the Merkle tree is kept in the smart contract on chain. In an epoch, when \texttt{auditLog()} is called, the ContractChecker contract will need to query the historical dataset off-chain (see the example below). When a query of a data key is sent, an ``authentication path'' is constructed by the hash of neighbor nodes along the path from the record to the root in the Merkle tree. This authentication path can be used to prove the membership (or non-membership) of the record in the historical dataset. When \texttt{auditLog()} is completed successfully, all operations in the current epoch are reflected to the off-chain Merkle tree and the on-chain hash root is updated as well.

For instance, consider the operation sequence $w_1(K),w_2(K'),r_3[w_1](K)$ where $w_1w_2(K')$ occurs in Epoch 1 and $r_3[w_1](K)$ occur in Epoch 2. For the Blockchain to assert the consistency of $r_3[w_1]$, it will need to know as of Epoch 2 whether the latest write of data key $K$ is $w_1$. The Blockchain will send out this query to the server and the server who maintains a Merkle tree of the current state (of latest records of all data keys) returns the authentication path for $w_1$, so that its freshness can be verified by the Blockchain. 


\subsubsection{Experiments: Blockchain Cost and Storage Capacity}
\begin{figure}[!hbt]
\begin{center}
\subfloat[With varying Gas cost in Ether]{
  
   \includegraphics[width=0.225\textwidth]{figures_macroycsb/exp-Gascost-Numberofoperations_temp.eps}
    \label{exp:capacityether}
}
\subfloat[Storage capacity that can be bought by $\$100$]{
\includegraphics[width=0.225\textwidth]{figures_macroycsb/exp-NumberofOperations-Timeline.eps}
    \label{exp:capacitydollar}
}
\end{center}
\caption{Storage capacity with Blockchain cost}
\label{exp:capacityether}
\vspace{-0.10in}
\end{figure} 


This experiment measures the storage capacity with transactions fee. Given a budget of Ether, ContractChecker's storage capacity is bounded which affects the number of operations the Blockchain can consume and the maximal number of clients it can support. 

In this experiment, we use the YCSB benchmark suit. To adapt YCSB to ContractChecker, we first play and record the YCSB workload trace. We then replay the trace during the experiments. In our experiments, we set an epoch to be one block time (B) and limit 140 operations per epoch (so that Blockchain is not saturated). We set finality delay to be $F\cdot{}B = 6B$.
We drive YCSB workload D (of $95\%$ reads) into ContractChecker. The workload consists of $11340$ operations in total which are evenly distributed among $81$ epochs (with each containing $140$ operations). 
We measure the Gas cost (from the transaction receipt) with the varying number of operations. The result is in Figure~\ref{exp:capacityether}. The Gas cost grows linearly with operation count. For the off-chain placement of historical operations (of both server and client logs), the total Gas is about $4.5$ Ether for $11340$ operations. 

The off-chain placement of historical operations saves $80\%$ of the cost comparing the on-chain placement.
This result shows that transaction fee is cheaper than on-chain storage in Ethereum and the off-chain placement that trades the latter for the former is cost effective.

We also convert the Ether to US dollar and show the dollar cost with ContractChecker storage capacity. Because the price of Ether in US dollar changes over time, we present the ContractChecker storage capacity allowed by $100$ dollars at a different time. The result is illustrated in Figure~\ref{exp:capacitydollar}. It shows that with $100$ dollars, the maximal capability it can buy occurs on Oct. 2015 when the Ether is cheapest. However, as the cryptocurrency price continuously drops in 2018, the ContractChecker will be more cost-effective in US dollar.


\section{Preliminary}

\subsection{Blockchain and Smart Contract}
\label{sec:prel:bkc}

Blockchain is the backend technology in today's cryptocurrencies, such as Bitcoin and Ethereum. This work considers the public Blockchain over the Internet, and do not consider permissioned Blockchains over a private ``consortium'' of players. Physically, a public Blockchain runs in a large-scale peer-to-peer network, where peer nodes, called miners, collectively maintain Blockchain data structures. The P2P network is open-membership in that anyone on the Internet can join. 

We now present the background of Blockchain system from two perspectives that are most relevant to our work: Blockchain as a distributed ledger and Blockchain as a smart-contract execution platform.

{\bf Distributed ledger}: Blockchain is a distributed ledger that stores the history of ``transactions'' for cryptocurrency payment. The Blockchain ledger can be viewed as storage that is publicly readable and is writable by decentralized authorities namely miners. In particular, writing a transaction to Blockchain goes through the following pipeline: 1) The transaction is broadcast to all miners, pending in their memory pools. 2) Pending transactions are selected (e.g., by transaction fee) to be validated based on some prescribed rules (e.g., no double spending transactions). 3) All Blockchain nodes run a consensus protocol to decide which valid transactions are to be included next in the Blockchain ledger. Following this pipeline, every ``block time'' $B$, the Blockchain is expected to produce a new block of accepted transactions. 

Writing a transaction to a Blockchain is {\it asynchronous} in the sense that it takes a long delay to confirm if the transaction is finally included in Blockchain. More precisely, only after there are $F$ blocks produced after the transaction, the transaction is considered finalized on the Blockchain. That is, it will be hard to change the transaction state on Blockchain. Writing a transaction to a Blockchain can {\it fail} in the sense that the Blockchain can drop valid transactions in some circumstances. For example, when the transaction throughput is larger than Blockchain's throughput limits\footnote{Public Blockchains are considered as low-throughput systems that accept just tens of transactions per second.} or transaction fee is too low,  Blockchain will drop transactions. In other words, Blockchain may have low write availability in the above conditions.

{\bf Contract execution}: Blockchain is also an execution platform for \emph{smart contact}. Smart contract is a program that can be executed in modern Blockchains, such as Ethereum and that is originally proposed to support financial applications over Blockchain. To execute a smart contract, the contract author writes a program, compiles it to bytecode and deploys it to the Blockchain by encoding the compiled bytecode in a special Blockchain transaction. Once the contract is deployed on all Blockchain miners, a party off-chain will be able to trigger the contract execution by sending another transaction encoding the runtime arguments. Internally, a smart contract is executed as a replicated state machine on Blockchain miners. That is, the execution instances are spawn and replicated across all miner nodes. Running a contract function is a state transition to the Blockchain where the begin and end contract states are encoded in two blocks in Blockchain and all miners running the contract race to include the execution result in the end block.

In public Blockchain, a fundamental security assumption is that the majority of miners are honest nodes in the sense that they execute the Blockchain software by honestly following the prescribed protocol. In the case of 51\% attacks where the majority of miners are malicious, many Blockchain security properties are broken. In practice, compromising $51\%$ of miners in a large-scale Blockchain network is extremely hard and we believe this is reasonable to assume an honest majority. There are more sophisticated attacks, such as selfish mining~\cite{DBLP:conf/fc/EyalS14}, that require only $33\%$ malicious miners, but they never happen in practice and we do not consider them in this paper.

{\bf Blockchain forks}: This work focuses on practical forks in real-world public Blockchains, and excludes theoretic Blockchain forks (due to $51\%$ attacks, selfish mining, etc.). There are two types of Blockchain forks: a transient fork among miners on recently found blocks, and a permanent fork among different Blockchain networks. 
The transient fork (the former) in a public Blockchain is eventually resolved after the finality delay when all miners reach consensus on one fork while other forks are orphaned. The permanent fork (the latter) is caused by the ``hard fork'' in Blockchain software updates (e.g., the case of bitcoin and bitcoin cash), launching an Alt coin (i.e., by running Blockchain software among a group of friends), etc. It is found common in practice. 

{\bf Blockchain cost} includes the fee to send a transaction and the cost of running smart-contracts. The higher a transaction fee is, the more likely the transaction will be included in the next block. For the smart-contract, any contract on chain needs to be associated with a cost budget, called ``Gas'', which bounds the execution time of the contract and is a mechanism for the defense of DoS (denial of service) attacks.

\section{Misc. of the system}

\subsubsection{ContractChecker Epoch Configuration}
\label{sec:settinge}

ContractChecker runs in epochs. The duration of an epoch $E$ can be configured in practice to respect various application-level requirements. In general, a large $E$ is preferred when 1) the application can afford longer delay in consistency assertion, 2) the clients tend to be available in a longer time period after their interaction with the cloud server, 3) there are more clients producing more attestations transactions in an epoch.

While the first two requirements are applications specific, we present a model for the third requirement. For simplicity, we consider epoch duration $E$ is set to be multiple of the block time $B$, namely $E=e\times{}B$. 
The value of $e$ must be set large enough to avoid the attestation transactions saturate the Blockchain. For instance, suppose there are $N=30$ clients and a Block can only store 20 transactions. Setting $e=1$ may saturate the Blockchain limited throughput as every block time, the protocol produces $30+1$ transactions which are above what the Blockchain can ingest (i.e., $20$ transaction per block). In this case, it is advised to configure $e\geq{2}$, such that the $31$ attestation transactions produced in each epoch can be amortized to at least two blocks.

\subsubsection{Identity Management}
\label{sec:identity}
In ContractChecker, both clients and the server are registered in the sense that their public keys are known by the contract code. The public keys are used to verify the log attestations from clients and the server. The log verification is necessary to prevent anyone from injecting arbitrary operations in the log which can easily obstruct the consistency assertion.

To set up the public keys, we assume a secure key-distribution channel exists. Clients can dynamically join and register; we assume an external trusted identity provider in place who assists the user authentication and sends the new public keys to the smart contract.

The clients and server can reuse the public key pair in their Blockchain wallets for ContractChecker operations. In this work, we assume the secret keys are securely managed by clients and server offline. With securely managed keys, a variety of attacks, e.g., clients and server impersonation, are prevented.



\section*{Acknowledgement}
Yuzhe (Richard) Tang's work is supported by National Science Foundation under Grant CNS1815814 and a gift from Intel. Jianliang Xu's work is supported by Hong Kong RGC grants C6030-18GF, C1008-16G, and 12201018. The authors thank Yue Cheng for the discussion of this work in the early stage.


\section{Introduction}
Providing consistency guarantees is a security measure for outsourced data storage in the cloud (e.g., Dropbox~\cite{me:dropbox} and Amazon S3~\cite{me:s3}), and becomes increasingly important and pressing in an age when cloud incidents are the norm.
The consistency of a data storage dictates how reads/writes should be ordered and whether a read should reflect the latest write (i.e., freshness). This property can be easily exploited by a malicious cloud provider and leads to severe security consequences. For instance, when the cloud storage hosts a pubic-key directory (as in certificate-transparency schemes~\cite{me:ct}), a malicious cloud violating storage consistency can return to the user a stale key (i.e., a public key revoked by its owner), which leads to unauthorized access to protected data. Providing storage consistency guarantee is critical to supporting many security infrastructures in the cloud (e.g., DNS server, Github/DockerHub, personal data hosting).

The problem of verifying remote storage consistency entails two steps: W1) establishing a globally consistent view of operation history across clients (i.e., log attestation), and W2) auditing the log for storage consistency (i.e., log auditing). Most existing approaches, including SUNDR~\cite{DBLP:conf/osdi/LiKMS04}, Caelus~\cite{DBLP:conf/sp/KimL15}, CloudProof~\cite{DBLP:conf/usenix/PopaLMWZ11}, etc., rely on trusted clients to carry out both steps (i.e., W1, W2). Recent work on Blockchain logging, notably Catena~\cite{DBLP:conf/sp/TomescuD17}, delegates the first step (W1) to the Blockchain as an append-only log (see \S~\ref{sec:rw:consistency} and \S~\ref{sec:analsysisexisting} for details), yet relying on individual clients to carry out the second step. 
Existing works place a burden on clients to do log auditing and are impractical for emerging applications with low-power clients such as smartphone and IoT devices; see \S~\ref{sec:targetapp} for a list of target applications.

We propose ContractChecker, a security protocol for Blockchain-based consistency verification. Distinct from existing works, ContractChecker uniquely delegates both log attestation (W1) and log auditing (W2) to Blockchain. By this means, it reduces the client-side load to a minimum (i.e., checking a client's local operation history), and lends itself to our target applications with low-power clients.
The ContractChecker protocol is materialized on Blockchain by expressing the logic of consistency checks in smart contracts. 
The ContractChecker protocol can detect any storage inconsistency by a MitM cloud server, and the security is reduced to the integrity of executing smart contracts.

Public Blockchain is known to have a limitation in high cost and confirmation delay. The Blockchain limitation presents challenges in ContractChecker for security and cost-effectiveness. First, the long transaction-confirmation delay in Blockchain can lead to new vulnerabilities. Concretely, updating an on-chain state takes a conceivable time to finalize, which opens a time window for an adversary to revert the state. This vulnerability can be exploited by malicious miners to trick the Blockchain to land incorrect checking results. We propose a delay-aware schedule to execute the ContractChecker protocol in a way that the protocol events are well coordinated with the life cycle of underlying transactions. The security and correctness of checking results are guaranteed by the invariant that the on-chain checks occur only over the data that is finalized.

Second, the high unit cost of Blockchain presents a challenge in practice. Consider the baseline protocol design that logs every storage operation by a dedicated transaction and that stores the entire operation history on Blockchain. This baseline leads to high cost in both transaction fee and contract-execution fee (i.e., Gas cost in Ethereum~\cite{me:eth}). This contradicts the very first reason of cloud data outsourcing, namely the cloud offers a cheaper solution for storage (i.e., cost-effectiveness). To optimize the cost, we propose techniques exploring various design choices on on-/off-chain storage and operation-transaction batching, etc.

We build a prototype system materializing the ContractChecker design on Ethereum~\cite{me:eth}. We write smart contracts expressing the logical checks and cryptographic operations on chain. Comprehensive security analysis is conducted by considering consistency attacks and new Blockchain-specific attacks. 

ContractChecker presents to end users a consistency-checking service that charges fee for data management on Blockchain. We evaluate the cost-effectiveness of this service under YCSB workloads~\cite{DBLP:conf/cloud/CooperSTRS10}. Our results show that on Ethereum, ContractChecker is the most inexpensive when placing the log storage off chain. The off-chain placement saves up to $80\%$ of the cost comparing an on-chain placement. ContractChecker can support $613710$ operations at the cost of $\$100$ US dollars at a real Ether price.

The contributions of this work are:

1. {\bf New use of Blockchain}: This work proposes a new use of Blockchain for cloud-storage verification. Unlike existing research, the work delegates both log attestation and log auditing on Blockchain which reduces the client cost for consistency verification (\S~\ref{sec:analsysisexisting}). 

2. {\bf Security protocol}: New security attacks are identified due to the new use of Blockchain, and new security protocols that schedule the on-chain events for consistency checking are proposed (\S~\ref{sec:secureprotocols}).

3. {\bf Blockchain cost optimization}: Delegated log auditing requires placing individual operations on chain. To save the Blockchain cost, we propose a series of optimization techniques by exploring design choices in storage placement and operation batching, etc. (\S~\ref{sec:costopt}).

4. {\bf Prototyping and evaluation}: We implement a ContractChecker prototype on Ethereum. Through experiments of both micro-benchmarks and macro-benchmarks based on YCSB, it shows the cost-effectiveness of the ContractChecker protocol (\S~\ref{sec:eval}).

\section{Preliminaries}
\label{sec:preliminary}

\subsection{Secure Consistency Verification Protocols}
\label{sec:rw:consistency}
Verifying the consistency of untrusted storage entails two steps: log attestation and log auditing.
In the step of log attestation, the untrusted server attests to the global log against a trusted attester and the clients verify the correctness of log attestation. The purpose of having the attester is to ensure there is a single view of the global log and to prevent the server from mounting the forking attack~\cite{DBLP:conf/podc/MazieresS02}. Once a global log (without fork\footnote{Note that the forking attack differs the Blockchain forks caused by software updates.}) is constructed, the second step can take place which is to check the consistency conditions over the established global history.

SUNDR~\cite{DBLP:conf/osdi/LiKMS04} is a secure log attestation scheme without trusted third party. SUNDR directly sends the server attestation to individual clients, which can be seamlessly and elegantly integrated to the data plane of serving reads/writes.
SUNDR achieves the level of fork consistency that any forking attack will be eventually detected. 
Caelus~\cite{DBLP:conf/sp/KimL15} is a log attestation scheme that rotates (or time-share) the role of attester among a group of personal devices. Caelus runs an epoch-based protocol for log attestation. Caelus audits the log and checks a variety of consistency models, by requiring each client to download the global operation history.
Similarly, CloudProof~\cite{DBLP:conf/usenix/PopaLMWZ11} relies on trusted data owners to attest to the server's claim of log and to audit the operation history. 
Catena~\cite{DBLP:conf/sp/TomescuD17} is a log-attestation scheme based on Blockchain.
Catena prevents the server forking attack by running an auditing pass on clients. 
In Catena, the security of preventing forking attacks is reduced to the Blockchain's security in preventing double-spending attacks. 

\label{sec:analsysisexisting}
All existing works rely on trusted clients (or data owners) to audit the log and check consistency conditions, as illustrated in Table~\ref{tab:distinct}. In this respect, ContractChecker is the first scheme that delegates both log attestation and log auditing to the trusted-third party Blockchain.

\begin{table}[!htbp] 
\caption{Distinction of the ContractChecker design: \xmark\xspace means the log operation is not supported by Blockchain, but instead by clients.}
\label{tab:distinct}\centering{\small
\begin{tabularx}{0.49\textwidth}{ |X|c|c| }
  \hline
Solutions & Attestation & Auditing 
\\
 & by Blockchain & by Blockchain
\\ \hline
SUNDR~\cite{DBLP:conf/osdi/LiKMS04}, 
Caelus~\cite{DBLP:conf/sp/KimL15}, CloudProof~\cite{DBLP:conf/usenix/PopaLMWZ11} & \xmark & \xmark
\\ \hline
Catena~\cite{DBLP:conf/sp/TomescuD17} & \cmark & \xmark
\\ \hline
 {\bf ContractChecker}& \cmark &  \cmark
\\ \hline
\end{tabularx}
}
\end{table}

\ifdefined\TTUT
\subsection{Preliminary: Caelus and Catena (Fork)}

In Cealus, a server sends an attested log to an attester who signs one attestation in one epoch. The server then broadcasts signed attestation to all clients, who will verify/audit the attestation against their local log. In Caelus, it is crucial that an attestation is not forked, as forking different attestations for verification at different clients’ sites is an effective way to conceal inconsistency. No forked attestation is assured in Caelus that there is only one known attester.

Catena delegates the Cealus attester to Blockchain. Like in Caelus, it is crucial to assure that the server does not fork attestation to the Blockchain. This can be done by having trusted clients to download the 100GB Blockchain and to check no double attestations on the same epoch. 

Catena makes this no-fork checking on Blockchain more efficient. In Catena, the clients do not download 100GB Blockchain, instead, they download the history of Catena transactions. No fork can be checked by any Catena transaction fully spending its predecessor transaction. In other words, there is no double-spend transaction in 100 GB Blockchain. 
\fi

\subsection{Blockchain and Smart Contract}
\label{sec:prel:bkc}

Blockchain is the backend technology in today’s cryptocurrencies, such as Bitcoin and Ethereum. This work considers the public Blockchain over the Internet, and don’t consider permissioned Blockchains over a private ``consortium'' of players. Physically, a public Blockchain runs in a large-scale peer-to-peer network, where peer nodes, called miners, collectively maintain Blockchain data structures. The P2P network is open-membership in that anyone on the Internet can join. 

We now present the background of Blockchain system from two perspectives that are most relevant to our work: Blockchain as a distributed ledger and Blockchain as a smart-contract execution platform.

{\it Distributed ledger}: Blockchain is a distributed ledger that stores the history of ``transactions’’ for cryptocurrency payment. The Blockchain ledger can be viewed as storage that is publicly readable and is writable by decentralized authorities namely miners. In particular, writing a transaction to Blockchain goes through the following pipeline: 1) The transaction is broadcast to all miners, pending in their memory pools. 2) Pending transactions are selected (e.g., by transaction fee) to be validated based on some prescribed rules (e.g., no double spending transactions). 3) All Blockchain nodes run a consensus protocol to decide which valid transactions are to be included next in the Blockchain ledger. Following this pipeline, every ``block time’’ $B$, the Blockchain is expected to produce a new block of accepted transactions. 

Writing a transaction to a Blockchain is {\it asynchronous} in the sense that it takes a long delay to confirm if the transaction is finally included in Blockchain. More precisely, only after there are $F$ blocks produced after the transaction, the transaction is considered finalized on the Blockchain. That is, it will be hard to change the transaction state on Blockchain. Writing a transaction to a Blockchain can {\it fail} in the sense that the Blockchain can drop valid transactions in some circumstances. For example, when the transaction throughput is larger than Blockchain’s throughput limits\footnote{Public Blockchains are considered as low-throughput systems that accept just tens of transactions per second} or transaction fee is too low,  Blockchain will drops transactions. In other words, Blockchain may have low write availability in the above conditions.

{\it Contract execution}: Blockchain is also an execution platform for \emph{smart contact}. Smart contract is a program that can be executed in modern Blockchains, such as Ethereum and that is originally proposed to support financial applications over Blockchain. To execute a smart contract, the contract author writes a program, compiles it to bytecode and deploys it to the Blockchain by encoding the compiled bytecode in a special Blockchain transaction. Once the contract is deployed on all Blockchain miners, a party off-chain will be able to trigger the contract execution by sending another transaction encoding the runtime arguments. Internally, a smart contract is executed as a replicated state machine on Blockchain miners. That is, the execution instances are spawn and replicated across all miner nodes. Running a contract function is a state transition to the Blockchain where the begin and end contract states are encoded in two blocks in Blockchain and all miners running the contract race to include the execution result in the end block.

In public Blockchain, a fundamental security assumption is that the majority of miners are honest nodes in the sense that they execute the Blockchain software by honestly following the prescribed protocol. In the case of 51\% attacks where the majority of miners are malicious, many Blockchain security properties are broken. In practice, compromising $51\%$ of miners in a large-scale Blockchain network is extremely hard and we believe this is reasonable to assume an honest majority. There are more sophisticated attacks, such as selfish mining~\cite{DBLP:conf/fc/EyalS14}, that require only $33\%$ malicious miners, but they never happen in practice and we don’t consider in this paper.

{\it Blockchain forks}: A Blockchain system is subject to forks of different kinds, both theoretically and practically. In theory, a significant portion of malicious miners can collude and effectively fork the Blockchain. For instance, with $51\%$ computing power, the adversarial miners can choose a block in the past (arbitrarily deep in the Blockchain) and focus on mining on a fork. The majority of computing power makes sure the fork will eventually catch up. There are advanced mining strategies (e.g., selfish mining) that require lower mining power (e.g., $33\%$). In practice, controlling a significant portion of computing power in large Blockchain is hard. This class of forking attacks is not observed in large, deployed Blockchains, such as Bitcoin and Ethereum.
 
A Blockchain fork can be a transient fork among disconnected miners on recently found blocks. In a network of honest majority, transient forks will be eventually resolved. Be more specific, after the finality delay, there will be one transient fork that survive and all other computing forks will be orphaned. 

A Blockchain fork can also be a performant fork due to the need of updating Blockchain software and supporting Altcoin applications. This is the most ``practical’’ class of Blockchain forks. In the past, Bitcoin has been hard-forked into Bitcoin cash and Bitcoin core due to the different development plan of Bitcoin codebase. A miner can create an Altcoin by changing the transaction-validity rules on an existing Blockchain and starting to mine by herself.

Forking a Blockchain can be used to double-spend a transaction, withdraw a payment, enforce censorship, etc.

{\it Blockchain costs}: Blockchain charges transaction fees to include a transaction. There is a minimal transaction fee. Miners decide what’s in the next block based on the provided transaction fee. So a sender can increase the fee to improve the chance her transaction is included in the next block. 

Blockchain also charges ``Gas’’ when executing a smart contract. A user needs to specify the Gas budget when initiating a contract to run on Blockchain. The contract keeps execution until the Gas budget is consumed (by the miners running the contract). The unit Gas cost is defined for running different contract instructions~\cite{wood2014ethereum}. Gas prevents denial of service attacks in Blockchain.

\section{Research Formulation}
\subsection{Motivating Applications}
\label{sec:targetapp}


While ContractChecker can definitely benefit small-scale cloud-hosted
applications such as smart homes~\cite{bolt_nsdi14}, we argue that
ContractChecker can be utilized in a long spectrum of application
scenarios, ranging from low-throughput small
organizations~\cite{bolt_nsdi14}, to enterprise-scale cloud object
stores~\cite{docker_fast18}. In the following we list two representative
examples of real-world use cases. 

{\it
DockerHub style container-distribution infrastructures} (hereafter
called ContainerRegistry):
The ``ContainerRegistry'' distributes the latest software from
developers to users in the form of Docker container images. The
ContainerRegistry is usually hosted in third-party public cloud, such
as in hub.docker.com, which is independent of both developers and
users. The storage consistency implies security as returning a stale
image (violating the strong consistency) from the hub means the users
may run buggy programs, vulnerable to the latest attacks. The
ContainerRegistry is usually accessed infrequently. For instance,
workload analysis on IBM Docker Registry reports that, among seven
geo-distributed registry deployments, the busiest one serves only 100
requests per minute for more than $80\%$ of
time~\cite{docker_fast18}\footnote{The workloads exhibit diurnal
patterns and the peak throughput is remarkably low as well.}.

{\it
Certificate-transparency(CT) log}: The CT log stores the
certificates about key-identity bindings, and is made public to
invite public scrutiny for timely detection of certificate mis-issuance.
Violating storage consistency in CT log
leads to the security breaches such as concealing of mis-issued certificate or use of revoked keys.
The load of writes in a CT log (regenerating/revoking a public key) is usually low and the read load is not high on a small number of domains (websites).

Additional relevant scenarios such as device synchronization through cloud and Github-hosted software development are found in Appendix \S~\ref{sec:additionalapp}.
These application scenarios feature the following properties that motivate the use of Blockchain: 
S1) The clients are of limited capability in computing, storage, and availability. Thus they outsource data storage to a third-party cloud. In both scenarios above, the client can be a mobile phone (e.g., hosting a web browser against a CT log or installing security patches against a ContainerRegistry). 
S2) On the cloud-hosted data storage, violating storage consistency leads to a security consequence to the application. Intuitively, using a Blockchain as a ``trusted’’ third-party witness can harden the application security.
S3) The storage-access load in our application scenarios is typically lower than tens of operations per second. In particular, the low throughput properties of these typical application scenarios make it amenable for the use of Blockchain, which is known to have limited throughput in ingesting transactions.

\subsection{System and Security Model}

Our system model consists of three parties: a storage server in the cloud, multiple concurrent clients and the Blockchain. Clients submit storage operations (i.e., data reads and writes) to the storage server. The operations are witnessed by the Blockchain via our ContractChecker protocol. 

\subsubsection{\bf Clients}

Clients are data owners who outsource the data storage to the cloud. They submit operations to the cloud storage to read or update their data. Different clients' operations may occur concurrently, that is, the cloud service may process multiple operations in parallel, with their time intervals overlapped. 
A client can be active when she has submitted operations recently (we will explain the definition of active clients later) and inactive when she goes offline without any operations on the cloud.

Clients in our model are \emph{stateless} in the sense that a client does not persist state across active sessions. That is, a client does not need to remember her past operations when she is engaged with a cloud. In addition, among clients, there are no direct communication channels. That is, other than the cloud or Blockchain, clients do not communicate out-of-band. We believe this model reflects low-power clients in many real-world situations. For example, in ContainerRegistry and CT log, clients can be web browsers running on smart phones. Web clients are stateless and do not directly communicate among themselves.

We assume each client is identified by her pseudonymous ID, say her public key. A client knows all other clients' public keys. We assume a protected communication channel or a trusted PKI offline to securely distribute public keys. The client identity management is describe in more details in Appendix \S~\ref{sec:setup}.

We assume clients share synchronized clocks by running NTP protocols. Synchronized clocks will be useful in our protocol when clients are required to log operations. The accuracy of NTP protocols may affect the precision of our consistency verification results. Existing protocols can achieve highly synchronized clocks and limit clock skews to the level of milliseconds~\cite{DBLP:journals/tocs/CorbettDEFFFGGHHHKKLLMMNQRRSSTWW13}, which we believe are sufficient in our system.

\subsubsection{\bf Cloud storage service}

The cloud service hosts a data store shared among multiple clients. The service accepts clients' requests and process them concurrently. That is, different operations from clients may be processed in parallel and in an out-of-order fashion.

Under this execution model, we consider strong consistency or linearizability~\cite{DBLP:journals/toplas/HerlihyW90}. Linearizability considers independent access to different data records and is sufficiently strong to capture necessary conditions in many security scenarios~\cite{DBLP:conf/sp/KimL15,DBLP:conf/usenix/PopaLMWZ11}. Weaker consistency that is widely adopted in modern cloud services~\cite{DBLP:journals/cacm/Terry13} is commonly less relevant to security-sensitive and critical applications. In this paper, we do not consider database serializability or isolation under multiple keys~\cite{DBLP:books/aw/BernsteinHG87}. 

We assume the cloud service makes a consistency-centric service-level agreement (SLA)~\cite{DBLP:conf/sosp/TerryPKBAA13} with the clients which states where the cloud service promises to guarantee strong consistency (more specifically, linearizability as will be defined next) over the operations it will serve. An honest server will enforce the promised consistency conditions during operational hours. 

A malicious storage server will violate the consistency conditions (as will be elaborated on), by returning a stale result for a read. In addition, a malicious server will not follow our ContractChecker protocol and tries to conceal the operation inconsistency from clients.
Consistency violation, if left undetected, can lead to severe security consequences such as impersonation attacks (recall \S~\ref{sec:targetapp}).

Moreover, we assume the cloud service is rational. While a malicious cloud server may forge operations to make an inconsistent operation history look like consistent (i.e., concealing the inconsistency), the server will not attempt to make a consistent operation history look like inconsistent. We believe this assumption reflects practical situations with SLA where the cloud server will be charged in case of verified inconsistency, and thus does not have the incentive to forge an inconsistent history.

\label{sec:cons}
{\it Consistency definition}:
We consider the storage service exposes a standard key-value API, where each data record is a key-value pair and each storage operation accesses target records by data key.
A storage operation, be it a read or write, is specified by two timestamps, which respectively represent 1) the begin time when the request of the operation is sent by the client, and 2) the end time when the response of the operation is received by the client. Formally, given a key-value pair $\langle{}K,V\rangle{}$, a read operation is $V=r_{[t_b,t_e]}(K)$ and $\texttt{ACK}=w_{[t_b,t_e]}(K,V)$. Here $r/w$ denotes read or write operation. $t_b<t_e$ and they are the begin and end timestamps. If two operations are concurrent, their time intervals $[t_b,t_e]$ may overlap.

An operation history is linearizable if the following two conditions are met: 1) All operations can be mapped to a total-order sequence that is compatible with the real-time intervals of the operations. 2) There is no stale read on the total-order sequence. That is, any read operation should return the record that is fresh on the total-order. This property is also called read freshness.

Any linearizable operation history can be represented by a totally-ordered operation sequence. We denote an operation sequence by operation indices.
For instance, in $w_1w_2r_3[w_2]$, the subscription is the operation index in the total-order (described below).
Linearizability specifies operations of the same data key; for simplicity, we omit data key in this notation.
The square bracket of a read indicates the result record. 
$r_3[w_2]$ denotes a read operation ordered as the third operation in the total-order sequence and which returns the record written by write $w_2$. 

{\it Network}: In this work, we assume a reliable network among clients, the server and Blockchain nodes. When one party sends a message to the network, the network will deliver the message to the receiver with negligible delay (comparing with the period our protocol runs). We don’t consider network faults or partition in this work.

\subsubsection{\bf Blockchain}

The Blockchain in our protocol is a public, permissionless Blockchain running over a large P2P network and supporting smart contract execution. Real-world examples include Ethereuem and the latest version of Bitcoin. In this setting, we assume the honest majority among Blockchain miners. We believe this is a reasonable assumption as in practice there are no successful $51\%$ attacks on Bitcoin or Ethereum.

The Blockchain in our protocol is parameterized by two arguments: block time $B$, which is the average time to find a block in a Blockchain; and finality delay $F$, which is the number of blocks needed to be appended after a finalized transaction. That is, a transaction is considered to be finalized in Blockchain when there are at least $F$ blocks included in the Blockchain after the transaction.

The Blockchain supports the execution of smart contracts. The contract is executed across all Blockchain miners. It guarantees the execution integrity and non-stoppability. That is, the Blockchain truthfully executes a smart contract based on the provided arguments, despite of the attacks to subvert the Blockchain (as described below). Once the execution of a contract starts, it is hard to stop the execution or to abort. 

{\it Blockchain write availaility}: The Blockchain may drop transactions based on its current load and transaction fee. A transaction with a higher fee will have a lower chance of being dropped~\cite{DBLP:conf/sp/TomescuD17} and have shorter latency to be included. This assumption will be tested in our evaluation.

{\it Blockchain attacks}: The Blockchain is subject to a series of threats. In this work, we focus on practical Blockchain threats and exclude the theoretic threats (e.g., $51\%$ attacks, selfish mining, etc.). 1) A Blockchain client may have her secret key stolen, and this coin stealing incidents have occurred frequently~\cite{XXX}. 2) The Blockchain may be forked permanently due to software update as in the case of Bitcoin cash (Blockchain forks). 3) Smart contacts may contain security bugs that can be exploited by a vector of attacks~\cite{XXX}, such as reentrancy attacks, buffer overflow attacks, etc. In practice, the DAO (decentralized autonomous organization) incidents are caused by this attack vector.

\subsection{Goals}

\subsubsection{\bf Security Goals}

In our system, there are two main threats: 1) In the case that inconsistency occurs, the malicious server wants to hide the inconsistency from victim clients. 2) In the case that all operations are consistent, a malicious client may want to accuse the benign server of the storage inconsistency that does not occur. We exclude other cases as they are not rational. For instance, we don’t consider that a rational server will forge operations such that a consistent operation history will appear inconsistent. We also don’t consider that a victim client will want to hide an inconsistent operation history. Due to this reason, we assume clients and the server will not collude to either hide inconsistency or accuse of false consistency.

Our security goals are listed below:

{\it Timely detection of inconsistency against malicious server}: A malicious server cannot hide the occurrence of inconsistent operations from victim clients. To be concrete, when inconsistency occurs, the protocol will assert there are inconsistent operations in a timely manner, even when a malicious server can forge a seemingly consistent log. In addition to that, the protocol will present a verifiable proof of the inconsistency, so that it can penalize the cloud service violating the consistency.

{\it No false accusation of inconsistency against malicious clients}: A malicious client cannot falsely accuse a benign server of inconsistency that does not occur. Given a consistent operation history, the protocol will assert it is consistent, even when there are malicious clients who want to forge inconsistent operations in the log.

\subsubsection{\bf Cost Goals}

{\it Client cost}: Clients in our protocol can remain stateless. That is, running the ContractChecker protocol, a client does not need to store her operations indefinitely and can truncate operations after use (i.e., stateless). In addition, the protocol data stored on a client is limited to the client’s local operation; a client does not need to store other clients’ operations (i.e., local operations). These two requirements make clients lightweight and render the protocol applicable to scenarios with low-power clients.

{\it Blockchain cost}: Blockchain cost, including transaction fee and the cost of running smart contract, should be reduced as much as possible to save the monetary cost of using the protocol. This presents an optimization goal of our work.

\subsubsection{\bf Non-goals}

{\it Data authenticity}: Data authenticity states a malicious cloud service cannot forge a client's data without being detected. We assume an external infrastructure in place that ensures data authenticity, such as MAC or digital signatures. To be more specific, the client who writes a record signs the record, and the signature can be verified to guarantee the data authenticity of the record. Here, clients’ public keys are securely distributed by a PKI or secure communication channel.

{\it Collusion}: In ContractChecker, we aim at security guarantees against a malicious cloud server and malicious clients. 
However, if the two parties collude, it will make the attack detection difficult, if not impossible. 
To be concrete, when a server colludes a client, the server can inject arbitrary operations at an arbitrary location in the server attestation, in such a way that any third-party cannot detect. This can be done easily by the server forging an operation with valid signatures from the colluding client. With the ability to forge a ``valid'' operation, one can affect the consistency of other operations (e.g., from benign clients): A consistent read can be mis-reported to be an inconsistent read if there is a forged write before it. An inconsistent, stale read can be concealed if one forges a delete that removes the fresh write. This makes it theoretically difficult to provide consistency guarantees in the presence of colluding server and clients. Due to this reason, we exclude from our threat model the collusion among clients and server. 
In practice, we believe server-client collusion is a rare situation.

{\it Contract program security}: Smart contract program in ContractChecker may be subject to existing attacks, such as reentrancy attacks, buffer overflow, etc. We assume external defense mechanisms, such as proper use of synchronization/mutex, boundary checks, etc. We don’t particularly address the protection at programming-language level.

\ifdefined\TTUT

\subsection{Research Goals}


{\it Problem statement}: This work aims at providing consistency guarantees of a remote low-throughput storage system, 1) with the security against a malicious server, 2) at a minimal cost to the clients, and 3) by a small cost of Blockchain. To be more specific, the security of our scheme can detect any inconsistency behavior of the malicious server. 
The cost of a client should be proportional to the size of the client's local operation history, and is independent of the global operation history.
The cost of the Blockchain should be as low as possible for the practical and cost-effective use of the scheme. 

{\it Assumptions and non-goals}: 
1) We assume our data model contains only non-identifiable information (e.g., operation type, time, data key being accessed) which can be safely published to the Blockchain. If there is identifiable information, it is hashed before being put into key-value records. By this means, we provide the basic level of user privacy. The privacy under linkage attacks and side-channel attacks~\cite{DBLP:conf/sp/NarayananS09,DBLP:journals/corr/abs-0903-3276} is out of the scope. 
2) We assume the storage throughput in the target storage is lower than that of  Blockchain. The system administrator is assumed to have sufficient funds to purchase enough storage space on Blockchain. This setting should admit various real-world applications as described in \S~\ref{sec:targetapp}. 
We do not aim at improving the Blockchain throughput in this paper. 
3) This work focuses on logical flaws of smart contracts. We assume the contracts we developed is either free of programming bugs or can be effectively debugged by external tools (e.g., following programming patterns~\cite{me:contractpattern}).
\fi

\section{The Security Protocols}
\label{sec:secureprotocols}

\subsection{Design Motivation}

The key design in ContractChecker is to use Blockchain to audit the log in a client-server system (recall Table~\ref{tab:distinct}). This use of Blockchain is motivated by our observations below:

{\it 1) Low cost on stateless clients}: By delegating log audit to the Blockchain, one can significantly relieve the burden from the clients. Existing consistency-verification protocols are based on client-side log auditing~\cite{DBLP:conf/sp/TomescuD17,DBLP:conf/sp/ZyskindNP15}, which requires a client to persist not only her own operations but also operations of all other clients, rendering it impractical for stateless clients. Delegating log auditing to the Blockchain, clients are relieved from storing any state about operations. Ideally, a client’s job is reduced to receiving log-audit results from the Blockchain.

{\it 2) Security without client availability}: To guarantee the protocol correctness under attacks, existing client-based schemes (e.g., Caelus) assume highly available clients, that is, they have to be online every epoch to participate in the periodic log auditing (see \S~\ref{XXX} for detailed analysis). Briefly, without highly available clients, it cannot distinguish the case of an offline client and the case of an online client reporting an attack but whose report gets suppressed by the untrusted server. 

Our work is motivated by that Blockchain can be used as a trusted ``communication channel’’ to report attack detection without assuming client availability. As we will see (in \S~\ref{XXX}), the proposed protocol allows an inactive client (who did not submit any operation in a given epoch) to be offline and not to participate in the protocol execution. Intuitively, this is realizable because the trusted communication enabled by Blockchain will not omit messages among clients.


\subsection{Protocol Overview}
\label{sec:overview}

ContractChecker is a protocol that runs among clients, a storage server and the Blockchain. The purpose of the protocol is to present a trustworthy assertion about the consistency of the operations among clients and the server. At a high level, the protocol works by asking clients and the server to attest to their views of operations to the Blockchain where different views are crosschecked and consistency conditions are verified. An attack from a malicious server (or client) by forging her view of the log can be detected and mitigated by the 
crosscheck on Blockchain.

In our protocol, the interaction between the Blockchain and the clients/server off chain can be described by 
the following three functions. Note that the protocol runs in epochs and here we consider the operations in one epoch.

\begin{itemize}
\item
$S.\texttt{attestServerLog}(Ops_S, sk_S)$: Server $S$ declares a total-order over the global history of operations in the current epoch ($Ops_S$). She attests to the declared total-order sequence by signing it with her secret key $sk_S$. 

\item
$C.\texttt{attestClientLog}(Ops_C, sk_C)$: An active client $C$ attests to her local operations in the current epoch ($Ops_C$) by signing it with her secret key $sk_C$. The local operation o a single client can also be concurrent and it does not need the client to declare a total-order. If a client is inactive, meaning she did not submit any operation in the epoch, she does not need to call this function. 

\item
$C.\texttt{consistencyResult}() = \{Y, N\}$: A client $C$ can check consistency of the current operation history. With Blockchain, the checking result is only valid when the attestations are finalized on the chain. This function is blocking until the finality is confirmed. If the attestations are not finalized, it will retry by calling \texttt{attestClientLog}.
\end{itemize}

\subsection{Design Alternatives}

We present alternative protocol designs that we encountered, in order to examine the design space and to justify our design choices. 

{\it No server attestation}: In our protocol, both clients and the server attest to their views of operation histories. An alternative design is to collect the operation history only from clients. In this scheme, all clients send their local operations to the Blockchain without collecting the server log. The union of client logs can reconstruct all operations and their relations in real time (i.e., serial or concurrent with each other). However, it does not have the total-order information necessary to determine the operation consistency (Recall \S~\ref{sec:cons}). Relying on the smart contracts to ``solve’’ the consistency total-order out of concurrent operation history, it would be an expensive approach. Therefore, we rely on the (untrusted) server to declare the consistency total-order in her attestation to the Blockchain. In addition, without server attestation, the protocol will be vulnerable under  malicious clients. Also note that Catena has studied the design choice without client attestations.

{\it Use Blockchain as data storage}: In our protocol, all operations are uploaded to the Blockchain. An alternative design is to use the Blockchain as the actual data storage. However, Blockchain is ill-suited to be data storage serving online operations. First, Blockchain incurs multiple rounds of confirmations for persisting data, leading to perceivable write latency. Second, when operations access large data records (e.g., multimedia data), storing them directly on Blockchain incurs a high cost. Therefore, in our work, we use Blockchain as a log auditor off the critical path. It records operations at a certain frequency (e.g., every 10 minutes) and only publishes the record hashes\footnote{More precisely, given a key-value record, we can publish to the Blockchain the key hash and the value hash.} to the Blockchain.

{\it Synchronize contract functions}: Conceptually, our high-level goal is to delegate the work of log auditing to the Blockchain. The work consists of log attestation, log crosscheck and consistency checking. For correctness, these three steps have to be run serially. Our original design is to implement the three steps in three ``public’’ contract functions which can be called from off-chain. However, the order in which the functions are called off-chain may differ from the order in which they get executed on individual miners. For instance, if a Blockchain client serially calls attestation, crosscheck and checking, the three functions may be delivered to an individual miner in a different order, say checking, crosscheck, attestation. One can rely on clients to synchronize different contract calls, say by requiring a client only calls crosscheck until it confirms the finality of the call of log attestation. However, this client-side synchronization is extremely slow and unnecessarily time-consuming.

Therefore, in our work, we implement the step of log attestation by a public contract function and the other two steps by a private contract function. A private contract function is called by another contract function and cannot be called from off-chain clients. By this means, the serial order is ensured directly by individual miners without expensive client-side finality confirmation.


\subsection{The Protocol: Execution and Construction}
\label{sec:basicprotocol}
In this section, we present the protocol in the top-down fashion. We first describe the overall protocol execution flow involving both on-chain and off-chain parties. We then describe the construction of the protocol with the details of the various primitives used in the construction..

\subsubsection{\bf Protocol Execution}


We present the overall protocol execution. The ContractChecker protocol runs in epochs. Each epoch is of a pre-defined time interval $E$. During an epoch, clients send read/write requests to the storage server in the cloud. For simplicity, we consider a client runs a single thread.\footnote{In practice, the case of a multi-threaded client can be treated as multiple single-threaded virtual clients.} The operations are logged on both sides of clients and the server as in Figure~\ref{lst:execution}). A client logs her own operations while the server logs the operations submitted by all clients. Given an operation, a client logs the start time when the request for the operation is sent and the end time when the response of the operation is received. We assume the NTP protocol in place enables all clients to log operation time with low inaccuracy. Both clients and the server store the logged operations locally. 

At the end of the epoch, both clients and the server attest to their operation log. The server calls \texttt{attestServerLog(ops\_server,$sk_S$)} where she declares a total-order sequence over the operations and signs the log with server key $sk_S$ before sending it the Blockchain. A client calls \texttt{attestClientLog(ops\_client, $sk_C$)} where she signs the logged operations with secret key $sk_C$ and sends it to the Blockchain. The total-order in the server attestation is necessary for consistency checking (recall the definition in \S~\ref{XXX}). 

The smart contract running on the Blockchain receives the calls of \texttt{attestServerLog(ops\_server,$sk_S$)} from the server and \texttt{attestClientLog(ops\_client, $sk_C$)}  from all clients. After that, it runs log verification, log crosschecking and log auditing as described previously. The result, namely the assertion of log consistency, is stored on chain for future inquiry. 

Clients can call \texttt{consistencyResult()} to check the consistency result. This function checks two conditions: 1) Whether all clients’ transactions \texttt{attestClientLog(ops\_client, $sk_C$)} are finalized on Blockchain, YYY. 2) whether the consistency assertion (i.e., the result of running \texttt{auditLog()}) is finalized on Blockchain.

The execution schedule of ContractChecker is parameterized by an epoch duration $E$. In practice, $E$ is set to be multiply of the block time on Blockchain, that is, $E=n\times{}B$. $n$ is determined based on the client availability and latency requirements in target scenarios.

\begin{figure}[!ht]
\begin{center}
    \includegraphics[width=0.45\textwidth]{figures/protocol-2-example.ps}
\end{center}
\caption{Running ContractChecker: An example scenario with two clients. Client $C_1$ sends a write $w_1$ before a read $r_3[w_1]$ that returns the record written by $w_1$. Client $C_2$ sends a write $w_2$ to the server.}
\label{fig:execution}
\vspace{-0.10in}
\end{figure}

{\it An example} is presented in Figure~\ref{fig:execution} where the ContractChecker protocol runs one epoch between two clients $C_1$ and $C_2$. An epoch can be set to multiple of Blockchain's block time. On Ethereum, it is multiply of $15$ seconds. During the epoch, client $C_1$ submits two operations to the server, namely $w_1$ and $r_3[w_1]$. $r_3[w_1]$ represents a read operation that returns write $w_1$. Client $C_2$ submits an operation $w_2$ to the server. All operations are on the same data key, and they are processed by the server in the serial order of $w_1w_2r_3[w_1]$. By the end of epoch, it first runs log attestation: 
$C_1$ calls $\texttt{attestClientLog}(w_1,r_3)$ and $C_2$ calls $\texttt{attestClientLog}(w_2)$. The server declares a total-order $w_1,w_2,r_3$ by calling $\texttt{attestServerLog}(w_1,w_2,r_3)$. 
The smart contract then stores the two client logs and one server log on the Blockchain. After that, it runs two functions: $\texttt{crosscheckLog}(\{w_1,r_3\},\{w_2\},\{w_1,w_2,r_3\})$, and $\texttt{auditLog}(\{w_1,w_2,r_3[w_1]\})$. As a result, the smart contract asserts the log is inconsistent and stores it on chain.

Meanwhile, the clients may call $C$.\texttt{consistencyResult()}. The function call will block until the transaction of $C$.\texttt{attestClientLog()} is finalized on Blockchain. On Ethereum, it takes $25$ epochs to finalize a transaction. After 25 epochs, if the transaction is finalized, the consistency assertion stored on chain can be treated as an immutable statement and be further used by applications. In addition, the client can truncate her local operations in that epoch. If the transaction is not included in the Blockchain, the client will retry $C$.\texttt{attestClientLog()}.

Now we modify the setting of this example that $w_1$ and $w_2$ are processed concurrently by the server (i.e., with overlapped time intervals). In this case, a rational server (which we assume in this paper; recall \S~\ref{sec:servertrust}) will search and attest to the total-order that is consistent, namely $w_2w_1r_3[w_1]$. Note that the other total-order $w_1w_2r_3[w_1]$ also matches the real-time relation, as $w_1$ and $w_2$ are concurrent. But it contains inconsistent read $r_3[w_1]$.

Note that in this example, the ContractChecker clients are stateless (in that client $C_1$ can discard operations $w_1r_3$ and truncate the log after client attestation) and store only local operations (in that client $C_1$ does not need to store the operations of client $C_2$). This saves the client cost, comparing all existing approaches including Catena and Caelus which require clients to maintain global state without log truncation.

\subsubsection{\bf Protocol Construction}

\input{text/lst2.tex}


{\it On-chain contract logic}: The two attestations described in \S~\ref{XXX} invoke a smart-contract on chain. The smart contract taking as input of log attestations from the server and clients will conduct four operations: verifying client attestations (\texttt{verifyClientLog()}), verifying the server attestation (\texttt{verifyServerLog()}), crosschecking the logs of clients and server (\texttt{crosscheckLog()}), and auditing the checked log to assert consistency (\texttt{auditLog()}).

In \texttt{verifyClientLog()}, the contract would verify the client attestation using the client’s public key. In \texttt{verifyServerLog()}, the contract verifies the server attestation using the server’s public key. It is optional that an individual operation can be signed by both the client and server (in \S~\ref{XXX}). In this case, both verification functions will verify individual operations as well using both clients’ and server’s public keys. Once logs are verified, the client logs are unioned and are crosscheck with the server log to find any inequality (\texttt{crosscheckLog()}). Once the logs are successfully cross-checked, it runs log auditing (i.e., \texttt{auditLog()}) where strong consistency conditions (e.g., operation ordering and read freshness) are checked over the crosschecked server log.


{\it Storage of historical operations}: In our scheme, the historical operations need to be persisted on the chain for future inquiry. Because verifying operation consistency in the current epoch entails operations in the past. A baseline to store the historical operations is an on-chain database run by the smart contract, which maintains a fresh snapshot of the dataset. This baseline essentially stores a replica of the dataset on the server and may cause high cost on chain.

We consider forming an authenticated data structure (ADS) between the server and Blockchain to enable the efficient authenticated serving of historical operations. Briefly, an ADS is a proof system between a trusted verifier and untrusted prover. A Merkle hash tree is a basic and commonly used ADS which proves the (non)-membership of a record in a dataset. In our scheme, the Blockchain serves as verifier who sends out queries about the latest state of a data key and the server serves as a prover who prepares the Merkle authentication path as a proof to authenticate queries. 

For instance, consider the operation sequence $w_1(K),w_2(K’),r_3[w_1](K)$ where $w_1w_2(K’)$ occurs in epoch 1 and $r_3[w_1](K)$ occur in epoch 2. For the Blockchain to assert the consistency of $r_3[w_1]$, it will need to know as of epoch 2 whether the latest write of data key $K$ is $w_1$. The Blockchain will send out this query to the server and the server who maintains a Merkle tree of the current state (of latest records of all data keys) returns the authentication path for $w_1$, so that its freshness can be verified by the Blockchain. 

{\it Finality of Client Attestations}: The finality checking is realized by all active clients staying online and confirming the finality of their own attestations. For a client to check the finality of her attestation, she simply checks if there are $F$ blocks on the Blockchain that are ordered after the block where her attestation transaction is stored. Blockchain’s immutability guarantees the hardness of altering or omitting the client attestation if its finality is confirmed on the chain. If the transaction is not finalized, the client is responsible for retrying \texttt{attestClientLog()} until finality.

A consistency assertion is only valid when \emph{all} active clients have confirmed the finality of their attestations. Had one client missed her attestation, there is a chance the client’s log is missed and the server can omit the client’s operations without being detected. To ensure all active clients confirm their attestation, we rely on a heuristic approach here: All clients are required to wait until $2F$ blocks after their attestations before the consistency assertion can be used. Any clients who decide to retry would increase their transaction fees to make sure with high probability their attestation will be included in the Blockchain for the second try.

\section{Protocol Analysis}
\label{sec:analysis}
In this subsection, we analyze the protocol correctness under both benign and malicious settings. We start with the correctness with benign clients and the server.  We consider the case of lowly-available clients. We then focus on the malicious cases, by analyzing protocol security with a malicious server, malicious clients, and unreliable Blockchain.

\subsection{Correctness}

In ContractChecker, the protocol correctness states that if the protocol is truthfully executed by benign clients and server, a consistent operation history will be asserted as a consistent history, and an inconsistent operation history will be asserted as an inconsistent history. Informally, given any consistent operation history $Ops_S$ and any $\{Ops_C\}$ with $\cup{Ops_C}=Ops_S$, it holds that $S.\texttt{attestServerLog}(Ops_S)$, $C.\texttt{attestClientLog}(Ops_C)$, $C.\texttt{consistencyResult}()=Y$. For any inconsistency operation history $Ops_S$ and any $\{Ops_C\}$, $S.\texttt{attestServerLog}(Ops_S)$, $C.\texttt{attestClientLog}(Ops_C)$, $C.\texttt{consistencyResult}()=N$.

Analyzing the protocol correctness is straightforward. If the clients and server are benign, the protocol guarantees the authentic copies of client logs and server log are send to the Blockchain as the input of \texttt{crosscheckLog()} and \texttt{auditLog()}. The computation logic guarantees that a server log with consistency total-order will be asserted as consistency. For an inconsistency log, the server cannot find a total-order without inconsistency and the case of inconsistency will be detected by \texttt{auditLog()}.

\label{sec:clientavail}
{\it Correctness with low client availability}: In ContractChecker, we consider active clients and inactive clients: Given an epoch, an active client is one that has submitted at least one operation to the cloud. Otherwise, it is an inactive client. ContractChecker requires only active clients in an epoch to be available to participate in the protocol by the end of the epoch. Be more precise, given an inactive client, it does not require its availability for protocol participation. 

The protocol correctness without the availability of inactive clients is straightforward. Whether inactive clients send their empty log to the Blockchain, it does not affect either the union of all client operations or the log crosscheck (\texttt{corsscheckLog()}). Therefore, an attack is detected by the server-client log inequality, which is irrelevant to the inactive clients’ empty logs. 

This is in contrast with existing client-based protocols which require the availability of both active and inactive clients (as analyzed in Appendix~\ref{sec:existingavailability}). Briefly, the reason that ContractChecker does not require availability of inactive clients while other protocols do is that it cannot distinguish the benign case of an inactive client who is legitimately unavailable from the malicious case of an active client who detects an attack but whose attack report is suppressed by the untrusted server who relays the report among clients. In ContractChecker, it does not rely on the untrusted server to report the case of an attack, but instead by the trusted Blockchain.

\subsection{Security under Server/Client Attacks}

\subsubsection{\bf Security against the Malicious Server}
\label{sec:servertrust}

In ContractChecker, the server’s job is to declare a total-order over concurrent operations and to attest to it. A benign server is allowed to find a total-order without inconsistent operations to the degree that she does not forge operations.

Before describing the server threats, we stress that our server, be it benign or malicious, is \emph{rational}. Given a consistent operation history, a rational server does not falsely attest to a total order with inconsistency, as it does not have the incentive (recall \S~\ref{XXX}). For instance, consider an operation history $w_1|w_2r_3[w_1]$ where $w_1$ and $w_2$ occur concurrently. A rational server will find the total-order for consistency (i.e., $w_2w_1r_3[w_1]$) and attest to it. The rational server is not incentivized to attest to the total-order with inconsistent operations (i.e., $w_1w_2r_3[w_1]$). Note that both total-orders match the real-time relation in the concurrent operation history.

{\it Server threats}: The goal of a malicious (and rational) server is this: Given an inconsistent operation history, a malicious server aims at concealing the inconsistency by forging operations and declaring a false total order over it. In order to conceal inconsistency, the malicious server can launch a variety of threats: A malicious server forges a non-existing operation (AS1), omits the valid operation (AS2), replays a valid operation multiple times (AS3), reorders the serially-executed operations (AS4). 

{\it Attack detection}: ContractChecker can detect the server attacks by the difference between the client logs and server log. Concretely, the server forging an operation (AS1) can be detected by an operation in the server log that cannot be found in any client log. The server omitting an operation (AS2) can be detected by an operation in a client log that cannot be found in the server log. The replay attack (AS3) can be detected by identical operations in the server log. Reordered operations (AS4) can be detected by the condition that the operation order does not match real-time (i.e., an operation that occurs later is ordered before an earlier operation). 

\subsubsection{\bf Security against Malicious Clients}

{\it Client threats}: A malicious client is incentivized to falsely accuse a benign server of inconsistent operations that the server did not process. Towards this goal, a malicious client can mount the following attacks to forge her log attestation. Specifically, she omits her local operation (AC1), forges an operation the server did not process (AC2), replays a valid operation multiple times (AC3), reorder the serially-executed operations (AC4). For instance, given a consistent history, the client can forge a write operation $w_2$ between $w_1$ and $r_3[w_1]$ to make $r_3$ look like a stale read. She can omit $w_1$ to make $r_3[w_1]$ look like an invalid read. She can reorder her local operations from $w_2w_1r_3[w_1]$ to   $w_1w_2r_3[w_1]$, such that $r_3[w_1]$ is falsely inconsistent.

{\it Attack detection}: The attacks by forging a client log can be detected by the difference between the client logs and server log. Due to no server-client collusion, we assume that the server attests to a truthful log of operations. Thus, any operation forged by the client will result in a mismatch to the server log (which can be similarly analyzed as malicious server attacks).

\subsubsection{\bf Security Hardening for Attack Mitigation}

\begin{figure}[!ht]
\begin{center}
    \includegraphics[width=0.25\textwidth]{figures/logaudit.eps}
\end{center}
\caption{The logic in \texttt{LogAudit()} in ContractChecker for attack detection and mitigation}
\label{fig:logaudit}
\vspace{-0.10in}
\end{figure}

In the ContractChecker, attacks from a malicious server or clients are detected by the mismatch between the server attestation and client attestations (in \texttt{crosscheckLog()}). In the case of attacks, the ContractChecker does not only detect them but also mitigate them in the sense of making a trustworthy assertion about the log consistency in the presence of attacks. We describe how attacks are detected and mitigated.

In order to distinguish attacks from clients and the server, we augment the basic protocol (in \S~\ref{sec:basicprotocol}) by requiring both client and server signatures on both server attestation and client attestation. More concretely, every online operation (i.e., read/write) is augmented with a server signature and a client signature. This can be naturally integrated to the regular request/response workflow without adding extra communication round. When a client submits a request, she embeds in the request her signature of the requested operation, such that the server receives a client-signed operation. When the server processes the operation, she produces a server signature over the operation response, such that the client receives a server-signed operation response. When the client starts to do attestation, she will sign her local log of server-signed operations with the client signature. When the server starts to do attestation, she will declare the total order based on the client-signed operations. When the Blockchain receives a client attestation, it will validate the input by verifying both the client signatures and server signatures attached to the attestation. So is the case of validating a server attestation. We call this extension by double-signed attestation.

{\it Distinguishing causes of attacks}: With the double-signed attestation, the ContractChecker can distinguish different attacks (in our threat model). When the server attestation contains an operation whose client signature cannot be verified, this is attributed to a server attack forging a non-existing operation (AS1). If the client signature can be verified but the operation cannot be found in a client attestation, this is attributed to a client attack who omits her local operation (AC1). When the client attestation contains an operation whose server signature cannot be verified, it is attributed to a client attack forging an operation the server did not process (AC2). If the server signature can be verified but the operation cannot be found in the server attestation, it is attributed to a server attack omitting the operation (AS2). The replay attack (AC3 and AS3) where a client (or server) may duplicate a signed operation multiple times can be detected by finding duplicated operations on the server (or client) attestation. Normally, each operation is uniquely identified by a client-generated nonce (using an external source of trusted randomness). In addition, a malicious server (or client) may want to reorder the serially-executed operations in a dfferent order (AC4 and AS4). This attack can be detected by the mismatch between the timestamps in the operations and the total in the attestation.

Note that we assume a rational server who will find a consistent total-order, if it exists, from the operation history and attests to it. An irrational server who does not find such a total order for consistent operation history may falsely report a case of inconsistency in ContractChecker.

{\it Repair server attestation}: In different attack scenarios, the ContractChecker can repair the server attestation to recover the truthful log and to further assert the log consistency. In AS1 (the server forging attack), the ContractChecker removes the forged operation from the server attestation. In AS2 (the server omission attack), the ContractChecker copy the omitted operation from the client attestation to the server attestation. In AC1 and AC2 (the client attacks by operation omission and forging), no action is needed to recover the server attestation. In replay attacks (AC3 and AS3), if it finds replayed operations on the server attestation, the ContractChecker removes the duplicated copy from the server attestation. After the repair, the ContractChecker can move forward and conduct consistency checking over the repaired server attestation. In reorder attacks (AC4 and AS4), the serial operations are reordered back to match the execution order in their timestamps.

The overall workflow of our ContractChecker for attack detection and mitigation is illustrated in Figure~\ref{fig:logaudit}.

\subsection{Security under Blockchain Exploits}

\subsubsection{\bf Faulty Blockchain and Malicious Server}

With a faulty Blockchain which drops transactions, a malicious server may coordinate with the Blockchain to selectively omit server operations, in order to conceal inconsistency. For instance, consider a client who pays low transaction fees or the Blockchain is saturated with its peak throughput (e.g., 10 transactions per second), either of which the Blockchain will drop transactions. Let’s say in Figure~\ref{fig:execution}, Client $C_2$’s call of \texttt{attestClientLog($w_2$)} is dropped by the Blockchain. The malicious server can accordingly omit $w_2$ on her side such that the log crosschecking between client logs and server log can succeed and falsely assert an inconsistent operation history is consistent.

{\it Attack prevention}: This attack is prevented by ContractChecker, more specifically by its client retry mechanism. In ContractChecker, an active client, once discovering her attestation gets dropped, will retry \texttt{attestClientLog()} for the second time when she will increase the transaction fee. With higher fee, the transaction will be accepted by the Blockchain. In addition, any client will wait $2F$ blocks before she will use the consistency assertion, leaving sufficient time for the assertion to be made before retry. Therefore, the attack is prevented. In the previous example, this means by the time $w_2$ is sent to the Blockchain after a retry, the ContractChecker will make a correct assertion about the operation inconsistency.

In the attack defense, we assume transaction retry will succeed before a timeout (e.g., $2F$ block time). This assumption is necessary to avoid impossibility results. Concretely, in our setting, both (inactive) clients and Blockchain can be unavailable. From ContractChecker’s point of view, \emph{it is indistinguishable between an inactive client who is allowed not to send a log attestation (the benign case) and an active client who encounters an unavailable Blockchain in accepting transaction (the exploitable case)}. To break the indistinguishability and to avoid the exploits,  our assumption that the Blockchain’s unavailability is time bounded is necessary.

\subsubsection{\bf Server Forking Attacks}

Consider multiple clients share a state hosted on a server. In this setup, a forking attacker is a malicious server who forks the shared state and serves different clients with different (forked) states. In client-based consistency protocols (e.g., Catena and Caelus), the malicious server may fork her log attestations for different auditing clients, such that the forked global logs appear to be consistent from different clients’ local views. 

In ContractChecker, the malicious server can mount a forking attack by equivocating with two conflicting attestations to the Blockchain. The hope is to make it crosscheck different clients’ attestations with different (forked) server attestations. However, it is more challenging to make a successful forking attack in ContractChecker than client-based auditing protocols. Because the log auditing (for consistency checking) in ContractChecker does not occur on individual clients, but instead in Blockchain nodes where all clients’ logs are fused. In this new setting, the success of a forking attack depends on whether one can separate different client logs and make them compared with the forked server logs. 

{\it 
Forking attack by exploiting contract races}: To launch a forking attack in ContractChecker, the malicious server may exploit the race conditions by running different contract functions concurrently. Be more specific, consider the sequence \texttt{s.serverAttestLog($w_1,w_2,r_3[w_1]$)}, \texttt{$C_1$.clientAttestLog($w_2$)},\texttt{$C_2$.clientAttestLog($w_1,r_3[w_1]$)}, \texttt{s.serverAttestLog($w_2,w_1,r_3[w_1]$)}. Before \texttt{s.serverAttestLog($w_2,w_1,r_3[w_1]$)} runs, the contract already enters \texttt{crosscheckLog()} where the server log $w_1,w_2,r_3[w_1]$ is being crosschecked with  client logs $w_2$ and $w_1,r_3[w_1]$. When \texttt{s.serverAttestLog($w_2,w_1,r_3[w_1]$)} runs, it might happen that the call of texttt{s.serverAttestLog($w_2,w_1,r_3[w_1]$)} replaces the variable of \texttt{ops\_server} \emph{during} \texttt{crosscheckLog()}. This may lead to the unwanted situation that client log $w_2$ is crosschecked with one server log $w_1,w_2,r_3[w_1]$, and client log $w_1,r_3[w_1]$ is crosschecked with another server log $w_2,w_1,r_3[w_1]$. In this situation, server log $w_2,w_1,r_3[w_1]$ will survive and will lead to incorrect assertion that the operations are consistent.

The ContractChecker can prevent this attack, due to the function synchronization. Specifically, \texttt{crosscheckLog()} is placed in a critical section such that any concurrent execution is  prevented. In other words, the execution of the attacker (i.e., calling function \texttt{s.serverAttestLog($w_2,w_1,r_3[w_1]$)}) and the vitcim (i.e., running function \texttt{crosscheckLog()}) has to be serialized. When the function execution is serialized, there is no chance exploiting the race conditions.

{\it
Forking attack by exploiting Blockchain forks}: In this version of forking attack, the malicious server can exploit the Blockchain forks. The server sends forked attestations to different Blockchain forks. In the case of transient forks, the server may be able to encode attestation forks in double-spending transactions as is done in Catena~\cite{DBLP:conf/sp/TomescuD17}. In the case of permanent forks, the server can simply encode attestation forks in two transactions and submit them separately to the two Blockchain forks. The hope is that if there is some client attestation which is omitted in one of the Blockchain forks, chances are the attack can succeed. For instance, to Blockhain fork 1, the server can send the attestation $w_2,w_1,r_3[w_1]$, client $C_1$ sends her attestation $w_1,r_3$, and client $C_2$ has her attestation be omitted. 

The forking attack by exploiting Blockchain forks cannot succeed in ContractChecker, if it guarantees any client will retry her attestation to \emph{all} Blockchain forks. In the previous example, client $C_2$’s attestation cannot be omitted if she retries the attestation to Blockchain fork 1.

{\it Notes on client-forking attacks}: 
Note that a malicious client may also fork her attestation and exploit the similar attack vectors (e.g., race conditions and Blockchain forks). However, without the collusion of the server and with the contract synchronization in place, the client-forking attack cannot succeed.

\section{Client Identity Management}

In ContractChecker, clients and server are pseudo-identified by their Blockchain addresses. Their addresses are publicly known (e.g., through secure public-key distribution) and are hard-coded in the ContractChecker contract. A function in ContractChecker is associated with an intended caller. For instance, function \texttt{attestClientLog} is associated with one of clients’ addresses. When the function is called, the contract will check if the caller matches one of the intended clients.  

ContractChecker requires clients to be identified and requires each contact-function call to authenticate clients through the identity. This is necessary not only for data authenticity but also for detecting inconsistency. Without client authentication, anyone can call a ContractChecker function and inject a forged operation to the on-chain log. The forged log can violate data authenticity or consistency. For instance, the server injects a non-existing write $w_3$ between $w_1w_2$ and $r_3$; this is done by calling $\texttt{attestClientLog}(w_3)$. The forged log can accept a read returning the forged write $r_3[w_3]$, which violate data authenticity. It can also violate consistency. For instance, the server injects a non-existing delete $d_3[w_2]$ between $w_1w_2$ and $r_3[w_1]$, which can effectively conceal the inconsistency read $r_3[w_1]$ from clients.

The above, we consider the case of static membership where clients’ addresses are hard-coded in the contract. The case of dynamic membership where clients join the network can be handled by an external, trusted identity provider service which authenticates newly joined clients and update the contract with their addresses.

{\it Security}: We consider that adversaries attempt to impersonate clients and inject forged operations to the on-chain log. The adversary can do so by 1) stealing the private key of a client, and 2) updating the addresses in the contract. For the attack vector 1), we assume clients’ private keys are securely stored. In the case of stolen keys, an external mechanism exists to notify clients and contract author to revoke the address from the contract. For attack vector 2), we assume a trusted contract author and a client-authentication mechanism. An adversary cannot be authenticated as a client and a contract author will not be tricked to whitelist an adversary’s address in the contract. Note that due to the security of a digital signature, one cannot forge a signature without knowing the private signing key.

\section{Evaluation}
\label{sec:eval}

In this section, we evaluate ContractChecker in terms of client cost and Blockchain cost. 

\input{text/fc19-kaili.tex}

\section{Related Work}

{\it
Blockchain applications}: Blockchain has been applied in both financial and non-financial applications. In the application scenarios, Blockchain and its security properties are repurposed to address application-specific security needs. CSC~\cite{DBLP:journals/corr/abs-1804-05141} runs criminal smart contract on Blockchain for facilitating commissioned crimes. Paralysis~\cite{DBLP:journals/iacr/ZhangDBJ18} supports practical wallet management under key loss/compromise by using Blockchain as trusted clock to detect client unavailability. Blockstack~\cite{DBLP:conf/usenix/AliNSF16} runs trusted directory on Blockchain by treating it as immutable data storage. IKP~\cite{DBLP:conf/sp/MatsumotoR17} proposes an incentive scheme based on Blockchain to address the certificate mis-issuance problems. Blockchain is also used as the source of randomness~\cite{DBLP:books/daglib/0040621}, non-equivocation log as in Catena~\cite{DBLP:conf/sp/TomescuD17}, etc. in many novel applications.

{\it
Blockchain throughput improvement}: There are known performance problems in Blockchain notably the limited throughput. There are protocol-analysis works on Blockchain that try to understand the throughput limitation (e.g., by block sizing~\cite{DBLP:conf/fc/CromanDEGJKMSSS16}). Lightning network~\cite{me:lightning,DBLP:journals/corr/MillerBKM17} is an off-chain scheme that batches multiple micro-payment transactions to reduce the load on chain. Lightweight mining protocols are proposed including proof-of-stake~\cite{me:pos1,me:pos2}, proof-of-elapsed-time~\cite{me:poet,DBLP:conf/uss/ZhangEEJR17}, etc. Ekiden~\cite{DBLP:journals/corr/abs-1804-05141} combines Blockchain with trusted hardware to form a virtual high-throughput Blockchain system. Blockchain sharding~\cite{me:omniledger,DBLP:conf/ccs/LuuNZBGS16} partitions the state of transaction graph among multiple miners, in a way to improve its scalability. 




\section{Conclusion}
This work presents ContractChecker, a lightweight consistency verification protocol based on Blockchain. 
ContractChecker is designed based on a new approach that runs log auditing on the Blockchain. This approach is advantageous in guaranteeing the strong consistency of the cloud storage and in saving the execution effort and storage cost of low-power and low-available clients.
ContractChecker addresses the security of malicious cloud mining by carefully scheduling logical checks on chain.
For cost-effective use of Blockchain, ContractChecker utilizes a series of cost-optimization techniques by exploring on-/off-chain storage placement, operation batching, etc.
ContractChecker is implemented in a middleware system federating cloud services, clients and the Blockchain. 
Through evaluation based on YCSB workloads, up to $80\%$ Blockchain cost can be saved by ContractChecker's optimization techniques.
\newpage


\section{learning}

\subsection{tables}

{\scriptsize \begin{verbatim} in beamer, see beamer_learn_slides. http://en.wikibooks.org/wiki/LaTeX/Tables#The_tabular.2A_environment_-_controlling_table_width
\end{verbatim}}

table with reference~\ref{tab:auth-attack}


\begin{table*}[!htbp]
\caption{Example of authorized searcher attack}
\label{tab:auth-attack}\centering{\small
\begin{tabularx}{0.5\textwidth}{ |X|c|c|c|c|c| }
  \hline
   & $p_0$ & $p_1$ & $p_2$ & $p_3$ & $p_4$ \\ \hline
  $r_a$ & $1$ & $0$ & $1$ & $0$ & $?$ \\ \hline
\end{tabularx}
}
\end{table*}

tabular (not table)

\begin{tabularx}{0.4\textwidth}{ |X|c|c|c| }
  \hline
  label1                    & label2 & label3 & label4 \\ \hline
  \multirow{2}{*}{multi-row} 
                             & item2  & item3  & item4  \\ \cline{2-4}
                             & item2'  & item3'  & item4'  \\ \hline
  \multicolumn{2}{|l|}{multi-column}   & item3''  & item4''  \\  \hline
  \multirow{5}{*}{\begin{sideways}sideways\end{sideways}}
                             & item2  & item3  & item4  \\ \cline{2-4}
                             & \shortstack[l]{item2'\\item2''}  & item3'  & item4'  \\ \cline{2-4}
                             & \shortstack[r]{item2'\\item2''}  & item3'  & item4'  \\ \cline{2-4}
                             & item2'  & item3'  & item4'  \\ \cline{2-4}
                             & item2'  & item3'  & item4'  \\ \hline
\end{tabularx}

\subsection{figures}
\begin{wrapfigure}{r}{0.35\textwidth}
\centering
\includegraphics[width=0.324\textwidth]{figures2/eff_rand_num_sample0.5.eps}
\caption{Wrapped figure}
\label{fig:perf}
\end{wrapfigure}

\ifdefined\TTUT
\begin{figure}[!ht]
\begin{center}
    \includegraphics[angle=90, width=0.45\textwidth]{figures2/eff_rand_num_sample0.5.eps}%
\end{center}
\caption{Easy figure}\label{fig:easy}
\vspace{-0.10in}\end{figure}

\begin{figure*}[!ht]
  \begin{center}
 
    \subfloat[Rotated]{%
      \includegraphics[angle=90, width=0.3\textwidth]{figures2/eff_rand_num_sample0.5.eps}%
      \label{exp:rand_num_1}%
    }%
   
    \subfloat[With more shared threads]{%
      \includegraphics[width=0.3\textwidth]{figures2/eff_rand_num_sample2.eps}%
      \label{exp:rand_num_2}%
    }%
    \subfloat[With sample ratio]{%
      \includegraphics[width=0.3\textwidth]{figures2/eff_rand_sample_num10.eps}%
      \label{exp:rand_sample}%
    }%
  \end{center
  \caption{Performance of optimization algorithm with random graph}\label{fig:complex}\vspace{-0.10in}
\end{figure*}
\fi

\subsection{algorithms}
\begin{algorithm}[h]
\caption{range-query(range $R$)}\small \label{alg:rangequery}
\begin{algorithmic}[1]
  \global\boldnumbertrue\State $\omega_R\leftarrow $ lowest-common-ancestor($R$) \Comment{comments: line number boldened}
  \State $\lambda\leftarrow $ DHT-lookup($f_{md}(\omega_R)$)
  \ForAll{$p \in P$} \Comment{comments: loop over all items}
    \State manipulate each term $p$
  \EndFor
  \If{$\lambda == NULL \And 1 \leq 0$}
      \State \Return lookup($R$.top\_left\_corner)
  \ElsIf{$R\subseteq{\lambda}$}
      \State \Return the keys of $\lambda$ that are in the range $R$
  \Else
      \State \Return recursive-forward($R$, $\omega_R$)
  \EndIf
\end{algorithmic}
\end{algorithm}

\subsection{equations}
\begin{eqnarray}
u &=& \sum_{l=0}^{n-1}{u_l} \mod{q}
=(\sum_{l=0}^{n-1}{ \sum_{j=0}^{c-1}{u_{l-j, j}} \mod{q}})\mod{q} \nonumber \\
&=& (\sum_{j=0}^{c-1}{ \sum_{l=0}^{n-1}{ u_{l-j, j} } })\mod{q}
=(\sum_{j=0}^{c-1}{ \sum_{i=-j}^{n-1-j}{ u_{i, j} } })\mod{q} \nonumber \\
&=& (\sum_{j=0}^{c-1}{\sum_{i=0}^{n-1}{ u_{i, j} } }) mod q
= (\sum_{i=0}^{n-1}{ \sum_{j=0}^{c-1}{ u_{i, j} }\mod{q} })\mod{q} \nonumber \\
&=& \sum_{i=0}^{n-1}{ v_i }\mod{q} = \sum_{i=0}^{n-1}{ v_i } = v
\end{eqnarray}

With right brace
\begin{eqnarray}
\underline{\sigma}, \epsilon \rightarrow{}\underline{\beta_*}
\begin{cases}
\begin{rcases}
\begin{rcases}
& \sum_{\forall\beta_*>1}{(\beta_* - 1)} \\
& \sum_{\forall\beta_*<1}{(1 - \beta_*)} \\  
\end{rcases} \rightarrow{} \underline{X_1}\% \\
\sum_{\beta_*<1}{1} \rightarrow{} \underline{X_2}\%
\end{rcases}
\end{cases}
 \rightarrow{\beta}
\end{eqnarray}

\subsection{listing}
\lstset{language=SQL, style=Oracle, caption={Rewritten query against a single view table},label=sql:rewritten}
\lstset{frame=lrbt,xleftmargin=\fboxsep,xrightmargin=-\fboxsep}
\begin{lstlisting}
  SELECT A, C FROM viewtable
  ORDER BY C LIMIT arg.k
\end{lstlisting}

\definecolor{mygreen}{rgb}{0,0.6,0}
\begin{figure}[h!]

\lstset{ %
  backgroundcolor=\color{white},  
 
  basicstyle=\scriptsize\ttfamily,       
  breakatwhitespace=false,        
  breaklines=true,                
  captionpos=b,                   
  commentstyle=\color{mygreen},   
  deletekeywords={...},           
  escapeinside={\%*}{*)},         
  extendedchars=true,             
 
  keepspaces=true,                
  keywordstyle=\color{blue},      
  language=Java,                
  morekeywords={*,...},           
  numbers=left,                   
  numbersep=5pt,                  
  numberstyle=\scriptsize\color{black},
  rulecolor=\color{black},        
  showspaces=false,               
  showstringspaces=false,         
  showtabs=false,                 
  stepnumber=1,                   
  stringstyle=\color{mymauve},    
  tabsize=2,                      
  title=\lstname,                 
  moredelim=[is][\bf]{*}{*},
}
\begin{lstlisting}
public void OnTouchEvent(MotionEvent e) {
Bitmap LoadPicture(String path) {
		...
		*Bitmap bm = BitmapFactory.decodeFile(file)*;
		return bm;
}

void EditPicture(Bitmap bm) {
		//heavy computational picture editing
		bm.getPixels(pix, 0, mPhotoWidth, 0, 0, mPhotoWidth, mPhotoHeight);
		for(every pixel) {
			...
		}	
		
		//embed location information into picture
		*Location loc = getLastKnownLocation(Provider)*;
		*double longitude = loc.getLongitude()*;
		*double latitude = loc.getLatitude()*;
		*EmbedLocation(bm, longitude, latitude);*
}
\end{lstlisting}
\caption{Privacy-preserving Offloading Example}
\label{figure:MotivatingExample}
\end{figure}


\subsection{fbox}
\begin{center}
\fbox{This is a sample statement}
\end{center}

\begin{center}
\fbox{\parbox{0.90\linewidth}{
This is a long long long statement: 
Blah blah blah blah 
Blah blah blah blah 
Blah blah blah blah 
Blah blah blah blah 
Blah blah blah blah 
Blah blah blah blah 
Blah blah blah blah 
Blah blah blah blah 
}}
\end{center}



\subsection{misc}
\begin{itemize}
  \item bold math type $\boldsymbol{<v_0, k>}$
  \item use other than default font size: {``\fontsize{8.5}{9} this's in font size 8.5''}. (second param. should be 1.2$\times$ first param. which is font size
  \item show tilde in url, use \textasciitilde{} rather than \~{}
  \item strike out text, \sout{text/$12$ removed}
  \item color, {\color{red}red}{\color{green}green}
  \item[$\bullet$] big bullet on each item
  \item circled text \circled{2}
  \item empty set (beautiful version) $\varnothing$ (needs ``\\usepackage\{amssymb\}''), which renames emptyset, $\emptyset$
  \item stackrel $\stackrel[c]{a}{=}$
\end{itemize}



\section{Introduction}
Today, the cloud-storage consistency is a pressingly important security property. With a cloud storage service (e.g., Dropbox~\cite{me:dropbox} and Amazon S3~\cite{me:s3}), the consistency indicates how reads/writes should be ordered and whether a read should reflect the latest write (i.e., freshness). This property is exploitable to a malicious cloud provider and leads to severe security consequences. For instance, when the cloud storage hosts a public-key directory (as in certificate-transparency schemes~\cite{me:ct}), a malicious cloud violating storage consistency can return to the user a revoked public key, leading to consequences like impersonation attacks and unauthorized data access. 
Making a trustworthy assertion about cloud storage consistency is fundamental to supporting information-security infrastructure in the clouds, such as public-key directories, software-update registry, personal device synchronization, etc.

Asserting the storage consistency in a client-server system entails two conceptual steps: W1) establishing a globally consistent view of operation log across clients (i.e., operation log attestation), and W2) auditing the log for checking consistency conditions (i.e., log auditing).
To the best of our knowledge, all existing approaches including Caelus~\cite{DBLP:conf/sp/KimL15}, CloudProof~\cite{DBLP:conf/usenix/PopaLMWZ11}, and  Catena~\cite{DBLP:conf/sp/TomescuD17}, assume trusted clients and rely on them to audit the log. More specifically, they make a single party attest to the log of operations (step W1) and send the attested log to individual clients, each of which audits the log against her local operations (W2). In particular, Catena~\cite{DBLP:conf/sp/TomescuD17} is a novel scheme that makes log attestation based on the Blockchain (W1 on Blockchain), yet still uses clients for log auditing (W2 by clients).
These client-based log auditing schemes require high client availability (i.e., all clients have to participate in the protocol execution) and incur high client cost (i.e., a client needs to store the global operation log of all other clients), rendering them ill-suited for applications with a large number of low-end and stateless clients; see \S~\ref{sec:targetapp} for a list of target applications.

We propose ContractChecker, a secure Blockchain-based consistency verification protocol. Distinct from existing works, ContractChecker uniquely delegates both log attestation (W1) and log auditing (W2) to the Blockchain. Concretely, ContractChecker runs a program on the Blockchain (i.e., the so-called smart contracts) to collect log attestations from clients and the server and to audit the log there for making the consistency assertion.
Comparing existing works, our approach, by delegating log auditing to Blockchain, has the advantage in lowering client availability requirement (i.e., only active clients who interact with the cloud are required to participate in the protocol) and in minimizing client overhead (i.e., a client only maintains her own operations for a limited period of time). 

While it seems straightforward to delegate the log auditing to Blockchain as a trusted third party (TTP), putting this idea into a secure protocol and system raises the following challenges: 1) How to securely collect and audit logs from mutually distrusting clients and server (detailed in \S~\ref{sec:security:serverclient})?
2) Real-world Blockchain systems are far from an ideal TTP and can be exploited to attack a log-auditing service on Blockchain (detailed in \S~\ref{sec:security:bkc}). First, a ContractChecker party, be it a client or the server, can be malicious and forge operations in her log attestation in order to trick ContractChecker to make an incorrect assertion about the storage consistency. We propose to cross-check the attestations from both the server and clients to detect any mismatch and log-forging attacks. In addition, in the presence of such attacks, we propose mitigation techniques (in \S~\ref{sec:security:serverclient:mitigation}) for the ContractChecker to securely attribute the cause of the attacks such that it can make a correct assertion despite of the attacks.

Second, real-world Blockchain systems are known to be limited in terms of E1) write unavailability (i.e., a valid transaction could be dropped by the Blockchain), E2) exploitable smart-contract race conditions (i.e., incorrect contract logic can be triggered by running contract code concurrently), and E3) Blockchain forks (i.e., a Blockchain network or data structure can be forked to multiple instances). 
We propose attacks against the use of Blockchain in the context of ContractChecker. These new attacks systematically exploit the Blockchain limitations mentioned above, and they are: a selective-omission attack exploiting Blockchain write unavailability (E1), a forking attack exploiting smart-contract race conditions (E2), and another version of forking attack exploiting Blockchain forks (E3). 

We propose countermeasures to defend the Blockchain-oriented ContractChecker attacks. To prevent write unavailability (E1), 
we increase the transaction fee during client attestations to improve the chance of Blockchain accepting a transaction in a certain period of time. 
To prevent the race conditions on ContractChecker (E2), we define a small critical section in the contract 
to secure the contract execution yet without losing the support of concurrent server and client attestations.
We prevent forking through Blockchain forks (E3) by ensuring all clients and server be aware of the presence of all Blockchain forks. 

We build a system prototype of ContractChecker based on Ethereum~\cite{me:eth}. The on-chain part runs a smart contract (in Solidity) that collects log attestations from clients and the server, crosschecks them and audits the log with consistency conditions.
We envision a novel application of ContractChecker to enforce a consistency-centric service-level agreement (SLA) with cloud providers.

We conduct cost analysis and experimental analysis on our prototype. 
We evaluate the client cost of the protocol and service under YCSB workloads~\cite{DBLP:conf/cloud/CooperSTRS10}. Our results show that on Ethereum, ContractChecker results in significant cost saving on the client side, with reasonable Gas cost on running smart contract.
We also measure the gas cost of ContractChecker and present the evaluation in technical report~\cite{me:tr19cc} (due to space limits). It shows the practicality of ContractChecker to the extent of supporting $613710$ operations at the cost of $\$100$ at a real Ether price.

The contributions of this work are:

1. {\bf New use of Blockchain}: This work addresses verifying cloud consistency based on public Blockchain. Unlike existing research, the work delegates log auditing to Blockchain, which has the advantage of reducing client costs and availability requirements. Based on this new use of Blockchain, we propose the ContractChecker consistency-verification protocol (\S~\ref{sec:rw:consistency} and \S~\ref{sec:motives}).

2. {\bf Secure protocol design}: We present a  secure protocol design for ContractChecker  among distrusting clients and cloud provider. The protocol cross-checks logs collected from different parties and then conduct consistency checks. It not only can detect the log-forging attacks from malicious clients and server, but also mitigate those attacks (\S~\ref{sec:secureprotocols}).

3. {\bf New attacks}: This work presents new security attacks against Blockchain-based log-auditing protocols. These new attacks exploits the limits in real Blockchain systems  (e.g., write unavailability, Blockchain forks, contract race conditions). We propose to harden the security of ContractChecker under these proposed new attacks and conduct an extensive security analysis (\S~\ref{sec:analysis}).

4. {\bf Prototyping and evaluation}: We implement a prototype of the ContractChecker on Ethereum/Solidity. 
By experiments on private and public Ethereum testnets, we extensively evaluate the client-side cost of the ContractChecker. The result shows the ContractChecker can scale to hundreds of clients and, in this setting, save client costs by more than one order of magnitude when compared with existing client-based log auditing works including Catena. The evaluation on client cost justifies the key design choice in ContractChecker to delegate log auditing to Blockchain (\S~\ref{sec:eval}).

\section{Preliminary: Secure Consistency Verification Protocols}
\label{sec:preliminary}
\label{sec:rw:consistency}
Suppose there are multiple clients interacting with an untrusted data-storage service. The problem of storage consistency verification is to convince all the clients that the untrusted storage service conforms to a certain storage consistency model. In the existing literature (as will be elaborated on), verifying storage consistency entails two steps: storage log attestation and log auditing. In log attestation, a conceptual trusted party (log attester) makes attestation about the collection of all storage operations and their ordering. The purpose of log attestation is to commit to a globally consistent view about the  operation ordering such that the malicious server cannot ``fork'' different views for different clients (i.e., the forking attack~\cite{DBLP:conf/podc/MazieresS02}). After a fork-free global log is established, the second step can take place which is to audit the log and check the consistency conditions over the global log of operations.

Existing work specializes the above framework. Specifically, SUNDR~\cite{DBLP:conf/osdi/LiKMS04} does not assume a trusted third party (i.e., no trusted attester) but instead relies on the untrusted server making log attestations to individual clients. Without the trusted attester, SUNDR does not prevent forking attacks, but makes them eventually detectable (i.e., the so-called level of fork consistency~\cite{DBLP:conf/osdi/LiKMS04}). In a sense, SUNDR is a fork-detectable log attestation scheme without trusted third party.
Caelus~\cite{DBLP:conf/sp/KimL15} addresses the application scenario with battery-powered clients of a cloud storage service. Caelus rotates (or time-shares) the role of log attester among personal devices to present a virtual and highly-available trusted attester. Log auditing occurs on individual clients and Caelus supports the checking of both strong and weak consistency models. Similarly, CloudProof~\cite{DBLP:conf/usenix/PopaLMWZ11} requires the untrusted server to attest to the operation log and relies on the trusted clients to audit the operation history for a variety of consistency models.
Catena~\cite{DBLP:conf/sp/TomescuD17} is a unique Blockchain-based log attestation scheme, which prevents the server-forking attack by ``abusing'' the Blockchain security in no double-spending transactions. 

\label{sec:analsysisexisting}
All existing consistency-verification schemes including the above rely on trusted clients (or data owners) to audit the operation log and check consistency conditions. In this respect, ContractChecker is the first scheme that delegates log auditing to the Blockchain. The unique design of ContractChecker is depicted in Table~\ref{tab:distinct}. Blockchain-oriented log delegation brings benefits in lower client cost and availability requirements as will be elaborated in \S~\ref{sec:motives}.

\begin{table}[!htbp] 
\caption{Distinction of the ContractChecker design: \xmark\xspace means the log operation is not supported by Blockchain, but instead by clients.}
\label{tab:distinct}\centering{\small
\begin{tabularx}{0.89\textwidth}{ |X|c|c| }
  \hline
Solutions & Attestation & Auditing 
\\
 & by Blockchain & by Blockchain
\\ \hline
SUNDR~\cite{DBLP:conf/osdi/LiKMS04}, 
Caelus~\cite{DBLP:conf/sp/KimL15}, CloudProof~\cite{DBLP:conf/usenix/PopaLMWZ11} & \xmark & \xmark
\\ \hline
Catena~\cite{DBLP:conf/sp/TomescuD17} & \cmark & \xmark
\\ \hline
 {\bf ContractChecker}& \cmark &  \cmark
\\ \hline
\end{tabularx}
}
\end{table}

\ifdefined\TTUT
\subsection{Preliminary: Caelus and Catena (Fork)}

In Caelus, a server sends an attested log to an attester who signs one attestation in one epoch. The server then broadcasts signed attestation to all clients, who will verify/audit the attestation against their local log. In Caelus, it is crucial that an attestation is not forked, as forking different attestations for verification at different clients' sites is an effective way to conceal inconsistency. No forked attestation is assured in Caelus that there is only one known attester.

Catena delegates the Caelus attester to Blockchain. Like in Caelus, it is crucial to assure that the server does not fork attestation to the Blockchain. This can be done by having trusted clients to download the 100GB Blockchain and to check no double attestations on the same epoch. 

Catena makes this no-fork checking on Blockchain more efficient. In Catena, the clients do not download 100GB Blockchain, instead, they download the history of Catena transactions. No fork can be checked by any Catena transaction fully spending its predecessor transaction. In other words, there is no double-spend transaction in 100 GB Blockchain. 
\fi

\section{Research Formulation}

\subsection{Target Applications}
\label{sec:targetapp}

The target application scenarios of ContractChecker are characterized by the following properties:
S1) The clients are of limited capability in computing, storage, and availability. This motivates them to outsource data storage to a more powerful cloud. 
S2) Violating storage consistency leads to security consequences. 
S3) The data load is low (e.g., typically lower than tens of operations per second). In particular, the low throughput properties of these typical application scenarios make it amenable for the use of Blockchain, which is known to have limited throughput in ingesting transactions.

In real world, there are many application scenarios that fit the above paradigm. As an example, consider a DockerHub~\cite{me:dockerhub} style container registry which distributes software patches for mobile apps. In this scenario, the clients are low-power smart phones (S1). Distributing a stale software image with unfixed security bugs leads to vulnerability on users' phone (S2). In terms of workloads, an IBM report~\cite{docker_fast18}  shows that among seven geo-distributed registry deployments, the busiest one serves only 100 requests per minute for more than $80\%$ of time(S3). We believe there are many real-world applications that meet our target scenarios, ranging from Google's certificate-transparency logs~\cite{me:ct}, iCloud style personal-device synchronization~\cite{me:icloudsync}, Github-hosted secure software development~\cite{DBLP:conf/uss/Torres-AriasACC16,me:github}, etc.

\subsection{System and Security Model}

Our system model consists of three parties: a storage server in the cloud, multiple concurrent clients and the Blockchain. Clients submit storage operations (i.e., data reads and writes) to the storage server. The operations are witnessed by the Blockchain via our ContractChecker protocol. 

\subsubsection{Clients}

Clients are data owners who outsource the data storage to the cloud. They submit operations to the cloud storage to read or update their data. Different clients' operations may occur concurrently, that is, the cloud service may process multiple operations in parallel, with their time intervals overlapped. 
A client can be active when she has submitted operations recently (we will explain the definition of active clients later) and inactive when she goes offline without any operations on the cloud.

Clients in our model are \emph{stateless} in the sense that a client does not persist state across active sessions. That is, a client does not need to remember her past operations when she is engaged with a cloud. In addition, among clients, there are no direct communication channels. That is, other than the cloud or Blockchain, clients do not communicate out-of-band. We believe this model reflects low-power clients in many real-world situations, such as smart-phone clients running web browsers. Web clients are stateless and do not directly communicate among themselves.

We assume each ContractChecker client is identified, say by her public key. When the Blockchain needs to identify a client, the client identity can be obtained and verified using client certificates issued by an offline trusted certificate authority (CA). Existing key-transparency systems such as CONIKS~\cite{DBLP:conf/uss/MelaraBBFF15} can be used here in companion with ContractChecker. 
More details about client identity management are described 
in Technical Report~\cite{me:tr19cc}.


We assume clients share synchronized clocks by running NTP protocols. Synchronized clocks will be useful in our protocol when clients are required to log operations. The accuracy of NTP protocols may affect the precision of our consistency verification results. Existing protocols can achieve highly synchronized clocks and limit clock skews to the level of milliseconds~\cite{DBLP:journals/tocs/CorbettDEFFFGGHHHKKLLMMNQRRSSTWW13}, which we believe are sufficient in our system.

\subsubsection{A Cloud Storage Service}
\label{sec:servertrust}
The cloud service hosts a data store shared among multiple clients. The service accepts clients' requests and processes them concurrently. That is, different operations from clients may be processed in parallel and in an out-of-order fashion.

Under this execution model, we consider strong consistency or linearizability~\cite{DBLP:journals/toplas/HerlihyW90}. Linearizability considers independent access to different data records and is sufficiently strong to capture necessary conditions in many security scenarios~\cite{DBLP:conf/sp/KimL15,DBLP:conf/usenix/PopaLMWZ11}. Weaker consistency that is widely adopted in modern cloud services~\cite{DBLP:journals/cacm/Terry13} is commonly less relevant to security-sensitive and critical applications. In this paper, we do not consider database serializability or isolation under multiple keys~\cite{DBLP:books/aw/BernsteinHG87}. 

We assume the cloud service makes a consistency-centric service-level agreement (SLA)~\cite{DBLP:conf/sosp/TerryPKBAA13} with the clients which states where the cloud service promises to guarantee strong consistency (more specifically, linearizability as will be defined next) over the operations it will serve. An honest server will enforce the promised consistency conditions during operational hours. 

A malicious storage server will violate the consistency conditions (as will be elaborated on), by returning a stale result for a read. In addition, a malicious server will not follow our ContractChecker protocol and tries to conceal the operation inconsistency from clients.
Consistency violation, if left undetected, can lead to severe security consequences such as impersonation attacks (recall \S~\ref{sec:targetapp}).

Moreover, we assume the cloud service is rational. While a malicious cloud server may forge operations to make an inconsistent operation history look like consistent (i.e., concealing the inconsistency), the server will not attempt to make a consistent operation history look like inconsistent. We believe this assumption reflects practical situations with SLA where the cloud server will be charged in case of verified inconsistency, and thus does not have the incentive to forge an inconsistent history.

\label{sec:cons}
{\bf Consistency definition}:
We consider the storage service exposes a standard key-value API, where each data record is a key-value pair and each storage operation accesses the target record by the data key.
A storage operation, be it a read or write, is specified by two timestamps, which respectively represent 1) the begin time when the request of the operation is sent by the client, and 2) the end time when the response of the operation is received by the client. Formally, given a key-value pair $\langle{}K,V\rangle{}$, a read operation is $V=r_{[t_b,t_e]}(K)$ and $\texttt{ACK}=w_{[t_b,t_e]}(K,V)$. Here $r/w$ denotes read or write operation. $t_b<t_e$ and they are the begin and end timestamps. If two operations are concurrent, their time intervals $[t_b,t_e]$ may overlap.

An operation history is linearizable if the following two conditions are met: 1) All operations can be mapped to a total-order sequence that is compatible with the real-time intervals of the operations. 2) There is no stale read on the total-order sequence. That is, any read operation should return the record that is fresh on the total-order. This property is also called read freshness.

Any linearizable operation history can be represented by a totally-ordered operation sequence. We denote an operation sequence by operation indices.
For instance, in $w_1w_2r_3[w_2]$, the subscription is the operation index in the total-order (described below).
Linearizability specifies operations of the same data key; for simplicity, we omit data key in this notation.
The square bracket of a read indicates the result record. 
$r_3[w_2]$ denotes a read operation ordered as the third operation in the total-order sequence and which returns the record written by write $w_2$. 

{\bf Network}: In this work, we assume a reliable network among clients, the server and Blockchain nodes. When one party sends a message to the network, the network will deliver the message to the receiver with negligible delay (comparing with the period our protocol runs). We do not consider network faults or partition in this work.

\subsubsection{Blockchain}
\label{sec:prel:bkc}
The Blockchain in our protocol is a public, permissionless Blockchain running over a large P2P network and supporting smart contract execution. Real-world examples include Ethereum and the latest version of Bitcoin. In this setting, we assume the honest majority among Blockchain miners. We believe this is a reasonable assumption as in practice there are no successful $51\%$ attacks on Bitcoin or Ethereum.

The Blockchain in our protocol is parameterized by the following arguments: block time $B$, which is the average time to find a block in a Blockchain; 
and transaction-validation delay $P$, which is the time between a pending transaction enters the memory pool and when it leaves for transaction validation; and finality delay $F$, which is the number of blocks needed to be appended after a finalized transaction. That is, a transaction is considered to be finalized in Blockchain when there are at least $F$ blocks included in the Blockchain after the transaction.

The Blockchain supports the execution of smart contracts. The contract is executed across all Blockchain miners. It guarantees the execution integrity and non-stoppability. That is, the Blockchain truthfully executes a smart contract based on the provided arguments, despite of the attacks to subvert the Blockchain (as described below). Once the execution of a contract starts, it is hard to stop the execution or to abort. 

{\bf Blockchain write availability}: The Blockchain may drop transactions based on its current load and transaction fee. A transaction with a higher fee will have a lower chance of being dropped~\cite{DBLP:conf/sp/TomescuD17} and have shorter latency to be included. This assumption will be tested in our evaluation.

{\bf Blockchain attacks}: The Blockchain is subject to a series of threats. In this work, we focus on practical Blockchain threats and exclude theoretic threats (e.g., $51\%$ attacks, selfish mining, etc.) and off-chain threats (e.g., stealing wallet coins and secret keys). 1) The Blockchain may be forked permanently due to software update as in the case of Bitcoin cash (Blockchain forks). 2) Smart contracts may contain security bugs that can be exploited by a vector of attacks~\cite{me:contractattacks}, such as reentrancy attacks, buffer overflow attacks, etc. In practice, the DAO (decentralized autonomous organization) incidents are caused by this attack vector.

\subsection{Goals}

\subsubsection{Security Goals}

In our system, there are two main threats: 1) In the case that inconsistency occurs, the malicious server wants to hide the inconsistency from victim clients. 2) In the case that all operations are consistent, a malicious client may want to accuse the benign server of the storage inconsistency that does not occur. We exclude other cases as they are not rational. For instance, we do not consider that a rational server will forge operations such that a consistent operation history will appear inconsistent. We also do not consider that a victim client will want to hide an inconsistent operation history. Due to this reason, we assume clients and the server will not collude to either hide inconsistency or accuse of false consistency.

Our security goals are listed below:

{\bf Timely detection of inconsistency against malicious server}: A malicious server cannot hide the occurrence of inconsistent operations from victim clients. To be concrete, when inconsistency occurs, the protocol will assert there are inconsistent operations in a timely manner, even when a malicious server can forge a seemingly consistent log. In addition to that, the protocol will present a verifiable proof of the inconsistency, so that it can penalize the cloud service for violating the consistency.

{\bf No false accusation of inconsistency against malicious clients}: A malicious client cannot falsely accuse a benign server of inconsistency that does not occur. Given a consistent operation history, the protocol will assert it is consistent, even when there are malicious clients who want to forge inconsistent operations in the log.

\subsubsection{Cost Goals}

{\bf Client cost}: Clients in our protocol can remain stateless. That is, running the ContractChecker protocol, a client does not need to store her operations indefinitely and can truncate operations after use (i.e., stateless). In addition, the protocol data stored on a client is limited to the client's local operation; a client does not need to store other clients' operations (i.e., local operations). These two requirements make clients lightweight and render the protocol applicable to scenarios with low-power clients.

\subsubsection{Non-goals}

{\bf Data authenticity}: Data authenticity states a malicious cloud service cannot forge a client's data without being detected. We assume an external infrastructure in place that ensures data authenticity, such as MAC or digital signatures. To be more specific, the client who writes a record signs the record, and the signature can be verified to guarantee the data authenticity of the record. Here, clients' public keys are securely distributed by a PKI or a secure communication channel.

{\bf Collusion}: In ContractChecker, we aim at security guarantees against a malicious cloud server 
\emph{or} malicious clients. However, we do not consider the case that a server colludes a client, because this would make it impossible for any third-party to detect the attack. To be concrete, a colluding client can lie about her log (e.g., omitting an operation), and the server can do the same. With the client and server both lying about their operations, any third-party cannot detect the existence of the lie. If an operation can be forged or omitted in a log, the consistency assertion over the log cannot be trusted. For instance, omitting $w_2$ in $w_1w_2r_3[w_1]$ leads to incorrect consistency assertion. 
Due to this reason, we exclude from our threat model the collusion among clients and server. 
In practice, we believe server-client collusion is a rare situation.


\ifdefined\TTUT

\subsection{Research Goals}


{\bf Problem statement}: This work aims at providing consistency guarantees of a remote low-throughput storage system, 1) with the security against a malicious server, 2) at a minimal cost to the clients, and 3) by a small cost of Blockchain. To be more specific, the security of our scheme can detect any inconsistency behavior of the malicious server. 
The cost of a client should be proportional to the size of the client's local operation history, and is independent of the global operation history.
The cost of the Blockchain should be as low as possible for the practical and cost-effective use of the scheme. 

{\bf Assumptions and non-goals}: 
1) We assume our data model contains only non-identifiable information (e.g., operation type, time, data key being accessed) which can be safely published to the Blockchain. If there is identifiable information, it is hashed before being put into key-value records. By this means, we provide the basic level of user privacy. The privacy under linkage attacks and side-channel attacks~\cite{DBLP:conf/sp/NarayananS09,DBLP:journals/corr/abs-0903-3276} is out of the scope. 
2) We assume the storage throughput in the target storage is lower than that of  Blockchain. The system administrator is assumed to have sufficient funds to purchase enough storage space on Blockchain. This setting should admit various real-world applications as described in \S~\ref{sec:targetapp}. 
We do not aim at improving the Blockchain throughput in this paper. 
3) This work focuses on logical flaws of smart contracts. We assume the contracts we developed is either free of programming bugs or can be effectively debugged by external tools (e.g., following programming patterns~\cite{me:contractpattern}).
\fi

\section{The Security Protocols}
\label{sec:secureprotocols}

\subsection{Design Motivation}
\label{sec:motives}
The key design in ContractChecker is to use Blockchain to audit the log in a client-server system (recall Table~\ref{tab:distinct}). This use of Blockchain is motivated by our observations below:

{\bf 1) Low client cost}: By delegating log audit to the Blockchain, one can significantly relieve the burden from the clients. Existing consistency-verification protocols are based on client-side log auditing~\cite{DBLP:conf/sp/TomescuD17,DBLP:conf/sp/ZyskindNP15}, which requires a client to persist not only her own operations but also operations of all other clients, 
limiting the system scalability. By delegating log auditing to the Blockchain, a client can be relieved from accessing other clients' operations, and can have a minimal overhead of receiving log-auditing results from the Blockchain.

{\bf 2) Freshness with stateless clients}: Consistency verification needs to access historical operations. With stateless clients who do not communicate, it is impossible to guarantee the freshness of any global state without trusted third party~\cite{DBLP:conf/osdi/LiKMS04,DBLP:conf/podc/MazieresS02}. The presence of Blockchain as a trusted third party is necessary and beneficial in guaranteeing the freshness of serving historical operations in the presence of server rollback attack.

{\bf 3) Security without client availability}: 
Intuitively, Blockchain serves as a highly available\footnote{The condition that Blockchain is highly available is described in \S~\ref{sec:prel:bkc}.} trusted third party, and it can be used to support clients with low availability. More specifically, in existing client-based auditing schemes, all clients are assumed to be highly available in the sense that they require inactive clients to participate in log auditing in every epoch. In a world without a highly available third-party, this requirement is necessary because otherwise it is hard to distinguish an inactive client who does not report (the benign case), and an active client whose report is suppressed by the malicious server (the attack case). With a Blockchain serving as a reliable broadcast channel among clients,\footnote{There are situations that consistency verification protocols require client-client communication, such as disseminating the global list of operations for client-based auditing and reporting attack incidents.} it can afford that an inactive client does not need to participate in the protocol execution. The reliable Blockchain makes it possible to collect all active clients' logs in the presence of untrusted server. (See \S~\ref{sec:analysis:correct} for a detailed correctness analysis)


In the following, we first present the protocol overview and then justify the design by describing the alternative designs we have explored (and dismissed). After that, we will present the details of our protocol execution.

\subsection{Protocol Overview}
\label{sec:overview}

ContractChecker is a protocol that runs among clients, a storage server and the Blockchain. The purpose of the protocol is to present a trustworthy assertion about the consistency of the operations among clients and the server. At a high level, the protocol works by asking clients and the server to periodically attest to their views of operations to the Blockchain where different views are crosschecked and consistency conditions are verified. The purpose of the crosscheck on Blockchain is to detect and mitigate the attack from a malicious server (or client) who forges her view of the log.

In our protocol, the interaction between the Blockchain and the clients/server off chain can be described by 
the following three functions. Note that the protocol runs in epochs and here we consider the operations in one epoch.

\begin{itemize}
\item
$S.\texttt{attestServerLog}(Ops_S, sk_S)$: Server $S$ declares a total-order over the global history of operations in the current epoch ($Ops_S$). She attests to the declared total-order sequence by signing it with her secret key $sk_S$. 

\item
$C.\texttt{attestClientLog}(Ops_C, sk_C)$: An active client $C$ attests to her local operations in the current epoch ($Ops_C$) by signing it with her secret key $sk_C$. Operations of a single client can also be concurrent and a client does not need to declare a total-order over her own operations. If a client is inactive, meaning she did not submit any operation in the epoch, she does not need to call this function. 

\item
$C.\texttt{consistencyResult}() = \{Y, N\}$: A client $C$ can check consistency of the current operation history. With Blockchain, the checking result is only valid when the attestations are finalized on the chain. This function is blocking until the finality is confirmed. If the attestations are not finalized, it will retry by calling \texttt{attestClientLog}.
\end{itemize}

\subsection{Protocol Design Alternatives}
\label{sec:alternative}

{\bf No server attestation}: 
Our protocol (as presented above) requires to collect the log from both clients and the server.
An alternative design is to collect the operation history only from clients. In this scheme, all clients send their local operations to the Blockchain without collecting the server log. The union of client logs can reconstruct all operations and their relations in real time (i.e., serial or concurrent with each other). 
However, there are two limits of this approach. First, the union of client logs does not have the total-order information (among concurrent operations) which is necessary to determine the storage consistency (Recall the consistency definition in \S~\ref{sec:cons}). Relying on the smart contracts to ``solve'' the operation total-order, it would be expensive in terms of gas cost. Second, having attestations from both clients and server is helpful to determine which party is lying in the presence of malicious client and server. In particular, without the server attestation, it would be impossible to mitigate attacks from malicious clients. Therefore, our protocol requires the (untrusted) server to declare the operation total-order and send her attestation to the Blockchain. 

{\bf Synchronizing public contract functions}: 
Our protocol implements log attestation as public contract functions (i.e., \texttt{attestServerLog()}, \texttt{attestClientLog()}) and implements the log crosschecking and auditing as private contract functions (i.e., \texttt{crosscheckLog()}). Our initial design is to implement all three tasks in three public contract functions that can be called from off-chain clients.

However, a problem arises with the order in which these public functions can be executed. The order in which the calls to public contract functions are issued (issuance order) may be different from the order in which the public contract functions are executed
 on Blockchain miners (execution order). For instance, if a Blockchain client can serially submit functions calls for log attestation, crosscheck and checking, the three functions may be delivered to individual Blockchain miners in a different order, say checking, crosscheck, attestation, which will break the protocol correctness. To fix this, one can rely on clients to synchronize different contract calls, say by requiring a client only calls crosscheck until it confirms the completion (or transaction finality) of the call of log attestation.
However, this client-side synchronization is extremely slow and unnecessarily time-consuming.

Therefore, our protocol implements the log crosschecking and auditing by private contract functions that can only be called by another contract on chain. 
By this means, the serial order is ensured directly by individual miners without expensive client-side finality confirmation.



\subsection{The Protocol: Execution and Construction}
\label{sec:basicprotocol}
In this section, we present the protocol in the top-down fashion. We first describe the overall protocol execution flow involving both on-chain and off-chain parties. We then describe the construction of the protocol with the details of the various primitives used in the construction..

\subsubsection{Overall Protocol Execution}


We present the overall protocol execution. The ContractChecker protocol runs in epochs. Each epoch is of a pre-defined time interval $E$. During an epoch, clients send read/write requests to the storage server in the cloud. For simplicity, we consider a client runs a single thread.\footnote{In practice, the case of a multi-threaded client can be treated as multiple single-threaded virtual clients.} The operations are logged on both sides of clients and the server as in Figure~\ref{lst:execution}). A client logs her own operations while the server logs the operations submitted by all clients. Given an operation, a client logs the start time when the request for the operation is sent and the end time when the response of the operation is received. We assume the NTP protocol in place enables all clients to log operation time with low inaccuracy. Both clients and the server store the logged operations locally. 

At the end of the epoch, both clients and the server attest to their operation log. The server calls \texttt{attestServerLog(ops\_server,$sk_S$)} where she declares a total-order sequence over the operations and signs the log with server key $sk_S$ before sending it the Blockchain. A client calls \texttt{attestClientLog(ops\_client, $sk_C$)} where she signs the logged operations with secret key $sk_C$ and sends it to the Blockchain. The total-order in the server attestation is necessary for consistency checking (recall the definition in \S~\ref{sec:cons}). 

The smart contract running on the Blockchain receives the calls of \texttt{attestServerLog(ops\_server,$sk_S$)} from the server and \texttt{attestClientLog(ops\_client, $sk_C$)}  from all active clients. After that, it runs log verification, log crosschecking and log auditing 
which will be elaborated on in \S~\ref{sec:onchain}.
The result, namely the assertion of log consistency, is stored on chain for future inquiry. 
Clients can call \texttt{consistencyResult()} to check the consistency result. 

The consistency assertion is valid only when two conditions are met: 1) all active clients' transactions \texttt{attestClientLog(ops\_client, $sk_C$)} are finalized on Blockchain.
2) the consistency assertion (i.e., the result of running \texttt{auditLog()}) is finalized on Blockchain. To guarantee the two conditions, all active clients in an epoch are synchronized among themselves and with the Blockchain (see \S~\ref{sec:syncclients} for details).

ContractChecker is parameterized by the duration of an epoch $E$, which can be set according to application-level requirements in timeliness of consistency assurance (see details in our technical report~\cite{me:tr19cc}).

\begin{figure}[!ht]
\begin{center}
    \includegraphics[width=0.65\textwidth]{figures/protocol-2-example.eps}
\end{center}
\caption{Running ContractChecker: An example scenario with two clients. Client $C_1$ sends a write $w_1$ before a read $r_3[w_1]$ that returns the record written by $w_1$. Client $C_2$ sends a write $w_2$ to the server.}
\label{fig:execution}
\vspace{-0.10in}
\end{figure}

{\bf An example} is presented in Figure~\ref{fig:execution} where the ContractChecker protocol runs one epoch between two clients $C_1$ and $C_2$. An epoch can be set to multiple of Blockchain's block time. On Ethereum, it is multiply of $15$ seconds. During the epoch, client $C_1$ submits two operations to the server, namely $w_1$ and $r_3[w_1]$. $r_3[w_1]$ represents a read operation that returns write $w_1$. Client $C_2$ submits an operation $w_2$ to the server. All operations are on the same data key, and they are processed by the server in the serial order of $w_1w_2r_3[w_1]$. By the end of epoch, it first runs log attestation: 
$C_1$ calls $\texttt{attestClientLog}(w_1,r_3)$ and $C_2$ calls $\texttt{attestClientLog}(w_2)$. The server declares a total-order $w_1,w_2,r_3$ by calling $\texttt{attestServerLog}(w_1,w_2,r_3)$. 
The smart contract then stores the two client logs and one server log on the Blockchain. After that, it runs two functions: $\texttt{crosscheckLog}(\{w_1,r_3\},\{w_2\},\{w_1,w_2,r_3\})$, and $\texttt{auditLog}(\{w_1,w_2,r_3[w_1]\})$. As a result, the smart contract asserts the log is inconsistent and stores it on chain.

Meanwhile, the clients may call $C$.\texttt{consistencyResult()}. The function call will block until the transaction of $C$.\texttt{attestClientLog()} is finalized on Blockchain. On Ethereum, it takes $25$ epochs to finalize a transaction. After 25 epochs, if the transaction is finalized, the consistency assertion stored on chain can be treated as an immutable statement and be further used by applications. In addition, the client can truncate her local operations in that epoch. If the transaction is not included in the Blockchain, the client will retry $C$.\texttt{attestClientLog()}.

Now we modify the setting of this example that $w_1$ and $w_2$ are processed concurrently by the server (i.e., with overlapped time intervals). In this case, a rational server (recall \S~\ref{sec:servertrust}) will search and attest to the total-order that is consistent, namely $w_2w_1r_3[w_1]$. Note that the other total-order $w_1w_2r_3[w_1]$ also matches the real-time relation, as $w_1$ and $w_2$ are concurrent. But it contains inconsistent read $r_3[w_1]$.

Note that in this example, the ContractChecker clients are stateless (in that client $C_1$ can discard operations $w_1r_3$ and truncate the log after client attestation) and store only local operations (in that client $C_1$ does not need to store the operations of client $C_2$). This saves the client cost, comparing all existing approaches including Catena and Caelus which require clients to maintain global state without log truncation.

\subsubsection{Construction of On-chain Contracts}
\label{sec:onchain}

\input{text/lst2.tex}
The two attestations described in \S~\ref{sec:overview} invoke a smart-contract on chain. The smart contract taking as input of log attestations from the server and clients will conduct four operations: verifying client attestations (\texttt{verifyClientLog()}), verifying the server attestation (\texttt{verifyServerLog()}), crosschecking the logs of clients and server (\texttt{crosscheckLog()}), and auditing the checked log to assert consistency (\texttt{auditLog()}).

In \texttt{verifyClientLog()}, the contract would verify the client attestation using the client's public key. In \texttt{verifyServerLog()}, the contract verifies the server attestation using the server's public key. It is optional that an individual operation can be signed by both the client and server. In this case, both verification functions will verify individual operations as well using both clients' and server's public keys. Once logs are verified, the client logs are union-ed and are crosschecked with the server log to find any inequality (\texttt{crosscheckLog()}). Once the logs are successfully cross-checked, it runs log auditing (i.e., \texttt{auditLog()}) where strong consistency conditions (e.g., operation ordering and read freshness) are checked over the crosschecked server log.

\subsubsection{Finality of Client Attestations}
\label{sec:syncclients}
The finality checking is realized by all active clients staying online and confirming the finality of their own attestations. For a client to check the finality of her attestation, she simply checks if there are $F$ blocks on the Blockchain that are ordered after the block where her attestation transaction is stored. Blockchain's immutability guarantees the hardness of altering or omitting the client attestation if its finality is confirmed on the chain. If the transaction is not finalized, the client is responsible for resubmitting \texttt{attestClientLog()} 
until the confirmed finality of the transaction.

A consistency assertion is only valid when all active clients have confirmed the finality of their log attestations. Had one client's log not been confirmed on the Blockchain, a malicious server can launch the selective-omission attack (detailed in \S~\ref{sec:security:bkc:available}) that leads to an incorrect assertion. Clients wait until all clients' attestations are finalized on Blockchain (see \S~\ref{sec:security:bkc:available} for a heuristic client-synchronization scheme).

\section{Protocol Analysis}
\label{sec:analysis}

In this subsection, we analyze the protocol correctness under both benign and malicious settings. We start with the correctness with benign clients and the server.  We consider the case of lowly-available clients. We then focus on the malicious cases, by analyzing protocol security with a malicious server, malicious clients, and unreliable Blockchain.

\subsection{Correctness}
\label{sec:analysis:correct}
In ContractChecker, the protocol correctness states that if the protocol is truthfully executed by benign clients and server, a consistent operation history will be asserted as a consistent history, and an inconsistent operation history will be asserted as an inconsistent history. Informally, given any consistent operation history $Ops_S$ and any $\{Ops_C\}$ with $\cup{Ops_C}=Ops_S$, it holds that $S.\texttt{attestServerLog}(Ops_S)$, $C.\texttt{attestClientLog}(Ops_C)$, $C.\texttt{consistencyResult}()=Y$. For any inconsistency operation history $Ops_S$ and any $\{Ops_C\}$, $S.\texttt{attestServerLog}(Ops_S)$, $C.\texttt{attestClientLog}(Ops_C)$, $C.\texttt{consistencyResult}()=N$.

Analyzing the protocol correctness is straightforward. If the clients and server are benign, the protocol guarantees the authentic copies of client logs and server log are send to the Blockchain as the input of \texttt{crosscheckLog()} and \texttt{auditLog()}. The computation logic guarantees that a server log with consistency total-order will be asserted as consistency. For an inconsistency log, the server cannot find a total-order without inconsistency and the case of inconsistency will be detected by \texttt{auditLog()}.

\label{sec:clientavail}
{\bf Correctness with low client availability}: In ContractChecker, we consider active clients and inactive clients: Given an epoch, an active client is one that has submitted at least one operation to the cloud. Otherwise, it is an inactive client. ContractChecker requires only active clients in an epoch to be available to participate in the protocol by the end of the epoch. Be more precise, given an inactive client, it does not require its availability for protocol participation. 

The protocol correctness without the availability of inactive clients is straightforward. Whether inactive clients send their empty log to the Blockchain, it does not affect either the union of all client operations or the log crosscheck (\texttt{crosscheckLog()}). Therefore, an attack is detected by the server-client log inequality, which is irrelevant to the inactive clients' empty logs. 

This is in contrast with existing client-based protocols which require the availability of both active and inactive clients.
Briefly, the reason that ContractChecker does not require availability of inactive clients while other protocols do is that it cannot distinguish the benign case of an inactive client who is legitimately unavailable from the malicious case of an active client who detects an attack but whose attack report is suppressed by the untrusted server who relays the report among clients. In ContractChecker, it does not rely on the untrusted server to report the case of an attack, but instead by the trusted Blockchain.

\subsection{Security under Server/Client Attacks}
\label{sec:security:serverclient}

In this subsection, we consider the attacks launched by individual malicious clients or server. As reasoned before, our threat model excludes the collusion between a client and server. We leave the Blockchain exploits to the next subsection.

In our threat model, either a client or the server can forge her attestation to the Blockchain. Specifically, she can forge a non-existing operation (A1), omit a valid operation (A2), replays a valid operation multiple times (A3), reorders the serially-executed operations (A4). 
Recall that our system model considers a rational server who, given concurrent and consistent operations, will not declare a total-order to make it look like an inconsistent log.


A malicious server can exploit the operation forging (A1-A4) to conceal an inconsistent log and to avoid paying the penalty to victim clients. For instance, successfully omitting $w_2$ in $w_1w_2r_3[w_1]$ may fool the ContractChecker to falsely assert the operation history to be consistent. A malicious client may exploit the operation forging (A1-A4) to forge an inconsistent log and to falsely accuse a benign cloud. For instance, a client can forge an operation (A1) $w_{2.5}$ in a consistent log $w_1w_2r_3[w_2]$ to make it look like inconsistent.

ContractChecker can detect any operation forging (A1, A2) by a mismatch between server attestation and client attestation (in \texttt{crosscheckLog()}). 
Without server-client collusion, if one party, say the server, forge an operation in the server attestation, the forged/omitted operation will be found in the server/client attestation, but not in the client/server attestation.
The replay attack (A3) can be detected by multiple identical operations in the server/client log. Reordered operations (A4) can be detected by the condition that the operation order does not match the real-time order (i.e., an operation that occurs later is ordered before an earlier operation).

\label{sec:security:serverclient:mitigation}
{\bf Security hardening for attack mitigation}: ContractChecker is security-hardened to not only detect attacks but also mitigate these attacks. Mitigating the attacks requires attributing an attack to the correct cause and to recover the system from the attack for further processing. The fundamental challenge in the attack attribution is about distinguishing the cause of inconsistency between a malicious client logging a forged operation or a malicious server omitting a valid operation.

To support attack attribution and to overcome this fundamental challenge, we require each online storage operation, when it is being served, needs to be witnessed and doubly signed by both the server and the submitting client. The double signatures can establish a ground truth to distinguish the cause of attacks at the consistency-checking time. For instance, if a doubly-signed operation is found in the server attestation but not in any client attestation, then it is attributed to a malicious client omitting her operation. If a doubly-signed operation is found in a client attestation but not in a server attestation, it is attributed to a malicious server omitting her operation. Note that a malicious client forging an operation can not get away as the forged operation can not be signed by the server. Also note that we don't consider the case of server-client collision, which presents an impossibility result for attack detection. 

By this means, the ContractChecker can distinguish the cause of different attacks (i.e., A1, A2, A3 or A4) and can recover the system from attestation forging. 
The details of the attack mitigation are presented in Technical Report~\cite{me:tr19cc}.

\subsection{Security under Blockchain Exploits}
\label{sec:security:bkc}
\subsubsection{Exploiting Blockchain Write Unavailability}
\label{sec:security:bkc:available}
Recall that the practical Blockchain systems exhibit low write availability, and may drop valid transactions. Given a faulty Blockchain like this, a malicious server can selectively omit operations in her attestation such that dropped transactions of client attestations correspond to the omitted operations in the server attestation. By this means, the server can omit operations without being detected by ContractChecker, in a way to conceal inconsistency. For instance, in Figure~\ref{fig:execution}, Client $C_2$'s call of \texttt{attestClientLog($w_2$)} can be dropped by the Blockchain. 
The malicious server, observing $w_2$ is not included in the Blockchain, can selectively omit the operation in her attestation. This will allow the forged log (with omitted operations) to pass the log crosschecking (more specifically, \texttt{crosscheckLog($\{w_1,r_3[w_1]\}$,$\{w_1,r_3[w_1]\}$)}, which further tricks the ContractChecker to assert incorrectly that the operation history (which is actually $w_1,w_2,r_3[w_1]$) is consistent. Because in this attack, the server selectively omit operations based on dropped transactions in Blockchain, we call this attack by \emph{selective-omission} attack.

{\bf Security hardening against Blockchain unavailability}: The selective-omission attack can be prevented if the finality of any client's log attestation in Blockchain can be assured of. To prevent the miss of a transaction on Blockchain, a common paradigm is to resubmit the transactions. A naive resubmission policy is to resubmit every $F$ block until the transaction is finalized. With this naive policy, it may lead to an unwanted situation where the resubmitted transaction keeps being declined (e.g., due to low transaction fee). 

Enforcing a time bound on transaction finality is crucial to the security of ContractChecker. That is, ContractChecker's security relies on whether a transaction (after resubmission) can be guarantee to succeed before a pre-scribed timeout. Because if both clients and Blockchain are allowed to be unavailable in an arbitrarily long time, it is impossible to distinguish between the benign case of an inactive client where the client does not send a transaction and the malicious case of an unavailable Blockchain under selective-omission attacks.

Therefore, our security hardening technique is to enforce a time bound on the transaction finality. Instead of resubmitting transactions, we require high transaction fee (e.g., based on a heuristic, $20\cdot{}10^{9}$ Wei in Ethereum transactions) and increase the chance of transaction being accepted in the first place namely in $F$ blocks. The higher transaction fee is, the more likely a transaction is being accepted to be included in the Blockchain. The relationship between Blockchain write availability and transaction fee is evaluated in 
our technical report~\cite{me:tr19cc}
With the high transaction fee, all clients wait for $F$ blocks after their transactions. 

{\bf Analysis of attack prevention}: If all active ContractChecker clients execute the transaction resubmission policy, the selective-omission attack can be prevented. What follows is the security analysis: Assume the resubmission policy can guarantee the high chance (the evaluation is in our technical report~\cite{me:tr19cc}) 
 that all clients' transactions (for \texttt{attestClientLog()}) are included in the Blockchain before the timeout of $F$ blocks. The selective-omission attack cannot succeed because any valid operation can be found in the client log attestations and the omission of the operation in the attack can be detected by the mismatch in log crosschecking. In the previous example, by the time $w_2$ is included in the Blockchain (before $F$ blocks), the ContractChecker can detect the $w_2$ is absent in the server log as it appears in Client $C_2$'s log. The ContractChecker can identify the attack, recover the server log for making a correct assertion about the operation inconsistency.

\subsubsection{Forking Attacks}

{\bf Preliminary on forking attacks}: Consider multiple clients share a state hosted on a server. In this setup, a forking attacker is a malicious server who forks the shared state and serves different clients with different (forked) states. In client-based consistency protocols (e.g., Catena and Caelus), the malicious server may fork her log attestations for different auditing clients, such that the forked global logs appear to be consistent from different clients' local views. 

In ContractChecker, both clients and server send their attestations to the Blockchain where the crosschecking occurs. The regular forking attack where the server forks her view among clients may not succeed because the Blockchain essentially provides a ``gossiping'' channel among clients and miners. However, Blockchain provides only an imperfect gossiping channel and there are exploits one can leverage to break the gossiping channel.

The central idea here is that the server can fork the inputs to the \texttt{crosscheckLog()} function in smart contract so that the function instances running on different miners take forked inputs (from the server and clients) and falsely accept separately. The forking can be facilitated by exploits such as smart contract races and Blockchain forks. 

\label{sec:security:bkc:fork}
{\bf Exploiting Blockchain forks}, the server log is forked by the malicious server and the logs of different clients may be forked due to network partitions. This could effectively lead to a forking attack. Concretely, when the network partition separates the Blockchain network and clients into different partitions and the server is in a position to mount the forking attack and to send different partitions different server views. For instance, consider the server wants to hide a ``total-order anomaly'' sequence $w_1|w_2,r_3[w_1]|r_4[w_2]$ where $w_1$ and $w_2$ are concurrent, $r_3$ and $r_4$ are concurrent, and the four operations are submitted from four different clients  (respectively $C_1,C_2,C_3,C_4$). The network partitions clients and Blockchain at the attestation time to two partitions, say $P_1$ and $P_2$, where in $P_1$ clients $C_1$ and $C_3$ attest to $w_1$ and $r_3$ to the Blockchain, and in $P_2$ clients $C_2$ and $C_4$ attest to $w_2$ and $r_4$ to the Blockchain. Then, the server is in a position to launch a forking attack by sending a view of server log ($w_2w_1r_3[w_1]$) to Blockchain partition $P_1$ and another (forked) view of server log ($w_1w_2r_4[w_2]$) to Blockchain partition $P_2$. Because the client attestations are also forked due to network partition, the smart contracts of ContractChecker running in both $P_1$ and $P_2$ will (falsely) accept.

To make this attack successful, the key is the Blockchain fork due to the network partition. In practice, however, this type of Blockchain fork is temporary and is resolved when the network reconnects. When the network reconnects, one of the Blockchain forks will be orphaned, which will leave some client attestation omitted eventually. For instance, if the fork in $P_1$ is chosen and that in $P_2$ is orphaned, the client attestations from $C_2$ and $C_4$ can be permanently lost. In our scheme, this attack is detected by our client-side technique (\S~\ref{sec:security:bkc:available}) which will check the finality of transactions after sufficient time.

For other types of Blockchain forks, such as caused by software updates, forking attacks cannot succeed. Because client attestations are not separated, all Blockchain forks will receive the same set of attestations of all clients. To hide an inconsistent anomaly (e.g., stale read), it would require the fresh write operation to be omitted in the Blockchain, which is impossible in the presence of all client attestations. Note that by forking the total-order declaration, it is not sufficient to hide inconsistency anomaly.


\label{sec:security:bkc:race}
{\bf Exploiting smart-contract races}, the forking server attempts to update the server log in the middle of function execution of \texttt{crosscheckLog()} by exploiting race conditions. The goal is to make client logs cross-checked with different (forked) versions of server log.
Concretely, consider the function-call sequence \texttt{$S$.serverAttestLog($w_1,w_2,r_3[w_1]$)}, \texttt{$C_1$.clientAttestLog($w_2$)}, \texttt{$C_2$.clientAttestLog($w_1,r_3[w_1]$)}, \texttt{$S$.serverAttestLog($w_2,w_1,r_3[w_1]$)}. Suppose before \texttt{$S$.serverAttestLog($w_2,w_1,r_3[w_1]$)} runs, the contract already enters \texttt{crosscheckLog()} where the server log $w_1,w_2,r_3[w_1]$ is being crosschecked with  client logs $w_2$ and $w_1,r_3[w_1]$. When \texttt{$S$.serverAttestLog($w_2,w_1,r_3[w_1]$)} runs, it might happen that the call of \texttt{$S$.serverAttestLog($w_2,w_1,r_3[w_1]$)} replaces the variable of \texttt{ops\_server} \emph{during} \texttt{crosscheckLog()}. This may lead to the unwanted situation that client log $w_2$ is crosschecked with one version of server log $w_1,w_2,r_3[w_1]$, and client log $w_1,r_3[w_1]$ is crosschecked with another version of server log $w_2,w_1,r_3[w_1]$. In this situation, server log $w_2,w_1,r_3[w_1]$ will survive as the successfully crosschecked version, which will lead to an incorrect consistency.
We call this attack by \emph{forking-by-races} attack.

The ContractChecker prevents the forking-by-races attack by synchronizing the critical functions and avoiding concurrency. Concretely, in ContractChecker, we define a critical section around the functions \texttt{crosscheckLog()} and \texttt{auditLog()}, such that the execution of these two victim functions needs to be serialized with other functions. To be more specific, in the forking-by-races attack, 
the attacker (i.e., calling function \texttt{$S$.serverAttestLog($w_2,w_1,r_3[w_1]$)}) and the victim (i.e., running function \texttt{crosscheckLog()}) are forced to execute in a serial order. Without concurrent execution of attacking and victim functions, the attack cannot succeed.

\subsection{Incentivize DoS Attacks}

{\bf DoS attacks}: With the policy of high transaction fee, it is tempting to design the following DoS attack: An attacker can 1) join the Blockchain network as an honest miner who mines and executes the smart contract to collect transaction fee, and 2) join the ContractChecker protocol as a client to send transactions and run DoS attacks. The rationale behind the attack is that the attacker can make coins from her ``honest miner'' role and spend the coins to generate some high-fee transactions sent to the Blockchain. This effect of the high-fee transactions is to race against the transactions sent from honest ContractChecker clients and to prevent them from being included in the Blockchain. The honest clients, in the hope of including their transactions in the Blockchain, would be forced to increase their fee again, which will be collected by the DoS attacker miner and inventive them to launch more DoS attacks.

We believe the above attack is hard to succeed in existing public Blockchain which runs in a large P2P network. The chance of making a perceivable amount of coins (by mining and running smart contract) in today's public Blockchain is slim. A self-sustainable DoS attack would need a large investment (similar to $51\%$ attack) to bootstrap. Without it, any DoS attacker would lose coins and cannot sustain.

\input{text/fc19-kaili.tex}

\section{Conclusion}
This work presents ContractChecker, a lightweight consistency verification protocol based on public Blockchain. 
It presents a new approach by auditing the storage log on the Blockchain, and has advantages in saving the clients' cost and lower availability requirements.
ContractChecker is implemented in a middleware system federating cloud services, clients and the Blockchain. 

\section{ContractChecker Middleware System}
\label{sec:middleware}

The ContractChecker middleware is a distributed system that runs several jobs on individual nodes and runs remote-procedure calls (RPCs) to connect them together. Concretely, the server and clients run local logging jobs (Job 1) that log the operation histories in their respective views. The server calls a log-attestation RPC to the Blockchain by the end of each epoch (Job 2). Each client calls a log-verification RPC to the Blockchain by the end of each epoch (Job 3); This job is about the client's operation history $F$ epochs ago. The Blockchain runs log-auditing job on chain (Job 4). 

The local jobs such as logging (Job 1) and \texttt{auditLog} (Job 4) are implemented using native programming language. In particular, Job 4 is a smart-contract program triggered by the log-verification job. The scheduling of the jobs and events is described before in Section~\ref{sec:secureprotocols}.

Most RPCs in ContractChecker are initiated by the off-chain parties; \texttt{attestLog} is initiated by the server and \texttt{verifyLog} is initiated by individual clients. They are implemented as a smart-contract function on chain as the RPC callee and a program off-chain as the RPC caller. 


\subsection{Off-chain Notification}

Some variants of ContractChecker require a reversed RPC for notification of off-chain parties. For instance, in off-chain persistent log (\S~\ref{sec:persistentlog}), the Blockchain needs to access the operations stored off-chain on server. Sending a notification from on-chain to off-chain, it presents a challenge in current Blockchain system, where transactions are sent from off-chain to on-chain. 

We implemented a basic off-chain service that virtually supports Blockchain-initiated RPCs. In this service, the Blockchain and off-chain server conceptually share a variable on-chain. The server periodically sends heartbeat messages to a smart-contract function that simply reads and returns the shared variable. The Blockchain has the write access to the shared variable. When it wants to notify the off-chain server, the Blockchain sets the value of the variable. Next time, when the server sends heartbeat transactions and calls the variable-check function, she will get a non-zero value in return. The server gets notified in a timely fashion (depending on how frequently it sends heartbeats).

\section{Client Identity Management}

In ContractChecker, clients and server are pseudo-identified by their Blockchain addresses. Their addresses are publicly known (e.g., through secure public-key distribution) and are hard-coded in the ContractChecker contract. A function in ContractChecker is associated with an intended caller. For instance, function \texttt{attestClientLog} is associated with one of clients’ addresses. When the function is called, the contract will check if the caller matches one of the intended clients.  

ContractChecker requires clients to be identified and requires each contact-function call to authenticate clients through the identity. This is necessary not only for data authenticity but also for detecting inconsistency. Without client authentication, anyone can call a ContractChecker function and inject a forged operation to the on-chain log. The forged log can violate data authenticity or consistency. For instance, the server injects a non-existing write $w_3$ between $w_1w_2$ and $r_3$; this is done by calling $\texttt{attestClientLog}(w_3)$. The forged log can accept a read returning the forged write $r_3[w_3]$, which violate data authenticity. It can also violate consistency. For instance, the server injects a non-existing delete $d_3[w_2]$ between $w_1w_2$ and $r_3[w_1]$, which can effectively conceal the inconsistency read $r_3[w_1]$ from clients.

The above, we consider the case of static membership where clients’ addresses are hard-coded in the contract. The case of dynamic membership where clients join the network can be handled by an external, trusted identity provider service which authenticates newly joined clients and update the contract with their addresses.

{\it Security}: We consider that adversaries attempt to impersonate clients and inject forged operations to the on-chain log. The adversary can do so by 1) stealing the private key of a client, and 2) updating the addresses in the contract. For the attack vector 1), we assume clients’ private keys are securely stored. In the case of stolen keys, an external mechanism exists to notify clients and contract author to revoke the address from the contract. For attack vector 2), we assume a trusted contract author and a client-authentication mechanism. An adversary cannot be authenticated as a client and a contract author will not be tricked to whitelist an adversary’s address in the contract. Note that due to the security of a digital signature, one cannot forge a signature without knowing the private signing key.

\newpage

\section{Client Identity Management (Longer)}
\subsection{Overview}
\label{sec:setup}

We consider clients are identified (e.g., by their public keys) and there is a trusted identity server who maintains a whitelist of trusted clients. During the system setup phase, each trusted client authenticates herself and register her public key with the trusted identity provider. This forms a closed membership among trusted clients. The identity provider sends the list of registered clients to the ContractChecker contract such that it can identify and authenticate clients in the online phase. The overall workflow is depicted in Figure~\ref{fig:model}. Note that the identity provider is engaged only in the system-setup phase, and is not involved in the online phase. The online-serving phase is the focus of ContractChecker protocol. 

\begin{figure}[!ht]
\begin{center}
    \includegraphics[width=0.4\textwidth]{figures/protocol1.ps}
\end{center}
\caption{System model in ContractChecker}
\label{fig:model}
\end{figure}

\subsection{Client Identity Management: Details}
\label{sec:idp}

In ContractChecker, clients and the server are pseudo-identified by their Blockchain addresses (public keys). However, unlike a raw Blockchain, the server and clients form a closed membership network in that not everyone can join the system as a client.

For now, we consider the static membership and assume the Blockchain addresses of clients and server are hardcoded in smart contract; We will consider the dynamic client membership in Section~\ref{sec:dynmember}.

Each function call in ContractChecker performs the authentication of the caller. This is simply done by checking the equality of the RPC call's address and the hard-coded address. For instance, serving the \texttt{attestLog}, the ContractChecker authenticates the caller and checks if she is the server. Serving other calls such as \texttt{attestLog}, the ContractChecker authenticates the caller and checks if she is one of the clients. The execution of these functions proceed only when the authentication succeeds.

{\bf Client-impersonation attacks}: We consider the attack where an adversary (e.g., the untrusted server) impersonates one of the clients.\footnote{ An adversary can of course impersonate a server and send a fake log. This case can be reduced to the untrusted server in our trust mode. We don't explicitly consider this case here.} The client impersonator can validate an operation forged by the malicious server. 

Without the client authentication, client-impersonation attack can easily succeed, as anyone can call any ContractChecker function on chain and inject arbitrary data to the log. The forged log can confuse downstream computations for the consistency checking. For instance, suppose the sequence of operations is $w_1w_2r_3$. The server can forge an operation $w_3$ in sequence $w_1w_2w_3r_3$ and impersonates a client who runs \texttt{verifyLog} to validate $w_3$. The server can return $r_3[w_3]$, an incorrect result, to a genuine client. Because log $w_1w_2w_3r_3$ can be verified, this incorrect result can be detected by ContractChecker. More severely, if a delete operation is supported, the server can forge a delete operation, say $d_3[w_2]$ as in $w_1w_2d_3[w_2]r_3$, which will be validated by the impersonated client. The server can then return stale write $w_1$ as the result to the client $r_3[w_1]$, without being detected by ContractChecker.

{\bf Security analysis}: The client authentication in ContractChecker is based on public key distribution and digital signature. A client impersonator who aims at passing the authentication code on chain may need to generate a signature that can be verified by one of these public keys hard-coded (Impersonation Attack 1 or IA1). The unforgeability of digital signature~\cite{DBLP:books/crc/KatzLindell2007} ensures the client's inability to forge a signature without its private key. The impersonator can also attack by stealing the victim client's private key (IA2). We assume the private key is securely stored in each client's off-chain wallet and is not disclosed externally. The impersonator can attack by modifying the hard-coded list of client addresses and by adding its own address there (IA3). We assume the hard-coded client addresses is a read-only variable in the smart contract and we assume the memory safety of smart contract. 

\subsubsection{Dynamic Client Membership}
\label{sec:dynmember}

In this section, we address the dynamic client membership where clients can join and leave the cloud-storage system. 

The dynamic client membership is handled by an external trusted identity provider (IdP). Instead of hard-coding client membership as in the static case, the ContractChecker maintains a directory (in a mapping variable) storing the Blockchain addresses of all registered clients. During the function calls, the caller clients are authenticated using the dynamic directory of addresses. When a new client joins the system, the IdP performs its own client registration using the standard InfoSec procedure. The Blockchain address of the client is included as one of her identities. Once the registration completes, the IdP server will add the new account and her Blockchain address to the ContractChecker. When a client leaves the system, the IdP deregisters the client account and removes the Blockchain address from the ContractChecker directory.

To authenticate the IdP itself, the Blockchain address of the IdP server is static and is hard-coded in the smart contracts. 
Recall that Figure~\ref{fig:model} has shown that the Blockchain interacts the IdP server to manage identity on chain.




\section{Evaluation}
\label{sec:eval}
\label{sec:macro}

In this section, we evaluate the client cost in ContractChecker.
We first present an analysis of client cost and then present our experimental results. 

\subsection{Cost Analysis}
{\bf Cost model}: For a consistency verification protocol, either client-based schemes or ContractChecker, its execution can be modeled by the following: Clients periodically send their log attestations and check the consistency results. In this process, a client's cost is characterized by 1) how many operations the client needs to store, and 2) how long the client needs to maintain an operation. In our cost model, we accredit to one cost unit storing one operation by a client in one epoch. Given a process of $T$ epochs, a client's total cost is the sum of cost units of all operations stored in the client in all epochs. If an operation is stored continuously in a client for $T$ epochs, it is counted as $T$ units. 

Based on the above model, we present a cost analysis of client-based auditing schemes and ContractChecker. 

{\bf Client cost in client-based auditing}:
In client-based auditing schemes, a client needs to access operations submitted by all clients in the current epoch, including herself and other clients; these operations may only need to be stored by the clients in one epoch, assuming a trusted third-party attester. 
For simplicity, we omit the cost of accessing historical operations. Instead, we focus on a low-bound estimate of the client cost in client-based auditing schemes:

\begin{equation}
CCost_{ClientAudit} \geq{} T\cdot{}M\cdot{}N
\label{eqn:clientaudit0}
\end{equation}

The above equation considers that the protocol is run in $T$ epochs among $N$ clients where each client in one epoch submits $M$ operations on average. The equation reports the total cost. We focus on the ``unit'' client cost, that is, the client cost per epoch and per operation:

\begin{equation}
CCost^{Avg}_{ClientAudit} =
CCost_{ClientAudit}/(T\cdot{}M) 
\geq{} N
\label{eqn:clientaudit}
\end{equation}

The above equation considers a client's cost in a process of running client-based auditing scheme in $T$ epochs, with totally $N$ clients where on average each client in one epoch submit $M$ operations. 

{\bf Client cost in ContractChecker}: 
In the above setting, a ContractChecker client only needs to store her own operations, that is, $M$ operation per epoch. 
But the ContractChecker client needs to keep an operation for, instead of the current epoch, but an extended period of time denoted by $F_t/E$ epochs. $F_t$ is the average delay for successfully submitting a client attestation to the Blockchain in ContractChecker. Specifically,

\begin{equation}
F_t=r\cdot{}(B\cdot{}F+P)
\label{eqn:ft}
\end{equation}

Here $r$ is the average times to resubmit a client attestation, and $F$/$B$/$P$ is the finality delay/block time/average wait time for transaction validation. Thus, ContractChecker's client cost is as follows. Note that in ContractChecker, log auditing is fully delegated and clients are relieved from accessing historical operations.

\begin{equation}
CCost^{Avg}_{ContractChecker} = F_t/E
\label{eqn:cc}
\end{equation}

Therefore, the cost saving of ContractChecker comparing existing client-based auditing schemes is:
$\frac{CCost^{Avg}_{ClientAudit}}{CCost^{Avg}_{ContractChecker}}
\geq \frac{E\cdot{}N}{F_t}$.
This formula shows that the cost saving of ContractChecker comparing existing work depends on three factors: the total attestation delay $F_t$, the maximal number of clients $N$, and epoch time $E$.
The larger $E$ is, the more costs the ContractChecker saves. Because with a larger $E$, the client-based schemes have to store an operation for longer time. The larger $F_t$ is, the fewer costs the ContractChecker saves. Because with a larger $F_t$, an operation needs to be stored on a ContractChecker client for longer time. The more clients there are (a larger $N$), the more costs the ContractChecker saves. Because with a larger $N$, the more operations a client needs to store (in client-based auditing schemes).


\subsection{Experiments}
\subsubsection{Client Cost}

\begin{figure*}[!hbt]
\begin{center}
\subfloat[With varying number of clients]{
   \includegraphics[width=0.225\textwidth]{figures_macroycsb/exp-Clientcost-Numberofclients-large.eps}
    \label{exp:numclient:1}
}
\subfloat[With varying number of clients]{
   \includegraphics[width=0.225\textwidth]{figures_macroycsb/exp-Clientcost-Numberofclients-small.eps}
    \label{exp:numclient:2}
}
\subfloat[With varying number of operations]{
   \includegraphics[width=0.225\textwidth]{figures_macroycsb/exp-Clientcost-Numberofoperationsperepoch-large.eps}
    \label{exp:numops:1}
}
\subfloat[With varying number of operations]{
   \includegraphics[width=0.225\textwidth]{figures_macroycsb/exp-Clientcost-Numberofoperationsperepoch-small.eps}
    \label{exp:numops:2}
}
\end{center}
\caption{Client costs of ContractChecker}
\label{exp:capacityether}
\vspace{-0.10in}
\end{figure*} 

Based on the cost model above, we design experiments for client cost measurement. Our experiments focus on transaction-validation delay ($P$) and maximal number of operations ($N\cdot{}M$), w.r.t. the budgeted amount of Ethers. Based on the results, we compare ContractChecker's client cost with that of client-based auditing schemes.

We design experiments to evaluate the client cost of ContractChecker in comparison with client-based auditing schemes. From our cost analysis, the unit client cost of ContractChecker is $F_t/E$ (Equation~\ref{eqn:cc}) and that of client-based schemes is proportional to $N$ (Equation~\ref{eqn:clientaudit}). The source of extra cost is that ContractChecker needs to maintain a local operation for extra time and client-based schemes need to replicate a client's operation to all other clients. In this section, we aim at comparing the client costs of these two scheme paradigms using experiments.

Designing the experiments, we observe there are two factors affecting the cost, the number of clients (i.e., $N$) and the number of operations per epoch (i.e., $M$). Increasing $N$ and $M$, it will saturate the current block ingesting the operations in an epoch and delays the inclusion of all operations to next blocks. We thus design experiments to measure $F_t$ with varying $N$ and $M$. We consider the setting that $E$ is longer than $F_t$  such that the Blockchain will not permanently drop transactions. To measure $F_t$, we run $N$ clients to concurrently submit their attestation transactions to the Blockchain. The $N$ clients then proactively check the finality of the transactions. For simplicity, we use the maximal transaction fee to reduce the transaction pending time and exclude the case of dropped transactions. 
We record the time duration between the first transaction is submitted and the last transaction is finalized on Blockchain. 

{\bf Experiment setup}: We conduct experiments in a private Ethereum testnet and a public testnet. 
For the public testnet, we connect our ContractChecker protocol to the Ropsten testnet~\cite{me:ropsten}. 
For the private testnet, we run four Ethereum miners in an LAN network on campus. The machine specs is Intel 8-core i7-6820HK CPU of 2.70GHz, 32 GB RAM and 1 TB Disk. The default configuration for Ethereum (e.g., difficulty levels) is used. 
Note that our target metrics (e.g., transaction fee and Gas) are independent of network scale.
We deploy our smart-contract program written in Solidity to the Blockchain, by leveraging an online Python tool\footnote{\url{https://github.com/ConsenSys/ethjsonrpc}}.

We present the client costs with varying $N$ (number of clients) in Figure~\ref{exp:numclient:1} and Figure~\ref{exp:numclient:2}. In this experiment, we consider $M=1$ (each client submits one operation in one epoch) for the maximal scalability. From Figure~\ref{exp:numclient:1}, it can be seen that ContractChecker incurs much lower unit client cost than client-based schemes. With increasing number of clients, the client-based schemes incur a linearly increasing cost, while the ContractChecker's cost barely changes (it slightly increases as shown and analyzed in Figure~\ref{exp:numclient:2}). The reason behind is that with a new client, the client-based schemes require to replicate a given operation while ContractChecker does not replicate local operations to the new client. With an increasing $N$, the number of operations per epoch may increase, and that causes ContractChecker's client cost to increase --- with more operations in an epoch, it takes more blocks to include the operations, thus longer $F_t$. This can be seen in Figure~\ref{exp:numclient:2} more clearly. More specifically, with the public testnet, it takes one blocks to include all operations produced by up to $N=200$ clients, takes two blocks by up to $370$ clients, etc. The private Blockchain testnet incurs a slightly higher client cost than the public Blockchain\footnote{This result is a bit surprising to us, as the private Blockchain testnet is dedicated to ContractChecker while the public testnet is shared. We verify this is due to that in the private testnet a block can be utilized up to $80\%$ of specified gas limits, while the public testnet a block can be utilized $100\%$.}, and also has lower variance. Note that the increase rate of ContractChecker with $N$ is much slower than that of client-based schemes.

We present the client costs with varying $M$ (the average number of operations per epoch per client) in Figure~\ref{exp:numops:1}. In this experiment, we consider $N=132$ clients so that we can test up to $M=100$ operations. The result shows that ContractChecker's client cost is about one fifth of client-based auditing schemes' cost. With the increasing $M$, ContractChecker's cost slightly increases.

\subsubsection{Blockchain Availability and Transaction Fee}
\label{sec:availability}

\begin{figure}[!ht]
  \begin{center}
    \includegraphics[width=0.425\textwidth]{figures_macroycsb/exp-PercentageofContractCheckertransactionsinablock-Blockheight.eps}%
  \end{center}\vspace{-0.15in}
  \caption{Blockchain availability under varying transaction fee}\label{exp:txfee}
\end{figure}

In this experiment, our goal is to show the relationship between Blockchain write availability and transaction fee. We simultaneously run two Ethereum clients (on two separate machines), each of which drives 1500 transactions to the Ropsten testnet. The two clients respectively use high transaction fee ($20*10^{-9}$ Ether) and low fee ($1*10^{-9}$ Ether). All transactions are driven to the Blockchain at the time of one block (with the relative block height $0$) and we observe how and when transactions of different fees get included in the Blockchain. We repeatedly conduct 10 experiments and present the averaged result in Figure~\ref{exp:txfee}. In this figure, all 1500 transactions with high fee are included in the blocks before (or with smaller block height) the other 1500 transactions with low fee. More specifically, the 1500 transactions of high fee takes about 6 blocks to be included while the 1500 transactions of low fee takes up to 10 blocks to be included. This result shows that with higher transaction fee, transactions get included earlier and it is less likely to drop the transactions with lower fee. 

\section{Motivating Applications}
\label{sec:targetapp}


While ContractChecker can definitely benefit small-scale cloud-hosted
applications such as smart homes~\cite{bolt_nsdi14}, we argue that
ContractChecker can be utilized in a long spectrum of application
scenarios, ranging from low-throughput small
organizations~\cite{bolt_nsdi14}, to enterprise-scale cloud object
stores~\cite{docker_fast18}. In the following we list two representative
examples of real-world use cases. 

{\bf
DockerHub style container-distribution infrastructures} (hereafter
called ContainerRegistry):
The ``ContainerRegistry'' distributes the latest software from
developers to users in the form of Docker container images. The
ContainerRegistry is usually hosted in third-party public cloud, such
as in hub.docker.com, which is independent of both developers and
users. The storage consistency implies security as returning a stale
image (violating the strong consistency) from the hub means the users
may run buggy programs, vulnerable to the latest attacks. The
ContainerRegistry is usually accessed infrequently. For instance,
workload analysis on IBM Docker Registry reports that, among seven
geo-distributed registry deployments, the busiest one serves only 100
requests per minute for more than $80\%$ of
time~\cite{docker_fast18}\footnote{The workloads exhibit diurnal
patterns and the peak throughput is remarkably low as well.}.

{\bf
Certificate-transparency(CT) log}: The CT log stores the
certificates about key-identity bindings, and is made public to
invite public scrutiny for timely detection of certificate mis-issuance.
Violating storage consistency in CT log
leads to the security breaches such as concealing of mis-issued certificate or use of revoked keys.
The load of writes in a CT log (regenerating/revoking a public key) is usually low and the read load is not high on a small number of domains (websites).

{\bf
GitHub style software-development infrastructures} (hereafter
called GitHub):
GitHub provides a software-development service among collaborative developers.
The GitHub service is hosted in
the third-party public cloud and the storage consistency is security
sensitive, as exploiting inconsistency can lead to wasted
development efforts on a deserted branch~\cite{DBLP:conf/uss/Torres-AriasACC16}. The access loads in a
certain GitHub repository depend on the size of development team and
are typically not high (as commonly observed in public repositories'
committing history).

{\bf
Device synchronization thru. cloud}:
In the personal cloud services, such as Apple iCloud~\cite{icloud}, Dropbox~\cite{me:dropbox} and Microsoft OneDrive~\cite{me:onedrive},
the cloud storage is used to synchronize
multiple personal devices of the same owner.  Storage
synchronization among devices occurs at a low frequency with
remarkably low average throughput, typically once every one
hour~\cite{dropbox_imc12,mobile_cloud_imc16}. The clients are typically
low-power resource-constraint devices in this scenario. Data consistency is
important to applications where the users need to view the latest
information when switching among devices. In the real world, even though iCloud is mostly reliable, users find local updates are not synchronized fast enough, leaving a human-perceivable time to observe stale data~\cite{me:icloudsync}. Using ContractChecker presents a more proactive solution to detect the real inconsistency incidents in personal cloud services.



These application scenarios feature the following properties that motivate the use of Blockchain: 
S1) The clients are of limited capability in computing, storage, and availability. Thus they outsource data storage to a third-party cloud. In both scenarios above, the client can be a mobile phone (e.g., hosting a web browser against a CT log or installing security patches against a ContainerRegistry). 
S2) On the cloud-hosted data storage, violating storage consistency leads to a security consequence to the application. Intuitively, using a Blockchain as a ``trusted'' third-party witness can harden the application security.
S3) The storage-access load in our application scenarios is typically lower than tens of operations per second. In particular, the low throughput properties of these typical application scenarios make it amenable for the use of Blockchain, which is known to have limited throughput in ingesting transactions.

\section{Security under Client/Server Attacks}
\label{sec:clientserver:appendix}

\subsection{\bf Security against the Malicious Server}
\label{sec:servertrust}

In ContractChecker, the server's job is to declare a total-order over concurrent operations and to attest to it. A benign server is allowed to find a total-order without inconsistent operations to the degree that she does not forge operations.

Before describing the server threats, we stress that our server, be it benign or malicious, is \emph{rational}. Given a consistent operation history, a rational server does not falsely attest to a total order with inconsistency, as it does not have the incentive to do so. For instance, consider an operation history $w_1|w_2r_3[w_1]$ where $w_1$ and $w_2$ occur concurrently. A rational server will find the total-order for consistency (i.e., $w_2w_1r_3[w_1]$) and attest to it. The rational server is not incentivized to attest to the total-order with inconsistent operations (i.e., $w_1w_2r_3[w_1]$). Note that both total-orders match the real-time relation in the concurrent operation history.

{\bf Server threats}: The goal of a malicious (and rational) server is this: Given an inconsistent operation history, a malicious server aims at concealing the inconsistency by forging operations and declaring a false total order over it. In order to conceal inconsistency, the malicious server can launch a variety of threats: A malicious server forges a non-existing operation (AS1), omits the valid operation (AS2), replays a valid operation multiple times (AS3), reorders the serially-executed operations (AS4). 

{\bf Attack detection}: ContractChecker can detect the server attacks by the difference between the client logs and server log. Concretely, the server forging an operation (AS1) can be detected by an operation in the server log that cannot be found in any client log. The server omitting an operation (AS2) can be detected by an operation in a client log that cannot be found in the server log. The replay attack (AS3) can be detected by identical operations in the server log. Reordered operations (AS4) can be detected by the condition that the operation order does not match real-time (i.e., an operation that occurs later is ordered before an earlier operation). 

\subsection{\bf Security against Malicious Clients}

{\bf Client threats}: A malicious client is incentivized to falsely accuse a benign server of inconsistent operations that the server did not process. Towards this goal, a malicious client can mount the following attacks to forge her log attestation. Specifically, she omits her local operation (AC1), forges an operation the server did not process (AC2), replays a valid operation multiple times (AC3), reorder the serially-executed operations (AC4). For instance, given a consistent history, the client can forge a write operation $w_2$ between $w_1$ and $r_3[w_1]$ to make $r_3$ look like a stale read. She can omit $w_1$ to make $r_3[w_1]$ look like an invalid read. She can reorder her local operations from $w_2w_1r_3[w_1]$ to   $w_1w_2r_3[w_1]$, such that $r_3[w_1]$ is falsely inconsistent.

{\bf Attack detection}: The attacks by forging a client log can be detected by the difference between the client logs and server log. Due to no server-client collusion, we assume that the server attests to a truthful log of operations. Thus, any operation forged by the client will result in a mismatch to the server log (which can be similarly analyzed as malicious server attacks).

\subsection{\bf Security Hardening for Attack Mitigation}
\label{sec:attackmitigate}

\begin{figure}[!ht]
\begin{center}
    \includegraphics[width=0.25\textwidth]{figures/logaudit.eps}
\end{center}
\caption{The logic in \texttt{LogAudit()} in ContractChecker for attack detection and mitigation}
\label{fig:logaudit}
\vspace{-0.10in}
\end{figure}

In the ContractChecker, attacks from a malicious server or clients are detected by the mismatch between the server attestation and client attestations (in \texttt{crosscheckLog()}). In the case of attacks, the ContractChecker does not only detect them but also mitigate them in the sense of making a trustworthy assertion about the log consistency in the presence of attacks. We describe how attacks are detected and mitigated.

In order to distinguish attacks from clients and the server, we augment the basic protocol (in \S~\ref{sec:basicprotocol}) by requiring both client and server signatures on both server attestation and client attestation. More concretely, every online operation (i.e., read/write) is augmented with a server signature and a client signature. This can be naturally integrated to the regular request/response workflow without adding extra communication round. When a client submits a request, she embeds in the request her signature of the requested operation, such that the server receives a client-signed operation. When the server processes the operation, she produces a server signature over the operation response, such that the client receives a server-signed operation response. When the client starts to do attestation, she will sign her local log of server-signed operations with the client signature. When the server starts to do attestation, she will declare the total order based on the client-signed operations. When the Blockchain receives a client attestation, it will validate the input by verifying both the client signatures and server signatures attached to the attestation. So is the case of validating a server attestation. We call this extension by double-signed attestation.

{\bf Distinguishing causes of attacks}: With the double-signed attestation, the ContractChecker can distinguish different attacks (in our threat model). When the server attestation contains an operation whose client signature cannot be verified, this is attributed to a server attack forging a non-existing operation (AS1). 
If the client signature of a server operation can be verified but the operation cannot be found in any client attestation, this is attributed to a client attack who omits her local operation (AC1). When the client attestation contains an operation whose server signature cannot be verified, it is attributed to a client attack forging an operation the server did not process (AC2). If the server signature can be verified but the operation cannot be found in the server attestation, it is attributed to a server attack omitting the operation (AS2). The replay attack (AC3 and AS3) where a client (or server) may duplicate a signed operation multiple times can be detected by finding duplicated operations on the server (or client) attestation. Normally, each operation is uniquely identified by a client-generated nonce (using an external source of trusted randomness). In addition, a malicious server (or client) may want to reorder the serially-executed operations in a different order (AC4 and AS4). This attack can be detected by the mismatch between the timestamps in the operations and the total in the attestation.

Note that we assume a rational server who will find a consistent total-order, if it exists, from the operation history and attests to it. In the case of an irrational server, she can break the protocol correctness. The irrational server can do so by intentionally declaring a total order containing inconsistent operations and by tricking the ContractChecker protocol to land a (false) assertion that the original operation history is inconsistent. To make the protocol resilient to irrational server attacks, it may require solving and declaring the total order on chain, which imposes a huge cost on the Blockchain. In addition, irrational server attacks are rare in practice. For these reasons we do not consider them in this work.

{\bf Repair server attestation}: In different attack scenarios, the ContractChecker can repair the server attestation to recover the truthful log and to further assert the log consistency. In AS1 (the server forging attack), the ContractChecker removes the forged operation from the server attestation. In AS2 (the server omission attack), the ContractChecker copy the omitted operation from the client attestation to the server attestation. In AC1 and AC2 (the client attacks by operation omission and forging), no action is needed to recover the server attestation. In replay attacks (AC3 and AS3), if it finds replayed operations on the server attestation, the ContractChecker removes the duplicated copy from the server attestation. After the repair, the ContractChecker can move forward and conduct consistency checking over the repaired server attestation. In reorder attacks (AC4 and AS4), the serial operations are reordered back to match the execution order in their timestamps.

The overall workflow of our ContractChecker for attack detection and mitigation is illustrated in Figure~\ref{fig:logaudit}.

\section{Cost-effective Security Hardening against Selective Omission Attacks}
\label{sec:costreliableatt}

To prevent the selective-omission attack, we propose a transaction-resubmission policy that provide high confidence of transaction finality within a time bound. In our policy, any active client will monitor the state of her \texttt{attestCliengLog()} call. If the finality is not confirmed after $F$ blocks, the client will increase the chance of inclusion by maximizing the transaction fee. We determine the maximal transaction fee based on heuristics in practice. High chances are that the second submission with maximal fee will make the transaction successfully included in the Blockchain.

With the resubmission policy, it can be expected all clients’ transactions in an epoch are successfully included in the Blockchain. We require that all clients wait after $2F$ blocks before using the log-consistency assertion produced by the ContractChecker program. Through this mechanism, it synchronizes across all active clients on the finality of their log attestations on Blockchain.

\section{Availability Requirement of Existing Protocols}
\label{sec:existingavailability}

{\bf Client availability in existing protocols}: In existing client-based protocols, logs are audited on the client side for checking consistency. When one client detects an attack (e.g., the server forged an operation in her log attestation), the incident needs to be reported in a timely fashion so that other clients can be notified to avoid making an incorrect assertion about log consistency.

In an untrusted server setting, the report of attack incidents is done by the untrusted server relaying messages among clients. For instance, client $c_1$ detecting an attack would send a message to the server and all other clients would pull the messages to be notified. The malicious server is able (and is well motivated) to suppress such ``attack detected’’ messages from other clients to conceal storage inconsistency. With highly available clients, this report-suppression attack itself can be detected by requiring all clients to report every epoch. Thus, the absence of a report on the server implies a report-suppression attack.

However, with unavailable clients, existing protocols relying on the untrusted server for message relay cannot guarantee protocol correctness. Be more specific, suppose a client is allowed to be offline and not to participate in the protocol in an epoch. Given the absence of the client’s report, other clients cannot distinguish between the case that the client is truly offline (the benign case) and the case that the client reports a detected attack but the malicious server suppresses it from other clients (the malicious case). Without distinguishing the two cases, other clients cannot make a correct assertion about the consistency. For instance, consider the server omits the $w_2$ in $w_1w_2r_3[w_1]$ in the attestation. If the client of $w_2$ is unavailable to audit the log in an epoch, other clients will not be aware of the omission of $w_2$ and may reach an incorrect assertion that the forged log $w_1r_3[w_1]$ seems to be consistent.

\subsection{Additional Related Work}

{\bf
Blockchain applications}: Blockchain has been applied in both financial and non-financial applications. In the application scenarios, Blockchain and its security properties are repurposed to address application-specific security needs. CSC~\cite{DBLP:journals/corr/abs-1804-05141} runs criminal smart contract on Blockchain for facilitating commissioned crimes. Paralysis~\cite{DBLP:journals/iacr/ZhangDBJ18} supports practical wallet management under key loss/compromise by using Blockchain as trusted clock to detect client unavailability. Blockstack~\cite{DBLP:conf/usenix/AliNSF16} runs trusted directory on Blockchain by treating it as immutable data storage. IKP~\cite{DBLP:conf/sp/MatsumotoR17} proposes an incentive scheme based on Blockchain to address the certificate mis-issuance problems. Blockchain is also used as the source of randomness~\cite{DBLP:books/daglib/0040621}, non-equivocation log as in Catena~\cite{DBLP:conf/sp/TomescuD17}, etc. in many novel applications.

{\bf
Blockchain throughput improvement}: There are known performance problems in Blockchain notably the limited throughput. There are protocol-analysis works on Blockchain that try to understand the throughput limitation (e.g., by block sizing~\cite{DBLP:conf/fc/CromanDEGJKMSSS16}). Lightning network~\cite{me:lightning,DBLP:journals/corr/MillerBKM17} is an off-chain scheme that batches multiple micro-payment transactions to reduce the load on chain. 
Blockchain sharding~\cite{me:omniledger,DBLP:conf/ccs/LuuNZBGS16} partitions the state of transaction graph among multiple miners, in a way to improve its scalability. 



\section{Open Problems}
\subsection{Protocol Insecurity under Collusion Attacks}
\label{sec:collusion}

{\bf Client-server collusion attack}: A malicious server, in collusion with a client, can conceal inconsistency from another client. To be concrete, consider the case in Figure~\ref{fig:execution} where clients $c_1$ and $c_2$ submit an inconsistent sequence of operations, $w_1w_2r_3[w_1]$. Assume in real-time $w_1$ happens before $w_2$. The malicious server attests to total order  $w_2w_1r_3[w_1]$, and client $c_2$ attests to $w_2$ with forged timestamp older than $w_1$. The result of ContractChecker is no inconsistency.

\subsection{Attacks by Irrational Servers/Clients}
\subsection{On-chain Write Buffer doesn't Save Cost}
\label{sec:onchainwritebuffer}

For placing persistent log, we also tried to place a write buffer on chain. This original hope is to use a fixed-length on-chain buffer to store recent writes and to serve reads with temporal locality. On write path, it saves the cost of space allocation, and on the read path, it directs most requests to on-chain reads, which are cheaper than off-chain reads (from an untrusted server). However, a hidden cost is that upon buffer overflows, the buffered writes need to be digested before being cleared. There is tradeoff between the saving in write allocation and the extra cost of hashing for overflow. In practice, as our measurement study shows, the saving is offset by the extra cost, which does not justify the write buffer design.



