Zero Knowledge Machine Learning
Worldcoin Use-Case
- IrisCode self-custody and upgrade ability.
- Making the Orb trustless, provide proof that fraud filters are applied.
Deep learning networks
layer | output shape | #parameters | #ops
-------------------- | --------------- | --------------- | ---------------
conv 32x5x5x3 | (116, 76, 32) | 2400 | 21158400
max-pool | (58, 38, 32) | 0 | 282112
relu | (58, 38, 32) | 0 | 70528
conv 32x5x5x32 | (54, 34, 32) | 25600 | 47001600
max-pool | (27, 17, 32) | 0 | 58752
relu | (27, 17, 32) | 0 | 14688
flatten | (14688,) | 0 | 0
full 1000x14688 | (1000,) | 14689000 | 14688000
relu | (1000,) | 0 | 1000
full 5x1000 | (5,) | 5005 | 5000
normalize | (5,) | 0 | 6
- Linear operations
- Matrix multiplications: $A ⋅ \vec x$
- Convolutions
- Biases: $\vec x + \vec b$
- Pooling
- Max pooling: $\max_i x_i$
- Sum/Avg pooling: $\sum_i x_i$
- Activation functions:
- ReLU: $\max(0,x)$
- PReLU: $\max(α⋅x,x)$ with $0 ≤ α < 1$
- Logistic: $\p{1 + \mathrm{e}^{-x}}^{-1}$
- Polynomial: $x^2 + x$,
- Argmax: $\argmax_i x_i$
- Softmax: $\mathrm{e}^{x_i}$ and rescaling $\norm{\vec x}_1 = 1$
- Normalize: Rescale such that 2-norm $\norm{\vec x}_2 = 1$.
Relevant ML evaluation work
Generally: lot's of similarities with embedded implementations: use fixed-point to avoid floating point math, model is held constant, can do precompute.
Differences: Fixed-point numbers in ZK can be large (very very large in some proof systems). Simple comparisons are expensive. Can do inverses trivially. (i.e. zk development we are all familiar with).
Prior ZK-ML work
- Justin Thaler (2013). "Time-Optimal Interactive Proofs for Circuit Evaluation" https://eprint.iacr.org/2013/351
- Pengtao Xie, Misha Bilenko, Tom Finley, Ran Gilad-Bachrach, Kristin Lauter, Michael Naehrig (2014). "Crypto-Nets: Neural Networks over Encrypted Data" https://arxiv.org/abs/1412.6181
- Nathan Dowlin, Ran Gilad-Bachrach, Kim Laine, Kristin Lauter, Michael Naehrig, John Wernsing (2016). "CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy" https://www.microsoft.com/en-us/research/publication/cryptonets-applying-neural-networks-to-encrypted-data-with-high-throughput-and-accuracy/
- Zahra Ghodsi, Tianyu Gu, Siddharth Garg (2017). "SafetyNets: Verifiable Execution of Deep Neural Networks on an Untrusted Cloud" https://arxiv.org/abs/1706.10268
- Payman Mohassel and Yupeng Zhang (2017). "SecureML: A System for Scalable Privacy-Preserving Machine Learning" https://eprint.iacr.org/2017/396
- Jian Liu, Mika Juuti, Yao Lu, and N. Asokan (2017). "Oblivious Neural Network Predictions via MiniONN transformations" https://eprint.iacr.org/2017/452
- Seunghwa Lee, Hankyung Ko, Jihye Kim, and Hyunok Oh (2020). "vCNN: Verifiable Convolutional Neural Network based on zk-SNARKs" https://eprint.iacr.org/2020/584
- Ramy E. Ali, Jinhyun So, A. Salman Avestimehr (2020). "On Polynomial Approximations for Privacy-Preserving and Verifiable ReLU Networks" https://arxiv.org/abs/2011.05530
- Boyuan Feng, Lianke Qin, Zhenfei Zhang, Yufei Ding, and Shumo Chu (2021). "ZEN: An Optimizing Compiler for Verifiable, Zero-Knowledge Neural Network Inferences" https://eprint.iacr.org/2021/087
- Tianyi Liu, Xiang Xie, and Yupeng Zhang (2021). "zkCNN: Zero Knowledge Proofs for Convolutional Neural Network Predictions and Accuracy" https://eprint.iacr.org/2021/673
- Chenkai Weng, Kang Yang, Xiang Xie, Jonathan Katz, and Xiao Wang (2021). "Mystique: Efficient Conversions for Zero-Knowledge Proofs with Applications to Machine Learning" https://eprint.iacr.org/2021/730 slides
- Zahra Ghodsi, Tianyu Gu, Siddharth Garg (2017). "SafetyNets: Verifiable Execution of Deep Neural Networks on an Untrusted Cloud" https://arxiv.org/abs/1706.10268
- @liaopeiyuan (2021). "zk-ml/demo" https://github.com/zk-ml/demo
- @socathie (2022). "CircomLib-ML" https://github.com/socathie/circomlib-ml GitCoin Grant Proposal
- @horacepan @sunfishstanford @henripal (2022). "ZK-MNIST" https://github.com/0xZKML/zk-mnist https://0xparc.org/blog/zk-mnist
- @recmo (2022). "proto-neural-zkp" https://github.com/worldcoin/proto-neural-zkp
Fix point
$$ \mathtt{a} = \floor{\frac{a}{2^{32}}} $$
$$ \mathtt{a} ⋅ \mathtt{b} = \floor{\frac{a}{2^{32}}} $$
Strategy ideas
- Results in low level optimized implementation of matrix multiplications and convolutions.
- Recursion around layers. Vectors passed between layers are smallish, so can be committed to.
- Target 16-bit fixpoint so we can use PLookup for Relu.
- dot product without renormalization.
- Flip max-pool and relu 😁
- Clever algorithms to compute convolutions (from simple tricks to FFT based)
- Efficient non-zk convolution algorithms: https://arxiv.org/abs/1903.01521 http://people.ece.umn.edu/users/parhi/SLIDES/chap8.pdf
