区块链原理 / 系统课时

用随机挑战限制伪造成功率

用随机挑战限制伪造成功率

随机挑战让证明者必须在不知道验证者会提出什么问题的情况下提前作出承诺。本篇通过二选一挑战、挑战空间扩展和多轮重复三个算例,计算作弊者的成功概率,并说明为什么随机性、协议结构和安全假设必须同时成立。

学习目标

  • 解释随机挑战为什么能限制不诚实证明者的成功概率。
  • 根据挑战空间大小和重复轮数计算可靠性界限。
  • 区分理论挑战概率、随机数质量和协议实现中的安全风险。

随机挑战为什么能约束作弊者

考虑一个交互式证明:证明者声称知道某个公开问题的秘密解,但不能直接公开秘密。验证者希望通过提问判断这一声明是否可信。

一种典型设计采用三步交互:

  1. 证明者先发送承诺 aa,此时不知道验证者接下来选择哪个问题。
  2. 验证者从规定的挑战集合中随机抽取 cc,发送给证明者。
  3. 证明者返回响应 zz,验证者检查 V(x,a,c,z)=1V(x,a,c,z)=1 是否成立,其中 xx 是公开声明。

三步交互式证明的消息时序

关键约束是先承诺、后挑战。如果一个作弊者没有秘密解,且对于同一个承诺最多只能回答两个挑战中的一个,那么随机挑战就会使它面临失败风险。

例如,挑战集合为 C={0,1}C=\{0,1\},验证者均匀抽样。作弊者提前准备了挑战 00 的有效响应,却无法回答挑战 11,那么:

P(作弊成功)≤12P(\text{作弊成功})\leq\frac{1}{2}

这不是所有零知识证明都天然满足的结论。它依赖具体协议的可靠性性质:在选定承诺后,不知道有效秘密的证明者不能同时正确应对两个不同挑战,或者同时应对将导致秘密可被提取。

挑战空间决定单轮成功上界

假设挑战集合大小为 NN,每个挑战被均匀选中的概率为 1/N1/N。对于某个固定承诺,如果作弊者最多可以有效回答其中 kk 个挑战,那么单轮成功概率满足:

Psuccess≤kNP_{\text{success}}\leq\frac{k}{N}

例如,挑战空间有 1616 种可能,作弊者只能回答其中一种,则成功概率不超过 1/16=6.25%1/16=6.25\%。

挑战总数 NN 可回答数量 kk 单轮成功概率上界
2 1 50%
8 1 12.5%
16 1 6.25%
16 4 25%

表格说明:仅增加挑战数量还不够。如果作弊者能够回答的挑战数量也增加,安全收益就可能很小。

对实际的 Sigma 协议,经常可以通过特殊可靠性说明:两个具有相同承诺、不同挑战且都被接受的响应,可以被提取器用于恢复见证。在适当的协议及知识可靠性假设下,这有助于建立类似 1/N1/N 的单轮知识错误界限;但不能仅根据挑战位数就断言整个证明系统达到同等安全级别。

此外,均匀性不能省略。如果验证者以 90%90\% 的概率选择 00,以 10%10\% 的概率选择 11,作弊者总是准备挑战 00,单轮成功率就可能达到 90%90\%,而不再是 50%50\%。

多轮重复怎样降低成功概率

假设某个协议在任意历史交互条件下,每轮作弊成功的条件概率都不超过 pp,并且验证者每轮重新生成不可预测的随机挑战。要让整份证明通过,作弊者必须连续通过全部 rr 轮。

利用条件概率的连乘规则,可以得到:

P(全部通过)≤prP(\text{全部通过})\leq p^r

以每轮上界 p=1/2p=1/2 为例:

重复轮数 rr 全部通过的概率上界
1 1/2=50%1/2=50\%
5 1/32=3.125%1/32=3.125\%
10 1/1024≈0.0977%1/1024\approx0.0977\%
20 1/1048576≈0.0000954%1/1048576\approx0.0000954\%
40 2−402^{-40},约为 9.09×10−139.09\times10^{-13}

假设希望理论作弊成功概率不超过 2−202^{-20},且每轮上界为 1/21/2,则至少需要 2020 轮。更一般地,当 0<p<10<p<1 时,需要满足:

r≥⌈log⁡εlog⁡p⌉r\geq\left\lceil\frac{\log\varepsilon}{\log p}\right\rceil

其中 ε\varepsilon 是允许的作弊成功概率上界。

独立随机挑战下的多轮重复与概率下降

这里不能把“使用了多轮”直接等同于“概率可以相乘”。如果后续挑战可由前面的挑战预测,或者重复过程错误地复用了可被利用的状态,那么每轮的条件成功概率可能不再受原来的 pp 约束。

随机性与协议结构怎样影响安全性

挑战协议能否达到计算出的上界,需要同时检查三个方面。

挑战生成: 验证者应使用适合密码学用途的随机数生成器,保证挑战难以提前预测。不能用固定种子、系统时间的简单变换或可预测序列代替。对于大小不是二的幂的挑战集合,还应避免直接取模产生明显偏差;可以采用拒绝采样等方法获得均匀分布。

消息顺序: 验证者必须在收到并固定承诺后产生挑战。如果证明者能在看到挑战后更换承诺,前面的成功率分析就可能失效。协议还应明确消息编码、轮次绑定和会话边界,避免不同会话的消息被错误拼接。

数学假设: 证明系统必须具有相应的可靠性或知识可靠性论证。挑战的不可预测性只提供随机检验机制,不能代替协议底层的代数性质、计算困难假设或提取器分析。

例如,一个有缺陷的验证算法无论输入什么响应都返回通过。即使挑战长达 256256 位、重复 100100 轮,作弊成功概率仍然是 100%100\%。这说明安全上界首先要由协议结构证明,再根据挑战分布计算。

从交互式挑战走向链上证明

链上验证通常希望验证者只检查一份证明,而不必与证明者往返多轮。因此,一些证明系统采用 Fiat–Shamir 变换,用密码学哈希函数根据公开上下文和承诺生成挑战。

例如,将协议标识、公开声明和承诺进行无歧义编码后计算哈希,再按协议规定映射到挑战集合。验证者会独立重算挑战,并检查响应。这样能够把特定形式的交互式公币协议转换为非交互式证明。

这里的安全论证通常依赖随机预言机模型或其他明确条件,不能认为哈希函数与真正的在线随机验证者在所有协议里完全等价。尤其需要保证输入编码无歧义、挑战绑定正确的公开声明,并考虑证明者反复尝试承诺以寻找有利哈希输出的能力。

可以用以下检查题检验理解:某协议每轮有 88 个等概率挑战,且对任意固定承诺,作弊者最多能回答一个挑战。重复 44 轮,并保证每轮条件成功率都不超过 1/81/8,那么整体作弊成功概率上界为:

(18)4=14096≈0.0244%\left(\frac{1}{8}\right)^4=\frac{1}{4096}\approx0.0244\%

这个结果只衡量上述假设下的可靠性错误,不等于协议的完整安全级别,更不能据此推断零知识性、抗量子安全性或智能合约实现安全。实际设计中应先证明每轮上界,再检查挑战来源、重复方式与链上验证实现是否保持这些前提。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用随机挑战限制伪造成功率

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通