Zhang Yinuo

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2025-215

December 19, 2025

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2025/EECS-2025-215.pdf

Zero-Knowledge Virtual Machines (zkVMs) enable scalable blockchain computation by allowing off-chain execution with on-chain verification through succinct proofs. A zkVM consists of a frontend, which compiles programs into constraint systems, and a backend, which generates cryptographic proofs that these constraints are satisfied. However, zkVMs remain prohibitively expensive: proof generation can be one million times slower than native execution. Since backend proving time scales linearly with constraint count, efficient frontends that minimize constraints are essential. This dissertation identifies key bottlenecks in zkVM frontends and develops three tech- niques for constraint reduction, organized into two themes. Constraint-Friendly Cryptography. Cryptographic primitives, especially hash func- tions, dominate constraint counts in real zkVM workloads. We develop two complementary strategies. Substitution applies when the application permits flexibility, such as zkVM memory consistency checking: we replace constraint-expensive hashing with a more constraint-friendly alternative under different cryptographic assumptions. Packing applies when the choice of hash function is fixed by external specification (e.g., SHA-3 for Ethereum compatibility). We observe that functions like SHA-2/3 iterate a fixed binary circuit many times, and develop a technique to exploit this repetitive structure, thus amortizing constraint overhead. **Floating-Point Arithmetic. **Emerging applications like zero-knowledge machine learn- ing require floating-point computation, but exact IEEE-754 verification leads to constraint explosion. We propose relaxation: since floating-point arithmetic is inherently approximate, we verify bounded relative error rather than exact rounding. This transforms the problem from bit-level circuit simulation to efficient range proofs, enabling practical zkVM support for ML workloads.

Advisors: Sanjam Garg

---

BibTeX citation:

@phdthesis{Yinuo:EECS-2025-215,
    Author= {Yinuo, Zhang},
    Title= {Constraint-Efficient Techniques for Zero-Knowledge Virtual Machines},
    School= {EECS Department, University of California, Berkeley},
    Year= {2025},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2025/EECS-2025-215.html},
    Number= {UCB/EECS-2025-215},
    Abstract= {Zero-Knowledge Virtual Machines (zkVMs) enable scalable blockchain computation by
allowing off-chain execution with on-chain verification through succinct proofs. A zkVM
consists of a frontend, which compiles programs into constraint systems, and a backend,
which generates cryptographic proofs that these constraints are satisfied. However, zkVMs
remain prohibitively expensive: proof generation can be one million times slower than native
execution. Since backend proving time scales linearly with constraint count, efficient frontends
that minimize constraints are essential.
This dissertation identifies key bottlenecks in zkVM frontends and develops three tech-
niques for constraint reduction, organized into two themes.
**Constraint-Friendly Cryptography.** Cryptographic primitives, especially hash func-
tions, dominate constraint counts in real zkVM workloads. We develop two complementary
strategies. Substitution applies when the application permits flexibility, such as zkVM memory
consistency checking: we replace constraint-expensive hashing with a more constraint-friendly
alternative under different cryptographic assumptions. Packing applies when the choice of
hash function is fixed by external specification (e.g., SHA-3 for Ethereum compatibility). We
observe that functions like SHA-2/3 iterate a fixed binary circuit many times, and develop a
technique to exploit this repetitive structure, thus amortizing constraint overhead.
**Floating-Point Arithmetic. **Emerging applications like zero-knowledge machine learn-
ing require floating-point computation, but exact IEEE-754 verification leads to constraint
explosion. We propose relaxation: since floating-point arithmetic is inherently approximate,
we verify bounded relative error rather than exact rounding. This transforms the problem
from bit-level circuit simulation to efficient range proofs, enabling practical zkVM support
for ML workloads.},
}

EndNote citation:

%0 Thesis
%A Yinuo, Zhang 
%T Constraint-Efficient Techniques for Zero-Knowledge Virtual Machines
%I EECS Department, University of California, Berkeley
%D 2025
%8 December 19
%@ UCB/EECS-2025-215
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2025/EECS-2025-215.html
%F Yinuo:EECS-2025-215