ZK Research Highlights (May 2023)
An Introduction to Zero-Knowledge Proofs in Blockchains and Economics
by Aleksander Berentsen, Jeremias Lenzi, and Remo Nyffenegger
review article on what ZKPs are and how they improve privacy and efficiency and describe applications for blockchains and other use cases.
Weak Fiat-Shamir Attacks on Modern Proof Systems
by Quang Dao, Jim Miller, Opal Wright and Paul Grubbs (IEEE S&P 2023)
study of F-S in implementations of modern proof systems.
perform a survey of open-source implementations and find 36 weak F-S implementations affecting 12 different proof systems.
For Bulletproofs, Plonk, Spartan, and Wesolowski’s VDF— develop novel knowledge soundness attacks accompanied by rigorous proofs of their efficacy.
discuss possible mitigations and takeaways
Formalizing Soundness Proofs of SNARKs
by Bolton Bailey and Andrew Miller
formal methods on soundness of a widespread class of SNARKs, formalize proofs for six different constructions, including the Groth '16.
written in the Lean 3 theorem proving language
Bounded Verification for Finite-Field-Blasting (In a Compiler for Zero Knowledge Proofs)
by Alex Ozdemir, Riad S. Wahby, Fraser Brown and Clark Barrett
ZKP compiler correctness by partially verifying a field-blasting compiler pass, a pass that translates Boolean and bit-vector logic into equivalent operations in a finite field.
implemented in the CirC ZKP compiler and have proved bounded versions of the corresponding verification conditions.
Study of Arithmetization Methods for STARKs
by Tiago Martins and João Farinha
explores two solutions for arithmetization of computational integrity statements in STARKs the algebraic intermediate representation, AIR, and is preprocessed variant, PAIR.
their soundness implications for Reed-Solomon proximity testing.
deriving the degree bounds for low-degree proximity testing.
reducing the degree bound with multiple selector columns
qualitatively comparing computational demands of the components of both arithmetization methods, particularly their impact on the low-degree extensions.
Arithmetization of predicates into Halo 2 using application specific trace types
by Morgan Thomas
update on the Open Specification Language (OSL) circuit compiler.
OSL is a language based on predicate logic which is amenable to compilation to arithmetic constraint systems. This system provides an alternative to universal zk-VMs and low level ad hoc constructions of arithmetic constraint systems.
ProtoStar: Generic Efficient Accumulation/Folding for Special Sound Protocols
by Benedikt Bünz and Binyi Chen
provide a generic, efficient accumulation (or folding) scheme for any special-sound protocol. The accumulation verifier only performs k+2 elliptic curve multiplications and k+d+O(1) field/hash operations.
ProtoStar is a non-uniform IVC scheme for Plonk that supports high-degree gates and (vector) lookups. The scheme does not require a trusted setup or pairings, and the prover does not need to compute any FFTs.
Non-Interactive Zero-Knowledge from Non-Interactive Batch Arguments
by Jeffrey Champion and David J. Wu (CRYPTO 2023)
leveraging succinctness for zero-knowledge.
show how to combine a batch argument for NP with a local pseudorandom generator and a dual-mode commitment scheme to obtain a NIZK for NP.
Batch Proofs are Statistically Hiding
by Nir Bitansky, Chethan Kamath, Omer Paneth, Ron Rothblum and Prashant Nalini Vasudevan
study the necessary conditions for the existence of batch proofs in these two settings: Statistical Soundness/ Computational Soundness
Non-interactive: the existence of non-interactive BARGs for NP and one-way functions, implies NISZKA for NP, with negligible soundness error, inverse polynomial zero-knowledge error, and non-uniform honest prover.
Benchmarking ZK-Circuits in Circom
by Colin Steidtmann and Sanjay Gollapudi
presenting comprehensive benchmarking results for a range of signature schemes and hash functions implemented in Circom
Poseidon, Pedersen, MiMC, SHA-256, ECDSA, EdDSA, Sparse Merkle Tree, and Keccak-256.
new Circom circuit and a full JavaScript test suite for the Schnorr signature scheme.
Ou: Automating the Parallelization of Zero-Knowledge Protocols
by Yuyang Sang, Ning Luo, Samuel Judson, Ben Chaimberg, Timos Antonopoulos, Xiao Wang, Ruzica Piskac and Zhong Shao (CCS 2023)
A front-end language Ou where users can write proof statements as imperative programs in a familiar syntax;
A compiler architecture Lian and implementation that automatically analyzes the program and compiles it into an optimized IR that can be lifted to a variety of ZKP constructions; and
A cutting algorithm, based on Pseudo-Boolean optimization and Integer Linear Programming, that reorders instructions and then partitions the program into efficiently sized chunks for parallel evaluation and efficient state reconciliation.
Privacy-preserving Attestation for Virtualized Network Infrastructures
by Ghada Arfaoui, Thibaut Jacques, Marc Lacoste, Cristina Onete and Léo Robert
propose a privacy preserving TPM(Trusted Platform Module)-based deep-attestation solution in multi-tenant environments
relies on vector commitments and ZK-SNARKs.
The Referendum Problem in Anonymous Voting for Decentralized Autonomous Organizations
by Artem Grigor, Vincenzo Iovino and Giuseppe Visconti (DLT 2023)
naive approach to run referenda over Ethereum can incur severe security problems.
propose both mitigations and hardness results for achieving voting procedures in which the proofs submitted on-chain are either ZK or succinct.
Lattice-based Commit-Transferrable Signatures and Applications to Anonymous Credentials
by Qiqi Lai, Feng-Hao Liu, Anna Lysyanskaya and Zhedong Wang
propose a new primitive to instantiate signature with protocols, called commit-transferrable signature (CTS).
When combined with a multi-theorem straight-line extractable NIZKPoK, CTS gives a modular approach to construct anonymous credentials.
show efficient instantiations of CTS and the required NIZKPoK from lattices
propose concrete parameters for the CTS, NIZKPoK, and the overall Anonymous Credentials, based on Module-SIS and Ring-LWE.
Curve Trees: Practical and Transparent Zero-Knowledge Accumulators
by Matteo Campanelli, Mathias Hall-Andersen and Simon Holmgaard Kamp (USENIX 2023)
zero-knowledge for set membership allows a user to show knowledge of an element in a large set without leaking the specific element. Zcash Sapling strong trust assumption: an underlying setup that must be generated by a trusted third party.
propose novel, more efficient and fully transparent constructions for accumulators supporting zero-knowledge proofs for set membership. inspired by commit-and-prove techniques to combine shallow Merkle trees and 2-cycles of elliptic curves into a highly practical construction.
basic accumulator construction---dubbed Curve Trees---is completely transparent (does not require a trusted setup) and is based on simple and widely used assumptions (DLOG and Random Oracle Model).
design a simple and concretely efficient anonymous cryptocurrency with full anonymity set, which we dub Vcash. Its transactions can be verified in ≈80ms or ≈5ms when batch-verifying multiple (>100) transactions; transaction sizes are 4KB.
A flexible Snark via the monomial basis
by Steve Thakur
describe a pairing-based SNARK with a universal updateable CRS that can be instantiated with any pairing-friendly curve endowed with a sufficiently large prime scalar field.
use the monomial basis, thus sidestepping the need for large smooth order subgroups in the scalar field. can be instantiated with outer curves to widely used curves such as Ed25519, secp256k1 and BN254.
relies on homomorphic table commitments, which makes them amenable to vector lookups.
Following...