区块链中的数学 - sigma协议与Fiat-Shamir变换

写在前面

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

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

Sigma协议9

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

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

P和V交互过程为：

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

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

举例说明

以指数运算为例， p为素数，q为p − 1,的最大素数因子，g 为$Z^*_p$ 中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 $, 即$ 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

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

相关阅读

区块链中的数学 - 何谓零知识证明?零知识证明的概念及性质

区块链中的数学 - RSA累加器的非成员证明 RSA Accumulator非成员证明

区块链中的数学 - Accumulator(累加器) 累加器与RSA Accumulator

区块链中的数学 - Kate承诺batch opening Kate承诺批量证明

区块链中的数学 - 多项式承诺 多项式知识和承诺

区块链中的数学 - Pedersen密钥共享 Pedersen 密钥分享

区块链中的数学 - Pedersen承诺 密码学承诺--Pedersen承诺

区块链中的数学 - 不经意传输 不经意传输协议

区块链中的数学 - RSA算法加解密过程及原理 RSA加解密算法

区块链中的数学 - BLS门限签名 BLS m of n门限签名

区块链中的数学 - BLS密钥聚合 BLS密钥聚合

Schorr签名与椭圆曲线 Schorr签名与椭圆曲线

区块链中的数学-Uniwap自动化做市商核心算法解析 Uniwap核心算法解析（中）