Scaling up Trustless DNN Inference with Zero-Knowledge Proofs

1. Instead of an innovative work, this work looks more like an incremental work on secure ML with ZK-SNARKs, where applies some specific engineering tricks on MobileNet.
2. Although authors mention the Halo 2 is a general-purpose system, this work only focuses on the empirical results on image tasks.

1. The writing is rather rough and there are many terms/statements that are unclear to me (please refer to Questions).
2. The contribution of this paper is unclear to me. It seems like the original ZK-SNARK (and its variants) is infeasible for deep NNs like MobileNet over large-scale datasets (Imagenet) but the authors didn’t explain the reason. The authors should highlight the difficulties when verifying MobileNet/Imagenet with ZK-SNARKs and how this paper solves these issues so that the contributions of this paper will be clearer.
3. The proposed adaptions to MobileNet only support 6 basic conv components, while more advanced techniques (e.g., attention mechanism) seem inapplicable. I believe this limits the deployments in the real world.

(1) Novelty is limited. Firstly, the introduction of halo2 [a] and Plonkish [b] intermediate representation in section 3 is not the contribution of this paper. Secondly, the quantization method in section 4.1 is largely based on existing quantization methods[c], [f]. Thirdly, any method that achieves verifiable machine learning can be applied to the application scenarios in section 5.

(2) Critical inconsistency. There are multiple references to the performance of the proposed method that are inconsistent. For example, in the abstract, the authors mention “achieving 79% top-5 accuracy, with verification taking as little as one second”; in the introduction, it becomes “MobileNet v2 achieving 79% accuracy while simultaneously being verifiable in 10 seconds”. However, in the experiment part, in Table 1, the verification time for the model with 79% accuracy is reported as 3.23s. Such inconsistency weakens the contribution of this paper and makes it less reliable.

(3) Wrong or unsupported technical statements. The paper offers technical claims that are inaccurate, weakening its overall contribution. It is not true that [d], [e] are based on interactive protocols or sum-check protocols. They are based on Groth16 [h], which is a non-interactive protocol.

(4) Lack of evidence. (i)Top-1 accuracy should be reported. (ii)There should also be a comparison with respect to accuracy, verification time, and proving time with baseline methods. (iii)There is no evidence to support the claim “Our choice of lower precision values of a and b results in a slight accuracy drop but dramatic improvements in prover and verifier performance” in section 4.1.

(5) More comparison and contrast with the existing works are needed. For example, the method in [f] already scales to VGG16, which typically has 138M parameters, while the MobileNet V2 this paper focuses on typically has 3.5M parameters. More comparison with prior works is needed, with respect to the nature of the underlying cryptographic protocol such as interactivity, the proving time, and verification time.

(6) Justification for the choice of model is needed. There should be a reason why MobileNet V2 is studied instead of the commonly used VGG16 or ResNet18. Is MobileNet V2 more suitable for cloud computing? The top-5 accuracy from 59.1%~79.2% seems much impractical for real applications.

(7) Some terms are not well defined. For example, in section 3, AIR is not defined. AIR stands for Arithmetic Intermediate Representation in the context of zero-knowledge proof.

(8) Verification time is longer than the inference time. In Table 1, it takes 3.23s for a user to verify the correctness of the model with 79% accuracy, which is longer than the inference time. In the field of verifiable computation, the client’s verification effort is expected to be lower than performing the computation locally [g].

[a]zcash. halo2, 2022. URL https://zcash.github.io/halo2/.

[b] Ariel Gabizon, Zachary J Williamson, and Oana Ciobotaru. 2019. Plonk: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive (2019).

[c] Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko. 2017. Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference. arXiv:1712.05877 [cs.LG] [d] LEE, S., KO, H., KIM, J., AND OH, H. vcnn: Verifiable convolutional neural network based on zk-snarks. Cryptology ePrint Archive (2020).

[e] WENG, J., WENG, J., TANG, G., YANG, A., LI, M., AND LIU, J.-N. pvcnn: Privacy-preserving and verifiable convolutional neural network testing. IEEE Transactions on Information Forensics and Security 18 (2023), 2218–2233.

[f] LIU, T., XIE, X., AND ZHANG, Y. Zkcnn: Zero knowledge proofs for convolutional neural network predictions and accuracy. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security (2021), pp. 2968–2985.

[g] GHODSI, Z., GU, T., AND GARG, S. Safetynets: Verifiable execution of deep neural networks on an untrusted cloud. Advances in Neural Information Processing Systems 30 (2017).

[h] GROTH, J. On the size of pairing-based non-interactive arguments. In Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35 (2016), Springer, pp. 305–326.

$\bullet$ Scalability of the look-up-table-based approach: While the authors claim scalability to ImageNet, they do not report top-1 accuracy. Furthermore, to better evaluate the effectiveness of the proposed method, it is essential to examine its performance on less complex datasets like CIFAR-10/100. In particular, the major concern with the look-up-table-based approach lies in its scalability from the viewpoint of the predictive performance of deeper models (such as ResNet52 and ResNet101) on complex datasets, which is not shown in the paper. Experimental results only with MobileNetV2 (and top-5 accuracy) are not good enough for claiming the scalability on imagenet.

$\bullet$ Space complexity of took-up table: The memory/storage overhead of the look-up table is not shown in the paper. Consequently, it remains unclear how the proposed non-interactive protocols trade off communication bandwidth (which is a crucial factor in interactive protocols such as OT) against memory usage. Additionally, it is not specified whether the verifier or prover is responsible for storing the lookup table (and whether it is feasible to have such memory capacity on the verifier/prover side).

$\bullet$ Timing breakdown for linear and non-linear operations: Given that non-linear computations are a significant bottleneck in trustless verification of machine learning inference using Zero-Knowledge Proofs, it would be insightful to include a timing breakdown (especially the proving and verification time, as shown in Table 1). Such an analysis could highlight the advantages of employing a look-up table-based method.

$\bullet$ The reuse of sub-circuits is not clearly explained in Section 4.

$\bullet$ Minor issues with the writing and relevant literature:

1. The same reference, "Safetynets: Verifiable execution of deep neural networks on an untrusted cloud" by Ghodsi et al., appears twice in the References section.

2. The statements made in the related work section, claiming that Homomorphic Encryption (HE) is impractical and has only been deployed on toy datasets, are inaccurate. For instance, the reference "Cheetah: Lean and fast secure two-party deep neural network inference" by Huang et al. in USENIX Security 2022 demonstrates the practicality of HE in real-world deep neural network inference scenarios.