# Constraint efficient neural networks
The recent interest in merging zero-knowledge cryptography and machine learning has led to progress at an impressive clip. In April of last year we had projects generating proofs for the final layer of a [small multi-layer perceptron trained on MNIST](https://0xparc.org/blog/zk-mnist), as of May 2023 we're getting entire transformer based models into circuits (see [here](https://hackmd.io/mGwARMgvSeq2nGvQWLL2Ww) and [here](https://github.com/ddkang/zkml)).
We're naturally arriving to a point where we should begin exploring architectures that are "easier" to prove. To quantify this ease of proving I want to introduce a concept or metric I've been calling constraint efficiency. Given $N$ network parameters, what is then the number of constraints $M$ generated within a ZK-circuit.
Obviously $M$ depends on a number of factors, in particular:
- the particular gates and constraints used to represent a neural network layer. Some frameworks will tradeoff a larger number of constraints for greater proving efficiency by way for instance of "accumulated arguments" (see the accumulated dot product argument [here](https://hackmd.io/mGwARMgvSeq2nGvQWLL2Ww) for an example) .
- The architecture of the network. Convolutional layers with large strides will generate less constraints than their fully-connected counterparts.
- The proof system used. Proof systems with lookup arguments might have less constraints than those without.
To help keep this enquiry focused we should instigate explorations where the proof system and the gates used to represent layers are fixed. More formally
> Given a proof system $\mathcal{P}$ and a set of gates $\{g_i\}$ what are architectures that minimize the ratio $\frac{M}{N}$ ?
### Some numbers
In our recent work getting [nanoGPT into Halo2-KZG](https://hackmd.io/mGwARMgvSeq2nGvQWLL2Ww), we noticed that transformers seemed to generate disproportionately larger $\frac{M}{N}$ ratios than we had experienced before. For instance for nanoGPT for an embedding size of 64 we get an $\frac{M}{N}$ ratio of $\approx 64$.
- A 1 million parameter model generates 64 million constraints.
- A 250k parameter model generates 16 million constraints
By contrast a 4-layer convolutional network (with some ReLU peppered troughout) with 3047 parameters generates 13152 constraints, giving us a ratio $\frac{M}{N}$ of $\approx 4$. Quite the difference !
### Current explorations
- [Zero Gravity](https://hackmd.io/@benjaminwilson/zero-gravity) explores the efficiency of weightless neural network in generating ZK-SNARKS.
- [Privacy Scaling Explorations](https://mirror.xyz/privacy-scaling-explorations.eth/K88lOS4XegJGzMoav9K5bLuT9Zhn3Hz2KkhB3ITq-m8) have launched an initiative to research ZK-efficient neural network architectures.
### Call to action
We'd love to see some explorations of efficient architectures for SNARKs. If you're keen to discuss this with me / the EZKL community join us [here](https://t.me/+CoTsgokvJBQ2NWQx).

Disclaimer this a more technical post that requires some prior knowledge of how Halo2 operates, and in particular in how its API is constructed. For background reading we highly recommend the Halo2 book and Halo2 Club.

1/26/2024Though seemingly very different concepts, zero-knowledge machine learning (ZKML), and more broadly zero-knowledge computation can help flesh out and build on-chain games, in some circles referred to as Autonomous Worlds (AW). Though the “privacy” component of ZKML could be interesting for creating new game design affordances, we believe that the verifiability of computation presents a clearer set of tools for on-chain game developers, and we’ve seen most developer and player energy to have been focused on this latter paradigm. Broadly, we’ve seen the flourishing of three principal methods for ZKML game-design that have inklings of popularity with both game designers and players.

11/12/2023Welcome to ezkl

10/13/2023Full disclosure; this post is not about gardening but about implementing ZK versions of machine learning algorithms with botanical nomenclature: decision trees, gradient boosted trees, and random forests. If you’re a keen gardener check this out.

9/15/2023
Published on ** HackMD**

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up