Verifiable Anomaly Detection using Zero-Knowledge Proofs

Table of Links

Abstract and Introduction

Problem Setting

The Proposed Two-Stages Anomaly Detection

Verifiable Anomaly Detection using ZKP

Evaluations

Related Works

Conclusion & References

4 VERIFIABLE ANOMALY DETECTION USING ZKP

There exists various type of ZKP schemes. In this ppaer, we utilize zero-knowledge Succinct Noninteractive Arguments of Knowledge (zkSNARKs) to verify anomaly detection. zkSNARKS offers constant proof size as well as constant verification time regardless of the size of the computation. This property is crucial for applications where verifier’s (client) resource is limited. Details of implementations are deferred to Section B.

ZKP-Compatible Language. The first challenge of applying ZKP protocols is to convert the computation into a ZKP-compatible language. ZKP protocols model computations as arithmetic circuits with addition and multiplication gates over a prime field. However, our computations for anomaly detection are over real numbers. The second challenge is that some computations such as square root are nonlinear, making it difficult to wire them as a circuit. To address these issues, we implement a class of operations that map real numbers to fixed-point numbers. To build our ZKP scheme, we use circom library (Circom Contributors, 2022). which can compile the description of an arithmetic circuit in a front-end language similar to C++ to back-end ZKP protocol.

ZKP for Anomaly Detection. Most of the computations in Algorithm 2 and Algorithm 3 are linear, which can be compiled into an arithmetic circuit easily. For instance, computing cosine similarity between two matrices of size n × n requires a circuit with O(n 2 ) multiplication gates and one division. While it is difficult to directly compute division on a circuit, it can be easily verified with prover providing the pre-computed quotient and remainder beforehand. We can utilize this idea and apply Freivalds’ algorithm (Freivalds, 1977) to verify matrix multiplication.

Matrix multiplication constitutes the basis of the verification schemes used for anomaly detection. Naively verifying a matrix multiplication AB = C where A, B, C are of size n×n requires proving the computation step by step, which requires O(n 3 ) multiplication gates. With Freivalds’ algorithm, the prover first computes the result off-circuit and commits to it. Then, the verifier generates a random vector v of length n, and checks A(Bv) ?= Cv. This approach reduces the size of the circuit to O(n 2 ). We exploit this idea of verifying the computation again to design an efficient protocol for

square-root, which is used in Algorithm 3. To verify that x = √y is computed correctly, we ask the prover to provide the answer x as witness and check in the ZKP is x is indeed the squreroot of y. Note that we cannot check x 2 is equal to y because zkSNARK works over prime field and the square root of an input number might not exist. Therefore, we check if x 2 is close to y by checking that x 2 ≤ y and (x + 1)2 ≥ y. This approach reduces the computation of squareroot to 2 multiplication and 2 comparison.