# Brave: Byzantine-Resilient and Privacy-Preserving
Peer-to-Peer Federated Learning

Zhangchen Xu1, Fengqing Jiang1, Luyao Niu1, Jinyuan Jia2, Radha Poovendran1

###### Abstract

Federated learning (FL) enables multiple participants to train a global
machine learning model without sharing their private training data. Peer-to-
peer (P2P) FL advances existing centralized FL paradigms by eliminating the
server that aggregates local models from participants and then updates the
global model. However, P2P FL is vulnerable to (i) _honest-but-curious_
participants whose objective is to infer private training data of other
participants, and (ii) _Byzantine_ participants who can transmit arbitrarily
manipulated local models to corrupt the learning process. P2P FL schemes that
simultaneously guarantee Byzantine resilience and preserve privacy have been
less studied. In this paper, we develop Brave, a protocol that ensures
Byzantine Resilience And priVacy-prEserving property for P2P FL in the
presence of both types of adversaries. We show that Brave preserves privacy by
establishing that any honest-but-curious adversary cannot infer other
participants’ private data by observing their models. We further prove that
Brave is Byzantine-resilient, which guarantees that all benign participants
converge to an identical model that deviates from a global model trained
without Byzantine adversaries by a bounded distance. We evaluate Brave against
three state-of-the-art adversaries on a P2P FL for image classification tasks
on benchmark datasets CIFAR10 and MNIST. Our results show that the global
model learned with Brave in the presence of adversaries achieves comparable
classification accuracy to a global model trained in the absence of any
adversary.

##  1 Introduction

Federated learning (FL) (McMahan et al. 2017; Konečnỳ et al. 2016) allows
multiple participants to collaboratively train a global model while avoiding
sharing their private data. In a classic centralized FL paradigm, a central
server coordinates the training process among the distributed participants and
aggregates their local models. However, centralized FL is not viable when the
server is subject to faults or becomes untrustworthy and/or unavailable
(Lalitha et al. 2019).

To address the high dependence on the reliability of the server in centralized
FL, Peer-to-Peer (P2P) federated learning has been proposed in (Lalitha et al.
2019; Roy et al. 2019). In P2P FL, the global model is updated by leveraging
information exchange between individual participants, thereby eliminating the
need for a central server. The P2P paradigm presents two significant
advantages. First, it eliminates the potential vulnerabilities associated with
a single point of failure. Second, it can be deployed for decentralized
applications such as vehicle-to-vehicle networks (Chen et al. 2021) and
Internet-of-Things (Savazzi, Nicoli, and Rampa 2020).

Due to the absence of central coordination in the P2P setting, the behaviors
of participants are unpredictable and uncontrollable. An unauthorized agent
can participate in P2P FL aiming to obtain sensitive data and/ or disrupt the
training process. Since local models are shared among participants, honest-
but-curious participants may be able to infer private training data by
launching a membership inference attack (Nasr, Shokri, and Houmansadr 2019).
Therefore, it is crucial to implement privacy-preserving techniques such as
secure Multi-Party Computation (MPC) (Yao 1982) for model aggregation in P2P
settings. Besides honest-but-curious participants, Byzantine participants can
send inconsistent models to different participants in P2P networks, inject
biased models, or even withhold its updates (Tolpegin et al. 2020; Xie,
Koyejo, and Gupta 2019; Fang et al. 2020). As a consequence, Byzantine
participants can degrade the global model or even cause the FL to fail.
Therefore, Byzantine-resilient model aggregation rules are needed to defend
against Byzantine attacks in P2P FL.

The current Byzantine-resilient model aggregation rules (Blanchard et al.
2017; Yin et al. 2018; Li et al. 2019), however, are not readily compatible
with privacy-preserving techniques such as MPC. These model aggregation rules
(Blanchard et al. 2017; Yin et al. 2018; Li et al. 2019) eliminate the
compromised models from adversaries by disclosing each individual
participant’s information. Consequently, the honest-but-curious adversaries
can infer private training data owned by the other participants, leveraging
such information disclosure. At present, however, P2P FL schemes that
simultaneously guarantee Byzantine resilience and preserve privacy have been
less investigated.

In this paper, we design a P2P FL scheme that achieves Byzantine resilience
while preserving privacy. We consider the presence of both honest-but-curious
and Byzantine participants, and define three properties: information-theoretic
privacy, $\epsilon$-convergence, and agreement. Information-theoretic privacy
ensures that no information about the participants’ local models is leaked
during the training process, $\epsilon$-convergence implies that the distance
between global models learned with and without Byzantine participants is at
most $\epsilon$, and agreement indicates the global model of all benign
participants are identical. We guarantee information-theoretic privacy by
first letting each participant make a commitment of its local model, which
will be ‘locked’ and thus not editable in the future. We then utilize MPC
technique to compare and sort the participants’ local models without
disclosing their true values. Each participant then invokes a trimming scheme
to exclude the largest and smallest $f$ local models when updating the global
model, where $f$ is the maximum number of Byzantine participants. The main
contributions of our paper are summarized as follows.

  * •

We propose Brave, a Byzantine Resilience And priVacy-prEserving protocol for
P2P FL. We prove that Brave ensures the local model of each participant to be
information-theoretically private during the learning process.

  * •

We design a privacy-preserving trimming scheme to ensure
$\epsilon$-convergence in the presence of Byzantine adversaries. We further
leverage distributed consensus to ensure agreement. We theoretically prove
that Brave is resilient to Byzantine participants given $N>3f+2$, where $N$ is
the total number of participants.

  * •

We evaluate Brave against three state-of-the-art adversaries on two image
classification tasks. Our results show that Brave guarantees
$\epsilon$-convergence if $N>3f+2$ holds. Furthermore, the global model
trained using P2P FL that implements Brave achieves comparable classification
accuracy to a global model learned in the absence of any adversary.

The rest of the paper is organized as follows. We present the literature
review in Section 2. In Section 3, we present the system model and problem
formulation. Section 4 describes Brave, a multi-stage protocol in P2P FL that
is information-theoretic privacy and Byzantine resilience. Section 5 shows
empirical results of Brave for image classification tasks on benchmark
datasets including CIFAR10 and MNIST. Section 6 concludes this paper and
discusses future work.

##  2 Related Work

In this section, we first review Byzantine-resilient and privacy-preserving
solutions developed for centralized FL. We then present P2P FL schemes that
guarantee Byzantine resilience and/ or preserve privacy.

Solutions in Centralized Federated Learning: To preserve privacy in FL,
differential privacy (DP) (Dwork 2008) based mechanisms were widely used to
protect model parameters (Truex et al. 2019; Wei et al. 2020). However,
(Hitaj, Ateniese, and Perez-Cruz 2017) pointed out that DP is not adequate for
safeguarding privacy in collaborative machine learning. Additionally, DP
factors could result in reduction of model accuracy (Bagdasaryan, Poursaeed,
and Shmatikov 2019). An alternative secure multi-party computation (MPC) (Yao
1982) based approach was adopted in (Bonawitz et al. 2017), which presented a
model aggregation method for FL using a pairwise mask to cloak the local
model. In (Mugunthan et al. 2019), DP and MPC were simultaneously applied to
further strengthen the privacy-preserving property.

Multiple Byzantine-resilient model aggregation rules were proposed to address
the presence of Byzantine adversaries in FL. Multi-Krum (Blanchard et al.
2017) updated the global model by selecting the gradient that minimizes the
sum of squared distances to its $N-f$ closest gradients. Similarly, (Yin et
al. 2018) proposed two coordinate-wise model aggregation rules, trimmed mean
and median. In trimmed mean (resp. median), the server sorted the value of
each model, removed the largest and smallest $f$ values, and then computed the
mean (resp. median) of the remaining values for the global model update.

To simultaneously preserve privacy and guarantee Byzantine resilience, DP and
Byzantine-resilient model aggregation techniques were adopted in (Ma et al.
2022b, a). The authors of (He, Karimireddy, and Jaggi 2020; Liu et al. 2021)
implemented Multi-Krum on two non-colluding honest-but-curious servers for
secure aggregation, and applied private calculation to ensure privacy. It is
worth noting that (Liu et al. 2021) implemented median as the Byzantine-
resilience aggregation rule, where local models from all participants were
sorted using MPC. In (Velicheti, Xia, and Koyejo 2021), a clustered FL
framework that randomly clusters clients before filtering malicious updates
was proposed, which cryptographically preserved the local model privacy and
was robust to Byzantine adversaries. A very recent work (Mohamad et al. 2023)
discussed the potential challenges in secure aggregation based on
cryptographic schemes for FL.

Solutions in P2P Federated Learning: There are two main categories in
realizing P2P FL. The first category adopted a fully decentralized framework
where no coordinator existed. In (Lalitha et al. 2019), the participants
aggregated data and updated their model by observing their one-hop neighbors.
In (Roy et al. 2019), the participant who intended to renew its local model
actively initiated an update by requesting the latest model from other
participants. Another category leveraged blockchain (Li et al. 2021; Ramanan
and Nakayama 2020; Chen et al. 2021; Shayan et al. 2021) or distributed
consensus algorithms (Che et al. 2021; Han et al. 2022) to synchronize the FL
process and coordinate the model aggregation. For example, (Chen et al. 2021)
proposed a blockchain-based P2P FL, where the public verifiable secret sharing
(PVSS) scheme was implemented to preserve privacy. In (Li et al. 2021),
blockchain was used for global model storage and the local model update
exchange, and a committee consensus mechanism was proposed to reduce the
amount of consensus computing. In (Ramanan and Nakayama 2020), smart contract
was applied to coordinate the round delineation, model aggregation, and update
tasks in FL. In (Che et al. 2021; Han et al. 2022), two distributed consensus
algorithms, PBFT (Castro and Liskov 1999) and Hotstuff (Yin et al. 2019), were
applied to coordinate the FL training process, and Multi-Krum was implemented
to enable Byzantine-resilience model aggregation. However, these solutions did
not consider privacy-preserving and Byzantine resilience simultaneously.

Currently, Byzantine-resilient and privacy-preserving P2P FL has been less
studied. The authors of (Shayan et al. 2021) simultaneously considered
privacy-preserving property and Byzantine resilience in P2P FL. Blockchain and
PVSS were used in (Shayan et al. 2021) to ensure differential privacy, whereas
Multi-Krum was applied to defend against Byzantine clients. The approach in
(Shayan et al. 2021) may inherit the performance degradation with respect to
DP factors (Hitaj, Ateniese, and Perez-Cruz 2017). Different from (Shayan et
al. 2021), Brave is information-theoretically private. We further demonstrate
that Brave does not degrade the performance of global model trained by P2P FL.
Therefore, the present paper is complementary to (Shayan et al. 2021).

##  3 System Model and Problem Formulation

System Model. We consider a P2P FL (Lalitha et al. 2019; Roy et al. 2019)
consisting of a set of participants $\mathbb{P}=\\{P_{1},\ldots,P_{N}\\}$ who
aim to learn a global model ${w}$. Each participant $P_{i}$ owns a certain
amount of private data $\mathcal{D}_{i}$. At iteration $t$ of P2P FL, each
participant $P_{i}$ updates its local model ${w}_{i}(t)$ using gradient
descent as

${w}_{i}(t+1)={w}(t)-\eta{g}_{i}(t),$ (1)

where
${g}_{i}(t)=\frac{\partial\mathcal{L}(\mathcal{D}_{i};{w}(t))}{\partial{w}(t)}$
is the gradient, $\mathcal{L}(\mathcal{D}_{i};{w}(t))$ is the loss function of
$P_{i}$, and $\eta$ is the learning rate. Participant $P_{i}$ then receives
local models ${w}_{j}(t+1)$ from other participants $j\neq i$, and updates the
global model as

${w}(t+1)=\frac{1}{N}\sum_{i=1}^{N}{w}_{i}(t+1).$ (2)

Such a procedure repeats until a stopping criterion is met.

Threat Model. We consider a P2P FL framework where both passive and Byzantine
adversaries exist and potentially overlap, with the remaining participants
identified as benign. The adversaries are assumed to have full access to the
messages they receive but are incapable of eavesdropping or intercepting the
communications of others. Furthermore, these adversaries have limited
computational capability to solve the discrete logarithms problem (McCurley
1990). This assumption is the foundation for the security of numerous public
key systems and protocols (Lee and Chang 1998; Joux, Odlyzko, and Pierrot
2014). Specifically, Passive adversaries (Nasr, Shokri, and Houmansadr 2019)
follow the procedure of P2P FL but aim to obtain the local models from the
other participants, thereby extrapolating private training data by launching
MIA (Nasr, Shokri, and Houmansadr 2019) on these local models. Byzantine
adversaries aim at compromising the learning performance of P2P FL by biasing
the local models of other participants. In pursuit of their objectives, the
Byzantine adversaries can create compromised local models, and send different
local models to different participants or just remain silent in the
communication process.

Problem Formulation. Our aim of this paper is to develop a protocol such that
the P2P FL guarantees both information-theoretic privacy and Byzantine
resilience, defined as below.

######  Definition 1 (Information-Theoretic Privacy).

A benign participant $P_{i}$’s local model ${w}_{i}$ is information-
theoretically private if its local model $w_{i}$ cannot be revealed by a
passive adversary by observing the message sent by $P_{i}$.

######  Definition 2 (Byzantine Resilience).

A P2P FL scheme is Byzantine-resilient if the following properties hold: 1)
_$\epsilon$ -Convergence_: There exists $\epsilon\geq 0$ such that
$\|{w}(T)-{w}(T)^{*}\|\leq\epsilon$ holds with probability at least $\zeta$,
where ${w}(T)^{*}$ is the global model obtained using Eqn. (1) and (2) without
Byzantine adversaries, and $T$ is the iteration index when P2P FL terminates.
2) _Agreement_ : The global model $w(t)$ of all benign participants is
identical for each iteration $t$.

Remark. Ensuring information-theoretic privacy and Byzantine resilience
implies the protocol is resilient to both passive adversaries and Byzantine
adversaries.

##  4 Design of Brave

We designed Brave, a multi-stage protocol in P2P FL that comprises four
stages: Commitment, Privacy-preserving Comparison, Sorting & Trimming, and
Aggregation & Verification. The proposed protocol is proven to achieve
information-theoretic privacy and Byzantine resilience if $N>3f+2$.

Figure 1: This figure shows the overall workflow of Brave.

To defend against Byzantine adversaries who might input differing models at
various stages, Brave starts with a commitment stage (➀) after participants
update their local models in each iteration. Following this, Brave enters a
privacy-preserving comparison stage (➁), which enables the sorting of local
models without revealing any information about their true values. Brave then
incorporate trimmed mean (Yin et al. 2018) in the sorting & trimming stage (➂)
to remove the outliers possibly introduced by Byzantine adversaries. In the
last aggregation & verification stage (➃), MPC (Bonawitz et al. 2017) is
performed to aggregate models while preserving privacy. This stage also
verifies the consistency of the aggregated model with the commitment. Fig. 2
illustrates the schematic message flow of Brave when applied to a P2P FL with
six participants.

Notations. We use $\mathbb{Z}_{q}$ to denote the set of non-negative integers
that are no larger than $q$. We denote $\mathbb{Z}_{q}^{m}$ as the set of
$m$-dimensional vectors with each entry taking values from $\mathbb{Z}_{q}$.
We denote set $\\{1,\ldots,m\\}$ as $[m]$.

Figure 2: This figure depicts a P2P FL with six participants
$\\{P_{0},\ldots,P_{5}\\}$ and illustrates the schematic message flow of
Brave. In this example, $P_{5}$ is a Byzantine adversary. In Stage 1, all
participants broadcast their commitments of local models to BFT broadcast
module. In Stage 2, the participants first exchange messages among themselves
using the point-to-point communication network. After that, they send a set of
relationships among local models to BFT broadcast. In Stage 3, the participant
sorts the local models along each coordinate after receiving the pairwise
comparison results. It then trims the largest and smallest $f$ values in each
coordinate. In Stage 4, MPC is is performed to aggregate models while
preserving privacy.

### Stage 1: Commitment

In what follows, we introduce the Commitment stage of Brave. In this stage,
each $P_{i}$ first updates its local model ${w}_{i}$ using Eqn. (1). Then, a
one-to-one strictly monotonic mapping is performed to map floating point
representation of ${w}_{i}$ to $\mathbb{Z}_{q}$ with $q$ being a large number,
and therefore, ${w}_{i}\in\mathbb{Z}_{q}^{m}$. If not specified, we assume all
${w}_{i}\in\mathbb{Z}_{q}^{m}$ when the context is clear. The protocol then
generates a private random helper ${r^{w}_{i}}\in\mathbb{Z}^{m}_{q}$. Given
local model ${w}_{i}$ and random helper ${r^{w}_{i}}$, $P_{i}$ next generates
a commitment of ${w}_{i}$ as
$\mathcal{W}_{i}=\mathcal{C}({w_{i}},{r^{w}_{i}})$, where $\mathcal{C}$
represents the commitment operation (we defer the detailed introduction on
commitment later). We say that ${w}_{i}$ w.r.t. $\mathcal{W}_{i}$ is the
claimed local model of $\mathcal{W}_{i}$. Note that for a benign participant,
${w}_{i}$ is exactly the local model, but for a Byzantine participant, the
claim of $\mathcal{W}_{i}$ may not be equal to its local model. The commitment
$\mathcal{W}_{i}$ is then broadcast to all other participants using BFT
broadcast. The details of the BFT broadcast can be found in Appendix A.

Brave utilizes the Pedersen commitment scheme for $\mathcal{C}$, defined as
follows.

######  Definition 3 (Pedersen Commitment Scheme (Pedersen 1992)).

Let $G_{q}$ denote a group of prime order $q$, such that the discrete
logarithm problem in this group is infeasible. Let $g$ and $h$ denote
independent generators of $G_{q}$ that are known to all participants. The
commitment $\mathcal{W}_{i}$ of local model ${w}_{i}\in\mathbb{Z}_{q}$ is
generated as

$\mathcal{C}({w}_{i},{r}_{i}^{{w}}):=g^{{w}_{i}}h^{{r}_{i}^{{w}}},$ (3)

where exponents and multiplication are coordinate-wise.

The Pedersen commitment in Eqn. (3) provides our protocol with the following
properties. First, the commitment $\mathcal{W}_{i}$ does not reveal any
information about the local model ${w}_{i}$, and thus ${w}_{i}$ is
_information-theoretically hiding_ (Pedersen 1992). Second, the commitment is
_computationally binding_ in the sense that one cannot solve for a local model
${w}_{i}^{\prime}$ such that
$\mathcal{C}({w}_{i},{r}_{i}^{{w}})=\mathcal{C}({w}_{i}^{\prime},{r}_{i}^{{w}^{\prime}})$
to open the commitment if it is unable to solve discrete logarithm problems.
Finally, the commitments obtained using Eqn. (3) are _additively homomorphic_
, i.e.,

$\mathcal{C}({w}_{1},{r}_{1}^{{w}})\mathcal{C}({w}_{2},{r}_{2}^{{w}})=\mathcal{C}({w}_{1}+{w}_{2},{r}_{1}^{{w}}+{r}_{2}^{{w}}).$
(4)

These properties are summarized in the following lemma 1.

######  Lemma 1 ((Pedersen 1992)).

The commitment procedure in Definition 3 is computationally binding and
additively homomorphic. Furthermore, it ensures that the local model ${w}_{i}$
is information-theoretically hiding.

In our design, the commitment scheme “locks” the initial input and prevents an
adversary node from modifying it in later steps. We prove that the proposed
commitment allows us to achieve the information-theoretic privacy and
Byzantine resilience of Brave in the Appendix. For a comprehensive
understanding, detailed pseudocode of this stage is provided in Algorithm 1 in
Appendix A.

### Stage 2: Privacy-Preserving Comparison

In this stage, each $P_{i}$ conducts a privacy-preserving comparison, which
coordinate-wise compares its model with all other participants. To preserve
the privacy of the true values in the local model, the comparison is achieved
by sharing a masked value obtained by adding a random number to the true
value, then canceling it during pairwise comparison.

Specifically, $P_{i}$ generates two random vectors
${v_{ij}},{r^{v}_{ij}}\in\mathbb{Z}_{q}^{m}$ associated with each $P_{j}$. It
then calculates a masked local model of $P_{i}$ with respect to $P_{j}$ as
${c_{ij}}={w_{i}}+{v_{ij}}$, and sums two random helpers as
${r^{w+v}_{ij}}={r^{w}_{i}}+{r^{v}_{ij}}$ for the purpose of authentication.
After that, it computes the commitment of ${v_{ij}}$, denoted as
$\mathcal{V}_{ij}$, using Eqn. (3) and random helper $r_{ij}^{v}$, and sends
${c_{ij}}$, ${r^{w+v}_{ij}}$, as well as $\mathcal{V}_{ij}$ to $P_{j}$. In
this communication, there are also some random vectors ${s^{1}_{ij}}$,
${r^{s1}_{ij}}$, ${s^{2}_{ij}}$, and ${r^{s2}_{ij}}$ being exchanged, which
serve as padding randomness in the next stage. After receiving the message
from $P_{j}$, $P_{i}$ leverages the additively homomorphic property of
commitment (Lemma 1) to verify the authenticity of $P_{j}$’s masked local
model $c_{ji}$ using

$\mathcal{W}_{j}\cdot\mathcal{V}_{ji}=\mathcal{C}(c_{ji},r^{w+v}_{ji}),$ (5)

where $\mathcal{W}_{j}$ is the commitment generated by $P_{j}$ in Stage 1. If
Eqn. (5) holds for every coordinate of ${c_{ji}}$, $P_{i}$ calculates
${d_{ij}}={v_{ij}}+{c_{ji}}$ and $r^{d}_{ij}=r^{v}_{ij}+r^{w+v}_{ji}$. It then
sends a message $m_{ij}:=[{d_{ij}}$,
${r^{d}_{ij}}$,$\mathcal{V}_{ij}$,$\mathcal{V}_{ji}$] to all other
participants except $P_{i}$. As shown in Fig. 2, we do not use BFT broadcast
here, since $P_{i}$ can never know ${d_{ij}}$ — if it knows, it can calculate
${v_{ji}}$, and then get ${P_{j}}$’s local model ${w_{j}}={{c_{ji}-v_{ji}}}$.

After exchanging messages with all other participants, each $P_{i}$ now
coordinate-wise compares the local models of any other two participants
denoted as $w_{q}$ and $w_{p}$ with $q,p\neq i$. $P_{i}$ first check if
$\mathcal{V}_{pq}$ or $\mathcal{V}_{qp}$ from $P_{q}$ and $P_{p}$ are the
same, If they are not the same, then at least one of $P_{q}$ and $P_{p}$ is
malicious. The participant then verifies whether the following two relations

$\left\\{\begin{array}[]{l}{d_{pq}}={v_{pq}+c_{qp}}={v_{pq}}+{v_{qp}}+{w_{q}}\\\
{d_{qp}}={v_{qp}}+{c_{pq}}={v_{qp}}+{v_{pq}}+{w_{p}}\end{array}\right.$ (6)

hold true or not by calculating the commitment of $d_{pq}$ and $d_{qp}$ via
$\mathcal{V}_{pq}$, $\mathcal{V}_{qp}$, $\mathcal{W}_{p}$, and
$\mathcal{W}_{q}$. Note that ${v_{pq}}+{v_{qp}}$ is a common term in Eqn. (6).
Therefore, if Eqn. (6) holds for all coordinates, then $P_{i}$ can obtain a
coordinate-wise relationship $\bowtie$ between $w_{p}^{k}$ and $w_{q}^{k}$ for
each coordinate $k$, where $\bowtie\in\\{<,>\\}$. We assume ties are broken
arbitrarily, so that an equality relationship does not occur. Finally, $P_{i}$
broadcasts the relationship of each $P_{p}$ and $P_{q}$ along each coordinate
$k$ to all participants using BFT broadcast. Please refer to Algorithm 2 in
Appendix A for detailed information.

### Stage 3: Sorting & Trimming

The Sorting & Trimming stage starts after the relationships are broadcast. In
this stage, $P_{i}$ first counts the relationships it received from BFT
broadcast. If a relationship $w_{p}^{k}\bowtie w_{q}^{k}$ appears more than
$2f$ times, it is accepted by $P_{i}$. Then in each coordinate $k$, $P_{i}$
sorts $\\{w_{j}^{k}:P_{j}\in\mathbb{P}\setminus{P_{i}}\\}$ coordinate-wise in
ascending order based on the accepted relationships as
$\mathcal{S}^{k}_{i}:=w_{a}^{k}<\ldots<w_{b}^{k}$. We denote the length of
$\mathcal{S}^{k}_{i}$ as $N_{i}^{k}\leq N$, where the equality holds when all
local models of the participants can be sorted in $\mathcal{S}^{k}_{i}$ using
$\mathcal{R}_{pq}$. After sorting, $P_{i}$ trims the lowest $f$ and highest
$f$ values in each $\mathcal{S}^{k}_{i}$. We denote the remaining participants
in the trimmed $\mathcal{S}^{k}_{i}$ as _contributors_ of coordinate $k$,
denoted as $\mathbb{C}^{k}_{i}\subset\mathbb{P}$. Detailed protocol can be
found in Algorithm 3 in Appendix A.

### Stage 4: Aggregation & Verification

Given the contributors from Stage 3, the last stage, Aggregation and
Verification, sums the local models of contributors and updates a global
model. Specifically, each $P_{i}$ calculates a cloaked local model
$\bar{w}_{i}$ within each coordinate $k$ as follows

$\bar{w}_{i}^{k}:=\left(w_{i}^{k}-\sum_{j\in\mathbb{C}^{k}_{-i}}a^{k}_{ij}+\sum_{j\in\mathbb{C}^{k}_{+i}}a^{k}_{ij}\right)\bmod\beta,$
(7)

where $\mathbb{C}^{k}_{-i}\subset\mathbb{C}_{i}^{k}$ (resp.
$\mathbb{C}^{k}_{+i}\subset\mathbb{C}_{i}^{k}$) is the set of contributors
whose local models are lower (resp. greater) than $w_{i}^{k}$ in $k$-th
coordinate, $\beta$ is a commonly known large prime number, and $a_{ij}$ is an
agreed randomness between $P_{i}$ and $P_{j}$. A similar calculation will be
performed to obtain the summation of the cloaked random helpers for
verification. Then $P_{i}$ sends the cloaked $\bar{w}_{i}$ and $\bar{r}_{i}$
with corresponding commitments $\mathcal{A}_{i}$ and $\mathcal{B}_{i}$ to all
participants via BFT broadcast.

After receiving $\bar{w}_{i}$ and $\bar{r}_{i}$ from the BFT broadcast, all
participants then sum the cloaked values and calculate the global model
$\bar{w}$. Each participant then verifies if

$\mathcal{C}(\bar{w}^{k},\bar{r}^{k})=\prod_{P_{j}\in\mathbb{C}_{i}^{k}}\mathcal{W}_{j}^{k}$
(8)

holds in each coordinate. If Eqn. (8) holds, $P_{i}$ computes $w^{k}$ as
$\frac{\bar{w}^{k}}{N_{i}^{k}-2f}$ for each coordinate $k$. $P_{i}$ next
projects $w^{k}$ to the floating numbers, and completes one iteration of P2P
FL. The pseudocode is provided in Algorithm 4 in Appendix A.

We note that if Eqn. (8) does not hold, then $P_{i}$ can identify the
Byzantine adversaries thanks to the commitment scheme. Specifically, for each
contributor $P_{j}\in\mathbb{C}_{i}^{k}$, if

$\mathcal{C}(\bar{w}_{j}^{k},\bar{r}^{k})\neq\mathcal{W}_{j}^{k}\prod_{P_{h}\in\mathbb{C}^{k}_{-i}}\mathcal{A}_{ih}^{k}\prod_{P_{h}\in\mathbb{C}^{k}_{+i}}(\mathcal{A}_{ih}^{k})^{-1},$
(9)

then $P_{i}$ flags $P_{j}$ as a Byzantine adversary. We term this procedure as
blame, and the detailed algorithm can be found in Algorithm 5 in Appendix A.

### Privacy and Resilience Guarantees of Brave

We present the information-theoretic privacy and Byzantine resilience of Brave
in Appendix B. Specifically, we leverage Lemma 1 of the Pedersen Commitment
scheme to prove information-theoretic privacy. To show the Byzantine
resilience of Brave, we prove $\epsilon$-convergence and agreement,
respectively. We show that the global model obtained by the benign
participants deviates from the optimal one by a bounded distance, i.e.,
satisfies $\epsilon$-convergence property. We then prove agreement by showing
that the relationship $\bowtie$ accepted by benign participants preserves the
correct ordering of the claimed local models, then prove the global model of
all benign participants is the same using BFT broadcast.

##  5 Experiments

We evaluate Brave against three state-of-the-art adversaries using two image
classification tasks. We demonstrate that Brave ensures the models learned by
P2P FL achieve comparable accuracy to global models trained in the absence of
any adversary, and hence resilient to the adversaries.

Table 1: This table presents the classification accuracy of the learned 2NN and CNN using a P2P FL with $N=10$ and $f=2$. The second row of the table represents the scenario where the Byzantine adversaries send their true local models and do not launch any attack. Rows 3-6 correspond to different threat models. We observe that Brave ensures the P2P FL to learn a global model with near-optimal classification accuracy against all threat models, and hence is Byzantine-resilient. Adversary Strategy | w/o Brave | Brave
---|---|---
2NN+MNIST | CNN+CIFAR10 | 2NN+MNIST | CNN+CIFAR10
No Attack | $\mathbf{97.35}\%$ | $\mathbf{63.94}\%$ | $97.21\%$ | $63.55\%$
Label Flip | $89.91\%$ | $52.15\%$ | $\textbf{96.74}\%$ | $\mathbf{60.91}\%$
Sign Flip | $11.35\%$ | $48.68\%$ | $\textbf{97.02}\%$ | $\mathbf{63.54}\%$
Gaussian $(\sigma=0.1)$ | $92.02\%$ | $55.58\%$ | $\textbf{96.92}\%$ | $\mathbf{63.08}\%$
Gaussian $(\sigma=1)$ | $53.01\%$ | $10.01\%$ | $\textbf{97.12}\%$ | $\mathbf{61.92}\%$
Table 2: This table presents the accuracy of the 2NN model trained by P2P FL with Brave involving $N=10,15,20$ participants. The number of Byzantine adversaries is set as $f/N=20\%$. We observe that Brave ensures near-optimal classification accuracy with different choices of $N$, and Brave is insensitive to parameter $N$. Adv. Strategy | $N=10$ | $N=15$ | $N=20$
---|---|---|---
No Attack | $97.21\%$ | $97.54\%$ | $\mathbf{97.64}\%$
Label Flip | $96.74\%$ | $97.18\%$ | $\mathbf{97.50}\%$
Sign Flip | $97.02\%$ | $97.34\%$ | $\mathbf{97.51}\%$
Gaussian ($\sigma=0.1$) | $96.92\%$ | $97.39\%$ | $\mathbf{97.42}\%$
Gaussian ($\sigma=1$) | $97.12\%$ | $97.27\%$ | $\mathbf{97.59}\%$

### Experimental Setup

_Datasets_ : We use two benchmark datasets: CIFAR10 (Krizhevsky 2009) and
MNIST (LeCun, Cortes, and Burges 2010), for image classification tasks.
CIFAR10 consists of $50000$ training and $10000$ testing images, each of size
$32\times 32$. Each image within CIFAR10 belongs to one of ten classes. There
are $60000$ training and $10000$ testing images in MNIST dataset. Each image
is of size $28\times 28$, and can be classified to one out of ten classes.

_Brave Setup_: We implement Brave on two P2P FL with different settings. In
the first P2P FL, we let the participants train a 2-hidden-layer model (2NN)
using samples from the MNIST dataset. In the second P2P FL, the participants
learn a Convolutional Neural Network (CNN) model using CIFAR10 dataset. In
both P2P FL, the training images from CIFAR10 or MNIST dataset are
independently and identically distributed (i.i.d.) to the participants so that
each participant has $|\mathcal{D}_{i}|=2000$ images within its private
dataset. The participants update their local models $w_{i}(t)$ using
stochastic gradient descent (SGD) algorithm with learning rate $\eta=0.01$
(McMahan et al. 2017).

_Baseline Setup_ : We present the effectiveness of Brave by comparing with a
baseline, P2P FL-naïve. The baseline implements the classic P2P FL as given in
Eqn. (1) and (2).

_Threat Models_ : We evaluate Brave against Byzantine adversaries who adopt
distinct strategies, detailed as below.

  * •

_No Attack_ : The adversaries does not initiate any attack and behave as
benign participants.

  * •

_Label Flip Attack(Tolpegin et al. 2020)_: Label flip attack is a data
poisoning attack. A Byzantine adversary launches a label flip attack by
training its local model using mislabeled data. As a consequence, a global
model that is corrupted by label flip attacks may misclassify the input image,
and hence exhibits low classification accuracy.

  * •

_Sign Flip Attack(Xie, Koyejo, and Gupta 2019)_: A Byzantine adversary carries
out a sign flip attack by first flipping the sign of its local model and then
sending it to the other participants. As a consequence, the original local
model $w_{i}$ of a Byzantine adversary is manipulated as $-w_{i}$.

  * •

_Gaussian Attack(Fang et al. 2020)_: Gaussian attack is essentially an
instantiation of a model poisoning attack. A Byzantine adversary manipulates
its local model by adding a zero-mean Gaussian noise
$y^{k}\sim\mathcal{N}(0,\sigma^{2})$ to $w_{i}^{k}(t)$ along each dimension
$k$. Here $\sigma$ is the standard deviation that can be tuned by the
Byzantine adversary. In our experiments, we evaluate the scenarios where
$\sigma$ are chosen as $0.1$ and $1$.

The state-of-the-art white-box membership inference attack (MIA) (Zhang et al.
2020) requires the passive adversaries to access the local models of other
participants and the architecture of the neural network. By our design of
Brave, the passive adversaries can only receive the masked local models and
commitments, whereas the local models are hidden. Therefore, the white-box MIA
is infeasible for P2P FL when Brave is implemented.

_Evaluation Metric_ : We use classification accuracy over the testing dataset
as the evaluation metric. It captures the fraction of input images sampled
from the testing dataset that can be correctly classified by using the learned
model.

### Experimental Results

In what follows, we demonstrate the effectiveness of Brave.

_Byzantine Resilience of Brave_: We evaluate the classification accuracy of
the learned global models obtained by P2P FL with $N=10$ participants and
$f=2$ Byzantine adversaries. In Table 1, we present the classification
accuracy of the learned 2NN and CNN when the Byzantine adversaries adopt
different attack strategies. We observe that if the Byzantine adversaries does
not initiate any attack, then Brave retains comparable accuracy compared with
classic P2P FL that does not implement Brave. Furthermore, Brave guarantees
significantly higher accuracy of the learned model once the Byzantine
adversaries send compromised local models to the other participants, and
thereby is Byzantine-resilient.

(a) Label Flip Attack

(b) Sign Flip Attack

(c) Gaussian Attack ($\sigma=1$)

Figure 3: This figure presents the accuracy of 2NN learned using P2P FL with
$N=10$ participants at each iteration $t$. When the number of Byzantine
adversaries $f$ satisfies $N>3f+2$, i.e., $f\in\\{0,1,2\\}$, Brave ensures
$\epsilon$-convergence property as given in Definition 2. When $f$ violates
$N>3f+2$, the Byzantine adversaries can corrupt the learned 2NN, and even
prevents FL from converging (Fig. 3(a), $f=4$).

(a) Label Flip Attack

(b) Sign Flip Attack

(c) Gaussian Attack ($\sigma=1$)

Figure 4: This figure presents how accuracy of the learned 2NN varies with
respect to the ratio of Byzantine participants when $N=10$. If $N>3f+2$ holds
(the left-hand side of the vertical red line), then Brave guarantees Byzantine
resilience as the performance of learned 2NN is comparable to P2P FL-naïve
learned without any adversary.

_$\epsilon$ -convergence of Brave_: We demonstrate $\epsilon$-convergence of
Brave in Fig. 3(a)-3(c). We observe that if $N>3f+2$ holds, then Brave
guarantees that the global model learned in the presence of Byzantine
adversaries remains $\epsilon$-close to the global model learned when $f=0$.
We further notice that the value of $\epsilon$ increases with respect to the
number of Byzantine adversaries. The presence of more Byzantine adversaries
could introduce additional bias to the learned global model, or even cause FL
to fail (as shown in Fig. 3(a) when $f=4$).

_Insensitivity to the Number of Participants $N$_: We evaluate the
effectiveness of Brave when applying to P2P FL of different scales, i.e., the
number of participants is $N=\\{10,15,20\\}$. In all three settings, we fix
the ratio of Byzantine participants as $f/N=20\%$. We find that the
classification accuracy increases with respect to the number of participants
$N$, given that $f/N$ remains fixed. Such increment of accuracy is because
more training data is used as $N$ increases. Therefore, we believe that Brave
is insensitive to the scale of P2P FL. For P2P FL of different scales, Brave
guarantees their Byzantine resilience when $N>3f+2$ holds.

_Sensitivity to the Ratio of Byzantine Adversaries $f/N$_: We evaluate the
effectiveness of Brave when the ratio of Byzantine adversaries $f/N$ varies in
Fig. 4(a)-4(c). We consider the 2NN learned using P2P FL with $N=10$. We
observe that Brave can maintain high classification accuracy (stay close to
the orange curve with triangle markers) when $f$ satisfies $N>3f+2$ (the left-
hand side of the vertical red line). When P2P FL does not implement Brave, a
significant decrease in accuracy can be observed from the blue curve even when
$N>3f+2$ holds. Once $N>3f+2$ is violated, the Byzantine resilience guarantee
provided by Brave decreases. However, P2P FL with Brave implemented still
outperforms P2P FL-naïve which does not adopt Brave.

##  6 Conclusion and Future Work

In this paper, we considered peer-to-peer federated learning in the presence
of both passive and Byzantine adversaries. The passive adversaries aimed at
inferring the other participants’ private information during the training
process, whereas Byzantine adversaries could arbitrarily manipulate the
information it sent to disrupt the learning algorithm. We developed a four-
stage P2P FL protocol named Brave that information-theoretically preserves
privacy and is resilient to malicious attacks caused by Byzantine adversaries.
We evaluated Brave using two image classification tasks with CIFAR10 and MNIST
datasets. Our results showed that Brave can effectively defend against the
state-of-the-art adversaries. In future work, we will reduce the complexity of
Brave and incorporate the delays incurred on the communication links when
participants exchange information.

## Acknowledgements

This work is partially supported by the National Science Foundation (NSF)
under grant No. 2229876 and Air Force Office of Scientific Research (AFOSR)
under grant FA9550-23-1-0208.

This work is supported in part by funds provided by the National Science
Foundation, by the Department of Homeland Security, and by IBM. Any opinions,
findings, and conclusions or recommendations expressed in this material are
those of the author(s) and do not necessarily reflect the views of the
National Science Foundation or its federal agency and industry partners.

## References

  * Bagdasaryan, Poursaeed, and Shmatikov (2019) Bagdasaryan, E.; Poursaeed, O.; and Shmatikov, V. 2019.  Differential privacy has disparate impact on model accuracy.  _Advances in Neural Information Processing Systems_ , 32.
  * Blanchard et al. (2017) Blanchard, P.; El Mhamdi, E. M.; Guerraoui, R.; and Stainer, J. 2017.  Machine learning with adversaries: Byzantine tolerant gradient descent.  _Advances in Neural Information Processing Systems_ , 30.
  * Bonawitz et al. (2017) Bonawitz, K.; Ivanov, V.; Kreuter, B.; Marcedone, A.; McMahan, H. B.; Patel, S.; Ramage, D.; Segal, A.; and Seth, K. 2017.  Practical secure aggregation for privacy-preserving machine learning.  In _ACM SIGSAC Conference on Computer and Communications Security_ , 1175–1191.
  * Castro and Liskov (1999) Castro, M.; and Liskov, B. 1999.  Practical Byzantine Fault Tolerance.  In _Third Symposium on Operating Systems Design and Implementation_ , OSDI ’99, 173–186. USA: USENIX Association.  ISBN 1880446391.
  * Che et al. (2021) Che, C.; Li, X.; Chen, C.; He, X.; and Zheng, Z. 2021.  A Decentralized Federated Learning Framework via Committee Mechanism with Convergence Guarantee.  _arXiv preprint arXiv:2108.00365_.
  * Chen et al. (2021) Chen, J.-H.; Chen, M.-R.; Zeng, G.-Q.; and Weng, J.-S. 2021.  BDFL: a Byzantine-fault-tolerance decentralized federated learning method for autonomous vehicle.  _IEEE Transactions on Vehicular Technology_ , 70(9): 8639–8652.
  * Dwork (2008) Dwork, C. 2008.  Differential privacy: A survey of results.  In _International Conference on Theory and Applications of Models of Computation_ , 1–19. Springer.
  * Fang et al. (2020) Fang, M.; Cao, X.; Jia, J.; and Gong, N. 2020.  Local model poisoning attacks to Byzantine-robust federated learning.  In _29th USENIX Security Symposium (USENIX Security 20)_ , 1605–1622.
  * Han et al. (2022) Han, J.; Han, Y.; Huang, G.; and Ma, Y. 2022.  DeFL: Decentralized Weight Aggregation for Cross-silo Federated Learning.  _arXiv preprint arXiv:2208.00848_.
  * He, Karimireddy, and Jaggi (2020) He, L.; Karimireddy, S. P.; and Jaggi, M. 2020.  Secure Byzantine-robust machine learning.  _arXiv preprint arXiv:2006.04747_.
  * Hitaj, Ateniese, and Perez-Cruz (2017) Hitaj, B.; Ateniese, G.; and Perez-Cruz, F. 2017.  Deep models under the GAN: information leakage from collaborative deep learning.  In _ACM SIGSAC Conference on Computer and Communications Security_ , 603–618.
  * Joux, Odlyzko, and Pierrot (2014) Joux, A.; Odlyzko, A.; and Pierrot, C. 2014.  The past, evolving present, and future of the discrete logarithm.  _Open Problems in Mathematics and Computational Science_ , 5–36.
  * Konečnỳ et al. (2016) Konečnỳ, J.; McMahan, H. B.; Yu, F. X.; Richtárik, P.; Suresh, A. T.; and Bacon, D. 2016.  Federated learning: Strategies for improving communication efficiency.  _arXiv preprint arXiv:1610.05492_.
  * Kotla et al. (2007) Kotla, R.; Alvisi, L.; Dahlin, M.; Clement, A.; and Wong, E. 2007.  Zyzzyva: Speculative Byzantine fault tolerance.  In _Twenty-first ACM SIGOPS Symposium on Operating Systems Principles_ , 45–58.
  * Krizhevsky (2009) Krizhevsky, A. 2009.  _Learning multiple layers of features from tiny images_.  Ph.D. thesis, University of Toronto.
  * Lalitha et al. (2019) Lalitha, A.; Kilinc, O. C.; Javidi, T.; and Koushanfar, F. 2019.  Peer-to-peer federated learning on graphs.  _arXiv preprint arXiv:1901.11173_.
  * Lamport, Shostak, and Pease (2019) Lamport, L.; Shostak, R.; and Pease, M. 2019.  _The Byzantine generals problem_ , 203–226.  Association for Computing Machinery.  ISBN 9781450372701.
  * LeCun, Cortes, and Burges (2010) LeCun, Y.; Cortes, C.; and Burges, C. 2010.  MNIST handwritten digit database.  Available: http://yann.lecun.com/exdb/mnist.
  * Lee and Chang (1998) Lee, W.-B.; and Chang, C.-C. 1998.  Efficient group signature scheme based on the discrete logarithm.  _IEE Proceedings-Computers and Digital Techniques_ , 145(1): 15–18.
  * Li et al. (2019) Li, L.; Xu, W.; Chen, T.; Giannakis, G. B.; and Ling, Q. 2019.  RSA: Byzantine-robust stochastic aggregation methods for distributed learning from heterogeneous datasets.  In _the AAAI Conference on Artificial Intelligence_ , volume 33, 1544–1551.
  * Li et al. (2021) Li, Y.; Chen, C.; Liu, N.; Huang, H.; Zheng, Z.; and Yan, Q. 2021.  A Blockchain-Based Decentralized Federated Learning Framework with Committee Consensus.  _IEEE Network_ , 35(1): 234–241.
  * Liu et al. (2021) Liu, A.; Zhang, J. Y.; Kumar, N.; Khurana, D.; and Koyejo, O. O. 2021.  Scalable Robust Federated Learning with Provable Security Guarantees.
  * Ma et al. (2022a) Ma, X.; Sun, X.; Wu, Y.; Liu, Z.; Chen, X.; and Dong, C. 2022a.  Differentially Private Byzantine-robust Federated Learning.  _IEEE Transactions on Parallel and Distributed Systems_.
  * Ma et al. (2022b) Ma, X.; Zhou, Y.; Wang, L.; and Miao, M. 2022b.  Privacy-preserving Byzantine-robust federated learning.  _Computer Standards & Interfaces_, 80: 103561.
  * McCurley (1990) McCurley, K. S. 1990.  The discrete logarithm problem.  In _Proc. of Symp. in Applied Math_ , volume 42, 49–74. USA.
  * McMahan et al. (2017) McMahan, B.; Moore, E.; Ramage, D.; Hampson, S.; and y Arcas, B. A. 2017.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial Intelligence and Statistics_ , 1273–1282. PMLR.
  * Mohamad et al. (2023) Mohamad, M.; Onen, M.; Jaballah, W. B.; and Contu, M. 2023.  SoK: Secure Aggregation based on cryptographic schemes for Federated Learning.  In _Privacy Enhancing Technologies Symposium_ , volume 1.
  * Mugunthan et al. (2019) Mugunthan, V.; Polychroniadou, A.; Byrd, D.; and Balch, T. H. 2019.  SMPAI: Secure multi-party computation for federated learning.  In _the NeurIPS 2019 Workshop on Robust AI in Financial Services_.
  * Nasr, Shokri, and Houmansadr (2019) Nasr, M.; Shokri, R.; and Houmansadr, A. 2019.  Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning.  In _IEEE Symposium on Security and Privacy (SP)_ , 739–753. IEEE.
  * Pedersen (1992) Pedersen, T. P. 1992.  Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing.  In _Advances in Cryptology — CRYPTO ’91_ , volume 576, 129–140. Springer Berlin Heidelberg.  ISBN 978-3-540-55188-1.
  * Ramanan and Nakayama (2020) Ramanan, P.; and Nakayama, K. 2020.  Baffle: Blockchain based aggregator free federated learning.  In _2020 IEEE International Conference on Blockchain (Blockchain)_ , 72–81. IEEE.
  * Roy et al. (2019) Roy, A. G.; Siddiqui, S.; Pölsterl, S.; Navab, N.; and Wachinger, C. 2019.  Braintorrent: A peer-to-peer environment for decentralized federated learning.  _arXiv preprint arXiv:1905.06731_.
  * Savazzi, Nicoli, and Rampa (2020) Savazzi, S.; Nicoli, M.; and Rampa, V. 2020.  Federated Learning With Cooperating Devices: A Consensus Approach for Massive IoT Networks.  _IEEE Internet of Things Journal_ , 7(5): 4641–4654.
  * Shayan et al. (2021) Shayan, M.; Fung, C.; Yoon, C. J. M.; and Beschastnikh, I. 2021.  Biscotti: A Blockchain System for Private and Secure Federated Learning.  _IEEE Transactions on Parallel and Distributed Systems_ , 32(7): 1513–1525.
  * Shi (2020) Shi, E. 2020.  Foundations of Distributed Consensus and Blockchains.  _URL: http://elaineshi. com/docs/blockchain-book. pdf_.
  * Tolpegin et al. (2020) Tolpegin, V.; Truex, S.; Gursoy, M. E.; and Liu, L. 2020.  Data poisoning attacks against federated learning systems.  In _European Symposium on Research in Computer Security_ , 480–501. Springer.
  * Truex et al. (2019) Truex, S.; Baracaldo, N.; Anwar, A.; Steinke, T.; Ludwig, H.; Zhang, R.; and Zhou, Y. 2019.  A hybrid approach to privacy-preserving federated learning.  In _12th ACM Workshop on Artificial Intelligence and Security_ , 1–11.
  * Velicheti, Xia, and Koyejo (2021) Velicheti, R. K.; Xia, D.; and Koyejo, O. 2021.  Secure Byzantine-Robust Distributed Learning via Clustering.  _arXiv preprint arXiv:2110.02940_.
  * Wei et al. (2020) Wei, K.; Li, J.; Ding, M.; Ma, C.; Yang, H. H.; Farokhi, F.; Jin, S.; Quek, T. Q.; and Poor, H. V. 2020.  Federated learning with differential privacy: Algorithms and performance analysis.  _IEEE Transactions on Information Forensics and Security_ , 15: 3454–3469.
  * Xie, Koyejo, and Gupta (2019) Xie, C.; Koyejo, S.; and Gupta, I. 2019.  Zeno: Distributed stochastic gradient descent with suspicion-based fault-tolerance.  In _International Conference on Machine Learning_ , 6893–6901. PMLR.
  * Yao (1982) Yao, A. C. 1982.  Protocols for secure computations.  In _23rd Annual Symposium on Foundations of Computer Science_ , 160–164.
  * Yin et al. (2018) Yin, D.; Chen, Y.; Kannan, R.; and Bartlett, P. 2018.  Byzantine-robust distributed learning: Towards optimal statistical rates.  In _International Conference on Machine Learning_ , 5650–5659. PMLR.
  * Yin et al. (2019) Yin, M.; Malkhi, D.; Reiter, M. K.; Gueta, G. G.; and Abraham, I. 2019.  Hotstuff: BFT consensus with linearity and responsiveness.  In _ACM Symposium on Principles of Distributed Computing_ , 347–356.
  * Zhang et al. (2020) Zhang, J.; Zhang, J.; Chen, J.; and Yu, S. 2020.  GAN enhanced membership inference: A passive local attack in federated learning.  In _IEEE International Conference on Communications (ICC)_ , 1–6. IEEE.

##  Appendix A Detailed Algorithms of Brave

### BFT Broadcast

All stages of Brave require the participants to broadcast messages via a
module named BFT broadcast. BFT broadcast utilizes Byzantine-fault-tolerant
(BFT) distributed consensus algorithms, which follow a propose-vote paradigm
(Shi 2020). In the BFT broadcast, the message sent by each participant is
treated as a proposal. All participants will incorporate the proposal to their
local information set as long as more than $N-f$ participants agree with the
proposal. Typical implementations of the BFT distributed consensus algorithms
include PBFT (Castro and Liskov 1999), Zyzzyva (Kotla et al. 2007), and
Hotstuff (Yin et al. 2019). Using the state-of-the-art implementation of BFT
broadcast, Hotstuff (Yin et al. 2019), Brave guarantees that all participants
will reach an agreement on messages sent by the participants, with
communication complexity linear in $N$.

### Stage 1: Commitment

After updating its local model ${w}_{i}(t)$ in each iteration, participant
$P_{i}$ generates a commitment of ${w}_{i}(t)$. Commitment allows participants
to pledge to a chosen value while keeping it hidden from others, with the
ability to reveal that value later.

Algorithm 1 Stage 1: Commitment

1: for all $P_{i}\in\mathbb{P}$ in parallel do

2: ${w}_{i}=$ Update(${w}(t),\mathcal{D}_{i}$)

3: ${r^{w}_{i}}\leftarrow$ Generate a random helper for commitment

4: $\mathcal{W}_{i}=\mathcal{C}({w_{i}},{r^{w}_{i}})$

5: BFT-Broadcast($\mathcal{W}_{i}$)

6: end for

### Stage 2: Privacy-preserving Comparison

In this stage, participant $P_{i}$ conducts a privacy-preserving comparison,
which coordinate-wise compares its model with all other participants.

Algorithm 2 Stage 2: Privacy-Preserving Comparison

1: for all $P_{i}\in\mathbb{P}$ in parallel do

2: for all $P_{j}\in\mathbb{P}\setminus\\{P_{i}\\}$ in parallel do

3: Generate random vectors ${v_{ij}},{r^{v}_{ij}}$,
${s^{1}_{ij}},{r^{s1}_{ij}},{s^{2}_{ij}},{r^{s2}_{ij}}$ in
$\mathbb{Z}_{q}^{m}$

4: ${{c_{ij}}}={v_{ij}}+{w_{i}}$; ${r^{w+v}_{ij}}={r^{w}_{i}}+{r^{v}_{ij}}$

5: $\mathcal{V}_{ij}=\mathcal{C}({v_{ij}},{r^{v}_{ij}})$

6: Send [$\mathcal{V}_{ij}$, ${c_{ij}}$, ${r^{w+v}_{ij}}$, ${s^{1}_{ij}}$,
${r^{s1}_{ij}}$, ${s^{2}_{ij}}$, ${r^{s2}_{ij}}$] to $P_{j}$

7: Receive [$\mathcal{V}_{ji}$, ${c_{ji}}$, ${r^{w+v}_{ji}}$, ${s^{1}_{ji}}$,
${r^{s1}_{ji}}$, ${s^{2}_{ji}}$, ${r^{s2}_{ji}}$] from $P_{j}$

8: if $\mathcal{W}_{j}\cdot\mathcal{V}_{ji}=\mathcal{C}(c_{ji},r^{w+v}_{ji})$
then

9: $d_{ij}=v_{ij}+c_{ji}$; $r^{d}_{ij}=r^{v}_{ij}+r^{w+v}_{ji}$

10: Send $m_{ij}$=[$d_{ij}$, $r^{d}_{ij}$, $\mathcal{V}_{ij}$,
$\mathcal{V}_{ji}$] to $\mathbb{P}\setminus\\{P_{j}\\}$

11: end if

12: end for

13: while receive $m_{pq}$ and $m_{qp}$ from $P_{p}$ and $P_{q}$ do

14: if same values of $\mathcal{V}_{pq}$ or $\mathcal{V}_{qp}$ from $m_{pq}$
and $m_{qp}$ then

15: if
$\mathcal{C}(d_{pq},r^{d}_{pq})=\mathcal{V}_{pq}\cdot\mathcal{V}_{qp}\cdot\mathcal{W}_{q}$
and
$\mathcal{C}(d_{qp},r^{d}_{qp})=\mathcal{V}_{qp}\cdot\mathcal{V}_{pq}\cdot\mathcal{W}_{p}$
then

16: for all $k\in[m]$ do

17: $\mathcal{R}_{pq}=\\{w_{p}^{k}\bowtie w_{q}^{k}:\forall k\\}$

18: end for

19: BFT-Broadcast($\mathcal{R}_{pq}$)

20: end if

21: end if

22: end while

23: end for

### Stage 3: Sorting and Trimming

In this stage, the participant sorts the local models along each coordinate
after receiving the pairwise comparison results. It then trims the largest and
smallest $f$ values in each coordinate and denotes the remainder as
contributors.

Algorithm 3 Stage 3: Contributor Selection

1: for all $P_{i}\in\mathbb{P}$ in parallel do

2: for all $\mathcal{R}_{pq}$ from BFT Broadcast do

3: if $w_{p}^{k}>w_{q}^{k}$ (resp. $w_{p}^{k}<w_{q}^{k}$) appears more than
$2f$ times then

4: Accept $w_{p}^{k}>w_{q}^{k}$ (resp. $w_{p}^{k}<w_{q}^{k}$)

5: end if

6: end for

7: for all $k\in[m]$ do

8: $\mathcal{S}^{k}_{i}$ $\leftarrow$ Topological sort all accepted
relationships

9: $N_{i}^{k}\leftarrow$ Length of $\mathcal{S}^{k}_{i}$

10: $\mathbb{C}_{i}^{k}$ $\leftarrow$ Participants define sorted $(f+1)$-th to
$(N_{i}^{k}-f)$-th as Contributors.

11: end for

12: end for

### Stage 4: Aggregation and Verification

In this stage, $P_{i}$ generates a private one-time pad (Bonawitz et al.
2017), and applies it to mask the selected contributing coordinates of its
local model before transmitting them via BFT broadcast. After receiving the
masked coordinates from other participants, each $P_{i}$ adds the masked
values coordinate-wise and verifies authenticity leveraging the commitment
scheme. Finally, each $P_{i}$ computes the global model if the summations of
the masked values are authenticated. $P_{i}$ can also identify the Byzantine
adversaries if the summations are not authenticated using blame.

Algorithm 4 Stage 4: Aggregation and Verification

1: for all $P_{i}\in\mathbb{P}$ in parallel do

2: for all $P_{j}\in\mathbb{P}\setminus\\{P_{i}\\}$ do

3: $a_{ij}=s^{1}_{ij}+s^{1}_{ji}$; $r^{a}_{ij}=r^{s1}_{ij}+r^{s1}_{ij}$

4: $b_{ij}=s^{2}_{ij}+s^{2}_{ji}$; $r^{b}_{ij}=r^{s2}_{ij}+r^{s2}_{ij}$

5: $\mathcal{A}_{ij}=\mathcal{C}(a_{ij},r^{a}_{ij})$;
$\mathcal{B}_{ij}=\mathcal{C}(b_{ij},r^{b}_{ij})$

6: end for

7: $\mathcal{A}_{i},\mathcal{B}_{i}\leftarrow\text{Pack all
}\mathcal{A}_{ij}\text{ and }\mathcal{B}_{ij}$

8: for all $k\in[m]$ do

9: if $P_{i}\in\mathbb{C}_{i}^{k}$ then

10:
$\bar{w}_{i}^{k}=\left(w_{i}^{k}-\sum_{j\in\mathbb{C}^{k}_{-i}}a^{k}_{ij}+\sum_{j\in\mathbb{C}^{k}_{+i}}a^{k}_{ij}\right)\bmod\beta$

11:
$\bar{r}_{i}^{k}=\left(r_{i}^{k}-\sum_{j\in\mathbb{C}^{k}_{-i}}b^{k}_{ij}+\sum_{j\in\mathbb{C}^{k}_{+i}}b^{k}_{ij}\right)\bmod\beta$

12: end if

13: end for

14: BFT-Broadcast($\bar{w}_{i}$, $\bar{r}_{i}$, $\mathcal{A}_{i}$,
$\mathcal{B}_{i}$)

15: for all $k\in[m]$ do

16: $\bar{w}^{k}=\sum_{P_{j}\in\mathbb{C}_{i}^{k}}\bar{w}_{j}^{k}\bmod\beta$

17: $\bar{r}^{k}=\sum_{P_{j}\in\mathbb{C}_{i}^{k}}\bar{r}_{j}^{k}\bmod\beta$

18: if
$\mathcal{C}(\bar{w}^{k},\bar{r}^{k})=\prod_{P_{j}\in\mathbb{C}_{i}^{k}}\mathcal{W}_{j}^{k}$
then

19: $w^{k}=\frac{\bar{w}^{k}}{N_{i}^{k}-2f}$

20: end if

21: end for

22: end for

Algorithm 5 Blame

1: if
$\mathcal{C}(\bar{w}^{k},\bar{r}_{j}^{k})\neq\prod_{P_{j}\in\mathbb{C}_{i}^{k}}\mathcal{W}_{j}^{k}$
then

2: for all $P_{j}\in\mathbb{C}_{i}^{k}$ do

3: if
$\mathcal{C}(\bar{w}_{j}^{k},\bar{r}^{k})\neq\mathcal{W}_{j}^{k}\prod_{P_{h}\in\mathbb{C}^{k}_{-i}}\mathcal{A}_{ih}^{k}\prod_{P_{h}\in\mathbb{C}^{k}_{+i}}(\mathcal{A}_{ih}^{k})^{-1}$
then

4: Flag $P_{j}$ as Byzantine adversary

5: end if

6: end for

7: end if

##  Appendix B Theoretical Analysis of Brave

In this section, we theoretically analyze the information-theoretic privacy
and Byzantine resilience of Brave.

### Proof of Information-Theoretic Privacy

We show that when the passive adversaries are not colluding, Brave guarantees
P2P FL to be privacy-preserving as follows.

######  Theorem 2 (Information-theoretic Privacy).

Consider a P2P FL in the presence of passive adversaries who are not
colluding. Our proposed protocol, Brave, guarantees information-theoretic
privacy of the participants’ local models.

###### Proof Sketch.

The proof can be divided into two parts. First, Lemma 1 shows the information-
theoretically hiding property of the commitment, i.e., the commitment itself
contains no information about the local model. Second, during the execution of
the protocol, the local model is always masked with some random vectors
$v_{ij}$ in Algorithm 2 and
$\sum_{j\in\mathbb{C}^{k}_{+i}}a^{k}_{ij}-\sum_{j\in\mathbb{C}^{k}_{-i}}a^{k}_{ij}$
in Algorithm 4, which are also information-theoretically hiding by our
protocol design. Therefore, the masked local model is independent of the local
model. ∎

### Proof of Byzantine Resilience

In what follows, we establish the Byzantine resilience of P2P FL after
applying Brave if $N>3f+2$. We first show that using Brave, the messages
broadcast by benign participants preserve the ordering of claimed local
models. The preservation of order prevents Byzantine adversaries from forging
the results of sorting by manipulating their claimed local models.

######  Lemma 3 (Local Non-Forgeability).

If a benign participant $P_{i}$ broadcasts $w^{k}_{p}>w^{k}_{q}$ at coordinate
$k$, then the claimed local model of $P_{p}$ w.r.t. to $\mathcal{W}_{p}$ is
greater than that of $P_{q}$ at coordinate $k$.

###### Proof.

Consider three cases when i) both $P_{p}$ and $P_{q}$ are benign, ii) either
$P_{p}$ or $P_{q}$ is Byzantine, iii) both $P_{p}$ and $P_{q}$ are Byzantine.
We show the proof of case iii), and similar approaches can be applied to cases
i) and ii).

Suppose that in coordinate $k$, $w^{k}_{p}>w^{k}_{q}$ holds. To pass the
authentication of a benign $P_{i}$, $P_{p}$ and $P_{q}$ must find a) another
valid pairs $w_{q}^{\prime}$ or $w_{p}^{\prime}$ such that
$w^{k^{\prime}}_{q}>w^{k^{\prime}}_{p}$ but $w^{k}_{q}<w^{k}_{p}$, or b)
another valid vector $v_{qp}^{\prime}+v_{pq}^{\prime}$ such that
$v^{k^{\prime}}_{qp}+v^{k^{\prime}}_{pq}-v^{k}_{qp}-v^{k}_{pq}>w^{k}_{p}-w^{k}_{q}$.
However, Lemma 1 indicates that the Pedersen commitment scheme is
computational binding, i.e., a Byzantine participant can not find another
value that opens the same commitment. Therefore, both a) and b) are
infeasible, and the comparison result of $d_{pq}$ and $d_{qp}$ truly reflects
the relationship between the claimed local models $w_{p}$ and $w_{q}$. ∎

Remark. In Lemma 3, we prove that the relationship accepted by benign
participants preserves the correct ordering of the claimed local models.

Next, we move from a local perspective to a holistic one. We first show below
the Byzantine-resilience of BFT broadcast if $N>3f+2$. We then prove the
adversary cannot forge a comparison, as shown in Proposition 1.

######  Lemma 4.

If $N>3f+2$, then the messages sent by a participant via BFT broadcast will be
received identically by benign participants.

###### Proof.

According to (Lamport, Shostak, and Pease 2019), consensus can be reached if
$N>3f$ without authentication under synchronous network assumption, and
identical information can be received. Thus the lemma follows given
$N>3f+2>3f$. ∎

######  Proposition 1 (Global Non-Forgeability).

If $w^{k}_{p}>w^{k}_{q}$ is accepted by a benign participant $P_{i}$ using
Algorithm 2, then the claimed local model of $P_{p}$ w.r.t. to
$\mathcal{W}_{p}$ is greater than that of $P_{q}$ at coordinate $k$ given
$N>3f+2$.

###### Proof.

If $P_{p}$ and $P_{q}$ are both benign, the above argument trivially holds.
Then we prove by contradiction to show that the Byzantine adversary cannot
forge the result. Assume $w^{k}_{p}>w^{k}_{q}$ is true, and a benign
participant receives a wrong relationship $w^{k}_{p}<w^{k}_{q}$ for more than
$f$ times. Recall that there are at most $f$ faulty participants, so there is
at least one benign participant that also broadcast $w^{k}_{p}<w^{k}_{q}$,
which contradicts Lemma 1. ∎

We next prove the liveness property of Brave, i.e., Brave allows the benign
participants to accept the true relationships between their local models,
regardless of the adversaries’ behaviors during training.

######  Proposition 2 (Liveness).

Suppose $P_{p}$ and $P_{q}$ are benign participants and assume w.l.o.g.
$w^{k}_{p}>w^{k}_{q}$. If $N>3f+2$ holds, then Algorithm 2 will guarantee that
$w^{k}_{p}>w^{k}_{q}$ is accepted by all benign participants.

###### Proof.

Since $P_{p}$ and $P_{q}$ are benign, they will follow the protocol and send
$m_{pq}$ and $m_{pq}$ that can be authenticated to other participants. As
$N>3f+2$, apart from $P_{p}$ and $P_{q}$, there are at least $(N-2)-f>2f$
benign nodes that will respond with $w^{k}_{p}>w^{k}_{q}$. Therefore, all
benign participants would receive more than $2f$ times $w^{k}_{p}>w^{k}_{q}$
and accept $w^{k}_{p}>w^{k}_{q}$. ∎

Given the aforementioned guarantees provided by Brave, we show that the benign
$P_{i}$ and $P_{j}$ can reach an agreement on relationship $\bowtie$ during
Stage 2.

######  Proposition 3 (Agreement on Pairwise Relationships).

The accepted relationships of all benign participants are identical given
$N>3f+2$.

###### Proof.

This property is guaranteed by the BFT broadcast given $N>3f$, as shown in
Lemma 4. ∎

With Proposition 1 and 3, we can now conclude that the relationships among
benign participants are correct and identical. Therefore, an agreement on
sorting can be reached.

######  Corollary 1 (Agreement on Sorting).

Given any benign participants $P_{i}$ and $P_{j}$, if $N>3f+2$ holds, then
Brave guarantees the sorting results $\mathcal{S}^{k}_{i}=\mathcal{S}^{k}_{j}$
for all $k$, i.e., the sorting of all benign participants is identical.

Based on Corollary 1, we show that Brave guarantees all benign participants to
obtain an identical global model $w$.

######  Proposition 4 (Agreement on Global Model).

The global model $w$ of all benign participants is identical given $N>3f+2$.

###### Proof.

Given Corollary 1 and Lemma 4, $\mathcal{S}_{i}^{k}=\mathcal{S}_{j}^{k}$,
$\bar{w}_{i}^{k}=\bar{w}_{j}^{k}$, and $\bar{r}_{i}^{k}=\bar{r}_{j}^{k}$ for
all benign participants $P_{i}$ and $P_{j}$. Thus $\bar{w}^{k}$ calculated in
Line 16 is identical among benign participants, leading to identical
verification result in Line 18 of Algorithm 4. Therefore, the global model $w$
is also identical. ∎

We conclude this section by proving that the global model obtained by the
benign participants deviates from the optimal one by a bounded distance, i.e.,
satisfies $\epsilon$-convergence property.

######  Theorem 5.

Assume that local model $w_{i}(t)$ belongs to a bounded set and is $z$-sub-
exponential for all $i$ and $t$. The global model $w(T)$ obtained by applying
Brave to P2P FL satisfies $\|w(T)-w(T)^{*}\|\leq\epsilon$ with probability at
least $\zeta$, where

$\displaystyle\zeta$
$\displaystyle=1-2m\exp\\{-(N-f)\min_{i}|\mathcal{D}_{i}|\min\\{\frac{\tau}{2z},\frac{\tau^{2}}{2z^{2}}\\}\\}$
$\displaystyle-2(N-f)m\exp\\{\min_{i}|\mathcal{D}_{i}|\min\\{\frac{\delta}{2z},\frac{\delta^{2}}{2z^{2}}\\}\\},$

$\epsilon=\sqrt{m}\frac{\tau+3f\delta/N}{1-2f/N}$, and $w(T)^{*}$ is the
optimal global model obtained using Eqn. (1) and (2) when P2P FL terminates at
iteration $T$.

###### Proof.

Using Corollary 1, we have that benign participants $P_{i}$ and $P_{j}$ own
identical $\mathcal{S}_{i}^{k}=\mathcal{S}_{j}^{k}$ for all benign
participants $i,j$. They further hold identical global model $w(t)$ for all
iteration $t$. Consider an arbitrary benign participant. If $w(T)$ is $z$-sub-
exponential, then using Lemma 3 of (Yin et al. 2018) yields that

$|w(T)^{k}-w(T)^{k^{*}}|\leq\frac{\tau+3f\delta/N}{1-2f/N}$

holds for each coordinate $k$ with probability at least
$1-2\exp\\{-(N-f)\min_{i}|\mathcal{D}_{i}|\min\\{\frac{\tau}{2z},\frac{\tau^{2}}{2z^{2}}\\}\\}-2(N-f)\exp\\{\min_{i}|\mathcal{D}_{i}|\min\\{\frac{\delta}{2z},\frac{\delta^{2}}{2z^{2}}\\}\\}$.
By using the definitions of $\|\cdot\|$ and union bound over all coordinate
$k$, we have that

$\|w(T)-w(T)^{*}\|\leq\sqrt{m}\frac{\tau+3f\delta/N}{1-2f/N}$

holds with probability at least $\zeta$ for any $\tau,\delta\geq 0$. ∎