ZENO: A Type-based Optimization Framework for Zero Knowledge Neural Network Inference

Proving you ran a neural network correctly without revealing the input takes hours because the proof system flattens the network into millions of scalar gates — ZENO keeps the tensor shape and the privacy labels around and gets ResNet-50 from an hour and a half down to eleven minutes.

Why this problem is worth solving

The applications are already real. World ID has people prove with an iris image that they are a unique human being, without the image leaving their device — the proof becomes a kind of anonymous passport. In the other direction, a company can prove its model achieves a claimed accuracy on a public dataset without releasing weights it regards as intellectual property. Both rest on a

That generation happens in three sequential steps. First the arithmetic function becomes a circuit, one gate per addition or multiplication. Then circuit computation condenses the circuit into

What people did before, and where it broke

• General zkSNARK frameworks. Arkworks, Bellman, Ginger and others take an arbitrary arithmetic function, or in some cases require you to hand them constraints directly. They are correct and general, and they see nothing above the level of an individual gate.
• Optimise the circuit locally. Most existing optimisation works on individual scalar gates and small local rewrites. That leaves the fundamental structure alone, including the dependency chain that makes the circuit inherently sequential — a parent gate cannot be computed until all its children are.
• Ignore privacy labels and encrypt everything. A naive implementation generates a constraint for every multiplication regardless of whether either operand was ever secret. The paper’s observation is that privacy has a price, and most implementations pay it on operations that did not need it.
• Represent every small value as a full field element. Neural networks work in 8-bit integers; zkSNARK operates in a finite field of around 254 bits. Storing an 8-bit activation as a 254-bit field element wastes both memory and computation, and existing frameworks do exactly that.
• Reuse plaintext neural network optimisations. Fusion is standard in ordinary inference engines, but it transfers badly: fusing ReLU into a convolution is routine in plaintext and impossible here, because a comparison operator costs hundreds of constraints. The goal is also different — plaintext fusion saves memory traffic, whereas here it must save constraint count.
• Prove each image independently. Existing work generates the whole constraint system afresh per image, even though the accuracy-proving use case runs the same network over a hundred images.
• The gap. Every optimisation opportunity here depends on knowing something the compilation step deliberately erases. Nobody had built a path from neural network semantics down to a proof circuit that kept the semantics alive.

How ZENO keeps and uses the type information

The idea

Do not lower until you have taken what you need. The entire paper turns on one observation about compiler design: an assembly-style circuit is an excellent target and a terrible place to optimise, because reconstructing tensor structure by scanning and parsing a flattened gate list costs more than it saves. So ZENO introduces a language layer above the circuit that names the network in terms of layers and carries a zkTensor type — a tensor paired with a privacy label — through every stage of proof generation. Everything else in the paper is a consequence of having that information available at the point where the circuit is built rather than after. Preserving high-level structure through a compiler that ultimately targets arithmetic circuits, instead of lowering early and hoping to recover the shape later, is the same discipline followed by compilers vectorising encrypted arithmetic, covered elsewhere on this site.

Privacy is a cost, so charge for it only where it is owed. The sharpest result in the paper comes from noticing what is free. Multiplying two private scalars costs one constraint; multiplying a public scalar by a private one costs nothing, because the public value can serve as a coefficient in the constraint rather than as a symbolic variable. A dot product of length n with both sides private therefore needs n+1 constraints, while the same dot product with one side public needs exactly one. Most zkSNARK neural network schemes only require one side to be secret — protecting the user’s image against a public model, or protecting the weights against a public dataset — so this asymmetry is the common case, not a corner case. Letting the cost model of a cryptographic scheme drive which program transformations are worth making, rather than treating the crypto as an opaque backend, is the same stance taken by compilers built around the price list of fully homomorphic operations, covered elsewhere on this site.

Exploit the mismatch between what networks need and what the field provides. Two of ZENO’s optimisations are the same trick applied at different levels. A neural network computes on 8-bit values while the proof system operates in a 254-bit field, so most of every field element is empty; knit encoding packs several dot-product results into one element and verifies them with a single equality check, choosing the batch size as the largest that cannot overflow — nine, for 8-bit operands and vectors of length 1024. Similarly, a network computes at tensor level while the circuit format only offered binary gates, so a dot product’s n-1 additions formed a chain four levels deep; a multi-child addition gate collapses them into one, halving the critical path and yielding a provably identical constraint system. Both are about refusing to inherit a representation that was designed for a different shape of problem. The alternative attack on the same bottleneck — leaving the representation alone and throwing hardware at the resulting arithmetic — is covered elsewhere on this site.

Following one dot product through the two representations

The chain is the problem. A parent gate cannot be computed until its children are, so the critical path grows with n, and circuit computation has to process every one of those addition gates individually.

Why it works

• The dominant step changes complexity class. Preserving tensor structure lets the circuit represent a dot product with a multi-child gate → circuit computation drops from quadratic to linear for fully connected, convolution and pooling layers → which is why speedup grows with network size, from 2.4 times on the smallest model to 8.5 times on VGG16.
• Public operands cost nothing, and most operands are public. A public scalar becomes a coefficient rather than a symbolic variable → a dot product with one public side needs 1 constraint instead of n+1 → and since latency is roughly proportional to constraint count, this is the single largest lever.
• Empty bits in the field are free capacity. 8-bit values stored in 254-bit elements waste most of every element → knit encoding packs several results into one and checks them together → cutting equality constraints, which directly reduces the security computation phase.
• Same-layer gates are independent and countable in advance. Gate counts follow directly from layer shapes → the scheduler can identify each layer’s gates without parsing the circuit → giving 6.2 times from parallelism without the overhead of reconstructing structure from a flattened representation.
• The same network over many images shares its constraints. The constraint system describes the computation, not the data → proving 100 images can reuse one system → worth a further 6.5% on top of the already-reduced circuit computation time.

What it costs (trade-offs and scope)

• The headline number belongs to the favourable privacy setting. 8.5 times is for private images with public weights. When both images and weights are private, the end-to-end gain is at most 2.01 times, because the privacy-driven optimisations have nothing to exploit.
• Practical is a relative word. ResNet-50 falls from about 90 minutes to 11 minutes and VGG16 from about 6.6 minutes to 48 seconds — but plaintext VGG16 inference on the same machine takes 4.2 seconds, so proving still costs roughly an order of magnitude more than computing, on top of a substantially larger machine.
• The dramatic speedups are step-level, not end-to-end. Circuit computation improves by 67.7 times on average and up to 315.6 times on individual convolution layers, but end-to-end gains are bounded by the security computation phase, which knit encoding reduces far less dramatically.
• Knit encoding’s safety rests on an overflow bound. It is secure precisely when bit overflow cannot occur, and ZENO picks the batch size from a formula over input bitwidth, field width and vector length. That is a sound argument but it makes correctness dependent on the tool choosing the parameter right.
• The frequency cache is deliberately limited. It caches results only for public operand pairs, specifically to avoid introducing timing side channels — a good instinct, but it also caps the benefit at 1.2 times.
• The models are small research networks. The evaluated accuracies are modest, with the CIFAR variants of LeNet at 55.35% and 63.68%. These are standard benchmarks in this literature, but they are not the networks the motivating applications would use.
• Single CPU, and the cross-framework comparison is partial. Everything runs on one Intel Xeon Gold 5218; GPU acceleration is named as future work. The comparison against Bellman and Ginger required manually porting constraints and covers two fully connected and two convolution layers rather than whole networks.

The evaluation

Check yourself

Sources

The paper is “ZENO: A Type-based Optimization Framework for Zero Knowledge Neural Network Inference” by Boyuan Feng, Zheng Wang, Yuke Wang, Shu Yang and Yufei Ding, published at ASPLOS 2024 Volume 1, pages 450-464, DOI 10.1145/3617232.3624852. The authors were at the University of California, Santa Barbara. An implementation is available at github.com/BoyuanFeng/ZENO.

This explainer is written from the full text, read from the author copy linked from Yuke Wang’s publication page. All figures above come from the paper’s own sections 4 through 7: the constraint counts of n+1 versus 1 for the two privacy settings, the gate counts of 2n-1 versus n+1 and the critical path reduction from four to two, the batch size of nine for 8-bit operands over length-1024 vectors, the latency table giving VGG16 at 398 against 48 seconds and ResNet-50 at 5154 against 680, the plaintext baselines including 4.2 seconds for VGG16, the 2.4 to 8.5 times end-to-end range for public weights and up to 2.01 times for private weights, the 67.7 times average circuit computation speedup with its 8.7, 6.2 and 1.2 times components, the 315.6 times convolution layer maximum, the 6.5% from batch constraint sharing, and the 4.09 and 5.26 times comparisons against Bellman and Ginger. Note that the ACM Digital Library copy is open access but sits behind an automated access check; the author-hosted copy used here is the same camera-ready paper.