ZKPunk's ZK Insights

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

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!

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

Highlights

quantum punks

我们的主要论点是，量子密码学这一规模虽小但正在不断发展的领域可以：

带来我们无法用经典密码学构建的新密码协议
对更广泛的量子产业起到加速作用更重要的是，我们之外的一小部分人相信，量子技术还有更多我们尚未发现的朋克应用。我们撰写这篇短文的目的，就是要让人们认识到量子技术的可能性，并聚集志同道合者共创未来。 Our main thesis is that a small yet growing field called Quantum Cryptography can:
lead to new cryptographic protocols that we could not build with classical cryptography
be accelerationist for the broader quantum industry

Even more so, a small movement of people beyond us, believe that there could be more cypherpunk applications of quantum technology that we have yet to discover. We wrote this short doc to create awareness of what is possible and to gather like-minded people to build this future.

Glue and coprocessor architectur

Vitalik 关于中央「粘合」组件和协处理器架构介绍的博客。其主要观点是，现代计算越来越多地遵循粘合和协处理器架构：中央「粘合」组件具有高通用性但效率低，负责在一个或多个协处理器组件之间传送数据；协处理器组件具有低通用性但效率高。

https://vitalik.eth.limo/general/2024/09/02/gluecp.html

Preserving Reality: The Crucial Role of Attestation in Anti-FakeAI.

TL;DR:加密技术成为应对这一威胁的主要防御手段，而验证则是确保内容真实性和验证人工参与的重要机制。本文深入探讨了验证，包括其定义、挑战和建议的解决方案。 TL;DR:Cryptography emerges as the primary defense against this threat, with attestation serving as a crucial mechanism to ensure content authenticity and validate human involvement. This article provides an in-depth exploration of attestation, including its definitions, challenges, and proposed solutions.

https://xiangxiecrypto.github.io/2024-08-28-zkAttestation/

Crypto’s AirTag Moment: Unlocking Mass Adoption with Web Proofs

How zkTLS will revolutionize airdrops, incentives, and marketplaces

https://www.nascent.xyz/idea/cryptos-airtag-moment

shinigami

shinigami is a Bitcoin Script library for generic Script VM execution in Cairo, enabling the generation of STARK proofs for Bitcoin Script computation and Bitcoin transaction execution.

Ente

Fully open source, End to End Encrypted alternative to Google Photos and Apple Photos

https://github.com/ente-io/ente

Notes on Extractable Witness Encryption for KZG Commitments and Efficient Laconic OT

https://www.leku.blog/kzg-we/

‘Groups’ Underpin Modern Math. Here’s How They Work.

Quanta Magazine 关于群的发展历史的介绍。整数与三角形的对称性有什么共同点？19 世纪，数学家们发明了群来回答这个问题。 What do the integers have in common with the symmetries of a triangle? In the 19th century, mathematicians invented groups as an answer to this question.

https://www.quantamagazine.org/groups-underpin-modern-math-heres-how-they-work-20240906/

Updates

Opening "packed" univariate polynomials over binary fields.

https://hackmd.io/xooS2jz1S_2VDOK6mtJ_lA?view

Mersenne 31 Polynomial Arithmetic

一个全面而简明的关于如何在 M31 域有效地实现域和多项式运算，特别是在 Circle STARK [UH24] 的背景下的介绍教程。通过探讨与这种域选择相关的优势和挑战，本说明旨在为从业人员提供有效优化其密码系统所需的知识。

https://github.com/ingonyama-zk/papers/blob/main/Mersenne31_polynomial_arithmetic.pdf

ICICLE v3: Going multi-platform

https://medium.com/@ingonyama/icicle-v3-1c9cc2f94402

Verifiable Summit 2024

https://www.youtube.com/watch?v=kw23u5djo2Y

Lurk 0.5 Benchmarks

https://argument.xyz/blog/perf-2024/

Papers

Tightly Secure Non-Interactive BLS Multi-Signatures

https://eprint.iacr.org/2024/1368

Locally Verifiable Distributed SNARGs

https://eprint.iacr.org/2024/1385

Cache Timing Leakages in Zero-Knowledge Protocols

https://eprint.iacr.org/2024/1390

Bandersnatch: a fast elliptic curve built over the BLS12-381 scalar field

本文介绍了在 BLS12-381 标量域上建立的新椭圆曲线 Bandersnatch。该曲线配备了高效的自同态特性，允许使用快速的标量乘法算法。基准测试表明，与具有类似特性的另一条名为 Jubjub 的曲线相比，乘法运算速度提高了 42%，R1CS 形式的电路规模减少了 21%，Plonk 电路减少了 10%。许多依赖于 Jubjub 曲线的零知识证明系统都能从我们的结果中受益。

https://link.springer.com/article/10.1007/s10623-024-01472-0

Learnings

Yet another circle STARK tutorial

https://solutions.chainsafe.io/blog/circle-starks/

Elliptic Curves: Cheat Sheet

椭圆曲线备忘清单，包含了关于椭圆曲线参数，性质和类型的介绍。

https://hackmd.io/@timofey/rJ8HP8Yaj

Developer's Guide to Application-Specific Elliptic Curves

https://taueflambda.dev/posts/app-specific-curves/

Juypter Notebook: Cryptography Fundamental

Bill Buchanan OBE 创建了一个 Juypter Notebook 来演示密码学的一些基础组件是如何运行的。

MIRACL Core

MIRACL Core is an open source library, & includes a wide range of public key encryption methods. It is especially focused on elliptic curve and pairing-friendly methods, but also supports a wide range of encryption methods, including RSA, AES and hashing.

https://asecuritysite.com/miracl/

Highlights

Is Telegram really an encrypted messaging app?

Apropos Pavel Durov’s arrest, cryptographer Matthew Green wrote a short post about whether Telegram is an “encrypted messaging app”. The TL;DR here is that Telegram has an optional end-to-end encryption mode that you have to turn on manually. It only works for individual conversations, not for group chats.

https://blog.cryptographyengineering.com/2024/08/25/telegram-is-not-really-an-encrypted-messaging-app/

Zirgen Circuit Compiler

Zirgen is a compiler for a domain-specific language, also called "zirgen", which creates arithmetic circuits for the RISC Zero proof system.

https://github.com/risc0/zirgen

Signed web pages with SXG

https://vivs.wiki/blog/SXG

How Base 3 Computing Beats Binary

Long explored but infrequently embraced, base 3 computing may yet find a home in cybersecurity.

https://www.quantamagazine.org/how-base-3-computing-beats-binary-20240809/

How Does Math Keep Secrets?

Cryptography is the thread that connects Julius Caesar, World War II and quantum computing, and it now lies under nearly every part of modern life. In this week’s episode, computer scientist Boaz Barak and co-host Janna Levin discuss the past and future of secrecy.

https://www.quantamagazine.org/how-does-math-keep-secrets-20240801/

Updates

A major breakthrough in multiplication over Bitcoin, and in STARK verification on Bitcoin signet

A new algorithm for M31 multiplication reduces multiplication cost by 70%. Unlike STARKs, this new multiplication algorithm (like the previous algorithm) does not require OP_CAT, cementing M31’s status as a Bitcoin-friendly prime, regardless of OP_CAT.

https://github.com/Bitcoin-Wildlife-Sanctuary/bitcoin-circle-stark

plonky3-ccs

A plonky3 to CCS converter.

https://github.com/dmpierre/plonky3-ccs

ZKVMs and Proof Verification with @ZKVProtocol, @RiscZero, @ProjectZKM and @alignedlayer

https://x.com/i/broadcasts/1ynJODXEAPvxR

IACR Crypto 2024 (Videos)

https://www.youtube.com/playlist?list=PLeeS-3Ml-rprqjxP_UcoPRdnj1BmELWfp

Frontiers in Complexity Theory: A Graduate Workshop （Videos）

https://www.youtube.com/playlist?list=PLKVCRT3MRed7d05URwQ9xVFF5qdfHxUxc

ZK Con 2024 : ZK For Consumer Use (Videos)

https://www.youtube.com/playlist?list=PLMl4DDeHR107CCfrRsebFFtPmeOlBFFMP

Papers

ECC’s Achilles’ Heel: Unveiling Weak Keys in Standardized Curves

https://eprint.iacr.org/2024/1321

SoK: Instruction Set Extensions for Cryptographers

https://eprint.iacr.org/2024/1323

On the structure of quaternion rings over ℤ/nℤ

https://arxiv.org/abs/1402.0956v2

Generalized one-way function and its application

https://eprint.iacr.org/2024/1343

Quantum Security of a Compact Multi-Signature

https://eprint.iacr.org/2024/1344

SoK: An Engineer’s Guide to Post-Quantum Cryptography for Embedded Devices

https://eprint.iacr.org/2024/1345

Zero-Knowledge Validation for an Offline Electronic Document Wallet using Bulletproofs

https://eprint.iacr.org/2024/1348

Proximity Gaps in Interleaved Codes

https://eprint.iacr.org/2024/1351

Direct Range Proofs for Paillier Cryptosystem and Their Applications

https://eprint.iacr.org/2024/1355

What Did Come Out of It? Analysis and Improvements of DIDComm Messaging

https://eprint.iacr.org/2024/1361

A Documentation of Ethereum’s PeerDAS

https://eprint.iacr.org/2024/1362

FLIP-and-prove R1CS

https://eprint.iacr.org/2024/1364

Learnings

Foundations and Applications of Zero-Knowledge Proofs

The workshop will cover several topics within this field, including classical results, interactive oracle proofs, proof from symmetric primitives, group and pairing-based proof systems such as ZK-SNARKs, lattice-based proof systems, and real-world applications.

https://www.icms.org.uk/ZeroKnowledgeProofs

Error Correction Zoo

https://errorcorrectionzoo.org/

STARK101-rs

A Rust tutorial for a basic STARK protocol to prove the calculation of a Fibonacci-Square sequence, as designed for StarkWare Sessions, and authored by the StarkWare team.

https://github.com/lambdaclass/STARK101-rs/

ZK Hack Montréal

Polygon - The eSTARK Proving System & Plonky3 : https://www.youtube.com/watch?v=2WjcXZYo7eA&list=PLj80z0cJm8QFGB6AsiAG3EB06L7xr5S1c&index=90
Risc Zero - Boundless On-chain Execution using Proven Off-chain Coprocessing : https://www.youtube.com/watch?v=7M5aKRaGG1Q&list=PLj80z0cJm8QFGB6AsiAG3EB06L7xr5S1c&index=89

Programming ZKPs: From Zero to Hero

This post will show you how to write basic Zero Knowledge Proofs (ZKPs) from scratch.

https://zkintro.com/articles/programming-zkps-from-zero-to-hero

Highlights

https://cryptography101.ca/

Greyhound: Fast Polynomial Commitments from Lattices

A new super fast and compact polynomial commitments from standard lattice assumptions! Greyhound combines the techniques that me and Khanh explored in FMN23 and SLAP with the LaBRADOR proof systems, constructing a super exciting and concretely efficient post quantum PCS, with a blazing fast vectorized AVX-512 implementation included. Just to give some numbers, for degree 2^30 proofs are 53KB and only take 3 minutes to compute!

📚: http://ia.cr/2024/1293
👨‍💻: http://github.com/lattice-dogs/labrador

StarkWare Scholar Summit

https://www.youtube.com/playlist?list=PLcIyXLwiPilWbZbZAl0EACeK86Y5SLspF

Updates

Implementation of the Labrador proof system

This repository contains our implementation of the Labrador proof system together with implementations of the Chihuahua, Dachshund and Greyhound front ends.

https://github.com/lattice-dogs/labrador

Bitcoin Header Validation using Nova

This repo contains circuits for validating Bitcoin headers using Nova. At each step, it allows validating multiple headers.

https://github.com/avras/btc-nova-lc

How we implemented the BN254 Ate pairing in lambdaworks

This post is a companion for implementation, explaining the mathematical theory and algorithms needed to understand the BN254 Ate pairing.

https://blog.lambdaclass.com/how-we-implemented-the-bn254-ate-pairing-in-lambdaworks

ZK Podcast Episode 335: Groth16, IVC and Formal Verification with Nexus

In this week’s episode, Anna chats with Jens Groth and Daniel Marin from Nexus. They catch up on all things Groth16 with the author himself before diving into a variety topics, such as formal verification in the context of ZKPs, the Nexus architecture, the benefits and challenges of building a system from the ground up, folding and IVC plus the properties these offer in a zkVM context and much more.

https://zeroknowledge.fm/335-2/

数学界最重要难题，快要破解了吗？

1859年，数学家黎曼提出了著名的“黎曼猜想”，100多年过去了，还是没有人能证明它，无数数学天才正在一步步向真相推进，现在他们又取得了新进展……

https://www.youtube.com/watch?v=xZ5qWfvEMYA

Noname Code Playground

https://noname-playground.xyz/

Papers

【论文速递】Crypto 2024 （多项式承诺、SNARKs、零知识证明、数据可用性采样、后量子聚合签名）

https://mp.weixin.qq.com/s/6MkzrMh7d1WslmeG-Uxcqg

https://eprint.iacr.org/2024/1289

Raccoon: A Masking-Friendly Signature Proven in the Probing Model

https://eprint.iacr.org/2024/1291

Identity-Based Encryption from Lattices with More Compactness in the Standard Model

https://eprint.iacr.org/2024/1295

Point (de)compression for elliptic curves over highly 2-adic finite fields

https://eprint.iacr.org/2024/1298

Permissionless Verifiable Information Dispersal (Data Availability for Bitcoin Rollups)

https://eprint.iacr.org/2024/1299

Efficient Zero-Knowledge Arguments for Paillier Cryptosystem

https://eprint.iacr.org/2024/1303

Learnings

Cryptography 101 : Kyber and Dilithium

Video lectures for Alfred Menezes's introductory course on Kyber-KEM and the Dilithium signature scheme. These lattice-based cryptographic scheme were standardized by NIST on August 13, 2024.

https://cryptography101.ca/kyber-dilithium/

Cryptography 101: Error-Correcting Codes

This course is an introduction to algebraic methods for devising error-correcting codes. These codes are used, for example, in satellite broadcasts, CD/DVD/Blu-ray players, memory chips, two-dimensional bar codes (including QR codes), and digital video broadcasting. The mathematical ingredients for the course are linear algebra, elementary number theory (integers modulo n and congruences), and abstract algebra (groups, rings, ideals, and finite fields).

https://cryptography101.ca/codes/

Plonk notes (wave 1) by ret2basic.eth

https://web3-security.notion.site/Plonk-notes-wave-1-d46f67abe0554e6ea4cb0eb4e5296bb7

不同的 Interpolation 算法介绍

https://web.ntnu.edu.tw/~algo/Interpolation.html

Highlights

NIST PQC 正式标准发布

Additive NTT (ANTT) by Ingonyama

有限扩展域上的加法 FFT 出现于 20 世纪 80 年代末。我们将加法 FFT 称为加法 NTT (ANTT)，是对加法子群而非乘法子群的求值。有趣的是，它们根本不是傅里叶变换，但它们服从类似 FFT 的递归结构，实现了 $O (n l o g n)$ 复杂度。链接是参考的书籍和 Ingonyama 为 Open-Binius 项目实现的 python 参考代码。

Theory: NTT201 book, chapter 3: https://github.com/ingonyama-zk/papers/blob/main/ntt_201_book.pdf
Reference code, Open-Binius repo: https://github.com/ingonyama-zk/open-binius/tree/main/ref/antt

Fibonacci Air Implementation in Plonky3

This repo implements a Fibonacci sequence generator and prover using the Plonky3 framework.

https://github.com/BrianSeong99/plonky3_fibonacci

Lemma: ZK Theorem Proving

Lemma is a ZK theorem proving framework that enables individuals to post unsolved theorem definitions accompanied by a bounty for anyone that can submit a valid Mathematical proof which solves the theorem. These proofs are validated on chain, and the bounties are trustlessly released to the solver.

https://github.com/asm-nop/lemma

Cryptographic Right Answers: Post Quantum Edition

后量子加密技术（PQC）的前景复杂而充满挑战，新算法和新标准不断涌现，如 Kyber、Dilithium 和 SPHINCS+，它们提供了更高的安全性，可抵御量子攻击。要驾驭这一格局，开发人员应优先使用成熟的加密库，避免定制实现，并专注于混合方案。

The post-quantum cryptography (PQC) landscape is complex and challenging, with new algorithms and standards emerging, such as Kyber, Dilithium, and SPHINCS+, which offer improved security against quantum attacks. To navigate this landscape, developers should prioritize using established cryptographic libraries, avoiding custom implementations, and focusing on hybrid schemes.

https://www.latacora.com/blog/2024/07/29/crypto-right-answers-pq/

Updates

Sparta(0)

Rust implementation of the SuperSpartan IOP

Reproducing and Exploiting ZK Circuit Vulnerabilities by ZKSECURITY

https://www.zksecurity.xyz/blog/posts/zkbugs/

What is a trusted setup and how is it secured? Pairings operations

https://www.youtube.com/watch?v=IDKn2Y9Kkc4

Beginner's Guide to zkSNARKs 3: Math (to get to PLONK) part 1 by PSE

https://www.youtube.com/watch?v=St3Xf9hUKiY

ZK Email 开源了一个基于 zk 电子邮件的通用账户恢复模块，其工作原理：

https://x.com/zkemail/status/1806392215260066055?t=mF_eYX45YdunFbSEJvWT-g&s=19

Papers

Succinct Non-Subsequence Arguments

https://eprint.iacr.org/2024/1264

Safe curves for elliptic-curve cryptography

https://eprint.iacr.org/2024/1265

AES-based CCR Hash with High Security and Its Application to Zero-Knowledge Proofs

https://eprint.iacr.org/2024/1271

A bound on the quantum value of all compiled nonlocal games

https://eprint.iacr.org/2024/1276

Improved Polynomial Division in Cryptography

论文的核心技术贡献是离散傅里叶变换下导数算子和逐点除法的新型共轭表示和组合，能够利用洛必达法则高效计算多项式除法。

https://eprint.iacr.org/2024/1279

Stackproofs: Private proofs of stack and contract execution using Protogalaxy

https://eprint.iacr.org/2024/1281

Basic Lattice Cryptography: The concepts behind Kyber (ML-KEM) and Dilithium (ML-DSA)

https://eprint.iacr.org/2024/1287

VerITAS: Verifying Image Transformations at Scale

VerITAS 使用零知识证明来证明只有某些编辑被应用于签名过的照片，首次实现了为真实大图像（3000 万像素）进行证明。其关键创新在于设计了一个新的证明系统，该系统能够证明对大量见证数据的有效签名。

https://eprint.iacr.org/2024/1066

Hekaton: Horizontally-Scalable zkSNARKs via Proof Aggregation

Hekaton 构造了一个新的「分发-聚合」框架，可以高效处理任意大规模计算。该框架将大型计算分解成小块，在分布式系统中并行证明这些小块，然后将得到的小块证明聚合成一个简洁的证明。实验表明 Hekaton 实现了很强的横向可扩展性（证明时间随着集群中节点数量的增加而线性减少），并且能够快速证明大型计算：它可以在一小时内证明大小为 $2^{35}$ 个门的电路，这比之前的工作快得多。

https://eprint.iacr.org/2024/1208

Learnings

Abstract Algebra Online Course

抽象代数涉及群、环、场和模块。这些抽象结构出现在许多不同的数学分支中，包括几何、数论、拓扑学等。它们甚至出现在量子力学等科学课题中。

Abstract Algebra deals with groups, rings, fields, and modules. These are abstract structures which appear in many different branches of mathematics, including geometry, number theory, topology, and more. They even appear in scientific topics such as quantum mechanics.

https://www.youtube.com/playlist?list=PLi01XoE8jYoi3SgnnGorR_XOW3IcK-TP6

Galois Theory Notes

The author has arXived their Galois theory course notes from 2021-2023, making them publicly available along with other course materials. The author notes that the Galois theory notes have been particularly popular, possibly due to their visually appealing format with color and icons.

https://golem.ph.utexas.edu/category/2024/08/galois_theory.html

Discrete Mathematics: An Open Introduction, 4th edition

https://discrete.openmathbooks.org/dmoi4/frontmatter.html

Essential Coding Theory

https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/web-coding-book.pdf

zkML: Tradeoffs in accuracy vs. proving cost

为了展示 ML 模型准确性与 SNARK 成本之间的权衡，作者使用 EZKL zkML 框架进行了概念验证，目标是强调准确性的微小提高如何可能导致巨大的计算开销，从而鼓励人们在构建需要可验证性的模型时，深思熟虑地考虑这些权衡因素。这篇文章详细介绍了这一过程，包括数据预处理、模型训练和证明生成。

https://np.engineering/posts/zkml-tradeoffs/

Highlights

SBC'24 Live Presentations

A live stream for the Science of Blockchain Conference (SBC) 2024 presentations taking place August 7-9 at Columbia University

https://www.youtube.com/@ic3initiativeforcryptocurr114/streams

0xPARC: Programmable Cryptography (Part 1)

Cryptography is undergoing a generational transition, from special-purpose cryptography to programmable cryptography.

https://0xparc.org/blog/programmable-cryptography-1

SuperSpartan by Hand

The goal of this article is to dive into the techniques behind the SuperSpartan's polynomial IOP, which uses the sum-check protocol to prove CCS instances, by writing the protocol explicitely for a specific example.

https://anoma.net/blog/superspartan-by-hand

HyperNova by Hand

The aim of this article is to unbundle the folding mechanism of the HyperNova protocol by writing it by hand.

https://anoma.net/blog/hypernova-by-hand

A Survey on the Applications of Zero-Knowledge Proofs

Applications of ZK from a practitioner/engineer’s perspective.

https://arxiv.org/pdf/2408.00243

How we created a research fast VM for ZKsync

LambdaClass team makes a deep dive into how the EraVM works and how it differs from the EVM.

https://blog.lambdaclass.com/how-we-created-a-research-fast-vm-for-zksync/

Awesome zero knowledge proofs

A curated list of awesome ZKP resources, libraries, tools and more.

https://github.com/sCrypt-Inc/awesome-zero-knowledge-proofs

The exposition of Additive NTT

A detailed theoretical introduction and Python implementation of Additive NTT

Updates

Nullifier Counter in RISC Zero for apps on top of Rarimo Protocol

https://github.com/distributed-lab/rarimo-issuer-risc0

ZK Summit 11 Folded

文章由 Jack Gilcrest 撰写，详细介绍了 Cursive 团队在 ZK Summit 11 中集成折叠方案（folding schemes）的实际应用和经验。

https://www.cursive.team/blog/zk-summit-folded

SP1 is live

SP1 is now feature-complete and recommended for production use.

https://blog.succinct.xyz/sp1-is-live/

SP1 Benchmarks: 8/6/24

SP1’s new GPU prover achieves state of the art performance, with the cheapest cloud costs vs. alternative zkVMs by up to 10x, across a diverse set of blockchain workloads like light clients and EVM rollups.

https://blog.succinct.xyz/sp1-benchmarks-8-6-24/

A thread about FRI by Paul Gafni

Chatting with peeps at SBC and realized I've made some educational resources about FRI soundness analysis that I never shared widely.

https://x.com/Paul_Gafni/status/1821928815150395689

Papers

Optimizing Big Integer Multiplication on Bitcoin: Introducing w-windowed Approach

https://eprint.iacr.org/2024/1236

Garuda and Pari: Smaller and Faster SNARKs via Equifficient Polynomial Commitments

https://eprint.iacr.org/2024/1245

MSMAC: Accelerating Multi-Scalar Multiplication for Zero-Knowledge Proof

https://eprint.iacr.org/2024/1246

Non-Interactive Zero-Knowledge from LPN and MQ

https://eprint.iacr.org/2024/1254

Concrete Analysis of Schnorr-type Signatures with Aborts

https://eprint.iacr.org/2024/1256

Efficient (Non-)Membership Tree from Multicollision-Resistance with Applications to Zero-Knowledge Proofs

https://eprint.iacr.org/2024/1259

zk-Promises: Making Zero-Knowledge Objects Accept the Call for Banning and Reputation

https://eprint.iacr.org/2024/1260

Highlights

未来科学大奖得主访谈：王小云的数学和密码人生

关于王小云院士，迄今内容最翔实的一篇访谈。

https://mp.weixin.qq.com/s/FWdGRikqBI4tg4SGkdvvnw

New Directions in Property Testing | Richard M. Karp Distinguished Lecture

Property testing algorithms seek to determine whether an unknown massive object has some particular property of interest, or is "far" from having the property, while inspecting only a tiny portion of the object. Recent years have witnessed significant progress on both classic property testing problems and the development of several new property testing problems and frameworks, motivated by connections to machine learning theory and high-dimensional data analysis. In this talk, Rocco Servedio will survey several of these new property testing problems, models, and results.

https://www.youtube.com/watch?v=QBr98n1ba4w

Awesome-ZKP-Security

帝国理工博士 Stefanos Chaliasos 整理的零知识证明安全性研究的博客，播客，披露，审计，访谈，CTF，和谜题，论文，工具列表。

A curated list of awesome ZKP Security resources, papers, tutorials, and tools.

https://github.com/StefanosChaliasos/Awesome-ZKP-Security

An Introduction to Verifiable Computation

可验证的计算的简单介绍，主要从概念和直觉层面介绍了可验证计算的定义，意义，基本组成部分和应用。

Part 1 What is verifiable computation? Part 2 Why should you care about verifiable computation? Part 3 What is a SNARK? Part 4 Conceptual building blocks for SNARKs Part 5 Building verifiable applications

https://hackmd.io/@pgaf/HytIDVAPC

Pinocchio: verifiable computation revisited

在这篇文章中，LambdaClass 介绍了匹诺曹协议背后的主要思想，以及他们使用 Lambdaworks 库的实现。

In this post LambdaClass covered the main ideas behind Pinocchio's protocol and their implementation using Lambdaworks library.

https://blog.lambdaclass.com/pinocchio-verifiable-computation-revisited

Apple Announcing Swift Homomorphic Encryption

苹果公司公布了 Swift 语言实现的同态加密包，并且以 iOS 18 中实现的 Live 来电显示和垃圾邮件拦截服务进行了演示。

https://www.swift.org/blog/announcing-swift-homomorphic-encryption/

Sphinx (A fork of SP1)

Sphinx is an open-source zero-knowledge virtual machine (zkVM) that can prove the execution of RISC-V bytecode, with initial tooling support for programs written in Rust. Additionally, Sphinx aims to support other reduction engines, including the evaluator for the Lurk programming language , which could be extended to other functional languages like JavaScript or Lean.

https://github.com/argumentcomputer/sphinx

Updates

Ingonyama x Starknet Strategic Partnership

Breaking the hashes-proven-per-second world record on Vitalik’s laptop

https://medium.com/@ingonyama/ingonyama-x-starknet-strategic-partnership-af22539d41b2

Irreducible x Polygon Labs

Irreducible 和 Polygon Labs 正在合作为 Polygon 的 ZK rollups 生态系统构建一个生产级、基于 Binius 的 ZK 虚拟机。

Announcing collaboration with Polygon Labs on Binius-based zkVM

https://www.irreducible.com/posts/irreducible-x-polygon-labs-collaboration

LatticeFold is updated

Dan Boneh 和 Binyi Chen 在第 4.3 节中为 CCS 关系添加了优化的折叠方案（感谢 @srinathtv 提出批量求和检查的问题）。还更新了知识证明，以处理 k > 2 时的 k 对 1 格点折叠。

We add an optimized folding scheme for CCS relation in Sect. 4.3 (thanks @srinathtv for bringing up the question of batching sumchecks). We also update our knowledge proof to deal with k-to-1 lattice folding where k > 2.

https://eprint.iacr.org/2024/257.pdf

PSE Project Spotlight Episode 1: Identity Day

The theme of our first episode is Identity featuring PSE projects such as TLSNotary, Semaphore and Anon Aadhaar. In this one-hour session we discuss all things identity and how cryptography enables a more secure and practical use case for it.

https://www.youtube.com/watch?v=M85rQ3_TUPk

From (RISC) Zero to Hero: Advanced ZK Programming for Ethereum with Rami Khalil, RISC Zero

https://www.youtube.com/watch?v=yZiC7CM9l1Y&list=PLcPzhUaCxlCgCvzkkaBWzVuHdBRsTNxj1&index=14

Think Like a Circom Circuit with OxMilica, ZK Educator

https://www.youtube.com/watch?v=aoOkX1hfmcI&list=PLcPzhUaCxlCgCvzkkaBWzVuHdBRsTNxj1&index=16

Unboxing Valida zkVM: Architectural Innovations in Custom ISA zkVM Design

https://www.youtube.com/watch?v=8-xuQC8UO6w

Research Day 2024 (Video Playlist)

https://www.youtube.com/playlist?list=PLrTmn1_Dm_Upsw8BY-1wVyqIDYgS5c51H

Encrypt Brussels 2024 (Video Playlist)

https://www.youtube.com/playlist?list=PLYQnwnLD-Fq2-79KMfSwssQdGwn8zEZPi

Eurocrypt 2024: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions (SLAP)

This blog post is based on the paper “SLAP: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions” presented by Giacomo Fenzi in Zurich at Eurocrypt 2024.

https://www.esat.kuleuven.be/cosic/blog/eurocrypt-2024-succinct-lattice-based-polynomial-commitments-from-standard-assumptions-slap/

Noir v0.31.0 is now live with:

New is_unconstrained logic condition
New set and map BoundedVecs methods
Redefined Noir <> Proving Backend interface

Read more about the new Noir <> Proving Backend workflow from end to end:

https://noir-lang.org/docs/getting_started/hello_noir/

Full changelog:

noir-edwards

Optimized implementation of Twisted Edwards curves.

https://github.com/noir-lang/noir-edwards

pz-web

Compiltion of a few useful phantom-zone applications usable in a browser.

https://github.com/RiverRuby/pz-web

Papers

Mova: folding without committing to error terms and without sumcheck

Mova 以 Nova 的折叠方案为基础，通过在验证器采样的随机点对 $E$ 和 $T$ 的多线性扩展 (MLE) 进行评估，从而避免对 Nova 的所谓误差项 $E$ 和交叉项 $T$ 做出承诺。

Mova, which is based on the Nova folding scheme, manages to avoid committing to Nova's so-called error term $E$ and cross term $T$ by replacing said commitments with evaluations of the Multilinear Extension (MLE) of $E$ and $T$ at a random point sampled by the Verifier.

https://eprint.iacr.org/2024/1220

What Have SNARGs Ever Done for FHE?

Does the SNARG actually add any meaningful security to input privacy? We address this question in this note and give a security definition that meaningfully captures the security of the FHE plus SNARG construction.

https://eprint.iacr.org/2024/1207

Hᴇᴋᴀᴛᴏɴ: Horizontally-Scalable zkSNARKs via Proof Aggregation

我们介绍 Hᴇᴋᴀᴛᴏɴ，它是一种可以高效处理任意大型计算的 zkSNARK。我们通过一个新的 "分发-聚合 "框架来构建 Hᴇᴋᴀᴛᴏɴ，该框架将大型计算分解成小块，在分布式系统中并行证明这些小块，然后将得到的小块证明聚合成一个简洁的证明。这个框架的基础是一种新技术，用于高效处理各块之间共享的数据。

We introduce Hᴇᴋᴀᴛᴏɴ, a zkSNARK that can efficiently handle arbitrarily large computations. We construct Hᴇᴋᴀᴛᴏɴ via a new "distribute-and-aggregate" framework that breaks up large computations into small chunks, proves these chunks in parallel in a distributed system, and then aggregates the resulting chunk proofs into a single succinct proof. Underlying this framework is a new technique for efficiently handling data that is shared between chunks.

https://eprint.iacr.org/2024/1208

Collaborative CP-NIZKs: Modular, Composable Proofs for Distributed Secrets

We present the first, general definition for collaborative commit-and-prove NIZK (CP-NIZK) proofs of knowledge and construct distributed protocols to enable their realization. We implement our protocols for two commonly used NIZKs, Groth16 and Bulletproofs, and evaluate their practicality in a variety of computational settings. Our findings indicate that composability adds only minor overhead, especially for large circuits.

https://eprint.iacr.org/2024/1209

More Optimizations to Sum-Check Proving

We describe an optimization to the sum-check prover that substantially reduces the cost coming from the eq $(w, x)$ factor. Over large prime-order fields, our optimization eliminates roughly $2^{n + 1}$ field multiplications compared to a standard linear-time implementation of the prover, and roughly $2^{n - 1}$ field multiplications when considered on top of Gruen's optimization. These savings are about a $25%$ (respectively $10%$ ) end-to-end prover speedup in common use cases, and potentially even larger when working over binary tower fields.

https://eprint.iacr.org/2024/1210

Efficient Layered Circuit for Verification of SHA3 Merkle Tree

We present an efficient layered circuit design for SHA3-256 Merkle tree verification, suitable for a GKR proof system, that achieves logarithmic verification and proof size.

https://eprint.iacr.org/2024/1212

Foldable, Recursive Proofs of Isogeny Computation with Reduced Time Complexity

We empirically build a system to prove the execution of the circuit computing the isogeny rather than produce a proof of knowledge. This proof can then be used as part of the verifiable folding scheme Nova, which reduces the complexity of an isogeny proof of computation for a chain of $n$ isogenies from $O (n)$ to $O (1)$ by providing at each step a single proof that proves the whole preceding chain.

https://eprint.iacr.org/2024/1219

Benchmarking Attacks on Learning with Errors

To improve our understanding of concrete LWE security, we provide the first benchmarks for LWE secret recovery on standardized parameters, for small and low-weight (sparse) secrets. We evaluate four LWE attacks in these settings to serve as a baseline: the Search-LWE attacks uSVP, SALSA, and Coo & Cruel, and the Decision-LWE attack: Dual Hybrid Meet-in-the-Middle (MitM).

https://eprint.iacr.org/2024/1229

Highlights

Exploring circle STARKs

Latest blog post by VitalikButerin covers Circle STARKs: how they can be implemented, how they're pushing STARK efficiency to the limit, and what’s next (optimizing for better UX and parallelization).

AI achieves silver-medal standard solving International Mathematical Olympiad problems

AlphaProof is a system that trains itself to prove mathematical statements in the formal language Lean. It couples a pre-trained language model with the AlphaZero reinforcement learning algorithm.

https://deepmind.google/discover/blog/ai-solves-imo-problems-at-silver-medal-level/

Schnorr signatures: Everything you wanted to know, but were afraid to ask!

Alin Tomescu 关于 Schnorr 签名的博客，Alin 的博客简洁清晰，具有很好的可读性，不管是初学者还是工程师都能够比较容易的理解协议的关键和数学核心。这篇博客介绍了：1. Schnorr 签名的历史 2. 定义 3. 批量验证技巧 4.（R，s）与（e，s）表示的对比 5. EdDSA 和 Ed25519 6. (错误）实现

https://alinush.github.io/2024/05/31/Schnorr-signatures.html

Our crypto experts answer 10 key questions

https://blog.trailofbits.com/2024/07/25/our-crypto-experts-answer-10-key-questions/

The path to general computation on Bitcoin

By StarkWare the first research paper on STARK over Bitcoin. This paper is the most practical covenant-rollup research ever published.

https://starkware.co/blog/general-computation-on-bitcoin/

Proof Composition Using Zero-Knowledge Virtual Machines: #RunawayZK

@wyatt_benno from @novanet_zkp introduced the concept of #RunawayZK, i.e. how zkVMs, proof composition and Non-Uniform Incremental Verifiable Computation can enable specialized proving schemes.

https://blog.icme.io/proof-composition-with-zkvm-runawayzk/

zkLogin: Send and Receive Crypto as Easily as Email

In @SoorajKSaju's latest writeup, he details how zkLogin makes accessing crypto "as simple as sending an email" – delivering web3 tech with a web2-like user experience.

https://x.com/SoorajKSaju/status/1813552167241822340

What is Entropy?

https://johncarlosbaez.wordpress.com/2024/07/20/what-is-entropy/

Updates

Justin Thaler - Proofs, Arguments, and Zero-Knowledge Study group organized by ZK Hack

https://www.youtube.com/playlist?list=PLTPK8HRi5qmlIBA7TDTO8hBOprAc1FIQv

How to Construct Infinite Sets

jHan 的视频介绍，包括什么是自然数？整数？有理数？有理数？虽然我们可能对这些数和集合有直观的理解，但要真正正式构建这些集合却并不那么容易。为此，我们必须使用集合论的一些公理，并仅使用这些假设，正式描述这些无限集合应该是什么样子。我们将开发集合论中的各种工具，如有序对、关系、排序和等价类，从零开始，从无到有，建立所有的实数。 We will develop various tools in set theory, like ordered pairs, relations, ordering, and equivalence classes, to begin with only zero, and from nothing, build all of the real numbers.

https://www.youtube.com/watch?v=dz7j38sCUkI

They're all SNARKs

zkSecurity 联合创始人 David 关于 SNARK 和 SNARG 以及 zk-SNARK 和 STARK 定义范围的评论，他认为考虑到所有的方案的验证都比直接运行原始计算更快，保留 succinct 给某一类单独方案是没有必要的。 I want to also call STARKs and bulletproofs SNARKs.

https://www.cryptologie.net/article/617/theyre-all-snarks/

Circle STARK notes

https://github.com/0xWOLAND/tinystark/blob/main/notes/circlestark.md

The Zama CoFHE Shop - EthCC 7 (Video Playlist)

https://www.youtube.com/playlist?list=PLbLgyT9GSKyu3EEncYzZYLJhK2a-FEikT

FHE Summit 2024 (Video Playlist)

Keynotes and Panel : https://www.youtube.com/playlist?list=PLeyFSoYRt-Wmp9w8THT64Bg3XOl1ZEw3O
Workshops : https://www.youtube.com/playlist?list=PLeyFSoYRt-WkhEP1hD2ZuxG-ktDoMAK5W

The BLAKE3 Hashing Framework

Internet-Draft submitted! A formal standardized specification is a requirement for certain systems and organizations (for ex., OpenSSL). We hope the IETF crypto working group recognizes the value and adoption of BLAKE3.

https://datatracker.ietf.org/doc/draft-aumasson-blake3/

Solvability of linear systems over finite fields

If you have n equations in n unknowns over a finite field with q elements, how likely is it that the system of equations has a solution?

https://www.johndcook.com/blog/2024/07/22/linear-systems-over-finite-fields/

Starkware’s Stwo prover now can prove 620,000 hashes in a second with Circle STARKs

They measured throughput for proving invocations of the Poseidon2 hash over M31 field on a MacPro M3.

https://x.com/StarkWareLtd/status/1807776563188162562

ZkBoost: Proof Supply Chain Abstraction

Gevulot announced ZkBoost, which can connect all proof networks such as proof marketplaces, prover networks and proof aggregators.

https://blog.gevulot.com/p/zkboost-proof-supply-chain-abstraction?triedRedirect=true

Warlock open-sourced new linear algebra library Noether in Rust.

Noether provides traits and blanket implementations for algebraic structures, from basic ones like magmas to more complex ones like fields. It leans heavily on the basic traits available in std::ops and num_traits.

Zero-Knowledge Learning Path: Introduction.

https://mirror.xyz/0x30677091E2Cbdd871DA9759557CC447DD6fB94Da/8Ot8zYmuatbukPCiupH4leTcReesXFhAi7ddu0jk-jI

Bitcoin Script VM in Cairo

shinigami is a library enabling Bitcoin Script VM execution in Cairo, thus allowing the generation of STARK proofs of generic Bitcoin Script computation. shinigami是一个可以在 Cairo 中执行比特币脚本虚拟机的库，因此可以生成通用比特币脚本计算的STARK证明。

https://github.com/keep-starknet-strange/shinigami

noir_rsa

Optimized Noir library that evaluates RSA signatures.

https://github.com/noir-lang/noir_rsa

Noir React Native starter

A simple template to generate ZK proofs with Noir on mobile using React Native

https://github.com/madztheo/noir-react-native-starter

Introduction of Cysic Network

https://medium.com/@cysic/introduction-of-cysic-network-86d5268e9df3

Papers

【论文速递】USENIX Security '24（密钥交换、零知识证明、安全多方计算、区块链）

https://mp.weixin.qq.com/s/2_St3j-LxSepm1J2DnkOMg

Towards Quantum-Safe Blockchain: Exploration of PQC and Public-key Recovery on Embedded Systems

https://eprint.iacr.org/2024/1178

Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem

https://eprint.iacr.org/2024/1171

AVeCQ: Anonymous Verifiable Crowdsourcing with Worker Qualities

https://eprint.iacr.org/2024/1175

Erebor and Durian: Full Anonymous Ring Signatures from Quaternions and Isogenies

https://eprint.iacr.org/2024/1185

Efficient Implementation of Super-optimal Pairings on Curves with Small Prime Fields at the 192-bit Security Level

https://eprint.iacr.org/2024/1195

Jolt-b: recursion friendly Jolt with basefold commitment

code: https://github.com/cysic-labs/jolt-b
paper: https://eprint.iacr.org/2024/1131

Donate(ERC20) : 0x18226b84677a7a59D0A498d428feE9208105D0F7

Highlights

Pairings for the Rest of Us

文章基于作者从各种公开课程和资料学习的经验，介绍了基于域扩展的椭圆曲线配对的基础概念，重点包括弗罗贝尼乌斯自同态和 Trace 映射，以帮助建立 $G_{1}$ 和 $G_{2}$ 子群，并逐步实现泰特配对。 In this article, we covered the foundational concepts for understanding elliptic curve pairings over field extensions, focusing on the Frobenius endomorphism and the Trace map to identify subgroups $G_{1}$ and $G_{2}$ and implemented the Tate pairing step-by-step.

sigma0-polymath

Polymath: Groth16 Is Not The Limit by Helger Lipmaa 论文中描述的非通用 zk-SNARK 的首次（据我们所知）实现，基于 Rust 和 arkworks。 This is the first (as far as we know) implementation of the non-universal zk-SNARK described in the paper Polymath: Groth16 Is Not The Limit by Helger Lipmaa.

https://github.com/sigma0-xyz/polymath

coCircom: Collaborative Circom

coCircom is a tool for building coSNARKs, a new technology that enables multiple distrusting parties to collaboratively compute a zero-knowledge proof (ZKP). It leverages the existing domain-specific language circom to define arithmetic circuits. With coCircom, all existing circom circuits can be promoted to coSNARKs without any modification to the original circuit. Additionally, coCircom is fully compatible with the Groth16 backend of snarkjs, the native proofing system for circom. Proofs built with coCircom can be verified using snarkjs, and vice versa.

A ZERO-KNOWLEDGE PROOF IS VERIFIED ON BITCOIN FOR THE FIRST TIME IN HISTORY

An open-source collaboration between StarkWare and venture firm L2 Iterative makes history verifying the first validity proof on a Bitcoin testnet

https://bitcoinmagazine.com/technical/a-zero-knowledge-proof-is-verified-on-bitcoin-for-the-first-time-in-history

BIP-327 MuSig2 in Four Applications: Inscription, Bitcoin Restaking, BitVM Co-sign, and Digital Asset Custody

This article introduces the applications of the BIP-327 MuSig2 multi-signature protocol in four of the most trending fields: Inscription, Restaking, BitVM Co-sign, and Digital Asset Custody.

https://blog.bitlayer.org/BIP-327_MuSig2_in_Four_Applications/

‘Sensational’ Proof Delivers New Insights Into Prime Numbers

The proof creates stricter limits on potential exceptions to the famous Riemann hypothesis.

https://www.quantamagazine.org/sensational-proof-delivers-new-insights-into-prime-numbers-20240715/

Geometrized arithmetic and the unity of mathematics

Lectures on philosophy of mathematicians. Speaker: Prof. Colin McLarty (Case Western Reserve University, USA)

https://www.youtube.com/watch?v=-q0lLA5mkbc

Digital Signature Algorithm intuitively

zkMarek 对于数字签名的讲解视频，通过样例出发，简洁明晰的展示了数字签名的工作原理。同时，这是一个系列视频，还包括了以太坊使用的 ECDSA 等的介绍。 In this video, we propose an intuitive approach to understanding digital signature, verifying it and what elliptic curve generator really does.

https://www.youtube.com/watch?v=F9PQfaRRkQw

Updates

Polygon Plonky3 is Production Ready

Today, researchers at Polygon Labs are excited to announce that Polygon Plonky3, the next generation of ZK proving systems, is production ready and open-source licensed under MIT/Apache.

https://polygon.technology/blog/polygon-plonky3-the-next-generation-of-zk-proving-systems-is-production-ready

riscairo

RISC-V ELF interpreter in cairo 2.

https://github.com/damip/riscairo

zkVM 1.0: Industry-Leading Performance Benchmarks

Across the board, we found that a properly configured RISC Zero zkVM outperforms a similarly configured Succinct SP1 deployment in both cost and speed.

Better, Faster, Smaller Binius

A major update to FRI-Binius yields better batching, faster recursion, and smaller proofs

https://www.irreducible.com/posts/better-faster-smaller-binius

Nexus 2.0: Jolt, HyperNova, and a New SDK

Nexus 2.0 与上个月发布的 1.0 zkVM 相比，引入了一些关键的新组件，推动了性能和效率的提升：

由 Jolt 算术化系统支持的新证明器前端
由 HyperNova 递归证明系统支持的新证明器后端
Nexus SDK，一个用于大规模并行生成多个证明的编程框架 A new prover frontend, powered by the Jolt arithmetization system A new prover backend, powered by the HyperNova recursive proof system The Nexus SDK, a programmatic framework for producing multiple proofs in parallel and at scale
https://blog.nexus.xyz/nexus-2-0-jolt-hypernova-and-a-new-sdk/

A key component of the Nexus 2.0 zkVM is a new SDK, a programmatic framework for computing multiple zkVM proofs at scale. It supports each of our Nova, HyperNova, and Jolt backends, enabling easy configuration to tailor proving to specific applications. Dynamic compilation, private input, public output, and logging support together provide a rich programmatic interface to guest programs. A simple, misuse-resistant design makes using the Nexus zkVM to prove even complex programs a straightforward process.

https://docs.nexus.xyz/zkvm/sdk-quick-start

Jolt Roadmap Update

Jolt 七月份的路线图，主要是三个部分:

On-chain verification: 基于 Zeromorph 的 PCS 来减少 verifier cost，基于 HyperKZG 的 PCS，以及 EVM Verifier 的实现
Optimization: 使用 Quarks 来优化 GKR 的实现，以及使用稀疏化表示方式来减少 Sumcheck 的内存占用
Devex: 支持 std，wasm，allocator，支持 RV32I-M，重构 R1CS
https://x.com/samrags_/status/1813954274629689628

The Story of Shor's Algorithm

Peter Shor really understood the landscape of theory from complexity to cryptography, a curiosity for quantum computing and the vision to see how it all connected together to get the quantum algorithm that almost single-handedly brought billions of dollars to the field.

https://blog.computationalcomplexity.org/2024/07/the-story-of-shors-algorithm.html

A Better World with Self-Sovereign Identity

Self-sovereign identity is a model for managing digital identities where individuals or businesses have complete control and ownership over their accounts and personal data.

https://medium.com/@aharon.smbatyan/a-better-world-with-self-sovereign-identity-c8ea50ed0c5e

BitVM verifier script optimization

This pull request fully implemented Algorithm 9 from "On Proving Pairings" paper for BitVM. Final Groth16 verifier script size is now approximately 2.9GB, reduced by 1.1G.

https://github.com/BitVM/BitVM/pull/83

zk Warsaw Meetup 16: Zero Knowledge Applications on Mina Protocol

Brandon Kase - CEO of o1Labs - the incubators of Mina Protocol leads a focused discussion on the application of zero-knowledge proofs in the Mina Protocol.

https://www.youtube.com/watch?v=etpZeX0V7ZY

circle-plonk

Using stwo to implement a Plonk prover and verifier over Circle STARK

https://github.com/Bitcoin-Wildlife-Sanctuary/circle-plonk

Papers

On the Concrete Security of Non-interactive FRI

Providing a thorough concrete security analysis of non-interactive FRI under various parameter settings from protocols deploying FRI today.

https://eprint.iacr.org/2024/1161

A Crack in the Firmament: Restoring Soundness of the Orion Proof System and More

Orion in its current revision is still unsound (with and without the zero-knowledge property) and demonstrates practical attacks on it. Then show how to repair Orion without additional assumptions, which requies non-trivial fixes when aiming to preserve the linear time prover complexity.

https://eprint.iacr.org/2024/1164

Dot-Product Proofs and Their Applications

点积证明（DPP）是一个简单的概率证明系统，其中输入语句 $x$ 和证明 $π$ 是有限域 $F$ 上的向量，而证明是通过对 $x$ 和 $π$ 进行单个点积查询 $⟨ q, (x ∥ π)⟩$ 来验证的。DPP 可以看作是一个 1-query 完全线性 PCP。论文还讨论了 DPP 的可行性和效率。 A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement $x$ and the proof $π$ are vectors over a finite field $F$ , and the proof is verified by making a single dot-product query $⟨ q, (x ∥ π)⟩$ jointly to $x$ and $π$ . A DPP can be viewed as a 1-query fully linear PCP. We study the feasibility and efficiency of DPPs.

https://eprint.iacr.org/2024/1138

Designated-Verifier zk-SNARKs Made Easy

Propose a construction of strong designated-verifier zk-SNARKs. The construction inspired by designated verifier signatures based on two-party ring signatures does not use encryption and can be applied on any public-verifiable zk-SNARKs to yield a designated-verifiable variant.

https://eprint.iacr.org/2024/1153

On cycles of pairing-friendly abelian varieties

One of the most promising avenues for realising scalable proof systems relies on the existence of 2-cycles of pairing-friendly elliptic curves. In this paper, the authors generalise the notion of cycles of pairing-friendly elliptic curves to study cycles of pairing-friendly abelian varieties, with a view towards realising more efficient pairing based SNARKs.

https://eprint.iacr.org/2024/869.pdf

Quasi-Linear Size PCPs with Small Soundness from HDX

A fantastic new result by Bafna, Minzer, and Vyas shows what can be viewed as a version of the PCP theorem of @IritDinur in the low soundness regime. They do so using high-dimensional expanders and ideas from fault-tolerant distributed computing. It's interesting to note that ideas from fault tolerance also recently arose in the setting of the quantum PCP conjecture. This (perhaps unexpected) connection between PCPs and fault tolerance seems to be quite promising.

https://arxiv.org/pdf/2407.12762v1

Highlights

Avi Wigderson Turing Award Lecture: “Alan Turing: A TCS Role Model”

阿维-维格德森 (Avi Wigderson) 获得了 2023 年 ACM A.M. 图灵奖，以表彰他对计算理论做出的奠基性贡献，包括重塑了我们对随机性在计算中的作用的理解，以及他数十年来在理论计算机科学领域的知识领导地位。 Wigderson 是新泽西州普林斯顿高等研究院数学学院的 Herbert H. Maass 教授。他在计算复杂性理论、算法与优化、随机性与密码学、并行与分布式计算、组合学、图论以及理论计算机科学与数学和科学之间的联系等领域一直处于领先地位。

https://www.youtube.com/watch?v=f2NiGO8zC1c

Peter Shor is the recipient of the 2025 Claude E. Shannon Award

The IEEE Information Theory Society is pleased to announce that Peter Shor is the recipient of the 2025 Claude E. Shannon Award for consistent and profound contributions to the field of information theory.

https://www.itsoc.org/news/shannon-award-2025

To Schnorr and beyond

马修·格林是约翰霍普金斯大学的教授和密码学家，他在下面的两篇博客里面详细的介绍了 Schnorr 签名系统模型、协议和数学原理，博客清晰且重点清晰。

Fiat-Shamir Heuristic

Zkproof 工作小组关于 Fiat-Shamir Heuristic 的标准化草案，草案作者是 CNRS 的 M. Orrù。草案简洁的定义了Fiat-Shamir Heuristic的接口、步骤和示例。

https://mmaker.github.io/stdsigma/draft-orru-zkproof-fiat-shamir.html

Sigma Protocols

Network 工作小组关于 Sigma Protocols 的标准化草案，草案作者是 CNRS 的 M. Orrù 和 AIT 的 S. Krenn。草案状态是 Informational，已经包括了丰富的细节和示例。

https://mmaker.github.io/stdsigma/draft-orru-zkproof-sigma.html

Announcing AES-GEM (AES with Galois Extended Mode)

https://blog.trailofbits.com/2024/07/12/announcing-aes-gem-aes-with-galois-extended-mode/

Interactive Arithmetization and Iterative Constraint Systems

David，zkSecurity的联合创始人，也是《真实世界的密码学》一书的作者关于交互式算术和迭代约束系统的总结博客，同时包含了一系列相关介绍的链接。

https://cryptologie.net/article/615/interactive-arithmetization-and-iterative-constraint-systems/

STIR won Best Paper at CRYPTO 2024!

https://x.com/GiacomoFenzi/status/1809172872981536862

Understanding the point at infinity in Elliptic Curves

https://www.youtube.com/shorts/josvCacPz7w

“神秘”的密码学到底在学些什么？

https://mp.weixin.qq.com/s/2A7EXSburxbEzhX3aLMFAg

The Phantom Zone

phantom-zone 是一个实验性的多方计算库，它使用多方完全同态加密来计算来自多方的私人输入的任意函数。目前，phantom-zone 的功能相当有限。它提供使用加密的 8 位无符号整数（称为 FheUint8）写入电路的功能，并且仅支持最多 8 方。FheUint8 支持与常规 uint8 相同的算法，介绍文档里面提到了一些例外情况。计划在未来将 API 扩展到其他有符号/无符号类型。

https://gauss.ing/blog/phantom-zone/

Privacy-preserving KYC

https://medium.com/@tisura/privacy-preserving-kyc-57002ab8d3f2

Proof of Twitter: ZK Email Demo

https://twitter.prove.email/

Hardhat ZKit

https://github.com/dl-solarity/hardhat-zkit

CryptoHack launched the ZKP section

https://cryptohack.org/challenges/zkp/

Ethereum Proofs - Noir Library Use Cases

https://www.vlayer.xyz/blog/ethereum-proofs-noir-library-use-cases

Blendy 🍹: a space-efficient sumcheck algorithm

https://github.com/compsec-epfl/space-efficient-sumcheck

Updates

ENCRYPT London 2024 (Playlist)

https://www.youtube.com/playlist?list=PLYQnwnLD-Fq1rYZYieFU5-mwCE2mMVprm

ZK and cryptography with Justin Thaler, Valeria Nikolaenko and Joseph Bonneau

https://www.youtube.com/watch?v=5RrSs8FswBo

The Man Who Solved the World’s Hardest Math Problem

https://www.youtube.com/watch?v=l6ev1lGq0B4

The Zombie Misconception of Theoretical Computer Science

https://scottaaronson.blog/?p=8106

Privado ID

https://www.privado.id/

CUDA Mini Course #3, presented by Hadar Sackstein, Algorithms Engineer at Ingonyama

https://www.youtube.com/watch?v=vhRfdMBANJ0

Now You Can Receive Crypto as Easily as an Email: The Mastermind Behind zkLogin - Kostas Kryptos

https://www.youtube.com/watch?v=NTypG0-PfrU

ETHGlobal Brussels (Video Playlist)

https://www.youtube.com/playlist?list=PLXzKMXK2aHh6G-EVZ4ZPy4w1bweZ1xDhq

BOUNDLESS by RISC Zero at EthCC Brussels, Belgium 2024

ZK Proofs in Action: Production-Ready Solutions for Real World Apps by Jeremy Bruestle
- https://www.youtube.com/watch?v=Cl2L2dklLbk&list=PLcPzhUaCxlCgCvzkkaBWzVuHdBRsTNxj1&index=41
Interoperability From Coordinated Sequencing & ZK Proofs by Ben Fisch, Espresso Labs
https://www.youtube.com/watch?v=V3aIRUDp7eo&list=PLcPzhUaCxlCgCvzkkaBWzVuHdBRsTNxj1&index=43
NEBRA UPA: Proof Aggregation for privacy, scaling and interoperability By Shumo Chu
- https://www.youtube.com/watch?v=_o7Lt46M7Gw&list=PLcPzhUaCxlCgCvzkkaBWzVuHdBRsTNxj1&index=47
The Endgame for Web3 by Zac Williamson
- https://www.youtube.com/watch?v=dz-5e1cnsJU

Papers

【论文速递】CiC Vol. 1, Issue 2 (7篇）

https://mp.weixin.qq.com/s/LjNaLdWKf1YoNjL_b3IHMQ

【论文速递】ASIA CCS '24（隐私保护协议、后量子、密码学、去中心化系统、认证签名）

https://mp.weixin.qq.com/s/FHkvyP1mVF_leNMHfWIflw

A Note on Efficient Computation of the Multilinear Extension

In this note we show how, given oracle access to $f : {0, 1}^{m} \to F$ and a point $z \in F^{m}$ , to compute $\hat{f} (z)$ using $O (2^{m})$ field operations and only $O (m)$ space.

https://eprint.iacr.org/2024/1103

Ringtail: Practical Two-Round Threshold Signatures from Learning with Errors

Introducing Ringtail, the most efficient 2-round lattice-based threshold signature from standard assumptions.

https://eprint.iacr.org/2024/1113

A Simple Post-Quantum Oblivious Transfer Protocol from Mod-LWR

https://eprint.iacr.org/2024/1116

Generic Anamorphic Encryption, Revisited: New Limitations and Constructions

https://eprint.iacr.org/2024/1119

Distributed Verifiable Random Function With Compact Proof

https://eprint.iacr.org/2024/1130

Jolt-b: recursion friendly Jolt with basefold commitment

https://eprint.iacr.org/2024/1131

Hadamard Product Argument from Lagrange-Based Univariate Polynomials

https://eprint.iacr.org/2024/613

Learnings

STARK 101

STARK 101 is a hands-on tutorial on how to write a STARK prover from scratch (in Python).

https://starkware.co/stark-101/

Quantum Computer Programming in 100 Easy Lessons

A beginner's course on basic quantum computing algorithms. Background required: basic knowledge of computer programming, probability, and geometry. Knowledge of linear algebra a plus.

https://www.youtube.com/playlist?list=PLm3J0oaFux3bF48kurxGR6jrmPaQf6lkN

zkSync Era Tutorial

https://www.youtube.com/playlist?list=PLgPVMJY4tnFNK260S6thZqEAXJhtcgHaW

Highlights

Adi Shamir: Wolf Prize Laureate in Mathematics 2024

https://wolffund.org.il/adi-shamir/ 恭喜 Shamir 由于密码学的数学基础等重要贡献，荣获本年度的沃尔夫数学奖。

Releasing Constantine v0.1.0, a modular cryptography stack for Ethereum

https://ethresear.ch/t/releasing-constantine-v0-1-0-a-modular-cryptography-stack-for-ethereum/19990 Constantine 提供了截至目前以太坊特定加密原语的最快实现，包括 BLS 签名，BN254 预编译（EIP-196 和 EIP-197，在 EIP-1108 中重新定价），BLS12-381 预编译（EIP-2537）和 KZG 多项式承诺（EIP-4844）。 Constantine 与 C、Go、Nim 和 Rust 有绑定。Constantine 用 Nim 语言写成，具有优秀的表现力、类型系统强度、易于被打包成 C 和 C++，并且与 Python 的语法接近，可以轻松移植以太坊研究和 PyEVM 的相关实现。Constantine 尚未经过审计，但由于以太坊基金会在 2023 年夏季的赞助，它已由 Guido Vranken 进行了广泛的模糊测试。还被添加到 OSS-Fuzz 和 Google 全天候开源模糊测试计划。

2 $π$ .com Blog

https://xn--2-umb.com/ Remco Bloemen 的笔记，包括了大量密码学原语和协议的整理总结，比如 Groth16，BLS 签名等。笔记简洁清晰，关注于原语和协议的核心，并且贴心的标记了适合大众阅读的文章。

Zorch

Zorch is a package for CUDA-optimized STARK proving.

https://github.com/vbuterin/zorch

Proximity Is What You Want: Low-Degree Testing for Reed-Solomon Codes

https://hackmd.io/IUO7OMrKSQu5Zoigwb6kWQ

Quantum is unimportant to post-quantum

https://blog.trailofbits.com/2024/07/01/quantum-is-unimportant-to-post-quantum/

Theory and Practical Implementation of BLS12-381

https://hackmd.io/hd6eOL_oSLK9o8nU3KfbCA

Convolutions, Fast Fourier Transform and Polynomials

https://www.alvarorevuelta.com/posts/fft-polynomials Alvaro Revuelta 在这篇博客中简洁清晰的解释了如何使用 FFT 来加速多项式乘法，使复杂度从直接相乘的 O(n^2) 降到 O(nlogn)。博客中还给出了示例代码和仿真结果。

With Fifth Busy Beaver, Researchers Approach Computation’s Limits

https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/

Zero-Knowledge Proofs and Their Role within the Blockchain

https://cacm.acm.org/article/zero-knowledge-proofs-and-their-role-within-the-blockchain/ Alex Williams 在 ACM 会刊上对零知识证明在区块链中的应用和限制进行了简明的总结。

Proteus

Proteus is an open-source platform for AI content provenance - leveraging proof of transformation to create incorruptible and robust watermarks.

https://www.proteus.photos/

Sumcheck and Open-Binius

Algebraic FFTs

https://rje.li/24-07-03-alg-fft.html

The ECFFT algorithm

https://solvable.group/posts/ecfft/

The Number Theoretic Transform in Kyber and Dilithium

https://electricdusk.com/ntt.html

A Zero Knowledge Paradigm : Part 3 Custom ISA

https://www.lita.foundation/blog/custom-instruction-set-architecture-achieving-ultimate-efficiency-in-zk-proving

Updates

Episode 330: Frameworks for Programmable Privacy with Ying Tong and Bryan Gillespie

https://zeroknowledge.fm/330-2/

Zero-Knowledge Location Privacy

https://www.youtube.com/watch?v=qeHQgKUfoCQ

Jolt: SNARKs for virtual machines via lookups - Arasu Arun (NYU), Michael Zhu (a16z Crypto)

https://www.youtube.com/watch?v=ebN-mt-P-Qw

A STARK breakthrough: Next-gen provers may be at least 100x faster

Delegated Spartan

https://github.com/recmo/delegated-spartan

Ingonyama CUDA Mini Course

micro-rsa-dsa-dh

Minimal implementation of older cryptography algorithms: RSA, DSA, DH.

https://github.com/paulmillr/micro-rsa-dsa-dh

Add noname as a frontend to sonobe

https://github.com/privacy-scaling-explorations/sonobe/pull/121

Papers

Adaptor Signatures: New Security Definition and A Generic Construction for NP Relations

https://eprint.iacr.org/2024/1051

Optimized Computation of the Jacobi Symbol

https://eprint.iacr.org/2024/1054

Enhancing Local Verification: Aggregate and Multi-Signature Schemes

https://eprint.iacr.org/2024/1055

Shuffle Arguments Based on Subset-Checking

https://eprint.iacr.org/2024/1056

Natively Compatible Super-Efficient Lookup Arguments and How to Apply Them

https://eprint.iacr.org/2024/1058

Quirky Interactive Reductions of Knowledge

https://eprint.iacr.org/2024/1060

Insta-Pok3r: Real-time Poker on Blockchain

https://eprint.iacr.org/2024/1061

VIMz: Verifiable Image Manipulation using Folding-based zkSNARKs

https://eprint.iacr.org/2024/1063 VIMz 旨在开发一个实用的框架，以在商用硬件上有效地证明高清和 4K 图像的真实性，通过使用 Nova 折叠证明，最大限度地降低了证明器复杂性。实验结果中减少了达到 3 倍的证明时间和 96 倍的内存开销（从 [Kang et al., arXiv 2022] 中的 309 GB 减少到仅 3.2 GB）。

VerITAS: Verifying Image Transformations at Scale

https://eprint.iacr.org/2024/1066

From Interaction to Independence: zkSNARKs for Transparent and Non-Interactive Remote Attestation

https://eprint.iacr.org/2024/1068

Trust Nobody: Privacy-Preserving Proofs for Edited Photos with Your Laptop

https://eprint.iacr.org/2024/1074

TaSSLE: Lasso for the commitment-phobic

https://eprint.iacr.org/2024/1075

Practical Non-interactive Multi-signatures, and a Multi- to Aggregate Signatures Compiler

https://eprint.iacr.org/2024/1081

Notes on Multiplying Cyclotomic Polynomials on a GPU

https://eprint.iacr.org/2024/1094

Highlights

Introducing the ZK Catalog

Ariel Gabizon UJ crypto course: the KZG PCS scheme and PlonK SNARK

https://github.com/arielgabizon/Lectures/blob/master/ujtalksKZG%2BPLONK.pdf

Disarming Fiat-Shamir footguns

https://blog.trailofbits.com/2024/06/24/disarming-fiat-shamir-footguns/

Building a Decentralized Privacy Preserving Order Book Exchange on Polygon Miden

https://alexanderjohnlee.medium.com/building-a-decentralized-privacy-preserving-order-book-exchange-on-polygon-miden-f4502a550cc5

FRIDA: Data-Availability Sampling from FRI

https://www.zksecurity.xyz/blog/posts/frida/

Montgomery Multiplication

Many algorithms in number theory, like prime testing or integer factorization, and in cryptography, like RSA, require lots of operations modulo a large number. The Montgomery (modular) multiplication is a method that allows computing such multiplications faster. Instead of dividing the product and subtracting n multiple times, it adds multiples of n to cancel out the lower bits and then just discards the lower bits.

https://cp-algorithms.com/algebra/montgomery_multiplication.html

zkPages

Zero-knowledge digital content single page store fronts. Enable anyone to create a secure digital content store front page on Starknet. Privacy-focused checkouts.

https://ethglobal.com/showcase/zkpages-n3aro

zKastle

zKastle is a solo strategy card game. Manage resources, and upgrade your village to make the maximum points possible. Make tactical decisions to help your village grow and flourish.

https://ethglobal.com/showcase/zkastle-jeh44

Solas

An attestation / citation system built on starknet using Cairo and starknet tooling.

https://ethglobal.com/showcase/solas-pekhm

Ingopedia

A comprehensive collection of resources and information related to Zero Knowledge Proofs from Ingonyama

https://www.ingonyama.com/ingopedia/communityguide

Updates

ZK Summit 11 Retrospective

Reflections on NFC cards and advanced cryptography at ZK Summit 11

https://www.cursive.team/blog/zk-summit

zkStudyClub - FRI-Binius: Polylogarithmic Proofs for Multilinears over Binary Towers (Ben Diamond)

https://www.youtube.com/watch?v=iZlJDT7V8Q4

Cloaking Layer - zCloak Network released its universal ZKP verification infrastructure for all blockchains

https://zcloaknetwork.medium.com/cloaking-layer-a-zk-verification-infra-for-all-chains-1162d3fcc37b

HyperNova: Recursive arguments for customizable constraint systems

The paper is now updated. The newly added content highlights a new use of folding schemes. Previously, folding schemes were used to construct IVC. We now show that certain folding schemes (e.g., Nova's) unlock a new approach to add ZK in proof systems.

https://eprint.iacr.org/2023/573.pdf

Papers

【论文速递】STOC 2024（量子、电路、单向函数、承诺、零知识、证明、不可区分混淆、格基SNARKs）

https://mp.weixin.qq.com/s/hhyuKvcY-AYE70kjemgjEg

On the vector subspaces of $F_{2^{n}}$ over which the multiplicative inverse function sums to zero

https://eprint.iacr.org/2024/1007

The Sum-Check Protocol over Fields of Small Characteristic

https://eprint.iacr.org/2024/1046

Constraint-Packing and the Sum-Check Protocol over Binary Tower Fields

https://eprint.iacr.org/2024/1038

A note on adding zero-knowledge to STARKs

https://eprint.iacr.org/2024/1037

A note on the G-FFT

https://eprint.iacr.org/2024/1036

Sparsity-Aware Protocol for ZK-friendly ML Models: Shedding Lights on Practical ZKML

Dong Mo博士团队新做的一个ZKML的工作。主要讲的是通过ternary network可以将神经网络模型（LLM之类）无损压缩和整数化，并且在这种简化的基础上面设计了一个叫SpaGKR的ZK算法，实现高效ZKML inference。目前初步测下来能做到100X以上的速度提升，之后会补实验部分。

https://eprint.iacr.org/2024/1018

Accelerating pairings on BW10 and BW14 Curves

https://eprint.iacr.org/2024/1017

A Succinct Range Proof for Polynomial-based Vector Commitment

https://eprint.iacr.org/2024/1016

Highlights

Luca Trevisan (1971-2024)

Luca Trevisan's Cryptography Lecture Notes from CS276, Spring 2009

One of the best learning resources about the Goldreich-Levin theorem, recommended by Prof. Deng Yi.

https://lucatrevisan.github.io/books/crypto.pdf

The ZF FROST Book

https://frost.zfnd.org/index.html

SoK: Programmable Privacy in Distributed Systems

https://eprint.iacr.org/2024/982

Abstract Algebra: Theory and Applications

A nice book with examples and programming exercises.

http://abstract.ups.edu/aata/aata.html

10 Weeks of Journey into vFHE

Arithmetizing FHE in Circom

https://pps-lab.com/blog/fhe_arithmetization/

Juvix: a language for intent-centric and declarative decentralized applications

https://docs.juvix.org/0.6.1/README.html

Updates

Nexus zkVM 1.0

https://nexus.xyz/

RISC Zero zkVM 1.0: Industry-Leading Performance Benchmarks

https://www.risczero.com/blog/beating-moores-law-with-zkvm-1-0

Episode 328: ZK on Bitcoin with Alpen Labs

https://zeroknowledge.fm/328-2/

Arkwork v0.5.0-alpha

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

北京密码学日成功举办

https://mp.weixin.qq.com/s/c21alfYq9j3fbkTyfUADQg

Eurocrypt 2024 Videos

SNARKs: https://www.youtube.com/watch?v=_WsCQc9Elcg
Proof Systems: https://www.youtube.com/watch?v=e0b3oKSrYt8

Papers

Fast SNARK-based Non-Interactive Distributed Verifiable Random Function with Ethereum Compatibility

https://eprint.iacr.org/2024/968

ICICLE v2: Polynomial API for Coding ZK Provers to Run on Specialized Hardware

https://eprint.iacr.org/2024/973

Volatile and Persistent Memory for zkSNARKs via Algebraic Interactive Proofs

https://eprint.iacr.org/2024/979

Hadamard Product Arguments and Their Applications

https://eprint.iacr.org/2024/981

On Knowledge-Soundness of Plonk in ROM from Falsifiable Assumptions

https://eprint.iacr.org/2024/994

Cross-chain bridges via backwards-compatible SNARKs

https://eprint.iacr.org/2024/995

Dishonest Majority Multi-Verifier Zero-Knowledge Proofs

https://eprint.iacr.org/2024/997

zkVoting : Zero-knowledge proof based coercion-resistant and E2E verifiable e-voting system

https://eprint.iacr.org/2024/1003

Relaxed Vector Commitment for Shorter Signatures

https://eprint.iacr.org/2024/1004

Formal Verification of Zero-Knowledge Circuits

https://arxiv.org/pdf/2311.08858

Highlights

Ronkathon: Learn Cryptography from First Principles

Ronkathon是受Plonkathon启发的一组密码原语的 Rust 实现。旨在展示应用密码学的理论特性以及编程语言中的具体应用的技术内容。Ronkathon是根据第一性原理构建的，因此无需了解外部库或详细依赖项（除rand和itertools之外）。大部分代码并未针对数学透明度和简洁性进行优化。

https://pluto.xyz/blog/ronkathon-learn-cryptography-from-first-principles

A Zero Knowledge Paradigm: Part 2- Exploring zk-VM Design Trade-offs

In the part 2 of their article series about zkVMs, @ventalitan from @lita_xyz first gave an overview of zkVM design, and then covered the trade-offs of all the different aspects it involves.

https://www.lita.foundation/blog/a-zero-knowledge-paradigm-part-2--exploring-zk-vm-design-trade-offs

Diving into Poseidon hash and its security

https://autoparallel.github.io/overview/index.html

The Nexus zkVM

https://docs.nexus.xyz/

Polygon Zero zkEVM

A collection of libraries to prove Ethereum blocks with Polygon Zero Type 1 zkEVM, powered by starky and plonky2 proving systems.

https://github.com/0xPolygonZero/zk_evm

How to verify ZK proofs on Bitcoin? by Polyhedra Network

https://hackmd.io/@polyhedra/bitcoin

All the proof aggregation solutions will use RISC-V zkVMs

https://blog.alignedlayer.com/all-the-proof-aggregation-solutions-will-use-risc-v-zkvms/

Episode 327: Proof Aggregation with Shumo and Yi from NEBRA

In this week’s episode Anna chats with Shumo and Yi from NEBRA. They discuss the high price of putting ZKPs on-chain before diving into NEBRA’s proposed solution to mitigating this, their Universal Proof Aggregation product. They cover what it takes to incorporate extra pricing systems into NEBRA UPA as well as the benefits that these systems will bring, how developers are meant to interact with them, and future integrations to enable seamless cross-zkRollup applications. The group round off by discussing prover marketplaces, verification aggregation systems, and the design space that this all opens up.

https://zeroknowledge.fm/327-2/

Pairings in Cryptography

Dan Boneh 介绍了 pairing 的原理和计算 pairing 的算法, 还讲了相关的应用, 比如可以利用 pairing 构建 BLS 签名和门限签名. https://youtu.be/8WDOpzxpnTE?si=JIguXJMSss9dru1A&t=1992 这里很搞笑, 说 pairing 的公式是法国数学家 Andre Weil 在二战期间的 2 年监狱服刑中搞出来的(因为拒绝当兵), 之后他在自传中建议法国数学家都去监狱中待两年, 因为确实很高产

https://youtu.be/8WDOpzxpnTE?si=Exjj-d5yK2LEQNMy

Cryptography and Privacy in Context | Ying Tong | Web3Privacy Now Berlin Meetup 2024

https://www.youtube.com/watch?v=XrpjfyEK7Hs

Zero Knowledge Security from OpenSense

A very nice and general introduction about Zero Knowledge Security. ZK Developers and auditors can level up their ZK auditing skills in this video.

https://www.youtube.com/watch?v=Ypreb-PKF7o

Fancy cryptography in the wild

Curated list of deployments of fancy cryptography. Cryptography counts as fancy if it uses primitives beyond symmetric ciphers, (EC)DH as key agreement, digital signatures, public key encryption such as RSA-OAEP, or KEMs, or uses those primitives in unusual ways, especially if it relies on properties beyond IND-CCA2.

https://github.com/fancy-cryptography/fancy-cryptography

Updates

Poseidon{2} for Noir

https://blog.taceo.io/poseidon2-for-noir/

Verification of zkWasm in Coq

This repository previews a Coq development to formally verify the zkWasm zkVM.

https://github.com/CertiKProject/zkwasm-fv

Catnet Bitcoin signet

Catnet is a custom Bitcoin signet with OP_CAT enabled, used to test implementation of Bitcoin Circle STARK Verifier.

https://github.com/Bitcoin-Wildlife-Sanctuary/catnet

David Wong - noname walkthrough

https://www.youtube.com/watch?v=pQer-ua73Vo

Justin Thaler - Proofs, Arguments, and Zero-Knowledge - Week 1

Justin Thaler在学习群组中对于自己名作Proofs, Arguments, and Zero-Knowledge一书的讲解，这是第一周的录像，还附有讲解时使用的笔记。

Ariel Gabizon - FFT's on the projective line and circle-STARKs

Ariel Gabizon gave a talk about how to enable fast FFTs over Fp when a large power of 2 divides p+1, which is the idea behind Circle STARK.

https://www.youtube.com/watch?v=d1f9sBajj10

How zkSharding Addresses the Blockchain Trilemma

=nil; Foundation的博客，总结了当前使用零知识证明对区块链进行扩展的技术路线，强调了zkSharding作为水平扩容路线的优势。

https://nil.foundation/blog/post/zkSharding_scaling

zkStudyClub - LatticeFold: Lattice Folding Schemes (Binyi Chen)

https://www.youtube.com/watch?v=-k8s7vVUx6s

Papers

Polymath: Groth16 Is Not The Limit

Proposes a zk-SNARK Polymath for the Square Arithmetic Programming constraint system using the KZG polynomial commitment scheme. Polymath has a shorter argument than Groth16. At 192-bit security, Polymath's argument is nearly half the size, making it highly competitive for high-security future applications.

https://eprint.iacr.org/2024/916

Leveled Fully-Homomorphic Signatures from Batch Arguments

We do not have homomorphic signatures with features such as multi-hop evaluation, context hiding, and fast amortized verification, while relying on standard falsifiable assumptions. In this work, we design homomorphic signatures satisfying all above properties. Constructing homomorphic signatures for polynomial-sized circuits from a variety of standard assumptions such as sub-exponential DDH, standard pairing-based assumptions, or learning with errors.

https://eprint.iacr.org/2024/931

A Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for NP

Constructing an adaptively-sound SNARG for NP in the CRS model from sub-exponentially-secure iO and sub-exponentially-secure one-way functions.

https://eprint.iacr.org/2024/933

Scalable Collaborative zk-SNARK and Its Application to Efficient Proof Outsourcing

Extending the existing zk-SNARKs Libra (Crypto'19) and HyperPlonk (Eurocrypt'23) into scalable collaborative zk-SNARKs.

https://eprint.iacr.org/2024/940

SmartZKCP: Towards Practical Data Exchange Marketplace Against Active Attacks

https://eprint.iacr.org/2024/941

Dual Polynomial Commitment Schemes and Applications to Commit-and-Prove SNARKs

https://eprint.iacr.org/2024/943

Communication Complexity vs Randomness Complexity in Interactive Proofs

https://eprint.iacr.org/2024/952

SNARGs under LWE via Propositional Proofs

https://eprint.iacr.org/2024/956

Interests

The State of Security Tools for ZKPs

zkSecurity team briefly discuss where vulnerabilities can be introduced when using ZKPs, and the state of security tools for finding vulnerabilities in ZKPs.

https://www.zksecurity.xyz/blog/posts/zksecurity-tools/

Highlights

The State of Security Tools for ZKPs

https://www.zksecurity.xyz/blog/posts/zksecurity-tools/

Circle STARKs: Part I, Mersenne

https://www.zksecurity.xyz/blog/posts/circle-starks-1/

Understanding Jolt: Clarifications and reflections by Justin Thaler

Justin Thaler explored four areas in Lasso and Jolt: (1) the relationship between the sum-check protocol and the Binius commitment scheme, (2) the role of sum-check and lookups in Jolt, (3) elliptic curves versus hashing, and (4) precompiles as they relate to zkVMs.

https://a16zcrypto.com/posts/article/understanding-jolt-clarifications-and-reflections/

BrainSTARK

This tutorial teaches the reader how to design a Turing-complete zk-STARK engine, consisting of a virtual machine, prover, and verifier. Brainfuck was chosen as the target language due to its well-known and simple instruction set, but the design patterns introduced in this tutorial generalize to arbitrary instruction set architectures

https://aszepieniec.github.io/stark-brainfuck/index

Bivariate Kate-Zaverucha-Goldberg (KZG) Constant-Sized Polynomial Commitments

This article presents a variant of the KZG commitment, the bivariate KZG commitment, which allows us to commit to polynomials with two variables. PolyhedraZK在这篇笔记中描述了二元KZG承诺，可以支持双变量的多项式承诺和验证。笔记简洁易懂。

https://github.com/PolyhedraZK/blogs/blob/main/bi-kzg.md

Updates

zkStudyClub - Reef: Fast Succinct Non-Interactive ZK Regex Proofs (Eli Margolin, Jess Woods: UPenn)

https://www.youtube.com/watch?v=68-BuxRR-EA
https://eprint.iacr.org/2023/1886

zkSecurity x Bain Capital Crypto Whiteboards: Unveiling the Power of Multi-Party Computation

https://www.zksecurity.xyz/blog/posts/mpc/

noname meets Ethereum: Integration with SnarkJS

https://www.zksecurity.xyz/blog/posts/noname-r1cs/

Scaling Bitcoin for mass use: A realistic vision by Eli Ben-Sasson

Starknet can become a single layer that settles on both Bitcoin and Ethereum.

https://starkware.co/scaling-bitcoin-for-mass-use/

HyperNova was accepted to appear at CRYPTO’24

Made several improvements. A significant addition is achieving ZK while only using a non-zk SNARK. This means an on-chain verifier can continue to verify sum-check messages in plaintext while being truly ZK! Eprint updating soon! 知名折叠方案，Kothapalli和Setty的著名工作，本次确定被密码学顶会CRYPTO’24接收发表。实现了对CCS约束的增量计算的递归证明。可以被推广到Plonkish, R1CS, 和AIR约束。HyperNova的优势在于复杂度上的大量优化，证明的每一步的主要复杂度来源于单个MSM，其大小等于约束系统中的变量数。另外本文还提出了nlookup，一个查找证明，特别适用于基于折叠方案的递归证明。

https://eprint.iacr.org/2023/573.pdf

Noir v0.30.0 update

Breaking changes:

remove Opcode::Brillig from ACIR
AES blackbox

https://github.com/noir-lang/noir/releases/tag/v0.30.0

Papers

Analyzing and Benchmarking ZK-Rollups

This paper offers a theoretical and empirical examination aimed at comprehending and evaluating ZK-Rollups, with particular attention to ZK-EVMs. Stefanos Chaliasos在zk-Bench之后关于零知识证明实施的又一个Benchmark研究，该研究主要关注ZK-Rollups的设计和实施，论文前半部分主要关注设计上的分析，后半部分对Polygon zkEVM和zkSync Era进行了一些实验和测试。

https://eprint.iacr.org/2024/889

zkCross: A Novel Architecture for Cross-Chain Privacy-Preserving Auditing

Proposes zkCross, a novel two-layer cross-chain architecture equipped with three cross-chain protocols to achieve privacy-preserving cross-chain auditing.

https://eprint.iacr.org/2024/888

Security of Fixed-Weight Repetitions of Special-Sound Multi-Round Proofs

https://eprint.iacr.org/2024/884

Epistle: Elastic Succinct Arguments for Plonk Constraint System

Presents Epistle, an elastic SNARK for Plonk constraint system. For an instance with size $N$ , in the time-efficient configuration, the prover uses $O_{λ} (N)$ cryptographic operations and $O (N)$ memory; in the space-efficient configuration, the prover uses $O_{λ} (N lo g N)$ cryptographic operations and $O (lo g N)$ memory. Compared to Gemini, this approach reduces the asymptotic time complexity of the space-efficient prover by a factor of $lo g N$ . The key technique we use is to make the toolbox for multivariate PIOP provided by HyperPlonk elastic.

https://eprint.iacr.org/2024/872

Cryptanalysis of Algebraic Verifiable Delay Functions

Analyze the security of these algebraic VDF candidates. In particular, shows that the latency of exponentiation can be reduced using parallel computation, against the preliminary assumptions.

https://eprint.iacr.org/2024/873

On cycles of pairing-friendly abelian varieties

Generalizes the notion of cycles of pairing-friendly elliptic curves to study cycles of pairing-friendly abelian varieties, with a view towards realizing more efficient pairing-based SNARKs.

https://eprint.iacr.org/2024/869

Loquat: A SNARK-Friendly Post-Quantum Signature based on the Legendre PRF with Applications in Ring and Aggregate Signatures

Designs and implements a novel NARK-friendly post-quantum signature scheme based on the Legendre PRF, named Loquat.

https://eprint.iacr.org/2024/868

Collaborative, Segregated NIZK (CoSNIZK) and More Efficient Lattice-Based Direct Anonymous Attestation

Defines collaborative, segregated, non-interactive zero knowledge (CoSNIZK). This notion generalizes the property of collaborative zero-knowledge so that the zero-knowledge property need only apply to a subset of provers during collaborative proof generation. The main contribution is the construction of a DAA based on the hardness of problems over module lattices as well as the ISISf assumption.

https://eprint.iacr.org/2024/864

Novel approximations of elementary functions in zero-knowledge proofs

In ZKP, all algebraic functions are exactly computable. Recognizing that, proceeds to the approximation of transcendental functions with algebraic functions.

https://eprint.iacr.org/2024/859

Generalized Indifferentiable Sponge and its Application to Polygon Miden VM

https://eprint.iacr.org/2024/911

Interests

Dark pool

Dark Pool 可以理解为一类平台的统称，这些平台使用增强隐私的技术，允许用户在不透露其身份或交易细节的情况下进行资产交易。下面的第一篇文章介绍了如何使用（门限）完全同态加密（Threshold Fully Homomorphic Encryption, TFHE）来构造一个暗黑的 Dark Pool，即使 Dark Pool 的运营者也无法查看订单详情。第二篇文章是对 Dark Pool 的一些介绍和延展。

https://blog.sunscreen.tech/building-a-truly-dark-dark-pool-2/
https://distributedresearch.substack.com/p/diving-into-dark-pools

ZKM’s Proving Service

ZKM 宣布发布其独家的证明服务，为开发人员提供高性能服务器的访问，这些服务器能够有效地处理生成零知识证明的密集计算要求。该服务专门针对 zkMIPS 进行了优化，zkMIPS 用于促进将 ZKP 功能集成到各种应用程序中。

https://www.zkm.io/blog/zkms-proving-service-breaking-down-the-barriers-for-proof-generation

Highlights

https://www.youtube.com/playlist?list=PLOEty2U8Y69Uzkd6MthUjWbOxQHzBAtCQ
https://www.youtube.com/playlist?list=PLOEty2U8Y69XR-KVpuDi4mCIOjBtUA-mQ
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.

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.

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

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

Kobi Gurkan: on the risk of circuit-specific setups

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

Nimue: a Fiat-Shamir library

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

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

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.

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/

Highlights

ZKProof 6 in Berlin

https://zkproof.org/events/zkproof-6-berlin/

Open-Binius by Ingonyama

Open-source hardware IPs for accelerating ZK proofs over binary fields.

https://github.com/ingonyama-zk/open-binius

Sonobe BTC

Using folding schemes for a provable bitcoin light client. Folding and proving 100,000 Bitcoin blocks with Nova via Sonobe library!

https://github.com/dmpierre/sonobe-btc

ZKThreads: A canonical ZK sharding framework for dApps

an application-level component allowing users to locally prove a batch of transactions and update the canonical state.

https://ethresear.ch/t/zkthreads-a-canonical-zk-sharding-framework-for-dapps/19619

SNARKnado

SNARKnado 用于验证比特币上的 SNARK，用基于SNARK的更像电路的协议取代了BitVM的RISC-V抽象。通过这种优化，可以将挑战-响应轮次减少到四个，从而将现有 BitVM RISC-V 设计改进了 8 倍以上。然而，与 BitVM2 不同的是，SNARKnado 不支持无需许可的挑战。

https://www.alpenlabs.io/blog/snarknado-practical-round-efficient-snark-verifier-on-bitcoin

Expander-rs

The Expander-RS cryptography library，is the open source rust version of Expander.

https://github.com/PolyhedraZK/Expander-rs

Updates

Noir v0.29.0 重大变化

use distinct return value witnesses by default
Bit shift is restricted to u8 right operand

https://github.com/noir-lang/noir/releases/tag/v0.29.0

Papers

Speeding Up Multi-Scalar Multiplications for Pairing-Based zkSNARKs

Revisiting the recent precomputation-based MSM calculation method proposed by Luo, Fu and Gong at CHES 2023 and generalize their approach, presented a general construction of optimal buckets. This improvement leads to significant performance improvements.

https://eprint.iacr.org/2024/750

More Embedded Curves for SNARK-Pairing-Friendly Curves

Showing how the problem of finding families of embedded curves is related to the problem of finding optimal formulas for subgroup membership testing on the pairing-friendly curve side. Then apply Smith's technique and Dai, Lin, Zhao, and Zhou criteria to obtain the formulas of embedded curves with KSS, and outline a generic algorithm for solving this problem in all cases; Provide two families of embedded curves for KSS18 and give examples of cryptographic size.

https://eprint.iacr.org/2024/752

Breaking Verifiable Delay Functions in the Random Oracle Model

Showing that VDFs with imperfect completeness and non-adaptive computational uniqueness cannot be constructed in the pure random oracle model (without additional computational assumptions).

https://eprint.iacr.org/2024/766

Clap: a Rust eDSL for PlonKish Proof Systems with a Semantics-preserving Optimizing Compiler

https://arxiv.org/abs/2405.12115

The Ouroboros of ZK: Why Verifying the Verifier Unlocks Longer-Term ZK Innovation

Researchers from Matter Labs outline a research program and justify the need for more work at the intersection of ZK and formal verification research.

https://eprint.iacr.org/2024/768

Instance-Hiding Interactive Proofs

The instance-hiding property requires that the prover should not learn anything about x in the course of the interaction. Investigating the properties and power of such instance-hiding proofs.

https://eprint.iacr.org/2024/776

Doubly-Efficient Batch Verification in Statistical Zero-Knowledge

https://eprint.iacr.org/2024/781

SmartBean: Transparent, Concretely Efficient, Polynomial Commitment Scheme with Logarithmic Verification and Communication Costs that Runs on Any Group

https://eprint.iacr.org/2024/785

A Note on Zero-Knowledge for NP and One-Way Functions

https://eprint.iacr.org/2024/800

Highlights

zkSNARKs in the ROM with Unconditional UC-Security

This paper proves that there exist zkSNARKs in the random oracle model (ROM) that unconditionally achieve UC-security.

https://eprint.iacr.org/2024/724

Relativized Succinct Arguments in the ROM Do Not Exist

This paper proves that relativized succinct arguments in the ROM do not exist. The impossibility holds even if the succinct argument is interactive, and even if soundness is computational (rather than statistical). Relativized SNARGs are a powerful primitive that, e.g., can be used to obtain constructions of IVC (incrementally-verifiable computation) and PCD (proof-carrying data) based on falsifiable cryptographic assumptions. This results rule out this approach for IVC and PCD in the ROM.

https://eprint.iacr.org/2024/728

Bain Capital Crypto Whiteboards

David Wong关于MPC (Multi-Party Computation) & Shamir Secret Sharing (SSS)的系列白板介绍视频。

https://www.youtube.com/playlist?list=PLRSMpO6IlBK1p3GMhbWEBmVfOFL-Fs4g1

Updates

DelphiusLab 发布 ZKWASM-Book

https://zkwasmdoc.gitbook.io/delphinus-zkwasm

Jolt 更新路线图

https://jolt.a16zcrypto.com/tasks.html

A proof-of-concept implementation of KiloNova

https://github.com/FranklinZty/KiloNova-poc

Noir v0.28.0

新的 min 和 max 函数简化了数值比较新的 as_array 方法简化了从切片到数组的转换新的 BarretenbergVerifier 类加速了证明验证，并支持验证密钥加载

变更日志: https://github.com/noir-lang/noir/releases/tag/v0.28.0
最新安装版本: https://noir-lang.org/docs/getting_started/installation/

Learning

图解 Lasso

看这个图能对 Lasso 有个框架的认识

图: https://excalidraw.com/#json=rxe_CEVy9pKi1OO6YaUKr,uWoUBAq26lkKj1akg5FbRg
对应的视频 https://www.youtube.com/watch?v=iDcXj9Vx3zY

为什么 Prover 不能在 Groth16 中作弊

这篇文章详细探讨了 Groth16 证明系统中的 Prover 为什么无法作弊，并且以一种与原始论文不同的方式证明了 Groth16 的 knowledge soundness 的性质。

https://hackmd.io/@chokermaxx/S1rh7EGeR

Notes on Collaborative zk-SNARKs

介绍 co-SNARKs。In Collaborative zk-SNARKs (co-SNARKs), the 3 parties $P_{1}$ , $P_{2}$ and $P_{3}$ each hold a piece of the secret data (secret witness $w$ ). They will then interact with each other into this MPC protocol to generate a single $π$ which is a zk-SNARK.

https://www.leku.blog/co-snarks/

Binyi Chen: LatticeFold - A Lattice-based Folding Scheme and Applications to Succinct Proof Systems

Binyi Chen 在 CMU Cylab Crypto Seminar 再次讲解 LatticeFold

https://www.youtube.com/watch?v=pre-nW3jawM

“Is Bandersnatch for Real?” by Antonio Sanso

presents a procedure to construct parameterized families of prime-order endomorphism-equipped elliptic curves that are defined over the scalar field of pairing-friendly elliptic curve families such as Barreto–Lynn–Scott (BLS), Barreto–Naehrig (BN) and Kachisa–Schaefer–Scott (KSS), providing general formulas derived from the curves’ seeds.

https://www.youtube.com/watch?v=aeDMk1XNzuw

A summary on the FRI low degree test

Polygon Labs的Ulrich Haböck对 [BSBHR18a]、[BSCI+20] 和 [BSGKS20] 等文献中的FRI low degree test和DEEP algebraic linking等技术进行了非正式的总结。总结基于[BSCI+20]带来的最新的健全性分析，讨论了实际安全参数的设置，FRI如何转化为多项式承诺方案，以及列表解码机制中DEEP采样的健全性。这篇文章能够帮助初学者快速理解FRI相关的技术要点和安全性设置。

https://eprint.iacr.org/2022/1216

Highlights

Building Cryptographic Proofs from Hash Functions

Alessandro Chiesa 和 Eylon Yogev 关于密码证明系统的重量级新书。其未来的历史地位恐怕不低于 Justin Thaler 的 Proofs, Arguments, and Zero-Knowledge。

This book provides a comprehensive and rigorous treatment of cryptographic proofs based on ideal hash functions. This includes notable constructions of SNARGs (succinct non-interactive arguments) based on ideal hash functions. For example, STARKs (scalable transparent arguments of knowledge) are an example of such SNARGs.

https://hash-based-snargs-book.github.io/

两种新的阈值加密方案

Silent Threshold Encryption 第一个方案不使用 iO/WE，完全避免了使用交互式设置。各方独立地生成其公钥对，但需要一个 KZG CRS（可验证的 zk-SNARK 公共参考字符串）。要进行加密，你只需要下载委员会的公钥+可以在加密时选择阈值，这还为我们提供了具有静默设置的时间锁加密。

paper

Batched Threshold Encryption 第二种方法可以实现批量解密密文，而这种方法的通信量与批量大小无关。通常情况下，如果有一个由 n 个参与方组成的委员会，他们需要通过 O(nB) 的通信量来解密 B 个密文，即每个参与方需要针对每个密文发送一条消息。但是，这个方法仅需要 O(n) 的通信量，即总体通信量与参与方数成正比，与密文数量无关。这种方法特别适用于加密的交易池场景，例如，在区块链技术中，需要快速解密整个区块的情况。简单来说，就像是无论我们要解密多少数据，所需要的沟通工作量都相当于只解密一个数据那么多。这样可以大大减少解密过程中的通信成本，提高整体效率。

Reckle Trees: Updatable Merkle Batch Proofs with Applications

Reckle trees, a new vector commitment based on succinct RECursive arguments and MerKLE trees. Reckle trees’ distinguishing feature is their support for succinct batch proofs that are updatable—enabling new applications in the blockchain setting where a proof needs to be computed and efficiently maintained over a moving stream of blocks. Assuming enough parallelism, our batch proofs are also computable in 𝑂(log𝑛) parallel time— independent of the size of the batch.

https://www.youtube.com/watch?v=lcWQHYox0qc
https://eprint.iacr.org/2024/493.pdf （已被CCS'24录用）

Polyhedra 开源基于 GKR 的证明系统 Expander

证明者性能在 Apple M3 Max CPU 上可达到每秒生成 5000 个 Keccak 哈希的证明。

https://expander.polyhedra.network/
https://github.com/PolyhedraZK/Expander

Updates

Binius: highly efficient proofs over binary fields 翻译及补充

来自 Harold & Jade 的翻译，并在原文的基础上补充了 RS-code 和二进制扩域相关的内容，V 在原文中简单介绍了 Plonky2 等协议来引出在小域上进行计算的优势，相信读者可以通过 Simple Binius ，Binary fields 和 Full Binius 这三节来完整的体会到 Binius 的威力和 Overview 。原文中的 Plonky2 部份由于不影响后续的理解，暂时没有校对。同时欢迎读者们通过在译文的仓库中留下 issue 来进行提问和交流。

Related Link

zkStudyClub: Accumulation w/o Homomorphism (Wilson Nguyen - Stanford, William Wang - NYU)

首个仅使用基于对称密码假设（Merkle Tree）的非同态向量承诺来构造的 Folding 方案。

https://www.youtube.com/watch?v=mQ0hZeJMAgo
https://eprint.iacr.org/2024/474

SP1 Testnet 的几个关键特性

SP1 Testnet 是一种针对开发者的快速、功能完整的零知识虚拟机（zkVM）。文章重点介绍了 SP1 Testnet 的几个关键特性：

性能与递归：SP1 Testnet 现在支持高效的 STARK 递归和链上验证，这使得它可以在任何 EVM 兼容链上快速生成端到端的零知识证明。
开源与 Rust 支持：SP1 是唯一一个完全开源的 zkVM，支持 Rust 标准库，开发者可以使用现有的 Rust crates 编写可验证的程序。
预编译中心架构：通过针对常见操作（如哈希、椭圆曲线运算等）的预编译中心架构，SP1 显著提高了区块链应用（如 ZK Rollups 和 ZK 桥接）的性能。
性能基准测试：文章还提供了 SP1 与其他 zkVMs（如 Risc0 和 JOLT）的性能比较，展示了 SP1 在生成 EVM 可验证证明的速度和效率上的优势。

Related link

Ingonyama 的新服务 ZaKi

本文介绍 ZaKi 如何通过使用最新的 ICICLE 库和专门配置的硬件，来提升零知识证明的计算效率和降低成本。

重点内容包括：

技术优势：ZaKi 利用 ICICLE 库（特别是其新变种 ICICLE-NG，无需 GPU 即可使用）来优化 ZK 特定工作负载的过渡，支持高核心计数 CPU 和尖端 Nvidia GPU。
性能提升：通过硬件加速，ZaKi 在最坏情况下比其他实例在有效成本性能上提高了多达 12.7 倍。
开发者支持：ZaKi 为开发者提供了一个已经优化好的托管环境，避免了硬件设置和配置的复杂性，使团队可以专注于他们的 ZK 应用。
持续改进和支持：随着开发者对平台越来越熟悉，他们将从 ICICLE 软件和硬件配置的持续更新中受益，后台处理这些更新，无需开发者承担常见升级的负担。
article link
Related info

Verifiable Compute: Scaling Trust with Cryptography

一篇系统性介绍可验证计算功能及用例的文章。

article link

A High-Level Technical Overview of Fully Homomorphic Encryption

Google工程师关于全同态加密最新最全的介绍。

https://www.jeremykun.com/2024/05/04/fhe-overview/

Trustless Audits without Revealing Data or Models

这篇论文提出了一个 ZkAudit 协议，支持证明 ML 模型或者数据集，目前支持 ImageNet 等数据集和 DNNs 等模型。

http://arxiv.org/abs/2404.04500

一个有意思的中心化地理位置猜测游戏。

玩家们试图在地图上准确指出一个隐藏的位置，但与传统的 GeoGuessr 不同，他们的确切猜测保持隐藏。通过零知识证明，游戏验证猜测是否落在指定的接近实际位置的范围内。程序采用 Noir 开发并编译，并且包含一个应用所需要的前端部分代码，对于想学习一个完整 app 开发的同学可以试试。

link

Highlights

Binius

highly efficient proofs over binary fields

来自 Vitalik Buterin，指明方向:

https://vitalik.eth.limo/general/2024/04/29/binius.html

Tower field and commitment in binius

来自 Wang Yao 的分享，学习 binius 的材料:

视频链接 https://youtu.be/X_kmmbBY6rQ
Ref：https://www.ulvetanna.io/news/binius-hardware-optimized-snark
Paper：https://eprint.iacr.org/2023/1784

Updates

On Proving Pairings

基于配对的协议被广泛使用，但在实际应用中配对计算成本过高依然是一个很大的问题。本文提出了一种高效的方式去证明椭圆曲线配对关系。

配对验证最后的求幂步骤可以被替换为更高效的“residue check”，并且合并到“Miller loop”中。
通过预计算必要的行来降低“Miller loop”的成本，并且当预先固定第二配对参数时，会相当高效。
如何通过组合商来改进[gar]的协议，从而更有效地证明更高阶关系，这些技术也自然延续到配对验证中。
Paper Link

Vision Mark-32: A ZK-Friendly Hash Function Over Binary Tower Fields

Irreducible（原 Ulvetanna）和 3MI Labs合作，提出新的 ZK 友好哈希函数--Vision Mark-32。这是一种面向算术化的哈希函数，专为与 Binius 一起使用而设计。Vision Mark-32 是 Vision 结构的一个特殊实例化，利用二进制塔域的独特性质来实现硬件的高性能实现，同时在 Binius 证明系统中保持高效可验证性，是对 Binus 论文提出的 Grøstl 哈希函数进一步地可以降低验证成本和证明大小的优化。
Link
paper

Keelung

一个基于 Haskell 的 ZK 开发的工具. 得益于 Haskell 强大的函数式编程能力，你可以通过基础的内置数据类型，复合成复杂的数据结构。目前基隆的默认后端使用的是 Aurora，开发者正在支持 Groth16 和 PLONK。0.21 版本已经支持了绝大部份的算法，比较，位操作。0.22 版本将支持 slicing 和 joining。喜欢 Haskell的同学可以尝试一下。

gitbook

Proof of Passport

护照证明让用户可以扫描政府颁发的护照中的 NFC 芯片，并证明 zk-SNARK 中签名的正确性。这解锁了两个有趣的用例：

对于抗女巫攻击，护照证明可以提供唯一身份的来源。
为了身份和隐私，护照证明允许选择性地披露私人数据。例如，用户可以透露他们的国籍或出生日期，而无需透露任何其他私人信息。
Github Link

Justin Thaler 关于 Sumcheck/LASSO/JOLT 最新的两个播客

Introducing Expander: The Fastest GKR Proof System to Date

Polyhedra Network 推出了新的开源 ZK 证明系统 Expander，其生成速度打破现有的世界纪录，为实现 ZKVM 和 ZKML 提供了基础设施。

Expander 使得任何规模的项目都能高效、安全、低成本地处理数据。同時，它为 AI Layer1 的实现提供了强大的支持，并且让用户使用手机支持 AI 分布式算力，推动 AI 和区块链技术的深度集成。

link

Highlights

理解 Lasso

Github Link 郭老师的理解 Lasso 系列文章，将 Lasso 总共分成四个不同的 Indexed Lookup Arguments 协议：
Lookup Arguments based on Offline Memory Checking
Lookup Arguments based on Spark
Lookup Arguments based on Surge
Lookup Arguments based on Sparse-dense Sumcheck

并单独对这些协议进行了解析。

Updates

Ulvetanna 现已更名为 Irreducible

Irreducible 最近发布的基准测试显示，在没有使用 Binius 的情况下，他们的 Polygon Hermes FPGA 证明器 (Plonky2) 就要比 GCP 参考实例快 40%，而且比 spot 用例更便宜。这个基准测试通过将低度扩展和叶哈希计算迁移到 FPGA 上，同时在一个 64 核 CPU 上完成其他所有操作。

出处：

https://twitter.com/gakonst/status/1783589455271739678

Hadamard Product Argument from Lagrange-Based UnivariatePolynomials

这篇论文提出了一种新方案，用于证明两个向量的 Hadamard 积关系，作为基于一元多项式的 SNARKs 的一个子协议。证明者使用线性密码学操作生成包含对数场元素的证明。验证需要对数密码学操作和固定数量的双线性群配对。该方案的构建基于 Lagrange 形式的 KZG（Kate, Zaverucha和Goldberg在2010年Asiacrypt上的工作）承诺和折叠技术。通过在 Lagrange 形式的一元多项式上使用折叠技术，构造了一个内积协议，通过精心选择适合折叠技术的随机多项式，从内积协议构造了 Hadamard 积协议，提供了一种验证线性代数关系的替代方法，该协议的具体证明大小优于以往工作。

paper：https://eprint.iacr.org/2024/613

Noir 更新到 v0.27.0

重大变更：Brillig 实现了类型化的内存这一版使 "Brillig" 更符合 AVM 的标准，并且删除了 arithmetic.rs 中的截断操作。

相关链接：https://github.com/noir-lang/noir/releases/tag/v0.27.0

一季度 ZK 前沿研究汇总

STIR: Reed–Solomon Proximity Testing with Fewer Queries
Beyond the Circuit: How to Minimize Foreign Arithmetic in ZKP Circuits
Circle STARKs
SoK: What don’t we know? Understanding Security Vulnerabilities in SNARKs
zkPi: Proving Lean Theorems in Zero-Knowledge
Parallel zkVM

出处:

https://twitter.com/zkv_xyz/status/1782832332862263454

zkSummit 11 系列 talk 已全部上线

出处: https://www.youtube.com/playlist?list=PLj80z0cJm8QFy2umHqu77a8dbZSqpSH54

Updates

Are Verkle proofs ZK-friendly?

Daniel Lubarov探讨Verkle 证明的 ZK 友好性的文章。结论：与二进制 Merkle 证明相比，很难说哪个对 ZK 更友好，会归结为一堆实现细节.

Link

Sonobe

Sonobe 是由 0xPARC 和 PSE 共同实现的一个模块化库，用于以Incremental Verifiable computation (IVC) 方式的折叠电路实例上。 Sonobe 是一个模块化库，用于以增量可验证计算（IVC）方式折叠电路实例。它具有多种折叠方案和决策器设置，允许用户选择最适合他们需求的方案。当前已经实现的折叠方案包括Nova及CycleFold（包括链上验证代码），接下来会继续实现 HyperNova 和 ProtoGalaxy。 Sonobe 被认为是一项探索性工作，旨在推动折叠方案的实践方面并推进链上（EVM）验证。但由于目前还尚未被审计，因此目前还尚不能用在产品开发上。

Link

State of ZK Report

2024 Q1 的 State of ZK Report, 介绍了 ZK 在 Bitcoin 的应用, 提到了 SP1 的发布等.

Link

zkWasm

Delphinus Lab开源了其zkWasm Prover，其基于Halo2对WASM指令集进行高度定制优化，支持Halo2 GPU加速、GWC和Shplonk两种多项式承诺方案，可在17秒内生成1百万WASM指令(NVIDIA 4090 GPU).

Link

Highlights

https://github.com/a16z/jolt

a16z 开源的的一个新的zkvm, 实现了 lookup singularity，对于开发者扩展来说是一个非常好的消息。相比较大多数项目工作在31bit或者64，其工作在一个256-bit field上，理论上可以实现更偏移的递归，并且保留了对未来64位数据的优化空间。

Quantum Algorithms for Lattice Problems

清华大学交叉信息研究院陈一镭助理教授提出了一个破解格密码的量子算法。该算法能够解决格上的近似最短向量问题（Approximate Shortest Vector Problems in Lattices, 简称 Lattice Problems）以及与之等价的带错误学习问题（Learning with Errors,简称LWE）。这项工作仍在同行评议中。如果被验证为正确，将为这个悬而未决的问题给出肯定的答复。它在科学上的意义将是双层的: 第一，这将是自30年前 Peter Shor 提出大数分解的量子算法以来，最重要的量子算法突破。第二，这将对美国NIST过去10年来选择后量子密码设计的思路产生颠覆性的影响，因为多数选出的后量子密码方案都是基于 Lattice Problems 或 LWE。陈一镭的工作无疑将使他们安全性受到质疑。（原文https://mp.weixin.qq.com/s/IdSmmJI2npQeRORRHHAScQ）

paper

Updates

LaZer: a Lattice Library for Zero-Knowledge and Succinct Proofs

一个便于协议设计师轻松使用基于格的SNARKs和零知识证明（ZK-proofs）的库。该库的基础是代数运算，最近效率最高的基于格的SNARKs和零知识证明就是建立在这些运算之上的。这些底层实现以及零知识协议都是用C语言编写的。随后，创建一个Python封装器，使协议设计师能够轻松创建实例和生成证明，同时使用高效的C语言操作，以便能够完全在Python中编写他们的协议，而不会在效率上损失太多

A library that allows for easy consumption of lattice-based SNARKs and ZK-proofs by protocol designers. The foundation of the library consists of algebraic operations upon which the most efficient recent lattice-based SNARKs and ZK proofs are built. These low-level implementations, as well as the ZK protocols, are written in C. Then create a Python wrapper that allows protocol designers to easily create instances and create proofs, as well as use the efficient C operations to be able to write their protocols entirely in Python without sacrificing much in the form of efficiency.

Link

A Time-Space Tradeoff for the Sumcheck Prover

这篇文章介绍了基于 multilinear sumcheck 协议的一类证明算法 Blendy，它实现了新的时间与空间的权衡算法。已有的证明算法中，时间和空间使用规模要么需要时间上O(NlogN)，空间上O(logN)，要么需要时间上O(N)空间上O(N)。新算法 Blendy 将n轮分为k个阶段来处理，通过在不同的阶段使用预计算和分阶段处理来优化性能，有效地平衡了执行时间和所需存储空间，最终实现了运行空间上需要O(kN) ，而空间上仅需要O(N^{1/k})。

paper

Proving the correct execution of concurrent services in zero-knowledge

Jolt 中为了处理对 RAM（和寄存器）的读/写，使用了 Spice 内存检查证明，该证明与 Lasso 本身密切相关。它们都基于离线内存检查(offline memory checking)技术，主要区别在于 Lasso 支持只读内存，而 Spice 支持读写内存，因此开销更高。

paper

可验证推理的水印和指纹的综述

一篇关于 AI 模型推理的可验证性的总综述，这个问题即怎么确保你这个推理结果是由某个特定的模型推理出来，这点无论是对私有大模型的订阅用户，或者是去中心化大模型服务商来说都很重要。文章提出了不同于 zk 的另一个传统方法，即水印方法。有兴趣的同学可以根据这篇综述涉及的链接继续阅读。

Link

Highlights

基于对称密钥假设的有上限深度累积方案及其优化

所有以往的累积方案（accumulation schemes）都依赖于同态向量承诺（homomorphic vector commitments），这些承诺的安全性基于公钥假设。本文中提出通过构建一个来自非同态向量承诺的累积方案，该方案仅基于对称密钥假设（例如 Merkle 树）。此方案通过利用对承诺向量的错误纠正（error-correcting）编码进行抽查（spot-checks）来克服对同态的需求。与以往的累积方案不同，此方案仅支持有限数量的累积步骤。但即使深度有上限的累积方案（accumulation schemes），也足以构建携带证明的数据（IVC的泛化）。另外本文还展示了几种对 PCD 构建的优化，显著提高了效率。本文的主要贡献主要包括：（1）引入了一种新的有上限的深度累积方案（bounded-depth accumulation schemes）概念，支持有限数量的累积。（2）有上限的深度的携带证明数据（PCD），根据已知结果[BCCT13]，足以获得多项式深度的增量可验证计算（IVC）。（3）从任意（非同态的）向量承诺方案（例如基于随机预言机的 Merkle 树）和任何线性代码构建了高效的有上限的深度累积方案。这种 PCD 方案需要更少的证明者开销，并实现了可信的后量子安全。（4）为实例化的 PCD 方案提供了几种优化，包括支持“批量”累积（'batch' accumulation）、从低深度 PCD 到 IVC 的新低开销编译器，以及一种新的混合 PCD 方案，将低深度 PCD 与任何基于 SNARK 的 PCD 方案结合。

paper

a note on the elliptic curve pairing checks in zero knowledge proofs

这篇文章主要探讨了零知识证明中椭圆曲线配对检查的一些重要概念和应用。它着重介绍了在零知识证明系统中使用椭圆曲线配对检查的技术，并深入讨论了其在密码学中的作用和应用。文章通过对配对检查的基本原理、常见应用场景以及一些相关概念的解释，为读者提供了对这一领域的深入理解和探索的入口。

link

Do You Need a Zero Knowledge Proof?

如果你正在探索零知识证明（ZKPs）的世界，想要了解它们如何在不同情境下发挥作用，我强烈推荐你阅读这篇文章。

它批判性地分析了 ZKPs 的适用性，将它们分为几种类型：SNARKs（简洁的非交互式知识论点）、提交然后证明 ZKPs、MPC in-head 和 Sigma 协议。每种类型都提供了不同的权衡和好处。文章通过一种创新的流程图方法，帮助你确定最适合你需求的ZKP系统，并提出了一套技术应用要求。它深入探讨了外包计算、数字自主身份和网络中的 ZKPs 这三个主要用例，提供了关于 ZKPs 其他应用的高层次概述，并探讨了它们在更广泛领域内的含义和机会。

这篇文章能够帮助你理解选择合适的 ZKP 系统所涉及的决策过程，明确这些加密工具何时以及如何在不同领域中有效使用，以及何时应该避免使用这些工具。对于那些寻求深入了解 ZKPs 潜力和局限的人来说，这篇文章是一份宝贵的资源。

paper

Updates

Aleo IP core.

最近 Ingo 公布了关于 Aleo 的最新产品 - Aleo IP core。 Aleo 首创了 KZG 谜题的概念，其中，作为 Aleo 共识机制的一部分，证明者竞相解决 ZK 币库谜题。最具成本效益的证明者可以获得更多奖励。这种独特的机制是迄今为止唯一能够产生公平竞争环境和对 ZK 证明的足够需求的实例 Aleo IP 是面向运行 Aleo 测试网难题的 ASIC 平台。Aleo IP 采用参数化 RTL 设计，可实现最先进的性能和功效。该设计是使用与运行频率为 1.2 GHz 的 TSMC 7nm 工艺兼容的工具进行综合的，包括单个矿工管理器负责用户界面和整个逻辑的管理与Aleo 核心数量。链接https://medium.com/@ingonyama/product-announcement-aleo-ip-core-e7181ca31094

bitvm1 与 bitvm2 的比较

bitvm1版本： Verifier 不断要求 Prover 揭示他指定步骤的中间状态，从而在 logN 次挑战之后可以确认 Prover 作恶了没。

两方参与挑战，链上交互次数为logN次
链上采用的验证的是 RISC_V 指令集执行的不正确性
在网络开始之前需要 Prover 和 Verifeir 提前的 presign，网络一经启动就无法再更改

bitvm2版本: Prover直接在链上用一笔交易揭示所有的中间状态之后，如果任何人发现揭示的某一步中间状态执行不正确都可以通过 f(x)!=y 的逻辑来解锁对应的Prover质押金额

任何人都可以 premissionless 的参与挑战 prover
链上交互次数大大减少
不再验证采用 RISC_V 指令集，而是采用在链上写一个原生的 zk verifier
因为每个 tapleaf 的 script 大小是 400kb(比特币节点限制)，意味着链上每 400kb 的验证 script 就 prover 需要揭示一个中间状态，同时又因为缺少 op_loop 指令，op_mul 指令以及 op_cat，会导致比特币无论是在做 groth16 verifier (椭圆曲线运算贵，并且 field size 是 254bit )或者在做 stark verifier (计算 Merkle Path 的困难)都会出现比较多中间状态的问题，这样 prover 需要花费更多的手续费来证明他是对的。 -link

其他

Constant-Size zk-SNARKs in ROM from Falsifiable Assumptions - Roberto Parisella：https://www.youtube.com/watch?v=VPAA85Mtt2s
Great work by @weikengchen: We now have finite field arithmetic for the M31 and Baby Bear fields, as well as for their degree-4 extensions.These are the basis for implementing STARK verifiers on Bitcoin.

link: https://twitter.com/robin_linus/status/1771809562246463577

Updates

Perfect Zero-Knowledge PCPs for #P

这周有一些关于计算复杂性理论的讨论出来, Kurt Pan 也写了一个关于PSPACE的随笔。而这篇文章讨论了一个针对 #P 族编程语言的 ZK PCP 构造的问题。如果对PCP陌生的同学，可以看看链接2的文章, 交互式证明系统(IP)的零知识性质可以细分为完美零知识PZK, 统计零知识SZK, 计算零知识CZK。历史上的一些重要理论结果都与此相关，比如：CZK = IP = PSPACE，PZK-MIP = MIP = NEXP, MIP*=RE，PCP定理等。一个ZK-PCP就是一个具有零知识性的PCP。类似的，一个PCP证明系统也可以细分成PZK,SZK,CZK（注意目前认为ZK-IPs和ZK-PCP无直接关系）。即使现在也有不错的相关理论结果出现，比如SZK-PCP[poly, poly] = NEXP，但对于PZK-PCP类的结构依然不甚清晰，是否有BPP之外的语言存在PZK-PCP构造依然是开放问题。

这篇论文是来自资深理论密码学家/计算复杂性理论家Tom Gur和Nicholas Spooner的一篇重要工作：为任意#P语言构建出了PZK-PCP，从而得到了首个BPP外语言的PZK-PCP构造，且同时对任意多项式时间恶意验证者实现了非自适应性和（完美）零知识。

论文基于 ZK sumcheck IOP 来实现：为了验证在 ${0, 1}^{m}$ 上的 $\sum F$ （对于算术电路F），证明者发送一个随机的 mask $R$ ，使得 $\sum R = 0$ ；验证者选择一个随机数 $c$ ；然后他们对 $c F + R$ 进行 $s u m c h ec k$ 。交互过程在这里很重要, 如果我们试图通过让证明者为多个不同的 $c$ 发送 $c F + R$ 的 $s u m c h ec k$ 证明来消除交互，那么零知识性将会丧失(因为sumcheck是线性的)。而论文利用了求和检查声明的置换不变性来打破这种线性关系。

Towards Verifiable FHE in Practice

Zama团队关于可验证FHE最新的一篇工作。FHE虽然可以对密文空间数据进行任意计算，但如果不能对该计算生成计算完整性证明，则无法在恶意敌手存在的环境下（比如云计算）得到真正的落地应用。在这项工作中，Zama团队使用plonky2设计了一个证明bootstrapping操作（FHE中最重要的操作）的算术电路，从而首次在实践中对FHE使用 SNARK 进行了计算完整性验证。在 AWS C6i.metal 实例上证明该电路，生成时间大约20分钟，证明大小约为 200 kB，验证时间不到 10 毫秒。该结果表明该技术路线可行，但依然是一个很慢的结果，未来改进空间依然巨大。

paper

BitVM ZK Verifier

BitVM 最近开源了他们的 ZK Verifier，以比特币上证明任何事情为目标，其主要流程如下：

用 RISC0 客户端程序创建STARK证明
将STARK证明包装成Groth16证明，并在在C语言中编写其对应的Groth16验证器
将验证器编译为rv32i指令集，从而转化为BitVM指令集

就第二部来看, 似乎如果有更多的工具可以减少开发 verifer的工作会更靠。

ZK Verifier

Client-side proof generation

这篇文章探讨了用于证明私有函数正确执行的客户端（资源受限）证明生成，并解释了它与通用rollup的证明生成的区别。隐私保护的zk-rollup的证明生成与通用zk-rollup有很大的区别。

这篇文章比较简单易懂，对于zk入门学习者可以参考文中的例子增加对 zk 的理解。笔者感兴趣的地方在于 Goblin Plonk（可能笔者之前没有了解过），他允许允许资源受限的证明者构建具有多层递归的zk-snark，其核心逻辑是将每个递归层的昂贵操作（如椭圆曲线操作）被推迟到最后一步，而不是在每个层次上执行。链接2是对Goblin Plonk的进一步参考资料。

Universal Proof Aggregation protocol

NEBRA 发布了Universal Proof Aggregation protocol (通用证明聚合协议)，使用零知识证明本身来扩展零知识证明验证。其核心思想是使用高效的递归SNARK（IVC/PCD）来获得近乎无限量的递归。这意味着可以在链外递归地证明多个零知识证明，并在链上仅验证单个聚合证明。

link

一些学习资料

Getting Started with RISC Zero

STARK MATH

Highlights

Mangrove: A Scalable Framework for Folding-based SNARKs

提出了一个构建高效的基于 folding 的 SNARK 框架。

首先，为 NP 语句开发了一个新的「均匀化」编译器，将任何多项式时间计算转换为一系列相同的简单步骤。由此产生的均匀计算特别适合通过基于folding的 IVC 方案进行处理。

其次，对基于 folding 的 IVC 进行了两项优化。第一个方法通过重构应用 folding 的关系来减少 IVC 的递归开销。第二个采用「commit-and-fold」策略来进一步简化关系。这些优化共同得到了具有许多良好性质的基于 folding 的 SNARK。

该方案使用常数大小 CRS。证明者具有

(i) 低内存占用， (ii) 仅对数据进行两次传递， (iii) 高度可并行化，以及 (iv) 具体高效。微基准测试表明，证明时间与领先的单体 SNARK 相当，并且比其他流式 SNARK 快得多。在笔记本电脑上，对于 2^24 (2^32) 个门，Mangrove 证明者预计需要 2 分钟（8 小时），峰值内存使用量约为 390 MB (800 MB)。

paper:https://eprint.iacr.org/2024/416

Stwo

Stwo（STARK Two）是 Starknet 下一代证明器的名称，旨在增强、加速并最终取代当前的证明器 – Stone（STARK One）。Stwo 的效率预计是 Stone 速度的 100 倍，将使用 Circle STARK 方案。Circle STARK 通过定义在 Mersenne 质数 M31（素数 2^31-1）上的圆上点的序列，找到了一个能够产生大量点且符合特定重复结构的方法。这种结构是高效 STARKs 的关键，因为它允许使用快速递归算法。

link: https://elibensasson.blog/2024/03/15/why-im-excited-by-circle-stark-and-stwo/

Updates

Sindri - ZKP API service

ZKP API 服务 Sindri 宣布和 IDE 工具 Remix 集成，旨在通过将 Sindri 的强大 API 嵌入到开发者已经依赖的基于浏览器的 Remix 解决方案中，简化零知识（ZK）开发过程。

Sindri是一个旨在简化零知识证明（ZKP）生成的 API 服务。它通过提供易于使用的 API 调用，将复杂的 ZKP 开发变得更简单。Sindri 还利用 GPU 和新算法来解决证明生成的瓶颈，提供与公开可用基准相媲美的性能。

Remix 是一个流行的开源 Web IDE（集成开发环境），专为智能合约开发和以太坊应用编程设计。它允许开发者直接在浏览器中编写、测试和部署智能合约，无需安装额外软件。

通过本次集成，开发者可以在浏览器中开发 ZK 电路和应用程序，并在浏览器中生成并验证 ZK 证明。为了进一步加快开发过程，此集成为内置于 Remix 中的 Circom 开发提供了预构建的帮助程序模板，这些模板可以允许开发人员直接进入构建。

link：https://sindri.app/blog/2024/03/13/remix-sindri/

BabySpartan

Setty 在 PSE 对最新的 BabySpartan 工作进行了介绍。

BabySpartan 是 SuperSpartan 和 Lasso 的简单组合。通过对 PCS 进行优化，可确保证明者以加密方式仅承诺「小」数值，避免大数值计算开销。

link：https://www.youtube.com/watch?v=6VuYqRcnhbA

zkKYC

相关 resource:
https://twitter.com/RiscZero/status/1767366884746469864 https://www.risczero.com/blog/
decentralized-identity-verification-with-zkkyc-and-soulbound-nfts
https://www.youtube.com/watch?v=oGjJ-rTFtQc&t=39s https://eprint.iacr.org/2023/296

Highlights

Parallel Zero-knowledge Virtual Machine

scroll 团队在zkvm的性能极限上的探索:

证明系统上采用了并行GRK
更小的域算术
在opcode级别进行成本计算

小编认为除此之外，本文还有两个亮点，在第四章阐释了非对称证明协议，并基于此设计的 non-uniform 的 prover 是更好的选择。在第六章介绍了一个 zkvm 的设计以及如何追踪一个程序的执行并让 trace 更接近 circuit。对zkvm设计有兴趣的同学推荐阅读。

Paper

Updates

Succinct’s Platform, Prover Network and SP1

本次zk播客采访了最近很火的 Succinct 团队的创始人，介绍了他们做 alpha.succinct.xyz - 一个帮助开发者自动构建证明器，存储电路图的开发者工具 - 的动机。也介绍了他们对未来 zk 技术和市场的一些想法。

podcast

Blitzar

Blitzar 是一个可用于GPU加速 zk 相关的数学计算的库，提供了如下功能:

Curve-25519 and Ristretto25519
Inner Product Argument

接口和使用挺方便的，有兴趣和需求的同学可以体验下。

github

MACI v1.2.0 更新

MACI 是一个以太坊工具，为链上投票提供隐私和反串通能力。如果您对MACI不熟悉，我们建议先阅读我们的文档，了解背景信息和技术细节。

MACI通过使用加密和零知识证明（zk-SNARKs）来隐藏每个人的投票方式，同时公开揭示最终结果，从而解决了这个问题。用户无法证明他们投票选择了哪个选项，因此贿赂者无法可靠地相信用户投票了他们偏好的选项。例如，选民可以告诉贿赂者他们将投票支持选项A，但实际上他们投票支持选项B。无法可靠地证明选民实际投票了哪个选项，因此贿赂者对支付选民按照他们的意愿投票的动机较小。

在 1.2.0 更新里面，

支持非二次投票的投票
一种新的抵御女巫攻击的机制, 用户必须满足设定好的的条件才能参与投票。例如，用户可能需要证明拥有某个特定的NFT，或证明他们已经通过某种人证验证。

Resource:

doc
github

Highlights

Circle STARKs

Traditional STARKs require a cyclic group of a smooth order in the field. This allows efficient interpolation of points using the FFT algorithm, and writing constraints that involve neighboring rows. The Elliptic Curve FFT (ECFFT, Part I and II) introduced a way to make efficient STARKs for any finite field, by using a cyclic group of an elliptic curve.

传统的STARKs需要在域中具有平滑阶数的循环群。这样可以使用FFT算法高效地插值点，并编写涉及相邻行的约束条件。椭圆曲线FFT（ECFFT，第一部分和第二部分）引入了一种使用椭圆曲线的循环群来制作任何有限域的高效STARKs的方法。

We show a simpler construction in the lines of ECFFT over the circle curve $x^{2} + y^{2} = 1$ . When $p + 1$ is divisible by a large power of 2 , this construction is as efficient as traditional STARKs and ECFFT. Applied to the Mersenne prime $p = 2^{31} - 1$ , our preliminary benchmarks indicate a speed-up by a factor of $1.4$ compared to a traditional STARK using the Babybear prime .

我们在椭圆曲线 $x^{2} + y^{2} = 1$ 上展示了一种更简单的构造方法。当 $p + 1$ 能被很大的 2 的倍数整除时，这种构造与传统的STARKs和ECFFT一样高效。当使用了Mersenne素数 $p = 2^{31} - 1$ ，我们的初步基准测试表明与使用Babybear素数的传统STARK相比，速度提升了 1.4 倍。

Paper

SP1 Reth

SP1 Reth是一个100%开源的POC，展示了Rollup 方案如何使用SP1构建一个高性能（type-1, bytecode compatible）的zkEVM，只需不到2000行可维护的Rust代码。通过利用SP1的开源、可定制的预编译系统，SP1 Reth实现了难以置信的性能（平均以太坊交易的证明成本约为0.01-0.02美元），未来还将有数量级的改进。

benchamrk

Updates

ZKBank

zkBank 是 zkSecurity的 David 发布的基于gnark框架的一个 challenge。以下是挑战地址和内容

Alice is a sneaky one, she's been trying to send more than what she has to Bob's account. Good thing that we use zero-knowledge proof to enforce the integrity of our transfer. We just want to make sure that Bob can get 100,000 worth of coins or more. Can you help us verify Alice's proof?

github

New accumulation schemes for large memories and deterministic computations

Benedikt Bünz 和他的博士生的最新的 folding 的工作, 突破了"witness barrier"和"lookup singularity". 该工作展示了如何通过仅提交4 small elements 来进行读写内存。以及如何避免提交中间见证。

The United Rollups of Ethereum

ETH基金会的研究员Justin Drake 探讨了 ETH Rollup的方方面面，MEV，递归证明，闪电贷等等，也提及了不少关于 zk 技术的应用和思考。

youtube link

Speeding up M31 (2^31 - 1) arithmetic on different CPU architectures for Plonky3

作者优化了 dot product 和 sum 两个操作，其核心原理在于延迟计算后的 reduce（规约）操作，而是在累积到一个 64bit 的寄存器中，在真正需要的时候进行规约，从而可以减少N+1个指令到一个指令。作者在 neon 和 AVX 上都实现了上述优化。值得阅读和参考。

加速效果是惊人的，对于 Mersenne 可以达到2.6倍以上

基于zk-SNARKs的大规模匿名电子投票方案zkConvex

This is a large-scale voting scheme that enhances privacy in Convex governance. It can effectively protect voter privacy while preventing vote-buying behaviors. This scheme uses recursive zkSNARKs implemented on pair-friendly elliptic curves to create a chain of proofs. At each step, the proof is passed to a new voter, who adds their own knowledge statement to it, ensuring that these proofs can still be verified by the verifier in constant or polylogarithmic time. The use of recursive zkSNARKs significantly improves system performance to support large-scale voting activities.

一种在Convex治理中增强隐私的大规模投票方案。能够有效地保护选民隐私，同时防止投票买卖的行为。这个方案基于配对友好椭圆曲线的循环实现递归zkSNARKs，创建了一个证明链。在每一步中，证明都会传递给一个新的选民，每个选民在其中添加自己的知识声明，同时确保这些证明仍然可以由验证者在恒定或多对数时间内验证。通过使用递归zkSNARKs能够显著提高系统性能，以支持大规模的投票活动。

link

ZKML Benchmarking 框架

一个在Setup， Proving time， Memory usage 和 Model accuracy 进行Benchmark的方法和报告。报告宣称（这是 EZKL 的报告），EZKL在各种模型的证明时间方面，相对于 RISC0 和 Orion 表现出显著的性能效率。导致这种效率的关键因素包括实现了高效的 logUP 和 einsum 参数以及其非虚拟机方法。如果你在进行zkml选型或开发可以参考一下这篇文章。

link

ZKP2P

这个项目来源第312期的Zero Knowledge Podcast，这个项目利用了Venmo的支付确认邮件的 DKIM 签名，用来证明SHA256、电子邮件正则表达式和RSA。这里有趣的地方在于他们利用正则表达式提取出关注的数据片段（价格），并用 zk regex 证明这个数据片段在那封来自venmo的电子邮件中。