A Blockchain-Based Approach for Saving and Tracking Differential-Privacy Cost

Differential privacy intuitively means that the adversary cannot determine with high confidence whether the randomized output comes from a dataset $D$ or its neighboring dataset $D^{\prime}$ which differs from $D$ by one record. The formal definition of $(\epsilon,\delta)$-differential privacy is given in Definition 1, and the notion of neighboring datasets is discussed in Remark 2.

Among various mechanisms to achieve DP, the Gaussian mechanism for real-valued queries proposed in [6] has received much attention. The improved result given by [20] is Lemma 1.

More discussions on the $\ell_{2}$-sensitivity of a query are given in Section III-H. Section VII-A discusses the setting of privacy parameters $\epsilon$ and $\delta$.

Blockchain. The blockchain technology is popularly used in systems requiring high security and transparency, such as Bitcoin and Ethereum [21]. The blockchain can be effectively used to solve the double-spending problem in Bitcoin transaction by using a peer-to-peer network. The solution is to hash transaction information in a chain of hash-based Proof-of-Work (PoW, used by Bitcoin) which is the consensus mechanism algorithm used to confirm transactions and produce new blocks to the chain. Once the record is formed, it cannot be changed except redoing Proof-of-Work.

Besides, the blockchain is constantly growing with appending ‘completed’ blocks. Blocks consisting of the most recent transactions are added to the chain in chronological order [22]. Each blockchain node can have a copy of the blockchain. The blockchain allows participants to track their transactions without centralized control.

Ethereum. Ethereum is a blockchain platform which allows users to create decentralized end-to-end applications [23]. The miners in Ethereum use Proof-of-Work consensus algorithm to complete transaction verification and synchronization. Besides, Ethereum can run smart contracts elaborated below.

Smart Contract. The smart contract was first proposed by Nick Szabo as a computerized transaction protocol that can execute terms of a contract automatically [24]. It intends to make a contract digitally, and allows to maintain credible transactions without a third party. With the development of blockchains, such as Ethereum, smart contracts are stored in the blockchain as scripts. A blockchain with a Turing-complete programming language allows everyone to customize smart contract scripts for transactions [25]. Smart contracts are triggered when transactions are created or generated on the blockchain to finishe specific tasks or services.

Our system includes the client, the blockchain, the server, and smart contract followed by more details as below.

Client: The primary function of the client is to transfer users’ queries to the blockchain smart contract. The client computes the required parameter standard deviation for the server to generate the Gaussian noise using the privacy parameters $\epsilon$ and $\delta$ and forwards the query to the blockchain. Also, the client can display the query result to the analyst after getting the noisy response to the query.

Blockchain Smart Contract: The blockchain serves as a middleware between the client and the server. It decides which query should be submitted to the server. The blockchain records the remaining privacy budget, query type, the noisy response to answer the query, the privacy parameters, and the amount of corresponding noise. If the remaining privacy budget is enough, the smart contract will execute the query match function with the recorded history. Otherwise, the smart contract will reject this query. If the current query does not match with any query in the history, the smart contract will call the server to calculate the result. If the query has been received before, the blockchain smart contract will not call the server if the noisy response can be completely generated by old noisy answers and will call the server if access to the dataset is still needed to generate the noisy response.

Server: The data provider hosts the server. The server provides APIs to answer analysts’ queries. When the API is called, the server will query the dataset to calculate the respective answer. After the true value $Q(D)$ is calculated, the server will add noise to perturb the answer. Then the server returns the noisy answer to the blockchain.

In the rest of the paper, we use Blockchain, Client, and Server to denote the blockchain, client, and server, respectively.

Match query with query history and generate noisy response: Blockchain compares the current query type with saved query types to retrieve previous query results. If it is the first time for Blockchain to see the query, Blockchain will forward the query to the server, and Server will return the perturbed result which satisfies differential privacy to Blockchain. If the current query type matches previous answers’ query type, Blockchain will compare the computed amount of noise with all previously saved amounts of noise under the same query type. Based on the comparison result, Blockchain will completely reuse old responses or call Server.

Manage privacy budget: Blockchain updates the privacy budget as queries are answered and the Blockchain ensures no new privacy cost will be incurred for answering queries once the specified privacy budget is exhausted.

The adversary model for our system is similar to [19]. Assume that there are two kinds of adversaries:

First, adversaries can obtain perturbed query results. They may try to infer users’ real information using perturbed queries’ results.

Second, adversaries attempt to modify the privacy budget. For example, they would like to decrease the used privacy budget so that users may exceed the privacy budget. As a result, privacy will leak. However, in our case, the privacy budget is recorded on the blockchain. The adversaries cannot tamper it once the privacy budget is stored in the blockchain.

We present our solution for reusing noise in Algorithm 1 in Section III-E. We consider real-valued queries so that the Gaussian mechanism can be used. Extensions to non-real-valued queries can be regarded as the future work, where we can apply the exponential mechanism of [12].

To clarify notation use, we note that $Q_{i}$ means the $i$-th query (ordered chronologically) and is answered by a randomized algorithm $\widetilde{Q}_{i}$. A type $t$-query means that the query’s type is $t$. Queries asked at different time can have the same query type. This is the reason that we reuse noise in Algorithm 1.

Suppose a dataset $D$ has been used to answer $m-1$ queries $Q_{1},Q_{2},\ldots,Q_{m-1}$, where the $i$-th query $Q_{i}$ for $i=1,2,\ldots,m-1$ is answered under $(\epsilon_{i},\delta_{i})$-differential privacy (by reusing noise, or generating fresh noise, or combining both). For $i=1,2,\ldots,m$, we define $\sigma_{i}:=\operatorname{Gaussian}(\Delta_{Q_{i}},\epsilon_{i},\delta_{i})$, where $\Delta_{Q_{i}}$ denotes the $\ell_{2}$-sensitivity of $Q_{i}$, where we defer the discussion of $\Delta_{Q_{i}}$ to Section III-H. As presented in Algorithm 1, we have several cases discussed below. For better understanding of these cases, we later discuss an example given in Table II in Section II.

1. Case 1):

   If $Q_{m}$ is seen for the first time, we obtain the noisy response $\widetilde{Q}_{m}(D)$ by adding a zero-mean Gaussian noise with standard deviation $\operatorname{Gaussian}(\Delta_{Q_{m}},\epsilon_{m},\delta_{m})$ independently to each dimension of the true result $Q_{m}(D)$ (if the privacy budget allows), as given by Line 7 of Algorithm 1, where $\operatorname{Gaussian}(\Delta_{Q_{m}},\epsilon_{m},\delta_{m}):=\sqrt{2\ln\frac{1.25}{\delta_{m}}}\times\frac{\Delta_{Q_{m}}}{\epsilon_{m}}$ from Lemma 1.

2. Case 2):

   If $Q_{m}$ has been received before, suppose $Q_{m}$ is a type $t$-query, and among the previous $m-1$ queries $Q_{1},Q_{2},\ldots,Q_{m-1}$, let $\boldsymbol{\Sigma}_{t}$ consist of the corresponding noise amounts for previous instances of type $t$-query; i.e., $\boldsymbol{\Sigma}_{t}:=\{\sigma_{j}:\sigma_{j}$ has been recorded in Blockchain and $Q_{j}$ is a type $t$-query$\}$.

   Blockchain compares $\sigma_{m}$ and the values in $\boldsymbol{\Sigma}_{t}$, resulting in the following subcases.

   1. Case 2A):

      If there exists $\sigma_{j}\in\boldsymbol{\Sigma}_{t}$ such that $\sigma_{m}=\sigma_{j}$, then $\widetilde{Q}_{m}(D)$ is set as $\widetilde{Q}_{j}(D)$.

   2. Case 2B):

      This case considers that $\sigma_{m}$ is less than $\min(\boldsymbol{\Sigma}_{t})$ which denotes the minimum in $\boldsymbol{\Sigma}_{t}$. Let $\widetilde{Q}_{t,\textup{min}}(D)$ denote the noisy response (kept in Blockchain) corresponding to $\min(\boldsymbol{\Sigma}_{t})$; specifically, if $\min(\boldsymbol{\Sigma}_{t})=\sigma_{j}$ for some $j$, then $\widetilde{Q}_{t,\textup{min}}(D)=\widetilde{Q}_{j}(D)$. Under $\sigma_{m}<\min(\boldsymbol{\Sigma}_{t})$, to minimize the privacy cost, we reuse $\frac{{\sigma_{m}}^{2}}{[\min(\boldsymbol{\Sigma}_{t})]^{2}}$ fraction of noise in $\widetilde{Q}_{t,\textup{min}}(D)$ to generate $\widetilde{Q}_{m}(D)$ (if the privacy budget allows). This will be obtained by Theorem 1’s Result (ii) to be presented in Section III-E. Specifically, under $\min(\boldsymbol{\Sigma}_{t})>\sigma_{m}$, as given by Line 22 of Algorithm 1, $\widetilde{Q}_{m}(D)$ is set by $\widetilde{Q}_{m}(D)\leftarrow Q_{m}(D)+\frac{{\sigma_{m}}^{2}}{[\min(\boldsymbol{\Sigma}_{t})]^{2}}\times[\widetilde{Q}_{t,\textup{min}}(D)-Q_{m}(D)]+\mathcal{N}(0,1)\times\sqrt{{\sigma_{m}}^{2}-\frac{{\sigma_{m}}^{4}}{[\min(\boldsymbol{\Sigma}_{t})]^{2}}}$. Note that if ${Q}_{m}$ is multidimensional, independent Gaussian noise will be added to each dimension according to the above formula. This also applies to other places of this paper.

   3. Case 2C):

      This case considers that $\sigma_{m}$ is greater than $\min(\boldsymbol{\Sigma}_{t})$ and $\sigma_{m}$ is different from all values in $\boldsymbol{\Sigma}_{t}$. Let $\sigma_{\ell}$ be the maximal possible value in $\boldsymbol{\Sigma}_{t}$ that is also smaller than $\sigma_{m}$; i.e., $\sigma_{\ell}=\max\{\sigma_{j}:\sigma_{j}\in\boldsymbol{\Sigma}_{t}\textup{ and }\sigma_{j}<\sigma_{m}\}$. Then $\widetilde{Q}_{m}(D)$ is set as $\widetilde{Q}_{\ell}(D)+\mathcal{N}(0,1)\times\sqrt{{\sigma_{m}}^{2}-{\sigma_{\ell}}^{2}}$. This will become clear by Theorem 1’s Result (ii) to be presented in Section III-E.

An example to explain Algorithm 1. Table II provides an example for better understanding of Algorithm 1. We consider three types of queries. In particular, $Q_{1},Q_{4},Q_{6},Q_{10},Q_{12}$ are type $1$-queries; $Q_{2},Q_{5},Q_{8},Q_{9},Q_{11}$ are type $2$-queries, and $Q_{3},Q_{7},Q_{13}$ are type $3$-queries.

Our noise-reuse rules of Algorithm 1 are designed to minimize the accumulated privacy cost. To explain this, inspired by [13], we define the privacy loss to quantify privacy cost. We analyze the privacy loss to characterize how privacy degrades in a fine-grained manner, instead of using the composition theorem by Kairouz et al. [27]. Although [27] gives the state-of-the-art results for the composition of differentially private algorithms, the results do not assume the underlying mechanisms to achieve differential privacy. In our analysis, by analyzing the privacy loss of Gaussian mechanisms specifically, we can obtain smaller privacy cost.

For a randomized algorithm $Y$, neighboring datasets $D$ and $D^{\prime}$, and output $y$, the privacy loss $L_{Y}(D,D^{\prime};y)$ represents the multiplicative difference between the probabilities that the same output $y$ is observed when the randomized algorithm $Y$ is applied to $D$ and $D^{\prime}$. Specifically, we define

where ${\mathbb{F}}\left[{\cdot}\right]$ denotes the probability density function.

For simplicity, we use probability density function ${\mathbb{F}}\left[{\cdot}\right]$ in Eq. (2) above by assuming that the randomized algorithm $Y$ has the continuous output. If $Y$ has the discrete output, we replace ${\mathbb{F}}\left[{\cdot}\right]$ by probability mass function ${\mathbb{P}}\left[{\cdot}\right]$.

When $y$ follows the probability distribution of random variable $Y(D)$, $L_{Y}(D,D^{\prime};y)$ follows the probability distribution of random variable ${L}_{Y}(D,D^{\prime};Y(D))$, which we write as ${L}_{Y}(D,D^{\prime})$ for simplicity.

We denote the composition of some randomized mechanisms $Y_{1},Y_{2},\ldots,Y_{m}$ for a positive integer $m$ by $Y_{1}\|Y_{2}\|\ldots\|Y_{m}$. For the composition, the privacy loss with respect to neighboring datasets $D$ and $D^{\prime}$ when the outputs of randomized mechanisms $Y_{1},Y_{2},\ldots,Y_{m}$ are $y_{1},y_{2},\ldots,y_{m}$ is defined by

When $y_{i}$ follows the probability distribution of random variable $Y_{i}(D)$ for each $i\in\{1,2,\ldots,m\}$, clearly $L_{Y_{1}\|Y_{2}\|\ldots\|Y_{m}}(D,D^{\prime};y_{1},y_{2},\ldots,y_{m})$ follows the probability distribution of random variable $L_{Y_{1}\|Y_{2}\|\ldots\|Y_{m}}(D,D^{\prime};Y_{1}(D),Y_{2}(D),\ldots,Y_{m}(D))$, which we write as $L_{Y_{1}\|Y_{2}\|\ldots\|Y_{m}}(D,D^{\prime})$ for simplicity.

With the privacy loss defined above, we now analyze how to reuse noise when a series of queries are answered under differential privacy. To this end, we present Theorem 1, which presents the optimal ratio of reusing noise to minimize privacy cost.

Eq. (4) of Theorem 1 clearly indicates the noise use ratio $\frac{{\sigma_{m}}^{2}}{[\min(\boldsymbol{\Sigma}_{t})]^{2}}$ of Case 2B) in Algorithm 1 (see Line 22 of Algorithm 1), and the noise use ratio $1$ of Cases 2A) and 2C) in Algorithm 1 (see Lines 15 and 30 of Algorithm 1).

By considering $r=0$ in Result (i) of Theorem 1, we obtain Corollary 1, which presents the classical result on the privacy loss of a single run of the Gaussian mechanism.

Corollary 1 has been shown in many prior studies [20, 9, 10] on the Gaussian mechanism for differential privacy.

By considering $r=0$ in Result (i) of Theorem 1, we obtain Corollary 2, which presents the privacy loss of the naive algorithm where the noisy response to each query is generated independently using fresh noise.

Among the above cases, Cases 2A) and 2C) do not incur additional privacy cost since they just use previous noisy results and generate fresh Gaussian noise, without access to the dataset $D$. In contrast, Cases 1) and 2B) incur additional privacy cost since they need to access the dataset $D$ to compute the true query result $Q_{m}(D)$. Hence, in Algorithm 1, the privacy cost is updated in Cases 1) and 2B), but not in Cases 2A) and 2C). In this section, we explain the reason that the privacy cost is updated in Algorithm 1 according to Lines 3 and 5 for Case 1), and Lines 18 and 19 for Case 2B).

When our Algorithm 1 is used, we let the above randomized mechanism $Y_{i}$ be our noisy response function $\widetilde{Q}_{i}$. When $\widetilde{Q}_{1},\widetilde{Q}_{2},\ldots,\widetilde{Q}_{i-1}$ on dataset $D$ are instantiated as $y_{1},y_{2},\ldots,y_{i-1}$, if the generation of $\widetilde{Q}_{i}$ on dataset $D$ uses $\widetilde{Q}_{j}$ for some $j<i$, then the auxiliary information $\textup{aux}_{i}$ in the input to $\widetilde{Q}_{i}$ contains $y_{j}$ ($\textup{aux}_{1}$ is $\emptyset$). For the consecutive use of our Algorithm 1, it will become clear that the privacy loss, defined by $L_{\widetilde{Q}_{1},\widetilde{Q}_{2},\ldots,\widetilde{Q}_{m}}(y_{1},y_{2},\ldots,y_{m}):=\ln\max_{\textup{neighboring datasets $D,D^{\prime}$}}\frac{{\mathbb{F}}\left[{\cap_{i=1}^{m}\left[\widetilde{Q}_{i}(D)=y_{i}\right]}\right]}{{\mathbb{F}}\left[{\cap_{i=1}^{m}\left[\widetilde{Q}_{i}(D^{\prime})=y_{i}\right]}\right]}$, follows a Gaussian probability distribution with mean $\frac{V}{2}$ and variance $V$ for some $V$, denoted by $\mathcal{N}(\frac{V}{2},V)$. For such a reason that form of privacy loss, the corresponding differential-privacy level is given by the following lemma.

Based on the privacy loss defined above, we have the following theorem which explains the rules to update the privacy cost in our Algorithm 1.

Theorem 2 explains the rules to update the privacy cost in Algorithm 1. Specifically, Result ⑤ gives Lines 3 and 5 for Case 1), and Result ⑥ gives Lines 18 and 19 for Case 2B).

Based on Theorem 2, we now analyze the total privacy cost when our system calls Algorithm 1 consecutively.

At the beginning when no query has been answered, we have $V=0$ (note that $\mathcal{N}(0,0)\equiv 0$). Then by induction via Corollary 1 and Theorem 2, for the consecutive use of Algorithm 1, the privacy loss is always in the form of $\mathcal{N}(\frac{V}{2},V)$ for some $V$. In our Algorithm 1, the privacy loss changes only when the query being answered belongs to Cases 1) and 2B). More formally, we have the following theorem.