ZK Research Highlights (July 2023)
Again, in this issue, I intentionally excluded huge amount of important works that will appear in Crypto 2023. There will be a special issue to present those works.
Zero Knowledge Virtual Machine step by step
by Tim Dokchitser and Alexandr Bulkin
provide a source of introductory information into building a zero knowledge proof system for general computation.
review how to build such a system with a polynomial commitment scheme, and how to implement a fully functional command set in terms of zero knowledge primitives.
ProtoGalaxy: Efficient ProtoStar-style folding of multiple instances
by Liam Eagen and Ariel Gabizon
Building on ideas from ProtoStar [BC23] we construct a folding scheme where the recursive verifier's ``marginal work'', beyond linearly combining witness commitments, consists only of a logarithmic number of field operations and a constant number of hashes.
performs well when folding multiple instances at one step, in which case the marginal number of verifier field operations per instance becomes constant, assuming constant degree gates.
Foundations of Data Availability Sampling
by Mathias Hall-Andersen and Mark Simkin and Benedikt Wagner
define data availability sampling precisely as a clean cryptographic primitive.
show how data availability sampling relates to erasure codes.
defining a new type of commitment schemes which naturally generalizes vector commitments and polynomial commitments.
analyze existing constructions and prove them secure.
give new constructions which are based on weaker assumptions, computationally more efficient, and do not rely on a trusted setup, at the cost of slightly larger communication complexity.
Oblivious Accumulators
by Foteini Baldimtsi and Ioanna Karantaidou and Srinivasan Raghuraman
define oblivious accumulators, a set commitment with concise membership proofs that hides the elements and the set size from every entity
two properties: element hiding and add-delete indistinguishability.
define almost-oblivious accumulators, that only achieve add-delete unlinkability, hide the elements but not the set size.
give a generic construction of an oblivious accumulator based on key-value commitments (KVC).
show a generic way to construct KVCs from an accumulator and a vector commitment scheme.
give lower bounds on the communication (size of update messages) required for oblivious accumulators and almost-oblivious accumulators.
Private Timestamps and Selective Verification of Notarised Data on a Blockchain
by Enrique Larraia and Owen Vaughan (IEEE IST-Africa 2023)
suggest using on-chain Pedersen commitments and off-chain zero knowledge proofs (ZKP) for designated verifiers to prove the link between the data and the on-chain commitment.
EDEN - a practical, SNARK-friendly combinator VM and ISA
by Logan Allen and Brian Klatt and Philip Quirk and Yaseen Shaikh
Nock is a minimal, homoiconic combinator function, a Turing-complete instruction set that is practical for general computation, and is notable for its use in Urbit.
introduce Eden, an Efficient Dyck Encoding of Nock that serves as a practical, SNARK-friendly combinator function and instruction set architecture.
describe arithmetization techniques and polynomial equations used to represent the Eden ISA in an Interactive Oracle Proof.
present the Eden zkVM, a particular instantiation of Eden as a zk-STARK.
Zombie: Middleboxes that Don’t Snoop
by Collin Zhang and Zachary DeStefano and Arasu Arun and Joseph Bonneau and Paul Grubbs and Michael Walfish
Zombie, the first system built using the Zero-knowledge middleboxes (ZKMB) paradigm.
preprocessing (to move the bulk of proof generation to idle times between requests),
asynchrony (to remove proving and verifying costs from the critical path),
batching (to amortize some of the verification work).
introduces a portfolio of techniques to efficiently encode regular expressions in probabilistic (and zero knowledge) proofs;
to support policies based on regular expressions, such as data loss prevention.
Hash Functions Monolith for ZK Applications: May the Speed of SHA-3 be With You
by Lorenzo Grassi and Dmitry Khovratovich and Reinhard Lüftenegger and Christian Rechberger and Markus Schofnegger and Roman Walch
propose a new 2-to-1 compression function and a SAFE hash function, instantiated by the Monolith permutation.
The permutation is significantly more efficient than its competitors, Reinforced Concrete and Tip5.
instantiate the lookup tables as functions defined over F2 while ensuring that the outputs are still elements in Fp.
performance comparable to SHA3-256
XHash8 and XHash12: Efficient STARK-friendly Hash Functions
by Tomer Ashur and Al Kindi and Mohammad Mahzoun
propose two new Arithmetization-Oriented(AO) hash functions, XHash8 and XHash12 which are designed based on improving the bottlenecks in RPO [ePrint 2022/1577].
XHash8 performs ≈2.75 times faster than RPO, and XHash12 performs ≈2 times faster than RPO
inheriting the security and robustness of the Marvellous design strategy.
Implementation and performance of a RLWE-based commitment scheme and ZKPoK for its linear and multiplicative relations
by Ramiro Martínez and Paz Morillo and Sergi Rovira
provide the implementation details and performance analysis of the lattice-based post-quantum commitment scheme introduced by Martínez and Morillo in their work titled «RLWE-Based Zero-Knowledge Proofs for Linear and Multiplicative Relations»
obtain tight conditions that allow us to find the best sets of parameters for actual instantiations of the commitment scheme and its companion ZKPoK.
very flexible and its parameters can be adjusted to obtain a trade-off between speed and memory usage
further extends the literature of exact Zero-Knowledge proofs, providing ZKPoK of committed elements without any soundness slack.
Automated Analysis of Halo2 Circuits
by Fatemeh Heidari Soureshjani and Mathias Hall-Andersen and MohammadMahdi Jahanara and Jeffrey Kam and Jan Gorzny and Mohsen Ahmadvand; Satisfiability Modulo Theories 2023 (SMT 2023)
describe methods for checking Halo2.
use abstract interpretation and an SMT solver to check various properties of Halo2 circuits.
abstract interpretation can detect unused gates, unconstrained cells, and unused columns.
SMT solver can detect under-constrained (in the sense that for the same public input they have two efficiently computable satisfying assignments) circuits.
ZK-for-Z2K: MPC-in-the-Head Zero-Knowledge Proofs
by Lennart Braun and Cyprien Delpech de Saint Guilhem and Robin Jadoul and Emmanuela Orsini and Nigel P. Smart and Titouan Tanguy
extend the MPC-in-the-head framework, used in recent efficient zero-knowledge protocols, to work over the ring which is the primary operating domain for modern CPUs.
explore various batching methodologies, leveraging Shamir's secret sharing schemes and Galois ring extensions, and show the applicability of our approach in RAM program verification.
analyse different options for instantiating the resulting ZK scheme over rings and compare their communication costs.
IOPs with Inverse Polynomial Soundness Error
by Gal Arnon and Alessandro Chiesa and Eylon Yogev , FOCS 2023
show that every language in NP has an Interactive Oracle Proof (IOP) with inverse polynomial soundness error and small query complexity.
Efficient Arguments and Proofs for Batch Arithmetic Circuit Satisfiability
by Jieyi Long
for the batch satisfiability problem, provide a construction of succinct interactive argument of knowledge for generic log-space uniform circuits based on the bilinear pairing and common reference string assumption.
For the evaluation problem, construct statistically sound interactive proofs for various special yet highly important types of circuits, including linear circuits, and circuits representing sum of polynomials.
describe protocols optimized specifically for batch FFT and batch matrix multiplication which achieve desirable properties, including lower prover time and better composability.
How to Compile Polynomial IOP into Simulation-Extractable SNARKs: A Modular Approach
by Markulf Kohlweiss and Mahak Pancholi and Akira Takahashi
Most SNARKs are initially only proven knowledge sound (KS). show that the commonly employed compilation strategy from polynomial interactive oracle proofs (PIOP) via polynomial commitments to knowledge sound SNARKS actually also achieves other desirable properties:
weak unique response (WUR)
and trapdoorless zero-knowledge (TLZK);
and that together they imply simulation extractability (SIM-EXT).
The factoring of SIM-EXT into KS + WUR + TLZK is becoming a cornerstone of the analysis of non-malleable SNARK systems.
Fiat-Shamir Security of FRI and Related SNARKs
by Alexander R. Block and Albert Garreta and Jonathan Katz and Justin Thaler and Pratyush Ranjan Tiwari and Michał Zając
prove the FS security of the FRI and batched FRI protocols;
by analyzing the round-by-round (RBR) soundness and RBR knowledge soundness of FRI.
analyze a general class of protocols, which we call \delta-correlated, that use low-degree proximity testing as a subroutine (this includes many "Plonk-like" protocols (e.g., Plonky2 and Redshift), ethSTARK, RISC Zero, etc.);
prove that if a \delta-correlated protocol is RBR (knowledge) sound under the assumption that adversaries always send low-degree polynomials, then it is RBR (knowledge) sound in general.
prove FS security of the aforementioned "Plonk-like" protocols
Bulletproofs With Stochastic Equation Sets
by Michael Brand and Benoit Poletti
present a protocol extending the standard Bulletproof protocol, allowing the Verifier to choose the set of equations after the Prover has already committed to portions of the solution.
Verifier-chosen (or stochastically-chosen) equation sets can be used to design smaller equation sets with less variables that are orders of magnitude faster both in proof generation and in proof verification, and even reduce the size
On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity
by Yanyi Liu and Rafael Pass
present the first “OWF-complete” promise problem---a promise problem whose worst-case hardness w.r.t. BPP (resp. P/poly) is equivalent to the existence of OWFs secure against PPT (resp. nuPPT) algorithms. The problem is a variant of the Minimum Time-bounded Kolmogorov Complexity problem.
Intmax2: A ZK-rollup with Minimal Onchain Data and Computation Costs Featuring Decentralized Aggregators
by Erik Rybakken and Leona Hioki and Mario Yaksetig
present a novel stateless ZK-rollup protocol with client-side validation called Intmax2. all of the data availability and computational costs are shifted to the client-side.
ARITHMETIZATION-ORIENTED APN FUNCTIONS
by Lilya Budaghyan and Mohit Pal
investigate arithmetization-oriented APN functions, APN permutations in the CCZ-classes of known families of APN power functions over prime field Fp.
present a new class of APN binomials over Fq obtained by modifying the planar function x^2 over Fq.
present a class of binomials having differential uniformity at most 5 defined via the quadratic character over finite fields of odd characteristic.
Two Shuffles Make a RAM: Improved Constant Overhead Zero Knowledge RAM
by Yibin Yang and David Heath
optimize arithmetic-circuit-based read/write memory uses only 4 input gates and 6 multiplication gates per memory access.
implemented our memory in the context of ZK proofs based on vector oblivious linear evaluation (VOLE)
AfricaCrypt 2023
MinRank in the Head: Short Signatures from Zero-Knowledge Proofs
by Gora Adj, Luis Rivera-Zamarripa and Javier Verbel
introduces the first MinRank-based digital signature scheme that uses the MPC-in-the-head, enabling it to achieve small signature sizes and running times.
Impossibilities in Succinct Arguments: Black-box Extraction and More
by Matteo Campanelli, Chaya Ganesh, Hamidreza Khoshakhlagh and Janno Siim
formalizing a folklore lower bound for the proof size of black-box extractable arguments based on the hardness of the language. This separates knowledge-sound SNARGs (SNARKs) in the random oracle model (that can have black-box extraction) and those in the standard model.
Under the existence of non-adaptively sound SNARGs (without extractability) and from standard assumptions, it is possible to build SNARKs with black-box extractability for a non-trivial subset of NP.
show that (under some mild assumptions) all NP languages cannot have SNARKs with black-box extractability even in the non-adaptive setting.
The Gentry-Wichs result does not account for the preprocessing model, under which fall several efficient constructions.
Poseidon2: A Faster Version of the Poseidon Hash Function
by Lorenzo Grassi, Dmitry Khovratovich and Markus Schofnegger
propose an optimized version of Poseidon, called Poseidon2.
Poseidon is a sponge hash function, while Poseidon2 can be either a sponge or a compression function depending on the use case.
Poseidon2 is instantiated by new and more efficient linear layers with respect to Poseidon.