Sigma零知识证明，知道秘密$\omega$，且与公开输入$Q$满足离散对数关系$Q=\omega G$

Sigma零知识证明协议

设关系$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。

   例子

1）P计算$h=g^xmod\ p$作为秘密

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

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

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

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

正确性(completeness)

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

公平性(special soundness)

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

零知识性 (special honest verifier zk)

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

sigma协议又称为诚实验证者的（特殊）零知识证明。即假设验证者是诚实的

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

该算法允许将交互步骤中随机挑战替换为非交互随机数预言机（Random oracle）。

1）P计算$h=g^xmod\ p$作为秘密

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

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

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

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

Sigma协议应用到ElGamal同态加密

同态密文运算

密钥生成：A,B,C,D的私钥和公钥分别是：

$A:(\alpha_1,g_1),g_1=g^{\alpha_1}\\ B:(\alpha_2,g_2),g_2=g^{\alpha_2}\\ C:(\alpha_3,g_3),g_3=g^{\alpha_1}\\ D:(\alpha_4,g_4),g_4=g^{\alpha_2}\\$

余额初始状态：

• A余额初始状态密文为$[C_0,D_0]$，其中$C_0=g^{r_0},D_0=g^{m_0}g_1^{r_0}$

• B余额初始状态密文为$[C_0^{\prime},D_0^{\prime}]$，其中$C_0^{\prime}=g^{r_0^{\prime}},D_0^{\prime}=g^{m_0^{\prime}}g_1^{r_0^{\prime}}$

• C,D起始状态金额为0

A支付给C金额数量为$m_1$，使用ElGamal同态加密生成密文$[C_1,D_1],[C_1^{\prime},D_1^{\prime}]$并生成零知识证明$zkProof$和范围证明$BulletProof$

• A选择随机数$r_1$，基于C的公钥$g_3$，生成$[C_1,D_1]$
• A选择随机数$r_1$，基于自己的公钥$g_1$，生成$[C_1^{\prime},D_1^{\prime}]$

$C_1=g^{r_1},\ D_1=g^{m_1}g_3^{r_1}\\ C_1^{\prime}=g^{r_1^{\prime}},D_1^{\prime}=g^{m_1^{\prime}}g_3^{r_1^{\prime}}\\ ZK\{r_1,r_1^{\prime},m_1,m_1^{\prime},m_1=m_1^{\prime}|C_1,D_1,C_1^{\prime},D_1^{\prime}\}\\ BulletProof\{0\le m_0-m_1\le2^{32},0\le m_1\le2^{32} \}$

A对交易单签名;矿工验证签名、零知识证明和范围证明。然后:

• 更新C金额记作$[C_1,D_1]$，则C能够解密获得$m_1$并进行支付，解密过程：$g^{m_1}=D_1/(C_1)^{\alpha_3}$
• 更新A的金额状态记为$[C_0/C_1^{\prime},D_0/D_1^{\prime}]$，则A能过够解密获得$m_0-m_1$并进行支付。解密过程：$g^{m_0-m_1^{\prime}}=(D_0/D_1^{\prime})/(C_0/C_1^{\prime})^{\alpha_1}$

C余额增加$m_1$，A余额减少$m_1^{\prime}$

B支付给C金额为$m_2$，使用ElGamal同态加密生成密文$[C_2,D_2],[C_2^{\prime},D_2^{\prime}]$，并生成零知识证明$zkProof$和范围证明$BulletProof$

$C_2=g^{r_2},\ D_2=g^{m_2}g_3^{r_2}\\ C_2^{\prime}=g^{r_2^{\prime}},D_2^{\prime}=g^{m_2^{\prime}}g_3^{r_2^{\prime}}\\ ZK\{r_2,r_2^{\prime},m_2,m_2^{\prime},m_2=m_2^{\prime}|C_2,D_2,C_2^{\prime},D_2^{\prime}\}\\ BulletProof\{0\le m_0-m_2\le2^{32},0\le m_2\le2^{32} \}$

B对交易单签名;矿工验证签名、零知识证明和范围证明。然后:

• 更新C金额记作$[C_1C_2,D_1D_2]$，则C能够解密获得$m_1+m_2$并进行支付，解密过程：$g^{m_1+m_2}=D_1D_2/(C_1C_2)^{\alpha_3}$
• 更新A的金额状态记为$[C_0/C_2^{\prime},D_0/D_2^{\prime}]$，则A能过够解密获得$m_0^{}\prime-m_2$并进行支付。解密过程：$g^{m_0^{\prime}-m_2^{\prime}}=(D_0^{\prime}/D_2^{\prime})/(C_0/C_2^{\prime})^{\alpha_2}$

C支付给D金额数量为$m_3$，使用ElGamal同态加密生成密文$[C_3,D_3],[C_3^{\prime},D_3^{\prime}]$，并生成零知识证明$zkProof$和范围证明$BulletProof$

$C_3=g^{r_3},\ D_3=g^{m_3}g_4^{r_3}\\ C_3^{\prime}=g^{r_3^{\prime}},D_3^{\prime}=g^{m_3^{\prime}}g_3^{r_3^{\prime}}\\ ZK\{r_3,r_3^{\prime},m_3,m_3^{\prime},m_3=m_3^{\prime}|C_3,D_3,C_3^{\prime},D_3^{\prime}\}\\ BulletProof\{0\le m_1+m_2-m_3\le2^{32},0\le m_3\le2^{32} \}$

C对交易单签名;矿工验证签名、零知识证明和范围证明。然后:

• 更新C金额记作$[C_1C_2/C_3^{\prime},D_1D_2/D_3{\prime}]$，则C能够解密获得$m_1+m_2-m_3$并进行支付，解密过程：$g^{m_1+m_2-m_3}=(D_1D_2/D_3^{\prime})/(C_1C_2/C_3)^{\alpha_3}$
• 更新A的金额状态记为$[C_3,D_3]$，则A能过够解密获得$m_3$并进行支付。解密过程：$g^{m_3}=(D_3)/(C_3)^{\alpha_4}$

Sigma 零知识证明确保：支付方的减少额 == 接收方的增加额。