# Differential Privacy-Based Double Auction for Data Market in Blockchain-Enhanced Internet of Things

Authors: Junhua Zhang; Caiming Zhong
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

With the rapid development of the Internet of Things (IoT), large amounts of data are collected, which constitute a valuable business resource. Hence, a suitable IoT data market needs to be established, and the provision of safe and effective trading services for multiple buyers and sellers is required. This paper introduces an IoT data market framework supported by blockchain. It focuses on a transaction realization scheme for multiple buyers and sellers. In the scheme, the mechanisms are designed to determine the corresponding data providers and recipients for the buyers and sellers, respectively, and the transaction prices of both parties. When the data market runs, an inference attack will raise bid information leakage issues. We study a transaction scheme that enables differential privacy protection of bids based on an exponential mechanism. This paper theoretically proves the individual rationality, weak budget balance, and truthfulness of the normal transaction scheme and differential privacy-based transaction scheme. This paper also theoretically proves the effectiveness of the differential privacy protection for bids of transaction participants. Furthermore, this paper verifies the performances of the two schemes through digital simulation experiments. From the experiments, we can also prove that these schemes occupy reasonable social welfare and computational overhead.


---

## Body

## 1. Introduction

With the widespread use of the Internet of Things (IoT), large amounts of data are collected and stored [1]. These are shared such as with data analysts, IoT service providers, and artificial intelligence developers, who wish to maximize their benefits [2], which has given rise to the IoT data market [3, 4]. This is generally online, allowing buyers and sellers to enter at any time, and it satisfies properties such as individual rationality and balanced budgets [5].Further analysis and decision-making based on the acquired data are needed to generate benefits for buyers. This requires the characteristics of data integrity, authenticity, and security. In addition, IoT data collection is often carried out by sensors at different locations, and data are stored nearby on a local edge server or base station. Therefore, distributed data transactions must conform to the characteristics of IoT data, in accordance with the characteristics of blockchain technology, and this has spurred interest in the research of blockchain-based IoT data market [6–9].The key problem in the IoT data market is how to efficiently and reasonably determine transaction prices [10–12]. Liu et al. [13] studied the price optimization mechanism in the data market in the context of blockchain-enhanced IoT, where the abstract objects are multiple sellers and one buyer, and a two-stage Stackelberg game is used to solve the pricing and purchasing problem of the data consumer and market agency. However, there are always multiple sellers and buyers, whose efficient pricing and purchases are a more general problem, which this paper approaches with a double auction.The current blockchain-based data market does not consider privacy leakage in transactions, which can easily lead to price information leakage under an inference attack [5]. The differential privacy-based method shows promise to prevent such leakage while ensuring lower computation and communication overhead and good auction performance. We adopt differential privacy in auctions to protect the commercial interests of both parties in a transaction.This paper addresses the above problems from three aspects:(1)
We describe the framework of a blockchain-enhanced IoT data market and propose a double-auction normal transaction method (DANTM) for multiple sellers and buyers(2)
To protect the price privacy of all parties, we upgrade DANTM to a double-auction transaction method based on differential privacy (DADPM). We demonstrate that our algorithms are individually rational, weakly budget-balanced, and truthful and prove that DADPM preserves the price privacy of buyers and sellers(3)
Simulations show that the proposed pricing schemes have the desired properties at a low time costThe remainder of this paper is structured as follows. Section2 reviews related research. Section 3 introduces a blockchain-enhanced IoT data market framework and a related data transaction model. Section 4 describes a double-auction scheme for data transactions in the IoT data market. Section 5 presents a differential privacy-based double-auction scheme. In Section 6, we evaluate our proposed schemes. We conclude our work in Section 7.


## 2. Related Work

With the development of the IoT, more and more data are collected from various IoT node devices, and these are important assets. IoT data have the requirements of real time and privacy, and related research of its market is proceeding [14, 15]. Blockchain, as an information infrastructure that provides transaction credibility and distribution, has been considered [16–19]. However, due to the limited resources of the IoT, related data markets supporting the application of blockchain technology are constructed by coordinating cloud and edge servers [13]. We present a data market framework and trading process in this context.Much effort has been made to develop secure, efficient, pricing models of low complexity for the IoT data market [13, 20–22]. Wang et al. [20] presented two pricing models for data transactions in device-to-device communication networks: a Stackelberg game based on one buyer and multiple sellers, and an alternative ascending clock auction based on one seller and multiple buyers. Liu et al. [13] formulated a two-stage Stackelberg game to solve the pricing and purchasing problem of one buyer and multiple sellers, considered competition between sellers, and proposed a competition-enhanced pricing scheme. However, there are no pricing models for multiple sellers and buyers in the IoT data market, which is the more general case.An auction market can be run fairly and efficiently via a trading process. A simple auction has one seller and multiple buyers, and a double auction has multiple sellers and buyers. From the perspective of resource trading, there is research on power and spectrum, adopting the pricing mode of an auction and sometimes considering the privacy protection of transaction information [5, 23]. Zhu and Shin [23] presented a differentially private and strategy-proof spectrum auction mechanism with approximate revenue maximization. Li et al. [5] proposed a differential privacy-based online double-auction scheme for energy trading in the smart grid, consisting of a Laplace-based winner determination rule and exponential-based allocation rule. There are certain differences between data and energy, as energy can only be consumed once, and data multiple times. There is no good or bad energy, but data have differences in quality. Our differential privacy-based double auction differs from previous schemes.


## 3. Framework, Model, and Desired Properties

### 3.1. Blockchain-Enhanced Data Market Framework for IoT

Figure1 displays the system architecture of a blockchain-enhanced IoT data market, targeting the challenges of security and efficiency. The components are IoT sensors and an edge server, base station, cloud server, and data user. IoT sensors collect original data and upload them to the edge server, which refines them and uploads them to a nearby base station, where they are stored for selling. Base stations are always connected to a cloud server through wired networks. The formal public data trading platform is set up on the cloud server. Data users can buy IoT data using a web browser. We set up blockchain on the base station and cloud server, using consortium blockchain for efficiency and data protection [24].Figure 1
System architecture of blockchain-enhanced IoT data market.In this system, base stations and cloud servers are the core part of the blockchain, in charge of commercial data storage and transactions. Base stations act as sellers, and users as buyers. Data trading rules are predefined in the blockchain as smart contracts. We design algorithms as data trading rules and protect the privacy of every participant. The IoT data market is a distributed system. Data can be sent from a base station directly to a buyer, which assures efficient trading. Blockchain records and stores transaction data and maintains the authenticity of transactions through its consensus mechanism. We adopt the proof-of-work (PoW) consensus protocol. Data transmission from seller to buyer can be assured by blockchain’s key mechanisms. The process of blockchain-enhanced IoT data trading is presented in Figure2.Figure 2
Trading process in IoT data market.We assume the following actions in Figure2 occur in a time slot:
(1)
Buyers (data users) and sellers (base stations) submit buying and selling requirements to the data trading platform (cloud server)(2)
The data trading platform runs data trading algorithms and decides on a trading scheme(3)
The first winning buyer (data user 1) and its data providers (base stations 1 and 2) are notified of the trading result(4)
The second winning buyer (data user 2) and its data providers (base stations 2 and 3) are notified of the trading result(5)
The first winning buyer (data user 1) and its data providers (base stations 1 and 2) directly implement data trading(6)
The second winning buyer (data user 2) and its data providers (base stations 2 and 3) directly implement data trading(7)
The blockchain network audits the transaction data


### 3.2. Designed Auction Model

n our data market, multiple buyers and sellers are involved in data transactions. A double-auction scheme is adopted to efficiently match the requirements of buyers and sellers. One trading process is finished in a time slot.Buyers and sellers that need data transactions in a time slot are referred to as active buyers and sellers. A data buyer’s bid information includes data kind, bid, data quality, and data quantity. A data seller’s asking information includes data kind, asking price, data quality, and data quantity.We assume below that the data market will match the data kind through a smart contract in blockchain, allow buyers and sellers of the same data kind to meet, and start the process of a double auction. Table1 lists the key notation used in our paper.Table 1
Notation.
SymbolDescriptionG, VSets of active buyers (G) and sellers (V) in slot tg, vAn active buyer (g) and seller (v) in slot tCg, PvSets of bids and asking pricescig, pivA bid and an asking priceDg, DvThe sets of data quality which are buyers’ requirements and sellers’ supplydig, divData quality, which is a buyer’s requirement and a seller’s supplyEg, EvSets of data quantity, which are buyers’ requirements and sellers’ supplyeg, evData quantity, which is a buyer’s requirement and a seller’s supplySg, SvSets of candidate buyers and sellersSwg, SwvSets of winning buyers and sellersfxtValid price for buyers (whenx=g) and sellers (when x=v) at slot tB, SSet of refined active buyers and sellersg¯A winning buyerp¯tg, p¯tvTrading price of winning buyerg and winning seller vDataTradingRecordData transaction result, including winning buyerg¯, trading price of g¯, data providers Swv, and whether requirement is satisfied (“yes” if ∑v∈Swvev−eg¯≥0), including winning sellers, trading prices, corresponding buyer, and amount of data providedqig, qivQuality value for candidate buyeri and seller iPrqig, PrqivProbability of being a winning buyer and seller


### 3.3. Desired Properties of Model

Definition 1. (Seller payoff).
The payoff to the winning seller for time slott is
(1)Utv=p¯tv−ptv⋅et.Definition 2. (Buyer payoff).
The payoff to the buyer in time slott is
(2)Utg=ctg−p¯tg⋅et.Definition 3. (Social welfare).
Social welfare in time slott is
(3)Utsw=∑v=1VUtv+∑g=1GUtg.Social Welfare Maximization: in double-auction markets, the goal is to maximize the total social welfare, i.e.,
(4)MaximizeUtsw,subjectto:et≤etv,∀v∈V;et≤etg,∀g∈G.Individual Rationality: each seller and buyer must receive a nonnegative payoff, i.e.,
(5)Utx≥0,wherextakesthevaluevorg.In other words, a winning seller is not rewarded with less than its asking priceptv, and a winning buyer must not be charged more than its bid ctg.Weak Budget Balance: for the data market in time slot t, if there exists
(6)∑g∈Gp¯tg⋅etg−∑v∈Vp¯tv⋅etv≥0,then the auction process satisfies the property of weak budget balance, which ensures that the auctioneer makes a tiny profit.Truthfulness: an auction is truthful if and only if
(7)Utxχtx≥Utxχ⟶tx,for each bidder i, whose true and false bids are χtx and χ⟶tx, respectively. This property ensures that bidders obtain their maximum payoff when and only when their truthful bids are reported.


## 3.1. Blockchain-Enhanced Data Market Framework for IoT

Figure1 displays the system architecture of a blockchain-enhanced IoT data market, targeting the challenges of security and efficiency. The components are IoT sensors and an edge server, base station, cloud server, and data user. IoT sensors collect original data and upload them to the edge server, which refines them and uploads them to a nearby base station, where they are stored for selling. Base stations are always connected to a cloud server through wired networks. The formal public data trading platform is set up on the cloud server. Data users can buy IoT data using a web browser. We set up blockchain on the base station and cloud server, using consortium blockchain for efficiency and data protection [24].Figure 1
System architecture of blockchain-enhanced IoT data market.In this system, base stations and cloud servers are the core part of the blockchain, in charge of commercial data storage and transactions. Base stations act as sellers, and users as buyers. Data trading rules are predefined in the blockchain as smart contracts. We design algorithms as data trading rules and protect the privacy of every participant. The IoT data market is a distributed system. Data can be sent from a base station directly to a buyer, which assures efficient trading. Blockchain records and stores transaction data and maintains the authenticity of transactions through its consensus mechanism. We adopt the proof-of-work (PoW) consensus protocol. Data transmission from seller to buyer can be assured by blockchain’s key mechanisms. The process of blockchain-enhanced IoT data trading is presented in Figure2.Figure 2
Trading process in IoT data market.We assume the following actions in Figure2 occur in a time slot:
(1)
Buyers (data users) and sellers (base stations) submit buying and selling requirements to the data trading platform (cloud server)(2)
The data trading platform runs data trading algorithms and decides on a trading scheme(3)
The first winning buyer (data user 1) and its data providers (base stations 1 and 2) are notified of the trading result(4)
The second winning buyer (data user 2) and its data providers (base stations 2 and 3) are notified of the trading result(5)
The first winning buyer (data user 1) and its data providers (base stations 1 and 2) directly implement data trading(6)
The second winning buyer (data user 2) and its data providers (base stations 2 and 3) directly implement data trading(7)
The blockchain network audits the transaction data


## 3.2. Designed Auction Model

n our data market, multiple buyers and sellers are involved in data transactions. A double-auction scheme is adopted to efficiently match the requirements of buyers and sellers. One trading process is finished in a time slot.Buyers and sellers that need data transactions in a time slot are referred to as active buyers and sellers. A data buyer’s bid information includes data kind, bid, data quality, and data quantity. A data seller’s asking information includes data kind, asking price, data quality, and data quantity.We assume below that the data market will match the data kind through a smart contract in blockchain, allow buyers and sellers of the same data kind to meet, and start the process of a double auction. Table1 lists the key notation used in our paper.Table 1
Notation.
SymbolDescriptionG, VSets of active buyers (G) and sellers (V) in slot tg, vAn active buyer (g) and seller (v) in slot tCg, PvSets of bids and asking pricescig, pivA bid and an asking priceDg, DvThe sets of data quality which are buyers’ requirements and sellers’ supplydig, divData quality, which is a buyer’s requirement and a seller’s supplyEg, EvSets of data quantity, which are buyers’ requirements and sellers’ supplyeg, evData quantity, which is a buyer’s requirement and a seller’s supplySg, SvSets of candidate buyers and sellersSwg, SwvSets of winning buyers and sellersfxtValid price for buyers (whenx=g) and sellers (when x=v) at slot tB, SSet of refined active buyers and sellersg¯A winning buyerp¯tg, p¯tvTrading price of winning buyerg and winning seller vDataTradingRecordData transaction result, including winning buyerg¯, trading price of g¯, data providers Swv, and whether requirement is satisfied (“yes” if ∑v∈Swvev−eg¯≥0), including winning sellers, trading prices, corresponding buyer, and amount of data providedqig, qivQuality value for candidate buyeri and seller iPrqig, PrqivProbability of being a winning buyer and seller


## 3.3. Desired Properties of Model

Definition 1. (Seller payoff).
The payoff to the winning seller for time slott is
(1)Utv=p¯tv−ptv⋅et.Definition 2. (Buyer payoff).
The payoff to the buyer in time slott is
(2)Utg=ctg−p¯tg⋅et.Definition 3. (Social welfare).
Social welfare in time slott is
(3)Utsw=∑v=1VUtv+∑g=1GUtg.Social Welfare Maximization: in double-auction markets, the goal is to maximize the total social welfare, i.e.,
(4)MaximizeUtsw,subjectto:et≤etv,∀v∈V;et≤etg,∀g∈G.Individual Rationality: each seller and buyer must receive a nonnegative payoff, i.e.,
(5)Utx≥0,wherextakesthevaluevorg.In other words, a winning seller is not rewarded with less than its asking priceptv, and a winning buyer must not be charged more than its bid ctg.Weak Budget Balance: for the data market in time slot t, if there exists
(6)∑g∈Gp¯tg⋅etg−∑v∈Vp¯tv⋅etv≥0,then the auction process satisfies the property of weak budget balance, which ensures that the auctioneer makes a tiny profit.Truthfulness: an auction is truthful if and only if
(7)Utxχtx≥Utxχ⟶tx,for each bidder i, whose true and false bids are χtx and χ⟶tx, respectively. This property ensures that bidders obtain their maximum payoff when and only when their truthful bids are reported.


## 4. DANTM

### 4.1. Double Auction with Valid Price Mechanism

We present the concept of a valid price.Definition 4. (Valid Price).
A valid price is a threshold value of a buyer’s bid and a seller’s asking price. It can determine whether a buyer or seller wins in an auction. A valid price is determined by bids, asking prices, and data quality of buyers and sellers.In a double-auction data market, active buyersG and sellers V in slot t submit their bidding information to the data market administrator, which can be realized in a smart contract in blockchain. The data market administrator assigns each buyer with seller-provided data through Algorithms 1–3 (see below). The following information is obtained for buyers: the winning buyer g¯ and its trading price, the data providers Swv, and whether its requirement is satisfied (i.e., whether ∑v∈Swvev−eg¯≥0). For sellers, the following information is obtained: the winning sellers, their trading price, the corresponding buyer, and the amount of data provided. The results are uniformly described by DataTradingRecord Algorithm 1 (DANTM) describing the auction scheme. We use Algorithm 2 to calculate the valid price for each active buyer and seller and use this to filter the active buyers G and sellers V to determine candidate participants Sg and Sv. We sort the candidate buyers in descending bid order and candidate sellers by ascending asking prices. We call Algorithm 3 to obtain a winning buyer g¯ (stored in Swg) and the related DataTradingRecord, delete that buyer from active buyers G, and serve the next active buyer.Algorithm 1: Double Auction with Valid Price Mechanism.
Input: active buyers and sellers G,V in slot t, and their bids (price, quality, and quantity) Pv,Cg,Dv,Dg,Eg,EvOutput: Data transaction result DataTradingRecord//InitializationSg⟵∅, Sv⟵∅, Swg⟵∅, DataTradingRecord⟵∅whileG−Swg≠∅doG⟵G−Swg, Swg⟵∅//Call Algorithm2 to calculate valid pricefxt=CalcValidPriceG,V,Cg,Pv,Dg,DvSg=g:cg≥fgt,∀g∈GSv=v:pv≤fvt,∀v∈VSg⟵sortcg in descending order, g∈SgSv⟵sortpv in ascending order, v∈Sv//Call Algorithm3 (normal method) for data tradingDataTradingRecord+,Swg=NormalTradeMethodSg,Sv,Cg,Pv,Eg,Evend


### 4.2. Valid Price Algorithm

Algorithm2 is used to calculate a valid price. We match the prices of active buyers and sellers in Cg,Pv to obtain the refined active buyers and sellers B,S, and call CalcValidPriceViaQuality (see below) to match the data quality of B,S among Dg,Dv, so as to select the proper prices of buyers and sellers and use them as valid price fxt for buyers (when x=g) and sellers (when x=v) at slot t.Algorithm 2:CalcValidPrice
Input: price and data quality of active buyers and sellers G,V,Cg,Px,Dg,Dv in slot tOutput: valid price fxt with x=vorg for data trading in slot tm=G; n=VSort prices of active buyers:c1g>c2g>⋯>cmgSort prices of active sellers:p1v<p2v<⋯<pnvifpnv≤cmgthenrefine active buyersB=1,2,⋯,,mrefine active sellersS=1,2,⋯,nelse ifclg≥pkv≥cl+1gthenrefine active buyersB=1,2,⋯,l, with 1≤l≤m−1refine active sellersS=1,2,⋯,k, with 1≤k≤nelse ifpk+1v≥crg≥pkvthenrefine active buyersB=1,2,⋯,r, with 1≤r≤mrefine active sellersS=1,2,⋯,k, with 1≤k≤n−1end//Call functionCalcValidPriceViaQuality to decide valid pricefxt=CalcValidPriceViaQualityB,S,Cg,Pv,Dg,DvreturnfxtThe functionCalcValidPriceViaQuality is as follows.FunctionCalcValidPriceViaQualityInput: price and data quality of refined active buyers and sellers B,S,Cg,Pv,Dg,Dv in slot tOutput: valid price fxt with x=vorg for data trading in slot tSort quality of refined active buyers inB as d1g<d2g<⋯<dy∗g, y∗=BSort quality of refined active sellers inS as d1v>d2v>⋯>ds∗v, s∗=Sifds∗v≥dy∗gthenfxt⟵minc1g,⋯,cy∗g,x=gmaxp1v,⋯,ps∗v,x=velse ifdw∗v≤dj∗g≤dw−1∗vthenfxt⟵cj∗g,x=gpw−1∗v,x=v with j∗∈1,2,⋯,y∗ and w∗∈2,3,⋯,s∗else ifdl∗g≤dk∗v≤dl+1∗gthenfxt⟵cl∗g,x=gpk∗v,x=v with l∗∈1,2,⋯,y−1∗ and k∗∈1,2,⋯,s∗endreturnfxtWe provide an intuitive explanation of Algorithm2 in Figure 3. To calculate the valid price, Algorithm 2 first ranks active buyers in descending order of price and active sellers in ascending order of price. On this basis, the prices of active buyers and active sellers are matched. As shown on the left of Figure 3, the buyer price (marked red) and the seller price (marked green) are the critical points, and the buyer and seller starting from the critical points to the left become refined active buyers and sellers. Next, refined active sellers are sorted in descending order of data quality and refined active buyers in ascending order of data quality. Then, the data quality of refined active buyers and refined active sellers are matched. As shown on the right of Figure 3, the buyer data quality (marked red) and the seller data quality (marked green) are the critical points, and we take the prices of the buyer and the seller located at the critical points as the corresponding valid price.Figure 3
Interpretive explanation of valid price calculation.


### 4.3. Normal Data Trading Method

We provide the normal data trading method as Algorithm3. In the data trading process, we select the buyer with the highest price in Sg as the winning buyer g¯ and assign the trading price for the sellers providing data. We record the data trading information for the winning buyer g¯ and for the sellers providing data (i.e., the winning sellers). The winning sellers provide data with all they can (ev), except that the last winning seller needs to provide data with the one the winning buyer needs left (∑v∈Swvev−eg¯), whose nonnegative value will indicate that the winning buyer has the enough data demanded.As shown in Algorithm3, when the number of candidate buyers exceeds 1, the trading price of the winning buyer g¯ is equal to the second highest price among the bids of these candidate buyers. When only one candidate buyer exists, the trading price of the winning buyer g¯ is equal to its bid. The former case follows the Vickrey-Clarke-Groves auction model [25] to ensure the truthfulness of our algorithm.The elements inSv−Swv and Swv are sorted according to their asking prices in a positive sequence, where Swv represents the winning data sellers and Sv−Swv represents the left sellers (nonwinning data providers). When there exist elements in Sv−Swv, we use the asking price of the first element in it as the trading price of all the sellers in Swv. When there are no elements in Sv−Swv, we use the asking price of the last element in Swv as the trading price of all the sellers in Swv. In this pricing scheme, data provided to a buyer from different sellers are given the same price, reflecting the principle of fairness.Algorithm 3:NormalTradeMethod
Input: candidate buyers and sellers Sg,Sv, data amounts Eg,Ev, and prices of candidate buyers and sellers Cg,Pv in slot tOutput: data transaction result DataTradingRecord and winning buyer//InitializationDataTradingRecord⟵∅,Swv⟵∅,Swg⟵∅//Decide winning buyerg¯⟵ buyer with highest price in Sg//Decide trading price of winning buyerifSg>1thenFind second-highest price fromCg as trading price of g¯elseUse price ofg¯ as trading price of g¯end//Decide winning sellers providing data to winning buyerwhile∑v∈Swvev<eg¯doSwv⟵Swv∪vend//Decide trading price of winning sellersifSv−Swv>0thenTrading price of sellers inSwv⟵Price of first seller in Sv−SwvelseTrading price of sellers inSwv⟵Price of last seller in Swvend//Record trading information of winning buyerifSwv≠∅thenSwg⟵Swg∪g¯DataTradingRecord+=g¯,tradingpriceofg¯,Swv,∑v∈Swvev−eg¯end//Record trading information of winning sellersfor eachv∈Swvdoif∑v∈Swvev−eg¯thenDataTradingRecord+=v,tradingpriceofv,g¯,∑v∈Swvev−eg¯exitelseDataTradingRecord+=v,tradingpriceofv,g¯,evendendreturnDataTradingRecord,SwgAs shown in Figure4, a data trading start pointer is adopted to indicate where a provider starts providing data. By default, the provider provides data starting from the location indicated by the pointer. Among those providing data to a buyer, data that can be provided by the last data provider may not be all that is required, so the cutoff point is recorded and fed back to the provider.Figure 4
Data trading start pointer for data providers.


### 4.4. DANTM Scheme Analysis

We theoretically analyze the DANTM scheme properties.Lemma 5.
The DANTM scheme is individually rational.Proof.
For the buyer, the DANTM scheme considers two cases. First isSg>1, where winning buyer g¯ is assigned trading price p¯tg¯ as the second-highest bid ptg′ from Cg. Since p¯tg¯=ptg′<ptg¯, there exists ptg¯−p¯tg¯>0. Second is Sg=1, where winning buyer g¯ is assigned trading price p¯tg¯ as bid ptg¯ of itself, so ptg¯−p¯tg¯=0. Hence, the scheme is individually rational for buyers.
For the seller, trading pricep¯tv of the winning sellers in Swv is assigned as asking price ctv′ of the first seller v′ in Sv−Swv. Since the asking prices of sellers in Sv are sorted in ascending order, p¯tv−ctv=ctv′−ctv>0. Therefore, the scheme is individually rational for sellers.Lemma 6.
The DANTM scheme is weakly budget-balanced.Proof.
A winning buyerg¯ is provided data by a group of winning sellers Swv with a single trading price. The data quantity is the same for both the buyer and sellers. To prove the lemma, we only need to show that p¯tg¯≥p¯tv. From the DANTM scheme, winning buyers and sellers come from candidate buyers/sellers, and pt−g¯≥fgt≥fvt≥pt−v.Lemma 7.
The DANTM scheme is truthful.Proof.
We consider two cases for a buyer. First isSg=1. If the initial bid of the winning buyer is lower than its real value ptg, the buyer loses the opportunity to first become a candidate buyer and receives utility Utg=0. If the initial bid is greater than ptg, a successful transaction may bring about negative utility Utg<0 because the transaction price p¯tg is greater than ptg. In the second case, Sg>1, the secondary bid is selected as p¯tg, in accordance with the Vickrey second price auction rule, which is known to be truthful [25].
The DANTM scheme also considers two cases for a seller. First, only one qualified seller provides data to the buyer. A seller with an asking price greater than its real valuectv loses the opportunity to become a winning seller and receives utility Utv=0. If the asking price is less than ctv, a successful transaction may have utility Utv<0 because p¯tv is less than ctv. Second, multiple qualified sellers provide data to the same purchaser. Among them, the offer with the highest asking price, following the Vickrey second price auction rule, guarantees a truthful ask [25], and other winning sellers will not get more utility. A seller whose asking price exceeds ctv loses the opportunity to become a winning seller, and Utv=0, or becomes the last winning one, which maybe provide limited data ∑v∈Swvev−eg¯ when ∑v∈Swvev−eg¯>0, and impact its utility Utv. If a seller gives an asking price below its real value ctv, its utility Utv is not affected.Theorem 8.
The DANTM scheme is individually rational, truthful, and weakly budget-balanced.


## 4.1. Double Auction with Valid Price Mechanism

We present the concept of a valid price.Definition 4. (Valid Price).
A valid price is a threshold value of a buyer’s bid and a seller’s asking price. It can determine whether a buyer or seller wins in an auction. A valid price is determined by bids, asking prices, and data quality of buyers and sellers.In a double-auction data market, active buyersG and sellers V in slot t submit their bidding information to the data market administrator, which can be realized in a smart contract in blockchain. The data market administrator assigns each buyer with seller-provided data through Algorithms 1–3 (see below). The following information is obtained for buyers: the winning buyer g¯ and its trading price, the data providers Swv, and whether its requirement is satisfied (i.e., whether ∑v∈Swvev−eg¯≥0). For sellers, the following information is obtained: the winning sellers, their trading price, the corresponding buyer, and the amount of data provided. The results are uniformly described by DataTradingRecord Algorithm 1 (DANTM) describing the auction scheme. We use Algorithm 2 to calculate the valid price for each active buyer and seller and use this to filter the active buyers G and sellers V to determine candidate participants Sg and Sv. We sort the candidate buyers in descending bid order and candidate sellers by ascending asking prices. We call Algorithm 3 to obtain a winning buyer g¯ (stored in Swg) and the related DataTradingRecord, delete that buyer from active buyers G, and serve the next active buyer.Algorithm 1: Double Auction with Valid Price Mechanism.
Input: active buyers and sellers G,V in slot t, and their bids (price, quality, and quantity) Pv,Cg,Dv,Dg,Eg,EvOutput: Data transaction result DataTradingRecord//InitializationSg⟵∅, Sv⟵∅, Swg⟵∅, DataTradingRecord⟵∅whileG−Swg≠∅doG⟵G−Swg, Swg⟵∅//Call Algorithm2 to calculate valid pricefxt=CalcValidPriceG,V,Cg,Pv,Dg,DvSg=g:cg≥fgt,∀g∈GSv=v:pv≤fvt,∀v∈VSg⟵sortcg in descending order, g∈SgSv⟵sortpv in ascending order, v∈Sv//Call Algorithm3 (normal method) for data tradingDataTradingRecord+,Swg=NormalTradeMethodSg,Sv,Cg,Pv,Eg,Evend


## 4.2. Valid Price Algorithm

Algorithm2 is used to calculate a valid price. We match the prices of active buyers and sellers in Cg,Pv to obtain the refined active buyers and sellers B,S, and call CalcValidPriceViaQuality (see below) to match the data quality of B,S among Dg,Dv, so as to select the proper prices of buyers and sellers and use them as valid price fxt for buyers (when x=g) and sellers (when x=v) at slot t.Algorithm 2:CalcValidPrice
Input: price and data quality of active buyers and sellers G,V,Cg,Px,Dg,Dv in slot tOutput: valid price fxt with x=vorg for data trading in slot tm=G; n=VSort prices of active buyers:c1g>c2g>⋯>cmgSort prices of active sellers:p1v<p2v<⋯<pnvifpnv≤cmgthenrefine active buyersB=1,2,⋯,,mrefine active sellersS=1,2,⋯,nelse ifclg≥pkv≥cl+1gthenrefine active buyersB=1,2,⋯,l, with 1≤l≤m−1refine active sellersS=1,2,⋯,k, with 1≤k≤nelse ifpk+1v≥crg≥pkvthenrefine active buyersB=1,2,⋯,r, with 1≤r≤mrefine active sellersS=1,2,⋯,k, with 1≤k≤n−1end//Call functionCalcValidPriceViaQuality to decide valid pricefxt=CalcValidPriceViaQualityB,S,Cg,Pv,Dg,DvreturnfxtThe functionCalcValidPriceViaQuality is as follows.FunctionCalcValidPriceViaQualityInput: price and data quality of refined active buyers and sellers B,S,Cg,Pv,Dg,Dv in slot tOutput: valid price fxt with x=vorg for data trading in slot tSort quality of refined active buyers inB as d1g<d2g<⋯<dy∗g, y∗=BSort quality of refined active sellers inS as d1v>d2v>⋯>ds∗v, s∗=Sifds∗v≥dy∗gthenfxt⟵minc1g,⋯,cy∗g,x=gmaxp1v,⋯,ps∗v,x=velse ifdw∗v≤dj∗g≤dw−1∗vthenfxt⟵cj∗g,x=gpw−1∗v,x=v with j∗∈1,2,⋯,y∗ and w∗∈2,3,⋯,s∗else ifdl∗g≤dk∗v≤dl+1∗gthenfxt⟵cl∗g,x=gpk∗v,x=v with l∗∈1,2,⋯,y−1∗ and k∗∈1,2,⋯,s∗endreturnfxtWe provide an intuitive explanation of Algorithm2 in Figure 3. To calculate the valid price, Algorithm 2 first ranks active buyers in descending order of price and active sellers in ascending order of price. On this basis, the prices of active buyers and active sellers are matched. As shown on the left of Figure 3, the buyer price (marked red) and the seller price (marked green) are the critical points, and the buyer and seller starting from the critical points to the left become refined active buyers and sellers. Next, refined active sellers are sorted in descending order of data quality and refined active buyers in ascending order of data quality. Then, the data quality of refined active buyers and refined active sellers are matched. As shown on the right of Figure 3, the buyer data quality (marked red) and the seller data quality (marked green) are the critical points, and we take the prices of the buyer and the seller located at the critical points as the corresponding valid price.Figure 3
Interpretive explanation of valid price calculation.


## 4.3. Normal Data Trading Method

We provide the normal data trading method as Algorithm3. In the data trading process, we select the buyer with the highest price in Sg as the winning buyer g¯ and assign the trading price for the sellers providing data. We record the data trading information for the winning buyer g¯ and for the sellers providing data (i.e., the winning sellers). The winning sellers provide data with all they can (ev), except that the last winning seller needs to provide data with the one the winning buyer needs left (∑v∈Swvev−eg¯), whose nonnegative value will indicate that the winning buyer has the enough data demanded.As shown in Algorithm3, when the number of candidate buyers exceeds 1, the trading price of the winning buyer g¯ is equal to the second highest price among the bids of these candidate buyers. When only one candidate buyer exists, the trading price of the winning buyer g¯ is equal to its bid. The former case follows the Vickrey-Clarke-Groves auction model [25] to ensure the truthfulness of our algorithm.The elements inSv−Swv and Swv are sorted according to their asking prices in a positive sequence, where Swv represents the winning data sellers and Sv−Swv represents the left sellers (nonwinning data providers). When there exist elements in Sv−Swv, we use the asking price of the first element in it as the trading price of all the sellers in Swv. When there are no elements in Sv−Swv, we use the asking price of the last element in Swv as the trading price of all the sellers in Swv. In this pricing scheme, data provided to a buyer from different sellers are given the same price, reflecting the principle of fairness.Algorithm 3:NormalTradeMethod
Input: candidate buyers and sellers Sg,Sv, data amounts Eg,Ev, and prices of candidate buyers and sellers Cg,Pv in slot tOutput: data transaction result DataTradingRecord and winning buyer//InitializationDataTradingRecord⟵∅,Swv⟵∅,Swg⟵∅//Decide winning buyerg¯⟵ buyer with highest price in Sg//Decide trading price of winning buyerifSg>1thenFind second-highest price fromCg as trading price of g¯elseUse price ofg¯ as trading price of g¯end//Decide winning sellers providing data to winning buyerwhile∑v∈Swvev<eg¯doSwv⟵Swv∪vend//Decide trading price of winning sellersifSv−Swv>0thenTrading price of sellers inSwv⟵Price of first seller in Sv−SwvelseTrading price of sellers inSwv⟵Price of last seller in Swvend//Record trading information of winning buyerifSwv≠∅thenSwg⟵Swg∪g¯DataTradingRecord+=g¯,tradingpriceofg¯,Swv,∑v∈Swvev−eg¯end//Record trading information of winning sellersfor eachv∈Swvdoif∑v∈Swvev−eg¯thenDataTradingRecord+=v,tradingpriceofv,g¯,∑v∈Swvev−eg¯exitelseDataTradingRecord+=v,tradingpriceofv,g¯,evendendreturnDataTradingRecord,SwgAs shown in Figure4, a data trading start pointer is adopted to indicate where a provider starts providing data. By default, the provider provides data starting from the location indicated by the pointer. Among those providing data to a buyer, data that can be provided by the last data provider may not be all that is required, so the cutoff point is recorded and fed back to the provider.Figure 4
Data trading start pointer for data providers.


## 4.4. DANTM Scheme Analysis

We theoretically analyze the DANTM scheme properties.Lemma 5.
The DANTM scheme is individually rational.Proof.
For the buyer, the DANTM scheme considers two cases. First isSg>1, where winning buyer g¯ is assigned trading price p¯tg¯ as the second-highest bid ptg′ from Cg. Since p¯tg¯=ptg′<ptg¯, there exists ptg¯−p¯tg¯>0. Second is Sg=1, where winning buyer g¯ is assigned trading price p¯tg¯ as bid ptg¯ of itself, so ptg¯−p¯tg¯=0. Hence, the scheme is individually rational for buyers.
For the seller, trading pricep¯tv of the winning sellers in Swv is assigned as asking price ctv′ of the first seller v′ in Sv−Swv. Since the asking prices of sellers in Sv are sorted in ascending order, p¯tv−ctv=ctv′−ctv>0. Therefore, the scheme is individually rational for sellers.Lemma 6.
The DANTM scheme is weakly budget-balanced.Proof.
A winning buyerg¯ is provided data by a group of winning sellers Swv with a single trading price. The data quantity is the same for both the buyer and sellers. To prove the lemma, we only need to show that p¯tg¯≥p¯tv. From the DANTM scheme, winning buyers and sellers come from candidate buyers/sellers, and pt−g¯≥fgt≥fvt≥pt−v.Lemma 7.
The DANTM scheme is truthful.Proof.
We consider two cases for a buyer. First isSg=1. If the initial bid of the winning buyer is lower than its real value ptg, the buyer loses the opportunity to first become a candidate buyer and receives utility Utg=0. If the initial bid is greater than ptg, a successful transaction may bring about negative utility Utg<0 because the transaction price p¯tg is greater than ptg. In the second case, Sg>1, the secondary bid is selected as p¯tg, in accordance with the Vickrey second price auction rule, which is known to be truthful [25].
The DANTM scheme also considers two cases for a seller. First, only one qualified seller provides data to the buyer. A seller with an asking price greater than its real valuectv loses the opportunity to become a winning seller and receives utility Utv=0. If the asking price is less than ctv, a successful transaction may have utility Utv<0 because p¯tv is less than ctv. Second, multiple qualified sellers provide data to the same purchaser. Among them, the offer with the highest asking price, following the Vickrey second price auction rule, guarantees a truthful ask [25], and other winning sellers will not get more utility. A seller whose asking price exceeds ctv loses the opportunity to become a winning seller, and Utv=0, or becomes the last winning one, which maybe provide limited data ∑v∈Swvev−eg¯ when ∑v∈Swvev−eg¯>0, and impact its utility Utv. If a seller gives an asking price below its real value ctv, its utility Utv is not affected.Theorem 8.
The DANTM scheme is individually rational, truthful, and weakly budget-balanced.


## 5. DADPM

### 5.1. Differential Privacy Data Trading Method

An inference attack can exist in a double auction [5], and when it works, data buyers or sellers can infer the bidding information of other buyers or sellers, which compromises their privacy. To protect privacy requires an obstacle to prevent the guessing of original bids from data trading results, in which case differential privacy is used. If two nearly identical inputs are input to a function, the probability distribution of their outputs is limited, which is the effect of differential privacy, which we define as follows.Definition 9 (Differential Privacy).
A functionf has ε-differential privacy (ε,δ-differential privacy) if, for any two input sets A and B with a single input difference, the outputs are within a fixed range R,
(8)PrfA∈R≤expε×PrfB∈R+δ,where ε and δ are small positive values.To maintain the privacy of bids for both winning buyers and sellers, we randomly select them from candidate buyers and sellers, while preserving some valuable properties. We present an exponential-based privacy preserving mechanism to choose winning buyers and sellers.We calculate the quality value for candidate buyers and determine the probability distribution of winning buyers. We want the buyer with a higher bid to be the winning buyer with priority. As the bidsCg of candidate buyers are arranged in descending order, c1g is the highest bid. We set the quality value of buyers as
(9)qig⟵cigc1g,determine the probability distribution of winning buyers,
(10)Prcig=expε1⋅qig∑sjg∈Sgexpε1⋅qjg,where Sg is the set of candidate buyers, and choose a winning buyer.We choose a method to calculate the quality value for sellers. We want a seller with a lower asking price to be the winning seller with priority. The asking pricesPv of candidate sellers are arranged in ascending order, so p1v is the lowest asking price. The quality value of a seller is
(11)qiv⟵p1vpiv.We calculate the probability distribution of winning sellers amongn candidate sellers
(12)Prpiv=expε2⋅qiv∑j=1nexpε2⋅fqjv,and choose a winning seller.We assume that the quality function of buyer (seller)i is bounded by qmin,qmax, and the difference between maximum and minimum value of the quality function of buyers (sellers) is △1 (△2).According to Theorem 9.36 in [25], while a mechanism is truthful, there is a critical value such that if a buyer’s bid is higher than the critical value, the buyer’s trading price is equal to the value; if a buyer’s bid is less than the value, the buyer will lose in the transaction. In our situation, we can conclude that the bid threshold is just our valid price fgt, and this is the trading price of the winning buyer. We similarly use valid price fvt as the trading price of the winning seller.Algorithm4 presents the implementation of data transaction preserving differential privacy, using DPTradeMethod instead of NormalTradeMethod defined in Algorithm 1:
(13)DataTradingRecord+,Swg=DPTradeMethodSg,Sv,Cg,Pv,Eg,Ev,fxt,DPparameters.We define Algorithm4 using differential privacy method as DADPM. To call DPTradeMethod, we add an input parameter, valid price fxt, and differential privacy-related parameters ε1 and ε2.To achieve differential privacy, we calculate the quality valueqig and probability distribution Prcig for each candidate buyer and select a data buyer g¯ according to this distribution, with trading price fgt as the trading price of g¯.We calculate the quality valueqiv for each candidate seller and obtain probability distribution Prpiv, selecting sellers according to this distribution to provide data for g¯. We use fvt as the trading price of sellers. Similar to the normal trade method, we record and return DataTradingRecord,Swg and adopt a data trading start pointer in Algorithm 4 as Algorithm 3.Algorithm 4:DPTradeMethod
Input: candidate buyers and sellers Sg,Sv, data amounts Eg,Ev, prices of candidate buyers and sellers Cg,Pv, valid price fxt in slot t, and differential privacy-related parameters ε1 and ε2.Output: data transaction result DataTradingRecord and winning buyer//InitializationDataTradingRecord⟵∅, Swv⟵∅, Swg⟵∅//Determine winning buyerfori=1 to Sgdoqig⟵cig/c1gendfori=1 toSgdoPrcig=expε1⋅qig/∑sjg∈Sgexpε1⋅qjgendSelect data buyerg¯∈Sg according to probability distribution Prcig//Determine trading price for winning buyerUsefgt as trading price of g¯//Calculate probability to be a winning sellerfori=1 to Svdoqiv⟵p1v/pivendfori=1 to SvdoPrpiv=expε2⋅qiv/∑j=1nexpε2⋅qjvendwhileSv≠∅do//Select a winning seller for the winning buyerSelect sellerv∈Sv according to probability distribution PrpivSwv⟵Swv∪vUsefvt as trading price of v//Record trading information of sellerif∑v∈Swvev≥eg¯thenDataTradingRecord+=(v, the trading price of v, g¯, ∑v∈Swvev−eg¯)exitelseDataTradingRecord+=(v, the trading price of v, g¯, ev)Sv⟵Sv−vendend//Record trading information of buyerifSwv≠∅thenSwg⟵Swg∪g¯DataTradingRecord+=(g¯, the trading price of g¯, Swv, ∑v∈Swvev−eg¯)endreturnDataTradingRecord,Swg


### 5.2. DADPM Analysis

We theoretically analyze DADPM.Lemma 10.
The DADPM scheme is individually rational.Proof.
The winning buyerg¯ is assigned trading price p¯tg¯ as valid price fgt. From the calculation of the active buyers Sg (Algorithm 1), ptg¯≥fgt So, ptg¯−p¯tg¯=ptg¯−fgt≥0. Therefore, DADPM is individually rational for buyers.
The trading pricep¯tv of the winning sellers in Swv is assigned as valid price fvt. From the calculation of the active sellers Sv (Algorithm 1), ctv≤fvt. So, p¯tv−ctv=fvt−ctv≥0. Therefore, DADPM is individually rational for sellers.
With a proof similar to that of the DANTM scheme, we can conclude Lemma11.Lemma 11.
The DADPM scheme is weakly budget-balanced.Lemma 12.
The DADPM scheme is truthful.Proof.
For buyers, we can prove the conclusion directly using Theorem 9.36 in [25], according to which, if there is a critical trading price for buyers, the scheme is truthful. From Algorithm 1, Sg is obtained by sorting cg in descending order, so the elements in Sg are monotone in cg. Also from Algorithm 1, Sg is obtained by filtering buyers with cg≥fgt. So, there exists a critical value fgt.
Recall that Vazirani et al. [25] discussed the situation of a simple auction, with one seller and multiple buyers. We discuss a double auction, with multiple sellers and buyers. A buyer’s bid is a preference to choose a buyer, and an asking price is a preference to choose a seller. Then, if there is a critical value of a trading price for sellers, the scheme is truthful.
Based on the above discussion, we can prove that the DADPM scheme is truthful for sellers. From Algorithm1, Sv is obtained by sorting pv in ascending order, so the elements in Sv are monotone in pv, andSv is obtained by filtering sellers with pv≤fvt. So, there exists a critical value fvt.Theorem 13.
The DADPM scheme is individually rational, truthful, and weakly budget-balanced.Now, we prove that DADPM preserves the data buyer’s valuation privacy.Theorem 14.
For data buyers, DADPM preserves (ε1e−1Δ1lne/δ, δ) differential privacy for bidders’ quality values when δ≤1/2.Proof.
We can prove our conclusions using a proof method similar to Theorem8 in [23]. Let Q and Q′ be vectors of a quality function that differ for a single bidder, and let Cg and C′g be corresponding bid vectors. We show that DADPM can preserve bid privacy even if the order of winning bidders is revealed. Assume we get an arbitrary sequence of winning buyers W=W′=w1,w2,⋯,wl with length l. The relative probability of obtaining the sequences for given vectors of quality function Q and Q′ is
(14)PrW=w1,w2,⋯,wlPrW′=w1,w2,⋯,wl=∏i=1lexpε1⋅qig/∑sjg∈Sgexpε1⋅qijgexpε1⋅q′ig/∑sjg∈Sgexpε1⋅q′ijg=∏i=1lexpε1⋅qig−q′ig×∏i=1l∑sjg∈Sgexpε1⋅q′ijg∑sjg∈Sgexpε1⋅qijg,if qig>q′ig, expε1⋅qig−q′ig≤expε1⋅Δ1, and the second product is less than 1. Therefore,
(15)PrW=w1,w2,⋯,wlPrW′=w1,w2,⋯,wl≤expε1⋅Δ1,if qig<q′ig, the first product is less than 1; therefore,
(16)PrW=w1,w2,⋯,wlPrW′=w1,w2,⋯,wl≤∏i=1l∑sjg∈Sgexpε1⋅q′ijg∑sjg∈Sgexpε1⋅qijg=∏i=1l∑sjg∈Sgexpε1⋅βij⋅expε1⋅qijg∑sjg∈Sgexpε1⋅qijg=∏i=1lEiexpε1⋅βi,
whereβij=q′ijg−qijg, and the expectation is taken over the probability distribution about the quality values of Sg at the time slot. Note that Sg is adjusted dynamically in DADPM, and qijg is the value of qjg to calculate Prcig when winning buyer i is selected. For all α≤1, eα≤1+e−1⋅α. Therefore, for all ε1≤1, we have
(17)∏i=1lEiexpε1⋅βi≤∏i=1lEi1+e−1ε1⋅βi≤expe−1ε1∏i=1lEiβi.
Sinceδ is a small positive value (δ≤1/2), by Lemma B.2 in [26], we have ∏i=1lEiβi≤Δ1lneδ−1.
So, there exists(18)PrW=w1,w2,⋯,wlPrW′=w1,w2,⋯,wl≤expε1⋅Δ1⋅e−1⋅lneδ−1.
Similar to the proof of Theorem14, we can conclude that DADPM preserves sellers’ valuation privacy.Theorem 15.
For data sellers, DADPM preserves (ε2e−1Δ2lne/δ, δ) differential privacy for bidders’ quality values when δ≤1/2.


### 5.3. Design Rationale Discussion

Two popular mechanisms to ensure differential privacy are the exponential mechanism and Gaussian mechanism. The exponential mechanism protects the privacy of the input by randomly selecting the output result via probability in a set. It is commonly used for a one-sided auction. Problems with lower social welfare and satisfaction ratio may occur when it is used for a double auction [5]. The Gaussian mechanism protects the privacy of the input by calculating the output results after adding Gaussian noise to the input. The disadvantage of this method is the difficulty in determining the size of the noise to achieve a balance between the protection of privacy and the auction performance.Researchers who used the above mechanisms include Zhu and Shin [23] and Li et al. [5]. Zhu and Shin [23] used the exponential mechanism to solve the one-side auction for spectrum with approximate revenue maximization and achieved good results. Li et al. [5] solved the double auction for smart grid, where the Gaussian mechanism was adopted for the privacy protection of bidders’ valuation, while the exponential mechanism was adopted for the protection of transaction volume.To the best of our knowledge, prior to our paper, there was no double-auction study on data and no differential privacy protection solution on this basis. Given the apparent shortcomings of the Gaussian mechanism, our work employs an exponential mechanism to protect price privacy.Our work for data double auction is different from the traditional sense of resource double auction, because the resource (such as the above spectrum and power) is unique; a resource in a slot can only match and provide to a unique buyer, and the data are repeatable, i.e., a seller of data in a slot can match and provide them to multiple different buyers, not a one-to-one matching relationship. Therefore, our work adopts the exponential mechanism for double auction, which theoretically has no problem, and will not encounter the low auction performance mentioned by Li et al. [5]. Later performance evaluations also demonstrate this.In addition, our work focuses on the single core element of the bid of the auction, which is different from [5] to protect valuation and transaction volume, making the background of using the exponential mechanism different from [5] at this point.


## 5.1. Differential Privacy Data Trading Method

An inference attack can exist in a double auction [5], and when it works, data buyers or sellers can infer the bidding information of other buyers or sellers, which compromises their privacy. To protect privacy requires an obstacle to prevent the guessing of original bids from data trading results, in which case differential privacy is used. If two nearly identical inputs are input to a function, the probability distribution of their outputs is limited, which is the effect of differential privacy, which we define as follows.Definition 9 (Differential Privacy).
A functionf has ε-differential privacy (ε,δ-differential privacy) if, for any two input sets A and B with a single input difference, the outputs are within a fixed range R,
(8)PrfA∈R≤expε×PrfB∈R+δ,where ε and δ are small positive values.To maintain the privacy of bids for both winning buyers and sellers, we randomly select them from candidate buyers and sellers, while preserving some valuable properties. We present an exponential-based privacy preserving mechanism to choose winning buyers and sellers.We calculate the quality value for candidate buyers and determine the probability distribution of winning buyers. We want the buyer with a higher bid to be the winning buyer with priority. As the bidsCg of candidate buyers are arranged in descending order, c1g is the highest bid. We set the quality value of buyers as
(9)qig⟵cigc1g,determine the probability distribution of winning buyers,
(10)Prcig=expε1⋅qig∑sjg∈Sgexpε1⋅qjg,where Sg is the set of candidate buyers, and choose a winning buyer.We choose a method to calculate the quality value for sellers. We want a seller with a lower asking price to be the winning seller with priority. The asking pricesPv of candidate sellers are arranged in ascending order, so p1v is the lowest asking price. The quality value of a seller is
(11)qiv⟵p1vpiv.We calculate the probability distribution of winning sellers amongn candidate sellers
(12)Prpiv=expε2⋅qiv∑j=1nexpε2⋅fqjv,and choose a winning seller.We assume that the quality function of buyer (seller)i is bounded by qmin,qmax, and the difference between maximum and minimum value of the quality function of buyers (sellers) is △1 (△2).According to Theorem 9.36 in [25], while a mechanism is truthful, there is a critical value such that if a buyer’s bid is higher than the critical value, the buyer’s trading price is equal to the value; if a buyer’s bid is less than the value, the buyer will lose in the transaction. In our situation, we can conclude that the bid threshold is just our valid price fgt, and this is the trading price of the winning buyer. We similarly use valid price fvt as the trading price of the winning seller.Algorithm4 presents the implementation of data transaction preserving differential privacy, using DPTradeMethod instead of NormalTradeMethod defined in Algorithm 1:
(13)DataTradingRecord+,Swg=DPTradeMethodSg,Sv,Cg,Pv,Eg,Ev,fxt,DPparameters.We define Algorithm4 using differential privacy method as DADPM. To call DPTradeMethod, we add an input parameter, valid price fxt, and differential privacy-related parameters ε1 and ε2.To achieve differential privacy, we calculate the quality valueqig and probability distribution Prcig for each candidate buyer and select a data buyer g¯ according to this distribution, with trading price fgt as the trading price of g¯.We calculate the quality valueqiv for each candidate seller and obtain probability distribution Prpiv, selecting sellers according to this distribution to provide data for g¯. We use fvt as the trading price of sellers. Similar to the normal trade method, we record and return DataTradingRecord,Swg and adopt a data trading start pointer in Algorithm 4 as Algorithm 3.Algorithm 4:DPTradeMethod
Input: candidate buyers and sellers Sg,Sv, data amounts Eg,Ev, prices of candidate buyers and sellers Cg,Pv, valid price fxt in slot t, and differential privacy-related parameters ε1 and ε2.Output: data transaction result DataTradingRecord and winning buyer//InitializationDataTradingRecord⟵∅, Swv⟵∅, Swg⟵∅//Determine winning buyerfori=1 to Sgdoqig⟵cig/c1gendfori=1 toSgdoPrcig=expε1⋅qig/∑sjg∈Sgexpε1⋅qjgendSelect data buyerg¯∈Sg according to probability distribution Prcig//Determine trading price for winning buyerUsefgt as trading price of g¯//Calculate probability to be a winning sellerfori=1 to Svdoqiv⟵p1v/pivendfori=1 to SvdoPrpiv=expε2⋅qiv/∑j=1nexpε2⋅qjvendwhileSv≠∅do//Select a winning seller for the winning buyerSelect sellerv∈Sv according to probability distribution PrpivSwv⟵Swv∪vUsefvt as trading price of v//Record trading information of sellerif∑v∈Swvev≥eg¯thenDataTradingRecord+=(v, the trading price of v, g¯, ∑v∈Swvev−eg¯)exitelseDataTradingRecord+=(v, the trading price of v, g¯, ev)Sv⟵Sv−vendend//Record trading information of buyerifSwv≠∅thenSwg⟵Swg∪g¯DataTradingRecord+=(g¯, the trading price of g¯, Swv, ∑v∈Swvev−eg¯)endreturnDataTradingRecord,Swg


## 5.2. DADPM Analysis

We theoretically analyze DADPM.Lemma 10.
The DADPM scheme is individually rational.Proof.
The winning buyerg¯ is assigned trading price p¯tg¯ as valid price fgt. From the calculation of the active buyers Sg (Algorithm 1), ptg¯≥fgt So, ptg¯−p¯tg¯=ptg¯−fgt≥0. Therefore, DADPM is individually rational for buyers.
The trading pricep¯tv of the winning sellers in Swv is assigned as valid price fvt. From the calculation of the active sellers Sv (Algorithm 1), ctv≤fvt. So, p¯tv−ctv=fvt−ctv≥0. Therefore, DADPM is individually rational for sellers.
With a proof similar to that of the DANTM scheme, we can conclude Lemma11.Lemma 11.
The DADPM scheme is weakly budget-balanced.Lemma 12.
The DADPM scheme is truthful.Proof.
For buyers, we can prove the conclusion directly using Theorem 9.36 in [25], according to which, if there is a critical trading price for buyers, the scheme is truthful. From Algorithm 1, Sg is obtained by sorting cg in descending order, so the elements in Sg are monotone in cg. Also from Algorithm 1, Sg is obtained by filtering buyers with cg≥fgt. So, there exists a critical value fgt.
Recall that Vazirani et al. [25] discussed the situation of a simple auction, with one seller and multiple buyers. We discuss a double auction, with multiple sellers and buyers. A buyer’s bid is a preference to choose a buyer, and an asking price is a preference to choose a seller. Then, if there is a critical value of a trading price for sellers, the scheme is truthful.
Based on the above discussion, we can prove that the DADPM scheme is truthful for sellers. From Algorithm1, Sv is obtained by sorting pv in ascending order, so the elements in Sv are monotone in pv, andSv is obtained by filtering sellers with pv≤fvt. So, there exists a critical value fvt.Theorem 13.
The DADPM scheme is individually rational, truthful, and weakly budget-balanced.Now, we prove that DADPM preserves the data buyer’s valuation privacy.Theorem 14.
For data buyers, DADPM preserves (ε1e−1Δ1lne/δ, δ) differential privacy for bidders’ quality values when δ≤1/2.Proof.
We can prove our conclusions using a proof method similar to Theorem8 in [23]. Let Q and Q′ be vectors of a quality function that differ for a single bidder, and let Cg and C′g be corresponding bid vectors. We show that DADPM can preserve bid privacy even if the order of winning bidders is revealed. Assume we get an arbitrary sequence of winning buyers W=W′=w1,w2,⋯,wl with length l. The relative probability of obtaining the sequences for given vectors of quality function Q and Q′ is
(14)PrW=w1,w2,⋯,wlPrW′=w1,w2,⋯,wl=∏i=1lexpε1⋅qig/∑sjg∈Sgexpε1⋅qijgexpε1⋅q′ig/∑sjg∈Sgexpε1⋅q′ijg=∏i=1lexpε1⋅qig−q′ig×∏i=1l∑sjg∈Sgexpε1⋅q′ijg∑sjg∈Sgexpε1⋅qijg,if qig>q′ig, expε1⋅qig−q′ig≤expε1⋅Δ1, and the second product is less than 1. Therefore,
(15)PrW=w1,w2,⋯,wlPrW′=w1,w2,⋯,wl≤expε1⋅Δ1,if qig<q′ig, the first product is less than 1; therefore,
(16)PrW=w1,w2,⋯,wlPrW′=w1,w2,⋯,wl≤∏i=1l∑sjg∈Sgexpε1⋅q′ijg∑sjg∈Sgexpε1⋅qijg=∏i=1l∑sjg∈Sgexpε1⋅βij⋅expε1⋅qijg∑sjg∈Sgexpε1⋅qijg=∏i=1lEiexpε1⋅βi,
whereβij=q′ijg−qijg, and the expectation is taken over the probability distribution about the quality values of Sg at the time slot. Note that Sg is adjusted dynamically in DADPM, and qijg is the value of qjg to calculate Prcig when winning buyer i is selected. For all α≤1, eα≤1+e−1⋅α. Therefore, for all ε1≤1, we have
(17)∏i=1lEiexpε1⋅βi≤∏i=1lEi1+e−1ε1⋅βi≤expe−1ε1∏i=1lEiβi.
Sinceδ is a small positive value (δ≤1/2), by Lemma B.2 in [26], we have ∏i=1lEiβi≤Δ1lneδ−1.
So, there exists(18)PrW=w1,w2,⋯,wlPrW′=w1,w2,⋯,wl≤expε1⋅Δ1⋅e−1⋅lneδ−1.
Similar to the proof of Theorem14, we can conclude that DADPM preserves sellers’ valuation privacy.Theorem 15.
For data sellers, DADPM preserves (ε2e−1Δ2lne/δ, δ) differential privacy for bidders’ quality values when δ≤1/2.


## 5.3. Design Rationale Discussion

Two popular mechanisms to ensure differential privacy are the exponential mechanism and Gaussian mechanism. The exponential mechanism protects the privacy of the input by randomly selecting the output result via probability in a set. It is commonly used for a one-sided auction. Problems with lower social welfare and satisfaction ratio may occur when it is used for a double auction [5]. The Gaussian mechanism protects the privacy of the input by calculating the output results after adding Gaussian noise to the input. The disadvantage of this method is the difficulty in determining the size of the noise to achieve a balance between the protection of privacy and the auction performance.Researchers who used the above mechanisms include Zhu and Shin [23] and Li et al. [5]. Zhu and Shin [23] used the exponential mechanism to solve the one-side auction for spectrum with approximate revenue maximization and achieved good results. Li et al. [5] solved the double auction for smart grid, where the Gaussian mechanism was adopted for the privacy protection of bidders’ valuation, while the exponential mechanism was adopted for the protection of transaction volume.To the best of our knowledge, prior to our paper, there was no double-auction study on data and no differential privacy protection solution on this basis. Given the apparent shortcomings of the Gaussian mechanism, our work employs an exponential mechanism to protect price privacy.Our work for data double auction is different from the traditional sense of resource double auction, because the resource (such as the above spectrum and power) is unique; a resource in a slot can only match and provide to a unique buyer, and the data are repeatable, i.e., a seller of data in a slot can match and provide them to multiple different buyers, not a one-to-one matching relationship. Therefore, our work adopts the exponential mechanism for double auction, which theoretically has no problem, and will not encounter the low auction performance mentioned by Li et al. [5]. Later performance evaluations also demonstrate this.In addition, our work focuses on the single core element of the bid of the auction, which is different from [5] to protect valuation and transaction volume, making the background of using the exponential mechanism different from [5] at this point.


## 6. Performance Evaluation

As there is no existing scheme for data double auction as far as we know, we directly evaluate the effectiveness of DANTM and DADPM, considering the auction process in a slot. We assume uniformly distributed bids, asking prices, and demand and supply volumes of bidders. We further assume substantial matches of data quality between providers and purchasers. We setε1 and ε2 to 0.1. Unless otherwise stated, simulation results are based on these settings.We evaluate the characteristics of DANTM and DADPM, including individual rationality, weak budget balance, and truthfulness, and their comprehensive performance, including social welfare, time cost, and privacy leakage.We ran simulations on a PC with a 1.80 GHz Intel Core i7-8565U CPU and 16 GB RAM under Windows 10. Results were averaged over 100 runs to obtain fair and credible results.


### 6.1. Evaluation of Basic Characteristics for DANTM and DADPM

#### 6.1.1. Individual Rationality

Figure5 shows payoffs for buyers and sellers using DANTM and DADPM. We can see that every payoff is positive, which satisfies the principle of individual rationality for buyers and sellers.Figure 5
Payoff for (a) buyers and (b) sellers.
(a)(b)


#### 6.1.2. Weak Budget Balance

Figure6 displays the relationship between the number of bidders and the average budget (defined in (6)) obtained with DANTM and DADPM. Half the bidders are buyers, and half are sellers; the same setting is used while the horizontal axis represents the number of bidders in Figures 7 and 8. The results show positive budgets in DANTM and DADPM; hence, a weak budget balance is reached.Figure 6
Budget of data market.Figure 7
Social welfare of data market.Figure 8
Time cost of data trading.


#### 6.1.3. Truthfulness

To verify truthfulness using DANTM and DADPM, we need to observe how the bid/asking price impacts the payoff for buyers/sellers. Figure9 shows the experimental results. In Figure 9(a), the payoff generally decreases with decreasing bids, which means that a lower bid does not help buyers obtain a higher payoff. In Figure 9(b), the payoff does not increase when sellers ask a higher price.Figure 9
Payoff change impacted by (a) bids and (b) asking prices.
(a)(b)


### 6.2. Evaluation of Comprehensive Performance for DANTM and DADPM

#### 6.2.1. Social Welfare

Figure7 shows the average social welfare for a bidder with different numbers of bidders. We can see that the average social welfare in DADPM is higher than in DANTM in most cases, which is due to different transaction pricing mechanisms. For convenience, we replace ε with Ifif in Figures 7 and 10 (note that ε represents ε1 and ε2).Figure 10
Privacy leakage: (a) buyers; (b) sellers.
(a)(b)


#### 6.2.2. Privacy Leakage

Definition 16 (Privacy Leakage).
AssumeQ1 and Q2 are neighboring databases that differ only in a single datum. We use W as the output of some algorithm M on input Q1 and Q2, and W+ is the set of outputs W. Pr is the probability distribution about MQi=W with i=1 and 2. The privacy leakage (Pl) between two neighboring databases is derived as [5]
(19)Pl=∑W∈W+PrMQ1=WlnPrMQ1=WPrMQ2=W.From the definition, we can see that privacy leakage indicates how we can distinguish the input when the generated output is the same. The less the privacy leakage, the better the privacy protection.In our situation, we change one bid in a group of bidders, with the winning bidders unchanged, to obtain the privacy leakage results in Figure10. In Figure 10(a), the privacy leakage is limited between −0.0002 and 0.0002. In Figure 10(b), it is limited between 0 and 0.0004. Based on these results, it is almost impossible to distinguish or infer the bidding information and threaten bidder privacy.


#### 6.2.3. Time Cost

Figure8 shows the time cost of data trading as the number of bidders changes from 10 to 100. In most cases, the time cost increases with the number of bidders. As the computing process is more complex in DADPM than in DANTM, its time cost is higher. The highest time cost is less than 20 ms, which indicates the effectiveness of our schemes.


## 6.1. Evaluation of Basic Characteristics for DANTM and DADPM

### 6.1.1. Individual Rationality

Figure5 shows payoffs for buyers and sellers using DANTM and DADPM. We can see that every payoff is positive, which satisfies the principle of individual rationality for buyers and sellers.Figure 5
Payoff for (a) buyers and (b) sellers.
(a)(b)


### 6.1.2. Weak Budget Balance

Figure6 displays the relationship between the number of bidders and the average budget (defined in (6)) obtained with DANTM and DADPM. Half the bidders are buyers, and half are sellers; the same setting is used while the horizontal axis represents the number of bidders in Figures 7 and 8. The results show positive budgets in DANTM and DADPM; hence, a weak budget balance is reached.Figure 6
Budget of data market.Figure 7
Social welfare of data market.Figure 8
Time cost of data trading.


### 6.1.3. Truthfulness

To verify truthfulness using DANTM and DADPM, we need to observe how the bid/asking price impacts the payoff for buyers/sellers. Figure9 shows the experimental results. In Figure 9(a), the payoff generally decreases with decreasing bids, which means that a lower bid does not help buyers obtain a higher payoff. In Figure 9(b), the payoff does not increase when sellers ask a higher price.Figure 9
Payoff change impacted by (a) bids and (b) asking prices.
(a)(b)


## 6.1.1. Individual Rationality

Figure5 shows payoffs for buyers and sellers using DANTM and DADPM. We can see that every payoff is positive, which satisfies the principle of individual rationality for buyers and sellers.Figure 5
Payoff for (a) buyers and (b) sellers.
(a)(b)


## 6.1.2. Weak Budget Balance

Figure6 displays the relationship between the number of bidders and the average budget (defined in (6)) obtained with DANTM and DADPM. Half the bidders are buyers, and half are sellers; the same setting is used while the horizontal axis represents the number of bidders in Figures 7 and 8. The results show positive budgets in DANTM and DADPM; hence, a weak budget balance is reached.Figure 6
Budget of data market.Figure 7
Social welfare of data market.Figure 8
Time cost of data trading.


## 6.1.3. Truthfulness

To verify truthfulness using DANTM and DADPM, we need to observe how the bid/asking price impacts the payoff for buyers/sellers. Figure9 shows the experimental results. In Figure 9(a), the payoff generally decreases with decreasing bids, which means that a lower bid does not help buyers obtain a higher payoff. In Figure 9(b), the payoff does not increase when sellers ask a higher price.Figure 9
Payoff change impacted by (a) bids and (b) asking prices.
(a)(b)


## 6.2. Evaluation of Comprehensive Performance for DANTM and DADPM

### 6.2.1. Social Welfare

Figure7 shows the average social welfare for a bidder with different numbers of bidders. We can see that the average social welfare in DADPM is higher than in DANTM in most cases, which is due to different transaction pricing mechanisms. For convenience, we replace ε with Ifif in Figures 7 and 10 (note that ε represents ε1 and ε2).Figure 10
Privacy leakage: (a) buyers; (b) sellers.
(a)(b)


### 6.2.2. Privacy Leakage

Definition 16 (Privacy Leakage).
AssumeQ1 and Q2 are neighboring databases that differ only in a single datum. We use W as the output of some algorithm M on input Q1 and Q2, and W+ is the set of outputs W. Pr is the probability distribution about MQi=W with i=1 and 2. The privacy leakage (Pl) between two neighboring databases is derived as [5]
(19)Pl=∑W∈W+PrMQ1=WlnPrMQ1=WPrMQ2=W.From the definition, we can see that privacy leakage indicates how we can distinguish the input when the generated output is the same. The less the privacy leakage, the better the privacy protection.In our situation, we change one bid in a group of bidders, with the winning bidders unchanged, to obtain the privacy leakage results in Figure10. In Figure 10(a), the privacy leakage is limited between −0.0002 and 0.0002. In Figure 10(b), it is limited between 0 and 0.0004. Based on these results, it is almost impossible to distinguish or infer the bidding information and threaten bidder privacy.


### 6.2.3. Time Cost

Figure8 shows the time cost of data trading as the number of bidders changes from 10 to 100. In most cases, the time cost increases with the number of bidders. As the computing process is more complex in DADPM than in DANTM, its time cost is higher. The highest time cost is less than 20 ms, which indicates the effectiveness of our schemes.


## 6.2.1. Social Welfare

Figure7 shows the average social welfare for a bidder with different numbers of bidders. We can see that the average social welfare in DADPM is higher than in DANTM in most cases, which is due to different transaction pricing mechanisms. For convenience, we replace ε with Ifif in Figures 7 and 10 (note that ε represents ε1 and ε2).Figure 10
Privacy leakage: (a) buyers; (b) sellers.
(a)(b)


## 6.2.2. Privacy Leakage

Definition 16 (Privacy Leakage).
AssumeQ1 and Q2 are neighboring databases that differ only in a single datum. We use W as the output of some algorithm M on input Q1 and Q2, and W+ is the set of outputs W. Pr is the probability distribution about MQi=W with i=1 and 2. The privacy leakage (Pl) between two neighboring databases is derived as [5]
(19)Pl=∑W∈W+PrMQ1=WlnPrMQ1=WPrMQ2=W.From the definition, we can see that privacy leakage indicates how we can distinguish the input when the generated output is the same. The less the privacy leakage, the better the privacy protection.In our situation, we change one bid in a group of bidders, with the winning bidders unchanged, to obtain the privacy leakage results in Figure10. In Figure 10(a), the privacy leakage is limited between −0.0002 and 0.0002. In Figure 10(b), it is limited between 0 and 0.0004. Based on these results, it is almost impossible to distinguish or infer the bidding information and threaten bidder privacy.


## 6.2.3. Time Cost

Figure8 shows the time cost of data trading as the number of bidders changes from 10 to 100. In most cases, the time cost increases with the number of bidders. As the computing process is more complex in DADPM than in DANTM, its time cost is higher. The highest time cost is less than 20 ms, which indicates the effectiveness of our schemes.


## 7. Conclusion

We described a blockchain-supported IoT data market framework and focused on data trading of multiple buyers and sellers. We presented a data trading scheme, based directly on the bid information of participants, to determine the winning sellers and buyers at auction and the amount and trading price. To protect participant bid information, we leveraged the data transaction scheme based on differential privacy, with the properties of individual rationality, weak budget balance, and truthfulness, and with good privacy protection based on an exponential mechanism. A performance evaluation demonstrated the effectiveness of the schemes. Experimental results confirmed the above properties, along with good performance in terms of social welfare and computational overhead.



---

*Source: 8038846-2022-06-21.xml*