Zero-Knowledge-Proof-Based Anomaly Detection: Problem Setting

Table of Links

Abstract and Introduction

Problem Setting

The Proposed Two-Stages Anomaly Detection

Verifiable Anomaly Detection using ZKP

Evaluations

Related Works

Conclusion & References

2 PROBLEM SETTING

In this section we present our threat model along with some preliminaries that we leverage in the proposed anomaly detection mechanism.

2.1 ADVERSARY MODEL

We consider an FL system where some subset of the clients might be malicious, while most of the clients (i.e., more than 50%) are honest. The clients would like to collaboratively train a model, however, malicious clients may conduct attacks to achieve some adversarial goals, including: i) planting a backdoor to misclassify a specific set of samples while minimally impacting the overall performance of the global model, i.e., backdoor attacks (Bagdasaryan et al., 2020b; Wang et al.,

2020); ii) altering the local models to prevent the global model from converging, i.e., Byzantine attacks (Chen et al., 2017; Fang et al., 2020); and iii) randomly submitting contrived models without actual training, i.e., free riders (Wang, 2022). Clients are aware that the FL server may take some defensive measures for their submissions to mitigate potential attacks, and they want to verify the integrity of these defensive measures, to ensure correct operation at the server.

2.2 PRELIMINARIES

Krum. Krum (Blanchard et al., 2017) is a well-known distance-based anomaly detection method in distributed learning that accepts local models that deviate less from the majority based on their pairwise distances. Given that there are f byzantine clients (i.e., malicious clients) among L clients in the FL system, where the server receives L local models as w1, w2, . . . , wL in each training round, Krum selects one of these models, i.e., the one that is the most likely to be benign, as the global model. An optimization of Krum is m-Krum (Blanchard et al., 2017) that selects m local models, instead of one, with the m smallest scores, to compute an average model when aggregating local models. Algorithms for Krum and m-Krum is shown in Algorithm 1.

Three Sigma Rule. The three sigma rule is an empirical rule stating that almost all of the population lies within three standard deviations of the mean in normal distributions. Specifically, in normal distributions N (µ, σ), the percentage of values within one, two, and three standard deviations of the mean are 68%, 95%, and 99.7%, respectively. This rule can be widely applied in real-world applications, since normal distributions are consistent with real-world data distributions (Lyon, 2014), and according to the central limit theorem (Rosenblatt, 1956), when aggregating independent random variables, even if the variables are generated by various distributions, the aggregation tends towards a normal distribution. Further, when the data are not normally distributed, we can transform the distribution to a normal distribution (Aoki, 1950; Osborne, 2010; Sakia, 1992; Weisberg, 2001). The three sigma rule has been used in anomaly detection (Han et al., 2019) since data outside two or three standard deviations of the mean take a very limited proportion; see Figure 2.

Zero-knowledge proofs. Zero-Knowledge Proofs (ZKPs)(Goldwasser et al., 1989) is a proof system that allow a prover to convince a verifier that a function on prover’s secret input (witness) is correctly computed. ZKPs ensures three properties: correctness, soundness, and zero-knowledge. Correctness means that if the prover is honest, then the proof they produce should check out (integrity property). Soundness ensures that a cheating prover will not convince verifier with overwhelming probability. Zero-knowledge guarantees that prover’s winess will be not learned by the verifier (privacy). Due to these properties, ZKP has been widely used in machine learning and blockchain applications (Lee et al., 2020; Feng et al., 2021; Liu et al., 2021; Sasson et al., 2014).