2.1 密码学原语：哈希、单向函数与难题假设

2.1 密码学原语：哈希、单向函数与难题假设

本节摘要：零知识证明的全部魔术都踩在三块原语之上：单向函数提供"去时容易回时难"的不对称，哈希函数提供数据指纹与随机性来源，难题假设提供作弊的成本下界。本节逐一拆解它们的性质、演算与在 ZK 协议中的岗位，承接第 1 章三性质，通往 2.2 的复杂性土壤。

为什么先看不对称性

任何一台零知识证明机器，拆到最后都靠同一个物理事实支撑：有些运算顺推轻而易举，逆推却要搬山。乘两个大素数，学校里学过竖式就能算；把乘积拆回两个素数因子，全世界最快的公开算法在合理参数下也要跑上万年。哈希也一样：给定内容立刻算出摘要，反过来找一段摘要恰好等于某个值的内容，只能碰运气。这类"正向与逆向成本极不对称"的函数，术语叫单向函数。它的存在性尚未被证明（这等价于 P 不等于 NP 之类的开放问题），但四十年来无人找到高效的逆推算法，整个现代密码学都把它当作地基来盖楼。

在 ZK 场景里，单向性回答的正是 1.3 节留下的问题：作弊者为什么装不出"知道秘密"？因为秘密往往就是某个单向运算的输入（比如离散对数里的指数），公开值是输出。验证者手里的公开值人人可见，但没有输入，谁也变不出与之自洽的应答。装知道的唯一办法是反解单向函数，而这正是难题假设所禁止的。

哈希函数：指纹、骰子与粘合剂

哈希函数 H 把任意长度的输入压成定长输出，它要在 ZK 里干三件活，各自对应一条性质。第一件是指纹：文件哈希一致则内容一致的概率极高，靠的是抗碰撞性——找不到两个不同输入撞出同一输出。第二件是骰子：输出看起来与随机数无异，且输入改动一个比特，输出就天翻地覆，这叫雪崩效应，它让"从承诺推导不出内容"（隐藏性）与"内容定下后承诺无法反悔"（绑定性）同时成立。第三件是粘合剂：3.2 节的 Fiat-Shamir 变换用哈希把多轮对话压成非交互证明，靠的正是"输出像骰子"这一点——哈希输出的挑战，作弊者无法在看清挑战后再回头改承诺。跑一段演算，亲眼看雪崩：

# 哈希雪崩效应演示：输入差一个字，输出面目全非
import hashlib

msgs = [
    "批准向账户A转账一百元",      # 原始指令
    "批准向账户A转账一百元。",    # 只多一个句号
    "批准向账户B转账一百元",      # 只改了收款账户字母
]
for m in msgs:
    digest = hashlib.sha256(m.encode("utf-8")).hexdigest()
    print(digest[:32], "<-", m)
# 输出是三行互不相似的十六进制串，且与输入差异毫无规律对应；
# 想造出摘要恰好等于某个目标值的指令，只能海量试错

# 概念演示"哈希当骰子"：挑战值 = 哈希(承诺) 的一个整数切片
R = b"commitment-bytes"
challenge = int.from_bytes(hashlib.sha256(R).digest(), "big") % 97
print("由承诺导出的挑战值:", challenge)   # 确定性：承诺不变，挑战必不变
​

演算里的确定性值得划重点：同一承诺永远导出同一挑战，这既让 Fiat-Shamir 有了根基，也解释了为什么承诺一旦发出去就再也不能改——改一个比特，挑战跟着全变，作弊剧本当场穿帮。

图：原语、构件与协议的层级关系

这张分层图是全书的地形图：第 4 章拆的是构件层，第 3 章拆的是协议层。读后面章节时迷路了，就回来对照一下自己当前在哪一层。

难题假设：把"不可能"标价

工程上没有绝对的不可能，只有贵到不划算。离散对数问题（DLP）：给定 g 与 g^x mod p，求 x——1.1 节的暴力演算已经演示过玩具规模下的逐个尝试，真实参数下穷举需要约 2 的 128 次方次运算，按全球算力合计也要烧掉不可接受的能量。大整数分解：RSA 的根基，目前最锋利的通用算法（数域筛）也是亚指数级而非多项式级。这些"目前没有多项式时间算法"的公开难题，就是密码学的计价单位——安全声明都写成"在某某假设下，作弊成本超过某某量级"。

两件事必须提醒。其一，假设是会过时的：量子计算对离散对数与分解是灭顶之灾（Shor 算法多项式时间解决），这直接催生了第 7 章的抗量子路线——STARK 只依赖哈希假设，正是在给"假设作废"买保险。其二，原语性质破坏的连锁反应是全局性的：一旦哈希出现可行碰撞，Fiat-Shamir 挑战可操纵、承诺可反悔、Merkle 树可伪造，上面所有协议一层不剩。所以读懂一份 ZK 方案的安全声明，先找它站在哪些假设上，再评估自己业务里这些假设的剩余寿命。

原语的寿命管理

选原语如同选建材，要看设计寿命。工程上给每项依赖做三栏登记：依赖什么（具体到假设与参数档）、还能活多久（最新密码分析进展、量子时间表）、替换成本（哪些上层构件要跟着动）。这张表让"要不要现在换"变成可计算的问题：某方案依赖的配对假设若在三年的技术视野内保持稳固，就值得继续用；若底层曲线已出现分析进展，哪怕离攻破尚远，也应启动替换评估。7.3 节会把这套方法展开成完整的迁移剧本，本节先立起"假设是资产、会折旧"的观念。

三问三答

**问：为什么哈希函数选来选去就那几款？**因为哈希的安全论证靠的是长期公开试炼而非数学证明——一款哈希要经过多年、全世界的分析与攻击仍屹立不倒，才敢进协议。这解释了为什么新哈希的采纳周期以十年计，也解释了为什么"自研哈希"在任何场景都是红旗信号。

**问：玩具演算里的小素数参数安全吗？**完全不安全，p=97 这类参数只是让读者能手算复现。真实协议的参数选择有严格的规范与常数来源（"nothing up my sleeve"原则——参数生成过程公开可查，无暗门），绝不能拿教学数字直接上生产。

**问：单向函数被攻破会怎样？**按层级连锁：承诺可反悔、挑战可操纵、签名可伪造，上层协议一层不剩全部作废。这也是为什么安全声明的第一行永远是"在某某假设下"——那行字就是整栋楼的地基声明。

补充视角：两把"尺子"怎么量原语

评估一项原语是否够用，工程上有两把互补的尺子。第一把叫安全尺：量的是假设的稳固程度——被公开研究多少年、攻破它的最好算法离多项式时间有多远、量子对手下还剩多少安全位。第二把叫成本尺：量的是每次运算的微秒数、字节数与并发友好度——同一性质可以有多个实现档位，价格差几倍很常见。两把尺子经常打架：安全档位最高的原语未必有最快的实现，最快的实现可能停留在较旧的参数档。工程决策的做法是把两把尺子的读数并排写进选型记录，而不是只用其中一把然后感觉良好。本章后续的协议都同时依赖这两把尺子——"安全声明"由安全尺背书，"性能三本账"（5.2）由成本尺背书。

最后一个提醒关于"组合陷阱"：原语各自安全，不代表拼起来仍安全——两个各自不可区分的承诺叠加，可能因可交换性产生可区分的结构。协议安全证明存在的意义正是分析这些组合效应，这也是"自创组合"与"有证明的协议"之间的鸿沟所在。工程上恪守一条：只使用有完整安全证明的协议，把原语当乐高自由拼装是密码学工程的第一大忌。

本节要点回顾

• 单向性是承重墙：装不出"知道秘密"，因为秘密在单向运算的输入侧；
• 哈希三岗位：指纹（抗碰撞）、骰子（伪随机输出）、粘合剂（Fiat-Shamir 与承诺）；
• 难题假设即计价：安全声明都是"假设 + 成本量级"的组合，不是绝对承诺；
• 假设有寿命：量子威胁与密码分析进展都要纳入选型评估，纯哈希方案是常见的保险策略。