# ZK Research Highlights (July 2023)

Again, in this issue, I intentionally excludedhugeamount of important works that will appear in Crypto 2023. There will be aspecial issueto 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 entitytwo 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.