ZK Insights | 2nd June 2024

Highlights

ZKProof 6 in Berlin (video list)

• Day 1: https://www.youtube.com/playlist?list=PLOEty2U8Y69Uzkd6MthUjWbOxQHzBAtCQ
• Day 2: https://www.youtube.com/playlist?list=PLOEty2U8Y69XR-KVpuDi4mCIOjBtUA-mQ
• Day 3: https://www.youtube.com/playlist?list=PLOEty2U8Y69WTd1ZVXgGCTZim5TCEAB9H

Polyhedra Expander Compiler Collection

The ExpanderCompilerCollection is a component of the Expander proof system. It transforms circuits written in gnark into an intermediate representation (IR) of a layered circuit. This IR can later be used by the Expander prover to generate proofs.

ExpanderCompilerCollection 是 Expander 证明系统的一个组件。它将用 gnark 编写的电路转换为分层电路的中间表示 （IR）。此 IR 稍后可由 Expander 证明器用于生成证明。

• https://github.com/PolyhedraZK/ExpanderCompilerCollection

Lita launches alpha release of Valida zero knowledge virtual machine and C Complier

• https://www.lita.foundation/blog/announcing-litas-valida-c-compiler-zkvm-the-first-step-towards-true-universal-zk

A Zero Knowledge Paradigm: Part 1 - What is a zk-VM?

• https://www.lita.foundation/blog/zero-knowledge-paradigm-zkvm

Current state of SNARKs

A survey of today’s SNARKs landscape.

Alpen Labs Team对当前SNARKs相关方案进行了分类总结，包括三种不同SNARKs方案的区分，sumcheck和GKR的使用，以及BitVM。简短明晰的总结了当前主流方案的发展现状，是不错的入门材料。

• https://www.alpenlabs.io/blog/current-state-of-snarks

Kobi Gurkan: on the risk of circuit-specific setups

• https://x.com/kobigurk/status/1793846260291588312

Nimue: a Fiat-Shamir library

Nimue是arkworks框架下一个实现了Fiat-Shamir相关协议的新库。Nimue的随机性不基于哈希，而是随机预言。它有助于编写多轮公共硬币协议。Nimue建立在SAFE框架之上，能提供生成验证者和证明者的随机硬币的API。

• https://github.com/arkworks-rs/nimue

The first ZKP Verify Code Implementation using Bitcoin Script

Zulu Network team has Open-Sourced the first ZKP Verify Code Implementation using Bitcoin Script, involving mainstream algorithms such as Groth16/FFlonk. This achievement lays the foundation for constructing a decentralized bridge based on BitVM2. It is based on the On Proving Parings paper whch significantly reduces the overall script size.

Zulu Network团队开源了第一个使用Bitcoin Script的ZKP验证代码实现，涉及Groth16/FFlonk等主流算法。这一成果为构建基于BitVM2的去中心化桥奠定了基础。它基于 On Proving Parings 论文，大大减小了整体脚本大小。

• Fflonk verifier script code: https://github.com/BitVM/BitVM/pull/69
• Groth16 verifier script code: https://github.com/zulu-network/BitVM
• Groth16 verifier rust code: https://github.com/zulu-network/bitvm-groth16-verifier

Updates

Plonkish Constraint Systems

As part of the ZKProof standardization effort, the Plonkish Constraint System Working Group is developing a specification, a reference implementation written in Rust, and test vectors for Plonkish arithmetisation.

• https://github.com/zkpstandard/wg-plonkish

On Proving Pairings - Andrija Novakovic

This paper explores efficient ways to prove correctness of elliptic curve pairing relations. First shows that the final exponentiation step of pairing verification can be replaced with a more efficient “residue check,” which can be incorporated into the Miller loop. Then shows how to reduce the cost of the Miller loop by precomputing all the necessary lines, and how this is especially efficient when the second pairing argument is fixed in advance. Instantiateing algorithms and show results for the BN254 curve.

• https://www.youtube.com/watch?v=ddtKDO_GQ5o
• https://eprint.iacr.org/2024/640.pdf

RISC Zero's Zeth Brings Validity Proofs to Optimism’s OP Stack

• https://www.risczero.com/blog/zeth-brings-validity-proofs-to-optimisms-op-stack

Sumcheck over GPU

Ingonyama release the CUDA code of sumcheck protocol.

• https://github.com/ingonyama-zk/icicle/blob/828fc9c006a6470f2d1b4f8ba7788f79473f5589/icicle%2FappUtils%2Fsumcheck%2Fsumcheck.cu#L595

Papers

Resettable Statistical Zero-Knowledge for NP

Showing an equivalence of resettable statistical zero-knowledge arguments for NP and witness encryption schemes for NP.

• https://eprint.iacr.org/2024/806

Zero-knowledge IOPs Approaching Witness Length

Constructing the first ZK-IOPs approaching the witness length for a natural NP problem. More specifically, designs constant-query and constant-round IOPs for 3SAT.

• https://eprint.iacr.org/2024/816

The Brave New World of Global Generic Groups and UC-Secure Zero-Overhead SNARKs

Establishing the UC security of Groth16 without any significant overhead. Providing a general framework for proving protocols secure in the presence of global generic groups, which then applys to Groth16.

• https://eprint.iacr.org/2024/818

zkLLM: Zero Knowledge Proofs for Large Language Models

Standing as the inaugural specialized zero-knowledge proof tailored for LLMs to the best of our knowledge. Presenting tlookup, a parallelized lookup argument designed for non-arithmetic tensor operations in deep learning, offering a solution with no asymptotic overhead. Introducing zkAttn, a specialized zero-knowledge proof crafted for the attention mechanism, carefully balancing considerations of running time, memory usage, and accuracy.

• https://arxiv.org/abs/2404.16109

Multivariate Multi-Polynomial Commitment and its Applications

Introducing and formally define Multivariate Multi-Polynomial (MMP) commitment, a commitment scheme on multiple multivariate polynomials, and illustrate the concept with an efficient construction, which enjoys constant commitment size and logarithmic proof size.

• https://eprint.iacr.org/2024/827

Hamming Weight Proofs of Proximity with One-Sided Error

A wide systematic study of proximity proofs with one-sided error for the Hamming weight problem Ham. Showing proofs of proximity for Ham with one-sided error and sublinear proof length in three models (MA, PCP, IOP).

• https://eprint.iacr.org/2024/832

The Round Complexity of Proofs in the Bounded Quantum Storage Model

• https://eprint.iacr.org/2024/836

Fully Secure MPC and zk-FLIOP Over Rings: New Constructions, Improvements and Extensions

Presenting a new MPC framework to obtain full security, compatible with effectively any ring. The framework works with any linear secret sharing scheme and relies on a new to utilize the machinery of zero-knowledge fully linear interactive oracle proofs (zk-FLIOP) in a black-box way.

• https://eprint.iacr.org/2024/837

Almost optimal succinct arguments for Boolean circuit on RAM

• https://eprint.iacr.org/2024/839

Batching-Efficient RAM using Updatable Lookup Arguments

• https://eprint.iacr.org/2024/840

How (Not) to Simulate PLONK

Constructs a simulator for the patched version of PLONK and prove that it achieves statistical zero knowledge.

• https://eprint.iacr.org/2024/848

Constant-Round Arguments for Batch-Verification and Bounded-Space Computations from One-Way Functions

• https://eprint.iacr.org/2024/850

Simulation-Extractable KZG Polynomial Commitments and Applications to HyperPlonk

• https://eprint.iacr.org/2024/854

Indistinguishability Obfuscation from Bilinear Maps and LPN Variants

Construct an indistinguishability obfuscation (IO) scheme from the sub-exponential hardness of the decisional linear problem on bilinear groups together with two variants of the learning parity with noise (LPN) problem, namely large-field LPN and (binary-field) sparse LPN.

• https://eprint.iacr.org/2024/856

Interests

Why There’s No ZK in Bitcoin: The Missing Pieces

Briefly introduced the significance and current development status of the bitcoin ecosystem of zk technology.

• https://www.youtube.com/live/GrSCZmFuy7U

BitVM: Smarter Bitcoin Contracts

• BitVM 为比特币开启了更加智能的合约功能.

• 使用场景: 目前看来主要是用于 Layer 2 的 Bridge

• 不需要软分叉就能实现 BitVM

• https://www.youtube.com/live/VIg7BjX_lJw?si=djNaeeufQ6Pq0oIl

• https://harryx1x1.fun/2024-05-29/bitvm/

*感谢 Kurt、Xor0v0、Harry、Purple、权 对本期 ZK Insights 的特别贡献！