ZK Insights | 28th July 2024

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).

• https://vitalik.eth.limo/general/2024/07/23/circlestarks.html
• 中文翻译：https://mp.weixin.qq.com/s/g6hcok1tJVIIOSoz3dxRFQ

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.

• https://x.com/warlock_xyz/status/1813680134538359088
• https://github.com/warlock-labs/noether

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

*感谢 Kurt、liquan.eth、Harry、权 对本期 ZK Insights 的特别贡献！