# Dynamic Outsourced Proofs of Retrievability Enabling Auditing Migration for Remote Storage Security

Authors: Lu Rao; Tengfei Tu; Hua Zhang; Qiaoyan Wen; Jia Xiao
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Remote data auditing service is important for mobile clients to guarantee the intactness of their outsourced data stored at cloud side. To relieve mobile client from the nonnegligible burden incurred by performing the frequent data auditing, more and more literatures propose that the execution of such data auditing should be migrated from mobile client to third-party auditor (TPA). However, existing public auditing schemes always assume that TPA is reliable, which is the potential risk for outsourced data security. Although Outsourced Proofs of Retrievability (OPOR) have been proposed to further protect against the malicious TPA and collusion among any two entities, the original OPOR scheme applies only to the static data, which is the limitation that should be solved for enabling data dynamics. In this paper, we design a novel authenticated data structure called bv23Tree, which enables client to batch-verify the indices and values of any number of appointed leaves all at once for efficiency. By utilizing bv23Tree and a hierarchical storage structure, we present the first solution for Dynamic OPOR (DOPOR), which extends the OPOR model to support dynamic updates of the outsourced data. Extensive security and performance analyses show the reliability and effectiveness of our proposed scheme.


---

## Body

## 1. Introduction

In today’s information era of data explosion, it is an inevitable trend for most people to have the ever-increasing big data storage demands. Storage outsourcing through the cloud has become a promising technology paradigm that populates the recent literatures [1–3] and has been regarded as a faster profit growth point [4] by various IT industry giants (e.g., Google Drive, Microsoft OneDrive, and Amazon EC2 and S3). Cloud storage not only allows mobile clients to access their outsourced data from anywhere at any time, but also provides mobile clients with many benefits such as the inexpensive storage cost and elastic configuration of the storage capacity, which attract more and more mobile clients (e.g., smartphones and laptops) to join the cloud for the convenient lifestyle.However, at the side of the cloud storage server (CSS), there still exist all kinds of internal and external threats against the storage security of outsourced data, such as Byzantine failures, the monetary reasons, and the hacker attacks [5, 6]. So, it is well known that CSS would be considered as a malicious entity that might try to hide the accident when data loss occurs, or even deliberately delete client’s data for saving storage cost. In this case, for the mobile client who has not actually possessed her data after storage outsourcing, an urgent requirement is how to guarantee thecorrectness andretrievability of the outsourced data. Here, correctness guarantee means that any appointed data returned from CSS should be the latest version of the authentic data, and retrievability guarantee means that the whole outsourced data can be correctly retrieved by the client without any data loss.Based on the application of erasure code and the periodic auditing against CSS, the security model Proof of Retrievability (POR) [7, 8] is defined to offer client-side devices the above two guarantees in the context of malicious CSS. However, given the fact that most mobile clients only have a limited capacity so that these clients are unlikely to keep online all the time to perform the frequent auditing, various public auditing schemes are proposed [5, 6, 9–11] for auditing migration, which enables mobile client to free herself by moving the heavy auditing tasks to a third-party auditor (TPA). But existing public schemes rely on the hypothesis that TPA is trusted to complete the migrated auditing tasks, meaning that these schemes do not provide any security guarantee to resist a malicious TPA that might break the auditing protocols, which is exactly the potential risk that has not been covered by current public auditing schemes [12].The first Outsourced Proof of Retrievability (OPOR) solution, proposed by Armknecht et al. and called Fortress [12], is a stronger security model to protect against any malicious entity (e.g., malicious TPA) and against collusion among any two entities. Fortress enables auditing migration, but it is just a static scheme. Supporting dynamic updates is an essential requirement for numerous practical cloud storage applications [13]. Although all kinds of authenticated data structures [6, 9, 13–16] have been proposed to support data dynamics, there still exist research gaps in these structures. For one thing, most existing dynamic authenticated data structures [9, 14–16] are designed based on the Merkle Hash Tree (MHT). Unfortunately, the use of MHT is not efficient in some cases since MHT is an unbalanced tree. For example, the height of MHT will increase linearly when many new data blocks are continuously inserted in the same leaf position, so in this worst case the expected O(log⁡n) performance cannot be ensured for authenticating the index and value of any appointed leaf node via MHT. For another, although some other authenticated structures such as rb23Tree [6] and Skip List [13] are proposed for dynamism, when there is a need to verify multiple leaf nodes of different data blocks (i.e., authenticate the indices and values of these leaf nodes), all above-mentioned dynamic methods merely adopt the straightforward way of verifying these different leaf nodes one by one with their respective proof paths. Since the verification upon a single proof path is of O(log⁡n) bandwidth and computation costs, as the number of verified leaf nodes increases, it is clearly not an efficient way to separately verify that many leaf nodes one by one. Although a balanced authenticated data structure (e.g., the rb23Tree [6]) constructed upon the balanced tree can avoid the worst case of MHT as discussed above, however, to the best of our knowledge, there is no such balanced authenticated structure that can deal with the problem of how to efficiently batch-verify any number of appointed leaf nodes altogether, which is a limitation that should be further addressed in this paper.Furthermore, to support data dynamics when applying erasure code, the scheme of [6] is based on the way of local coding, that is, encoding each raw data block individually to ensure that an update upon any raw block only affects a small amount of the encoded blocks. However, such local coding solution is vulnerable to the selective deletion attack from malicious CSS [14], because once a targeted raw block has been updated in the case of local coding, CSS can learn which congenetic encoded blocks correspond to this targeted block. Then, CSS can selectively delete these congenetic encoded blocks to actually cause the loss of the targeted block, and simultaneously CSS can pass the data auditing with significant probability, since the auditing relies on the sampling technology that can hardly cover these selectively deleted encoded blocks if the size of deleted data is tiny. Although both the private and the public Dynamic POR (DPOR) schemes [14] are proposed to resist the above selective deletion attack, the direct application of these two DPOR schemes into OPOR model will result in security or efficiency problems. On the one hand, within the private DPOR of [14], the auditing can only be executed using client’s secret key. But TPA is prohibited from obtaining such secret in OPOR, or otherwise the malicious TPA might share client’s secret key with malicious CSS [12] so that CSS can break the auditing protocols without actually holding the outsourced data. On the other hand, in order to support public auditing, the public DPOR of [14] cannot apply the blockless verification technique [8, 9, 13, 17] that combines multiple challenged blocks into a single aggregated block for efficiency, so it has to use the straightforward way of requiring TPA to retrieve all randomly challenged actual blocks during each POR audit. As shown in [9], this straightforward way could lead to a large communication overhead and thus is inefficient and should be avoided.From the above, there will be various problems if the current dynamic schemes are directly ported to the OPOR model. In this paper, to solve these mentioned problems, we propose a concrete Dynamic Outsourced Proofs of Retrievability (DOPOR) scheme enabling auditing migration. DOPOR not only can defend against the malicious TPA and collusion, but also can enable efficient data dynamics under the setting of erasure code. Specifically, our contributions are summarized as follows.( 1 ) Different from traditional authenticated structures that only have the ability to verify different leaves one by one, we propose the novel authenticated data structure called bv23Tree, which is based on the balanced 2-3 tree to ensure the logarithmic complexity in any case of updates and simultaneously enables the verifier to batch-verify the indices and values of multiple appointed leaves all at once for efficiency.( 2 ) To defend against the selective deletion attack, we utilize a hierarchical storage structure with the same-sized levels for the unified management of outsourced encoded data and encoded update operations. According to this hierarchical structure and the bv23Tree, we resolve the open questions of [12] by transforming another secure public POR into the OPOR model and designing an appropriate dynamic scheme to efficiently integrate dynamic updates with OPOR.( 3 ) We analyze the security of our solution and conduct an extensive experimental study. The experimental results demonstrate the effectiveness of our scheme.The rest of this paper is organized as follows: Section2 states the background and introduces the architecture and system model of DOPOR. Section 3 shows the novel dynamic structure bv23Tree in detail, based on which we present detailed DOPOR solution in Section 4. Section 5 provides the security analysis, and Section 6 evaluates the experimental performance. Section 7 overviews the related work. Finally, this paper is concluded in Section 8.


## 2. Background and System Architecture

### 2.1. Problem Statement

We begin with the background of OPOR, as shown in [12]. There are three entities involved in an outsourced auditing environment: mobile client (i.e., data owner), cloud storage server (CSS), and third-party auditor (TPA). Because of their limited local storage capacity, mobile clients are motivated to outsource their large data files to CSS and then can make use of various on-demand cloud storage services. However, because CSS might be misbehaving, it is very important to design the periodic remote data auditing mechanism against CSS, which enables the mobile client to have the assurance that her outsourced data is always available and can be completely retrieved from CSS if necessary. Further, to liberate the mobile client from struggling with the endless online data auditing, OPOR also introduces TPA that has the expertise and ability to perform the above frequent auditing tasks on behalf of the mobile client, and then the mobile client can be offline to rest most of the time.Although OPOR model has the same three entities as existing public auditing model [9, 10, 15, 16], one of the main differences between the two is thatTPA might be also malicious within OPOR[12]. In other words, TPA might violate the auditing protocols, for example, by claiming that he has honestly performed all past auditing, but actually he tells a lie.Furthermore, any two entities might be in collusion within OPOR [12]. For example, firstly, malicious CSS might collude with malicious TPA to deceive the honest client when outsourced data has been lost. Secondly, malicious client might collude with malicious CSS to frame the honest TPA, by asserting that TPA did not correctly perform the required auditing work to bring TPA into the compensation lawsuit. Since any entity might be malicious, in order to solve the problem of securely sampling the periodic challenges for frequent auditing, the time-based bitcoin pseudorandom source is introduced into the OPOR model. As demonstrated in [12], due to the fact that the bitcoin pseudorandom source cannot be manipulated by any entity, it is secure to be used for generating the continuous random seeds for periodic challenges.OPOR inherits the retrievability guarantee of POR [8] by applying erasure code, meaning that the client can retrieve the whole outsourced data in case of minor data corruption. However, when both of the data dynamics and erasure code are considered, the problem of how to efficiently perform the updates is intractable. Within the first OPOR scheme Fortress [12], client’s original data file (including n raw data blocks) is entirely encoded before outsourcing, so an update operation upon any single raw data block will affect the whole outsourced encoded data. In this case, the only way for client is to download and decode the whole outsourced encoded data and then encode and upload all the data again after performing the updates, which means unbearable bandwidth and computation costs. This is why Fortress is just a static scheme that cannot support efficient dynamic updates.


### 2.2. Dynamic OPOR (DOPOR) Architecture

The representative DOPOR architecture is presented in Figure1. Based on the bitcoin source that controls the random sampling of periodic challenges, once TPA accepts the migrated auditing tasks from the client, TPA must generate the corresponding logs after he completes each specified POR audit against CSS. In this case, the client is able to check TPA’s work at any point in time by verifying TPA’s logs, and then she can judge that if TPA did his auditing work correctly in the past. As shown in [12], such client’s checking against TPA can be much less frequent than the TPA’s POR audits against CSS, since the client can batch-check a number of accumulated TPA logs all at once.Figure 1
Dynamic OPOR (DOPOR) architecture.To support dynamic updates, we apply a similar idea to [14] within our solution, which is to place all accumulated update operations into an erasure-coded buffer at CSS side, rather than immediately executing these update operations upon the outsourced encoded data. As shown in Figure 1, the CSS-side storage is organized in two different buffers denoted with U (i.e., unencoded buffer) and E (i.e., erasure-coded buffer). Buffer U will independently store an up-to-date copy of all the raw data blocks, which are organized by our proposed bv23Tree, to support the efficient batch reads from cloud storage without struggling with the erasure code. On the other side, buffer E is further divided into two parts, ED and EO, which store the whole outsourced original encoded data blocks and all the accumulated encoded update operations, respectively. In case of data loss, client can recover the up-to-date copy of the whole outsourced raw data by decoding the entire buffer E and combining both of ED and EO, so the periodic POR audits only need to be performed upon buffer E for the retrievability guarantee.As will be described in Section4.1, both ED and EO constitute a complete hierarchical storage structure where all levels have the same size, which are different from the levels of exponentially growing capacity in [14]. After the client performs a batch of update operations upon buffer U, benefitting from the same-sized levels of DOPOR, this batch of update operations can be wholly encoded and then directly placed into EO to fill up the corresponding level for improved computation cost, without executing the rebuilding of a level as in [14] that incurs O(log⁡n) amortized cost for each update operation. More importantly, based on the same-sized levels, our DOPOR solution can build upon the public verification POR scheme of [8], the aggregation technique of which provides the support for the client’s checking against malicious TPA.Finally, after everyn update operations, when the size of EO grows to the same size as ED, buffer E will be rebuilt. The rebuilding of E will rewrite the whole ED with the encoded version of all the up-to-date raw data blocks and meanwhile empty the whole EO. Since E is only rebuilt once in every n update operations, the amortized complexity of rebuilding E will be O(1) per update operation. However, different from the existing schemes [14, 18, 19] that require O(n) client-side temporary memory for such rebuilding, as shown in Section 4.3, based on the ability of batch reads and the same-sized levels, the client of DOPOR only requires O(λ) client-side memory to gradually rebuild E, where λ is the security parameter that is independent of the data size n. So, DOPOR further reduces the required client’s memory when rebuilding and thus is suitable for the client-side mobile devices.


### 2.3. System Model

Formally, the complete definition of DOPOR system can be described by the following ten protocols:(i)
GenKey(1k)→skE,pkE: when inputting the security parameter k, this protocol outputs a pair of public-private keys for each entity E∈{client,CSS,TPA}.(ii)
GenTags(skclient,F)→B,Φ: when inputting the client’s secret key skclient and the original file F that is an ordered set of raw data blocks mi, this protocol encodes F into the encoded file B and outputs B as an ordered set of codeword blocks bi. It also outputs the tags set Φ=σi, where each σi is computed based on skclient and bi.(iii)
OutsourceData(F,B,Φ)→Ψ,P: when inputting the original file F, the encoded file B, and tags Φ, it outputs the bv23Tree Ψ that is constructed based on F. After outsourcing all the input data and Ψ to CSS, this protocol also outputs the public parameters set P for POR audits.(iv)
ReadBlocksxroot,Π,st → M,false: when inputting the root hash xroot of the bv23Tree, the set of any k blocks indices Π=a1,a2,…,ak, and the CSS state st, this protocol outputs the appointed data blocks set M=ma1,ma2,…,mak, or false otherwise.(v)
PerformUpdatesxroot,SO,skclient,st,sp→xroot∗,st∗,sp∗,false: when inputting the tree root hash xroot, the set of update operations SO, client’s secret key skclient, the CSS state st, and the state pointer sp that is related to st, it outputs a new root hash xroot∗, a new CSS state st∗, and a new pointer sp∗ showing that all the operations in SO are correctly executed in a batch, or false otherwise.(vi)
Rebuildxroot,skclient,st,sp→st∗,sp∗,false: when inputting the tree root hash xroot, client’s secret key skclient, CSS state st, and state pointer sp, it outputs a new CSS state st∗ and a new pointer sp∗ showing that the rebuilding is completed, or false otherwise.(vii)
RandomChalB,t,P→Qt: when inputting the bitcoin source B, the time t, and the public parameters P, it outputs a bitcoin-based challenge Qt for POR audit.(viii)
GenProofQt,st→ρ(t): when inputting the challenge Qt and the CSS state st, it outputs CSS’s proof ρ(t) to enable TPA to perform a POR audit.(ix)
PORAudit(P,Qt,ρt)→Λ(t),DTPA: when inputting public parameters set P, challenge Qt, and CSS’s proof ρ(t), it outputs TPA’s log Λ(t) and decision DTPA. DTPA is true if TPA audit passes, or false otherwise.(x)
CheckLogs(B,T,ΛT,P,skclient)→Dclient: when inputting the bitcoin source B, a point-in-time set T=t1,t2,…,tk, the corresponding TPA’s logs set ΛT=Λ(t)t∈T, the public parameters P, and client’s secret key skclient, this protocol outputs a client’s decision Dclient. DTPA is true if client’s batch-checking upon ΛT can pass, or false otherwise.


## 2.1. Problem Statement

We begin with the background of OPOR, as shown in [12]. There are three entities involved in an outsourced auditing environment: mobile client (i.e., data owner), cloud storage server (CSS), and third-party auditor (TPA). Because of their limited local storage capacity, mobile clients are motivated to outsource their large data files to CSS and then can make use of various on-demand cloud storage services. However, because CSS might be misbehaving, it is very important to design the periodic remote data auditing mechanism against CSS, which enables the mobile client to have the assurance that her outsourced data is always available and can be completely retrieved from CSS if necessary. Further, to liberate the mobile client from struggling with the endless online data auditing, OPOR also introduces TPA that has the expertise and ability to perform the above frequent auditing tasks on behalf of the mobile client, and then the mobile client can be offline to rest most of the time.Although OPOR model has the same three entities as existing public auditing model [9, 10, 15, 16], one of the main differences between the two is thatTPA might be also malicious within OPOR[12]. In other words, TPA might violate the auditing protocols, for example, by claiming that he has honestly performed all past auditing, but actually he tells a lie.Furthermore, any two entities might be in collusion within OPOR [12]. For example, firstly, malicious CSS might collude with malicious TPA to deceive the honest client when outsourced data has been lost. Secondly, malicious client might collude with malicious CSS to frame the honest TPA, by asserting that TPA did not correctly perform the required auditing work to bring TPA into the compensation lawsuit. Since any entity might be malicious, in order to solve the problem of securely sampling the periodic challenges for frequent auditing, the time-based bitcoin pseudorandom source is introduced into the OPOR model. As demonstrated in [12], due to the fact that the bitcoin pseudorandom source cannot be manipulated by any entity, it is secure to be used for generating the continuous random seeds for periodic challenges.OPOR inherits the retrievability guarantee of POR [8] by applying erasure code, meaning that the client can retrieve the whole outsourced data in case of minor data corruption. However, when both of the data dynamics and erasure code are considered, the problem of how to efficiently perform the updates is intractable. Within the first OPOR scheme Fortress [12], client’s original data file (including n raw data blocks) is entirely encoded before outsourcing, so an update operation upon any single raw data block will affect the whole outsourced encoded data. In this case, the only way for client is to download and decode the whole outsourced encoded data and then encode and upload all the data again after performing the updates, which means unbearable bandwidth and computation costs. This is why Fortress is just a static scheme that cannot support efficient dynamic updates.


## 2.2. Dynamic OPOR (DOPOR) Architecture

The representative DOPOR architecture is presented in Figure1. Based on the bitcoin source that controls the random sampling of periodic challenges, once TPA accepts the migrated auditing tasks from the client, TPA must generate the corresponding logs after he completes each specified POR audit against CSS. In this case, the client is able to check TPA’s work at any point in time by verifying TPA’s logs, and then she can judge that if TPA did his auditing work correctly in the past. As shown in [12], such client’s checking against TPA can be much less frequent than the TPA’s POR audits against CSS, since the client can batch-check a number of accumulated TPA logs all at once.Figure 1
Dynamic OPOR (DOPOR) architecture.To support dynamic updates, we apply a similar idea to [14] within our solution, which is to place all accumulated update operations into an erasure-coded buffer at CSS side, rather than immediately executing these update operations upon the outsourced encoded data. As shown in Figure 1, the CSS-side storage is organized in two different buffers denoted with U (i.e., unencoded buffer) and E (i.e., erasure-coded buffer). Buffer U will independently store an up-to-date copy of all the raw data blocks, which are organized by our proposed bv23Tree, to support the efficient batch reads from cloud storage without struggling with the erasure code. On the other side, buffer E is further divided into two parts, ED and EO, which store the whole outsourced original encoded data blocks and all the accumulated encoded update operations, respectively. In case of data loss, client can recover the up-to-date copy of the whole outsourced raw data by decoding the entire buffer E and combining both of ED and EO, so the periodic POR audits only need to be performed upon buffer E for the retrievability guarantee.As will be described in Section4.1, both ED and EO constitute a complete hierarchical storage structure where all levels have the same size, which are different from the levels of exponentially growing capacity in [14]. After the client performs a batch of update operations upon buffer U, benefitting from the same-sized levels of DOPOR, this batch of update operations can be wholly encoded and then directly placed into EO to fill up the corresponding level for improved computation cost, without executing the rebuilding of a level as in [14] that incurs O(log⁡n) amortized cost for each update operation. More importantly, based on the same-sized levels, our DOPOR solution can build upon the public verification POR scheme of [8], the aggregation technique of which provides the support for the client’s checking against malicious TPA.Finally, after everyn update operations, when the size of EO grows to the same size as ED, buffer E will be rebuilt. The rebuilding of E will rewrite the whole ED with the encoded version of all the up-to-date raw data blocks and meanwhile empty the whole EO. Since E is only rebuilt once in every n update operations, the amortized complexity of rebuilding E will be O(1) per update operation. However, different from the existing schemes [14, 18, 19] that require O(n) client-side temporary memory for such rebuilding, as shown in Section 4.3, based on the ability of batch reads and the same-sized levels, the client of DOPOR only requires O(λ) client-side memory to gradually rebuild E, where λ is the security parameter that is independent of the data size n. So, DOPOR further reduces the required client’s memory when rebuilding and thus is suitable for the client-side mobile devices.


## 2.3. System Model

Formally, the complete definition of DOPOR system can be described by the following ten protocols:(i)
GenKey(1k)→skE,pkE: when inputting the security parameter k, this protocol outputs a pair of public-private keys for each entity E∈{client,CSS,TPA}.(ii)
GenTags(skclient,F)→B,Φ: when inputting the client’s secret key skclient and the original file F that is an ordered set of raw data blocks mi, this protocol encodes F into the encoded file B and outputs B as an ordered set of codeword blocks bi. It also outputs the tags set Φ=σi, where each σi is computed based on skclient and bi.(iii)
OutsourceData(F,B,Φ)→Ψ,P: when inputting the original file F, the encoded file B, and tags Φ, it outputs the bv23Tree Ψ that is constructed based on F. After outsourcing all the input data and Ψ to CSS, this protocol also outputs the public parameters set P for POR audits.(iv)
ReadBlocksxroot,Π,st → M,false: when inputting the root hash xroot of the bv23Tree, the set of any k blocks indices Π=a1,a2,…,ak, and the CSS state st, this protocol outputs the appointed data blocks set M=ma1,ma2,…,mak, or false otherwise.(v)
PerformUpdatesxroot,SO,skclient,st,sp→xroot∗,st∗,sp∗,false: when inputting the tree root hash xroot, the set of update operations SO, client’s secret key skclient, the CSS state st, and the state pointer sp that is related to st, it outputs a new root hash xroot∗, a new CSS state st∗, and a new pointer sp∗ showing that all the operations in SO are correctly executed in a batch, or false otherwise.(vi)
Rebuildxroot,skclient,st,sp→st∗,sp∗,false: when inputting the tree root hash xroot, client’s secret key skclient, CSS state st, and state pointer sp, it outputs a new CSS state st∗ and a new pointer sp∗ showing that the rebuilding is completed, or false otherwise.(vii)
RandomChalB,t,P→Qt: when inputting the bitcoin source B, the time t, and the public parameters P, it outputs a bitcoin-based challenge Qt for POR audit.(viii)
GenProofQt,st→ρ(t): when inputting the challenge Qt and the CSS state st, it outputs CSS’s proof ρ(t) to enable TPA to perform a POR audit.(ix)
PORAudit(P,Qt,ρt)→Λ(t),DTPA: when inputting public parameters set P, challenge Qt, and CSS’s proof ρ(t), it outputs TPA’s log Λ(t) and decision DTPA. DTPA is true if TPA audit passes, or false otherwise.(x)
CheckLogs(B,T,ΛT,P,skclient)→Dclient: when inputting the bitcoin source B, a point-in-time set T=t1,t2,…,tk, the corresponding TPA’s logs set ΛT=Λ(t)t∈T, the public parameters P, and client’s secret key skclient, this protocol outputs a client’s decision Dclient. DTPA is true if client’s batch-checking upon ΛT can pass, or false otherwise.


## 3. Balanced Authenticated Data Structure

Within the rb23Tree of [6], for verifying a leaf, the client must retrieve from the adversary a corresponding proof path that consists of O(log⁡n)marks. However, the limitation of rb23Tree method is that a lot of duplicated information will exist in the proof paths of different leaves, which will waste too much communication cost when the client verifies many leaves one after another by retrieving different proof paths. To solve this problem, we propose thebatch-verifications 2-3 Tree, calledbv23Tree, for efficiency.


### 3.1. Batch-Verifications 2-3 Tree

Following the definition of 2-3 Tree [20], each nonleaf node of bv23Tree can have two or three children. Let F be an original data file consisting of n raw blocks F={m1,m2,…,mn}. With the hash function h·, the bv23Tree on fileF can be constructed by storing at each tree node v a 3-element tuple sv,rv,xv, defined as follows:(i)
sv is thestatus of node v. Let P denote the parent node of v. Let ch1,ch2,ch3 be the three left-to-right children of P, respectively. Specifically, if P only has two children, then ch3=null. So, sv is defined as(1)sv=0,ifvisch1;1,ifvisch2;2,ifch3≠null,visch3.(ii)
rv is therank value of node v, which is similar to the concept defined in existing rank-based MHT scheme [16]. Namely, rv stores the number of leaf nodes that belong to the subtree with node v as the root. If v is a leaf node, we define rv=1.(iii)
xv represents theauthentication hash value of node v. The value of rv is defined with different cases.Case 0. v=null; then (2)xv=null.Case 1. v is the ith leaf node; then(3)xv=hmi.Case 2. v is a nonleaf node with children ch1,ch2, and ch3 as above (sometimes ch3 will be null):(4)xv=hrv∥xch1∥xch2∥xch3,where ∥ denotes the concatenation operation.We show an example of bv23Tree in Figure2, which is constructed on 16 file blocks {mi}1≤i≤16. Next, we use the concise shorthand for some symbols. Given a bv23Tree node vi, we use si, ri, and xi to denote svi, rvi, and xvi, respectively, so each tree node vi and its corresponding 3-element tuple si,ri,xi are not distinguished. And we also use hi to denote the hash value hmi for convenience.Figure 2
An example of bv23Tree. Besides the verified ordered leaves setL={v3,v4,v8,v10,v12,v14}, the verifier only needs to retrieve the necessary auxiliary tree nodes (colored in red), which are organized into a special table structure as will be shown later. Then, the verifier can batch-verify the indices and values of these leaves in L all together.


### 3.2. Batch Queries

The integrity (i.e., authenticity and freshness) of file blocks can be protected by the corresponding hash valueshi1≤i≤n stored in leaves, while the integrity of the leaves themselves will be protected by bv23Tree. Now, suppose that the whole file blocks m1,m2,…,mn and a bv23Tree on all blocks have been stored at CSS. Client wants to verify the integrity of any k ordered file blocks ma1,ma2,…,mak1≤a1<a2<⋯<ak≤n read from CSS and thus batch-queries CSS by issuing the ordered indices set Π=a1,a2,…,ak that appoints k ordered leaves va1,va2,…,vak. Then, CSS calls Algorithm 1 to generate the correspondingproof table and responds to client with the k appointed leaves and their proof table.Algorithm 1:Algorithm for generating proof table Tk×l.
Proof_Table Ψ , Π → T k × l. With the bv23Tree Ψ of l levels, and the k ordered indices set Π=a1,a2,…,ak that appoint k ordered leavesva1,va2,…,vak, this algorithm generates the corresponding proof table Tk×l. (1)initialize node array A1⋯k by A[i]←vaii=1,2,…,k; (2)A[i] tracks the parent of the current node v as below (3)j←1; j tracks the column of the proof table Tk×l (4)whilej≤ldo (5)fori=1,2,…,kdo (6)ifAi=nullthen (7)Ti,j←null; (8)elseAi≠null (9)letv denote the current tree node stored in Ai (10)if  node v only has one sibling node, which is denoted by svthen (11)ifsv exists in Aθ, in this casei<θ≤kthen (12)Ti,j←θ; Aθ←null; (13)elsesv does not exist in current array A[] (14)Ti,j←sv; (15)end if (16)elsenodev has two sibling nodes, which are denoted by (sv1,sv2) (17)note that the sequence of (sv1,sv2) must follow the left-to-right principle as in Figure 2, e.g., two siblings of node v8 must be denoted by (v7,v9) (18)if  only sv1 (or sv2) exists in Aθthen (19)Ti,j←θ,sv2 (or Ti,j←sv1,θ); (20)Aθ←null; (21)else ifboth sv1 and sv2 exist in Aθ1 and Aθ2, respectively, then (22)Ti,j←θ1,θ2; Aθ1←null; Aθ2←null; (23)else both sv1 and sv2 do not exist in current array A (24)Ti,j←sv1,sv2; (25)end if (26)end if (27)Ai← the parent node of the current node v; (28)end if (29)end for (30)j←j+1; (31)end while (32)returnthe proof table Tk×l;An example of proof table is shown in Table1. Without loss of generality, suppose the number of the levels of a bv23Tree is l. Due to the property of balanced tree, the number l must be O(log⁡n) complexity. Let Tk×l denote the proof table of any k appointed leaves; then Tk×l has the following characteristics:(i)
Tk×l contains k rows and l columns, respectively (i.e., Tk×l consists of k×l items).(ii)
Each itemTi,j(1≤i≤k,1≤j≤l) can have one or two components, and each component can be a tree node vi or a mark θ2≤θ≤k or null. Since θ only denotes a pointer that points to the θth row of the table Tk×l itself, the communication cost of a mark θ is little when compared to the cost of a node vi.(iii)
The more the leaves are batch-verified, the more thenull that exists in Tk×l. And no matter how many leaves are batch-verified, each necessary auxiliary tree node vi only appears once in Tk×l.Table 1
An example of proof table.
Table itemTi,j j = 1 j = 2 j = 3 i = 1   row 1 2 v 17 ( 3 ,  4 ) i = 2   row 2 Null Null Null i = 3   row 3 ( v 7 , v 9 ) v 19 Null i = 4   row 4 v 11 ( 5 , v 23 ) Null i = 5   row 5 ( v 13 , 6 ) Null Null i = 6   row 6 Null Null Null The corresponding proof tableT6×3 is generated based on the bv23Tree and the appointed ordered leaves set L={v3,v4,v8,v10,v12,v14} of Figure 2.In the context of the batch verifications uponk appointed leaves, compared to the proof path method as in [6], the communication cost of the proof table Tk×l is much less than that of transferring different proof paths of k leaves, respectively. This is because the proof table avoids the limitation of proof paths that the repetitive node information (e.g., node hash values) will exhibit in the proof paths of different leaves with high probability, so there is a plenty of null in the proof table to save the communication cost. Furthermore, compared to the 8-element tuplemarkin proof path of [6], each tree node vi included in the proof table is only related to a 3-element tuple, which further reduces the communication cost.


### 3.3. Batch Verifications

Upon receiving from CSS thek appointed leaves set L=va1,va2,…,vak and the required proof table Tk×l, client can run Algorithm 2 to batch-verify the indices and values of these k leaves in L all at once, by using her local metadata xroot. An example of batch verifications upon multiple leaves is shown in Table 2.Table 2
An example of batch verifications.
Variables Initialization j = 1 j = 2 j = 3 H 1 x 3 x 18 x 24 x root I S 1 1 1 ,  2 3 ,  4 3 ,  4 ,  8 ,  10 ,  12 ,  14  H 2 x 4 I S 2 1 2  H 3 x 8 x 20 x 25 I S 3 1 2 4 8 ,  10 ,  12 ,  14  H 4 x 10 x 21 x 26 I S 4 1 1 1 ,  3 ,  5 6 ,  8 ,  10  H 5 x 12 x 22 I S 5 1 1 ,  3 3 ,  5  H 6 x 14 I S 6 1 3 The process of batch verifications upon the appointed ordered leaves setL={v3,v4,v8,v10,v12,v14} of Figure 2, according to Algorithm 2 and the proof table T6×3 of Table 1.Algorithm 2:Algorithm for batch-verifying all appointed leaves in L.
Batch_Verifyxroot,Π,L,Tk×l→true,false. This algorithm can batch-verify not only the hash values of allk ordered leaves L=va1,va2,…,vak provided by CSS, but also that the indices of thesek leaves are exactly matched with the appointed indices set Π=a1,a2,…,ak. (1)foreach leaf vai≔sai,rai,xai, i=1,2,…,k, do (2)initialize Ri←rai; Hi←xai; ISi←1; (3)end for (4)initialize Row_Set←1,2,…,k; (5)forj=1,2,…,l  do (6)for  each i in Row_Set  do (7)if item Ti,j only has one component Cthen (8)callDeal_One_ComponentC; (9)else  Ti,j  has  two  components  C1,C2 (10)callDeal_Two_ComponentsC1,C2; (11)end if (12)end for (13)end for (14)ifH1=xroot and IS1=a1,a2,…,ak  then (15)return  true; (16)else (17)return  false; (18)end if Function  Deal_One_Component  C (1)if  C  is  null  then (2)continue; (3)else ifC is a node vt≔st,rt,xt  then (4)Ri←Ri+rt; (5)if  st=0  then (6)ISi←ISi⊕rt; (7)Hi←hRi∥xt∥Hi; (8)else  st=1 (9)Hi←hRi∥Hi∥xt; (10)end if (11)elseCisamarkθ (12)ISθ←ISθ⊕Ri; (13)Ri←Ri+Rθ; (14)Hi←hRi∥Hi∥Hθ; (15)ISi←AppendISi,ISθ; (16)delete  θ from the  Row_Set; (17)end if Function  Deal_Two_ComponentsC1,C2 (1)ifC1 and C2 are two nodes vt and vτ, respectively, then (2)note that vt≔st,rt,xt, vτ≔sτ,rτ,xτ (3)assign  S←S∈0,1,2 and  S∉st,sτ; (4)Ri←Ri+rt+rτ; (5)if  S=0  then (6)Hi←hRi∥Hi∥xt∥xτ; (7)else if  S=1  then (8)ISi←ISi⊕rt; Hi←hRi∥xt∥Hi∥xτ; (9)elseS=2 (10)ISi←ISi⊕rt+rτ; Hi←hRi∥xt∥xτ∥Hi; (11)end if (12)else ifC1 is a node vt, and C2 is a mark θ, then (13)in terms of the left-to-right principle, the value of st can only be 0 or 1 in this case (14)if  st=0  then (15)ISθ←ISθ⊕Ri; (16)ISi←AppendISi,ISθ; (17)ISi←ISi⊕rt; (18)Ri←Ri+rt+Rθ; (19)Hi←hRi∥xt∥Hi∥Hθ; (20)elsest=1 (21)ISθ←ISθ⊕Ri+rt; (22)ISi←AppendISi,ISθ; (23)Ri←Ri+rt+Rθ; (24)Hi←hRi∥Hi∥xt∥Hθ (25)end if (26)delete θ from the  Row_Set; (27)else ifC1 is a mark θ, and C2 is a node vt, then (28)ISθ←ISθ⊕Ri; (29)ISi←AppendISi,ISθ; (30)Ri←Ri+Rθ+rt; (31)Hi←hRi∥Hi∥Hθ∥xt; (32)delete θ from the  Row_Set; (33)elseC1 and C2 are two marks θ1 and θ2, respectively (34)ISθ2←ISθ2⊕Rθ1; (35)ISθ1←AppendISθ1,ISθ2 (36)ISθ1←ISθ1⊕Ri; (37)ISi←AppendISi,ISθ1; (38)Ri←Ri+Rθ1+Rθ2; (39)Hi←hRi∥Hi∥Hθ1∥Hθ2; (40)delete  θ1 and θ2 from the  Row_Set; (41)end ifWithin Algorithm2, the function Append· is to merge two different sets of numbers while preserving the order of these numbers. For example, given two sets IS1=4 and IS2=6,8,10, then AppendIS1,IS2=4,6,8,10. In addition, the operator notation “⊕” is to add a number to every element of a set. For example, let IS3=4,6,8,10; then IS3⊕4=8,10,12,14. Algorithm 2 applies each nonnull item Ti,j of Tk×l to iteratively compute tuple Ri,Hi,ISi. If the returned leaves set L and table Tk×l are right, we will get the following results after the outermost for-loop of Algorithm 2 is finished:(i)
ValueH1 is equal to xroot, that is, the authentication hash value of the root of bv23Tree.(ii)
ValueIS1 is exactly the same as a1,a2,…,ak, that is, the indices set of k appointed ordered leaves in L.At a high level, Algorithm2 is also the way to gradually construct thepartial bv23Tree, which precisely covers all appointed leaves in L, the paths from these appointed leaves to the root, and all the siblings of the nodes on these paths. Based on this partial bv23Tree, the batch updates upon outsourced original raw blocks {m1,m2,…,mn} can be supported, as shown in Algorithms 3 and 4.Algorithm 3:Algorithm for CSS to perform the batch updates.
Batch_Updates S O , Ψ , F → L  , T k × l  ,  x r o o t ∗. Input parameters SO=O1,O2,…,Oc are a batch of update operations, Ψ is the bv23Tree, andF={m1,m2,…,mn} are the whole outsourced original blocks. This algorithm outputs an ordered leaves setL, the proof table Tk×l, and the updated root hash value xroot∗ from the final state bv23Tree Ψ∗. (1)extract from SO the largest ordered targeted indices set Π=a1,a2,…,ak, by removing the duplicate indices; (2)read leaves set L=va1,va2,…,vakfrom Ψ; (3)obtain Tk×l ← Proof_TableΨ,Π; (4)update the file blocks set F according to the sequential executions of all update operations O1,O2,…,Oc; (5)perform each of the update operations in sequence on Ψ and then obtain the final state Ψ∗; more specifically, transform Ψ in terms of each operation, and update the status sv, rank rv, and hash value xv of the affected tree nodes during each transformation; (for the modification operation without transformation, only need to update the hash values of the nodes on the path from the targeted leaf to the root) (6)returnL,Tk×l,xroot∗, where xroot∗ is the authentication hash value of the root of final state Ψ∗;Algorithm 4:Algorithm for client to verify the result of batch updates.
Verify_Updates x root , S O , L , T k × l , x root ∗ → true , false. Input parameters xroot is client local metadata, update operations setSO=O1,O2,…,Oc are generated by client herself, L, Tk×l, xroot∗ are provided by CSS as computed in Algorithm3. This algorithm outputs true if the batch updates are successful, or false otherwise. (1)extract Π=a1,a2,…,ak from SO as in Algorithm 3; (2)if  Batch_Verifyxroot,Π,L,Tk×l=truethen (3)construct partial bv23Tree with xroot as the root hash; (4)elseBatch_Verifyxroot,Π,L,Tk×l=false (5)return  false; (6)end if (7)perform each update operation Oi of  SO upon above partial bv23Tree by the same transformations as in Algorithm 3, and then compute the final state root hash xroot′; (8)ifxroot′=xroot∗  then (9)replace local xroot with xroot∗, return  true; (10)elsexroot′≠xroot∗ (11)return  false; (12)end if


### 3.4. Batch Updates

Three basic types of dynamic update operations are modification (M), insertion (I), and deletion (D) [9]. Any block-level update operation O can be defined by the form of O≔“Uam”, where U∈M,I,D denotes operation type, a is the index of targeted block, and m is the new data block that will be exactly stored according to the targeted index a (m is null for deletion). For example, “M2m” is to modify the 2nd block to m, “I3m” is to insert m after the 3rd block, and “D4null” is to delete the 4th block.In the setting of dynamism, the update operations should be performed not only on the data blocks, but also on the bv23Tree. Note that only the insertion and deletion can cause the structure transformation of bv23Tree, and the maintenance of this transformation is essentially identical to the maintenance of a standard 2-3 tree [20], except that the updating of each affected tree node v should be considered in terms of the 3-element tuple sv,rv,xv. As in Figure 3, we give an example for the structure transformation of bv23Tree after repetitively inserting (or deleting) the appointed data blocks at the same index position.Figure 3
From(1) to (4) is the structure transformation of bv23Tree after performing three insertion operations I3m1∗,I3m2∗,I3m3∗ in order. And the reverse transformation from (4) to (1) is based on the sequential executions of three identical deletion operations.Now, suppose that client caches a batch of ordered update operationsSO≔O1,O2,…,Oc, which refer to an ordered indices set Π=a1,a2,…,ak, k≤c, by the removal of duplicate indices. To batch-update the remote data, client first issues SO to CSS and obtains the returned ordered leaves set L=va1,va2,…,vak along with the proof table Tk×l. As shown in Section 3.3, during the process of executing Algorithm 2 to batch-verify L, client can construct the corresponding partial bv23Tree. Then, after sequentially performing each operation of SO upon the partial bv23Tree, client can compute by herself what would be the authentication hash value of the final state tree root. Finally, if CSS outputs the same final state root hash value as the one computed by client herself, client outputs true, meaning that CSS correctly performs the batch updates according to SO. Otherwise, client outputs false. As shown in Algorithms 3 and 4, we outline theBatch_Updates algorithm performed by CSS and theVerify_Updates algorithm performed by client, respectively.


## 3.1. Batch-Verifications 2-3 Tree

Following the definition of 2-3 Tree [20], each nonleaf node of bv23Tree can have two or three children. Let F be an original data file consisting of n raw blocks F={m1,m2,…,mn}. With the hash function h·, the bv23Tree on fileF can be constructed by storing at each tree node v a 3-element tuple sv,rv,xv, defined as follows:(i)
sv is thestatus of node v. Let P denote the parent node of v. Let ch1,ch2,ch3 be the three left-to-right children of P, respectively. Specifically, if P only has two children, then ch3=null. So, sv is defined as(1)sv=0,ifvisch1;1,ifvisch2;2,ifch3≠null,visch3.(ii)
rv is therank value of node v, which is similar to the concept defined in existing rank-based MHT scheme [16]. Namely, rv stores the number of leaf nodes that belong to the subtree with node v as the root. If v is a leaf node, we define rv=1.(iii)
xv represents theauthentication hash value of node v. The value of rv is defined with different cases.Case 0. v=null; then (2)xv=null.Case 1. v is the ith leaf node; then(3)xv=hmi.Case 2. v is a nonleaf node with children ch1,ch2, and ch3 as above (sometimes ch3 will be null):(4)xv=hrv∥xch1∥xch2∥xch3,where ∥ denotes the concatenation operation.We show an example of bv23Tree in Figure2, which is constructed on 16 file blocks {mi}1≤i≤16. Next, we use the concise shorthand for some symbols. Given a bv23Tree node vi, we use si, ri, and xi to denote svi, rvi, and xvi, respectively, so each tree node vi and its corresponding 3-element tuple si,ri,xi are not distinguished. And we also use hi to denote the hash value hmi for convenience.Figure 2
An example of bv23Tree. Besides the verified ordered leaves setL={v3,v4,v8,v10,v12,v14}, the verifier only needs to retrieve the necessary auxiliary tree nodes (colored in red), which are organized into a special table structure as will be shown later. Then, the verifier can batch-verify the indices and values of these leaves in L all together.


## 3.2. Batch Queries

The integrity (i.e., authenticity and freshness) of file blocks can be protected by the corresponding hash valueshi1≤i≤n stored in leaves, while the integrity of the leaves themselves will be protected by bv23Tree. Now, suppose that the whole file blocks m1,m2,…,mn and a bv23Tree on all blocks have been stored at CSS. Client wants to verify the integrity of any k ordered file blocks ma1,ma2,…,mak1≤a1<a2<⋯<ak≤n read from CSS and thus batch-queries CSS by issuing the ordered indices set Π=a1,a2,…,ak that appoints k ordered leaves va1,va2,…,vak. Then, CSS calls Algorithm 1 to generate the correspondingproof table and responds to client with the k appointed leaves and their proof table.Algorithm 1:Algorithm for generating proof table Tk×l.
Proof_Table Ψ , Π → T k × l. With the bv23Tree Ψ of l levels, and the k ordered indices set Π=a1,a2,…,ak that appoint k ordered leavesva1,va2,…,vak, this algorithm generates the corresponding proof table Tk×l. (1)initialize node array A1⋯k by A[i]←vaii=1,2,…,k; (2)A[i] tracks the parent of the current node v as below (3)j←1; j tracks the column of the proof table Tk×l (4)whilej≤ldo (5)fori=1,2,…,kdo (6)ifAi=nullthen (7)Ti,j←null; (8)elseAi≠null (9)letv denote the current tree node stored in Ai (10)if  node v only has one sibling node, which is denoted by svthen (11)ifsv exists in Aθ, in this casei<θ≤kthen (12)Ti,j←θ; Aθ←null; (13)elsesv does not exist in current array A[] (14)Ti,j←sv; (15)end if (16)elsenodev has two sibling nodes, which are denoted by (sv1,sv2) (17)note that the sequence of (sv1,sv2) must follow the left-to-right principle as in Figure 2, e.g., two siblings of node v8 must be denoted by (v7,v9) (18)if  only sv1 (or sv2) exists in Aθthen (19)Ti,j←θ,sv2 (or Ti,j←sv1,θ); (20)Aθ←null; (21)else ifboth sv1 and sv2 exist in Aθ1 and Aθ2, respectively, then (22)Ti,j←θ1,θ2; Aθ1←null; Aθ2←null; (23)else both sv1 and sv2 do not exist in current array A (24)Ti,j←sv1,sv2; (25)end if (26)end if (27)Ai← the parent node of the current node v; (28)end if (29)end for (30)j←j+1; (31)end while (32)returnthe proof table Tk×l;An example of proof table is shown in Table1. Without loss of generality, suppose the number of the levels of a bv23Tree is l. Due to the property of balanced tree, the number l must be O(log⁡n) complexity. Let Tk×l denote the proof table of any k appointed leaves; then Tk×l has the following characteristics:(i)
Tk×l contains k rows and l columns, respectively (i.e., Tk×l consists of k×l items).(ii)
Each itemTi,j(1≤i≤k,1≤j≤l) can have one or two components, and each component can be a tree node vi or a mark θ2≤θ≤k or null. Since θ only denotes a pointer that points to the θth row of the table Tk×l itself, the communication cost of a mark θ is little when compared to the cost of a node vi.(iii)
The more the leaves are batch-verified, the more thenull that exists in Tk×l. And no matter how many leaves are batch-verified, each necessary auxiliary tree node vi only appears once in Tk×l.Table 1
An example of proof table.
Table itemTi,j j = 1 j = 2 j = 3 i = 1   row 1 2 v 17 ( 3 ,  4 ) i = 2   row 2 Null Null Null i = 3   row 3 ( v 7 , v 9 ) v 19 Null i = 4   row 4 v 11 ( 5 , v 23 ) Null i = 5   row 5 ( v 13 , 6 ) Null Null i = 6   row 6 Null Null Null The corresponding proof tableT6×3 is generated based on the bv23Tree and the appointed ordered leaves set L={v3,v4,v8,v10,v12,v14} of Figure 2.In the context of the batch verifications uponk appointed leaves, compared to the proof path method as in [6], the communication cost of the proof table Tk×l is much less than that of transferring different proof paths of k leaves, respectively. This is because the proof table avoids the limitation of proof paths that the repetitive node information (e.g., node hash values) will exhibit in the proof paths of different leaves with high probability, so there is a plenty of null in the proof table to save the communication cost. Furthermore, compared to the 8-element tuplemarkin proof path of [6], each tree node vi included in the proof table is only related to a 3-element tuple, which further reduces the communication cost.


## 3.3. Batch Verifications

Upon receiving from CSS thek appointed leaves set L=va1,va2,…,vak and the required proof table Tk×l, client can run Algorithm 2 to batch-verify the indices and values of these k leaves in L all at once, by using her local metadata xroot. An example of batch verifications upon multiple leaves is shown in Table 2.Table 2
An example of batch verifications.
Variables Initialization j = 1 j = 2 j = 3 H 1 x 3 x 18 x 24 x root I S 1 1 1 ,  2 3 ,  4 3 ,  4 ,  8 ,  10 ,  12 ,  14  H 2 x 4 I S 2 1 2  H 3 x 8 x 20 x 25 I S 3 1 2 4 8 ,  10 ,  12 ,  14  H 4 x 10 x 21 x 26 I S 4 1 1 1 ,  3 ,  5 6 ,  8 ,  10  H 5 x 12 x 22 I S 5 1 1 ,  3 3 ,  5  H 6 x 14 I S 6 1 3 The process of batch verifications upon the appointed ordered leaves setL={v3,v4,v8,v10,v12,v14} of Figure 2, according to Algorithm 2 and the proof table T6×3 of Table 1.Algorithm 2:Algorithm for batch-verifying all appointed leaves in L.
Batch_Verifyxroot,Π,L,Tk×l→true,false. This algorithm can batch-verify not only the hash values of allk ordered leaves L=va1,va2,…,vak provided by CSS, but also that the indices of thesek leaves are exactly matched with the appointed indices set Π=a1,a2,…,ak. (1)foreach leaf vai≔sai,rai,xai, i=1,2,…,k, do (2)initialize Ri←rai; Hi←xai; ISi←1; (3)end for (4)initialize Row_Set←1,2,…,k; (5)forj=1,2,…,l  do (6)for  each i in Row_Set  do (7)if item Ti,j only has one component Cthen (8)callDeal_One_ComponentC; (9)else  Ti,j  has  two  components  C1,C2 (10)callDeal_Two_ComponentsC1,C2; (11)end if (12)end for (13)end for (14)ifH1=xroot and IS1=a1,a2,…,ak  then (15)return  true; (16)else (17)return  false; (18)end if Function  Deal_One_Component  C (1)if  C  is  null  then (2)continue; (3)else ifC is a node vt≔st,rt,xt  then (4)Ri←Ri+rt; (5)if  st=0  then (6)ISi←ISi⊕rt; (7)Hi←hRi∥xt∥Hi; (8)else  st=1 (9)Hi←hRi∥Hi∥xt; (10)end if (11)elseCisamarkθ (12)ISθ←ISθ⊕Ri; (13)Ri←Ri+Rθ; (14)Hi←hRi∥Hi∥Hθ; (15)ISi←AppendISi,ISθ; (16)delete  θ from the  Row_Set; (17)end if Function  Deal_Two_ComponentsC1,C2 (1)ifC1 and C2 are two nodes vt and vτ, respectively, then (2)note that vt≔st,rt,xt, vτ≔sτ,rτ,xτ (3)assign  S←S∈0,1,2 and  S∉st,sτ; (4)Ri←Ri+rt+rτ; (5)if  S=0  then (6)Hi←hRi∥Hi∥xt∥xτ; (7)else if  S=1  then (8)ISi←ISi⊕rt; Hi←hRi∥xt∥Hi∥xτ; (9)elseS=2 (10)ISi←ISi⊕rt+rτ; Hi←hRi∥xt∥xτ∥Hi; (11)end if (12)else ifC1 is a node vt, and C2 is a mark θ, then (13)in terms of the left-to-right principle, the value of st can only be 0 or 1 in this case (14)if  st=0  then (15)ISθ←ISθ⊕Ri; (16)ISi←AppendISi,ISθ; (17)ISi←ISi⊕rt; (18)Ri←Ri+rt+Rθ; (19)Hi←hRi∥xt∥Hi∥Hθ; (20)elsest=1 (21)ISθ←ISθ⊕Ri+rt; (22)ISi←AppendISi,ISθ; (23)Ri←Ri+rt+Rθ; (24)Hi←hRi∥Hi∥xt∥Hθ (25)end if (26)delete θ from the  Row_Set; (27)else ifC1 is a mark θ, and C2 is a node vt, then (28)ISθ←ISθ⊕Ri; (29)ISi←AppendISi,ISθ; (30)Ri←Ri+Rθ+rt; (31)Hi←hRi∥Hi∥Hθ∥xt; (32)delete θ from the  Row_Set; (33)elseC1 and C2 are two marks θ1 and θ2, respectively (34)ISθ2←ISθ2⊕Rθ1; (35)ISθ1←AppendISθ1,ISθ2 (36)ISθ1←ISθ1⊕Ri; (37)ISi←AppendISi,ISθ1; (38)Ri←Ri+Rθ1+Rθ2; (39)Hi←hRi∥Hi∥Hθ1∥Hθ2; (40)delete  θ1 and θ2 from the  Row_Set; (41)end ifWithin Algorithm2, the function Append· is to merge two different sets of numbers while preserving the order of these numbers. For example, given two sets IS1=4 and IS2=6,8,10, then AppendIS1,IS2=4,6,8,10. In addition, the operator notation “⊕” is to add a number to every element of a set. For example, let IS3=4,6,8,10; then IS3⊕4=8,10,12,14. Algorithm 2 applies each nonnull item Ti,j of Tk×l to iteratively compute tuple Ri,Hi,ISi. If the returned leaves set L and table Tk×l are right, we will get the following results after the outermost for-loop of Algorithm 2 is finished:(i)
ValueH1 is equal to xroot, that is, the authentication hash value of the root of bv23Tree.(ii)
ValueIS1 is exactly the same as a1,a2,…,ak, that is, the indices set of k appointed ordered leaves in L.At a high level, Algorithm2 is also the way to gradually construct thepartial bv23Tree, which precisely covers all appointed leaves in L, the paths from these appointed leaves to the root, and all the siblings of the nodes on these paths. Based on this partial bv23Tree, the batch updates upon outsourced original raw blocks {m1,m2,…,mn} can be supported, as shown in Algorithms 3 and 4.Algorithm 3:Algorithm for CSS to perform the batch updates.
Batch_Updates S O , Ψ , F → L  , T k × l  ,  x r o o t ∗. Input parameters SO=O1,O2,…,Oc are a batch of update operations, Ψ is the bv23Tree, andF={m1,m2,…,mn} are the whole outsourced original blocks. This algorithm outputs an ordered leaves setL, the proof table Tk×l, and the updated root hash value xroot∗ from the final state bv23Tree Ψ∗. (1)extract from SO the largest ordered targeted indices set Π=a1,a2,…,ak, by removing the duplicate indices; (2)read leaves set L=va1,va2,…,vakfrom Ψ; (3)obtain Tk×l ← Proof_TableΨ,Π; (4)update the file blocks set F according to the sequential executions of all update operations O1,O2,…,Oc; (5)perform each of the update operations in sequence on Ψ and then obtain the final state Ψ∗; more specifically, transform Ψ in terms of each operation, and update the status sv, rank rv, and hash value xv of the affected tree nodes during each transformation; (for the modification operation without transformation, only need to update the hash values of the nodes on the path from the targeted leaf to the root) (6)returnL,Tk×l,xroot∗, where xroot∗ is the authentication hash value of the root of final state Ψ∗;Algorithm 4:Algorithm for client to verify the result of batch updates.
Verify_Updates x root , S O , L , T k × l , x root ∗ → true , false. Input parameters xroot is client local metadata, update operations setSO=O1,O2,…,Oc are generated by client herself, L, Tk×l, xroot∗ are provided by CSS as computed in Algorithm3. This algorithm outputs true if the batch updates are successful, or false otherwise. (1)extract Π=a1,a2,…,ak from SO as in Algorithm 3; (2)if  Batch_Verifyxroot,Π,L,Tk×l=truethen (3)construct partial bv23Tree with xroot as the root hash; (4)elseBatch_Verifyxroot,Π,L,Tk×l=false (5)return  false; (6)end if (7)perform each update operation Oi of  SO upon above partial bv23Tree by the same transformations as in Algorithm 3, and then compute the final state root hash xroot′; (8)ifxroot′=xroot∗  then (9)replace local xroot with xroot∗, return  true; (10)elsexroot′≠xroot∗ (11)return  false; (12)end if


## 3.4. Batch Updates

Three basic types of dynamic update operations are modification (M), insertion (I), and deletion (D) [9]. Any block-level update operation O can be defined by the form of O≔“Uam”, where U∈M,I,D denotes operation type, a is the index of targeted block, and m is the new data block that will be exactly stored according to the targeted index a (m is null for deletion). For example, “M2m” is to modify the 2nd block to m, “I3m” is to insert m after the 3rd block, and “D4null” is to delete the 4th block.In the setting of dynamism, the update operations should be performed not only on the data blocks, but also on the bv23Tree. Note that only the insertion and deletion can cause the structure transformation of bv23Tree, and the maintenance of this transformation is essentially identical to the maintenance of a standard 2-3 tree [20], except that the updating of each affected tree node v should be considered in terms of the 3-element tuple sv,rv,xv. As in Figure 3, we give an example for the structure transformation of bv23Tree after repetitively inserting (or deleting) the appointed data blocks at the same index position.Figure 3
From(1) to (4) is the structure transformation of bv23Tree after performing three insertion operations I3m1∗,I3m2∗,I3m3∗ in order. And the reverse transformation from (4) to (1) is based on the sequential executions of three identical deletion operations.Now, suppose that client caches a batch of ordered update operationsSO≔O1,O2,…,Oc, which refer to an ordered indices set Π=a1,a2,…,ak, k≤c, by the removal of duplicate indices. To batch-update the remote data, client first issues SO to CSS and obtains the returned ordered leaves set L=va1,va2,…,vak along with the proof table Tk×l. As shown in Section 3.3, during the process of executing Algorithm 2 to batch-verify L, client can construct the corresponding partial bv23Tree. Then, after sequentially performing each operation of SO upon the partial bv23Tree, client can compute by herself what would be the authentication hash value of the final state tree root. Finally, if CSS outputs the same final state root hash value as the one computed by client herself, client outputs true, meaning that CSS correctly performs the batch updates according to SO. Otherwise, client outputs false. As shown in Algorithms 3 and 4, we outline theBatch_Updates algorithm performed by CSS and theVerify_Updates algorithm performed by client, respectively.


## 4. DOPOR Solution

### 4.1. Cloud Server Storage Configuration

As shown in Figure1, there are two different buffers U and E at CSS side for outsourced data storage. Client’s original file F, consisting of n raw blocks F={m1,m2,…,mn}, will be separately stored into U and E with different formats, detailed as follows.U (Unencoded Buffer). To support the efficient reads, buffer U always stores the up-to-date copy of the raw data blocks, and thus the update operations issued from client must be immediately performed upon the appointed blocks of U. All the blocks in U are organized by the bv23Tree as proposed in Section 3, the batch-verifications property of which enables client to batch-read a group of raw blocks from U for improved performance.E (Erasure-Coded Buffer). Buffer E is organized by the same-sized hierarchical structure, as in Figure 4, where each level has the same size to hold λ encoded blocks with the blocks tags (λ is the security parameter). Moreover, E is equally divided into two parts ED and EO with the same capacity. ED is to store encoded data blocks, and EO is to store encoded operations blocks. At the beginning, client applies erasure code to encode the entire file F into n~ encoded data blocks, computes the blocks tags, and sequentially stores them into ED in terms of the blocks indices as shown in Figure 4. Subsequently, the content of ED will not be changed until buffer E is rebuilt. As shown in Section 3.4, each update operation O is of the form “Uam”, which can also be regarded as an operation block. In this case, after a batch of update operations SO={O1,O2,…,Oc}c<λ are performed upon U, client will encode SO into λ encoded operations blocks and store them along with the blocks tags into a corresponding level of EO. So, EO is empty in the initial state and will be incrementally filled up level by level over time. At last, once EO is full, the rebuilding of E is triggered, as will be described later.Figure 4
CSS-side hierarchical storage structure for erasure-coded buffer E, where each level storesλ encoded blocks along with tags.At a high level, by decoding the whole E and sequentially performing the accumulated update operations of EO upon the original data blocks of ED, the latest version of the whole client’s outsourced raw data can be recovered. Therefore, the periodic POR audits only need to be deployed against the buffer E, which functions as a backup storage to provide the retrievability guarantee when data loss occurs. To resist the mentioned selective deletion attack as before, every POR audit will sample challenged blocks from each filled level of E. Because each level is entirely encoded, malicious CSS must corrupt a significant portion of the encoded blocks of one level to actually cause the data loss. However, if malicious CSS corrupts that many encoded blocks of one level, it cannot pass the POR audits with overwhelming probability.


### 4.2. Initialization

We also work in the bilinear setting, whereG is a multiplicative cyclic group of prime order p and g is a generator of G. Let e:G×G→GT be the same nondegenerate bilinear map as in [8] that has the following property: for any z,ω∈Gand a,b∈Zp, eza,ωb=e(z,ω)ab. Let H:{0,1}∗→G be the secure BLS hash function. The initialization of our scheme is described as follows.(1)
GenKey(1k): each entity E∈{client,CSS,TPA} generates a signing key pair sskE,spkE for their respective signatures. In addition, client samples a random element α←RZp and computes ω←gα. α is kept secret by client but ω is public. So, client’s private key skclient=α,sskclient and her public key pkclient=ω,spkclient.(2)
GenTags(skclient,F): client applies erasure code to encode F={mi}1≤i≤n into n~ codeword blocks B=bi1≤i≤n~, and each bi is s sectors long: bi≔{bij}1≤j≤s. Client then generates a name fid for F and samples s elements u1,…,us←RG. For each index i, 1≤i≤n~, with her secret key α in skclient, client computes for bi the corresponding tag σi←Hfid∥i·∏j=1sujbijα and attaches σi to bi.(3)
OutsourceData(F,B,Φ): based on F={m1,m2,…,mn}, client generates the corresponding bv23Tree Ψ with the root hash xroot, as shown in Section 3.1. Then, client outsources F,Ψ into the buffer U and outsources all encoded data blocks B=bi1≤i≤n~ (along with their tags Φ=σi1≤i≤n~) into the ED part of buffer E, the layout of which is shown in Figure 4. In addition, let sp be a state pointer that denotes the number of the filled levels of buffer E. Clearly, the range of sp is n~/λ≤sp≤2n~/λ, as in Figure 4. Let cl denote the number of the challenged blocks from a filled level, and let P=sp,cl,g,ω,fid,u1,…,us be the public parameters set for POR audits. Finally, client keeps P and xroot locally, sends P to TPA, and deletes F,Ψ,B,Φ from her local storage.


### 4.3. Data Access Mechanisms

Based on the bv23Tree of buffer U and the hierarchical configuration of same-sized levels of buffer E, DOPOR supports batch updates that enable the client to perform a batch of update operations upon the outsourced storage, which is suitable for the common scenario of [14] where writes are frequent. Now, after completing the initialization of DOPOR, the client can access and update her outsourced data by the following three protocols.1   R e a d B l o c k s x root , Π , s t. With her local root hash xroot of bv23Tree, the client can batch-read any k appointed raw blocks from CSS, by sending the ordered blocks indices set Π=a1,a2,…,ak as the query to CSS. Here, let buffer U be the CSS state st. In terms of Section 3, upon receiving Π, CSS accesses appointed raw blocks M=ma1,ma2,…,mak and the tree leaves L=va1,va2,…,vak from U, generates Tk×l←Proof_TableΨ,Π, and returns M,L,Tk×l to the client. Then, the client batch-verifies the authenticity of L by callingBatch_Verifyxroot,Π,L,Tk×l and finally checks the integrity of all raw blocks of M according to the corresponding hash values stored in L.2   P e r f o r m U p d a t e s x root , S O , s k client , s t , s p. Suppose that the client keeps O(λ) local storage to cache cc<λ ordered update operations SO≔O1,O2,…,Oc. Then, the client sends SO to CSS for performing these c operations in a batch. As shown in Section 3.4, on receiving SO, with the raw data F and bv23Tree Ψ stored in buffer U, CSS can executeBatch_UpdatesSO,Ψ,F to return to the client the results L,Tk×l,xroot∗ for batch updates, and the client can callVerify_Updatesxroot,SO,L,Tk×l,xroot∗ to authenticate these returned results.If the above results pass the client’s authentication, the client then applies an erasure code to encodeSO into λ encoded operations blocks bi1,bi2,…,biλ. Based on local state pointer sp, client first computes the indices i1,i2,…,iλ of these λ encoded blocks in order iτ=sp·λ+τ, 1≤τ≤λ, and computes the tag σiτ for each biτ by the same tag formula as in GenTags(·) of initialization. Secondly, client outsources these λ blocks bi1,bi2,…,biλ along with their tags into the sp+1th level of buffer E (i.e., the corresponding empty level of EO). Finally, client sends to TPA the updated state pointer sp∗=sp+1 with her signature and empties her O(λ) local storage for caching the next c ordered update operations. Overall, through this protocol, the CSS state st consists of U and EO as above.( 3 )   R e b u i l d x root , s k client , s t , s p. Once in every n update operations, when EO of buffer E gets filled (i.e., sp is equal to 2n~/λ as in Figure 4), the periodic rebuilding for E is triggered. Since buffer U stores the up-to-date copy of all raw data blocks, client can carry out this rebuilding based on U for the performance improvement, instead of decoding the whole E and applying all operations of EO on the original data of ED. (ED and EO will not be decoded and combined, unless client detects data corruption within CSS and wants to retrieve the whole data.)Benefitting from the ability of batch-reading multiple blocks from CSS and our hierarchical configuration, client can rebuild E with onlyO(λ) local memory that is the same size as a level of the hierarchical structure, which is the significant improvement when compared to existing schemes [14, 18, 19] that require such rebuilding with O(n) client local memory. In this protocol, the CSS state st consists of U and E. At the beginning, client runs ReadBlocks· to batch-read the first cc<λ raw blocks from U. After encoding these c blocks into λ codeword blocks, client computes the corresponding λ tags by the same way as in GenTags(·), where the indices of λ codeword blocks of each level are shown in Figure 4. Then, client outsources to CSS these λ codeword blocks and tags that will be stored in the first level of ED. Subsequently, client can empty her O(λ) local memory and batch-read from U the next batch of c blocks, which are processed and outsourced to CSS by the same procedures as above, except that each batch of λ processed codeword blocks and tags will be stored in the corresponding different level of ED (e.g., the second batch will be stored in the second level of ED, etc.). After the last batch of blocks from U are processed and outsourced, client authorizes CSS to update the whole ED with all above outsourced codeword blocks and tags, and CSS simultaneously empties the whole EO. Finally, client publishes the updated state pointer sp∗ to TPA, meaning that the rebuilding is over. Overall, the amortized bandwidth of rebuilding E is O(1) per update operation, since this rebuilding is executed only once every n update operations.


### 4.4. Outsourced Proof of Retrievability (OPOR)

(  1) R a n d o m C h a l B , t , P. The periodic random challenges are generated based on the time-based bitcoin pseudorandom source B. More specifically, given the current time t, the tool getblockhash(t) [12] from the bitcoin source B can output the hash of the latest block that has arisen since time t in the bitcoin block chain. As shown in [12], for a future time t, no adversary can predict the hash of a bitcoin block that will arise in the future. In addition, for a past time t, the hash of previous bitcoin block, returned by getblockhash(t), is objective and irrefutable against any adversary. Thus, let coint denote the output of getblockhash(t); then coint can be considered as a secure pseudorandom coin for time t.With the public parametersp,cl∈P, TPA can generate the random POR challenge of length sp·cl, by calling the same probabilistic algorithm Samplecoint,sp·cl as in [12] that coint is obtained from getblockhash(t) for the different time t. Specifically, to ensure that a POR challenge can sample the same amount of cl blocks from each filled level of buffer E (i.e., ED and EO) at CSS, TPA first calls Samplecoint,cl to choose a random cl-elements subset I∗=st,1,st,2,…,st,cl of 1,λ, and then it computes the sp·cl-elements set I as follows:(5)I=ζ·λ+τ∣0≤ζ≤sp-1,τ∈I∗,Moreover, for eachi∈I, as in [12], TPA also depends on Samplecoint,sp·cl to choose a corresponding random element αi←RZp. Finally, let Qt≔i,αii∈I denote an sp·cl-elements set, which is regarded as the POR challenge at time t and sent to CSS by TPA.(  2) G e n P r o o f ( Q t , s t ). Here, let buffer E be the CSS state st. Upon receiving challenge Qt, for each index i specified by Qt, CSS reads the corresponding block bi≔{bij}1≤j≤s and tag σi from E. Now CSS performs exactly as in the public verification scheme of [8] by computing the values μj(t), 1≤j≤s, along with σ(t) as follows: (6)μjt⟵∑i,αi∈Qtαi·bij∈Zp,σt⟵∏i,αi∈Qtσiαi∈G.At last, CSS sends to TPA its responseρ(t)∥sigCSS, where ρ(t)≔μ1(t),μ2(t),…,μs(t),σ(t), and sigCSS is CSS’s signature to provide nonrepudiation.(  3) P O R A u d i t ( P , Q t , ρ t ). Based on the public parameters set P and the challenge Qt, TPA can compute his own auditing parameter ξ(t) as follows:(7)ξt⟵∏i,αi∈QtHfid∥iαi∈G.Then, after TPA parses the CSS’s response to obtainρ(t), TPA will audit ρ(t) by checking the following equation:(8)eσt,g≟eξt·∏j=1sujμjt,ω.If this verification does not pass, TPA informs the client of this abnormal situation, meaning that the data loss occurs. Finally, TPA must generate and store the following logΛ(t) that corresponds to the challenge at time t:(9)Λt≔t,coint,ξt,ρt∥sigCSS.(  4) C h e c k L o g s ( B , T , Λ T , P , s k client ). To protect against malicious TPA who might violate the above auditing process or even collude with CSS, the client can verify TPA’s work by checking TPA’s logs. However, instead of checking the accumulated TPA’s logs one by one, client is able to batch-check multiple TPA’s logs all together, so such a client’s batch-checking against TPA is only seldom performed in practice, as shown in [12].Client can check the latest TPA’s log for a minimal check, since this log reflects the latest status of retrievability for the outsourced data [12]. More generally, to perform a batch-checking against TPA, client selects a point-in-time set T=t1,t2,…,tk and sends T to TPA, where each t∈T marks the time of a past challenge.Upon receivingT, for each t∈T, in terms of ρ(t) and ξ(t) stored in log⁡Λ(t), TPA computes(10)μjT⟵∑t∈Tμjt∈Zpfor1≤j≤s,σT⟵∏t∈Tσt∈G,ξT⟵∏t∈Tξt.Then, TPA responds to client with his proofϱ(T)≔μ1(T),μ2(T),…,μs(T),σ(T),ξ(T), which is also signed by TPA.Based on the public parameterssp and cl, for each t∈T, the client is able to reconstruct alone each past challenge Qt as described in the protocol RandomChal(·), by using Samplecoint,sp·cl with the pseudorandom coint obtained from getblockhash(t). So, client can compute her own checking parameter η(T) as follows:(11)ηT⟵∏t∈T∏i,αi∈QtHfid∥iαi∈G.After verifying TPA’s signature on the proofϱ(T), client first checks that whether η(T) is equal to ξ(T) of ϱ(T). If η(T)≠ξ(T), client outputs false, confirming that TPA was irresponsible for the past POR audits. Finally, client checks the following equation with her secret key α∈skclient:(12)ηT·∏j=1sujμjTα≟σT.If the above client’s check fails, client outputsfalse, which means that there exists collusion among TPA and CSS and that the data corruption has occurred within CSS. The correctness of (12) is demonstrated as follows:(13)σT=∏t∈Tσt=∏t∈T∏i,αi∈Qtσiαi=∏t∈T∏i,αi∈QtHfid∥iαi·∏j=1sujαi·bijα=∏t∈T∏i,αi∈QtHfid∥iαi·∏j=1suj∑t∈T∑i,αi∈Qtαi·bijα=ηT·∏j=1sujμjTα.


## 4.1. Cloud Server Storage Configuration

As shown in Figure1, there are two different buffers U and E at CSS side for outsourced data storage. Client’s original file F, consisting of n raw blocks F={m1,m2,…,mn}, will be separately stored into U and E with different formats, detailed as follows.U (Unencoded Buffer). To support the efficient reads, buffer U always stores the up-to-date copy of the raw data blocks, and thus the update operations issued from client must be immediately performed upon the appointed blocks of U. All the blocks in U are organized by the bv23Tree as proposed in Section 3, the batch-verifications property of which enables client to batch-read a group of raw blocks from U for improved performance.E (Erasure-Coded Buffer). Buffer E is organized by the same-sized hierarchical structure, as in Figure 4, where each level has the same size to hold λ encoded blocks with the blocks tags (λ is the security parameter). Moreover, E is equally divided into two parts ED and EO with the same capacity. ED is to store encoded data blocks, and EO is to store encoded operations blocks. At the beginning, client applies erasure code to encode the entire file F into n~ encoded data blocks, computes the blocks tags, and sequentially stores them into ED in terms of the blocks indices as shown in Figure 4. Subsequently, the content of ED will not be changed until buffer E is rebuilt. As shown in Section 3.4, each update operation O is of the form “Uam”, which can also be regarded as an operation block. In this case, after a batch of update operations SO={O1,O2,…,Oc}c<λ are performed upon U, client will encode SO into λ encoded operations blocks and store them along with the blocks tags into a corresponding level of EO. So, EO is empty in the initial state and will be incrementally filled up level by level over time. At last, once EO is full, the rebuilding of E is triggered, as will be described later.Figure 4
CSS-side hierarchical storage structure for erasure-coded buffer E, where each level storesλ encoded blocks along with tags.At a high level, by decoding the whole E and sequentially performing the accumulated update operations of EO upon the original data blocks of ED, the latest version of the whole client’s outsourced raw data can be recovered. Therefore, the periodic POR audits only need to be deployed against the buffer E, which functions as a backup storage to provide the retrievability guarantee when data loss occurs. To resist the mentioned selective deletion attack as before, every POR audit will sample challenged blocks from each filled level of E. Because each level is entirely encoded, malicious CSS must corrupt a significant portion of the encoded blocks of one level to actually cause the data loss. However, if malicious CSS corrupts that many encoded blocks of one level, it cannot pass the POR audits with overwhelming probability.


## 4.2. Initialization

We also work in the bilinear setting, whereG is a multiplicative cyclic group of prime order p and g is a generator of G. Let e:G×G→GT be the same nondegenerate bilinear map as in [8] that has the following property: for any z,ω∈Gand a,b∈Zp, eza,ωb=e(z,ω)ab. Let H:{0,1}∗→G be the secure BLS hash function. The initialization of our scheme is described as follows.(1)
GenKey(1k): each entity E∈{client,CSS,TPA} generates a signing key pair sskE,spkE for their respective signatures. In addition, client samples a random element α←RZp and computes ω←gα. α is kept secret by client but ω is public. So, client’s private key skclient=α,sskclient and her public key pkclient=ω,spkclient.(2)
GenTags(skclient,F): client applies erasure code to encode F={mi}1≤i≤n into n~ codeword blocks B=bi1≤i≤n~, and each bi is s sectors long: bi≔{bij}1≤j≤s. Client then generates a name fid for F and samples s elements u1,…,us←RG. For each index i, 1≤i≤n~, with her secret key α in skclient, client computes for bi the corresponding tag σi←Hfid∥i·∏j=1sujbijα and attaches σi to bi.(3)
OutsourceData(F,B,Φ): based on F={m1,m2,…,mn}, client generates the corresponding bv23Tree Ψ with the root hash xroot, as shown in Section 3.1. Then, client outsources F,Ψ into the buffer U and outsources all encoded data blocks B=bi1≤i≤n~ (along with their tags Φ=σi1≤i≤n~) into the ED part of buffer E, the layout of which is shown in Figure 4. In addition, let sp be a state pointer that denotes the number of the filled levels of buffer E. Clearly, the range of sp is n~/λ≤sp≤2n~/λ, as in Figure 4. Let cl denote the number of the challenged blocks from a filled level, and let P=sp,cl,g,ω,fid,u1,…,us be the public parameters set for POR audits. Finally, client keeps P and xroot locally, sends P to TPA, and deletes F,Ψ,B,Φ from her local storage.


## 4.3. Data Access Mechanisms

Based on the bv23Tree of buffer U and the hierarchical configuration of same-sized levels of buffer E, DOPOR supports batch updates that enable the client to perform a batch of update operations upon the outsourced storage, which is suitable for the common scenario of [14] where writes are frequent. Now, after completing the initialization of DOPOR, the client can access and update her outsourced data by the following three protocols.1   R e a d B l o c k s x root , Π , s t. With her local root hash xroot of bv23Tree, the client can batch-read any k appointed raw blocks from CSS, by sending the ordered blocks indices set Π=a1,a2,…,ak as the query to CSS. Here, let buffer U be the CSS state st. In terms of Section 3, upon receiving Π, CSS accesses appointed raw blocks M=ma1,ma2,…,mak and the tree leaves L=va1,va2,…,vak from U, generates Tk×l←Proof_TableΨ,Π, and returns M,L,Tk×l to the client. Then, the client batch-verifies the authenticity of L by callingBatch_Verifyxroot,Π,L,Tk×l and finally checks the integrity of all raw blocks of M according to the corresponding hash values stored in L.2   P e r f o r m U p d a t e s x root , S O , s k client , s t , s p. Suppose that the client keeps O(λ) local storage to cache cc<λ ordered update operations SO≔O1,O2,…,Oc. Then, the client sends SO to CSS for performing these c operations in a batch. As shown in Section 3.4, on receiving SO, with the raw data F and bv23Tree Ψ stored in buffer U, CSS can executeBatch_UpdatesSO,Ψ,F to return to the client the results L,Tk×l,xroot∗ for batch updates, and the client can callVerify_Updatesxroot,SO,L,Tk×l,xroot∗ to authenticate these returned results.If the above results pass the client’s authentication, the client then applies an erasure code to encodeSO into λ encoded operations blocks bi1,bi2,…,biλ. Based on local state pointer sp, client first computes the indices i1,i2,…,iλ of these λ encoded blocks in order iτ=sp·λ+τ, 1≤τ≤λ, and computes the tag σiτ for each biτ by the same tag formula as in GenTags(·) of initialization. Secondly, client outsources these λ blocks bi1,bi2,…,biλ along with their tags into the sp+1th level of buffer E (i.e., the corresponding empty level of EO). Finally, client sends to TPA the updated state pointer sp∗=sp+1 with her signature and empties her O(λ) local storage for caching the next c ordered update operations. Overall, through this protocol, the CSS state st consists of U and EO as above.( 3 )   R e b u i l d x root , s k client , s t , s p. Once in every n update operations, when EO of buffer E gets filled (i.e., sp is equal to 2n~/λ as in Figure 4), the periodic rebuilding for E is triggered. Since buffer U stores the up-to-date copy of all raw data blocks, client can carry out this rebuilding based on U for the performance improvement, instead of decoding the whole E and applying all operations of EO on the original data of ED. (ED and EO will not be decoded and combined, unless client detects data corruption within CSS and wants to retrieve the whole data.)Benefitting from the ability of batch-reading multiple blocks from CSS and our hierarchical configuration, client can rebuild E with onlyO(λ) local memory that is the same size as a level of the hierarchical structure, which is the significant improvement when compared to existing schemes [14, 18, 19] that require such rebuilding with O(n) client local memory. In this protocol, the CSS state st consists of U and E. At the beginning, client runs ReadBlocks· to batch-read the first cc<λ raw blocks from U. After encoding these c blocks into λ codeword blocks, client computes the corresponding λ tags by the same way as in GenTags(·), where the indices of λ codeword blocks of each level are shown in Figure 4. Then, client outsources to CSS these λ codeword blocks and tags that will be stored in the first level of ED. Subsequently, client can empty her O(λ) local memory and batch-read from U the next batch of c blocks, which are processed and outsourced to CSS by the same procedures as above, except that each batch of λ processed codeword blocks and tags will be stored in the corresponding different level of ED (e.g., the second batch will be stored in the second level of ED, etc.). After the last batch of blocks from U are processed and outsourced, client authorizes CSS to update the whole ED with all above outsourced codeword blocks and tags, and CSS simultaneously empties the whole EO. Finally, client publishes the updated state pointer sp∗ to TPA, meaning that the rebuilding is over. Overall, the amortized bandwidth of rebuilding E is O(1) per update operation, since this rebuilding is executed only once every n update operations.


## 4.4. Outsourced Proof of Retrievability (OPOR)

(  1) R a n d o m C h a l B , t , P. The periodic random challenges are generated based on the time-based bitcoin pseudorandom source B. More specifically, given the current time t, the tool getblockhash(t) [12] from the bitcoin source B can output the hash of the latest block that has arisen since time t in the bitcoin block chain. As shown in [12], for a future time t, no adversary can predict the hash of a bitcoin block that will arise in the future. In addition, for a past time t, the hash of previous bitcoin block, returned by getblockhash(t), is objective and irrefutable against any adversary. Thus, let coint denote the output of getblockhash(t); then coint can be considered as a secure pseudorandom coin for time t.With the public parametersp,cl∈P, TPA can generate the random POR challenge of length sp·cl, by calling the same probabilistic algorithm Samplecoint,sp·cl as in [12] that coint is obtained from getblockhash(t) for the different time t. Specifically, to ensure that a POR challenge can sample the same amount of cl blocks from each filled level of buffer E (i.e., ED and EO) at CSS, TPA first calls Samplecoint,cl to choose a random cl-elements subset I∗=st,1,st,2,…,st,cl of 1,λ, and then it computes the sp·cl-elements set I as follows:(5)I=ζ·λ+τ∣0≤ζ≤sp-1,τ∈I∗,Moreover, for eachi∈I, as in [12], TPA also depends on Samplecoint,sp·cl to choose a corresponding random element αi←RZp. Finally, let Qt≔i,αii∈I denote an sp·cl-elements set, which is regarded as the POR challenge at time t and sent to CSS by TPA.(  2) G e n P r o o f ( Q t , s t ). Here, let buffer E be the CSS state st. Upon receiving challenge Qt, for each index i specified by Qt, CSS reads the corresponding block bi≔{bij}1≤j≤s and tag σi from E. Now CSS performs exactly as in the public verification scheme of [8] by computing the values μj(t), 1≤j≤s, along with σ(t) as follows: (6)μjt⟵∑i,αi∈Qtαi·bij∈Zp,σt⟵∏i,αi∈Qtσiαi∈G.At last, CSS sends to TPA its responseρ(t)∥sigCSS, where ρ(t)≔μ1(t),μ2(t),…,μs(t),σ(t), and sigCSS is CSS’s signature to provide nonrepudiation.(  3) P O R A u d i t ( P , Q t , ρ t ). Based on the public parameters set P and the challenge Qt, TPA can compute his own auditing parameter ξ(t) as follows:(7)ξt⟵∏i,αi∈QtHfid∥iαi∈G.Then, after TPA parses the CSS’s response to obtainρ(t), TPA will audit ρ(t) by checking the following equation:(8)eσt,g≟eξt·∏j=1sujμjt,ω.If this verification does not pass, TPA informs the client of this abnormal situation, meaning that the data loss occurs. Finally, TPA must generate and store the following logΛ(t) that corresponds to the challenge at time t:(9)Λt≔t,coint,ξt,ρt∥sigCSS.(  4) C h e c k L o g s ( B , T , Λ T , P , s k client ). To protect against malicious TPA who might violate the above auditing process or even collude with CSS, the client can verify TPA’s work by checking TPA’s logs. However, instead of checking the accumulated TPA’s logs one by one, client is able to batch-check multiple TPA’s logs all together, so such a client’s batch-checking against TPA is only seldom performed in practice, as shown in [12].Client can check the latest TPA’s log for a minimal check, since this log reflects the latest status of retrievability for the outsourced data [12]. More generally, to perform a batch-checking against TPA, client selects a point-in-time set T=t1,t2,…,tk and sends T to TPA, where each t∈T marks the time of a past challenge.Upon receivingT, for each t∈T, in terms of ρ(t) and ξ(t) stored in log⁡Λ(t), TPA computes(10)μjT⟵∑t∈Tμjt∈Zpfor1≤j≤s,σT⟵∏t∈Tσt∈G,ξT⟵∏t∈Tξt.Then, TPA responds to client with his proofϱ(T)≔μ1(T),μ2(T),…,μs(T),σ(T),ξ(T), which is also signed by TPA.Based on the public parameterssp and cl, for each t∈T, the client is able to reconstruct alone each past challenge Qt as described in the protocol RandomChal(·), by using Samplecoint,sp·cl with the pseudorandom coint obtained from getblockhash(t). So, client can compute her own checking parameter η(T) as follows:(11)ηT⟵∏t∈T∏i,αi∈QtHfid∥iαi∈G.After verifying TPA’s signature on the proofϱ(T), client first checks that whether η(T) is equal to ξ(T) of ϱ(T). If η(T)≠ξ(T), client outputs false, confirming that TPA was irresponsible for the past POR audits. Finally, client checks the following equation with her secret key α∈skclient:(12)ηT·∏j=1sujμjTα≟σT.If the above client’s check fails, client outputsfalse, which means that there exists collusion among TPA and CSS and that the data corruption has occurred within CSS. The correctness of (12) is demonstrated as follows:(13)σT=∏t∈Tσt=∏t∈T∏i,αi∈Qtσiαi=∏t∈T∏i,αi∈QtHfid∥iαi·∏j=1sujαi·bijα=∏t∈T∏i,αi∈QtHfid∥iαi·∏j=1suj∑t∈T∑i,αi∈Qtαi·bijα=ηT·∏j=1sujμjTα.


## 5. Security Analysis

Similar to the analysis of [8, 12], we evaluate the soundness of our DOPOR scheme according to three parts: unforgeability, liability, and extractability.Theorem 1 (unforgeability).
It is computationally infeasible for any adversaryA to forge a proof that can pass verifier’s check, if the Computational Diffie-Hellman (CDH) problem and the Discrete Logarithm (DL) problem are hard.Proof.
Since CSS does not check any proof throughout the whole process of executing DOPOR, there are only two cases to be discussed.
Case 1. TPA plays the role of verifier to check the proof returned from CSS during executing the protocols GenProof(·) and PORAudit(·) as shown in Section 4.4. In this case, observe that both CSS and TPA perform exactly the same as the BLS-based public verification scheme of [8], so the unforgeability guarantee immediately follows from the work of [8]. As shown in [21], the BLS scheme is secure when the CDH problem is hard in bilinear groups, based on which the unforgeability of BLS-based public scheme has been proven in [8] and thus omitted here.
Case 2. The client acts as the verifier to check TPA’s logs as in the protocol CheckLogs(·) of Section 4.4. To pass the client’s check with (12), TPA should return the correct proof μ1(T),μ2(T),…,μs(T),σ(T). Now, assume that TPA is able to forge the proof. As shown in [8], due to the security of BLS scheme, the BLS-based homomorphic verifiable tag σi is unforgeable, and thus the aggregated tag σ(T) is also unforgeable. So, the only choice for TPA is to generate the forged aggregated block, denoted with μ~1(T),μ~2(T),…,μ~s(T), as the response to client’s check. Then, for (12) to be satisfied, we have(14)ηT·∏j=1sujμ~jTα=σT.
In addition, according to the correct proof, we have(15)ηT·∏j=1sujμjTα=σT.
Note thatη(T) is the parameter computed by client herself, and the security of η(T) is ensured by the security of bitcoin pseudorandom source of [12]. Based on the security of BLS scheme, we can learn that(16)∏j=1sujμjT=∏j=1sujμ~jT⟹∏j=1sujΔμjT=1,where Δμj(T)=μ~j(T)-μj(T) and μ~j(T)≠μj(T).
For any two given elementsg1,g2∈G, we have uj=g1pjg2qj∈G, where pj,qj∈Zp. Hence, (16) is transformed as follows: (17)∏j=1sg1pjg2qjΔμjT=1⟹g2=g1-∑j=1spj·ΔμjT/∑j=1sqj·ΔμjT.
Obviously, (17) means that malicious TPA can solve the DL problem, which is in conflict with the assumption that DL problem is hard. Therefore, it is infeasible for TPA to forge a proof to pass the client’s check. This completes our proof.Theorem 2 (liability).
If any adversaryA attempts to cheat or frame the honest entity who has been well behaving, the honest entity can output incontestable evidence to confirm the misbehavior of adversary A in case of lawsuit.Proof.
It is clear that if the honest entity can protect against the collusion of the other two malicious entities, then this honest entity can certainly protect against any single malicious entity. Hence, to prove Theorem2, it suffices to consider the following three cases where only one entity is honest.
Case 1. Honest client defends against the collusion of CSS and TPA. Obviously, CSS has incentive to collude with TPA only when the outsourced data corruption has occurred at cloud side. In this case, once the corrupted data blocks are challenged, according to Theorem 1, both CSS and TPA cannot forge an effective proof to pass client’s check against TPA’s log, unless they can solve the DL problem (but this probability is negligible). Therefore, the false output by client when executing the protocol CheckLogs(·) is the incontestable evidence to identify the collusion of CSS and TPA.
Case 2. Honest TPA defends against the collusion of client and CSS. As shown in the protocol PORAudit(·) of Section 4.4, TPA completes his auditing work by computing the auditing parameter ξ(t) and verifying (8), where all these processes are reproducible and undeniable for the malicious entities. More specifically, on the one hand, the nonrepudiation of parameter ξ(t) is derived from the objectivity of challenge Qt, which is computed based on the secure bitcoin pseudorandom source and the public parameters sp,cl. On the other hand, all other inputs involved in verifying (8) are also undeniable for both client and CSS; for example, μ1(t),μ2(t),…,μs(t),σ(t) are signed by CSS’s signature, and g,ω,u1,…,us are the public parameters confirmed by all entities. Hence, the honest TPA can provide his logs Λ(t) in case of lawsuit, which includes all above incontestable evidence enabling the playback of all past TPA’s auditing work to prove the innocence of TPA.
Case 3. Honest CSS defends against the collusion of client and TPA. When malicious client colludes with TPA to falsely accuse CSS of corrupting the ith block bi, CSS can output the intact bi={bij}1≤j≤s and its tag σi as the incontestable evidence. As shown in [8], each tag σi constructed and outsourced by client herself is unforgeable. Based on the security of BLS signature scheme, as long as the above bi and σi output by CSS satisfy (18), then CSS is innocent.(18)eσi,g≟eHfid∥i·∏j=1sujbij,ω.
This completes the proof of Theorem2.According to Theorem2, all the three entities have to behave properly in DOPOR. In this case, the extractability during the TPA’ audits against CSS can immediately follow from the work of [8], since the procedure of TPA’s audits of DOPOR corresponds to the public verification scheme of [8]. As for the extractability of performing CheckLogs(·) protocol, we have the following theorem.Theorem 3 (extractability).
During the client’s checking against TPA, if client does not outputfalse after checking TPA’s logs, then there exists a deterministic extraction algorithm, based on which client can extract the challenged file blocks by the repetitive interactions with TPA.Proof.
According to Theorem1, to pass client’s check during the execution of protocol CheckLogs(·), TPA has to respond to client with the correct proof ϱ(T) that includes the aggregated block μ1(T),μ2(T),…,μs(T), and each μj(T) is a linear equation of the following form:(19)μjT=∑t∈Tμjt=∑t∈T∑i,αi∈Qtαi·bij,where T is a set of point-in-times chosen by client herself, and all the coefficients αi are dominated by these point-in-times as shown in the protocol RandomChal(·) of Section 4.4.
Now, suppose client chooses the appropriate point-in-times in the past to generate different setT and checks TPA’s logs for a polynomial number of times by sending different T to TPA; then, client can get a total of s systems of linear equations that are built upon the challenged target blocks. Finally, by solving these s systems, client can extract all target blocks.When referring to dynamic updates, as shown in Section4.3, the procedure of performing updates is divided into two parts: (1) performing the batch updates upon buffer U according to the algorithmsBatch_Updates· andVerify_Updates·, as shown in Section 3.4, the essence of which is based on the property of batch verifications of bv23Tree, while the security of this property is ensured by Theorem 4; (2) outsourcing a batch of encoded operations blocks and their tags to buffer E, the security of which is directly ensured by the security of the unforgeable tags, the periodic executions of POR audits against buffer E, and the erasure code scheme.Theorem 4.
Assuming the existence of a collision-resistant hash functionh·, for any k ordered indices set Π=a1,a2,…,ak appointed by the client, the corresponding proof table Tk×l generated using the bv23Tree ensures the integrity of all the k appointed leaves L=va1,va2,…,vak returned from CSS with overwhelming probability.Proof.
As shown in Section3.2, upon receiving the appointed ordered indices set Π=a1,a2,…,ak, CSS should respond to client with the corresponding leaves L=va1,va2,…,vak and proof table Tk×l. Now, suppose that CSS tries to act dishonestly; then, the possible ways for CSS to misbehave can be covered by the following two cases.
Case 1. Malicious CSS either forges some leaves within L or forges some items within the proof table Tk×l. As shown in Section 3.3, client possesses the public tree root hash xroot and will verify both L and Tk×l by calling the algorithmBatch_Verify(·), the procedure of which is to recalculate the public xroot by iteratively hashing the values of all tree nodes included in L and Tk×l in terms of the specified order. Apparently, the above forged L or Tk×l can enableBatch_Verify(·) to output the same root hash value as xroot, meaning that CSS is able to find the collisions against the hash functionh·, which contradicts the assumption that h· is collision-resistant. Therefore, it is a negligible probability for malicious CSS to forge L or Tk×l.
Case 2. Malicious CSS launches the replacing attack; that is, CSS returns the replaced L~ where some appointed leaves are replaced with other existing leaves of bv23Tree and the corresponding proof table T~k×l that is correctly generated based on L~. Without loss of generality, suppose that L~=vx,vy,…,vak, where vx and vy are not the appointed leaves; that is, x≠a1 and y≠a2. In this case, although the final hash value output byBatch_Verify(·) is equal to the public xroot, the final value of the variable IS1 withinBatch_Verify(·) will be x,y,…,ak instead of the specified a1,a2,…,ak, which contradicts the expected results as shown in Section 3.3. So, client will still output false meaning that above malicious attack is detected by client.
In short, if there exists a collision-resistant hash function, malicious CSS has to return all the appointed leaves along with the correct proof table to pass client’s batch verifications upon these leaves.


## 6. Performance Evaluation

Our experiments were deployed using Python language on the Linux system with Intel Xeon E5-2609 CPU running at 2.40 GHz, 16 GB of RAM, and 7200 RPM 600 GB Serial ATA drive with a 32 MB buffer. The cryptographic operations were implemented based on the Python Cryptography Toolkit [22] and Pypbc library [23], and we used the 80-bit security parameter that means the order p of group G is of 160-bit length. We chose 1 GB raw data file F for testing and relied on the 9,12 erasure code for encoding. For ease of comparison, all block sizes are set to 4 KB as in [6, 14]. Our results are an average of 20 rounds.


### 6.1. POR Audits Cost

During each POR audit, since the number of challenged blocksI is far less than the total number of encoded file blocks n~ (e.g., the percent I/n~=1% as in [12]), the time consumed in proof computation (or proof verification) will not be the bottleneck for CSS (or TPA). The POR audit phase of DOPOR corresponds to the execution of the public verification construction of [8], the efficient computation performance of which has been confirmed as shown in previous studies [5, 6, 10]. Therefore, the computation time of POR audit phase is not the primary concern in our DOPOR scheme, and we will focus on evaluating the bandwidth cost of this phase.Figure5 depicts the total TPA-CSS bandwidth cost for executing POR audit once, for various percents of challenged blocks. Here, with regard to the given parameters cl and λ in DOPOR, the percentage of challenged blocks is equal to cl/λ. It is obvious that the public DPOR of [14] results in a large communication overhead since it must transfer all challenged blocks during each audit, which greatly affects the bandwidth performance. By relying on the technologies of blockless verification and homomorphic authenticators (tags) to compress the proof size, the bandwidth costs of both our DOPOR and the static OPOR (i.e., Fortress) of [12] are only dominated by the sizes of challenges released from TPA and thus gradually increase with the percents of challenged blocks. Note that the bandwidth cost of DOPOR is always less than that of Fortress, since TPA only needs to send a single challenge for each audit in DOPOR, but there are two parallel challenges for TPA to be sent in Fortress. This is due to the fact that, during each audit, Fortress requires CSS to respond with two different responses [12]: one is used by TPA for auditing CSS and the other will be used by client for checking TPA’s work. And thus these two responses correspond to two parallel challenges in Fortress. However, as shown in Section 4.4, DOPOR enables CSS to respond with only one response, which is based on the public key cryptosystem to support both TPA’s auditing and client’s checking. So, within DOPOR, there is only one challenge corresponding to the above sole CSS’s response.Figure 5
TPA-CSS bandwidth cost for a POR audit, with respect to the fraction of challenged blocks of the total number of encoded blocks.


### 6.2. Read Cost

When client reads a batch of raw blocks from CSS, the integrity of these blocks is guaranteed by the authenticated data structure of the up-to-date buffer U. In Figure6, we evaluate the extra bandwidth cost (i.e., not including the bandwidth of transferring the blocks themselves) incurred on client side for batch-verifying the leaves of all returned raw blocks with the proposed proof table of bv23Tree, when compared to the costs of the rb23Tree method [6] and the standard MHT method [14] that can only verify all appointed leaves by transferring their respective proof paths. As shown, with the increasing number of blocks batch-read from CSS, the extra bandwidth cost caused by rb23Tree is much higher than MHT, since the basic component of proof path of rb23Tree is an 8-element tuplemark with a larger size. However, owing to the proof table that avoids transferring all repetitive node values within different proof paths, our bv23Tree incurs the lowest extra bandwidth cost among the three dynamic structures. Likewise, as shown in Figure 7, based on bv23Tree, client also further reduces the computation time spent for verifying the integrity of all returned blocks, due to the fact that the proof table enables client to batch-verify all returned leaves together just by computing the tree root hash once, avoiding the straightforward way of rb23Tree and standard MHT that client has to verify different leaves one after another by repeatedly computing the tree root hash with different proof paths.Figure 6
Extra bandwidth cost consumed by client for verifying the leaves of all blocks batch-read from CSS, according to different authenticated data structures.Figure 7
Computation time spent by client for verifying the integrity of all blocks batch-read from CSS, according to different authenticated data structures.In conclusion, our results show that the more the blocks batch-read from CSS, the more the repetitive node values omitted for transferring and computing according to proof table, and thus the client will save more costs based on bv23Tree for improving the performance of reads.


### 6.3. Write Cost

Now, we evaluate the performance of writes for DOPOR and the public DPOR of [14], both of which apply the client-side cache measure for performing writes; that is, client will cache locally a group of raw blocks (contained in the update operations of modification or insertion as in Section 3.4) and write these blocks in a batch to CSS, as shown in the protocol PerformUpdates· of Section 4.3. For DOPOR of this experiment, the parameter c is the number of client-side cached blocks, which determines the parameter λ according to the erasure-coding rate.Figure8 depicts the client-CSS amortized bandwidth cost for writing each 4 KB raw block. With the increasing number of client-side cached blocks, our results show that DOPOR incurs 17%~48% more amortized bandwidth than the public DPOR, due to the fact that DOPOR needs to transfer the additional encoded operations blocks besides the raw blocks. However, recall that the required bandwidth cost for frequent POR audits in the public DPOR is orders of magnitude higher than that in DOPOR (Figure 5), and DOPOR achieves a stronger security level by protecting against malicious TPA and collusion than the public DPOR. Furthermore, as shown in Figure 9, the public DPOR incurs an average of 45% more computation time at CSS side than DOPOR, since during performing writes the public DPOR must rebuild the corresponding levels of an MHT-based hierarchical structure located on CSS’s disk, which results in a lot of additional disk I/O time when compared to DOPOR that does not need to do such rebuilding.Figure 8
Client-CSS amortized bandwidth cost for each block when writing all cached blocks in a batch to CSS.Figure 9
Computation time spent by CSS when writing all cached blocks in a batch to CSS.


### 6.4. Client-Side Checking Cost

As shown in [12], although client should not be embroiled in the most frequent POR audits, it is necessary to give client the capability of checking TPA’s past work to protect against the malicious TPA.Since both DOPOR and the Fortress scheme of [12] adopt the aggregation technology to compress the proof size, the client-TPA bandwidth costs during checking TPA are alike for these two schemes, so in this experiment we focus on measuring the client’s computation time of two investigated schemes when batch-checking TPA’s logs, as shown in Figure 10. Here, one log corresponds to a past POR audit performed by TPA with challenging 1% of the total encoded blocks. Compared to Fortress, DOPOR requires more time at client side for checking TPA, due to the fact that the exponentiation operation on the elliptic curve of DOPOR incurs more computation cost than the module operation of Fortress. However, recall that DOPOR enables the efficient data dynamics that cannot be supported in Fortress, so the additional client-side time cost incurred by DOPOR, that is, the distance between the line of DOPOR and that of Fortress as in Figure 10, can be regarded as the price for dynamism under the OPOR setting. Indeed, this additional dynamism cost can be tolerated by client to a great extent, since the client’s checking against TPA is an optional verification and is only seldom executed in practice [12]; for example, client might just batch-check TPA’s logs once in several months or even a year.Figure 10
Computation time spent by client for batch-checking TPA’s logs (including the time to access the bitcoin source).


## 6.1. POR Audits Cost

During each POR audit, since the number of challenged blocksI is far less than the total number of encoded file blocks n~ (e.g., the percent I/n~=1% as in [12]), the time consumed in proof computation (or proof verification) will not be the bottleneck for CSS (or TPA). The POR audit phase of DOPOR corresponds to the execution of the public verification construction of [8], the efficient computation performance of which has been confirmed as shown in previous studies [5, 6, 10]. Therefore, the computation time of POR audit phase is not the primary concern in our DOPOR scheme, and we will focus on evaluating the bandwidth cost of this phase.Figure5 depicts the total TPA-CSS bandwidth cost for executing POR audit once, for various percents of challenged blocks. Here, with regard to the given parameters cl and λ in DOPOR, the percentage of challenged blocks is equal to cl/λ. It is obvious that the public DPOR of [14] results in a large communication overhead since it must transfer all challenged blocks during each audit, which greatly affects the bandwidth performance. By relying on the technologies of blockless verification and homomorphic authenticators (tags) to compress the proof size, the bandwidth costs of both our DOPOR and the static OPOR (i.e., Fortress) of [12] are only dominated by the sizes of challenges released from TPA and thus gradually increase with the percents of challenged blocks. Note that the bandwidth cost of DOPOR is always less than that of Fortress, since TPA only needs to send a single challenge for each audit in DOPOR, but there are two parallel challenges for TPA to be sent in Fortress. This is due to the fact that, during each audit, Fortress requires CSS to respond with two different responses [12]: one is used by TPA for auditing CSS and the other will be used by client for checking TPA’s work. And thus these two responses correspond to two parallel challenges in Fortress. However, as shown in Section 4.4, DOPOR enables CSS to respond with only one response, which is based on the public key cryptosystem to support both TPA’s auditing and client’s checking. So, within DOPOR, there is only one challenge corresponding to the above sole CSS’s response.Figure 5
TPA-CSS bandwidth cost for a POR audit, with respect to the fraction of challenged blocks of the total number of encoded blocks.


## 6.2. Read Cost

When client reads a batch of raw blocks from CSS, the integrity of these blocks is guaranteed by the authenticated data structure of the up-to-date buffer U. In Figure6, we evaluate the extra bandwidth cost (i.e., not including the bandwidth of transferring the blocks themselves) incurred on client side for batch-verifying the leaves of all returned raw blocks with the proposed proof table of bv23Tree, when compared to the costs of the rb23Tree method [6] and the standard MHT method [14] that can only verify all appointed leaves by transferring their respective proof paths. As shown, with the increasing number of blocks batch-read from CSS, the extra bandwidth cost caused by rb23Tree is much higher than MHT, since the basic component of proof path of rb23Tree is an 8-element tuplemark with a larger size. However, owing to the proof table that avoids transferring all repetitive node values within different proof paths, our bv23Tree incurs the lowest extra bandwidth cost among the three dynamic structures. Likewise, as shown in Figure 7, based on bv23Tree, client also further reduces the computation time spent for verifying the integrity of all returned blocks, due to the fact that the proof table enables client to batch-verify all returned leaves together just by computing the tree root hash once, avoiding the straightforward way of rb23Tree and standard MHT that client has to verify different leaves one after another by repeatedly computing the tree root hash with different proof paths.Figure 6
Extra bandwidth cost consumed by client for verifying the leaves of all blocks batch-read from CSS, according to different authenticated data structures.Figure 7
Computation time spent by client for verifying the integrity of all blocks batch-read from CSS, according to different authenticated data structures.In conclusion, our results show that the more the blocks batch-read from CSS, the more the repetitive node values omitted for transferring and computing according to proof table, and thus the client will save more costs based on bv23Tree for improving the performance of reads.


## 6.3. Write Cost

Now, we evaluate the performance of writes for DOPOR and the public DPOR of [14], both of which apply the client-side cache measure for performing writes; that is, client will cache locally a group of raw blocks (contained in the update operations of modification or insertion as in Section 3.4) and write these blocks in a batch to CSS, as shown in the protocol PerformUpdates· of Section 4.3. For DOPOR of this experiment, the parameter c is the number of client-side cached blocks, which determines the parameter λ according to the erasure-coding rate.Figure8 depicts the client-CSS amortized bandwidth cost for writing each 4 KB raw block. With the increasing number of client-side cached blocks, our results show that DOPOR incurs 17%~48% more amortized bandwidth than the public DPOR, due to the fact that DOPOR needs to transfer the additional encoded operations blocks besides the raw blocks. However, recall that the required bandwidth cost for frequent POR audits in the public DPOR is orders of magnitude higher than that in DOPOR (Figure 5), and DOPOR achieves a stronger security level by protecting against malicious TPA and collusion than the public DPOR. Furthermore, as shown in Figure 9, the public DPOR incurs an average of 45% more computation time at CSS side than DOPOR, since during performing writes the public DPOR must rebuild the corresponding levels of an MHT-based hierarchical structure located on CSS’s disk, which results in a lot of additional disk I/O time when compared to DOPOR that does not need to do such rebuilding.Figure 8
Client-CSS amortized bandwidth cost for each block when writing all cached blocks in a batch to CSS.Figure 9
Computation time spent by CSS when writing all cached blocks in a batch to CSS.


## 6.4. Client-Side Checking Cost

As shown in [12], although client should not be embroiled in the most frequent POR audits, it is necessary to give client the capability of checking TPA’s past work to protect against the malicious TPA.Since both DOPOR and the Fortress scheme of [12] adopt the aggregation technology to compress the proof size, the client-TPA bandwidth costs during checking TPA are alike for these two schemes, so in this experiment we focus on measuring the client’s computation time of two investigated schemes when batch-checking TPA’s logs, as shown in Figure 10. Here, one log corresponds to a past POR audit performed by TPA with challenging 1% of the total encoded blocks. Compared to Fortress, DOPOR requires more time at client side for checking TPA, due to the fact that the exponentiation operation on the elliptic curve of DOPOR incurs more computation cost than the module operation of Fortress. However, recall that DOPOR enables the efficient data dynamics that cannot be supported in Fortress, so the additional client-side time cost incurred by DOPOR, that is, the distance between the line of DOPOR and that of Fortress as in Figure 10, can be regarded as the price for dynamism under the OPOR setting. Indeed, this additional dynamism cost can be tolerated by client to a great extent, since the client’s checking against TPA is an optional verification and is only seldom executed in practice [12]; for example, client might just batch-check TPA’s logs once in several months or even a year.Figure 10
Computation time spent by client for batch-checking TPA’s logs (including the time to access the bitcoin source).


## 7. Related Work

Nowadays, with the rapid development of cloud computing, more and more cloud applications are designed upon the big data stored at CSS side, such as the service quality evaluation [24] and cloud service recommendation [25, 26]. However, how to guarantee the storage security of the big data is a critical challenge for mobile clients in the setting of cloud computing. Proof of Retrievability (POR) is a kind of security measure that builds upon cryptographic proofs to ensure the correctness and retrievability of client’s big data outsourced to cloud. Juels and Kaliski Jr. [7] proposed the first POR scheme by utilizing the “sentinels” technique, where client can conceal some sentinel blocks among other original data blocks for remote POR audits before outsourcing her data. But this proposal can only support a limited number of POR audits, since performing the audits will expose the corresponding sentinels, so the frequent audits cannot be sustained once all sentinels are exhausted. Based on the pseudorandom functions (PRFs) and BLS signatures [21], Shacham and Waters [8] proposed two improved POR schemes with private verification and public verification, respectively. Both of these schemes enable an unlimited number of audits against CSS and simultaneously compress the response of CSS into one aggregated block along with a small authenticator value for optimized auditing bandwidth. Subsequently, Dodis et al. [27] generalized the constructions of [7, 8] by combining the concepts of POR with the coding and complexity theory. In view of the importance of data dynamics, Cash et al. [18] provided a Dynamic POR (DPOR) scheme based on the ORAM technique. Because ORAM will incur the heavy bandwidth overhead for client when performing dynamic updates under the POR setting, by replacing ORAM with the FFT-based constructible code and the hierarchical storage structure, Shi et al. [14] designed a more efficient private DPOR scheme than that of [18] and simultaneously applied the MHT structure to turn this private DPOR into a public DPOR scheme. Furthermore, with the observations made upon previous POR studies, Etemad and Küpçü [19] proposed a general framework to construct efficient DPOR and defend against the selective deletion attack described in [14].On the other hand, Provable Data Possession (PDP), first proposed by Ateniese et al. [17], is a closely related research direction that focuses on ensuring the integrity of outsourced data. The difference between POR and PDP is that POR applies the erasure code but PDP does not. As shown in [19], the security level of POR is stronger than that of PDP, since POR ensures thatthe whole outsourced data can be retrieved by client, when compared to PDP that only guarantees the integrity ofmost of the outsourced data. Given that some existing public auditing schemes [5, 15, 16] are designed without involving erasure code, these schemes can be classed as the variants of PDP. Zhu et al. [4] presented a cooperative PDP (CPDP) scheme for distributed Multicloud Storage setting. Wang et al. [5] designed the random masking technology to protect client’s outsourced data from leaking to TPA during the audits. Erway et al. [13] proposed the first Dynamic PDP (DPDP) scheme to support efficient data updates using Skip List. And then variant authenticated structures were proposed for data dynamics, such as the standard MHT method [9], rank-based MHT [15], multireplica MHT [16], and rb23Tree [6]. However, all these authenticated structures can only verify different leaves one by one, which is an inefficient way for client when there are many leaves that need to be verified.In addition, as shown in [12], when referring to public verification (auditing), the potential security risk is that TPA might also be malicious. But this risk has not been considered by all the above public schemes. Outsourced Proof of Retrievability (OPOR), proposed by Armknecht et al. [12], is the first scheme to protect against malicious TPA under the public POR setting. However, the OPOR construction of [12] only supports the static data, which is the limitation that should be further solved.


## 8. Conclusions

As a stronger security model in the context of remote data auditing, Outsourced Proof of Retrievability (OPOR) focuses on dealing with the dilemma that client hopes to resort to TPA for assessing the storage security of her outsourced data, while TPA might be malicious and collude with CSS to cheat client. In this paper, we propose a concrete DOPOR scheme to support data dynamics under the environment of OPOR. Our DOPOR scheme is constructed based on a newly designed authenticated data structure, called bv23Tree, which not only relies on the property of balanced tree to guarantee the expected logarithmic complexity in any case of dynamic updates, but also enables client to batch-verify multiple appointed leaves all together for improved performance. Under the setting of employing erasure code, by separating the updated data from the original data and adopting the hierarchical structure of same-sized levels to uniformly store all encoded data, DOPOR can efficiently support batch reads and updates upon outsourced storage according to the feature of batch verifications of bv23Tree. When compared to the state of the art, our experiments show that DOPOR incurs a lower bandwidth cost for frequent TPA’s audits than the original static OPOR scheme, and the overall performance of DOPOR for reads and writes is comparable to that of existing public Dynamic POR scheme.



---

*Source: 4186243-2018-05-09.xml*