2024-07-21 zk-insights Weekly

Highlights

Pairings for the Rest of Us

文章基于作者从各种公开课程和资料学习的经验，介绍了基于域扩展的椭圆曲线配对的基础概念，重点包括弗罗贝尼乌斯自同态和 Trace 映射，以帮助建立 $\mathbb{G}_1$ 和 $\mathbb{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 $\mathbb{G}_1$ and $\mathbb{G}_2$ and implemented the Tate pairing step-by-step.

• <https://hackmd.io/@brozorec/pairings-for-the-rest-of-us-1>
• <https://hackmd.io/@brozorec/pairings-for-the-rest-of-us-2>

  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.

• <https://docs.taceo.io/>
• <https://github.com/TaceoLabs/collaborative-circom>

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.

• <https://www.risczero.com/blog/beating-moores-law-with-zkvm-1-0>
• <https://reports.risczero.com/release-1.0>

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）是一个简单的概率证明系统，其中输入语句 $\mathbf{x}$ 和证明 $\pi$ 是有限域 $\mathbb{F}$ 上的向量，而证明是通过对 $\mathbf{x}$ 和 $\pi$ 进行单个点积查询 $\langle \mathbf{q}, (\mathbf{x} | \boldsymbol{\pi}) \rangle$ 来验证的。DPP 可以看作是一个 1-query 完全线性 PCP。论文还讨论了 DPP 的可行性和效率。 A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement $\mathbf{x}$ and the proof $\pi$ are vectors over a finite field $\mathbb{F}$, and the proof is verified by making a single dot-product query $\langle \mathbf{q}, (\mathbf{x} | \boldsymbol{\pi}) \rangle$ jointly to $\mathbf{x}$ and $\pi$. 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>