Soteria: A Provably Compliant User Right Manager
Using a Novel Two-Layer Blockchain Technology

As consumers are not expected to understand formal languages, the ESA notation is designed to provide a natural language interface. The sharing agreements can be translated from formal to natural language using a rule-based translation. The previous example can be expressed in natural language as follows:

“Stanford Medical Center can read the age, ethnicity and PSA of Bob’s EHR for research and if the PSA is greater than or equal to 2.”

While the automatically generated sentences can be verbose and clunky due to the rule-based translation, they are understandable, and they are guaranteed to correspond exactly to the code of the agreement. Furthermore, the ESA notation is designed so that a user can define their own sharing agreement in natural language. Previous work has shown that it is possible to automatically translate natural language access controls into attribute-based policies for personal data sharing [15, 16], and the same semantic parsing technology is used here. Thorough analysis of semantic parsing is out of scope for this paper.

To prove compliance to an external auditor, Soteria stores the requester, the purpose and the final query, right before it is issued to the database, including all the clauses related to the sharing agreements. Using the set of the sharing agreements in force at the time, the auditor can then formally verify that the query was compliant. Given a query from requester $r$ for purpose $p$ in the audit logs of the form:

$$\texttt{SELECT}~{}\bar{f}~{}\texttt{FROM}~{}t~{}\texttt{WHERE}~{}\pi$$

and sharing agreements of the form:

	$\displaystyle\gamma_{1},\pi_{1}(r,p)\texttt{:}\left[f_{1},f_{2},\ldots\right]~{}~{}\texttt{of}~{}~{}t,\pi_{1}(f_{1},f_{2},\ldots)$
	$\displaystyle\gamma_{2},\pi_{2}(r,p)\texttt{:}\left[f_{1},f_{2},\ldots\right]~{}~{}\texttt{of}~{}~{}t,\pi_{2}(f_{1},f_{2},\ldots)$
	$\displaystyle\ldots$

the query is compliant if and only if

	$\displaystyle\pi\models$	$\displaystyle\left(\gamma=\gamma_{1}\wedge\pi_{1}(r,p)\wedge\pi_{1}(f_{1},f_{2},\ldots)\right)\vee$
		$\displaystyle\left(\gamma=\gamma_{2}\wedge\pi_{2}(r,p)\wedge\pi_{2}(f_{1},f_{2},\ldots)\right)\vee\ldots$

This logical formula can be verified efficiently using a satisfiability modulo theory (SMT) solver [8].

To ensure that all queries are compliant, Soteria uses the following algorithm to construct a query that is guaranteed by construction to satisfy the sharing agreements. Given a SQL query from requester $r$ for purpose $p$ of the form:

$$\texttt{SELECT}~{}\bar{f}~{}\texttt{FROM}~{}t~{}\texttt{WHERE}~{}\pi$$

and sharing agreements of the form:

	$\displaystyle\gamma_{1},\pi_{1}(r,p)\texttt{:}\left[f_{1},f_{2},\ldots\right]~{}~{}\texttt{of}~{}~{}t,\pi_{1}(f_{1},f_{2},\ldots)$
	$\displaystyle\gamma_{2},\pi_{2}(r,p)\texttt{:}\left[f_{1},f_{2},\ldots\right]~{}~{}\texttt{of}~{}~{}t,\pi_{2}(f_{1},f_{2},\ldots)$
	$\displaystyle\ldots$

Soteria constructs a query of the form:

SELECT $\bar{f}\cap\left\{f_{1},f_{2},\ldots\right\}$ FROM $t$ WHERE $\pi$ AND
	$\left(\gamma=\gamma_{1}~{}\texttt{AND}~{}\pi_{1}(r,p)~{}\texttt{AND}~{}\pi_{1}(f_{1},f_{2},\ldots)\right)\texttt{OR}$
	$\left(\gamma=\gamma_{2}~{}\texttt{AND}~{}\pi_{2}(r,p)~{}\texttt{AND}\pi_{2}(f_{1},f_{2},\ldots)\right)\texttt{OR}\ldots$,

where $\gamma$ is the field in the table containing the owner of that row.

It is possible to prove that the result set of this query is consistent with the sharing agreement. Only the fields allowed by the agreement are returned, and a row is included only if the predicates in the sharing agreement in force for the row owner are satisfied.

We note that the SQL query, while correct, might not be very efficient, as it includes at least one clause for each owner of the data in the database. In our experience, this is sufficient, as in practice the same sharing agreement is used by many different consumers, so clauses can be unified when the query is constructed. As consumers’ preferences become more fine-grained, this might not be the case. Future work should investigate an optimization algorithm or an index structure suitable to queries of this form, so that both performance and formal correctness can be maintained.

A data requester can be an application user defined in CCPA or a company that stores user data. The URM component of Soteria does not verify the identity of the data requester. Such verification should be handled by the data transport protocol, and is out of scope of the Soteria protocol. Figure 1 shows that applications outside the Soteria box handles user registration and authentication. Soteria does not mandate any specific transport protocol; meaningful protocols could be REST, could be messaging-based [16], or could even be through physical media.

Furthermore, Soteria does not verify the purpose of the data access. The design assumes that at identification time, the data transport protocol will also compute the allowed purpose of data access. For example, using REST data transport, a medical data requester could be issued two different access tokens, one for clinical purposes and the other for research purposes. The correct purpose can be established through an existing business agreement between the data provider and data requester. If the data requester then uses the data in a manner inconsistent with the agreed purpose, the provider can use Soteria to establish that the fault lies with the requester.

To support limiting what data is stored by a business entity such as AWS, queries that manipulate data (insert, update, delete) are also intercepted by Soteria, and modified to match the ESA that limit the storage of data. Write queries that are not allowed by any ESA are not executed and are not logged.

To support permanent deletion of the data upon request by the consumer, the data itself (included in the VALUES and SET clauses of the insert and update queries) is masked in the audit log, as the audit log is immutable and append-only. For this reason, an ESA about data storage that depend on the specific values cannot be audited after the fact. Soteria disallows such ESA: only the set of fields to write can be controlled.

Continuing the previous example, the patient might issue a following the data storage ESA:

$\gamma=\text{``Bob''}:\left[\textit{age},\textit{ethnicity},\textit{PSA},\textit{phone},\textit{medication}\right]$

of EHR.write

This ESA allows age, ethnicity, PSA readings, contact information and current medications to be stored. It does not allow any other column to be stored, so the following query:

INSERT INTO EHR $\texttt{SET}~{}\textit{person}=\text{``Bob''},~{}\textit{age}=52,$
	$\textit{ethnicity}~{}=\text{white},~{}\textit{PSA}=1.5,~{}\textit{phone}=\text{``555-555-5555''},$
	$\textit{smoker}=\texttt{TRUE},~{}\textit{consumesAlcohol}=\texttt{FALSE},\ldots$

would be rewritten as the following:

INSERT INTO EHR $\texttt{SET}~{}\textit{person}=\text{``Bob''},~{}\textit{age}=52,$
	$\textit{ethnicity}~{}=\text{white},~{}\textit{PSA}=1.5,~{}\textit{phone}=\text{``555-555-5555''},$
	$\textit{smoker}=\texttt{NULL},~{}\textit{consumesAlcohol}=\texttt{NULL},\ldots$

Deletions are a special case of write, because they reduce the data that is stored about a specific customer rather than store new data. Hence, deletion is always allowed regardless of the current ESA. All deletions are logged, to prove that they were executed properly.

Additionally, upon revoking an ESA about data storage, some columns that were previously allowed might becomes disallowed. In that case, Soteria overwrites the data to set those columns to NULL. In case all columns are now disallowed, such as when all ESAs for a customer are revoked, Soteria deletes the row entirely. Both the database write (update or delete) and the ESA revocation are logged for later auditing.

Tendermint is a leader-based BFT approach that does not conduct leader selection, aiming to reduce the number of communication IOs. Unlike PBFT which is composed of two modes, normal mode and view-change mode, Tendermint can frequently change leaders (proposers) and make consensus progress under a single mode by using a predefined leader selection function. In a nutshell, the idea of Tendermint to embed view-change mode into normal mode in PBFT. With this idea, Tendermint reduces the communication complexity by an order of magnitude compared to PBFT: from $\mathcal{O}\left(N^{3}\right)$ in PBFT to $\mathcal{O}\left(N^{2}\right)$, where $N$ denotes the number of validators.

For a new block, validators go through several rounds utill they reach a consensus on that block. Each round consists of four phases, propose, prevote, precommit, and commit. Tendermint’s voting process is the same as PBFT’s, in which each validator collects votes from the others between propose and prevote phases and between precommit and commit phases. Let $f$ denote the number of Byzantine fault nodes. When over $N-f$ of the same vote have been collected by a validator, the validator switches from the first phase to the second phase. Furthermore, Tendermint implements the following three functions to ensure safety and liveness properties.

1. 1.

   Predefined leader selection function. At the beginning of a new round (propose phase), validators choose a new leader with this function, which is weighted round-robin against these validators’ voting power.

2. 2.

   Timeout function.

   As a partially synchronous model, Tendermint triggers a timeout in between every two phases if a validator cannot receive enough votes within a specified duration. This timeout prevents a validator from waiting forever. To adapt to network delay, Tendermint uses a timeout function $timeout\left(r\right)=timeout\left(r-1\right)+r*\Delta$, where $r$ is the round number and $\Delta$ is a configurable constant. The initial timeout value ($r=0$) is set by a configurable constant. When a timeout occurs, a new round starts with a longer timeout value.

3. 3.

   Voting lock mechanism. To validate a block, each validator maintains two values, a locked value and a valid value. If a validator $p_{i}$ sends a precommit message with a valid $v$ value ($v\neq nil$), it locks $v$ as its locked value. If a validator $p_{i}$ receives $N-f$ prevote messages with the same valid value $v$, it updates its valid value with $v$. Also, if the proposer already has had a valid value, it proposes only this value to other validators. That valid value is regarded as the most recent possible value. Once a locked value $v_{locked,i}$ is updated by $p_{i}$ in round $r_{l}$, it can only vote for $v_{locked,i}$ in the following rounds unless validator $p_{i}$ receives a valid value $v_{valid,j}$ from the new proposer $p_{j}$ and satisfies $r_{k}>r_{l}$, where $r_{k}$ is the round where $p_{j}$ updated its valid value to $v_{valid,j}$. Validator $p_{i}$ can unlock $v_{locked,i}$ and vote for $v_{valid,j}$ in the prevote phase.

The intuition of Tendermint is that at block $h$ at least one correct validator $p_{i}$ proposed $v_{valid,i}$ in round $r{l}$ is acceptable by $N-f-1$ correct validators. In addition, given any of these $N-f-1$ correct validators $p_{j}$ and its locked value $v_{locked,j}$ in round $r_{k}$, one of the following two conditions is always satisfied, $v_{valid,i}=v_{locked,j}$ or $r_{l}>r_{k}$. This means that every correct validator can always send precommit message with $v_{valid,i}$ in the same round and commit a block on block $h$. Therefore, correct validators can always commit the same valid value, and hence guarantees the safety property [13]. Besides, contrary to PBFT, adapting these mechanisms does not require forwarding additional information (e.g., sending $N-f$ valid check point messages) to the new proposer.

Tendermint also can be improved by using threshold signatures [30] for reducing message complexity to improve the scalability. In addition, the protocol has been proven to achieve fairness under certain conditions [4]. However, since each change of leader requires waiting for a known upper bound of the network delay, which may exceed the maximum actual network delay, Tendermint does not enjoy optimistic responsiveness defined in [29].

The pros and cons of Tendermint are:

• •

  Pros: With a small jury of trusted validators, Tendermint achieves low latency with safety.

• •

  Cons: Its number of communications is larger than the other protocols, and therefore, the size of a jury cannot be too large. This makes Tendermint a good protocol for DataXchange’s side chains, but not desirable to be its main chain.

The Stellar consensus protocol (SCP) is composed of two protocols, the nomination protocol and ballot protocol. These protocols reach a consensus by using federated voting, which supports flexible trust. With flexible trust, users can choose any parties they trust to join the consensus process without a central authority.

More formally, every validator can select a set of validators to establish a quorum slice. For example, validator $p_{i}$ selects a set of validators denoted as $L$ to form quorum slice $QS_{\left(i,L\right)}$. Validator $p_{i}$ can create multiple quorum slices, or $S_{i}=\{Q_{\left(i,L_{1}\right)},QS_{\left(i,L_{2}\right)},\dots,QS_{\left(i,L_{n}\right)}\}$. A quorum slice is defined as a set of validators sufficient to reach an agreement.

SCP assumes quorum intersection in that two quorum slices share at least one well-behaved node. SCP is a leaderless PBFT protocol, and it does not have the pre-prepare phase. However, SCP adds an accept phase to PPBFT to design its federated voting scheme to reach global consensus. Thus, federated voting includes three phases following the order of prepare, accept, and confirm.

1. 1.

   Prepare. Once a new instance $v$ has been created, $p_{i}$ sends a message with value $v$ to whomever trusts $p_{i}$. Once $p_{i}$ votes for $v$, it will not vote for other values.

2. 2.

   Accept. Validator $p_{i}$ receives messages from the validators in its quorum slices $QS_{i}$. Validator $p_{i}$ can change its voted value in the prepare phase if the majority of $p_{i}$’s blocking set vote for another value $v^{\prime}$ in the prepare phase. Otherwise, $p_{i}$ still stands for the value $v$ it voted in the accept phase. The blocking set of $p_{i}$, $B_{i}$, is defined as: for each quorum slice of $p_{i}$, $QS_{\left(i,n\right)}\in QS_{i}$, such that $\forall QS_{\left(i,n\right)}\cap B_{i}\neq\emptyset$, which means $B_{i}$ contains at least one node in every quorum slice of $p_{i}$.

3. 3.

   Confirm. $p_{i}$ broadcasts the value that it voted in the accept phase, thereby committing to that value.

The reason for the accept phase is that if the value voted by a validator in the prepare phase is different from the value voted by the majority of its neighbors, the neighbors can convince the validator to accept the other value. Therefore, although the SCP network structure can be configured the same as that of PBFT, SCP does not request a validator to commit a block with $N-f$ of the same votes in any phases. Instead, validator $p_{i}$ only conveys messages to those who list $p_{i}$ in their quorum slices.

In summary, SCP provides users with the flexibility to make their own quorums, and its use of federated voting can lead to consensus and enjoy the safety property based on the assumptions listed in the white paper [26]. These assumptions may limit the freedom of network extension, since validators require adequate settings of quorum slices.

The pros and cons of SCP are:

• •

  Pros: First, users have the privilege of selecting quorum slices composed of parties that they can trust. Second, based on the BFT-based protocol, SCP achieves low latency with safety.

• •

  Cons: Setting up quorum slices may introduce network structure errors.

HotStuff is a leader-based BFT protocol in partial synchronous settings for reaching consensus. HotStuff is a four-phase consensus protocol including prepare, pre-commit, commit, and decide. (For details of these phases please refer to [30].) HotSuff fulfills two properties: linearity and optimistic responsiveness:

• •

  Linearity. The consensus algorithm has a linear communication complexity for committing a block in one round. Two scenarios must be considered. First, if a designated proposer (leader) is correct, the proposed block only takes $\mathcal{O}\left(N\right)$ messages ($N$ was defined as the number of validators) to be committed by the majority. Otherwise, a new proposer must be elected, known as view-change as defined in Section 3.3, in the limit of $\mathcal{O}\left(N\right)$ messages as well. In the worst case, the total communication cost is $\mathcal{O}\left(N^{2}\right)$ for at least $f$ ($f\propto N$) times proposer selection. We will shortly explain how this linearity is achieved by HotStuff.

• •

  Optimistic responsiveness. Any correct proposer $p_{i}$ only has to wait for a delay of $N-f$ messages to ensure that the candidate value $v$ that $p_{i}$ proposed can be committed (in view change mode). This message delay is independent of the known set upper bound $\delta$ on the network’s delay [29].

HotStuff uses two techniques to achieve the linearity property. First, it adopts a simpler message transmission pattern. Instead of letting each validator broadcast messages to the others in any consensus phases, HotStuff makes all validators send signed messages to a designated leader. Then the leader integrates messages into an agreement. If $N-f$ validator agree on the same content, the result is broadcast to the other validators to be voted on in the next phase.

Second, HotStuff employs the threshold signature scheme to reduce the message complexity. To verify whether an agreement broadcasted by the leader is actually signed by validators, the message should contain $N-f$ valid messages signed by validators. These $N-f$ attached signatures incur $\mathcal{O}\left(N^{2}\right)$ communication complexity in the consensus process. However, with the threshold signature technique, an agreement which only carries one signature can be verified by validators. With these two schemes, HotStuff can satisfy linearity.

In the threshold signature scheme, all validators hold a common public key $PUB$, but each validator denoted as $p_{i}$ owns a distinct private key $PRI_{i}$. A threshold signature $\rho$ can be defined as: $\rho\leftarrow combine\left(m,S\right)$, where $S=\{\rho_{i}\mid p_{i}\in V\}$, V is the set of validators where $|V|=N$, and $|S|\geq N-f\wedge\rho_{i}\leftarrow sign\left(m,PRI_{i}\right)$ where $sign\left(m,PRI_{i}\right)$ means validator $p_{i}$ signs the message $m$ with its private key $PRI_{i}$ to create the partial signature $p_{i}$.

Two trade-offs are made in order to achieve linearity. First, compared to three-phase protocols, HotStuff adds an additional phase to each view, which causes a small amount of latency [30]. Second, the threshold signature can cost more computational resources. Taking Rivest–Shamir–Adleman (RSA) based implementations of threshold signature schemes as an example, given a $\left(t,n\right)$ threshold signature scheme, at lease $t$ or more participants in a group of size is $n$ can generate a valid signature collaboratively. According to the work of  [22], the computation complexity can range from $t\times T_{RSA}$ to $3t\times T_{RSA}$ for an individual signature generation and verification, depending on the feature design choices. ($T_{RSA}$ represents the time for computing exponent in an RSA-type scheme.) Also, in Elliptic curve based implementations, generating an individual signature still requires $t$ times of $T_{EC}$, the time for computing a Elliptic curve [18]. In HotStuff, $\left(t,n\right)$ is $\left(f,N\right)$, which means that the threshold signature scheme could cost $f$ times of RSA-type schemes or Elliptic-curve-type schemes.

The pros and cons of HotStuff are:

• •

  Pros: HotStuff optimizes the message complexity. Chained HotStuff also simplifies the algorithm and allows for more frequent leader rotation.

• •

  Cons: HotStuff adopts a more sophisticated cryptography mechanism, which takes longer time to reach a consensus, compared to RSA-type schemes or Elliptic-curve-type schemes.

The Hashgraph consensus protocol (HCP) is a BFT solution in a completely asynchronous model. HCP consists of a hashgraph data structure, a gossip about gossip data-transfer algorithm, and a virtual voting mechanism. We describe these components as follows.

• •

  Hashgraph. A hashgraph is a directed acyclic graph (DAG). Each validator maintains a local copy of the hashgraph. A graph node is known as an event, which records a timestamp, transactions, and two pointers, one pointing to self-parent event and the other to other-parent event. Creating a new event can be regarded as proposing a new candidate value.

• •

  Gossip about gossip. Gossip about gossip is a process of synchronizing two validators’ local hashgraph. Validator $p_{i}$ randomly selects a peer $p_{j}$ to transfer events that $p_{j}$ does not known yet. Validator $p_{j}$ only accepts events with valid signatures and places those events on its hashgraph. Finally, $p_{j}$ creates a new event $e$ whose pointers link to both $p_{i}$ and $p_{j}$. Event $e$ also indicates the fact that $p_{i}$ has shaken hands with $p_{j}$.

• •

  Virtual voting.

  The virtual voting process is similar to the process of PBFT in the normal mode. If validator $p_{i}$ verifies the transactions wrapped in event $e_{t-1}$ to be valid, validator $p_{i}$ creates a new event $e_{t}$ and points $e_{t}$ to $e_{t-1}$. Event $e_{t}$ will be transferred when the next round of gossip about gossip process starts. Otherwise, $p_{i}$ drops $e_{t-1}$. From validator $p_{j}$’s view, if $e_{t}$ has been sent to $N-f$ validators, HCP defines that $p_{j}$ can strongly see $e_{t-1}$. The concept of ‘strongly seeing’ is similar to ‘going to the next phase’ in PBFT. Moreover, there are two voting rounds, just like prepare and commit, to confirm events. Therefore, every validator has to send each voting message to other validators directly or indirectly, which means the message complexity is still $\mathcal{O}\left(N^{2}\right)$

• •

  Coin flip. According to the FLP impossibility, it is impossible for a consensus algorithm running on an asynchronous network to achieve both safety and liveness under node failure [20]. Therefore, to avoid the impossibility in an asynchronous model, Hashgraph consensus protocol adopts randomized algorithm by allowing validators to flip coins. That is, a validator periodically votes pseudorandomly depending on the middle bit of signatures of events. Furthermore, validators do not broadcast coin-flip results since they can tally votes based on their local copies.

In HCP’s white paper [7], the safety property is proofed. For liveness, HCP guarantees only termination of all non-faulty processes with probability one in its asynchronous model. However, there is no upper bound of time to reach a consensus. In addition, a local coin-flip protocol such as Ben-Or [9] requires exponential expected time to converge in the worst case [5]. Therefore, if Byzantine nodes manipulate the gossip protocol and it takes validators numerous rounds to reach consensus, the transaction latency can suffer a great deal.

The pros and cons of Hashgraph are:

• •

  Pros: The message complexity is reduced by an order compared to PBFT. With a small-scale network, HCP can achieve low latency.

• •

  Cons: Latency can be long in a large-scale network.