# PMAB: A Public Mutual Audit Blockchain for Outsourced Data in Cloud Storage

Authors: Hanzhe Yang; Ruidan Su; Pei Huang; Yuhan Bai; Kai Fan; Kan Yang; Hui Li; Yintang Yang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

With the rapid growth of data, limited by the storage capacity, more and more IoT applications choose to outsource data to Cloud Service Providers (CSPs). But, in such scenarios, outsourced data in cloud storage can be easily corrupted and difficult to be found in time, which brings about potential security issues. Thus, Provable Data Possession (PDP) protocol has been extensively researched due to its capability of supporting efficient audit for outsourced data in cloud. However, most PDP schemes require the Third-Party Auditor (TPA) to audit data for Data Owners (DOs), which requires the TPA to be trustworthy and fair. To eliminate the TPA, we present a Public Mutual Audit Blockchain (PMAB) for outsourced data in cloud storage. We first propose an audit chain architecture based on Ouroboros and an incentive mechanism based on credit to allow CSPs to audit each other mutually with anticollusion (any CSP is not willing to help other CSPs conceal data problems). Then, we design an audit protocol to achieve public audit efficiently with low cost of audit verification. Rigorous analysis explains the security of PMAB using game theory, and performance analysis shows the efficiency of PMAB using the real-world dataset.


---

## Body

## 1. Introduction

With the rapid technological advancements in Internet of Things (IoT), more terminals and better transmission efficiency also mean that mass data is generated while providing more convenience [1]. Massive terminal data and limited storage capacity make these IoT applications have to turn to Cloud Service Providers (CSPs) to obtain professional data storage support as Data Owners (DOs). In other words, technological advancements promote the integration of cloud services and IoT. In particular, cloud services are located in the data layer of IoT and interact with application servers to provide data services [2].However, cloud services not only provide convenience for IoT but also challenge the privacy and security of data generated by terminals [3, 4]. As the data is stored in the cloud, the Data Owner will lose the strong control over the data. CSPs may be damaged by external threats, such as hacking or natural disasters, and even they may tamper with data for their own benefit. These external and internal attacks can damage the integrity of remote data [5]. If the integrity of data cannot be audited in time, with the damaged data being used for key calculation or operation, incalculable disaster will be triggered. The remote outsourcing data audit technology can assure the data integrity with only a small amount of interaction, which can just solve the above-mentioned security problems.In 2008, Ateniese et al. [6] first proposed a partially dynamic Provable Data Possession (PDP) protocol. As a classic remote outsourcing data audit technology, PDP later developed the characteristics of dynamic audit, batch verification, and public audit [7–11]. The traditional public audit involves the interaction between multiple parties, which leads to the trust problem. For example, centralized storage makes audit results easy to be tampered with, TPA may help CSPs conceal data problems for profit, and so on.The problem of multiparty trust in traditional data integrity audit makes it an inevitable trend to integrate blockchain technology into data integrity audit [12]. Yue et al. [12] and Liu et al. [13], respectively, proposed the prototype of data integrity audit framework combining IoT and P2P cloud storage environment with blockchain, but its application scenarios are relatively limited. Yu et al. [14] used blockchain for audit proof storage, and the Data Owner completed the audit of data integrity by verifying the audit proof stored on blockchain. Xu et al. [15] used blockchain to arbitrate disputed audit results. Huang et al. [16] completed verification of audit tasks and record of dynamic operations through representative nodes of the consortium chain built by PBFT consensus. Lu et al. [17] used Fabric (Consortium Blockchain) to store audit records and proposed a reputation system for TPA. TPA is an entity that makes profit through audit. The remuneration paid by DOs to TPA must be less than the actual value of the audited data; otherwise, the audit will be meaningless. Therefore, TPA is easy to be bribed by the benefits (more than audit remuneration but less than data value) paid by malicious CSP. In this case, collusion attacks are difficult to avoid.Fan et al. [18] proposed an automated audit architecture based on Ethereum (Common Blockchain), which uses smart contracts to perform audit tasks and pay related compensation. Although Common Blockchain can effectively avoid collusion attacks because of its large scale of consensus nodes and effective incentive mechanism, it is difficult to reach an acceptable execution efficiency under larger-scale audit verification. Despite the fact that Consortium Blockchain is more efficient, there still exists the nothing-at-the-attack [19]. Without an effective incentive mechanism, collusion attacks will not be well resisted. PMAB is based on Consortium Blockchain and ensures mutual supervision through effective credit-based incentive mechanism, which strengthens the supervision of CSPs while auditing data. In [18], Verifiable Delay Function (VDF) is used to realize automatic audit; that is, the system automatically generates secure random source to generate audit challenge without DOs’ participation, which further reduces the cost of DOs. However, the security of the random source comes from the continuous computing power consumption, which is not efficient enough. Therefore, due to the lack of customized blockchain design for audit protocol, the existing schemes still suffer from excessive overheads and collusion attacks.To tackle the above challenges, we propose a Public Mutual Auditing Blockchain (PMAB) for outsourced data in cloud storage to solve collusion attacks in the public audit scheme, greatly reduce the audit cost, and improve the audit efficiency. The contributions of this paper can be summarized as follows:(i)
We present a customized blockchain architecture PMAB for public audit, which enables all CSPs to automatically audit each other through audit contract and releases DOs from data audit cost(ii)
We propose a credit-based incentive mechanism to resist collusion attacks while quantifying behaviors of entities(iii)
We put forward a consensus for PMAB that combines an efficient public audit protocol. After rigorous security and performance analysis, our scheme can achieve expected security goal and audit efficiency significantly ahead of existing schemesThe outline of this paper is as follows: we first introduce the background knowledge, the system model, threat model, and design goals. In the latter, we describe the concrete constructions of PMAB and audit protocol. After that, security and performance analyses are detailed. Finally, the summary and future work of this paper are presented.


## 2. Preliminaries

### 2.1. Ouroboros

Ouroboros is a kind of blockchain consensus based on Proof of Stake (PoS), which was proposed by Kiayias et al. [20] and proved secure. It uses Publicly Verifiable Secret Sharing Scheme (PVSS) [21] to generate antibiased random numbers as random source of the representative election algorithm Follow the Satoshi (FTS), so that the candidate can be elected as the representative node with a certain probability, which is equal to the proportion of the candidate’s stake to the overall stake of all candidates.


## 2.1. Ouroboros

Ouroboros is a kind of blockchain consensus based on Proof of Stake (PoS), which was proposed by Kiayias et al. [20] and proved secure. It uses Publicly Verifiable Secret Sharing Scheme (PVSS) [21] to generate antibiased random numbers as random source of the representative election algorithm Follow the Satoshi (FTS), so that the candidate can be elected as the representative node with a certain probability, which is equal to the proportion of the candidate’s stake to the overall stake of all candidates.


## 3. Problem Statement

### 3.1. System Model

PMAB considers a public data audit scenario for outsourced data in cloud storage, which is mainly composed of Data Owner (DO), Cloud Service Providers (CSPs), and Regulator (R) as shown in Figure1. Audit chain and credit chain are two distributed ledgers maintained by CSPs and R, which, respectively, record audit information and credit of each entity. After outsourcing data to CSPs, DO (e.g., an IoT application collects data via their terminals) generates the audit contract with CSPs and R (Steps 1 and 2). In public audit, the audited CSP provides proof to the audit chain according to the challenge (Steps 3 and 4); then some CSPs complete audit verification and credit settlement under the supervision of R (Step 5). Finally, DO can obtain audit and credit settlement results through these two distributed ledgers (Step 6). The specific roles of all entities in PMAB are described as follows:(i)
DO has limited communication, computation, and storage resources. It outsources data to CSPs and achieves public audit with PMAB(ii)
CSP provides DOs with significant storage space and computation capability. It is also responsible for maintaining two distributed ledgers, while responding proof to challenges and completing public audit(iii)
R is also responsible for maintaining two distributed ledgers while supervising public audit process and administrating PMABFigure 1
System model of PMAB.


### 3.2. Threat Model

PMAB considers that some corrupted CSPs will try to bribe other CSPs to conceal their data problem in audit verification. DO is honest but curious; it will try to obtain the identity and audited outsourcing data of other DOs based on the audit information from audit chain.R is assumed to be a trustworthy regulatory agency that supervises cloud storage services.


### 3.3. Design Goals

To achieve secure and efficient automated data audit under the above threat model, PMAB should achieve the following goals about anticollusion, privacy preserving, efficiency, automated audit, and dynamic audit:Anticollusion. PMAB should prevent corrupted CSPs from passing audit verification through collusion attacksPrivacy Preserving. Except for R, CSP, and DO participating in the audit contract, all other entities cannot obtain the specific identity and outsourced data information of the DOAntiforgery. The audit proof forged by malicious CSP cannot pass the audit verificationAntireplace. For malicious CSP, when generating audit proof, it cannot use the combination of intact data block related information to get the proof of damaged data blockEfficiency. The average cost of batch audit in the audit protocol of PMAB should be limited to a very low and constant level, and the overall verification and the consensus time of PMAB should be controlled within a limited timeAutomated Audit. PMAB should achieve automatic audit periodically based on audit contractsDynamic Audit. The remote data that is modified dynamically can be audited timely and effectively


## 3.1. System Model

PMAB considers a public data audit scenario for outsourced data in cloud storage, which is mainly composed of Data Owner (DO), Cloud Service Providers (CSPs), and Regulator (R) as shown in Figure1. Audit chain and credit chain are two distributed ledgers maintained by CSPs and R, which, respectively, record audit information and credit of each entity. After outsourcing data to CSPs, DO (e.g., an IoT application collects data via their terminals) generates the audit contract with CSPs and R (Steps 1 and 2). In public audit, the audited CSP provides proof to the audit chain according to the challenge (Steps 3 and 4); then some CSPs complete audit verification and credit settlement under the supervision of R (Step 5). Finally, DO can obtain audit and credit settlement results through these two distributed ledgers (Step 6). The specific roles of all entities in PMAB are described as follows:(i)
DO has limited communication, computation, and storage resources. It outsources data to CSPs and achieves public audit with PMAB(ii)
CSP provides DOs with significant storage space and computation capability. It is also responsible for maintaining two distributed ledgers, while responding proof to challenges and completing public audit(iii)
R is also responsible for maintaining two distributed ledgers while supervising public audit process and administrating PMABFigure 1
System model of PMAB.


## 3.2. Threat Model

PMAB considers that some corrupted CSPs will try to bribe other CSPs to conceal their data problem in audit verification. DO is honest but curious; it will try to obtain the identity and audited outsourcing data of other DOs based on the audit information from audit chain.R is assumed to be a trustworthy regulatory agency that supervises cloud storage services.


## 3.3. Design Goals

To achieve secure and efficient automated data audit under the above threat model, PMAB should achieve the following goals about anticollusion, privacy preserving, efficiency, automated audit, and dynamic audit:Anticollusion. PMAB should prevent corrupted CSPs from passing audit verification through collusion attacksPrivacy Preserving. Except for R, CSP, and DO participating in the audit contract, all other entities cannot obtain the specific identity and outsourced data information of the DOAntiforgery. The audit proof forged by malicious CSP cannot pass the audit verificationAntireplace. For malicious CSP, when generating audit proof, it cannot use the combination of intact data block related information to get the proof of damaged data blockEfficiency. The average cost of batch audit in the audit protocol of PMAB should be limited to a very low and constant level, and the overall verification and the consensus time of PMAB should be controlled within a limited timeAutomated Audit. PMAB should achieve automatic audit periodically based on audit contractsDynamic Audit. The remote data that is modified dynamically can be audited timely and effectively


## 4. Public Mutual Audit Blockchain

### 4.1. Design Overview of PMAB

As the analysis above, all public audit schemes based on blockchain cannot audit efficiently and resist collusion attacks at the same time.In PMAB, we innovatively use the mutual audit between CSPs instead of TPA’s audit. According to the game theory, we design an incentive mechanism based on credit, so that no CSP is willing to help other CSPs conceal data problems. Furthermore, based on Ouroboros [20], we design an audit protocol that combines with the blockchain consensus to efficiently and automatically complete public audits.Therefore, the description of PMAB is mainly divided into two parts: basic blockchain structure and audit protocol.


### 4.2. Basic Blockchain Structure of PMAB

Blockchain architecture is the basic design of PMAB, which is mainly composed of two parts, namely, credit chain and audit chain. In this part, we will introduce the core of credit chain (i.e., the incentive mechanism) and the basic data structure in audit chain.


#### 4.2.1. Incentive Mechanism

Incentive mechanism is the power source and security cornerstone of blockchain system. The credit valuecredit is the core of PMAB incentive mechanism, which mainly comes from CSPs’ initial Credit, deposit, and audit remuneration reward paid by DOs. The candidate node with higher credit is more likely to be elected as a representative node. Moreover, the credit lost by collusion will outweigh the creditgained, and rational CSPs will conduct honest audits to maximize benefits. Some key concepts related to creditare described below:(i)
initialCredit. When each CSP joins PMAB, it needs to pay some deposits in exchange for initialCredit, which will be confiscated when the malicious behavior of this CSP is found. Only when initial Credit reaches the threshold can it become a candidate node.(ii)
deposit. When the audit contract is constructed, the CSP needs to mortgage deposit, of which dataValue and penalty are equal in half.(iii)
dataValue. As the compensation that CSP pays to DO when audit fails, it represents the value of data.(iv)
penalty. As a fine for the malicious behavior of CSP when being audited.(v)
bonusPool. All forfeited initialCredit and penalty will be put into bonusPool, and the honest CSPs participating in the audit will divide up bonusPool.


#### 4.2.2. Block and AuditContract

Block and AuditContract are basic data structure in audit chain. Block stores the contents and results of each audit. AuditContract keeps the specific information of each audit task. The whole contract is stored in R, the associated DO, and CSP, all CSPs just keep conHeader, which determines the audit task information of each consensus.The structures ofBlock and AuditContract are shown in Figures 2(a) and 2(b). Descriptions of key fields are as follows:(i)
nonce. A random value obtained by PVSS [21] in Ouroboros [20] is used as random source for this audit(ii)
proof. All audit proofs collected by the representative node during the audit(iii)
auditCons. The collection of audit tasks covered in this audit(iv)
verResult. The results of this audit(v)
ConPk. The public key to be used in the audit verification(vi)
auditRate. The proportion of audited data to outsourced data(vii)
Rproof. A proof of the overall stored data provided by RFigure 2
The structure ofBlock and AuditContract. (a) The structure of Block. (b) The structure of AuditContract.
(a)(b)


### 4.3. High Description of Audit Protocol

This part focuses on the audit protocol of PMAB, which is divided into Setup phase and Audit phase. There are system parameters initialization and audit preparation in Setup phase. Audit phase includes the generation and verification of audit proof, as well as credit settlement. In addition, in order to verify the remote data of dynamic operation in time, PMAB supports dynamic audit.


#### 4.3.1. Setup Phase

In this phase, the system parameters are first initialized inKeyGen. Then CSPs join PMAB in SystemIni. After DO preprocesses files which will be outsourced and uploads them to CSP in FileToCSP, the AuditContract is constructed by DO, CSP, and R in AuditConGen.KeyGen. With a security parameter λ, two elliptic curve groups G1 and G2 and a multiplicative group GT of the large prime order p, a bilinear pairing e:G1×G2⟶GT, a field Zp of residue classes modulo p, two random generators g1∈G1 and g2∈G2, a pseudorandom permutation (PRP) π⋅, and a pseudorandom function (PRF) f⋅ are picked.(1)Sℙ=G1,G2,GT,g1,g2,e,π,f.Furthermore, for the convenience of expression,σϵ⋅ is used to represent a signature signed by entity ϵ and IDϵ is used to represent the unique identicator of entity ϵ.SystemIni. After the new CSP exchanges initialCreditIcr from R, R broadcasts new node access notification NAN=t,IDCSP,CSPaddress,Icr,σRNAN to all CSP nodes, where t is the timestamp and CSPaddress is the network address of new CSP. After receiving the NAN, other CSP nodes establish the connection with new node.FileToCSP. Assuming that the file that DO needs to store isF, DO divides Finto following data blocks:F=m1,m2,…,mi,…,mn,i∈1,n,mi∈Zp. DO generates a random parameter ωF∈Zp∗ for F, thereby obtaining the verification random number set RF=ri,i∈1,n, where ri=fωFi. Then sk=α∈Zp∗ is randomly selected as audit private key; thereby BLS homomorphic verification tags σi=g1mi+riα for each data block mi are generated, thereby obtaining a tag set σ=σi,i∈1,n. Finally, DO sends a tag collection message TC=t,F,σ,σDOTC to the CSP that stores outsourced data.AuditConGen. Assuming that DO and CSP have negotiated deposit, auditRate, auditTime, and other information for AuditContract, DO generates audit public key ConPk=g2α and sends RF to R. After R generatesRproof=g1r1+r2+…+rn, CSP fills all information in the AuditContract, especiallysign=σCSP|DO|RAuditContract. Then DO can delete F and σ locally. After receiving con=t,IDR,ConHeader,σRcon, each CSP stores ConHeader in local contract collection Con.


#### 4.3.2. Audit Phase

This part mainly focuses on the detailed process of data audit. Before each round of audit, the CSP whoseinitialCredit reaches the threshold will participate in representative election as a candidate. After PVSS and FTS [17, 18], we get random source Random and a representative Rep, and other candidates become endorsers Endo. After the audited CSP obtains the audit proof P through ProofGen based on Random, PMAB completes the audit consensus and appends Block to audit chain in AuditConsensus. After CreSettlement, audit result verResult is added to audit chain and credit is updated to credit chain. Finally, DO can obtain audit results related to itself from audit chain. For ease of understanding, the following description is based on a scenario, where a CSP is audited by multiple DOs.ProofGen. After obtaining the random Source Random, each CSP checks whether it needs to be audited this round based on local contract collectionCon. If it does, the corresponding challenge set chal will be calculated according to Random, and the audit proof set P will be generated.CSP first generates two keysk1=fRandomheight andk2=fRandomheight+1. The audit contract set ConCache=Contractjj∈1,K that needs to be executed by the CSP in this round is generated, where K represents the number of audit contracts in ConCache. According to auditRatej of Contractj in ConCache and the actual size nj of the audited file, the number of challenged blocks for this audit contract zj is computed as zj=⌈auditRatej×nj⌉. Furthermore, the challenge set of current round Chal=chaljj∈1,K of the CSP is obtained, where chalj=il,vl,il=πk1l,vl=fk2l,l∈1,zj. CSP then calculates the tag proof TPj=∏chaljσilvl and the data block proof DPj=g1∑chaljmil⋅vl corresponding to each chalj, thereby forming the tag proof set Φ=∏ChalTPj and the data block proof set μ=DPjj∈1,K. Finally, the proof set P=Φ,μ of the CSP is obtained.AuditConsensus. As shown in Figure 3 an audit consensus is conducted after ProofGen. First, the audited CSP sends its own proof message proof=t,P,σCSPproof to Rep and Endo nodes. Rep packs received proof into a message proofs=t,P,σRepproofs and broadcasts it to all Endo nodes, where N represents the number of nodes that need to execute audit contracts. After receivingproofs, Endo nodes compare it to proof they received; if proof is included in proofs, they will pack the message response=t,proofs,σEndoresponse and send it to Rep. After collecting allresponse, Rep packs the message RproofRequest=t,responsess∈1,N,σCSPRepRproofRequest and sends it to R. To verify RproofRequest, R compares proofs of all response in RproofRequest. If they are the same, R will calculate the random number proof proofR=ξss∈1,N required for this round of proof consensus, where ξs=RPj=g1∑chaljril⋅vlj∈1,K, and then package message RproofResponse=t,proofR,σRRproofResponse and send it to Rep.Figure 3
The process for generating newBlock.Then,Rep fills RproofRequest|RproofResponse in proofs, ConCache in auditCons, Random in nonce, and so on while generating a new Block.Finally,Block is broadcast to all CSPs and R.CreSettlement. After AuditConsensus, all Endo and Rep nodes verify the proof P to audit the outsourced data. The verification operation is to verify whether the following equation holds for audited CSP.(2)eΦ,g2=∏ConCacheeDPj⋅RPj,ConPkj.If it holds,Ver=true; otherwise, Ver=false. Then message verify=t,Ver,σRep/Endoverify is sent to R.After receiving allverify, R verifies whether there are different verification results. If all verify are the same, verification result set RVer and the malicious nodes set Mal will be empty (i.e, all Endo and Rep are honest); otherwise, R will use equation (2) to further verify proofs for the dispute and then get RVer=verifyss∈1,A and Mal=IDEndos/Repss∈1,M, where A represents the number of disputed proofs and Mrepresents the number of malicious nodes. After receiving ack=Verss∈1,N,RVer,Mal,t,σRack from R, all nodes put it into verResult of the corresponding Block in audit chain. Then all CSPs and R will conduct credit settlement based onack. First, the total reward totalReward of all executed audit contracts in ConCache is calculated and put in bonusPool, and the DO in the audit contract is compensated for data corruption. If dataValue, Mal is not empty, all initialCredits of the CSP and penalty in the corresponding audit contract involved are put into bonusPool. Finally, credit in bonusPool will be obtained by virtuous Endo and Rep (Rep can get an extra part).To prove the correctness of audit process, equation (2) can be derived as follows:(3)eΦ,g2=e∏Chal∏ChalJg1mil+rilαjvl,g2=∏ConCachee∏chaljg1mil+rilvl,g2αj=∏ConCacheeg∑chaljmil⋅vl+∑chaljril⋅vl,ConPkj=∏ConCacheeDPj⋅RPj,ConPkj.


#### 4.3.3. Dynamic Audit

EMAB supports dynamic auditing; that is, it supports DO in auditing data after dynamical operations, which mainly consist of insertion, modification, and deletion. The details are described below.(i)
Insertion. Suppose that DO wants to insert a data block mj in file F, j is the index position to be inserted, and 1≤j≤n+1, where nrepresents the number of data blocks of origin F. DO updates the local FIT data (the auxiliary data linked list corresponding to file F) and inserts the new node Bj=n+1,rj=fωFn+1 into the j−th position of FIT. DO calculates the BLS-HVT σj=g1mj+rjα of mj and sends the message insert=t,j,mj,σj,σDOinsert to the CSP to help update mj and σj. The message updateRproof=t,j,rj,σDOupdateRproof is sent to R to help update RF.(ii)
Modification. Suppose that DO wants to update the data block mj in file F. The message update=t,j,mj,σj,σDOupdate is sent to the CSP to help it update the data block mj and BLS-HVT σj, where σj=g1mj+rjα.(iii)
Deletion. Suppose that DO wants to delete data block mj in file F. DO moves the j−th node in F’s FIT to the end of the chain and sets its Bj to −1. The message delete=t,j,σDOdelete is sent to CSP to help it delete the corresponding data block mj and BLS-HVT σj. The message deleteRproof=t,j,σDOdeleteRproof is sent to R to help it delete the corresponding random number element rj.All dynamic operation records are stored in the dynamic operation domain of corresponding audit contract after all participants sign. In the following audit consensus, all new data will be applied.


## 4.1. Design Overview of PMAB

As the analysis above, all public audit schemes based on blockchain cannot audit efficiently and resist collusion attacks at the same time.In PMAB, we innovatively use the mutual audit between CSPs instead of TPA’s audit. According to the game theory, we design an incentive mechanism based on credit, so that no CSP is willing to help other CSPs conceal data problems. Furthermore, based on Ouroboros [20], we design an audit protocol that combines with the blockchain consensus to efficiently and automatically complete public audits.Therefore, the description of PMAB is mainly divided into two parts: basic blockchain structure and audit protocol.


## 4.2. Basic Blockchain Structure of PMAB

Blockchain architecture is the basic design of PMAB, which is mainly composed of two parts, namely, credit chain and audit chain. In this part, we will introduce the core of credit chain (i.e., the incentive mechanism) and the basic data structure in audit chain.


### 4.2.1. Incentive Mechanism

Incentive mechanism is the power source and security cornerstone of blockchain system. The credit valuecredit is the core of PMAB incentive mechanism, which mainly comes from CSPs’ initial Credit, deposit, and audit remuneration reward paid by DOs. The candidate node with higher credit is more likely to be elected as a representative node. Moreover, the credit lost by collusion will outweigh the creditgained, and rational CSPs will conduct honest audits to maximize benefits. Some key concepts related to creditare described below:(i)
initialCredit. When each CSP joins PMAB, it needs to pay some deposits in exchange for initialCredit, which will be confiscated when the malicious behavior of this CSP is found. Only when initial Credit reaches the threshold can it become a candidate node.(ii)
deposit. When the audit contract is constructed, the CSP needs to mortgage deposit, of which dataValue and penalty are equal in half.(iii)
dataValue. As the compensation that CSP pays to DO when audit fails, it represents the value of data.(iv)
penalty. As a fine for the malicious behavior of CSP when being audited.(v)
bonusPool. All forfeited initialCredit and penalty will be put into bonusPool, and the honest CSPs participating in the audit will divide up bonusPool.


### 4.2.2. Block and AuditContract

Block and AuditContract are basic data structure in audit chain. Block stores the contents and results of each audit. AuditContract keeps the specific information of each audit task. The whole contract is stored in R, the associated DO, and CSP, all CSPs just keep conHeader, which determines the audit task information of each consensus.The structures ofBlock and AuditContract are shown in Figures 2(a) and 2(b). Descriptions of key fields are as follows:(i)
nonce. A random value obtained by PVSS [21] in Ouroboros [20] is used as random source for this audit(ii)
proof. All audit proofs collected by the representative node during the audit(iii)
auditCons. The collection of audit tasks covered in this audit(iv)
verResult. The results of this audit(v)
ConPk. The public key to be used in the audit verification(vi)
auditRate. The proportion of audited data to outsourced data(vii)
Rproof. A proof of the overall stored data provided by RFigure 2
The structure ofBlock and AuditContract. (a) The structure of Block. (b) The structure of AuditContract.
(a)(b)


## 4.2.1. Incentive Mechanism

Incentive mechanism is the power source and security cornerstone of blockchain system. The credit valuecredit is the core of PMAB incentive mechanism, which mainly comes from CSPs’ initial Credit, deposit, and audit remuneration reward paid by DOs. The candidate node with higher credit is more likely to be elected as a representative node. Moreover, the credit lost by collusion will outweigh the creditgained, and rational CSPs will conduct honest audits to maximize benefits. Some key concepts related to creditare described below:(i)
initialCredit. When each CSP joins PMAB, it needs to pay some deposits in exchange for initialCredit, which will be confiscated when the malicious behavior of this CSP is found. Only when initial Credit reaches the threshold can it become a candidate node.(ii)
deposit. When the audit contract is constructed, the CSP needs to mortgage deposit, of which dataValue and penalty are equal in half.(iii)
dataValue. As the compensation that CSP pays to DO when audit fails, it represents the value of data.(iv)
penalty. As a fine for the malicious behavior of CSP when being audited.(v)
bonusPool. All forfeited initialCredit and penalty will be put into bonusPool, and the honest CSPs participating in the audit will divide up bonusPool.


## 4.2.2. Block and AuditContract

Block and AuditContract are basic data structure in audit chain. Block stores the contents and results of each audit. AuditContract keeps the specific information of each audit task. The whole contract is stored in R, the associated DO, and CSP, all CSPs just keep conHeader, which determines the audit task information of each consensus.The structures ofBlock and AuditContract are shown in Figures 2(a) and 2(b). Descriptions of key fields are as follows:(i)
nonce. A random value obtained by PVSS [21] in Ouroboros [20] is used as random source for this audit(ii)
proof. All audit proofs collected by the representative node during the audit(iii)
auditCons. The collection of audit tasks covered in this audit(iv)
verResult. The results of this audit(v)
ConPk. The public key to be used in the audit verification(vi)
auditRate. The proportion of audited data to outsourced data(vii)
Rproof. A proof of the overall stored data provided by RFigure 2
The structure ofBlock and AuditContract. (a) The structure of Block. (b) The structure of AuditContract.
(a)(b)


## 4.3. High Description of Audit Protocol

This part focuses on the audit protocol of PMAB, which is divided into Setup phase and Audit phase. There are system parameters initialization and audit preparation in Setup phase. Audit phase includes the generation and verification of audit proof, as well as credit settlement. In addition, in order to verify the remote data of dynamic operation in time, PMAB supports dynamic audit.


### 4.3.1. Setup Phase

In this phase, the system parameters are first initialized inKeyGen. Then CSPs join PMAB in SystemIni. After DO preprocesses files which will be outsourced and uploads them to CSP in FileToCSP, the AuditContract is constructed by DO, CSP, and R in AuditConGen.KeyGen. With a security parameter λ, two elliptic curve groups G1 and G2 and a multiplicative group GT of the large prime order p, a bilinear pairing e:G1×G2⟶GT, a field Zp of residue classes modulo p, two random generators g1∈G1 and g2∈G2, a pseudorandom permutation (PRP) π⋅, and a pseudorandom function (PRF) f⋅ are picked.(1)Sℙ=G1,G2,GT,g1,g2,e,π,f.Furthermore, for the convenience of expression,σϵ⋅ is used to represent a signature signed by entity ϵ and IDϵ is used to represent the unique identicator of entity ϵ.SystemIni. After the new CSP exchanges initialCreditIcr from R, R broadcasts new node access notification NAN=t,IDCSP,CSPaddress,Icr,σRNAN to all CSP nodes, where t is the timestamp and CSPaddress is the network address of new CSP. After receiving the NAN, other CSP nodes establish the connection with new node.FileToCSP. Assuming that the file that DO needs to store isF, DO divides Finto following data blocks:F=m1,m2,…,mi,…,mn,i∈1,n,mi∈Zp. DO generates a random parameter ωF∈Zp∗ for F, thereby obtaining the verification random number set RF=ri,i∈1,n, where ri=fωFi. Then sk=α∈Zp∗ is randomly selected as audit private key; thereby BLS homomorphic verification tags σi=g1mi+riα for each data block mi are generated, thereby obtaining a tag set σ=σi,i∈1,n. Finally, DO sends a tag collection message TC=t,F,σ,σDOTC to the CSP that stores outsourced data.AuditConGen. Assuming that DO and CSP have negotiated deposit, auditRate, auditTime, and other information for AuditContract, DO generates audit public key ConPk=g2α and sends RF to R. After R generatesRproof=g1r1+r2+…+rn, CSP fills all information in the AuditContract, especiallysign=σCSP|DO|RAuditContract. Then DO can delete F and σ locally. After receiving con=t,IDR,ConHeader,σRcon, each CSP stores ConHeader in local contract collection Con.


### 4.3.2. Audit Phase

This part mainly focuses on the detailed process of data audit. Before each round of audit, the CSP whoseinitialCredit reaches the threshold will participate in representative election as a candidate. After PVSS and FTS [17, 18], we get random source Random and a representative Rep, and other candidates become endorsers Endo. After the audited CSP obtains the audit proof P through ProofGen based on Random, PMAB completes the audit consensus and appends Block to audit chain in AuditConsensus. After CreSettlement, audit result verResult is added to audit chain and credit is updated to credit chain. Finally, DO can obtain audit results related to itself from audit chain. For ease of understanding, the following description is based on a scenario, where a CSP is audited by multiple DOs.ProofGen. After obtaining the random Source Random, each CSP checks whether it needs to be audited this round based on local contract collectionCon. If it does, the corresponding challenge set chal will be calculated according to Random, and the audit proof set P will be generated.CSP first generates two keysk1=fRandomheight andk2=fRandomheight+1. The audit contract set ConCache=Contractjj∈1,K that needs to be executed by the CSP in this round is generated, where K represents the number of audit contracts in ConCache. According to auditRatej of Contractj in ConCache and the actual size nj of the audited file, the number of challenged blocks for this audit contract zj is computed as zj=⌈auditRatej×nj⌉. Furthermore, the challenge set of current round Chal=chaljj∈1,K of the CSP is obtained, where chalj=il,vl,il=πk1l,vl=fk2l,l∈1,zj. CSP then calculates the tag proof TPj=∏chaljσilvl and the data block proof DPj=g1∑chaljmil⋅vl corresponding to each chalj, thereby forming the tag proof set Φ=∏ChalTPj and the data block proof set μ=DPjj∈1,K. Finally, the proof set P=Φ,μ of the CSP is obtained.AuditConsensus. As shown in Figure 3 an audit consensus is conducted after ProofGen. First, the audited CSP sends its own proof message proof=t,P,σCSPproof to Rep and Endo nodes. Rep packs received proof into a message proofs=t,P,σRepproofs and broadcasts it to all Endo nodes, where N represents the number of nodes that need to execute audit contracts. After receivingproofs, Endo nodes compare it to proof they received; if proof is included in proofs, they will pack the message response=t,proofs,σEndoresponse and send it to Rep. After collecting allresponse, Rep packs the message RproofRequest=t,responsess∈1,N,σCSPRepRproofRequest and sends it to R. To verify RproofRequest, R compares proofs of all response in RproofRequest. If they are the same, R will calculate the random number proof proofR=ξss∈1,N required for this round of proof consensus, where ξs=RPj=g1∑chaljril⋅vlj∈1,K, and then package message RproofResponse=t,proofR,σRRproofResponse and send it to Rep.Figure 3
The process for generating newBlock.Then,Rep fills RproofRequest|RproofResponse in proofs, ConCache in auditCons, Random in nonce, and so on while generating a new Block.Finally,Block is broadcast to all CSPs and R.CreSettlement. After AuditConsensus, all Endo and Rep nodes verify the proof P to audit the outsourced data. The verification operation is to verify whether the following equation holds for audited CSP.(2)eΦ,g2=∏ConCacheeDPj⋅RPj,ConPkj.If it holds,Ver=true; otherwise, Ver=false. Then message verify=t,Ver,σRep/Endoverify is sent to R.After receiving allverify, R verifies whether there are different verification results. If all verify are the same, verification result set RVer and the malicious nodes set Mal will be empty (i.e, all Endo and Rep are honest); otherwise, R will use equation (2) to further verify proofs for the dispute and then get RVer=verifyss∈1,A and Mal=IDEndos/Repss∈1,M, where A represents the number of disputed proofs and Mrepresents the number of malicious nodes. After receiving ack=Verss∈1,N,RVer,Mal,t,σRack from R, all nodes put it into verResult of the corresponding Block in audit chain. Then all CSPs and R will conduct credit settlement based onack. First, the total reward totalReward of all executed audit contracts in ConCache is calculated and put in bonusPool, and the DO in the audit contract is compensated for data corruption. If dataValue, Mal is not empty, all initialCredits of the CSP and penalty in the corresponding audit contract involved are put into bonusPool. Finally, credit in bonusPool will be obtained by virtuous Endo and Rep (Rep can get an extra part).To prove the correctness of audit process, equation (2) can be derived as follows:(3)eΦ,g2=e∏Chal∏ChalJg1mil+rilαjvl,g2=∏ConCachee∏chaljg1mil+rilvl,g2αj=∏ConCacheeg∑chaljmil⋅vl+∑chaljril⋅vl,ConPkj=∏ConCacheeDPj⋅RPj,ConPkj.


### 4.3.3. Dynamic Audit

EMAB supports dynamic auditing; that is, it supports DO in auditing data after dynamical operations, which mainly consist of insertion, modification, and deletion. The details are described below.(i)
Insertion. Suppose that DO wants to insert a data block mj in file F, j is the index position to be inserted, and 1≤j≤n+1, where nrepresents the number of data blocks of origin F. DO updates the local FIT data (the auxiliary data linked list corresponding to file F) and inserts the new node Bj=n+1,rj=fωFn+1 into the j−th position of FIT. DO calculates the BLS-HVT σj=g1mj+rjα of mj and sends the message insert=t,j,mj,σj,σDOinsert to the CSP to help update mj and σj. The message updateRproof=t,j,rj,σDOupdateRproof is sent to R to help update RF.(ii)
Modification. Suppose that DO wants to update the data block mj in file F. The message update=t,j,mj,σj,σDOupdate is sent to the CSP to help it update the data block mj and BLS-HVT σj, where σj=g1mj+rjα.(iii)
Deletion. Suppose that DO wants to delete data block mj in file F. DO moves the j−th node in F’s FIT to the end of the chain and sets its Bj to −1. The message delete=t,j,σDOdelete is sent to CSP to help it delete the corresponding data block mj and BLS-HVT σj. The message deleteRproof=t,j,σDOdeleteRproof is sent to R to help it delete the corresponding random number element rj.All dynamic operation records are stored in the dynamic operation domain of corresponding audit contract after all participants sign. In the following audit consensus, all new data will be applied.


## 4.3.1. Setup Phase

In this phase, the system parameters are first initialized inKeyGen. Then CSPs join PMAB in SystemIni. After DO preprocesses files which will be outsourced and uploads them to CSP in FileToCSP, the AuditContract is constructed by DO, CSP, and R in AuditConGen.KeyGen. With a security parameter λ, two elliptic curve groups G1 and G2 and a multiplicative group GT of the large prime order p, a bilinear pairing e:G1×G2⟶GT, a field Zp of residue classes modulo p, two random generators g1∈G1 and g2∈G2, a pseudorandom permutation (PRP) π⋅, and a pseudorandom function (PRF) f⋅ are picked.(1)Sℙ=G1,G2,GT,g1,g2,e,π,f.Furthermore, for the convenience of expression,σϵ⋅ is used to represent a signature signed by entity ϵ and IDϵ is used to represent the unique identicator of entity ϵ.SystemIni. After the new CSP exchanges initialCreditIcr from R, R broadcasts new node access notification NAN=t,IDCSP,CSPaddress,Icr,σRNAN to all CSP nodes, where t is the timestamp and CSPaddress is the network address of new CSP. After receiving the NAN, other CSP nodes establish the connection with new node.FileToCSP. Assuming that the file that DO needs to store isF, DO divides Finto following data blocks:F=m1,m2,…,mi,…,mn,i∈1,n,mi∈Zp. DO generates a random parameter ωF∈Zp∗ for F, thereby obtaining the verification random number set RF=ri,i∈1,n, where ri=fωFi. Then sk=α∈Zp∗ is randomly selected as audit private key; thereby BLS homomorphic verification tags σi=g1mi+riα for each data block mi are generated, thereby obtaining a tag set σ=σi,i∈1,n. Finally, DO sends a tag collection message TC=t,F,σ,σDOTC to the CSP that stores outsourced data.AuditConGen. Assuming that DO and CSP have negotiated deposit, auditRate, auditTime, and other information for AuditContract, DO generates audit public key ConPk=g2α and sends RF to R. After R generatesRproof=g1r1+r2+…+rn, CSP fills all information in the AuditContract, especiallysign=σCSP|DO|RAuditContract. Then DO can delete F and σ locally. After receiving con=t,IDR,ConHeader,σRcon, each CSP stores ConHeader in local contract collection Con.


## 4.3.2. Audit Phase

This part mainly focuses on the detailed process of data audit. Before each round of audit, the CSP whoseinitialCredit reaches the threshold will participate in representative election as a candidate. After PVSS and FTS [17, 18], we get random source Random and a representative Rep, and other candidates become endorsers Endo. After the audited CSP obtains the audit proof P through ProofGen based on Random, PMAB completes the audit consensus and appends Block to audit chain in AuditConsensus. After CreSettlement, audit result verResult is added to audit chain and credit is updated to credit chain. Finally, DO can obtain audit results related to itself from audit chain. For ease of understanding, the following description is based on a scenario, where a CSP is audited by multiple DOs.ProofGen. After obtaining the random Source Random, each CSP checks whether it needs to be audited this round based on local contract collectionCon. If it does, the corresponding challenge set chal will be calculated according to Random, and the audit proof set P will be generated.CSP first generates two keysk1=fRandomheight andk2=fRandomheight+1. The audit contract set ConCache=Contractjj∈1,K that needs to be executed by the CSP in this round is generated, where K represents the number of audit contracts in ConCache. According to auditRatej of Contractj in ConCache and the actual size nj of the audited file, the number of challenged blocks for this audit contract zj is computed as zj=⌈auditRatej×nj⌉. Furthermore, the challenge set of current round Chal=chaljj∈1,K of the CSP is obtained, where chalj=il,vl,il=πk1l,vl=fk2l,l∈1,zj. CSP then calculates the tag proof TPj=∏chaljσilvl and the data block proof DPj=g1∑chaljmil⋅vl corresponding to each chalj, thereby forming the tag proof set Φ=∏ChalTPj and the data block proof set μ=DPjj∈1,K. Finally, the proof set P=Φ,μ of the CSP is obtained.AuditConsensus. As shown in Figure 3 an audit consensus is conducted after ProofGen. First, the audited CSP sends its own proof message proof=t,P,σCSPproof to Rep and Endo nodes. Rep packs received proof into a message proofs=t,P,σRepproofs and broadcasts it to all Endo nodes, where N represents the number of nodes that need to execute audit contracts. After receivingproofs, Endo nodes compare it to proof they received; if proof is included in proofs, they will pack the message response=t,proofs,σEndoresponse and send it to Rep. After collecting allresponse, Rep packs the message RproofRequest=t,responsess∈1,N,σCSPRepRproofRequest and sends it to R. To verify RproofRequest, R compares proofs of all response in RproofRequest. If they are the same, R will calculate the random number proof proofR=ξss∈1,N required for this round of proof consensus, where ξs=RPj=g1∑chaljril⋅vlj∈1,K, and then package message RproofResponse=t,proofR,σRRproofResponse and send it to Rep.Figure 3
The process for generating newBlock.Then,Rep fills RproofRequest|RproofResponse in proofs, ConCache in auditCons, Random in nonce, and so on while generating a new Block.Finally,Block is broadcast to all CSPs and R.CreSettlement. After AuditConsensus, all Endo and Rep nodes verify the proof P to audit the outsourced data. The verification operation is to verify whether the following equation holds for audited CSP.(2)eΦ,g2=∏ConCacheeDPj⋅RPj,ConPkj.If it holds,Ver=true; otherwise, Ver=false. Then message verify=t,Ver,σRep/Endoverify is sent to R.After receiving allverify, R verifies whether there are different verification results. If all verify are the same, verification result set RVer and the malicious nodes set Mal will be empty (i.e, all Endo and Rep are honest); otherwise, R will use equation (2) to further verify proofs for the dispute and then get RVer=verifyss∈1,A and Mal=IDEndos/Repss∈1,M, where A represents the number of disputed proofs and Mrepresents the number of malicious nodes. After receiving ack=Verss∈1,N,RVer,Mal,t,σRack from R, all nodes put it into verResult of the corresponding Block in audit chain. Then all CSPs and R will conduct credit settlement based onack. First, the total reward totalReward of all executed audit contracts in ConCache is calculated and put in bonusPool, and the DO in the audit contract is compensated for data corruption. If dataValue, Mal is not empty, all initialCredits of the CSP and penalty in the corresponding audit contract involved are put into bonusPool. Finally, credit in bonusPool will be obtained by virtuous Endo and Rep (Rep can get an extra part).To prove the correctness of audit process, equation (2) can be derived as follows:(3)eΦ,g2=e∏Chal∏ChalJg1mil+rilαjvl,g2=∏ConCachee∏chaljg1mil+rilvl,g2αj=∏ConCacheeg∑chaljmil⋅vl+∑chaljril⋅vl,ConPkj=∏ConCacheeDPj⋅RPj,ConPkj.


## 4.3.3. Dynamic Audit

EMAB supports dynamic auditing; that is, it supports DO in auditing data after dynamical operations, which mainly consist of insertion, modification, and deletion. The details are described below.(i)
Insertion. Suppose that DO wants to insert a data block mj in file F, j is the index position to be inserted, and 1≤j≤n+1, where nrepresents the number of data blocks of origin F. DO updates the local FIT data (the auxiliary data linked list corresponding to file F) and inserts the new node Bj=n+1,rj=fωFn+1 into the j−th position of FIT. DO calculates the BLS-HVT σj=g1mj+rjα of mj and sends the message insert=t,j,mj,σj,σDOinsert to the CSP to help update mj and σj. The message updateRproof=t,j,rj,σDOupdateRproof is sent to R to help update RF.(ii)
Modification. Suppose that DO wants to update the data block mj in file F. The message update=t,j,mj,σj,σDOupdate is sent to the CSP to help it update the data block mj and BLS-HVT σj, where σj=g1mj+rjα.(iii)
Deletion. Suppose that DO wants to delete data block mj in file F. DO moves the j−th node in F’s FIT to the end of the chain and sets its Bj to −1. The message delete=t,j,σDOdelete is sent to CSP to help it delete the corresponding data block mj and BLS-HVT σj. The message deleteRproof=t,j,σDOdeleteRproof is sent to R to help it delete the corresponding random number element rj.All dynamic operation records are stored in the dynamic operation domain of corresponding audit contract after all participants sign. In the following audit consensus, all new data will be applied.


## 5. Security Analysis

In this part, we mainly analyze anticollusion, privacy preserving, antiforgery, and antireplace described in Section3.3.


### 5.1. Anticollusion

PMAB can resist collusion attacks from consensus nodes (Rep and Endo). Colluding nodes cannot deceive R by sending wrong verify to bypass corrupted data blocks. They definitely betray each other because honest behavior is more profitable than collusion.Because consensus nodes will sendverify to R at the same time in each round of audit consensus, this process can be regarded as a static and complete information game. For simplicity, we take two consensus nodes, namely, player1 and player2, for example. Suppose that v1 and v2 are dataValue of player1 and player2, respectively, p1 and p2 are initialCredit (and penalty) of player1 and player2v1<p1,v1<p2,v2<p1,v2<p1, m, 0<m<v2 is the cost of bribery, and u is the reward of audit.The game elements are as follows:(i)
playersplayer1,player2(ii)
strategyhonest,malicious(iii)
utilityProfit matrix when both players have data problems and only player2 has data problems as Tables 1 and 2 show, respectivelyTable 1
Profit matrix when bothplayers have data problems.
player2honestmaliciousplayer1honestu−v1, u−v2p2+u−v1, u−p2−v2maliciousu−p1−v1, p1+u−v2u,uTable 2
Profit matrix when onlyplayer2 has data problems.
player2honestmaliciousplayer1honestu,u−v2,p2+u, u−p2−v2maliciousu−p1, p1+u−v2u+m,u−mWhen both players have data problems, forplayer2, it is easy to know u−v2>u−p2−v2 andp1+u−v2>u, so honest must be the dominant strategy of player2. Similarly, it is easy to know that for, player1, honest is also the dominant strategy. So, the Nash equilibrium point in this case falls in case (honest, honest). Therefore, in this case, no collusion problem occurs. When only player2 has data problems, for player2, it is easy to know u−v2>u−p2−v2 and p1+u−v2>u−m , so honest must be the dominant strategy of player2. For player1, it is easy to know u>u−p1 and P2+u>u+m, so honest must be the dominant strategy of player1. So the Nash equilibrium point in this case falls in case (honest, honest). Therefore, in this case, no collusion problem occurs.The situation of more players is similar to the situation of two players. In summary, PMAB can avoid collusion problems.


### 5.2. Privacy Preserving

Apart fromR and audited CSP, all other CSPs cannot obtain the relationship between audit tasks and DOs from Con, and the specific data block information from P, that is, PMAB, can protect DO’s identity privacy and data privacy.Identity Privacy Protection. All ConHeader are stored in CSPs’ local contract collection Con. Only the audit public key ConPk in ConHeader is associated with DO, but ConPk of each ConHeader of DO can be different. If there is no duplicate ConPk, it is impossible to get the association between ConPk and DO. So the privacy of the DO’s identity is protected.Data Privacy Protection. In the audit consensus, it is difficult for the consensus nodes to obtain ∑chaljmil⋅vl from DPj=g1∑chaljmil⋅vl because of DLP. Moreover, even if ∑chaljmil⋅vl is given, the specific information of mil cannot be solved out without knowing the number of mil⋅vl. Therefore, PMAB can ensure that consensus nodes cannot obtain the data information of the audit data during the verification process, which protects data privacy.


### 5.3. Antiforgery

If the data blockmi within chal has been modified to mi+offi by the CSP, where offi denotes the modification part, to adapt the new DP∗, a new TP∗ should be computed as follows:(4)TP∗=∏chalg1mil+ril+offilskvl=∏chalg1mil+rilsk⋅g1offilskvl=∏chalσilvl⋅g1sk⋅∑chaloffil⋅vl=TP⋅g1sk⋅∑chaloffil⋅vl.Because this CSP only ownsTP, it needs to know sk for obtaining TP∗. However, sk is a private key of the DO. In our assumption, sk cannot be obtained by others. Hence, the audit proof cannot be forged by a CSP, and PMAB can resist forgery attack.


### 5.4. Antireplace

Suppose that a corrupted data blockmj has been checked, and two data blocks mj1 andmj2 are intact. To obtain the HVT of mj, the correct combination of σj1 and σj2 should be found. Since σj1=g1mj1+rj1ask,σj2=g1mj2+rj2sk, a CSP sets that(5)σj∗=σj1αj1⋅σj2αj2=g1mj1+rj1skαj1⋅g1mj2+rj2skαj2=g1αj1⋅mj1+rj1+αj2⋅mj2+rj2sk,where αj1,αj2∈Zp. If σj∗ is to be equal to σj, αj1⋅mj1+rj1+αj2⋅mj2+rj2=mj+rj must be satisfied. In order to meet this requirement, rj1, rj2, and rj must be known. But CSP cannot get them based on the information it already has. For example, if g1, mj, and g1mj+rjsk are known, it is required to solve rj. rj is unknown, so rj+mj is also unknown. If g1 is given, solving rj+mj from g1mj+rjsk is a DLP problem. So in polynomial time the probability of solving rj is negligible.Similarly, solvingrj1 and rj2 is the same as solving rj. So replace attack from CSP can be resisted in EMAB.


## 5.1. Anticollusion

PMAB can resist collusion attacks from consensus nodes (Rep and Endo). Colluding nodes cannot deceive R by sending wrong verify to bypass corrupted data blocks. They definitely betray each other because honest behavior is more profitable than collusion.Because consensus nodes will sendverify to R at the same time in each round of audit consensus, this process can be regarded as a static and complete information game. For simplicity, we take two consensus nodes, namely, player1 and player2, for example. Suppose that v1 and v2 are dataValue of player1 and player2, respectively, p1 and p2 are initialCredit (and penalty) of player1 and player2v1<p1,v1<p2,v2<p1,v2<p1, m, 0<m<v2 is the cost of bribery, and u is the reward of audit.The game elements are as follows:(i)
playersplayer1,player2(ii)
strategyhonest,malicious(iii)
utilityProfit matrix when both players have data problems and only player2 has data problems as Tables 1 and 2 show, respectivelyTable 1
Profit matrix when bothplayers have data problems.
player2honestmaliciousplayer1honestu−v1, u−v2p2+u−v1, u−p2−v2maliciousu−p1−v1, p1+u−v2u,uTable 2
Profit matrix when onlyplayer2 has data problems.
player2honestmaliciousplayer1honestu,u−v2,p2+u, u−p2−v2maliciousu−p1, p1+u−v2u+m,u−mWhen both players have data problems, forplayer2, it is easy to know u−v2>u−p2−v2 andp1+u−v2>u, so honest must be the dominant strategy of player2. Similarly, it is easy to know that for, player1, honest is also the dominant strategy. So, the Nash equilibrium point in this case falls in case (honest, honest). Therefore, in this case, no collusion problem occurs. When only player2 has data problems, for player2, it is easy to know u−v2>u−p2−v2 and p1+u−v2>u−m , so honest must be the dominant strategy of player2. For player1, it is easy to know u>u−p1 and P2+u>u+m, so honest must be the dominant strategy of player1. So the Nash equilibrium point in this case falls in case (honest, honest). Therefore, in this case, no collusion problem occurs.The situation of more players is similar to the situation of two players. In summary, PMAB can avoid collusion problems.


## 5.2. Privacy Preserving

Apart fromR and audited CSP, all other CSPs cannot obtain the relationship between audit tasks and DOs from Con, and the specific data block information from P, that is, PMAB, can protect DO’s identity privacy and data privacy.Identity Privacy Protection. All ConHeader are stored in CSPs’ local contract collection Con. Only the audit public key ConPk in ConHeader is associated with DO, but ConPk of each ConHeader of DO can be different. If there is no duplicate ConPk, it is impossible to get the association between ConPk and DO. So the privacy of the DO’s identity is protected.Data Privacy Protection. In the audit consensus, it is difficult for the consensus nodes to obtain ∑chaljmil⋅vl from DPj=g1∑chaljmil⋅vl because of DLP. Moreover, even if ∑chaljmil⋅vl is given, the specific information of mil cannot be solved out without knowing the number of mil⋅vl. Therefore, PMAB can ensure that consensus nodes cannot obtain the data information of the audit data during the verification process, which protects data privacy.


## 5.3. Antiforgery

If the data blockmi within chal has been modified to mi+offi by the CSP, where offi denotes the modification part, to adapt the new DP∗, a new TP∗ should be computed as follows:(4)TP∗=∏chalg1mil+ril+offilskvl=∏chalg1mil+rilsk⋅g1offilskvl=∏chalσilvl⋅g1sk⋅∑chaloffil⋅vl=TP⋅g1sk⋅∑chaloffil⋅vl.Because this CSP only ownsTP, it needs to know sk for obtaining TP∗. However, sk is a private key of the DO. In our assumption, sk cannot be obtained by others. Hence, the audit proof cannot be forged by a CSP, and PMAB can resist forgery attack.


## 5.4. Antireplace

Suppose that a corrupted data blockmj has been checked, and two data blocks mj1 andmj2 are intact. To obtain the HVT of mj, the correct combination of σj1 and σj2 should be found. Since σj1=g1mj1+rj1ask,σj2=g1mj2+rj2sk, a CSP sets that(5)σj∗=σj1αj1⋅σj2αj2=g1mj1+rj1skαj1⋅g1mj2+rj2skαj2=g1αj1⋅mj1+rj1+αj2⋅mj2+rj2sk,where αj1,αj2∈Zp. If σj∗ is to be equal to σj, αj1⋅mj1+rj1+αj2⋅mj2+rj2=mj+rj must be satisfied. In order to meet this requirement, rj1, rj2, and rj must be known. But CSP cannot get them based on the information it already has. For example, if g1, mj, and g1mj+rjsk are known, it is required to solve rj. rj is unknown, so rj+mj is also unknown. If g1 is given, solving rj+mj from g1mj+rjsk is a DLP problem. So in polynomial time the probability of solving rj is negligible.Similarly, solvingrj1 and rj2 is the same as solving rj. So replace attack from CSP can be resisted in EMAB.


## 6. Performance Analysis

In this part, we focus on the theoretical and experimental analyses of PMAB’s performance through comparing them with similar schemes: Dredas [18], Fabric [17], and CAB [16]. The notations used in the performance analysis are shown in Table 3.Table 3
Notation definitions of performance analysis.
NotationDescriptionHHash function mapping a string to a point onG1 and G2.EModular exponentiation onG1 and G2.PBilinear pairing operation ofe.MPoint multiplication onG1 and G2.nThe total number of data blocks outsourced.zThe number of challenged data blocks.


### 6.1. Theoretical Analysis

The comparison of entities’ computation cost with Dredas [18], Fabric [17], and CAB [16], also supporting public audit by blockchain, is shown in Table 4.Table 4
Comparison of computation cost.
SchemesDOCSPTPAConsensus nodeDredasnH+2nE+nMzH+2z+1E+2z−1M—2E+2P+2MFabricnH+2nE+nMzE+2z−1M2P+z+1E+zM—CABnH+2nE+nMzE+2z−1M—zH+z+1E+3P+zMPMAB2nEz+1E+z−1M—2P+MComputation overheads are mainly distributed inFileToCSP, ProofGen, and AuditConsensus in the comparison. In order to provide the reference for comparison, we test 1000 times and then obtain the average cost of each operation; that is, H=18.98ms,E=9.64ms,P=4.63ms, and M=2.51ms. From Table 4, we can see that the DO and consensus node in the PMAB cost much less. Firstly, in FileToCSP, DO generates tags for all data blocks to be uploaded. In this part, compared with all other schemes, nH+nM operations are avoided in PMAB. Then, in ProofGen, audited CSP computes challenges and corresponding proofs. In this part, zM−E operations are avoided in PMAB, compared with other fastest schemes. Finally, in AuditConsensus, the smart contract in Dredas [18], the TPA in Fabric [17], or each consensus node in CAB [16] and PMAB verifies the correctness of proofs. Proof verification is the core part of public audit, and it is also the efficiency bottleneck of the whole public audit. In this part, the verification cost of Fabric and CAB increases linearly, while the verification cost of Dredas [18] and PMAB remains at a lower and constant level, and furthermore PMAB avoids 2E+M operations compared with Dredas [18].


### 6.2. Experimental Analysis

We evaluate performance of PMAB by conducting several experiments using JDK 1.8 on Ubuntu 16.04 system equipped with Intel Core i5-8400 CPU at 2.3 GHz and 4 GB RAM. We also use Docker to virtualize different nodes. WebSocket and Netty are used for TCP and HTTP communication, respectively. All pairing operations and related calculations on an elliptic curve are implemented with JPBC library v2.0.0 and type A pairing parameters, in which the group order is set to 160 bits and the base field order is 512 bits. The signature algorithm is implemented by the identity-based signature in [22] with JPBC library. The hash algorithm implemented is SHA-512 in BouncyCastle library. The encryption and decryption algorithm uses RSA-1024 in the security library JCE (Java Cryptography Extension) of Java. The test datasets stem from China-Brazil Earth Resources Satellite (CBERS) on Amazon Web Service (AWS). The image files in CBERS are converted to Cloud Optimized GeoTIFF format in order to optimize its use for cloud-based applications. Each test file is divided into 10,000 4 KB data blocks. According to LFT (Loss Function Theory) presented in [12], the optimal balance between the high detection probability and the low verification cost can be achieved by challenging a limited number of data blocks. Therefore, the sample size of data blocks in our experiments is changed from 50 to 500.FileToCSPTime. Figure 4 shows the computation cost of DO in FileToCSP. With the sample size increasing, it is obvious that the growth rate of FileToCSP’s computation cost in PMAB (0.91 s∼8.85 s) is less than half as much as other schemes (1.85 s∼18.21 s).Figure 4
The computation cost comparison inFileToCSP.ProofGenTime. Figure 5 shows audited CSP’s computation cost during generating audit proof. Dredas [18] takes significantly more time (1.81 s∼18.04 s) because there are many heavy operations such as H and E on G in the proof generation, while the proof generation times of PMAB and the remaining schemes are almost the same (0.45 s∼4.54 s).Figure 5
The computation cost comparison inProofGenTime.AuditVerifyTime. Figure 6 shows the verification time of the TPA in Fabric [17] and the consensus node in Dredas [18], CAB [16], and PMAB spend, respectively, where the verification time of Dredas [18] and PMAB ranges from 0.019 s to 0.034 s and the verification time of Fabric [17] and CAB [16] ranges from 1.36 s to 13.44 s. It is obvious that there is a linear relationship between the number of challenged blocks and the verification time of Fabric [17] and CAB [16], while the verification times of Dredas [18] and PMAB tend to be 27 ms and 20 ms, respectively. Thanks to less expensive operations such as H and E, our verification cost is more acceptable to each involved verifier compared with other schemes.Figure 6
The verification cost comparison inAuditVerifyTime.BatchAuditTime. In Figure 7, we compare the batch auditing with Dredas [18], Fabric [17], and CAB [16] under the condition that each DO challenges the same CSP with 250 data blocks in a challenge set. The average audit time of Dredas [18] and PMAB ranges from 0.007 s to 0.028 s, and the average audit time of Fabric [17] and CAB [16] ranges from 6.679 s to 6.83 s. It is obvious that, with the increase in the number of aggregated audit tasks, the average audit time cost of Fabric [17] and CAB [16] fluctuates between 6.8 s and 6.9 s, while Dredas [18] and PMAB tend to 0.02 s and 0.005 s, respectively. PMAB is four times faster than the fastest of other schemes in average audit time of the batch audit. Considering that the single validation time of PMAB in Figure 6 is only one-third faster than that of Dredas [18], our batch audit efficiency is higher.Figure 7
The computation cost comparison inBatchAuditTime.RandomGenTime. In each consensus of the blockchain, a random source will be obtained to complete the current round of audit tasks, that is, automatic audit. The random sources in Dredas [18] are generated by a verifiable random function (VRF). In order to ensure the freshness and security of the generated random source, CSP needs to execute VRF by taking the nonce of the new Ethereum block as a seed, until the block is fully confirmed by the Ethereum network; that is, the block cannot be tampered with afterwards. Then the VRF is terminated, and the corresponding random source is obtained. The smart contract verifies the validity of the random source before using it. However, the validation process can be divided into K parallel tasks by using K process states provided by CSP, so the validation time is 1/K of the generation time. According to [23], the average time to generate a new block in Ethereum is 14 s. Generally, eight blocks are generated before the block is confirmed by the network, so it takes at least 112 s to get the random source. Assuming K = 100, that is, there are 100 parallel verification processes, the verification takes nearly 2 s. Therefore, the random source generation time of Dredas [18] is constant at 114 s. In the random source generation process of our scheme, each consensus node has to send and process 2n−1 messages (n is the number of consensus nodes) and do n hash operations and n−1 encryption operations. If a node does not send open, each node should decrypt Eiopeni it receives to solve this case. Figure 8 shows the comparison between PMAB and Dredas [18] in terms of the random source generation time, where the time cost of PMAB ranges from 0.25 s to 3 s and the time cost of Dredas [18] is always 114 s. The time cost of our random source generation method (PVSS [21]) increases linearly and slowly with increase in the number of consensus nodes. We roughly estimate that it will take more than 3000 consensus nodes to spend as much random source generation time as Dredas [18]. However, PMAB uses the threshold of initialCredit to limit the number of consensus nodes. Only a few consensus nodes are required to complete PVSS [21] and audit consensus. Therefore, PMAB’s random source generation is more efficient.Figure 8
The random source generation time comparison inRandomGenTime.ParallGenProof. In the face of large-scale audit case, according to the formation processes of Φ andμ, our protocol in PMAB actually supports parallel generation and aggregation of audit proofs employing MapReduce principle [24]. CSP will divide the whole task of proof generation into small tasks of the same scale for parallel execution and then aggregate the results of single tasks. We set 10 audit tasks as a group and make CSP process the audit proof generation process in parallel, testing the change of proof generation time when the number of audit tasks grows from 100 to 1000, in which 250 data blocks were questioned for each audit task. As shown in Figure 9, it is clear that when CSP is faced with a large number of requests, it proves that the generation time is nearly constant (22.68 s) and does not affect the consensus overhead of PMAB.Figure 9
The computation cost inParallGenProof.ConsensusTime. As shown in Figure 10, we test the time variation of PMAB’s AuditConsensus per round as the number of CSPs increased (from 20 to 200). Each CSP node has 1000 audit tasks and each audit task challenged 250 data blocks. It is obvious that the time of PMAB’s audit consensus tends to be constant (27.03 s) with the increase of the number of CSPs, since only a limited number of consensus nodes are needed to complete the audit consensus (the number of consensus nodes in this experiment is limited to less than 100). Therefore, PMAB has strong scalability and stability.Figure 10
The communication cost inConsensusTime.


## 6.1. Theoretical Analysis

The comparison of entities’ computation cost with Dredas [18], Fabric [17], and CAB [16], also supporting public audit by blockchain, is shown in Table 4.Table 4
Comparison of computation cost.
SchemesDOCSPTPAConsensus nodeDredasnH+2nE+nMzH+2z+1E+2z−1M—2E+2P+2MFabricnH+2nE+nMzE+2z−1M2P+z+1E+zM—CABnH+2nE+nMzE+2z−1M—zH+z+1E+3P+zMPMAB2nEz+1E+z−1M—2P+MComputation overheads are mainly distributed inFileToCSP, ProofGen, and AuditConsensus in the comparison. In order to provide the reference for comparison, we test 1000 times and then obtain the average cost of each operation; that is, H=18.98ms,E=9.64ms,P=4.63ms, and M=2.51ms. From Table 4, we can see that the DO and consensus node in the PMAB cost much less. Firstly, in FileToCSP, DO generates tags for all data blocks to be uploaded. In this part, compared with all other schemes, nH+nM operations are avoided in PMAB. Then, in ProofGen, audited CSP computes challenges and corresponding proofs. In this part, zM−E operations are avoided in PMAB, compared with other fastest schemes. Finally, in AuditConsensus, the smart contract in Dredas [18], the TPA in Fabric [17], or each consensus node in CAB [16] and PMAB verifies the correctness of proofs. Proof verification is the core part of public audit, and it is also the efficiency bottleneck of the whole public audit. In this part, the verification cost of Fabric and CAB increases linearly, while the verification cost of Dredas [18] and PMAB remains at a lower and constant level, and furthermore PMAB avoids 2E+M operations compared with Dredas [18].


## 6.2. Experimental Analysis

We evaluate performance of PMAB by conducting several experiments using JDK 1.8 on Ubuntu 16.04 system equipped with Intel Core i5-8400 CPU at 2.3 GHz and 4 GB RAM. We also use Docker to virtualize different nodes. WebSocket and Netty are used for TCP and HTTP communication, respectively. All pairing operations and related calculations on an elliptic curve are implemented with JPBC library v2.0.0 and type A pairing parameters, in which the group order is set to 160 bits and the base field order is 512 bits. The signature algorithm is implemented by the identity-based signature in [22] with JPBC library. The hash algorithm implemented is SHA-512 in BouncyCastle library. The encryption and decryption algorithm uses RSA-1024 in the security library JCE (Java Cryptography Extension) of Java. The test datasets stem from China-Brazil Earth Resources Satellite (CBERS) on Amazon Web Service (AWS). The image files in CBERS are converted to Cloud Optimized GeoTIFF format in order to optimize its use for cloud-based applications. Each test file is divided into 10,000 4 KB data blocks. According to LFT (Loss Function Theory) presented in [12], the optimal balance between the high detection probability and the low verification cost can be achieved by challenging a limited number of data blocks. Therefore, the sample size of data blocks in our experiments is changed from 50 to 500.FileToCSPTime. Figure 4 shows the computation cost of DO in FileToCSP. With the sample size increasing, it is obvious that the growth rate of FileToCSP’s computation cost in PMAB (0.91 s∼8.85 s) is less than half as much as other schemes (1.85 s∼18.21 s).Figure 4
The computation cost comparison inFileToCSP.ProofGenTime. Figure 5 shows audited CSP’s computation cost during generating audit proof. Dredas [18] takes significantly more time (1.81 s∼18.04 s) because there are many heavy operations such as H and E on G in the proof generation, while the proof generation times of PMAB and the remaining schemes are almost the same (0.45 s∼4.54 s).Figure 5
The computation cost comparison inProofGenTime.AuditVerifyTime. Figure 6 shows the verification time of the TPA in Fabric [17] and the consensus node in Dredas [18], CAB [16], and PMAB spend, respectively, where the verification time of Dredas [18] and PMAB ranges from 0.019 s to 0.034 s and the verification time of Fabric [17] and CAB [16] ranges from 1.36 s to 13.44 s. It is obvious that there is a linear relationship between the number of challenged blocks and the verification time of Fabric [17] and CAB [16], while the verification times of Dredas [18] and PMAB tend to be 27 ms and 20 ms, respectively. Thanks to less expensive operations such as H and E, our verification cost is more acceptable to each involved verifier compared with other schemes.Figure 6
The verification cost comparison inAuditVerifyTime.BatchAuditTime. In Figure 7, we compare the batch auditing with Dredas [18], Fabric [17], and CAB [16] under the condition that each DO challenges the same CSP with 250 data blocks in a challenge set. The average audit time of Dredas [18] and PMAB ranges from 0.007 s to 0.028 s, and the average audit time of Fabric [17] and CAB [16] ranges from 6.679 s to 6.83 s. It is obvious that, with the increase in the number of aggregated audit tasks, the average audit time cost of Fabric [17] and CAB [16] fluctuates between 6.8 s and 6.9 s, while Dredas [18] and PMAB tend to 0.02 s and 0.005 s, respectively. PMAB is four times faster than the fastest of other schemes in average audit time of the batch audit. Considering that the single validation time of PMAB in Figure 6 is only one-third faster than that of Dredas [18], our batch audit efficiency is higher.Figure 7
The computation cost comparison inBatchAuditTime.RandomGenTime. In each consensus of the blockchain, a random source will be obtained to complete the current round of audit tasks, that is, automatic audit. The random sources in Dredas [18] are generated by a verifiable random function (VRF). In order to ensure the freshness and security of the generated random source, CSP needs to execute VRF by taking the nonce of the new Ethereum block as a seed, until the block is fully confirmed by the Ethereum network; that is, the block cannot be tampered with afterwards. Then the VRF is terminated, and the corresponding random source is obtained. The smart contract verifies the validity of the random source before using it. However, the validation process can be divided into K parallel tasks by using K process states provided by CSP, so the validation time is 1/K of the generation time. According to [23], the average time to generate a new block in Ethereum is 14 s. Generally, eight blocks are generated before the block is confirmed by the network, so it takes at least 112 s to get the random source. Assuming K = 100, that is, there are 100 parallel verification processes, the verification takes nearly 2 s. Therefore, the random source generation time of Dredas [18] is constant at 114 s. In the random source generation process of our scheme, each consensus node has to send and process 2n−1 messages (n is the number of consensus nodes) and do n hash operations and n−1 encryption operations. If a node does not send open, each node should decrypt Eiopeni it receives to solve this case. Figure 8 shows the comparison between PMAB and Dredas [18] in terms of the random source generation time, where the time cost of PMAB ranges from 0.25 s to 3 s and the time cost of Dredas [18] is always 114 s. The time cost of our random source generation method (PVSS [21]) increases linearly and slowly with increase in the number of consensus nodes. We roughly estimate that it will take more than 3000 consensus nodes to spend as much random source generation time as Dredas [18]. However, PMAB uses the threshold of initialCredit to limit the number of consensus nodes. Only a few consensus nodes are required to complete PVSS [21] and audit consensus. Therefore, PMAB’s random source generation is more efficient.Figure 8
The random source generation time comparison inRandomGenTime.ParallGenProof. In the face of large-scale audit case, according to the formation processes of Φ andμ, our protocol in PMAB actually supports parallel generation and aggregation of audit proofs employing MapReduce principle [24]. CSP will divide the whole task of proof generation into small tasks of the same scale for parallel execution and then aggregate the results of single tasks. We set 10 audit tasks as a group and make CSP process the audit proof generation process in parallel, testing the change of proof generation time when the number of audit tasks grows from 100 to 1000, in which 250 data blocks were questioned for each audit task. As shown in Figure 9, it is clear that when CSP is faced with a large number of requests, it proves that the generation time is nearly constant (22.68 s) and does not affect the consensus overhead of PMAB.Figure 9
The computation cost inParallGenProof.ConsensusTime. As shown in Figure 10, we test the time variation of PMAB’s AuditConsensus per round as the number of CSPs increased (from 20 to 200). Each CSP node has 1000 audit tasks and each audit task challenged 250 data blocks. It is obvious that the time of PMAB’s audit consensus tends to be constant (27.03 s) with the increase of the number of CSPs, since only a limited number of consensus nodes are needed to complete the audit consensus (the number of consensus nodes in this experiment is limited to less than 100). Therefore, PMAB has strong scalability and stability.Figure 10
The communication cost inConsensusTime.


## 7. Conclusions

In this paper, PMAB for outsourced data in cloud storage was proposed. In PMAB, in order to achieve the goal of automatic audit safely, we constructed an audit chain architecture based on Ouroboros [20] and an incentive mechanism based on credit to allow CSPs to audit each other mutually with anticollusion. In addition, an audit protocol was designed to achieve public audit efficiently with low cost of audit verification. Security and performance analyses showed that PMAB achieves great audit efficiency and security goals. In future work, we will aim to research more specific incentive mechanism quantitative design and efficient problem positioning in batch audit.



---

*Source: 9993855-2021-06-02.xml*