# Asymmetric trust - reading summary

paper link [https://arxiv.org/abs/1906.09314](https://arxiv.org/abs/1906.09314)

## system model
1. Processes $\mathcal{P}$ = { $p_1$, $p_2$, ..., $p_n$ }
2. Functionality is a primitive either used by individual processe, or is a service provided by the process
* Each functionality is specified by an interface, which defines events that trigger it and its properties that handled the event. A process can use its state to dynamically change its handle.
* event is categorized as input event or output event
3. Executions and faults: a execution is a running of all processes, which keep progress until there is natural end. An fair executation requires no execution stop prematurely or deviate from the protocol.

## symmetric trust
A fail prone system, $\mathcal{F}$, is a collection of set defined within $2^{\mathcal{P}}$, such that every element $F \in \mathcal{F}$ is not contained by another element $G \in \mathcal{F}$. Every set $F$ represents a maximal set of processes that can fail together. A protocol designed for $\mathcal{F}$ can achieve its properties as long as the actual faulty set $F \in \mathcal{F}$. Let $\mathcal{A^*} = \{ A' | A' \subseteq A, A \in \mathcal{A} \}$. For example
$\mathcal{A} = \{ (1,2,3), (3,4) \}$, then $\mathcal{A^*} = \{(1),(2),(3),(4),(1,2), (1,3),(2,3),(1,2,3),(3,4) \}$

A fail prone system is an abstraction for a supposed reality.

### definition | Byzantine Quorum system
On top of a fail prone system, $\mathcal{F}$, we can define some useful system that has some desired proporty, including **Consistency** and **Availability**. Let's define a collection of set $\mathcal{Q}$ whose set elements are quorum set.
* Consistency says, common elements from any 2 quorum contain at least 1 non-faulty process. i.e. for all $Q_1, Q_2 \in \mathcal{Q}$, for all maximal faulty set $F \in \mathcal{F}$, such that $Q_1 \cap Q_2 \not\subseteq F$
* Availability says, for any faulty set there exist at least one quorum does not have any common process to each other. i.e. for all $F \in \mathcal{F}$, there exist a $Q \in \mathcal{Q}, such that $Q \cap F = \emptyset$

The Byzantine Quorum system allows a protocol to be designed on top of it despite arbitrary action of the faulty node.

### definition | $Q^3$ condition

A fail prone system satisfies $Q^3$ condition, $Q^3(\mathcal{F})$, if no 3 set inside $\mathcal{F}$ covers all the sets. i.e. for any $F_1, F_2, F_3 \in \mathcal{F}$, such that $\mathcal{P} \not\subseteq F_1 \cup F_2 \cup F_3$.

There exists a method to turn a fail prone system $\mathcal{S}$ into a quorum system $\mathcal{Q}$, by bijective complement, i.e. $\mathcal{Q} = \bar{\mathcal{S}} = \{\mathcal{P} \setminus S: S \in \mathcal{S}\}$

#### lemma 1
Given a fail prone system $\mathcal{F}$, if $Q^3(\mathcal{F})$ is satified, then there exists a Byzantine Quorum system that has consistency and availability properties. which is the bijiective complment of $\mathcal{F}$, $\bar{\mathcal{F}}$.

### definition | core set
A core set $C \subset \mathcal{P}$ if
1. for all $F \in \mathcal{F}$, such that $(\mathcal{P} \setminus F) \cap C \neq \emptyset$. i.e. $C \not\subseteq F$
2. for all $C' \subsetneq C$, such that $(\mathcal{P} \setminus F) \cap C' = \emptyset$. i.e. $C' \subseteq F$.

In a threshold settiing, any set of f+1 is a core set.

"A core set C for F is a minimal set of processes that contains at least one correct process in every execution"
## Asymmetric trust

In an asymmetric fail prone system, every process can create its own abstraction of supposed reality, and together the system, $\mathbb{F} = [\mathcal{F_1}, \mathcal{F_2}, ..., \mathcal{F_n}]$. Whereas in a symmetric trust system like, threshold system, every process holds trust assumption, i.e. $\mathcal{F}$ is any f processes in the $p_1,..p_n$.

### definition | Asymmetric byzantine quorum system

The system contains a collection of Quorum system, $\mathbb{Q} = [\mathcal{Q_1},..,\mathcal{Q_n}]$. It satisfies
* Consistency says, there exists a common non-faulty process, from any 2 quorum set of their perspective 2 process's quorum. i.e. for all $i, j \in [1,n]$, for all $Q_i \in \mathcal{Q_i}, Q_j \in \mathcal{Q_j}$, $F_{ij} \in \mathcal{F^*_i } \cap \mathcal{F^*_j}$, $Q_i \cap Q_j \not\subseteq F_{ij}$
* Availability says, for any process, i, and every faulty set of the process i, there exist a quoruo set that is disjoint of it. i.e. for all $i \in [1,..n]$, for all $F_i \in \mathcal{F_i}$, there exist a $Q_i \in \mathcal{Q_i}$, such that $Q_i \cap F_i = \emptyset$

### definition | ${B^3}$ condition

An asymmetric fail-prone system $\mathbb{F}$ satisfied ${B^3}$ condition, ${B^3}(\mathbb{F})$, if for all $i,j$, for all $F_i \in \mathcal{F_i}$, $F_j \in \mathcal{F_j}$, $F_{ij} \in \mathcal{F^*_i} \cap \mathcal{F^*_j}$, such that $\mathcal{P} \not\subseteq F_i \cup F_j \cup F_{ij}$

#### example

An example does not satisfy ${B^3}$

### definition | Kernel

In a symmetric Byzantine quorum system $\mathcal{Q}$, a kernel $K$ is a set of process that has at least one element for quorum $Q \in \mathcal{Q}$, i.e. $K \cap Q \neq \emptyset$ for all $Q$; and it is minimal in the sense, for all $K' \subsetneq K$, there exist a $Q$. The kernel system of $\mathcal{K}$ of quorum system $\mathcal{Q}$ is a set of all kernel in $\mathcal{Q}$.

Kernel of $\mathcal{Q}$ is related to core set of \mathcal{F}, if $\mathcal{Q} = \bar{\mathcal{F}}$ is minimal

### definition | Asymmetric core set and kernels

$\mathbb{F} = [\mathcal{F_1},..., \mathcal{F_n}]$, a asymmetric core system is an array of collection $[\mathcal{C_1}..,\mathcal{C_n}]$, where $\mathcal{C_i}$ is a core set system for fail prone system $\mathcal{F_i}$. $C_i \in \mathcal{C_i}$. And similarly for $\mathbb{K} = [\mathcal{K_1}..,\mathcal{K_n}]$.

### definition | naive and wise process

Although there are $F$ faulty process, no one process has the entire picture on which process is fault. (But it might not be true with forensics). Symmetric quorum system is designed to tolerate $\mathcal{F}$.

In Asymmetric quorum system, there are 3 types of processes
1. A process $p_i \in F$ is a faulty process
2. A correct process $p_i$, for which $F \not\in \mathcal{F^*_i}$ is called naive
3. A correct process $p_i$, for which $F \in \mathcal{F^*_i}$ is called wise

Protocol for asymmetric quorum cannot make the same guarantee to both naive and wise processes.

### definition | guild

A Guild is a set of wise processes that contains at least one quorum for each member. The existence of guild ensures liveness and consistency of the system.

Given a fail prone system $\mathbb{F}$, an asymmetric quorum system $\mathbb{Q}$ and an execution with faulty processes $F$, a guild, $\mathcal{G}$ for $\mathcal{F}$ satisfies 2 properties
1. Wisdom says, every member of the guild includes the members of actual faulty process. i.e. for all $p_i \in \mathcal{G}$, such that $F \in \mathcal{F^*_i}$
2. guild contains a quorum for each of its member. i.e. for all $p_i \in \mathcal{G}$, there exists a quorum from the quorum system $Q_i \in \mathcal{Q_i}$, such that $Q_i \subseteq \mathcal{G}$.

The union of 2 Guilds is still a guild. hence there exists a unique maximal guild