Highlights Introducing the ZK Catalog https://medium.com/l2beat/introducing-the-zk-catalog-7ac6f22889c0 https://l2beat.com/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/

Highlights Luca Trevisan (1971-2024) https://windowsontheory.org/2024/06/19/luca-trevisan-1971-2024/ https://scottaaronson.blog/?p=8057 https://blog.computationalcomplexity.org/2024/06/luca-trevisan-1971-2024.html 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

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.

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.

Highlights ZKProof 6 in Berlin (video list) 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

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

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

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

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 的材料:

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 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） 验证。 但由于目前还尚未被审计，因此目前还尚不能用在产品开发上。

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

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

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$上的$∑F$（对于算术电路F），证明者发送一个随机的 mask $R$，使得$∑R = 0$；验证者选择一个随机数$c$；然后他们对$cF+R$ 进行$sumcheck$。交互过程在这里很重要, 如果我们试图通过让证明者为多个不同的$c$发送$cF+R$的$sumcheck$证明来消除交互，那么零知识性将会丧失(因为sumcheck是线性的)。而论文利用了求和检查声明的置换不变性来打破这种线性关系。 paper PCP Theorems

Highlights Mangrove: A Scalable Framework for Folding-based SNARKs 提出了一个构建高效的基于 folding 的 SNARK 框架。 首先，为 NP 语句开发了一个新的「均匀化」编译器，将任何多项式时间计算转换为一系列相同的简单步骤。由此产生的均匀计算特别适合通过基于folding的 IVC 方案进行处理。 其次，对基于 folding 的 IVC 进行了两项优化。第一个方法通过重构应用 folding 的关系来减少 IVC 的递归开销。第二个采用「commit-and-fold」策略来进一步简化关系。这些优化共同得到了具有许多良好性质的基于 folding 的 SNARK。 该方案使用常数大小 CRS。证明者具有

Highlights Parallel Zero-knowledge Virtual Machine scroll 团队在zkvm的性能极限上的探索: 证明系统上采用了并行GRK 更小的域算术 在opcode级别进行成本计算 小编认为除此之外，本文还有两个亮点，在第四章阐释了非对称证明协议，并基于此设计的 non-uniform 的 prover 是更好的选择。 在第六章介绍了一个 zkvm 的设计以及如何追踪一个程序的执行并让 trace 更接近 circuit。对zkvm设计有兴趣的同学推荐阅读。

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