卷 II · 对答CH 07深度 7/23

「没泄露」的严格意思

「验证者什么也没学到」这句话怎么可能被证明?你没法穷举「所有他可能学到的东西」。1985 年 Goldwasser、Micali 和 Rackoff 给出的答案,是这个领域最漂亮的一次转向:不去证明他没学到,而是去证明他本来就能自己造出他看到的全部东西。本机在一个小群上把两边的记录穷举完毕——各 121 条,逐条对上,总变差距离精确为 0

模拟器121 vs 121距离 0

◻ 本章先赊三条
第一条。「零知识」的定义里没有「知识」这个词。它是一个关于概率分布的陈述:真记录的分布,和一个假记录的分布,完全一样。 第二条。模拟器和第 6 章的抽取器是同一个数学事实的两面;一个用来说「他必须知道」,一个用来说「你学不到」。 第三条。既然假记录和真记录一模一样,那真记录凭什么能说服人?答案还是顺序——而这也解释了为什么零知识证明不能拿去给第三方看

换一个问法

直接证明「Victor 什么也没学到」是不可能的:你得先定义「知识」,再穷举他所有可能的推理路径。这条路走不通。

1985 年那篇论文换了个问法:

◆ 零知识的定义

存在一个模拟器——一个完全不知道秘密的程序——它输出的「对话记录」,和真证明者与验证者交互产生的记录,服从同一个概率分布

如果这件事成立,那么 Victor 从真对话里学到的任何东西,他自己在家关起门来也能学到(因为他自己就能跑那个模拟器)。所以真对话给他的知识增量精确为零。

这个转向的漂亮之处在于:它把一个认识论问题,变成了一个可以用代码验证的分布相等问题

模拟器长什么样

第 6 章已经把它写出来了,只是当时是当作麻烦提到的:

真证明者(知道 ⟦x⟧)           模拟器(什么都不知道)
────────────────────────      ────────────────────────
1. 随机取 k,算 R = k·G        1. 随机取 c 和 s
2. 收到挑战 c                  2. 倒推 R = s·G − c·P
3. 算 s = k + c·x              3. 输出 (R, c, s)

输出 (R, c, s)                 —

验证等式 s·G == R + c·P        验证等式 s·G == R + c·P
   ✓ 成立                          ✓ 也成立(倒推时就是这么定的)

模拟器把三步的顺序倒过来做:先定答案,再倒推题目。它算出来的 R 完全合法,三元组完美通过验证——而它从头到尾没碰过 x。

本机在真的 secp256k1 上跑了一次:

secp256k1 上倒着造一条记录,验证通过吗   True
  造它用到私钥了吗                        没有

把两边的分布全部数出来

「服从同一个分布」听起来很虚。所以我们找一个小到可以穷举的群,把两边的记录一条不落地列出来数一遍。

用模 23 的乘法群里那个 11 阶子群(元素只有 11 个:1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18):

群阶 q = 11,生成元 g = 2,秘密 x = 6,公钥 P = g^x

真证明者能产生的记录:k 取遍 0…10,c 取遍 0…10
    → 11 × 11 = 121 条 (R, c, s)

模拟器能产生的记录:s 取遍 0…10,c 取遍 0…10
    → 11 × 11 = 121 条 (R, c, s)
真证明者能产生的问答记录条数    121
  其中互不相同的                121
模拟器(不知道 x)能产生的条数   121
  其中互不相同的                121

★ 总变差距离                   0.0000000000
★ 每条记录两边各出现几次          各 1 次,全部对上

样例(R, c, s)   1, 0, 0   1, 1, 6   1, 2, 1   1, 3, 7

不是「接近」,不是「统计上不可区分」——逐条相同,一条不多,一条不少,每条出现的次数也一样。这叫完美零知识(perfect zero-knowledge)。

为什么会这么整齐?因为两边其实在描述同一个集合。所有通过验证的三元组,恰好构成集合

{ (R, c, s) :  R = s·G − c·P,  c ∈ Z_q,  s ∈ Z_q }

它有 q × q = 121 个元素——因为 c 和 s 一旦定下,R 就唯一确定了。

真证明者:随机取 (k, c),得到其中均匀分布的一条。
模拟器:  随机取 (s, c),也得到其中均匀分布的一条。

同一个集合,同一个均匀分布。所以距离是 0。

那真的那份凭什么能说服人

这是所有人卡住的地方,而答案只有两个字:顺序

真交互模拟器
先定什么先定 R(押注)先定 c 和 s(答案)
c 从哪来Victor 在看到 R 之后临时抛出的模拟器自己选的
说服力有:证明者必须在不知道 c 的情况下就锁死 R无:它就是先看答案再出题
产生的记录长什么样一模一样,分布距离 0

说服力不在那三个数里,在它们被产生出来的顺序里。而顺序这件事,是没法记录在纸上的——这就带出了一个非常实际、也非常反直觉的后果:

◆ 一份交互式零知识证明,是不能转给第三方的

Victor 亲自参与了交互,所以他信。但他把这份记录发到网上,说「看,Peggy 证明了她知道私钥」——没有人会信他,因为这份记录他自己就能伪造,五行代码的事。

这个性质叫不可转移性(deniability),它有时是缺点,有时恰恰是卖点

  • 缺点:你想让一份证明被全世界验证(比如放到区块链上),交互式就不行。第 8 章会解决这个问题——代价是把可否认性弄丢。
  • 卖点:Signal、WhatsApp 这类通讯软件刻意保留了这个性质。你能确认消息是对方发的,但你没法向别人证明这一点——因为那份记录你自己也能造。「我能确信,但我没法举报你」,这是一个刻意的设计选择。
✎ 术语正名

「一模一样」有三个强度,工程上要分清:

  • 完美零知识:两个分布严格相等。上面那个 121 vs 121 就是。
  • 统计零知识:两个分布的总变差距离小到可忽略(比如 2⁻¹²⁸)。再强的算力也分不出来。
  • 计算零知识:两个分布可能差很远,但没有多项式时间的算法能分辨。今天几乎所有实用系统都在这一档。

还有一个隐藏在定义里的关键限定:上面证的其实是 honest-verifier 零知识——假设 Victor 老老实实地随机抛 c。如果 Victor 使坏(比如把 c 挑成和 R 有关的某个值),需要额外的构造才能保证仍然零知识。这个「诚实验证者」的前提,在很多论文的定理里藏得很深,读的时候要专门找。

⌨ 自己跑一遍

这一章的核心结论可以被完全穷举,所以值得亲手数一遍。二十行:

from collections import Counter

p, q, g = 23, 11, 2          # 模 23 的 11 阶子群
x = 6                        # ⟦ 秘密 ⟧
P = pow(g, x, p)

real, sim = Counter(), Counter()

for k in range(q):                       # 真证明者:遍历所有 (k, c)
    for c in range(q):
        R = pow(g, k, p)
        s = (k + c * x) % q
        real[(R, c, s)] += 1

inv_P = pow(P, -1, p)
for s in range(q):                       # 模拟器:遍历所有 (s, c),不碰 x
    for c in range(q):
        R = pow(g, s, p) * pow(inv_P, c, p) % p
        sim[(R, c, s)] += 1

total = sum(real.values())
keys = set(real) | set(sim)
tv = sum(abs(real[k] - sim[k]) for k in keys) / (2 * total)

print('真   %d 条,其中互不相同 %d 条' % (total, len(real)))
print('模拟 %d 条,其中互不相同 %d 条' % (sum(sim.values()), len(sim)))
print('总变差距离 %.10f' % tv)
print('每条两边各出现一次?', all(real[k] == 1 and sim[k] == 1 for k in keys))
真   121 条,其中互不相同 121 条
模拟 121 条,其中互不相同 121 条
总变差距离 0.0000000000
每条两边各出现一次? True

注意模拟器那段代码里没有出现 xx 改成任何别的值(0 到 10),real 那一半会变,sim 那一半也会跟着变(因为 P 变了),而两者始终相等——这正是「无论秘密是什么,看到的东西都一样」。

python3 -c " p,q,g,x=23,11,2,6; P=pow(g,x,p); iP=pow(P,-1,p) a={(pow(g,k,p),c,(k+c*x)%q) for k in range(q) for c in range(q)} b={(pow(g,s,p)*pow(iP,c,p)%p,c,s) for s in range(q) for c in range(q)} print(len(a), len(b), a==b)"

在线跑:python.org/shell。最后那行直接把两个集合判等,输出 121 121 True

▸ 在现实里
  • 为什么密码登录不是零知识。你把密码发给服务器,服务器拿到的东西它自己造不出来——它现在真的知道你的密码了。这就是为什么撞库能成立:一个网站泄露的密码,在另一个网站也能用。零知识版本的登录协议是存在的(SRP、OPAQUE),服务器全程拿不到密码,可惜部署率极低——原因不是技术,是生态惯性。
  • 可否认性是通讯软件的一个真实卖点。PGP 签名的邮件不可否认:你签了,全世界都能验,包括法庭。而 Signal 刻意用了一种「双方都能伪造记录」的认证方式,于是聊天记录截图在密码学上不构成任何证据。这不是 bug,是明确写在协议设计目标里的。
  • 「我不看,所以我不知道」在合规上是有价值的。模拟器思想的现实类比是信息隔离:如果一个部门能证明「我们收到的东西,我们不接触业务也能自己生成一份一模一样的」,那它就没有内幕信息。零知识给了这个直觉一个精确的形式。
  • 反面:一个「零知识」系统泄露信息的最常见方式,不是协议本身。是时间(你什么时候提交的证明)、是大小(证明多长)、是元数据(谁在和谁交互)。第 19 章会给出一个数字:协议本身完美零知识的混币池,因为「你存完 10 分钟就取了」,有效匿名集从 1000 掉到 1.6。
✗ 这个直觉是错的

「既然模拟器能造出一模一样的记录,那这个证明系统不就被攻破了吗?骗子照着模拟器做不就行了。」

骗子确实能造出一份看起来完美的记录,但他造不出一次真实的交互。区别在于:模拟器需要先知道 c 才能定 R,而在真交互里 R 必须先交出去、c 才出现。他能伪造历史,但没法预测未来。

这是这本书里反复出现的同一个支点,第 4 章叫它「先钉死再挑战」。零知识和可靠性这两条看起来打架的性质,是靠「顺序」这一根柱子同时撑住的:因为记录本身没有信息(零知识),也因为顺序没法伪造(可靠性)。

顺带说一个更微妙的后果:一旦你用第 8 章那招把协议变成非交互的,「顺序」就必须由别的东西来保证——那时它由哈希函数的不可预测性来保证。而第 9 章会展示,那个哈希只要少放一个参数,这根柱子就断了,作弊者当场恢复「先看题再答」的能力,通过率回到 100%。

✓ 结账

这一章的一句话

「什么也没学到」被翻译成了一个可以用代码穷举的陈述:一个完全不知道秘密的程序,能产生分布完全相同的对话记录;于是说服力就从「记录的内容」里被彻底剥离出来,只剩下「记录被产生的顺序」。

但「顺序」需要 Victor 本人在场抛骰子,这很麻烦:他得在线,他得可信,而且这份证明只对他一个人有效。下一章用一招把 Victor 整个删掉——让证明者自己抛骰子,但用一种他没法作弊的方式。来回次数从 2 变成 0,证明变成一个 64 字节的文件,谁都能验。顺带你会发现:你每天在用的数字签名,本来就是这么一份零知识证明,只是从来没人这样介绍过它。