ZK Insights | 15th Sep 2024

Highlights

What Does It Mean To Know?

这是一篇探讨零知识中的知识的含义的博客，ZK-proofs 是加密货币最伟大的进步之一。但是，哲学家对「知识」的研究已有千年历史。在这篇文章中，我将比较哲学家对知识定义的「合理真实信念」理论和 ZK-proofs 所隐含的知识规范。另外，博客还畅想了如果将 ZK-proofs 的知识范围推广到 NP 语言之外，可能带来的新变化。

ZK- proofs are one of crypto's greatest advancements. But "knowledge" has been studied by philosophers for 1000s of years. In this post, I compare the “justified true belief” theory of knowledge with the specification of knowledge implied by ZK-proofs

• https://mirror.xyz/0x62D8aAfD495613C9B2a506Ada695293cc0379ddD/SUpsNOkmou2Y7YH5f8nA06-Lv0tizKAlkuju7O8Yk8Q

Two Vulnerabilities in gnark's Groth16 Proofs

对 Zellic 发现的两个漏洞的分析，这两个漏洞破坏了 gnark 的 Groth16 证明的零知识性和可靠性。

An analysis of two vulnerabilities Zellic discovered that broke zero-knowledge and soundness of gnark’s Groth16 proofs with commitments

• https://www.zellic.io/blog/gnark-bug-groth16-commitments/

Designing high-performance zkVMs 

这是一篇来自 RISC Zero 的博客，介绍了关于高性能零知识虚拟机的设计。主要包括两个部分：

在第 1 部分中，作者对 RISC Zero 的 zkVM 所依赖的证明系统进行概述，并介绍他们在提高 zkVM 性能方面的计划。

在第 2 部分中，作者仔细研究证明系统的每一层，包括与折叠方案、JOLT、Binius 和 Circle STARKs 等创新有关的设计因素。

This article is a deep-dive into proof system design for zkVMs, split into two parts.

In Part 1, we give a high-level overview of the proof system that underlies RISC Zero’s zkVM, and what’s on our horizon for improving zkVM performance.

In Part 2, we’ll take a closer look at each layer of the proof system, touching on design considerations with respect to innovations such as folding schemes, JOLT, Binius, and Circle STARKs.

• https://risczero.com/blog/designing-high-performance-zkVMs

riscMPC

General-purpose multi-party computation from RISC-V assembly.

• https://github.com/fabian1409/risc-mpc

Knot Group Wiki

• https://knot-group.github.io/wiki/introduction/

Meet the Mind: The Brain Behind Shor’s Algorithm

• https://www.youtube.com/watch?v=wnhZPmB8KLg

Introducing zkDL++

Ingonyama 提出的证明任何深度神经网络完整性的前沿框架。演示：为 @AIatMetaStable 签名提取可证明的水印

A cutting-edge framework for proving the integrity of any deep neural network.

Demo: Provable Watermark Extraction for @AIatMetaStable Signature

• https://hackmd.io/@Ingonyama/zkdl_plus_plus

Provable Watermark Extraction

zkDL++ is a novel framework designed for provable AI. Leveraging zkDL++, we address a key challenge in generative AI watermarking: Maintaining privacy while ensuring provability. By enhancing the watermarking system developed by Meta, zkDL++ solves the problem of needing to keep watermark extractors private to avoid attacks, offering a more secure solution. Beyond watermarking, zkDL++ proves the integrity of any deep neural network (DNN) with high efficiency.

• https://medium.com/@ingonyama/provable-watermark-extraction-e8ef9ee47f25

Updates

Yuval Ishai: Dot-Product Proofs

A dot-product proof is a simple probabilistic proof system in which the verifier decides whether to accept an input vector based on a single linear combination of the entries of the input and a proof vector. I will present constructions of linear-size dot-product proofs for circuit satisfiability and discuss two kinds of applications: exponential-time hardness of approximation of MAX-LIN from ETH, and minimizing verification complexity of succinct arguments.

• https://www.youtube.com/watch?v=RFBjmGgs4Vw

Quang Dao: Non-Interactive Zero-Knowledge from LPN and MQ

We give the first construction of non-interactive zero-knowledge (NIZK) arguments from post-quantum assumptions other than Learning with Errors. In particular, we achieve NIZK under the polynomial hardness of the Learning Parity with Noise (LPN) assumption, and the exponential hardness of solving random under-determined multivariate quadratic equations (MQ). We also construct NIZK satisfying statistical zero-knowledge assuming a new variant of LPN, Dense-Sparse LPN, introduced by Dao and Jain (CRYPTO 2024), together with exponentially-hard MQ.

• https://www.youtube.com/watch?v=Cfxw8NutXjk&t=20s

Polygon Miden Alpha Testnet v4 is Live

• https://polygon.technology/blog/polygon-miden-alpha-testnet-v4-is-live

Papers

【论文速递】SCN`24（零知识证明、承诺）

• https://mp.weixin.qq.com/s/U7kCWo9LWzwGHb0RyDRaLg

ZKFault: Fault attack analysis on zero-knowledge based post-quantum digital signature schemes

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

Code-Based Zero-Knowledge from VOLE-in-the-Head and Their Applications: Simpler, Faster, and Smaller

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

The Black-Box Simulation Barrier Persists in a Fully Quantum World

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

Lego-DLC: batching module for commit-carrying SNARK under Pedersen Engines

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

A Recursive zk-based State Update System

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

New Techniques for Preimage Sampling: Improved NIZKs and More from LWE

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

A Note on Ligero and Logarithmic Randomness

This is a short note which explains how Ligero works in the framework of "succinct proofs and linear algebra" and how we can view it as a beautifully simple protocol for succinct proofs of matrix-vector multiplication!

• https://angeris.github.io/papers/log-randomness.pdf
• https://eprint.iacr.org/2024/1399

Learn

Peter Shor's Lecture Notes for 8.370/18.435 Quantum Computation from Fall 2022

• https://math.mit.edu/~shor/435-LN/

From AIRs to RAPs - how PLONK-style arithmetization works

• https://hackmd.io/@aztec-network/plonk-arithmetiization-air

What is algebraic geometry?

• https://www.youtube.com/watch?v=UAPIGin-R54

Course: Abstract Algebra

Algebra is the language of modern mathematics. This course introduces students to that language through a study of groups, group actions, vector spaces, linear algebra, and the theory of fields. These lectures are from the Harvard Faculty of Arts and Sciences course Mathematics 122, which was offered as an online course at the Extension School.

• https://youtube.com/playlist?list=PLelIK3uylPMGzHBuR3hLMHrYfMqWWsmx5&si=bmLG3Zb0EL18r7N8

Course: Visual Group Theory

This course contains over 40 videos from undergraduate Abstract Algebra course (Math 4120) at Clemson University.

• https://youtube.com/playlist?list=PLwV-9DG53NDxU337smpTwm6sef4x-SCLv&si=no-6Y1x8mHXb7tZB

Course: Abstract Algebra I: Group Theory

• https://youtube.com/playlist?list=PLL0ATV5XYF8AQZuEYPnVwpiFy0jEipqN-&si=1eYLoxMzvneD5Xyn

Course: Exploring Abstract Algebra II

• https://youtube.com/playlist?list=PLL0ATV5XYF8DTGAPKRPtYa4E8rOLcw88y&si=6TklSwuwseBDO6Kq

*感谢 Kurt、Harry、only4sim、miles 对本期 ZK Insights 的特别贡献！