Cryptography on As it was

Hash To Curve

maocred@gmail.com (Halois) — Mon, 16 Mar 2026 00:00:00 +0800

Reading: RFC 9380, Hashing to Elliptic Curves.

Core problem: given an arbitrary byte string, produce a point in the correct elliptic-curve subgroup, with the distribution and side-channel properties a protocol actually needs. This is not “hash to an $x$ and try to solve for $y$”.

The RFC answer is a pipeline, not a trick:

$$ \text{bytes} \rightarrow \text{field elements} \rightarrow \text{curve points} \rightarrow \text{subgroup points} $$

plus domain separation and constant-time constraints.¹

This note only tracks that structure: what object the RFC is defining, why encode_to_curve and hash_to_curve differ, and why suites such as secp256k1 and BLS12-381 are built the way they are.

KZG 多项式承诺的曲线基础及其协议应用

maocred@gmail.com (Halois) — Tue, 16 Dec 2025 08:00:00 +0800

Reading: KZG turns polynomial objects into deployable commitments.

到 ECC 子系列的最后一篇，问题已经收缩得很具体了。前面几篇分别回答了 why not one curve、账户层为什么停在 secp256k1、pairing-friendly curves 为什么进入 verifier、以及 Ethereum 为什么在 BN254 与 BLS12-381 之间形成长期工程张力。到了 EIP-4844，pairing-friendly curve 不再只是 verifier 的数学背景，而是直接进入 data-availability commitment workflow。

这里真正要理解的，不是“BLS12-381 为什么常出现”，而是“KZG commitments 为什么会自然进入 blob workflow”。如果一个协议只需要对数据做普通哈希承诺，那么 pairing-friendly curve 完全可以不出现；但如果协议既想对多项式对象做常数大小承诺，又想对某个 evaluation claim 给出紧凑 opening proof，那么 verifier 最终就会落到 pairing equation 上，而这也是 KZG commitments and opening proofs rely on pairing-friendly curves 的根本原因。¹ ²

所以这一篇的顺序会比“直接讲 blob”更慢半步：先定义 polynomial commitment object，再写 minimal KZG opening verification equation，随后把这个对象映射到 EIP-4844 blobs 的 commitment / proof / verification workflow，最后把 trusted setup 从尾注抬成 first-class protocol constraint，并在文末给出工程实现对接。

Quick Note. This article explains why KZG commitments and opening proofs rely on pairing-friendly curves. It also gives the minimal KZG opening verification equation, shows the role of BLS12-381 in modern Ethereum data-availability commitments, maps the polynomial commitment object to the blob-commitment workflow in EIP-4844, and makes trusted setup a first-class protocol constraint rather than an afterthought.

Ethereum 中配对友好曲线的演化路径：从 BN254 到 BLS12-381

maocred@gmail.com (Halois) — Mon, 15 Dec 2025 08:00:00 +0800

Reading: Ethereum curve history is interface history first.

上一篇已经把 pairing-friendly curves 的数学接口说清了，但 Ethereum 的工程现实从来不只是“知道 pairing 有用”这么简单。真正决定协议能不能落地的，往往不是抽象上的 verifier compression，而是 execution layer 到底暴露了什么接口、这些接口的 gas 怎么定价、以及库和工具链是否能稳定消费这些接口。

所以 Ethereum 中配对友好曲线的演化路径，首先是一段接口史。BN254/alt_bn128 之所以先进入链上主流，不是因为今天回头看它最优雅，而是因为它先被 precompile 暴露成了真实可调用能力。相反，BLS12-381 虽然在安全 margin 和现代生态上形成了明显的 upgrade pressure，但 deployment friction 也更真实，执行层并不会因为“它看起来更好”就自动完成迁移。¹ ² ³

这一篇的重点因此不是“比较两条曲线谁更先进”，而是按时间线回答三件事：为什么 Ethereum adopted BN254/alt_bn128 precompiles early，gas-cost considerations 怎样直接改变 protocol feasibility，以及 BLS12-381 为什么持续构成升级压力却又没有简单替换掉 BN254。文末再把这条时间线压成工程实现对接清单。⁴

Quick Note. This article explains why Ethereum adopted BN254/alt_bn128 precompiles early. It also contrasts BN254 and BLS12-381 in security margin, ecosystem maturity, and deployment friction, maps Ethereum precompile history to cryptographic capability changes, relates curve choice to verifier cost and deployability, and ties gas pricing and precompile availability to protocol feasibility.

Pairing-Friendly Curves 的数学结构与协议动机

maocred@gmail.com (Halois) — Sun, 14 Dec 2025 08:00:00 +0800

Reading: pairing is a verifier interface, not a prestige upgrade.

前 3 篇已经把 ECC 子系列的前半段压实了：Web3 为什么不会只用一条曲线，账户层为什么长期停在 secp256k1，以及 signer-side 风险如何从 ECDLP 走向 nonce leakage。到这里，新的问题自然出现：既然账户层不需要 pairing，为什么 BLS signatures、SNARK verifier 和 KZG 却总会把 pairing-friendly curves 拉进来？

关键不在“这类曲线更先进”，而在“这类协议的 verifier 从一开始就需要另一种代数接口”。普通离散对数群擅长表达签名关系；pairing-friendly setting 则擅长把分散在多个群元素、多个约束甚至多个消息上的关系压缩成少数几个 pairing checks。也就是说，这里发生的不是曲线选型审美，而是 protocol verification compression。¹ ²

所以这一篇不会把 pairing 写成完整教材。更有用的顺序是：先定义最小 bilinear map properties，再给出一个 minimal pairing equation pattern，随后分别说明 BLS signatures、SNARK verifier intuition 和 KZG opening verification 为什么会消费同一类接口。最后再把这些数学对象压成工程实现对接边界。

Quick Note. This article defines the minimal bilinear map properties needed for protocol use. It also explains why pairings enable aggregate signature verification and polynomial opening verification, gives the minimal pairing equation pattern, and shows the mapping from bilinearity to protocol verification compression. It deliberately avoids expanding into full Miller-loop or final-exponentiation implementation details.

椭圆曲线签名的安全性分析：从 ECDLP 到 HNP、EC-HNP 与 EHNP

maocred@gmail.com (Halois) — Sat, 13 Dec 2025 08:00:00 +0800

Reading: ECDLP is the baseline, not the whole risk surface.

前两篇已经把 ECC 子系列里最容易混淆的两件事拆开了: 哪些协议只消费普通离散对数群，哪些协议需要 pairing；以及为什么账户层长期绑定 secp256k1。这一篇继续沿着账户层往下走，但焦点不再是“签名接口长什么样”，而是“签名接口在哪里失守”。

对椭圆曲线签名来说，曲线层首先给出的安全基线是 ECDLP security assumption。如果敌手只能看到公钥 $P=dG$，却拿不到关于私钥 $d$ 和临时标量 $k$ 的额外泄漏，那么攻击目标仍然是离散对数问题本身。但真实系统并不总是在这个理想模型里运行。wallet and signing implementations 会暴露 nonce 生成、缓存访问、功耗、分支、fault handling 和接口复用等边界，而这些边界往往把问题从“解曲线上的离散对数”改写成“恢复带泄漏的 secret scalar”。¹ ²

ECDSA 的危险点尤其集中在 nonce。只要签名方程里的 nonce 有重复、偏置、部分泄漏，或者可由 side-channel trace 提供不完整信息，攻击者面对的就不再是 black-box ECDLP，而是某种 hidden-number style relation。也正是因此，HNP / EC-HNP / EHNP 不是只存在于格论教科书里的标签，而是现实账户系统在弱随机数、硬件钱包、远程 signer 和实现缺陷下会真正碰到的攻击视角。³ ⁴

Quick Note. This article connects ECDSA nonce leakage to hidden-number style linear constraints. It also distinguishes HNP, EC-HNP, and EHNP rather than flattening them into a generic lattice-attack label, covers nonce bias, partial leakage, and side-channel trace models relevant to wallet and signing implementations, and separates curve-level security from implementation leakage and protocol misuse.

secp256k1 的协议定位与签名机制

maocred@gmail.com (Halois) — Fri, 12 Dec 2025 08:00:00 +0800

Reading: same curve, different signature interfaces.

上一篇已经把 Web3 里的曲线职责图画出来了。这一篇只把账户层单独拎出来：为什么 Bitcoin 和 Ethereum 长期把 secp256k1 当作账户与交易签名曲线，而不是换到 pairing-friendly curve；以及为什么在同一条曲线上，ECDSA 和 Schnorr 会导向不同的协议接口和工程边界。

账户层消费的不是 pairing，也不是多项式 opening proof，而是普通离散对数群上的签名验证关系。这件事决定了 secp256k1 的核心价值并不在“它是哪条曲线”，而在“它背后的实现生态、签名接口和安全边界是否足够稳定”。因此这篇文章真正要比较的对象不是 secp256k1 vs BLS12-381，而是 secp256k1 上的 ECDSA vs Schnorr。¹ ²

如果把账户层写成“曲线教程”，重点会跑偏。更有用的顺序是：先说明 secp256k1 为什么留在账户层，再写 ECDSA 的最小验证关系和它对 nonce 的敏感性，再写 Schnorr 如何在同一条曲线上改写签名接口，最后把这些差异落到 Bitcoin、Ethereum、libsecp256k1、RFC 6979 与钱包实现的现实接口上。³ ⁴

Quick Note. This article separates ECDSA and Schnorr verification logic while keeping both on the same curve family. It also explains protocol fit for Bitcoin and Ethereum account usage, and connects implementation constraints to constant-time scalar arithmetic.

Web3 语境下椭圆曲线密码学的系统分工

maocred@gmail.com (Halois) — Thu, 11 Dec 2025 08:00:00 +0800

Reading: this is a system map, not an ECC primer.

在 Web3 里谈椭圆曲线密码学，最常见的误读是把所有场景压成同一个问题: “既然都是 ECC，为什么不选一条最强的曲线统一掉？”这个问题本身就错了。账户签名、共识聚合签名、链上 zkSNARK 验证、EIP-4844 里的 KZG commitment，虽然都使用了椭圆曲线上的群对象，但它们消费的代数接口并不相同，因此几乎不会自然收敛到同一条曲线。

如果只看“安全位数”，现实会显得很奇怪。Bitcoin 和 Ethereum 的账户层长期绑定在 secp256k1；Ethereum 的链上 zk verifier 历史上却依赖 BN254/alt_bn128 预编译；到了 BLS 聚合签名与 KZG，又几乎总会碰到 BLS12-381。这里真正决定系统形态的，不只是密码学安全性，还包括预编译、gas 成本、标准化、已有库、证明系统接口，以及协议是否依赖 pairing。¹ ² ³

所以这一篇不重讲椭圆曲线的群律，也不把三条曲线写成百科词条。更有用的做法是先画出一张职责图: 哪些系统只需要普通离散对数群，哪些系统必须进入 pairing-friendly curve，哪些场景看似是“曲线选择”，其实首先是“链上可用性和 verifier 成本”的问题。到文末，再把这张图压成工程实现对接清单。

Quick Note. This article explicitly distinguishes ordinary elliptic-curve groups from pairing-friendly curves. It also states the historical role of BN254/alt_bn128 in Ethereum and contrasts it with the modern role of BLS12-381. Finally, it treats trusted setup as a protocol-level constraint rather than an intrinsic ECC property.

zkEVM 与 ZK 系统安全性：约束设计、内存一致性与 soundness footguns

maocred@gmail.com (Halois) — Wed, 10 Dec 2025 08:00:00 +0800

Reading: soundness is only as strong as the constrained surface.

zkEVM 文章最容易写歪的地方，是把“有 EVM opcode、能出 proof、链上 verifier 接受”误当成安全性本身。真正需要抓住的是：proof 只覆盖那些被约束、被 commitment 绑定、再被 transcript 吸收进去的对象。任何没有被这条链路真正绑住的语义，都不在证明系统的 soundness boundary 里。

所以这篇不讨论产品对比，而讨论 engineering attack surface。zkEVM 不等于“把客户端代码翻译成电路”；更准确地说，它是把 opcode 语义、memory read/write、storage queue、状态根更新、lookup 表、递归聚合这些对象拆成一组 constraint obligations，再证明这些 obligations 一起闭合。¹ ² ³

也因此，最典型的 failure mode 不是某条大公式明显写错，而是 linkage 丢了。某个 selector 没把实例绑定到正确路径，某个 queue payload 没和前一层结果相等，某个 lookup 只检查 limb 合法却没检查重组，某个 challenge 没吸收所有 commitments。只要缺一条边，prover 就可能构造一个“局部都像样、全局却不是你想证明的执行”的 witness。

IPA 系证明与递归：Bulletproofs、Halo、Nova/Folding

maocred@gmail.com (Halois) — Tue, 09 Dec 2025 08:00:00 +0800

Reading: recursion through the IPA lens.

这一篇最容易写错的方式，是把 Bulletproofs、Halo、Nova 分成三段协议摘要。那样会丢掉真正重要的主线：inner-product machinery 为什么天然会把系统推向 recursion；以及“可递归的对象”到底在不同系统里发生了什么变化。

若只从结果看：

Bulletproofs 给出对数级压缩证明
Halo 给出递归验证路线
Nova 给出 folding / IVC

这三句都不假，但还是太散。更有用的看法是：它们都在处理“证明对象如何被继续压缩”这个问题，只是压缩的对象不同。

在这条线上：

Bulletproofs 压缩的是高维 relation 本身
Halo 累积的是 verification obligations
Nova 折叠的是 instance / witness state

所以这一篇的主角不是 chronology，而是对象变化：从证明一个 instance claim，到维护一个 accumulator，再到维护一个可继续折叠的证明状态。¹ ² ³

PLONKish 体系：置换论证、lookup 与自定义门

maocred@gmail.com (Halois) — Mon, 08 Dec 2025 08:00:00 +0800

Reading: PLONKish as a design space, not a single protocol.

到了这一阶段，证明系统讨论的重点已经不再是“有没有多项式承诺”或者“有没有低度测试”，而是你把 computation 摆成什么 witness surface。PLONKish 的意义就在这里：它把现代 proving systems 的证明面固定成了 rows、columns、selectors、copy constraints、lookup tables、custom gates 这些对象，然后允许设计者在这个面上不断加表达力。

如果把 permutation、lookup、custom gates 分开讲，很容易误以为它们是三种后来加上的 feature。更准确的理解是：它们都在回答同一个问题，

当 witness 被排成列多项式之后，系统如何表达“这些列之间哪些值必须相等、哪些值必须属于某张表、以及每一行到底允许执行什么语义”？

PLONKish 的主角因此不是某篇单独论文，而是 grand-product machinery 和基于 selector 的约束设计。copy constraints 被重写成 permutation relation；lookup 被重写成 multiset relation；custom gates 则不断给 quotient degree、selector count、column layout 和 prover cost 施压。

这一篇的主线因此也不是 feature list，而是同一个 proving surface 上的三类约束重写。¹ ²

STARK：AIR、低度测试与透明性

maocred@gmail.com (Halois) — Sun, 07 Dec 2025 08:00:00 +0800

Reading: STARK as a proof pipeline, not a brand label.

如果说 Groth16 的关键词是 QAP + CRS + pairing equation，那么 STARK 的关键词就是 trace + AIR + FRI。把它说成“没有 trusted setup 的 SNARK”不算错，但也没抓住结构。真正要理解的是：STARK 证明的对象不是一个静态约束向量，而是一整张 execution trace；AIR 不是一个术语包装，而是把这张 trace 的合法性写成代数关系；FRI 则不是附在最后的 appendix，而是整个 soundness contract 的后半段。

前一篇已经把 FRI 放到 polynomial commitment / low-degree testing 的统一接口里了。这一篇要把它放回系统级视角：trace 怎样变成列多项式，边界条件和转移条件怎样被压成 composition polynomial，以及为什么“低度”在这里不是顺带属性，而是 verifier 最终抓住 cheating trace 的主要证据。

所以这一篇的主链不是：

$$ \text{AIR}\quad\text{and}\quad\text{FRI} $$

而是：

$$ \text{trace} \longrightarrow \text{AIR constraints} \longrightarrow \text{composition polynomial} \longrightarrow \text{FRI low-degree test}. $$

Groth16：从 QAP 到配对检验方程

maocred@gmail.com (Halois) — Sat, 06 Dec 2025 08:00:00 +0800

Reading: Groth16 as a derivation, not a magic trick.

Groth16 最容易被记成一句营销话术：proof 只有三个群元素，验证很快，所以它很强。这个说法不假，但几乎没解释任何东西。真正该理解的是：这三个群元素到底在编码什么；它们为什么足以代表一个 QAP witness；以及最后那条 pairing product equation 为什么不是凭空出现的黑箱检查，而是 QAP identity 在秘密点评估之后的压缩形式。

前两篇已经把接口准备好了。第 4 篇给出

$$ A_{\mathbf{w}}(X)B_{\mathbf{w}}(X) - C_{\mathbf{w}}(X) = H(X)Z(X), $$

第 5 篇解释了 KZG 风格的核心直觉：多项式关系可以通过秘密点 $\tau$ 上的群编码与 pairing check 来验证。Groth16 本质上就是把这条思路做到了 QAP satisfiability relation 上，但它还额外引入了若干 trapdoors，把 witness 可伪造空间压得非常窄，最终只留下三段 proof tuple。¹ ²

所以这篇不打算把 Groth16 写成一个“比别的 SNARK 更短”的结果，而是把这条推导链写出来：

$$ \text{QAP relation} \longrightarrow \text{CRS at secret point} \longrightarrow \text{proof tuple } (A,B,C) \longrightarrow \text{pairing product equation}. $$

多项式承诺的统一看法：KZG、IPA、FRI

maocred@gmail.com (Halois) — Fri, 05 Dec 2025 08:00:00 +0800

Reading: one article, three schemes, one interface.

前一篇已经把 computation 变成了多项式对象：QAP 里有 $A_{\mathbf{w}}, B_{\mathbf{w}}, C_{\mathbf{w}}, H, Z$，AIR 里有 trace polynomials 与 composition polynomial。到了这里，问题不再是“如何把程序写成多项式”，而是“如何承诺这些多项式，并在不泄露全部系数的前提下证明某些点值或低度性声明”。

如果把 KZG、IPA、FRI 分别介绍，很容易写成三段协议百科。更有用的视角是：三者都在回答同一个问题，只是 machinery 不一样。这个问题可以先压成最小形式：

我已经对一个多项式 $f(X)$ 做了承诺。现在我要证明在点 $z$ 上，它的取值确实是 $y = f(z)$，或者至少证明它来自某个低度多项式家族。

在这个统一接口下：

KZG 把 opening 变成 pairing verification equation
IPA 把 opening 变成 coefficient vector 和 evaluation vector 的 inner-product proof
FRI 把 low-degree claim 变成 repeated folding and query consistency checks

所以这一篇的重点不是“哪个更好”，而是它们各自把 evaluation proof 压成了什么对象，又因此带来了什么 setup、proof size 和 verifier cost。¹ ² ³

从算术电路到 R1CS、QAP 与 AIR

maocred@gmail.com (Halois) — Thu, 04 Dec 2025 08:00:00 +0800

Reading: arithmetization as interface design, not notation churn.

前面三篇一直在准备同一件事：证明系统不会直接消费“某个程序跑对了”这种语义句子。它们消费的是某种 algebraic surface，最好能被承诺、挑战、开点、低度测试或者 pairing equation 直接处理。到了这一篇，主角不再是 transcript skeleton，而是 computation 本身如何被翻译成代数约束。

如果只用一句话概括算术化，它就是把“计算正确”改写成“某个 witness 满足一组 field 上的代数关系”。但这句话还不够，因为后面的证明系统并不直接吃“很多条关系”。它们更喜欢的是：

向量上的 rank-1 constraints
多项式上的恒等式或整除关系
execution trace 上的 transition constraints

所以这一篇真正要写清楚的不是名词，而是两条链：

$$ \text{circuit} \longrightarrow \text{R1CS} \longrightarrow \text{QAP} $$

以及

$$ \text{trace} \longrightarrow \text{AIR}. $$

两条链的共同目标都是同一个：把 computation 变成一个证明系统能消费的 polynomial object。¹ ² ³

Sigma 协议的统一视角：Schnorr、表示证明与 Fiat-Shamir

maocred@gmail.com (Halois) — Wed, 03 Dec 2025 08:00:00 +0800

Reading: sigma protocols as the first reusable proof skeleton of the series.

上一篇把 Pedersen 承诺写成了一个 relation：

$$ C = g^m h^r. $$

这一篇开始研究，怎样围绕这种 relation 构造一个既能 extraction、又能 simulation 的三步证明骨架。真正需要记住的不是 “Schnorr” 这个名字，而是同一个模板：first message 先把 witness 压进一个承诺式对象，verifier 给出一个公币 challenge，prover 再用线性响应把 witness 带回来。

Sigma 协议之所以重要，不是因为它是某个古典协议家族，而是因为它把三件后面一直会重复出现的东西压进了同一份 transcript：

commitment / first message
extractor 需要的两份 accepting transcripts
simulator 需要重建的 transcript distribution

这也是它成为后续现代证明系统桥梁的原因。Schnorr 证明离散对数是最小例子，表示证明是直接推广，而 Fiat-Shamir 则显示这套骨架一旦被 hash 取代 challenge，交互虽然消失，模型边界却一起换掉了。¹ ² ³

有限域、循环群、离散对数与 Pedersen 承诺

maocred@gmail.com (Halois) — Tue, 02 Dec 2025 08:00:00 +0800

Reading: Pedersen commitments as the first concrete algebraic interface in the ZK series.

上一篇把 relation、instance、witness、soundness、zero knowledge、knowledge soundness 的接口钉住了。这一篇开始把这些抽象对象落到具体代数对象上，但只选最小够用的一组: 标量域 $\mathbb{Z}_q$、一个 prime-order 循环群 $G$、两个生成元 $g,h$，以及一个承诺式子

$$ C = g^m h^r. $$

这个式子看起来很短，但后面几篇会不断回到它。消息 $m$ 和随机数 $r$ 都是标量；群元素 $C$ 是公开 instance；opening 则是 witness $(m,r)$。如果把这些对象先写清楚，后面再看表示证明、Schnorr、Fiat-Shamir 时，很多结构就不再像“新协议”，而只是同一个关系换了一个验证方式。

Pedersen 承诺最值得写的不是“它同时 hiding 和 binding”这句口号，而是两条具体推导: 第一，为什么对固定消息，随机 $r$ 会把 $g^m h^r$ 推成群上的均匀分布，因此得到 perfect hiding；第二，为什么一旦有人给出两组不同的 opening，就能从

$$ g^m h^r = g^{m'} h^{r'} $$

直接解出 $\log_g h$，因此 binding 只能是 computational 的。¹ ²

零知识证明的最小理论框架

maocred@gmail.com (Halois) — Mon, 01 Dec 2025 08:00:00 +0800

Reading: GMR 1989, Goldreich, and the standard zero-knowledge definition chain.

开篇先不讲洞穴故事，也不讲“验证者虽然信了但什么都没学到”这种直觉口号。后面整条 ZK 系列都会反复调用同一批对象: relation、language、instance、witness、prover、verifier、transcript、view、simulator、extractor。第一篇的任务，只是把这些对象之间的接口一次性钉死。

零知识证明真正容易混掉的，不是某个协议细节，而是哪些性质分别由 completeness、soundness、zero knowledge、knowledge soundness 约束；哪些结论只对 honest verifier 成立；哪些地方已经从 proof 退到了 argument。只要这些边界不先写清楚，后面看到 Sigma、Fiat-Shamir、SNARK、STARK 时就会不断把不同层次的结论混在一起。

本文给出一个最小理论框架: 从 $R(x, w)$ 定义语言，到交互证明的接受事件，再到 verifier view 与 simulator 的 indistinguishability，最后补上 argument/proof 与 knowledge soundness 的分界。它不是一篇历史综述，而是一份后续文章默认继承的接口说明书。¹ ²