by Kurt Pan Vitalik recently wrote a great post on the trade-offs about replacing the KZG commitment to arithmetic hash-based one in EIP-4844. The article is very instructive and forward-looking, but unless you are a tech-savvy and keep an eye on the state-of-art progress, there will be a lot of prerequisites to be met to understand the article. In this short article I will present to you some of the necessities and learning materials for understanding Vitalik's post. The purpose is not to be mathematically or cryptographically rigorous or complete, it is mainly to serve as a preview of the landscape. I hope this article will make the learning process a little bit easier for you. Mathematics Mathematics (for most people) is hard, especially the ones involved in blockchain frontier technologies, which to many seem like moon math. But at the same time math is necessary for the clarification of concepts, formal description and analysis, security proofs and many other necessary steps of research.

:::info 作者：Kurt Pan ::: 定理： 如果哈希函数$H$是随机预言 且如果CDH问题是困难的 则BLS签名方案是选择消息攻击下存在不可伪造（EU-CMA) 安全的 安全损失$L=q_H$，$q_H$是对随机预言哈希查询的次数

:::info 原文：https://geometry.xyz/notebook/Hashing-to-the-secp256k1-Elliptic-Curve 作者：weijie.eth 译者：Kurt Pan ::: 引言 许多密码学协议，比如可聚合分布式密钥生成和BLS签名方案，都需要用到哈希到曲线算法，确定性地将任意字节串转换成椭圆曲线上的一个点。这样的算法并非平凡，因为不仅仅是要产生有效的曲线点，而且还要以安全且高效的方式来产生。 这篇文章中，我将总结哈希到曲线函数的技术现状，重点是其在secp256k1椭圆曲线上的应用，以及一般的哈希到曲线算法背后的一些安全考虑和性能优化。

Strong Diffie-Hellman (SDH) 问题定义如下： 给定$(q+2)$长的元组 $\left(g_1, g_2, g_2^\gamma, g_2^{\left(\gamma^2\right)}, \ldots, g_2^{\left(\gamma^q\right)}\right)$ 作为输入，输出 $\left(g_1^{1 /(\gamma+x)}, x\right)$ ，其中$x \in \mathbb{Z}_p^*$。 SDH假设就是，不存在多项式时间算法可以以不可忽略概率解决SDH问题。 Schnorr协议，是一个证明「知道离散对数」的ZKPoK。以下ZKPoK协议是对Schnorr协议的扩展，可以以零知识的方式证明「知道SDH问题的解」。（至于我为什么要介绍这个协议，以后就慢慢知道了。 :wink:） 秘密值：$\gamma$ 公开值： $g_1, u, v, h \in G_1 , g_2, w \in G_2$, 其中$w=g_2^\gamma$

:::info 原文：https://medium.com/@boneh/using-zk-proofs-to-fight-disinformation-17e7d57fe52f 作者：Trisha Datta ，Dan Boneh 译者：Kurt Pan ::: 验证数字图像的拍摄时间地点变得越来越困难。 图像出处在新闻媒体领域尤为重要。 俄罗斯在 2 月入侵乌克兰后，网上流传的几张照片和视频 对冲突进行了错误的声称。 一个例子是两张照片的所谓的一一对比。 第一张据称是俄罗斯空袭后的叙利亚，第二张据称是俄罗斯入侵后的乌克兰。 《今日美国》后来的分析显示，第一张照片实际上是 2017 年在伊拉克拍摄的，而第二张照片虽然确实是乌克兰的，但拍摄于入侵前两周。 虽然这些事实核查服务是重要的，但如果个人能够亲自验证照片的出处，他们将避免去依赖第三方，并使他们能够保护自己免受此类假消息的侵害。 在一个理想的世界里，照片会带有地理位置和时间戳，以及这些信息是正确的证明。 这样的话，如果用户在在线新闻文章中看到一张照片，他可以使用提供的证明来验证照片的拍摄时间地点，而且无需信任文章的发布者或第三方事实核查网站。 这种验证可以通过诸如一个可以自动检测和验证这些证明的浏览器扩展之类的东西来进行。 这篇博文的其余部分讨论了我们做出这样的一个系统的尝试。

==Crypto means Cryptography!== 如果一个Crypto行业的从业者对于密码学只是采取敬而远之，当作工具利用，甚至轻视的态度，在我看来这是堪称「Web 3.0迷惑行为」的。因为没有密码学就没有了这个行业的技术根基，精神根基。对于根基，应该再怎么重视都不为过。 “但是密码学太TM难了！”这是同学们的心声，我对此完全感同身受。不过我还是要在这里小幽默一下：密码学“难”就对了！如果这个宇宙中没有hardness，那密码学也就不存在了。密码学正是在利用这个宇宙中存在的计算困难性，来为一个更安全更自由更平等的社会添砖加瓦！ Just kidding. 这个系列是对密码学中的常见概念的辨析，面向以严肃心态学习密码学的初学者。个人能力有限所以请DYOR并欢迎指正。 也欢迎小伙伴们提出下一期的答疑点，我会尽力去解答。（注意要求是真的「密码学」问题，不包括「财富密码」…… :zany_face:）

:::info 原文：https://0xparc.org/blog/batch-ecdsa 作者：John Guibas , Uma Roy 译者：Kurt Pan ::: 我们带来了 circom-batch-ECDSA，一个基于circom-ECDSA（由0xPARC 社区中其他人之前完成的工作）之上的概念验证实现，其灵感来自halo2-batch-ECDSA，它允许在单个 SNARK 中显著更快地验证一批 ECDSA 签名。 简介 ECDSA 签名是一种广泛使用的密码学原语，可使人确信一条消息只能来自拥有特定公钥的人。在区块链场景中，ECDSA 签名通常用于验证提交的交易是否来自拥有发出交易的账户的人。

Kurt Pan Groth16 方案回顾 SNARK领域中的延展攻击，是指给定敌手一个合法证明，敌手在不知道见证的条件下自己生成新的（对相同或不同公开输入的）合法证明。 $$ AB=\alpha \beta+\sum_{i=0}^{l} z_{i} \left(\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)\right)+\ C_{\text {paired }}(x) $$

\begin{aligned} S_1 &= 1-1+1-1+\ldots \ 1-S_1 &= 1-(1-1+1-1+\ldots) \ &= 1-1+1-1+\ldots = S_1\ S_1 &=\frac{1}{2} \end{aligned} \begin{aligned} S_2 &= 1-2+3-4+\ldots \ 2S_2 &= 1-2+3-4+\ldots \

:::info 作者：Kurt Pan ::: 感谢Trapdoor Tech李星老师和安比实验室Even的帮助 :wink: 背景 Geometry是Kobi Gurkan 等人所在的一个新成立不久的研究组织，Kobi本人曾给ZK HACK 出过9道puzzles，这次又合作给出了这个关于Groth16延展攻击的新puzzle：ZK Hack x Geometry Puzzle I 该puzzle的主要内容在这个github仓库中：zkhack-groth-puzzle，

A PCP Theorem for Interactive Proofs and Applications 提出PCP定理的扩展--IOP定理：任何k轮IP可以判定的语言都具有一个k轮公开抛币IOP，其中验证者在每条消息中读取$O(1)$的比特。几个应用：对一个随机可满足性问题的新的近似困难结果，IOP到IOP转换，新概念index-decodable PCP，允许对非确定性计算在ROM中得到一个commit-and-prove SNARK。 Families of SNARK-friendly 2-chains of elliptic curves CANS’20引入了对递归zk-SNARK友好的配对友好椭圆曲线的2链：由BLS12-377曲线和新的BW6-761曲线构成。本文推广到定义在任意BLS12曲线上的任意BW6曲线，构成了一个新的2链配对友好曲线簇。导出新的CP曲线上的optimal ate and optimal Tate配对的高效公式，说明对BLS12和BLS24，BW6的构造相比于CP曲线具有最快的配对速度。BLS12-377/BW6-761对Groth16是最优的，而BLS24-315/BW6-672对PlonK是最优的。 Gemini: elastic SNARKs for diverse environments 提出Elastic SNARKs：证明者可以依据执行环境和要证明的语句灵活分配不同的时间（线性或准线性）空间（线性或对数）资源，且生成的结果不变。提供elastic PIOP的定义框架并给出elastic PIOP到支持对输入顺序或随机访问的预处理论证系统的编译器。给出Gemini，一个新的无FFT的预处理elastic SNARKs。 SNARGs for P from Sub-exponential DDH and QR

:::info 作者：Steven Galbraith 译者：Kurt Pan 原文链接：https://ellipticnews.wordpress.com/2022/07/31/breaking-supersingular-isogeny-diffie-hellman-sidh/ ::: Wouter Castryck 和 Thomas Decru的论文An effective key recovery attack on SIDH是同源密码分析的重大突破。这个结果与 Jao 和 De Feo 的 SIDH 协议以及 NIST 第 4 轮决赛入围方案 SIKE 有关。 我没有时间解释所有的技术细节，但这里有一些对你急迫问题的快速解答。

引言 「知识证明」关心的不只是「这个陈述是不是正确的」，而是「你是否知道为什么这个陈述是正确的」。「陈述是正确的」并不意味这「你知道为什么这个陈述是正确的」，完全存在如下可能：你在不知道该陈述为什么是正确的「证据」的同时可以生成「该陈述是正确的」零知识证明。反过来如果「陈述是错误」的，那么你是不可能「知道」相应的「并不存在」的证据的。 比如说有一个公钥$h=g^{x}$ ，你想要证明你拥有私钥$x$从而证明你的身份。如果你只是调用对任意$\mathcal{NP}$语言的零知识证明系统去证明$h \in L$，其中$L=\left{h \mid \exists x: g^{x}=h\right}$。（回想教科书里的零知识证明都是在证明某个陈述$x\in L$，该系统满足完备性，可靠性和零知识性。），你只需要永远发送信息“Yes"即可。这是一个合法的零知识证明系统，但这当然是远远不够的，因为对于任意一个群元素$h$，其对应的私钥$x$一定「存在」。你要去证明的是「我知道相对应的私钥」，而不仅仅是「对应的私钥存在」。 在定义「知识证明」之前先来回顾一下一个哲学家们争论了几千年也没有结果的问题：「什么是知识？」维基百科中对「知识」定义如下：Knowledge is a familiarity or awareness, of someone or something。这个定义因为无法量化，涉及主观和内隐的东西，并不能令人满意。（关于「知识」和「信息」关系的更多讨论，请参考我之前的文章）于是秉持「实用主义」的计算机科学家开始尝试用「输出」来定义「知识」，使得「知识」变为具体的可以进行检验和处理的东西。这种思想迁移到计算机世界中就是「图灵机」的输出，这也和图灵本人定义「人工智能」的「行为主义」观点是一致的。 如果机器「知道」一个东西，它可以将其「输出」出来。 具体一点，如果一个机器知道陈述$x$的证据，那么它就可以把该证据$w$(满足$(x,w)\in R$)输出出来。

「知识」是什么，这个问题哲学家已经辩论几千年了，没有一个最终的答案。 这个 "5个level讲零知识"的视频中，Shang-Hua Teng 教授作为零知识专家提出了一个问题：“为什么叫「零知识证明」，而不叫「零信息证明」或「零数据证明」？“ 显然证明系统中是有数据的，所以肯定不是「零数据证明」。 Sahai教授给出了如下回答：零知识是那些你总是可以预测答案的东西，因为你已经知道答案所以你不可能在交互中获取任何新「知识」。 这个回答是很重要的insight，事实上GMR正是就是以这个insight用「模拟范式」定义了零知识。但是很明显这个回答依然避开了那个tricky的问题：“什么是「知识」？” “知识”在数学上是有非常良好的定义的。但“零知识”不是“零信息”的，因为要至少传递一些 01 串的信息给对方。零知识本质上在于熵很大，都是很随机的信息，无法从中提取出有用的知识

:::info 原文地址：https://eng-blog.o1labs.org/posts/plonk/ 作者：Anaïs Querol 译者：Kurt Pan ::: Kimchi 是我们新的无需信任的 zkSNARK，它基于PLONK证明系统和Bulletproofs承诺方案。这篇文章的目的是缓解阅读上述论文后产生的症状。毕竟，PLONK精心挑选的缩写（Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge）绝不仅仅是一个有趣的巧合：让我们试着把一瓶 plonk（英式英语：廉价酒） 变成一杯美酒🍷，然后干杯🍻！ [TOC]

在如何判断两个大文件内容是否相等，如何快速验证矩阵乘法的正确性两篇文章中我们都使用了Reed-Solomon编码作为关键性的构造方法，且在可靠性证明时使用了一个多项式的关键引理，Schwartz-Zippel 引理。 那么为什么对于一个长向量Reed-Solomon编码之后对多项式在随机点处的求值就可以作为原始向量的哈希指纹了呢，是什么原因使得这个特殊的$\mathbb{F}_p$元素就可以完全作为整个$\mathbb{F}_p^n$长度向量的代表了呢？ 对于$n$维向量$a, b \in \mathbb{F}{p}^{n}$，其Reed-Solomon编码是以向量各项作为多项式系数的多项式 $p{a}$ 和 $p_{b}$ 。注意编码后的多项式成为了分布在整个有限域$\mathbb{F}_{p}$上的长度为$p$的向量。因为$p \gg n$，即编码后向量的长度要远远大于编码前向量的长度。编码过程本身是一个距离放大的过程，如果原始向量$a, b$哪怕在一个项上有所不同，那么编码后的两个向量在至少$1-n / p$ 个坐标上都会不同，即几乎每一项都会不同。这种雪崩现象也是可以将Reed-Solomon编码作为哈希函数的原因。 因为有一点不同的两个向量编码后的向量几乎每一项都不同，故可以随机选择$r \in \mathbb{F}{p}$，使用$p{a}(r)$ and $p_{b}(r)$这两个$\mathbb{F}_{p}$元素（即编码后向量中的其中随机一项）来代表整个原始向量，并和相对应项来进行比较。故检查两个向量$a$ 和 $b$ 是否相等的问题就可以归约到检查相对应的编码后的两个随机项是否相等的问题了。 例子

问题 找到「矩阵乘法」的高效算法是计算机科学长久以来的一个研究课题，对于两个$n \times n$的矩阵，平凡的矩阵乘法算法的时间复杂度为$\mathcal{O}(n^3)$。之后经过计算机科学家半个多世纪的努力（Strassen算法，Coppersmith-Winograd算法，laser方法等），最前沿算法的时间复杂度已经降低为$\mathcal{O}\left(n^{2.37286}\right)$。 但本文要探讨的并非计算矩阵乘法本身的高效算法，而是检验矩阵乘法计算正确性的高效算法，换句话说，我们提出如下问题： 是否存在比已知最好的矩阵乘法算法更快的检验矩阵乘法计算正确性的算法？即给定三个$n \times n$的矩阵$A,B,C$，高效地判定$A\times B \stackrel{?}{=} C$ 的算法。 Freivalds 算法 Freivalds在1977年给出了一个时间复杂度为$\mathcal{O}(n^2)$的随机化算法，对上述问题给出了一个肯定的答案。注意到仅仅读入输入$A,B,C$就需要$\mathcal{O}(n^2)$了，所以Freivalds算法只比读入输入增加了常数多的额外开销，远远快于最快的计算矩阵乘法的算法。

Schwartz-Zippel 引理 Schwartz-Zippel 引理是关于有限域中的多变量多项式零点个数的紧致上界，具体表述如下： 对于域$\mathbb{F}$上的每一个阶最多为$d$的$n$变元非零多项式，对于任意有限集合$S \subseteq F$, $$ \operatorname{Pr}{r{1}, \ldots, r_{n} \leftarrow S}\left[f\left(r_{1}, \ldots, r_{n}\right)=0\right] \leq \frac{d}{|S|} $$ 等价地，$f$在$S^{n}$中最多有 $d|S|^{n-1}$个根，($Z(f)$是$f$的零点集) ： $$ \left|Z(f) \cap S^{n}\right| \leq d \cdot|S|^{n-1}

问题 两个相隔千里的人Alice和Bob，每人拥有一个非常大的文件，其中各自包含$n$个字符，分别记为：$a=\left(a_{1}, \ldots, a_{n}\right)$， $b = \left(b_{1}, \ldots, b_{n}\right)$。 二人的目标是，判断他们的两个文件是不是相等的，即对所有$i=1, \ldots, n$，是否$a_{i}=b_{i}$ 。 基准解法 Alice把他的整个文件发给Bob，Bob检验对所有$i=1, \ldots, n$，是否$a_{i}=b_{i}$ 。显然当文件大小很大时，该解法通信复杂量过大。 下界：基于姚氏通信复杂性模型 （这一小节其实是写本篇的初衷，但过于技术，恕我不翻译。）