区块链中的数学（七十四）--sigma协议与Fiat-Shamir变换

blocksight 2021-05-06 23:08:07 阅读数:455

本文一共[544]字，预计阅读时长:1分钟~

协议区块数学七十四 sigma

写在前面

上一篇介绍了零知识证明的概念及性质，没有举常见的数独，地图染色的例子，这些可以自行搜索了解，

本文继续讲sigma协议，具备一定零知识性质的协议！

Sigma协议9

设关系 $R\subseteq X * Y$, 那么<P, V> 构建在R上的一个Sigma 协议为：

P是一个叫证明的交互式协议，其输入为一个witness-statement对(x,y) R.V是一个叫验证的交互式协议，其输入为一个statement，y R.

P和V交互过程为：

首先，P计算一个承诺(commitment) t ，将其发送给V；
在收到来自P的消息后，V在有限的挑战空间C中随机选取一个挑战元素(challenge) c，并将其发送给P ；
在接收到来自V的挑战后， P计算出一个反馈(response) z ,将其发送给V
在收到了来自P的反馈后, V输出accept或者reject。

抽象定义往往让人费解，举例说明！

举例说明

以指数运算为例， p为素数，q为p − 1,的最大素数因子，g 为中order为q的元素，某x是P的秘密，详细流程：1）P计算 $h =g^x mod p$, 作为承诺给V

2）P选择随机数$r ∈ z_q $，计算$a = g^r mod p$, P将a值发送给V

3） V选择随机数challenge e，V将e值发送给P；

4） P计算$z = r + ex mod q$, 将z值发送给V，

5） V判断 $g^z=? =ah^e mod p$是否成立，若成立，则V接受认为P确实知道正确的x.

sigma协议又称为诚实验证者的（特殊）零知识证明。即假设验证者是诚实的。这个例子类似Schnorr身份认证协议，只是后者通常采用非交互的方式。

正确性(completeness)

在上面的协议中，正确性意味着如果每个人都遵守协议，那么协议正常执行。在Sigma协议的中，这意味着P和V这么做，V最后应该接受状态。

公平性(special soundness)

公平性意味着P不能证明一个错误的陈述statement. Sigma协议实现公平的。准确地说，特殊公平性！特殊公平性是说，如果P能让V在挑战中找到两个挑战，那么这两个挑战分别是(e,z)和(e′,z′)。通过代数计算【幂除法】可以得到 $𝑑 =(e-e^1)^{-1} $, 即$ x = 𝑑⋅(𝑠 − 𝑠^′)$。这样计算出x那么只能满足其中一个等式。

零知识性 (special honest verifier zk)

V既不能从协议中知道x的值，而且还不能向第三者，证明V知道这个秘密（即V无法冒充P）。也就是V从协议中什么也没学到（除了P知道x之外）。

Fiat-Shamir变换

交互式方式有其应用局限，比如得双方或多方同时在线等。Fiat-Shamir变换，又叫Fiat-Shamir Heurisitc（启发式），或者Fiat-Shamir Paradigm（范式），是Fiat和Shamir在1986年提出的一个变换，其特点是可以将交互式零知识证明转换为非交互式零知识证明。这样就通过减少通信步骤而提高了通信的效率！

该算法允许将交互步骤中随机挑战替换为非交互随机数预言机（Random oracle）。随机数预言机，即随机数函数，是一种针对任意输入得到的输出之间是相互独立切均匀分布的函数。理想的随机数预言机并不存在，通常采用伪随机数（PRNG）在工程代码中，经常采用密码学哈希函数作为随机数预言机。

看下非交互式sigma协议：1）P计算 $h =g^x mod p$, 作为秘密

2）P选择随机数$r ∈z_q$ ，计算$a = g^r mod p$, P将a值发送给V

3）P计算 $e = Hash(h, a)$；

4） P计算$z = r + ex mod q$, 将z值发送给V，

5） V判断 $g^z=? = ah^e mod p$是否成立，同时检验e的哈希结果是否正确，都通过后，则V接受认为P确实知道正确的x.

小结

本文介绍Sigma协议的交互和非交互性质，简单明了，介绍了零知识证明中常用的Fiat-Shamir变换，Sigma协议还有一些变种和用途，下节再说吧！

如果你觉得不够简单明了，说明基础还欠缺，耐心把之前文章看下，合抱之木，生于毫末，百尺之台起于累土！！

参考:https://www.cs.au.dk/~ivan/Sigma.pdf https://www.crypto.ethz.ch/publications/files/CamSta97b.pdf

欢迎关注&在看，疑问请留言！

写在前面

上一篇介绍了RSA Accumulator非成员证明以及区块链中的应用，有些细节没有展开，比如说为什么要使用素因子？因为它们的乘积将唯一地表示集合。否则，会有混淆【同一乘积，会有不同因子组合，如18 = 2 9 = 3 6】等等。

到现在为止，有了签名，密码学承诺，同态计算，椭圆曲线等基础，接下来可以看零知识证明的具体内容了。本篇属于科普，相比以往，愉快阅读不烧脑！

何谓零知识证明

零知识证明通俗来说通过某种手段让验证者相信（确认）证明者的陈诉正确（例如知道某个关键信息），同时不暴露该信息本身。网络上有很多例子可以帮助理解，这里我们举一个场景：假如V捡到一个丢失的银行卡，P过来说银行卡是他的，并说他知晓银行卡卡号和密码，由于银行卡在V手中，V可以轻松判断P说的卡号是否正确，但是V依然不太相信P就是卡的主人，于是P还说知道银行卡的取款密码，但是不能直接告诉V否则的话就泄露了。于是他们约定，来到附近的ATM机旁，V离ATM机保持一定距离，使得能够看得见P执行取款操作，但不能太近以至于看到P输入的取款密码。P就在ATM旁等待V的操作指令。

二人就位后，V让取出100元，P插入卡，输入密码后取出100元（假设卡里确实都是有钱的），V让再取出300元，P照做又一次取出了300元，反复几次后，V确信银行卡就是P的。

P通过这种方式拿到了银行卡，没有让V知道其取款密码，这个模拟的场景就是零知识证明的应用场景了。

用途

零知识证明常用于以下场景：(1）证明隐私数据情况：一个人的银行账户金额多于 X;去年，一家银行未与实体 Y 进行交易;一个人的信用评分高于 Z;在不暴露全部 DNA 数据的前提下匹配 DNA

(2）匿名认证：在不揭露身份的情况下（比如登录密码），证明请求者R有权访问网站的受限区域;证明一个人来自一组被允许的国家/地区列表中的某个国家/地区，但不暴露具体是哪个;证明一个人是某机构会员但不是是谁。（3）匿名支付/代币：区块链中的（不可追踪的）隐私币; 付款完全脱离任何一种显示身份;纳税而不透露收入;

（4）外包计算将昂贵的计算任务外包，并在不重新执行的情况下验证计算结果是否正确；它打开了一种零信任计算的类别；改进区块链模型，从所有节点做同样的计算，到只需一方计算然后其它节点进行验证等，zk rollup layer2方案等。

ZK-SNARK

自1985 年，零知识证明这个概念在 “交互式证明系统的知识复杂性”一文中被引入，后来包括非交互式研究，近几年在区块链的研究与应用发展迅速。零知识证明系统要满足以下性质。

完整性: 只要陈述(statement)是正确的，prover 就可以让 verifier 确信;
可靠性: 如果陈述(statement)是错误的，那么作弊的 prover 就没有办法让 verifier 相信
零知识: 协议的交互仅仅揭露陈述(statement)是否正确而不泄漏任何其它的信息

目前成熟应用是zk-SNARK技术方案。这个术语含义：

ZK-SNARK全称:zero-knowledge succinct non-interactive arguments of knowledge

Succint (简洁性) :与实际计算的长度相比，生成的零知识证据消息很小。

Non-interactive (非交互性) :对于 zk-SNARK 算法来说，通常有一个构建阶段，构建阶段完成之后，证明者 (prover) 只需向验证者 (verifier) 发送一个消息即可。而且，SNARK 通常还有一个被称作是 "公开验证者" 的特性，意味着任何人无需任何交互即可验证零知识证据，这对区块链是至关重要的。

Arguments (争议性) :验证者只能抵抗计算能力有限的证明者的攻击。具有足够计算能力的证明者可以创建伪造的零知识证据以欺骗验证者。这也通常被称为 "计算完好性 (computational soundness)"，而不是 "完美完好性 (perfect soundness) "。

of Knowledge :对于一个证明者来说，在不知晓特定证明 (witness) 的前提下，构建一个有效的零知识证据是不可能的。

小结

在任意的零知识证明系统中，都有一个 prover 在不泄漏任何额外信息的前提下要让 verifier 确信某些陈述（Statement）是正确的。

ZK-SNARK目前应用较多，有不少成熟的库，如libsnark,bellman等.也有不需要setup的zk-stark的方案，以后有时间再说吧。

好了，下一篇继续介绍零知识证明其他内容！。

原文链接：https://mp.weixin.qq.com/s/LHuRAA1RPzbccKHZ1wdU6g欢迎关注公众号：blocksight