ZK Insights | 7th July 2024

Highlights

Adi Shamir: Wolf Prize Laureate in Mathematics 2024

恭喜 Shamir 由于密码学的数学基础等重要贡献，荣获本年度的沃尔夫数学奖。

• https://wolffund.org.il/adi-shamir/

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

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 全天候开源模糊测试计划。

• https://ethresear.ch/t/releasing-constantine-v0-1-0-a-modular-cryptography-stack-for-ethereum/19990

2 .com Blog

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

• https://2π.com/

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

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

• https://www.alvarorevuelta.com/posts/fft-polynomials

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

Alex Williams 在 ACM 会刊上对零知识证明在区块链中的应用和限制进行了简明的总结。

• https://cacm.acm.org/article/zero-knowledge-proofs-and-their-role-within-the-blockchain/

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

• https://medium.com/@ingonyama/sumcheck-and-open-binius-35220e5bd03a
• https://hackmd.io/@suyash67/B1npBL_LR

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

• https://blockworks.co/news/starkware-polygon-labs-stwo-zk-prover
• https://starkware.co/starkware-new-proving-record/

Delegated Spartan

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

Ingonyama CUDA Mini Course

• https://www.youtube.com/watch?v=SMmimEie89w
• https://www.youtube.com/watch?v=n9MYnq-9hdc

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

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

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

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

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