$\uppi$QLB: A Privacy-preserving with Integrity-assuring Query Language for Blockchain

Consider a blockchain-based stock market where the data records in the blockchain are about the information related to the various stocks (e.g., share prices, available shares, transaction amount, number of shares). In such a system, the SPs will host the information related to the stock market.

To run transactions (e.g., buy, sell, or check the market prices on specific shares), a client will first need to query the system by sending a request to the SPs. The query will contain information that if the (potentially malicious) SP learns, it can impact the result. For example, if an SP learns that a specific stock (mentioned in a client’s query) is either a hot stock (i.e., many clients queried it) or people are bidding on opening price, then the malicious SP could tamper the result and influence the market (e.g., increase the actual price of a specific share). However, if integrity of the response can be verified, the malicious SP will be not able to carry out such an activity.

In another example, let us consider a blockchain-based rental-car system where car information (e.g., price, model, built-year, color, customer pick-up location, customer drop-off location, city, and rental-period) is the data recorded in the blocks. To rent cars, clients will first perform a search to find their preferred ones. To do so, clients send queries to various SPs. Such queries might however contain sensitive information (e.g., pick-up & drop-off locations, price ranges, or rental-period). If SPs learn such confidential information, it can jeopardize the client’s privacy.

$\uppi$QLB enables running SQL-like queries over blockchain-based systems. In this section, we describe some examples of such queries.

Using the rental-car example, we assume that a client wishes to find the minimum price for a specific car model with a specific color. This client also prefers to hide the car model and the color of the car in the query. Hence, the client generates the following query:

SELECT MIN($price$) WHERE $car_{-}model$ = ? $\wedge$ $color$ = ?

Note that “$?$” indicates the sensitive information that $\uppi$QLB must hide from SPs when sending the query.

Let us consider another example, namely a healthcare system. A client may need to find the total number of patients diagnosed with a specific disease in a specific hospital, or the total number of patients visited a specialist at a specific hospital/location.

Using $\uppi$QLB, the client can hide the information s/he prefers (e.g., $disease$ and $dr_{-}spec$) by generating the following query:

SELECT COUNT($pt_{-}id$) WHERE $disease$ =? $\wedge$ $dr_{-}spec$ =?

Let $\mathbb{G}$ denote an Abelian group and an integer $p>1$. FSS [30, 31, 32] is defined by a tuple ($\sf{\mathsf{G}en}$, $\sf{\mathsf{E}val}$):

• •

  ${\sf{\mathsf{G}en}}(1^{\uplambda},f)\rightarrow K_{1},...,K_{p}$: It gets a security parameter $1^{\uplambda}$ and a function $f:\{0,1\}^{n}\rightarrow\mathbb{G}$, then splits $f$ into $p$ function shares (or keys) ($K_{1},...,K_{p}$).

• •

  ${\sf{\mathsf{E}val}}(K_{i},x)\rightarrow y_{i}$: It takes $K_{i}$ and $x$ as input and outputs $y_{i}$ which is the result corresponding to the party $i$.

FSS provides both correctness and security. FSS’s correctness ensures that adding up all outputs from $\sf{\mathsf{E}val}$ is equivalent to the original $f$, i.e., $\sum_{i=1}^{p}y_{i}=y=f(x)$. For security, FSS guarantees any strict subset of $K_{i}$ does not reveal anything about the original function $f$. The work in [30] provides a game-based definition of FSS security in Definition 1. This game models an adversary ($\sf{\mathcal{A}dv}$) capable of compromising $p-1$ shares and aiming to use this knowledge to identify which $\sf{\mathcal{A}dv}$-generated function ($f^{0}$ or $f^{1}$) is used to generate these $p-1$ shares. Theorem 1 states that an FSS scheme is considered secure if $\sf{\mathcal{A}dv}$ cannot distinguish $f^{0}$ and $f^{1}$ based on $p-1$ output shares with more than a negligible probability. In other words, without all $p$ shares, $\sf{\mathcal{A}dv}$ cannot infer anything about the original $f$.

In this work, we consider two types of $f$ for FSS:

• •

  Distributed point function $f_{a,y}$ that is evaluated to a fixed element $y\in\mathbb{G}$ on a specific input $a$, and to $0$ otherwise, i.e.:

  $$f_{a,y}(x)=\begin{cases}y,&\text{if }\ x=a\\ 0,&\text{otherwise}\end{cases}$$

  (1)

• •

  Interval function $f_{a,b,y}$ that is evaluated to $y\in\mathbb{G}$ only when an input is within a specific interval $[a,b]$, and to $0$ otherwise, i.e.:

  $$f_{a,b,y}(x)=\begin{cases}y,&\text{if }\ a\leq x\leq b\\ 0,&\text{otherwise}\end{cases}$$

  (2)

For these two types, Theorem 1 implies confidentiality of $a$, $b$ and $y$, i.e., their values cannot be inferred from any of the function shares.

Blockchain can be considered as a public database. It is a decentralized distributed database where the data records are transparent for public, i.e., everyone can access the data. To query the public database with privacy-preserving guarantees, several studies have been conducted and different models have been proposed. Recently, with the introduction of FSS, several researchers proposed different models to privately query the public records [33, 31, 34]. In such models, a client generates keys using FSS with $y=1$ in Eq.1 or 2, and sends these shares to the servers. A given server evaluates the function share on each record of the database, sums the evaluation together and returns the result to the client. The client upon receiving all the results adds them up and finds the result of the query.

In all these settings, while FSS guarantees confidentiality of client queries, a client is unable to verify the integrity of the results received from servers. In particular, a malicious server can introduce an error $\delta$ to the final output without being detected by the client. This can be done by having the malicious server respond to the subquery with $y_{\sf{\mathcal{A}dv}}+\delta$, instead of $y_{\sf{\mathcal{A}dv}}$, where $y_{\sf{\mathcal{A}dv}}$ is a benign output from ${\sf{\mathsf{E}val}}(K_{\sf{\mathcal{A}dv}},x)$. In this case, after aggregating all outputs, the client obtains the incorrect result that is off from the expected value by $\delta$, i.e., $(\sum_{i=1,i\neq\sf{\mathcal{A}dv}}^{p}y_{i})+(y_{\sf{\mathcal{A}dv}}+\delta)=(\sum_{i=1}^{p}y_{i})+\delta=y+\delta=f(x)+\delta$.

In the blockchain context, verifiable integrity of the query response is of paramount importance due to the followings:

• •

  Blockchain is a decentralized system, i.e., there is no central authority controlling blockchain; hence, some servers might be malicious. It is therefore important that a client can verify the query response. This is different for public databases, as they are owned by organizations that can protect servers and detect malicious parties at early stages.

• •

  The size of a blockchain database is significantly high and lightweight devices are unable to download the entire database to perform queries locally. Hence, it is important to enable them to verify the query responses.

This work describes $\uppi$QLB as a solution to address the shortcomings of existing models. $\uppi$QLB makes use of FSS to enable private search of blockchain databases, while providing the integrity of the query results and retaining the original goal of ensuring the confidentiality of clients’ queries.

As shown in Figure 4, $\uppi$QLB is comprised of two entities:

• •

  Service Provider (SP) is the full node or the miner in blockchain terminology. An SP retains a full replica of the blockchain database and is able to provide query processing services.

• •

  Client is a user of the system. It sends query requests to SPs. A client can be either a light node or an external node. As mentioned, a light node in the blockchain terminology refers to the node that only hosts the block header data. However, an external node is the node/user who does not hold any of he blockchain data and does not exist in the blockchain network. It only sends queries to SPs.

In terms of algorithms, $\uppi$QLB consists of a tuple $({\sf{\mathsf{G}en}},{\sf{\mathsf{E}val}},{\sf{\mathsf{V}erif}})$, defined as follows:

• •

  ${\sf{\mathsf{G}en}}(1^{\uplambda},q,s)\rightarrow q^{\prime},K_{1},...,K_{p}$: It takes as input a security parameter $1^{\uplambda}$, a query with the format described in $\S$IV-B and a set of secret expressions $s$ in $q$. It then outputs $p$ function shares and a private query $q^{\prime}$ that removes $s$ value (i.e., replacing it with $?$ as in Section II). This function is performed by the client.

• •

  ${\sf{\mathsf{E}val}}(K_{i},D,q^{\prime})\rightarrow y_{i}$: It takes as input a function share $K_{i}$, which corresponds to each SP, $D$ – the entire data from blockchain and a private query $q^{\prime}$. It then performs an evaluation using $K_{i}$ and $q^{\prime}$ on $D$ and outputs $y_{i}$. This function is performed by a SP.

• •

  ${\sf{\mathsf{V}erif}}(y_{1},...,y_{p})\rightarrow R$: It takes as input all the share outputs received from the SPs. Then, it verifies whether all $y_{i}$-s are honestly generated on the same blockchain data. If it detects any malformed $y_{i}$, it outputs $\perp$ (i.e., aborts). Otherwise, it produces the query result $R$. This function is performed by the client.

$\uppi$QLB is designed to facilitate the execution of SQL-liked queries on blockchain databases. It first limits the number of blocks that SPs need to search over, then transforms the SQL syntax into a format compatible with the blockchain system. It then uses FSS [31] to divide the query into $p$ shares (queries).

Fig 5 depicts the $\uppi$QLB’s query format, where type refers to one of the following query types: SUM, COUNT, AVG, MIN and MAX queries. blk_range_cond specifies the time range, i.e., $t_{1}<blk_{-}range_{-}cond<t_{2}$, where $t_{1}$ is the lower bound and $t_{2}$ is the upper bound. This condition is necessary because in blockchain there is no table to be specified in order to narrow down the search on a database; but rather the full history of all the generated blocks since the genesis block. Hence, it is a must to narrow down the number of blocks that the SP needs to search over; otherwise, the search can be too expensive, time-consuming or may never stop. Thus, $\uppi$QLB shortens the number of blocks by introducing the blk_range_cond, $t_{1}$ must be bigger than $t_{g}$, which refers to the time that the genesis block was generated, and $t_{2}$ must be lower than $t_{c}$, which is the current time. $\uppi$QLB has considered another condition for blk_range_cond (i.e., the difference between $t_{1}$ and $t_{2}$) which should be limited and must not exceed a threshold $\uptau$. This is to ensure that the number of blocks generated between $t_{1}$ and $t_{2}$ does not exceed a given threshold. The value of $\uptau$ depends on the block generation rate of the network. If the block generation rate is high, then $\uptau$ must be low; and if the block generation rate is low, then $\uptau$ can be bigger.

$\uppi$QLB is designed to support two different conditions: $(i)$ single, and $(ii)$ range condition.

• •

  Single condition is when the query condition has only one value. That is in the query format where expr in the condition equals to only one secret value. In this case, the ${\sf{\mathsf{G}en}}$ function defines $f$ based on Eq.1.

• •

  Range condition is when the condition is within a range interval. In this condition, the ${\sf{\mathsf{G}en}}$ function defines $f$ following Eq.2.

Additionally, $\uppi$QLB is designed to support two query models: simple and complex. The simple model refers to when a query has only one condition (either single or range). The complex model refers to when a query is composed of several conditions using $AND$ and $OR$. Note that, $\uppi$QLB supports not more than one range condition in one query request.

Figure 4 illustrates how a query processing works in $\uppi$QLB, which involves the following steps:

1. 1.

   The client generates a query, $q$ and specifies the secret information (i.e., the information that the client prefers not to share with SPs) to specify the private query $q^{\prime}$.

2. 2.

   Using $\uppi$QLB.$\sf{\mathsf{G}en}$ function, the query is divided into several subqueries/function shares, depicted as $f_{i}$ in Figure 4.

3. 3.

   The client forwards the subqueries to SPs.

4. 4.

   SPs execute the subquery using $\uppi$QLB.$\sf{\mathsf{E}val}$ function and return the results back to the client.

5. 5.

   The client combines the results and generates the final output of the query using the $\uppi$QLB.$\sf{\mathsf{V}erif}$ function. This function enables the client to either abort or acquire the query’s response.

$\uppi$QLB assumes that at least one of the SPs is honest, i.e., it always honestly follows the protocol and does not collude with other SPs. The rest of the SPs can be malicious. The malicious SP ($\sf{\mathcal{A}dv}$) may attempt to learn the sensitive information from the client’s query in order to set up different attacks. For example, in a blockchain-based stock market application, if $\sf{\mathcal{A}dv}$ finds out the shares that the client is interested in purchasing, $\sf{\mathcal{A}dv}$ may modify the price of the share to charge the client more; or $\sf{\mathcal{A}dv}$ may use the location information to endanger the client. Moreover, $\sf{\mathcal{A}dv}$ can also tamper with the query and the response. Tampering with the query means the adversary may search on a different query instead of the client-provided query. Tampering with the response leads to returning an incorrect or forged response.

We assume that the client is not malicious. A malicious client is a client that attempts to access private data records or tampers with the existing records in the server. This is inapplicable here because $\uppi$QLB is proposed for the public data records, where the database is not private and not directly modifiable by the client. Hence, everyone can see the data publicly. $\uppi$QLB also assumes that the communication between an SP and the client is over a secure channel (e.g., SSL) and the user of the system is not compromised, i.e., the client follows the protocol.

At high level, $\uppi$QLB provides two security properties:

1. 1.

   Query Confidentiality: it ensures that sensitive information from the query remains hidden to SPs.

2. 2.

   Response Integrity: it guarantees detection when malicious SPs tamper with the query responses.

The Query Confidentiality property is defined using the security game provided in Definition 2. It models $\sf{\mathcal{A}dv}$ who can compromise $p-1$ SPs with the goal of learning some sensitive information about the query. It assumes $\sf{\mathcal{A}dv}$ has oracle access to all $\uppi$QLB algorithms. $\sf{\mathcal{A}dv}$ is allowed to submit two queries to the challenger as long as these queries contain the same structure and differ only by the secret value in their query condition. The challenger randomly selects one of the two submitted queries, computes the private query $q^{\prime}$ and $p-1$ shares from the selected query and outputs them to $\sf{\mathcal{A}dv}$. $\sf{\mathcal{A}dv}$ wins the game if it can identify which query is used by the challenger. 

Next, we formalize the Response Integrity property with the security game provided in Definition 3. It models $\sf{\mathcal{A}dv}$ that aims is to manipulate the query response by gaining control of $p-1$ SPs. 

Ultimately, we want to prove Theorem 2 and Theorem 3 below to formally guarantees Query Confidentiality and Response Integrity, respectively, in $\uppi$QLB. 

The proofs for these two theorems are provided in Section V-B after various concepts are introduced.

We now discuss how to construct $\uppi$QLB to serve a query with a single condition.

${\sf{\mathsf{G}en}}(1^{\uplambda},q,s)$: depending on the query condition, single or range, this function first samples a random value $y\in\mathbb{G}$ and constructs the $f$ function from $y$, where $f:\{0,1\}^{n}\rightarrow\mathbb{G}$. In this work, we assume the size of group $\mathbb{G}$ is exponential in terms of $\uplambda$. For instance, $f$ could be $f:\{0,1\}^{n}\rightarrow\mathbb{Z}_{2^{\uplambda}}$. Among the above query examples, $q_{1}$ and $q_{3}$ are single and $q_{2}$ and $q_{5}$ are range conditions. Thus, if we pass $q_{1}$ and $q_{2}$ to the ${\sf{\mathsf{G}en}}$ function, it behaves as follows:

• •

  Single condition – ${\sf{\mathsf{G}en}}(1^{\uplambda},q_{1},\{Item\})$: $\sf{\mathsf{G}en}$ takes both $q_{1}$ and the secret attribute Item as input. This signifies that Item is sensitive information and the client aims to hide its value in the query. Thus, $\sf{\mathsf{G}en}$ randomly samples $y$ from $\mathbb{G}$ and defines $f$ as follows:

  $$f(x)=\begin{cases}y,&\text{if }\ x=2\\ 0,&\text{otherwise}\end{cases}$$

  (3)

• •

  Range condition – ${\sf{\mathsf{G}en}}(1^{\uplambda},q_{2},\{Price\})$: $\sf{\mathsf{G}en}$ takes as an input the $q_{2}$ and the secret attribute Price. Again, it randomly samples $y$ from $\mathbb{G}$ and then defines the $f$ as follows:

  $$f(x)=\begin{cases}y,&\text{if }\ 1<x<10\\ 0,&\text{otherwise}\end{cases}$$

  (4)

In this work, we assume that the range condition evaluates to one record only. To allow for multiple records within a specified range, $\uppi$QLB can be extended by adopting the interval evaluation technique used by Splinter [34], which we leave for future work. After defining $f$, it then calls FSS.${\sf{\mathsf{G}en}}(1^{\uplambda},f)$ to output $p$ function shares. The shares and the private query $q^{\prime}$ are sent to SPs in a format of $\{K_{i},q^{\prime}\}$. 

${\sf{\mathsf{E}val}}(K_{i},D,q^{\prime})$: the SP, upon receiving $\{K_{i},q^{\prime}\}$, performs three operations on $D$ (blockchain data). First, it specifies/limits the number of blocks (to process the query) in $D$ according to $blk_{-}range_{-}cond$ in the $q^{\prime}$. Second, it creates an intermediate table depending on the query condition (single or range, which can be extracted from $q^{\prime}$). If the query is a single condition query, the $SP$ executes $GROUPBY$ over the column in the query condition (to recall the query condition, see Figure 5). And if the query is a range condition query, then the $SP$ creates the intermediate table over the column in the query type (to recall the query type, see Figure 5) without executing $GROUPBY$. Third, it generates the binary representation of the values of the column in the query type, denoted as $BIN$.

After that, $\sf{\mathsf{E}val}$ evaluates two sub-functions on the intermediate table: $(i)$ $comp$, stands for compute; and $(ii)$, $merg$, stands for merge. The $comp$ is equivalent to FSS.$\sf{\mathsf{E}val}$ except it is executed over the binary representation of the values of the column in the query type, $BIN$. That is, $comp$ takes as an input two values: $(i)$ $c$ that refers to the column in the condition, the value of which is hidden; and $(ii)$ $BIN$; and performs the FSS.$\sf{\mathsf{E}val}$ function over these two inputs. $comp$ is executed $l$ times, where $l$ is the number of columns of $BIN$, in other word, the maximum number of bits required to represent the binary value of the data, $2^{l}$. The output of each execution of $comp$ is given to the $merg$ function. $merg$ takes as input all the values generated from $comp$ and merge/concatenate them together and generates a binary array, $y_{i}$, with $l$ elements. The $y_{i}$ is the final output of $\sf{\mathsf{E}val}$ and is returned to the client. Algorithm 1 details the $\sf{\mathsf{E}val}$ function.

The behaviour of this function, specifically the $comp$ sub-function, depends on the query types. We now explain this function in detail for each query type that $\uppi$QLB supports, namely, SUM, AVG, COUNT, MIN, and MAX.

• •

  SUM: assume that the $SP$ receives $\{K_{i},q_{1}^{\prime}\}$. $SP$ generates the intermediate table for this query, depicted in Figure 9. Then, it generates the binary representation of the values of the column $SUM(Price)$, shown in Figure 9, as the $BIN$ (recall that the size of each row in the $BIN$ is $l$, i.e., the maximum bits required to represent the binary value of the data). Finally, the $\sf{\mathsf{E}val}$ function is triggered. $\sf{\mathsf{E}val}$ function first executes the $comp$ subfunction which takes as an input $Item$ and $BIN$ as in Figure 9. One execution of the $comp$ is as follows:

  $$b_{k}=\displaystyle\sum_{j=0}^{n}FSS.{\sf{\mathsf{E}val}}(K_{i},c_{j})\cdot BIN[j][k]$$

  (5)

  This function is repeated for all the columns in $BIN$, Figure 9. The outputs of each execution of $comp$, i.e., $b_{k}$, are sent to the $merg$ subfunction, where the $b_{k}$-s are merged/concatenated into an array $y_{i}$. The final $y_{i}$ is then returned to the client. Algorithm 1 depicts the $\sf{\mathsf{E}val}$ function execution.

  

• •

  COUNT: In this query type, the $\sf{\mathsf{E}val}$ execution is similar to the SUM-based query type. Assume $SP$ receives $\{K_{i},q_{2}\prime\}$. It creates the intermediate table and $BIN$ as depicted in Figure 10. Then, $SP$ can apply $comp$ sub-function for all columns in $c$ and appends the results into a single array $y_{i}$, which is in turn sent back to the client.

  

• •

  AVG: This type of query results in a similar execution of $\sf{\mathsf{E}val}$ as the SUM- and COUNT-based query types. Suppose $SP$ receives $\{K_{i},q_{3}\prime\}$, we refer to Figure 11 for the resulting intermediate table and $BIN$ variable in this query.

  

• •

  MAX: among above queries, the $q_{4}$ is a MAX query which is an example of the complex query model; hence, we defer its explanation to $\S$ V-C.

• •

  MIN: if the $SP$ receives $Q_{i}=\{K_{i},q_{5}\prime\}$, it first creates the intermediate table and then performs the $comp$ and $merg$ similar to the previous queries. We thus omit its detail for brevity.

$\sf{\mathsf{V}erif}$ $(y_{1},...,y_{p})$: Upon receiving the results from all $SP$-s, the client executes the $\sf{\mathsf{V}erif}$ function to output the final results. Recall that $y_{i}$ is a binary array of the outputs from the $\sf{\mathsf{E}val}$ function executed by $SP_{i}$ on each column of the $BIN$ matrix. Thus, in order to find the final result of the query, the client needs to perform the $\sf{\mathsf{V}erif}$ function on each bit of the $y_{i}$. To perform this, the client follows these steps: $(i)$, it creates a binary matrix of the received $y_{i}$-s; $(ii)$, it adds the values of each column of the matrix and include it to a $temp$ variable. $if(temp==y)$ then it adds a binary value $1$ into the result array, otherwise $if(temp==0)$ then it adds a binary value $0$ into the result array; if $temp$ is neither $y$ nor $0$, the client detects a misbehaviour and aborts the protocol. This could be due to the server being malicious or other errors in the systems. Algorithm 2 details the $\sf{\mathsf{V}erif}$ function.

This section provides proofs for Theorem 2 and Theorem 3.

In this section, we explain how complex queries are executed. As mentioned, complex queries are the ones with the combination of $AND$ and $OR$ in the query condition. That is, the query can have more than two conditions. We support the following complex queries:

• •

  AND - Single Conditions: if the complex query is formed by the AND, we concatenate the conditions into one condition and behave the newly formed query as a simple model query. Assume that the query condition is $c_{1}=secret_{1}$ AND $c_{2}=secret_{2}$ AND … AND $c_{n}=secret_{n}$, where each query condition is a single condition. $\uppi$QLB concatenates these conditions into one: $C=c_{1}||c_{2}||...||c_{n}$. This results in a single condition query of the simple model which $\uppi$QLB can process, explained in $\S$V-A.

• •

  OR - Single Condition: if the complex query is formed by the OR and the query conditions are disjoint, i.e., $c_{1}$ does not overlap with $c_{2}$, then we create $f$ for each condition individually and then add all $f$-s together. Assume that the query condition is $c_{1}=secret_{1}$ OR $c_{2}=secret_{2}$ OR $...$ OR $c_{n}=secret_{n}$. $\uppi$QLB generates $f$ for each $c_{i}$ using the simple model functions, then combine all the generated functions, i.e, $f=f_{c_{1}}+f_{c_{2}}+...+f_{c_{n}}$. And finally it passes $f$ to the $\uppi$QLB.$\sf{\mathsf{G}en}$ function, explained in the simple model above, $\S$V-A

Below, we explain an example of a complex query.

Among the above queries, $q_{4}$ is a complex query as it contains $\wedge$ in the query condition. Now assume that the $SP$ receives $\{K_{i},q_{4}\prime\}$. In this type of query, compared to the previous queries explained in $\S$V-A, $SP$ performs one additional task when creating the intermediate table. It first creates a join column consisting of two columns in the query condition (i.e., for $q_{4}\prime$, it is $Color$ and $Item$). And then it performs the $GROUPBY$ over this newly created column. Thus, in this example, $q_{4}\prime$, $SP$ creates the intermediate table as shown in Figure 12 based on the joint $Color-Item$ columns. Later, it generates $BIN$ (see Figure 12) for the column $MAX(Price)$. After the setup is finished, then it performs $comp$ and $merg$ on this intermediate table. The rest of this query is similar to execution of the rest of queries explained in $\S$ V-A.

Computation cost/complexity refers to the computations required to process the query and retrieve the data. This cost is $O(N\times logN)$ for Splinter, where $N$ is the number of database records. $\uppi$QLB requires less asymptotic time, i.e., $O(N\times l)$, where $l$ is a small constant indicating the number of bits required to represent each database column. Whereas Waldo’s computation cost grows linearly with the number of query predicates: $O(N\times p)$.

We calculated the computation complexity of $\uppi$QLB and then plotted its behaviour for different number of data records in the database. We then plotted the behaviour of Splinter and Waldo over the same set of data records used for $\uppi$QLB. For Waldo and Splinter we used the computation complexity provided in the original papers. As depicted in Figure 13, $\uppi$QLB performs slightly better compared to the baselines when the number of records in the database are small. However, when the record size increases, the performance of Waldo and Splinter deteriorates significantly compared to $\uppi$QLB. More specifically, when the number of data records increases from $10^{8}$ to $10^{9}$, we can see that $\uppi$QLB performs faster (a magnitude of two) compared to Splinter. This difference is even more when we compare $\uppi$QLB and Waldo, where for $10^{9}$ number of records $\uppi$QLB performs over four times faster than Waldo (with $2-predicates$). When the number of predicates increases Waldo’s performance degrades the most compared to Splinter and $\uppi$QLB.

After we evaluated the computation cost of $\uppi$QLB, we switched our attention to the bandwidth comparison. We calculated the client and server bandwidth separately and compared the $\uppi$QLB’s results with the baselines. Figure 14 illustrates the evaluation results. For the client bandwidth, we compared $\uppi$QLB with Waldo only as Splinter did not provide enough information on the paper to allow us to compute the client’s bandwidth. The results show that in $\uppi$QLB, a client requires slightly less bandwidth to perform queries compared to Waldo. This is due to the fact that Waldo generates two pairs of FSS keys for each SP. That is, when the number of SPs are two, Waldo’s client generates in total $four$ pairs of keys to send to the SPs. While in $\uppi$QLB client only generates one key for each SP.

However, the server’s bandwidth is computed based on: $(i),$ the round trips between client and server, $(ii),$ the size of the data that the server sends to client, and $(iii),$ the Maximum Transmission Unit, $MTU$, each server has. We assume all the servers are running on AWS (Amazon Web Services) EC2 instances and each instance type is $m5.xlarge$ with $10\ Gbps$ network bandwidth and the $MTU$ is $1500$ bytes. As illustrated in Figure 14, the server’s bandwidth in $\uppi$QLB is constant and independent from the number of records. This is exactly similar in Splinter for sum-based queries. However, Splinter requires $10$ times more bandwidth for TOPK, MIN, and MAX queries compared to $\uppi$QLB. This is due to the extra communication between server and client for building the intermediate table in Splinter. Waldo, however, requires the highest bandwidth compared to $\uppi$QLB and Splinter as it grows linearly when the number of records increases.

Last, we evaluated the latency. We assumed the minimum latency between client and the server (SP) for each message is $1\ ms$. To plot the results, we computed the latency for one query over different size of records and repeated it for $\uppi$QLB, Splinter, and Waldo (with $2,4,$ and $8$ predicates). Note that the number of predicates does not affect the latency of the $\uppi$QLB and Splinter. However, the latency of Waldo varies depending on the number of predicates. As illustrated in Figure 15, $\uppi$QLB has the lowest latency compared to the baselines. More specifically, when the number of records are small (below $2^{27}$), $\uppi$QLB, Splinter, Waldo-2-predicates, and Waldo-4-predicates have almost the same latency, less than $2$ seconds. However, when the number of records increases, the latency surges significantly for Splinter and Waldo, while $\uppi$QLB experiences a moderate increase in latency. For example, when the number of records is increased to $2^{28}$, $\uppi$QLB’s latency is still $1$ seconds; however, Splinter’s and Waldo-4-predicates’s latency surges to around $5$ seconds. For the maximum records of $2^{30}$, $\uppi$QLB’s latency is around $5$ seconds which is a factor of $2$ and $4$ times less than Waldo-2-predicates, and Splinter and Waldo-4-predicates, respectively. Waldo-8-predicates experiences the highest latency.

Several prior work [22, 23, 24, 25, 26, 27, 28, 29] proposed methods to run queries over an encrypted database. Data in such systems is encrypted before stored, and queries are executed over encrypted data. The aim here is to protect private data from an untrusted or a compromised server. Hence, the purpose of such systems is different from the one of $\uppi$QLB, which aims to protect the confidentiality of queries over a public database, where servers could be malicious and the database is publicly accessible.

Lastly, current search approaches for blockchain databases require users to maintain the entire blockchain to run queries (in order to support query integrity). This is not an economical approach as the maintenance cost of blockchain is significant and blockchain’s data size is considerably large. Many companies, including IBM [9], Oracle [10], FlureeDB[8], and BigchainDB [11] provided a search functionality for blockchain databases that unfortunately rely on a central trusted party that executes user’s queries. This obviously causes a single point of failure and confidentiality as well as integrity guarantees are not also supported.

In $2019$, Xu et al. [12] proposed vChain to address a limitation in the previous search schemes for blockchain. vChain’s main focus was to provide the integrity for the search without requiring nodes to download the entire blockchain database. It enabled verifiable Boolean range queries for blockchain databases, where clients are able to verify the results of their searches. Although vChain did achieve a good search performance and provided integrity, it did not consider the confidentiality of clients’ queries.

VQL [49] is another work that has been proposed for search improvement on blockchain databases. To provide both efficient and verifiable data queries, VQL adds a Verifiable Query Layer to the blockchain systems. This middleware layer extracts transactions stored in the underlying blockchain system and reorganizes them in databases to provide various query services for public users. It has also applied a cryptographic hash value for each constructed database to prevent data being modified. The main issue with this approach is clearly the extra layer added to the blockchain system. This directly impacts the blockchain size. Additionally, it degrades the overall performance of the blockchain systems as reorganizing and creating the extra layer incur an overhead on top of the tasks the blockchain systems need to perform. More importantly, VQL does not provide the query confidentiality.