ZKP News - 2024-04

Note: The following content was translated into English by AI.

2024.4.30

[Papers]

• 3MI Labs and Ulvetanna collaborate in the paper “Vision Mark-32: ZK-Friendly Hash Function Over Binary Tower Fields,” proposing a special construction over binary tower fields and achieving a fully pipelined FPGA implementation. Experiments show an order-of-magnitude improvement over Poseidon hashing. Note: The paper is also a good primer on binary tower fields. Paper

• Alqahtani et al. propose PBP-LEMs, a privacy-preserving billing protocol for local energy markets, in their paper “Privacy-Preserving Billing for Local Energy Markets.” Note: This is an example of ZKP in a real application scenario. Paper

• Sun et al. introduce zkLLM in “zkLLM: Zero Knowledge Proofs for Large Language Models,” a system that verifies the correctness of LLM outputs using the sumcheck protocol. It produces proofs under 200 kB and can attest to a 1.3B-parameter model within 15 minutes. Paper

• Barthoulot et al. redefine cryptographic accumulators in “Cryptographic Accumulators: New Definitions, Enhanced Security, and Delegatable Proofs,” adding a “privately evaluated unforgeability” property that bolsters security against forgery attacks. Note: Accumulators can replace the widely used Merkle Tree in certain contexts, drawing significant attention. Paper

[Open Source]

• Valida, an open-source zkVM project built on Plonky3, is still in an early phase and has yet to demonstrate clear differentiating strengths. Source | ZK11 Talk

[News]

• Polygon shared new benchmarks showing their FPGA prover for Plonky2 outperforms the CPU version, achieving 40% faster proving at lower cost. Notably, the hardware-optimized SNARK technique “Binius” was not yet enabled in these tests. 𝕏

• Encode Club’s 6-week ZK Bootcamp starts on May 20. Register now.

[Blogs]

• A detailed article on how to implement ZKP on Bitcoin. Note: It concludes that deploying ZKP on Bitcoin remains challenging today. Blog

• A launch post for Ligetron, a zkML framework built on Ligero. For 440 million floating-point instructions and 3 billion integer instructions, the prover runs for roughly 14 hours (50,000 seconds) while the verifier runs for 6.5 hours (22,000 seconds). The resulting proof is about 10 GB in length and peak memory usage. Note: The code has not been open sourced. Blog

2024.4.24

[Papers]

• The OpenZeppelin team highlights a vulnerability in the Fiat-Shamir transform for KZG-based PLONK verifiers in “The Last Challenge Attack: Exploiting a Vulnerable Implementation of the Fiat-Shamir Transform in a KZG-based SNARK.” The issue was disclosed promptly and patched. Paper | Patch Advisory | Attack PoC

• Balbás et al. introduce a modular verifiable computing framework in “Modular Sumcheck Proofs with Applications to Machine Learning and Image Processing,” using the sumcheck protocol to accelerate convolutions in ML workloads. Paper | Code

• Hui et al. present “LLRing: Logarithmic Linkable Ring Signatures with Transparent Setup,” a scheme with logarithmic verification complexity that halves the number of group exponentiations compared to OmniRing and shows promise for inner-product relation proofs. Paper

• Tang et al. analyze the security of ZKP systems in “Zero-Knowledge Proof Vulnerability Analysis and Security Auditing,” cataloging multiple vulnerability classes. Note: Although the writing quality is uneven, the vulnerability taxonomy is informative. Paper

• Pham et al. propose “Sisu: Decentralized Trustless Bridge For Full Ethereum Node,” building on zkBridge techniques to improve proof efficiency for Ethereum full-node signatures. Paper | Circuits

• Ernstberger et al. design zero-knowledge location privacy circuits in “Zero-Knowledge Location Privacy via Accurate Floating Point SNARKs,” allowing users to prove they are inside a region without revealing exact coordinates. The circuits adhere to IEEE 754 floating-point standards (code not open sourced). Paper | Video

[Blogs]

• ZKV releases the latest State of ZK Q1 2024. Past issues

• A deep dive into the compatibility of Verkle proofs and ZKP concludes that, despite theoretical efficiency gains, Verkle implementations have not shown decisive advantages over Merkle proofs in practice. Blog

• A business-focused article argues that leading ZKP projects are vertically integrating from applications, to VMs, to proof markets, aggregation, and settlement layers. Blog

[Open Source]

• Sonobe is an experimental arithmetic circuit folding library co-developed by 0xPARC and PSE. It currently supports Nova and CycleFold, with HyperNova and ProtoGalaxy under development, and offers front-end tooling for arkworks and Circom. Code

[Info]

• A curated list of ZK-related Twitter accounts: 𝕏

[News]

• Lagrange launched the “Euclid” public testnet featuring a ZKP coprocessor and verifiable database. 𝕏 | Blog

2024.4.17

[Papers]

• Kemmoe et al. publish “RSA-Based Dynamic Accumulator without Hashing into Primes,” optimizing dynamic accumulators that rely on RSA moduli rather than prime inputs. Note: Traditional RSA accumulators require prime elements, making them expensive. Removing that requirement greatly improves performance. This paper extends the non-prime RSA accumulator from Boneh et al. with additional operations and proofs. Accumulators excel at membership proofs, a common ZKP use case. Paper

• Zhu et al. introduce “Elastic MSM: A Fast, Elastic and Modular Preprocessing Technique for Multi-Scalar Multiplication Algorithm on GPUs,” describing GPU preprocessing that boosts MSM performance and potentially accelerates ZKP systems. Paper

• Bottazzi from the Ethereum Foundation presents “Greco: Fast Zero-Knowledge Proofs for Valid FHE RLWE Ciphertexts Formation,” which uses ZKP to enhance the security and efficiency of multi-party FHE applications, such as proving the validity of encrypted ballots in anonymous voting. Paper | Code

• Yuan et al. revisit Fiat-Shamir signature security under quantum superposition attacks in “Revisiting the Security of Fiat-Shamir Signature Schemes under Superposition Attacks,” detailing how to maintain security for deterministic FS signatures in quantum settings. Note: The FS transform underpins FS signatures and most modern non-interactive ZKPs. Paper

• Erfurth proposes a new digital signature scheme for compressed JPEG images in “Digital Signatures for Authenticating Compressed JPEG Images,” ensuring signatures remain valid even after compression. Note: Proving the authenticity of images is increasingly important in the AI era. Paper

• Satriawan et al. offer “A Complete Beginner Guide to the Number Theoretic Transform (NTT),” covering NTT fundamentals, linear/circular/negacyclic convolutions, and practical examples. Note: NTT is a foundational algorithm for many ZKP systems. Paper

• Sun et al. examine pairing optimizations for isogeny-based cryptosystems in “Pairing Optimizations for Isogeny-based Cryptosystems,” addressing efficiency concerns in that post-quantum domain. Paper

[Open Source]

• Lurk Lab releases Yatima, a Lean 4 compiler backend compiled through the Lurk kernel to produce ZKPs for Lean 4 execution and type checking. Note: Lean 4, a functional language for formal proofs, aims to guarantee correctness through formal verification. 𝕏 | Code

• RISC Zero outlines its roadmap toward zkVM 1.0 in four stages: (1) trusted setup ceremony, (2) audits and bug bounties, (3) mainnet validators, and (4) the zkVM 1.0 release. 𝕏 | Code

[Info]

• Antalpha Lab published a series of recent offline workshop recordings (Mandarin) covering IVC, KZG, PCD, lookup tables, and more. Link

• Ingonyama uploaded talks from ZK Accelerate, including sessions on hardware acceleration, Marlin, Miden, and more. Link

• Scroll reportedly spends 2.4 ETH per hour to achieve aggressive one-minute finality (based on full-month data from February). Data

2024.4.10

[Papers]

• Robert presents a new algorithm in “Fast pairings via biextensions and cubical arithmetic,” substantially improving pairing computations over existing methods like Miller’s algorithm. It unifies and extends several pairing techniques and accelerates pairings on specific elliptic curves. This offers theoretical foundations for higher verifier efficiency in systems like GROTH16. Paper

• Victor Shoup analyzes Schnorr signatures in “The many faces of Schnorr,” tightening security bounds and informing future threshold signature designs. Highly relevant for upcoming threshold signature protocols. Paper

• Saah et al. propose a trusted-setup-free commitment scheme based on supersingular isogenies in “Avoiding Trusted Setup in Isogeny-based Commitments,” advancing post-quantum cryptography. Paper

• Karl et al. study hardware acceleration of SPHINCS+ in “The Impact of Hash Primitives and Communication Overhead for Hardware-Accelerated SPHINCS+,” showing that hardware accelerators significantly improve performance, especially when outfitted with FIFOs to address data transfer bottlenecks. Paper

• Alessandro Chiesa (co-author of Marlin) explores “A Time-Space Tradeoff for the Sumcheck Prover,” presenting a prover algorithm that optimizes both time and memory for sumcheck protocols over multilinear polynomials, with practical performance benefits. Paper | Code

• Sanso et al. publish “Families of prime-order endomorphism-equipped embedded curves on pairing-friendly curves,” outlining parameterized constructions for elliptic curve families (BLS, BN, KSS) equipped with prime-order endomorphisms. Recommended for ZKP scenarios that need efficient elliptic curves. Paper

[Experiments]

• A mobile ZKP performance study showcases benchmarks for anonymity solutions like Anon-Aadhaar on phones, covering throughput and feasibility. Experiment | Code | Demo

[Open Source]

• Polygon Zero’s ZeroBin enables distributed proving for plonky2 proofs through hosted servers. Code

[Blogs]

• The fhEVM team continues evangelizing fully homomorphic EVMs. Their latest article positions fhEVM as offering stronger privacy for complex blockchain use cases, while zkEVM still leads in efficiency and performance. Blog

• Justin Thaler and team claim Jolt significantly outperforms existing systems, running six times faster than RISC Zero and twice as fast as SP1 in early tests. Jolt is a VM built on Lasso. 𝕏 | Blog

  Additional expert discussions under this 𝕏 thread:

  • Integrating Binius with Lasso could drive further speedups. 𝕏

  • Some argue RISC Zero’s lack of precompiles skews comparisons because precompiles target Jolt’s primary bottlenecks. 𝕏

[Challenges]

• Ingonyama announced a new challenge centered on GPU acceleration for the sumcheck protocol. Challenge | 𝕏

[News]

• Polygon zkEVM readied a high-performance RPC node for production, promising 150× faster sync times and 10× less disk usage. 𝕏

[Info]

• A comparative table summarizing features of various zkVM systems. 𝕏

2024.4.3

[Papers]

• The authors of Binius publish “Polylogarithmic Proofs for Multilinears over Binary Towers,” combining binary tower fields with FRI to craft a new polynomial commitment scheme that dramatically shrinks proof sizes. 𝕏 | Paper | Blog

• The draft “Aligned Layer: universal verification layer” envisions a new universal verification layer powered by ZKP, giving developers a decentralized verification network backed by Ethereum security. 𝕏 | Paper

[Open Source]

• QED Protocol releases a PoC demonstrating plonky2 verifying plonky3 proofs. 𝕏 | Code

• ICICLE v1.9.1 introduces ECNTT, columnar NTT processing, MSM precomputation, halves compilation time, and adds Keccak-256/512 support. A Go version is forthcoming. 𝕏 | Blog

[Blogs]

• Pablo Kogan proposes methods to balance privacy and compliance via blacklists/whitelists, traceability, and privacy budgets, exploring new frontiers in encrypted privacy compliance. 𝕏 | Blog

[Events]

• ZK Accelerate takes place in Athens on April 11 (free admission) at the Athens Marriott Hotel, right next to the ZK Summit 11 venue. 𝕏 | Schedule