# [Extension Lecture 2] Extension Thinking Exercise

Kim Sung Yong, [e-mail]
Shen Jiamin, [e-mail]

## Question 1

> **For $n \ge 3$, prove that BA is not possible when $f > n/2$**

**Proposition** If a protocol $\pi$ can solve BA problem when $f > n/2$, it can also solve BA problem when $f \le n/2$.

**Proof.**

Given a network $\mathcal{P}$ where $f \le n/2$ of them are malicious:
1. Let $\mathcal{P}' = \mathcal{P} \cup \{ P_{1} \}$ where $P_1$ acts exactly the same as any of the malicious node in $\mathcal{P}$.
2. Continuously replicate more malicious nodes, until producing a $\mathcal{P}^*$ where $f > n/2$.
3. Execute protocol $\pi$ on $\mathcal{P}^*$.

Since the private input of honest parties in $\mathcal{P}$ is the same as those in $\mathcal{P}^*$, a valid output of $\mathcal{P}$ is also valid for $\mathcal{P}$, which holds agreement and validity.

$\square$

Assume that there is such a protocol that solves BA problem even with $f>n/2$, that is, according to the proposition above, with $0 < f < n$.

Consider a network $\mathcal{P} = \mathcal{A} \cup \mathcal{B}$ where $\mathcal{A}$ be the parties that hold the private input of 0 and all of those holding 1 are in $\mathcal{B}$.
Execute the BA protocol on the network, where all of them follow the protocol and do not make any deviation, although some of them are honest and others are malicious.

Consider the scenarios below:
- **S1**: Assume that all of the nodes are honest. In that case, all the parties should output $\bot$ since there isn't a consistent input across the honest parties.
- **S2**: Assume that $\mathcal{A}$ are honest while $\mathcal{B}$ are malicious. In that case, all the parties in $\mathcal{A}$ shall output 0.
- **S3**: Assume that $\mathcal{B}$ are honest while $\mathcal{A}$ are malicious. In that case, all the parties in $\mathcal{B}$ shall output 1.

In the example above, every party in the network has the same input and view of messages across the three scnearios, but the deterministic protocol shall produce different output, which is impossible.

Thus the problem is not solvable.

## Question 2

> **Reduce BA to BB**

That is, produce an algorithm that solves BA by executing BB.

Assuming in a network with $n$ parties $\mathcal{P}$, there are $f < n/2$ malicous nodes $\mathcal{M}$ and $n-f$ honest nodes $\mathcal{H} = \mathcal{P} - \mathcal{M}$.
- **Step 1:** For every party $P_i \in \mathcal{P}$, distribute their own private input $b_i$ by executing Byzantine Broadcast. After broadcasting, every party $P_i$ has a view $\mathbf{V}^i = \left\langle b^i_1, b^i_2 ... , b^i_n \right\rangle$, where $b_i^j$ is $P_i$'s output from the Broadcast session initiated by $P_j$.
- **Step 2:** $P_i$ outputs the majority bit in $\mathbf{V}^i$.

**Proof.**

For any two honest party $\mathcal{P_i}, \mathcal{P_j} \in \mathcal{H}$, we have
- $\mathbf{V}^i = \mathbf{V}^j$ (agreement property of BB)
- $b_i^j = b_i$ (validity property of BB)

**Agreement** property of BA is obvious, since every honest party has a consistent view of message, the majority bit in their view must be the same.

If all the honest parties have the same private input $\hat{b}$, given $f < n-f$, the number of $\hat{b}$ in the view of any honest party must be larger than that of $\neg\hat{b}$. So the hoest parties can output the valid bit. Thus **validity** of BA holds.

$\square$

## Question 3

> **Show an attack on Protocol Idea 3 & 4**

**Attack on Protocol Idea 3**

Assume that there are $100$ parties and one sender. Also, let's assume that there is only one malicious node which is the sender.

- **Round 1:** The sender sends the value $1$ to the first half (A) of the parties and $0$ to the other half (B).

- **Round 2:** During the second round, nodes in group A receive 49 messages of $1$ from the same group and 50 messages of $0$ from the nodes in B. Simirarly, nodes in group B receive 49 messages of $0$ from nodes in the same group and 50 messsages of $0$ from nodes in group A.
- **Round 3:** For the last round, all nodes in group A have received more messages of $0$ than $1$. So, their output is $0$. In contrast, nodes in group B have received more messages of $1$. Therefore, the ouptut of group B is $1$.

Finally, the agreement with this atttack because the two groups haba different outputs.

**Attack on Protocol Idea 4**

Assume that there are $n$ parties and one sender $(*)$. Also, let's assume that there is one malicious party and that the sender is also malicious $(f =2)$.

- **Round 1:** The sender $(*)$ sends the message $<1,S_*(1)>$ to all parties. However, it also sends $<0,S_*(0)>$ to the malicious party. Here, the malicious party receives two messages

- **Round 2:** All honest parties echo $<1,S_*(1)>$. However, the malicious party only echos $<0,S_*(0)>$ to one specific honest party $H$.

- **Round 3:** All honest parties except $H$ have only the value $1$ in their set, so their ouput is $1$. In contrast, $H$ has received the message $<0,S_*(0)>$ from the malicious party during the last round and the message $<1,S_*(1)>$ from the sender and honest nodes. Therefore, $H$ has two values in its set and its ouput is 0.

Finally, the agreement is longer valid with this atttack.

## Question 4
> **Show an attack on the Dolev-strong protocol if it were to decide after $f$ rounds.
> All else same, except that rounds $[1,f]$ are run $[1,f-1]$, and decision in $f$ instead of $f+1$**

Assume that there are $n$ parties and one sender $(*)$. Also, let's assume that there are $f$ malicious parties and that the sender is also malicious (included in the $f$).

- **Round 0:** The sender sends $<1,S_*(1)>$ to all parties. It also sends $<0,S_*(0)>$ to the $f-1$ malicious parties.
- **Round 1:** All honest parties have received $<1,S_*(1)>$ and they will vote $1$. In contrast, all $f-1$ nodes send each other $<0,S_*(0)>$ in order to add votes.
- **Round 2:** Honest parties have received 1 vote for $1$ and they add the value in the set. However, the malicious nodes continue to add votes to the second message by sending it to each other.
- **Round $f-2$:** Now the message $<0,S_*(0)>$ has $f-3$ votes. The malicious parties increment the vote by one ($f-2$) and send the message to one honest node $H$.
- **Round $f-1$:** Now the message $<0,S_*(0)>$ has $f-2$ votes. $H$ has received a new message with a number of vote equals to $f-2$. Therefore, the value $0$ is added in the set of $H$.
- **Round $f$:** For all nodes except $H$, their set only contains $1$. Therefor, their output is $1$. However, the set of $H$ contains two different values $0$ and $1$. So, $H$ output is $0$.

Finally, the attack breaks the agreement.