这篇文章上次修改于 258 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
zk-Sigma
知道 1 个秘密 $w$
椭圆曲线生成元为 $G$ ，群的阶为 $| F_r |$ ；标量域为 $F_r$ ，基域为 $F_q$
知道秘密 $w$，且与公开输入 $Q$ 满足离散对数关系 $Q = w \cdot G$
交互式版：
- （承诺）P 选择随机数 $r$，计算 $A = r \cdot G$，发送 A
- （挑战）V 发送随机数 $e$
- （响应）P 计算 $z=r + e \cdot w$，发送 $z$
- （验证）V 校验 $z \cdot G == A + e \cdot Q$
非交互式 A 版：发送承诺和响应（数据量较大）。挑战的计算：$e=hash(Q,A)$，要求哈希函数是抗碰撞的
非交互式 B 版：发送挑战和响应（数据量较小）。由验证方重新自己重新计算承诺 $A=z \cdot G - e \cdot Q$，然后哈希校验 $e == hash(Q, A)$
知道 2 个秘密 $s, l$
椭圆曲线生成元为 $G$ ，群的阶为 $| F_r |$ ；标量域为 $F_r$ ，基域为 $F_q$
用户秘密为 $s, l, \rho$，与公开输入为 $G, V, R$，满足离散对数关系 $V = s \cdot R + l \cdot G$
- （承诺）P 选择随机数 $a, b \in F_r$，计算 $H = a \cdot G + b \cdot G$，发送 A
- （挑战）V 发送随机数 $c = Hash(G, V, R, H)$ mod $F_r$
- （响应）P 计算 $t=a + c \cdot s$ mod $|F_r|$，$u = b + c \cdot l$ mod $|F_r|$，发送 $(H, t, u)$
（验证）V 计算 $c$，校验 $t \cdot R + u \cdot G == H + c \cdot V$
推导：$t \cdot R + u \cdot G =(a + c \cdot s) \cdot R + (b + c \cdot l) \cdot G = H + c \cdot V$
证明两个值相等
确保：支付方都减少额 == 接收方的增加额
背景
素数群 $G$ 的阶为 $q$，生成元为 $g$
Alice/Bob/Carol 私钥和公钥分别为
Alice：$(\alpha_1, g_1), g_1=g^{\alpha_1}$
Bob：$(\alpha_2, g_2), g_2=g^{\alpha_2}$
Carol：$(\alpha_3, g_3), g_3=g^{\alpha_3}$
余额初始状态：
- Alice 余额为 $m_0$，选择随机数 $r_0 \in Z_q$，可得到密文 $[C_0, D_0]$，其中 $C_0=g^{r_0}, \space D_0=g^{m_0} \cdot g_1^{r_0}$
- Bob 余额为 $m_0'$，选择随机数 $r_0' \in Z_q$，可得到密文 $[C_0', D_0']$，其中 $C_0'=g^{r_0'}, \space D_0'=g^{m_0'} \cdot g_2^{r_0'}$
- Carol 余额为 0
Alice 支付给 Carol 金额数量为 $m_1$，选择随机数 $r_1,r_1' \in Z_q$，基于 ElGamal 同态加密生成密文 $[C_1, D_1], [C_1', D_1']$
$$ \begin{align} &C_1=g^{r_1}, \space D_1=g^{m_1} \cdot g_3^{r_1} \\ &C_1'=g^{r_1'}, \space D_1'=g^{m_1'} \cdot g_3^{r_1'} \\ \end{align} $$
需要使用零知识证明 $m_1 = m_1'$ 且知道 $r_1,r_1',m_1,m_1'$
Alice 对交易签名，矿工验证签名、零知识和范围证明后
- 更新 Carol 金额为 $[C_1,D_1]$，Carol 可解密获得金额 $g^{m_1}=D_1/(C_1)^{\alpha_3}$，然后暴力搜索 $m_1$
- 更新 Alice 金额为 $[C_0/C_1',D_0/D_1']$，Alice 可解密获得金额 $g^{m_0-m_1'}=(D_0/D_1')/(C_0/C_1')^{\alpha_1}$
证明
为了避免暴露 $m_1$ 或 $m_1'$，可选择随机数 $m_1''$ 作为输入
承诺：选择 2 个随机数 $r_1'', r_1''' \in Z_q$ 和随机数 $m_1''$，构造 2 个密文
$$ \begin{align} &C_1''=g^{r_1''}, \space D_1''=g^{m_1''} \cdot g_3^{r_1''} \\ &C_1'''=g^{r_1'''}, \space D_1'''=g^{m_1''} \cdot g_3^{r_1'''} \\ \end{align} $$
挑战：计算哈希值 $e=hash(g_1, g_3, C_1, D_1, C_1', D_1', C_1'', D_1'',C_1''', D_1''')$
响应：计算 $z_1=r_1'' + e \cdot r_1, \space z_2=r_1'''+e \cdot r_1', \space \hat{m}=m_1'' + e \cdot m_1$
发送数据：$Proof(C_1'', D_1'', C_1''', D_1''', z_1, z_2, \hat{m})$
验证：计算哈希值 $e=hash(g_1, g_3, C_1, D_1, C_1', D_1', C_1'', D_1'',C_1''', D_1''')$，校验以下 4 个等式
$$ \begin{align} C_1^e \cdot C_1'' = g^{z_1}, \space D_1^e \cdot D_1'' = g^{\hat{m}} \cdot g_3^{z_1} \\ C_1'^e \cdot C_1''' = g^{z_2}, \space D_1'^e \cdot D_1''' = g^{\hat{m}} \cdot g_1^{z_2} \\ \end{align} $$
推导
$$ \begin{align} &C_1^e \cdot C_1'' = g^{er_1} \cdot g^{r_1''}= g^{z_1}\\ &D_1^e \cdot D_1'' = g^{em_1} \cdot g_3^{er_1} \cdot g^{m_1''} \cdot g_3^{r_1''} = g^{em_1+m_1''} \cdot g_3^{er_1+r_1''} = g^{\hat{m}} \cdot g_3^{z_1} \\ & C_1'^e \cdot C_1''' = g^{er_1'} \cdot g^{r_1'''}=g^{z_2} \\ &D_1'^e \cdot D_1''' = g^{em_1'} \cdot g_3^{er_1'} \cdot g^{m_1''} \cdot g_3^{r_1'''} = g^{em_1'+m_1''} \cdot g_3^{er_1'+r_1'''} = g^{\hat{m}} \cdot g_3^{z_2} \\ \end{align} $$
两个验证中，$\hat{m}$ 对应 $m_1$ 和 $m_1'$，响应中的 $\hat{m}$ 也对应 $m_1$ 和 $m_1'$，因此 $m_1=m_1'$
zk-Schnorr
A 版
zk-Schnorr 证明知道 ECC 私钥
椭圆曲线生成元为 $G$ ，群的阶为 $| F_r |$ ；标量域为 $F_r$ ，基域为 $F_q$
证明方的私钥为 $sk$ ，公钥为 $PK$ ，满足离散对数关系 $PK = sk \cdot G$
- （承诺）选择随机数 $r \in F_r$ ，计算 $R = r \cdot G$
- （挑战）计算随机数 $c = hash ( PK , R )$ mod $| F_r |$
- （响应）计算 $z = r + c \cdot sk$ mod $| F_r |$ ，发送 $( R , z ) $
- （验证）计算随机数 $ c = hash ( PK , R )$ mod $| F_r |$ ，校验 $z \cdot G = R + c \cdot PK $
公式推导：$z \cdot G = ( r + c \cdot sk ) \cdot G = R + c \cdot PK$
B 版
- （承诺）选择随机数 $r \in F_r$ ，计算 $R = r \cdot G$
- （挑战）计算随机数 $c = hash ( PK , R )$ mod $| F_r |$
- （响应）计算 $z = r + c \cdot sk$ mod $| F_r |$ ，发送 $( c , z ) $
- （验证）计算 $R = z \cdot G - c \cdot PK$，校验 $c == hash(PK, R)$ mod $|F_r|$
没有评论